Re: [PATCH 5/6] btrfs: only copy dir index keys when logging a directory

On Mon, Oct 25, 2021 at 05:01:12PM +0100, Filipe Manana wrote:

On Mon, Oct 25, 2021 at 4:36 PM Josef Bacik [off-list ref] wrote:

quoted

On Mon, Oct 25, 2021 at 10:56:25AM +0100, fdmanana@kernel.org wrote:

quoted

From: Filipe Manana <redacted>

Currently, when logging a directory, we copy both dir items and dir index
items from the fs/subvolume tree to the log tree. Both items have exactly
the same data (same struct btrfs_dir_item), the difference lies in the key
values, where a dir index key contains the index number of a directory
entry while the dir item key does not, as it's used for doing fast lookups
of an entry by name, while the former is used for sorting entries when
listing a directory.

We can exploit that and log only the dir index items, since they contain
all the information needed to correctly add, replace and delete directory
entries when replaying a log tree. Logging only the dir index items is
also backward and forward compatible: an unpatched kernel (without this
change) can correctly replay a log tree generated by a patched kernel
(with this patch), and a patched kernel can correctly replay a log tree
generated by an unpatched kernel.

This took me a very long time to grok, so it deserves more explanation.

The problem I had was how this worked in general, and I was missing the fact
that we're only calling drop_dir_item() if we find the name in the root,
otherwise we either goto insert if we're DIR_INDEX or bail if we're DIR_ITEM.

So whichever we find first in the log, we call drop_dir_item() only if there's a
conflict.  Then the heavy work is done once we find the DIR_INDEX item.

Which means that the only work we do if we find DIR_ITEM is drop_dir_item(),
which we do in the case if we find DIR_INDEX and the item is there.

This is why we don't actually need the DIR_ITEM to properly replay the log for
older kernels, because DIR_INDEX does the same work, and actually does the heavy
lifting of adding the BACKREF's and such.

This took probably 30-45 minutes for me to work out, and I'm only 90% sure I
have it right, so an explanation as to why it's ok for older kernels would be
very helpful.  Thanks,

Is the following fine for you?

The backward compatibility is ensured because:

1) For inserting a new dentry: a dentry is only inserted when we find a
   new dir index key - we can only insert if we know the dir index offset,
   which is encoded in the dir index key's offset;

2) For deleting dentries: during log replay, before adding or replacing
   dentries, we first replay dentry deletions. Whenever we find a dir item
   key or a dir index key in the subvolume/fs tree that is not logged in
   a range for which the log tree is authoritative, we do the unlink of
   the dentry, which removes both the existing dir item key and the dir
   index key. Therefore logging just dir index keys is enough to ensure
   dentry deletions are correctly replayed;

3) For dentry replacements: they work when we log only dir index keys
   and this is due to a combination of 1) and 2). If we replace a
   dentry with name "foobar" to point from inode A to inode B, then we
   know the dir index key for the new dentry is different from the old
   one, as it has an index number (key offset) larger than the old one.
   This results in replaying a deletion, through replay_dir_deletes(),
   that causes the old dentry to be removed, both the dir item key and
   the dir index key, as mentioned at 2). Then when processing the new
   dir index key, we add the new dentry, adding both a new dir item key
   and a new index key pointing to inode B, as stated in 1).

Yup this works for me, thanks,

Josef