]> arthur.barton.de Git - bup.git/commit
DESIGN: document the actual hashsplit algorithm
authorJohannes Berg <johannes@sipsolutions.net>
Fri, 1 May 2020 22:52:53 +0000 (00:52 +0200)
committerRob Browning <rlb@defaultvalue.org>
Sun, 5 Jul 2020 16:16:22 +0000 (11:16 -0500)
commit7b140d5b027db0a82e059e545ab47a0ec03fbf32
tree294e1462e171de1027a6860e5191745441dffeec
parenta305de08c7747df480258a9a22d7c76f7e15f7f4
DESIGN: document the actual hashsplit algorithm

The hashsplit algorithm, when used for the fanout, has a quirk
that appears to be due to an implementation bug.

In order for splitting to occur, the lowest 13 (BUP_BLOBBITS)
bits of the csum need to be 1. Then, per DESIGN, the next bits
that are 1 are used for the fanout. However, the implementation
doesn't actually work this way. What actually happens is that
the lower 13 bits need to be ones:

 ........1'1111'1111'1111

Then, the DESIGN document states that the next bits that are 1
should be used for the fanout:

 ....'111_'____'____'____

However, the implementation actually ignores the next bit ('x')

 ....'11x_'____'____'____

and it doesn't matter whether that's set to 0 or 1, the fanout
will be based on the next higher bits (marked '.' and '1').

Fix this in the DESIGN documentation rather than changing the
algorithm as the latter would cause a save of an identical file
to completely rewrite the tree objects that make up the file,
due to different fanout behaviour.

Signed-off-by: Johannes Berg <johannes@sipsolutions.net>
DESIGN