git/reftable/stack.c, branch v2.45.2

reftable/stack: use geometric table compaction

2024-04-08T19:11:10Z

To reduce the number of on-disk reftables, compaction is performed. Contiguous tables with the same binary log value of size are grouped into segments. The segment that has both the lowest binary log value and contains more than one table is set as the starting point when identifying the compaction segment. Since segments containing a single table are not initially considered for compaction, if the table appended to the list does not match the previous table log value, no compaction occurs for the new table. It is therefore possible for unbounded growth of the table list. This can be demonstrated by repeating the following sequence: git branch -f foo git branch -d foo Each operation results in a new table being written with no compaction occurring until a separate operation produces a table matching the previous table log value. Instead, to avoid unbounded growth of the table list, the compaction strategy is updated to ensure tables follow a geometric sequence after each operation by individually evaluating each table in reverse index order. This strategy results in a much simpler and more robust algorithm compared to the previous one while also maintaining a minimal ordered set of tables on-disk. When creating 10 thousand references, the new strategy has no performance impact: Benchmark 1: update-ref: create refs sequentially (revision = HEAD~) Time (mean ± σ): 26.516 s ± 0.047 s [User: 17.864 s, System: 8.491 s] Range (min … max): 26.447 s … 26.569 s 10 runs Benchmark 2: update-ref: create refs sequentially (revision = HEAD) Time (mean ± σ): 26.417 s ± 0.028 s [User: 17.738 s, System: 8.500 s] Range (min … max): 26.366 s … 26.444 s 10 runs Summary update-ref: create refs sequentially (revision = HEAD) ran 1.00 ± 0.00 times faster than update-ref: create refs sequentially (revision = HEAD~) Some tests in `t0610-reftable-basics.sh` assert the on-disk state of tables and are therefore updated to specify the correct new table count. Since compaction is more aggressive in ensuring tables maintain a geometric sequence, the expected table count is reduced in these tests. In `reftable/stack_test.c` tests related to `sizes_to_segments()` are removed because the function is no longer needed. Also, the `test_suggest_compaction_segment()` test is updated to better showcase and reflect the new geometric compaction behavior. Signed-off-by: Justin Tobler Acked-by: Patrick Steinhardt Signed-off-by: Junio C Hamano

reftable/stack: expose option to disable auto-compaction

2024-04-08T19:11:10Z

The reftable stack already has a variable to configure whether or not to run auto-compaction, but it is inaccessible to users of the library. There exist use cases where a caller may want to have more control over auto-compaction. Move the `disable_auto_compact` option into `reftable_write_options` to allow external callers to disable auto-compaction. This will be used in a subsequent commit. Signed-off-by: Justin Tobler Acked-by: Patrick Steinhardt Signed-off-by: Junio C Hamano

reftable/stack: gracefully handle failed auto-compaction due to locks

2024-03-25T16:54:07Z

Whenever we commit a new table to the reftable stack we will end up invoking auto-compaction of the stack to keep the total number of tables at bay. This auto-compaction may fail though in case at least one of the tables which we are about to compact is locked. This is indicated by the compaction function returning `REFTABLE_LOCK_ERROR`. We do not handle this case though, and thus bubble that return value up the calling chain, which will ultimately cause a failure. Fix this bug by ignoring `REFTABLE_LOCK_ERROR`. Signed-off-by: Patrick Steinhardt Signed-off-by: Junio C Hamano

reftable/stack: use error codes when locking fails during compaction

2024-03-25T16:51:11Z

Compaction of a reftable stack may fail gracefully when there is a concurrent process that writes to the reftable stack and which has thus locked either the "tables.list" file or one of the tables. This is expected and can be handled gracefully by some of the callers which invoke compaction. Thus, to indicate this situation to our callers, we return a positive return code from `stack_compact_range()` and bubble it up to the caller. This kind of error handling is somewhat awkward though as many callers in the call chain never even think of handling positive return values. Thus, the result is either that such errors are swallowed by accident, or that we abort operations with an unhelpful error message. Make the code more robust by always using negative error codes when compaction fails, with `REFTABLE_LOCK_ERROR` for the described benign error case. Note that only a single callsite knew to handle positive error codes gracefully in the first place. Subsequent commits will touch up some of the other sites to handle those errors better. Signed-off-by: Patrick Steinhardt Signed-off-by: Junio C Hamano

reftable/error: discern locked/outdated errors

2024-03-25T16:51:11Z

We currently throw two different errors into a similar-but-different error code: - Errors when trying to lock the reftable stack. - Errors when trying to write to the reftable stack which has been modified concurrently. This results in unclear error handling and user-visible error messages. Create a new `REFTABLE_OUTDATED_ERROR` so that those error conditions can be clearly told apart from each other. Adjust users of the old `REFTABLE_LOCK_ERROR` to use the new error code as required. Signed-off-by: Patrick Steinhardt Signed-off-by: Junio C Hamano

reftable/stack: fix error handling in `reftable_stack_init_addition()`

2024-03-25T16:51:11Z

In `reftable_stack_init_addition()` we call `stack_uptodate()` after having created the lockfile to check whether the stack was modified concurrently, which is indicated by a positive return code from the latter function. If so, we return a `REFTABLE_LOCK_ERROR` to the caller and abort the addition. The error handling has an off-by-one though because we check whether the error code is `> 1` instead of `> 0`. Thus, instead of returning the locking error, we would return a positive value. One of the callers of `reftable_stack_init_addition()` works around this bug by repeating the error code check without the off-by-one. But other callers are subtly broken by this bug. Fix this by checking for `err > 0` instead. This has the consequence that `reftable_stack_init_addition()` won't ever return a positive error code anymore, but will instead return `REFTABLE_LOCK_ERROR` now. Thus, we can drop the check for a positive error code in `stack_try_add()` now. Signed-off-by: Patrick Steinhardt Signed-off-by: Junio C Hamano

reftable/stack: register compacted tables as tempfiles

2024-03-07T20:34:14Z

We do not register tables resulting from stack compaction with the tempfile API. Those tables will thus not be deleted in case Git gets killed. Refactor the code to register compacted tables as tempfiles. Signed-off-by: Patrick Steinhardt Signed-off-by: Junio C Hamano

reftable/stack: register lockfiles during compaction

2024-03-07T20:34:13Z

We do not register any of the locks we acquire when compacting the reftable stack via our lockfiles interfaces. These locks will thus not be released when Git gets killed. Refactor the code to register locks as lockfiles. Signed-off-by: Patrick Steinhardt Signed-off-by: Junio C Hamano

reftable/stack: register new tables as tempfiles

2024-03-07T20:34:13Z

We do not register new tables which we're about to add to the stack with the tempfile API. Those tables will thus not be deleted in case Git gets killed. Refactor the code to register tables as tempfiles. Signed-off-by: Patrick Steinhardt Signed-off-by: Junio C Hamano

Merge branch 'ps/reftable-styles'

2024-02-12T21:16:10Z

Code clean-up in various reftable code paths. * ps/reftable-styles: reftable/record: improve semantics when initializing records reftable/merged: refactor initialization of iterators reftable/merged: refactor seeking of records reftable/stack: use `size_t` to track stack length reftable/stack: use `size_t` to track stack slices during compaction reftable/stack: index segments with `size_t` reftable/stack: fix parameter validation when compacting range reftable: introduce macros to allocate arrays reftable: introduce macros to grow arrays