On 2020-02-03 at 21:04:45, Johan Herland wrote: > As noted in the previous commit, the nature of the fanout heuristic > in the notes code causes the exact point at which we increase or > decrease the notes fanout to vary with the objects being annotated. > Since the object ids generated by the test environment are > deterministic (by design), the notes generated and tested by t3305 > are always the same, and we therefore happen to see the same fanout > behavior from one run to the next. > > Coincidentally, if we were to change the test environment slightly > (say by making a test commit on an unrelated branch before we start > the t3305 test proper), we not only see the fanout switch happen at > different points, we also manage to trigger a _bug_ in the notes > code where the fanout 1 -> 0 switch is not applied uniformly across > the notes tree, but instead yields a notes tree like this: > > ... > bdeafb301e44b0e4db0f738a2d2a7beefdb70b70 > bff2d39b4f7122bd4c5caee3de353a774d1e632a > d3/8ec8f851adf470131178085bfbaab4b12ad2a7 > e0b173960431a3e692ae929736df3c9b73a11d5b > eb3c3aede523d729990ac25c62a93eb47c21e2e3 > ... > > The bug occurs when we are writing out a notes tree with a newly > decreased fanout, and the notes tree contains unexpanded subtrees > that should be consolidated into the parent tree as a consequence of > the decreased fanout): > > Subtrees that happen to sit at an _even_ level in the internal notes > 16-tree structure (in other words: subtrees whose path - "d3" in the > example above - is unique in the first nibble - i.e. there are no > other note paths that start with "d") are _not_ unpacked as part of > the tree writeout. This error will repeat itself in subsequent note > trees until the subtree is forced to be unpacked. In t3305 this only > happens when the d38ec8f8 note is itself removed from the tree. > > The error is not severe (no information is lost, and the notes code > is able to read/decode this tree and manipulate it correctly), but > this is nonetheless a bug in the current implementation that should > be fixed. > > That said, fixing the off-by-one error is not without complications: > We must take into account that the load_subtree() call from > for_each_note_helper() (that is now done to correctly unpack the > subtree while we're writing out the notes tree) may end up inserting > unpacked non-notes into the linked list of non_note entries held by > the struct notes_tree. Since we are in the process of writing out the > notes tree, this linked list is currently in the process of being > traversed by write_each_non_note_until(). The unpacked non-notes are > necessarily inserted between the last non-note we wrote out, and the > next non-note to be written. Hence, we cannot simply hold the > next_non_note to write in struct write_each_note_data (as we would > then silently skip these newly inserted notes), but must instead > always follow the ->next pointer from the last non-note we wrote. > (This part is was caught by an existing test in t3304.) I think you have "is was" here. You probably want one or the other. > Cc: Johannes Schindelin <Johannes.Schindelin@xxxxxx> > Cc: Brian M. Carlson <sandals@xxxxxxxxxxxxxxxxxxxx> I generally write my name in lower case, but I think typically we prefer to omit Cc lines in patches (unlike LKML), so it may just be better to remove these lines. > Signed-off-by: Johan Herland <johan@xxxxxxxxxxx> Patch 1 looked good to me. Your explanation here makes sense, but I must admit that I still don't understand this code, so I can't give an outright approval. I do appreciate that it comes with a test, though. I haven't tested, but I expect this series will make Dscho's patch unnecessary, so I'll drop it in my reroll unless one of you tells me to keep it. -- brian m. carlson: Houston, Texas, US OpenPGP: https://keybase.io/bk2204
Attachment:
signature.asc
Description: PGP signature
