On Wed, Jul 4, 2012 at 9:13 PM, Alex Lyakas
<alex.bolshoy.btrfs@xxxxxxxxx> wrote:
> Hi Alex,
>
>> +static int tree_compare_item(struct btrfs_root *left_root,
>> + struct btrfs_path *left_path,
>> + struct btrfs_path *right_path,
>> + char *tmp_buf)
>> +{
>> + int cmp;
>> + int len1, len2;
>> + unsigned long off1, off2;
>> +
>> + len1 = btrfs_item_size_nr(left_path->nodes[0], left_path->slots[0]);
>> + len2 = btrfs_item_size_nr(right_path->nodes[0], right_path->slots[0]);
>> + if (len1 != len2)
>> + return 1;
>> +
>> + off1 = btrfs_item_ptr_offset(left_path->nodes[0], left_path->slots[0]);
>> + off2 = btrfs_item_ptr_offset(right_path->nodes[0],
>> + right_path->slots[0]);
>> +
>> + read_extent_buffer(left_path->nodes[0], tmp_buf, off1, len1);
>> +
>> + cmp = memcmp_extent_buffer(right_path->nodes[0], tmp_buf, off2, len1);
>> + if (cmp)
>> + return 1;
>> + return 0;
>> +}
> It might be worth to note in the comment, that tmp_buff should be
> large enough to hold the item from the left tree. Can it happen that
> the right tree has a different leafsize?
>
This function is only to be used for for the tree compare function and
there we allocate a buffer of root->leafsize, so definitely all items
should fit. As far as I know, Chris (please correct me if I'm wrong)
once guaranteed that ALL trees in a FS will have the same leaf size
and this will ever be the case.
>> + /*
>> + * Strategy: Go to the first items of both trees. Then do
>> + *
>> + * If both trees are at level 0
>> + * Compare keys of current items
>> + * If left < right treat left item as new, advance left tree
>> + * and repeat
>> + * If left > right treat right item as deleted, advance right tree
>> + * and repeat
>> + * If left == right do deep compare of items, treat as changed if
>> + * needed, advance both trees and repeat
>> + * If both trees are at the same level but not at level 0
>> + * Compare keys of current nodes/leafs
>> + * If left < right advance left tree and repeat
>> + * If left > right advance right tree and repeat
>> + * If left == right compare blockptrs of the next nodes/leafs
>> + * If they match advance both trees but stay at the same level
>> + * and repeat
>> + * If they don't match advance both trees while allowing to go
>> + * deeper and repeat
>> + * If tree levels are different
>> + * Advance the tree that needs it and repeat
>> + *
>> + * Advancing a tree means:
>> + * If we are at level 0, try to go to the next slot. If that's not
>> + * possible, go one level up and repeat. Stop when we found a level
>> + * where we could go to the next slot. We may at this point be on a
>> + * node or a leaf.
>> + *
>> + * If we are not at level 0 and not on shared tree blocks, go one
>> + * level deeper.
>> + *
>> + * If we are not at level 0 and on shared tree blocks, go one slot to
>> + * the right if possible or go up and right.
>> + */
> According to the strategy and to the code later, "left" tree is
> treated as "newer one", while "right" as "older one", correct? Do you
> think it would be more intuitive to make it the other way around,
> although I guess this is a matter of personal taste. I had to draw the
> leafs reversed to keep going:
> R L
> ----- -----
> | | | | | | | |
> ----- -----
>
>
To be honest...I always preferred the way you suggested in the past
when I thought about compares. But for some reason, I didn't even
think about that and just implemented that function in single
flow...it took days until I've even noticed that I swapped left/right
in my head :D I now would like to stay with that, as all the btrfs
send code uses left/right in this way and I never had the problem with
mixing that up again. If people like, I have nothing against changing
that later if someone wants to, but that's nothing I would like to do
myself.
>> + if (advance_left && !left_end_reached) {
>> + ret = tree_advance(left_root, left_path, &left_level,
>> + left_root_level,
>> + advance_left != ADVANCE_ONLY_NEXT,
>> + &left_key);
>> + if (ret < 0)
>> + left_end_reached = ADVANCE;
>> + advance_left = 0;
>> + }
>> + if (advance_right && !right_end_reached) {
>> + ret = tree_advance(right_root, right_path, &right_level,
>> + right_root_level,
>> + advance_right != ADVANCE_ONLY_NEXT,
>> + &right_key);
>> + if (ret < 0)
>> + right_end_reached = ADVANCE;
>> + advance_right = 0;
>> + }
> Do you think it's worth it to put a check/warning/smth before that,
> that either advance_right or advance_left is non-zero, or we have
> reached ends in both trees?
>
>
Having the left or right end reached before the other sides end is
reached is something that is completely normal and expected.
>> + } else if (left_level == right_level) {
> ...
>> + } else if (left_level < right_level) {
>> + advance_right = ADVANCE;
>> + } else {
>> + advance_left = ADVANCE;
>> + }
> Can you pls explain why it is correct?
> Why if we are on lower level in the "newer" tree than we are in the
> "older" tree, we need to advance the "older" tree? I.e., why this
> implies that we are on the lower key in the "older" tree? (And
> vice-versa). I.e., how difference in levels indicates relation between
> keys?
Difference in levels has no relation to the keys. These advances
basically try to keep the two trees positions "in-sync". The compare
always tries to get both trees to a point where they are at the same
level, as only then we can compare keys. Also, the two trees may have
different root levels, this code also handles that case.
>
> Thanks,
> Alex.
Thanks for the review :)
--
To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
