{"thread":{"id":"60638","subject":"[PATCH 0/7] reftable: fixes and optimizations (pt.2)","startedAt":"2023-12-20T09:17:07Z","lastAt":"2024-02-15T07:43:49Z","messageCount":36,"participants":["Patrick Steinhardt","Junio C Hamano","Karthik Nayak","Han-Wen Nienhuys"],"isPatch":true,"patchVersion":1,"patchTotal":7},"messages":[{"id":"485839","messageId":"cover.1703063544.git.ps@pks.im","threadId":"60638","inReplyTo":null,"subject":"[PATCH 0/7] reftable: fixes and optimizations (pt.2)","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2023-12-20T09:17:01Z","receivedAt":"2023-12-20T09:17:07Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"Hi,\n\nthis is the second set of patches that fixes bugs and performs some\nslight memory optimizations. The series builds on top of c0cadb0576,\nwhich has been merged to `next`.\n\nThe series is structured as follows:\n\n - Patch 1: some hardening to not corrupt the reftable stack on\n compaction.\n\n - Patch 2: fix corruption of a reftable when writing multiple indices.\n\n - Patches 3 - 7: various smallish refactorings to optimize memory\n usage. Overall these reduce allocations when iterating many refs by\n almost 85%.\n\nThanks in advance for your review!\n\nPatrick\n\nPatrick Steinhardt (7):\n reftable/stack: do not overwrite errors when compacting\n reftable/writer: fix index corruption when writing multiple indices\n reftable/record: constify some parts of the interface\n reftable/record: store \"val1\" hashes as static arrays\n reftable/record: store \"val2\" hashes as static arrays\n reftable/merged: really reuse buffers to compute record keys\n reftable/merged: transfer ownership of records when iterating\n\n reftable/block_test.c | 4 +-\n reftable/merged.c | 8 +--\n reftable/merged_test.c | 16 +++---\n reftable/readwrite_test.c | 103 +++++++++++++++++++++++++++++++------\n reftable/record.c | 17 ++----\n reftable/record_test.c | 5 --\n reftable/reftable-record.h | 10 ++--\n reftable/stack.c | 20 +++----\n reftable/stack_test.c | 2 -\n reftable/writer.c | 4 +-\n 10 files changed, 117 insertions(+), 72 deletions(-)\n\n\nbase-commit: c0cadb0576d4920915eb3bd38a7d1abfcbd25f98\n-- \n2.43.GIT\n\n"},{"id":"485840","messageId":"573fb2c4fb6c97d4279058cce6aab877c27e77bc.1703063544.git.ps@pks.im","threadId":"60638","inReplyTo":"cover.1703063544.git.ps@pks.im","subject":"[PATCH 1/7] reftable/stack: do not overwrite errors when compacting","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2023-12-20T09:17:05Z","receivedAt":"2023-12-20T09:17:09Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"In order to compact multiple stacks we iterate through the merged ref\nand log records. When there is any error either when reading the records\nfrom the old merged table or when writing the records to the new table\nthen we break out of the respective loops. When breaking out of the loop\nfor the ref records though the error code will be overwritten, which may\ncause us to inadvertently skip over bad ref records. In the worst case,\nthis can lead to a compacted stack that is missing records.\n\nFix the code by using `goto done` instead so that any potential error\ncodes are properly returned to the caller.\n\nSigned-off-by: Patrick Steinhardt \n---\n reftable/stack.c | 20 ++++++++------------\n 1 file changed, 8 insertions(+), 12 deletions(-)\n\ndiff --git a/reftable/stack.c b/reftable/stack.c\nindex 16bab82063..8729508dc3 100644\n--- a/reftable/stack.c\n+++ b/reftable/stack.c\n@@ -801,18 +801,16 @@ static int stack_write_compact(struct reftable_stack *st,\n \t\t\terr = 0;\n \t\t\tbreak;\n \t\t}\n-\t\tif (err < 0) {\n-\t\t\tbreak;\n-\t\t}\n+\t\tif (err < 0)\n+\t\t\tgoto done;\n \n \t\tif (first == 0 && reftable_ref_record_is_deletion(&ref)) {\n \t\t\tcontinue;\n \t\t}\n \n \t\terr = reftable_writer_add_ref(wr, &ref);\n-\t\tif (err < 0) {\n-\t\t\tbreak;\n-\t\t}\n+\t\tif (err < 0)\n+\t\t\tgoto done;\n \t\tentries++;\n \t}\n \treftable_iterator_destroy(&it);\n@@ -827,9 +825,8 @@ static int stack_write_compact(struct reftable_stack *st,\n \t\t\terr = 0;\n \t\t\tbreak;\n \t\t}\n-\t\tif (err < 0) {\n-\t\t\tbreak;\n-\t\t}\n+\t\tif (err < 0)\n+\t\t\tgoto done;\n \t\tif (first == 0 && reftable_log_record_is_deletion(&log)) {\n \t\t\tcontinue;\n \t\t}\n@@ -845,9 +842,8 @@ static int stack_write_compact(struct reftable_stack *st,\n \t\t}\n \n \t\terr = reftable_writer_add_log(wr, &log);\n-\t\tif (err < 0) {\n-\t\t\tbreak;\n-\t\t}\n+\t\tif (err < 0)\n+\t\t\tgoto done;\n \t\tentries++;\n \t}\n \n-- \n2.43.GIT\n\n"},{"id":"485841","messageId":"86ee79c48d599fee5e85bf88a17a59929ae1ecab.1703063544.git.ps@pks.im","threadId":"60638","inReplyTo":"cover.1703063544.git.ps@pks.im","subject":"[PATCH 2/7] reftable/writer: fix index corruption when writing multiple indices","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2023-12-20T09:17:09Z","receivedAt":"2023-12-20T09:17:13Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"Each reftable may contain multiple types of blocks for refs, objects and\nreflog records, where each of these may have an index that makes it more\nefficient to find the records. It was observed that the index for log\nrecords can become corrupted under certain circumstances, where the\nfirst entry of the index points into the object index instead of to the\nlog records.\n\nAs it turns out, this corruption can occur whenever we write a log index\nas well as at least one additional index. Writing records and their index\nis basically a two-step process:\n\n 1. We write all blocks for the corresponding record. Each block that\n gets written is added to a list of blocks to index.\n\n 2. Once all blocks were written we finish the section. If at least two\n blocks have been added to the list of blocks to index then we will\n now write the index for those blocks and flush it, as well.\n\nWhen we have a very large number of blocks then we may decide to write a\nmulti-level index, which is why we also keep track of the list of the\nindex blocks in the same way as we previously kept track of the blocks\nto index.\n\nNow when we have finished writing all index blocks we clear the index\nand flush the last block to disk. This is done in the wrong order though\nbecause flushing the block to disk will re-add it to the list of blocks\nto be indexed. The result is that the next section we are about to write\nwill have an entry in the list of blocks to index that points to the\nlast block of the preceding section's index, which will corrupt the log\nindex.\n\nFix this corruption by clearing the index after having written the last\nblock.\n\nSigned-off-by: Patrick Steinhardt \n---\n reftable/readwrite_test.c | 80 +++++++++++++++++++++++++++++++++++++++\n reftable/writer.c | 4 +-\n 2 files changed, 82 insertions(+), 2 deletions(-)\n\ndiff --git a/reftable/readwrite_test.c b/reftable/readwrite_test.c\nindex 278663f22d..9c16e0504e 100644\n--- a/reftable/readwrite_test.c\n+++ b/reftable/readwrite_test.c\n@@ -798,6 +798,85 @@ static void test_write_key_order(void)\n \tstrbuf_release(&buf);\n }\n \n+static void test_write_multiple_indices(void)\n+{\n+\tstruct reftable_write_options opts = {\n+\t\t.block_size = 100,\n+\t};\n+\tstruct strbuf writer_buf = STRBUF_INIT, buf = STRBUF_INIT;\n+\tstruct reftable_block_source source = { 0 };\n+\tstruct reftable_iterator it = { 0 };\n+\tconst struct reftable_stats *stats;\n+\tstruct reftable_writer *writer;\n+\tstruct reftable_reader *reader;\n+\tint err, i;\n+\n+\twriter = reftable_new_writer(&strbuf_add_void, &writer_buf, &opts);\n+\treftable_writer_set_limits(writer, 1, 1);\n+\tfor (i = 0; i < 100; i++) {\n+\t\tunsigned char hash[GIT_SHA1_RAWSZ] = {i};\n+\t\tstruct reftable_ref_record ref = {\n+\t\t\t.update_index = 1,\n+\t\t\t.value_type = REFTABLE_REF_VAL1,\n+\t\t\t.value.val1 = hash,\n+\t\t};\n+\n+\t\tstrbuf_reset(&buf);\n+\t\tstrbuf_addf(&buf, \"refs/heads/%04d\", i);\n+\t\tref.refname = buf.buf,\n+\n+\t\terr = reftable_writer_add_ref(writer, &ref);\n+\t\tEXPECT_ERR(err);\n+\t}\n+\n+\tfor (i = 0; i < 100; i++) {\n+\t\tunsigned char hash[GIT_SHA1_RAWSZ] = {i};\n+\t\tstruct reftable_log_record log = {\n+\t\t\t.update_index = 1,\n+\t\t\t.value_type = REFTABLE_LOG_UPDATE,\n+\t\t\t.value.update = {\n+\t\t\t\t.old_hash = hash,\n+\t\t\t\t.new_hash = hash,\n+\t\t\t},\n+\t\t};\n+\n+\t\tstrbuf_reset(&buf);\n+\t\tstrbuf_addf(&buf, \"refs/heads/%04d\", i);\n+\t\tlog.refname = buf.buf,\n+\n+\t\terr = reftable_writer_add_log(writer, &log);\n+\t\tEXPECT_ERR(err);\n+\t}\n+\n+\treftable_writer_close(writer);\n+\n+\t/*\n+\t * The written data should be sufficiently large to result in indices\n+\t * for each of the block types.\n+\t */\n+\tstats = reftable_writer_stats(writer);\n+\tEXPECT(stats->ref_stats.index_offset > 0);\n+\tEXPECT(stats->obj_stats.index_offset > 0);\n+\tEXPECT(stats->log_stats.index_offset > 0);\n+\n+\tblock_source_from_strbuf(&source, &writer_buf);\n+\terr = reftable_new_reader(&reader, &source, \"filename\");\n+\tEXPECT_ERR(err);\n+\n+\t/*\n+\t * Seeking the log uses the log index now. In case there is any\n+\t * confusion regarding indices we would notice here.\n+\t */\n+\terr = reftable_reader_seek_log(reader, &it, \"\");\n+\tEXPECT_ERR(err);\n+\n+\treftable_iterator_destroy(&it);\n+\treftable_writer_free(writer);\n+\treftable_reader_free(reader);\n+\tstrbuf_release(&writer_buf);\n+\tstrbuf_release(&buf);\n+}\n+\n static void test_corrupt_table_empty(void)\n {\n \tstruct strbuf buf = STRBUF_INIT;\n@@ -847,5 +926,6 @@ int readwrite_test_main(int argc, const char *argv[])\n \tRUN_TEST(test_log_overflow);\n \tRUN_TEST(test_write_object_id_length);\n \tRUN_TEST(test_write_object_id_min_length);\n+\tRUN_TEST(test_write_multiple_indices);\n \treturn 0;\n }\ndiff --git a/reftable/writer.c b/reftable/writer.c\nindex 2e322a5683..ee4590e20f 100644\n--- a/reftable/writer.c\n+++ b/reftable/writer.c\n@@ -432,12 +432,12 @@ static int writer_finish_section(struct reftable_writer *w)\n \t\treftable_free(idx);\n \t}\n \n-\twriter_clear_index(w);\n-\n \terr = writer_flush_block(w);\n \tif (err < 0)\n \t\treturn err;\n \n+\twriter_clear_index(w);\n+\n \tbstats = writer_reftable_block_stats(w, typ);\n \tbstats->index_blocks = w->stats.idx_stats.blocks - before_blocks;\n \tbstats->index_offset = index_start;\n-- \n2.43.GIT\n\n"},{"id":"485842","messageId":"3ad4a0e5b9afd7ef841c2671ac4a8dd23b315e4b.1703063544.git.ps@pks.im","threadId":"60638","inReplyTo":"cover.1703063544.git.ps@pks.im","subject":"[PATCH 3/7] reftable/record: constify some parts of the interface","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2023-12-20T09:17:13Z","receivedAt":"2023-12-20T09:17:17Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"We're about to convert reftable records to stop storing their object IDs\nas allocated hashes. Prepare for this refactoring by constifying some\nparts of the interface that will be impacted by this.\n\nSigned-off-by: Patrick Steinhardt \n---\n reftable/record.c | 8 ++++----\n reftable/reftable-record.h | 4 ++--\n 2 files changed, 6 insertions(+), 6 deletions(-)\n\ndiff --git a/reftable/record.c b/reftable/record.c\nindex fbaa1fbef5..5e258c734b 100644\n--- a/reftable/record.c\n+++ b/reftable/record.c\n@@ -76,7 +76,7 @@ int reftable_is_block_type(uint8_t typ)\n \treturn 0;\n }\n \n-uint8_t *reftable_ref_record_val1(const struct reftable_ref_record *rec)\n+const unsigned char *reftable_ref_record_val1(const struct reftable_ref_record *rec)\n {\n \tswitch (rec->value_type) {\n \tcase REFTABLE_REF_VAL1:\n@@ -88,7 +88,7 @@ uint8_t *reftable_ref_record_val1(const struct reftable_ref_record *rec)\n \t}\n }\n \n-uint8_t *reftable_ref_record_val2(const struct reftable_ref_record *rec)\n+const unsigned char *reftable_ref_record_val2(const struct reftable_ref_record *rec)\n {\n \tswitch (rec->value_type) {\n \tcase REFTABLE_REF_VAL2:\n@@ -242,7 +242,7 @@ static char hexdigit(int c)\n \treturn 'a' + (c - 10);\n }\n \n-static void hex_format(char *dest, uint8_t *src, int hash_size)\n+static void hex_format(char *dest, const unsigned char *src, int hash_size)\n {\n \tassert(hash_size > 0);\n \tif (src) {\n@@ -1164,7 +1164,7 @@ int reftable_record_equal(struct reftable_record *a, struct reftable_record *b,\n \t\treftable_record_data(a), reftable_record_data(b), hash_size);\n }\n \n-static int hash_equal(uint8_t *a, uint8_t *b, int hash_size)\n+static int hash_equal(const unsigned char *a, const unsigned char *b, int hash_size)\n {\n \tif (a && b)\n \t\treturn !memcmp(a, b, hash_size);\ndiff --git a/reftable/reftable-record.h b/reftable/reftable-record.h\nindex 67104f8fbf..f7eb2d6015 100644\n--- a/reftable/reftable-record.h\n+++ b/reftable/reftable-record.h\n@@ -49,11 +49,11 @@ struct reftable_ref_record {\n \n /* Returns the first hash, or NULL if `rec` is not of type\n * REFTABLE_REF_VAL1 or REFTABLE_REF_VAL2. */\n-uint8_t *reftable_ref_record_val1(const struct reftable_ref_record *rec);\n+const unsigned char *reftable_ref_record_val1(const struct reftable_ref_record *rec);\n \n /* Returns the second hash, or NULL if `rec` is not of type\n * REFTABLE_REF_VAL2. */\n-uint8_t *reftable_ref_record_val2(const struct reftable_ref_record *rec);\n+const unsigned char *reftable_ref_record_val2(const struct reftable_ref_record *rec);\n \n /* returns whether 'ref' represents a deletion */\n int reftable_ref_record_is_deletion(const struct reftable_ref_record *ref);\n-- \n2.43.GIT\n\n"},{"id":"485843","messageId":"06c9eab67802ba933b44d32f5c8d11fddc216c26.1703063544.git.ps@pks.im","threadId":"60638","inReplyTo":"cover.1703063544.git.ps@pks.im","subject":"[PATCH 4/7] reftable/record: store \"val1\" hashes as static arrays","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2023-12-20T09:17:17Z","receivedAt":"2023-12-20T09:17:20Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"When reading ref records of type \"val1\" we store its object ID in an\nallocated array. This results in an additional allocation for every\nsingle ref record we read, which is rather inefficient especially when\niterating over refs.\n\nRefactor the code to instead use a static array of `GIT_MAX_RAWSZ`\nbytes. While this means that `struct ref_record` is bigger now, we\ntypically do not store all refs in an array anyway and instead only\nhandle a limited number of records at the same point in time.\n\nUsing `git show-ref --quiet` in a repository with ~350k refs this leads\nto a significant drop in allocations. Before:\n\n HEAP SUMMARY:\n in use at exit: 21,098 bytes in 192 blocks\n total heap usage: 2,116,683 allocs, 2,116,491 frees, 76,098,060 bytes allocated\n\nAfter:\n\n HEAP SUMMARY:\n in use at exit: 21,098 bytes in 192 blocks\n total heap usage: 1,419,031 allocs, 1,418,839 frees, 62,145,036 bytes allocated\n\nSigned-off-by: Patrick Steinhardt \n---\n reftable/block_test.c | 4 +---\n reftable/merged_test.c | 16 ++++++----------\n reftable/readwrite_test.c | 11 +++--------\n reftable/record.c | 3 ---\n reftable/record_test.c | 1 -\n reftable/reftable-record.h | 2 +-\n reftable/stack_test.c | 2 --\n 7 files changed, 11 insertions(+), 28 deletions(-)\n\ndiff --git a/reftable/block_test.c b/reftable/block_test.c\nindex c00bbc8aed..dedb05c7d8 100644\n--- a/reftable/block_test.c\n+++ b/reftable/block_test.c\n@@ -49,13 +49,11 @@ static void test_block_read_write(void)\n \n \tfor (i = 0; i < N; i++) {\n \t\tchar name[100];\n-\t\tuint8_t hash[GIT_SHA1_RAWSZ];\n \t\tsnprintf(name, sizeof(name), \"branch%02d\", i);\n-\t\tmemset(hash, i, sizeof(hash));\n \n \t\trec.u.ref.refname = name;\n \t\trec.u.ref.value_type = REFTABLE_REF_VAL1;\n-\t\trec.u.ref.value.val1 = hash;\n+\t\tmemset(rec.u.ref.value.val1, i, GIT_SHA1_RAWSZ);\n \n \t\tnames[i] = xstrdup(name);\n \t\tn = block_writer_add(&bw, &rec);\ndiff --git a/reftable/merged_test.c b/reftable/merged_test.c\nindex d08c16abef..b3927a5d73 100644\n--- a/reftable/merged_test.c\n+++ b/reftable/merged_test.c\n@@ -123,13 +123,11 @@ static void readers_destroy(struct reftable_reader **readers, size_t n)\n \n static void test_merged_between(void)\n {\n-\tuint8_t hash1[GIT_SHA1_RAWSZ] = { 1, 2, 3, 0 };\n-\n \tstruct reftable_ref_record r1[] = { {\n \t\t.refname = \"b\",\n \t\t.update_index = 1,\n \t\t.value_type = REFTABLE_REF_VAL1,\n-\t\t.value.val1 = hash1,\n+\t\t.value.val1 = { 1, 2, 3, 0 },\n \t} };\n \tstruct reftable_ref_record r2[] = { {\n \t\t.refname = \"a\",\n@@ -165,26 +163,24 @@ static void test_merged_between(void)\n \n static void test_merged(void)\n {\n-\tuint8_t hash1[GIT_SHA1_RAWSZ] = { 1 };\n-\tuint8_t hash2[GIT_SHA1_RAWSZ] = { 2 };\n \tstruct reftable_ref_record r1[] = {\n \t\t{\n \t\t\t.refname = \"a\",\n \t\t\t.update_index = 1,\n \t\t\t.value_type = REFTABLE_REF_VAL1,\n-\t\t\t.value.val1 = hash1,\n+\t\t\t.value.val1 = { 1 },\n \t\t},\n \t\t{\n \t\t\t.refname = \"b\",\n \t\t\t.update_index = 1,\n \t\t\t.value_type = REFTABLE_REF_VAL1,\n-\t\t\t.value.val1 = hash1,\n+\t\t\t.value.val1 = { 1 },\n \t\t},\n \t\t{\n \t\t\t.refname = \"c\",\n \t\t\t.update_index = 1,\n \t\t\t.value_type = REFTABLE_REF_VAL1,\n-\t\t\t.value.val1 = hash1,\n+\t\t\t.value.val1 = { 1 },\n \t\t}\n \t};\n \tstruct reftable_ref_record r2[] = { {\n@@ -197,13 +193,13 @@ static void test_merged(void)\n \t\t\t.refname = \"c\",\n \t\t\t.update_index = 3,\n \t\t\t.value_type = REFTABLE_REF_VAL1,\n-\t\t\t.value.val1 = hash2,\n+\t\t\t.value.val1 = { 2 },\n \t\t},\n \t\t{\n \t\t\t.refname = \"d\",\n \t\t\t.update_index = 3,\n \t\t\t.value_type = REFTABLE_REF_VAL1,\n-\t\t\t.value.val1 = hash1,\n+\t\t\t.value.val1 = { 1 },\n \t\t},\n \t};\n \ndiff --git a/reftable/readwrite_test.c b/reftable/readwrite_test.c\nindex 9c16e0504e..56c0b4db5d 100644\n--- a/reftable/readwrite_test.c\n+++ b/reftable/readwrite_test.c\n@@ -60,18 +60,15 @@ static void write_table(char ***names, struct strbuf *buf, int N,\n \t*names = reftable_calloc(sizeof(char *) * (N + 1));\n \treftable_writer_set_limits(w, update_index, update_index);\n \tfor (i = 0; i < N; i++) {\n-\t\tuint8_t hash[GIT_SHA256_RAWSZ] = { 0 };\n \t\tchar name[100];\n \t\tint n;\n \n-\t\tset_test_hash(hash, i);\n-\n \t\tsnprintf(name, sizeof(name), \"refs/heads/branch%02d\", i);\n \n \t\tref.refname = name;\n \t\tref.update_index = update_index;\n \t\tref.value_type = REFTABLE_REF_VAL1;\n-\t\tref.value.val1 = hash;\n+\t\tset_test_hash(ref.value.val1, i);\n \t\t(*names)[i] = xstrdup(name);\n \n \t\tn = reftable_writer_add_ref(w, &ref);\n@@ -675,11 +672,10 @@ static void test_write_object_id_min_length(void)\n \tstruct strbuf buf = STRBUF_INIT;\n \tstruct reftable_writer *w =\n \t\treftable_new_writer(&strbuf_add_void, &buf, &opts);\n-\tuint8_t hash[GIT_SHA1_RAWSZ] = {42};\n \tstruct reftable_ref_record ref = {\n \t\t.update_index = 1,\n \t\t.value_type = REFTABLE_REF_VAL1,\n-\t\t.value.val1 = hash,\n+\t\t.value.val1 = {42},\n \t};\n \tint err;\n \tint i;\n@@ -711,11 +707,10 @@ static void test_write_object_id_length(void)\n \tstruct strbuf buf = STRBUF_INIT;\n \tstruct reftable_writer *w =\n \t\treftable_new_writer(&strbuf_add_void, &buf, &opts);\n-\tuint8_t hash[GIT_SHA1_RAWSZ] = {42};\n \tstruct reftable_ref_record ref = {\n \t\t.update_index = 1,\n \t\t.value_type = REFTABLE_REF_VAL1,\n-\t\t.value.val1 = hash,\n+\t\t.value.val1 = {42},\n \t};\n \tint err;\n \tint i;\ndiff --git a/reftable/record.c b/reftable/record.c\nindex 5e258c734b..a67a6b4d8a 100644\n--- a/reftable/record.c\n+++ b/reftable/record.c\n@@ -219,7 +219,6 @@ static void reftable_ref_record_copy_from(void *rec, const void *src_rec,\n \tcase REFTABLE_REF_DELETION:\n \t\tbreak;\n \tcase REFTABLE_REF_VAL1:\n-\t\tref->value.val1 = reftable_malloc(hash_size);\n \t\tmemcpy(ref->value.val1, src->value.val1, hash_size);\n \t\tbreak;\n \tcase REFTABLE_REF_VAL2:\n@@ -303,7 +302,6 @@ void reftable_ref_record_release(struct reftable_ref_record *ref)\n \t\treftable_free(ref->value.val2.value);\n \t\tbreak;\n \tcase REFTABLE_REF_VAL1:\n-\t\treftable_free(ref->value.val1);\n \t\tbreak;\n \tcase REFTABLE_REF_DELETION:\n \t\tbreak;\n@@ -394,7 +392,6 @@ static int reftable_ref_record_decode(void *rec, struct strbuf key,\n \t\t\treturn -1;\n \t\t}\n \n-\t\tr->value.val1 = reftable_malloc(hash_size);\n \t\tmemcpy(r->value.val1, in.buf, hash_size);\n \t\tstring_view_consume(&in, hash_size);\n \t\tbreak;\ndiff --git a/reftable/record_test.c b/reftable/record_test.c\nindex 70ae78feca..5c94d26e35 100644\n--- a/reftable/record_test.c\n+++ b/reftable/record_test.c\n@@ -119,7 +119,6 @@ static void test_reftable_ref_record_roundtrip(void)\n \t\tcase REFTABLE_REF_DELETION:\n \t\t\tbreak;\n \t\tcase REFTABLE_REF_VAL1:\n-\t\t\tin.u.ref.value.val1 = reftable_malloc(GIT_SHA1_RAWSZ);\n \t\t\tset_hash(in.u.ref.value.val1, 1);\n \t\t\tbreak;\n \t\tcase REFTABLE_REF_VAL2:\ndiff --git a/reftable/reftable-record.h b/reftable/reftable-record.h\nindex f7eb2d6015..44b5125445 100644\n--- a/reftable/reftable-record.h\n+++ b/reftable/reftable-record.h\n@@ -38,7 +38,7 @@ struct reftable_ref_record {\n #define REFTABLE_NR_REF_VALUETYPES 4\n \t} value_type;\n \tunion {\n-\t\tuint8_t *val1; /* malloced hash. */\n+\t\tunsigned char val1[GIT_MAX_RAWSZ];\n \t\tstruct {\n \t\t\tuint8_t *value; /* first value, malloced hash */\n \t\t\tuint8_t *target_value; /* second value, malloced hash */\ndiff --git a/reftable/stack_test.c b/reftable/stack_test.c\nindex 14a3fc11ee..feab49d7f7 100644\n--- a/reftable/stack_test.c\n+++ b/reftable/stack_test.c\n@@ -463,7 +463,6 @@ static void test_reftable_stack_add(void)\n \t\trefs[i].refname = xstrdup(buf);\n \t\trefs[i].update_index = i + 1;\n \t\trefs[i].value_type = REFTABLE_REF_VAL1;\n-\t\trefs[i].value.val1 = reftable_malloc(GIT_SHA1_RAWSZ);\n \t\tset_test_hash(refs[i].value.val1, i);\n \n \t\tlogs[i].refname = xstrdup(buf);\n@@ -600,7 +599,6 @@ static void test_reftable_stack_tombstone(void)\n \t\trefs[i].update_index = i + 1;\n \t\tif (i % 2 == 0) {\n \t\t\trefs[i].value_type = REFTABLE_REF_VAL1;\n-\t\t\trefs[i].value.val1 = reftable_malloc(GIT_SHA1_RAWSZ);\n \t\t\tset_test_hash(refs[i].value.val1, i);\n \t\t}\n \n-- \n2.43.GIT\n\n"},{"id":"485844","messageId":"49f13c123f211c0cf4b22316a326930ee5852c38.1703063544.git.ps@pks.im","threadId":"60638","inReplyTo":"cover.1703063544.git.ps@pks.im","subject":"[PATCH 5/7] reftable/record: store \"val2\" hashes as static arrays","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2023-12-20T09:17:22Z","receivedAt":"2023-12-20T09:17:25Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"Similar to the preceding commit, convert ref records of type \"val2\" to\nstore their object IDs in static arrays instead of allocating them for\nevery single record.\n\nWe're using the same benchmark as in the preceding commit, with `git\nshow-ref --quiet` in a repository with ~350k refs. This time around\nthough the effects aren't this huge. Before:\n\n HEAP SUMMARY:\n in use at exit: 21,163 bytes in 193 blocks\n total heap usage: 1,419,040 allocs, 1,418,847 frees, 62,153,868 bytes allocated\n\nAfter:\n\n HEAP SUMMARY:\n in use at exit: 21,163 bytes in 193 blocks\n total heap usage: 1,410,148 allocs, 1,409,955 frees, 61,976,068 bytes allocated\n\nThis is because \"val2\"-type records are typically only stored for peeled\ntags, and the number of annotated tags in the benchmark repository is\nrather low. Still, it can be seen that this change leads to a reduction\nof allocations overall, even if only a small one.\n\nSigned-off-by: Patrick Steinhardt \n---\n reftable/readwrite_test.c | 12 ++++--------\n reftable/record.c | 6 ------\n reftable/record_test.c | 4 ----\n reftable/reftable-record.h | 4 ++--\n 4 files changed, 6 insertions(+), 20 deletions(-)\n\ndiff --git a/reftable/readwrite_test.c b/reftable/readwrite_test.c\nindex 56c0b4db5d..900afc1b70 100644\n--- a/reftable/readwrite_test.c\n+++ b/reftable/readwrite_test.c\n@@ -547,8 +547,6 @@ static void test_table_refs_for(int indexed)\n \t\tuint8_t hash[GIT_SHA1_RAWSZ];\n \t\tchar fill[51] = { 0 };\n \t\tchar name[100];\n-\t\tuint8_t hash1[GIT_SHA1_RAWSZ];\n-\t\tuint8_t hash2[GIT_SHA1_RAWSZ];\n \t\tstruct reftable_ref_record ref = { NULL };\n \n \t\tmemset(hash, i, sizeof(hash));\n@@ -558,11 +556,9 @@ static void test_table_refs_for(int indexed)\n \t\tname[40] = 0;\n \t\tref.refname = name;\n \n-\t\tset_test_hash(hash1, i / 4);\n-\t\tset_test_hash(hash2, 3 + i / 4);\n \t\tref.value_type = REFTABLE_REF_VAL2;\n-\t\tref.value.val2.value = hash1;\n-\t\tref.value.val2.target_value = hash2;\n+\t\tset_test_hash(ref.value.val2.value, i / 4);\n+\t\tset_test_hash(ref.value.val2.target_value, 3 + i / 4);\n \n \t\t/* 80 bytes / entry, so 3 entries per block. Yields 17\n \t\t */\n@@ -570,8 +566,8 @@ static void test_table_refs_for(int indexed)\n \t\tn = reftable_writer_add_ref(w, &ref);\n \t\tEXPECT(n == 0);\n \n-\t\tif (!memcmp(hash1, want_hash, GIT_SHA1_RAWSZ) ||\n-\t\t !memcmp(hash2, want_hash, GIT_SHA1_RAWSZ)) {\n+\t\tif (!memcmp(ref.value.val2.value, want_hash, GIT_SHA1_RAWSZ) ||\n+\t\t !memcmp(ref.value.val2.target_value, want_hash, GIT_SHA1_RAWSZ)) {\n \t\t\twant_names[want_names_len++] = xstrdup(name);\n \t\t}\n \t}\ndiff --git a/reftable/record.c b/reftable/record.c\nindex a67a6b4d8a..5c3fbb7b2a 100644\n--- a/reftable/record.c\n+++ b/reftable/record.c\n@@ -222,9 +222,7 @@ static void reftable_ref_record_copy_from(void *rec, const void *src_rec,\n \t\tmemcpy(ref->value.val1, src->value.val1, hash_size);\n \t\tbreak;\n \tcase REFTABLE_REF_VAL2:\n-\t\tref->value.val2.value = reftable_malloc(hash_size);\n \t\tmemcpy(ref->value.val2.value, src->value.val2.value, hash_size);\n-\t\tref->value.val2.target_value = reftable_malloc(hash_size);\n \t\tmemcpy(ref->value.val2.target_value,\n \t\t src->value.val2.target_value, hash_size);\n \t\tbreak;\n@@ -298,8 +296,6 @@ void reftable_ref_record_release(struct reftable_ref_record *ref)\n \t\treftable_free(ref->value.symref);\n \t\tbreak;\n \tcase REFTABLE_REF_VAL2:\n-\t\treftable_free(ref->value.val2.target_value);\n-\t\treftable_free(ref->value.val2.value);\n \t\tbreak;\n \tcase REFTABLE_REF_VAL1:\n \t\tbreak;\n@@ -401,11 +397,9 @@ static int reftable_ref_record_decode(void *rec, struct strbuf key,\n \t\t\treturn -1;\n \t\t}\n \n-\t\tr->value.val2.value = reftable_malloc(hash_size);\n \t\tmemcpy(r->value.val2.value, in.buf, hash_size);\n \t\tstring_view_consume(&in, hash_size);\n \n-\t\tr->value.val2.target_value = reftable_malloc(hash_size);\n \t\tmemcpy(r->value.val2.target_value, in.buf, hash_size);\n \t\tstring_view_consume(&in, hash_size);\n \t\tbreak;\ndiff --git a/reftable/record_test.c b/reftable/record_test.c\nindex 5c94d26e35..2876db7d27 100644\n--- a/reftable/record_test.c\n+++ b/reftable/record_test.c\n@@ -122,11 +122,7 @@ static void test_reftable_ref_record_roundtrip(void)\n \t\t\tset_hash(in.u.ref.value.val1, 1);\n \t\t\tbreak;\n \t\tcase REFTABLE_REF_VAL2:\n-\t\t\tin.u.ref.value.val2.value =\n-\t\t\t\treftable_malloc(GIT_SHA1_RAWSZ);\n \t\t\tset_hash(in.u.ref.value.val2.value, 1);\n-\t\t\tin.u.ref.value.val2.target_value =\n-\t\t\t\treftable_malloc(GIT_SHA1_RAWSZ);\n \t\t\tset_hash(in.u.ref.value.val2.target_value, 2);\n \t\t\tbreak;\n \t\tcase REFTABLE_REF_SYMREF:\ndiff --git a/reftable/reftable-record.h b/reftable/reftable-record.h\nindex 44b5125445..83d252ec2c 100644\n--- a/reftable/reftable-record.h\n+++ b/reftable/reftable-record.h\n@@ -40,8 +40,8 @@ struct reftable_ref_record {\n \tunion {\n \t\tunsigned char val1[GIT_MAX_RAWSZ];\n \t\tstruct {\n-\t\t\tuint8_t *value; /* first value, malloced hash */\n-\t\t\tuint8_t *target_value; /* second value, malloced hash */\n+\t\t\tunsigned char value[GIT_MAX_RAWSZ]; /* first hash */\n+\t\t\tunsigned char target_value[GIT_MAX_RAWSZ]; /* second hash */\n \t\t} val2;\n \t\tchar *symref; /* referent, malloced 0-terminated string */\n \t} value;\n-- \n2.43.GIT\n\n"},{"id":"485845","messageId":"32b7ddee28243922ae2754ec69252ff87635202a.1703063544.git.ps@pks.im","threadId":"60638","inReplyTo":"cover.1703063544.git.ps@pks.im","subject":"[PATCH 6/7] reftable/merged: really reuse buffers to compute record keys","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2023-12-20T09:17:26Z","receivedAt":"2023-12-20T09:17:29Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"In 829231dc20 (reftable/merged: reuse buffer to compute record keys,\n2023-12-11), we have refactored the merged iterator to reuse a set of\nbuffers that it would otherwise have to reallocate on every single\niteration. Unfortunately, there was a brown-paper-bag-style bug here as\nwe continue to release these buffers after the iteration, and thus we\nhave essentially gained nothing.\n\nFix this performance issue by not releasing those buffers on iteration\nanymore, where we instead rely on `merged_iter_close()` to release the\nbuffers for us.\n\nUsing `git show-ref --quiet` in a repository with ~350k refs this leads\nto a significant drop in allocations. Before:\n\n HEAP SUMMARY:\n in use at exit: 21,163 bytes in 193 blocks\n total heap usage: 1,410,148 allocs, 1,409,955 frees, 61,976,068 bytes allocated\n\nAfter:\n\n HEAP SUMMARY:\n in use at exit: 21,163 bytes in 193 blocks\n total heap usage: 708,058 allocs, 707,865 frees, 36,783,255 bytes allocated\n\nSigned-off-by: Patrick Steinhardt \n---\n reftable/merged.c | 2 --\n 1 file changed, 2 deletions(-)\n\ndiff --git a/reftable/merged.c b/reftable/merged.c\nindex 556bb5c556..a28bb99aaf 100644\n--- a/reftable/merged.c\n+++ b/reftable/merged.c\n@@ -128,8 +128,6 @@ static int merged_iter_next_entry(struct merged_iter *mi,\n \n done:\n \treftable_record_release(&entry.rec);\n-\tstrbuf_release(&mi->entry_key);\n-\tstrbuf_release(&mi->key);\n \treturn err;\n }\n \n-- \n2.43.GIT\n\n"},{"id":"485846","messageId":"3dbabea22a2fca6b9eeddde26da664e50ccfddab.1703063544.git.ps@pks.im","threadId":"60638","inReplyTo":"cover.1703063544.git.ps@pks.im","subject":"[PATCH 7/7] reftable/merged: transfer ownership of records when iterating","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2023-12-20T09:17:31Z","receivedAt":"2023-12-20T09:17:34Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"When iterating over recods with the merged iterator we put the records\ninto a priority queue before yielding them to the caller. This means\nthat we need to allocate the contents of these records before we can\npass them over to the caller.\n\nThe handover to the caller is quite inefficient though because we first\ndeallocate the record passed in by the caller and then copy over the new\nrecord, which requires us to reallocate memory.\n\nRefactor the code to instead transfer ownership of the new record to the\ncaller. So instead of reallocating all contents, we now release the old\nrecord and then copy contents of the new record into place.\n\nThe following benchmark of `git show-ref --quiet` in a repository with\naround 350k refs shows a clear improvement. Before:\n\n HEAP SUMMARY:\n in use at exit: 21,163 bytes in 193 blocks\n total heap usage: 708,058 allocs, 707,865 frees, 36,783,255 bytes allocated\n\nAfter:\n\n HEAP SUMMARY:\n in use at exit: 21,163 bytes in 193 blocks\n total heap usage: 357,007 allocs, 356,814 frees, 24,193,602 bytes allocated\n\nThis shows that we now have roundabout a single allocation per record\nthat we're yielding from the iterator. Ideally, we'd also get rid of\nthis allocation so that the number of allocations doesn't scale with the\nnumber of refs anymore. This would require some larger surgery though\nbecause the memory is owned by the priority queue before transferring it\nover to the caller.\n\nSigned-off-by: Patrick Steinhardt \n---\n reftable/merged.c | 6 ++++--\n 1 file changed, 4 insertions(+), 2 deletions(-)\n\ndiff --git a/reftable/merged.c b/reftable/merged.c\nindex a28bb99aaf..a52914d667 100644\n--- a/reftable/merged.c\n+++ b/reftable/merged.c\n@@ -124,10 +124,12 @@ static int merged_iter_next_entry(struct merged_iter *mi,\n \t\treftable_record_release(&top.rec);\n \t}\n \n-\treftable_record_copy_from(rec, &entry.rec, hash_size(mi->hash_id));\n+\treftable_record_release(rec);\n+\t*rec = entry.rec;\n \n done:\n-\treftable_record_release(&entry.rec);\n+\tif (err)\n+\t\treftable_record_release(&entry.rec);\n \treturn err;\n }\n \n-- \n2.43.GIT\n\n"},{"id":"485847","messageId":"ZYKy-nnZ3xjXwUmV@tanuki","threadId":"60638","inReplyTo":"06c9eab67802ba933b44d32f5c8d11fddc216c26.1703063544.git.ps@pks.im","subject":"Re: [PATCH 4/7] reftable/record: store \"val1\" hashes as static arrays","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2023-12-20T09:25:14Z","receivedAt":"2023-12-20T09:25:18Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"On Wed, Dec 20, 2023 at 10:17:17AM +0100, Patrick Steinhardt wrote:\n> When reading ref records of type \"val1\" we store its object ID in an\n> allocated array. This results in an additional allocation for every\n> single ref record we read, which is rather inefficient especially when\n> iterating over refs.\n> \n> Refactor the code to instead use a static array of `GIT_MAX_RAWSZ`\n> bytes. While this means that `struct ref_record` is bigger now, we\n> typically do not store all refs in an array anyway and instead only\n> handle a limited number of records at the same point in time.\n> \n> Using `git show-ref --quiet` in a repository with ~350k refs this leads\n> to a significant drop in allocations. Before:\n> \n> HEAP SUMMARY:\n> in use at exit: 21,098 bytes in 192 blocks\n> total heap usage: 2,116,683 allocs, 2,116,491 frees, 76,098,060 bytes allocated\n> \n> After:\n> \n> HEAP SUMMARY:\n> in use at exit: 21,098 bytes in 192 blocks\n> total heap usage: 1,419,031 allocs, 1,418,839 frees, 62,145,036 bytes allocated\n> \n> Signed-off-by: Patrick Steinhardt \n\nI screwed up the rebase. The following diff is required on top:\n\ndiff --git a/reftable/readwrite_test.c b/reftable/readwrite_test.c\nindex 56c0b4db5d..87b238105c 100644\n--- a/reftable/readwrite_test.c\n+++ b/reftable/readwrite_test.c\n@@ -809,11 +809,10 @@ static void test_write_multiple_indices(void)\n \twriter = reftable_new_writer(&strbuf_add_void, &writer_buf, &opts);\n \treftable_writer_set_limits(writer, 1, 1);\n \tfor (i = 0; i < 100; i++) {\n-\t\tunsigned char hash[GIT_SHA1_RAWSZ] = {i};\n \t\tstruct reftable_ref_record ref = {\n \t\t\t.update_index = 1,\n \t\t\t.value_type = REFTABLE_REF_VAL1,\n-\t\t\t.value.val1 = hash,\n+\t\t\t.value.val1 = {i},\n \t\t};\n \n \t\tstrbuf_reset(&buf);\n\nWill fix in v2 of this series.\n\nPatrick\n"},{"id":"485883","messageId":"xmqqr0jgsn9g.fsf@gitster.g","threadId":"60638","inReplyTo":"cover.1703063544.git.ps@pks.im","subject":"Re: [PATCH 0/7] reftable: fixes and optimizations (pt.2)","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2023-12-20T19:10:51Z","receivedAt":"2023-12-20T19:10:57Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Patrick Steinhardt writes:\n\n> Patrick Steinhardt (7):\n> reftable/stack: do not overwrite errors when compacting\n> reftable/writer: fix index corruption when writing multiple indices\n> reftable/record: constify some parts of the interface\n> reftable/record: store \"val1\" hashes as static arrays\n> reftable/record: store \"val2\" hashes as static arrays\n> reftable/merged: really reuse buffers to compute record keys\n> reftable/merged: transfer ownership of records when iterating\n\nSomething like this need to be split and sprinkled into relevant\nsteps in v2 in order to pass \"make hdr-check\", it seems.\n\n reftable/reftable-record.h | 1 +\n reftable/reftable-stack.h | 1 +\n 2 files changed, 2 insertions(+)\n\ndiff --git c/reftable/reftable-record.h w/reftable/reftable-record.h\nindex 83d252ec2c..fd1160615c 100644\n--- c/reftable/reftable-record.h\n+++ w/reftable/reftable-record.h\n@@ -9,6 +9,7 @@ license that can be found in the LICENSE file or at\n #ifndef REFTABLE_RECORD_H\n #define REFTABLE_RECORD_H\n \n+#include \n #include \n \n /*\ndiff --git c/reftable/reftable-stack.h w/reftable/reftable-stack.h\nindex 1b602dda58..50b1a4f4dd 100644\n--- c/reftable/reftable-stack.h\n+++ w/reftable/reftable-stack.h\n@@ -9,6 +9,7 @@ license that can be found in the LICENSE file or at\n #ifndef REFTABLE_STACK_H\n #define REFTABLE_STACK_H\n \n+#include \n #include \"reftable-writer.h\"\n \n /*\n"},{"id":"486079","messageId":"cover.1703743174.git.ps@pks.im","threadId":"60638","inReplyTo":"cover.1703063544.git.ps@pks.im","subject":"[PATCH v2 0/8] reftable: fixes and optimizations (pt.2)","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2023-12-28T06:27:32Z","receivedAt":"2023-12-28T06:27:38Z","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 contains additional\nfixes and optimizations for the reftable library. Changes compared to\nv1:\n\n - Added a patch to not auto-compact twice in `reftable_stack_add()`,\n reported by Han-Wen.\n\n - Fixed an issue I've previously introduced while rebasing the patch\n series.\n\n - Fixed a missing header, as reported by Junio.\n\nDue to the added patch that avoids double auto-compaction this patch\nseries now depends on 637e34a783 (Merge branch 'ps/reftable-fixes',\n2023-12-27).\n\nPatrick\n\nPatrick Steinhardt (8):\n reftable/stack: do not overwrite errors when compacting\n reftable/stack: do not auto-compact twice in `reftable_stack_add()`\n reftable/writer: fix index corruption when writing multiple indices\n reftable/record: constify some parts of the interface\n reftable/record: store \"val1\" hashes as static arrays\n reftable/record: store \"val2\" hashes as static arrays\n reftable/merged: really reuse buffers to compute record keys\n reftable/merged: transfer ownership of records when iterating\n\n reftable/block_test.c | 4 +-\n reftable/merged.c | 8 +--\n reftable/merged_test.c | 16 +++---\n reftable/readwrite_test.c | 102 +++++++++++++++++++++++++++++++------\n reftable/record.c | 17 ++-----\n reftable/record_test.c | 5 --\n reftable/reftable-record.h | 11 ++--\n reftable/stack.c | 23 +++------\n reftable/stack_test.c | 2 -\n reftable/writer.c | 4 +-\n 10 files changed, 117 insertions(+), 75 deletions(-)\n\nRange-diff against v1:\n1: 573fb2c4fb = 1: 22a57020c6 reftable/stack: do not overwrite errors when compacting\n-: ---------- > 2: a08f7efc99 reftable/stack: do not auto-compact twice in `reftable_stack_add()`\n2: 86ee79c48d = 3: c00e08d97f reftable/writer: fix index corruption when writing multiple indices\n3: 3ad4a0e5b9 = 4: 3416268087 reftable/record: constify some parts of the interface\n4: 06c9eab678 ! 5: 46ca3a37f8 reftable/record: store \"val1\" hashes as static arrays\n @@ reftable/readwrite_test.c: static void test_write_object_id_length(void)\n \t};\n \tint err;\n \tint i;\n +@@ reftable/readwrite_test.c: static void test_write_multiple_indices(void)\n + \twriter = reftable_new_writer(&strbuf_add_void, &writer_buf, &opts);\n + \treftable_writer_set_limits(writer, 1, 1);\n + \tfor (i = 0; i < 100; i++) {\n +-\t\tunsigned char hash[GIT_SHA1_RAWSZ] = {i};\n + \t\tstruct reftable_ref_record ref = {\n + \t\t\t.update_index = 1,\n + \t\t\t.value_type = REFTABLE_REF_VAL1,\n +-\t\t\t.value.val1 = hash,\n ++\t\t\t.value.val1 = {i},\n + \t\t};\n + \n + \t\tstrbuf_reset(&buf);\n \n ## reftable/record.c ##\n @@ reftable/record.c: static void reftable_ref_record_copy_from(void *rec, const void *src_rec,\n @@ reftable/record_test.c: static void test_reftable_ref_record_roundtrip(void)\n \t\tcase REFTABLE_REF_VAL2:\n \n ## reftable/reftable-record.h ##\n +@@ reftable/reftable-record.h: license that can be found in the LICENSE file or at\n + #ifndef REFTABLE_RECORD_H\n + #define REFTABLE_RECORD_H\n + \n ++#include \"hash-ll.h\"\n + #include \n + \n + /*\n @@ reftable/reftable-record.h: struct reftable_ref_record {\n #define REFTABLE_NR_REF_VALUETYPES 4\n \t} value_type;\n5: 49f13c123f = 6: c8a36917b1 reftable/record: store \"val2\" hashes as static arrays\n6: 32b7ddee28 = 7: 6313f8affd reftable/merged: really reuse buffers to compute record keys\n7: 3dbabea22a = 8: 25a3919e58 reftable/merged: transfer ownership of records when iterating\n\n-- \n2.43.GIT\n\n"},{"id":"486080","messageId":"22a57020c66551f1828b56cfccda97f1c77117dc.1703743174.git.ps@pks.im","threadId":"60638","inReplyTo":"cover.1703743174.git.ps@pks.im","subject":"[PATCH v2 1/8] reftable/stack: do not overwrite errors when compacting","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2023-12-28T06:27:37Z","receivedAt":"2023-12-28T06:27:40Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"In order to compact multiple stacks we iterate through the merged ref\nand log records. When there is any error either when reading the records\nfrom the old merged table or when writing the records to the new table\nthen we break out of the respective loops. When breaking out of the loop\nfor the ref records though the error code will be overwritten, which may\ncause us to inadvertently skip over bad ref records. In the worst case,\nthis can lead to a compacted stack that is missing records.\n\nFix the code by using `goto done` instead so that any potential error\ncodes are properly returned to the caller.\n\nSigned-off-by: Patrick Steinhardt \n---\n reftable/stack.c | 20 ++++++++------------\n 1 file changed, 8 insertions(+), 12 deletions(-)\n\ndiff --git a/reftable/stack.c b/reftable/stack.c\nindex 16bab82063..8729508dc3 100644\n--- a/reftable/stack.c\n+++ b/reftable/stack.c\n@@ -801,18 +801,16 @@ static int stack_write_compact(struct reftable_stack *st,\n \t\t\terr = 0;\n \t\t\tbreak;\n \t\t}\n-\t\tif (err < 0) {\n-\t\t\tbreak;\n-\t\t}\n+\t\tif (err < 0)\n+\t\t\tgoto done;\n \n \t\tif (first == 0 && reftable_ref_record_is_deletion(&ref)) {\n \t\t\tcontinue;\n \t\t}\n \n \t\terr = reftable_writer_add_ref(wr, &ref);\n-\t\tif (err < 0) {\n-\t\t\tbreak;\n-\t\t}\n+\t\tif (err < 0)\n+\t\t\tgoto done;\n \t\tentries++;\n \t}\n \treftable_iterator_destroy(&it);\n@@ -827,9 +825,8 @@ static int stack_write_compact(struct reftable_stack *st,\n \t\t\terr = 0;\n \t\t\tbreak;\n \t\t}\n-\t\tif (err < 0) {\n-\t\t\tbreak;\n-\t\t}\n+\t\tif (err < 0)\n+\t\t\tgoto done;\n \t\tif (first == 0 && reftable_log_record_is_deletion(&log)) {\n \t\t\tcontinue;\n \t\t}\n@@ -845,9 +842,8 @@ static int stack_write_compact(struct reftable_stack *st,\n \t\t}\n \n \t\terr = reftable_writer_add_log(wr, &log);\n-\t\tif (err < 0) {\n-\t\t\tbreak;\n-\t\t}\n+\t\tif (err < 0)\n+\t\t\tgoto done;\n \t\tentries++;\n \t}\n \n-- \n2.43.GIT\n\n"},{"id":"486081","messageId":"a08f7efc992538e88803b157c142a55df65a1a81.1703743174.git.ps@pks.im","threadId":"60638","inReplyTo":"cover.1703743174.git.ps@pks.im","subject":"[PATCH v2 2/8] reftable/stack: do not auto-compact twice in `reftable_stack_add()`","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2023-12-28T06:27:41Z","receivedAt":"2023-12-28T06:27:44Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"In 5c086453ff (reftable/stack: perform auto-compaction with\ntransactional interface, 2023-12-11), we fixed a bug where the\ntransactional interface to add changes to a reftable stack did not\nperform auto-compaction by calling `reftable_stack_auto_compact()` in\n`reftable_stack_addition_commit()`. While correct, this change may now\ncause us to perform auto-compaction twice in the non-transactional\ninterface `reftable_stack_add()`:\n\n - It performs auto-compaction by itself.\n\n - It now transitively performs auto-compaction via the transactional\n interface.\n\nRemove the first instance so that we only end up doing auto-compaction\nonce.\n\nReported-by: Han-Wen Nienhuys \nSigned-off-by: Patrick Steinhardt \n---\n reftable/stack.c | 3 ---\n 1 file changed, 3 deletions(-)\n\ndiff --git a/reftable/stack.c b/reftable/stack.c\nindex 8729508dc3..7ffeb3ee10 100644\n--- a/reftable/stack.c\n+++ b/reftable/stack.c\n@@ -425,9 +425,6 @@ int reftable_stack_add(struct reftable_stack *st,\n \t\treturn err;\n \t}\n \n-\tif (!st->disable_auto_compact)\n-\t\treturn reftable_stack_auto_compact(st);\n-\n \treturn 0;\n }\n \n-- \n2.43.GIT\n\n"},{"id":"486082","messageId":"c00e08d97fc71f0c879082291899ec0d47e885e3.1703743174.git.ps@pks.im","threadId":"60638","inReplyTo":"cover.1703743174.git.ps@pks.im","subject":"[PATCH v2 3/8] reftable/writer: fix index corruption when writing multiple indices","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2023-12-28T06:27:45Z","receivedAt":"2023-12-28T06:27:48Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"Each reftable may contain multiple types of blocks for refs, objects and\nreflog records, where each of these may have an index that makes it more\nefficient to find the records. It was observed that the index for log\nrecords can become corrupted under certain circumstances, where the\nfirst entry of the index points into the object index instead of to the\nlog records.\n\nAs it turns out, this corruption can occur whenever we write a log index\nas well as at least one additional index. Writing records and their index\nis basically a two-step process:\n\n 1. We write all blocks for the corresponding record. Each block that\n gets written is added to a list of blocks to index.\n\n 2. Once all blocks were written we finish the section. If at least two\n blocks have been added to the list of blocks to index then we will\n now write the index for those blocks and flush it, as well.\n\nWhen we have a very large number of blocks then we may decide to write a\nmulti-level index, which is why we also keep track of the list of the\nindex blocks in the same way as we previously kept track of the blocks\nto index.\n\nNow when we have finished writing all index blocks we clear the index\nand flush the last block to disk. This is done in the wrong order though\nbecause flushing the block to disk will re-add it to the list of blocks\nto be indexed. The result is that the next section we are about to write\nwill have an entry in the list of blocks to index that points to the\nlast block of the preceding section's index, which will corrupt the log\nindex.\n\nFix this corruption by clearing the index after having written the last\nblock.\n\nSigned-off-by: Patrick Steinhardt \n---\n reftable/readwrite_test.c | 80 +++++++++++++++++++++++++++++++++++++++\n reftable/writer.c | 4 +-\n 2 files changed, 82 insertions(+), 2 deletions(-)\n\ndiff --git a/reftable/readwrite_test.c b/reftable/readwrite_test.c\nindex 278663f22d..9c16e0504e 100644\n--- a/reftable/readwrite_test.c\n+++ b/reftable/readwrite_test.c\n@@ -798,6 +798,85 @@ static void test_write_key_order(void)\n \tstrbuf_release(&buf);\n }\n \n+static void test_write_multiple_indices(void)\n+{\n+\tstruct reftable_write_options opts = {\n+\t\t.block_size = 100,\n+\t};\n+\tstruct strbuf writer_buf = STRBUF_INIT, buf = STRBUF_INIT;\n+\tstruct reftable_block_source source = { 0 };\n+\tstruct reftable_iterator it = { 0 };\n+\tconst struct reftable_stats *stats;\n+\tstruct reftable_writer *writer;\n+\tstruct reftable_reader *reader;\n+\tint err, i;\n+\n+\twriter = reftable_new_writer(&strbuf_add_void, &writer_buf, &opts);\n+\treftable_writer_set_limits(writer, 1, 1);\n+\tfor (i = 0; i < 100; i++) {\n+\t\tunsigned char hash[GIT_SHA1_RAWSZ] = {i};\n+\t\tstruct reftable_ref_record ref = {\n+\t\t\t.update_index = 1,\n+\t\t\t.value_type = REFTABLE_REF_VAL1,\n+\t\t\t.value.val1 = hash,\n+\t\t};\n+\n+\t\tstrbuf_reset(&buf);\n+\t\tstrbuf_addf(&buf, \"refs/heads/%04d\", i);\n+\t\tref.refname = buf.buf,\n+\n+\t\terr = reftable_writer_add_ref(writer, &ref);\n+\t\tEXPECT_ERR(err);\n+\t}\n+\n+\tfor (i = 0; i < 100; i++) {\n+\t\tunsigned char hash[GIT_SHA1_RAWSZ] = {i};\n+\t\tstruct reftable_log_record log = {\n+\t\t\t.update_index = 1,\n+\t\t\t.value_type = REFTABLE_LOG_UPDATE,\n+\t\t\t.value.update = {\n+\t\t\t\t.old_hash = hash,\n+\t\t\t\t.new_hash = hash,\n+\t\t\t},\n+\t\t};\n+\n+\t\tstrbuf_reset(&buf);\n+\t\tstrbuf_addf(&buf, \"refs/heads/%04d\", i);\n+\t\tlog.refname = buf.buf,\n+\n+\t\terr = reftable_writer_add_log(writer, &log);\n+\t\tEXPECT_ERR(err);\n+\t}\n+\n+\treftable_writer_close(writer);\n+\n+\t/*\n+\t * The written data should be sufficiently large to result in indices\n+\t * for each of the block types.\n+\t */\n+\tstats = reftable_writer_stats(writer);\n+\tEXPECT(stats->ref_stats.index_offset > 0);\n+\tEXPECT(stats->obj_stats.index_offset > 0);\n+\tEXPECT(stats->log_stats.index_offset > 0);\n+\n+\tblock_source_from_strbuf(&source, &writer_buf);\n+\terr = reftable_new_reader(&reader, &source, \"filename\");\n+\tEXPECT_ERR(err);\n+\n+\t/*\n+\t * Seeking the log uses the log index now. In case there is any\n+\t * confusion regarding indices we would notice here.\n+\t */\n+\terr = reftable_reader_seek_log(reader, &it, \"\");\n+\tEXPECT_ERR(err);\n+\n+\treftable_iterator_destroy(&it);\n+\treftable_writer_free(writer);\n+\treftable_reader_free(reader);\n+\tstrbuf_release(&writer_buf);\n+\tstrbuf_release(&buf);\n+}\n+\n static void test_corrupt_table_empty(void)\n {\n \tstruct strbuf buf = STRBUF_INIT;\n@@ -847,5 +926,6 @@ int readwrite_test_main(int argc, const char *argv[])\n \tRUN_TEST(test_log_overflow);\n \tRUN_TEST(test_write_object_id_length);\n \tRUN_TEST(test_write_object_id_min_length);\n+\tRUN_TEST(test_write_multiple_indices);\n \treturn 0;\n }\ndiff --git a/reftable/writer.c b/reftable/writer.c\nindex 2e322a5683..ee4590e20f 100644\n--- a/reftable/writer.c\n+++ b/reftable/writer.c\n@@ -432,12 +432,12 @@ static int writer_finish_section(struct reftable_writer *w)\n \t\treftable_free(idx);\n \t}\n \n-\twriter_clear_index(w);\n-\n \terr = writer_flush_block(w);\n \tif (err < 0)\n \t\treturn err;\n \n+\twriter_clear_index(w);\n+\n \tbstats = writer_reftable_block_stats(w, typ);\n \tbstats->index_blocks = w->stats.idx_stats.blocks - before_blocks;\n \tbstats->index_offset = index_start;\n-- \n2.43.GIT\n\n"},{"id":"486083","messageId":"3416268087d474ce45b141105367d7f606bf36a8.1703743174.git.ps@pks.im","threadId":"60638","inReplyTo":"cover.1703743174.git.ps@pks.im","subject":"[PATCH v2 4/8] reftable/record: constify some parts of the interface","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2023-12-28T06:27:50Z","receivedAt":"2023-12-28T06:27:53Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"We're about to convert reftable records to stop storing their object IDs\nas allocated hashes. Prepare for this refactoring by constifying some\nparts of the interface that will be impacted by this.\n\nSigned-off-by: Patrick Steinhardt \n---\n reftable/record.c | 8 ++++----\n reftable/reftable-record.h | 4 ++--\n 2 files changed, 6 insertions(+), 6 deletions(-)\n\ndiff --git a/reftable/record.c b/reftable/record.c\nindex fbaa1fbef5..5e258c734b 100644\n--- a/reftable/record.c\n+++ b/reftable/record.c\n@@ -76,7 +76,7 @@ int reftable_is_block_type(uint8_t typ)\n \treturn 0;\n }\n \n-uint8_t *reftable_ref_record_val1(const struct reftable_ref_record *rec)\n+const unsigned char *reftable_ref_record_val1(const struct reftable_ref_record *rec)\n {\n \tswitch (rec->value_type) {\n \tcase REFTABLE_REF_VAL1:\n@@ -88,7 +88,7 @@ uint8_t *reftable_ref_record_val1(const struct reftable_ref_record *rec)\n \t}\n }\n \n-uint8_t *reftable_ref_record_val2(const struct reftable_ref_record *rec)\n+const unsigned char *reftable_ref_record_val2(const struct reftable_ref_record *rec)\n {\n \tswitch (rec->value_type) {\n \tcase REFTABLE_REF_VAL2:\n@@ -242,7 +242,7 @@ static char hexdigit(int c)\n \treturn 'a' + (c - 10);\n }\n \n-static void hex_format(char *dest, uint8_t *src, int hash_size)\n+static void hex_format(char *dest, const unsigned char *src, int hash_size)\n {\n \tassert(hash_size > 0);\n \tif (src) {\n@@ -1164,7 +1164,7 @@ int reftable_record_equal(struct reftable_record *a, struct reftable_record *b,\n \t\treftable_record_data(a), reftable_record_data(b), hash_size);\n }\n \n-static int hash_equal(uint8_t *a, uint8_t *b, int hash_size)\n+static int hash_equal(const unsigned char *a, const unsigned char *b, int hash_size)\n {\n \tif (a && b)\n \t\treturn !memcmp(a, b, hash_size);\ndiff --git a/reftable/reftable-record.h b/reftable/reftable-record.h\nindex 67104f8fbf..f7eb2d6015 100644\n--- a/reftable/reftable-record.h\n+++ b/reftable/reftable-record.h\n@@ -49,11 +49,11 @@ struct reftable_ref_record {\n \n /* Returns the first hash, or NULL if `rec` is not of type\n * REFTABLE_REF_VAL1 or REFTABLE_REF_VAL2. */\n-uint8_t *reftable_ref_record_val1(const struct reftable_ref_record *rec);\n+const unsigned char *reftable_ref_record_val1(const struct reftable_ref_record *rec);\n \n /* Returns the second hash, or NULL if `rec` is not of type\n * REFTABLE_REF_VAL2. */\n-uint8_t *reftable_ref_record_val2(const struct reftable_ref_record *rec);\n+const unsigned char *reftable_ref_record_val2(const struct reftable_ref_record *rec);\n \n /* returns whether 'ref' represents a deletion */\n int reftable_ref_record_is_deletion(const struct reftable_ref_record *ref);\n-- \n2.43.GIT\n\n"},{"id":"486084","messageId":"46ca3a37f805cd36faa26927220c2793d4cdd561.1703743174.git.ps@pks.im","threadId":"60638","inReplyTo":"cover.1703743174.git.ps@pks.im","subject":"[PATCH v2 5/8] reftable/record: store \"val1\" hashes as static arrays","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2023-12-28T06:27:55Z","receivedAt":"2023-12-28T06:27:59Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"When reading ref records of type \"val1\" we store its object ID in an\nallocated array. This results in an additional allocation for every\nsingle ref record we read, which is rather inefficient especially when\niterating over refs.\n\nRefactor the code to instead use a static array of `GIT_MAX_RAWSZ`\nbytes. While this means that `struct ref_record` is bigger now, we\ntypically do not store all refs in an array anyway and instead only\nhandle a limited number of records at the same point in time.\n\nUsing `git show-ref --quiet` in a repository with ~350k refs this leads\nto a significant drop in allocations. Before:\n\n HEAP SUMMARY:\n in use at exit: 21,098 bytes in 192 blocks\n total heap usage: 2,116,683 allocs, 2,116,491 frees, 76,098,060 bytes allocated\n\nAfter:\n\n HEAP SUMMARY:\n in use at exit: 21,098 bytes in 192 blocks\n total heap usage: 1,419,031 allocs, 1,418,839 frees, 62,145,036 bytes allocated\n\nSigned-off-by: Patrick Steinhardt \n---\n reftable/block_test.c | 4 +---\n reftable/merged_test.c | 16 ++++++----------\n reftable/readwrite_test.c | 14 ++++----------\n reftable/record.c | 3 ---\n reftable/record_test.c | 1 -\n reftable/reftable-record.h | 3 ++-\n reftable/stack_test.c | 2 --\n 7 files changed, 13 insertions(+), 30 deletions(-)\n\ndiff --git a/reftable/block_test.c b/reftable/block_test.c\nindex c00bbc8aed..dedb05c7d8 100644\n--- a/reftable/block_test.c\n+++ b/reftable/block_test.c\n@@ -49,13 +49,11 @@ static void test_block_read_write(void)\n \n \tfor (i = 0; i < N; i++) {\n \t\tchar name[100];\n-\t\tuint8_t hash[GIT_SHA1_RAWSZ];\n \t\tsnprintf(name, sizeof(name), \"branch%02d\", i);\n-\t\tmemset(hash, i, sizeof(hash));\n \n \t\trec.u.ref.refname = name;\n \t\trec.u.ref.value_type = REFTABLE_REF_VAL1;\n-\t\trec.u.ref.value.val1 = hash;\n+\t\tmemset(rec.u.ref.value.val1, i, GIT_SHA1_RAWSZ);\n \n \t\tnames[i] = xstrdup(name);\n \t\tn = block_writer_add(&bw, &rec);\ndiff --git a/reftable/merged_test.c b/reftable/merged_test.c\nindex d08c16abef..b3927a5d73 100644\n--- a/reftable/merged_test.c\n+++ b/reftable/merged_test.c\n@@ -123,13 +123,11 @@ static void readers_destroy(struct reftable_reader **readers, size_t n)\n \n static void test_merged_between(void)\n {\n-\tuint8_t hash1[GIT_SHA1_RAWSZ] = { 1, 2, 3, 0 };\n-\n \tstruct reftable_ref_record r1[] = { {\n \t\t.refname = \"b\",\n \t\t.update_index = 1,\n \t\t.value_type = REFTABLE_REF_VAL1,\n-\t\t.value.val1 = hash1,\n+\t\t.value.val1 = { 1, 2, 3, 0 },\n \t} };\n \tstruct reftable_ref_record r2[] = { {\n \t\t.refname = \"a\",\n@@ -165,26 +163,24 @@ static void test_merged_between(void)\n \n static void test_merged(void)\n {\n-\tuint8_t hash1[GIT_SHA1_RAWSZ] = { 1 };\n-\tuint8_t hash2[GIT_SHA1_RAWSZ] = { 2 };\n \tstruct reftable_ref_record r1[] = {\n \t\t{\n \t\t\t.refname = \"a\",\n \t\t\t.update_index = 1,\n \t\t\t.value_type = REFTABLE_REF_VAL1,\n-\t\t\t.value.val1 = hash1,\n+\t\t\t.value.val1 = { 1 },\n \t\t},\n \t\t{\n \t\t\t.refname = \"b\",\n \t\t\t.update_index = 1,\n \t\t\t.value_type = REFTABLE_REF_VAL1,\n-\t\t\t.value.val1 = hash1,\n+\t\t\t.value.val1 = { 1 },\n \t\t},\n \t\t{\n \t\t\t.refname = \"c\",\n \t\t\t.update_index = 1,\n \t\t\t.value_type = REFTABLE_REF_VAL1,\n-\t\t\t.value.val1 = hash1,\n+\t\t\t.value.val1 = { 1 },\n \t\t}\n \t};\n \tstruct reftable_ref_record r2[] = { {\n@@ -197,13 +193,13 @@ static void test_merged(void)\n \t\t\t.refname = \"c\",\n \t\t\t.update_index = 3,\n \t\t\t.value_type = REFTABLE_REF_VAL1,\n-\t\t\t.value.val1 = hash2,\n+\t\t\t.value.val1 = { 2 },\n \t\t},\n \t\t{\n \t\t\t.refname = \"d\",\n \t\t\t.update_index = 3,\n \t\t\t.value_type = REFTABLE_REF_VAL1,\n-\t\t\t.value.val1 = hash1,\n+\t\t\t.value.val1 = { 1 },\n \t\t},\n \t};\n \ndiff --git a/reftable/readwrite_test.c b/reftable/readwrite_test.c\nindex 9c16e0504e..87b238105c 100644\n--- a/reftable/readwrite_test.c\n+++ b/reftable/readwrite_test.c\n@@ -60,18 +60,15 @@ static void write_table(char ***names, struct strbuf *buf, int N,\n \t*names = reftable_calloc(sizeof(char *) * (N + 1));\n \treftable_writer_set_limits(w, update_index, update_index);\n \tfor (i = 0; i < N; i++) {\n-\t\tuint8_t hash[GIT_SHA256_RAWSZ] = { 0 };\n \t\tchar name[100];\n \t\tint n;\n \n-\t\tset_test_hash(hash, i);\n-\n \t\tsnprintf(name, sizeof(name), \"refs/heads/branch%02d\", i);\n \n \t\tref.refname = name;\n \t\tref.update_index = update_index;\n \t\tref.value_type = REFTABLE_REF_VAL1;\n-\t\tref.value.val1 = hash;\n+\t\tset_test_hash(ref.value.val1, i);\n \t\t(*names)[i] = xstrdup(name);\n \n \t\tn = reftable_writer_add_ref(w, &ref);\n@@ -675,11 +672,10 @@ static void test_write_object_id_min_length(void)\n \tstruct strbuf buf = STRBUF_INIT;\n \tstruct reftable_writer *w =\n \t\treftable_new_writer(&strbuf_add_void, &buf, &opts);\n-\tuint8_t hash[GIT_SHA1_RAWSZ] = {42};\n \tstruct reftable_ref_record ref = {\n \t\t.update_index = 1,\n \t\t.value_type = REFTABLE_REF_VAL1,\n-\t\t.value.val1 = hash,\n+\t\t.value.val1 = {42},\n \t};\n \tint err;\n \tint i;\n@@ -711,11 +707,10 @@ static void test_write_object_id_length(void)\n \tstruct strbuf buf = STRBUF_INIT;\n \tstruct reftable_writer *w =\n \t\treftable_new_writer(&strbuf_add_void, &buf, &opts);\n-\tuint8_t hash[GIT_SHA1_RAWSZ] = {42};\n \tstruct reftable_ref_record ref = {\n \t\t.update_index = 1,\n \t\t.value_type = REFTABLE_REF_VAL1,\n-\t\t.value.val1 = hash,\n+\t\t.value.val1 = {42},\n \t};\n \tint err;\n \tint i;\n@@ -814,11 +809,10 @@ static void test_write_multiple_indices(void)\n \twriter = reftable_new_writer(&strbuf_add_void, &writer_buf, &opts);\n \treftable_writer_set_limits(writer, 1, 1);\n \tfor (i = 0; i < 100; i++) {\n-\t\tunsigned char hash[GIT_SHA1_RAWSZ] = {i};\n \t\tstruct reftable_ref_record ref = {\n \t\t\t.update_index = 1,\n \t\t\t.value_type = REFTABLE_REF_VAL1,\n-\t\t\t.value.val1 = hash,\n+\t\t\t.value.val1 = {i},\n \t\t};\n \n \t\tstrbuf_reset(&buf);\ndiff --git a/reftable/record.c b/reftable/record.c\nindex 5e258c734b..a67a6b4d8a 100644\n--- a/reftable/record.c\n+++ b/reftable/record.c\n@@ -219,7 +219,6 @@ static void reftable_ref_record_copy_from(void *rec, const void *src_rec,\n \tcase REFTABLE_REF_DELETION:\n \t\tbreak;\n \tcase REFTABLE_REF_VAL1:\n-\t\tref->value.val1 = reftable_malloc(hash_size);\n \t\tmemcpy(ref->value.val1, src->value.val1, hash_size);\n \t\tbreak;\n \tcase REFTABLE_REF_VAL2:\n@@ -303,7 +302,6 @@ void reftable_ref_record_release(struct reftable_ref_record *ref)\n \t\treftable_free(ref->value.val2.value);\n \t\tbreak;\n \tcase REFTABLE_REF_VAL1:\n-\t\treftable_free(ref->value.val1);\n \t\tbreak;\n \tcase REFTABLE_REF_DELETION:\n \t\tbreak;\n@@ -394,7 +392,6 @@ static int reftable_ref_record_decode(void *rec, struct strbuf key,\n \t\t\treturn -1;\n \t\t}\n \n-\t\tr->value.val1 = reftable_malloc(hash_size);\n \t\tmemcpy(r->value.val1, in.buf, hash_size);\n \t\tstring_view_consume(&in, hash_size);\n \t\tbreak;\ndiff --git a/reftable/record_test.c b/reftable/record_test.c\nindex 70ae78feca..5c94d26e35 100644\n--- a/reftable/record_test.c\n+++ b/reftable/record_test.c\n@@ -119,7 +119,6 @@ static void test_reftable_ref_record_roundtrip(void)\n \t\tcase REFTABLE_REF_DELETION:\n \t\t\tbreak;\n \t\tcase REFTABLE_REF_VAL1:\n-\t\t\tin.u.ref.value.val1 = reftable_malloc(GIT_SHA1_RAWSZ);\n \t\t\tset_hash(in.u.ref.value.val1, 1);\n \t\t\tbreak;\n \t\tcase REFTABLE_REF_VAL2:\ndiff --git a/reftable/reftable-record.h b/reftable/reftable-record.h\nindex f7eb2d6015..7f3a0df635 100644\n--- a/reftable/reftable-record.h\n+++ b/reftable/reftable-record.h\n@@ -9,6 +9,7 @@ license that can be found in the LICENSE file or at\n #ifndef REFTABLE_RECORD_H\n #define REFTABLE_RECORD_H\n \n+#include \"hash-ll.h\"\n #include \n \n /*\n@@ -38,7 +39,7 @@ struct reftable_ref_record {\n #define REFTABLE_NR_REF_VALUETYPES 4\n \t} value_type;\n \tunion {\n-\t\tuint8_t *val1; /* malloced hash. */\n+\t\tunsigned char val1[GIT_MAX_RAWSZ];\n \t\tstruct {\n \t\t\tuint8_t *value; /* first value, malloced hash */\n \t\t\tuint8_t *target_value; /* second value, malloced hash */\ndiff --git a/reftable/stack_test.c b/reftable/stack_test.c\nindex 14a3fc11ee..feab49d7f7 100644\n--- a/reftable/stack_test.c\n+++ b/reftable/stack_test.c\n@@ -463,7 +463,6 @@ static void test_reftable_stack_add(void)\n \t\trefs[i].refname = xstrdup(buf);\n \t\trefs[i].update_index = i + 1;\n \t\trefs[i].value_type = REFTABLE_REF_VAL1;\n-\t\trefs[i].value.val1 = reftable_malloc(GIT_SHA1_RAWSZ);\n \t\tset_test_hash(refs[i].value.val1, i);\n \n \t\tlogs[i].refname = xstrdup(buf);\n@@ -600,7 +599,6 @@ static void test_reftable_stack_tombstone(void)\n \t\trefs[i].update_index = i + 1;\n \t\tif (i % 2 == 0) {\n \t\t\trefs[i].value_type = REFTABLE_REF_VAL1;\n-\t\t\trefs[i].value.val1 = reftable_malloc(GIT_SHA1_RAWSZ);\n \t\t\tset_test_hash(refs[i].value.val1, i);\n \t\t}\n \n-- \n2.43.GIT\n\n"},{"id":"486085","messageId":"c8a36917b12a0c32f49ed7632483ad1f37c9855c.1703743174.git.ps@pks.im","threadId":"60638","inReplyTo":"cover.1703743174.git.ps@pks.im","subject":"[PATCH v2 6/8] reftable/record: store \"val2\" hashes as static arrays","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2023-12-28T06:28:00Z","receivedAt":"2023-12-28T06:28:03Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"Similar to the preceding commit, convert ref records of type \"val2\" to\nstore their object IDs in static arrays instead of allocating them for\nevery single record.\n\nWe're using the same benchmark as in the preceding commit, with `git\nshow-ref --quiet` in a repository with ~350k refs. This time around\nthough the effects aren't this huge. Before:\n\n HEAP SUMMARY:\n in use at exit: 21,163 bytes in 193 blocks\n total heap usage: 1,419,040 allocs, 1,418,847 frees, 62,153,868 bytes allocated\n\nAfter:\n\n HEAP SUMMARY:\n in use at exit: 21,163 bytes in 193 blocks\n total heap usage: 1,410,148 allocs, 1,409,955 frees, 61,976,068 bytes allocated\n\nThis is because \"val2\"-type records are typically only stored for peeled\ntags, and the number of annotated tags in the benchmark repository is\nrather low. Still, it can be seen that this change leads to a reduction\nof allocations overall, even if only a small one.\n\nSigned-off-by: Patrick Steinhardt \n---\n reftable/readwrite_test.c | 12 ++++--------\n reftable/record.c | 6 ------\n reftable/record_test.c | 4 ----\n reftable/reftable-record.h | 4 ++--\n 4 files changed, 6 insertions(+), 20 deletions(-)\n\ndiff --git a/reftable/readwrite_test.c b/reftable/readwrite_test.c\nindex 87b238105c..178766dfa8 100644\n--- a/reftable/readwrite_test.c\n+++ b/reftable/readwrite_test.c\n@@ -547,8 +547,6 @@ static void test_table_refs_for(int indexed)\n \t\tuint8_t hash[GIT_SHA1_RAWSZ];\n \t\tchar fill[51] = { 0 };\n \t\tchar name[100];\n-\t\tuint8_t hash1[GIT_SHA1_RAWSZ];\n-\t\tuint8_t hash2[GIT_SHA1_RAWSZ];\n \t\tstruct reftable_ref_record ref = { NULL };\n \n \t\tmemset(hash, i, sizeof(hash));\n@@ -558,11 +556,9 @@ static void test_table_refs_for(int indexed)\n \t\tname[40] = 0;\n \t\tref.refname = name;\n \n-\t\tset_test_hash(hash1, i / 4);\n-\t\tset_test_hash(hash2, 3 + i / 4);\n \t\tref.value_type = REFTABLE_REF_VAL2;\n-\t\tref.value.val2.value = hash1;\n-\t\tref.value.val2.target_value = hash2;\n+\t\tset_test_hash(ref.value.val2.value, i / 4);\n+\t\tset_test_hash(ref.value.val2.target_value, 3 + i / 4);\n \n \t\t/* 80 bytes / entry, so 3 entries per block. Yields 17\n \t\t */\n@@ -570,8 +566,8 @@ static void test_table_refs_for(int indexed)\n \t\tn = reftable_writer_add_ref(w, &ref);\n \t\tEXPECT(n == 0);\n \n-\t\tif (!memcmp(hash1, want_hash, GIT_SHA1_RAWSZ) ||\n-\t\t !memcmp(hash2, want_hash, GIT_SHA1_RAWSZ)) {\n+\t\tif (!memcmp(ref.value.val2.value, want_hash, GIT_SHA1_RAWSZ) ||\n+\t\t !memcmp(ref.value.val2.target_value, want_hash, GIT_SHA1_RAWSZ)) {\n \t\t\twant_names[want_names_len++] = xstrdup(name);\n \t\t}\n \t}\ndiff --git a/reftable/record.c b/reftable/record.c\nindex a67a6b4d8a..5c3fbb7b2a 100644\n--- a/reftable/record.c\n+++ b/reftable/record.c\n@@ -222,9 +222,7 @@ static void reftable_ref_record_copy_from(void *rec, const void *src_rec,\n \t\tmemcpy(ref->value.val1, src->value.val1, hash_size);\n \t\tbreak;\n \tcase REFTABLE_REF_VAL2:\n-\t\tref->value.val2.value = reftable_malloc(hash_size);\n \t\tmemcpy(ref->value.val2.value, src->value.val2.value, hash_size);\n-\t\tref->value.val2.target_value = reftable_malloc(hash_size);\n \t\tmemcpy(ref->value.val2.target_value,\n \t\t src->value.val2.target_value, hash_size);\n \t\tbreak;\n@@ -298,8 +296,6 @@ void reftable_ref_record_release(struct reftable_ref_record *ref)\n \t\treftable_free(ref->value.symref);\n \t\tbreak;\n \tcase REFTABLE_REF_VAL2:\n-\t\treftable_free(ref->value.val2.target_value);\n-\t\treftable_free(ref->value.val2.value);\n \t\tbreak;\n \tcase REFTABLE_REF_VAL1:\n \t\tbreak;\n@@ -401,11 +397,9 @@ static int reftable_ref_record_decode(void *rec, struct strbuf key,\n \t\t\treturn -1;\n \t\t}\n \n-\t\tr->value.val2.value = reftable_malloc(hash_size);\n \t\tmemcpy(r->value.val2.value, in.buf, hash_size);\n \t\tstring_view_consume(&in, hash_size);\n \n-\t\tr->value.val2.target_value = reftable_malloc(hash_size);\n \t\tmemcpy(r->value.val2.target_value, in.buf, hash_size);\n \t\tstring_view_consume(&in, hash_size);\n \t\tbreak;\ndiff --git a/reftable/record_test.c b/reftable/record_test.c\nindex 5c94d26e35..2876db7d27 100644\n--- a/reftable/record_test.c\n+++ b/reftable/record_test.c\n@@ -122,11 +122,7 @@ static void test_reftable_ref_record_roundtrip(void)\n \t\t\tset_hash(in.u.ref.value.val1, 1);\n \t\t\tbreak;\n \t\tcase REFTABLE_REF_VAL2:\n-\t\t\tin.u.ref.value.val2.value =\n-\t\t\t\treftable_malloc(GIT_SHA1_RAWSZ);\n \t\t\tset_hash(in.u.ref.value.val2.value, 1);\n-\t\t\tin.u.ref.value.val2.target_value =\n-\t\t\t\treftable_malloc(GIT_SHA1_RAWSZ);\n \t\t\tset_hash(in.u.ref.value.val2.target_value, 2);\n \t\t\tbreak;\n \t\tcase REFTABLE_REF_SYMREF:\ndiff --git a/reftable/reftable-record.h b/reftable/reftable-record.h\nindex 7f3a0df635..bb6e99acd3 100644\n--- a/reftable/reftable-record.h\n+++ b/reftable/reftable-record.h\n@@ -41,8 +41,8 @@ struct reftable_ref_record {\n \tunion {\n \t\tunsigned char val1[GIT_MAX_RAWSZ];\n \t\tstruct {\n-\t\t\tuint8_t *value; /* first value, malloced hash */\n-\t\t\tuint8_t *target_value; /* second value, malloced hash */\n+\t\t\tunsigned char value[GIT_MAX_RAWSZ]; /* first hash */\n+\t\t\tunsigned char target_value[GIT_MAX_RAWSZ]; /* second hash */\n \t\t} val2;\n \t\tchar *symref; /* referent, malloced 0-terminated string */\n \t} value;\n-- \n2.43.GIT\n\n"},{"id":"486086","messageId":"6313f8affdc136b183c1bd411d481efe5c676aee.1703743174.git.ps@pks.im","threadId":"60638","inReplyTo":"cover.1703743174.git.ps@pks.im","subject":"[PATCH v2 7/8] reftable/merged: really reuse buffers to compute record keys","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2023-12-28T06:28:04Z","receivedAt":"2023-12-28T06:28:08Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"In 829231dc20 (reftable/merged: reuse buffer to compute record keys,\n2023-12-11), we have refactored the merged iterator to reuse a set of\nbuffers that it would otherwise have to reallocate on every single\niteration. Unfortunately, there was a brown-paper-bag-style bug here as\nwe continue to release these buffers after the iteration, and thus we\nhave essentially gained nothing.\n\nFix this performance issue by not releasing those buffers on iteration\nanymore, where we instead rely on `merged_iter_close()` to release the\nbuffers for us.\n\nUsing `git show-ref --quiet` in a repository with ~350k refs this leads\nto a significant drop in allocations. Before:\n\n HEAP SUMMARY:\n in use at exit: 21,163 bytes in 193 blocks\n total heap usage: 1,410,148 allocs, 1,409,955 frees, 61,976,068 bytes allocated\n\nAfter:\n\n HEAP SUMMARY:\n in use at exit: 21,163 bytes in 193 blocks\n total heap usage: 708,058 allocs, 707,865 frees, 36,783,255 bytes allocated\n\nSigned-off-by: Patrick Steinhardt \n---\n reftable/merged.c | 2 --\n 1 file changed, 2 deletions(-)\n\ndiff --git a/reftable/merged.c b/reftable/merged.c\nindex 556bb5c556..a28bb99aaf 100644\n--- a/reftable/merged.c\n+++ b/reftable/merged.c\n@@ -128,8 +128,6 @@ static int merged_iter_next_entry(struct merged_iter *mi,\n \n done:\n \treftable_record_release(&entry.rec);\n-\tstrbuf_release(&mi->entry_key);\n-\tstrbuf_release(&mi->key);\n \treturn err;\n }\n \n-- \n2.43.GIT\n\n"},{"id":"486087","messageId":"25a3919e583a9d13403b8add92260529e19e08fb.1703743174.git.ps@pks.im","threadId":"60638","inReplyTo":"cover.1703743174.git.ps@pks.im","subject":"[PATCH v2 8/8] reftable/merged: transfer ownership of records when iterating","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2023-12-28T06:28:09Z","receivedAt":"2023-12-28T06:28:12Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"When iterating over recods with the merged iterator we put the records\ninto a priority queue before yielding them to the caller. This means\nthat we need to allocate the contents of these records before we can\npass them over to the caller.\n\nThe handover to the caller is quite inefficient though because we first\ndeallocate the record passed in by the caller and then copy over the new\nrecord, which requires us to reallocate memory.\n\nRefactor the code to instead transfer ownership of the new record to the\ncaller. So instead of reallocating all contents, we now release the old\nrecord and then copy contents of the new record into place.\n\nThe following benchmark of `git show-ref --quiet` in a repository with\naround 350k refs shows a clear improvement. Before:\n\n HEAP SUMMARY:\n in use at exit: 21,163 bytes in 193 blocks\n total heap usage: 708,058 allocs, 707,865 frees, 36,783,255 bytes allocated\n\nAfter:\n\n HEAP SUMMARY:\n in use at exit: 21,163 bytes in 193 blocks\n total heap usage: 357,007 allocs, 356,814 frees, 24,193,602 bytes allocated\n\nThis shows that we now have roundabout a single allocation per record\nthat we're yielding from the iterator. Ideally, we'd also get rid of\nthis allocation so that the number of allocations doesn't scale with the\nnumber of refs anymore. This would require some larger surgery though\nbecause the memory is owned by the priority queue before transferring it\nover to the caller.\n\nSigned-off-by: Patrick Steinhardt \n---\n reftable/merged.c | 6 ++++--\n 1 file changed, 4 insertions(+), 2 deletions(-)\n\ndiff --git a/reftable/merged.c b/reftable/merged.c\nindex a28bb99aaf..a52914d667 100644\n--- a/reftable/merged.c\n+++ b/reftable/merged.c\n@@ -124,10 +124,12 @@ static int merged_iter_next_entry(struct merged_iter *mi,\n \t\treftable_record_release(&top.rec);\n \t}\n \n-\treftable_record_copy_from(rec, &entry.rec, hash_size(mi->hash_id));\n+\treftable_record_release(rec);\n+\t*rec = entry.rec;\n \n done:\n-\treftable_record_release(&entry.rec);\n+\tif (err)\n+\t\treftable_record_release(&entry.rec);\n \treturn err;\n }\n \n-- \n2.43.GIT\n\n"},{"id":"486126","messageId":"xmqq8r5ei7jv.fsf@gitster.g","threadId":"60638","inReplyTo":"6313f8affdc136b183c1bd411d481efe5c676aee.1703743174.git.ps@pks.im","subject":"Re: [PATCH v2 7/8] reftable/merged: really reuse buffers to compute record keys","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2023-12-28T17:03:00Z","receivedAt":"2023-12-28T17:03:11Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Patrick Steinhardt writes:\n\n> In 829231dc20 (reftable/merged: reuse buffer to compute record keys,\n> 2023-12-11), we have refactored the merged iterator to reuse a set of\n> buffers that it would otherwise have to reallocate on every single\n> iteration. Unfortunately, there was a brown-paper-bag-style bug here as\n> we continue to release these buffers after the iteration, and thus we\n> have essentially gained nothing.\n\ns/-style// perhaps. It took me more than just reading of the above\nbut I needed to see the code before noticed that you are talking\nabout strbuf_release(). Only after that I think I understood what\nyou meant as a bug.\n\n With the change, instead of using a new \"entry_key\" strbuf for\n each iteration, the code now passes mi->entry_key to\n reftable_record_key(), which will reuse the existing .buf member\n of the strbuf to avoid reallcation. But releasing the strbuf in\n each iteration defeats such optimization.\n\nI suspect that a Git developer who will be reading \"git log\" output\nin 6 months and finds the above paragraph understands the problem\nand its fix better if the description hinted strbuf_reset() near\nwhere it mentions \"release\", something like:\n\n ... to reuse a pair of long-living strbufs by relying on the\n fact that reftable_record_key() tries to reuse its already\n allocated .buf member by calling strbuf_reset(), which should\n give us significantly fewer reallocation compared to the old\n code that used on-stack strbufs that are allocated for each and\n every iteration. Unfortunately, we called strbuf_release() on\n these long-living strbufs that we meant to reuse, defeating the\n optimization.\n\nor along that line, perhaps?\n\nOther than that, a very reasonable fix. Thanks for a pleasant read.\n\n> Fix this performance issue by not releasing those buffers on iteration\n> anymore, where we instead rely on `merged_iter_close()` to release the\n> buffers for us.\n>\n> Using `git show-ref --quiet` in a repository with ~350k refs this leads\n> to a significant drop in allocations. Before:\n>\n> HEAP SUMMARY:\n> in use at exit: 21,163 bytes in 193 blocks\n> total heap usage: 1,410,148 allocs, 1,409,955 frees, 61,976,068 bytes allocated\n>\n> After:\n>\n> HEAP SUMMARY:\n> in use at exit: 21,163 bytes in 193 blocks\n> total heap usage: 708,058 allocs, 707,865 frees, 36,783,255 bytes allocated\n>\n> Signed-off-by: Patrick Steinhardt \n> ---\n> reftable/merged.c | 2 --\n> 1 file changed, 2 deletions(-)\n>\n> diff --git a/reftable/merged.c b/reftable/merged.c\n> index 556bb5c556..a28bb99aaf 100644\n> --- a/reftable/merged.c\n> +++ b/reftable/merged.c\n> @@ -128,8 +128,6 @@ static int merged_iter_next_entry(struct merged_iter *mi,\n> \n> done:\n> \treftable_record_release(&entry.rec);\n> -\tstrbuf_release(&mi->entry_key);\n> -\tstrbuf_release(&mi->key);\n> \treturn err;\n> }\n"},{"id":"486127","messageId":"xmqq1qb6i7jl.fsf@gitster.g","threadId":"60638","inReplyTo":"46ca3a37f805cd36faa26927220c2793d4cdd561.1703743174.git.ps@pks.im","subject":"Re: [PATCH v2 5/8] reftable/record: store \"val1\" hashes as static arrays","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2023-12-28T17:03:10Z","receivedAt":"2023-12-28T17:03:16Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Patrick Steinhardt writes:\n\n> When reading ref records of type \"val1\" we store its object ID in an\n\nI'd find it easier to follow if we had a comma before \"we store\",\nbut perhaps I am old fashioned.\n\n> allocated array. This results in an additional allocation for every\n> single ref record we read, which is rather inefficient especially when\n> iterating over refs.\n>\n> Refactor the code to instead use a static array of `GIT_MAX_RAWSZ`\n\n\"a static\" -> \"an embedded\", perhaps? The struct as the whole may\nor may not be static but the point of this patch is that the array\nis embedded in it.\n\n> bytes. While this means that `struct ref_record` is bigger now, we\n> typically do not store all refs in an array anyway and instead only\n> handle a limited number of records at the same point in time.\n\nNicely explained.\n\n> Using `git show-ref --quiet` in a repository with ~350k refs this leads\n> to a significant drop in allocations. Before:\n>\n> HEAP SUMMARY:\n> in use at exit: 21,098 bytes in 192 blocks\n> total heap usage: 2,116,683 allocs, 2,116,491 frees, 76,098,060 bytes allocated\n>\n> After:\n>\n> HEAP SUMMARY:\n> in use at exit: 21,098 bytes in 192 blocks\n> total heap usage: 1,419,031 allocs, 1,418,839 frees, 62,145,036 bytes allocated\n>\n> Signed-off-by: Patrick Steinhardt \n> ---\n> reftable/block_test.c | 4 +---\n> reftable/merged_test.c | 16 ++++++----------\n> reftable/readwrite_test.c | 14 ++++----------\n> reftable/record.c | 3 ---\n> reftable/record_test.c | 1 -\n> reftable/reftable-record.h | 3 ++-\n> reftable/stack_test.c | 2 --\n> 7 files changed, 13 insertions(+), 30 deletions(-)\n>\n> diff --git a/reftable/block_test.c b/reftable/block_test.c\n> index c00bbc8aed..dedb05c7d8 100644\n> --- a/reftable/block_test.c\n> +++ b/reftable/block_test.c\n> @@ -49,13 +49,11 @@ static void test_block_read_write(void)\n> \n> \tfor (i = 0; i < N; i++) {\n> \t\tchar name[100];\n> -\t\tuint8_t hash[GIT_SHA1_RAWSZ];\n> \t\tsnprintf(name, sizeof(name), \"branch%02d\", i);\n> -\t\tmemset(hash, i, sizeof(hash));\n> \n> \t\trec.u.ref.refname = name;\n> \t\trec.u.ref.value_type = REFTABLE_REF_VAL1;\n> -\t\trec.u.ref.value.val1 = hash;\n> +\t\tmemset(rec.u.ref.value.val1, i, GIT_SHA1_RAWSZ);\n> \n> \t\tnames[i] = xstrdup(name);\n> \t\tn = block_writer_add(&bw, &rec);\n> diff --git a/reftable/merged_test.c b/reftable/merged_test.c\n> index d08c16abef..b3927a5d73 100644\n> --- a/reftable/merged_test.c\n> +++ b/reftable/merged_test.c\n> @@ -123,13 +123,11 @@ static void readers_destroy(struct reftable_reader **readers, size_t n)\n> \n> static void test_merged_between(void)\n> {\n> -\tuint8_t hash1[GIT_SHA1_RAWSZ] = { 1, 2, 3, 0 };\n> -\n> \tstruct reftable_ref_record r1[] = { {\n> \t\t.refname = \"b\",\n> \t\t.update_index = 1,\n> \t\t.value_type = REFTABLE_REF_VAL1,\n> -\t\t.value.val1 = hash1,\n> +\t\t.value.val1 = { 1, 2, 3, 0 },\n> \t} };\n> \tstruct reftable_ref_record r2[] = { {\n> \t\t.refname = \"a\",\n> @@ -165,26 +163,24 @@ static void test_merged_between(void)\n> \n> static void test_merged(void)\n> {\n> -\tuint8_t hash1[GIT_SHA1_RAWSZ] = { 1 };\n> -\tuint8_t hash2[GIT_SHA1_RAWSZ] = { 2 };\n> \tstruct reftable_ref_record r1[] = {\n> \t\t{\n> \t\t\t.refname = \"a\",\n> \t\t\t.update_index = 1,\n> \t\t\t.value_type = REFTABLE_REF_VAL1,\n> -\t\t\t.value.val1 = hash1,\n> +\t\t\t.value.val1 = { 1 },\n> \t\t},\n> \t\t{\n> \t\t\t.refname = \"b\",\n> \t\t\t.update_index = 1,\n> \t\t\t.value_type = REFTABLE_REF_VAL1,\n> -\t\t\t.value.val1 = hash1,\n> +\t\t\t.value.val1 = { 1 },\n> \t\t},\n> \t\t{\n> \t\t\t.refname = \"c\",\n> \t\t\t.update_index = 1,\n> \t\t\t.value_type = REFTABLE_REF_VAL1,\n> -\t\t\t.value.val1 = hash1,\n> +\t\t\t.value.val1 = { 1 },\n> \t\t}\n> \t};\n> \tstruct reftable_ref_record r2[] = { {\n> @@ -197,13 +193,13 @@ static void test_merged(void)\n> \t\t\t.refname = \"c\",\n> \t\t\t.update_index = 3,\n> \t\t\t.value_type = REFTABLE_REF_VAL1,\n> -\t\t\t.value.val1 = hash2,\n> +\t\t\t.value.val1 = { 2 },\n> \t\t},\n> \t\t{\n> \t\t\t.refname = \"d\",\n> \t\t\t.update_index = 3,\n> \t\t\t.value_type = REFTABLE_REF_VAL1,\n> -\t\t\t.value.val1 = hash1,\n> +\t\t\t.value.val1 = { 1 },\n> \t\t},\n> \t};\n> \n> diff --git a/reftable/readwrite_test.c b/reftable/readwrite_test.c\n> index 9c16e0504e..87b238105c 100644\n> --- a/reftable/readwrite_test.c\n> +++ b/reftable/readwrite_test.c\n> @@ -60,18 +60,15 @@ static void write_table(char ***names, struct strbuf *buf, int N,\n> \t*names = reftable_calloc(sizeof(char *) * (N + 1));\n> \treftable_writer_set_limits(w, update_index, update_index);\n> \tfor (i = 0; i < N; i++) {\n> -\t\tuint8_t hash[GIT_SHA256_RAWSZ] = { 0 };\n> \t\tchar name[100];\n> \t\tint n;\n> \n> -\t\tset_test_hash(hash, i);\n> -\n> \t\tsnprintf(name, sizeof(name), \"refs/heads/branch%02d\", i);\n> \n> \t\tref.refname = name;\n> \t\tref.update_index = update_index;\n> \t\tref.value_type = REFTABLE_REF_VAL1;\n> -\t\tref.value.val1 = hash;\n> +\t\tset_test_hash(ref.value.val1, i);\n> \t\t(*names)[i] = xstrdup(name);\n> \n> \t\tn = reftable_writer_add_ref(w, &ref);\n> @@ -675,11 +672,10 @@ static void test_write_object_id_min_length(void)\n> \tstruct strbuf buf = STRBUF_INIT;\n> \tstruct reftable_writer *w =\n> \t\treftable_new_writer(&strbuf_add_void, &buf, &opts);\n> -\tuint8_t hash[GIT_SHA1_RAWSZ] = {42};\n> \tstruct reftable_ref_record ref = {\n> \t\t.update_index = 1,\n> \t\t.value_type = REFTABLE_REF_VAL1,\n> -\t\t.value.val1 = hash,\n> +\t\t.value.val1 = {42},\n> \t};\n> \tint err;\n> \tint i;\n> @@ -711,11 +707,10 @@ static void test_write_object_id_length(void)\n> \tstruct strbuf buf = STRBUF_INIT;\n> \tstruct reftable_writer *w =\n> \t\treftable_new_writer(&strbuf_add_void, &buf, &opts);\n> -\tuint8_t hash[GIT_SHA1_RAWSZ] = {42};\n> \tstruct reftable_ref_record ref = {\n> \t\t.update_index = 1,\n> \t\t.value_type = REFTABLE_REF_VAL1,\n> -\t\t.value.val1 = hash,\n> +\t\t.value.val1 = {42},\n> \t};\n> \tint err;\n> \tint i;\n> @@ -814,11 +809,10 @@ static void test_write_multiple_indices(void)\n> \twriter = reftable_new_writer(&strbuf_add_void, &writer_buf, &opts);\n> \treftable_writer_set_limits(writer, 1, 1);\n> \tfor (i = 0; i < 100; i++) {\n> -\t\tunsigned char hash[GIT_SHA1_RAWSZ] = {i};\n> \t\tstruct reftable_ref_record ref = {\n> \t\t\t.update_index = 1,\n> \t\t\t.value_type = REFTABLE_REF_VAL1,\n> -\t\t\t.value.val1 = hash,\n> +\t\t\t.value.val1 = {i},\n> \t\t};\n> \n> \t\tstrbuf_reset(&buf);\n> diff --git a/reftable/record.c b/reftable/record.c\n> index 5e258c734b..a67a6b4d8a 100644\n> --- a/reftable/record.c\n> +++ b/reftable/record.c\n> @@ -219,7 +219,6 @@ static void reftable_ref_record_copy_from(void *rec, const void *src_rec,\n> \tcase REFTABLE_REF_DELETION:\n> \t\tbreak;\n> \tcase REFTABLE_REF_VAL1:\n> -\t\tref->value.val1 = reftable_malloc(hash_size);\n> \t\tmemcpy(ref->value.val1, src->value.val1, hash_size);\n> \t\tbreak;\n> \tcase REFTABLE_REF_VAL2:\n> @@ -303,7 +302,6 @@ void reftable_ref_record_release(struct reftable_ref_record *ref)\n> \t\treftable_free(ref->value.val2.value);\n> \t\tbreak;\n> \tcase REFTABLE_REF_VAL1:\n> -\t\treftable_free(ref->value.val1);\n> \t\tbreak;\n> \tcase REFTABLE_REF_DELETION:\n> \t\tbreak;\n> @@ -394,7 +392,6 @@ static int reftable_ref_record_decode(void *rec, struct strbuf key,\n> \t\t\treturn -1;\n> \t\t}\n> \n> -\t\tr->value.val1 = reftable_malloc(hash_size);\n> \t\tmemcpy(r->value.val1, in.buf, hash_size);\n> \t\tstring_view_consume(&in, hash_size);\n> \t\tbreak;\n> diff --git a/reftable/record_test.c b/reftable/record_test.c\n> index 70ae78feca..5c94d26e35 100644\n> --- a/reftable/record_test.c\n> +++ b/reftable/record_test.c\n> @@ -119,7 +119,6 @@ static void test_reftable_ref_record_roundtrip(void)\n> \t\tcase REFTABLE_REF_DELETION:\n> \t\t\tbreak;\n> \t\tcase REFTABLE_REF_VAL1:\n> -\t\t\tin.u.ref.value.val1 = reftable_malloc(GIT_SHA1_RAWSZ);\n> \t\t\tset_hash(in.u.ref.value.val1, 1);\n> \t\t\tbreak;\n> \t\tcase REFTABLE_REF_VAL2:\n> diff --git a/reftable/reftable-record.h b/reftable/reftable-record.h\n> index f7eb2d6015..7f3a0df635 100644\n> --- a/reftable/reftable-record.h\n> +++ b/reftable/reftable-record.h\n> @@ -9,6 +9,7 @@ license that can be found in the LICENSE file or at\n> #ifndef REFTABLE_RECORD_H\n> #define REFTABLE_RECORD_H\n> \n> +#include \"hash-ll.h\"\n> #include \n> \n> /*\n> @@ -38,7 +39,7 @@ struct reftable_ref_record {\n> #define REFTABLE_NR_REF_VALUETYPES 4\n> \t} value_type;\n> \tunion {\n> -\t\tuint8_t *val1; /* malloced hash. */\n> +\t\tunsigned char val1[GIT_MAX_RAWSZ];\n> \t\tstruct {\n> \t\t\tuint8_t *value; /* first value, malloced hash */\n> \t\t\tuint8_t *target_value; /* second value, malloced hash */\n> diff --git a/reftable/stack_test.c b/reftable/stack_test.c\n> index 14a3fc11ee..feab49d7f7 100644\n> --- a/reftable/stack_test.c\n> +++ b/reftable/stack_test.c\n> @@ -463,7 +463,6 @@ static void test_reftable_stack_add(void)\n> \t\trefs[i].refname = xstrdup(buf);\n> \t\trefs[i].update_index = i + 1;\n> \t\trefs[i].value_type = REFTABLE_REF_VAL1;\n> -\t\trefs[i].value.val1 = reftable_malloc(GIT_SHA1_RAWSZ);\n> \t\tset_test_hash(refs[i].value.val1, i);\n> \n> \t\tlogs[i].refname = xstrdup(buf);\n> @@ -600,7 +599,6 @@ static void test_reftable_stack_tombstone(void)\n> \t\trefs[i].update_index = i + 1;\n> \t\tif (i % 2 == 0) {\n> \t\t\trefs[i].value_type = REFTABLE_REF_VAL1;\n> -\t\t\trefs[i].value.val1 = reftable_malloc(GIT_SHA1_RAWSZ);\n> \t\t\tset_test_hash(refs[i].value.val1, i);\n> \t\t}\n"},{"id":"486128","messageId":"xmqqtto2gswa.fsf@gitster.g","threadId":"60638","inReplyTo":"25a3919e583a9d13403b8add92260529e19e08fb.1703743174.git.ps@pks.im","subject":"Re: [PATCH v2 8/8] reftable/merged: transfer ownership of records when iterating","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2023-12-28T17:04:53Z","receivedAt":"2023-12-28T17:04:56Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Patrick Steinhardt writes:\n\n> When iterating over recods with the merged iterator we put the records\n\n\"records\"?\n\nI commented on a few patches in this iteration that I found a bit\nharder to follow than necessary; aside from these small nits,\neverything in the series looked quite well explained and executed.\n\nThanks.\n\n"},{"id":"486232","messageId":"cover.1704262787.git.ps@pks.im","threadId":"60638","inReplyTo":"cover.1703063544.git.ps@pks.im","subject":"[PATCH v3 0/8] reftable: fixes and optimizations (pt.2)","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-01-03T06:22:08Z","receivedAt":"2024-01-03T06:22:14Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"Hi,\n\nthis is the third version of my patch series that contains additional\nfixes and optimizations for the reftable library.\n\nThe only changes in this iteration are improvements to the commit\nmessages to hopefully make them easier to understand. Thanks Junio for\nyour suggestions!\n\nPatrick\n\nPatrick Steinhardt (8):\n reftable/stack: do not overwrite errors when compacting\n reftable/stack: do not auto-compact twice in `reftable_stack_add()`\n reftable/writer: fix index corruption when writing multiple indices\n reftable/record: constify some parts of the interface\n reftable/record: store \"val1\" hashes as static arrays\n reftable/record: store \"val2\" hashes as static arrays\n reftable/merged: really reuse buffers to compute record keys\n reftable/merged: transfer ownership of records when iterating\n\n reftable/block_test.c | 4 +-\n reftable/merged.c | 8 +--\n reftable/merged_test.c | 16 +++---\n reftable/readwrite_test.c | 102 +++++++++++++++++++++++++++++++------\n reftable/record.c | 17 ++-----\n reftable/record_test.c | 5 --\n reftable/reftable-record.h | 11 ++--\n reftable/stack.c | 23 +++------\n reftable/stack_test.c | 2 -\n reftable/writer.c | 4 +-\n 10 files changed, 117 insertions(+), 75 deletions(-)\n\nRange-diff against v2:\n1: 22a57020c6 = 1: 1dc8ddf04a reftable/stack: do not overwrite errors when compacting\n2: a08f7efc99 = 2: eccc34a4b6 reftable/stack: do not auto-compact twice in `reftable_stack_add()`\n3: c00e08d97f = 3: 15e12b8f29 reftable/writer: fix index corruption when writing multiple indices\n4: 3416268087 = 4: 017e8943c7 reftable/record: constify some parts of the interface\n5: 46ca3a37f8 ! 5: f1d2190489 reftable/record: store \"val1\" hashes as static arrays\n @@ Metadata\n ## Commit message ##\n reftable/record: store \"val1\" hashes as static arrays\n \n - When reading ref records of type \"val1\" we store its object ID in an\n + When reading ref records of type \"val1\", we store its object ID in an\n allocated array. This results in an additional allocation for every\n single ref record we read, which is rather inefficient especially when\n iterating over refs.\n \n - Refactor the code to instead use a static array of `GIT_MAX_RAWSZ`\n + Refactor the code to instead use an embedded array of `GIT_MAX_RAWSZ`\n bytes. While this means that `struct ref_record` is bigger now, we\n typically do not store all refs in an array anyway and instead only\n handle a limited number of records at the same point in time.\n6: c8a36917b1 = 6: 6ec02d6775 reftable/record: store \"val2\" hashes as static arrays\n7: 6313f8affd ! 7: 845dec2390 reftable/merged: really reuse buffers to compute record keys\n @@ Commit message\n reftable/merged: really reuse buffers to compute record keys\n \n In 829231dc20 (reftable/merged: reuse buffer to compute record keys,\n - 2023-12-11), we have refactored the merged iterator to reuse a set of\n - buffers that it would otherwise have to reallocate on every single\n - iteration. Unfortunately, there was a brown-paper-bag-style bug here as\n - we continue to release these buffers after the iteration, and thus we\n - have essentially gained nothing.\n + 2023-12-11), we have refactored the merged iterator to reuse a pair of\n + long-living strbufs by relying on the fact that `reftable_record_key()`\n + tries to reuse already allocated strbufs by calling `strbuf_reset()`,\n + which should give us significantly fewer reallocations compared to the\n + old code that used on-stack strbufs that are allocated for each and\n + every iteration. Unfortunately, we called `strbuf_release()` on these\n + long-living strbufs that we meant to reuse on each iteration, defeating\n + the optimization.\n \n Fix this performance issue by not releasing those buffers on iteration\n anymore, where we instead rely on `merged_iter_close()` to release the\n8: 25a3919e58 ! 8: eea0e161ad reftable/merged: transfer ownership of records when iterating\n @@ Metadata\n ## Commit message ##\n reftable/merged: transfer ownership of records when iterating\n \n - When iterating over recods with the merged iterator we put the records\n + When iterating over records with the merged iterator we put the records\n into a priority queue before yielding them to the caller. This means\n that we need to allocate the contents of these records before we can\n pass them over to the caller.\n\nbase-commit: a26002b62827b89a19b1084bd75d9371d565d03c\n-- \n2.43.GIT\n\n"},{"id":"486233","messageId":"1dc8ddf04a112c38f41d573a48dac3f99b4b51e9.1704262787.git.ps@pks.im","threadId":"60638","inReplyTo":"cover.1704262787.git.ps@pks.im","subject":"[PATCH v3 1/8] reftable/stack: do not overwrite errors when compacting","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-01-03T06:22:13Z","receivedAt":"2024-01-03T06:22:16Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"In order to compact multiple stacks we iterate through the merged ref\nand log records. When there is any error either when reading the records\nfrom the old merged table or when writing the records to the new table\nthen we break out of the respective loops. When breaking out of the loop\nfor the ref records though the error code will be overwritten, which may\ncause us to inadvertently skip over bad ref records. In the worst case,\nthis can lead to a compacted stack that is missing records.\n\nFix the code by using `goto done` instead so that any potential error\ncodes are properly returned to the caller.\n\nSigned-off-by: Patrick Steinhardt \n---\n reftable/stack.c | 20 ++++++++------------\n 1 file changed, 8 insertions(+), 12 deletions(-)\n\ndiff --git a/reftable/stack.c b/reftable/stack.c\nindex 16bab82063..8729508dc3 100644\n--- a/reftable/stack.c\n+++ b/reftable/stack.c\n@@ -801,18 +801,16 @@ static int stack_write_compact(struct reftable_stack *st,\n \t\t\terr = 0;\n \t\t\tbreak;\n \t\t}\n-\t\tif (err < 0) {\n-\t\t\tbreak;\n-\t\t}\n+\t\tif (err < 0)\n+\t\t\tgoto done;\n \n \t\tif (first == 0 && reftable_ref_record_is_deletion(&ref)) {\n \t\t\tcontinue;\n \t\t}\n \n \t\terr = reftable_writer_add_ref(wr, &ref);\n-\t\tif (err < 0) {\n-\t\t\tbreak;\n-\t\t}\n+\t\tif (err < 0)\n+\t\t\tgoto done;\n \t\tentries++;\n \t}\n \treftable_iterator_destroy(&it);\n@@ -827,9 +825,8 @@ static int stack_write_compact(struct reftable_stack *st,\n \t\t\terr = 0;\n \t\t\tbreak;\n \t\t}\n-\t\tif (err < 0) {\n-\t\t\tbreak;\n-\t\t}\n+\t\tif (err < 0)\n+\t\t\tgoto done;\n \t\tif (first == 0 && reftable_log_record_is_deletion(&log)) {\n \t\t\tcontinue;\n \t\t}\n@@ -845,9 +842,8 @@ static int stack_write_compact(struct reftable_stack *st,\n \t\t}\n \n \t\terr = reftable_writer_add_log(wr, &log);\n-\t\tif (err < 0) {\n-\t\t\tbreak;\n-\t\t}\n+\t\tif (err < 0)\n+\t\t\tgoto done;\n \t\tentries++;\n \t}\n \n-- \n2.43.GIT\n\n"},{"id":"486234","messageId":"eccc34a4b68ccbc5097e807dcb349e2dd9f5b58e.1704262787.git.ps@pks.im","threadId":"60638","inReplyTo":"cover.1704262787.git.ps@pks.im","subject":"[PATCH v3 2/8] reftable/stack: do not auto-compact twice in `reftable_stack_add()`","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-01-03T06:22:17Z","receivedAt":"2024-01-03T06:22:20Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"In 5c086453ff (reftable/stack: perform auto-compaction with\ntransactional interface, 2023-12-11), we fixed a bug where the\ntransactional interface to add changes to a reftable stack did not\nperform auto-compaction by calling `reftable_stack_auto_compact()` in\n`reftable_stack_addition_commit()`. While correct, this change may now\ncause us to perform auto-compaction twice in the non-transactional\ninterface `reftable_stack_add()`:\n\n - It performs auto-compaction by itself.\n\n - It now transitively performs auto-compaction via the transactional\n interface.\n\nRemove the first instance so that we only end up doing auto-compaction\nonce.\n\nReported-by: Han-Wen Nienhuys \nSigned-off-by: Patrick Steinhardt \n---\n reftable/stack.c | 3 ---\n 1 file changed, 3 deletions(-)\n\ndiff --git a/reftable/stack.c b/reftable/stack.c\nindex 8729508dc3..7ffeb3ee10 100644\n--- a/reftable/stack.c\n+++ b/reftable/stack.c\n@@ -425,9 +425,6 @@ int reftable_stack_add(struct reftable_stack *st,\n \t\treturn err;\n \t}\n \n-\tif (!st->disable_auto_compact)\n-\t\treturn reftable_stack_auto_compact(st);\n-\n \treturn 0;\n }\n \n-- \n2.43.GIT\n\n"},{"id":"486235","messageId":"15e12b8f2904cc879498c344945f3f6380c0aa86.1704262787.git.ps@pks.im","threadId":"60638","inReplyTo":"cover.1704262787.git.ps@pks.im","subject":"[PATCH v3 3/8] reftable/writer: fix index corruption when writing multiple indices","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-01-03T06:22:21Z","receivedAt":"2024-01-03T06:22:24Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"Each reftable may contain multiple types of blocks for refs, objects and\nreflog records, where each of these may have an index that makes it more\nefficient to find the records. It was observed that the index for log\nrecords can become corrupted under certain circumstances, where the\nfirst entry of the index points into the object index instead of to the\nlog records.\n\nAs it turns out, this corruption can occur whenever we write a log index\nas well as at least one additional index. Writing records and their index\nis basically a two-step process:\n\n 1. We write all blocks for the corresponding record. Each block that\n gets written is added to a list of blocks to index.\n\n 2. Once all blocks were written we finish the section. If at least two\n blocks have been added to the list of blocks to index then we will\n now write the index for those blocks and flush it, as well.\n\nWhen we have a very large number of blocks then we may decide to write a\nmulti-level index, which is why we also keep track of the list of the\nindex blocks in the same way as we previously kept track of the blocks\nto index.\n\nNow when we have finished writing all index blocks we clear the index\nand flush the last block to disk. This is done in the wrong order though\nbecause flushing the block to disk will re-add it to the list of blocks\nto be indexed. The result is that the next section we are about to write\nwill have an entry in the list of blocks to index that points to the\nlast block of the preceding section's index, which will corrupt the log\nindex.\n\nFix this corruption by clearing the index after having written the last\nblock.\n\nSigned-off-by: Patrick Steinhardt \n---\n reftable/readwrite_test.c | 80 +++++++++++++++++++++++++++++++++++++++\n reftable/writer.c | 4 +-\n 2 files changed, 82 insertions(+), 2 deletions(-)\n\ndiff --git a/reftable/readwrite_test.c b/reftable/readwrite_test.c\nindex 278663f22d..9c16e0504e 100644\n--- a/reftable/readwrite_test.c\n+++ b/reftable/readwrite_test.c\n@@ -798,6 +798,85 @@ static void test_write_key_order(void)\n \tstrbuf_release(&buf);\n }\n \n+static void test_write_multiple_indices(void)\n+{\n+\tstruct reftable_write_options opts = {\n+\t\t.block_size = 100,\n+\t};\n+\tstruct strbuf writer_buf = STRBUF_INIT, buf = STRBUF_INIT;\n+\tstruct reftable_block_source source = { 0 };\n+\tstruct reftable_iterator it = { 0 };\n+\tconst struct reftable_stats *stats;\n+\tstruct reftable_writer *writer;\n+\tstruct reftable_reader *reader;\n+\tint err, i;\n+\n+\twriter = reftable_new_writer(&strbuf_add_void, &writer_buf, &opts);\n+\treftable_writer_set_limits(writer, 1, 1);\n+\tfor (i = 0; i < 100; i++) {\n+\t\tunsigned char hash[GIT_SHA1_RAWSZ] = {i};\n+\t\tstruct reftable_ref_record ref = {\n+\t\t\t.update_index = 1,\n+\t\t\t.value_type = REFTABLE_REF_VAL1,\n+\t\t\t.value.val1 = hash,\n+\t\t};\n+\n+\t\tstrbuf_reset(&buf);\n+\t\tstrbuf_addf(&buf, \"refs/heads/%04d\", i);\n+\t\tref.refname = buf.buf,\n+\n+\t\terr = reftable_writer_add_ref(writer, &ref);\n+\t\tEXPECT_ERR(err);\n+\t}\n+\n+\tfor (i = 0; i < 100; i++) {\n+\t\tunsigned char hash[GIT_SHA1_RAWSZ] = {i};\n+\t\tstruct reftable_log_record log = {\n+\t\t\t.update_index = 1,\n+\t\t\t.value_type = REFTABLE_LOG_UPDATE,\n+\t\t\t.value.update = {\n+\t\t\t\t.old_hash = hash,\n+\t\t\t\t.new_hash = hash,\n+\t\t\t},\n+\t\t};\n+\n+\t\tstrbuf_reset(&buf);\n+\t\tstrbuf_addf(&buf, \"refs/heads/%04d\", i);\n+\t\tlog.refname = buf.buf,\n+\n+\t\terr = reftable_writer_add_log(writer, &log);\n+\t\tEXPECT_ERR(err);\n+\t}\n+\n+\treftable_writer_close(writer);\n+\n+\t/*\n+\t * The written data should be sufficiently large to result in indices\n+\t * for each of the block types.\n+\t */\n+\tstats = reftable_writer_stats(writer);\n+\tEXPECT(stats->ref_stats.index_offset > 0);\n+\tEXPECT(stats->obj_stats.index_offset > 0);\n+\tEXPECT(stats->log_stats.index_offset > 0);\n+\n+\tblock_source_from_strbuf(&source, &writer_buf);\n+\terr = reftable_new_reader(&reader, &source, \"filename\");\n+\tEXPECT_ERR(err);\n+\n+\t/*\n+\t * Seeking the log uses the log index now. In case there is any\n+\t * confusion regarding indices we would notice here.\n+\t */\n+\terr = reftable_reader_seek_log(reader, &it, \"\");\n+\tEXPECT_ERR(err);\n+\n+\treftable_iterator_destroy(&it);\n+\treftable_writer_free(writer);\n+\treftable_reader_free(reader);\n+\tstrbuf_release(&writer_buf);\n+\tstrbuf_release(&buf);\n+}\n+\n static void test_corrupt_table_empty(void)\n {\n \tstruct strbuf buf = STRBUF_INIT;\n@@ -847,5 +926,6 @@ int readwrite_test_main(int argc, const char *argv[])\n \tRUN_TEST(test_log_overflow);\n \tRUN_TEST(test_write_object_id_length);\n \tRUN_TEST(test_write_object_id_min_length);\n+\tRUN_TEST(test_write_multiple_indices);\n \treturn 0;\n }\ndiff --git a/reftable/writer.c b/reftable/writer.c\nindex 2e322a5683..ee4590e20f 100644\n--- a/reftable/writer.c\n+++ b/reftable/writer.c\n@@ -432,12 +432,12 @@ static int writer_finish_section(struct reftable_writer *w)\n \t\treftable_free(idx);\n \t}\n \n-\twriter_clear_index(w);\n-\n \terr = writer_flush_block(w);\n \tif (err < 0)\n \t\treturn err;\n \n+\twriter_clear_index(w);\n+\n \tbstats = writer_reftable_block_stats(w, typ);\n \tbstats->index_blocks = w->stats.idx_stats.blocks - before_blocks;\n \tbstats->index_offset = index_start;\n-- \n2.43.GIT\n\n"},{"id":"486236","messageId":"017e8943c7b0b735d0252ad368f52443601da716.1704262787.git.ps@pks.im","threadId":"60638","inReplyTo":"cover.1704262787.git.ps@pks.im","subject":"[PATCH v3 4/8] reftable/record: constify some parts of the interface","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-01-03T06:22:26Z","receivedAt":"2024-01-03T06:22:29Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"We're about to convert reftable records to stop storing their object IDs\nas allocated hashes. Prepare for this refactoring by constifying some\nparts of the interface that will be impacted by this.\n\nSigned-off-by: Patrick Steinhardt \n---\n reftable/record.c | 8 ++++----\n reftable/reftable-record.h | 4 ++--\n 2 files changed, 6 insertions(+), 6 deletions(-)\n\ndiff --git a/reftable/record.c b/reftable/record.c\nindex fbaa1fbef5..5e258c734b 100644\n--- a/reftable/record.c\n+++ b/reftable/record.c\n@@ -76,7 +76,7 @@ int reftable_is_block_type(uint8_t typ)\n \treturn 0;\n }\n \n-uint8_t *reftable_ref_record_val1(const struct reftable_ref_record *rec)\n+const unsigned char *reftable_ref_record_val1(const struct reftable_ref_record *rec)\n {\n \tswitch (rec->value_type) {\n \tcase REFTABLE_REF_VAL1:\n@@ -88,7 +88,7 @@ uint8_t *reftable_ref_record_val1(const struct reftable_ref_record *rec)\n \t}\n }\n \n-uint8_t *reftable_ref_record_val2(const struct reftable_ref_record *rec)\n+const unsigned char *reftable_ref_record_val2(const struct reftable_ref_record *rec)\n {\n \tswitch (rec->value_type) {\n \tcase REFTABLE_REF_VAL2:\n@@ -242,7 +242,7 @@ static char hexdigit(int c)\n \treturn 'a' + (c - 10);\n }\n \n-static void hex_format(char *dest, uint8_t *src, int hash_size)\n+static void hex_format(char *dest, const unsigned char *src, int hash_size)\n {\n \tassert(hash_size > 0);\n \tif (src) {\n@@ -1164,7 +1164,7 @@ int reftable_record_equal(struct reftable_record *a, struct reftable_record *b,\n \t\treftable_record_data(a), reftable_record_data(b), hash_size);\n }\n \n-static int hash_equal(uint8_t *a, uint8_t *b, int hash_size)\n+static int hash_equal(const unsigned char *a, const unsigned char *b, int hash_size)\n {\n \tif (a && b)\n \t\treturn !memcmp(a, b, hash_size);\ndiff --git a/reftable/reftable-record.h b/reftable/reftable-record.h\nindex 67104f8fbf..f7eb2d6015 100644\n--- a/reftable/reftable-record.h\n+++ b/reftable/reftable-record.h\n@@ -49,11 +49,11 @@ struct reftable_ref_record {\n \n /* Returns the first hash, or NULL if `rec` is not of type\n * REFTABLE_REF_VAL1 or REFTABLE_REF_VAL2. */\n-uint8_t *reftable_ref_record_val1(const struct reftable_ref_record *rec);\n+const unsigned char *reftable_ref_record_val1(const struct reftable_ref_record *rec);\n \n /* Returns the second hash, or NULL if `rec` is not of type\n * REFTABLE_REF_VAL2. */\n-uint8_t *reftable_ref_record_val2(const struct reftable_ref_record *rec);\n+const unsigned char *reftable_ref_record_val2(const struct reftable_ref_record *rec);\n \n /* returns whether 'ref' represents a deletion */\n int reftable_ref_record_is_deletion(const struct reftable_ref_record *ref);\n-- \n2.43.GIT\n\n"},{"id":"486237","messageId":"f1d21904892153c74d22e4fc814aedfafcb28f41.1704262787.git.ps@pks.im","threadId":"60638","inReplyTo":"cover.1704262787.git.ps@pks.im","subject":"[PATCH v3 5/8] reftable/record: store \"val1\" hashes as static arrays","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-01-03T06:22:30Z","receivedAt":"2024-01-03T06:22:34Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"When reading ref records of type \"val1\", we store its object ID in an\nallocated array. This results in an additional allocation for every\nsingle ref record we read, which is rather inefficient especially when\niterating over refs.\n\nRefactor the code to instead use an embedded array of `GIT_MAX_RAWSZ`\nbytes. While this means that `struct ref_record` is bigger now, we\ntypically do not store all refs in an array anyway and instead only\nhandle a limited number of records at the same point in time.\n\nUsing `git show-ref --quiet` in a repository with ~350k refs this leads\nto a significant drop in allocations. Before:\n\n HEAP SUMMARY:\n in use at exit: 21,098 bytes in 192 blocks\n total heap usage: 2,116,683 allocs, 2,116,491 frees, 76,098,060 bytes allocated\n\nAfter:\n\n HEAP SUMMARY:\n in use at exit: 21,098 bytes in 192 blocks\n total heap usage: 1,419,031 allocs, 1,418,839 frees, 62,145,036 bytes allocated\n\nSigned-off-by: Patrick Steinhardt \n---\n reftable/block_test.c | 4 +---\n reftable/merged_test.c | 16 ++++++----------\n reftable/readwrite_test.c | 14 ++++----------\n reftable/record.c | 3 ---\n reftable/record_test.c | 1 -\n reftable/reftable-record.h | 3 ++-\n reftable/stack_test.c | 2 --\n 7 files changed, 13 insertions(+), 30 deletions(-)\n\ndiff --git a/reftable/block_test.c b/reftable/block_test.c\nindex c00bbc8aed..dedb05c7d8 100644\n--- a/reftable/block_test.c\n+++ b/reftable/block_test.c\n@@ -49,13 +49,11 @@ static void test_block_read_write(void)\n \n \tfor (i = 0; i < N; i++) {\n \t\tchar name[100];\n-\t\tuint8_t hash[GIT_SHA1_RAWSZ];\n \t\tsnprintf(name, sizeof(name), \"branch%02d\", i);\n-\t\tmemset(hash, i, sizeof(hash));\n \n \t\trec.u.ref.refname = name;\n \t\trec.u.ref.value_type = REFTABLE_REF_VAL1;\n-\t\trec.u.ref.value.val1 = hash;\n+\t\tmemset(rec.u.ref.value.val1, i, GIT_SHA1_RAWSZ);\n \n \t\tnames[i] = xstrdup(name);\n \t\tn = block_writer_add(&bw, &rec);\ndiff --git a/reftable/merged_test.c b/reftable/merged_test.c\nindex d08c16abef..b3927a5d73 100644\n--- a/reftable/merged_test.c\n+++ b/reftable/merged_test.c\n@@ -123,13 +123,11 @@ static void readers_destroy(struct reftable_reader **readers, size_t n)\n \n static void test_merged_between(void)\n {\n-\tuint8_t hash1[GIT_SHA1_RAWSZ] = { 1, 2, 3, 0 };\n-\n \tstruct reftable_ref_record r1[] = { {\n \t\t.refname = \"b\",\n \t\t.update_index = 1,\n \t\t.value_type = REFTABLE_REF_VAL1,\n-\t\t.value.val1 = hash1,\n+\t\t.value.val1 = { 1, 2, 3, 0 },\n \t} };\n \tstruct reftable_ref_record r2[] = { {\n \t\t.refname = \"a\",\n@@ -165,26 +163,24 @@ static void test_merged_between(void)\n \n static void test_merged(void)\n {\n-\tuint8_t hash1[GIT_SHA1_RAWSZ] = { 1 };\n-\tuint8_t hash2[GIT_SHA1_RAWSZ] = { 2 };\n \tstruct reftable_ref_record r1[] = {\n \t\t{\n \t\t\t.refname = \"a\",\n \t\t\t.update_index = 1,\n \t\t\t.value_type = REFTABLE_REF_VAL1,\n-\t\t\t.value.val1 = hash1,\n+\t\t\t.value.val1 = { 1 },\n \t\t},\n \t\t{\n \t\t\t.refname = \"b\",\n \t\t\t.update_index = 1,\n \t\t\t.value_type = REFTABLE_REF_VAL1,\n-\t\t\t.value.val1 = hash1,\n+\t\t\t.value.val1 = { 1 },\n \t\t},\n \t\t{\n \t\t\t.refname = \"c\",\n \t\t\t.update_index = 1,\n \t\t\t.value_type = REFTABLE_REF_VAL1,\n-\t\t\t.value.val1 = hash1,\n+\t\t\t.value.val1 = { 1 },\n \t\t}\n \t};\n \tstruct reftable_ref_record r2[] = { {\n@@ -197,13 +193,13 @@ static void test_merged(void)\n \t\t\t.refname = \"c\",\n \t\t\t.update_index = 3,\n \t\t\t.value_type = REFTABLE_REF_VAL1,\n-\t\t\t.value.val1 = hash2,\n+\t\t\t.value.val1 = { 2 },\n \t\t},\n \t\t{\n \t\t\t.refname = \"d\",\n \t\t\t.update_index = 3,\n \t\t\t.value_type = REFTABLE_REF_VAL1,\n-\t\t\t.value.val1 = hash1,\n+\t\t\t.value.val1 = { 1 },\n \t\t},\n \t};\n \ndiff --git a/reftable/readwrite_test.c b/reftable/readwrite_test.c\nindex 9c16e0504e..87b238105c 100644\n--- a/reftable/readwrite_test.c\n+++ b/reftable/readwrite_test.c\n@@ -60,18 +60,15 @@ static void write_table(char ***names, struct strbuf *buf, int N,\n \t*names = reftable_calloc(sizeof(char *) * (N + 1));\n \treftable_writer_set_limits(w, update_index, update_index);\n \tfor (i = 0; i < N; i++) {\n-\t\tuint8_t hash[GIT_SHA256_RAWSZ] = { 0 };\n \t\tchar name[100];\n \t\tint n;\n \n-\t\tset_test_hash(hash, i);\n-\n \t\tsnprintf(name, sizeof(name), \"refs/heads/branch%02d\", i);\n \n \t\tref.refname = name;\n \t\tref.update_index = update_index;\n \t\tref.value_type = REFTABLE_REF_VAL1;\n-\t\tref.value.val1 = hash;\n+\t\tset_test_hash(ref.value.val1, i);\n \t\t(*names)[i] = xstrdup(name);\n \n \t\tn = reftable_writer_add_ref(w, &ref);\n@@ -675,11 +672,10 @@ static void test_write_object_id_min_length(void)\n \tstruct strbuf buf = STRBUF_INIT;\n \tstruct reftable_writer *w =\n \t\treftable_new_writer(&strbuf_add_void, &buf, &opts);\n-\tuint8_t hash[GIT_SHA1_RAWSZ] = {42};\n \tstruct reftable_ref_record ref = {\n \t\t.update_index = 1,\n \t\t.value_type = REFTABLE_REF_VAL1,\n-\t\t.value.val1 = hash,\n+\t\t.value.val1 = {42},\n \t};\n \tint err;\n \tint i;\n@@ -711,11 +707,10 @@ static void test_write_object_id_length(void)\n \tstruct strbuf buf = STRBUF_INIT;\n \tstruct reftable_writer *w =\n \t\treftable_new_writer(&strbuf_add_void, &buf, &opts);\n-\tuint8_t hash[GIT_SHA1_RAWSZ] = {42};\n \tstruct reftable_ref_record ref = {\n \t\t.update_index = 1,\n \t\t.value_type = REFTABLE_REF_VAL1,\n-\t\t.value.val1 = hash,\n+\t\t.value.val1 = {42},\n \t};\n \tint err;\n \tint i;\n@@ -814,11 +809,10 @@ static void test_write_multiple_indices(void)\n \twriter = reftable_new_writer(&strbuf_add_void, &writer_buf, &opts);\n \treftable_writer_set_limits(writer, 1, 1);\n \tfor (i = 0; i < 100; i++) {\n-\t\tunsigned char hash[GIT_SHA1_RAWSZ] = {i};\n \t\tstruct reftable_ref_record ref = {\n \t\t\t.update_index = 1,\n \t\t\t.value_type = REFTABLE_REF_VAL1,\n-\t\t\t.value.val1 = hash,\n+\t\t\t.value.val1 = {i},\n \t\t};\n \n \t\tstrbuf_reset(&buf);\ndiff --git a/reftable/record.c b/reftable/record.c\nindex 5e258c734b..a67a6b4d8a 100644\n--- a/reftable/record.c\n+++ b/reftable/record.c\n@@ -219,7 +219,6 @@ static void reftable_ref_record_copy_from(void *rec, const void *src_rec,\n \tcase REFTABLE_REF_DELETION:\n \t\tbreak;\n \tcase REFTABLE_REF_VAL1:\n-\t\tref->value.val1 = reftable_malloc(hash_size);\n \t\tmemcpy(ref->value.val1, src->value.val1, hash_size);\n \t\tbreak;\n \tcase REFTABLE_REF_VAL2:\n@@ -303,7 +302,6 @@ void reftable_ref_record_release(struct reftable_ref_record *ref)\n \t\treftable_free(ref->value.val2.value);\n \t\tbreak;\n \tcase REFTABLE_REF_VAL1:\n-\t\treftable_free(ref->value.val1);\n \t\tbreak;\n \tcase REFTABLE_REF_DELETION:\n \t\tbreak;\n@@ -394,7 +392,6 @@ static int reftable_ref_record_decode(void *rec, struct strbuf key,\n \t\t\treturn -1;\n \t\t}\n \n-\t\tr->value.val1 = reftable_malloc(hash_size);\n \t\tmemcpy(r->value.val1, in.buf, hash_size);\n \t\tstring_view_consume(&in, hash_size);\n \t\tbreak;\ndiff --git a/reftable/record_test.c b/reftable/record_test.c\nindex 70ae78feca..5c94d26e35 100644\n--- a/reftable/record_test.c\n+++ b/reftable/record_test.c\n@@ -119,7 +119,6 @@ static void test_reftable_ref_record_roundtrip(void)\n \t\tcase REFTABLE_REF_DELETION:\n \t\t\tbreak;\n \t\tcase REFTABLE_REF_VAL1:\n-\t\t\tin.u.ref.value.val1 = reftable_malloc(GIT_SHA1_RAWSZ);\n \t\t\tset_hash(in.u.ref.value.val1, 1);\n \t\t\tbreak;\n \t\tcase REFTABLE_REF_VAL2:\ndiff --git a/reftable/reftable-record.h b/reftable/reftable-record.h\nindex f7eb2d6015..7f3a0df635 100644\n--- a/reftable/reftable-record.h\n+++ b/reftable/reftable-record.h\n@@ -9,6 +9,7 @@ license that can be found in the LICENSE file or at\n #ifndef REFTABLE_RECORD_H\n #define REFTABLE_RECORD_H\n \n+#include \"hash-ll.h\"\n #include \n \n /*\n@@ -38,7 +39,7 @@ struct reftable_ref_record {\n #define REFTABLE_NR_REF_VALUETYPES 4\n \t} value_type;\n \tunion {\n-\t\tuint8_t *val1; /* malloced hash. */\n+\t\tunsigned char val1[GIT_MAX_RAWSZ];\n \t\tstruct {\n \t\t\tuint8_t *value; /* first value, malloced hash */\n \t\t\tuint8_t *target_value; /* second value, malloced hash */\ndiff --git a/reftable/stack_test.c b/reftable/stack_test.c\nindex 14a3fc11ee..feab49d7f7 100644\n--- a/reftable/stack_test.c\n+++ b/reftable/stack_test.c\n@@ -463,7 +463,6 @@ static void test_reftable_stack_add(void)\n \t\trefs[i].refname = xstrdup(buf);\n \t\trefs[i].update_index = i + 1;\n \t\trefs[i].value_type = REFTABLE_REF_VAL1;\n-\t\trefs[i].value.val1 = reftable_malloc(GIT_SHA1_RAWSZ);\n \t\tset_test_hash(refs[i].value.val1, i);\n \n \t\tlogs[i].refname = xstrdup(buf);\n@@ -600,7 +599,6 @@ static void test_reftable_stack_tombstone(void)\n \t\trefs[i].update_index = i + 1;\n \t\tif (i % 2 == 0) {\n \t\t\trefs[i].value_type = REFTABLE_REF_VAL1;\n-\t\t\trefs[i].value.val1 = reftable_malloc(GIT_SHA1_RAWSZ);\n \t\t\tset_test_hash(refs[i].value.val1, i);\n \t\t}\n \n-- \n2.43.GIT\n\n"},{"id":"486238","messageId":"6ec02d6775c0f3e3274d57ef4a7dfeefac8308a9.1704262787.git.ps@pks.im","threadId":"60638","inReplyTo":"cover.1704262787.git.ps@pks.im","subject":"[PATCH v3 6/8] reftable/record: store \"val2\" hashes as static arrays","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-01-03T06:22:34Z","receivedAt":"2024-01-03T06:22:38Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"Similar to the preceding commit, convert ref records of type \"val2\" to\nstore their object IDs in static arrays instead of allocating them for\nevery single record.\n\nWe're using the same benchmark as in the preceding commit, with `git\nshow-ref --quiet` in a repository with ~350k refs. This time around\nthough the effects aren't this huge. Before:\n\n HEAP SUMMARY:\n in use at exit: 21,163 bytes in 193 blocks\n total heap usage: 1,419,040 allocs, 1,418,847 frees, 62,153,868 bytes allocated\n\nAfter:\n\n HEAP SUMMARY:\n in use at exit: 21,163 bytes in 193 blocks\n total heap usage: 1,410,148 allocs, 1,409,955 frees, 61,976,068 bytes allocated\n\nThis is because \"val2\"-type records are typically only stored for peeled\ntags, and the number of annotated tags in the benchmark repository is\nrather low. Still, it can be seen that this change leads to a reduction\nof allocations overall, even if only a small one.\n\nSigned-off-by: Patrick Steinhardt \n---\n reftable/readwrite_test.c | 12 ++++--------\n reftable/record.c | 6 ------\n reftable/record_test.c | 4 ----\n reftable/reftable-record.h | 4 ++--\n 4 files changed, 6 insertions(+), 20 deletions(-)\n\ndiff --git a/reftable/readwrite_test.c b/reftable/readwrite_test.c\nindex 87b238105c..178766dfa8 100644\n--- a/reftable/readwrite_test.c\n+++ b/reftable/readwrite_test.c\n@@ -547,8 +547,6 @@ static void test_table_refs_for(int indexed)\n \t\tuint8_t hash[GIT_SHA1_RAWSZ];\n \t\tchar fill[51] = { 0 };\n \t\tchar name[100];\n-\t\tuint8_t hash1[GIT_SHA1_RAWSZ];\n-\t\tuint8_t hash2[GIT_SHA1_RAWSZ];\n \t\tstruct reftable_ref_record ref = { NULL };\n \n \t\tmemset(hash, i, sizeof(hash));\n@@ -558,11 +556,9 @@ static void test_table_refs_for(int indexed)\n \t\tname[40] = 0;\n \t\tref.refname = name;\n \n-\t\tset_test_hash(hash1, i / 4);\n-\t\tset_test_hash(hash2, 3 + i / 4);\n \t\tref.value_type = REFTABLE_REF_VAL2;\n-\t\tref.value.val2.value = hash1;\n-\t\tref.value.val2.target_value = hash2;\n+\t\tset_test_hash(ref.value.val2.value, i / 4);\n+\t\tset_test_hash(ref.value.val2.target_value, 3 + i / 4);\n \n \t\t/* 80 bytes / entry, so 3 entries per block. Yields 17\n \t\t */\n@@ -570,8 +566,8 @@ static void test_table_refs_for(int indexed)\n \t\tn = reftable_writer_add_ref(w, &ref);\n \t\tEXPECT(n == 0);\n \n-\t\tif (!memcmp(hash1, want_hash, GIT_SHA1_RAWSZ) ||\n-\t\t !memcmp(hash2, want_hash, GIT_SHA1_RAWSZ)) {\n+\t\tif (!memcmp(ref.value.val2.value, want_hash, GIT_SHA1_RAWSZ) ||\n+\t\t !memcmp(ref.value.val2.target_value, want_hash, GIT_SHA1_RAWSZ)) {\n \t\t\twant_names[want_names_len++] = xstrdup(name);\n \t\t}\n \t}\ndiff --git a/reftable/record.c b/reftable/record.c\nindex a67a6b4d8a..5c3fbb7b2a 100644\n--- a/reftable/record.c\n+++ b/reftable/record.c\n@@ -222,9 +222,7 @@ static void reftable_ref_record_copy_from(void *rec, const void *src_rec,\n \t\tmemcpy(ref->value.val1, src->value.val1, hash_size);\n \t\tbreak;\n \tcase REFTABLE_REF_VAL2:\n-\t\tref->value.val2.value = reftable_malloc(hash_size);\n \t\tmemcpy(ref->value.val2.value, src->value.val2.value, hash_size);\n-\t\tref->value.val2.target_value = reftable_malloc(hash_size);\n \t\tmemcpy(ref->value.val2.target_value,\n \t\t src->value.val2.target_value, hash_size);\n \t\tbreak;\n@@ -298,8 +296,6 @@ void reftable_ref_record_release(struct reftable_ref_record *ref)\n \t\treftable_free(ref->value.symref);\n \t\tbreak;\n \tcase REFTABLE_REF_VAL2:\n-\t\treftable_free(ref->value.val2.target_value);\n-\t\treftable_free(ref->value.val2.value);\n \t\tbreak;\n \tcase REFTABLE_REF_VAL1:\n \t\tbreak;\n@@ -401,11 +397,9 @@ static int reftable_ref_record_decode(void *rec, struct strbuf key,\n \t\t\treturn -1;\n \t\t}\n \n-\t\tr->value.val2.value = reftable_malloc(hash_size);\n \t\tmemcpy(r->value.val2.value, in.buf, hash_size);\n \t\tstring_view_consume(&in, hash_size);\n \n-\t\tr->value.val2.target_value = reftable_malloc(hash_size);\n \t\tmemcpy(r->value.val2.target_value, in.buf, hash_size);\n \t\tstring_view_consume(&in, hash_size);\n \t\tbreak;\ndiff --git a/reftable/record_test.c b/reftable/record_test.c\nindex 5c94d26e35..2876db7d27 100644\n--- a/reftable/record_test.c\n+++ b/reftable/record_test.c\n@@ -122,11 +122,7 @@ static void test_reftable_ref_record_roundtrip(void)\n \t\t\tset_hash(in.u.ref.value.val1, 1);\n \t\t\tbreak;\n \t\tcase REFTABLE_REF_VAL2:\n-\t\t\tin.u.ref.value.val2.value =\n-\t\t\t\treftable_malloc(GIT_SHA1_RAWSZ);\n \t\t\tset_hash(in.u.ref.value.val2.value, 1);\n-\t\t\tin.u.ref.value.val2.target_value =\n-\t\t\t\treftable_malloc(GIT_SHA1_RAWSZ);\n \t\t\tset_hash(in.u.ref.value.val2.target_value, 2);\n \t\t\tbreak;\n \t\tcase REFTABLE_REF_SYMREF:\ndiff --git a/reftable/reftable-record.h b/reftable/reftable-record.h\nindex 7f3a0df635..bb6e99acd3 100644\n--- a/reftable/reftable-record.h\n+++ b/reftable/reftable-record.h\n@@ -41,8 +41,8 @@ struct reftable_ref_record {\n \tunion {\n \t\tunsigned char val1[GIT_MAX_RAWSZ];\n \t\tstruct {\n-\t\t\tuint8_t *value; /* first value, malloced hash */\n-\t\t\tuint8_t *target_value; /* second value, malloced hash */\n+\t\t\tunsigned char value[GIT_MAX_RAWSZ]; /* first hash */\n+\t\t\tunsigned char target_value[GIT_MAX_RAWSZ]; /* second hash */\n \t\t} val2;\n \t\tchar *symref; /* referent, malloced 0-terminated string */\n \t} value;\n-- \n2.43.GIT\n\n"},{"id":"486239","messageId":"845dec239019886575ba6796f34b0181c78981de.1704262787.git.ps@pks.im","threadId":"60638","inReplyTo":"cover.1704262787.git.ps@pks.im","subject":"[PATCH v3 7/8] reftable/merged: really reuse buffers to compute record keys","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-01-03T06:22:39Z","receivedAt":"2024-01-03T06:22:42Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"In 829231dc20 (reftable/merged: reuse buffer to compute record keys,\n2023-12-11), we have refactored the merged iterator to reuse a pair of\nlong-living strbufs by relying on the fact that `reftable_record_key()`\ntries to reuse already allocated strbufs by calling `strbuf_reset()`,\nwhich should give us significantly fewer reallocations compared to the\nold code that used on-stack strbufs that are allocated for each and\nevery iteration. Unfortunately, we called `strbuf_release()` on these\nlong-living strbufs that we meant to reuse on each iteration, defeating\nthe optimization.\n\nFix this performance issue by not releasing those buffers on iteration\nanymore, where we instead rely on `merged_iter_close()` to release the\nbuffers for us.\n\nUsing `git show-ref --quiet` in a repository with ~350k refs this leads\nto a significant drop in allocations. Before:\n\n HEAP SUMMARY:\n in use at exit: 21,163 bytes in 193 blocks\n total heap usage: 1,410,148 allocs, 1,409,955 frees, 61,976,068 bytes allocated\n\nAfter:\n\n HEAP SUMMARY:\n in use at exit: 21,163 bytes in 193 blocks\n total heap usage: 708,058 allocs, 707,865 frees, 36,783,255 bytes allocated\n\nSigned-off-by: Patrick Steinhardt \n---\n reftable/merged.c | 2 --\n 1 file changed, 2 deletions(-)\n\ndiff --git a/reftable/merged.c b/reftable/merged.c\nindex 556bb5c556..a28bb99aaf 100644\n--- a/reftable/merged.c\n+++ b/reftable/merged.c\n@@ -128,8 +128,6 @@ static int merged_iter_next_entry(struct merged_iter *mi,\n \n done:\n \treftable_record_release(&entry.rec);\n-\tstrbuf_release(&mi->entry_key);\n-\tstrbuf_release(&mi->key);\n \treturn err;\n }\n \n-- \n2.43.GIT\n\n"},{"id":"486240","messageId":"eea0e161adca68e986cd7af0a195e60b8d4cbc9f.1704262787.git.ps@pks.im","threadId":"60638","inReplyTo":"cover.1704262787.git.ps@pks.im","subject":"[PATCH v3 8/8] reftable/merged: transfer ownership of records when iterating","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-01-03T06:22:43Z","receivedAt":"2024-01-03T06:22:46Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"When iterating over records with the merged iterator we put the records\ninto a priority queue before yielding them to the caller. This means\nthat we need to allocate the contents of these records before we can\npass them over to the caller.\n\nThe handover to the caller is quite inefficient though because we first\ndeallocate the record passed in by the caller and then copy over the new\nrecord, which requires us to reallocate memory.\n\nRefactor the code to instead transfer ownership of the new record to the\ncaller. So instead of reallocating all contents, we now release the old\nrecord and then copy contents of the new record into place.\n\nThe following benchmark of `git show-ref --quiet` in a repository with\naround 350k refs shows a clear improvement. Before:\n\n HEAP SUMMARY:\n in use at exit: 21,163 bytes in 193 blocks\n total heap usage: 708,058 allocs, 707,865 frees, 36,783,255 bytes allocated\n\nAfter:\n\n HEAP SUMMARY:\n in use at exit: 21,163 bytes in 193 blocks\n total heap usage: 357,007 allocs, 356,814 frees, 24,193,602 bytes allocated\n\nThis shows that we now have roundabout a single allocation per record\nthat we're yielding from the iterator. Ideally, we'd also get rid of\nthis allocation so that the number of allocations doesn't scale with the\nnumber of refs anymore. This would require some larger surgery though\nbecause the memory is owned by the priority queue before transferring it\nover to the caller.\n\nSigned-off-by: Patrick Steinhardt \n---\n reftable/merged.c | 6 ++++--\n 1 file changed, 4 insertions(+), 2 deletions(-)\n\ndiff --git a/reftable/merged.c b/reftable/merged.c\nindex a28bb99aaf..a52914d667 100644\n--- a/reftable/merged.c\n+++ b/reftable/merged.c\n@@ -124,10 +124,12 @@ static int merged_iter_next_entry(struct merged_iter *mi,\n \t\treftable_record_release(&top.rec);\n \t}\n \n-\treftable_record_copy_from(rec, &entry.rec, hash_size(mi->hash_id));\n+\treftable_record_release(rec);\n+\t*rec = entry.rec;\n \n done:\n-\treftable_record_release(&entry.rec);\n+\tif (err)\n+\t\treftable_record_release(&entry.rec);\n \treturn err;\n }\n \n-- \n2.43.GIT\n\n"},{"id":"487924","messageId":"CAOLa=ZQk_SocUWkoTgJuKyyGWVU85gtw+=8o1ffgBQmh5dQnqQ@mail.gmail.com","threadId":"60638","inReplyTo":"f1d21904892153c74d22e4fc814aedfafcb28f41.1704262787.git.ps@pks.im","subject":"Re: [PATCH v3 5/8] reftable/record: store \"val1\" hashes as static arrays","fromName":"Karthik Nayak","fromEmail":"karthik.188@gmail.com","sentAt":"2024-02-05T11:39:31Z","receivedAt":"2024-02-05T11:39:33Z","isPatch":true,"sender":{"key":"karthik.188@gmail.com","avatar":"https://avatars.githubusercontent.com/u/1786334?v=4"},"body":"Patrick Steinhardt writes:\n\n> When reading ref records of type \"val1\", we store its object ID in an\n> allocated array. This results in an additional allocation for every\n> single ref record we read, which is rather inefficient especially when\n> iterating over refs.\n>\n> Refactor the code to instead use an embedded array of `GIT_MAX_RAWSZ`\n> bytes. While this means that `struct ref_record` is bigger now, we\n> typically do not store all refs in an array anyway and instead only\n> handle a limited number of records at the same point in time.\n>\n> Using `git show-ref --quiet` in a repository with ~350k refs this leads\n> to a significant drop in allocations. Before:\n>\n> HEAP SUMMARY:\n> in use at exit: 21,098 bytes in 192 blocks\n> total heap usage: 2,116,683 allocs, 2,116,491 frees, 76,098,060 bytes allocated\n>\n> After:\n>\n> HEAP SUMMARY:\n> in use at exit: 21,098 bytes in 192 blocks\n> total heap usage: 1,419,031 allocs, 1,418,839 frees, 62,145,036 bytes allocated\n\nCurious, did you also do perf benchmarking on this?\n"},{"id":"487926","messageId":"CAOLa=ZTZAC7ZNrpexiSbfW_-hoaW6iV3rbimqTGX2-7qY_pEHQ@mail.gmail.com","threadId":"60638","inReplyTo":"cover.1704262787.git.ps@pks.im","subject":"Re: [PATCH v3 0/8] reftable: fixes and optimizations (pt.2)","fromName":"Karthik Nayak","fromEmail":"karthik.188@gmail.com","sentAt":"2024-02-05T13:08:42Z","receivedAt":"2024-02-05T13:08:43Z","isPatch":true,"sender":{"key":"karthik.188@gmail.com","avatar":"https://avatars.githubusercontent.com/u/1786334?v=4"},"body":"Patrick Steinhardt writes:\n\nHello,\n\n> Hi,\n>\n> this is the third version of my patch series that contains additional\n> fixes and optimizations for the reftable library.\n>\n\nI have reviewed this version and have nothing to add. Thanks!\n"},{"id":"488026","messageId":"ZcHLpkrIG07U4Ep2@tanuki","threadId":"60638","inReplyTo":"CAOLa=ZQk_SocUWkoTgJuKyyGWVU85gtw+=8o1ffgBQmh5dQnqQ@mail.gmail.com","subject":"Re: [PATCH v3 5/8] reftable/record: store \"val1\" hashes as static arrays","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-02-06T06:03:18Z","receivedAt":"2024-02-06T06:03:24Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"On Mon, Feb 05, 2024 at 03:39:31AM -0800, Karthik Nayak wrote:\n> Patrick Steinhardt writes:\n> \n> > When reading ref records of type \"val1\", we store its object ID in an\n> > allocated array. This results in an additional allocation for every\n> > single ref record we read, which is rather inefficient especially when\n> > iterating over refs.\n> >\n> > Refactor the code to instead use an embedded array of `GIT_MAX_RAWSZ`\n> > bytes. While this means that `struct ref_record` is bigger now, we\n> > typically do not store all refs in an array anyway and instead only\n> > handle a limited number of records at the same point in time.\n> >\n> > Using `git show-ref --quiet` in a repository with ~350k refs this leads\n> > to a significant drop in allocations. Before:\n> >\n> > HEAP SUMMARY:\n> > in use at exit: 21,098 bytes in 192 blocks\n> > total heap usage: 2,116,683 allocs, 2,116,491 frees, 76,098,060 bytes allocated\n> >\n> > After:\n> >\n> > HEAP SUMMARY:\n> > in use at exit: 21,098 bytes in 192 blocks\n> > total heap usage: 1,419,031 allocs, 1,418,839 frees, 62,145,036 bytes allocated\n> \n> Curious, did you also do perf benchmarking on this?\n\nI didn't back then, but here you go. The following test shows a single\nref matching a specific pattern out of 1 million refs:\n\n Benchmark 1: show-ref: single matching ref (revision = HEAD~)\n Time (mean ± σ): 191.1 ms ± 5.2 ms [User: 188.1 ms, System: 2.8 ms]\n Range (min … max): 186.2 ms … 214.5 ms 100 runs\n\n Benchmark 2: show-ref: single matching ref (revision = HEAD)\n Time (mean ± σ): 189.7 ms ± 5.3 ms [User: 186.7 ms, System: 2.8 ms]\n Range (min … max): 184.1 ms … 213.4 ms 100 runs\n\n Summary\n show-ref: single matching ref (revision = HEAD) ran\n 1.01 ± 0.04 times faster than show-ref: single matching ref (revision = HEAD~)\n\nNot much of a win here, which is probably expected. On glibc the\nallocator seems to be really efficient churning out many small blocks of\nmemory, which is also something I have noticed in other contexts. I do\nexpect that other platorms might see more significant results.\n\nPatrick\n"},{"id":"488649","messageId":"CAOw_e7b72HVQob_hiV0gtRhGWsb=rz40WL=oaV63t7oOmEA-mw@mail.gmail.com","threadId":"60638","inReplyTo":"1dc8ddf04a112c38f41d573a48dac3f99b4b51e9.1704262787.git.ps@pks.im","subject":"Re: [PATCH v3 1/8] reftable/stack: do not overwrite errors when compacting","fromName":"Han-Wen Nienhuys","fromEmail":"hanwenn@gmail.com","sentAt":"2024-02-14T15:12:54Z","receivedAt":"2024-02-14T15:13:06Z","isPatch":true,"sender":{"key":"hanwenn@gmail.com","avatar":"https://gravatar.com/avatar/058832acb8d613baeb6ce9d21b009d9772424a309b9a521330423daef909a27a?d=mp&s=160"},"body":"Good catch!\n\nSorry for messing this up.\n\n> In the worst case,\n> this can lead to a compacted stack that is missing records.\n\nYeah, that would be an insidious corruption. Have you considered\nwriting a test to reproduce this (and thus verify that the fix really\nfixes the problem?)\n\nI think it wouldn't be too difficult: you could create a custom\nblocksource wrapper that returns I/O error on the Nth read, and then\ncreate a reftable with two ref blocks (could just be 2 records if you\nuse a small blocksize and a large refname) and two log blocks. Merge\nthat with an empty table, and see if the compacted result is what you\ngot in. Loop over N to get coverage for all error paths.\n\nOn Wed, Jan 3, 2024 at 7:22 AM Patrick Steinhardt wrote:\n>\n> In order to compact multiple stacks we iterate through the merged ref\n> and log records. When there is any error either when reading the records\n> from the old merged table or when writing the records to the new table\n> then we break out of the respective loops. When breaking out of the loop\n> for the ref records though the error code will be overwritten, which may\n> cause us to inadvertently skip over bad ref records. In the worst case,\n> this can lead to a compacted stack that is missing records.\n>\n> Fix the code by using `goto done` instead so that any potential error\n> codes are properly returned to the caller.\n>\n> Signed-off-by: Patrick Steinhardt \n> ---\n> reftable/stack.c | 20 ++++++++------------\n> 1 file changed, 8 insertions(+), 12 deletions(-)\n>\n> diff --git a/reftable/stack.c b/reftable/stack.c\n> index 16bab82063..8729508dc3 100644\n> --- a/reftable/stack.c\n> +++ b/reftable/stack.c\n> @@ -801,18 +801,16 @@ static int stack_write_compact(struct reftable_stack *st,\n> err = 0;\n> break;\n> }\n> - if (err < 0) {\n> - break;\n> - }\n> + if (err < 0)\n> + goto done;\n>\n> if (first == 0 && reftable_ref_record_is_deletion(&ref)) {\n> continue;\n> }\n>\n> err = reftable_writer_add_ref(wr, &ref);\n> - if (err < 0) {\n> - break;\n> - }\n> + if (err < 0)\n> + goto done;\n> entries++;\n> }\n> reftable_iterator_destroy(&it);\n> @@ -827,9 +825,8 @@ static int stack_write_compact(struct reftable_stack *st,\n> err = 0;\n> break;\n> }\n> - if (err < 0) {\n> - break;\n> - }\n> + if (err < 0)\n> + goto done;\n> if (first == 0 && reftable_log_record_is_deletion(&log)) {\n> continue;\n> }\n> @@ -845,9 +842,8 @@ static int stack_write_compact(struct reftable_stack *st,\n> }\n>\n> err = reftable_writer_add_log(wr, &log);\n> - if (err < 0) {\n> - break;\n> - }\n> + if (err < 0)\n> + goto done;\n> entries++;\n> }\n>\n> --\n> 2.43.GIT\n>\n\n\n-- \nHan-Wen Nienhuys - hanwenn@gmail.com - http://www.xs4all.nl/~hanwen\n"},{"id":"488691","messageId":"Zc3AsEu0FYzU6tMX@tanuki","threadId":"60638","inReplyTo":"CAOw_e7b72HVQob_hiV0gtRhGWsb=rz40WL=oaV63t7oOmEA-mw@mail.gmail.com","subject":"Re: [PATCH v3 1/8] reftable/stack: do not overwrite errors when compacting","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-02-15T07:43:44Z","receivedAt":"2024-02-15T07:43:49Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"On Wed, Feb 14, 2024 at 04:12:54PM +0100, Han-Wen Nienhuys wrote:\n> Good catch!\n> \n> Sorry for messing this up.\n\nNothing to be sorry about, bugs happen to all of us.\n\n> > In the worst case,\n> > this can lead to a compacted stack that is missing records.\n> \n> Yeah, that would be an insidious corruption. Have you considered\n> writing a test to reproduce this (and thus verify that the fix really\n> fixes the problem?)\n> \n> I think it wouldn't be too difficult: you could create a custom\n> blocksource wrapper that returns I/O error on the Nth read, and then\n> create a reftable with two ref blocks (could just be 2 records if you\n> use a small blocksize and a large refname) and two log blocks. Merge\n> that with an empty table, and see if the compacted result is what you\n> got in. Loop over N to get coverage for all error paths.\n\nAh, that's a feasible way to write such a test indeed. I may come back\nto it in the future and will add it to our backlog. Thanks!\n\nPatrick\n"}]}