{"thread":{"id":"61069","subject":"[PATCH] reftable/block: fix binary search over restart counter","startedAt":"2024-03-07T15:26:45Z","lastAt":"2024-03-11T17:33:27Z","messageCount":9,"participants":["Patrick Steinhardt","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"490192","messageId":"a4312698cceab5f2438c9dd34465da21d719e256.1709825186.git.ps@pks.im","threadId":"61069","inReplyTo":null,"subject":"[PATCH] reftable/block: fix binary search over restart counter","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-03-07T15:26:38Z","receivedAt":"2024-03-07T15:26:45Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"Records store their keys prefix-compressed. As many records will share a\ncommon prefix (e.g. \"refs/heads/\"), this can end up saving quite a bit\nof disk space. The downside of this is that it is not possible to just\nseek into the middle of a block and consume the corresponding record\nbecause it may depend on prefixes read from preceding records.\n\nTo help with this usecase, the reftable format writes every n'th record\nwithout using prefix compression, which is called a \"restart\". The list\nof restarts is stored at the end of each block so that a reader can\nfigure out entry points at which to read a full record without having to\nread all preceding records.\n\nThis allows us to do a binary search over the records in a block when\nsearching for a particular key by iterating through the restarts until\nwe have found the section in which our record must be located. From\nthereon we perform a linear search to locate the desired record.\n\nThis mechanism is broken though. In `block_reader_seek()` we call\n`binsearch()` over the count of restarts in the current block. The\nfunction we pass to compare records with each other computes the key at\nthe current index and then compares it to our search key by calling\n`strbuf_cmp()`, returning its result directly. But `binsearch()` expects\nus to return a truish value that indicates whether the current index is\nsmaller than the searched-for key. And unless our key exactly matches\nthe value at the restart counter we always end up returning a truish\nvalue.\n\nThe consequence is that `binsearch()` essentially always returns 0,\nindicacting to us that we must start searching right at the beginning of\nthe block. This works by chance because we now always do a linear scan\nfrom the start of the block, and thus we would still end up finding the\ndesired record. But needless to say, this makes the optimization quite\nuseless.\n\nFix this bug by returning whether the current key is smaller than the\nsearched key. As the current behaviour was correct it is not possible to\nwrite a test. Furthermore it is also not really possible to demonstrate\nin a benchmark that this fix speeds up seeking records.\n\nThis may cause the reader to question whether this binary search makes\nsense in the first place if it doesn't even help with performance. But\nit would end up helping if we were to read a reftable with a much larger\nblock size. Blocks can be up to 16MB in size, in which case it will\nbecome much more important to avoid the linear scan. We are not yet\nready to read or write such larger blocks though, so we have to live\nwithout a benchmark demonstrating this.\n\nSigned-off-by: Patrick Steinhardt <ps@pks.im>\n---\n reftable/block.c | 2 +-\n 1 file changed, 1 insertion(+), 1 deletion(-)\n\ndiff --git a/reftable/block.c b/reftable/block.c\nindex 72eb73b380..3d7a7022e7 100644\n--- a/reftable/block.c\n+++ b/reftable/block.c\n@@ -302,7 +302,7 @@ static int restart_key_less(size_t idx, void *args)\n \n \tresult = strbuf_cmp(&a->key, &rkey);\n \tstrbuf_release(&rkey);\n-\treturn result;\n+\treturn result <= 0;\n }\n \n void block_iter_copy_from(struct block_iter *dest, struct block_iter *src)\n-- \n2.44.0\n\n"},{"id":"490195","messageId":"ZenqLgfSomVlYDwh@tanuki","threadId":"61069","inReplyTo":"a4312698cceab5f2438c9dd34465da21d719e256.1709825186.git.ps@pks.im","subject":"Re: [PATCH] reftable/block: fix binary search over restart counter","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-03-07T16:24:14Z","receivedAt":"2024-03-07T16:24:20Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"On Thu, Mar 07, 2024 at 04:26:38PM +0100, Patrick Steinhardt wrote:\n> Records store their keys prefix-compressed. As many records will share a\n> common prefix (e.g. \"refs/heads/\"), this can end up saving quite a bit\n> of disk space. The downside of this is that it is not possible to just\n> seek into the middle of a block and consume the corresponding record\n> because it may depend on prefixes read from preceding records.\n> \n> To help with this usecase, the reftable format writes every n'th record\n> without using prefix compression, which is called a \"restart\". The list\n> of restarts is stored at the end of each block so that a reader can\n> figure out entry points at which to read a full record without having to\n> read all preceding records.\n> \n> This allows us to do a binary search over the records in a block when\n> searching for a particular key by iterating through the restarts until\n> we have found the section in which our record must be located. From\n> thereon we perform a linear search to locate the desired record.\n> \n> This mechanism is broken though. In `block_reader_seek()` we call\n> `binsearch()` over the count of restarts in the current block. The\n> function we pass to compare records with each other computes the key at\n> the current index and then compares it to our search key by calling\n> `strbuf_cmp()`, returning its result directly. But `binsearch()` expects\n> us to return a truish value that indicates whether the current index is\n> smaller than the searched-for key. And unless our key exactly matches\n> the value at the restart counter we always end up returning a truish\n> value.\n> \n> The consequence is that `binsearch()` essentially always returns 0,\n> indicacting to us that we must start searching right at the beginning of\n> the block. This works by chance because we now always do a linear scan\n> from the start of the block, and thus we would still end up finding the\n> desired record. But needless to say, this makes the optimization quite\n> useless.\n> \n> Fix this bug by returning whether the current key is smaller than the\n> searched key. As the current behaviour was correct it is not possible to\n> write a test. Furthermore it is also not really possible to demonstrate\n> in a benchmark that this fix speeds up seeking records.\n> \n> This may cause the reader to question whether this binary search makes\n> sense in the first place if it doesn't even help with performance. But\n> it would end up helping if we were to read a reftable with a much larger\n> block size. Blocks can be up to 16MB in size, in which case it will\n> become much more important to avoid the linear scan. We are not yet\n> ready to read or write such larger blocks though, so we have to live\n> without a benchmark demonstrating this.\n> \n> Signed-off-by: Patrick Steinhardt <ps@pks.im>\n> ---\n>  reftable/block.c | 2 +-\n>  1 file changed, 1 insertion(+), 1 deletion(-)\n> \n> diff --git a/reftable/block.c b/reftable/block.c\n> index 72eb73b380..3d7a7022e7 100644\n> --- a/reftable/block.c\n> +++ b/reftable/block.c\n> @@ -302,7 +302,7 @@ static int restart_key_less(size_t idx, void *args)\n>  \n>  \tresult = strbuf_cmp(&a->key, &rkey);\n>  \tstrbuf_release(&rkey);\n> -\treturn result;\n> +\treturn result <= 0;\n>  }\n>  \n>  void block_iter_copy_from(struct block_iter *dest, struct block_iter *src)\n> -- \n> 2.44.0\n> \n\nHum. I noticed that this causes a memory leak in our CI. I'll need to\ninvestigate.\n\nPatrick\n"},{"id":"490213","messageId":"cover.1709843663.git.ps@pks.im","threadId":"61069","inReplyTo":"a4312698cceab5f2438c9dd34465da21d719e256.1709825186.git.ps@pks.im","subject":"[PATCH v2 0/2] reftable/block: fix binary search over restart counter","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-03-07T20:35:52Z","receivedAt":"2024-03-07T20:35:59Z","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 fixes the binary\nsearch over block restart counters. I've add another commit on top that\nfixes a memory leak that was uncovered by the fix.\n\nPatrick\n\nPatrick Steinhardt (2):\n  reftable/record: fix memory leak when decoding object records\n  reftable/block: fix binary search over restart counter\n\n reftable/block.c  | 2 +-\n reftable/record.c | 2 ++\n 2 files changed, 3 insertions(+), 1 deletion(-)\n\n\nbase-commit: 43072b4ca132437f21975ac6acc6b72dc22fd398\n-- \n2.43.1\n\n"},{"id":"490214","messageId":"a963054f9a063ca0c4fdcf613fd0ab2e9c681ac9.1709843663.git.ps@pks.im","threadId":"61069","inReplyTo":"cover.1709843663.git.ps@pks.im","subject":"[PATCH v2 1/2] reftable/record: fix memory leak when decoding object records","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-03-07T20:35:58Z","receivedAt":"2024-03-07T20:36:02Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"When decoding records it is customary to reuse a `struct\nreftable_ref_record` across calls. Thus, it may happen that the record\nalready holds some allocated memory. When decoding ref and log records\nwe handle this by releasing or reallocating held memory. But we fail to\ndo this for object records, which causes us to leak memory.\n\nFix this memory leak by releasing object records before we decode into\nthem. We may eventually want to reuse memory instead to avoid needless\nreallocations. But for now, let's just plug the leak and be done.\n\nSigned-off-by: Patrick Steinhardt <ps@pks.im>\n---\n reftable/record.c | 2 ++\n 1 file changed, 2 insertions(+)\n\ndiff --git a/reftable/record.c b/reftable/record.c\nindex d6bb42e887..9c31feb35c 100644\n--- a/reftable/record.c\n+++ b/reftable/record.c\n@@ -569,6 +569,8 @@ static int reftable_obj_record_decode(void *rec, struct strbuf key,\n \tuint64_t last;\n \tint j;\n \n+\treftable_obj_record_release(r);\n+\n \tREFTABLE_ALLOC_ARRAY(r->hash_prefix, key.len);\n \tmemcpy(r->hash_prefix, key.buf, key.len);\n \tr->hash_prefix_len = key.len;\n-- \n2.43.1\n\n"},{"id":"490215","messageId":"370b608f9007abe9c0562d76894e2475d19867a1.1709843663.git.ps@pks.im","threadId":"61069","inReplyTo":"cover.1709843663.git.ps@pks.im","subject":"[PATCH v2 2/2] reftable/block: fix binary search over restart counter","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-03-07T20:36:02Z","receivedAt":"2024-03-07T20:36:06Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"Records store their keys prefix-compressed. As many records will share a\ncommon prefix (e.g. \"refs/heads/\"), this can end up saving quite a bit\nof disk space. The downside of this is that it is not possible to just\nseek into the middle of a block and consume the corresponding record\nbecause it may depend on prefixes read from preceding records.\n\nTo help with this usecase, the reftable format writes every n'th record\nwithout using prefix compression, which is called a \"restart\". The list\nof restarts is stored at the end of each block so that a reader can\nfigure out entry points at which to read a full record without having to\nread all preceding records.\n\nThis allows us to do a binary search over the records in a block when\nsearching for a particular key by iterating through the restarts until\nwe have found the section in which our record must be located. From\nthereon we perform a linear search to locate the desired record.\n\nThis mechanism is broken though. In `block_reader_seek()` we call\n`binsearch()` over the count of restarts in the current block. The\nfunction we pass to compare records with each other computes the key at\nthe current index and then compares it to our search key by calling\n`strbuf_cmp()`, returning its result directly. But `binsearch()` expects\nus to return a truish value that indicates whether the current index is\nsmaller than the searched-for key. And unless our key exactly matches\nthe value at the restart counter we always end up returning a truish\nvalue.\n\nThe consequence is that `binsearch()` essentially always returns 0,\nindicacting to us that we must start searching right at the beginning of\nthe block. This works by chance because we now always do a linear scan\nfrom the start of the block, and thus we would still end up finding the\ndesired record. But needless to say, this makes the optimization quite\nuseless.\n\nFix this bug by returning whether the current key is smaller than the\nsearched key. As the current behaviour was correct it is not possible to\nwrite a test. Furthermore it is also not really possible to demonstrate\nin a benchmark that this fix speeds up seeking records.\n\nThis may cause the reader to question whether this binary search makes\nsense in the first place if it doesn't even help with performance. But\nit would end up helping if we were to read a reftable with a much larger\nblock size. Blocks can be up to 16MB in size, in which case it will\nbecome much more important to avoid the linear scan. We are not yet\nready to read or write such larger blocks though, so we have to live\nwithout a benchmark demonstrating this.\n\nSigned-off-by: Patrick Steinhardt <ps@pks.im>\n---\n reftable/block.c | 2 +-\n 1 file changed, 1 insertion(+), 1 deletion(-)\n\ndiff --git a/reftable/block.c b/reftable/block.c\nindex 72eb73b380..1663030386 100644\n--- a/reftable/block.c\n+++ b/reftable/block.c\n@@ -302,7 +302,7 @@ static int restart_key_less(size_t idx, void *args)\n \n \tresult = strbuf_cmp(&a->key, &rkey);\n \tstrbuf_release(&rkey);\n-\treturn result;\n+\treturn result < 0;\n }\n \n void block_iter_copy_from(struct block_iter *dest, struct block_iter *src)\n-- \n2.43.1\n\n"},{"id":"490229","messageId":"xmqq7cidk4e4.fsf@gitster.g","threadId":"61069","inReplyTo":"370b608f9007abe9c0562d76894e2475d19867a1.1709843663.git.ps@pks.im","subject":"Re: [PATCH v2 2/2] reftable/block: fix binary search over restart counter","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2024-03-07T23:29:07Z","receivedAt":"2024-03-07T23:29:12Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Patrick Steinhardt <ps@pks.im> writes:\n\n> The consequence is that `binsearch()` essentially always returns 0,\n> indicacting to us that we must start searching right at the beginning of\n> the block. This works by chance because we now always do a linear scan\n> from the start of the block, and thus we would still end up finding the\n> desired record. But needless to say, this makes the optimization quite\n> useless.\n>\n> Fix this bug by returning whether the current key is smaller than the\n> searched key. As the current behaviour was correct it is not possible to\n> write a test. Furthermore it is also not really possible to demonstrate\n> in a benchmark that this fix speeds up seeking records.\n\nThis is an amusing bug.  \n\nI wonder if we inherited it from the original implementation---this\nwas imported from jgit, right?\n\nThanks for a detailed write-up.  \n\nThe \"it is a fix, but the breakage is well hidden and cannot be\nobserved only by checking for correctness\" aspect of the bug\ndeserves the unusually large \"number of paragraphs explaining the\nchange divided by number of changed lines\" ratio ;-).\n\nApplied.\n\n> Signed-off-by: Patrick Steinhardt <ps@pks.im>\n> ---\n>  reftable/block.c | 2 +-\n>  1 file changed, 1 insertion(+), 1 deletion(-)\n>\n> diff --git a/reftable/block.c b/reftable/block.c\n> index 72eb73b380..1663030386 100644\n> --- a/reftable/block.c\n> +++ b/reftable/block.c\n> @@ -302,7 +302,7 @@ static int restart_key_less(size_t idx, void *args)\n>  \n>  \tresult = strbuf_cmp(&a->key, &rkey);\n>  \tstrbuf_release(&rkey);\n> -\treturn result;\n> +\treturn result < 0;\n>  }\n>  \n>  void block_iter_copy_from(struct block_iter *dest, struct block_iter *src)\n"},{"id":"490230","messageId":"xmqq34t1k12p.fsf@gitster.g","threadId":"61069","inReplyTo":"xmqq7cidk4e4.fsf@gitster.g","subject":"Re: [PATCH v2 2/2] reftable/block: fix binary search over restart counter","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2024-03-08T00:40:46Z","receivedAt":"2024-03-08T00:40:48Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano <gitster@pobox.com> writes:\n\n> Patrick Steinhardt <ps@pks.im> writes:\n>\n>> The consequence is that `binsearch()` essentially always returns 0,\n>> indicacting to us that we must start searching right at the beginning of\n>> the block. This works by chance because we now always do a linear scan\n>> from the start of the block, and thus we would still end up finding the\n>> desired record. But needless to say, this makes the optimization quite\n>> useless.\n\n>> Fix this bug by returning whether the current key is smaller than the\n>> searched key. As the current behaviour was correct it is not possible to\n>> write a test. Furthermore it is also not really possible to demonstrate\n>> in a benchmark that this fix speeds up seeking records.\n>\n> This is an amusing bug.  \n\nHaving said all that.\n\nI have to wonder if it is the custom implementation of binsearch()\nthe reftable/basic.c file has, not this particular comparison\ncallback.  It makes an unusual expectation on the comparison\nfunction, unlike bsearch(3) whose compar(a,b) is expected to return\nan answer with the same sign as \"a - b\".\n\nI just checked the binary search loops we have in the core part of\nthe system, like the one in hash-lookup.c (which takes advantage of\nthe random and uniform nature of hashed values to converge faster\nthan log2) and ones in builtin/pack-objects.c (both of which are\nabsolute bog-standard).  Luckily, we do not use such an unusual\nconvention (well, we avoid overhead of compar callbacks to begin\nwith, so it is a bit of apples-to-oranges comparison).\n\n"},{"id":"490351","messageId":"Ze6UDkipgNsDVCwf@tanuki","threadId":"61069","inReplyTo":"xmqq34t1k12p.fsf@gitster.g","subject":"Re: [PATCH v2 2/2] reftable/block: fix binary search over restart counter","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-03-11T05:18:06Z","receivedAt":"2024-03-11T05:18:13Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"On Thu, Mar 07, 2024 at 04:40:46PM -0800, Junio C Hamano wrote:\n> Junio C Hamano <gitster@pobox.com> writes:\n> \n> > Patrick Steinhardt <ps@pks.im> writes:\n> >\n> >> The consequence is that `binsearch()` essentially always returns 0,\n> >> indicacting to us that we must start searching right at the beginning of\n> >> the block. This works by chance because we now always do a linear scan\n> >> from the start of the block, and thus we would still end up finding the\n> >> desired record. But needless to say, this makes the optimization quite\n> >> useless.\n> \n> >> Fix this bug by returning whether the current key is smaller than the\n> >> searched key. As the current behaviour was correct it is not possible to\n> >> write a test. Furthermore it is also not really possible to demonstrate\n> >> in a benchmark that this fix speeds up seeking records.\n> >\n> > This is an amusing bug.  \n> \n> Having said all that.\n> \n> I have to wonder if it is the custom implementation of binsearch()\n> the reftable/basic.c file has, not this particular comparison\n> callback.  It makes an unusual expectation on the comparison\n> function, unlike bsearch(3) whose compar(a,b) is expected to return\n> an answer with the same sign as \"a - b\".\n> \n> I just checked the binary search loops we have in the core part of\n> the system, like the one in hash-lookup.c (which takes advantage of\n> the random and uniform nature of hashed values to converge faster\n> than log2) and ones in builtin/pack-objects.c (both of which are\n> absolute bog-standard).  Luckily, we do not use such an unusual\n> convention (well, we avoid overhead of compar callbacks to begin\n> with, so it is a bit of apples-to-oranges comparison).\n\nVery true, this behaviour cought me by surprise, as well, and I do think\nit's quite easy to get wrong. Now I would've understood if `binsearch()`\nwere able to handle and forward errors to the caller by passing -1. And\nI almost thought that was the case because `restart_key_less()` can\nindeed fail, and it would return a negative value if so. But that error\nreturn code is then not taken as an indicator of failure, but instead\nwill cause us to treat the current value as smaller than the comparison\nkey.\n\nBut we do know to bubble the error up via the pasesd-in args by setting\n`args->error = -1`. Funny thing though: I just now noticed that we check\nfor `args.error` _before_ we call `binsearch()`. Oops.\n\nI will send a follow-up patch that addresses these issues.\n\nPatrick\n"},{"id":"490370","messageId":"xmqqmsr4smfx.fsf@gitster.g","threadId":"61069","inReplyTo":"Ze6UDkipgNsDVCwf@tanuki","subject":"Re: [PATCH v2 2/2] reftable/block: fix binary search over restart counter","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2024-03-11T17:33:22Z","receivedAt":"2024-03-11T17:33:27Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Patrick Steinhardt <ps@pks.im> writes:\n\n> But we do know to bubble the error up via the pasesd-in args by setting\n> `args->error = -1`. Funny thing though: I just now noticed that we check\n> for `args.error` _before_ we call `binsearch()`. Oops.\n>\n> I will send a follow-up patch that addresses these issues.\n\nThanks, that is doubly amusing ;-)\n"}]}