Hi Jan, >> # I saw that slot==0 is special. My understanding is that btrfs >> maintains the property that the parent of each node/leaf has a key >> pointing to that node/leaf, which must be equal to the key in the >> slot==0 of this node/leaf. That's what fixup_low_keys() tries to >> maintain. Is this correct? > > Yes. I'm not 100% sure if the key in the parent node must match exactly > the first key of the child node. It is probably allowed that it's less > or equal than the first key. It is guaranteed to be larger than the > largest of the previous (left) node, though. > > And yes, that's what fixup_low_keys is correcting. > >> # If my understanding in the previous bullet is correct: Is that the >> reason that in btrfs_prev_leaf() it is assumed that if there is a >> lesser key, btrfs_search_slot() will never bring us to the slot==0 of >> the current leaf? > > It's quite straight: We look for a key smaller than the first (slot 0) > of the current leaf. If we find the current leaf again (because > btrfs_search_slot returns the place where such a key would have be > inserted), then there's no previous leaf. No preconditions or > assumptions on nodes in levels needed. Let's say that slot[0] of the current leaf (A) has key=10. And let's say that its parent node (N) has key=5 (and not 10). Let's say we have a previous leaf (B), whose last slot has key=2. If such tree is valid, then: btrfs_prev_leaf() will search for key==9. Then btrfs_search_slot() would bring us node N and leaf A again, wouldn't it? Because key(N)<=9. So we will receive leaf A back, and will think that there is no previous leaf, while there is. What am I missing here? Thanks for your help, Alex. -- 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
