{"thread":{"id":"61207","subject":"[PATCH 0/9] reftable: optimize table and block iterators","startedAt":"2024-03-27T06:36:56Z","lastAt":"2024-04-10T11:35:18Z","messageCount":31,"participants":["Patrick Steinhardt","Justin Tobler","Karthik Nayak"],"isPatch":true,"patchVersion":1,"patchTotal":9},"messages":[{"id":"491633","messageId":"cover.1711519925.git.ps@pks.im","threadId":"61207","inReplyTo":null,"subject":"[PATCH 0/9] reftable: optimize table and block iterators","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-03-27T06:36:53Z","receivedAt":"2024-03-27T06:36:56Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"Hi,\n\n * The code to iterate over reftable blocks has seen some optimization\n   to reduce memory allocation and deallocation.\n\nPreceding patch series have optimized memory allocation patterns when\niterating through ref or log records. This has led to a constant number\nof allocations when decoding and yielding those records to our callers.\nOne thing that is still missing though is an optimization for the table\nand block iterators which are responsible for iterating through the\nseparate blocks in the table. So while the number of allocations does\nnot scale with the number of refs (directly) anymore, it still scales\nwith the number of blocks.\n\nThis is getting tackled by this patch series now which refactors the\ntable and block iterators such that the former can reuse the latter\nwithout reallocations. With this change iterating through records is now\nusing a truly constant number of allocations.\n\nPatrick\n\nPatrick Steinhardt (9):\n  reftable/block: rename `block_reader_start()`\n  reftable/block: merge `block_iter_seek()` and `block_reader_seek()`\n  reftable/block: better grouping of functions\n  reftable/block: introduce `block_reader_release()`\n  reftable/block: move ownership of block reader into `struct\n    table_iter`\n  reftable/reader: iterate to next block in place\n  reftable/block: reuse uncompressed blocks\n  reftable/block: open-code call to `uncompress2()`\n  reftable/block: reuse `zstream` state on inflation\n\n reftable/block.c      | 152 ++++++++++++++++++++++--------------\n reftable/block.h      |  49 +++++++-----\n reftable/block_test.c |   6 +-\n reftable/iter.c       |   2 +-\n reftable/reader.c     | 176 ++++++++++++++++++++++--------------------\n 5 files changed, 222 insertions(+), 163 deletions(-)\n\n-- \n2.44.GIT\n\n"},{"id":"491634","messageId":"24b0dda29e2f48265b35a78a10c9902f2bf4fa77.1711519925.git.ps@pks.im","threadId":"61207","inReplyTo":"cover.1711519925.git.ps@pks.im","subject":"[PATCH 1/9] reftable/block: rename `block_reader_start()`","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-03-27T06:36:57Z","receivedAt":"2024-03-27T06:37:00Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"The function `block_reader_start()` does not really apply to the block\nreader, but to the block iterator. It's name is thus somewhat confusing.\nRename it to `block_iter_seek_start()` to clarify.\n\nWe will rename `block_reader_seek()` in similar spirit in the next\ncommit.\n\nSigned-off-by: Patrick Steinhardt <ps@pks.im>\n---\n reftable/block.c      | 2 +-\n reftable/block.h      | 2 +-\n reftable/block_test.c | 2 +-\n reftable/iter.c       | 2 +-\n reftable/reader.c     | 4 ++--\n 5 files changed, 6 insertions(+), 6 deletions(-)\n\ndiff --git a/reftable/block.c b/reftable/block.c\nindex e2a2cee58d..d5f32867bb 100644\n--- a/reftable/block.c\n+++ b/reftable/block.c\n@@ -266,7 +266,7 @@ static uint32_t block_reader_restart_offset(struct block_reader *br, int i)\n \treturn get_be24(br->restart_bytes + 3 * i);\n }\n \n-void block_reader_start(struct block_reader *br, struct block_iter *it)\n+void block_iter_seek_start(struct block_iter *it, struct block_reader *br)\n {\n \tit->br = br;\n \tstrbuf_reset(&it->last_key);\ndiff --git a/reftable/block.h b/reftable/block.h\nindex 47acc62c0a..44a9a8de7d 100644\n--- a/reftable/block.h\n+++ b/reftable/block.h\n@@ -98,7 +98,7 @@ int block_reader_init(struct block_reader *br, struct reftable_block *bl,\n \t\t      int hash_size);\n \n /* Position `it` at start of the block */\n-void block_reader_start(struct block_reader *br, struct block_iter *it);\n+void block_iter_seek_start(struct block_iter *it, struct block_reader *br);\n \n /* Position `it` to the `want` key in the block */\n int block_reader_seek(struct block_reader *br, struct block_iter *it,\ndiff --git a/reftable/block_test.c b/reftable/block_test.c\nindex e162c6e33f..a719be7c50 100644\n--- a/reftable/block_test.c\n+++ b/reftable/block_test.c\n@@ -69,7 +69,7 @@ static void test_block_read_write(void)\n \n \tblock_reader_init(&br, &block, header_off, block_size, GIT_SHA1_RAWSZ);\n \n-\tblock_reader_start(&br, &it);\n+\tblock_iter_seek_start(&it, &br);\n \n \twhile (1) {\n \t\tint r = block_iter_next(&it, &rec);\ndiff --git a/reftable/iter.c b/reftable/iter.c\nindex 7aa30c4a51..aa9ac199b1 100644\n--- a/reftable/iter.c\n+++ b/reftable/iter.c\n@@ -115,7 +115,7 @@ static int indexed_table_ref_iter_next_block(struct indexed_table_ref_iter *it)\n \t\t/* indexed block does not exist. */\n \t\treturn REFTABLE_FORMAT_ERROR;\n \t}\n-\tblock_reader_start(&it->block_reader, &it->cur);\n+\tblock_iter_seek_start(&it->cur, &it->block_reader);\n \treturn 0;\n }\n \ndiff --git a/reftable/reader.c b/reftable/reader.c\nindex b113daab77..d7d47e8640 100644\n--- a/reftable/reader.c\n+++ b/reftable/reader.c\n@@ -345,7 +345,7 @@ static int table_iter_next_block(struct table_iter *dest,\n \t\t*brp = br;\n \n \t\tdest->is_finished = 0;\n-\t\tblock_reader_start(brp, &dest->bi);\n+\t\tblock_iter_seek_start(&dest->bi, brp);\n \t}\n \treturn 0;\n }\n@@ -429,7 +429,7 @@ static int reader_table_iter_at(struct reftable_reader *r,\n \tti->r = r;\n \tti->typ = block_reader_type(brp);\n \tti->block_off = off;\n-\tblock_reader_start(brp, &ti->bi);\n+\tblock_iter_seek_start(&ti->bi, brp);\n \treturn 0;\n }\n \n-- \n2.44.GIT\n\n"},{"id":"491635","messageId":"a2b7f0f559d381d649b6bf27403f099a68221f00.1711519925.git.ps@pks.im","threadId":"61207","inReplyTo":"cover.1711519925.git.ps@pks.im","subject":"[PATCH 2/9] reftable/block: merge `block_iter_seek()` and `block_reader_seek()`","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-03-27T06:37:01Z","receivedAt":"2024-03-27T06:37:04Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"The function `block_iter_seek()` is merely a simple wrapper around\n`block_reader_seek()`. Merge those two functions into a new function\n`block_iter_seek_key()` that more clearly says what it is actually\ndoing.\n\nSigned-off-by: Patrick Steinhardt <ps@pks.im>\n---\n reftable/block.c      | 9 ++-------\n reftable/block.h      | 7 ++-----\n reftable/block_test.c | 4 ++--\n reftable/reader.c     | 4 ++--\n 4 files changed, 8 insertions(+), 16 deletions(-)\n\ndiff --git a/reftable/block.c b/reftable/block.c\nindex d5f32867bb..3f182c5d1f 100644\n--- a/reftable/block.c\n+++ b/reftable/block.c\n@@ -362,19 +362,14 @@ int block_reader_first_key(struct block_reader *br, struct strbuf *key)\n \treturn 0;\n }\n \n-int block_iter_seek(struct block_iter *it, struct strbuf *want)\n-{\n-\treturn block_reader_seek(it->br, it, want);\n-}\n-\n void block_iter_close(struct block_iter *it)\n {\n \tstrbuf_release(&it->last_key);\n \tstrbuf_release(&it->scratch);\n }\n \n-int block_reader_seek(struct block_reader *br, struct block_iter *it,\n-\t\t      struct strbuf *want)\n+int block_iter_seek_key(struct block_iter *it, struct block_reader *br,\n+\t\t\tstruct strbuf *want)\n {\n \tstruct restart_find_args args = {\n \t\t.key = *want,\ndiff --git a/reftable/block.h b/reftable/block.h\nindex 44a9a8de7d..1734bee917 100644\n--- a/reftable/block.h\n+++ b/reftable/block.h\n@@ -101,8 +101,8 @@ int block_reader_init(struct block_reader *br, struct reftable_block *bl,\n void block_iter_seek_start(struct block_iter *it, struct block_reader *br);\n \n /* Position `it` to the `want` key in the block */\n-int block_reader_seek(struct block_reader *br, struct block_iter *it,\n-\t\t      struct strbuf *want);\n+int block_iter_seek_key(struct block_iter *it, struct block_reader *br,\n+\t\t\tstruct strbuf *want);\n \n /* Returns the block type (eg. 'r' for refs) */\n uint8_t block_reader_type(struct block_reader *r);\n@@ -115,9 +115,6 @@ void block_iter_copy_from(struct block_iter *dest, struct block_iter *src);\n /* return < 0 for error, 0 for OK, > 0 for EOF. */\n int block_iter_next(struct block_iter *it, struct reftable_record *rec);\n \n-/* Seek to `want` with in the block pointed to by `it` */\n-int block_iter_seek(struct block_iter *it, struct strbuf *want);\n-\n /* deallocate memory for `it`. The block reader and its block is left intact. */\n void block_iter_close(struct block_iter *it);\n \ndiff --git a/reftable/block_test.c b/reftable/block_test.c\nindex a719be7c50..26a9cfbc83 100644\n--- a/reftable/block_test.c\n+++ b/reftable/block_test.c\n@@ -89,7 +89,7 @@ static void test_block_read_write(void)\n \t\tstrbuf_reset(&want);\n \t\tstrbuf_addstr(&want, names[i]);\n \n-\t\tn = block_reader_seek(&br, &it, &want);\n+\t\tn = block_iter_seek_key(&it, &br, &want);\n \t\tEXPECT(n == 0);\n \n \t\tn = block_iter_next(&it, &rec);\n@@ -98,7 +98,7 @@ static void test_block_read_write(void)\n \t\tEXPECT_STREQ(names[i], rec.u.ref.refname);\n \n \t\twant.len--;\n-\t\tn = block_reader_seek(&br, &it, &want);\n+\t\tn = block_iter_seek_key(&it, &br, &want);\n \t\tEXPECT(n == 0);\n \n \t\tn = block_iter_next(&it, &rec);\ndiff --git a/reftable/reader.c b/reftable/reader.c\nindex d7d47e8640..f70efa2b7c 100644\n--- a/reftable/reader.c\n+++ b/reftable/reader.c\n@@ -483,7 +483,7 @@ static int reader_seek_linear(struct table_iter *ti,\n \t\ttable_iter_copy_from(ti, &next);\n \t}\n \n-\terr = block_iter_seek(&ti->bi, &want_key);\n+\terr = block_iter_seek_key(&ti->bi, ti->bi.br, &want_key);\n \tif (err < 0)\n \t\tgoto done;\n \terr = 0;\n@@ -558,7 +558,7 @@ static int reader_seek_indexed(struct reftable_reader *r,\n \t\tif (err != 0)\n \t\t\tgoto done;\n \n-\t\terr = block_iter_seek(&next.bi, &want_index.u.idx.last_key);\n+\t\terr = block_iter_seek_key(&next.bi, next.bi.br, &want_index.u.idx.last_key);\n \t\tif (err < 0)\n \t\t\tgoto done;\n \n-- \n2.44.GIT\n\n"},{"id":"491636","messageId":"88a705b3e26a12805f13f6e315aa2b815045cbb7.1711519925.git.ps@pks.im","threadId":"61207","inReplyTo":"cover.1711519925.git.ps@pks.im","subject":"[PATCH 3/9] reftable/block: better grouping of functions","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-03-27T06:37:05Z","receivedAt":"2024-03-27T06:37:08Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"Function definitions and declaration of `struct block_reader` and\n`struct block_iter` are somewhat mixed up, making it hard to see which\nfunctions belong together. Rearrange them.\n\nSigned-off-by: Patrick Steinhardt <ps@pks.im>\n---\n reftable/block.c | 50 ++++++++++++++++++++++++------------------------\n reftable/block.h | 22 ++++++++++-----------\n 2 files changed, 36 insertions(+), 36 deletions(-)\n\ndiff --git a/reftable/block.c b/reftable/block.c\nindex 3f182c5d1f..6b78dd3424 100644\n--- a/reftable/block.c\n+++ b/reftable/block.c\n@@ -175,11 +175,6 @@ int block_writer_finish(struct block_writer *w)\n \treturn w->next;\n }\n \n-uint8_t block_reader_type(struct block_reader *r)\n-{\n-\treturn r->block.data[r->header_off];\n-}\n-\n int block_reader_init(struct block_reader *br, struct reftable_block *block,\n \t\t      uint32_t header_off, uint32_t table_block_size,\n \t\t      int hash_size)\n@@ -261,6 +256,31 @@ int block_reader_init(struct block_reader *br, struct reftable_block *block,\n \treturn err;\n }\n \n+uint8_t block_reader_type(struct block_reader *r)\n+{\n+\treturn r->block.data[r->header_off];\n+}\n+\n+int block_reader_first_key(struct block_reader *br, struct strbuf *key)\n+{\n+\tint off = br->header_off + 4, n;\n+\tstruct string_view in = {\n+\t\t.buf = br->block.data + off,\n+\t\t.len = br->block_len - off,\n+\t};\n+\tuint8_t extra = 0;\n+\n+\tstrbuf_reset(key);\n+\n+\tn = reftable_decode_key(key, &extra, in);\n+\tif (n < 0)\n+\t\treturn n;\n+\tif (!key->len)\n+\t\treturn REFTABLE_FORMAT_ERROR;\n+\n+\treturn 0;\n+}\n+\n static uint32_t block_reader_restart_offset(struct block_reader *br, int i)\n {\n \treturn get_be24(br->restart_bytes + 3 * i);\n@@ -342,26 +362,6 @@ int block_iter_next(struct block_iter *it, struct reftable_record *rec)\n \treturn 0;\n }\n \n-int block_reader_first_key(struct block_reader *br, struct strbuf *key)\n-{\n-\tint off = br->header_off + 4, n;\n-\tstruct string_view in = {\n-\t\t.buf = br->block.data + off,\n-\t\t.len = br->block_len - off,\n-\t};\n-\tuint8_t extra = 0;\n-\n-\tstrbuf_reset(key);\n-\n-\tn = reftable_decode_key(key, &extra, in);\n-\tif (n < 0)\n-\t\treturn n;\n-\tif (!key->len)\n-\t\treturn REFTABLE_FORMAT_ERROR;\n-\n-\treturn 0;\n-}\n-\n void block_iter_close(struct block_iter *it)\n {\n \tstrbuf_release(&it->last_key);\ndiff --git a/reftable/block.h b/reftable/block.h\nindex 1734bee917..d73ed73549 100644\n--- a/reftable/block.h\n+++ b/reftable/block.h\n@@ -76,6 +76,17 @@ struct block_reader {\n \tuint32_t full_block_size;\n };\n \n+/* initializes a block reader. */\n+int block_reader_init(struct block_reader *br, struct reftable_block *bl,\n+\t\t      uint32_t header_off, uint32_t table_block_size,\n+\t\t      int hash_size);\n+\n+/* Returns the block type (eg. 'r' for refs) */\n+uint8_t block_reader_type(struct block_reader *r);\n+\n+/* Decodes the first key in the block */\n+int block_reader_first_key(struct block_reader *br, struct strbuf *key);\n+\n /* Iterate over entries in a block */\n struct block_iter {\n \t/* offset within the block of the next entry to read. */\n@@ -92,11 +103,6 @@ struct block_iter {\n \t.scratch = STRBUF_INIT, \\\n }\n \n-/* initializes a block reader. */\n-int block_reader_init(struct block_reader *br, struct reftable_block *bl,\n-\t\t      uint32_t header_off, uint32_t table_block_size,\n-\t\t      int hash_size);\n-\n /* Position `it` at start of the block */\n void block_iter_seek_start(struct block_iter *it, struct block_reader *br);\n \n@@ -104,12 +110,6 @@ void block_iter_seek_start(struct block_iter *it, struct block_reader *br);\n int block_iter_seek_key(struct block_iter *it, struct block_reader *br,\n \t\t\tstruct strbuf *want);\n \n-/* Returns the block type (eg. 'r' for refs) */\n-uint8_t block_reader_type(struct block_reader *r);\n-\n-/* Decodes the first key in the block */\n-int block_reader_first_key(struct block_reader *br, struct strbuf *key);\n-\n void block_iter_copy_from(struct block_iter *dest, struct block_iter *src);\n \n /* return < 0 for error, 0 for OK, > 0 for EOF. */\n-- \n2.44.GIT\n\n"},{"id":"491637","messageId":"9a1253649a4dc993da7caced2f15839d988905d9.1711519925.git.ps@pks.im","threadId":"61207","inReplyTo":"cover.1711519925.git.ps@pks.im","subject":"[PATCH 4/9] reftable/block: introduce `block_reader_release()`","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-03-27T06:37:09Z","receivedAt":"2024-03-27T06:37:13Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"Introduce a new function `block_reader_release()` that releases\nresources acquired by the block reader. This function will be extended\nin a subsequent commit.\n\nSigned-off-by: Patrick Steinhardt <ps@pks.im>\n---\n reftable/block.c  | 5 +++++\n reftable/block.h  | 2 ++\n reftable/reader.c | 2 +-\n 3 files changed, 8 insertions(+), 1 deletion(-)\n\ndiff --git a/reftable/block.c b/reftable/block.c\nindex 6b78dd3424..013849f028 100644\n--- a/reftable/block.c\n+++ b/reftable/block.c\n@@ -256,6 +256,11 @@ int block_reader_init(struct block_reader *br, struct reftable_block *block,\n \treturn err;\n }\n \n+void block_reader_release(struct block_reader *br)\n+{\n+\treftable_block_done(&br->block);\n+}\n+\n uint8_t block_reader_type(struct block_reader *r)\n {\n \treturn r->block.data[r->header_off];\ndiff --git a/reftable/block.h b/reftable/block.h\nindex d73ed73549..601a1e0e89 100644\n--- a/reftable/block.h\n+++ b/reftable/block.h\n@@ -81,6 +81,8 @@ int block_reader_init(struct block_reader *br, struct reftable_block *bl,\n \t\t      uint32_t header_off, uint32_t table_block_size,\n \t\t      int hash_size);\n \n+void block_reader_release(struct block_reader *br);\n+\n /* Returns the block type (eg. 'r' for refs) */\n uint8_t block_reader_type(struct block_reader *r);\n \ndiff --git a/reftable/reader.c b/reftable/reader.c\nindex f70efa2b7c..f925570bf3 100644\n--- a/reftable/reader.c\n+++ b/reftable/reader.c\n@@ -253,7 +253,7 @@ static void table_iter_block_done(struct table_iter *ti)\n \tif (!ti->bi.br) {\n \t\treturn;\n \t}\n-\treftable_block_done(&ti->bi.br->block);\n+\tblock_reader_release(ti->bi.br);\n \tFREE_AND_NULL(ti->bi.br);\n \n \tti->bi.last_key.len = 0;\n-- \n2.44.GIT\n\n"},{"id":"491638","messageId":"f10882a0840a77f2569cf891374b70d1e84ceb4b.1711519925.git.ps@pks.im","threadId":"61207","inReplyTo":"cover.1711519925.git.ps@pks.im","subject":"[PATCH 5/9] reftable/block: move ownership of block reader into `struct table_iter`","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-03-27T06:37:13Z","receivedAt":"2024-03-27T06:37:17Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"The table iterator allows the caller to iterate through all records in a\nreftable table. To do so it iterates through all blocks of the desired\ntype one by one, where for each block it creates a new block iterator\nand yields all its entries.\n\nOne of the things that is somewhat confusing in this context is who owns\nthe block reader that is being used to read the blocks and pass them to\nthe block iterator. Intuitively, as the table iterator is responsible\nfor iterating through the blocks, one would assume that this iterator is\nalso responsible for managing the lifecycle of the reader. And while it\nsomewhat is, the block reader is ultimately stored inside of the block\niterator.\n\nRefactor the code such that the block reader is instead fully managed by\nthe table iterator. Instead of passing the reader to the block iterator,\nwe now only end up passing the block data to it. Despite clearing up the\nlifecycle of the reader, it will also allow for better reuse of the\nreader in subsequent patches.\n\nThe following benchmark prints a single matching ref out of 1 million\nrefs. Before:\n\n  HEAP SUMMARY:\n      in use at exit: 13,603 bytes in 125 blocks\n    total heap usage: 6,607 allocs, 6,482 frees, 509,635 bytes allocated\n\nAfter:\n\n  HEAP SUMMARY:\n      in use at exit: 13,603 bytes in 125 blocks\n    total heap usage: 7,235 allocs, 7,110 frees, 301,481 bytes allocated\n\nNote that while there are more allocation and free calls now, the\noverall number of bytes allocated is significantly lower. The number of\nallocations will be reduced significantly by the next patch though.\n\nSigned-off-by: Patrick Steinhardt <ps@pks.im>\n---\n reftable/block.c  |  43 ++++++++++------\n reftable/block.h  |  19 ++++---\n reftable/reader.c | 123 ++++++++++++++++++++++------------------------\n 3 files changed, 102 insertions(+), 83 deletions(-)\n\ndiff --git a/reftable/block.c b/reftable/block.c\nindex 013849f028..8f5dfe10bf 100644\n--- a/reftable/block.c\n+++ b/reftable/block.c\n@@ -261,12 +261,12 @@ void block_reader_release(struct block_reader *br)\n \treftable_block_done(&br->block);\n }\n \n-uint8_t block_reader_type(struct block_reader *r)\n+uint8_t block_reader_type(const struct block_reader *r)\n {\n \treturn r->block.data[r->header_off];\n }\n \n-int block_reader_first_key(struct block_reader *br, struct strbuf *key)\n+int block_reader_first_key(const struct block_reader *br, struct strbuf *key)\n {\n \tint off = br->header_off + 4, n;\n \tstruct string_view in = {\n@@ -286,14 +286,16 @@ int block_reader_first_key(struct block_reader *br, struct strbuf *key)\n \treturn 0;\n }\n \n-static uint32_t block_reader_restart_offset(struct block_reader *br, int i)\n+static uint32_t block_reader_restart_offset(const struct block_reader *br, int i)\n {\n \treturn get_be24(br->restart_bytes + 3 * i);\n }\n \n-void block_iter_seek_start(struct block_iter *it, struct block_reader *br)\n+void block_iter_seek_start(struct block_iter *it, const struct block_reader *br)\n {\n-\tit->br = br;\n+\tit->block = br->block.data;\n+\tit->block_len = br->block_len;\n+\tit->hash_size = br->hash_size;\n \tstrbuf_reset(&it->last_key);\n \tit->next_off = br->header_off + 4;\n }\n@@ -301,7 +303,7 @@ void block_iter_seek_start(struct block_iter *it, struct block_reader *br)\n struct restart_find_args {\n \tint error;\n \tstruct strbuf key;\n-\tstruct block_reader *r;\n+\tconst struct block_reader *r;\n };\n \n static int restart_key_less(size_t idx, void *args)\n@@ -329,9 +331,11 @@ static int restart_key_less(size_t idx, void *args)\n \treturn result < 0;\n }\n \n-void block_iter_copy_from(struct block_iter *dest, struct block_iter *src)\n+void block_iter_copy_from(struct block_iter *dest, const struct block_iter *src)\n {\n-\tdest->br = src->br;\n+\tdest->block = src->block;\n+\tdest->block_len = src->block_len;\n+\tdest->hash_size = src->hash_size;\n \tdest->next_off = src->next_off;\n \tstrbuf_reset(&dest->last_key);\n \tstrbuf_addbuf(&dest->last_key, &src->last_key);\n@@ -340,14 +344,14 @@ void block_iter_copy_from(struct block_iter *dest, struct block_iter *src)\n int block_iter_next(struct block_iter *it, struct reftable_record *rec)\n {\n \tstruct string_view in = {\n-\t\t.buf = it->br->block.data + it->next_off,\n-\t\t.len = it->br->block_len - it->next_off,\n+\t\t.buf = (unsigned char *) it->block + it->next_off,\n+\t\t.len = it->block_len - it->next_off,\n \t};\n \tstruct string_view start = in;\n \tuint8_t extra = 0;\n \tint n = 0;\n \n-\tif (it->next_off >= it->br->block_len)\n+\tif (it->next_off >= it->block_len)\n \t\treturn 1;\n \n \tn = reftable_decode_key(&it->last_key, &extra, in);\n@@ -357,7 +361,7 @@ int block_iter_next(struct block_iter *it, struct reftable_record *rec)\n \t\treturn REFTABLE_FORMAT_ERROR;\n \n \tstring_view_consume(&in, n);\n-\tn = reftable_record_decode(rec, it->last_key, extra, in, it->br->hash_size,\n+\tn = reftable_record_decode(rec, it->last_key, extra, in, it->hash_size,\n \t\t\t\t   &it->scratch);\n \tif (n < 0)\n \t\treturn -1;\n@@ -367,13 +371,22 @@ int block_iter_next(struct block_iter *it, struct reftable_record *rec)\n \treturn 0;\n }\n \n+void block_iter_reset(struct block_iter *it)\n+{\n+\tstrbuf_reset(&it->last_key);\n+\tit->next_off = 0;\n+\tit->block = NULL;\n+\tit->block_len = 0;\n+\tit->hash_size = 0;\n+}\n+\n void block_iter_close(struct block_iter *it)\n {\n \tstrbuf_release(&it->last_key);\n \tstrbuf_release(&it->scratch);\n }\n \n-int block_iter_seek_key(struct block_iter *it, struct block_reader *br,\n+int block_iter_seek_key(struct block_iter *it, const struct block_reader *br,\n \t\t\tstruct strbuf *want)\n {\n \tstruct restart_find_args args = {\n@@ -394,7 +407,9 @@ int block_iter_seek_key(struct block_iter *it, struct block_reader *br,\n \t\tit->next_off = block_reader_restart_offset(br, i - 1);\n \telse\n \t\tit->next_off = br->header_off + 4;\n-\tit->br = br;\n+\tit->block = br->block.data;\n+\tit->block_len = br->block_len;\n+\tit->hash_size = br->hash_size;\n \n \treftable_record_init(&rec, block_reader_type(br));\n \ndiff --git a/reftable/block.h b/reftable/block.h\nindex 601a1e0e89..b41efa5042 100644\n--- a/reftable/block.h\n+++ b/reftable/block.h\n@@ -84,16 +84,18 @@ int block_reader_init(struct block_reader *br, struct reftable_block *bl,\n void block_reader_release(struct block_reader *br);\n \n /* Returns the block type (eg. 'r' for refs) */\n-uint8_t block_reader_type(struct block_reader *r);\n+uint8_t block_reader_type(const struct block_reader *r);\n \n /* Decodes the first key in the block */\n-int block_reader_first_key(struct block_reader *br, struct strbuf *key);\n+int block_reader_first_key(const struct block_reader *br, struct strbuf *key);\n \n /* Iterate over entries in a block */\n struct block_iter {\n \t/* offset within the block of the next entry to read. */\n \tuint32_t next_off;\n-\tstruct block_reader *br;\n+\tconst unsigned char *block;\n+\tsize_t block_len;\n+\tint hash_size;\n \n \t/* key for last entry we read. */\n \tstruct strbuf last_key;\n@@ -106,17 +108,22 @@ struct block_iter {\n }\n \n /* Position `it` at start of the block */\n-void block_iter_seek_start(struct block_iter *it, struct block_reader *br);\n+void block_iter_seek_start(struct block_iter *it, const struct block_reader *br);\n \n /* Position `it` to the `want` key in the block */\n-int block_iter_seek_key(struct block_iter *it, struct block_reader *br,\n+int block_iter_seek_key(struct block_iter *it, const struct block_reader *br,\n \t\t\tstruct strbuf *want);\n \n-void block_iter_copy_from(struct block_iter *dest, struct block_iter *src);\n+void block_iter_copy_from(struct block_iter *dest, const struct block_iter *src);\n \n /* return < 0 for error, 0 for OK, > 0 for EOF. */\n int block_iter_next(struct block_iter *it, struct reftable_record *rec);\n \n+/*\n+ * Reset the block iterator to pristine state without releasing its memory.\n+ */\n+void block_iter_reset(struct block_iter *it);\n+\n /* deallocate memory for `it`. The block reader and its block is left intact. */\n void block_iter_close(struct block_iter *it);\n \ndiff --git a/reftable/reader.c b/reftable/reader.c\nindex f925570bf3..b77b639751 100644\n--- a/reftable/reader.c\n+++ b/reftable/reader.c\n@@ -220,6 +220,7 @@ struct table_iter {\n \tstruct reftable_reader *r;\n \tuint8_t typ;\n \tuint64_t block_off;\n+\tstruct block_reader br;\n \tstruct block_iter bi;\n \tint is_finished;\n };\n@@ -227,16 +228,6 @@ struct table_iter {\n \t.bi = BLOCK_ITER_INIT \\\n }\n \n-static void table_iter_copy_from(struct table_iter *dest,\n-\t\t\t\t struct table_iter *src)\n-{\n-\tdest->r = src->r;\n-\tdest->typ = src->typ;\n-\tdest->block_off = src->block_off;\n-\tdest->is_finished = src->is_finished;\n-\tblock_iter_copy_from(&dest->bi, &src->bi);\n-}\n-\n static int table_iter_next_in_block(struct table_iter *ti,\n \t\t\t\t    struct reftable_record *rec)\n {\n@@ -250,14 +241,8 @@ static int table_iter_next_in_block(struct table_iter *ti,\n \n static void table_iter_block_done(struct table_iter *ti)\n {\n-\tif (!ti->bi.br) {\n-\t\treturn;\n-\t}\n-\tblock_reader_release(ti->bi.br);\n-\tFREE_AND_NULL(ti->bi.br);\n-\n-\tti->bi.last_key.len = 0;\n-\tti->bi.next_off = 0;\n+\tblock_reader_release(&ti->br);\n+\tblock_iter_reset(&ti->bi);\n }\n \n static int32_t extract_block_size(uint8_t *data, uint8_t *typ, uint64_t off,\n@@ -321,32 +306,33 @@ int reader_init_block_reader(struct reftable_reader *r, struct block_reader *br,\n \treturn err;\n }\n \n+static void table_iter_close(struct table_iter *ti)\n+{\n+\ttable_iter_block_done(ti);\n+\tblock_iter_close(&ti->bi);\n+}\n+\n static int table_iter_next_block(struct table_iter *dest,\n \t\t\t\t struct table_iter *src)\n {\n-\tuint64_t next_block_off = src->block_off + src->bi.br->full_block_size;\n-\tstruct block_reader br = { 0 };\n-\tint err = 0;\n+\tuint64_t next_block_off = src->block_off + src->br.full_block_size;\n+\tint err;\n \n \tdest->r = src->r;\n \tdest->typ = src->typ;\n \tdest->block_off = next_block_off;\n \n-\terr = reader_init_block_reader(src->r, &br, next_block_off, src->typ);\n-\tif (err > 0) {\n+\terr = reader_init_block_reader(src->r, &dest->br, next_block_off, src->typ);\n+\tif (err > 0)\n \t\tdest->is_finished = 1;\n-\t\treturn 1;\n-\t}\n-\tif (err != 0)\n+\tif (err) {\n+\t\ttable_iter_block_done(dest);\n \t\treturn err;\n-\telse {\n-\t\tstruct block_reader *brp =\n-\t\t\treftable_malloc(sizeof(struct block_reader));\n-\t\t*brp = br;\n-\n-\t\tdest->is_finished = 0;\n-\t\tblock_iter_seek_start(&dest->bi, brp);\n \t}\n+\n+\tdest->is_finished = 0;\n+\tblock_iter_seek_start(&dest->bi, &dest->br);\n+\n \treturn 0;\n }\n \n@@ -377,14 +363,13 @@ static int table_iter_next(struct table_iter *ti, struct reftable_record *rec)\n \t\t * iterator is drained.\n \t\t */\n \t\terr = table_iter_next_block(&next, ti);\n-\t\ttable_iter_block_done(ti);\n \t\tif (err) {\n \t\t\tti->is_finished = 1;\n \t\t\treturn err;\n \t\t}\n \n-\t\ttable_iter_copy_from(ti, &next);\n-\t\tblock_iter_close(&next.bi);\n+\t\ttable_iter_close(ti);\n+\t\t*ti = next;\n \t}\n }\n \n@@ -393,16 +378,14 @@ static int table_iter_next_void(void *ti, struct reftable_record *rec)\n \treturn table_iter_next(ti, rec);\n }\n \n-static void table_iter_close(void *p)\n+static void table_iter_close_void(void *ti)\n {\n-\tstruct table_iter *ti = p;\n-\ttable_iter_block_done(ti);\n-\tblock_iter_close(&ti->bi);\n+\ttable_iter_close(ti);\n }\n \n static struct reftable_iterator_vtable table_iter_vtable = {\n \t.next = &table_iter_next_void,\n-\t.close = &table_iter_close,\n+\t.close = &table_iter_close_void,\n };\n \n static void iterator_from_table_iter(struct reftable_iterator *it,\n@@ -417,19 +400,16 @@ static int reader_table_iter_at(struct reftable_reader *r,\n \t\t\t\tstruct table_iter *ti, uint64_t off,\n \t\t\t\tuint8_t typ)\n {\n-\tstruct block_reader br = { 0 };\n-\tstruct block_reader *brp = NULL;\n+\tint err;\n \n-\tint err = reader_init_block_reader(r, &br, off, typ);\n+\terr = reader_init_block_reader(r, &ti->br, off, typ);\n \tif (err != 0)\n \t\treturn err;\n \n-\tbrp = reftable_malloc(sizeof(struct block_reader));\n-\t*brp = br;\n \tti->r = r;\n-\tti->typ = block_reader_type(brp);\n+\tti->typ = block_reader_type(&ti->br);\n \tti->block_off = off;\n-\tblock_iter_seek_start(&ti->bi, brp);\n+\tblock_iter_seek_start(&ti->bi, &ti->br);\n \treturn 0;\n }\n \n@@ -454,23 +434,34 @@ static int reader_seek_linear(struct table_iter *ti,\n {\n \tstruct strbuf want_key = STRBUF_INIT;\n \tstruct strbuf got_key = STRBUF_INIT;\n-\tstruct table_iter next = TABLE_ITER_INIT;\n \tstruct reftable_record rec;\n \tint err = -1;\n \n \treftable_record_init(&rec, reftable_record_type(want));\n \treftable_record_key(want, &want_key);\n \n+\t/*\n+\t * First we need to locate the block that must contain our record. To\n+\t * do so we scan through blocks linearly until we find the first block\n+\t * whose first key is bigger than our wanted key. Once we have found\n+\t * that block we know that the key must be contained in the preceding\n+\t * block.\n+\t *\n+\t * This algorithm is somewhat unfortunate because it means that we\n+\t * always have to seek one block too far and then back up. But as we\n+\t * can only decode the _first_ key of a block but not its _last_ key we\n+\t * have no other way to do this.\n+\t */\n \twhile (1) {\n+\t\tstruct table_iter next = TABLE_ITER_INIT;\n+\n \t\terr = table_iter_next_block(&next, ti);\n \t\tif (err < 0)\n \t\t\tgoto done;\n-\n-\t\tif (err > 0) {\n+\t\tif (err > 0)\n \t\t\tbreak;\n-\t\t}\n \n-\t\terr = block_reader_first_key(next.bi.br, &got_key);\n+\t\terr = block_reader_first_key(&next.br, &got_key);\n \t\tif (err < 0)\n \t\t\tgoto done;\n \n@@ -480,16 +471,20 @@ static int reader_seek_linear(struct table_iter *ti,\n \t\t}\n \n \t\ttable_iter_block_done(ti);\n-\t\ttable_iter_copy_from(ti, &next);\n+\t\t*ti = next;\n \t}\n \n-\terr = block_iter_seek_key(&ti->bi, ti->bi.br, &want_key);\n+\t/*\n+\t * We have located the block that must contain our record, so we seek\n+\t * the wanted key inside of it. If the block does not contain our key\n+\t * we know that the corresponding record does not exist.\n+\t */\n+\terr = block_iter_seek_key(&ti->bi, &ti->br, &want_key);\n \tif (err < 0)\n \t\tgoto done;\n \terr = 0;\n \n done:\n-\tblock_iter_close(&next.bi);\n \treftable_record_release(&rec);\n \tstrbuf_release(&want_key);\n \tstrbuf_release(&got_key);\n@@ -508,6 +503,7 @@ static int reader_seek_indexed(struct reftable_reader *r,\n \t\t.u.idx = { .last_key = STRBUF_INIT },\n \t};\n \tstruct table_iter index_iter = TABLE_ITER_INIT;\n+\tstruct table_iter empty = TABLE_ITER_INIT;\n \tstruct table_iter next = TABLE_ITER_INIT;\n \tint err = 0;\n \n@@ -549,7 +545,6 @@ static int reader_seek_indexed(struct reftable_reader *r,\n \t\t * not exist.\n \t\t */\n \t\terr = table_iter_next(&index_iter, &index_result);\n-\t\ttable_iter_block_done(&index_iter);\n \t\tif (err != 0)\n \t\t\tgoto done;\n \n@@ -558,7 +553,7 @@ static int reader_seek_indexed(struct reftable_reader *r,\n \t\tif (err != 0)\n \t\t\tgoto done;\n \n-\t\terr = block_iter_seek_key(&next.bi, next.bi.br, &want_index.u.idx.last_key);\n+\t\terr = block_iter_seek_key(&next.bi, &next.br, &want_index.u.idx.last_key);\n \t\tif (err < 0)\n \t\t\tgoto done;\n \n@@ -572,18 +567,20 @@ static int reader_seek_indexed(struct reftable_reader *r,\n \t\t\tbreak;\n \t\t}\n \n-\t\ttable_iter_copy_from(&index_iter, &next);\n+\t\ttable_iter_close(&index_iter);\n+\t\tindex_iter = next;\n+\t\tnext = empty;\n \t}\n \n \tif (err == 0) {\n-\t\tstruct table_iter empty = TABLE_ITER_INIT;\n \t\tstruct table_iter *malloced = reftable_calloc(1, sizeof(*malloced));\n-\t\t*malloced = empty;\n-\t\ttable_iter_copy_from(malloced, &next);\n+\t\t*malloced = next;\n+\t\tnext = empty;\n \t\titerator_from_table_iter(it, malloced);\n \t}\n+\n done:\n-\tblock_iter_close(&next.bi);\n+\ttable_iter_close(&next);\n \ttable_iter_close(&index_iter);\n \treftable_record_release(&want_index);\n \treftable_record_release(&index_result);\n-- \n2.44.GIT\n\n"},{"id":"491639","messageId":"ae359cb714faa550b585af4a002ad84b01c2b576.1711519925.git.ps@pks.im","threadId":"61207","inReplyTo":"cover.1711519925.git.ps@pks.im","subject":"[PATCH 6/9] reftable/reader: iterate to next block in place","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-03-27T06:37:17Z","receivedAt":"2024-03-27T06:37:20Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"The table iterator has to iterate towards the next block once it has\nyielded all records of the current block. This is done by creating a new\ntable iterator, initializing it to the next block, releasing the old\niterator and then copying over the data.\n\nRefactor the code to instead advance the table iterator in place. This\nis simpler and unlocks some optimizations in subsequent patches. Also,\nit allows us to avoid some allocations.\n\nThe following measurements show a single matching ref out of 1 million\nrefs. Before this change:\n\n  HEAP SUMMARY:\n      in use at exit: 13,603 bytes in 125 blocks\n    total heap usage: 7,235 allocs, 7,110 frees, 301,481 bytes allocated\n\nAfter:\n\n  HEAP SUMMARY:\n      in use at exit: 13,603 bytes in 125 blocks\n    total heap usage: 315 allocs, 190 frees, 107,027 bytes allocated\n\nSigned-off-by: Patrick Steinhardt <ps@pks.im>\n---\n reftable/block.c  |  2 ++\n reftable/reader.c | 47 ++++++++++++++++++++++++++---------------------\n 2 files changed, 28 insertions(+), 21 deletions(-)\n\ndiff --git a/reftable/block.c b/reftable/block.c\nindex 8f5dfe10bf..471ebd8580 100644\n--- a/reftable/block.c\n+++ b/reftable/block.c\n@@ -188,6 +188,8 @@ int block_reader_init(struct block_reader *br, struct reftable_block *block,\n \tuint8_t *restart_bytes = NULL;\n \tuint8_t *uncompressed = NULL;\n \n+\treftable_block_done(&br->block);\n+\n \tif (!reftable_is_block_type(typ)) {\n \t\terr =  REFTABLE_FORMAT_ERROR;\n \t\tgoto done;\ndiff --git a/reftable/reader.c b/reftable/reader.c\nindex b77b639751..dd4de294a1 100644\n--- a/reftable/reader.c\n+++ b/reftable/reader.c\n@@ -312,26 +312,20 @@ static void table_iter_close(struct table_iter *ti)\n \tblock_iter_close(&ti->bi);\n }\n \n-static int table_iter_next_block(struct table_iter *dest,\n-\t\t\t\t struct table_iter *src)\n+static int table_iter_next_block(struct table_iter *ti)\n {\n-\tuint64_t next_block_off = src->block_off + src->br.full_block_size;\n+\tuint64_t next_block_off = ti->block_off + ti->br.full_block_size;\n \tint err;\n \n-\tdest->r = src->r;\n-\tdest->typ = src->typ;\n-\tdest->block_off = next_block_off;\n-\n-\terr = reader_init_block_reader(src->r, &dest->br, next_block_off, src->typ);\n+\terr = reader_init_block_reader(ti->r, &ti->br, next_block_off, ti->typ);\n \tif (err > 0)\n-\t\tdest->is_finished = 1;\n-\tif (err) {\n-\t\ttable_iter_block_done(dest);\n+\t\tti->is_finished = 1;\n+\tif (err)\n \t\treturn err;\n-\t}\n \n-\tdest->is_finished = 0;\n-\tblock_iter_seek_start(&dest->bi, &dest->br);\n+\tti->block_off = next_block_off;\n+\tti->is_finished = 0;\n+\tblock_iter_seek_start(&ti->bi, &ti->br);\n \n \treturn 0;\n }\n@@ -342,7 +336,6 @@ static int table_iter_next(struct table_iter *ti, struct reftable_record *rec)\n \t\treturn REFTABLE_API_ERROR;\n \n \twhile (1) {\n-\t\tstruct table_iter next = TABLE_ITER_INIT;\n \t\tint err;\n \n \t\tif (ti->is_finished)\n@@ -362,14 +355,11 @@ static int table_iter_next(struct table_iter *ti, struct reftable_record *rec)\n \t\t * table and retry. If there are no more blocks then the\n \t\t * iterator is drained.\n \t\t */\n-\t\terr = table_iter_next_block(&next, ti);\n+\t\terr = table_iter_next_block(ti);\n \t\tif (err) {\n \t\t\tti->is_finished = 1;\n \t\t\treturn err;\n \t\t}\n-\n-\t\ttable_iter_close(ti);\n-\t\t*ti = next;\n \t}\n }\n \n@@ -453,9 +443,24 @@ static int reader_seek_linear(struct table_iter *ti,\n \t * have no other way to do this.\n \t */\n \twhile (1) {\n-\t\tstruct table_iter next = TABLE_ITER_INIT;\n+\t\tstruct table_iter next = *ti;\n+\n+\t\t/*\n+\t\t * We must be careful to not modify underlying data of `ti`\n+\t\t * because we may find that `next` does not contain our desired\n+\t\t * block, but that `ti` does. In that case, we would discard\n+\t\t * `next` and continue with `ti`.\n+\t\t *\n+\t\t * This also means that we cannot reuse allocated memory for\n+\t\t * `next` here. While it would be great if we could, it should\n+\t\t * in practice not be too bad given that we should only ever\n+\t\t * end up doing linear seeks with at most three blocks. As soon\n+\t\t * as we have more than three blocks we would have an index, so\n+\t\t * we would not do a linear search there anymore.\n+\t\t */\n+\t\tmemset(&next.br.block, 0, sizeof(next.br.block));\n \n-\t\terr = table_iter_next_block(&next, ti);\n+\t\terr = table_iter_next_block(&next);\n \t\tif (err < 0)\n \t\t\tgoto done;\n \t\tif (err > 0)\n-- \n2.44.GIT\n\n"},{"id":"491640","messageId":"1e4eba7e9b6b706b30eb5748156ce991ecb4ae37.1711519925.git.ps@pks.im","threadId":"61207","inReplyTo":"cover.1711519925.git.ps@pks.im","subject":"[PATCH 7/9] reftable/block: reuse uncompressed blocks","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-03-27T06:37:21Z","receivedAt":"2024-03-27T06:37:24Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"The reftable backend stores reflog entries in a compressed format and\nthus needs to uncompress blocks before one can read records from it.\nFor each reflog block we thus have to allocate an array that we can\ndecompress the block contents into. This block is being discarded\nwhenever the table iterator moves to the next block. Consequently, we\nreallocate a new array on every block, which is quite wasteful.\n\nRefactor the code to reuse the uncompressed block data when moving the\nblock reader to a new block. This significantly reduces the number of\nallocations when iterating through many compressed blocks. The following\nmeasurements are done with `git reflog list` when listing 100k reflogs.\nBefore:\n\n  HEAP SUMMARY:\n      in use at exit: 13,473 bytes in 122 blocks\n    total heap usage: 45,755 allocs, 45,633 frees, 254,779,456 bytes allocated\n\nAfter:\n\n  HEAP SUMMARY:\n      in use at exit: 13,473 bytes in 122 blocks\n    total heap usage: 23,028 allocs, 22,906 frees, 162,813,547 bytes allocated\n\nSigned-off-by: Patrick Steinhardt <ps@pks.im>\n---\n reftable/block.c  | 14 ++++++--------\n reftable/block.h  |  4 ++++\n reftable/reader.c | 27 ++++++++++++++++-----------\n 3 files changed, 26 insertions(+), 19 deletions(-)\n\ndiff --git a/reftable/block.c b/reftable/block.c\nindex 471ebd8580..31af075c1d 100644\n--- a/reftable/block.c\n+++ b/reftable/block.c\n@@ -186,7 +186,6 @@ int block_reader_init(struct block_reader *br, struct reftable_block *block,\n \tuint16_t restart_count = 0;\n \tuint32_t restart_start = 0;\n \tuint8_t *restart_bytes = NULL;\n-\tuint8_t *uncompressed = NULL;\n \n \treftable_block_done(&br->block);\n \n@@ -202,14 +201,15 @@ int block_reader_init(struct block_reader *br, struct reftable_block *block,\n \t\tuLongf src_len = block->len - block_header_skip;\n \n \t\t/* Log blocks specify the *uncompressed* size in their header. */\n-\t\tREFTABLE_ALLOC_ARRAY(uncompressed, sz);\n+\t\tREFTABLE_ALLOC_GROW(br->uncompressed_data, sz,\n+\t\t\t\t    br->uncompressed_cap);\n \n \t\t/* Copy over the block header verbatim. It's not compressed. */\n-\t\tmemcpy(uncompressed, block->data, block_header_skip);\n+\t\tmemcpy(br->uncompressed_data, block->data, block_header_skip);\n \n \t\t/* Uncompress */\n \t\tif (Z_OK !=\n-\t\t    uncompress2(uncompressed + block_header_skip, &dst_len,\n+\t\t    uncompress2(br->uncompressed_data + block_header_skip, &dst_len,\n \t\t\t\tblock->data + block_header_skip, &src_len)) {\n \t\t\terr = REFTABLE_ZLIB_ERROR;\n \t\t\tgoto done;\n@@ -222,10 +222,8 @@ int block_reader_init(struct block_reader *br, struct reftable_block *block,\n \n \t\t/* We're done with the input data. */\n \t\treftable_block_done(block);\n-\t\tblock->data = uncompressed;\n-\t\tuncompressed = NULL;\n+\t\tblock->data = br->uncompressed_data;\n \t\tblock->len = sz;\n-\t\tblock->source = malloc_block_source();\n \t\tfull_block_size = src_len + block_header_skip;\n \t} else if (full_block_size == 0) {\n \t\tfull_block_size = sz;\n@@ -254,12 +252,12 @@ int block_reader_init(struct block_reader *br, struct reftable_block *block,\n \tbr->restart_bytes = restart_bytes;\n \n done:\n-\treftable_free(uncompressed);\n \treturn err;\n }\n \n void block_reader_release(struct block_reader *br)\n {\n+\treftable_free(br->uncompressed_data);\n \treftable_block_done(&br->block);\n }\n \ndiff --git a/reftable/block.h b/reftable/block.h\nindex b41efa5042..79275d67f1 100644\n--- a/reftable/block.h\n+++ b/reftable/block.h\n@@ -66,6 +66,10 @@ struct block_reader {\n \tstruct reftable_block block;\n \tint hash_size;\n \n+\t/* Uncompressed data for log entries. */\n+\tunsigned char *uncompressed_data;\n+\tsize_t uncompressed_cap;\n+\n \t/* size of the data, excluding restart data. */\n \tuint32_t block_len;\n \tuint8_t *restart_bytes;\ndiff --git a/reftable/reader.c b/reftable/reader.c\nindex dd4de294a1..aacd5f1337 100644\n--- a/reftable/reader.c\n+++ b/reftable/reader.c\n@@ -459,6 +459,8 @@ static int reader_seek_linear(struct table_iter *ti,\n \t\t * we would not do a linear search there anymore.\n \t\t */\n \t\tmemset(&next.br.block, 0, sizeof(next.br.block));\n+\t\tnext.br.uncompressed_data = NULL;\n+\t\tnext.br.uncompressed_cap = 0;\n \n \t\terr = table_iter_next_block(&next);\n \t\tif (err < 0)\n@@ -599,25 +601,28 @@ static int reader_seek_internal(struct reftable_reader *r,\n \tstruct reftable_reader_offsets *offs =\n \t\treader_offsets_for(r, reftable_record_type(rec));\n \tuint64_t idx = offs->index_offset;\n-\tstruct table_iter ti = TABLE_ITER_INIT;\n-\tint err = 0;\n+\tstruct table_iter ti = TABLE_ITER_INIT, *p;\n+\tint err;\n+\n \tif (idx > 0)\n \t\treturn reader_seek_indexed(r, it, rec);\n \n \terr = reader_start(r, &ti, reftable_record_type(rec), 0);\n \tif (err < 0)\n-\t\treturn err;\n+\t\tgoto out;\n+\n \terr = reader_seek_linear(&ti, rec);\n \tif (err < 0)\n-\t\treturn err;\n-\telse {\n-\t\tstruct table_iter *p =\n-\t\t\treftable_malloc(sizeof(struct table_iter));\n-\t\t*p = ti;\n-\t\titerator_from_table_iter(it, p);\n-\t}\n+\t\tgoto out;\n \n-\treturn 0;\n+\tREFTABLE_ALLOC_ARRAY(p, 1);\n+\t*p = ti;\n+\titerator_from_table_iter(it, p);\n+\n+out:\n+\tif (err)\n+\t\ttable_iter_close(&ti);\n+\treturn err;\n }\n \n static int reader_seek(struct reftable_reader *r, struct reftable_iterator *it,\n-- \n2.44.GIT\n\n"},{"id":"491641","messageId":"bf4c1ab797d32284b469034c5272383fd998439e.1711519925.git.ps@pks.im","threadId":"61207","inReplyTo":"cover.1711519925.git.ps@pks.im","subject":"[PATCH 8/9] reftable/block: open-code call to `uncompress2()`","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-03-27T06:37:25Z","receivedAt":"2024-03-27T06:37:28Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"The reftable format stores log blocks in a compressed format. Thus,\nwhenever we want to read such a block we first need to decompress it.\nThis is done by calling the convenience function `uncompress2()` of the\nzlib library, which is a simple wrapper that manages the lifecycle of\nthe `zstream` structure for us.\n\nWhile nice for one-off inflation of data, when iterating through reflogs\nwe will likely end up inflating many such log blocks. This requires us\nto reallocate the state of the `zstream` every single time, which adds\nup over time. It would thus be great to reuse the `zstream` instead of\ndiscarding it after every inflation.\n\nOpen-code the call to `uncompress2()` such that we can start reusing the\n`zstream` in the subsequent commit. Note that our open-coded variant is\ndifferent from `uncompress2()` in two ways:\n\n  - We do not loop around `inflate()` until we have processed all input.\n    As our input is limited by the maximum block size, which is 16MB, we\n    should not hit limits of `inflate()`.\n\n  - We use `Z_FINISH` instead of `Z_NO_FLUSH`. Quoting the `inflate()`\n    documentation: \"inflate() should normally be called until it returns\n    Z_STREAM_END or an error. However if all decompression is to be\n    performed in a single step (a single call of inflate), the parameter\n    flush should be set to Z_FINISH.\"\n\n    Furthermore, \"Z_FINISH also informs inflate to not maintain a\n    sliding window if the stream completes, which reduces inflate's\n    memory footprint.\"\n\nOther than that this commit is expected to be functionally equivalent\nand does not yet reuse the `zstream`.\n\nSigned-off-by: Patrick Steinhardt <ps@pks.im>\n---\n reftable/block.c | 38 ++++++++++++++++++++++++++++----------\n 1 file changed, 28 insertions(+), 10 deletions(-)\n\ndiff --git a/reftable/block.c b/reftable/block.c\nindex 31af075c1d..31e7255056 100644\n--- a/reftable/block.c\n+++ b/reftable/block.c\n@@ -195,10 +195,10 @@ int block_reader_init(struct block_reader *br, struct reftable_block *block,\n \t}\n \n \tif (typ == BLOCK_TYPE_LOG) {\n-\t\tint block_header_skip = 4 + header_off;\n-\t\tuLongf dst_len = sz - block_header_skip; /* total size of dest\n-\t\t\t\t\t\t\t    buffer. */\n-\t\tuLongf src_len = block->len - block_header_skip;\n+\t\tuint32_t block_header_skip = 4 + header_off;\n+\t\tuLong dst_len = sz - block_header_skip;\n+\t\tuLong src_len = block->len - block_header_skip;\n+\t\tz_stream stream = {0};\n \n \t\t/* Log blocks specify the *uncompressed* size in their header. */\n \t\tREFTABLE_ALLOC_GROW(br->uncompressed_data, sz,\n@@ -207,15 +207,33 @@ int block_reader_init(struct block_reader *br, struct reftable_block *block,\n \t\t/* Copy over the block header verbatim. It's not compressed. */\n \t\tmemcpy(br->uncompressed_data, block->data, block_header_skip);\n \n-\t\t/* Uncompress */\n-\t\tif (Z_OK !=\n-\t\t    uncompress2(br->uncompressed_data + block_header_skip, &dst_len,\n-\t\t\t\tblock->data + block_header_skip, &src_len)) {\n+\t\terr = inflateInit(&stream);\n+\t\tif (err != Z_OK) {\n \t\t\terr = REFTABLE_ZLIB_ERROR;\n \t\t\tgoto done;\n \t\t}\n \n-\t\tif (dst_len + block_header_skip != sz) {\n+\t\tstream.next_in = block->data + block_header_skip;\n+\t\tstream.avail_in = src_len;\n+\t\tstream.next_out = br->uncompressed_data + block_header_skip;\n+\t\tstream.avail_out = dst_len;\n+\n+\t\t/*\n+\t\t * We know both input as well as output size, and we know that\n+\t\t * the sizes should never be bigger than `uInt_MAX` because\n+\t\t * blocks can at most be 16MB large. We can thus use `Z_FINISH`\n+\t\t * here to instruct zlib to inflate the data in one go, which\n+\t\t * is more efficient than using `Z_NO_FLUSH`.\n+\t\t */\n+\t\terr = inflate(&stream, Z_FINISH);\n+\t\tinflateEnd(&stream);\n+\t\tif (err != Z_STREAM_END) {\n+\t\t\terr = REFTABLE_ZLIB_ERROR;\n+\t\t\tgoto done;\n+\t\t}\n+\t\terr = 0;\n+\n+\t\tif (stream.total_out + block_header_skip != sz) {\n \t\t\terr = REFTABLE_FORMAT_ERROR;\n \t\t\tgoto done;\n \t\t}\n@@ -224,7 +242,7 @@ int block_reader_init(struct block_reader *br, struct reftable_block *block,\n \t\treftable_block_done(block);\n \t\tblock->data = br->uncompressed_data;\n \t\tblock->len = sz;\n-\t\tfull_block_size = src_len + block_header_skip;\n+\t\tfull_block_size = src_len + block_header_skip - stream.avail_in;\n \t} else if (full_block_size == 0) {\n \t\tfull_block_size = sz;\n \t} else if (sz < full_block_size && sz < block->len &&\n-- \n2.44.GIT\n\n"},{"id":"491642","messageId":"43e6538968bbd4a0bc4217ebbaa834a98e2020c3.1711519925.git.ps@pks.im","threadId":"61207","inReplyTo":"cover.1711519925.git.ps@pks.im","subject":"[PATCH 9/9] reftable/block: reuse `zstream` state on inflation","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-03-27T06:37:29Z","receivedAt":"2024-03-27T06:37:33Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"When calling `inflateInit()` and `inflate()`, the zlib library will\nallocate several data structures for the underlying `zstream` to keep\ntrack of various information. Thus, when inflating repeatedly, it is\npossible to optimize memory allocation patterns by reusing the `zstream`\nand then calling `inflateReset()` on it to prepare it for the next chunk\nof data to inflate.\n\nThis is exactly what the reftable code is doing: when iterating through\nreflogs we need to potentially inflate many log blocks, but we discard\nthe `zstream` every single time. Instead, as we reuse the `block_reader`\nfor each of the blocks anyway, we can initialize the `zstream` once and\nthen reuse it for subsequent inflations.\n\nRefactor the code to do so, which leads to a significant reduction in\nthe number of allocations. The following measurements were done when\niterating through 1 million reflog entries. Before:\n\n  HEAP SUMMARY:\n      in use at exit: 13,473 bytes in 122 blocks\n    total heap usage: 23,028 allocs, 22,906 frees, 162,813,552 bytes allocated\n\nAfter:\n\n  HEAP SUMMARY:\n      in use at exit: 13,473 bytes in 122 blocks\n    total heap usage: 302 allocs, 180 frees, 88,352 bytes allocated\n\nSigned-off-by: Patrick Steinhardt <ps@pks.im>\n---\n reftable/block.c  | 25 +++++++++++++++----------\n reftable/block.h  |  3 +++\n reftable/reader.c |  1 +\n 3 files changed, 19 insertions(+), 10 deletions(-)\n\ndiff --git a/reftable/block.c b/reftable/block.c\nindex 31e7255056..2e39640b1c 100644\n--- a/reftable/block.c\n+++ b/reftable/block.c\n@@ -198,7 +198,6 @@ int block_reader_init(struct block_reader *br, struct reftable_block *block,\n \t\tuint32_t block_header_skip = 4 + header_off;\n \t\tuLong dst_len = sz - block_header_skip;\n \t\tuLong src_len = block->len - block_header_skip;\n-\t\tz_stream stream = {0};\n \n \t\t/* Log blocks specify the *uncompressed* size in their header. */\n \t\tREFTABLE_ALLOC_GROW(br->uncompressed_data, sz,\n@@ -207,16 +206,21 @@ int block_reader_init(struct block_reader *br, struct reftable_block *block,\n \t\t/* Copy over the block header verbatim. It's not compressed. */\n \t\tmemcpy(br->uncompressed_data, block->data, block_header_skip);\n \n-\t\terr = inflateInit(&stream);\n+\t\tif (!br->zstream) {\n+\t\t\tREFTABLE_CALLOC_ARRAY(br->zstream, 1);\n+\t\t\terr = inflateInit(br->zstream);\n+\t\t} else {\n+\t\t\terr = inflateReset(br->zstream);\n+\t\t}\n \t\tif (err != Z_OK) {\n \t\t\terr = REFTABLE_ZLIB_ERROR;\n \t\t\tgoto done;\n \t\t}\n \n-\t\tstream.next_in = block->data + block_header_skip;\n-\t\tstream.avail_in = src_len;\n-\t\tstream.next_out = br->uncompressed_data + block_header_skip;\n-\t\tstream.avail_out = dst_len;\n+\t\tbr->zstream->next_in = block->data + block_header_skip;\n+\t\tbr->zstream->avail_in = src_len;\n+\t\tbr->zstream->next_out = br->uncompressed_data + block_header_skip;\n+\t\tbr->zstream->avail_out = dst_len;\n \n \t\t/*\n \t\t * We know both input as well as output size, and we know that\n@@ -225,15 +229,14 @@ int block_reader_init(struct block_reader *br, struct reftable_block *block,\n \t\t * here to instruct zlib to inflate the data in one go, which\n \t\t * is more efficient than using `Z_NO_FLUSH`.\n \t\t */\n-\t\terr = inflate(&stream, Z_FINISH);\n-\t\tinflateEnd(&stream);\n+\t\terr = inflate(br->zstream, Z_FINISH);\n \t\tif (err != Z_STREAM_END) {\n \t\t\terr = REFTABLE_ZLIB_ERROR;\n \t\t\tgoto done;\n \t\t}\n \t\terr = 0;\n \n-\t\tif (stream.total_out + block_header_skip != sz) {\n+\t\tif (br->zstream->total_out + block_header_skip != sz) {\n \t\t\terr = REFTABLE_FORMAT_ERROR;\n \t\t\tgoto done;\n \t\t}\n@@ -242,7 +245,7 @@ int block_reader_init(struct block_reader *br, struct reftable_block *block,\n \t\treftable_block_done(block);\n \t\tblock->data = br->uncompressed_data;\n \t\tblock->len = sz;\n-\t\tfull_block_size = src_len + block_header_skip - stream.avail_in;\n+\t\tfull_block_size = src_len + block_header_skip - br->zstream->avail_in;\n \t} else if (full_block_size == 0) {\n \t\tfull_block_size = sz;\n \t} else if (sz < full_block_size && sz < block->len &&\n@@ -275,6 +278,8 @@ int block_reader_init(struct block_reader *br, struct reftable_block *block,\n \n void block_reader_release(struct block_reader *br)\n {\n+\tinflateEnd(br->zstream);\n+\treftable_free(br->zstream);\n \treftable_free(br->uncompressed_data);\n \treftable_block_done(&br->block);\n }\ndiff --git a/reftable/block.h b/reftable/block.h\nindex 79275d67f1..93f4338771 100644\n--- a/reftable/block.h\n+++ b/reftable/block.h\n@@ -56,6 +56,8 @@ int block_writer_finish(struct block_writer *w);\n /* clears out internally allocated block_writer members. */\n void block_writer_release(struct block_writer *bw);\n \n+struct z_stream;\n+\n /* Read a block. */\n struct block_reader {\n \t/* offset of the block header; nonzero for the first block in a\n@@ -67,6 +69,7 @@ struct block_reader {\n \tint hash_size;\n \n \t/* Uncompressed data for log entries. */\n+\tz_stream *zstream;\n \tunsigned char *uncompressed_data;\n \tsize_t uncompressed_cap;\n \ndiff --git a/reftable/reader.c b/reftable/reader.c\nindex aacd5f1337..481dff10d4 100644\n--- a/reftable/reader.c\n+++ b/reftable/reader.c\n@@ -459,6 +459,7 @@ static int reader_seek_linear(struct table_iter *ti,\n \t\t * we would not do a linear search there anymore.\n \t\t */\n \t\tmemset(&next.br.block, 0, sizeof(next.br.block));\n+\t\tnext.br.zstream = NULL;\n \t\tnext.br.uncompressed_data = NULL;\n \t\tnext.br.uncompressed_cap = 0;\n \n-- \n2.44.GIT\n\n"},{"id":"492132","messageId":"hwfkdfilniy46usnc3vnksaphdxboi5bxep4ek7aj2qxfhu332@6ym7dnn35k7z","threadId":"61207","inReplyTo":"f10882a0840a77f2569cf891374b70d1e84ceb4b.1711519925.git.ps@pks.im","subject":"Re: [PATCH 5/9] reftable/block: move ownership of block reader into `struct table_iter`","fromName":"Justin Tobler","fromEmail":"jltobler@gmail.com","sentAt":"2024-04-03T04:52:58Z","receivedAt":"2024-04-03T04:53:57Z","isPatch":true,"sender":{"key":"jltobler@gmail.com","avatar":"https://avatars.githubusercontent.com/u/53454972?v=4"},"body":"On 24/03/27 07:37AM, Patrick Steinhardt wrote:\n> The table iterator allows the caller to iterate through all records in a\n> reftable table. To do so it iterates through all blocks of the desired\n> type one by one, where for each block it creates a new block iterator\n> and yields all its entries.\n> \n> One of the things that is somewhat confusing in this context is who owns\n> the block reader that is being used to read the blocks and pass them to\n> the block iterator. Intuitively, as the table iterator is responsible\n> for iterating through the blocks, one would assume that this iterator is\n> also responsible for managing the lifecycle of the reader. And while it\n> somewhat is, the block reader is ultimately stored inside of the block\n> iterator.\n> \n> Refactor the code such that the block reader is instead fully managed by\n> the table iterator. Instead of passing the reader to the block iterator,\n> we now only end up passing the block data to it. Despite clearing up the\n> lifecycle of the reader, it will also allow for better reuse of the\n> reader in subsequent patches.\n> \n> The following benchmark prints a single matching ref out of 1 million\n> refs. Before:\n> \n>   HEAP SUMMARY:\n>       in use at exit: 13,603 bytes in 125 blocks\n>     total heap usage: 6,607 allocs, 6,482 frees, 509,635 bytes allocated\n> \n> After:\n> \n>   HEAP SUMMARY:\n>       in use at exit: 13,603 bytes in 125 blocks\n>     total heap usage: 7,235 allocs, 7,110 frees, 301,481 bytes allocated\n> \n> Note that while there are more allocation and free calls now, the\n> overall number of bytes allocated is significantly lower. The number of\n> allocations will be reduced significantly by the next patch though.\n> \n> Signed-off-by: Patrick Steinhardt <ps@pks.im>\n...\n> @@ -340,14 +344,14 @@ void block_iter_copy_from(struct block_iter *dest, struct block_iter *src)\n>  int block_iter_next(struct block_iter *it, struct reftable_record *rec)\n>  {\n>  \tstruct string_view in = {\n> -\t\t.buf = it->br->block.data + it->next_off,\n> -\t\t.len = it->br->block_len - it->next_off,\n> +\t\t.buf = (unsigned char *) it->block + it->next_off,\n\nWould it be best to use the `uint8_t *` type instead of `unsigned char *`\nto match `string_view.buf`? Not sure if it matters in this case.\n\n> +\t\t.len = it->block_len - it->next_off,\n>  \t};\n...  \n> diff --git a/reftable/block.h b/reftable/block.h\n> index 601a1e0e89..b41efa5042 100644\n> --- a/reftable/block.h\n> +++ b/reftable/block.h\n> @@ -84,16 +84,18 @@ int block_reader_init(struct block_reader *br, struct reftable_block *bl,\n>  void block_reader_release(struct block_reader *br);\n>  \n>  /* Returns the block type (eg. 'r' for refs) */\n> -uint8_t block_reader_type(struct block_reader *r);\n> +uint8_t block_reader_type(const struct block_reader *r);\n>  \n>  /* Decodes the first key in the block */\n> -int block_reader_first_key(struct block_reader *br, struct strbuf *key);\n> +int block_reader_first_key(const struct block_reader *br, struct strbuf *key);\n>  \n>  /* Iterate over entries in a block */\n>  struct block_iter {\n>  \t/* offset within the block of the next entry to read. */\n>  \tuint32_t next_off;\n> -\tstruct block_reader *br;\n> +\tconst unsigned char *block;\n\nSame question here. Would it be better to use `uint8_t *`? Or does it not\nreally matter?\n\n> +\tsize_t block_len;\n> +\tint hash_size;\n>  \n>  \t/* key for last entry we read. */\n>  \tstruct strbuf last_key;\n> @@ -106,17 +108,22 @@ struct block_iter {\n>  }\n>  \n>  /* Position `it` at start of the block */\n> -void block_iter_seek_start(struct block_iter *it, struct block_reader *br);\n> +void block_iter_seek_start(struct block_iter *it, const struct block_reader *br);\n>  \n>  /* Position `it` to the `want` key in the block */\n> -int block_iter_seek_key(struct block_iter *it, struct block_reader *br,\n> +int block_iter_seek_key(struct block_iter *it, const struct block_reader *br,\n>  \t\t\tstruct strbuf *want);\n>  \n> -void block_iter_copy_from(struct block_iter *dest, struct block_iter *src);\n> +void block_iter_copy_from(struct block_iter *dest, const struct block_iter *src);\n>  \n>  /* return < 0 for error, 0 for OK, > 0 for EOF. */\n>  int block_iter_next(struct block_iter *it, struct reftable_record *rec);\n>  \n> +/*\n> + * Reset the block iterator to pristine state without releasing its memory.\n> + */\n\nDo we want to make the comment a single line to match the other adjacent\nexamples?\n\n> +void block_iter_reset(struct block_iter *it);\n> +\n>  /* deallocate memory for `it`. The block reader and its block is left intact. */\n>  void block_iter_close(struct block_iter *it);\n>  \n...\n\n-Justin\n"},{"id":"492156","messageId":"Zg1VM6fz3TnmTGqy@tanuki","threadId":"61207","inReplyTo":"hwfkdfilniy46usnc3vnksaphdxboi5bxep4ek7aj2qxfhu332@6ym7dnn35k7z","subject":"Re: [PATCH 5/9] reftable/block: move ownership of block reader into `struct table_iter`","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-04-03T13:10:11Z","receivedAt":"2024-04-03T13:10:17Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"On Tue, Apr 02, 2024 at 11:52:58PM -0500, Justin Tobler wrote:\n> On 24/03/27 07:37AM, Patrick Steinhardt wrote:\n> > The table iterator allows the caller to iterate through all records in a\n> > reftable table. To do so it iterates through all blocks of the desired\n> > type one by one, where for each block it creates a new block iterator\n> > and yields all its entries.\n> > \n> > One of the things that is somewhat confusing in this context is who owns\n> > the block reader that is being used to read the blocks and pass them to\n> > the block iterator. Intuitively, as the table iterator is responsible\n> > for iterating through the blocks, one would assume that this iterator is\n> > also responsible for managing the lifecycle of the reader. And while it\n> > somewhat is, the block reader is ultimately stored inside of the block\n> > iterator.\n> > \n> > Refactor the code such that the block reader is instead fully managed by\n> > the table iterator. Instead of passing the reader to the block iterator,\n> > we now only end up passing the block data to it. Despite clearing up the\n> > lifecycle of the reader, it will also allow for better reuse of the\n> > reader in subsequent patches.\n> > \n> > The following benchmark prints a single matching ref out of 1 million\n> > refs. Before:\n> > \n> >   HEAP SUMMARY:\n> >       in use at exit: 13,603 bytes in 125 blocks\n> >     total heap usage: 6,607 allocs, 6,482 frees, 509,635 bytes allocated\n> > \n> > After:\n> > \n> >   HEAP SUMMARY:\n> >       in use at exit: 13,603 bytes in 125 blocks\n> >     total heap usage: 7,235 allocs, 7,110 frees, 301,481 bytes allocated\n> > \n> > Note that while there are more allocation and free calls now, the\n> > overall number of bytes allocated is significantly lower. The number of\n> > allocations will be reduced significantly by the next patch though.\n> > \n> > Signed-off-by: Patrick Steinhardt <ps@pks.im>\n> ...\n> > @@ -340,14 +344,14 @@ void block_iter_copy_from(struct block_iter *dest, struct block_iter *src)\n> >  int block_iter_next(struct block_iter *it, struct reftable_record *rec)\n> >  {\n> >  \tstruct string_view in = {\n> > -\t\t.buf = it->br->block.data + it->next_off,\n> > -\t\t.len = it->br->block_len - it->next_off,\n> > +\t\t.buf = (unsigned char *) it->block + it->next_off,\n> \n> Would it be best to use the `uint8_t *` type instead of `unsigned char *`\n> to match `string_view.buf`? Not sure if it matters in this case.\n\nIt doesn't really. `uint8_t` should always be equivalent to `unsigned\nchar`. I'd also think that `unsigned char` is a bit more idiomatic in\nour codebase, but may be mistaken there.\n\n> > +\t\t.len = it->block_len - it->next_off,\n> >  \t};\n> ...  \n> > diff --git a/reftable/block.h b/reftable/block.h\n> > index 601a1e0e89..b41efa5042 100644\n> > --- a/reftable/block.h\n> > +++ b/reftable/block.h\n> > @@ -84,16 +84,18 @@ int block_reader_init(struct block_reader *br, struct reftable_block *bl,\n> >  void block_reader_release(struct block_reader *br);\n> >  \n> >  /* Returns the block type (eg. 'r' for refs) */\n> > -uint8_t block_reader_type(struct block_reader *r);\n> > +uint8_t block_reader_type(const struct block_reader *r);\n> >  \n> >  /* Decodes the first key in the block */\n> > -int block_reader_first_key(struct block_reader *br, struct strbuf *key);\n> > +int block_reader_first_key(const struct block_reader *br, struct strbuf *key);\n> >  \n> >  /* Iterate over entries in a block */\n> >  struct block_iter {\n> >  \t/* offset within the block of the next entry to read. */\n> >  \tuint32_t next_off;\n> > -\tstruct block_reader *br;\n> > +\tconst unsigned char *block;\n> \n> Same question here. Would it be better to use `uint8_t *`? Or does it not\n> really matter?\n\nSame answer :)\n\n> > +\tsize_t block_len;\n> > +\tint hash_size;\n> >  \n> >  \t/* key for last entry we read. */\n> >  \tstruct strbuf last_key;\n> > @@ -106,17 +108,22 @@ struct block_iter {\n> >  }\n> >  \n> >  /* Position `it` at start of the block */\n> > -void block_iter_seek_start(struct block_iter *it, struct block_reader *br);\n> > +void block_iter_seek_start(struct block_iter *it, const struct block_reader *br);\n> >  \n> >  /* Position `it` to the `want` key in the block */\n> > -int block_iter_seek_key(struct block_iter *it, struct block_reader *br,\n> > +int block_iter_seek_key(struct block_iter *it, const struct block_reader *br,\n> >  \t\t\tstruct strbuf *want);\n> >  \n> > -void block_iter_copy_from(struct block_iter *dest, struct block_iter *src);\n> > +void block_iter_copy_from(struct block_iter *dest, const struct block_iter *src);\n> >  \n> >  /* return < 0 for error, 0 for OK, > 0 for EOF. */\n> >  int block_iter_next(struct block_iter *it, struct reftable_record *rec);\n> >  \n> > +/*\n> > + * Reset the block iterator to pristine state without releasing its memory.\n> > + */\n> \n> Do we want to make the comment a single line to match the other adjacent\n> examples?\n\nCan do. I'll refrain from sending a new version of this patch series for\nnow though as none of the comments really need addressing, in my\nopinion. But please, feel free to push back in case you disagree.\n\nPatrick\n\n> > +void block_iter_reset(struct block_iter *it);\n> > +\n> >  /* deallocate memory for `it`. The block reader and its block is left intact. */\n> >  void block_iter_close(struct block_iter *it);\n> >  \n> ...\n> \n> -Justin\n"},{"id":"492157","messageId":"CAOLa=ZQ4Vq7YfUsh4mky8HsEurp3RyUEXsZS7tDU0XMc+6Gv0w@mail.gmail.com","threadId":"61207","inReplyTo":"9a1253649a4dc993da7caced2f15839d988905d9.1711519925.git.ps@pks.im","subject":"Re: [PATCH 4/9] reftable/block: introduce `block_reader_release()`","fromName":"Karthik Nayak","fromEmail":"karthik.188@gmail.com","sentAt":"2024-04-03T13:16:35Z","receivedAt":"2024-04-03T13:16:36Z","isPatch":true,"sender":{"key":"karthik.188@gmail.com","avatar":"https://avatars.githubusercontent.com/u/1786334?v=4"},"body":"Patrick Steinhardt <ps@pks.im> writes:\n>\n> diff --git a/reftable/reader.c b/reftable/reader.c\n> index f70efa2b7c..f925570bf3 100644\n> --- a/reftable/reader.c\n> +++ b/reftable/reader.c\n> @@ -253,7 +253,7 @@ static void table_iter_block_done(struct table_iter *ti)\n>  \tif (!ti->bi.br) {\n>  \t\treturn;\n>  \t}\n> -\treftable_block_done(&ti->bi.br->block);\n> +\tblock_reader_release(ti->bi.br);\n>  \tFREE_AND_NULL(ti->bi.br);\n>\n>  \tti->bi.last_key.len = 0;\n\nI would expect `FREE_AND_NULL(ti->bi.br)` to also be within\n`block_reader_release`, but then you'd have to pass `table_iter` or\n`**`. So I guess this is okay.\n"},{"id":"492159","messageId":"CAOLa=ZRB=4TRTDR1Xb5CCDqXi9qEATBO_qZ1LvKUHsLff1_y3A@mail.gmail.com","threadId":"61207","inReplyTo":"cover.1711519925.git.ps@pks.im","subject":"Re: [PATCH 0/9] reftable: optimize table and block iterators","fromName":"Karthik Nayak","fromEmail":"karthik.188@gmail.com","sentAt":"2024-04-03T13:33:31Z","receivedAt":"2024-04-03T13:33:33Z","isPatch":true,"sender":{"key":"karthik.188@gmail.com","avatar":"https://avatars.githubusercontent.com/u/1786334?v=4"},"body":"Patrick Steinhardt <ps@pks.im> writes:\n\n> Hi,\n>\n>  * The code to iterate over reftable blocks has seen some optimization\n>    to reduce memory allocation and deallocation.\n>\n> Preceding patch series have optimized memory allocation patterns when\n> iterating through ref or log records. This has led to a constant number\n> of allocations when decoding and yielding those records to our callers.\n> One thing that is still missing though is an optimization for the table\n> and block iterators which are responsible for iterating through the\n> separate blocks in the table. So while the number of allocations does\n> not scale with the number of refs (directly) anymore, it still scales\n> with the number of blocks.\n>\n> This is getting tackled by this patch series now which refactors the\n> table and block iterators such that the former can reuse the latter\n> without reallocations. With this change iterating through records is now\n> using a truly constant number of allocations.\n\nThis patch series already looks good to me, I have nothing to add here.\n"},{"id":"492512","messageId":"ZhPezL_8Ozf375FI@tanuki","threadId":"61207","inReplyTo":"CAOLa=ZQ4Vq7YfUsh4mky8HsEurp3RyUEXsZS7tDU0XMc+6Gv0w@mail.gmail.com","subject":"Re: [PATCH 4/9] reftable/block: introduce `block_reader_release()`","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-04-08T12:10:52Z","receivedAt":"2024-04-08T12:10:59Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"On Wed, Apr 03, 2024 at 06:16:35AM -0700, Karthik Nayak wrote:\n> Patrick Steinhardt <ps@pks.im> writes:\n> >\n> > diff --git a/reftable/reader.c b/reftable/reader.c\n> > index f70efa2b7c..f925570bf3 100644\n> > --- a/reftable/reader.c\n> > +++ b/reftable/reader.c\n> > @@ -253,7 +253,7 @@ static void table_iter_block_done(struct table_iter *ti)\n> >  \tif (!ti->bi.br) {\n> >  \t\treturn;\n> >  \t}\n> > -\treftable_block_done(&ti->bi.br->block);\n> > +\tblock_reader_release(ti->bi.br);\n> >  \tFREE_AND_NULL(ti->bi.br);\n> >\n> >  \tti->bi.last_key.len = 0;\n> \n> I would expect `FREE_AND_NULL(ti->bi.br)` to also be within\n> `block_reader_release`, but then you'd have to pass `table_iter` or\n> `**`. So I guess this is okay.\n\nIt is customary in the Git codebase to discern `release` and `free`\nfunctions. `release` will release all memory hosted by a structure, but\nwill not release the structure itself. `free` on the other hand is\nexpected to free both the memory hosted by a structure, and the\nstructure itself. `block_reader_release()` thus shouldn't free the\n`struct block_reader`.\n\nPatrick\n"},{"id":"492513","messageId":"cover.1712578376.git.ps@pks.im","threadId":"61207","inReplyTo":"cover.1711519925.git.ps@pks.im","subject":"[PATCH v2 00/10] reftable: optimize table and block iterators","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-04-08T12:16:22Z","receivedAt":"2024-04-08T12:16:28Z","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 aims to optimize\nthe reftable table and block iterators.\n\nChanges compared to v1:\n\n    - The series now deepends on ps/reftable-binsearch-update at\n      d51d8cc368 (reftable/block: avoid decoding keys when searching\n      restart points, 2024-04-03). This is to resolve a merge conflict\n      with that other series which has landed in \"next\" already.\n\n    - Rewrote a comment to be single-line to fit into the style of other\n      comments better.\n\n    - A new patch on top that avoids copying block iterators altogether\n      for another speedup.\n\nThanks!\n\nPatrick\n\nPatrick Steinhardt (10):\n  reftable/block: rename `block_reader_start()`\n  reftable/block: merge `block_iter_seek()` and `block_reader_seek()`\n  reftable/block: better grouping of functions\n  reftable/block: introduce `block_reader_release()`\n  reftable/block: move ownership of block reader into `struct\n    table_iter`\n  reftable/reader: iterate to next block in place\n  reftable/block: reuse uncompressed blocks\n  reftable/block: open-code call to `uncompress2()`\n  reftable/block: reuse `zstream` state on inflation\n  reftable/block: avoid copying block iterators on seek\n\n reftable/block.c      | 176 +++++++++++++++++++++++++-----------------\n reftable/block.h      |  47 ++++++-----\n reftable/block_test.c |   6 +-\n reftable/iter.c       |   2 +-\n reftable/reader.c     | 176 ++++++++++++++++++++++--------------------\n 5 files changed, 229 insertions(+), 178 deletions(-)\n\nRange-diff against v1:\n 1:  24b0dda29e =  1:  eb487557a8 reftable/block: rename `block_reader_start()`\n 2:  a2b7f0f559 !  2:  d0b318b8ee reftable/block: merge `block_iter_seek()` and `block_reader_seek()`\n    @@ reftable/block.c: int block_reader_first_key(struct block_reader *br, struct str\n     +int block_iter_seek_key(struct block_iter *it, struct block_reader *br,\n     +\t\t\tstruct strbuf *want)\n      {\n    - \tstruct restart_find_args args = {\n    - \t\t.key = *want,\n    + \tstruct restart_needle_less_args args = {\n    + \t\t.needle = *want,\n     \n      ## reftable/block.h ##\n     @@ reftable/block.h: int block_reader_init(struct block_reader *br, struct reftable_block *bl,\n 3:  88a705b3e2 =  3:  c3f928d1e9 reftable/block: better grouping of functions\n 4:  9a1253649a =  4:  35f1bf5072 reftable/block: introduce `block_reader_release()`\n 5:  f10882a084 !  5:  e8e8bbae62 reftable/block: move ownership of block reader into `struct table_iter`\n    @@ reftable/block.c: int block_reader_first_key(struct block_reader *br, struct str\n      \tit->next_off = br->header_off + 4;\n      }\n     @@ reftable/block.c: void block_iter_seek_start(struct block_iter *it, struct block_reader *br)\n    - struct restart_find_args {\n    + struct restart_needle_less_args {\n      \tint error;\n    - \tstruct strbuf key;\n    --\tstruct block_reader *r;\n    -+\tconst struct block_reader *r;\n    + \tstruct strbuf needle;\n    +-\tstruct block_reader *reader;\n    ++\tconst struct block_reader *reader;\n      };\n      \n    - static int restart_key_less(size_t idx, void *args)\n    -@@ reftable/block.c: static int restart_key_less(size_t idx, void *args)\n    - \treturn result < 0;\n    + static int restart_needle_less(size_t idx, void *_args)\n    +@@ reftable/block.c: static int restart_needle_less(size_t idx, void *_args)\n    + \treturn args->needle.len < suffix_len;\n      }\n      \n     -void block_iter_copy_from(struct block_iter *dest, struct block_iter *src)\n    @@ reftable/block.c: int block_iter_next(struct block_iter *it, struct reftable_rec\n     +int block_iter_seek_key(struct block_iter *it, const struct block_reader *br,\n      \t\t\tstruct strbuf *want)\n      {\n    - \tstruct restart_find_args args = {\n    + \tstruct restart_needle_less_args args = {\n     @@ reftable/block.c: int block_iter_seek_key(struct block_iter *it, struct block_reader *br,\n      \t\tit->next_off = block_reader_restart_offset(br, i - 1);\n      \telse\n    @@ reftable/block.h: struct block_iter {\n      /* return < 0 for error, 0 for OK, > 0 for EOF. */\n      int block_iter_next(struct block_iter *it, struct reftable_record *rec);\n      \n    -+/*\n    -+ * Reset the block iterator to pristine state without releasing its memory.\n    -+ */\n    ++/* Reset the block iterator to pristine state without releasing its memory. */\n     +void block_iter_reset(struct block_iter *it);\n     +\n      /* deallocate memory for `it`. The block reader and its block is left intact. */\n 6:  ae359cb714 =  6:  685f0a40bc reftable/reader: iterate to next block in place\n 7:  1e4eba7e9b =  7:  a7906a3383 reftable/block: reuse uncompressed blocks\n 8:  bf4c1ab797 =  8:  6635c7b986 reftable/block: open-code call to `uncompress2()`\n 9:  43e6538968 =  9:  587b5601c0 reftable/block: reuse `zstream` state on inflation\n -:  ---------- > 10:  cc5ff0d598 reftable/block: avoid copying block iterators on seek\n-- \n2.44.GIT\n\n"},{"id":"492514","messageId":"eb487557a8b5fa26c87101ec297221ddc916f3b5.1712578376.git.ps@pks.im","threadId":"61207","inReplyTo":"cover.1712578376.git.ps@pks.im","subject":"[PATCH v2 01/10] reftable/block: rename `block_reader_start()`","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-04-08T12:16:26Z","receivedAt":"2024-04-08T12:16:31Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"The function `block_reader_start()` does not really apply to the block\nreader, but to the block iterator. It's name is thus somewhat confusing.\nRename it to `block_iter_seek_start()` to clarify.\n\nWe will rename `block_reader_seek()` in similar spirit in the next\ncommit.\n\nSigned-off-by: Patrick Steinhardt <ps@pks.im>\n---\n reftable/block.c      | 2 +-\n reftable/block.h      | 2 +-\n reftable/block_test.c | 2 +-\n reftable/iter.c       | 2 +-\n reftable/reader.c     | 4 ++--\n 5 files changed, 6 insertions(+), 6 deletions(-)\n\ndiff --git a/reftable/block.c b/reftable/block.c\nindex 298e8c56b9..53ea92d04e 100644\n--- a/reftable/block.c\n+++ b/reftable/block.c\n@@ -266,7 +266,7 @@ static uint32_t block_reader_restart_offset(struct block_reader *br, int i)\n \treturn get_be24(br->restart_bytes + 3 * i);\n }\n \n-void block_reader_start(struct block_reader *br, struct block_iter *it)\n+void block_iter_seek_start(struct block_iter *it, struct block_reader *br)\n {\n \tit->br = br;\n \tstrbuf_reset(&it->last_key);\ndiff --git a/reftable/block.h b/reftable/block.h\nindex 47acc62c0a..44a9a8de7d 100644\n--- a/reftable/block.h\n+++ b/reftable/block.h\n@@ -98,7 +98,7 @@ int block_reader_init(struct block_reader *br, struct reftable_block *bl,\n \t\t      int hash_size);\n \n /* Position `it` at start of the block */\n-void block_reader_start(struct block_reader *br, struct block_iter *it);\n+void block_iter_seek_start(struct block_iter *it, struct block_reader *br);\n \n /* Position `it` to the `want` key in the block */\n int block_reader_seek(struct block_reader *br, struct block_iter *it,\ndiff --git a/reftable/block_test.c b/reftable/block_test.c\nindex e162c6e33f..a719be7c50 100644\n--- a/reftable/block_test.c\n+++ b/reftable/block_test.c\n@@ -69,7 +69,7 @@ static void test_block_read_write(void)\n \n \tblock_reader_init(&br, &block, header_off, block_size, GIT_SHA1_RAWSZ);\n \n-\tblock_reader_start(&br, &it);\n+\tblock_iter_seek_start(&it, &br);\n \n \twhile (1) {\n \t\tint r = block_iter_next(&it, &rec);\ndiff --git a/reftable/iter.c b/reftable/iter.c\nindex 7aa30c4a51..aa9ac199b1 100644\n--- a/reftable/iter.c\n+++ b/reftable/iter.c\n@@ -115,7 +115,7 @@ static int indexed_table_ref_iter_next_block(struct indexed_table_ref_iter *it)\n \t\t/* indexed block does not exist. */\n \t\treturn REFTABLE_FORMAT_ERROR;\n \t}\n-\tblock_reader_start(&it->block_reader, &it->cur);\n+\tblock_iter_seek_start(&it->cur, &it->block_reader);\n \treturn 0;\n }\n \ndiff --git a/reftable/reader.c b/reftable/reader.c\nindex b113daab77..d7d47e8640 100644\n--- a/reftable/reader.c\n+++ b/reftable/reader.c\n@@ -345,7 +345,7 @@ static int table_iter_next_block(struct table_iter *dest,\n \t\t*brp = br;\n \n \t\tdest->is_finished = 0;\n-\t\tblock_reader_start(brp, &dest->bi);\n+\t\tblock_iter_seek_start(&dest->bi, brp);\n \t}\n \treturn 0;\n }\n@@ -429,7 +429,7 @@ static int reader_table_iter_at(struct reftable_reader *r,\n \tti->r = r;\n \tti->typ = block_reader_type(brp);\n \tti->block_off = off;\n-\tblock_reader_start(brp, &ti->bi);\n+\tblock_iter_seek_start(&ti->bi, brp);\n \treturn 0;\n }\n \n-- \n2.44.GIT\n\n"},{"id":"492515","messageId":"d0b318b8ee33b6c8c749dcb5781b9dd37f00ed44.1712578376.git.ps@pks.im","threadId":"61207","inReplyTo":"cover.1712578376.git.ps@pks.im","subject":"[PATCH v2 02/10] reftable/block: merge `block_iter_seek()` and `block_reader_seek()`","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-04-08T12:16:31Z","receivedAt":"2024-04-08T12:16:35Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"The function `block_iter_seek()` is merely a simple wrapper around\n`block_reader_seek()`. Merge those two functions into a new function\n`block_iter_seek_key()` that more clearly says what it is actually\ndoing.\n\nSigned-off-by: Patrick Steinhardt <ps@pks.im>\n---\n reftable/block.c      | 9 ++-------\n reftable/block.h      | 7 ++-----\n reftable/block_test.c | 4 ++--\n reftable/reader.c     | 4 ++--\n 4 files changed, 8 insertions(+), 16 deletions(-)\n\ndiff --git a/reftable/block.c b/reftable/block.c\nindex 53ea92d04e..1015f9c04c 100644\n--- a/reftable/block.c\n+++ b/reftable/block.c\n@@ -373,19 +373,14 @@ int block_reader_first_key(struct block_reader *br, struct strbuf *key)\n \treturn 0;\n }\n \n-int block_iter_seek(struct block_iter *it, struct strbuf *want)\n-{\n-\treturn block_reader_seek(it->br, it, want);\n-}\n-\n void block_iter_close(struct block_iter *it)\n {\n \tstrbuf_release(&it->last_key);\n \tstrbuf_release(&it->scratch);\n }\n \n-int block_reader_seek(struct block_reader *br, struct block_iter *it,\n-\t\t      struct strbuf *want)\n+int block_iter_seek_key(struct block_iter *it, struct block_reader *br,\n+\t\t\tstruct strbuf *want)\n {\n \tstruct restart_needle_less_args args = {\n \t\t.needle = *want,\ndiff --git a/reftable/block.h b/reftable/block.h\nindex 44a9a8de7d..1734bee917 100644\n--- a/reftable/block.h\n+++ b/reftable/block.h\n@@ -101,8 +101,8 @@ int block_reader_init(struct block_reader *br, struct reftable_block *bl,\n void block_iter_seek_start(struct block_iter *it, struct block_reader *br);\n \n /* Position `it` to the `want` key in the block */\n-int block_reader_seek(struct block_reader *br, struct block_iter *it,\n-\t\t      struct strbuf *want);\n+int block_iter_seek_key(struct block_iter *it, struct block_reader *br,\n+\t\t\tstruct strbuf *want);\n \n /* Returns the block type (eg. 'r' for refs) */\n uint8_t block_reader_type(struct block_reader *r);\n@@ -115,9 +115,6 @@ void block_iter_copy_from(struct block_iter *dest, struct block_iter *src);\n /* return < 0 for error, 0 for OK, > 0 for EOF. */\n int block_iter_next(struct block_iter *it, struct reftable_record *rec);\n \n-/* Seek to `want` with in the block pointed to by `it` */\n-int block_iter_seek(struct block_iter *it, struct strbuf *want);\n-\n /* deallocate memory for `it`. The block reader and its block is left intact. */\n void block_iter_close(struct block_iter *it);\n \ndiff --git a/reftable/block_test.c b/reftable/block_test.c\nindex a719be7c50..26a9cfbc83 100644\n--- a/reftable/block_test.c\n+++ b/reftable/block_test.c\n@@ -89,7 +89,7 @@ static void test_block_read_write(void)\n \t\tstrbuf_reset(&want);\n \t\tstrbuf_addstr(&want, names[i]);\n \n-\t\tn = block_reader_seek(&br, &it, &want);\n+\t\tn = block_iter_seek_key(&it, &br, &want);\n \t\tEXPECT(n == 0);\n \n \t\tn = block_iter_next(&it, &rec);\n@@ -98,7 +98,7 @@ static void test_block_read_write(void)\n \t\tEXPECT_STREQ(names[i], rec.u.ref.refname);\n \n \t\twant.len--;\n-\t\tn = block_reader_seek(&br, &it, &want);\n+\t\tn = block_iter_seek_key(&it, &br, &want);\n \t\tEXPECT(n == 0);\n \n \t\tn = block_iter_next(&it, &rec);\ndiff --git a/reftable/reader.c b/reftable/reader.c\nindex d7d47e8640..f70efa2b7c 100644\n--- a/reftable/reader.c\n+++ b/reftable/reader.c\n@@ -483,7 +483,7 @@ static int reader_seek_linear(struct table_iter *ti,\n \t\ttable_iter_copy_from(ti, &next);\n \t}\n \n-\terr = block_iter_seek(&ti->bi, &want_key);\n+\terr = block_iter_seek_key(&ti->bi, ti->bi.br, &want_key);\n \tif (err < 0)\n \t\tgoto done;\n \terr = 0;\n@@ -558,7 +558,7 @@ static int reader_seek_indexed(struct reftable_reader *r,\n \t\tif (err != 0)\n \t\t\tgoto done;\n \n-\t\terr = block_iter_seek(&next.bi, &want_index.u.idx.last_key);\n+\t\terr = block_iter_seek_key(&next.bi, next.bi.br, &want_index.u.idx.last_key);\n \t\tif (err < 0)\n \t\t\tgoto done;\n \n-- \n2.44.GIT\n\n"},{"id":"492516","messageId":"c3f928d1e97375974f14fd3e96e0c4edffde9af9.1712578376.git.ps@pks.im","threadId":"61207","inReplyTo":"cover.1712578376.git.ps@pks.im","subject":"[PATCH v2 03/10] reftable/block: better grouping of functions","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-04-08T12:16:36Z","receivedAt":"2024-04-08T12:16:43Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"Function definitions and declaration of `struct block_reader` and\n`struct block_iter` are somewhat mixed up, making it hard to see which\nfunctions belong together. Rearrange them.\n\nSigned-off-by: Patrick Steinhardt <ps@pks.im>\n---\n reftable/block.c | 50 ++++++++++++++++++++++++------------------------\n reftable/block.h | 22 ++++++++++-----------\n 2 files changed, 36 insertions(+), 36 deletions(-)\n\ndiff --git a/reftable/block.c b/reftable/block.c\nindex 1015f9c04c..e65453e11b 100644\n--- a/reftable/block.c\n+++ b/reftable/block.c\n@@ -175,11 +175,6 @@ int block_writer_finish(struct block_writer *w)\n \treturn w->next;\n }\n \n-uint8_t block_reader_type(struct block_reader *r)\n-{\n-\treturn r->block.data[r->header_off];\n-}\n-\n int block_reader_init(struct block_reader *br, struct reftable_block *block,\n \t\t      uint32_t header_off, uint32_t table_block_size,\n \t\t      int hash_size)\n@@ -261,6 +256,31 @@ int block_reader_init(struct block_reader *br, struct reftable_block *block,\n \treturn err;\n }\n \n+uint8_t block_reader_type(struct block_reader *r)\n+{\n+\treturn r->block.data[r->header_off];\n+}\n+\n+int block_reader_first_key(struct block_reader *br, struct strbuf *key)\n+{\n+\tint off = br->header_off + 4, n;\n+\tstruct string_view in = {\n+\t\t.buf = br->block.data + off,\n+\t\t.len = br->block_len - off,\n+\t};\n+\tuint8_t extra = 0;\n+\n+\tstrbuf_reset(key);\n+\n+\tn = reftable_decode_key(key, &extra, in);\n+\tif (n < 0)\n+\t\treturn n;\n+\tif (!key->len)\n+\t\treturn REFTABLE_FORMAT_ERROR;\n+\n+\treturn 0;\n+}\n+\n static uint32_t block_reader_restart_offset(struct block_reader *br, int i)\n {\n \treturn get_be24(br->restart_bytes + 3 * i);\n@@ -353,26 +373,6 @@ int block_iter_next(struct block_iter *it, struct reftable_record *rec)\n \treturn 0;\n }\n \n-int block_reader_first_key(struct block_reader *br, struct strbuf *key)\n-{\n-\tint off = br->header_off + 4, n;\n-\tstruct string_view in = {\n-\t\t.buf = br->block.data + off,\n-\t\t.len = br->block_len - off,\n-\t};\n-\tuint8_t extra = 0;\n-\n-\tstrbuf_reset(key);\n-\n-\tn = reftable_decode_key(key, &extra, in);\n-\tif (n < 0)\n-\t\treturn n;\n-\tif (!key->len)\n-\t\treturn REFTABLE_FORMAT_ERROR;\n-\n-\treturn 0;\n-}\n-\n void block_iter_close(struct block_iter *it)\n {\n \tstrbuf_release(&it->last_key);\ndiff --git a/reftable/block.h b/reftable/block.h\nindex 1734bee917..d73ed73549 100644\n--- a/reftable/block.h\n+++ b/reftable/block.h\n@@ -76,6 +76,17 @@ struct block_reader {\n \tuint32_t full_block_size;\n };\n \n+/* initializes a block reader. */\n+int block_reader_init(struct block_reader *br, struct reftable_block *bl,\n+\t\t      uint32_t header_off, uint32_t table_block_size,\n+\t\t      int hash_size);\n+\n+/* Returns the block type (eg. 'r' for refs) */\n+uint8_t block_reader_type(struct block_reader *r);\n+\n+/* Decodes the first key in the block */\n+int block_reader_first_key(struct block_reader *br, struct strbuf *key);\n+\n /* Iterate over entries in a block */\n struct block_iter {\n \t/* offset within the block of the next entry to read. */\n@@ -92,11 +103,6 @@ struct block_iter {\n \t.scratch = STRBUF_INIT, \\\n }\n \n-/* initializes a block reader. */\n-int block_reader_init(struct block_reader *br, struct reftable_block *bl,\n-\t\t      uint32_t header_off, uint32_t table_block_size,\n-\t\t      int hash_size);\n-\n /* Position `it` at start of the block */\n void block_iter_seek_start(struct block_iter *it, struct block_reader *br);\n \n@@ -104,12 +110,6 @@ void block_iter_seek_start(struct block_iter *it, struct block_reader *br);\n int block_iter_seek_key(struct block_iter *it, struct block_reader *br,\n \t\t\tstruct strbuf *want);\n \n-/* Returns the block type (eg. 'r' for refs) */\n-uint8_t block_reader_type(struct block_reader *r);\n-\n-/* Decodes the first key in the block */\n-int block_reader_first_key(struct block_reader *br, struct strbuf *key);\n-\n void block_iter_copy_from(struct block_iter *dest, struct block_iter *src);\n \n /* return < 0 for error, 0 for OK, > 0 for EOF. */\n-- \n2.44.GIT\n\n"},{"id":"492517","messageId":"35f1bf50729efcee7b9162ffe79d40142418c0cf.1712578376.git.ps@pks.im","threadId":"61207","inReplyTo":"cover.1712578376.git.ps@pks.im","subject":"[PATCH v2 04/10] reftable/block: introduce `block_reader_release()`","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-04-08T12:16:40Z","receivedAt":"2024-04-08T12:16:46Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"Introduce a new function `block_reader_release()` that releases\nresources acquired by the block reader. This function will be extended\nin a subsequent commit.\n\nSigned-off-by: Patrick Steinhardt <ps@pks.im>\n---\n reftable/block.c  | 5 +++++\n reftable/block.h  | 2 ++\n reftable/reader.c | 2 +-\n 3 files changed, 8 insertions(+), 1 deletion(-)\n\ndiff --git a/reftable/block.c b/reftable/block.c\nindex e65453e11b..fe836c21e5 100644\n--- a/reftable/block.c\n+++ b/reftable/block.c\n@@ -256,6 +256,11 @@ int block_reader_init(struct block_reader *br, struct reftable_block *block,\n \treturn err;\n }\n \n+void block_reader_release(struct block_reader *br)\n+{\n+\treftable_block_done(&br->block);\n+}\n+\n uint8_t block_reader_type(struct block_reader *r)\n {\n \treturn r->block.data[r->header_off];\ndiff --git a/reftable/block.h b/reftable/block.h\nindex d73ed73549..601a1e0e89 100644\n--- a/reftable/block.h\n+++ b/reftable/block.h\n@@ -81,6 +81,8 @@ int block_reader_init(struct block_reader *br, struct reftable_block *bl,\n \t\t      uint32_t header_off, uint32_t table_block_size,\n \t\t      int hash_size);\n \n+void block_reader_release(struct block_reader *br);\n+\n /* Returns the block type (eg. 'r' for refs) */\n uint8_t block_reader_type(struct block_reader *r);\n \ndiff --git a/reftable/reader.c b/reftable/reader.c\nindex f70efa2b7c..f925570bf3 100644\n--- a/reftable/reader.c\n+++ b/reftable/reader.c\n@@ -253,7 +253,7 @@ static void table_iter_block_done(struct table_iter *ti)\n \tif (!ti->bi.br) {\n \t\treturn;\n \t}\n-\treftable_block_done(&ti->bi.br->block);\n+\tblock_reader_release(ti->bi.br);\n \tFREE_AND_NULL(ti->bi.br);\n \n \tti->bi.last_key.len = 0;\n-- \n2.44.GIT\n\n"},{"id":"492518","messageId":"e8e8bbae62bf3481396efed7e6a0d4c592d845bc.1712578376.git.ps@pks.im","threadId":"61207","inReplyTo":"cover.1712578376.git.ps@pks.im","subject":"[PATCH v2 05/10] reftable/block: move ownership of block reader into `struct table_iter`","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-04-08T12:16:45Z","receivedAt":"2024-04-08T12:16:50Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"The table iterator allows the caller to iterate through all records in a\nreftable table. To do so it iterates through all blocks of the desired\ntype one by one, where for each block it creates a new block iterator\nand yields all its entries.\n\nOne of the things that is somewhat confusing in this context is who owns\nthe block reader that is being used to read the blocks and pass them to\nthe block iterator. Intuitively, as the table iterator is responsible\nfor iterating through the blocks, one would assume that this iterator is\nalso responsible for managing the lifecycle of the reader. And while it\nsomewhat is, the block reader is ultimately stored inside of the block\niterator.\n\nRefactor the code such that the block reader is instead fully managed by\nthe table iterator. Instead of passing the reader to the block iterator,\nwe now only end up passing the block data to it. Despite clearing up the\nlifecycle of the reader, it will also allow for better reuse of the\nreader in subsequent patches.\n\nThe following benchmark prints a single matching ref out of 1 million\nrefs. Before:\n\n  HEAP SUMMARY:\n      in use at exit: 13,603 bytes in 125 blocks\n    total heap usage: 6,607 allocs, 6,482 frees, 509,635 bytes allocated\n\nAfter:\n\n  HEAP SUMMARY:\n      in use at exit: 13,603 bytes in 125 blocks\n    total heap usage: 7,235 allocs, 7,110 frees, 301,481 bytes allocated\n\nNote that while there are more allocation and free calls now, the\noverall number of bytes allocated is significantly lower. The number of\nallocations will be reduced significantly by the next patch though.\n\nSigned-off-by: Patrick Steinhardt <ps@pks.im>\n---\n reftable/block.c  |  43 ++++++++++------\n reftable/block.h  |  17 ++++---\n reftable/reader.c | 123 ++++++++++++++++++++++------------------------\n 3 files changed, 100 insertions(+), 83 deletions(-)\n\ndiff --git a/reftable/block.c b/reftable/block.c\nindex fe836c21e5..2d8d0668b3 100644\n--- a/reftable/block.c\n+++ b/reftable/block.c\n@@ -261,12 +261,12 @@ void block_reader_release(struct block_reader *br)\n \treftable_block_done(&br->block);\n }\n \n-uint8_t block_reader_type(struct block_reader *r)\n+uint8_t block_reader_type(const struct block_reader *r)\n {\n \treturn r->block.data[r->header_off];\n }\n \n-int block_reader_first_key(struct block_reader *br, struct strbuf *key)\n+int block_reader_first_key(const struct block_reader *br, struct strbuf *key)\n {\n \tint off = br->header_off + 4, n;\n \tstruct string_view in = {\n@@ -286,14 +286,16 @@ int block_reader_first_key(struct block_reader *br, struct strbuf *key)\n \treturn 0;\n }\n \n-static uint32_t block_reader_restart_offset(struct block_reader *br, int i)\n+static uint32_t block_reader_restart_offset(const struct block_reader *br, int i)\n {\n \treturn get_be24(br->restart_bytes + 3 * i);\n }\n \n-void block_iter_seek_start(struct block_iter *it, struct block_reader *br)\n+void block_iter_seek_start(struct block_iter *it, const struct block_reader *br)\n {\n-\tit->br = br;\n+\tit->block = br->block.data;\n+\tit->block_len = br->block_len;\n+\tit->hash_size = br->hash_size;\n \tstrbuf_reset(&it->last_key);\n \tit->next_off = br->header_off + 4;\n }\n@@ -301,7 +303,7 @@ void block_iter_seek_start(struct block_iter *it, struct block_reader *br)\n struct restart_needle_less_args {\n \tint error;\n \tstruct strbuf needle;\n-\tstruct block_reader *reader;\n+\tconst struct block_reader *reader;\n };\n \n static int restart_needle_less(size_t idx, void *_args)\n@@ -340,9 +342,11 @@ static int restart_needle_less(size_t idx, void *_args)\n \treturn args->needle.len < suffix_len;\n }\n \n-void block_iter_copy_from(struct block_iter *dest, struct block_iter *src)\n+void block_iter_copy_from(struct block_iter *dest, const struct block_iter *src)\n {\n-\tdest->br = src->br;\n+\tdest->block = src->block;\n+\tdest->block_len = src->block_len;\n+\tdest->hash_size = src->hash_size;\n \tdest->next_off = src->next_off;\n \tstrbuf_reset(&dest->last_key);\n \tstrbuf_addbuf(&dest->last_key, &src->last_key);\n@@ -351,14 +355,14 @@ void block_iter_copy_from(struct block_iter *dest, struct block_iter *src)\n int block_iter_next(struct block_iter *it, struct reftable_record *rec)\n {\n \tstruct string_view in = {\n-\t\t.buf = it->br->block.data + it->next_off,\n-\t\t.len = it->br->block_len - it->next_off,\n+\t\t.buf = (unsigned char *) it->block + it->next_off,\n+\t\t.len = it->block_len - it->next_off,\n \t};\n \tstruct string_view start = in;\n \tuint8_t extra = 0;\n \tint n = 0;\n \n-\tif (it->next_off >= it->br->block_len)\n+\tif (it->next_off >= it->block_len)\n \t\treturn 1;\n \n \tn = reftable_decode_key(&it->last_key, &extra, in);\n@@ -368,7 +372,7 @@ int block_iter_next(struct block_iter *it, struct reftable_record *rec)\n \t\treturn REFTABLE_FORMAT_ERROR;\n \n \tstring_view_consume(&in, n);\n-\tn = reftable_record_decode(rec, it->last_key, extra, in, it->br->hash_size,\n+\tn = reftable_record_decode(rec, it->last_key, extra, in, it->hash_size,\n \t\t\t\t   &it->scratch);\n \tif (n < 0)\n \t\treturn -1;\n@@ -378,13 +382,22 @@ int block_iter_next(struct block_iter *it, struct reftable_record *rec)\n \treturn 0;\n }\n \n+void block_iter_reset(struct block_iter *it)\n+{\n+\tstrbuf_reset(&it->last_key);\n+\tit->next_off = 0;\n+\tit->block = NULL;\n+\tit->block_len = 0;\n+\tit->hash_size = 0;\n+}\n+\n void block_iter_close(struct block_iter *it)\n {\n \tstrbuf_release(&it->last_key);\n \tstrbuf_release(&it->scratch);\n }\n \n-int block_iter_seek_key(struct block_iter *it, struct block_reader *br,\n+int block_iter_seek_key(struct block_iter *it, const struct block_reader *br,\n \t\t\tstruct strbuf *want)\n {\n \tstruct restart_needle_less_args args = {\n@@ -436,7 +449,9 @@ int block_iter_seek_key(struct block_iter *it, struct block_reader *br,\n \t\tit->next_off = block_reader_restart_offset(br, i - 1);\n \telse\n \t\tit->next_off = br->header_off + 4;\n-\tit->br = br;\n+\tit->block = br->block.data;\n+\tit->block_len = br->block_len;\n+\tit->hash_size = br->hash_size;\n \n \treftable_record_init(&rec, block_reader_type(br));\n \ndiff --git a/reftable/block.h b/reftable/block.h\nindex 601a1e0e89..d733d45ee0 100644\n--- a/reftable/block.h\n+++ b/reftable/block.h\n@@ -84,16 +84,18 @@ int block_reader_init(struct block_reader *br, struct reftable_block *bl,\n void block_reader_release(struct block_reader *br);\n \n /* Returns the block type (eg. 'r' for refs) */\n-uint8_t block_reader_type(struct block_reader *r);\n+uint8_t block_reader_type(const struct block_reader *r);\n \n /* Decodes the first key in the block */\n-int block_reader_first_key(struct block_reader *br, struct strbuf *key);\n+int block_reader_first_key(const struct block_reader *br, struct strbuf *key);\n \n /* Iterate over entries in a block */\n struct block_iter {\n \t/* offset within the block of the next entry to read. */\n \tuint32_t next_off;\n-\tstruct block_reader *br;\n+\tconst unsigned char *block;\n+\tsize_t block_len;\n+\tint hash_size;\n \n \t/* key for last entry we read. */\n \tstruct strbuf last_key;\n@@ -106,17 +108,20 @@ struct block_iter {\n }\n \n /* Position `it` at start of the block */\n-void block_iter_seek_start(struct block_iter *it, struct block_reader *br);\n+void block_iter_seek_start(struct block_iter *it, const struct block_reader *br);\n \n /* Position `it` to the `want` key in the block */\n-int block_iter_seek_key(struct block_iter *it, struct block_reader *br,\n+int block_iter_seek_key(struct block_iter *it, const struct block_reader *br,\n \t\t\tstruct strbuf *want);\n \n-void block_iter_copy_from(struct block_iter *dest, struct block_iter *src);\n+void block_iter_copy_from(struct block_iter *dest, const struct block_iter *src);\n \n /* return < 0 for error, 0 for OK, > 0 for EOF. */\n int block_iter_next(struct block_iter *it, struct reftable_record *rec);\n \n+/* Reset the block iterator to pristine state without releasing its memory. */\n+void block_iter_reset(struct block_iter *it);\n+\n /* deallocate memory for `it`. The block reader and its block is left intact. */\n void block_iter_close(struct block_iter *it);\n \ndiff --git a/reftable/reader.c b/reftable/reader.c\nindex f925570bf3..b77b639751 100644\n--- a/reftable/reader.c\n+++ b/reftable/reader.c\n@@ -220,6 +220,7 @@ struct table_iter {\n \tstruct reftable_reader *r;\n \tuint8_t typ;\n \tuint64_t block_off;\n+\tstruct block_reader br;\n \tstruct block_iter bi;\n \tint is_finished;\n };\n@@ -227,16 +228,6 @@ struct table_iter {\n \t.bi = BLOCK_ITER_INIT \\\n }\n \n-static void table_iter_copy_from(struct table_iter *dest,\n-\t\t\t\t struct table_iter *src)\n-{\n-\tdest->r = src->r;\n-\tdest->typ = src->typ;\n-\tdest->block_off = src->block_off;\n-\tdest->is_finished = src->is_finished;\n-\tblock_iter_copy_from(&dest->bi, &src->bi);\n-}\n-\n static int table_iter_next_in_block(struct table_iter *ti,\n \t\t\t\t    struct reftable_record *rec)\n {\n@@ -250,14 +241,8 @@ static int table_iter_next_in_block(struct table_iter *ti,\n \n static void table_iter_block_done(struct table_iter *ti)\n {\n-\tif (!ti->bi.br) {\n-\t\treturn;\n-\t}\n-\tblock_reader_release(ti->bi.br);\n-\tFREE_AND_NULL(ti->bi.br);\n-\n-\tti->bi.last_key.len = 0;\n-\tti->bi.next_off = 0;\n+\tblock_reader_release(&ti->br);\n+\tblock_iter_reset(&ti->bi);\n }\n \n static int32_t extract_block_size(uint8_t *data, uint8_t *typ, uint64_t off,\n@@ -321,32 +306,33 @@ int reader_init_block_reader(struct reftable_reader *r, struct block_reader *br,\n \treturn err;\n }\n \n+static void table_iter_close(struct table_iter *ti)\n+{\n+\ttable_iter_block_done(ti);\n+\tblock_iter_close(&ti->bi);\n+}\n+\n static int table_iter_next_block(struct table_iter *dest,\n \t\t\t\t struct table_iter *src)\n {\n-\tuint64_t next_block_off = src->block_off + src->bi.br->full_block_size;\n-\tstruct block_reader br = { 0 };\n-\tint err = 0;\n+\tuint64_t next_block_off = src->block_off + src->br.full_block_size;\n+\tint err;\n \n \tdest->r = src->r;\n \tdest->typ = src->typ;\n \tdest->block_off = next_block_off;\n \n-\terr = reader_init_block_reader(src->r, &br, next_block_off, src->typ);\n-\tif (err > 0) {\n+\terr = reader_init_block_reader(src->r, &dest->br, next_block_off, src->typ);\n+\tif (err > 0)\n \t\tdest->is_finished = 1;\n-\t\treturn 1;\n-\t}\n-\tif (err != 0)\n+\tif (err) {\n+\t\ttable_iter_block_done(dest);\n \t\treturn err;\n-\telse {\n-\t\tstruct block_reader *brp =\n-\t\t\treftable_malloc(sizeof(struct block_reader));\n-\t\t*brp = br;\n-\n-\t\tdest->is_finished = 0;\n-\t\tblock_iter_seek_start(&dest->bi, brp);\n \t}\n+\n+\tdest->is_finished = 0;\n+\tblock_iter_seek_start(&dest->bi, &dest->br);\n+\n \treturn 0;\n }\n \n@@ -377,14 +363,13 @@ static int table_iter_next(struct table_iter *ti, struct reftable_record *rec)\n \t\t * iterator is drained.\n \t\t */\n \t\terr = table_iter_next_block(&next, ti);\n-\t\ttable_iter_block_done(ti);\n \t\tif (err) {\n \t\t\tti->is_finished = 1;\n \t\t\treturn err;\n \t\t}\n \n-\t\ttable_iter_copy_from(ti, &next);\n-\t\tblock_iter_close(&next.bi);\n+\t\ttable_iter_close(ti);\n+\t\t*ti = next;\n \t}\n }\n \n@@ -393,16 +378,14 @@ static int table_iter_next_void(void *ti, struct reftable_record *rec)\n \treturn table_iter_next(ti, rec);\n }\n \n-static void table_iter_close(void *p)\n+static void table_iter_close_void(void *ti)\n {\n-\tstruct table_iter *ti = p;\n-\ttable_iter_block_done(ti);\n-\tblock_iter_close(&ti->bi);\n+\ttable_iter_close(ti);\n }\n \n static struct reftable_iterator_vtable table_iter_vtable = {\n \t.next = &table_iter_next_void,\n-\t.close = &table_iter_close,\n+\t.close = &table_iter_close_void,\n };\n \n static void iterator_from_table_iter(struct reftable_iterator *it,\n@@ -417,19 +400,16 @@ static int reader_table_iter_at(struct reftable_reader *r,\n \t\t\t\tstruct table_iter *ti, uint64_t off,\n \t\t\t\tuint8_t typ)\n {\n-\tstruct block_reader br = { 0 };\n-\tstruct block_reader *brp = NULL;\n+\tint err;\n \n-\tint err = reader_init_block_reader(r, &br, off, typ);\n+\terr = reader_init_block_reader(r, &ti->br, off, typ);\n \tif (err != 0)\n \t\treturn err;\n \n-\tbrp = reftable_malloc(sizeof(struct block_reader));\n-\t*brp = br;\n \tti->r = r;\n-\tti->typ = block_reader_type(brp);\n+\tti->typ = block_reader_type(&ti->br);\n \tti->block_off = off;\n-\tblock_iter_seek_start(&ti->bi, brp);\n+\tblock_iter_seek_start(&ti->bi, &ti->br);\n \treturn 0;\n }\n \n@@ -454,23 +434,34 @@ static int reader_seek_linear(struct table_iter *ti,\n {\n \tstruct strbuf want_key = STRBUF_INIT;\n \tstruct strbuf got_key = STRBUF_INIT;\n-\tstruct table_iter next = TABLE_ITER_INIT;\n \tstruct reftable_record rec;\n \tint err = -1;\n \n \treftable_record_init(&rec, reftable_record_type(want));\n \treftable_record_key(want, &want_key);\n \n+\t/*\n+\t * First we need to locate the block that must contain our record. To\n+\t * do so we scan through blocks linearly until we find the first block\n+\t * whose first key is bigger than our wanted key. Once we have found\n+\t * that block we know that the key must be contained in the preceding\n+\t * block.\n+\t *\n+\t * This algorithm is somewhat unfortunate because it means that we\n+\t * always have to seek one block too far and then back up. But as we\n+\t * can only decode the _first_ key of a block but not its _last_ key we\n+\t * have no other way to do this.\n+\t */\n \twhile (1) {\n+\t\tstruct table_iter next = TABLE_ITER_INIT;\n+\n \t\terr = table_iter_next_block(&next, ti);\n \t\tif (err < 0)\n \t\t\tgoto done;\n-\n-\t\tif (err > 0) {\n+\t\tif (err > 0)\n \t\t\tbreak;\n-\t\t}\n \n-\t\terr = block_reader_first_key(next.bi.br, &got_key);\n+\t\terr = block_reader_first_key(&next.br, &got_key);\n \t\tif (err < 0)\n \t\t\tgoto done;\n \n@@ -480,16 +471,20 @@ static int reader_seek_linear(struct table_iter *ti,\n \t\t}\n \n \t\ttable_iter_block_done(ti);\n-\t\ttable_iter_copy_from(ti, &next);\n+\t\t*ti = next;\n \t}\n \n-\terr = block_iter_seek_key(&ti->bi, ti->bi.br, &want_key);\n+\t/*\n+\t * We have located the block that must contain our record, so we seek\n+\t * the wanted key inside of it. If the block does not contain our key\n+\t * we know that the corresponding record does not exist.\n+\t */\n+\terr = block_iter_seek_key(&ti->bi, &ti->br, &want_key);\n \tif (err < 0)\n \t\tgoto done;\n \terr = 0;\n \n done:\n-\tblock_iter_close(&next.bi);\n \treftable_record_release(&rec);\n \tstrbuf_release(&want_key);\n \tstrbuf_release(&got_key);\n@@ -508,6 +503,7 @@ static int reader_seek_indexed(struct reftable_reader *r,\n \t\t.u.idx = { .last_key = STRBUF_INIT },\n \t};\n \tstruct table_iter index_iter = TABLE_ITER_INIT;\n+\tstruct table_iter empty = TABLE_ITER_INIT;\n \tstruct table_iter next = TABLE_ITER_INIT;\n \tint err = 0;\n \n@@ -549,7 +545,6 @@ static int reader_seek_indexed(struct reftable_reader *r,\n \t\t * not exist.\n \t\t */\n \t\terr = table_iter_next(&index_iter, &index_result);\n-\t\ttable_iter_block_done(&index_iter);\n \t\tif (err != 0)\n \t\t\tgoto done;\n \n@@ -558,7 +553,7 @@ static int reader_seek_indexed(struct reftable_reader *r,\n \t\tif (err != 0)\n \t\t\tgoto done;\n \n-\t\terr = block_iter_seek_key(&next.bi, next.bi.br, &want_index.u.idx.last_key);\n+\t\terr = block_iter_seek_key(&next.bi, &next.br, &want_index.u.idx.last_key);\n \t\tif (err < 0)\n \t\t\tgoto done;\n \n@@ -572,18 +567,20 @@ static int reader_seek_indexed(struct reftable_reader *r,\n \t\t\tbreak;\n \t\t}\n \n-\t\ttable_iter_copy_from(&index_iter, &next);\n+\t\ttable_iter_close(&index_iter);\n+\t\tindex_iter = next;\n+\t\tnext = empty;\n \t}\n \n \tif (err == 0) {\n-\t\tstruct table_iter empty = TABLE_ITER_INIT;\n \t\tstruct table_iter *malloced = reftable_calloc(1, sizeof(*malloced));\n-\t\t*malloced = empty;\n-\t\ttable_iter_copy_from(malloced, &next);\n+\t\t*malloced = next;\n+\t\tnext = empty;\n \t\titerator_from_table_iter(it, malloced);\n \t}\n+\n done:\n-\tblock_iter_close(&next.bi);\n+\ttable_iter_close(&next);\n \ttable_iter_close(&index_iter);\n \treftable_record_release(&want_index);\n \treftable_record_release(&index_result);\n-- \n2.44.GIT\n\n"},{"id":"492519","messageId":"685f0a40bc5ac6a8c3eaab78bac2050c0cad8de4.1712578376.git.ps@pks.im","threadId":"61207","inReplyTo":"cover.1712578376.git.ps@pks.im","subject":"[PATCH v2 06/10] reftable/reader: iterate to next block in place","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-04-08T12:16:50Z","receivedAt":"2024-04-08T12:16:59Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"The table iterator has to iterate towards the next block once it has\nyielded all records of the current block. This is done by creating a new\ntable iterator, initializing it to the next block, releasing the old\niterator and then copying over the data.\n\nRefactor the code to instead advance the table iterator in place. This\nis simpler and unlocks some optimizations in subsequent patches. Also,\nit allows us to avoid some allocations.\n\nThe following measurements show a single matching ref out of 1 million\nrefs. Before this change:\n\n  HEAP SUMMARY:\n      in use at exit: 13,603 bytes in 125 blocks\n    total heap usage: 7,235 allocs, 7,110 frees, 301,481 bytes allocated\n\nAfter:\n\n  HEAP SUMMARY:\n      in use at exit: 13,603 bytes in 125 blocks\n    total heap usage: 315 allocs, 190 frees, 107,027 bytes allocated\n\nSigned-off-by: Patrick Steinhardt <ps@pks.im>\n---\n reftable/block.c  |  2 ++\n reftable/reader.c | 47 ++++++++++++++++++++++++++---------------------\n 2 files changed, 28 insertions(+), 21 deletions(-)\n\ndiff --git a/reftable/block.c b/reftable/block.c\nindex 2d8d0668b3..0c4e71eae3 100644\n--- a/reftable/block.c\n+++ b/reftable/block.c\n@@ -188,6 +188,8 @@ int block_reader_init(struct block_reader *br, struct reftable_block *block,\n \tuint8_t *restart_bytes = NULL;\n \tuint8_t *uncompressed = NULL;\n \n+\treftable_block_done(&br->block);\n+\n \tif (!reftable_is_block_type(typ)) {\n \t\terr =  REFTABLE_FORMAT_ERROR;\n \t\tgoto done;\ndiff --git a/reftable/reader.c b/reftable/reader.c\nindex b77b639751..dd4de294a1 100644\n--- a/reftable/reader.c\n+++ b/reftable/reader.c\n@@ -312,26 +312,20 @@ static void table_iter_close(struct table_iter *ti)\n \tblock_iter_close(&ti->bi);\n }\n \n-static int table_iter_next_block(struct table_iter *dest,\n-\t\t\t\t struct table_iter *src)\n+static int table_iter_next_block(struct table_iter *ti)\n {\n-\tuint64_t next_block_off = src->block_off + src->br.full_block_size;\n+\tuint64_t next_block_off = ti->block_off + ti->br.full_block_size;\n \tint err;\n \n-\tdest->r = src->r;\n-\tdest->typ = src->typ;\n-\tdest->block_off = next_block_off;\n-\n-\terr = reader_init_block_reader(src->r, &dest->br, next_block_off, src->typ);\n+\terr = reader_init_block_reader(ti->r, &ti->br, next_block_off, ti->typ);\n \tif (err > 0)\n-\t\tdest->is_finished = 1;\n-\tif (err) {\n-\t\ttable_iter_block_done(dest);\n+\t\tti->is_finished = 1;\n+\tif (err)\n \t\treturn err;\n-\t}\n \n-\tdest->is_finished = 0;\n-\tblock_iter_seek_start(&dest->bi, &dest->br);\n+\tti->block_off = next_block_off;\n+\tti->is_finished = 0;\n+\tblock_iter_seek_start(&ti->bi, &ti->br);\n \n \treturn 0;\n }\n@@ -342,7 +336,6 @@ static int table_iter_next(struct table_iter *ti, struct reftable_record *rec)\n \t\treturn REFTABLE_API_ERROR;\n \n \twhile (1) {\n-\t\tstruct table_iter next = TABLE_ITER_INIT;\n \t\tint err;\n \n \t\tif (ti->is_finished)\n@@ -362,14 +355,11 @@ static int table_iter_next(struct table_iter *ti, struct reftable_record *rec)\n \t\t * table and retry. If there are no more blocks then the\n \t\t * iterator is drained.\n \t\t */\n-\t\terr = table_iter_next_block(&next, ti);\n+\t\terr = table_iter_next_block(ti);\n \t\tif (err) {\n \t\t\tti->is_finished = 1;\n \t\t\treturn err;\n \t\t}\n-\n-\t\ttable_iter_close(ti);\n-\t\t*ti = next;\n \t}\n }\n \n@@ -453,9 +443,24 @@ static int reader_seek_linear(struct table_iter *ti,\n \t * have no other way to do this.\n \t */\n \twhile (1) {\n-\t\tstruct table_iter next = TABLE_ITER_INIT;\n+\t\tstruct table_iter next = *ti;\n+\n+\t\t/*\n+\t\t * We must be careful to not modify underlying data of `ti`\n+\t\t * because we may find that `next` does not contain our desired\n+\t\t * block, but that `ti` does. In that case, we would discard\n+\t\t * `next` and continue with `ti`.\n+\t\t *\n+\t\t * This also means that we cannot reuse allocated memory for\n+\t\t * `next` here. While it would be great if we could, it should\n+\t\t * in practice not be too bad given that we should only ever\n+\t\t * end up doing linear seeks with at most three blocks. As soon\n+\t\t * as we have more than three blocks we would have an index, so\n+\t\t * we would not do a linear search there anymore.\n+\t\t */\n+\t\tmemset(&next.br.block, 0, sizeof(next.br.block));\n \n-\t\terr = table_iter_next_block(&next, ti);\n+\t\terr = table_iter_next_block(&next);\n \t\tif (err < 0)\n \t\t\tgoto done;\n \t\tif (err > 0)\n-- \n2.44.GIT\n\n"},{"id":"492520","messageId":"a7906a3383841fbdc6f4b1ebd82ea1422f99ae85.1712578376.git.ps@pks.im","threadId":"61207","inReplyTo":"cover.1712578376.git.ps@pks.im","subject":"[PATCH v2 07/10] reftable/block: reuse uncompressed blocks","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-04-08T12:16:54Z","receivedAt":"2024-04-08T12:17:02Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"The reftable backend stores reflog entries in a compressed format and\nthus needs to uncompress blocks before one can read records from it.\nFor each reflog block we thus have to allocate an array that we can\ndecompress the block contents into. This block is being discarded\nwhenever the table iterator moves to the next block. Consequently, we\nreallocate a new array on every block, which is quite wasteful.\n\nRefactor the code to reuse the uncompressed block data when moving the\nblock reader to a new block. This significantly reduces the number of\nallocations when iterating through many compressed blocks. The following\nmeasurements are done with `git reflog list` when listing 100k reflogs.\nBefore:\n\n  HEAP SUMMARY:\n      in use at exit: 13,473 bytes in 122 blocks\n    total heap usage: 45,755 allocs, 45,633 frees, 254,779,456 bytes allocated\n\nAfter:\n\n  HEAP SUMMARY:\n      in use at exit: 13,473 bytes in 122 blocks\n    total heap usage: 23,028 allocs, 22,906 frees, 162,813,547 bytes allocated\n\nSigned-off-by: Patrick Steinhardt <ps@pks.im>\n---\n reftable/block.c  | 14 ++++++--------\n reftable/block.h  |  4 ++++\n reftable/reader.c | 27 ++++++++++++++++-----------\n 3 files changed, 26 insertions(+), 19 deletions(-)\n\ndiff --git a/reftable/block.c b/reftable/block.c\nindex 0c4e71eae3..9460273290 100644\n--- a/reftable/block.c\n+++ b/reftable/block.c\n@@ -186,7 +186,6 @@ int block_reader_init(struct block_reader *br, struct reftable_block *block,\n \tuint16_t restart_count = 0;\n \tuint32_t restart_start = 0;\n \tuint8_t *restart_bytes = NULL;\n-\tuint8_t *uncompressed = NULL;\n \n \treftable_block_done(&br->block);\n \n@@ -202,14 +201,15 @@ int block_reader_init(struct block_reader *br, struct reftable_block *block,\n \t\tuLongf src_len = block->len - block_header_skip;\n \n \t\t/* Log blocks specify the *uncompressed* size in their header. */\n-\t\tREFTABLE_ALLOC_ARRAY(uncompressed, sz);\n+\t\tREFTABLE_ALLOC_GROW(br->uncompressed_data, sz,\n+\t\t\t\t    br->uncompressed_cap);\n \n \t\t/* Copy over the block header verbatim. It's not compressed. */\n-\t\tmemcpy(uncompressed, block->data, block_header_skip);\n+\t\tmemcpy(br->uncompressed_data, block->data, block_header_skip);\n \n \t\t/* Uncompress */\n \t\tif (Z_OK !=\n-\t\t    uncompress2(uncompressed + block_header_skip, &dst_len,\n+\t\t    uncompress2(br->uncompressed_data + block_header_skip, &dst_len,\n \t\t\t\tblock->data + block_header_skip, &src_len)) {\n \t\t\terr = REFTABLE_ZLIB_ERROR;\n \t\t\tgoto done;\n@@ -222,10 +222,8 @@ int block_reader_init(struct block_reader *br, struct reftable_block *block,\n \n \t\t/* We're done with the input data. */\n \t\treftable_block_done(block);\n-\t\tblock->data = uncompressed;\n-\t\tuncompressed = NULL;\n+\t\tblock->data = br->uncompressed_data;\n \t\tblock->len = sz;\n-\t\tblock->source = malloc_block_source();\n \t\tfull_block_size = src_len + block_header_skip;\n \t} else if (full_block_size == 0) {\n \t\tfull_block_size = sz;\n@@ -254,12 +252,12 @@ int block_reader_init(struct block_reader *br, struct reftable_block *block,\n \tbr->restart_bytes = restart_bytes;\n \n done:\n-\treftable_free(uncompressed);\n \treturn err;\n }\n \n void block_reader_release(struct block_reader *br)\n {\n+\treftable_free(br->uncompressed_data);\n \treftable_block_done(&br->block);\n }\n \ndiff --git a/reftable/block.h b/reftable/block.h\nindex d733d45ee0..12414eb642 100644\n--- a/reftable/block.h\n+++ b/reftable/block.h\n@@ -66,6 +66,10 @@ struct block_reader {\n \tstruct reftable_block block;\n \tint hash_size;\n \n+\t/* Uncompressed data for log entries. */\n+\tunsigned char *uncompressed_data;\n+\tsize_t uncompressed_cap;\n+\n \t/* size of the data, excluding restart data. */\n \tuint32_t block_len;\n \tuint8_t *restart_bytes;\ndiff --git a/reftable/reader.c b/reftable/reader.c\nindex dd4de294a1..aacd5f1337 100644\n--- a/reftable/reader.c\n+++ b/reftable/reader.c\n@@ -459,6 +459,8 @@ static int reader_seek_linear(struct table_iter *ti,\n \t\t * we would not do a linear search there anymore.\n \t\t */\n \t\tmemset(&next.br.block, 0, sizeof(next.br.block));\n+\t\tnext.br.uncompressed_data = NULL;\n+\t\tnext.br.uncompressed_cap = 0;\n \n \t\terr = table_iter_next_block(&next);\n \t\tif (err < 0)\n@@ -599,25 +601,28 @@ static int reader_seek_internal(struct reftable_reader *r,\n \tstruct reftable_reader_offsets *offs =\n \t\treader_offsets_for(r, reftable_record_type(rec));\n \tuint64_t idx = offs->index_offset;\n-\tstruct table_iter ti = TABLE_ITER_INIT;\n-\tint err = 0;\n+\tstruct table_iter ti = TABLE_ITER_INIT, *p;\n+\tint err;\n+\n \tif (idx > 0)\n \t\treturn reader_seek_indexed(r, it, rec);\n \n \terr = reader_start(r, &ti, reftable_record_type(rec), 0);\n \tif (err < 0)\n-\t\treturn err;\n+\t\tgoto out;\n+\n \terr = reader_seek_linear(&ti, rec);\n \tif (err < 0)\n-\t\treturn err;\n-\telse {\n-\t\tstruct table_iter *p =\n-\t\t\treftable_malloc(sizeof(struct table_iter));\n-\t\t*p = ti;\n-\t\titerator_from_table_iter(it, p);\n-\t}\n+\t\tgoto out;\n \n-\treturn 0;\n+\tREFTABLE_ALLOC_ARRAY(p, 1);\n+\t*p = ti;\n+\titerator_from_table_iter(it, p);\n+\n+out:\n+\tif (err)\n+\t\ttable_iter_close(&ti);\n+\treturn err;\n }\n \n static int reader_seek(struct reftable_reader *r, struct reftable_iterator *it,\n-- \n2.44.GIT\n\n"},{"id":"492522","messageId":"6635c7b986559e0684a3c5d374bb3460aeaa0084.1712578376.git.ps@pks.im","threadId":"61207","inReplyTo":"cover.1712578376.git.ps@pks.im","subject":"[PATCH v2 08/10] reftable/block: open-code call to `uncompress2()`","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-04-08T12:16:59Z","receivedAt":"2024-04-08T12:17:10Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"The reftable format stores log blocks in a compressed format. Thus,\nwhenever we want to read such a block we first need to decompress it.\nThis is done by calling the convenience function `uncompress2()` of the\nzlib library, which is a simple wrapper that manages the lifecycle of\nthe `zstream` structure for us.\n\nWhile nice for one-off inflation of data, when iterating through reflogs\nwe will likely end up inflating many such log blocks. This requires us\nto reallocate the state of the `zstream` every single time, which adds\nup over time. It would thus be great to reuse the `zstream` instead of\ndiscarding it after every inflation.\n\nOpen-code the call to `uncompress2()` such that we can start reusing the\n`zstream` in the subsequent commit. Note that our open-coded variant is\ndifferent from `uncompress2()` in two ways:\n\n  - We do not loop around `inflate()` until we have processed all input.\n    As our input is limited by the maximum block size, which is 16MB, we\n    should not hit limits of `inflate()`.\n\n  - We use `Z_FINISH` instead of `Z_NO_FLUSH`. Quoting the `inflate()`\n    documentation: \"inflate() should normally be called until it returns\n    Z_STREAM_END or an error. However if all decompression is to be\n    performed in a single step (a single call of inflate), the parameter\n    flush should be set to Z_FINISH.\"\n\n    Furthermore, \"Z_FINISH also informs inflate to not maintain a\n    sliding window if the stream completes, which reduces inflate's\n    memory footprint.\"\n\nOther than that this commit is expected to be functionally equivalent\nand does not yet reuse the `zstream`.\n\nSigned-off-by: Patrick Steinhardt <ps@pks.im>\n---\n reftable/block.c | 38 ++++++++++++++++++++++++++++----------\n 1 file changed, 28 insertions(+), 10 deletions(-)\n\ndiff --git a/reftable/block.c b/reftable/block.c\nindex 9460273290..435922b569 100644\n--- a/reftable/block.c\n+++ b/reftable/block.c\n@@ -195,10 +195,10 @@ int block_reader_init(struct block_reader *br, struct reftable_block *block,\n \t}\n \n \tif (typ == BLOCK_TYPE_LOG) {\n-\t\tint block_header_skip = 4 + header_off;\n-\t\tuLongf dst_len = sz - block_header_skip; /* total size of dest\n-\t\t\t\t\t\t\t    buffer. */\n-\t\tuLongf src_len = block->len - block_header_skip;\n+\t\tuint32_t block_header_skip = 4 + header_off;\n+\t\tuLong dst_len = sz - block_header_skip;\n+\t\tuLong src_len = block->len - block_header_skip;\n+\t\tz_stream stream = {0};\n \n \t\t/* Log blocks specify the *uncompressed* size in their header. */\n \t\tREFTABLE_ALLOC_GROW(br->uncompressed_data, sz,\n@@ -207,15 +207,33 @@ int block_reader_init(struct block_reader *br, struct reftable_block *block,\n \t\t/* Copy over the block header verbatim. It's not compressed. */\n \t\tmemcpy(br->uncompressed_data, block->data, block_header_skip);\n \n-\t\t/* Uncompress */\n-\t\tif (Z_OK !=\n-\t\t    uncompress2(br->uncompressed_data + block_header_skip, &dst_len,\n-\t\t\t\tblock->data + block_header_skip, &src_len)) {\n+\t\terr = inflateInit(&stream);\n+\t\tif (err != Z_OK) {\n \t\t\terr = REFTABLE_ZLIB_ERROR;\n \t\t\tgoto done;\n \t\t}\n \n-\t\tif (dst_len + block_header_skip != sz) {\n+\t\tstream.next_in = block->data + block_header_skip;\n+\t\tstream.avail_in = src_len;\n+\t\tstream.next_out = br->uncompressed_data + block_header_skip;\n+\t\tstream.avail_out = dst_len;\n+\n+\t\t/*\n+\t\t * We know both input as well as output size, and we know that\n+\t\t * the sizes should never be bigger than `uInt_MAX` because\n+\t\t * blocks can at most be 16MB large. We can thus use `Z_FINISH`\n+\t\t * here to instruct zlib to inflate the data in one go, which\n+\t\t * is more efficient than using `Z_NO_FLUSH`.\n+\t\t */\n+\t\terr = inflate(&stream, Z_FINISH);\n+\t\tinflateEnd(&stream);\n+\t\tif (err != Z_STREAM_END) {\n+\t\t\terr = REFTABLE_ZLIB_ERROR;\n+\t\t\tgoto done;\n+\t\t}\n+\t\terr = 0;\n+\n+\t\tif (stream.total_out + block_header_skip != sz) {\n \t\t\terr = REFTABLE_FORMAT_ERROR;\n \t\t\tgoto done;\n \t\t}\n@@ -224,7 +242,7 @@ int block_reader_init(struct block_reader *br, struct reftable_block *block,\n \t\treftable_block_done(block);\n \t\tblock->data = br->uncompressed_data;\n \t\tblock->len = sz;\n-\t\tfull_block_size = src_len + block_header_skip;\n+\t\tfull_block_size = src_len + block_header_skip - stream.avail_in;\n \t} else if (full_block_size == 0) {\n \t\tfull_block_size = sz;\n \t} else if (sz < full_block_size && sz < block->len &&\n-- \n2.44.GIT\n\n"},{"id":"492523","messageId":"587b5601c0c51a8f041258a27e693a2590468eed.1712578376.git.ps@pks.im","threadId":"61207","inReplyTo":"cover.1712578376.git.ps@pks.im","subject":"[PATCH v2 09/10] reftable/block: reuse `zstream` state on inflation","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-04-08T12:17:04Z","receivedAt":"2024-04-08T12:17:11Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"When calling `inflateInit()` and `inflate()`, the zlib library will\nallocate several data structures for the underlying `zstream` to keep\ntrack of various information. Thus, when inflating repeatedly, it is\npossible to optimize memory allocation patterns by reusing the `zstream`\nand then calling `inflateReset()` on it to prepare it for the next chunk\nof data to inflate.\n\nThis is exactly what the reftable code is doing: when iterating through\nreflogs we need to potentially inflate many log blocks, but we discard\nthe `zstream` every single time. Instead, as we reuse the `block_reader`\nfor each of the blocks anyway, we can initialize the `zstream` once and\nthen reuse it for subsequent inflations.\n\nRefactor the code to do so, which leads to a significant reduction in\nthe number of allocations. The following measurements were done when\niterating through 1 million reflog entries. Before:\n\n  HEAP SUMMARY:\n      in use at exit: 13,473 bytes in 122 blocks\n    total heap usage: 23,028 allocs, 22,906 frees, 162,813,552 bytes allocated\n\nAfter:\n\n  HEAP SUMMARY:\n      in use at exit: 13,473 bytes in 122 blocks\n    total heap usage: 302 allocs, 180 frees, 88,352 bytes allocated\n\nSigned-off-by: Patrick Steinhardt <ps@pks.im>\n---\n reftable/block.c  | 25 +++++++++++++++----------\n reftable/block.h  |  3 +++\n reftable/reader.c |  1 +\n 3 files changed, 19 insertions(+), 10 deletions(-)\n\ndiff --git a/reftable/block.c b/reftable/block.c\nindex 435922b569..c6c4a68ea1 100644\n--- a/reftable/block.c\n+++ b/reftable/block.c\n@@ -198,7 +198,6 @@ int block_reader_init(struct block_reader *br, struct reftable_block *block,\n \t\tuint32_t block_header_skip = 4 + header_off;\n \t\tuLong dst_len = sz - block_header_skip;\n \t\tuLong src_len = block->len - block_header_skip;\n-\t\tz_stream stream = {0};\n \n \t\t/* Log blocks specify the *uncompressed* size in their header. */\n \t\tREFTABLE_ALLOC_GROW(br->uncompressed_data, sz,\n@@ -207,16 +206,21 @@ int block_reader_init(struct block_reader *br, struct reftable_block *block,\n \t\t/* Copy over the block header verbatim. It's not compressed. */\n \t\tmemcpy(br->uncompressed_data, block->data, block_header_skip);\n \n-\t\terr = inflateInit(&stream);\n+\t\tif (!br->zstream) {\n+\t\t\tREFTABLE_CALLOC_ARRAY(br->zstream, 1);\n+\t\t\terr = inflateInit(br->zstream);\n+\t\t} else {\n+\t\t\terr = inflateReset(br->zstream);\n+\t\t}\n \t\tif (err != Z_OK) {\n \t\t\terr = REFTABLE_ZLIB_ERROR;\n \t\t\tgoto done;\n \t\t}\n \n-\t\tstream.next_in = block->data + block_header_skip;\n-\t\tstream.avail_in = src_len;\n-\t\tstream.next_out = br->uncompressed_data + block_header_skip;\n-\t\tstream.avail_out = dst_len;\n+\t\tbr->zstream->next_in = block->data + block_header_skip;\n+\t\tbr->zstream->avail_in = src_len;\n+\t\tbr->zstream->next_out = br->uncompressed_data + block_header_skip;\n+\t\tbr->zstream->avail_out = dst_len;\n \n \t\t/*\n \t\t * We know both input as well as output size, and we know that\n@@ -225,15 +229,14 @@ int block_reader_init(struct block_reader *br, struct reftable_block *block,\n \t\t * here to instruct zlib to inflate the data in one go, which\n \t\t * is more efficient than using `Z_NO_FLUSH`.\n \t\t */\n-\t\terr = inflate(&stream, Z_FINISH);\n-\t\tinflateEnd(&stream);\n+\t\terr = inflate(br->zstream, Z_FINISH);\n \t\tif (err != Z_STREAM_END) {\n \t\t\terr = REFTABLE_ZLIB_ERROR;\n \t\t\tgoto done;\n \t\t}\n \t\terr = 0;\n \n-\t\tif (stream.total_out + block_header_skip != sz) {\n+\t\tif (br->zstream->total_out + block_header_skip != sz) {\n \t\t\terr = REFTABLE_FORMAT_ERROR;\n \t\t\tgoto done;\n \t\t}\n@@ -242,7 +245,7 @@ int block_reader_init(struct block_reader *br, struct reftable_block *block,\n \t\treftable_block_done(block);\n \t\tblock->data = br->uncompressed_data;\n \t\tblock->len = sz;\n-\t\tfull_block_size = src_len + block_header_skip - stream.avail_in;\n+\t\tfull_block_size = src_len + block_header_skip - br->zstream->avail_in;\n \t} else if (full_block_size == 0) {\n \t\tfull_block_size = sz;\n \t} else if (sz < full_block_size && sz < block->len &&\n@@ -275,6 +278,8 @@ int block_reader_init(struct block_reader *br, struct reftable_block *block,\n \n void block_reader_release(struct block_reader *br)\n {\n+\tinflateEnd(br->zstream);\n+\treftable_free(br->zstream);\n \treftable_free(br->uncompressed_data);\n \treftable_block_done(&br->block);\n }\ndiff --git a/reftable/block.h b/reftable/block.h\nindex 12414eb642..c1bd1892cb 100644\n--- a/reftable/block.h\n+++ b/reftable/block.h\n@@ -56,6 +56,8 @@ int block_writer_finish(struct block_writer *w);\n /* clears out internally allocated block_writer members. */\n void block_writer_release(struct block_writer *bw);\n \n+struct z_stream;\n+\n /* Read a block. */\n struct block_reader {\n \t/* offset of the block header; nonzero for the first block in a\n@@ -67,6 +69,7 @@ struct block_reader {\n \tint hash_size;\n \n \t/* Uncompressed data for log entries. */\n+\tz_stream *zstream;\n \tunsigned char *uncompressed_data;\n \tsize_t uncompressed_cap;\n \ndiff --git a/reftable/reader.c b/reftable/reader.c\nindex aacd5f1337..481dff10d4 100644\n--- a/reftable/reader.c\n+++ b/reftable/reader.c\n@@ -459,6 +459,7 @@ static int reader_seek_linear(struct table_iter *ti,\n \t\t * we would not do a linear search there anymore.\n \t\t */\n \t\tmemset(&next.br.block, 0, sizeof(next.br.block));\n+\t\tnext.br.zstream = NULL;\n \t\tnext.br.uncompressed_data = NULL;\n \t\tnext.br.uncompressed_cap = 0;\n \n-- \n2.44.GIT\n\n"},{"id":"492521","messageId":"cc5ff0d5988691043206f9e912f5ffa1bcfee94e.1712578376.git.ps@pks.im","threadId":"61207","inReplyTo":"cover.1712578376.git.ps@pks.im","subject":"[PATCH v2 10/10] reftable/block: avoid copying block iterators on seek","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-04-08T12:17:08Z","receivedAt":"2024-04-08T12:17:14Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"When seeking a reftable record in a block we need to position the\niterator _before_ the sought-after record so that the next call to\n`block_iter_next()` would yield that record. To achieve this, the loop\nthat performs the linear needs to restore the previous position once it\nhas found the record.\n\nThis is done by advancing two `block_iter`s: one to check whether the\nnext record is our sought-after record, and one that we update after\nevery iteration. This of course involves quite a lot of copying and also\nleads to needless memory allocations.\n\nRefactor the code to get rid of the `next` iterator and the copying this\ninvolves. Instead, we can restore the previous offset such that the call\nto `next` will return the correct record.\n\nNext to being simpler conceptually this also leads to a nice speedup.\nThe following benchmark parser 10k refs out of 100k existing refs via\n`git-rev-list --no-walk`:\n\n  Benchmark 1: rev-list: print many refs (HEAD~)\n    Time (mean ± σ):     170.2 ms ±   1.7 ms    [User: 86.1 ms, System: 83.6 ms]\n    Range (min … max):   166.4 ms … 180.3 ms    500 runs\n\n  Benchmark 2: rev-list: print many refs (HEAD~)\n    Time (mean ± σ):     161.6 ms ±   1.6 ms    [User: 78.1 ms, System: 83.0 ms]\n    Range (min … max):   158.4 ms … 172.3 ms    500 runs\n\n  Summary\n    rev-list: print many refs (HEAD) ran\n      1.05 ± 0.01 times faster than rev-list: print many refs (HEAD~)\n\nSigned-off-by: Patrick Steinhardt <ps@pks.im>\n---\n reftable/block.c | 32 ++++++++++++++------------------\n reftable/block.h |  2 --\n 2 files changed, 14 insertions(+), 20 deletions(-)\n\ndiff --git a/reftable/block.c b/reftable/block.c\nindex c6c4a68ea1..3e87460cba 100644\n--- a/reftable/block.c\n+++ b/reftable/block.c\n@@ -365,16 +365,6 @@ static int restart_needle_less(size_t idx, void *_args)\n \treturn args->needle.len < suffix_len;\n }\n \n-void block_iter_copy_from(struct block_iter *dest, const struct block_iter *src)\n-{\n-\tdest->block = src->block;\n-\tdest->block_len = src->block_len;\n-\tdest->hash_size = src->hash_size;\n-\tdest->next_off = src->next_off;\n-\tstrbuf_reset(&dest->last_key);\n-\tstrbuf_addbuf(&dest->last_key, &src->last_key);\n-}\n-\n int block_iter_next(struct block_iter *it, struct reftable_record *rec)\n {\n \tstruct string_view in = {\n@@ -427,7 +417,6 @@ int block_iter_seek_key(struct block_iter *it, const struct block_reader *br,\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 \tint err = 0;\n \tsize_t i;\n@@ -486,11 +475,13 @@ int block_iter_seek_key(struct block_iter *it, const struct block_reader *br,\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\tsize_t prev_off = it->next_off;\n+\n+\t\terr = block_iter_next(it, &rec);\n \t\tif (err < 0)\n \t\t\tgoto done;\n \t\tif (err > 0) {\n+\t\t\tit->next_off = prev_off;\n \t\t\terr = 0;\n \t\t\tgoto done;\n \t\t}\n@@ -501,18 +492,23 @@ int block_iter_seek_key(struct block_iter *it, const struct block_reader *br,\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\t * Note that we store the next record's key record directly in\n+\t\t * `last_key` without restoring the key of the preceding record\n+\t\t * in case we need to go one record back. This is safe to do as\n+\t\t * `block_iter_next()` would return the ref whose key is equal\n+\t\t * to `last_key` now, and naturally all keys share a prefix\n+\t\t * with themselves.\n \t\t */\n \t\treftable_record_key(&rec, &it->last_key);\n-\t\tif (strbuf_cmp(&it->last_key, want) >= 0)\n+\t\tif (strbuf_cmp(&it->last_key, want) >= 0) {\n+\t\t\tit->next_off = prev_off;\n \t\t\tgoto done;\n-\n-\t\tblock_iter_copy_from(it, &next);\n+\t\t}\n \t}\n \n done:\n-\tblock_iter_close(&next);\n \treftable_record_release(&rec);\n-\n \treturn err;\n }\n \ndiff --git a/reftable/block.h b/reftable/block.h\nindex c1bd1892cb..ea4384a7e2 100644\n--- a/reftable/block.h\n+++ b/reftable/block.h\n@@ -121,8 +121,6 @@ void block_iter_seek_start(struct block_iter *it, const struct block_reader *br)\n int block_iter_seek_key(struct block_iter *it, const struct block_reader *br,\n \t\t\tstruct strbuf *want);\n \n-void block_iter_copy_from(struct block_iter *dest, const struct block_iter *src);\n-\n /* return < 0 for error, 0 for OK, > 0 for EOF. */\n int block_iter_next(struct block_iter *it, struct reftable_record *rec);\n \n-- \n2.44.GIT\n\n"},{"id":"492605","messageId":"vab3mzg3meohikmfl5v57uxj6w7w2odrx7cvhmoto7am2bl2yt@6l4salel4ko5","threadId":"61207","inReplyTo":"cc5ff0d5988691043206f9e912f5ffa1bcfee94e.1712578376.git.ps@pks.im","subject":"Re: [PATCH v2 10/10] reftable/block: avoid copying block iterators on seek","fromName":"Justin Tobler","fromEmail":"jltobler@gmail.com","sentAt":"2024-04-09T01:29:14Z","receivedAt":"2024-04-09T01:30:14Z","isPatch":true,"sender":{"key":"jltobler@gmail.com","avatar":"https://avatars.githubusercontent.com/u/53454972?v=4"},"body":"On 24/04/08 02:17PM, Patrick Steinhardt wrote:\n> When seeking a reftable record in a block we need to position the\n> iterator _before_ the sought-after record so that the next call to\n> `block_iter_next()` would yield that record. To achieve this, the loop\n> that performs the linear needs to restore the previous position once it\n\nDid we mean to say \"linear seek\" here? Otherwise this looks good to me.\n\n-Justin\n\n> has found the record.\n> \n> This is done by advancing two `block_iter`s: one to check whether the\n> next record is our sought-after record, and one that we update after\n> every iteration. This of course involves quite a lot of copying and also\n> leads to needless memory allocations.\n> \n> Refactor the code to get rid of the `next` iterator and the copying this\n> involves. Instead, we can restore the previous offset such that the call\n> to `next` will return the correct record.\n> \n> Next to being simpler conceptually this also leads to a nice speedup.\n> The following benchmark parser 10k refs out of 100k existing refs via\n> `git-rev-list --no-walk`:\n> \n>   Benchmark 1: rev-list: print many refs (HEAD~)\n>     Time (mean ± σ):     170.2 ms ±   1.7 ms    [User: 86.1 ms, System: 83.6 ms]\n>     Range (min … max):   166.4 ms … 180.3 ms    500 runs\n> \n>   Benchmark 2: rev-list: print many refs (HEAD~)\n>     Time (mean ± σ):     161.6 ms ±   1.6 ms    [User: 78.1 ms, System: 83.0 ms]\n>     Range (min … max):   158.4 ms … 172.3 ms    500 runs\n> \n>   Summary\n>     rev-list: print many refs (HEAD) ran\n>       1.05 ± 0.01 times faster than rev-list: print many refs (HEAD~)\n> \n> Signed-off-by: Patrick Steinhardt <ps@pks.im>\n...\n"},{"id":"492606","messageId":"wpkr5pmz53zp3nuzezfmqme3b3ymtnwx2noeto6ioi77q67z4y@7k7qg6s2eehr","threadId":"61207","inReplyTo":"cover.1712578376.git.ps@pks.im","subject":"Re: [PATCH v2 00/10] reftable: optimize table and block iterators","fromName":"Justin Tobler","fromEmail":"jltobler@gmail.com","sentAt":"2024-04-09T01:32:42Z","receivedAt":"2024-04-09T01:33:42Z","isPatch":true,"sender":{"key":"jltobler@gmail.com","avatar":"https://avatars.githubusercontent.com/u/53454972?v=4"},"body":"On 24/04/08 02:16PM, Patrick Steinhardt wrote:\n> Hi,\n> \n> this is the second version of my patch series that aims to optimize\n> the reftable table and block iterators.\n> \n> Changes compared to v1:\n> \n>     - The series now deepends on ps/reftable-binsearch-update at\n>       d51d8cc368 (reftable/block: avoid decoding keys when searching\n>       restart points, 2024-04-03). This is to resolve a merge conflict\n>       with that other series which has landed in \"next\" already.\n> \n>     - Rewrote a comment to be single-line to fit into the style of other\n>       comments better.\n> \n>     - A new patch on top that avoids copying block iterators altogether\n>       for another speedup.\n> \n> Thanks!\n> \n> Patrick\n\nThanks, other than a small question about one of the commit messages,\nthis version looks good to me.\n\n-Justin\n"},{"id":"492612","messageId":"ZhSzla7GwfdokQbG@tanuki","threadId":"61207","inReplyTo":"vab3mzg3meohikmfl5v57uxj6w7w2odrx7cvhmoto7am2bl2yt@6l4salel4ko5","subject":"Re: [PATCH v2 10/10] reftable/block: avoid copying block iterators on seek","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-04-09T03:18:45Z","receivedAt":"2024-04-09T03:18:50Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"On Mon, Apr 08, 2024 at 08:29:14PM -0500, Justin Tobler wrote:\n> On 24/04/08 02:17PM, Patrick Steinhardt wrote:\n> > When seeking a reftable record in a block we need to position the\n> > iterator _before_ the sought-after record so that the next call to\n> > `block_iter_next()` would yield that record. To achieve this, the loop\n> > that performs the linear needs to restore the previous position once it\n> \n> Did we mean to say \"linear seek\" here? Otherwise this looks good to me.\n> \n> -Justin\n\nOh, yes, of course. Thanks for reading this carefully!\n\nPatrick\n\n> > has found the record.\n> > \n> > This is done by advancing two `block_iter`s: one to check whether the\n> > next record is our sought-after record, and one that we update after\n> > every iteration. This of course involves quite a lot of copying and also\n> > leads to needless memory allocations.\n> > \n> > Refactor the code to get rid of the `next` iterator and the copying this\n> > involves. Instead, we can restore the previous offset such that the call\n> > to `next` will return the correct record.\n> > \n> > Next to being simpler conceptually this also leads to a nice speedup.\n> > The following benchmark parser 10k refs out of 100k existing refs via\n> > `git-rev-list --no-walk`:\n> > \n> >   Benchmark 1: rev-list: print many refs (HEAD~)\n> >     Time (mean ± σ):     170.2 ms ±   1.7 ms    [User: 86.1 ms, System: 83.6 ms]\n> >     Range (min … max):   166.4 ms … 180.3 ms    500 runs\n> > \n> >   Benchmark 2: rev-list: print many refs (HEAD~)\n> >     Time (mean ± σ):     161.6 ms ±   1.6 ms    [User: 78.1 ms, System: 83.0 ms]\n> >     Range (min … max):   158.4 ms … 172.3 ms    500 runs\n> > \n> >   Summary\n> >     rev-list: print many refs (HEAD) ran\n> >       1.05 ± 0.01 times faster than rev-list: print many refs (HEAD~)\n> > \n> > Signed-off-by: Patrick Steinhardt <ps@pks.im>\n> ...\n"},{"id":"492710","messageId":"CAOLa=ZTnnmBvwXMbHqJ+58kPGe4jwLhu_GaEfkAXyfVa5imeYA@mail.gmail.com","threadId":"61207","inReplyTo":"587b5601c0c51a8f041258a27e693a2590468eed.1712578376.git.ps@pks.im","subject":"Re: [PATCH v2 09/10] reftable/block: reuse `zstream` state on inflation","fromName":"Karthik Nayak","fromEmail":"karthik.188@gmail.com","sentAt":"2024-04-10T10:15:56Z","receivedAt":"2024-04-10T10:15:57Z","isPatch":true,"sender":{"key":"karthik.188@gmail.com","avatar":"https://avatars.githubusercontent.com/u/1786334?v=4"},"body":"Patrick Steinhardt <ps@pks.im> writes:\n\n> When calling `inflateInit()` and `inflate()`, the zlib library will\n> allocate several data structures for the underlying `zstream` to keep\n> track of various information. Thus, when inflating repeatedly, it is\n> possible to optimize memory allocation patterns by reusing the `zstream`\n> and then calling `inflateReset()` on it to prepare it for the next chunk\n> of data to inflate.\n>\n> This is exactly what the reftable code is doing: when iterating through\n> reflogs we need to potentially inflate many log blocks, but we discard\n> the `zstream` every single time. Instead, as we reuse the `block_reader`\n> for each of the blocks anyway, we can initialize the `zstream` once and\n> then reuse it for subsequent inflations.\n>\n> Refactor the code to do so, which leads to a significant reduction in\n> the number of allocations. The following measurements were done when\n> iterating through 1 million reflog entries. Before:\n>\n>   HEAP SUMMARY:\n>       in use at exit: 13,473 bytes in 122 blocks\n>     total heap usage: 23,028 allocs, 22,906 frees, 162,813,552 bytes allocated\n>\n> After:\n>\n>   HEAP SUMMARY:\n>       in use at exit: 13,473 bytes in 122 blocks\n>     total heap usage: 302 allocs, 180 frees, 88,352 bytes allocated\n>\n\nReally nice how just reusing the data structure has such a significant\nimpact.\n"},{"id":"492713","messageId":"CAOLa=ZRxQPnPxM+sZtuL-a5DVJL8Xx+D7t2d4cLoPT-hLaK_UA@mail.gmail.com","threadId":"61207","inReplyTo":"cover.1712578376.git.ps@pks.im","subject":"Re: [PATCH v2 00/10] reftable: optimize table and block iterators","fromName":"Karthik Nayak","fromEmail":"karthik.188@gmail.com","sentAt":"2024-04-10T11:35:17Z","receivedAt":"2024-04-10T11:35:18Z","isPatch":true,"sender":{"key":"karthik.188@gmail.com","avatar":"https://avatars.githubusercontent.com/u/1786334?v=4"},"body":"Patrick Steinhardt <ps@pks.im> writes:\n\n> Hi,\n>\n> this is the second version of my patch series that aims to optimize\n> the reftable table and block iterators.\n>\n> Changes compared to v1:\n>\n>     - The series now deepends on ps/reftable-binsearch-update at\n>       d51d8cc368 (reftable/block: avoid decoding keys when searching\n>       restart points, 2024-04-03). This is to resolve a merge conflict\n>       with that other series which has landed in \"next\" already.\n>\n>     - Rewrote a comment to be single-line to fit into the style of other\n>       comments better.\n>\n>     - A new patch on top that avoids copying block iterators altogether\n>       for another speedup.\n>\n\nOverall this series looks good to me. Thanks\n"}]}