{"thread":{"id":"61179","subject":"[PATCH 0/7] reftable: improvements for the `binsearch()` mechanism","startedAt":"2024-03-22T12:22:34Z","lastAt":"2024-04-03T06:04:33Z","messageCount":45,"participants":["Patrick Steinhardt","Justin Tobler"],"isPatch":true,"patchVersion":1,"patchTotal":7},"messages":[{"id":"491232","messageId":"cover.1711109214.git.ps@pks.im","threadId":"61179","inReplyTo":null,"subject":"[PATCH 0/7] reftable: improvements for the `binsearch()` mechanism","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-03-22T12:22:26Z","receivedAt":"2024-03-22T12:22:34Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"Hi,\n\nthis patch series contains various improvements for the `binsearch()`\nmechanism used by the reftable library:\n\n - Callsites are refactored to make it more obvious what exactly they\n are doing. This mostly involves improved names for callback\n functions.\n\n - Error handling is improved such that binsearch() knows to abort when\n the callback returns a negative value.\n\n - Error handling for binary searching over restart counters is fixed\n so that we check for errors at the correct point in time.\n\n - Decoding of record keys is refactored when searching over restart\n counters to not require allocations anymore.\n\nThanks!\n\nPatrick\n\nPatrick Steinhardt (7):\n reftable/basics: fix return type of `binsearch()` to be `size_t`\n reftable/basics: improve `binsearch()` test\n reftable/refname: refactor binary search over refnames\n reftable/block: refactor binary search over restart points\n reftable/block: fix error handling when searching restart points\n reftable/record: extract function to decode key lengths\n reftable/block: avoid decoding keys when searching restart points\n\n reftable/basics.c | 7 ++-\n reftable/basics.h | 7 +--\n reftable/basics_test.c | 55 +++++++++++---------\n reftable/block.c | 114 ++++++++++++++++++++++++++++++-----------\n reftable/record.c | 34 ++++++++----\n reftable/record.h | 6 +++\n reftable/refname.c | 53 +++++++++----------\n 7 files changed, 179 insertions(+), 97 deletions(-)\n\n-- \n2.44.0\n\n"},{"id":"491233","messageId":"cd82ac6531f87917c736c4b523496ef270be34b5.1711109214.git.ps@pks.im","threadId":"61179","inReplyTo":"cover.1711109214.git.ps@pks.im","subject":"[PATCH 1/7] reftable/basics: fix return type of `binsearch()` to be `size_t`","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-03-22T12:22:30Z","receivedAt":"2024-03-22T12:22:34Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"The `binsearch()` function can be used to find the first element for\nwhich a callback functions returns a truish value. But while the array\nsize is of type `size_t`, the function in fact returns an `int` that is\nsupposed to index into that array.\n\nFix the function signature to return a `size_t`. This conversion does\nnot change any semantics given that the function would only ever return\na value in the range `[0, sz]` anyway.\n\nSigned-off-by: Patrick Steinhardt \n---\n reftable/basics.c | 2 +-\n reftable/basics.h | 2 +-\n reftable/basics_test.c | 6 +++---\n reftable/block.c | 3 ++-\n reftable/refname.c | 17 +++++++----------\n 5 files changed, 14 insertions(+), 16 deletions(-)\n\ndiff --git a/reftable/basics.c b/reftable/basics.c\nindex 0785aff941..2c5f34b39e 100644\n--- a/reftable/basics.c\n+++ b/reftable/basics.c\n@@ -27,7 +27,7 @@ void put_be16(uint8_t *out, uint16_t i)\n \tout[1] = (uint8_t)(i & 0xff);\n }\n \n-int binsearch(size_t sz, int (*f)(size_t k, void *args), void *args)\n+size_t binsearch(size_t sz, int (*f)(size_t k, void *args), void *args)\n {\n \tsize_t lo = 0;\n \tsize_t hi = sz;\ndiff --git a/reftable/basics.h b/reftable/basics.h\nindex 91f3533efe..2672520e76 100644\n--- a/reftable/basics.h\n+++ b/reftable/basics.h\n@@ -28,7 +28,7 @@ void put_be16(uint8_t *out, uint16_t i);\n * Contrary to bsearch(3), this returns something useful if the argument is not\n * found.\n */\n-int binsearch(size_t sz, int (*f)(size_t k, void *args), void *args);\n+size_t binsearch(size_t sz, int (*f)(size_t k, void *args), void *args);\n \n /*\n * Frees a NULL terminated array of malloced strings. The array itself is also\ndiff --git a/reftable/basics_test.c b/reftable/basics_test.c\nindex 1fcd229725..dc1c87c5df 100644\n--- a/reftable/basics_test.c\n+++ b/reftable/basics_test.c\n@@ -34,15 +34,15 @@ static void test_binsearch(void)\n \n \tint i = 0;\n \tfor (i = 1; i < 11; i++) {\n-\t\tint res;\n+\t\tsize_t res;\n+\n \t\targs.key = i;\n \t\tres = binsearch(sz, &binsearch_func, &args);\n \n \t\tif (res < sz) {\n \t\t\tEXPECT(args.key < arr[res]);\n-\t\t\tif (res > 0) {\n+\t\t\tif (res > 0)\n \t\t\t\tEXPECT(args.key >= arr[res - 1]);\n-\t\t\t}\n \t\t} else {\n \t\t\tEXPECT(args.key == 10 || args.key == 11);\n \t\t}\ndiff --git a/reftable/block.c b/reftable/block.c\nindex e2a2cee58d..422885bddb 100644\n--- a/reftable/block.c\n+++ b/reftable/block.c\n@@ -382,7 +382,8 @@ int block_reader_seek(struct block_reader *br, struct block_iter *it,\n \t};\n \tstruct block_iter next = BLOCK_ITER_INIT;\n \tstruct reftable_record rec;\n-\tint err = 0, i;\n+\tint err = 0;\n+\tsize_t i;\n \n \tif (args.error) {\n \t\terr = REFTABLE_FORMAT_ERROR;\ndiff --git a/reftable/refname.c b/reftable/refname.c\nindex 7570e4acf9..64eba1b886 100644\n--- a/reftable/refname.c\n+++ b/reftable/refname.c\n@@ -33,10 +33,9 @@ static int modification_has_ref(struct modification *mod, const char *name)\n \t\t\t.names = mod->add,\n \t\t\t.want = name,\n \t\t};\n-\t\tint idx = binsearch(mod->add_len, find_name, &arg);\n-\t\tif (idx < mod->add_len && !strcmp(mod->add[idx], name)) {\n+\t\tsize_t idx = binsearch(mod->add_len, find_name, &arg);\n+\t\tif (idx < mod->add_len && !strcmp(mod->add[idx], name))\n \t\t\treturn 0;\n-\t\t}\n \t}\n \n \tif (mod->del_len > 0) {\n@@ -44,10 +43,9 @@ static int modification_has_ref(struct modification *mod, const char *name)\n \t\t\t.names = mod->del,\n \t\t\t.want = name,\n \t\t};\n-\t\tint idx = binsearch(mod->del_len, find_name, &arg);\n-\t\tif (idx < mod->del_len && !strcmp(mod->del[idx], name)) {\n+\t\tsize_t idx = binsearch(mod->del_len, find_name, &arg);\n+\t\tif (idx < mod->del_len && !strcmp(mod->del[idx], name))\n \t\t\treturn 1;\n-\t\t}\n \t}\n \n \terr = reftable_table_read_ref(&mod->tab, name, &ref);\n@@ -77,7 +75,7 @@ static int modification_has_ref_with_prefix(struct modification *mod,\n \t\t\t.names = mod->add,\n \t\t\t.want = prefix,\n \t\t};\n-\t\tint idx = binsearch(mod->add_len, find_name, &arg);\n+\t\tsize_t idx = binsearch(mod->add_len, find_name, &arg);\n \t\tif (idx < mod->add_len &&\n \t\t !strncmp(prefix, mod->add[idx], strlen(prefix)))\n \t\t\tgoto done;\n@@ -96,11 +94,10 @@ static int modification_has_ref_with_prefix(struct modification *mod,\n \t\t\t\t.names = mod->del,\n \t\t\t\t.want = ref.refname,\n \t\t\t};\n-\t\t\tint idx = binsearch(mod->del_len, find_name, &arg);\n+\t\t\tsize_t idx = binsearch(mod->del_len, find_name, &arg);\n \t\t\tif (idx < mod->del_len &&\n-\t\t\t !strcmp(ref.refname, mod->del[idx])) {\n+\t\t\t !strcmp(ref.refname, mod->del[idx]))\n \t\t\t\tcontinue;\n-\t\t\t}\n \t\t}\n \n \t\tif (strncmp(ref.refname, prefix, strlen(prefix))) {\n-- \n2.44.0\n\n"},{"id":"491234","messageId":"7955f7983a6d8ef81a572f108b11c7afa93e34fd.1711109214.git.ps@pks.im","threadId":"61179","inReplyTo":"cover.1711109214.git.ps@pks.im","subject":"[PATCH 2/7] reftable/basics: improve `binsearch()` test","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-03-22T12:22:35Z","receivedAt":"2024-03-22T12:22:38Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"The `binsearch()` test is somewhat weird in that it doesn't explicitly\nspell out its expectations. Instead it does so in a rather ad-hoc way\nwith some hard-to-understand computations.\n\nRefactor the test to spell out the needle as well as expected index for\nall testcases. This refactoring highlights that the `binsearch_func()`\nis written somewhat weirdly to find the first integer smaller than the\nneedle, not smaller or equal to it. Adjust the function accordingly.\n\nWhile at it, rename the callback function to better convey its meaning.\n\nSigned-off-by: Patrick Steinhardt \n---\n reftable/basics_test.c | 55 ++++++++++++++++++++++++------------------\n 1 file changed, 31 insertions(+), 24 deletions(-)\n\ndiff --git a/reftable/basics_test.c b/reftable/basics_test.c\nindex dc1c87c5df..85c4d1621c 100644\n--- a/reftable/basics_test.c\n+++ b/reftable/basics_test.c\n@@ -12,40 +12,47 @@ license that can be found in the LICENSE file or at\n #include \"test_framework.h\"\n #include \"reftable-tests.h\"\n \n-struct binsearch_args {\n-\tint key;\n-\tint *arr;\n+struct integer_needle_lesseq {\n+\tint needle;\n+\tint *haystack;\n };\n \n-static int binsearch_func(size_t i, void *void_args)\n+static int integer_needle_lesseq(size_t i, void *_args)\n {\n-\tstruct binsearch_args *args = void_args;\n-\n-\treturn args->key < args->arr[i];\n+\tstruct integer_needle_lesseq *args = _args;\n+\treturn args->needle <= args->haystack[i];\n }\n \n static void test_binsearch(void)\n {\n-\tint arr[] = { 2, 4, 6, 8, 10 };\n-\tsize_t sz = ARRAY_SIZE(arr);\n-\tstruct binsearch_args args = {\n-\t\t.arr = arr,\n+\tint haystack[] = { 2, 4, 6, 8, 10 };\n+\tstruct {\n+\t\tint needle;\n+\t\tsize_t expected_idx;\n+\t} testcases[] = {\n+\t\t{-9000, 0},\n+\t\t{-1, 0},\n+\t\t{0, 0},\n+\t\t{2, 0},\n+\t\t{3, 1},\n+\t\t{4, 1},\n+\t\t{7, 3},\n+\t\t{9, 4},\n+\t\t{10, 4},\n+\t\t{11, 5},\n+\t\t{9000, 5},\n \t};\n+\tsize_t i = 0;\n \n-\tint i = 0;\n-\tfor (i = 1; i < 11; i++) {\n-\t\tsize_t res;\n-\n-\t\targs.key = i;\n-\t\tres = binsearch(sz, &binsearch_func, &args);\n+\tfor (i = 0; i < ARRAY_SIZE(testcases); i++) {\n+\t\tstruct integer_needle_lesseq args = {\n+\t\t\t.haystack = haystack,\n+\t\t\t.needle = testcases[i].needle,\n+\t\t};\n+\t\tsize_t idx;\n \n-\t\tif (res < sz) {\n-\t\t\tEXPECT(args.key < arr[res]);\n-\t\t\tif (res > 0)\n-\t\t\t\tEXPECT(args.key >= arr[res - 1]);\n-\t\t} else {\n-\t\t\tEXPECT(args.key == 10 || args.key == 11);\n-\t\t}\n+\t\tidx = binsearch(ARRAY_SIZE(haystack), &integer_needle_lesseq, &args);\n+\t\tEXPECT(idx == testcases[i].expected_idx);\n \t}\n }\n \n-- \n2.44.0\n\n"},{"id":"491235","messageId":"44386818ce681da02f00a498acf66043aa55558e.1711109214.git.ps@pks.im","threadId":"61179","inReplyTo":"cover.1711109214.git.ps@pks.im","subject":"[PATCH 3/7] reftable/refname: refactor binary search over refnames","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-03-22T12:22:39Z","receivedAt":"2024-03-22T12:22:43Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"It is comparatively hard to understand how exactly the binary search\nover refnames works given that the function and variable names are not\nexactly easy to grasp. Rename them to make this more obvious. This\nshould not result in any change in behaviour.\n\nSigned-off-by: Patrick Steinhardt \n---\n reftable/refname.c | 44 ++++++++++++++++++++++----------------------\n 1 file changed, 22 insertions(+), 22 deletions(-)\n\ndiff --git a/reftable/refname.c b/reftable/refname.c\nindex 64eba1b886..9ec488d727 100644\n--- a/reftable/refname.c\n+++ b/reftable/refname.c\n@@ -12,15 +12,15 @@\n #include \"refname.h\"\n #include \"reftable-iterator.h\"\n \n-struct find_arg {\n-\tchar **names;\n-\tconst char *want;\n+struct refname_needle_lesseq_args {\n+\tchar **haystack;\n+\tconst char *needle;\n };\n \n-static int find_name(size_t k, void *arg)\n+static int refname_needle_lesseq(size_t k, void *arg)\n {\n-\tstruct find_arg *f_arg = arg;\n-\treturn strcmp(f_arg->names[k], f_arg->want) >= 0;\n+\tstruct refname_needle_lesseq_args *f_arg = arg;\n+\treturn strcmp(f_arg->needle, f_arg->haystack[k]) <= 0;\n }\n \n static int modification_has_ref(struct modification *mod, const char *name)\n@@ -29,21 +29,21 @@ static int modification_has_ref(struct modification *mod, const char *name)\n \tint err = 0;\n \n \tif (mod->add_len > 0) {\n-\t\tstruct find_arg arg = {\n-\t\t\t.names = mod->add,\n-\t\t\t.want = name,\n+\t\tstruct refname_needle_lesseq_args arg = {\n+\t\t\t.haystack = mod->add,\n+\t\t\t.needle = name,\n \t\t};\n-\t\tsize_t idx = binsearch(mod->add_len, find_name, &arg);\n+\t\tsize_t idx = binsearch(mod->add_len, refname_needle_lesseq, &arg);\n \t\tif (idx < mod->add_len && !strcmp(mod->add[idx], name))\n \t\t\treturn 0;\n \t}\n \n \tif (mod->del_len > 0) {\n-\t\tstruct find_arg arg = {\n-\t\t\t.names = mod->del,\n-\t\t\t.want = name,\n+\t\tstruct refname_needle_lesseq_args arg = {\n+\t\t\t.haystack = mod->del,\n+\t\t\t.needle = name,\n \t\t};\n-\t\tsize_t idx = binsearch(mod->del_len, find_name, &arg);\n+\t\tsize_t idx = binsearch(mod->del_len, refname_needle_lesseq, &arg);\n \t\tif (idx < mod->del_len && !strcmp(mod->del[idx], name))\n \t\t\treturn 1;\n \t}\n@@ -71,11 +71,11 @@ static int modification_has_ref_with_prefix(struct modification *mod,\n \tint err = 0;\n \n \tif (mod->add_len > 0) {\n-\t\tstruct find_arg arg = {\n-\t\t\t.names = mod->add,\n-\t\t\t.want = prefix,\n+\t\tstruct refname_needle_lesseq_args arg = {\n+\t\t\t.haystack = mod->add,\n+\t\t\t.needle = prefix,\n \t\t};\n-\t\tsize_t idx = binsearch(mod->add_len, find_name, &arg);\n+\t\tsize_t idx = binsearch(mod->add_len, refname_needle_lesseq, &arg);\n \t\tif (idx < mod->add_len &&\n \t\t !strncmp(prefix, mod->add[idx], strlen(prefix)))\n \t\t\tgoto done;\n@@ -90,11 +90,11 @@ static int modification_has_ref_with_prefix(struct modification *mod,\n \t\t\tgoto done;\n \n \t\tif (mod->del_len > 0) {\n-\t\t\tstruct find_arg arg = {\n-\t\t\t\t.names = mod->del,\n-\t\t\t\t.want = ref.refname,\n+\t\t\tstruct refname_needle_lesseq_args arg = {\n+\t\t\t\t.haystack = mod->del,\n+\t\t\t\t.needle = ref.refname,\n \t\t\t};\n-\t\t\tsize_t idx = binsearch(mod->del_len, find_name, &arg);\n+\t\t\tsize_t idx = binsearch(mod->del_len, refname_needle_lesseq, &arg);\n \t\t\tif (idx < mod->del_len &&\n \t\t\t !strcmp(ref.refname, mod->del[idx]))\n \t\t\t\tcontinue;\n-- \n2.44.0\n\n"},{"id":"491236","messageId":"f56275f288d94837d49e49ec806a803c6ec911d0.1711109214.git.ps@pks.im","threadId":"61179","inReplyTo":"cover.1711109214.git.ps@pks.im","subject":"[PATCH 4/7] reftable/block: refactor binary search over restart points","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-03-22T12:22:43Z","receivedAt":"2024-03-22T12:22:46Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"When seeking a record in our block reader we perform a binary search\nover the block's restart points so that we don't have to do a linear\nscan over the whole block. The logic to do so is quite intricate though,\nwhich makes it hard to understand.\n\nImprove documentation and rename some of the functions and variables so\nthat the code becomes easier to understand overall. This refactoring\nshould not result in any change in behaviour.\n\nSigned-off-by: Patrick Steinhardt \n---\n reftable/block.c | 97 ++++++++++++++++++++++++++++++++++--------------\n 1 file changed, 70 insertions(+), 27 deletions(-)\n\ndiff --git a/reftable/block.c b/reftable/block.c\nindex 422885bddb..6cd4c053df 100644\n--- a/reftable/block.c\n+++ b/reftable/block.c\n@@ -273,34 +273,36 @@ void block_reader_start(struct block_reader *br, struct block_iter *it)\n \tit->next_off = br->header_off + 4;\n }\n \n-struct restart_find_args {\n+struct restart_needle_less_args {\n \tint error;\n-\tstruct strbuf key;\n-\tstruct block_reader *r;\n+\tstruct strbuf needle;\n+\tstruct block_reader *reader;\n };\n \n-static int restart_key_less(size_t idx, void *args)\n+static int restart_needle_less(size_t idx, void *_args)\n {\n-\tstruct restart_find_args *a = args;\n-\tuint32_t off = block_reader_restart_offset(a->r, idx);\n+\tstruct restart_needle_less_args *args = _args;\n+\tuint32_t off = block_reader_restart_offset(args->reader, idx);\n \tstruct string_view in = {\n-\t\t.buf = a->r->block.data + off,\n-\t\t.len = a->r->block_len - off,\n+\t\t.buf = args->reader->block.data + off,\n+\t\t.len = args->reader->block_len - off,\n \t};\n-\n-\t/* the restart key is verbatim in the block, so this could avoid the\n-\t alloc for decoding the key */\n-\tstruct strbuf rkey = STRBUF_INIT;\n+\tstruct strbuf kth_restart_key = STRBUF_INIT;\n \tuint8_t unused_extra;\n-\tint n = reftable_decode_key(&rkey, &unused_extra, in);\n-\tint result;\n+\tint result, n;\n+\n+\t/*\n+\t * TODO: The restart key is verbatim in the block, so we can in theory\n+\t * avoid decoding the key and thus save some allocations.\n+\t */\n+\tn = reftable_decode_key(&kth_restart_key, &unused_extra, in);\n \tif (n < 0) {\n-\t\ta->error = 1;\n+\t\targs->error = 1;\n \t\treturn -1;\n \t}\n \n-\tresult = strbuf_cmp(&a->key, &rkey);\n-\tstrbuf_release(&rkey);\n+\tresult = strbuf_cmp(&args->needle, &kth_restart_key);\n+\tstrbuf_release(&kth_restart_key);\n \treturn result < 0;\n }\n \n@@ -376,9 +378,9 @@ void block_iter_close(struct block_iter *it)\n int block_reader_seek(struct block_reader *br, struct block_iter *it,\n \t\t struct strbuf *want)\n {\n-\tstruct restart_find_args args = {\n-\t\t.key = *want,\n-\t\t.r = br,\n+\tstruct restart_needle_less_args args = {\n+\t\t.needle = *want,\n+\t\t.reader = br,\n \t};\n \tstruct block_iter next = BLOCK_ITER_INIT;\n \tstruct reftable_record rec;\n@@ -390,7 +392,35 @@ int block_reader_seek(struct block_reader *br, struct block_iter *it,\n \t\tgoto done;\n \t}\n \n-\ti = binsearch(br->restart_count, &restart_key_less, &args);\n+\t/*\n+\t * Perform a binary search over the block's restart points, which\n+\t * avoids doing a linear scan over the whole block. Like this, we\n+\t * identify the section of the block that should contain our key.\n+\t *\n+\t * Note that we explicitly search for the first restart point _greater_\n+\t * than the sought-after record, not _greater or equal_ to it. In case\n+\t * the sought-after record is located directly at the restart point we\n+\t * would otherwise start doing the linear search at the preceding\n+\t * restart point. While that works alright, we would end up scanning\n+\t * too many record.\n+\t */\n+\ti = binsearch(br->restart_count, &restart_needle_less, &args);\n+\n+\t/*\n+\t * Now there are multiple cases:\n+\t *\n+\t * - `i == 0`: The wanted record must be contained before the first\n+\t * restart point. We will thus start searching for the record in\n+\t * that section after accounting for the header offset.\n+\t *\n+\t * - `i == restart_count`: The wanted record was not found at any of\n+\t * the restart points. As there is no restart point at the end of\n+\t * the section the record may thus be contained in the last block.\n+\t *\n+\t * - `i > 0`: The wanted record must be contained in the section\n+\t * before the found restart point. We thus do a linear search\n+\t * starting from the preceding restart point.\n+\t */\n \tif (i > 0)\n \t\tit->next_off = block_reader_restart_offset(br, i - 1);\n \telse\n@@ -399,21 +429,34 @@ int block_reader_seek(struct block_reader *br, struct block_iter *it,\n \n \treftable_record_init(&rec, block_reader_type(br));\n \n-\t/* We're looking for the last entry less/equal than the wanted key, so\n-\t we have to go one entry too far and then back up.\n-\t*/\n+\t/*\n+\t * We're looking for the last entry less than the wanted key so that\n+\t * the next call to `block_reader_next()` would yield the wanted\n+\t * record. We thus don't want to position our reader at the sought\n+\t * after record, but one before. To do so, we have to go one entry too\n+\t * far and then back up.\n+\t */\n \twhile (1) {\n \t\tblock_iter_copy_from(&next, it);\n \t\terr = block_iter_next(&next, &rec);\n \t\tif (err < 0)\n \t\t\tgoto done;\n-\n-\t\treftable_record_key(&rec, &it->last_key);\n-\t\tif (err > 0 || strbuf_cmp(&it->last_key, want) >= 0) {\n+\t\tif (err > 0) {\n \t\t\terr = 0;\n \t\t\tgoto done;\n \t\t}\n \n+\t\t/*\n+\t\t * Check whether the current key is greater or equal to the\n+\t\t * sought-after key. In case it is greater we know that the\n+\t\t * record does not exist in the block and can thus abort early.\n+\t\t * In case it is equal to the sought-after key we have found\n+\t\t * the desired record.\n+\t\t */\n+\t\treftable_record_key(&rec, &it->last_key);\n+\t\tif (strbuf_cmp(&it->last_key, want) >= 0)\n+\t\t\tgoto done;\n+\n \t\tblock_iter_copy_from(it, &next);\n \t}\n \n-- \n2.44.0\n\n"},{"id":"491237","messageId":"36b1ef8e5c0948392210e859b61d9ae3bdb58be9.1711109214.git.ps@pks.im","threadId":"61179","inReplyTo":"cover.1711109214.git.ps@pks.im","subject":"[PATCH 5/7] reftable/block: fix error handling when searching restart points","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-03-22T12:22:47Z","receivedAt":"2024-03-22T12:22:50Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"When doing the binary search over restart points in a block we need to\ndecode the record keys. This decoding step can result in an error when\nthe block is corrupted, which we indicate to the caller of the binary\nsearch by setting `args.error = 1`. But the only caller that exists\nmishandles this because it in fact performs the error check before\ncalling `binsearch()`.\n\nFix this bug by checking for errors at the right point in time.\nFurthermore, refactor `binsearch()` so that it aborts the search in case\nthe callback function returns a negative value so that we don't\nneedlessly continue to search the block.\n\nSigned-off-by: Patrick Steinhardt \n---\n reftable/basics.c | 5 ++++-\n reftable/basics.h | 5 +++--\n reftable/block.c | 9 ++++-----\n 3 files changed, 11 insertions(+), 8 deletions(-)\n\ndiff --git a/reftable/basics.c b/reftable/basics.c\nindex 2c5f34b39e..fea711db7e 100644\n--- a/reftable/basics.c\n+++ b/reftable/basics.c\n@@ -39,8 +39,11 @@ size_t binsearch(size_t sz, int (*f)(size_t k, void *args), void *args)\n \t */\n \twhile (hi - lo > 1) {\n \t\tsize_t mid = lo + (hi - lo) / 2;\n+\t\tint ret = f(mid, args);\n+\t\tif (ret < 0)\n+\t\t\treturn sz;\n \n-\t\tif (f(mid, args))\n+\t\tif (ret > 0)\n \t\t\thi = mid;\n \t\telse\n \t\t\tlo = mid;\ndiff --git a/reftable/basics.h b/reftable/basics.h\nindex 2672520e76..523ecd5307 100644\n--- a/reftable/basics.h\n+++ b/reftable/basics.h\n@@ -22,8 +22,9 @@ uint32_t get_be24(uint8_t *in);\n void put_be16(uint8_t *out, uint16_t i);\n \n /*\n- * find smallest index i in [0, sz) at which f(i) is true, assuming\n- * that f is ascending. Return sz if f(i) is false for all indices.\n+ * find smallest index i in [0, sz) at which `f(i) > 0`, assuming that f is\n+ * ascending. Return sz if `f(i) == 0` for all indices. The search is aborted\n+ * and `sz` is returned in case `f(i) < 0`.\n *\n * Contrary to bsearch(3), this returns something useful if the argument is not\n * found.\ndiff --git a/reftable/block.c b/reftable/block.c\nindex 6cd4c053df..ca80a05e21 100644\n--- a/reftable/block.c\n+++ b/reftable/block.c\n@@ -387,11 +387,6 @@ int block_reader_seek(struct block_reader *br, struct block_iter *it,\n \tint err = 0;\n \tsize_t i;\n \n-\tif (args.error) {\n-\t\terr = REFTABLE_FORMAT_ERROR;\n-\t\tgoto done;\n-\t}\n-\n \t/*\n \t * Perform a binary search over the block's restart points, which\n \t * avoids doing a linear scan over the whole block. Like this, we\n@@ -405,6 +400,10 @@ int block_reader_seek(struct block_reader *br, struct block_iter *it,\n \t * too many record.\n \t */\n \ti = binsearch(br->restart_count, &restart_needle_less, &args);\n+\tif (args.error) {\n+\t\terr = REFTABLE_FORMAT_ERROR;\n+\t\tgoto done;\n+\t}\n \n \t/*\n \t * Now there are multiple cases:\n-- \n2.44.0\n\n"},{"id":"491238","messageId":"38666de451348b0306c55b57d22fa55d2365792d.1711109214.git.ps@pks.im","threadId":"61179","inReplyTo":"cover.1711109214.git.ps@pks.im","subject":"[PATCH 6/7] reftable/record: extract function to decode key lengths","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-03-22T12:22:51Z","receivedAt":"2024-03-22T12:22:54Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"We're about to refactor the binary search over restart points so that it\ndoes not need to fully decode the record keys anymore. To do so we will\nneed to decode the record key lengths, which is non-trivial logic.\n\nExtract the logic to decode these lengths from `refatble_decode_key()`\nso that we can reuse it.\n\nSigned-off-by: Patrick Steinhardt \n---\n reftable/record.c | 34 +++++++++++++++++++++++++---------\n reftable/record.h | 6 ++++++\n 2 files changed, 31 insertions(+), 9 deletions(-)\n\ndiff --git a/reftable/record.c b/reftable/record.c\nindex 23b497adab..5506f3e913 100644\n--- a/reftable/record.c\n+++ b/reftable/record.c\n@@ -159,26 +159,42 @@ int reftable_encode_key(int *restart, struct string_view dest,\n \treturn start.len - dest.len;\n }\n \n-int reftable_decode_key(struct strbuf *last_key, uint8_t *extra,\n-\t\t\tstruct string_view in)\n+int reftable_decode_keylen(struct string_view in,\n+\t\t\t uint64_t *prefix_len,\n+\t\t\t uint64_t *suffix_len,\n+\t\t\t uint8_t *extra)\n {\n-\tint start_len = in.len;\n-\tuint64_t prefix_len = 0;\n-\tuint64_t suffix_len = 0;\n+\tsize_t start_len = in.len;\n \tint n;\n \n-\tn = get_var_int(&prefix_len, &in);\n+\tn = get_var_int(prefix_len, &in);\n \tif (n < 0)\n \t\treturn -1;\n \tstring_view_consume(&in, n);\n \n-\tn = get_var_int(&suffix_len, &in);\n+\tn = get_var_int(suffix_len, &in);\n \tif (n <= 0)\n \t\treturn -1;\n \tstring_view_consume(&in, n);\n \n-\t*extra = (uint8_t)(suffix_len & 0x7);\n-\tsuffix_len >>= 3;\n+\t*extra = (uint8_t)(*suffix_len & 0x7);\n+\t*suffix_len >>= 3;\n+\n+\treturn start_len - in.len;\n+}\n+\n+int reftable_decode_key(struct strbuf *last_key, uint8_t *extra,\n+\t\t\tstruct string_view in)\n+{\n+\tint start_len = in.len;\n+\tuint64_t prefix_len = 0;\n+\tuint64_t suffix_len = 0;\n+\tint n;\n+\n+\tn = reftable_decode_keylen(in, &prefix_len, &suffix_len, extra);\n+\tif (n < 0)\n+\t\treturn -1;\n+\tstring_view_consume(&in, n);\n \n \tif (in.len < suffix_len ||\n \t prefix_len > last_key->len)\ndiff --git a/reftable/record.h b/reftable/record.h\nindex 826ee1c55c..d778133e6e 100644\n--- a/reftable/record.h\n+++ b/reftable/record.h\n@@ -86,6 +86,12 @@ int reftable_encode_key(int *is_restart, struct string_view dest,\n \t\t\tstruct strbuf prev_key, struct strbuf key,\n \t\t\tuint8_t extra);\n \n+/* Decode a record's key lengths. */\n+int reftable_decode_keylen(struct string_view in,\n+\t\t\t uint64_t *prefix_len,\n+\t\t\t uint64_t *suffix_len,\n+\t\t\t uint8_t *extra);\n+\n /*\n * Decode into `last_key` and `extra` from `in`. `last_key` is expected to\n * contain the decoded key of the preceding record, if any.\n-- \n2.44.0\n\n"},{"id":"491239","messageId":"f716400686ab9f04f5dee48ce2b90cfc5f07124e.1711109214.git.ps@pks.im","threadId":"61179","inReplyTo":"cover.1711109214.git.ps@pks.im","subject":"[PATCH 7/7] reftable/block: avoid decoding keys when searching restart points","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-03-22T12:22:55Z","receivedAt":"2024-03-22T12:22:58Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"When searching over restart points in a block we decode the key of each\nof the records, which results in a memory allocation. This is quite\npointless though given that records it restart points will never use\nprefix compression and thus store their keys verbatim in the block.\n\nRefactor the code so that we can avoid decoding the keys, which saves us\nsome allocations.\n\nSigned-off-by: Patrick Steinhardt \n---\n reftable/block.c | 29 +++++++++++++++++++----------\n 1 file changed, 19 insertions(+), 10 deletions(-)\n\ndiff --git a/reftable/block.c b/reftable/block.c\nindex ca80a05e21..8bb4e43cec 100644\n--- a/reftable/block.c\n+++ b/reftable/block.c\n@@ -287,23 +287,32 @@ static int restart_needle_less(size_t idx, void *_args)\n \t\t.buf = args->reader->block.data + off,\n \t\t.len = args->reader->block_len - off,\n \t};\n-\tstruct strbuf kth_restart_key = STRBUF_INIT;\n-\tuint8_t unused_extra;\n-\tint result, n;\n+\tuint64_t prefix_len, suffix_len;\n+\tuint8_t extra;\n+\tint n;\n \n \t/*\n-\t * TODO: The restart key is verbatim in the block, so we can in theory\n-\t * avoid decoding the key and thus save some allocations.\n+\t * Records at restart points are stored without prefix compression, so\n+\t * there is no need to fully decode the record key here. This removes\n+\t * the need for allocating memory.\n \t */\n-\tn = reftable_decode_key(&kth_restart_key, &unused_extra, in);\n-\tif (n < 0) {\n+\tn = reftable_decode_keylen(in, &prefix_len, &suffix_len, &extra);\n+\tif (n < 0 || prefix_len) {\n \t\targs->error = 1;\n \t\treturn -1;\n \t}\n \n-\tresult = strbuf_cmp(&args->needle, &kth_restart_key);\n-\tstrbuf_release(&kth_restart_key);\n-\treturn result < 0;\n+\tstring_view_consume(&in, n);\n+\tif (suffix_len > in.len) {\n+\t\targs->error = 1;\n+\t\treturn -1;\n+\t}\n+\n+\tn = memcmp(args->needle.buf, in.buf,\n+\t\t args->needle.len < suffix_len ? args->needle.len : suffix_len);\n+\tif (n)\n+\t\treturn n < 0;\n+\treturn args->needle.len < suffix_len;\n }\n \n void block_iter_copy_from(struct block_iter *dest, struct block_iter *src)\n-- \n2.44.0\n\n"},{"id":"491258","messageId":"zlj4jlfv645bxqgtjkrm3qdan3b7q4lzhxv3nqp7qagycri323@m5hhhxwuoetv","threadId":"61179","inReplyTo":"7955f7983a6d8ef81a572f108b11c7afa93e34fd.1711109214.git.ps@pks.im","subject":"Re: [PATCH 2/7] reftable/basics: improve `binsearch()` test","fromName":"Justin Tobler","fromEmail":"jltobler@gmail.com","sentAt":"2024-03-22T18:46:56Z","receivedAt":"2024-03-22T18:48:47Z","isPatch":true,"sender":{"key":"jltobler@gmail.com","avatar":"https://avatars.githubusercontent.com/u/53454972?v=4"},"body":"On 24/03/22 01:22PM, Patrick Steinhardt wrote:\n> The `binsearch()` test is somewhat weird in that it doesn't explicitly\n> spell out its expectations. Instead it does so in a rather ad-hoc way\n> with some hard-to-understand computations.\n> \n> Refactor the test to spell out the needle as well as expected index for\n> all testcases. This refactoring highlights that the `binsearch_func()`\n> is written somewhat weirdly to find the first integer smaller than the\n> needle, not smaller or equal to it. Adjust the function accordingly.\n> \n> While at it, rename the callback function to better convey its meaning.\n> \n> Signed-off-by: Patrick Steinhardt \n> ---\n> reftable/basics_test.c | 55 ++++++++++++++++++++++++------------------\n> 1 file changed, 31 insertions(+), 24 deletions(-)\n> \n> diff --git a/reftable/basics_test.c b/reftable/basics_test.c\n> index dc1c87c5df..85c4d1621c 100644\n> --- a/reftable/basics_test.c\n> +++ b/reftable/basics_test.c\n> @@ -12,40 +12,47 @@ license that can be found in the LICENSE file or at\n> #include \"test_framework.h\"\n> #include \"reftable-tests.h\"\n> \n> -struct binsearch_args {\n> -\tint key;\n> -\tint *arr;\n> +struct integer_needle_lesseq {\n> +\tint needle;\n> +\tint *haystack;\n> };\n\nThis is probably just personal preference, but I think `key` and `arr`\nin this case are a bit more straightforward. I do like that we rename\nthe args to be more specific. Do we want to also append `_args` to\ndenote that it is an argument set? Maybe `integer_lesseq_args`?\n\n> \n> -static int binsearch_func(size_t i, void *void_args)\n> +static int integer_needle_lesseq(size_t i, void *_args)\n> {\n> -\tstruct binsearch_args *args = void_args;\n> -\n> -\treturn args->key < args->arr[i];\n> +\tstruct integer_needle_lesseq *args = _args;\n> +\treturn args->needle <= args->haystack[i];\n> }\n\n-Justin\n"},{"id":"491259","messageId":"4ea7gnm5gbuvqnoyxdll3ccxxhr4bmlgzwpjtc7kqzbaf5juzb@5kwcy2qhblss","threadId":"61179","inReplyTo":"44386818ce681da02f00a498acf66043aa55558e.1711109214.git.ps@pks.im","subject":"Re: [PATCH 3/7] reftable/refname: refactor binary search over refnames","fromName":"Justin Tobler","fromEmail":"jltobler@gmail.com","sentAt":"2024-03-22T18:55:17Z","receivedAt":"2024-03-22T18:56:15Z","isPatch":true,"sender":{"key":"jltobler@gmail.com","avatar":"https://avatars.githubusercontent.com/u/53454972?v=4"},"body":"On 24/03/22 01:22PM, Patrick Steinhardt wrote:\n> It is comparatively hard to understand how exactly the binary search\n> over refnames works given that the function and variable names are not\n> exactly easy to grasp. Rename them to make this more obvious. This\n> should not result in any change in behaviour.\n> \n> Signed-off-by: Patrick Steinhardt \n> ---\n> reftable/refname.c | 44 ++++++++++++++++++++++----------------------\n> 1 file changed, 22 insertions(+), 22 deletions(-)\n> \n> diff --git a/reftable/refname.c b/reftable/refname.c\n> index 64eba1b886..9ec488d727 100644\n> --- a/reftable/refname.c\n> +++ b/reftable/refname.c\n> @@ -12,15 +12,15 @@\n> #include \"refname.h\"\n> #include \"reftable-iterator.h\"\n> \n> -struct find_arg {\n> -\tchar **names;\n> -\tconst char *want;\n> +struct refname_needle_lesseq_args {\n> +\tchar **haystack;\n> +\tconst char *needle;\n> };\n\nI agree that the previous `names` and `want` are a bit ambiguous. What\ndo you think about `refnames` and `target_refname` instead?\n\n-Justin\n"},{"id":"491431","messageId":"ZgFM5pUU4TKRbiMt@tanuki","threadId":"61179","inReplyTo":"zlj4jlfv645bxqgtjkrm3qdan3b7q4lzhxv3nqp7qagycri323@m5hhhxwuoetv","subject":"Re: [PATCH 2/7] reftable/basics: improve `binsearch()` test","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-03-25T10:07:34Z","receivedAt":"2024-03-25T10:07:39Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"On Fri, Mar 22, 2024 at 01:46:56PM -0500, Justin Tobler wrote:\n> On 24/03/22 01:22PM, Patrick Steinhardt wrote:\n> > The `binsearch()` test is somewhat weird in that it doesn't explicitly\n> > spell out its expectations. Instead it does so in a rather ad-hoc way\n> > with some hard-to-understand computations.\n> > \n> > Refactor the test to spell out the needle as well as expected index for\n> > all testcases. This refactoring highlights that the `binsearch_func()`\n> > is written somewhat weirdly to find the first integer smaller than the\n> > needle, not smaller or equal to it. Adjust the function accordingly.\n> > \n> > While at it, rename the callback function to better convey its meaning.\n> > \n> > Signed-off-by: Patrick Steinhardt \n> > ---\n> > reftable/basics_test.c | 55 ++++++++++++++++++++++++------------------\n> > 1 file changed, 31 insertions(+), 24 deletions(-)\n> > \n> > diff --git a/reftable/basics_test.c b/reftable/basics_test.c\n> > index dc1c87c5df..85c4d1621c 100644\n> > --- a/reftable/basics_test.c\n> > +++ b/reftable/basics_test.c\n> > @@ -12,40 +12,47 @@ license that can be found in the LICENSE file or at\n> > #include \"test_framework.h\"\n> > #include \"reftable-tests.h\"\n> > \n> > -struct binsearch_args {\n> > -\tint key;\n> > -\tint *arr;\n> > +struct integer_needle_lesseq {\n> > +\tint needle;\n> > +\tint *haystack;\n> > };\n> \n> This is probably just personal preference, but I think `key` and `arr`\n> in this case are a bit more straightforward.\n\nI was trying to make this consistent across all the callsites, and here\nI personally think that `haystack` and `needle` are well understood by\nmost folks and generic enough.\n\n> I do like that we rename\n> the args to be more specific. Do we want to also append `_args` to\n> denote that it is an argument set? Maybe `integer_lesseq_args`?\n\nOh, yeah, that's an oversight indeed.\n\nPatrick\n"},{"id":"491433","messageId":"ZgFM7Jw5y3JdImbE@tanuki","threadId":"61179","inReplyTo":"4ea7gnm5gbuvqnoyxdll3ccxxhr4bmlgzwpjtc7kqzbaf5juzb@5kwcy2qhblss","subject":"Re: [PATCH 3/7] reftable/refname: refactor binary search over refnames","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-03-25T10:07:40Z","receivedAt":"2024-03-25T10:07:43Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"On Fri, Mar 22, 2024 at 01:55:17PM -0500, Justin Tobler wrote:\n> On 24/03/22 01:22PM, Patrick Steinhardt wrote:\n> > It is comparatively hard to understand how exactly the binary search\n> > over refnames works given that the function and variable names are not\n> > exactly easy to grasp. Rename them to make this more obvious. This\n> > should not result in any change in behaviour.\n> > \n> > Signed-off-by: Patrick Steinhardt \n> > ---\n> > reftable/refname.c | 44 ++++++++++++++++++++++----------------------\n> > 1 file changed, 22 insertions(+), 22 deletions(-)\n> > \n> > diff --git a/reftable/refname.c b/reftable/refname.c\n> > index 64eba1b886..9ec488d727 100644\n> > --- a/reftable/refname.c\n> > +++ b/reftable/refname.c\n> > @@ -12,15 +12,15 @@\n> > #include \"refname.h\"\n> > #include \"reftable-iterator.h\"\n> > \n> > -struct find_arg {\n> > -\tchar **names;\n> > -\tconst char *want;\n> > +struct refname_needle_lesseq_args {\n> > +\tchar **haystack;\n> > +\tconst char *needle;\n> > };\n> \n> I agree that the previous `names` and `want` are a bit ambiguous. What\n> do you think about `refnames` and `target_refname` instead?\n\nAs said in the preceding commit I was rather aiming for consistency\nacross the callsites, so I'll keep this as-is for now. I'm happy to be\noverruled though if others feel the same way.\n\nPatrick\n"},{"id":"491437","messageId":"cover.1711361340.git.ps@pks.im","threadId":"61179","inReplyTo":"cover.1711109214.git.ps@pks.im","subject":"[PATCH v2 0/7] reftable: improvements for the `binsearch()` mechanism","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-03-25T10:10:25Z","receivedAt":"2024-03-25T10:10:30Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"Hi,\n\nthis is the second version of my patch series that refactors the\n`binsearch()` mechanism in the reftable library. There's only a single\nchange compared to v1, namely a renamed struct.\n\nThanks!\n\nPatrick\n\nPatrick Steinhardt (7):\n reftable/basics: fix return type of `binsearch()` to be `size_t`\n reftable/basics: improve `binsearch()` test\n reftable/refname: refactor binary search over refnames\n reftable/block: refactor binary search over restart points\n reftable/block: fix error handling when searching restart points\n reftable/record: extract function to decode key lengths\n reftable/block: avoid decoding keys when searching restart points\n\n reftable/basics.c | 7 ++-\n reftable/basics.h | 7 +--\n reftable/basics_test.c | 55 +++++++++++---------\n reftable/block.c | 114 ++++++++++++++++++++++++++++++-----------\n reftable/record.c | 34 ++++++++----\n reftable/record.h | 6 +++\n reftable/refname.c | 53 +++++++++----------\n 7 files changed, 179 insertions(+), 97 deletions(-)\n\nRange-diff against v1:\n1: cd82ac6531 = 1: cd82ac6531 reftable/basics: fix return type of `binsearch()` to be `size_t`\n2: 7955f7983a ! 2: a277d4fa6f reftable/basics: improve `binsearch()` test\n @@ reftable/basics_test.c: license that can be found in the LICENSE file or at\n -struct binsearch_args {\n -\tint key;\n -\tint *arr;\n -+struct integer_needle_lesseq {\n ++struct integer_needle_lesseq_args {\n +\tint needle;\n +\tint *haystack;\n };\n @@ reftable/basics_test.c: license that can be found in the LICENSE file or at\n -\tstruct binsearch_args *args = void_args;\n -\n -\treturn args->key < args->arr[i];\n -+\tstruct integer_needle_lesseq *args = _args;\n ++\tstruct integer_needle_lesseq_args *args = _args;\n +\treturn args->needle <= args->haystack[i];\n }\n \n @@ reftable/basics_test.c: license that can be found in the LICENSE file or at\n -\t\targs.key = i;\n -\t\tres = binsearch(sz, &binsearch_func, &args);\n +\tfor (i = 0; i < ARRAY_SIZE(testcases); i++) {\n -+\t\tstruct integer_needle_lesseq args = {\n ++\t\tstruct integer_needle_lesseq_args args = {\n +\t\t\t.haystack = haystack,\n +\t\t\t.needle = testcases[i].needle,\n +\t\t};\n3: 44386818ce = 3: 9ffcf45c32 reftable/refname: refactor binary search over refnames\n4: f56275f288 = 4: 5e20d93ae0 reftable/block: refactor binary search over restart points\n5: 36b1ef8e5c = 5: 5bbeab114f reftable/block: fix error handling when searching restart points\n6: 38666de451 = 6: 271bacb210 reftable/record: extract function to decode key lengths\n7: f716400686 = 7: e751b3c536 reftable/block: avoid decoding keys when searching restart points\n-- \n2.44.GIT\n\n"},{"id":"491438","messageId":"cd82ac6531f87917c736c4b523496ef270be34b5.1711361340.git.ps@pks.im","threadId":"61179","inReplyTo":"cover.1711361340.git.ps@pks.im","subject":"[PATCH v2 1/7] reftable/basics: fix return type of `binsearch()` to be `size_t`","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-03-25T10:10:30Z","receivedAt":"2024-03-25T10:10:33Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"The `binsearch()` function can be used to find the first element for\nwhich a callback functions returns a truish value. But while the array\nsize is of type `size_t`, the function in fact returns an `int` that is\nsupposed to index into that array.\n\nFix the function signature to return a `size_t`. This conversion does\nnot change any semantics given that the function would only ever return\na value in the range `[0, sz]` anyway.\n\nSigned-off-by: Patrick Steinhardt \n---\n reftable/basics.c | 2 +-\n reftable/basics.h | 2 +-\n reftable/basics_test.c | 6 +++---\n reftable/block.c | 3 ++-\n reftable/refname.c | 17 +++++++----------\n 5 files changed, 14 insertions(+), 16 deletions(-)\n\ndiff --git a/reftable/basics.c b/reftable/basics.c\nindex 0785aff941..2c5f34b39e 100644\n--- a/reftable/basics.c\n+++ b/reftable/basics.c\n@@ -27,7 +27,7 @@ void put_be16(uint8_t *out, uint16_t i)\n \tout[1] = (uint8_t)(i & 0xff);\n }\n \n-int binsearch(size_t sz, int (*f)(size_t k, void *args), void *args)\n+size_t binsearch(size_t sz, int (*f)(size_t k, void *args), void *args)\n {\n \tsize_t lo = 0;\n \tsize_t hi = sz;\ndiff --git a/reftable/basics.h b/reftable/basics.h\nindex 91f3533efe..2672520e76 100644\n--- a/reftable/basics.h\n+++ b/reftable/basics.h\n@@ -28,7 +28,7 @@ void put_be16(uint8_t *out, uint16_t i);\n * Contrary to bsearch(3), this returns something useful if the argument is not\n * found.\n */\n-int binsearch(size_t sz, int (*f)(size_t k, void *args), void *args);\n+size_t binsearch(size_t sz, int (*f)(size_t k, void *args), void *args);\n \n /*\n * Frees a NULL terminated array of malloced strings. The array itself is also\ndiff --git a/reftable/basics_test.c b/reftable/basics_test.c\nindex 1fcd229725..dc1c87c5df 100644\n--- a/reftable/basics_test.c\n+++ b/reftable/basics_test.c\n@@ -34,15 +34,15 @@ static void test_binsearch(void)\n \n \tint i = 0;\n \tfor (i = 1; i < 11; i++) {\n-\t\tint res;\n+\t\tsize_t res;\n+\n \t\targs.key = i;\n \t\tres = binsearch(sz, &binsearch_func, &args);\n \n \t\tif (res < sz) {\n \t\t\tEXPECT(args.key < arr[res]);\n-\t\t\tif (res > 0) {\n+\t\t\tif (res > 0)\n \t\t\t\tEXPECT(args.key >= arr[res - 1]);\n-\t\t\t}\n \t\t} else {\n \t\t\tEXPECT(args.key == 10 || args.key == 11);\n \t\t}\ndiff --git a/reftable/block.c b/reftable/block.c\nindex e2a2cee58d..422885bddb 100644\n--- a/reftable/block.c\n+++ b/reftable/block.c\n@@ -382,7 +382,8 @@ int block_reader_seek(struct block_reader *br, struct block_iter *it,\n \t};\n \tstruct block_iter next = BLOCK_ITER_INIT;\n \tstruct reftable_record rec;\n-\tint err = 0, i;\n+\tint err = 0;\n+\tsize_t i;\n \n \tif (args.error) {\n \t\terr = REFTABLE_FORMAT_ERROR;\ndiff --git a/reftable/refname.c b/reftable/refname.c\nindex 7570e4acf9..64eba1b886 100644\n--- a/reftable/refname.c\n+++ b/reftable/refname.c\n@@ -33,10 +33,9 @@ static int modification_has_ref(struct modification *mod, const char *name)\n \t\t\t.names = mod->add,\n \t\t\t.want = name,\n \t\t};\n-\t\tint idx = binsearch(mod->add_len, find_name, &arg);\n-\t\tif (idx < mod->add_len && !strcmp(mod->add[idx], name)) {\n+\t\tsize_t idx = binsearch(mod->add_len, find_name, &arg);\n+\t\tif (idx < mod->add_len && !strcmp(mod->add[idx], name))\n \t\t\treturn 0;\n-\t\t}\n \t}\n \n \tif (mod->del_len > 0) {\n@@ -44,10 +43,9 @@ static int modification_has_ref(struct modification *mod, const char *name)\n \t\t\t.names = mod->del,\n \t\t\t.want = name,\n \t\t};\n-\t\tint idx = binsearch(mod->del_len, find_name, &arg);\n-\t\tif (idx < mod->del_len && !strcmp(mod->del[idx], name)) {\n+\t\tsize_t idx = binsearch(mod->del_len, find_name, &arg);\n+\t\tif (idx < mod->del_len && !strcmp(mod->del[idx], name))\n \t\t\treturn 1;\n-\t\t}\n \t}\n \n \terr = reftable_table_read_ref(&mod->tab, name, &ref);\n@@ -77,7 +75,7 @@ static int modification_has_ref_with_prefix(struct modification *mod,\n \t\t\t.names = mod->add,\n \t\t\t.want = prefix,\n \t\t};\n-\t\tint idx = binsearch(mod->add_len, find_name, &arg);\n+\t\tsize_t idx = binsearch(mod->add_len, find_name, &arg);\n \t\tif (idx < mod->add_len &&\n \t\t !strncmp(prefix, mod->add[idx], strlen(prefix)))\n \t\t\tgoto done;\n@@ -96,11 +94,10 @@ static int modification_has_ref_with_prefix(struct modification *mod,\n \t\t\t\t.names = mod->del,\n \t\t\t\t.want = ref.refname,\n \t\t\t};\n-\t\t\tint idx = binsearch(mod->del_len, find_name, &arg);\n+\t\t\tsize_t idx = binsearch(mod->del_len, find_name, &arg);\n \t\t\tif (idx < mod->del_len &&\n-\t\t\t !strcmp(ref.refname, mod->del[idx])) {\n+\t\t\t !strcmp(ref.refname, mod->del[idx]))\n \t\t\t\tcontinue;\n-\t\t\t}\n \t\t}\n \n \t\tif (strncmp(ref.refname, prefix, strlen(prefix))) {\n-- \n2.44.GIT\n\n"},{"id":"491440","messageId":"a277d4fa6fb9e8b2e758176dba3cc979a8895451.1711361340.git.ps@pks.im","threadId":"61179","inReplyTo":"cover.1711361340.git.ps@pks.im","subject":"[PATCH v2 2/7] reftable/basics: improve `binsearch()` test","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-03-25T10:10:34Z","receivedAt":"2024-03-25T10:10:37Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"The `binsearch()` test is somewhat weird in that it doesn't explicitly\nspell out its expectations. Instead it does so in a rather ad-hoc way\nwith some hard-to-understand computations.\n\nRefactor the test to spell out the needle as well as expected index for\nall testcases. This refactoring highlights that the `binsearch_func()`\nis written somewhat weirdly to find the first integer smaller than the\nneedle, not smaller or equal to it. Adjust the function accordingly.\n\nWhile at it, rename the callback function to better convey its meaning.\n\nSigned-off-by: Patrick Steinhardt \n---\n reftable/basics_test.c | 55 ++++++++++++++++++++++++------------------\n 1 file changed, 31 insertions(+), 24 deletions(-)\n\ndiff --git a/reftable/basics_test.c b/reftable/basics_test.c\nindex dc1c87c5df..997c4d9e01 100644\n--- a/reftable/basics_test.c\n+++ b/reftable/basics_test.c\n@@ -12,40 +12,47 @@ license that can be found in the LICENSE file or at\n #include \"test_framework.h\"\n #include \"reftable-tests.h\"\n \n-struct binsearch_args {\n-\tint key;\n-\tint *arr;\n+struct integer_needle_lesseq_args {\n+\tint needle;\n+\tint *haystack;\n };\n \n-static int binsearch_func(size_t i, void *void_args)\n+static int integer_needle_lesseq(size_t i, void *_args)\n {\n-\tstruct binsearch_args *args = void_args;\n-\n-\treturn args->key < args->arr[i];\n+\tstruct integer_needle_lesseq_args *args = _args;\n+\treturn args->needle <= args->haystack[i];\n }\n \n static void test_binsearch(void)\n {\n-\tint arr[] = { 2, 4, 6, 8, 10 };\n-\tsize_t sz = ARRAY_SIZE(arr);\n-\tstruct binsearch_args args = {\n-\t\t.arr = arr,\n+\tint haystack[] = { 2, 4, 6, 8, 10 };\n+\tstruct {\n+\t\tint needle;\n+\t\tsize_t expected_idx;\n+\t} testcases[] = {\n+\t\t{-9000, 0},\n+\t\t{-1, 0},\n+\t\t{0, 0},\n+\t\t{2, 0},\n+\t\t{3, 1},\n+\t\t{4, 1},\n+\t\t{7, 3},\n+\t\t{9, 4},\n+\t\t{10, 4},\n+\t\t{11, 5},\n+\t\t{9000, 5},\n \t};\n+\tsize_t i = 0;\n \n-\tint i = 0;\n-\tfor (i = 1; i < 11; i++) {\n-\t\tsize_t res;\n-\n-\t\targs.key = i;\n-\t\tres = binsearch(sz, &binsearch_func, &args);\n+\tfor (i = 0; i < ARRAY_SIZE(testcases); i++) {\n+\t\tstruct integer_needle_lesseq_args args = {\n+\t\t\t.haystack = haystack,\n+\t\t\t.needle = testcases[i].needle,\n+\t\t};\n+\t\tsize_t idx;\n \n-\t\tif (res < sz) {\n-\t\t\tEXPECT(args.key < arr[res]);\n-\t\t\tif (res > 0)\n-\t\t\t\tEXPECT(args.key >= arr[res - 1]);\n-\t\t} else {\n-\t\t\tEXPECT(args.key == 10 || args.key == 11);\n-\t\t}\n+\t\tidx = binsearch(ARRAY_SIZE(haystack), &integer_needle_lesseq, &args);\n+\t\tEXPECT(idx == testcases[i].expected_idx);\n \t}\n }\n \n-- \n2.44.GIT\n\n"},{"id":"491436","messageId":"9ffcf45c32f22245c9978436affcefa914fc6927.1711361340.git.ps@pks.im","threadId":"61179","inReplyTo":"cover.1711361340.git.ps@pks.im","subject":"[PATCH v2 3/7] reftable/refname: refactor binary search over refnames","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-03-25T10:10:38Z","receivedAt":"2024-03-25T10:10:42Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"It is comparatively hard to understand how exactly the binary search\nover refnames works given that the function and variable names are not\nexactly easy to grasp. Rename them to make this more obvious. This\nshould not result in any change in behaviour.\n\nSigned-off-by: Patrick Steinhardt \n---\n reftable/refname.c | 44 ++++++++++++++++++++++----------------------\n 1 file changed, 22 insertions(+), 22 deletions(-)\n\ndiff --git a/reftable/refname.c b/reftable/refname.c\nindex 64eba1b886..9ec488d727 100644\n--- a/reftable/refname.c\n+++ b/reftable/refname.c\n@@ -12,15 +12,15 @@\n #include \"refname.h\"\n #include \"reftable-iterator.h\"\n \n-struct find_arg {\n-\tchar **names;\n-\tconst char *want;\n+struct refname_needle_lesseq_args {\n+\tchar **haystack;\n+\tconst char *needle;\n };\n \n-static int find_name(size_t k, void *arg)\n+static int refname_needle_lesseq(size_t k, void *arg)\n {\n-\tstruct find_arg *f_arg = arg;\n-\treturn strcmp(f_arg->names[k], f_arg->want) >= 0;\n+\tstruct refname_needle_lesseq_args *f_arg = arg;\n+\treturn strcmp(f_arg->needle, f_arg->haystack[k]) <= 0;\n }\n \n static int modification_has_ref(struct modification *mod, const char *name)\n@@ -29,21 +29,21 @@ static int modification_has_ref(struct modification *mod, const char *name)\n \tint err = 0;\n \n \tif (mod->add_len > 0) {\n-\t\tstruct find_arg arg = {\n-\t\t\t.names = mod->add,\n-\t\t\t.want = name,\n+\t\tstruct refname_needle_lesseq_args arg = {\n+\t\t\t.haystack = mod->add,\n+\t\t\t.needle = name,\n \t\t};\n-\t\tsize_t idx = binsearch(mod->add_len, find_name, &arg);\n+\t\tsize_t idx = binsearch(mod->add_len, refname_needle_lesseq, &arg);\n \t\tif (idx < mod->add_len && !strcmp(mod->add[idx], name))\n \t\t\treturn 0;\n \t}\n \n \tif (mod->del_len > 0) {\n-\t\tstruct find_arg arg = {\n-\t\t\t.names = mod->del,\n-\t\t\t.want = name,\n+\t\tstruct refname_needle_lesseq_args arg = {\n+\t\t\t.haystack = mod->del,\n+\t\t\t.needle = name,\n \t\t};\n-\t\tsize_t idx = binsearch(mod->del_len, find_name, &arg);\n+\t\tsize_t idx = binsearch(mod->del_len, refname_needle_lesseq, &arg);\n \t\tif (idx < mod->del_len && !strcmp(mod->del[idx], name))\n \t\t\treturn 1;\n \t}\n@@ -71,11 +71,11 @@ static int modification_has_ref_with_prefix(struct modification *mod,\n \tint err = 0;\n \n \tif (mod->add_len > 0) {\n-\t\tstruct find_arg arg = {\n-\t\t\t.names = mod->add,\n-\t\t\t.want = prefix,\n+\t\tstruct refname_needle_lesseq_args arg = {\n+\t\t\t.haystack = mod->add,\n+\t\t\t.needle = prefix,\n \t\t};\n-\t\tsize_t idx = binsearch(mod->add_len, find_name, &arg);\n+\t\tsize_t idx = binsearch(mod->add_len, refname_needle_lesseq, &arg);\n \t\tif (idx < mod->add_len &&\n \t\t !strncmp(prefix, mod->add[idx], strlen(prefix)))\n \t\t\tgoto done;\n@@ -90,11 +90,11 @@ static int modification_has_ref_with_prefix(struct modification *mod,\n \t\t\tgoto done;\n \n \t\tif (mod->del_len > 0) {\n-\t\t\tstruct find_arg arg = {\n-\t\t\t\t.names = mod->del,\n-\t\t\t\t.want = ref.refname,\n+\t\t\tstruct refname_needle_lesseq_args arg = {\n+\t\t\t\t.haystack = mod->del,\n+\t\t\t\t.needle = ref.refname,\n \t\t\t};\n-\t\t\tsize_t idx = binsearch(mod->del_len, find_name, &arg);\n+\t\t\tsize_t idx = binsearch(mod->del_len, refname_needle_lesseq, &arg);\n \t\t\tif (idx < mod->del_len &&\n \t\t\t !strcmp(ref.refname, mod->del[idx]))\n \t\t\t\tcontinue;\n-- \n2.44.GIT\n\n"},{"id":"491434","messageId":"5e20d93ae000359f2231bf950a930cfc4898ced2.1711361340.git.ps@pks.im","threadId":"61179","inReplyTo":"cover.1711361340.git.ps@pks.im","subject":"[PATCH v2 4/7] reftable/block: refactor binary search over restart points","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-03-25T10:10:42Z","receivedAt":"2024-03-25T10:10:46Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"When seeking a record in our block reader we perform a binary search\nover the block's restart points so that we don't have to do a linear\nscan over the whole block. The logic to do so is quite intricate though,\nwhich makes it hard to understand.\n\nImprove documentation and rename some of the functions and variables so\nthat the code becomes easier to understand overall. This refactoring\nshould not result in any change in behaviour.\n\nSigned-off-by: Patrick Steinhardt \n---\n reftable/block.c | 97 ++++++++++++++++++++++++++++++++++--------------\n 1 file changed, 70 insertions(+), 27 deletions(-)\n\ndiff --git a/reftable/block.c b/reftable/block.c\nindex 422885bddb..6cd4c053df 100644\n--- a/reftable/block.c\n+++ b/reftable/block.c\n@@ -273,34 +273,36 @@ void block_reader_start(struct block_reader *br, struct block_iter *it)\n \tit->next_off = br->header_off + 4;\n }\n \n-struct restart_find_args {\n+struct restart_needle_less_args {\n \tint error;\n-\tstruct strbuf key;\n-\tstruct block_reader *r;\n+\tstruct strbuf needle;\n+\tstruct block_reader *reader;\n };\n \n-static int restart_key_less(size_t idx, void *args)\n+static int restart_needle_less(size_t idx, void *_args)\n {\n-\tstruct restart_find_args *a = args;\n-\tuint32_t off = block_reader_restart_offset(a->r, idx);\n+\tstruct restart_needle_less_args *args = _args;\n+\tuint32_t off = block_reader_restart_offset(args->reader, idx);\n \tstruct string_view in = {\n-\t\t.buf = a->r->block.data + off,\n-\t\t.len = a->r->block_len - off,\n+\t\t.buf = args->reader->block.data + off,\n+\t\t.len = args->reader->block_len - off,\n \t};\n-\n-\t/* the restart key is verbatim in the block, so this could avoid the\n-\t alloc for decoding the key */\n-\tstruct strbuf rkey = STRBUF_INIT;\n+\tstruct strbuf kth_restart_key = STRBUF_INIT;\n \tuint8_t unused_extra;\n-\tint n = reftable_decode_key(&rkey, &unused_extra, in);\n-\tint result;\n+\tint result, n;\n+\n+\t/*\n+\t * TODO: The restart key is verbatim in the block, so we can in theory\n+\t * avoid decoding the key and thus save some allocations.\n+\t */\n+\tn = reftable_decode_key(&kth_restart_key, &unused_extra, in);\n \tif (n < 0) {\n-\t\ta->error = 1;\n+\t\targs->error = 1;\n \t\treturn -1;\n \t}\n \n-\tresult = strbuf_cmp(&a->key, &rkey);\n-\tstrbuf_release(&rkey);\n+\tresult = strbuf_cmp(&args->needle, &kth_restart_key);\n+\tstrbuf_release(&kth_restart_key);\n \treturn result < 0;\n }\n \n@@ -376,9 +378,9 @@ void block_iter_close(struct block_iter *it)\n int block_reader_seek(struct block_reader *br, struct block_iter *it,\n \t\t struct strbuf *want)\n {\n-\tstruct restart_find_args args = {\n-\t\t.key = *want,\n-\t\t.r = br,\n+\tstruct restart_needle_less_args args = {\n+\t\t.needle = *want,\n+\t\t.reader = br,\n \t};\n \tstruct block_iter next = BLOCK_ITER_INIT;\n \tstruct reftable_record rec;\n@@ -390,7 +392,35 @@ int block_reader_seek(struct block_reader *br, struct block_iter *it,\n \t\tgoto done;\n \t}\n \n-\ti = binsearch(br->restart_count, &restart_key_less, &args);\n+\t/*\n+\t * Perform a binary search over the block's restart points, which\n+\t * avoids doing a linear scan over the whole block. Like this, we\n+\t * identify the section of the block that should contain our key.\n+\t *\n+\t * Note that we explicitly search for the first restart point _greater_\n+\t * than the sought-after record, not _greater or equal_ to it. In case\n+\t * the sought-after record is located directly at the restart point we\n+\t * would otherwise start doing the linear search at the preceding\n+\t * restart point. While that works alright, we would end up scanning\n+\t * too many record.\n+\t */\n+\ti = binsearch(br->restart_count, &restart_needle_less, &args);\n+\n+\t/*\n+\t * Now there are multiple cases:\n+\t *\n+\t * - `i == 0`: The wanted record must be contained before the first\n+\t * restart point. We will thus start searching for the record in\n+\t * that section after accounting for the header offset.\n+\t *\n+\t * - `i == restart_count`: The wanted record was not found at any of\n+\t * the restart points. As there is no restart point at the end of\n+\t * the section the record may thus be contained in the last block.\n+\t *\n+\t * - `i > 0`: The wanted record must be contained in the section\n+\t * before the found restart point. We thus do a linear search\n+\t * starting from the preceding restart point.\n+\t */\n \tif (i > 0)\n \t\tit->next_off = block_reader_restart_offset(br, i - 1);\n \telse\n@@ -399,21 +429,34 @@ int block_reader_seek(struct block_reader *br, struct block_iter *it,\n \n \treftable_record_init(&rec, block_reader_type(br));\n \n-\t/* We're looking for the last entry less/equal than the wanted key, so\n-\t we have to go one entry too far and then back up.\n-\t*/\n+\t/*\n+\t * We're looking for the last entry less than the wanted key so that\n+\t * the next call to `block_reader_next()` would yield the wanted\n+\t * record. We thus don't want to position our reader at the sought\n+\t * after record, but one before. To do so, we have to go one entry too\n+\t * far and then back up.\n+\t */\n \twhile (1) {\n \t\tblock_iter_copy_from(&next, it);\n \t\terr = block_iter_next(&next, &rec);\n \t\tif (err < 0)\n \t\t\tgoto done;\n-\n-\t\treftable_record_key(&rec, &it->last_key);\n-\t\tif (err > 0 || strbuf_cmp(&it->last_key, want) >= 0) {\n+\t\tif (err > 0) {\n \t\t\terr = 0;\n \t\t\tgoto done;\n \t\t}\n \n+\t\t/*\n+\t\t * Check whether the current key is greater or equal to the\n+\t\t * sought-after key. In case it is greater we know that the\n+\t\t * record does not exist in the block and can thus abort early.\n+\t\t * In case it is equal to the sought-after key we have found\n+\t\t * the desired record.\n+\t\t */\n+\t\treftable_record_key(&rec, &it->last_key);\n+\t\tif (strbuf_cmp(&it->last_key, want) >= 0)\n+\t\t\tgoto done;\n+\n \t\tblock_iter_copy_from(it, &next);\n \t}\n \n-- \n2.44.GIT\n\n"},{"id":"491441","messageId":"5bbeab114f9f0563c9a6c07417b90d41c7fcddc1.1711361340.git.ps@pks.im","threadId":"61179","inReplyTo":"cover.1711361340.git.ps@pks.im","subject":"[PATCH v2 5/7] reftable/block: fix error handling when searching restart points","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-03-25T10:10:47Z","receivedAt":"2024-03-25T10:10:50Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"When doing the binary search over restart points in a block we need to\ndecode the record keys. This decoding step can result in an error when\nthe block is corrupted, which we indicate to the caller of the binary\nsearch by setting `args.error = 1`. But the only caller that exists\nmishandles this because it in fact performs the error check before\ncalling `binsearch()`.\n\nFix this bug by checking for errors at the right point in time.\nFurthermore, refactor `binsearch()` so that it aborts the search in case\nthe callback function returns a negative value so that we don't\nneedlessly continue to search the block.\n\nSigned-off-by: Patrick Steinhardt \n---\n reftable/basics.c | 5 ++++-\n reftable/basics.h | 5 +++--\n reftable/block.c | 9 ++++-----\n 3 files changed, 11 insertions(+), 8 deletions(-)\n\ndiff --git a/reftable/basics.c b/reftable/basics.c\nindex 2c5f34b39e..fea711db7e 100644\n--- a/reftable/basics.c\n+++ b/reftable/basics.c\n@@ -39,8 +39,11 @@ size_t binsearch(size_t sz, int (*f)(size_t k, void *args), void *args)\n \t */\n \twhile (hi - lo > 1) {\n \t\tsize_t mid = lo + (hi - lo) / 2;\n+\t\tint ret = f(mid, args);\n+\t\tif (ret < 0)\n+\t\t\treturn sz;\n \n-\t\tif (f(mid, args))\n+\t\tif (ret > 0)\n \t\t\thi = mid;\n \t\telse\n \t\t\tlo = mid;\ndiff --git a/reftable/basics.h b/reftable/basics.h\nindex 2672520e76..523ecd5307 100644\n--- a/reftable/basics.h\n+++ b/reftable/basics.h\n@@ -22,8 +22,9 @@ uint32_t get_be24(uint8_t *in);\n void put_be16(uint8_t *out, uint16_t i);\n \n /*\n- * find smallest index i in [0, sz) at which f(i) is true, assuming\n- * that f is ascending. Return sz if f(i) is false for all indices.\n+ * find smallest index i in [0, sz) at which `f(i) > 0`, assuming that f is\n+ * ascending. Return sz if `f(i) == 0` for all indices. The search is aborted\n+ * and `sz` is returned in case `f(i) < 0`.\n *\n * Contrary to bsearch(3), this returns something useful if the argument is not\n * found.\ndiff --git a/reftable/block.c b/reftable/block.c\nindex 6cd4c053df..ca80a05e21 100644\n--- a/reftable/block.c\n+++ b/reftable/block.c\n@@ -387,11 +387,6 @@ int block_reader_seek(struct block_reader *br, struct block_iter *it,\n \tint err = 0;\n \tsize_t i;\n \n-\tif (args.error) {\n-\t\terr = REFTABLE_FORMAT_ERROR;\n-\t\tgoto done;\n-\t}\n-\n \t/*\n \t * Perform a binary search over the block's restart points, which\n \t * avoids doing a linear scan over the whole block. Like this, we\n@@ -405,6 +400,10 @@ int block_reader_seek(struct block_reader *br, struct block_iter *it,\n \t * too many record.\n \t */\n \ti = binsearch(br->restart_count, &restart_needle_less, &args);\n+\tif (args.error) {\n+\t\terr = REFTABLE_FORMAT_ERROR;\n+\t\tgoto done;\n+\t}\n \n \t/*\n \t * Now there are multiple cases:\n-- \n2.44.GIT\n\n"},{"id":"491435","messageId":"271bacb210837ca4984155cbbc90915e9f2331c0.1711361340.git.ps@pks.im","threadId":"61179","inReplyTo":"cover.1711361340.git.ps@pks.im","subject":"[PATCH v2 6/7] reftable/record: extract function to decode key lengths","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-03-25T10:10:55Z","receivedAt":"2024-03-25T10:10:58Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"We're about to refactor the binary search over restart points so that it\ndoes not need to fully decode the record keys anymore. To do so we will\nneed to decode the record key lengths, which is non-trivial logic.\n\nExtract the logic to decode these lengths from `refatble_decode_key()`\nso that we can reuse it.\n\nSigned-off-by: Patrick Steinhardt \n---\n reftable/record.c | 34 +++++++++++++++++++++++++---------\n reftable/record.h | 6 ++++++\n 2 files changed, 31 insertions(+), 9 deletions(-)\n\ndiff --git a/reftable/record.c b/reftable/record.c\nindex 23b497adab..5506f3e913 100644\n--- a/reftable/record.c\n+++ b/reftable/record.c\n@@ -159,26 +159,42 @@ int reftable_encode_key(int *restart, struct string_view dest,\n \treturn start.len - dest.len;\n }\n \n-int reftable_decode_key(struct strbuf *last_key, uint8_t *extra,\n-\t\t\tstruct string_view in)\n+int reftable_decode_keylen(struct string_view in,\n+\t\t\t uint64_t *prefix_len,\n+\t\t\t uint64_t *suffix_len,\n+\t\t\t uint8_t *extra)\n {\n-\tint start_len = in.len;\n-\tuint64_t prefix_len = 0;\n-\tuint64_t suffix_len = 0;\n+\tsize_t start_len = in.len;\n \tint n;\n \n-\tn = get_var_int(&prefix_len, &in);\n+\tn = get_var_int(prefix_len, &in);\n \tif (n < 0)\n \t\treturn -1;\n \tstring_view_consume(&in, n);\n \n-\tn = get_var_int(&suffix_len, &in);\n+\tn = get_var_int(suffix_len, &in);\n \tif (n <= 0)\n \t\treturn -1;\n \tstring_view_consume(&in, n);\n \n-\t*extra = (uint8_t)(suffix_len & 0x7);\n-\tsuffix_len >>= 3;\n+\t*extra = (uint8_t)(*suffix_len & 0x7);\n+\t*suffix_len >>= 3;\n+\n+\treturn start_len - in.len;\n+}\n+\n+int reftable_decode_key(struct strbuf *last_key, uint8_t *extra,\n+\t\t\tstruct string_view in)\n+{\n+\tint start_len = in.len;\n+\tuint64_t prefix_len = 0;\n+\tuint64_t suffix_len = 0;\n+\tint n;\n+\n+\tn = reftable_decode_keylen(in, &prefix_len, &suffix_len, extra);\n+\tif (n < 0)\n+\t\treturn -1;\n+\tstring_view_consume(&in, n);\n \n \tif (in.len < suffix_len ||\n \t prefix_len > last_key->len)\ndiff --git a/reftable/record.h b/reftable/record.h\nindex 826ee1c55c..d778133e6e 100644\n--- a/reftable/record.h\n+++ b/reftable/record.h\n@@ -86,6 +86,12 @@ int reftable_encode_key(int *is_restart, struct string_view dest,\n \t\t\tstruct strbuf prev_key, struct strbuf key,\n \t\t\tuint8_t extra);\n \n+/* Decode a record's key lengths. */\n+int reftable_decode_keylen(struct string_view in,\n+\t\t\t uint64_t *prefix_len,\n+\t\t\t uint64_t *suffix_len,\n+\t\t\t uint8_t *extra);\n+\n /*\n * Decode into `last_key` and `extra` from `in`. `last_key` is expected to\n * contain the decoded key of the preceding record, if any.\n-- \n2.44.GIT\n\n"},{"id":"491439","messageId":"e751b3c536ace78f975b7d2553c22dbf6845a8d4.1711361340.git.ps@pks.im","threadId":"61179","inReplyTo":"cover.1711361340.git.ps@pks.im","subject":"[PATCH v2 7/7] reftable/block: avoid decoding keys when searching restart points","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-03-25T10:11:06Z","receivedAt":"2024-03-25T10:11:09Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"When searching over restart points in a block we decode the key of each\nof the records, which results in a memory allocation. This is quite\npointless though given that records it restart points will never use\nprefix compression and thus store their keys verbatim in the block.\n\nRefactor the code so that we can avoid decoding the keys, which saves us\nsome allocations.\n\nSigned-off-by: Patrick Steinhardt \n---\n reftable/block.c | 29 +++++++++++++++++++----------\n 1 file changed, 19 insertions(+), 10 deletions(-)\n\ndiff --git a/reftable/block.c b/reftable/block.c\nindex ca80a05e21..8bb4e43cec 100644\n--- a/reftable/block.c\n+++ b/reftable/block.c\n@@ -287,23 +287,32 @@ static int restart_needle_less(size_t idx, void *_args)\n \t\t.buf = args->reader->block.data + off,\n \t\t.len = args->reader->block_len - off,\n \t};\n-\tstruct strbuf kth_restart_key = STRBUF_INIT;\n-\tuint8_t unused_extra;\n-\tint result, n;\n+\tuint64_t prefix_len, suffix_len;\n+\tuint8_t extra;\n+\tint n;\n \n \t/*\n-\t * TODO: The restart key is verbatim in the block, so we can in theory\n-\t * avoid decoding the key and thus save some allocations.\n+\t * Records at restart points are stored without prefix compression, so\n+\t * there is no need to fully decode the record key here. This removes\n+\t * the need for allocating memory.\n \t */\n-\tn = reftable_decode_key(&kth_restart_key, &unused_extra, in);\n-\tif (n < 0) {\n+\tn = reftable_decode_keylen(in, &prefix_len, &suffix_len, &extra);\n+\tif (n < 0 || prefix_len) {\n \t\targs->error = 1;\n \t\treturn -1;\n \t}\n \n-\tresult = strbuf_cmp(&args->needle, &kth_restart_key);\n-\tstrbuf_release(&kth_restart_key);\n-\treturn result < 0;\n+\tstring_view_consume(&in, n);\n+\tif (suffix_len > in.len) {\n+\t\targs->error = 1;\n+\t\treturn -1;\n+\t}\n+\n+\tn = memcmp(args->needle.buf, in.buf,\n+\t\t args->needle.len < suffix_len ? args->needle.len : suffix_len);\n+\tif (n)\n+\t\treturn n < 0;\n+\treturn args->needle.len < suffix_len;\n }\n \n void block_iter_copy_from(struct block_iter *dest, struct block_iter *src)\n-- \n2.44.GIT\n\n"},{"id":"492064","messageId":"zvw6ezlchqyl5tq4zuia7az5b3i4swwvtm42muwe4i7gngswgz@ztujhb4ruewm","threadId":"61179","inReplyTo":"9ffcf45c32f22245c9978436affcefa914fc6927.1711361340.git.ps@pks.im","subject":"Re: [PATCH v2 3/7] reftable/refname: refactor binary search over refnames","fromName":"Justin Tobler","fromEmail":"jltobler@gmail.com","sentAt":"2024-04-02T16:27:01Z","receivedAt":"2024-04-02T16:27:59Z","isPatch":true,"sender":{"key":"jltobler@gmail.com","avatar":"https://avatars.githubusercontent.com/u/53454972?v=4"},"body":"On 24/03/25 11:10AM, Patrick Steinhardt wrote:\n> It is comparatively hard to understand how exactly the binary search\n> over refnames works given that the function and variable names are not\n> exactly easy to grasp. Rename them to make this more obvious. This\n> should not result in any change in behaviour.\n> \n> Signed-off-by: Patrick Steinhardt \n> ---\n> reftable/refname.c | 44 ++++++++++++++++++++++----------------------\n> 1 file changed, 22 insertions(+), 22 deletions(-)\n> \n> diff --git a/reftable/refname.c b/reftable/refname.c\n> index 64eba1b886..9ec488d727 100644\n> --- a/reftable/refname.c\n> +++ b/reftable/refname.c\n> @@ -12,15 +12,15 @@\n> #include \"refname.h\"\n> #include \"reftable-iterator.h\"\n> \n> -struct find_arg {\n> -\tchar **names;\n> -\tconst char *want;\n> +struct refname_needle_lesseq_args {\n> +\tchar **haystack;\n> +\tconst char *needle;\n> };\n> \n> -static int find_name(size_t k, void *arg)\n> +static int refname_needle_lesseq(size_t k, void *arg)\n> {\n> -\tstruct find_arg *f_arg = arg;\n> -\treturn strcmp(f_arg->names[k], f_arg->want) >= 0;\n> +\tstruct refname_needle_lesseq_args *f_arg = arg;\n\nnit: Looks like the `f_arg` variable name is a remnant from when the\ntype was called `find_arg`. Do we want to rename this to `args`? We \ncould also rename `void *arg` to `void *_args`.\n\n> +\treturn strcmp(f_arg->needle, f_arg->haystack[k]) <= 0;\n> }\n> \n> static int modification_has_ref(struct modification *mod, const char *name)\n> @@ -29,21 +29,21 @@ static int modification_has_ref(struct modification *mod, const char *name)\n> \tint err = 0;\n> \n> \tif (mod->add_len > 0) {\n> -\t\tstruct find_arg arg = {\n> -\t\t\t.names = mod->add,\n> -\t\t\t.want = name,\n> +\t\tstruct refname_needle_lesseq_args arg = {\n> +\t\t\t.haystack = mod->add,\n> +\t\t\t.needle = name,\n> \t\t};\n> -\t\tsize_t idx = binsearch(mod->add_len, find_name, &arg);\n> +\t\tsize_t idx = binsearch(mod->add_len, refname_needle_lesseq, &arg);\n> \t\tif (idx < mod->add_len && !strcmp(mod->add[idx], name))\n> \t\t\treturn 0;\n> \t}\n> \n> \tif (mod->del_len > 0) {\n> -\t\tstruct find_arg arg = {\n> -\t\t\t.names = mod->del,\n> -\t\t\t.want = name,\n> +\t\tstruct refname_needle_lesseq_args arg = {\n\nnit: In the other commits we use `args`. Do we want to be consistent?\n\n-Justin\n\n> +\t\t\t.haystack = mod->del,\n> +\t\t\t.needle = name,\n> \t\t};\n> -\t\tsize_t idx = binsearch(mod->del_len, find_name, &arg);\n> +\t\tsize_t idx = binsearch(mod->del_len, refname_needle_lesseq, &arg);\n> \t\tif (idx < mod->del_len && !strcmp(mod->del[idx], name))\n> \t\t\treturn 1;\n> \t}\n> @@ -71,11 +71,11 @@ static int modification_has_ref_with_prefix(struct modification *mod,\n> \tint err = 0;\n> \n> \tif (mod->add_len > 0) {\n> -\t\tstruct find_arg arg = {\n> -\t\t\t.names = mod->add,\n> -\t\t\t.want = prefix,\n> +\t\tstruct refname_needle_lesseq_args arg = {\n> +\t\t\t.haystack = mod->add,\n> +\t\t\t.needle = prefix,\n> \t\t};\n> -\t\tsize_t idx = binsearch(mod->add_len, find_name, &arg);\n> +\t\tsize_t idx = binsearch(mod->add_len, refname_needle_lesseq, &arg);\n> \t\tif (idx < mod->add_len &&\n> \t\t !strncmp(prefix, mod->add[idx], strlen(prefix)))\n> \t\t\tgoto done;\n> @@ -90,11 +90,11 @@ static int modification_has_ref_with_prefix(struct modification *mod,\n> \t\t\tgoto done;\n> \n> \t\tif (mod->del_len > 0) {\n> -\t\t\tstruct find_arg arg = {\n> -\t\t\t\t.names = mod->del,\n> -\t\t\t\t.want = ref.refname,\n> +\t\t\tstruct refname_needle_lesseq_args arg = {\n> +\t\t\t\t.haystack = mod->del,\n> +\t\t\t\t.needle = ref.refname,\n> \t\t\t};\n> -\t\t\tsize_t idx = binsearch(mod->del_len, find_name, &arg);\n> +\t\t\tsize_t idx = binsearch(mod->del_len, refname_needle_lesseq, &arg);\n> \t\t\tif (idx < mod->del_len &&\n> \t\t\t !strcmp(ref.refname, mod->del[idx]))\n> \t\t\t\tcontinue;\n> -- \n> 2.44.GIT\n> \n\n\n"},{"id":"492066","messageId":"45v2z6uszlkanwl5qhvio4ikrrytztohbmdpnmdwiefyznclum@xhbvlvnfmkmq","threadId":"61179","inReplyTo":"5e20d93ae000359f2231bf950a930cfc4898ced2.1711361340.git.ps@pks.im","subject":"Re: [PATCH v2 4/7] reftable/block: refactor binary search over restart points","fromName":"Justin Tobler","fromEmail":"jltobler@gmail.com","sentAt":"2024-04-02T16:42:29Z","receivedAt":"2024-04-02T16:43:27Z","isPatch":true,"sender":{"key":"jltobler@gmail.com","avatar":"https://avatars.githubusercontent.com/u/53454972?v=4"},"body":"On 24/03/25 11:10AM, Patrick Steinhardt wrote:\n> When seeking a record in our block reader we perform a binary search\n> over the block's restart points so that we don't have to do a linear\n> scan over the whole block. The logic to do so is quite intricate though,\n> which makes it hard to understand.\n> \n> Improve documentation and rename some of the functions and variables so\n> that the code becomes easier to understand overall. This refactoring\n> should not result in any change in behaviour.\n> \n> Signed-off-by: Patrick Steinhardt \n> ---\n... \n> -\ti = binsearch(br->restart_count, &restart_key_less, &args);\n> +\t/*\n> +\t * Perform a binary search over the block's restart points, which\n> +\t * avoids doing a linear scan over the whole block. Like this, we\n> +\t * identify the section of the block that should contain our key.\n> +\t *\n> +\t * Note that we explicitly search for the first restart point _greater_\n> +\t * than the sought-after record, not _greater or equal_ to it. In case\n> +\t * the sought-after record is located directly at the restart point we\n> +\t * would otherwise start doing the linear search at the preceding\n> +\t * restart point. While that works alright, we would end up scanning\n> +\t * too many record.\n> +\t */\n> +\ti = binsearch(br->restart_count, &restart_needle_less, &args);\n> +\n> +\t/*\n> +\t * Now there are multiple cases:\n> +\t *\n> +\t * - `i == 0`: The wanted record must be contained before the first\n> +\t * restart point. We will thus start searching for the record in\n> +\t * that section after accounting for the header offset.\n\nTo clarify my understanding, does a restart_offset not exist at the\nbeginning of a block? I was originally under the impression that the\nfirst reset point would be at the beginning of the block (or just after\nthe header). If this was the case, the first restart point being greater\nwould indicate that the wanted record is not contained within the block.\n\n-Justin\n\n> +\t *\n> +\t * - `i == restart_count`: The wanted record was not found at any of\n> +\t * the restart points. As there is no restart point at the end of\n> +\t * the section the record may thus be contained in the last block.\n> +\t *\n> +\t * - `i > 0`: The wanted record must be contained in the section\n> +\t * before the found restart point. We thus do a linear search\n> +\t * starting from the preceding restart point.\n> +\t */\n> \tif (i > 0)\n> \t\tit->next_off = block_reader_restart_offset(br, i - 1);\n> \telse\n> @@ -399,21 +429,34 @@ int block_reader_seek(struct block_reader *br, struct block_iter *it,\n> \n> \treftable_record_init(&rec, block_reader_type(br));\n> \n> -\t/* We're looking for the last entry less/equal than the wanted key, so\n> -\t we have to go one entry too far and then back up.\n> -\t*/\n> +\t/*\n> +\t * We're looking for the last entry less than the wanted key so that\n> +\t * the next call to `block_reader_next()` would yield the wanted\n> +\t * record. We thus don't want to position our reader at the sought\n> +\t * after record, but one before. To do so, we have to go one entry too\n> +\t * far and then back up.\n> +\t */\n> \twhile (1) {\n> \t\tblock_iter_copy_from(&next, it);\n> \t\terr = block_iter_next(&next, &rec);\n> \t\tif (err < 0)\n> \t\t\tgoto done;\n> -\n> -\t\treftable_record_key(&rec, &it->last_key);\n> -\t\tif (err > 0 || strbuf_cmp(&it->last_key, want) >= 0) {\n> +\t\tif (err > 0) {\n> \t\t\terr = 0;\n> \t\t\tgoto done;\n> \t\t}\n> \n> +\t\t/*\n> +\t\t * Check whether the current key is greater or equal to the\n> +\t\t * sought-after key. In case it is greater we know that the\n> +\t\t * record does not exist in the block and can thus abort early.\n> +\t\t * In case it is equal to the sought-after key we have found\n> +\t\t * the desired record.\n> +\t\t */\n> +\t\treftable_record_key(&rec, &it->last_key);\n> +\t\tif (strbuf_cmp(&it->last_key, want) >= 0)\n> +\t\t\tgoto done;\n> +\n> \t\tblock_iter_copy_from(it, &next);\n> \t}\n> \n> -- \n> 2.44.GIT\n> \n\n\n"},{"id":"492067","messageId":"eiyd2nmwxjaetkux4prwm6adcx7z77ry3wc62art6gnfklvgmw@hox32vwuu5sj","threadId":"61179","inReplyTo":"e751b3c536ace78f975b7d2553c22dbf6845a8d4.1711361340.git.ps@pks.im","subject":"Re: [PATCH v2 7/7] reftable/block: avoid decoding keys when searching restart points","fromName":"Justin Tobler","fromEmail":"jltobler@gmail.com","sentAt":"2024-04-02T16:47:16Z","receivedAt":"2024-04-02T16:48:15Z","isPatch":true,"sender":{"key":"jltobler@gmail.com","avatar":"https://avatars.githubusercontent.com/u/53454972?v=4"},"body":"On 24/03/25 11:11AM, Patrick Steinhardt wrote:\n> When searching over restart points in a block we decode the key of each\n> of the records, which results in a memory allocation. This is quite\n> pointless though given that records it restart points will never use\n> prefix compression and thus store their keys verbatim in the block.\n> \n> Refactor the code so that we can avoid decoding the keys, which saves us\n> some allocations.\n\nOut of curiousity, do you have any benchmarks around this change and\nwould that be something we would want to add to the commit message?\n\n-Justin\n\n> \n> Signed-off-by: Patrick Steinhardt \n> ---\n> reftable/block.c | 29 +++++++++++++++++++----------\n> 1 file changed, 19 insertions(+), 10 deletions(-)\n> \n> diff --git a/reftable/block.c b/reftable/block.c\n> index ca80a05e21..8bb4e43cec 100644\n> --- a/reftable/block.c\n> +++ b/reftable/block.c\n> @@ -287,23 +287,32 @@ static int restart_needle_less(size_t idx, void *_args)\n> \t\t.buf = args->reader->block.data + off,\n> \t\t.len = args->reader->block_len - off,\n> \t};\n> -\tstruct strbuf kth_restart_key = STRBUF_INIT;\n> -\tuint8_t unused_extra;\n> -\tint result, n;\n> +\tuint64_t prefix_len, suffix_len;\n> +\tuint8_t extra;\n> +\tint n;\n> \n> \t/*\n> -\t * TODO: The restart key is verbatim in the block, so we can in theory\n> -\t * avoid decoding the key and thus save some allocations.\n> +\t * Records at restart points are stored without prefix compression, so\n> +\t * there is no need to fully decode the record key here. This removes\n> +\t * the need for allocating memory.\n> \t */\n> -\tn = reftable_decode_key(&kth_restart_key, &unused_extra, in);\n> -\tif (n < 0) {\n> +\tn = reftable_decode_keylen(in, &prefix_len, &suffix_len, &extra);\n> +\tif (n < 0 || prefix_len) {\n> \t\targs->error = 1;\n> \t\treturn -1;\n> \t}\n> \n> -\tresult = strbuf_cmp(&args->needle, &kth_restart_key);\n> -\tstrbuf_release(&kth_restart_key);\n> -\treturn result < 0;\n> +\tstring_view_consume(&in, n);\n> +\tif (suffix_len > in.len) {\n> +\t\targs->error = 1;\n> +\t\treturn -1;\n> +\t}\n> +\n> +\tn = memcmp(args->needle.buf, in.buf,\n> +\t\t args->needle.len < suffix_len ? args->needle.len : suffix_len);\n> +\tif (n)\n> +\t\treturn n < 0;\n> +\treturn args->needle.len < suffix_len;\n> }\n> \n> void block_iter_copy_from(struct block_iter *dest, struct block_iter *src)\n> -- \n> 2.44.GIT\n> \n\n\n"},{"id":"492069","messageId":"Zgw9Jt9nkoupo38Q@tanuki","threadId":"61179","inReplyTo":"zvw6ezlchqyl5tq4zuia7az5b3i4swwvtm42muwe4i7gngswgz@ztujhb4ruewm","subject":"Re: [PATCH v2 3/7] reftable/refname: refactor binary search over refnames","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-04-02T17:15:18Z","receivedAt":"2024-04-02T17:15:25Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"On Tue, Apr 02, 2024 at 11:27:01AM -0500, Justin Tobler wrote:\n> On 24/03/25 11:10AM, Patrick Steinhardt wrote:\n> > It is comparatively hard to understand how exactly the binary search\n> > over refnames works given that the function and variable names are not\n> > exactly easy to grasp. Rename them to make this more obvious. This\n> > should not result in any change in behaviour.\n> > \n> > Signed-off-by: Patrick Steinhardt \n> > ---\n> > reftable/refname.c | 44 ++++++++++++++++++++++----------------------\n> > 1 file changed, 22 insertions(+), 22 deletions(-)\n> > \n> > diff --git a/reftable/refname.c b/reftable/refname.c\n> > index 64eba1b886..9ec488d727 100644\n> > --- a/reftable/refname.c\n> > +++ b/reftable/refname.c\n> > @@ -12,15 +12,15 @@\n> > #include \"refname.h\"\n> > #include \"reftable-iterator.h\"\n> > \n> > -struct find_arg {\n> > -\tchar **names;\n> > -\tconst char *want;\n> > +struct refname_needle_lesseq_args {\n> > +\tchar **haystack;\n> > +\tconst char *needle;\n> > };\n> > \n> > -static int find_name(size_t k, void *arg)\n> > +static int refname_needle_lesseq(size_t k, void *arg)\n> > {\n> > -\tstruct find_arg *f_arg = arg;\n> > -\treturn strcmp(f_arg->names[k], f_arg->want) >= 0;\n> > +\tstruct refname_needle_lesseq_args *f_arg = arg;\n> \n> nit: Looks like the `f_arg` variable name is a remnant from when the\n> type was called `find_arg`. Do we want to rename this to `args`? We \n> could also rename `void *arg` to `void *_args`.\n\nYup.\n\n> > +\treturn strcmp(f_arg->needle, f_arg->haystack[k]) <= 0;\n> > }\n> > \n> > static int modification_has_ref(struct modification *mod, const char *name)\n> > @@ -29,21 +29,21 @@ static int modification_has_ref(struct modification *mod, const char *name)\n> > \tint err = 0;\n> > \n> > \tif (mod->add_len > 0) {\n> > -\t\tstruct find_arg arg = {\n> > -\t\t\t.names = mod->add,\n> > -\t\t\t.want = name,\n> > +\t\tstruct refname_needle_lesseq_args arg = {\n> > +\t\t\t.haystack = mod->add,\n> > +\t\t\t.needle = name,\n> > \t\t};\n> > -\t\tsize_t idx = binsearch(mod->add_len, find_name, &arg);\n> > +\t\tsize_t idx = binsearch(mod->add_len, refname_needle_lesseq, &arg);\n> > \t\tif (idx < mod->add_len && !strcmp(mod->add[idx], name))\n> > \t\t\treturn 0;\n> > \t}\n> > \n> > \tif (mod->del_len > 0) {\n> > -\t\tstruct find_arg arg = {\n> > -\t\t\t.names = mod->del,\n> > -\t\t\t.want = name,\n> > +\t\tstruct refname_needle_lesseq_args arg = {\n> \n> nit: In the other commits we use `args`. Do we want to be consistent?\n\nYeah. Given that it was my own argument to be consistent across\ncallsites I should rather make it truly consistent :)\n\nPatrick\n\n> -Justin\n> \n> > +\t\t\t.haystack = mod->del,\n> > +\t\t\t.needle = name,\n> > \t\t};\n> > -\t\tsize_t idx = binsearch(mod->del_len, find_name, &arg);\n> > +\t\tsize_t idx = binsearch(mod->del_len, refname_needle_lesseq, &arg);\n> > \t\tif (idx < mod->del_len && !strcmp(mod->del[idx], name))\n> > \t\t\treturn 1;\n> > \t}\n> > @@ -71,11 +71,11 @@ static int modification_has_ref_with_prefix(struct modification *mod,\n> > \tint err = 0;\n> > \n> > \tif (mod->add_len > 0) {\n> > -\t\tstruct find_arg arg = {\n> > -\t\t\t.names = mod->add,\n> > -\t\t\t.want = prefix,\n> > +\t\tstruct refname_needle_lesseq_args arg = {\n> > +\t\t\t.haystack = mod->add,\n> > +\t\t\t.needle = prefix,\n> > \t\t};\n> > -\t\tsize_t idx = binsearch(mod->add_len, find_name, &arg);\n> > +\t\tsize_t idx = binsearch(mod->add_len, refname_needle_lesseq, &arg);\n> > \t\tif (idx < mod->add_len &&\n> > \t\t !strncmp(prefix, mod->add[idx], strlen(prefix)))\n> > \t\t\tgoto done;\n> > @@ -90,11 +90,11 @@ static int modification_has_ref_with_prefix(struct modification *mod,\n> > \t\t\tgoto done;\n> > \n> > \t\tif (mod->del_len > 0) {\n> > -\t\t\tstruct find_arg arg = {\n> > -\t\t\t\t.names = mod->del,\n> > -\t\t\t\t.want = ref.refname,\n> > +\t\t\tstruct refname_needle_lesseq_args arg = {\n> > +\t\t\t\t.haystack = mod->del,\n> > +\t\t\t\t.needle = ref.refname,\n> > \t\t\t};\n> > -\t\t\tsize_t idx = binsearch(mod->del_len, find_name, &arg);\n> > +\t\t\tsize_t idx = binsearch(mod->del_len, refname_needle_lesseq, &arg);\n> > \t\t\tif (idx < mod->del_len &&\n> > \t\t\t !strcmp(ref.refname, mod->del[idx]))\n> > \t\t\t\tcontinue;\n> > -- \n> > 2.44.GIT\n> > \n> \n> \n"},{"id":"492070","messageId":"Zgw9PlgGDcmwLnDB@tanuki","threadId":"61179","inReplyTo":"45v2z6uszlkanwl5qhvio4ikrrytztohbmdpnmdwiefyznclum@xhbvlvnfmkmq","subject":"Re: [PATCH v2 4/7] reftable/block: refactor binary search over restart points","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-04-02T17:15:42Z","receivedAt":"2024-04-02T17:15:46Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"On Tue, Apr 02, 2024 at 11:42:29AM -0500, Justin Tobler wrote:\n> On 24/03/25 11:10AM, Patrick Steinhardt wrote:\n> > When seeking a record in our block reader we perform a binary search\n> > over the block's restart points so that we don't have to do a linear\n> > scan over the whole block. The logic to do so is quite intricate though,\n> > which makes it hard to understand.\n> > \n> > Improve documentation and rename some of the functions and variables so\n> > that the code becomes easier to understand overall. This refactoring\n> > should not result in any change in behaviour.\n> > \n> > Signed-off-by: Patrick Steinhardt \n> > ---\n> ... \n> > -\ti = binsearch(br->restart_count, &restart_key_less, &args);\n> > +\t/*\n> > +\t * Perform a binary search over the block's restart points, which\n> > +\t * avoids doing a linear scan over the whole block. Like this, we\n> > +\t * identify the section of the block that should contain our key.\n> > +\t *\n> > +\t * Note that we explicitly search for the first restart point _greater_\n> > +\t * than the sought-after record, not _greater or equal_ to it. In case\n> > +\t * the sought-after record is located directly at the restart point we\n> > +\t * would otherwise start doing the linear search at the preceding\n> > +\t * restart point. While that works alright, we would end up scanning\n> > +\t * too many record.\n> > +\t */\n> > +\ti = binsearch(br->restart_count, &restart_needle_less, &args);\n> > +\n> > +\t/*\n> > +\t * Now there are multiple cases:\n> > +\t *\n> > +\t * - `i == 0`: The wanted record must be contained before the first\n> > +\t * restart point. We will thus start searching for the record in\n> > +\t * that section after accounting for the header offset.\n> \n> To clarify my understanding, does a restart_offset not exist at the\n> beginning of a block? I was originally under the impression that the\n> first reset point would be at the beginning of the block (or just after\n> the header). If this was the case, the first restart point being greater\n> would indicate that the wanted record is not contained within the block.\n\nIt wouldn't make much sense to include it as a restart point. A restart\npoint is a point where the prefix compression will be reset such that\nthe record at that point can be read without reading preceding records.\nThis is always implicitly true for the first record in a block as it is\nnever prefix-compressed. Consequently, writing a restart point for the\nfirst record would be a waste of disk space.\n\nPatrick\n\n> -Justin\n> \n> > +\t *\n> > +\t * - `i == restart_count`: The wanted record was not found at any of\n> > +\t * the restart points. As there is no restart point at the end of\n> > +\t * the section the record may thus be contained in the last block.\n> > +\t *\n> > +\t * - `i > 0`: The wanted record must be contained in the section\n> > +\t * before the found restart point. We thus do a linear search\n> > +\t * starting from the preceding restart point.\n> > +\t */\n> > \tif (i > 0)\n> > \t\tit->next_off = block_reader_restart_offset(br, i - 1);\n> > \telse\n> > @@ -399,21 +429,34 @@ int block_reader_seek(struct block_reader *br, struct block_iter *it,\n> > \n> > \treftable_record_init(&rec, block_reader_type(br));\n> > \n> > -\t/* We're looking for the last entry less/equal than the wanted key, so\n> > -\t we have to go one entry too far and then back up.\n> > -\t*/\n> > +\t/*\n> > +\t * We're looking for the last entry less than the wanted key so that\n> > +\t * the next call to `block_reader_next()` would yield the wanted\n> > +\t * record. We thus don't want to position our reader at the sought\n> > +\t * after record, but one before. To do so, we have to go one entry too\n> > +\t * far and then back up.\n> > +\t */\n> > \twhile (1) {\n> > \t\tblock_iter_copy_from(&next, it);\n> > \t\terr = block_iter_next(&next, &rec);\n> > \t\tif (err < 0)\n> > \t\t\tgoto done;\n> > -\n> > -\t\treftable_record_key(&rec, &it->last_key);\n> > -\t\tif (err > 0 || strbuf_cmp(&it->last_key, want) >= 0) {\n> > +\t\tif (err > 0) {\n> > \t\t\terr = 0;\n> > \t\t\tgoto done;\n> > \t\t}\n> > \n> > +\t\t/*\n> > +\t\t * Check whether the current key is greater or equal to the\n> > +\t\t * sought-after key. In case it is greater we know that the\n> > +\t\t * record does not exist in the block and can thus abort early.\n> > +\t\t * In case it is equal to the sought-after key we have found\n> > +\t\t * the desired record.\n> > +\t\t */\n> > +\t\treftable_record_key(&rec, &it->last_key);\n> > +\t\tif (strbuf_cmp(&it->last_key, want) >= 0)\n> > +\t\t\tgoto done;\n> > +\n> > \t\tblock_iter_copy_from(it, &next);\n> > \t}\n> > \n> > -- \n> > 2.44.GIT\n> > \n> \n> \n"},{"id":"492071","messageId":"Zgw9RByBo8sKpeRf@tanuki","threadId":"61179","inReplyTo":"eiyd2nmwxjaetkux4prwm6adcx7z77ry3wc62art6gnfklvgmw@hox32vwuu5sj","subject":"Re: [PATCH v2 7/7] reftable/block: avoid decoding keys when searching restart points","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-04-02T17:15:48Z","receivedAt":"2024-04-02T17:15:52Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"On Tue, Apr 02, 2024 at 11:47:16AM -0500, Justin Tobler wrote:\n> On 24/03/25 11:11AM, Patrick Steinhardt wrote:\n> > When searching over restart points in a block we decode the key of each\n> > of the records, which results in a memory allocation. This is quite\n> > pointless though given that records it restart points will never use\n> > prefix compression and thus store their keys verbatim in the block.\n> > \n> > Refactor the code so that we can avoid decoding the keys, which saves us\n> > some allocations.\n> \n> Out of curiousity, do you have any benchmarks around this change and\n> would that be something we would want to add to the commit message?\n\nI don't have a benchmark. The problem is that the difference isn't\nreally measureable when doing a single seek, only, because seeks are\nsimply too fast. The only usecase where I know that there are a ton of\nof record seeks are writes, but here the performance improvement is\ngetting drowned out by everything else.\n\nYou can try to measure allocations and indeed see a difference. But\nagain, this is getting drowned out by the noise for writes. With my\nblock reader refactorings (ps/reftable-block-iteration-optim) you can\nsee the difference when iterating through refs. Before:\n\n HEAP SUMMARY:\n in use at exit: 13,603 bytes in 125 blocks\n total heap usage: 314 allocs, 189 frees, 106,035 bytes allocated\n\nAfter:\n\n HEAP SUMMARY:\n in use at exit: 13,603 bytes in 125 blocks\n total heap usage: 303 allocs, 178 frees, 105,763 bytes allocated\n\nBut yeah, it's nothing that'd make you go \"Oh, wow!\". As said, it will\nadd up when doing many seeks, but I didn't manage to find a proper\nbenchamrk yet that would be worthy to make it into the commit message.\n\nPatrick\n\n> -Justin\n> \n> > \n> > Signed-off-by: Patrick Steinhardt \n> > ---\n> > reftable/block.c | 29 +++++++++++++++++++----------\n> > 1 file changed, 19 insertions(+), 10 deletions(-)\n> > \n> > diff --git a/reftable/block.c b/reftable/block.c\n> > index ca80a05e21..8bb4e43cec 100644\n> > --- a/reftable/block.c\n> > +++ b/reftable/block.c\n> > @@ -287,23 +287,32 @@ static int restart_needle_less(size_t idx, void *_args)\n> > \t\t.buf = args->reader->block.data + off,\n> > \t\t.len = args->reader->block_len - off,\n> > \t};\n> > -\tstruct strbuf kth_restart_key = STRBUF_INIT;\n> > -\tuint8_t unused_extra;\n> > -\tint result, n;\n> > +\tuint64_t prefix_len, suffix_len;\n> > +\tuint8_t extra;\n> > +\tint n;\n> > \n> > \t/*\n> > -\t * TODO: The restart key is verbatim in the block, so we can in theory\n> > -\t * avoid decoding the key and thus save some allocations.\n> > +\t * Records at restart points are stored without prefix compression, so\n> > +\t * there is no need to fully decode the record key here. This removes\n> > +\t * the need for allocating memory.\n> > \t */\n> > -\tn = reftable_decode_key(&kth_restart_key, &unused_extra, in);\n> > -\tif (n < 0) {\n> > +\tn = reftable_decode_keylen(in, &prefix_len, &suffix_len, &extra);\n> > +\tif (n < 0 || prefix_len) {\n> > \t\targs->error = 1;\n> > \t\treturn -1;\n> > \t}\n> > \n> > -\tresult = strbuf_cmp(&args->needle, &kth_restart_key);\n> > -\tstrbuf_release(&kth_restart_key);\n> > -\treturn result < 0;\n> > +\tstring_view_consume(&in, n);\n> > +\tif (suffix_len > in.len) {\n> > +\t\targs->error = 1;\n> > +\t\treturn -1;\n> > +\t}\n> > +\n> > +\tn = memcmp(args->needle.buf, in.buf,\n> > +\t\t args->needle.len < suffix_len ? args->needle.len : suffix_len);\n> > +\tif (n)\n> > +\t\treturn n < 0;\n> > +\treturn args->needle.len < suffix_len;\n> > }\n> > \n> > void block_iter_copy_from(struct block_iter *dest, struct block_iter *src)\n> > -- \n> > 2.44.GIT\n> > \n> \n> \n"},{"id":"492075","messageId":"cover.1712078263.git.ps@pks.im","threadId":"61179","inReplyTo":"cover.1711109214.git.ps@pks.im","subject":"[PATCH v3 0/7] reftable: improvements for the `binsearch()` mechanism","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-04-02T17:24:37Z","receivedAt":"2024-04-02T17:24:42Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"Hi,\n\nthis is the third version of my patch series that refactors the\n`binsearch()` mechanism in the reftable library. There's only a single\nchange compared to v2, namely a rename of some arguments when calling\n`refname_needle_lesseq()`.\n\nThanks!\n\nPatrick\n\nPatrick Steinhardt (7):\n reftable/basics: fix return type of `binsearch()` to be `size_t`\n reftable/basics: improve `binsearch()` test\n reftable/refname: refactor binary search over refnames\n reftable/block: refactor binary search over restart points\n reftable/block: fix error handling when searching restart points\n reftable/record: extract function to decode key lengths\n reftable/block: avoid decoding keys when searching restart points\n\n reftable/basics.c | 7 ++-\n reftable/basics.h | 7 +--\n reftable/basics_test.c | 55 +++++++++++---------\n reftable/block.c | 114 ++++++++++++++++++++++++++++++-----------\n reftable/record.c | 34 ++++++++----\n reftable/record.h | 6 +++\n reftable/refname.c | 53 +++++++++----------\n 7 files changed, 179 insertions(+), 97 deletions(-)\n\nRange-diff against v2:\n1: cd82ac6531 = 1: baa07ef144 reftable/basics: fix return type of `binsearch()` to be `size_t`\n2: a277d4fa6f = 2: cbc2a107c1 reftable/basics: improve `binsearch()` test\n3: 9ffcf45c32 ! 3: f5bf65e0dd reftable/refname: refactor binary search over refnames\n @@ reftable/refname.c\n };\n \n -static int find_name(size_t k, void *arg)\n -+static int refname_needle_lesseq(size_t k, void *arg)\n ++static int refname_needle_lesseq(size_t k, void *_args)\n {\n -\tstruct find_arg *f_arg = arg;\n -\treturn strcmp(f_arg->names[k], f_arg->want) >= 0;\n -+\tstruct refname_needle_lesseq_args *f_arg = arg;\n -+\treturn strcmp(f_arg->needle, f_arg->haystack[k]) <= 0;\n ++\tstruct refname_needle_lesseq_args *args = _args;\n ++\treturn strcmp(args->needle, args->haystack[k]) <= 0;\n }\n \n static int modification_has_ref(struct modification *mod, const char *name)\n @@ reftable/refname.c: static int modification_has_ref(struct modification *mod, co\n -\t\tstruct find_arg arg = {\n -\t\t\t.names = mod->add,\n -\t\t\t.want = name,\n -+\t\tstruct refname_needle_lesseq_args arg = {\n ++\t\tstruct refname_needle_lesseq_args args = {\n +\t\t\t.haystack = mod->add,\n +\t\t\t.needle = name,\n \t\t};\n -\t\tsize_t idx = binsearch(mod->add_len, find_name, &arg);\n -+\t\tsize_t idx = binsearch(mod->add_len, refname_needle_lesseq, &arg);\n ++\t\tsize_t idx = binsearch(mod->add_len, refname_needle_lesseq, &args);\n \t\tif (idx < mod->add_len && !strcmp(mod->add[idx], name))\n \t\t\treturn 0;\n \t}\n @@ reftable/refname.c: static int modification_has_ref(struct modification *mod, co\n -\t\tstruct find_arg arg = {\n -\t\t\t.names = mod->del,\n -\t\t\t.want = name,\n -+\t\tstruct refname_needle_lesseq_args arg = {\n ++\t\tstruct refname_needle_lesseq_args args = {\n +\t\t\t.haystack = mod->del,\n +\t\t\t.needle = name,\n \t\t};\n -\t\tsize_t idx = binsearch(mod->del_len, find_name, &arg);\n -+\t\tsize_t idx = binsearch(mod->del_len, refname_needle_lesseq, &arg);\n ++\t\tsize_t idx = binsearch(mod->del_len, refname_needle_lesseq, &args);\n \t\tif (idx < mod->del_len && !strcmp(mod->del[idx], name))\n \t\t\treturn 1;\n \t}\n @@ reftable/refname.c: static int modification_has_ref_with_prefix(struct modificat\n -\t\tstruct find_arg arg = {\n -\t\t\t.names = mod->add,\n -\t\t\t.want = prefix,\n -+\t\tstruct refname_needle_lesseq_args arg = {\n ++\t\tstruct refname_needle_lesseq_args args = {\n +\t\t\t.haystack = mod->add,\n +\t\t\t.needle = prefix,\n \t\t};\n -\t\tsize_t idx = binsearch(mod->add_len, find_name, &arg);\n -+\t\tsize_t idx = binsearch(mod->add_len, refname_needle_lesseq, &arg);\n ++\t\tsize_t idx = binsearch(mod->add_len, refname_needle_lesseq, &args);\n \t\tif (idx < mod->add_len &&\n \t\t !strncmp(prefix, mod->add[idx], strlen(prefix)))\n \t\t\tgoto done;\n @@ reftable/refname.c: static int modification_has_ref_with_prefix(struct modificat\n -\t\t\tstruct find_arg arg = {\n -\t\t\t\t.names = mod->del,\n -\t\t\t\t.want = ref.refname,\n -+\t\t\tstruct refname_needle_lesseq_args arg = {\n ++\t\t\tstruct refname_needle_lesseq_args args = {\n +\t\t\t\t.haystack = mod->del,\n +\t\t\t\t.needle = ref.refname,\n \t\t\t};\n -\t\t\tsize_t idx = binsearch(mod->del_len, find_name, &arg);\n -+\t\t\tsize_t idx = binsearch(mod->del_len, refname_needle_lesseq, &arg);\n ++\t\t\tsize_t idx = binsearch(mod->del_len, refname_needle_lesseq, &args);\n \t\t\tif (idx < mod->del_len &&\n \t\t\t !strcmp(ref.refname, mod->del[idx]))\n \t\t\t\tcontinue;\n4: 5e20d93ae0 = 4: 435cd0be94 reftable/block: refactor binary search over restart points\n5: 5bbeab114f = 5: 8d8abfd290 reftable/block: fix error handling when searching restart points\n6: 271bacb210 = 6: f87f7ad01a reftable/record: extract function to decode key lengths\n7: e751b3c536 = 7: f53bf9e1cc reftable/block: avoid decoding keys when searching restart points\n\nbase-commit: 11c821f2f2a31e70fb5cc449f9a29401c333aad2\n-- \n2.44.GIT\n\n"},{"id":"492076","messageId":"baa07ef14425ff45296c2eb677c07b085bacafb3.1712078263.git.ps@pks.im","threadId":"61179","inReplyTo":"cover.1712078263.git.ps@pks.im","subject":"[PATCH v3 1/7] reftable/basics: fix return type of `binsearch()` to be `size_t`","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-04-02T17:24:41Z","receivedAt":"2024-04-02T17:24:45Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"The `binsearch()` function can be used to find the first element for\nwhich a callback functions returns a truish value. But while the array\nsize is of type `size_t`, the function in fact returns an `int` that is\nsupposed to index into that array.\n\nFix the function signature to return a `size_t`. This conversion does\nnot change any semantics given that the function would only ever return\na value in the range `[0, sz]` anyway.\n\nSigned-off-by: Patrick Steinhardt \n---\n reftable/basics.c | 2 +-\n reftable/basics.h | 2 +-\n reftable/basics_test.c | 6 +++---\n reftable/block.c | 3 ++-\n reftable/refname.c | 17 +++++++----------\n 5 files changed, 14 insertions(+), 16 deletions(-)\n\ndiff --git a/reftable/basics.c b/reftable/basics.c\nindex 0785aff941..2c5f34b39e 100644\n--- a/reftable/basics.c\n+++ b/reftable/basics.c\n@@ -27,7 +27,7 @@ void put_be16(uint8_t *out, uint16_t i)\n \tout[1] = (uint8_t)(i & 0xff);\n }\n \n-int binsearch(size_t sz, int (*f)(size_t k, void *args), void *args)\n+size_t binsearch(size_t sz, int (*f)(size_t k, void *args), void *args)\n {\n \tsize_t lo = 0;\n \tsize_t hi = sz;\ndiff --git a/reftable/basics.h b/reftable/basics.h\nindex 91f3533efe..2672520e76 100644\n--- a/reftable/basics.h\n+++ b/reftable/basics.h\n@@ -28,7 +28,7 @@ void put_be16(uint8_t *out, uint16_t i);\n * Contrary to bsearch(3), this returns something useful if the argument is not\n * found.\n */\n-int binsearch(size_t sz, int (*f)(size_t k, void *args), void *args);\n+size_t binsearch(size_t sz, int (*f)(size_t k, void *args), void *args);\n \n /*\n * Frees a NULL terminated array of malloced strings. The array itself is also\ndiff --git a/reftable/basics_test.c b/reftable/basics_test.c\nindex 1fcd229725..dc1c87c5df 100644\n--- a/reftable/basics_test.c\n+++ b/reftable/basics_test.c\n@@ -34,15 +34,15 @@ static void test_binsearch(void)\n \n \tint i = 0;\n \tfor (i = 1; i < 11; i++) {\n-\t\tint res;\n+\t\tsize_t res;\n+\n \t\targs.key = i;\n \t\tres = binsearch(sz, &binsearch_func, &args);\n \n \t\tif (res < sz) {\n \t\t\tEXPECT(args.key < arr[res]);\n-\t\t\tif (res > 0) {\n+\t\t\tif (res > 0)\n \t\t\t\tEXPECT(args.key >= arr[res - 1]);\n-\t\t\t}\n \t\t} else {\n \t\t\tEXPECT(args.key == 10 || args.key == 11);\n \t\t}\ndiff --git a/reftable/block.c b/reftable/block.c\nindex e2a2cee58d..422885bddb 100644\n--- a/reftable/block.c\n+++ b/reftable/block.c\n@@ -382,7 +382,8 @@ int block_reader_seek(struct block_reader *br, struct block_iter *it,\n \t};\n \tstruct block_iter next = BLOCK_ITER_INIT;\n \tstruct reftable_record rec;\n-\tint err = 0, i;\n+\tint err = 0;\n+\tsize_t i;\n \n \tif (args.error) {\n \t\terr = REFTABLE_FORMAT_ERROR;\ndiff --git a/reftable/refname.c b/reftable/refname.c\nindex 7570e4acf9..64eba1b886 100644\n--- a/reftable/refname.c\n+++ b/reftable/refname.c\n@@ -33,10 +33,9 @@ static int modification_has_ref(struct modification *mod, const char *name)\n \t\t\t.names = mod->add,\n \t\t\t.want = name,\n \t\t};\n-\t\tint idx = binsearch(mod->add_len, find_name, &arg);\n-\t\tif (idx < mod->add_len && !strcmp(mod->add[idx], name)) {\n+\t\tsize_t idx = binsearch(mod->add_len, find_name, &arg);\n+\t\tif (idx < mod->add_len && !strcmp(mod->add[idx], name))\n \t\t\treturn 0;\n-\t\t}\n \t}\n \n \tif (mod->del_len > 0) {\n@@ -44,10 +43,9 @@ static int modification_has_ref(struct modification *mod, const char *name)\n \t\t\t.names = mod->del,\n \t\t\t.want = name,\n \t\t};\n-\t\tint idx = binsearch(mod->del_len, find_name, &arg);\n-\t\tif (idx < mod->del_len && !strcmp(mod->del[idx], name)) {\n+\t\tsize_t idx = binsearch(mod->del_len, find_name, &arg);\n+\t\tif (idx < mod->del_len && !strcmp(mod->del[idx], name))\n \t\t\treturn 1;\n-\t\t}\n \t}\n \n \terr = reftable_table_read_ref(&mod->tab, name, &ref);\n@@ -77,7 +75,7 @@ static int modification_has_ref_with_prefix(struct modification *mod,\n \t\t\t.names = mod->add,\n \t\t\t.want = prefix,\n \t\t};\n-\t\tint idx = binsearch(mod->add_len, find_name, &arg);\n+\t\tsize_t idx = binsearch(mod->add_len, find_name, &arg);\n \t\tif (idx < mod->add_len &&\n \t\t !strncmp(prefix, mod->add[idx], strlen(prefix)))\n \t\t\tgoto done;\n@@ -96,11 +94,10 @@ static int modification_has_ref_with_prefix(struct modification *mod,\n \t\t\t\t.names = mod->del,\n \t\t\t\t.want = ref.refname,\n \t\t\t};\n-\t\t\tint idx = binsearch(mod->del_len, find_name, &arg);\n+\t\t\tsize_t idx = binsearch(mod->del_len, find_name, &arg);\n \t\t\tif (idx < mod->del_len &&\n-\t\t\t !strcmp(ref.refname, mod->del[idx])) {\n+\t\t\t !strcmp(ref.refname, mod->del[idx]))\n \t\t\t\tcontinue;\n-\t\t\t}\n \t\t}\n \n \t\tif (strncmp(ref.refname, prefix, strlen(prefix))) {\n-- \n2.44.GIT\n\n"},{"id":"492077","messageId":"cbc2a107c1c067a0c6891bfeb33f2311f2f072b4.1712078263.git.ps@pks.im","threadId":"61179","inReplyTo":"cover.1712078263.git.ps@pks.im","subject":"[PATCH v3 2/7] reftable/basics: improve `binsearch()` test","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-04-02T17:24:45Z","receivedAt":"2024-04-02T17:24:49Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"The `binsearch()` test is somewhat weird in that it doesn't explicitly\nspell out its expectations. Instead it does so in a rather ad-hoc way\nwith some hard-to-understand computations.\n\nRefactor the test to spell out the needle as well as expected index for\nall testcases. This refactoring highlights that the `binsearch_func()`\nis written somewhat weirdly to find the first integer smaller than the\nneedle, not smaller or equal to it. Adjust the function accordingly.\n\nWhile at it, rename the callback function to better convey its meaning.\n\nSigned-off-by: Patrick Steinhardt \n---\n reftable/basics_test.c | 55 ++++++++++++++++++++++++------------------\n 1 file changed, 31 insertions(+), 24 deletions(-)\n\ndiff --git a/reftable/basics_test.c b/reftable/basics_test.c\nindex dc1c87c5df..997c4d9e01 100644\n--- a/reftable/basics_test.c\n+++ b/reftable/basics_test.c\n@@ -12,40 +12,47 @@ license that can be found in the LICENSE file or at\n #include \"test_framework.h\"\n #include \"reftable-tests.h\"\n \n-struct binsearch_args {\n-\tint key;\n-\tint *arr;\n+struct integer_needle_lesseq_args {\n+\tint needle;\n+\tint *haystack;\n };\n \n-static int binsearch_func(size_t i, void *void_args)\n+static int integer_needle_lesseq(size_t i, void *_args)\n {\n-\tstruct binsearch_args *args = void_args;\n-\n-\treturn args->key < args->arr[i];\n+\tstruct integer_needle_lesseq_args *args = _args;\n+\treturn args->needle <= args->haystack[i];\n }\n \n static void test_binsearch(void)\n {\n-\tint arr[] = { 2, 4, 6, 8, 10 };\n-\tsize_t sz = ARRAY_SIZE(arr);\n-\tstruct binsearch_args args = {\n-\t\t.arr = arr,\n+\tint haystack[] = { 2, 4, 6, 8, 10 };\n+\tstruct {\n+\t\tint needle;\n+\t\tsize_t expected_idx;\n+\t} testcases[] = {\n+\t\t{-9000, 0},\n+\t\t{-1, 0},\n+\t\t{0, 0},\n+\t\t{2, 0},\n+\t\t{3, 1},\n+\t\t{4, 1},\n+\t\t{7, 3},\n+\t\t{9, 4},\n+\t\t{10, 4},\n+\t\t{11, 5},\n+\t\t{9000, 5},\n \t};\n+\tsize_t i = 0;\n \n-\tint i = 0;\n-\tfor (i = 1; i < 11; i++) {\n-\t\tsize_t res;\n-\n-\t\targs.key = i;\n-\t\tres = binsearch(sz, &binsearch_func, &args);\n+\tfor (i = 0; i < ARRAY_SIZE(testcases); i++) {\n+\t\tstruct integer_needle_lesseq_args args = {\n+\t\t\t.haystack = haystack,\n+\t\t\t.needle = testcases[i].needle,\n+\t\t};\n+\t\tsize_t idx;\n \n-\t\tif (res < sz) {\n-\t\t\tEXPECT(args.key < arr[res]);\n-\t\t\tif (res > 0)\n-\t\t\t\tEXPECT(args.key >= arr[res - 1]);\n-\t\t} else {\n-\t\t\tEXPECT(args.key == 10 || args.key == 11);\n-\t\t}\n+\t\tidx = binsearch(ARRAY_SIZE(haystack), &integer_needle_lesseq, &args);\n+\t\tEXPECT(idx == testcases[i].expected_idx);\n \t}\n }\n \n-- \n2.44.GIT\n\n"},{"id":"492078","messageId":"f5bf65e0dde70e7753e715b1fd207ef0e556669c.1712078263.git.ps@pks.im","threadId":"61179","inReplyTo":"cover.1712078263.git.ps@pks.im","subject":"[PATCH v3 3/7] reftable/refname: refactor binary search over refnames","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-04-02T17:24:49Z","receivedAt":"2024-04-02T17:24:53Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"It is comparatively hard to understand how exactly the binary search\nover refnames works given that the function and variable names are not\nexactly easy to grasp. Rename them to make this more obvious. This\nshould not result in any change in behaviour.\n\nSigned-off-by: Patrick Steinhardt \n---\n reftable/refname.c | 44 ++++++++++++++++++++++----------------------\n 1 file changed, 22 insertions(+), 22 deletions(-)\n\ndiff --git a/reftable/refname.c b/reftable/refname.c\nindex 64eba1b886..bbfde15754 100644\n--- a/reftable/refname.c\n+++ b/reftable/refname.c\n@@ -12,15 +12,15 @@\n #include \"refname.h\"\n #include \"reftable-iterator.h\"\n \n-struct find_arg {\n-\tchar **names;\n-\tconst char *want;\n+struct refname_needle_lesseq_args {\n+\tchar **haystack;\n+\tconst char *needle;\n };\n \n-static int find_name(size_t k, void *arg)\n+static int refname_needle_lesseq(size_t k, void *_args)\n {\n-\tstruct find_arg *f_arg = arg;\n-\treturn strcmp(f_arg->names[k], f_arg->want) >= 0;\n+\tstruct refname_needle_lesseq_args *args = _args;\n+\treturn strcmp(args->needle, args->haystack[k]) <= 0;\n }\n \n static int modification_has_ref(struct modification *mod, const char *name)\n@@ -29,21 +29,21 @@ static int modification_has_ref(struct modification *mod, const char *name)\n \tint err = 0;\n \n \tif (mod->add_len > 0) {\n-\t\tstruct find_arg arg = {\n-\t\t\t.names = mod->add,\n-\t\t\t.want = name,\n+\t\tstruct refname_needle_lesseq_args args = {\n+\t\t\t.haystack = mod->add,\n+\t\t\t.needle = name,\n \t\t};\n-\t\tsize_t idx = binsearch(mod->add_len, find_name, &arg);\n+\t\tsize_t idx = binsearch(mod->add_len, refname_needle_lesseq, &args);\n \t\tif (idx < mod->add_len && !strcmp(mod->add[idx], name))\n \t\t\treturn 0;\n \t}\n \n \tif (mod->del_len > 0) {\n-\t\tstruct find_arg arg = {\n-\t\t\t.names = mod->del,\n-\t\t\t.want = name,\n+\t\tstruct refname_needle_lesseq_args args = {\n+\t\t\t.haystack = mod->del,\n+\t\t\t.needle = name,\n \t\t};\n-\t\tsize_t idx = binsearch(mod->del_len, find_name, &arg);\n+\t\tsize_t idx = binsearch(mod->del_len, refname_needle_lesseq, &args);\n \t\tif (idx < mod->del_len && !strcmp(mod->del[idx], name))\n \t\t\treturn 1;\n \t}\n@@ -71,11 +71,11 @@ static int modification_has_ref_with_prefix(struct modification *mod,\n \tint err = 0;\n \n \tif (mod->add_len > 0) {\n-\t\tstruct find_arg arg = {\n-\t\t\t.names = mod->add,\n-\t\t\t.want = prefix,\n+\t\tstruct refname_needle_lesseq_args args = {\n+\t\t\t.haystack = mod->add,\n+\t\t\t.needle = prefix,\n \t\t};\n-\t\tsize_t idx = binsearch(mod->add_len, find_name, &arg);\n+\t\tsize_t idx = binsearch(mod->add_len, refname_needle_lesseq, &args);\n \t\tif (idx < mod->add_len &&\n \t\t !strncmp(prefix, mod->add[idx], strlen(prefix)))\n \t\t\tgoto done;\n@@ -90,11 +90,11 @@ static int modification_has_ref_with_prefix(struct modification *mod,\n \t\t\tgoto done;\n \n \t\tif (mod->del_len > 0) {\n-\t\t\tstruct find_arg arg = {\n-\t\t\t\t.names = mod->del,\n-\t\t\t\t.want = ref.refname,\n+\t\t\tstruct refname_needle_lesseq_args args = {\n+\t\t\t\t.haystack = mod->del,\n+\t\t\t\t.needle = ref.refname,\n \t\t\t};\n-\t\t\tsize_t idx = binsearch(mod->del_len, find_name, &arg);\n+\t\t\tsize_t idx = binsearch(mod->del_len, refname_needle_lesseq, &args);\n \t\t\tif (idx < mod->del_len &&\n \t\t\t !strcmp(ref.refname, mod->del[idx]))\n \t\t\t\tcontinue;\n-- \n2.44.GIT\n\n"},{"id":"492079","messageId":"435cd0be949d65f53d2ccd1cdbfe13f097af5e50.1712078263.git.ps@pks.im","threadId":"61179","inReplyTo":"cover.1712078263.git.ps@pks.im","subject":"[PATCH v3 4/7] reftable/block: refactor binary search over restart points","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-04-02T17:24:53Z","receivedAt":"2024-04-02T17:24:57Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"When seeking a record in our block reader we perform a binary search\nover the block's restart points so that we don't have to do a linear\nscan over the whole block. The logic to do so is quite intricate though,\nwhich makes it hard to understand.\n\nImprove documentation and rename some of the functions and variables so\nthat the code becomes easier to understand overall. This refactoring\nshould not result in any change in behaviour.\n\nSigned-off-by: Patrick Steinhardt \n---\n reftable/block.c | 97 ++++++++++++++++++++++++++++++++++--------------\n 1 file changed, 70 insertions(+), 27 deletions(-)\n\ndiff --git a/reftable/block.c b/reftable/block.c\nindex 422885bddb..6cd4c053df 100644\n--- a/reftable/block.c\n+++ b/reftable/block.c\n@@ -273,34 +273,36 @@ void block_reader_start(struct block_reader *br, struct block_iter *it)\n \tit->next_off = br->header_off + 4;\n }\n \n-struct restart_find_args {\n+struct restart_needle_less_args {\n \tint error;\n-\tstruct strbuf key;\n-\tstruct block_reader *r;\n+\tstruct strbuf needle;\n+\tstruct block_reader *reader;\n };\n \n-static int restart_key_less(size_t idx, void *args)\n+static int restart_needle_less(size_t idx, void *_args)\n {\n-\tstruct restart_find_args *a = args;\n-\tuint32_t off = block_reader_restart_offset(a->r, idx);\n+\tstruct restart_needle_less_args *args = _args;\n+\tuint32_t off = block_reader_restart_offset(args->reader, idx);\n \tstruct string_view in = {\n-\t\t.buf = a->r->block.data + off,\n-\t\t.len = a->r->block_len - off,\n+\t\t.buf = args->reader->block.data + off,\n+\t\t.len = args->reader->block_len - off,\n \t};\n-\n-\t/* the restart key is verbatim in the block, so this could avoid the\n-\t alloc for decoding the key */\n-\tstruct strbuf rkey = STRBUF_INIT;\n+\tstruct strbuf kth_restart_key = STRBUF_INIT;\n \tuint8_t unused_extra;\n-\tint n = reftable_decode_key(&rkey, &unused_extra, in);\n-\tint result;\n+\tint result, n;\n+\n+\t/*\n+\t * TODO: The restart key is verbatim in the block, so we can in theory\n+\t * avoid decoding the key and thus save some allocations.\n+\t */\n+\tn = reftable_decode_key(&kth_restart_key, &unused_extra, in);\n \tif (n < 0) {\n-\t\ta->error = 1;\n+\t\targs->error = 1;\n \t\treturn -1;\n \t}\n \n-\tresult = strbuf_cmp(&a->key, &rkey);\n-\tstrbuf_release(&rkey);\n+\tresult = strbuf_cmp(&args->needle, &kth_restart_key);\n+\tstrbuf_release(&kth_restart_key);\n \treturn result < 0;\n }\n \n@@ -376,9 +378,9 @@ void block_iter_close(struct block_iter *it)\n int block_reader_seek(struct block_reader *br, struct block_iter *it,\n \t\t struct strbuf *want)\n {\n-\tstruct restart_find_args args = {\n-\t\t.key = *want,\n-\t\t.r = br,\n+\tstruct restart_needle_less_args args = {\n+\t\t.needle = *want,\n+\t\t.reader = br,\n \t};\n \tstruct block_iter next = BLOCK_ITER_INIT;\n \tstruct reftable_record rec;\n@@ -390,7 +392,35 @@ int block_reader_seek(struct block_reader *br, struct block_iter *it,\n \t\tgoto done;\n \t}\n \n-\ti = binsearch(br->restart_count, &restart_key_less, &args);\n+\t/*\n+\t * Perform a binary search over the block's restart points, which\n+\t * avoids doing a linear scan over the whole block. Like this, we\n+\t * identify the section of the block that should contain our key.\n+\t *\n+\t * Note that we explicitly search for the first restart point _greater_\n+\t * than the sought-after record, not _greater or equal_ to it. In case\n+\t * the sought-after record is located directly at the restart point we\n+\t * would otherwise start doing the linear search at the preceding\n+\t * restart point. While that works alright, we would end up scanning\n+\t * too many record.\n+\t */\n+\ti = binsearch(br->restart_count, &restart_needle_less, &args);\n+\n+\t/*\n+\t * Now there are multiple cases:\n+\t *\n+\t * - `i == 0`: The wanted record must be contained before the first\n+\t * restart point. We will thus start searching for the record in\n+\t * that section after accounting for the header offset.\n+\t *\n+\t * - `i == restart_count`: The wanted record was not found at any of\n+\t * the restart points. As there is no restart point at the end of\n+\t * the section the record may thus be contained in the last block.\n+\t *\n+\t * - `i > 0`: The wanted record must be contained in the section\n+\t * before the found restart point. We thus do a linear search\n+\t * starting from the preceding restart point.\n+\t */\n \tif (i > 0)\n \t\tit->next_off = block_reader_restart_offset(br, i - 1);\n \telse\n@@ -399,21 +429,34 @@ int block_reader_seek(struct block_reader *br, struct block_iter *it,\n \n \treftable_record_init(&rec, block_reader_type(br));\n \n-\t/* We're looking for the last entry less/equal than the wanted key, so\n-\t we have to go one entry too far and then back up.\n-\t*/\n+\t/*\n+\t * We're looking for the last entry less than the wanted key so that\n+\t * the next call to `block_reader_next()` would yield the wanted\n+\t * record. We thus don't want to position our reader at the sought\n+\t * after record, but one before. To do so, we have to go one entry too\n+\t * far and then back up.\n+\t */\n \twhile (1) {\n \t\tblock_iter_copy_from(&next, it);\n \t\terr = block_iter_next(&next, &rec);\n \t\tif (err < 0)\n \t\t\tgoto done;\n-\n-\t\treftable_record_key(&rec, &it->last_key);\n-\t\tif (err > 0 || strbuf_cmp(&it->last_key, want) >= 0) {\n+\t\tif (err > 0) {\n \t\t\terr = 0;\n \t\t\tgoto done;\n \t\t}\n \n+\t\t/*\n+\t\t * Check whether the current key is greater or equal to the\n+\t\t * sought-after key. In case it is greater we know that the\n+\t\t * record does not exist in the block and can thus abort early.\n+\t\t * In case it is equal to the sought-after key we have found\n+\t\t * the desired record.\n+\t\t */\n+\t\treftable_record_key(&rec, &it->last_key);\n+\t\tif (strbuf_cmp(&it->last_key, want) >= 0)\n+\t\t\tgoto done;\n+\n \t\tblock_iter_copy_from(it, &next);\n \t}\n \n-- \n2.44.GIT\n\n"},{"id":"492080","messageId":"8d8abfd2907e9e128fc7fa4a462be18312f105bc.1712078263.git.ps@pks.im","threadId":"61179","inReplyTo":"cover.1712078263.git.ps@pks.im","subject":"[PATCH v3 5/7] reftable/block: fix error handling when searching restart points","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-04-02T17:24:57Z","receivedAt":"2024-04-02T17:25:01Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"When doing the binary search over restart points in a block we need to\ndecode the record keys. This decoding step can result in an error when\nthe block is corrupted, which we indicate to the caller of the binary\nsearch by setting `args.error = 1`. But the only caller that exists\nmishandles this because it in fact performs the error check before\ncalling `binsearch()`.\n\nFix this bug by checking for errors at the right point in time.\nFurthermore, refactor `binsearch()` so that it aborts the search in case\nthe callback function returns a negative value so that we don't\nneedlessly continue to search the block.\n\nSigned-off-by: Patrick Steinhardt \n---\n reftable/basics.c | 5 ++++-\n reftable/basics.h | 5 +++--\n reftable/block.c | 9 ++++-----\n 3 files changed, 11 insertions(+), 8 deletions(-)\n\ndiff --git a/reftable/basics.c b/reftable/basics.c\nindex 2c5f34b39e..fea711db7e 100644\n--- a/reftable/basics.c\n+++ b/reftable/basics.c\n@@ -39,8 +39,11 @@ size_t binsearch(size_t sz, int (*f)(size_t k, void *args), void *args)\n \t */\n \twhile (hi - lo > 1) {\n \t\tsize_t mid = lo + (hi - lo) / 2;\n+\t\tint ret = f(mid, args);\n+\t\tif (ret < 0)\n+\t\t\treturn sz;\n \n-\t\tif (f(mid, args))\n+\t\tif (ret > 0)\n \t\t\thi = mid;\n \t\telse\n \t\t\tlo = mid;\ndiff --git a/reftable/basics.h b/reftable/basics.h\nindex 2672520e76..523ecd5307 100644\n--- a/reftable/basics.h\n+++ b/reftable/basics.h\n@@ -22,8 +22,9 @@ uint32_t get_be24(uint8_t *in);\n void put_be16(uint8_t *out, uint16_t i);\n \n /*\n- * find smallest index i in [0, sz) at which f(i) is true, assuming\n- * that f is ascending. Return sz if f(i) is false for all indices.\n+ * find smallest index i in [0, sz) at which `f(i) > 0`, assuming that f is\n+ * ascending. Return sz if `f(i) == 0` for all indices. The search is aborted\n+ * and `sz` is returned in case `f(i) < 0`.\n *\n * Contrary to bsearch(3), this returns something useful if the argument is not\n * found.\ndiff --git a/reftable/block.c b/reftable/block.c\nindex 6cd4c053df..ca80a05e21 100644\n--- a/reftable/block.c\n+++ b/reftable/block.c\n@@ -387,11 +387,6 @@ int block_reader_seek(struct block_reader *br, struct block_iter *it,\n \tint err = 0;\n \tsize_t i;\n \n-\tif (args.error) {\n-\t\terr = REFTABLE_FORMAT_ERROR;\n-\t\tgoto done;\n-\t}\n-\n \t/*\n \t * Perform a binary search over the block's restart points, which\n \t * avoids doing a linear scan over the whole block. Like this, we\n@@ -405,6 +400,10 @@ int block_reader_seek(struct block_reader *br, struct block_iter *it,\n \t * too many record.\n \t */\n \ti = binsearch(br->restart_count, &restart_needle_less, &args);\n+\tif (args.error) {\n+\t\terr = REFTABLE_FORMAT_ERROR;\n+\t\tgoto done;\n+\t}\n \n \t/*\n \t * Now there are multiple cases:\n-- \n2.44.GIT\n\n"},{"id":"492081","messageId":"f87f7ad01a5789b77a695c6e4e246dcb2b740000.1712078263.git.ps@pks.im","threadId":"61179","inReplyTo":"cover.1712078263.git.ps@pks.im","subject":"[PATCH v3 6/7] reftable/record: extract function to decode key lengths","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-04-02T17:25:01Z","receivedAt":"2024-04-02T17:25:05Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"We're about to refactor the binary search over restart points so that it\ndoes not need to fully decode the record keys anymore. To do so we will\nneed to decode the record key lengths, which is non-trivial logic.\n\nExtract the logic to decode these lengths from `refatble_decode_key()`\nso that we can reuse it.\n\nSigned-off-by: Patrick Steinhardt \n---\n reftable/record.c | 34 +++++++++++++++++++++++++---------\n reftable/record.h | 6 ++++++\n 2 files changed, 31 insertions(+), 9 deletions(-)\n\ndiff --git a/reftable/record.c b/reftable/record.c\nindex 23b497adab..5506f3e913 100644\n--- a/reftable/record.c\n+++ b/reftable/record.c\n@@ -159,26 +159,42 @@ int reftable_encode_key(int *restart, struct string_view dest,\n \treturn start.len - dest.len;\n }\n \n-int reftable_decode_key(struct strbuf *last_key, uint8_t *extra,\n-\t\t\tstruct string_view in)\n+int reftable_decode_keylen(struct string_view in,\n+\t\t\t uint64_t *prefix_len,\n+\t\t\t uint64_t *suffix_len,\n+\t\t\t uint8_t *extra)\n {\n-\tint start_len = in.len;\n-\tuint64_t prefix_len = 0;\n-\tuint64_t suffix_len = 0;\n+\tsize_t start_len = in.len;\n \tint n;\n \n-\tn = get_var_int(&prefix_len, &in);\n+\tn = get_var_int(prefix_len, &in);\n \tif (n < 0)\n \t\treturn -1;\n \tstring_view_consume(&in, n);\n \n-\tn = get_var_int(&suffix_len, &in);\n+\tn = get_var_int(suffix_len, &in);\n \tif (n <= 0)\n \t\treturn -1;\n \tstring_view_consume(&in, n);\n \n-\t*extra = (uint8_t)(suffix_len & 0x7);\n-\tsuffix_len >>= 3;\n+\t*extra = (uint8_t)(*suffix_len & 0x7);\n+\t*suffix_len >>= 3;\n+\n+\treturn start_len - in.len;\n+}\n+\n+int reftable_decode_key(struct strbuf *last_key, uint8_t *extra,\n+\t\t\tstruct string_view in)\n+{\n+\tint start_len = in.len;\n+\tuint64_t prefix_len = 0;\n+\tuint64_t suffix_len = 0;\n+\tint n;\n+\n+\tn = reftable_decode_keylen(in, &prefix_len, &suffix_len, extra);\n+\tif (n < 0)\n+\t\treturn -1;\n+\tstring_view_consume(&in, n);\n \n \tif (in.len < suffix_len ||\n \t prefix_len > last_key->len)\ndiff --git a/reftable/record.h b/reftable/record.h\nindex 826ee1c55c..d778133e6e 100644\n--- a/reftable/record.h\n+++ b/reftable/record.h\n@@ -86,6 +86,12 @@ int reftable_encode_key(int *is_restart, struct string_view dest,\n \t\t\tstruct strbuf prev_key, struct strbuf key,\n \t\t\tuint8_t extra);\n \n+/* Decode a record's key lengths. */\n+int reftable_decode_keylen(struct string_view in,\n+\t\t\t uint64_t *prefix_len,\n+\t\t\t uint64_t *suffix_len,\n+\t\t\t uint8_t *extra);\n+\n /*\n * Decode into `last_key` and `extra` from `in`. `last_key` is expected to\n * contain the decoded key of the preceding record, if any.\n-- \n2.44.GIT\n\n"},{"id":"492082","messageId":"f53bf9e1ccc27c6d0a0fc320c36ca58f24e2d204.1712078263.git.ps@pks.im","threadId":"61179","inReplyTo":"cover.1712078263.git.ps@pks.im","subject":"[PATCH v3 7/7] reftable/block: avoid decoding keys when searching restart points","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-04-02T17:25:05Z","receivedAt":"2024-04-02T17:25:09Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"When searching over restart points in a block we decode the key of each\nof the records, which results in a memory allocation. This is quite\npointless though given that records it restart points will never use\nprefix compression and thus store their keys verbatim in the block.\n\nRefactor the code so that we can avoid decoding the keys, which saves us\nsome allocations.\n\nSigned-off-by: Patrick Steinhardt \n---\n reftable/block.c | 29 +++++++++++++++++++----------\n 1 file changed, 19 insertions(+), 10 deletions(-)\n\ndiff --git a/reftable/block.c b/reftable/block.c\nindex ca80a05e21..8bb4e43cec 100644\n--- a/reftable/block.c\n+++ b/reftable/block.c\n@@ -287,23 +287,32 @@ static int restart_needle_less(size_t idx, void *_args)\n \t\t.buf = args->reader->block.data + off,\n \t\t.len = args->reader->block_len - off,\n \t};\n-\tstruct strbuf kth_restart_key = STRBUF_INIT;\n-\tuint8_t unused_extra;\n-\tint result, n;\n+\tuint64_t prefix_len, suffix_len;\n+\tuint8_t extra;\n+\tint n;\n \n \t/*\n-\t * TODO: The restart key is verbatim in the block, so we can in theory\n-\t * avoid decoding the key and thus save some allocations.\n+\t * Records at restart points are stored without prefix compression, so\n+\t * there is no need to fully decode the record key here. This removes\n+\t * the need for allocating memory.\n \t */\n-\tn = reftable_decode_key(&kth_restart_key, &unused_extra, in);\n-\tif (n < 0) {\n+\tn = reftable_decode_keylen(in, &prefix_len, &suffix_len, &extra);\n+\tif (n < 0 || prefix_len) {\n \t\targs->error = 1;\n \t\treturn -1;\n \t}\n \n-\tresult = strbuf_cmp(&args->needle, &kth_restart_key);\n-\tstrbuf_release(&kth_restart_key);\n-\treturn result < 0;\n+\tstring_view_consume(&in, n);\n+\tif (suffix_len > in.len) {\n+\t\targs->error = 1;\n+\t\treturn -1;\n+\t}\n+\n+\tn = memcmp(args->needle.buf, in.buf,\n+\t\t args->needle.len < suffix_len ? args->needle.len : suffix_len);\n+\tif (n)\n+\t\treturn n < 0;\n+\treturn args->needle.len < suffix_len;\n }\n \n void block_iter_copy_from(struct block_iter *dest, struct block_iter *src)\n-- \n2.44.GIT\n\n"},{"id":"492094","messageId":"ympg3oam4pty53qnxhtnla2xac73gdqsoclwsuzcmjd4dn4xre@j64veypnecrj","threadId":"61179","inReplyTo":"Zgw9PlgGDcmwLnDB@tanuki","subject":"Re: [PATCH v2 4/7] reftable/block: refactor binary search over restart points","fromName":"Justin Tobler","fromEmail":"jltobler@gmail.com","sentAt":"2024-04-02T17:46:30Z","receivedAt":"2024-04-02T17:47:28Z","isPatch":true,"sender":{"key":"jltobler@gmail.com","avatar":"https://avatars.githubusercontent.com/u/53454972?v=4"},"body":"On 24/04/02 07:15PM, Patrick Steinhardt wrote:\n> On Tue, Apr 02, 2024 at 11:42:29AM -0500, Justin Tobler wrote:\n> > On 24/03/25 11:10AM, Patrick Steinhardt wrote:\n> > > When seeking a record in our block reader we perform a binary search\n> > > over the block's restart points so that we don't have to do a linear\n> > > scan over the whole block. The logic to do so is quite intricate though,\n> > > which makes it hard to understand.\n> > > \n> > > Improve documentation and rename some of the functions and variables so\n> > > that the code becomes easier to understand overall. This refactoring\n> > > should not result in any change in behaviour.\n> > > \n> > > Signed-off-by: Patrick Steinhardt \n> > > ---\n> > ... \n> > > -\ti = binsearch(br->restart_count, &restart_key_less, &args);\n> > > +\t/*\n> > > +\t * Perform a binary search over the block's restart points, which\n> > > +\t * avoids doing a linear scan over the whole block. Like this, we\n> > > +\t * identify the section of the block that should contain our key.\n> > > +\t *\n> > > +\t * Note that we explicitly search for the first restart point _greater_\n> > > +\t * than the sought-after record, not _greater or equal_ to it. In case\n> > > +\t * the sought-after record is located directly at the restart point we\n> > > +\t * would otherwise start doing the linear search at the preceding\n> > > +\t * restart point. While that works alright, we would end up scanning\n> > > +\t * too many record.\n> > > +\t */\n> > > +\ti = binsearch(br->restart_count, &restart_needle_less, &args);\n> > > +\n> > > +\t/*\n> > > +\t * Now there are multiple cases:\n> > > +\t *\n> > > +\t * - `i == 0`: The wanted record must be contained before the first\n> > > +\t * restart point. We will thus start searching for the record in\n> > > +\t * that section after accounting for the header offset.\n> > \n> > To clarify my understanding, does a restart_offset not exist at the\n> > beginning of a block? I was originally under the impression that the\n> > first reset point would be at the beginning of the block (or just after\n> > the header). If this was the case, the first restart point being greater\n> > would indicate that the wanted record is not contained within the block.\n> \n> It wouldn't make much sense to include it as a restart point. A restart\n> point is a point where the prefix compression will be reset such that\n> the record at that point can be read without reading preceding records.\n> This is always implicitly true for the first record in a block as it is\n> never prefix-compressed. Consequently, writing a restart point for the\n> first record would be a waste of disk space.\n\nThanks Patrick! Good to know :)\n\nFrom Documentation/technical/reftable.txt:\n\n> As the first ref block shares the first file block with the file\n> header, all restart_offset in the first block are relative to the\n> start of the file (position 0), and include the file header. This \n> forces the first restart_offset to be 28.\n\nI'm assumming this is out-of-date.\n\n-Justin\n"},{"id":"492095","messageId":"owpd2yaxorwbbaurra2zra6zrd2qgshdiubnkgzqouzkqd3xgq@s7a6wchg4xnn","threadId":"61179","inReplyTo":"cover.1712078263.git.ps@pks.im","subject":"Re: [PATCH v3 0/7] reftable: improvements for the `binsearch()` mechanism","fromName":"Justin Tobler","fromEmail":"jltobler@gmail.com","sentAt":"2024-04-02T17:49:02Z","receivedAt":"2024-04-02T17:50:00Z","isPatch":true,"sender":{"key":"jltobler@gmail.com","avatar":"https://avatars.githubusercontent.com/u/53454972?v=4"},"body":"On 24/04/02 07:24PM, Patrick Steinhardt wrote:\n> Hi,\n> \n> this is the third version of my patch series that refactors the\n> `binsearch()` mechanism in the reftable library. There's only a single\n> change compared to v2, namely a rename of some arguments when calling\n> `refname_needle_lesseq()`.\n> \n> Thanks!\n> \n> Patrick\n> \n...\n\nThanks Patrick! This version looks good to me :)\n\n-Justin\n"},{"id":"492133","messageId":"Zgzwyjwo780Ry1XL@tanuki","threadId":"61179","inReplyTo":"ympg3oam4pty53qnxhtnla2xac73gdqsoclwsuzcmjd4dn4xre@j64veypnecrj","subject":"Re: [PATCH v2 4/7] reftable/block: refactor binary search over restart points","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-04-03T06:01:46Z","receivedAt":"2024-04-03T06:01:53Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"On Tue, Apr 02, 2024 at 12:46:30PM -0500, Justin Tobler wrote:\n> On 24/04/02 07:15PM, Patrick Steinhardt wrote:\n> > On Tue, Apr 02, 2024 at 11:42:29AM -0500, Justin Tobler wrote:\n> > > On 24/03/25 11:10AM, Patrick Steinhardt wrote:\n> > > > When seeking a record in our block reader we perform a binary search\n> > > > over the block's restart points so that we don't have to do a linear\n> > > > scan over the whole block. The logic to do so is quite intricate though,\n> > > > which makes it hard to understand.\n> > > > \n> > > > Improve documentation and rename some of the functions and variables so\n> > > > that the code becomes easier to understand overall. This refactoring\n> > > > should not result in any change in behaviour.\n> > > > \n> > > > Signed-off-by: Patrick Steinhardt \n> > > > ---\n> > > ... \n> > > > -\ti = binsearch(br->restart_count, &restart_key_less, &args);\n> > > > +\t/*\n> > > > +\t * Perform a binary search over the block's restart points, which\n> > > > +\t * avoids doing a linear scan over the whole block. Like this, we\n> > > > +\t * identify the section of the block that should contain our key.\n> > > > +\t *\n> > > > +\t * Note that we explicitly search for the first restart point _greater_\n> > > > +\t * than the sought-after record, not _greater or equal_ to it. In case\n> > > > +\t * the sought-after record is located directly at the restart point we\n> > > > +\t * would otherwise start doing the linear search at the preceding\n> > > > +\t * restart point. While that works alright, we would end up scanning\n> > > > +\t * too many record.\n> > > > +\t */\n> > > > +\ti = binsearch(br->restart_count, &restart_needle_less, &args);\n> > > > +\n> > > > +\t/*\n> > > > +\t * Now there are multiple cases:\n> > > > +\t *\n> > > > +\t * - `i == 0`: The wanted record must be contained before the first\n> > > > +\t * restart point. We will thus start searching for the record in\n> > > > +\t * that section after accounting for the header offset.\n> > > \n> > > To clarify my understanding, does a restart_offset not exist at the\n> > > beginning of a block? I was originally under the impression that the\n> > > first reset point would be at the beginning of the block (or just after\n> > > the header). If this was the case, the first restart point being greater\n> > > would indicate that the wanted record is not contained within the block.\n> > \n> > It wouldn't make much sense to include it as a restart point. A restart\n> > point is a point where the prefix compression will be reset such that\n> > the record at that point can be read without reading preceding records.\n> > This is always implicitly true for the first record in a block as it is\n> > never prefix-compressed. Consequently, writing a restart point for the\n> > first record would be a waste of disk space.\n> \n> Thanks Patrick! Good to know :)\n> \n> From Documentation/technical/reftable.txt:\n> \n> > As the first ref block shares the first file block with the file\n> > header, all restart_offset in the first block are relative to the\n> > start of the file (position 0), and include the file header. This \n> > forces the first restart_offset to be 28.\n> \n> I'm assumming this is out-of-date.\n\nThat paragraph actually made me re-check my own assumptions. Turns out\nmy claim is wrong. The function responsible for registering restarts is\n`block_writer_register_restart()`, which gets a parameter `is_restart`\nthat is determined by `reftable_encode_key()`. And that function in turn\nwill set `restart = 1` whenever `prefix_len == 0`. And given that the\nfirst record always has `prefix_len == 0`, it will thus have a restart\npoint, as well.\n\nI'll update the comment like this:\n\ndiff --git a/reftable/block.c b/reftable/block.c\nindex 8bb4e43cec..298e8c56b9 100644\n--- a/reftable/block.c\n+++ b/reftable/block.c\n@@ -417,9 +417,12 @@ int block_reader_seek(struct block_reader *br, struct block_iter *it,\n \t/*\n \t * Now there are multiple cases:\n \t *\n-\t * - `i == 0`: The wanted record must be contained before the first\n-\t * restart point. We will thus start searching for the record in\n-\t * that section after accounting for the header offset.\n+\t * - `i == 0`: The wanted record is smaller than the record found at\n+\t * the first restart point. As the first restart point is the first\n+\t * record in the block, our wanted record cannot be located in this\n+\t * block at all. We still need to position the iterator so that the\n+\t * next call to `block_iter_next()` will yield an end-of-iterator\n+\t * signal.\n \t *\n \t * - `i == restart_count`: The wanted record was not found at any of\n \t * the restart points. As there is no restart point at the end of\n\nThanks for making me challenge my own assumptions!\n\nPatrick\n"},{"id":"492134","messageId":"cover.1712123093.git.ps@pks.im","threadId":"61179","inReplyTo":"cover.1711109214.git.ps@pks.im","subject":"[PATCH v4 0/7] reftable: improvements for the `binsearch()` mechanism","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-04-03T06:03:52Z","receivedAt":"2024-04-03T06:03:56Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"Hi,\n\nthis is the fourth and hopefully final version of my patch series that\nrefactors the `binsearch()` mechanism in the reftable library.\n\nThere's only a single change compared to v3, which is a fix to a comment\nthat was misexplaining one of the cases when searching for the restart\npoints.\n\nThanks!\n\nPatrick\n\nPatrick Steinhardt (7):\n reftable/basics: fix return type of `binsearch()` to be `size_t`\n reftable/basics: improve `binsearch()` test\n reftable/refname: refactor binary search over refnames\n reftable/block: refactor binary search over restart points\n reftable/block: fix error handling when searching restart points\n reftable/record: extract function to decode key lengths\n reftable/block: avoid decoding keys when searching restart points\n\n reftable/basics.c | 7 ++-\n reftable/basics.h | 7 +--\n reftable/basics_test.c | 55 ++++++++++---------\n reftable/block.c | 117 ++++++++++++++++++++++++++++++-----------\n reftable/record.c | 34 ++++++++----\n reftable/record.h | 6 +++\n reftable/refname.c | 53 +++++++++----------\n 7 files changed, 182 insertions(+), 97 deletions(-)\n\nRange-diff against v3:\n1: baa07ef144 = 1: baa07ef144 reftable/basics: fix return type of `binsearch()` to be `size_t`\n2: cbc2a107c1 = 2: cbc2a107c1 reftable/basics: improve `binsearch()` test\n3: f5bf65e0dd = 3: f5bf65e0dd reftable/refname: refactor binary search over refnames\n4: 435cd0be94 ! 4: 6d4a79f3e2 reftable/block: refactor binary search over restart points\n @@ reftable/block.c: int block_reader_seek(struct block_reader *br, struct block_it\n +\t/*\n +\t * Now there are multiple cases:\n +\t *\n -+\t * - `i == 0`: The wanted record must be contained before the first\n -+\t * restart point. We will thus start searching for the record in\n -+\t * that section after accounting for the header offset.\n ++\t * - `i == 0`: The wanted record is smaller than the record found at\n ++\t * the first restart point. As the first restart point is the first\n ++\t * record in the block, our wanted record cannot be located in this\n ++\t * block at all. We still need to position the iterator so that the\n ++\t * next call to `block_iter_next()` will yield an end-of-iterator\n ++\t * signal.\n +\t *\n +\t * - `i == restart_count`: The wanted record was not found at any of\n +\t * the restart points. As there is no restart point at the end of\n5: 8d8abfd290 = 5: 52c238ee9f reftable/block: fix error handling when searching restart points\n6: f87f7ad01a = 6: ca41ad30f4 reftable/record: extract function to decode key lengths\n7: f53bf9e1cc = 7: 632f725dde reftable/block: avoid decoding keys when searching restart points\n-- \n2.44.GIT\n\n"},{"id":"492135","messageId":"baa07ef14425ff45296c2eb677c07b085bacafb3.1712123093.git.ps@pks.im","threadId":"61179","inReplyTo":"cover.1712123093.git.ps@pks.im","subject":"[PATCH v4 1/7] reftable/basics: fix return type of `binsearch()` to be `size_t`","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-04-03T06:03:56Z","receivedAt":"2024-04-03T06:03:59Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"The `binsearch()` function can be used to find the first element for\nwhich a callback functions returns a truish value. But while the array\nsize is of type `size_t`, the function in fact returns an `int` that is\nsupposed to index into that array.\n\nFix the function signature to return a `size_t`. This conversion does\nnot change any semantics given that the function would only ever return\na value in the range `[0, sz]` anyway.\n\nSigned-off-by: Patrick Steinhardt \n---\n reftable/basics.c | 2 +-\n reftable/basics.h | 2 +-\n reftable/basics_test.c | 6 +++---\n reftable/block.c | 3 ++-\n reftable/refname.c | 17 +++++++----------\n 5 files changed, 14 insertions(+), 16 deletions(-)\n\ndiff --git a/reftable/basics.c b/reftable/basics.c\nindex 0785aff941..2c5f34b39e 100644\n--- a/reftable/basics.c\n+++ b/reftable/basics.c\n@@ -27,7 +27,7 @@ void put_be16(uint8_t *out, uint16_t i)\n \tout[1] = (uint8_t)(i & 0xff);\n }\n \n-int binsearch(size_t sz, int (*f)(size_t k, void *args), void *args)\n+size_t binsearch(size_t sz, int (*f)(size_t k, void *args), void *args)\n {\n \tsize_t lo = 0;\n \tsize_t hi = sz;\ndiff --git a/reftable/basics.h b/reftable/basics.h\nindex 91f3533efe..2672520e76 100644\n--- a/reftable/basics.h\n+++ b/reftable/basics.h\n@@ -28,7 +28,7 @@ void put_be16(uint8_t *out, uint16_t i);\n * Contrary to bsearch(3), this returns something useful if the argument is not\n * found.\n */\n-int binsearch(size_t sz, int (*f)(size_t k, void *args), void *args);\n+size_t binsearch(size_t sz, int (*f)(size_t k, void *args), void *args);\n \n /*\n * Frees a NULL terminated array of malloced strings. The array itself is also\ndiff --git a/reftable/basics_test.c b/reftable/basics_test.c\nindex 1fcd229725..dc1c87c5df 100644\n--- a/reftable/basics_test.c\n+++ b/reftable/basics_test.c\n@@ -34,15 +34,15 @@ static void test_binsearch(void)\n \n \tint i = 0;\n \tfor (i = 1; i < 11; i++) {\n-\t\tint res;\n+\t\tsize_t res;\n+\n \t\targs.key = i;\n \t\tres = binsearch(sz, &binsearch_func, &args);\n \n \t\tif (res < sz) {\n \t\t\tEXPECT(args.key < arr[res]);\n-\t\t\tif (res > 0) {\n+\t\t\tif (res > 0)\n \t\t\t\tEXPECT(args.key >= arr[res - 1]);\n-\t\t\t}\n \t\t} else {\n \t\t\tEXPECT(args.key == 10 || args.key == 11);\n \t\t}\ndiff --git a/reftable/block.c b/reftable/block.c\nindex e2a2cee58d..422885bddb 100644\n--- a/reftable/block.c\n+++ b/reftable/block.c\n@@ -382,7 +382,8 @@ int block_reader_seek(struct block_reader *br, struct block_iter *it,\n \t};\n \tstruct block_iter next = BLOCK_ITER_INIT;\n \tstruct reftable_record rec;\n-\tint err = 0, i;\n+\tint err = 0;\n+\tsize_t i;\n \n \tif (args.error) {\n \t\terr = REFTABLE_FORMAT_ERROR;\ndiff --git a/reftable/refname.c b/reftable/refname.c\nindex 7570e4acf9..64eba1b886 100644\n--- a/reftable/refname.c\n+++ b/reftable/refname.c\n@@ -33,10 +33,9 @@ static int modification_has_ref(struct modification *mod, const char *name)\n \t\t\t.names = mod->add,\n \t\t\t.want = name,\n \t\t};\n-\t\tint idx = binsearch(mod->add_len, find_name, &arg);\n-\t\tif (idx < mod->add_len && !strcmp(mod->add[idx], name)) {\n+\t\tsize_t idx = binsearch(mod->add_len, find_name, &arg);\n+\t\tif (idx < mod->add_len && !strcmp(mod->add[idx], name))\n \t\t\treturn 0;\n-\t\t}\n \t}\n \n \tif (mod->del_len > 0) {\n@@ -44,10 +43,9 @@ static int modification_has_ref(struct modification *mod, const char *name)\n \t\t\t.names = mod->del,\n \t\t\t.want = name,\n \t\t};\n-\t\tint idx = binsearch(mod->del_len, find_name, &arg);\n-\t\tif (idx < mod->del_len && !strcmp(mod->del[idx], name)) {\n+\t\tsize_t idx = binsearch(mod->del_len, find_name, &arg);\n+\t\tif (idx < mod->del_len && !strcmp(mod->del[idx], name))\n \t\t\treturn 1;\n-\t\t}\n \t}\n \n \terr = reftable_table_read_ref(&mod->tab, name, &ref);\n@@ -77,7 +75,7 @@ static int modification_has_ref_with_prefix(struct modification *mod,\n \t\t\t.names = mod->add,\n \t\t\t.want = prefix,\n \t\t};\n-\t\tint idx = binsearch(mod->add_len, find_name, &arg);\n+\t\tsize_t idx = binsearch(mod->add_len, find_name, &arg);\n \t\tif (idx < mod->add_len &&\n \t\t !strncmp(prefix, mod->add[idx], strlen(prefix)))\n \t\t\tgoto done;\n@@ -96,11 +94,10 @@ static int modification_has_ref_with_prefix(struct modification *mod,\n \t\t\t\t.names = mod->del,\n \t\t\t\t.want = ref.refname,\n \t\t\t};\n-\t\t\tint idx = binsearch(mod->del_len, find_name, &arg);\n+\t\t\tsize_t idx = binsearch(mod->del_len, find_name, &arg);\n \t\t\tif (idx < mod->del_len &&\n-\t\t\t !strcmp(ref.refname, mod->del[idx])) {\n+\t\t\t !strcmp(ref.refname, mod->del[idx]))\n \t\t\t\tcontinue;\n-\t\t\t}\n \t\t}\n \n \t\tif (strncmp(ref.refname, prefix, strlen(prefix))) {\n-- \n2.44.GIT\n\n"},{"id":"492136","messageId":"cbc2a107c1c067a0c6891bfeb33f2311f2f072b4.1712123093.git.ps@pks.im","threadId":"61179","inReplyTo":"cover.1712123093.git.ps@pks.im","subject":"[PATCH v4 2/7] reftable/basics: improve `binsearch()` test","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-04-03T06:04:00Z","receivedAt":"2024-04-03T06:04:04Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"The `binsearch()` test is somewhat weird in that it doesn't explicitly\nspell out its expectations. Instead it does so in a rather ad-hoc way\nwith some hard-to-understand computations.\n\nRefactor the test to spell out the needle as well as expected index for\nall testcases. This refactoring highlights that the `binsearch_func()`\nis written somewhat weirdly to find the first integer smaller than the\nneedle, not smaller or equal to it. Adjust the function accordingly.\n\nWhile at it, rename the callback function to better convey its meaning.\n\nSigned-off-by: Patrick Steinhardt \n---\n reftable/basics_test.c | 55 ++++++++++++++++++++++++------------------\n 1 file changed, 31 insertions(+), 24 deletions(-)\n\ndiff --git a/reftable/basics_test.c b/reftable/basics_test.c\nindex dc1c87c5df..997c4d9e01 100644\n--- a/reftable/basics_test.c\n+++ b/reftable/basics_test.c\n@@ -12,40 +12,47 @@ license that can be found in the LICENSE file or at\n #include \"test_framework.h\"\n #include \"reftable-tests.h\"\n \n-struct binsearch_args {\n-\tint key;\n-\tint *arr;\n+struct integer_needle_lesseq_args {\n+\tint needle;\n+\tint *haystack;\n };\n \n-static int binsearch_func(size_t i, void *void_args)\n+static int integer_needle_lesseq(size_t i, void *_args)\n {\n-\tstruct binsearch_args *args = void_args;\n-\n-\treturn args->key < args->arr[i];\n+\tstruct integer_needle_lesseq_args *args = _args;\n+\treturn args->needle <= args->haystack[i];\n }\n \n static void test_binsearch(void)\n {\n-\tint arr[] = { 2, 4, 6, 8, 10 };\n-\tsize_t sz = ARRAY_SIZE(arr);\n-\tstruct binsearch_args args = {\n-\t\t.arr = arr,\n+\tint haystack[] = { 2, 4, 6, 8, 10 };\n+\tstruct {\n+\t\tint needle;\n+\t\tsize_t expected_idx;\n+\t} testcases[] = {\n+\t\t{-9000, 0},\n+\t\t{-1, 0},\n+\t\t{0, 0},\n+\t\t{2, 0},\n+\t\t{3, 1},\n+\t\t{4, 1},\n+\t\t{7, 3},\n+\t\t{9, 4},\n+\t\t{10, 4},\n+\t\t{11, 5},\n+\t\t{9000, 5},\n \t};\n+\tsize_t i = 0;\n \n-\tint i = 0;\n-\tfor (i = 1; i < 11; i++) {\n-\t\tsize_t res;\n-\n-\t\targs.key = i;\n-\t\tres = binsearch(sz, &binsearch_func, &args);\n+\tfor (i = 0; i < ARRAY_SIZE(testcases); i++) {\n+\t\tstruct integer_needle_lesseq_args args = {\n+\t\t\t.haystack = haystack,\n+\t\t\t.needle = testcases[i].needle,\n+\t\t};\n+\t\tsize_t idx;\n \n-\t\tif (res < sz) {\n-\t\t\tEXPECT(args.key < arr[res]);\n-\t\t\tif (res > 0)\n-\t\t\t\tEXPECT(args.key >= arr[res - 1]);\n-\t\t} else {\n-\t\t\tEXPECT(args.key == 10 || args.key == 11);\n-\t\t}\n+\t\tidx = binsearch(ARRAY_SIZE(haystack), &integer_needle_lesseq, &args);\n+\t\tEXPECT(idx == testcases[i].expected_idx);\n \t}\n }\n \n-- \n2.44.GIT\n\n"},{"id":"492137","messageId":"f5bf65e0dde70e7753e715b1fd207ef0e556669c.1712123093.git.ps@pks.im","threadId":"61179","inReplyTo":"cover.1712123093.git.ps@pks.im","subject":"[PATCH v4 3/7] reftable/refname: refactor binary search over refnames","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-04-03T06:04:05Z","receivedAt":"2024-04-03T06:04:09Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"It is comparatively hard to understand how exactly the binary search\nover refnames works given that the function and variable names are not\nexactly easy to grasp. Rename them to make this more obvious. This\nshould not result in any change in behaviour.\n\nSigned-off-by: Patrick Steinhardt \n---\n reftable/refname.c | 44 ++++++++++++++++++++++----------------------\n 1 file changed, 22 insertions(+), 22 deletions(-)\n\ndiff --git a/reftable/refname.c b/reftable/refname.c\nindex 64eba1b886..bbfde15754 100644\n--- a/reftable/refname.c\n+++ b/reftable/refname.c\n@@ -12,15 +12,15 @@\n #include \"refname.h\"\n #include \"reftable-iterator.h\"\n \n-struct find_arg {\n-\tchar **names;\n-\tconst char *want;\n+struct refname_needle_lesseq_args {\n+\tchar **haystack;\n+\tconst char *needle;\n };\n \n-static int find_name(size_t k, void *arg)\n+static int refname_needle_lesseq(size_t k, void *_args)\n {\n-\tstruct find_arg *f_arg = arg;\n-\treturn strcmp(f_arg->names[k], f_arg->want) >= 0;\n+\tstruct refname_needle_lesseq_args *args = _args;\n+\treturn strcmp(args->needle, args->haystack[k]) <= 0;\n }\n \n static int modification_has_ref(struct modification *mod, const char *name)\n@@ -29,21 +29,21 @@ static int modification_has_ref(struct modification *mod, const char *name)\n \tint err = 0;\n \n \tif (mod->add_len > 0) {\n-\t\tstruct find_arg arg = {\n-\t\t\t.names = mod->add,\n-\t\t\t.want = name,\n+\t\tstruct refname_needle_lesseq_args args = {\n+\t\t\t.haystack = mod->add,\n+\t\t\t.needle = name,\n \t\t};\n-\t\tsize_t idx = binsearch(mod->add_len, find_name, &arg);\n+\t\tsize_t idx = binsearch(mod->add_len, refname_needle_lesseq, &args);\n \t\tif (idx < mod->add_len && !strcmp(mod->add[idx], name))\n \t\t\treturn 0;\n \t}\n \n \tif (mod->del_len > 0) {\n-\t\tstruct find_arg arg = {\n-\t\t\t.names = mod->del,\n-\t\t\t.want = name,\n+\t\tstruct refname_needle_lesseq_args args = {\n+\t\t\t.haystack = mod->del,\n+\t\t\t.needle = name,\n \t\t};\n-\t\tsize_t idx = binsearch(mod->del_len, find_name, &arg);\n+\t\tsize_t idx = binsearch(mod->del_len, refname_needle_lesseq, &args);\n \t\tif (idx < mod->del_len && !strcmp(mod->del[idx], name))\n \t\t\treturn 1;\n \t}\n@@ -71,11 +71,11 @@ static int modification_has_ref_with_prefix(struct modification *mod,\n \tint err = 0;\n \n \tif (mod->add_len > 0) {\n-\t\tstruct find_arg arg = {\n-\t\t\t.names = mod->add,\n-\t\t\t.want = prefix,\n+\t\tstruct refname_needle_lesseq_args args = {\n+\t\t\t.haystack = mod->add,\n+\t\t\t.needle = prefix,\n \t\t};\n-\t\tsize_t idx = binsearch(mod->add_len, find_name, &arg);\n+\t\tsize_t idx = binsearch(mod->add_len, refname_needle_lesseq, &args);\n \t\tif (idx < mod->add_len &&\n \t\t !strncmp(prefix, mod->add[idx], strlen(prefix)))\n \t\t\tgoto done;\n@@ -90,11 +90,11 @@ static int modification_has_ref_with_prefix(struct modification *mod,\n \t\t\tgoto done;\n \n \t\tif (mod->del_len > 0) {\n-\t\t\tstruct find_arg arg = {\n-\t\t\t\t.names = mod->del,\n-\t\t\t\t.want = ref.refname,\n+\t\t\tstruct refname_needle_lesseq_args args = {\n+\t\t\t\t.haystack = mod->del,\n+\t\t\t\t.needle = ref.refname,\n \t\t\t};\n-\t\t\tsize_t idx = binsearch(mod->del_len, find_name, &arg);\n+\t\t\tsize_t idx = binsearch(mod->del_len, refname_needle_lesseq, &args);\n \t\t\tif (idx < mod->del_len &&\n \t\t\t !strcmp(ref.refname, mod->del[idx]))\n \t\t\t\tcontinue;\n-- \n2.44.GIT\n\n"},{"id":"492138","messageId":"6d4a79f3e26f24e8eeec9abcad1d7fdaa3d6e252.1712123093.git.ps@pks.im","threadId":"61179","inReplyTo":"cover.1712123093.git.ps@pks.im","subject":"[PATCH v4 4/7] reftable/block: refactor binary search over restart points","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-04-03T06:04:09Z","receivedAt":"2024-04-03T06:04:17Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"When seeking a record in our block reader we perform a binary search\nover the block's restart points so that we don't have to do a linear\nscan over the whole block. The logic to do so is quite intricate though,\nwhich makes it hard to understand.\n\nImprove documentation and rename some of the functions and variables so\nthat the code becomes easier to understand overall. This refactoring\nshould not result in any change in behaviour.\n\nSigned-off-by: Patrick Steinhardt \n---\n reftable/block.c | 100 ++++++++++++++++++++++++++++++++++-------------\n 1 file changed, 73 insertions(+), 27 deletions(-)\n\ndiff --git a/reftable/block.c b/reftable/block.c\nindex 422885bddb..57e3dbf658 100644\n--- a/reftable/block.c\n+++ b/reftable/block.c\n@@ -273,34 +273,36 @@ void block_reader_start(struct block_reader *br, struct block_iter *it)\n \tit->next_off = br->header_off + 4;\n }\n \n-struct restart_find_args {\n+struct restart_needle_less_args {\n \tint error;\n-\tstruct strbuf key;\n-\tstruct block_reader *r;\n+\tstruct strbuf needle;\n+\tstruct block_reader *reader;\n };\n \n-static int restart_key_less(size_t idx, void *args)\n+static int restart_needle_less(size_t idx, void *_args)\n {\n-\tstruct restart_find_args *a = args;\n-\tuint32_t off = block_reader_restart_offset(a->r, idx);\n+\tstruct restart_needle_less_args *args = _args;\n+\tuint32_t off = block_reader_restart_offset(args->reader, idx);\n \tstruct string_view in = {\n-\t\t.buf = a->r->block.data + off,\n-\t\t.len = a->r->block_len - off,\n+\t\t.buf = args->reader->block.data + off,\n+\t\t.len = args->reader->block_len - off,\n \t};\n-\n-\t/* the restart key is verbatim in the block, so this could avoid the\n-\t alloc for decoding the key */\n-\tstruct strbuf rkey = STRBUF_INIT;\n+\tstruct strbuf kth_restart_key = STRBUF_INIT;\n \tuint8_t unused_extra;\n-\tint n = reftable_decode_key(&rkey, &unused_extra, in);\n-\tint result;\n+\tint result, n;\n+\n+\t/*\n+\t * TODO: The restart key is verbatim in the block, so we can in theory\n+\t * avoid decoding the key and thus save some allocations.\n+\t */\n+\tn = reftable_decode_key(&kth_restart_key, &unused_extra, in);\n \tif (n < 0) {\n-\t\ta->error = 1;\n+\t\targs->error = 1;\n \t\treturn -1;\n \t}\n \n-\tresult = strbuf_cmp(&a->key, &rkey);\n-\tstrbuf_release(&rkey);\n+\tresult = strbuf_cmp(&args->needle, &kth_restart_key);\n+\tstrbuf_release(&kth_restart_key);\n \treturn result < 0;\n }\n \n@@ -376,9 +378,9 @@ void block_iter_close(struct block_iter *it)\n int block_reader_seek(struct block_reader *br, struct block_iter *it,\n \t\t struct strbuf *want)\n {\n-\tstruct restart_find_args args = {\n-\t\t.key = *want,\n-\t\t.r = br,\n+\tstruct restart_needle_less_args args = {\n+\t\t.needle = *want,\n+\t\t.reader = br,\n \t};\n \tstruct block_iter next = BLOCK_ITER_INIT;\n \tstruct reftable_record rec;\n@@ -390,7 +392,38 @@ int block_reader_seek(struct block_reader *br, struct block_iter *it,\n \t\tgoto done;\n \t}\n \n-\ti = binsearch(br->restart_count, &restart_key_less, &args);\n+\t/*\n+\t * Perform a binary search over the block's restart points, which\n+\t * avoids doing a linear scan over the whole block. Like this, we\n+\t * identify the section of the block that should contain our key.\n+\t *\n+\t * Note that we explicitly search for the first restart point _greater_\n+\t * than the sought-after record, not _greater or equal_ to it. In case\n+\t * the sought-after record is located directly at the restart point we\n+\t * would otherwise start doing the linear search at the preceding\n+\t * restart point. While that works alright, we would end up scanning\n+\t * too many record.\n+\t */\n+\ti = binsearch(br->restart_count, &restart_needle_less, &args);\n+\n+\t/*\n+\t * Now there are multiple cases:\n+\t *\n+\t * - `i == 0`: The wanted record is smaller than the record found at\n+\t * the first restart point. As the first restart point is the first\n+\t * record in the block, our wanted record cannot be located in this\n+\t * block at all. We still need to position the iterator so that the\n+\t * next call to `block_iter_next()` will yield an end-of-iterator\n+\t * signal.\n+\t *\n+\t * - `i == restart_count`: The wanted record was not found at any of\n+\t * the restart points. As there is no restart point at the end of\n+\t * the section the record may thus be contained in the last block.\n+\t *\n+\t * - `i > 0`: The wanted record must be contained in the section\n+\t * before the found restart point. We thus do a linear search\n+\t * starting from the preceding restart point.\n+\t */\n \tif (i > 0)\n \t\tit->next_off = block_reader_restart_offset(br, i - 1);\n \telse\n@@ -399,21 +432,34 @@ int block_reader_seek(struct block_reader *br, struct block_iter *it,\n \n \treftable_record_init(&rec, block_reader_type(br));\n \n-\t/* We're looking for the last entry less/equal than the wanted key, so\n-\t we have to go one entry too far and then back up.\n-\t*/\n+\t/*\n+\t * We're looking for the last entry less than the wanted key so that\n+\t * the next call to `block_reader_next()` would yield the wanted\n+\t * record. We thus don't want to position our reader at the sought\n+\t * after record, but one before. To do so, we have to go one entry too\n+\t * far and then back up.\n+\t */\n \twhile (1) {\n \t\tblock_iter_copy_from(&next, it);\n \t\terr = block_iter_next(&next, &rec);\n \t\tif (err < 0)\n \t\t\tgoto done;\n-\n-\t\treftable_record_key(&rec, &it->last_key);\n-\t\tif (err > 0 || strbuf_cmp(&it->last_key, want) >= 0) {\n+\t\tif (err > 0) {\n \t\t\terr = 0;\n \t\t\tgoto done;\n \t\t}\n \n+\t\t/*\n+\t\t * Check whether the current key is greater or equal to the\n+\t\t * sought-after key. In case it is greater we know that the\n+\t\t * record does not exist in the block and can thus abort early.\n+\t\t * In case it is equal to the sought-after key we have found\n+\t\t * the desired record.\n+\t\t */\n+\t\treftable_record_key(&rec, &it->last_key);\n+\t\tif (strbuf_cmp(&it->last_key, want) >= 0)\n+\t\t\tgoto done;\n+\n \t\tblock_iter_copy_from(it, &next);\n \t}\n \n-- \n2.44.GIT\n\n"},{"id":"492139","messageId":"52c238ee9fdd3257333931f938be38712d3532d5.1712123093.git.ps@pks.im","threadId":"61179","inReplyTo":"cover.1712123093.git.ps@pks.im","subject":"[PATCH v4 5/7] reftable/block: fix error handling when searching restart points","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-04-03T06:04:18Z","receivedAt":"2024-04-03T06:04:21Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"When doing the binary search over restart points in a block we need to\ndecode the record keys. This decoding step can result in an error when\nthe block is corrupted, which we indicate to the caller of the binary\nsearch by setting `args.error = 1`. But the only caller that exists\nmishandles this because it in fact performs the error check before\ncalling `binsearch()`.\n\nFix this bug by checking for errors at the right point in time.\nFurthermore, refactor `binsearch()` so that it aborts the search in case\nthe callback function returns a negative value so that we don't\nneedlessly continue to search the block.\n\nSigned-off-by: Patrick Steinhardt \n---\n reftable/basics.c | 5 ++++-\n reftable/basics.h | 5 +++--\n reftable/block.c | 9 ++++-----\n 3 files changed, 11 insertions(+), 8 deletions(-)\n\ndiff --git a/reftable/basics.c b/reftable/basics.c\nindex 2c5f34b39e..fea711db7e 100644\n--- a/reftable/basics.c\n+++ b/reftable/basics.c\n@@ -39,8 +39,11 @@ size_t binsearch(size_t sz, int (*f)(size_t k, void *args), void *args)\n \t */\n \twhile (hi - lo > 1) {\n \t\tsize_t mid = lo + (hi - lo) / 2;\n+\t\tint ret = f(mid, args);\n+\t\tif (ret < 0)\n+\t\t\treturn sz;\n \n-\t\tif (f(mid, args))\n+\t\tif (ret > 0)\n \t\t\thi = mid;\n \t\telse\n \t\t\tlo = mid;\ndiff --git a/reftable/basics.h b/reftable/basics.h\nindex 2672520e76..523ecd5307 100644\n--- a/reftable/basics.h\n+++ b/reftable/basics.h\n@@ -22,8 +22,9 @@ uint32_t get_be24(uint8_t *in);\n void put_be16(uint8_t *out, uint16_t i);\n \n /*\n- * find smallest index i in [0, sz) at which f(i) is true, assuming\n- * that f is ascending. Return sz if f(i) is false for all indices.\n+ * find smallest index i in [0, sz) at which `f(i) > 0`, assuming that f is\n+ * ascending. Return sz if `f(i) == 0` for all indices. The search is aborted\n+ * and `sz` is returned in case `f(i) < 0`.\n *\n * Contrary to bsearch(3), this returns something useful if the argument is not\n * found.\ndiff --git a/reftable/block.c b/reftable/block.c\nindex 57e3dbf658..ca217636ae 100644\n--- a/reftable/block.c\n+++ b/reftable/block.c\n@@ -387,11 +387,6 @@ int block_reader_seek(struct block_reader *br, struct block_iter *it,\n \tint err = 0;\n \tsize_t i;\n \n-\tif (args.error) {\n-\t\terr = REFTABLE_FORMAT_ERROR;\n-\t\tgoto done;\n-\t}\n-\n \t/*\n \t * Perform a binary search over the block's restart points, which\n \t * avoids doing a linear scan over the whole block. Like this, we\n@@ -405,6 +400,10 @@ int block_reader_seek(struct block_reader *br, struct block_iter *it,\n \t * too many record.\n \t */\n \ti = binsearch(br->restart_count, &restart_needle_less, &args);\n+\tif (args.error) {\n+\t\terr = REFTABLE_FORMAT_ERROR;\n+\t\tgoto done;\n+\t}\n \n \t/*\n \t * Now there are multiple cases:\n-- \n2.44.GIT\n\n"},{"id":"492140","messageId":"ca41ad30f46985c227a70cd11cc065363687c32c.1712123093.git.ps@pks.im","threadId":"61179","inReplyTo":"cover.1712123093.git.ps@pks.im","subject":"[PATCH v4 6/7] reftable/record: extract function to decode key lengths","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-04-03T06:04:22Z","receivedAt":"2024-04-03T06:04:25Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"We're about to refactor the binary search over restart points so that it\ndoes not need to fully decode the record keys anymore. To do so we will\nneed to decode the record key lengths, which is non-trivial logic.\n\nExtract the logic to decode these lengths from `refatble_decode_key()`\nso that we can reuse it.\n\nSigned-off-by: Patrick Steinhardt \n---\n reftable/record.c | 34 +++++++++++++++++++++++++---------\n reftable/record.h | 6 ++++++\n 2 files changed, 31 insertions(+), 9 deletions(-)\n\ndiff --git a/reftable/record.c b/reftable/record.c\nindex 23b497adab..5506f3e913 100644\n--- a/reftable/record.c\n+++ b/reftable/record.c\n@@ -159,26 +159,42 @@ int reftable_encode_key(int *restart, struct string_view dest,\n \treturn start.len - dest.len;\n }\n \n-int reftable_decode_key(struct strbuf *last_key, uint8_t *extra,\n-\t\t\tstruct string_view in)\n+int reftable_decode_keylen(struct string_view in,\n+\t\t\t uint64_t *prefix_len,\n+\t\t\t uint64_t *suffix_len,\n+\t\t\t uint8_t *extra)\n {\n-\tint start_len = in.len;\n-\tuint64_t prefix_len = 0;\n-\tuint64_t suffix_len = 0;\n+\tsize_t start_len = in.len;\n \tint n;\n \n-\tn = get_var_int(&prefix_len, &in);\n+\tn = get_var_int(prefix_len, &in);\n \tif (n < 0)\n \t\treturn -1;\n \tstring_view_consume(&in, n);\n \n-\tn = get_var_int(&suffix_len, &in);\n+\tn = get_var_int(suffix_len, &in);\n \tif (n <= 0)\n \t\treturn -1;\n \tstring_view_consume(&in, n);\n \n-\t*extra = (uint8_t)(suffix_len & 0x7);\n-\tsuffix_len >>= 3;\n+\t*extra = (uint8_t)(*suffix_len & 0x7);\n+\t*suffix_len >>= 3;\n+\n+\treturn start_len - in.len;\n+}\n+\n+int reftable_decode_key(struct strbuf *last_key, uint8_t *extra,\n+\t\t\tstruct string_view in)\n+{\n+\tint start_len = in.len;\n+\tuint64_t prefix_len = 0;\n+\tuint64_t suffix_len = 0;\n+\tint n;\n+\n+\tn = reftable_decode_keylen(in, &prefix_len, &suffix_len, extra);\n+\tif (n < 0)\n+\t\treturn -1;\n+\tstring_view_consume(&in, n);\n \n \tif (in.len < suffix_len ||\n \t prefix_len > last_key->len)\ndiff --git a/reftable/record.h b/reftable/record.h\nindex 826ee1c55c..d778133e6e 100644\n--- a/reftable/record.h\n+++ b/reftable/record.h\n@@ -86,6 +86,12 @@ int reftable_encode_key(int *is_restart, struct string_view dest,\n \t\t\tstruct strbuf prev_key, struct strbuf key,\n \t\t\tuint8_t extra);\n \n+/* Decode a record's key lengths. */\n+int reftable_decode_keylen(struct string_view in,\n+\t\t\t uint64_t *prefix_len,\n+\t\t\t uint64_t *suffix_len,\n+\t\t\t uint8_t *extra);\n+\n /*\n * Decode into `last_key` and `extra` from `in`. `last_key` is expected to\n * contain the decoded key of the preceding record, if any.\n-- \n2.44.GIT\n\n"},{"id":"492141","messageId":"632f725dde7b7f2eda83d285af90c7d989f294dc.1712123093.git.ps@pks.im","threadId":"61179","inReplyTo":"cover.1712123093.git.ps@pks.im","subject":"[PATCH v4 7/7] reftable/block: avoid decoding keys when searching restart points","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-04-03T06:04:29Z","receivedAt":"2024-04-03T06:04:33Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"When searching over restart points in a block we decode the key of each\nof the records, which results in a memory allocation. This is quite\npointless though given that records it restart points will never use\nprefix compression and thus store their keys verbatim in the block.\n\nRefactor the code so that we can avoid decoding the keys, which saves us\nsome allocations.\n\nSigned-off-by: Patrick Steinhardt \n---\n reftable/block.c | 29 +++++++++++++++++++----------\n 1 file changed, 19 insertions(+), 10 deletions(-)\n\ndiff --git a/reftable/block.c b/reftable/block.c\nindex ca217636ae..298e8c56b9 100644\n--- a/reftable/block.c\n+++ b/reftable/block.c\n@@ -287,23 +287,32 @@ static int restart_needle_less(size_t idx, void *_args)\n \t\t.buf = args->reader->block.data + off,\n \t\t.len = args->reader->block_len - off,\n \t};\n-\tstruct strbuf kth_restart_key = STRBUF_INIT;\n-\tuint8_t unused_extra;\n-\tint result, n;\n+\tuint64_t prefix_len, suffix_len;\n+\tuint8_t extra;\n+\tint n;\n \n \t/*\n-\t * TODO: The restart key is verbatim in the block, so we can in theory\n-\t * avoid decoding the key and thus save some allocations.\n+\t * Records at restart points are stored without prefix compression, so\n+\t * there is no need to fully decode the record key here. This removes\n+\t * the need for allocating memory.\n \t */\n-\tn = reftable_decode_key(&kth_restart_key, &unused_extra, in);\n-\tif (n < 0) {\n+\tn = reftable_decode_keylen(in, &prefix_len, &suffix_len, &extra);\n+\tif (n < 0 || prefix_len) {\n \t\targs->error = 1;\n \t\treturn -1;\n \t}\n \n-\tresult = strbuf_cmp(&args->needle, &kth_restart_key);\n-\tstrbuf_release(&kth_restart_key);\n-\treturn result < 0;\n+\tstring_view_consume(&in, n);\n+\tif (suffix_len > in.len) {\n+\t\targs->error = 1;\n+\t\treturn -1;\n+\t}\n+\n+\tn = memcmp(args->needle.buf, in.buf,\n+\t\t args->needle.len < suffix_len ? args->needle.len : suffix_len);\n+\tif (n)\n+\t\treturn n < 0;\n+\treturn args->needle.len < suffix_len;\n }\n \n void block_iter_copy_from(struct block_iter *dest, struct block_iter *src)\n-- \n2.44.GIT\n\n"}]}