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@gmx.de>
> Cc: Brian M. Carlson <sandals@crustytoothpaste.net>

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@herland.net>

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