reftable: fixes and optimizations (pt.2)
cover reftable: fixes and optimizations (pt.2)
Hi,
this is the second set of patches that fixes bugs and performs some slight memory optimizations. The series builds on top of c0cadb0576, which has been merged to next.
The series is structured as follows:
- Patch 1: some hardening to not corrupt the reftable stack on compaction.
- Patch 2: fix corruption of a reftable when writing multiple indices.
- Patches 3 - 7: various smallish refactorings to optimize memory usage. Overall these reduce allocations when iterating many refs by almost 85%.
Thanks in advance for your review!
Patrick
Patrick Steinhardt (7):
reftable/stack: do not overwrite errors when compacting reftable/writer: fix index corruption when writing multiple indices reftable/record: constify some parts of the interface reftable/record: store "val1" hashes as static arrays reftable/record: store "val2" hashes as static arrays reftable/merged: really reuse buffers to compute record keys reftable/merged: transfer ownership of records when iterating
reftable/block_test.c | 4 +- reftable/merged.c | 8 +-- reftable/merged_test.c | 16 +++--- reftable/readwrite_test.c | 103 +++++++++++++++++++++++++++++++------ reftable/record.c | 17 ++---- reftable/record_test.c | 5 -- reftable/reftable-record.h | 10 ++-- reftable/stack.c | 20 +++---- reftable/stack_test.c | 2 - reftable/writer.c | 4 +- 10 files changed, 117 insertions(+), 72 deletions(-)
base-commit: c0cadb0576d4920915eb3bd38a7d1abfcbd25f98
Signature · 1 line
2.43.GIT
PATCH 1/7 reftable/stack: do not overwrite errors when compacting
In order to compact multiple stacks we iterate through the merged ref and log records. When there is any error either when reading the records from the old merged table or when writing the records to the new table then we break out of the respective loops. When breaking out of the loop for the ref records though the error code will be overwritten, which may cause us to inadvertently skip over bad ref records. In the worst case, this can lead to a compacted stack that is missing records.
Fix the code by using goto done instead so that any potential error codes are properly returned to the caller.
--- reftable/stack.c | 20 ++++++++------------ 1 file changed, 8 insertions(+), 12 deletions(-)
reftable/stack.c +8 -12
@@ -801,18 +801,16 @@ static int stack_write_compact(struct reftable_stack *st, err =0 ;break ; } -if (err <0 ) { -break ; - } +if (err <0 ) + goto done;if (first ==0 &&reftable_ref_record_is_deletion (&ref)) {continue ; } err =reftable_writer_add_ref (wr, &ref); -if (err <0 ) { -break ; - } +if (err <0 ) + goto done; entries++; }reftable_iterator_destroy (&it);
@@ -827,9 +825,8 @@ static int stack_write_compact(struct reftable_stack *st, err =0 ;break ; } -if (err <0 ) { -break ; - } +if (err <0 ) + goto done;if (first ==0 &&reftable_log_record_is_deletion (&log)) {continue ; }
@@ -845,9 +842,8 @@ static int stack_write_compact(struct reftable_stack *st, } err =reftable_writer_add_log (wr, &log); -if (err <0 ) { -break ; - } +if (err <0 ) + goto done; entries++; }
Signature · 1 line
2.43.GIT
PATCH 2/7 reftable/writer: fix index corruption when writing multiple indices
In reply to Patrick SteinhardtEach reftable may contain multiple types of blocks for refs, objects and reflog records, where each of these may have an index that makes it more efficient to find the records. It was observed that the index for log records can become corrupted under certain circumstances, where the first entry of the index points into the object index instead of to the log records.
As it turns out, this corruption can occur whenever we write a log index as well as at least one additional index. Writing records and their index is basically a two-step process:
1. We write all blocks for the corresponding record. Each block that gets written is added to a list of blocks to index.
2. Once all blocks were written we finish the section. If at least two blocks have been added to the list of blocks to index then we will now write the index for those blocks and flush it, as well.
When we have a very large number of blocks then we may decide to write a multi-level index, which is why we also keep track of the list of the index blocks in the same way as we previously kept track of the blocks to index.
Now when we have finished writing all index blocks we clear the index and flush the last block to disk. This is done in the wrong order though because flushing the block to disk will re-add it to the list of blocks to be indexed. The result is that the next section we are about to write will have an entry in the list of blocks to index that points to the last block of the preceding section's index, which will corrupt the log index.
Fix this corruption by clearing the index after having written the last block.
--- reftable/readwrite_test.c | 80 +++++++++++++++++++++++++++++++++++++++ reftable/writer.c | 4 +- 2 files changed, 82 insertions(+), 2 deletions(-)
reftable/readwrite_test.c +80 -0
@@ -798,6 +798,85 @@ static void test_write_key_order(void)strbuf_release (&buf); } +static void test_write_multiple_indices (void ) +{ +struct reftable_write_options opts = { + .block_size =100 , + }; +struct strbuf writer_buf =STRBUF_INIT , buf =STRBUF_INIT ; +struct reftable_block_source source = {0 }; +struct reftable_iterator it = {0 }; +const struct reftable_stats *stats; +struct reftable_writer *writer; +struct reftable_reader *reader; +int err, i; + + writer =reftable_new_writer (&strbuf_add_void, &writer_buf, &opts); +reftable_writer_set_limits (writer,1 ,1 ); +for (i =0 ; i <100 ; i++) { +unsigned char hash[GIT_SHA1_RAWSZ ] = {i}; +struct reftable_ref_record ref = { + .update_index =1 , + .value_type =REFTABLE_REF_VAL1 , + .value.val1 = hash, + }; + +strbuf_reset (&buf); +strbuf_addf (&buf,"refs/heads/%04d" , i); + ref.refname = buf.buf, + + err =reftable_writer_add_ref (writer, &ref); +EXPECT_ERR (err); + } + +for (i =0 ; i <100 ; i++) { +unsigned char hash[GIT_SHA1_RAWSZ ] = {i}; +struct reftable_log_record log = { + .update_index =1 , + .value_type =REFTABLE_LOG_UPDATE , + .value.update = { + .old_hash = hash, + .new_hash = hash, + }, + }; + +strbuf_reset (&buf); +strbuf_addf (&buf,"refs/heads/%04d" , i); + log.refname = buf.buf, + + err =reftable_writer_add_log (writer, &log); +EXPECT_ERR (err); + } + +reftable_writer_close (writer); + +/* +* The written data should be sufficiently large to result in indices +* for each of the block types. +*/ + stats =reftable_writer_stats (writer); +EXPECT (stats->ref_stats.index_offset >0 ); +EXPECT (stats->obj_stats.index_offset >0 ); +EXPECT (stats->log_stats.index_offset >0 ); + +block_source_from_strbuf (&source, &writer_buf); + err =reftable_new_reader (&reader, &source,"filename" ); +EXPECT_ERR (err); + +/* +* Seeking the log uses the log index now. In case there is any +* confusion regarding indices we would notice here. +*/ + err =reftable_reader_seek_log (reader, &it,"" ); +EXPECT_ERR (err); + +reftable_iterator_destroy (&it); +reftable_writer_free (writer); +reftable_reader_free (reader); +strbuf_release (&writer_buf); +strbuf_release (&buf); +} +static void test_corrupt_table_empty (void ) {struct strbuf buf =STRBUF_INIT ;
@@ -847,5 +926,6 @@ int readwrite_test_main(int argc, const char *argv[])RUN_TEST (test_log_overflow);RUN_TEST (test_write_object_id_length);RUN_TEST (test_write_object_id_min_length); +RUN_TEST (test_write_multiple_indices);return 0 ; }
reftable/writer.c +2 -2
@@ -432,12 +432,12 @@ static int writer_finish_section(struct reftable_writer *w)reftable_free (idx); } -writer_clear_index (w); - err =writer_flush_block (w);if (err <0 )return err; +writer_clear_index (w); + bstats =writer_reftable_block_stats (w, typ); bstats->index_blocks = w->stats.idx_stats.blocks - before_blocks; bstats->index_offset = index_start;
Signature · 1 line
2.43.GIT
PATCH 3/7 reftable/record: constify some parts of the interface
In reply to Patrick SteinhardtWe're about to convert reftable records to stop storing their object IDs as allocated hashes. Prepare for this refactoring by constifying some parts of the interface that will be impacted by this.
--- reftable/record.c | 8 ++++---- reftable/reftable-record.h | 4 ++-- 2 files changed, 6 insertions(+), 6 deletions(-)
reftable/record.c +4 -4
@@ -76,7 +76,7 @@ int reftable_is_block_type(uint8_t typ)return 0 ; } -uint8_t *reftable_ref_record_val1 (const struct reftable_ref_record *rec) +const unsigned char *reftable_ref_record_val1 (const struct reftable_ref_record *rec) {switch (rec->value_type) {case REFTABLE_REF_VAL1 :
@@ -88,7 +88,7 @@ uint8_t *reftable_ref_record_val1(const struct reftable_ref_record *rec) } } -uint8_t *reftable_ref_record_val2 (const struct reftable_ref_record *rec) +const unsigned char *reftable_ref_record_val2 (const struct reftable_ref_record *rec) {switch (rec->value_type) {case REFTABLE_REF_VAL2 :
@@ -242,7 +242,7 @@ static char hexdigit(int c)return 'a' + (c -10 ); } -static void hex_format (char *dest,uint8_t *src,int hash_size) +static void hex_format (char *dest,const unsigned char *src,int hash_size) {assert (hash_size >0 );if (src) {
@@ -1164,7 +1164,7 @@ int reftable_record_equal(struct reftable_record *a, struct reftable_record *b, reftable_record_data(a), reftable_record_data(b), hash_size); } -static int hash_equal (uint8_t *a,uint8_t *b,int hash_size) +static int hash_equal (const unsigned char *a,const unsigned char *b,int hash_size) {if (a && b)return !memcmp (a, b, hash_size);
reftable/reftable-record.h +2 -2
@@ -49,11 +49,11 @@ struct reftable_ref_record {/* Returns the first hash, or NULL if `rec` is not of type * REFTABLE_REF_VAL1 or REFTABLE_REF_VAL2. */ -uint8_t *reftable_ref_record_val1 (const struct reftable_ref_record *rec); +const unsigned char *reftable_ref_record_val1 (const struct reftable_ref_record *rec);/* Returns the second hash, or NULL if `rec` is not of type * REFTABLE_REF_VAL2. */ -uint8_t *reftable_ref_record_val2 (const struct reftable_ref_record *rec); +const unsigned char *reftable_ref_record_val2 (const struct reftable_ref_record *rec);/* returns whether 'ref' represents a deletion */ int reftable_ref_record_is_deletion (const struct reftable_ref_record *ref);
Signature · 1 line
2.43.GIT
PATCH 4/7 reftable/record: store "val1" hashes as static arrays
In reply to Patrick SteinhardtWhen reading ref records of type "val1" we store its object ID in an allocated array. This results in an additional allocation for every single ref record we read, which is rather inefficient especially when iterating over refs.
Refactor the code to instead use a static array of GIT_MAX_RAWSZ bytes. While this means that struct ref_record is bigger now, we typically do not store all refs in an array anyway and instead only handle a limited number of records at the same point in time.
Using git show-ref --quiet in a repository with ~350k refs this leads to a significant drop in allocations. Before:
HEAP SUMMARY:
in use at exit: 21,098 bytes in 192 blocks
total heap usage: 2,116,683 allocs, 2,116,491 frees, 76,098,060 bytes allocated
After:
HEAP SUMMARY:
in use at exit: 21,098 bytes in 192 blocks
total heap usage: 1,419,031 allocs, 1,418,839 frees, 62,145,036 bytes allocated
--- reftable/block_test.c | 4 +--- reftable/merged_test.c | 16 ++++++---------- reftable/readwrite_test.c | 11 +++-------- reftable/record.c | 3 --- reftable/record_test.c | 1 - reftable/reftable-record.h | 2 +- reftable/stack_test.c | 2 -- 7 files changed, 11 insertions(+), 28 deletions(-)
reftable/block_test.c +1 -3
@@ -49,13 +49,11 @@ static void test_block_read_write(void)for (i =0 ; i <N ; i++) {char name[100 ]; -uint8_t hash[GIT_SHA1_RAWSZ ];snprintf (name,sizeof (name),"branch%02d" , i); -memset (hash, i,sizeof (hash)); rec.u.ref.refname = name; rec.u.ref.value_type =REFTABLE_REF_VAL1 ; - rec.u.ref.value.val1 = hash; +memset (rec.u.ref.value.val1, i,GIT_SHA1_RAWSZ ); names[i] =xstrdup (name); n =block_writer_add (&bw, &rec);
reftable/merged_test.c +6 -10
@@ -123,13 +123,11 @@ static void readers_destroy(struct reftable_reader **readers, size_t n)static void test_merged_between (void ) { -uint8_t hash1[GIT_SHA1_RAWSZ ] = {1 ,2 ,3 ,0 }; -struct reftable_ref_record r1[] = { { .refname ="b" , .update_index =1 , .value_type =REFTABLE_REF_VAL1 , - .value.val1 = hash1, + .value.val1 = {1 ,2 ,3 ,0 }, } };struct reftable_ref_record r2[] = { { .refname ="a" ,
@@ -165,26 +163,24 @@ static void test_merged_between(void)static void test_merged (void ) { -uint8_t hash1[GIT_SHA1_RAWSZ ] = {1 }; -uint8_t hash2[GIT_SHA1_RAWSZ ] = {2 };struct reftable_ref_record r1[] = { { .refname ="a" , .update_index =1 , .value_type =REFTABLE_REF_VAL1 , - .value.val1 = hash1, + .value.val1 = {1 }, }, { .refname ="b" , .update_index =1 , .value_type =REFTABLE_REF_VAL1 , - .value.val1 = hash1, + .value.val1 = {1 }, }, { .refname ="c" , .update_index =1 , .value_type =REFTABLE_REF_VAL1 , - .value.val1 = hash1, + .value.val1 = {1 }, } };struct reftable_ref_record r2[] = { {
@@ -197,13 +193,13 @@ static void test_merged(void) .refname = "c", .update_index = 3, .value_type = REFTABLE_REF_VAL1, - .value.val1 = hash2, + .value.val1 = { 2 }, }, { .refname = "d", .update_index = 3, .value_type = REFTABLE_REF_VAL1, - .value.val1 = hash1, + .value.val1 = { 1 }, }, };
reftable/readwrite_test.c +3 -8
@@ -60,18 +60,15 @@ static void write_table(char ***names, struct strbuf *buf, int N, *names =reftable_calloc (sizeof (char *) * (N +1 ));reftable_writer_set_limits (w, update_index, update_index);for (i =0 ; i <N ; i++) { -uint8_t hash[GIT_SHA256_RAWSZ ] = {0 };char name[100 ];int n; -set_test_hash (hash, i); -snprintf (name,sizeof (name),"refs/heads/branch%02d" , i); ref.refname = name; ref.update_index = update_index; ref.value_type =REFTABLE_REF_VAL1 ; - ref.value.val1 = hash; +set_test_hash (ref.value.val1, i); (*names)[i] =xstrdup (name); n =reftable_writer_add_ref (w, &ref);
@@ -675,11 +672,10 @@ static void test_write_object_id_min_length(void)struct strbuf buf =STRBUF_INIT ;struct reftable_writer *w =reftable_new_writer (&strbuf_add_void, &buf, &opts); -uint8_t hash[GIT_SHA1_RAWSZ ] = {42 };struct reftable_ref_record ref = { .update_index =1 , .value_type =REFTABLE_REF_VAL1 , - .value.val1 = hash, + .value.val1 = {42 }, };int err;int i;
@@ -711,11 +707,10 @@ static void test_write_object_id_length(void)struct strbuf buf =STRBUF_INIT ;struct reftable_writer *w =reftable_new_writer (&strbuf_add_void, &buf, &opts); -uint8_t hash[GIT_SHA1_RAWSZ ] = {42 };struct reftable_ref_record ref = { .update_index =1 , .value_type =REFTABLE_REF_VAL1 , - .value.val1 = hash, + .value.val1 = {42 }, };int err;int i;
reftable/record.c +0 -3
@@ -219,7 +219,6 @@ static void reftable_ref_record_copy_from(void *rec, const void *src_rec,case REFTABLE_REF_DELETION :break ;case REFTABLE_REF_VAL1 : - ref->value.val1 =reftable_malloc (hash_size);memcpy (ref->value.val1, src->value.val1, hash_size);break ;case REFTABLE_REF_VAL2 :
@@ -303,7 +302,6 @@ void reftable_ref_record_release(struct reftable_ref_record *ref)reftable_free (ref->value.val2.value);break ;case REFTABLE_REF_VAL1 : -reftable_free (ref->value.val1);break ;case REFTABLE_REF_DELETION :break ;
@@ -394,7 +392,6 @@ static int reftable_ref_record_decode(void *rec, struct strbuf key,return -1 ; } - r->value.val1 =reftable_malloc (hash_size);memcpy (r->value.val1, in.buf, hash_size);string_view_consume (&in, hash_size);break ;
reftable/record_test.c +0 -1
@@ -119,7 +119,6 @@ static void test_reftable_ref_record_roundtrip(void)case REFTABLE_REF_DELETION :break ;case REFTABLE_REF_VAL1 : - in.u.ref.value.val1 =reftable_malloc (GIT_SHA1_RAWSZ );set_hash (in.u.ref.value.val1,1 );break ;case REFTABLE_REF_VAL2 :
reftable/reftable-record.h +1 -1
@@ -38,7 +38,7 @@ struct reftable_ref_record {#define REFTABLE_NR_REF_VALUETYPES 4 } value_type;union { -uint8_t *val1;/* malloced hash. */ +unsigned char val1[GIT_MAX_RAWSZ ];struct {uint8_t *value;/* first value, malloced hash */ uint8_t *target_value;/* second value, malloced hash */
reftable/stack_test.c +0 -2
@@ -463,7 +463,6 @@ static void test_reftable_stack_add(void) refs[i].refname =xstrdup (buf); refs[i].update_index = i +1 ; refs[i].value_type =REFTABLE_REF_VAL1 ; - refs[i].value.val1 =reftable_malloc (GIT_SHA1_RAWSZ );set_test_hash (refs[i].value.val1, i); logs[i].refname =xstrdup (buf);
@@ -600,7 +599,6 @@ static void test_reftable_stack_tombstone(void) refs[i].update_index = i +1 ;if (i %2 ==0 ) { refs[i].value_type =REFTABLE_REF_VAL1 ; - refs[i].value.val1 =reftable_malloc (GIT_SHA1_RAWSZ );set_test_hash (refs[i].value.val1, i); }
Signature · 1 line
2.43.GIT
PATCH 5/7 reftable/record: store "val2" hashes as static arrays
In reply to Patrick SteinhardtSimilar to the preceding commit, convert ref records of type "val2" to store their object IDs in static arrays instead of allocating them for every single record.
We're using the same benchmark as in the preceding commit, with git show-ref --quiet in a repository with ~350k refs. This time around though the effects aren't this huge. Before:
HEAP SUMMARY:
in use at exit: 21,163 bytes in 193 blocks
total heap usage: 1,419,040 allocs, 1,418,847 frees, 62,153,868 bytes allocated
After:
HEAP SUMMARY:
in use at exit: 21,163 bytes in 193 blocks
total heap usage: 1,410,148 allocs, 1,409,955 frees, 61,976,068 bytes allocated
This is because "val2"-type records are typically only stored for peeled tags, and the number of annotated tags in the benchmark repository is rather low. Still, it can be seen that this change leads to a reduction of allocations overall, even if only a small one.
--- reftable/readwrite_test.c | 12 ++++-------- reftable/record.c | 6 ------ reftable/record_test.c | 4 ---- reftable/reftable-record.h | 4 ++-- 4 files changed, 6 insertions(+), 20 deletions(-)
reftable/readwrite_test.c +4 -8
@@ -547,8 +547,6 @@ static void test_table_refs_for(int indexed)uint8_t hash[GIT_SHA1_RAWSZ ];char fill[51 ] = {0 };char name[100 ]; -uint8_t hash1[GIT_SHA1_RAWSZ ]; -uint8_t hash2[GIT_SHA1_RAWSZ ];struct reftable_ref_record ref = {NULL };memset (hash, i,sizeof (hash));
@@ -558,11 +556,9 @@ static void test_table_refs_for(int indexed) name[40 ] =0 ; ref.refname = name; -set_test_hash (hash1, i /4 ); -set_test_hash (hash2,3 + i /4 ); ref.value_type =REFTABLE_REF_VAL2 ; - ref.value.val2.value = hash1; - ref.value.val2.target_value = hash2; +set_test_hash (ref.value.val2.value, i /4 ); +set_test_hash (ref.value.val2.target_value,3 + i /4 );/* 80 bytes / entry, so 3 entries per block. Yields 17 */
@@ -570,8 +566,8 @@ static void test_table_refs_for(int indexed) n =reftable_writer_add_ref (w, &ref);EXPECT (n ==0 ); -if (!memcmp (hash1, want_hash,GIT_SHA1_RAWSZ ) || - !memcmp (hash2, want_hash,GIT_SHA1_RAWSZ )) { +if (!memcmp (ref.value.val2.value, want_hash,GIT_SHA1_RAWSZ ) || + !memcmp (ref.value.val2.target_value, want_hash,GIT_SHA1_RAWSZ )) { want_names[want_names_len++] =xstrdup (name); } }
reftable/record.c +0 -6
@@ -222,9 +222,7 @@ static void reftable_ref_record_copy_from(void *rec, const void *src_rec,memcpy (ref->value.val1, src->value.val1, hash_size);break ;case REFTABLE_REF_VAL2 : - ref->value.val2.value =reftable_malloc (hash_size);memcpy (ref->value.val2.value, src->value.val2.value, hash_size); - ref->value.val2.target_value =reftable_malloc (hash_size);memcpy (ref->value.val2.target_value, src->value.val2.target_value, hash_size);break ;
@@ -298,8 +296,6 @@ void reftable_ref_record_release(struct reftable_ref_record *ref)reftable_free (ref->value.symref);break ;case REFTABLE_REF_VAL2 : -reftable_free (ref->value.val2.target_value); -reftable_free (ref->value.val2.value);break ;case REFTABLE_REF_VAL1 :break ;
@@ -401,11 +397,9 @@ static int reftable_ref_record_decode(void *rec, struct strbuf key,return -1 ; } - r->value.val2.value =reftable_malloc (hash_size);memcpy (r->value.val2.value, in.buf, hash_size);string_view_consume (&in, hash_size); - r->value.val2.target_value =reftable_malloc (hash_size);memcpy (r->value.val2.target_value, in.buf, hash_size);string_view_consume (&in, hash_size);break ;
reftable/record_test.c +0 -4
@@ -122,11 +122,7 @@ static void test_reftable_ref_record_roundtrip(void)set_hash (in.u.ref.value.val1,1 );break ;case REFTABLE_REF_VAL2 : - in.u.ref.value.val2.value = -reftable_malloc (GIT_SHA1_RAWSZ );set_hash (in.u.ref.value.val2.value,1 ); - in.u.ref.value.val2.target_value = -reftable_malloc (GIT_SHA1_RAWSZ );set_hash (in.u.ref.value.val2.target_value,2 );break ;case REFTABLE_REF_SYMREF :
reftable/reftable-record.h +2 -2
@@ -40,8 +40,8 @@ struct reftable_ref_record {union {unsigned char val1[GIT_MAX_RAWSZ ];struct { -uint8_t *value;/* first value, malloced hash */ -uint8_t *target_value;/* second value, malloced hash */ +unsigned char value[GIT_MAX_RAWSZ ];/* first hash */ +unsigned char target_value[GIT_MAX_RAWSZ ];/* second hash */ } val2;char *symref;/* referent, malloced 0-terminated string */ } value;
Signature · 1 line
2.43.GIT
PATCH 6/7 reftable/merged: really reuse buffers to compute record keys
In reply to Patrick SteinhardtIn 829231dc20 (reftable/merged: reuse buffer to compute record keys, 2023-12-11), we have refactored the merged iterator to reuse a set of buffers that it would otherwise have to reallocate on every single iteration. Unfortunately, there was a brown-paper-bag-style bug here as we continue to release these buffers after the iteration, and thus we have essentially gained nothing.
Fix this performance issue by not releasing those buffers on iteration anymore, where we instead rely on merged_iter_close() to release the buffers for us.
Using git show-ref --quiet in a repository with ~350k refs this leads to a significant drop in allocations. Before:
HEAP SUMMARY:
in use at exit: 21,163 bytes in 193 blocks
total heap usage: 1,410,148 allocs, 1,409,955 frees, 61,976,068 bytes allocated
After:
HEAP SUMMARY:
in use at exit: 21,163 bytes in 193 blocks
total heap usage: 708,058 allocs, 707,865 frees, 36,783,255 bytes allocated
--- reftable/merged.c | 2 -- 1 file changed, 2 deletions(-)
reftable/merged.c +0 -2
@@ -128,8 +128,6 @@ static int merged_iter_next_entry(struct merged_iter *mi, done:reftable_record_release (&entry.rec); -strbuf_release (&mi->entry_key); -strbuf_release (&mi->key);return err; }
Signature · 1 line
2.43.GIT
PATCH 7/7 reftable/merged: transfer ownership of records when iterating
In reply to Patrick SteinhardtWhen iterating over recods with the merged iterator we put the records into a priority queue before yielding them to the caller. This means that we need to allocate the contents of these records before we can pass them over to the caller.
The handover to the caller is quite inefficient though because we first deallocate the record passed in by the caller and then copy over the new record, which requires us to reallocate memory.
Refactor the code to instead transfer ownership of the new record to the caller. So instead of reallocating all contents, we now release the old record and then copy contents of the new record into place.
The following benchmark of git show-ref --quiet in a repository with around 350k refs shows a clear improvement. Before:
HEAP SUMMARY:
in use at exit: 21,163 bytes in 193 blocks
total heap usage: 708,058 allocs, 707,865 frees, 36,783,255 bytes allocated
After:
HEAP SUMMARY:
in use at exit: 21,163 bytes in 193 blocks
total heap usage: 357,007 allocs, 356,814 frees, 24,193,602 bytes allocated
This shows that we now have roundabout a single allocation per record that we're yielding from the iterator. Ideally, we'd also get rid of this allocation so that the number of allocations doesn't scale with the number of refs anymore. This would require some larger surgery though because the memory is owned by the priority queue before transferring it over to the caller.
--- reftable/merged.c | 6 ++++-- 1 file changed, 4 insertions(+), 2 deletions(-)
reftable/merged.c +4 -2
@@ -124,10 +124,12 @@ static int merged_iter_next_entry(struct merged_iter *mi,reftable_record_release (&top.rec); } -reftable_record_copy_from (rec, &entry.rec,hash_size (mi->hash_id)); +reftable_record_release (rec); + *rec = entry.rec; done: -reftable_record_release (&entry.rec); +if (err) +reftable_record_release (&entry.rec);return err; }
Signature · 1 line
2.43.GIT
Re: [PATCH 4/7] reftable/record: store "val1" hashes as static arrays
In reply to Patrick SteinhardtQuoted 17 lines · Patrick Steinhardt
When reading ref records of type "val1" we store its object ID in an allocated array. This results in an additional allocation for every single ref record we read, which is rather inefficient especially when iterating over refs.
Refactor the code to instead use a static array of
GIT_MAX_RAWSZbytes. While this means thatstruct ref_recordis bigger now, we typically do not store all refs in an array anyway and instead only handle a limited number of records at the same point in time.Using
git show-ref --quietin a repository with ~350k refs this leads to a significant drop in allocations. Before:HEAP SUMMARY:
in use at exit: 21,098 bytes in 192 blocks
total heap usage: 2,116,683 allocs, 2,116,491 frees, 76,098,060 bytes allocated
Quoted 7 lines
After:
HEAP SUMMARY:
in use at exit: 21,098 bytes in 192 blocks
total heap usage: 1,419,031 allocs, 1,418,839 frees, 62,145,036 bytes allocatedSigned-off-by Patrick Steinhardt <[email protected]>
I screwed up the rebase. The following diff is required on top:
reftable/readwrite_test.c +1 -2
@@ -809,11 +809,10 @@ static void test_write_multiple_indices(void) writer =reftable_new_writer (&strbuf_add_void, &writer_buf, &opts);reftable_writer_set_limits (writer,1 ,1 );for (i =0 ; i <100 ; i++) { -unsigned char hash[GIT_SHA1_RAWSZ ] = {i};struct reftable_ref_record ref = { .update_index =1 , .value_type =REFTABLE_REF_VAL1 , - .value.val1 = hash, + .value.val1 = {i}, };strbuf_reset (&buf);
Will fix in v2 of this series.
Patrick
Quoted 8 lines · Patrick Steinhardt
Patrick Steinhardt (7):
reftable/stack: do not overwrite errors when compacting reftable/writer: fix index corruption when writing multiple indices reftable/record: constify some parts of the interface reftable/record: store "val1" hashes as static arrays reftable/record: store "val2" hashes as static arrays reftable/merged: really reuse buffers to compute record keys reftable/merged: transfer ownership of records when iterating
Something like this need to be split and sprinkled into relevant steps in v2 in order to pass "make hdr-check", it seems.
reftable/reftable-record.h | 1 + reftable/reftable-stack.h | 1 + 2 files changed, 2 insertions(+)
reftable/reftable-record.h +1 -0
@@ -9,6 +9,7 @@ license that can be found in the LICENSE file or at#ifndef REFTABLE_RECORD_H #define REFTABLE_RECORD_H +#include <hash-ll.h> #include <stdint.h> /*
reftable/reftable-stack.h +1 -0
@@ -9,6 +9,7 @@ license that can be found in the LICENSE file or at#ifndef REFTABLE_STACK_H #define REFTABLE_STACK_H +#include <hash-ll.h> #include "reftable-writer.h" /*
v2 cover reftable: fixes and optimizations (pt.2)
In reply to Patrick SteinhardtHi,
this is the second version of my patch series that contains additional fixes and optimizations for the reftable library. Changes compared to v1:
- Added a patch to not auto-compact twice in reftable_stack_add(), reported by Han-Wen.
- Fixed an issue I've previously introduced while rebasing the patch series.
- Fixed a missing header, as reported by Junio.
Due to the added patch that avoids double auto-compaction this patch series now depends on 637e34a783 (Merge branch 'ps/reftable-fixes', 2023-12-27).
Patrick
Patrick Steinhardt (8):
reftable/stack: do not overwrite errors when compacting reftable/stack: do not auto-compact twice in reftable_stack_add() reftable/writer: fix index corruption when writing multiple indices reftable/record: constify some parts of the interface reftable/record: store "val1" hashes as static arrays reftable/record: store "val2" hashes as static arrays reftable/merged: really reuse buffers to compute record keys reftable/merged: transfer ownership of records when iterating
reftable/block_test.c | 4 +- reftable/merged.c | 8 +-- reftable/merged_test.c | 16 +++--- reftable/readwrite_test.c | 102 +++++++++++++++++++++++++++++++------ reftable/record.c | 17 ++----- reftable/record_test.c | 5 -- reftable/reftable-record.h | 11 ++-- reftable/stack.c | 23 +++------ reftable/stack_test.c | 2 - reftable/writer.c | 4 +- 10 files changed, 117 insertions(+), 75 deletions(-)
Range-diff against v1:
1: 573fb2c4fb = 1: 22a57020c6 reftable/stack: do not overwrite errors when compacting -: ---------- > 2: a08f7efc99 reftable/stack: do not auto-compact twice in `reftable_stack_add()` 2: 86ee79c48d = 3: c00e08d97f reftable/writer: fix index corruption when writing multiple indices 3: 3ad4a0e5b9 = 4: 3416268087 reftable/record: constify some parts of the interface 4: 06c9eab678 ! 5: 46ca3a37f8 reftable/record: store "val1" hashes as static arrays
@@ reftable/readwrite_test.c: static void test_write_object_id_length(void)
};
int err;
int i;
+@@ reftable/readwrite_test.c: static void test_write_multiple_indices(void)
+ writer = reftable_new_writer(&strbuf_add_void, &writer_buf, &opts);
+ reftable_writer_set_limits(writer, 1, 1);
+ for (i = 0; i < 100; i++) {
+- unsigned char hash[GIT_SHA1_RAWSZ] = {i};
+ struct reftable_ref_record ref = {
+ .update_index = 1,
+ .value_type = REFTABLE_REF_VAL1,
+- .value.val1 = hash,
++ .value.val1 = {i},
+ };
+
+ strbuf_reset(&buf);
## reftable/record.c ##
@@ reftable/record.c: static void reftable_ref_record_copy_from(void *rec, const void *src_rec,
@@ reftable/record_test.c: static void test_reftable_ref_record_roundtrip(void)
case REFTABLE_REF_VAL2:
## reftable/reftable-record.h ##
+@@ reftable/reftable-record.h: license that can be found in the LICENSE file or at
+ #ifndef REFTABLE_RECORD_H
+ #define REFTABLE_RECORD_H
+
++#include "hash-ll.h"
+ #include <stdint.h>
+
+ /*
@@ reftable/reftable-record.h: struct reftable_ref_record {
#define REFTABLE_NR_REF_VALUETYPES 4
} value_type;
5: 49f13c123f = 6: c8a36917b1 reftable/record: store "val2" hashes as static arrays 6: 32b7ddee28 = 7: 6313f8affd reftable/merged: really reuse buffers to compute record keys 7: 3dbabea22a = 8: 25a3919e58 reftable/merged: transfer ownership of records when iterating
Signature · 1 line
2.43.GIT
PATCH v2 1/8 reftable/stack: do not overwrite errors when compacting
In order to compact multiple stacks we iterate through the merged ref and log records. When there is any error either when reading the records from the old merged table or when writing the records to the new table then we break out of the respective loops. When breaking out of the loop for the ref records though the error code will be overwritten, which may cause us to inadvertently skip over bad ref records. In the worst case, this can lead to a compacted stack that is missing records.
Fix the code by using goto done instead so that any potential error codes are properly returned to the caller.
--- reftable/stack.c | 20 ++++++++------------ 1 file changed, 8 insertions(+), 12 deletions(-)
reftable/stack.c +8 -12
@@ -801,18 +801,16 @@ static int stack_write_compact(struct reftable_stack *st, err =0 ;break ; } -if (err <0 ) { -break ; - } +if (err <0 ) + goto done;if (first ==0 &&reftable_ref_record_is_deletion (&ref)) {continue ; } err =reftable_writer_add_ref (wr, &ref); -if (err <0 ) { -break ; - } +if (err <0 ) + goto done; entries++; }reftable_iterator_destroy (&it);
@@ -827,9 +825,8 @@ static int stack_write_compact(struct reftable_stack *st, err =0 ;break ; } -if (err <0 ) { -break ; - } +if (err <0 ) + goto done;if (first ==0 &&reftable_log_record_is_deletion (&log)) {continue ; }
@@ -845,9 +842,8 @@ static int stack_write_compact(struct reftable_stack *st, } err =reftable_writer_add_log (wr, &log); -if (err <0 ) { -break ; - } +if (err <0 ) + goto done; entries++; }
Signature · 1 line
2.43.GIT
PATCH v2 2/8 reftable/stack: do not auto-compact twice in `reftable_stack_add()`
In reply to Patrick SteinhardtIn 5c086453ff (reftable/stack: perform auto-compaction with transactional interface, 2023-12-11), we fixed a bug where the transactional interface to add changes to a reftable stack did not perform auto-compaction by calling reftable_stack_auto_compact() in reftable_stack_addition_commit(). While correct, this change may now cause us to perform auto-compaction twice in the non-transactional interface reftable_stack_add():
- It performs auto-compaction by itself.
- It now transitively performs auto-compaction via the transactional interface.
Remove the first instance so that we only end up doing auto-compaction once.
--- reftable/stack.c | 3 --- 1 file changed, 3 deletions(-)
reftable/stack.c +0 -3
@@ -425,9 +425,6 @@ int reftable_stack_add(struct reftable_stack *st,return err; } -if (!st->disable_auto_compact) -return reftable_stack_auto_compact (st); -return 0 ; }
Signature · 1 line
2.43.GIT
PATCH v2 3/8 reftable/writer: fix index corruption when writing multiple indices
In reply to Patrick SteinhardtEach reftable may contain multiple types of blocks for refs, objects and reflog records, where each of these may have an index that makes it more efficient to find the records. It was observed that the index for log records can become corrupted under certain circumstances, where the first entry of the index points into the object index instead of to the log records.
As it turns out, this corruption can occur whenever we write a log index as well as at least one additional index. Writing records and their index is basically a two-step process:
1. We write all blocks for the corresponding record. Each block that gets written is added to a list of blocks to index.
2. Once all blocks were written we finish the section. If at least two blocks have been added to the list of blocks to index then we will now write the index for those blocks and flush it, as well.
When we have a very large number of blocks then we may decide to write a multi-level index, which is why we also keep track of the list of the index blocks in the same way as we previously kept track of the blocks to index.
Now when we have finished writing all index blocks we clear the index and flush the last block to disk. This is done in the wrong order though because flushing the block to disk will re-add it to the list of blocks to be indexed. The result is that the next section we are about to write will have an entry in the list of blocks to index that points to the last block of the preceding section's index, which will corrupt the log index.
Fix this corruption by clearing the index after having written the last block.
--- reftable/readwrite_test.c | 80 +++++++++++++++++++++++++++++++++++++++ reftable/writer.c | 4 +- 2 files changed, 82 insertions(+), 2 deletions(-)
reftable/readwrite_test.c +80 -0
@@ -798,6 +798,85 @@ static void test_write_key_order(void)strbuf_release (&buf); } +static void test_write_multiple_indices (void ) +{ +struct reftable_write_options opts = { + .block_size =100 , + }; +struct strbuf writer_buf =STRBUF_INIT , buf =STRBUF_INIT ; +struct reftable_block_source source = {0 }; +struct reftable_iterator it = {0 }; +const struct reftable_stats *stats; +struct reftable_writer *writer; +struct reftable_reader *reader; +int err, i; + + writer =reftable_new_writer (&strbuf_add_void, &writer_buf, &opts); +reftable_writer_set_limits (writer,1 ,1 ); +for (i =0 ; i <100 ; i++) { +unsigned char hash[GIT_SHA1_RAWSZ ] = {i}; +struct reftable_ref_record ref = { + .update_index =1 , + .value_type =REFTABLE_REF_VAL1 , + .value.val1 = hash, + }; + +strbuf_reset (&buf); +strbuf_addf (&buf,"refs/heads/%04d" , i); + ref.refname = buf.buf, + + err =reftable_writer_add_ref (writer, &ref); +EXPECT_ERR (err); + } + +for (i =0 ; i <100 ; i++) { +unsigned char hash[GIT_SHA1_RAWSZ ] = {i}; +struct reftable_log_record log = { + .update_index =1 , + .value_type =REFTABLE_LOG_UPDATE , + .value.update = { + .old_hash = hash, + .new_hash = hash, + }, + }; + +strbuf_reset (&buf); +strbuf_addf (&buf,"refs/heads/%04d" , i); + log.refname = buf.buf, + + err =reftable_writer_add_log (writer, &log); +EXPECT_ERR (err); + } + +reftable_writer_close (writer); + +/* +* The written data should be sufficiently large to result in indices +* for each of the block types. +*/ + stats =reftable_writer_stats (writer); +EXPECT (stats->ref_stats.index_offset >0 ); +EXPECT (stats->obj_stats.index_offset >0 ); +EXPECT (stats->log_stats.index_offset >0 ); + +block_source_from_strbuf (&source, &writer_buf); + err =reftable_new_reader (&reader, &source,"filename" ); +EXPECT_ERR (err); + +/* +* Seeking the log uses the log index now. In case there is any +* confusion regarding indices we would notice here. +*/ + err =reftable_reader_seek_log (reader, &it,"" ); +EXPECT_ERR (err); + +reftable_iterator_destroy (&it); +reftable_writer_free (writer); +reftable_reader_free (reader); +strbuf_release (&writer_buf); +strbuf_release (&buf); +} +static void test_corrupt_table_empty (void ) {struct strbuf buf =STRBUF_INIT ;
@@ -847,5 +926,6 @@ int readwrite_test_main(int argc, const char *argv[])RUN_TEST (test_log_overflow);RUN_TEST (test_write_object_id_length);RUN_TEST (test_write_object_id_min_length); +RUN_TEST (test_write_multiple_indices);return 0 ; }
reftable/writer.c +2 -2
@@ -432,12 +432,12 @@ static int writer_finish_section(struct reftable_writer *w)reftable_free (idx); } -writer_clear_index (w); - err =writer_flush_block (w);if (err <0 )return err; +writer_clear_index (w); + bstats =writer_reftable_block_stats (w, typ); bstats->index_blocks = w->stats.idx_stats.blocks - before_blocks; bstats->index_offset = index_start;
Signature · 1 line
2.43.GIT
PATCH v2 4/8 reftable/record: constify some parts of the interface
In reply to Patrick SteinhardtWe're about to convert reftable records to stop storing their object IDs as allocated hashes. Prepare for this refactoring by constifying some parts of the interface that will be impacted by this.
--- reftable/record.c | 8 ++++---- reftable/reftable-record.h | 4 ++-- 2 files changed, 6 insertions(+), 6 deletions(-)
reftable/record.c +4 -4
@@ -76,7 +76,7 @@ int reftable_is_block_type(uint8_t typ)return 0 ; } -uint8_t *reftable_ref_record_val1 (const struct reftable_ref_record *rec) +const unsigned char *reftable_ref_record_val1 (const struct reftable_ref_record *rec) {switch (rec->value_type) {case REFTABLE_REF_VAL1 :
@@ -88,7 +88,7 @@ uint8_t *reftable_ref_record_val1(const struct reftable_ref_record *rec) } } -uint8_t *reftable_ref_record_val2 (const struct reftable_ref_record *rec) +const unsigned char *reftable_ref_record_val2 (const struct reftable_ref_record *rec) {switch (rec->value_type) {case REFTABLE_REF_VAL2 :
@@ -242,7 +242,7 @@ static char hexdigit(int c)return 'a' + (c -10 ); } -static void hex_format (char *dest,uint8_t *src,int hash_size) +static void hex_format (char *dest,const unsigned char *src,int hash_size) {assert (hash_size >0 );if (src) {
@@ -1164,7 +1164,7 @@ int reftable_record_equal(struct reftable_record *a, struct reftable_record *b, reftable_record_data(a), reftable_record_data(b), hash_size); } -static int hash_equal (uint8_t *a,uint8_t *b,int hash_size) +static int hash_equal (const unsigned char *a,const unsigned char *b,int hash_size) {if (a && b)return !memcmp (a, b, hash_size);
reftable/reftable-record.h +2 -2
@@ -49,11 +49,11 @@ struct reftable_ref_record {/* Returns the first hash, or NULL if `rec` is not of type * REFTABLE_REF_VAL1 or REFTABLE_REF_VAL2. */ -uint8_t *reftable_ref_record_val1 (const struct reftable_ref_record *rec); +const unsigned char *reftable_ref_record_val1 (const struct reftable_ref_record *rec);/* Returns the second hash, or NULL if `rec` is not of type * REFTABLE_REF_VAL2. */ -uint8_t *reftable_ref_record_val2 (const struct reftable_ref_record *rec); +const unsigned char *reftable_ref_record_val2 (const struct reftable_ref_record *rec);/* returns whether 'ref' represents a deletion */ int reftable_ref_record_is_deletion (const struct reftable_ref_record *ref);
Signature · 1 line
2.43.GIT
PATCH v2 5/8 reftable/record: store "val1" hashes as static arrays
In reply to Patrick SteinhardtWhen reading ref records of type "val1" we store its object ID in an allocated array. This results in an additional allocation for every single ref record we read, which is rather inefficient especially when iterating over refs.
Refactor the code to instead use a static array of GIT_MAX_RAWSZ bytes. While this means that struct ref_record is bigger now, we typically do not store all refs in an array anyway and instead only handle a limited number of records at the same point in time.
Using git show-ref --quiet in a repository with ~350k refs this leads to a significant drop in allocations. Before:
HEAP SUMMARY:
in use at exit: 21,098 bytes in 192 blocks
total heap usage: 2,116,683 allocs, 2,116,491 frees, 76,098,060 bytes allocated
After:
HEAP SUMMARY:
in use at exit: 21,098 bytes in 192 blocks
total heap usage: 1,419,031 allocs, 1,418,839 frees, 62,145,036 bytes allocated
--- reftable/block_test.c | 4 +--- reftable/merged_test.c | 16 ++++++---------- reftable/readwrite_test.c | 14 ++++---------- reftable/record.c | 3 --- reftable/record_test.c | 1 - reftable/reftable-record.h | 3 ++- reftable/stack_test.c | 2 -- 7 files changed, 13 insertions(+), 30 deletions(-)
reftable/block_test.c +1 -3
@@ -49,13 +49,11 @@ static void test_block_read_write(void)for (i =0 ; i <N ; i++) {char name[100 ]; -uint8_t hash[GIT_SHA1_RAWSZ ];snprintf (name,sizeof (name),"branch%02d" , i); -memset (hash, i,sizeof (hash)); rec.u.ref.refname = name; rec.u.ref.value_type =REFTABLE_REF_VAL1 ; - rec.u.ref.value.val1 = hash; +memset (rec.u.ref.value.val1, i,GIT_SHA1_RAWSZ ); names[i] =xstrdup (name); n =block_writer_add (&bw, &rec);
reftable/merged_test.c +6 -10
@@ -123,13 +123,11 @@ static void readers_destroy(struct reftable_reader **readers, size_t n)static void test_merged_between (void ) { -uint8_t hash1[GIT_SHA1_RAWSZ ] = {1 ,2 ,3 ,0 }; -struct reftable_ref_record r1[] = { { .refname ="b" , .update_index =1 , .value_type =REFTABLE_REF_VAL1 , - .value.val1 = hash1, + .value.val1 = {1 ,2 ,3 ,0 }, } };struct reftable_ref_record r2[] = { { .refname ="a" ,
@@ -165,26 +163,24 @@ static void test_merged_between(void)static void test_merged (void ) { -uint8_t hash1[GIT_SHA1_RAWSZ ] = {1 }; -uint8_t hash2[GIT_SHA1_RAWSZ ] = {2 };struct reftable_ref_record r1[] = { { .refname ="a" , .update_index =1 , .value_type =REFTABLE_REF_VAL1 , - .value.val1 = hash1, + .value.val1 = {1 }, }, { .refname ="b" , .update_index =1 , .value_type =REFTABLE_REF_VAL1 , - .value.val1 = hash1, + .value.val1 = {1 }, }, { .refname ="c" , .update_index =1 , .value_type =REFTABLE_REF_VAL1 , - .value.val1 = hash1, + .value.val1 = {1 }, } };struct reftable_ref_record r2[] = { {
@@ -197,13 +193,13 @@ static void test_merged(void) .refname = "c", .update_index = 3, .value_type = REFTABLE_REF_VAL1, - .value.val1 = hash2, + .value.val1 = { 2 }, }, { .refname = "d", .update_index = 3, .value_type = REFTABLE_REF_VAL1, - .value.val1 = hash1, + .value.val1 = { 1 }, }, };
reftable/readwrite_test.c +4 -10
@@ -60,18 +60,15 @@ static void write_table(char ***names, struct strbuf *buf, int N, *names =reftable_calloc (sizeof (char *) * (N +1 ));reftable_writer_set_limits (w, update_index, update_index);for (i =0 ; i <N ; i++) { -uint8_t hash[GIT_SHA256_RAWSZ ] = {0 };char name[100 ];int n; -set_test_hash (hash, i); -snprintf (name,sizeof (name),"refs/heads/branch%02d" , i); ref.refname = name; ref.update_index = update_index; ref.value_type =REFTABLE_REF_VAL1 ; - ref.value.val1 = hash; +set_test_hash (ref.value.val1, i); (*names)[i] =xstrdup (name); n =reftable_writer_add_ref (w, &ref);
@@ -675,11 +672,10 @@ static void test_write_object_id_min_length(void)struct strbuf buf =STRBUF_INIT ;struct reftable_writer *w =reftable_new_writer (&strbuf_add_void, &buf, &opts); -uint8_t hash[GIT_SHA1_RAWSZ ] = {42 };struct reftable_ref_record ref = { .update_index =1 , .value_type =REFTABLE_REF_VAL1 , - .value.val1 = hash, + .value.val1 = {42 }, };int err;int i;
@@ -711,11 +707,10 @@ static void test_write_object_id_length(void)struct strbuf buf =STRBUF_INIT ;struct reftable_writer *w =reftable_new_writer (&strbuf_add_void, &buf, &opts); -uint8_t hash[GIT_SHA1_RAWSZ ] = {42 };struct reftable_ref_record ref = { .update_index =1 , .value_type =REFTABLE_REF_VAL1 , - .value.val1 = hash, + .value.val1 = {42 }, };int err;int i;
@@ -814,11 +809,10 @@ static void test_write_multiple_indices(void) writer =reftable_new_writer (&strbuf_add_void, &writer_buf, &opts);reftable_writer_set_limits (writer,1 ,1 );for (i =0 ; i <100 ; i++) { -unsigned char hash[GIT_SHA1_RAWSZ ] = {i};struct reftable_ref_record ref = { .update_index =1 , .value_type =REFTABLE_REF_VAL1 , - .value.val1 = hash, + .value.val1 = {i}, };strbuf_reset (&buf);
reftable/record.c +0 -3
@@ -219,7 +219,6 @@ static void reftable_ref_record_copy_from(void *rec, const void *src_rec,case REFTABLE_REF_DELETION :break ;case REFTABLE_REF_VAL1 : - ref->value.val1 =reftable_malloc (hash_size);memcpy (ref->value.val1, src->value.val1, hash_size);break ;case REFTABLE_REF_VAL2 :
@@ -303,7 +302,6 @@ void reftable_ref_record_release(struct reftable_ref_record *ref)reftable_free (ref->value.val2.value);break ;case REFTABLE_REF_VAL1 : -reftable_free (ref->value.val1);break ;case REFTABLE_REF_DELETION :break ;
@@ -394,7 +392,6 @@ static int reftable_ref_record_decode(void *rec, struct strbuf key,return -1 ; } - r->value.val1 =reftable_malloc (hash_size);memcpy (r->value.val1, in.buf, hash_size);string_view_consume (&in, hash_size);break ;
reftable/record_test.c +0 -1
@@ -119,7 +119,6 @@ static void test_reftable_ref_record_roundtrip(void)case REFTABLE_REF_DELETION :break ;case REFTABLE_REF_VAL1 : - in.u.ref.value.val1 =reftable_malloc (GIT_SHA1_RAWSZ );set_hash (in.u.ref.value.val1,1 );break ;case REFTABLE_REF_VAL2 :
reftable/reftable-record.h +2 -1
@@ -9,6 +9,7 @@ license that can be found in the LICENSE file or at#ifndef REFTABLE_RECORD_H #define REFTABLE_RECORD_H +#include "hash-ll.h" #include <stdint.h> /*
@@ -38,7 +39,7 @@ struct reftable_ref_record {#define REFTABLE_NR_REF_VALUETYPES 4 } value_type;union { -uint8_t *val1;/* malloced hash. */ +unsigned char val1[GIT_MAX_RAWSZ ];struct {uint8_t *value;/* first value, malloced hash */ uint8_t *target_value;/* second value, malloced hash */
reftable/stack_test.c +0 -2
@@ -463,7 +463,6 @@ static void test_reftable_stack_add(void) refs[i].refname =xstrdup (buf); refs[i].update_index = i +1 ; refs[i].value_type =REFTABLE_REF_VAL1 ; - refs[i].value.val1 =reftable_malloc (GIT_SHA1_RAWSZ );set_test_hash (refs[i].value.val1, i); logs[i].refname =xstrdup (buf);
@@ -600,7 +599,6 @@ static void test_reftable_stack_tombstone(void) refs[i].update_index = i +1 ;if (i %2 ==0 ) { refs[i].value_type =REFTABLE_REF_VAL1 ; - refs[i].value.val1 =reftable_malloc (GIT_SHA1_RAWSZ );set_test_hash (refs[i].value.val1, i); }
Signature · 1 line
2.43.GIT
PATCH v2 6/8 reftable/record: store "val2" hashes as static arrays
In reply to Patrick SteinhardtSimilar to the preceding commit, convert ref records of type "val2" to store their object IDs in static arrays instead of allocating them for every single record.
We're using the same benchmark as in the preceding commit, with git show-ref --quiet in a repository with ~350k refs. This time around though the effects aren't this huge. Before:
HEAP SUMMARY:
in use at exit: 21,163 bytes in 193 blocks
total heap usage: 1,419,040 allocs, 1,418,847 frees, 62,153,868 bytes allocated
After:
HEAP SUMMARY:
in use at exit: 21,163 bytes in 193 blocks
total heap usage: 1,410,148 allocs, 1,409,955 frees, 61,976,068 bytes allocated
This is because "val2"-type records are typically only stored for peeled tags, and the number of annotated tags in the benchmark repository is rather low. Still, it can be seen that this change leads to a reduction of allocations overall, even if only a small one.
--- reftable/readwrite_test.c | 12 ++++-------- reftable/record.c | 6 ------ reftable/record_test.c | 4 ---- reftable/reftable-record.h | 4 ++-- 4 files changed, 6 insertions(+), 20 deletions(-)
reftable/readwrite_test.c +4 -8
@@ -547,8 +547,6 @@ static void test_table_refs_for(int indexed)uint8_t hash[GIT_SHA1_RAWSZ ];char fill[51 ] = {0 };char name[100 ]; -uint8_t hash1[GIT_SHA1_RAWSZ ]; -uint8_t hash2[GIT_SHA1_RAWSZ ];struct reftable_ref_record ref = {NULL };memset (hash, i,sizeof (hash));
@@ -558,11 +556,9 @@ static void test_table_refs_for(int indexed) name[40 ] =0 ; ref.refname = name; -set_test_hash (hash1, i /4 ); -set_test_hash (hash2,3 + i /4 ); ref.value_type =REFTABLE_REF_VAL2 ; - ref.value.val2.value = hash1; - ref.value.val2.target_value = hash2; +set_test_hash (ref.value.val2.value, i /4 ); +set_test_hash (ref.value.val2.target_value,3 + i /4 );/* 80 bytes / entry, so 3 entries per block. Yields 17 */
@@ -570,8 +566,8 @@ static void test_table_refs_for(int indexed) n =reftable_writer_add_ref (w, &ref);EXPECT (n ==0 ); -if (!memcmp (hash1, want_hash,GIT_SHA1_RAWSZ ) || - !memcmp (hash2, want_hash,GIT_SHA1_RAWSZ )) { +if (!memcmp (ref.value.val2.value, want_hash,GIT_SHA1_RAWSZ ) || + !memcmp (ref.value.val2.target_value, want_hash,GIT_SHA1_RAWSZ )) { want_names[want_names_len++] =xstrdup (name); } }
reftable/record.c +0 -6
@@ -222,9 +222,7 @@ static void reftable_ref_record_copy_from(void *rec, const void *src_rec,memcpy (ref->value.val1, src->value.val1, hash_size);break ;case REFTABLE_REF_VAL2 : - ref->value.val2.value =reftable_malloc (hash_size);memcpy (ref->value.val2.value, src->value.val2.value, hash_size); - ref->value.val2.target_value =reftable_malloc (hash_size);memcpy (ref->value.val2.target_value, src->value.val2.target_value, hash_size);break ;
@@ -298,8 +296,6 @@ void reftable_ref_record_release(struct reftable_ref_record *ref)reftable_free (ref->value.symref);break ;case REFTABLE_REF_VAL2 : -reftable_free (ref->value.val2.target_value); -reftable_free (ref->value.val2.value);break ;case REFTABLE_REF_VAL1 :break ;
@@ -401,11 +397,9 @@ static int reftable_ref_record_decode(void *rec, struct strbuf key,return -1 ; } - r->value.val2.value =reftable_malloc (hash_size);memcpy (r->value.val2.value, in.buf, hash_size);string_view_consume (&in, hash_size); - r->value.val2.target_value =reftable_malloc (hash_size);memcpy (r->value.val2.target_value, in.buf, hash_size);string_view_consume (&in, hash_size);break ;
reftable/record_test.c +0 -4
@@ -122,11 +122,7 @@ static void test_reftable_ref_record_roundtrip(void)set_hash (in.u.ref.value.val1,1 );break ;case REFTABLE_REF_VAL2 : - in.u.ref.value.val2.value = -reftable_malloc (GIT_SHA1_RAWSZ );set_hash (in.u.ref.value.val2.value,1 ); - in.u.ref.value.val2.target_value = -reftable_malloc (GIT_SHA1_RAWSZ );set_hash (in.u.ref.value.val2.target_value,2 );break ;case REFTABLE_REF_SYMREF :
reftable/reftable-record.h +2 -2
@@ -41,8 +41,8 @@ struct reftable_ref_record {union {unsigned char val1[GIT_MAX_RAWSZ ];struct { -uint8_t *value;/* first value, malloced hash */ -uint8_t *target_value;/* second value, malloced hash */ +unsigned char value[GIT_MAX_RAWSZ ];/* first hash */ +unsigned char target_value[GIT_MAX_RAWSZ ];/* second hash */ } val2;char *symref;/* referent, malloced 0-terminated string */ } value;
Signature · 1 line
2.43.GIT
PATCH v2 7/8 reftable/merged: really reuse buffers to compute record keys
In reply to Patrick SteinhardtIn 829231dc20 (reftable/merged: reuse buffer to compute record keys, 2023-12-11), we have refactored the merged iterator to reuse a set of buffers that it would otherwise have to reallocate on every single iteration. Unfortunately, there was a brown-paper-bag-style bug here as we continue to release these buffers after the iteration, and thus we have essentially gained nothing.
Fix this performance issue by not releasing those buffers on iteration anymore, where we instead rely on merged_iter_close() to release the buffers for us.
Using git show-ref --quiet in a repository with ~350k refs this leads to a significant drop in allocations. Before:
HEAP SUMMARY:
in use at exit: 21,163 bytes in 193 blocks
total heap usage: 1,410,148 allocs, 1,409,955 frees, 61,976,068 bytes allocated
After:
HEAP SUMMARY:
in use at exit: 21,163 bytes in 193 blocks
total heap usage: 708,058 allocs, 707,865 frees, 36,783,255 bytes allocated
--- reftable/merged.c | 2 -- 1 file changed, 2 deletions(-)
reftable/merged.c +0 -2
@@ -128,8 +128,6 @@ static int merged_iter_next_entry(struct merged_iter *mi, done:reftable_record_release (&entry.rec); -strbuf_release (&mi->entry_key); -strbuf_release (&mi->key);return err; }
Signature · 1 line
2.43.GIT
PATCH v2 8/8 reftable/merged: transfer ownership of records when iterating
In reply to Patrick SteinhardtWhen iterating over recods with the merged iterator we put the records into a priority queue before yielding them to the caller. This means that we need to allocate the contents of these records before we can pass them over to the caller.
The handover to the caller is quite inefficient though because we first deallocate the record passed in by the caller and then copy over the new record, which requires us to reallocate memory.
Refactor the code to instead transfer ownership of the new record to the caller. So instead of reallocating all contents, we now release the old record and then copy contents of the new record into place.
The following benchmark of git show-ref --quiet in a repository with around 350k refs shows a clear improvement. Before:
HEAP SUMMARY:
in use at exit: 21,163 bytes in 193 blocks
total heap usage: 708,058 allocs, 707,865 frees, 36,783,255 bytes allocated
After:
HEAP SUMMARY:
in use at exit: 21,163 bytes in 193 blocks
total heap usage: 357,007 allocs, 356,814 frees, 24,193,602 bytes allocated
This shows that we now have roundabout a single allocation per record that we're yielding from the iterator. Ideally, we'd also get rid of this allocation so that the number of allocations doesn't scale with the number of refs anymore. This would require some larger surgery though because the memory is owned by the priority queue before transferring it over to the caller.
--- reftable/merged.c | 6 ++++-- 1 file changed, 4 insertions(+), 2 deletions(-)
reftable/merged.c +4 -2
@@ -124,10 +124,12 @@ static int merged_iter_next_entry(struct merged_iter *mi,reftable_record_release (&top.rec); } -reftable_record_copy_from (rec, &entry.rec,hash_size (mi->hash_id)); +reftable_record_release (rec); + *rec = entry.rec; done: -reftable_record_release (&entry.rec); +if (err) +reftable_record_release (&entry.rec);return err; }
Signature · 1 line
2.43.GIT
Re: [PATCH v2 7/8] reftable/merged: really reuse buffers to compute record keys
In reply to Patrick SteinhardtQuoted 6 lines · Patrick Steinhardt
In
829231dc20(reftable/merged: reuse buffer to compute record keys, 2023-12-11), we have refactored the merged iterator to reuse a set of buffers that it would otherwise have to reallocate on every single iteration. Unfortunately, there was a brown-paper-bag-style bug here as we continue to release these buffers after the iteration, and thus we have essentially gained nothing.
s/-style// perhaps. It took me more than just reading of the above but I needed to see the code before noticed that you are talking about strbuf_release(). Only after that I think I understood what you meant as a bug.
With the change, instead of using a new "entry_key" strbuf for each iteration, the code now passes mi->entry_key to reftable_record_key(), which will reuse the existing .buf member of the strbuf to avoid reallcation. But releasing the strbuf in each iteration defeats such optimization.
I suspect that a Git developer who will be reading "git log" output in 6 months and finds the above paragraph understands the problem and its fix better if the description hinted strbuf_reset() near where it mentions "release", something like:
... to reuse a pair of long-living strbufs by relying on the fact that reftable_record_key() tries to reuse its already allocated .buf member by calling strbuf_reset(), which should give us significantly fewer reallocation compared to the old code that used on-stack strbufs that are allocated for each and every iteration. Unfortunately, we called strbuf_release() on these long-living strbufs that we meant to reuse, defeating the optimization.
or along that line, perhaps?
Other than that, a very reasonable fix. Thanks for a pleasant read.
Quoted 34 lines
Fix this performance issue by not releasing those buffers on iteration anymore, where we instead rely on
merged_iter_close()to release the buffers for us.Using
git show-ref --quietin a repository with ~350k refs this leads to a significant drop in allocations. Before:HEAP SUMMARY:
in use at exit: 21,163 bytes in 193 blocks
total heap usage: 1,410,148 allocs, 1,409,955 frees, 61,976,068 bytes allocatedAfter:
HEAP SUMMARY:
in use at exit: 21,163 bytes in 193 blocks
total heap usage: 708,058 allocs, 707,865 frees, 36,783,255 bytes allocatedSigned-off-by Patrick Steinhardt <[email protected]>--- reftable/merged.c | 2 -- 1 file changed, 2 deletions(-)reftable/merged.c +0
-2@@ -128,8 +128,6 @@ static int merged_iter_next_entry(struct merged_iter *mi, done:reftable_record_release (&entry.rec); -strbuf_release (&mi->entry_key); -strbuf_release (&mi->key);return err; }
Re: [PATCH v2 5/8] reftable/record: store "val1" hashes as static arrays
In reply to Patrick SteinhardtQuoted 1 line · Patrick Steinhardt
When reading ref records of type "val1" we store its object ID in an
I'd find it easier to follow if we had a comma before "we store", but perhaps I am old fashioned.
Quoted 5 lines
allocated array. This results in an additional allocation for every single ref record we read, which is rather inefficient especially when iterating over refs.
Refactor the code to instead use a static array of
GIT_MAX_RAWSZ
"a static" -> "an embedded", perhaps? The struct as the whole may or may not be static but the point of this patch is that the array is embedded in it.
Quoted 3 lines
bytes. While this means that
struct ref_recordis bigger now, we typically do not store all refs in an array anyway and instead only handle a limited number of records at the same point in time.
Nicely explained.
Quoted 251 lines
Using
git show-ref --quietin a repository with ~350k refs this leads to a significant drop in allocations. Before:HEAP SUMMARY:
in use at exit: 21,098 bytes in 192 blocks
total heap usage: 2,116,683 allocs, 2,116,491 frees, 76,098,060 bytes allocatedAfter:
HEAP SUMMARY:
in use at exit: 21,098 bytes in 192 blocks
total heap usage: 1,419,031 allocs, 1,418,839 frees, 62,145,036 bytes allocatedSigned-off-by Patrick Steinhardt <[email protected]>--- reftable/block_test.c | 4 +--- reftable/merged_test.c | 16 ++++++---------- reftable/readwrite_test.c | 14 ++++---------- reftable/record.c | 3 --- reftable/record_test.c | 1 - reftable/reftable-record.h | 3 ++- reftable/stack_test.c | 2 -- 7 files changed, 13 insertions(+), 30 deletions(-)reftable/block_test.c +1
-3@@ -49,13 +49,11 @@ static void test_block_read_write(void)for (i =0 ; i <N ; i++) {char name[100 ]; -uint8_t hash[GIT_SHA1_RAWSZ ];snprintf (name,sizeof (name),"branch%02d" , i); -memset (hash, i,sizeof (hash)); rec.u.ref.refname = name; rec.u.ref.value_type =REFTABLE_REF_VAL1 ; - rec.u.ref.value.val1 = hash; +memset (rec.u.ref.value.val1, i,GIT_SHA1_RAWSZ ); names[i] =xstrdup (name); n =block_writer_add (&bw, &rec);reftable/merged_test.c +6
-10@@ -123,13 +123,11 @@ static void readers_destroy(struct reftable_reader **readers, size_t n)static void test_merged_between (void ) { -uint8_t hash1[GIT_SHA1_RAWSZ ] = {1 ,2 ,3 ,0 }; -struct reftable_ref_record r1[] = { { .refname ="b" , .update_index =1 , .value_type =REFTABLE_REF_VAL1 , - .value.val1 = hash1, + .value.val1 = {1 ,2 ,3 ,0 }, } };struct reftable_ref_record r2[] = { { .refname ="a" ,@@ -165,26 +163,24 @@ static void test_merged_between(void)static void test_merged (void ) { -uint8_t hash1[GIT_SHA1_RAWSZ ] = {1 }; -uint8_t hash2[GIT_SHA1_RAWSZ ] = {2 };struct reftable_ref_record r1[] = { { .refname ="a" , .update_index =1 , .value_type =REFTABLE_REF_VAL1 , - .value.val1 = hash1, + .value.val1 = {1 }, }, { .refname ="b" , .update_index =1 , .value_type =REFTABLE_REF_VAL1 , - .value.val1 = hash1, + .value.val1 = {1 }, }, { .refname ="c" , .update_index =1 , .value_type =REFTABLE_REF_VAL1 , - .value.val1 = hash1, + .value.val1 = {1 }, } };struct reftable_ref_record r2[] = { {@@ -197,13 +193,13 @@ static void test_merged(void) .refname = "c", .update_index = 3, .value_type = REFTABLE_REF_VAL1, - .value.val1 = hash2, + .value.val1 = { 2 }, }, { .refname = "d", .update_index = 3, .value_type = REFTABLE_REF_VAL1, - .value.val1 = hash1, + .value.val1 = { 1 }, }, };reftable/readwrite_test.c +4
-10@@ -60,18 +60,15 @@ static void write_table(char ***names, struct strbuf *buf, int N, *names =reftable_calloc (sizeof (char *) * (N +1 ));reftable_writer_set_limits (w, update_index, update_index);for (i =0 ; i <N ; i++) { -uint8_t hash[GIT_SHA256_RAWSZ ] = {0 };char name[100 ];int n; -set_test_hash (hash, i); -snprintf (name,sizeof (name),"refs/heads/branch%02d" , i); ref.refname = name; ref.update_index = update_index; ref.value_type =REFTABLE_REF_VAL1 ; - ref.value.val1 = hash; +set_test_hash (ref.value.val1, i); (*names)[i] =xstrdup (name); n =reftable_writer_add_ref (w, &ref);@@ -675,11 +672,10 @@ static void test_write_object_id_min_length(void)struct strbuf buf =STRBUF_INIT ;struct reftable_writer *w =reftable_new_writer (&strbuf_add_void, &buf, &opts); -uint8_t hash[GIT_SHA1_RAWSZ ] = {42 };struct reftable_ref_record ref = { .update_index =1 , .value_type =REFTABLE_REF_VAL1 , - .value.val1 = hash, + .value.val1 = {42 }, };int err;int i;@@ -711,11 +707,10 @@ static void test_write_object_id_length(void)struct strbuf buf =STRBUF_INIT ;struct reftable_writer *w =reftable_new_writer (&strbuf_add_void, &buf, &opts); -uint8_t hash[GIT_SHA1_RAWSZ ] = {42 };struct reftable_ref_record ref = { .update_index =1 , .value_type =REFTABLE_REF_VAL1 , - .value.val1 = hash, + .value.val1 = {42 }, };int err;int i;@@ -814,11 +809,10 @@ static void test_write_multiple_indices(void) writer =reftable_new_writer (&strbuf_add_void, &writer_buf, &opts);reftable_writer_set_limits (writer,1 ,1 );for (i =0 ; i <100 ; i++) { -unsigned char hash[GIT_SHA1_RAWSZ ] = {i};struct reftable_ref_record ref = { .update_index =1 , .value_type =REFTABLE_REF_VAL1 , - .value.val1 = hash, + .value.val1 = {i}, };strbuf_reset (&buf);reftable/record.c +0
-3@@ -219,7 +219,6 @@ static void reftable_ref_record_copy_from(void *rec, const void *src_rec,case REFTABLE_REF_DELETION :break ;case REFTABLE_REF_VAL1 : - ref->value.val1 =reftable_malloc (hash_size);memcpy (ref->value.val1, src->value.val1, hash_size);break ;case REFTABLE_REF_VAL2 :@@ -303,7 +302,6 @@ void reftable_ref_record_release(struct reftable_ref_record *ref)reftable_free (ref->value.val2.value);break ;case REFTABLE_REF_VAL1 : -reftable_free (ref->value.val1);break ;case REFTABLE_REF_DELETION :break ;@@ -394,7 +392,6 @@ static int reftable_ref_record_decode(void *rec, struct strbuf key,return -1 ; } - r->value.val1 =reftable_malloc (hash_size);memcpy (r->value.val1, in.buf, hash_size);string_view_consume (&in, hash_size);break ;reftable/record_test.c +0
-1@@ -119,7 +119,6 @@ static void test_reftable_ref_record_roundtrip(void)case REFTABLE_REF_DELETION :break ;case REFTABLE_REF_VAL1 : - in.u.ref.value.val1 =reftable_malloc (GIT_SHA1_RAWSZ );set_hash (in.u.ref.value.val1,1 );break ;case REFTABLE_REF_VAL2 :reftable/reftable-record.h +2
-1@@ -9,6 +9,7 @@ license that can be found in the LICENSE file or at#ifndef REFTABLE_RECORD_H #define REFTABLE_RECORD_H +#include "hash-ll.h" #include <stdint.h> /* @@ -38,7 +39,7 @@ struct reftable_ref_record {#define REFTABLE_NR_REF_VALUETYPES 4 } value_type;union { -uint8_t *val1;/* malloced hash. */ +unsigned char val1[GIT_MAX_RAWSZ ];struct {uint8_t *value;/* first value, malloced hash */ uint8_t *target_value;/* second value, malloced hash */ reftable/stack_test.c +0
-2@@ -463,7 +463,6 @@ static void test_reftable_stack_add(void) refs[i].refname =xstrdup (buf); refs[i].update_index = i +1 ; refs[i].value_type =REFTABLE_REF_VAL1 ; - refs[i].value.val1 =reftable_malloc (GIT_SHA1_RAWSZ );set_test_hash (refs[i].value.val1, i); logs[i].refname =xstrdup (buf);@@ -600,7 +599,6 @@ static void test_reftable_stack_tombstone(void) refs[i].update_index = i +1 ;if (i %2 ==0 ) { refs[i].value_type =REFTABLE_REF_VAL1 ; - refs[i].value.val1 =reftable_malloc (GIT_SHA1_RAWSZ );set_test_hash (refs[i].value.val1, i); }
Re: [PATCH v2 8/8] reftable/merged: transfer ownership of records when iterating
In reply to Patrick SteinhardtQuoted 1 line · Patrick Steinhardt
When iterating over recods with the merged iterator we put the records
"records"?
I commented on a few patches in this iteration that I found a bit harder to follow than necessary; aside from these small nits, everything in the series looked quite well explained and executed.
Thanks.
v3 cover reftable: fixes and optimizations (pt.2)
In reply to Patrick SteinhardtHi,
this is the third version of my patch series that contains additional fixes and optimizations for the reftable library.
The only changes in this iteration are improvements to the commit messages to hopefully make them easier to understand. Thanks Junio for your suggestions!
Patrick
Patrick Steinhardt (8):
reftable/stack: do not overwrite errors when compacting reftable/stack: do not auto-compact twice in reftable_stack_add() reftable/writer: fix index corruption when writing multiple indices reftable/record: constify some parts of the interface reftable/record: store "val1" hashes as static arrays reftable/record: store "val2" hashes as static arrays reftable/merged: really reuse buffers to compute record keys reftable/merged: transfer ownership of records when iterating
reftable/block_test.c | 4 +- reftable/merged.c | 8 +-- reftable/merged_test.c | 16 +++--- reftable/readwrite_test.c | 102 +++++++++++++++++++++++++++++++------ reftable/record.c | 17 ++----- reftable/record_test.c | 5 -- reftable/reftable-record.h | 11 ++-- reftable/stack.c | 23 +++------ reftable/stack_test.c | 2 - reftable/writer.c | 4 +- 10 files changed, 117 insertions(+), 75 deletions(-)
Range-diff against v2:
1: 22a57020c6 = 1: 1dc8ddf04a reftable/stack: do not overwrite errors when compacting 2: a08f7efc99 = 2: eccc34a4b6 reftable/stack: do not auto-compact twice in `reftable_stack_add()` 3: c00e08d97f = 3: 15e12b8f29 reftable/writer: fix index corruption when writing multiple indices 4: 3416268087 = 4: 017e8943c7 reftable/record: constify some parts of the interface 5: 46ca3a37f8 ! 5: f1d2190489 reftable/record: store "val1" hashes as static arrays
@@ Metadata
## Commit message ##
reftable/record: store "val1" hashes as static arrays
- When reading ref records of type "val1" we store its object ID in an
+ When reading ref records of type "val1", we store its object ID in an
allocated array. This results in an additional allocation for every single ref record we read, which is rather inefficient especially when iterating over refs.
- Refactor the code to instead use a static array of GIT_MAX_RAWSZ
+ Refactor the code to instead use an embedded array of GIT_MAX_RAWSZ
bytes. While this means that struct ref_record is bigger now, we typically do not store all refs in an array anyway and instead only handle a limited number of records at the same point in time.
6: c8a36917b1 = 6: 6ec02d6775 reftable/record: store "val2" hashes as static arrays 7: 6313f8affd ! 7: 845dec2390 reftable/merged: really reuse buffers to compute record keys
@@ Commit message
reftable/merged: really reuse buffers to compute record keys
In 829231dc20 (reftable/merged: reuse buffer to compute record keys,
- 2023-12-11), we have refactored the merged iterator to reuse a set of
- buffers that it would otherwise have to reallocate on every single
- iteration. Unfortunately, there was a brown-paper-bag-style bug here as
- we continue to release these buffers after the iteration, and thus we
- have essentially gained nothing.
+ 2023-12-11), we have refactored the merged iterator to reuse a pair of
+ long-living strbufs by relying on the fact that reftable_record_key()
+ tries to reuse already allocated strbufs by calling strbuf_reset(),
+ which should give us significantly fewer reallocations compared to the
+ old code that used on-stack strbufs that are allocated for each and
+ every iteration. Unfortunately, we called strbuf_release() on these
+ long-living strbufs that we meant to reuse on each iteration, defeating
+ the optimization.
Fix this performance issue by not releasing those buffers on iteration anymore, where we instead rely on merged_iter_close() to release the
8: 25a3919e58 ! 8: eea0e161ad reftable/merged: transfer ownership of records when iterating
@@ Metadata
## Commit message ##
reftable/merged: transfer ownership of records when iterating
- When iterating over recods with the merged iterator we put the records
+ When iterating over records with the merged iterator we put the records
into a priority queue before yielding them to the caller. This means that we need to allocate the contents of these records before we can pass them over to the caller.
base-commit: a26002b62827b89a19b1084bd75d9371d565d03c
Signature · 1 line
2.43.GIT
PATCH v3 1/8 reftable/stack: do not overwrite errors when compacting
In order to compact multiple stacks we iterate through the merged ref and log records. When there is any error either when reading the records from the old merged table or when writing the records to the new table then we break out of the respective loops. When breaking out of the loop for the ref records though the error code will be overwritten, which may cause us to inadvertently skip over bad ref records. In the worst case, this can lead to a compacted stack that is missing records.
Fix the code by using goto done instead so that any potential error codes are properly returned to the caller.
--- reftable/stack.c | 20 ++++++++------------ 1 file changed, 8 insertions(+), 12 deletions(-)
reftable/stack.c +8 -12
@@ -801,18 +801,16 @@ static int stack_write_compact(struct reftable_stack *st, err =0 ;break ; } -if (err <0 ) { -break ; - } +if (err <0 ) + goto done;if (first ==0 &&reftable_ref_record_is_deletion (&ref)) {continue ; } err =reftable_writer_add_ref (wr, &ref); -if (err <0 ) { -break ; - } +if (err <0 ) + goto done; entries++; }reftable_iterator_destroy (&it);
@@ -827,9 +825,8 @@ static int stack_write_compact(struct reftable_stack *st, err =0 ;break ; } -if (err <0 ) { -break ; - } +if (err <0 ) + goto done;if (first ==0 &&reftable_log_record_is_deletion (&log)) {continue ; }
@@ -845,9 +842,8 @@ static int stack_write_compact(struct reftable_stack *st, } err =reftable_writer_add_log (wr, &log); -if (err <0 ) { -break ; - } +if (err <0 ) + goto done; entries++; }
Signature · 1 line
2.43.GIT
PATCH v3 2/8 reftable/stack: do not auto-compact twice in `reftable_stack_add()`
In reply to Patrick SteinhardtIn 5c086453ff (reftable/stack: perform auto-compaction with transactional interface, 2023-12-11), we fixed a bug where the transactional interface to add changes to a reftable stack did not perform auto-compaction by calling reftable_stack_auto_compact() in reftable_stack_addition_commit(). While correct, this change may now cause us to perform auto-compaction twice in the non-transactional interface reftable_stack_add():
- It performs auto-compaction by itself.
- It now transitively performs auto-compaction via the transactional interface.
Remove the first instance so that we only end up doing auto-compaction once.
--- reftable/stack.c | 3 --- 1 file changed, 3 deletions(-)
reftable/stack.c +0 -3
@@ -425,9 +425,6 @@ int reftable_stack_add(struct reftable_stack *st,return err; } -if (!st->disable_auto_compact) -return reftable_stack_auto_compact (st); -return 0 ; }
Signature · 1 line
2.43.GIT
PATCH v3 3/8 reftable/writer: fix index corruption when writing multiple indices
In reply to Patrick SteinhardtEach reftable may contain multiple types of blocks for refs, objects and reflog records, where each of these may have an index that makes it more efficient to find the records. It was observed that the index for log records can become corrupted under certain circumstances, where the first entry of the index points into the object index instead of to the log records.
As it turns out, this corruption can occur whenever we write a log index as well as at least one additional index. Writing records and their index is basically a two-step process:
1. We write all blocks for the corresponding record. Each block that gets written is added to a list of blocks to index.
2. Once all blocks were written we finish the section. If at least two blocks have been added to the list of blocks to index then we will now write the index for those blocks and flush it, as well.
When we have a very large number of blocks then we may decide to write a multi-level index, which is why we also keep track of the list of the index blocks in the same way as we previously kept track of the blocks to index.
Now when we have finished writing all index blocks we clear the index and flush the last block to disk. This is done in the wrong order though because flushing the block to disk will re-add it to the list of blocks to be indexed. The result is that the next section we are about to write will have an entry in the list of blocks to index that points to the last block of the preceding section's index, which will corrupt the log index.
Fix this corruption by clearing the index after having written the last block.
--- reftable/readwrite_test.c | 80 +++++++++++++++++++++++++++++++++++++++ reftable/writer.c | 4 +- 2 files changed, 82 insertions(+), 2 deletions(-)
reftable/readwrite_test.c +80 -0
@@ -798,6 +798,85 @@ static void test_write_key_order(void)strbuf_release (&buf); } +static void test_write_multiple_indices (void ) +{ +struct reftable_write_options opts = { + .block_size =100 , + }; +struct strbuf writer_buf =STRBUF_INIT , buf =STRBUF_INIT ; +struct reftable_block_source source = {0 }; +struct reftable_iterator it = {0 }; +const struct reftable_stats *stats; +struct reftable_writer *writer; +struct reftable_reader *reader; +int err, i; + + writer =reftable_new_writer (&strbuf_add_void, &writer_buf, &opts); +reftable_writer_set_limits (writer,1 ,1 ); +for (i =0 ; i <100 ; i++) { +unsigned char hash[GIT_SHA1_RAWSZ ] = {i}; +struct reftable_ref_record ref = { + .update_index =1 , + .value_type =REFTABLE_REF_VAL1 , + .value.val1 = hash, + }; + +strbuf_reset (&buf); +strbuf_addf (&buf,"refs/heads/%04d" , i); + ref.refname = buf.buf, + + err =reftable_writer_add_ref (writer, &ref); +EXPECT_ERR (err); + } + +for (i =0 ; i <100 ; i++) { +unsigned char hash[GIT_SHA1_RAWSZ ] = {i}; +struct reftable_log_record log = { + .update_index =1 , + .value_type =REFTABLE_LOG_UPDATE , + .value.update = { + .old_hash = hash, + .new_hash = hash, + }, + }; + +strbuf_reset (&buf); +strbuf_addf (&buf,"refs/heads/%04d" , i); + log.refname = buf.buf, + + err =reftable_writer_add_log (writer, &log); +EXPECT_ERR (err); + } + +reftable_writer_close (writer); + +/* +* The written data should be sufficiently large to result in indices +* for each of the block types. +*/ + stats =reftable_writer_stats (writer); +EXPECT (stats->ref_stats.index_offset >0 ); +EXPECT (stats->obj_stats.index_offset >0 ); +EXPECT (stats->log_stats.index_offset >0 ); + +block_source_from_strbuf (&source, &writer_buf); + err =reftable_new_reader (&reader, &source,"filename" ); +EXPECT_ERR (err); + +/* +* Seeking the log uses the log index now. In case there is any +* confusion regarding indices we would notice here. +*/ + err =reftable_reader_seek_log (reader, &it,"" ); +EXPECT_ERR (err); + +reftable_iterator_destroy (&it); +reftable_writer_free (writer); +reftable_reader_free (reader); +strbuf_release (&writer_buf); +strbuf_release (&buf); +} +static void test_corrupt_table_empty (void ) {struct strbuf buf =STRBUF_INIT ;
@@ -847,5 +926,6 @@ int readwrite_test_main(int argc, const char *argv[])RUN_TEST (test_log_overflow);RUN_TEST (test_write_object_id_length);RUN_TEST (test_write_object_id_min_length); +RUN_TEST (test_write_multiple_indices);return 0 ; }
reftable/writer.c +2 -2
@@ -432,12 +432,12 @@ static int writer_finish_section(struct reftable_writer *w)reftable_free (idx); } -writer_clear_index (w); - err =writer_flush_block (w);if (err <0 )return err; +writer_clear_index (w); + bstats =writer_reftable_block_stats (w, typ); bstats->index_blocks = w->stats.idx_stats.blocks - before_blocks; bstats->index_offset = index_start;
Signature · 1 line
2.43.GIT
PATCH v3 4/8 reftable/record: constify some parts of the interface
In reply to Patrick SteinhardtWe're about to convert reftable records to stop storing their object IDs as allocated hashes. Prepare for this refactoring by constifying some parts of the interface that will be impacted by this.
--- reftable/record.c | 8 ++++---- reftable/reftable-record.h | 4 ++-- 2 files changed, 6 insertions(+), 6 deletions(-)
reftable/record.c +4 -4
@@ -76,7 +76,7 @@ int reftable_is_block_type(uint8_t typ)return 0 ; } -uint8_t *reftable_ref_record_val1 (const struct reftable_ref_record *rec) +const unsigned char *reftable_ref_record_val1 (const struct reftable_ref_record *rec) {switch (rec->value_type) {case REFTABLE_REF_VAL1 :
@@ -88,7 +88,7 @@ uint8_t *reftable_ref_record_val1(const struct reftable_ref_record *rec) } } -uint8_t *reftable_ref_record_val2 (const struct reftable_ref_record *rec) +const unsigned char *reftable_ref_record_val2 (const struct reftable_ref_record *rec) {switch (rec->value_type) {case REFTABLE_REF_VAL2 :
@@ -242,7 +242,7 @@ static char hexdigit(int c)return 'a' + (c -10 ); } -static void hex_format (char *dest,uint8_t *src,int hash_size) +static void hex_format (char *dest,const unsigned char *src,int hash_size) {assert (hash_size >0 );if (src) {
@@ -1164,7 +1164,7 @@ int reftable_record_equal(struct reftable_record *a, struct reftable_record *b, reftable_record_data(a), reftable_record_data(b), hash_size); } -static int hash_equal (uint8_t *a,uint8_t *b,int hash_size) +static int hash_equal (const unsigned char *a,const unsigned char *b,int hash_size) {if (a && b)return !memcmp (a, b, hash_size);
reftable/reftable-record.h +2 -2
@@ -49,11 +49,11 @@ struct reftable_ref_record {/* Returns the first hash, or NULL if `rec` is not of type * REFTABLE_REF_VAL1 or REFTABLE_REF_VAL2. */ -uint8_t *reftable_ref_record_val1 (const struct reftable_ref_record *rec); +const unsigned char *reftable_ref_record_val1 (const struct reftable_ref_record *rec);/* Returns the second hash, or NULL if `rec` is not of type * REFTABLE_REF_VAL2. */ -uint8_t *reftable_ref_record_val2 (const struct reftable_ref_record *rec); +const unsigned char *reftable_ref_record_val2 (const struct reftable_ref_record *rec);/* returns whether 'ref' represents a deletion */ int reftable_ref_record_is_deletion (const struct reftable_ref_record *ref);
Signature · 1 line
2.43.GIT
PATCH v3 5/8 reftable/record: store "val1" hashes as static arrays
In reply to Patrick SteinhardtWhen reading ref records of type "val1", we store its object ID in an allocated array. This results in an additional allocation for every single ref record we read, which is rather inefficient especially when iterating over refs.
Refactor the code to instead use an embedded array of GIT_MAX_RAWSZ bytes. While this means that struct ref_record is bigger now, we typically do not store all refs in an array anyway and instead only handle a limited number of records at the same point in time.
Using git show-ref --quiet in a repository with ~350k refs this leads to a significant drop in allocations. Before:
HEAP SUMMARY:
in use at exit: 21,098 bytes in 192 blocks
total heap usage: 2,116,683 allocs, 2,116,491 frees, 76,098,060 bytes allocated
After:
HEAP SUMMARY:
in use at exit: 21,098 bytes in 192 blocks
total heap usage: 1,419,031 allocs, 1,418,839 frees, 62,145,036 bytes allocated
--- reftable/block_test.c | 4 +--- reftable/merged_test.c | 16 ++++++---------- reftable/readwrite_test.c | 14 ++++---------- reftable/record.c | 3 --- reftable/record_test.c | 1 - reftable/reftable-record.h | 3 ++- reftable/stack_test.c | 2 -- 7 files changed, 13 insertions(+), 30 deletions(-)
reftable/block_test.c +1 -3
@@ -49,13 +49,11 @@ static void test_block_read_write(void)for (i =0 ; i <N ; i++) {char name[100 ]; -uint8_t hash[GIT_SHA1_RAWSZ ];snprintf (name,sizeof (name),"branch%02d" , i); -memset (hash, i,sizeof (hash)); rec.u.ref.refname = name; rec.u.ref.value_type =REFTABLE_REF_VAL1 ; - rec.u.ref.value.val1 = hash; +memset (rec.u.ref.value.val1, i,GIT_SHA1_RAWSZ ); names[i] =xstrdup (name); n =block_writer_add (&bw, &rec);
reftable/merged_test.c +6 -10
@@ -123,13 +123,11 @@ static void readers_destroy(struct reftable_reader **readers, size_t n)static void test_merged_between (void ) { -uint8_t hash1[GIT_SHA1_RAWSZ ] = {1 ,2 ,3 ,0 }; -struct reftable_ref_record r1[] = { { .refname ="b" , .update_index =1 , .value_type =REFTABLE_REF_VAL1 , - .value.val1 = hash1, + .value.val1 = {1 ,2 ,3 ,0 }, } };struct reftable_ref_record r2[] = { { .refname ="a" ,
@@ -165,26 +163,24 @@ static void test_merged_between(void)static void test_merged (void ) { -uint8_t hash1[GIT_SHA1_RAWSZ ] = {1 }; -uint8_t hash2[GIT_SHA1_RAWSZ ] = {2 };struct reftable_ref_record r1[] = { { .refname ="a" , .update_index =1 , .value_type =REFTABLE_REF_VAL1 , - .value.val1 = hash1, + .value.val1 = {1 }, }, { .refname ="b" , .update_index =1 , .value_type =REFTABLE_REF_VAL1 , - .value.val1 = hash1, + .value.val1 = {1 }, }, { .refname ="c" , .update_index =1 , .value_type =REFTABLE_REF_VAL1 , - .value.val1 = hash1, + .value.val1 = {1 }, } };struct reftable_ref_record r2[] = { {
@@ -197,13 +193,13 @@ static void test_merged(void) .refname = "c", .update_index = 3, .value_type = REFTABLE_REF_VAL1, - .value.val1 = hash2, + .value.val1 = { 2 }, }, { .refname = "d", .update_index = 3, .value_type = REFTABLE_REF_VAL1, - .value.val1 = hash1, + .value.val1 = { 1 }, }, };
reftable/readwrite_test.c +4 -10
@@ -60,18 +60,15 @@ static void write_table(char ***names, struct strbuf *buf, int N, *names =reftable_calloc (sizeof (char *) * (N +1 ));reftable_writer_set_limits (w, update_index, update_index);for (i =0 ; i <N ; i++) { -uint8_t hash[GIT_SHA256_RAWSZ ] = {0 };char name[100 ];int n; -set_test_hash (hash, i); -snprintf (name,sizeof (name),"refs/heads/branch%02d" , i); ref.refname = name; ref.update_index = update_index; ref.value_type =REFTABLE_REF_VAL1 ; - ref.value.val1 = hash; +set_test_hash (ref.value.val1, i); (*names)[i] =xstrdup (name); n =reftable_writer_add_ref (w, &ref);
@@ -675,11 +672,10 @@ static void test_write_object_id_min_length(void)struct strbuf buf =STRBUF_INIT ;struct reftable_writer *w =reftable_new_writer (&strbuf_add_void, &buf, &opts); -uint8_t hash[GIT_SHA1_RAWSZ ] = {42 };struct reftable_ref_record ref = { .update_index =1 , .value_type =REFTABLE_REF_VAL1 , - .value.val1 = hash, + .value.val1 = {42 }, };int err;int i;
@@ -711,11 +707,10 @@ static void test_write_object_id_length(void)struct strbuf buf =STRBUF_INIT ;struct reftable_writer *w =reftable_new_writer (&strbuf_add_void, &buf, &opts); -uint8_t hash[GIT_SHA1_RAWSZ ] = {42 };struct reftable_ref_record ref = { .update_index =1 , .value_type =REFTABLE_REF_VAL1 , - .value.val1 = hash, + .value.val1 = {42 }, };int err;int i;
@@ -814,11 +809,10 @@ static void test_write_multiple_indices(void) writer =reftable_new_writer (&strbuf_add_void, &writer_buf, &opts);reftable_writer_set_limits (writer,1 ,1 );for (i =0 ; i <100 ; i++) { -unsigned char hash[GIT_SHA1_RAWSZ ] = {i};struct reftable_ref_record ref = { .update_index =1 , .value_type =REFTABLE_REF_VAL1 , - .value.val1 = hash, + .value.val1 = {i}, };strbuf_reset (&buf);
reftable/record.c +0 -3
@@ -219,7 +219,6 @@ static void reftable_ref_record_copy_from(void *rec, const void *src_rec,case REFTABLE_REF_DELETION :break ;case REFTABLE_REF_VAL1 : - ref->value.val1 =reftable_malloc (hash_size);memcpy (ref->value.val1, src->value.val1, hash_size);break ;case REFTABLE_REF_VAL2 :
@@ -303,7 +302,6 @@ void reftable_ref_record_release(struct reftable_ref_record *ref)reftable_free (ref->value.val2.value);break ;case REFTABLE_REF_VAL1 : -reftable_free (ref->value.val1);break ;case REFTABLE_REF_DELETION :break ;
@@ -394,7 +392,6 @@ static int reftable_ref_record_decode(void *rec, struct strbuf key,return -1 ; } - r->value.val1 =reftable_malloc (hash_size);memcpy (r->value.val1, in.buf, hash_size);string_view_consume (&in, hash_size);break ;
reftable/record_test.c +0 -1
@@ -119,7 +119,6 @@ static void test_reftable_ref_record_roundtrip(void)case REFTABLE_REF_DELETION :break ;case REFTABLE_REF_VAL1 : - in.u.ref.value.val1 =reftable_malloc (GIT_SHA1_RAWSZ );set_hash (in.u.ref.value.val1,1 );break ;case REFTABLE_REF_VAL2 :
reftable/reftable-record.h +2 -1
@@ -9,6 +9,7 @@ license that can be found in the LICENSE file or at#ifndef REFTABLE_RECORD_H #define REFTABLE_RECORD_H +#include "hash-ll.h" #include <stdint.h> /*
@@ -38,7 +39,7 @@ struct reftable_ref_record {#define REFTABLE_NR_REF_VALUETYPES 4 } value_type;union { -uint8_t *val1;/* malloced hash. */ +unsigned char val1[GIT_MAX_RAWSZ ];struct {uint8_t *value;/* first value, malloced hash */ uint8_t *target_value;/* second value, malloced hash */
reftable/stack_test.c +0 -2
@@ -463,7 +463,6 @@ static void test_reftable_stack_add(void) refs[i].refname =xstrdup (buf); refs[i].update_index = i +1 ; refs[i].value_type =REFTABLE_REF_VAL1 ; - refs[i].value.val1 =reftable_malloc (GIT_SHA1_RAWSZ );set_test_hash (refs[i].value.val1, i); logs[i].refname =xstrdup (buf);
@@ -600,7 +599,6 @@ static void test_reftable_stack_tombstone(void) refs[i].update_index = i +1 ;if (i %2 ==0 ) { refs[i].value_type =REFTABLE_REF_VAL1 ; - refs[i].value.val1 =reftable_malloc (GIT_SHA1_RAWSZ );set_test_hash (refs[i].value.val1, i); }
Signature · 1 line
2.43.GIT
PATCH v3 6/8 reftable/record: store "val2" hashes as static arrays
In reply to Patrick SteinhardtSimilar to the preceding commit, convert ref records of type "val2" to store their object IDs in static arrays instead of allocating them for every single record.
We're using the same benchmark as in the preceding commit, with git show-ref --quiet in a repository with ~350k refs. This time around though the effects aren't this huge. Before:
HEAP SUMMARY:
in use at exit: 21,163 bytes in 193 blocks
total heap usage: 1,419,040 allocs, 1,418,847 frees, 62,153,868 bytes allocated
After:
HEAP SUMMARY:
in use at exit: 21,163 bytes in 193 blocks
total heap usage: 1,410,148 allocs, 1,409,955 frees, 61,976,068 bytes allocated
This is because "val2"-type records are typically only stored for peeled tags, and the number of annotated tags in the benchmark repository is rather low. Still, it can be seen that this change leads to a reduction of allocations overall, even if only a small one.
--- reftable/readwrite_test.c | 12 ++++-------- reftable/record.c | 6 ------ reftable/record_test.c | 4 ---- reftable/reftable-record.h | 4 ++-- 4 files changed, 6 insertions(+), 20 deletions(-)
reftable/readwrite_test.c +4 -8
@@ -547,8 +547,6 @@ static void test_table_refs_for(int indexed)uint8_t hash[GIT_SHA1_RAWSZ ];char fill[51 ] = {0 };char name[100 ]; -uint8_t hash1[GIT_SHA1_RAWSZ ]; -uint8_t hash2[GIT_SHA1_RAWSZ ];struct reftable_ref_record ref = {NULL };memset (hash, i,sizeof (hash));
@@ -558,11 +556,9 @@ static void test_table_refs_for(int indexed) name[40 ] =0 ; ref.refname = name; -set_test_hash (hash1, i /4 ); -set_test_hash (hash2,3 + i /4 ); ref.value_type =REFTABLE_REF_VAL2 ; - ref.value.val2.value = hash1; - ref.value.val2.target_value = hash2; +set_test_hash (ref.value.val2.value, i /4 ); +set_test_hash (ref.value.val2.target_value,3 + i /4 );/* 80 bytes / entry, so 3 entries per block. Yields 17 */
@@ -570,8 +566,8 @@ static void test_table_refs_for(int indexed) n =reftable_writer_add_ref (w, &ref);EXPECT (n ==0 ); -if (!memcmp (hash1, want_hash,GIT_SHA1_RAWSZ ) || - !memcmp (hash2, want_hash,GIT_SHA1_RAWSZ )) { +if (!memcmp (ref.value.val2.value, want_hash,GIT_SHA1_RAWSZ ) || + !memcmp (ref.value.val2.target_value, want_hash,GIT_SHA1_RAWSZ )) { want_names[want_names_len++] =xstrdup (name); } }
reftable/record.c +0 -6
@@ -222,9 +222,7 @@ static void reftable_ref_record_copy_from(void *rec, const void *src_rec,memcpy (ref->value.val1, src->value.val1, hash_size);break ;case REFTABLE_REF_VAL2 : - ref->value.val2.value =reftable_malloc (hash_size);memcpy (ref->value.val2.value, src->value.val2.value, hash_size); - ref->value.val2.target_value =reftable_malloc (hash_size);memcpy (ref->value.val2.target_value, src->value.val2.target_value, hash_size);break ;
@@ -298,8 +296,6 @@ void reftable_ref_record_release(struct reftable_ref_record *ref)reftable_free (ref->value.symref);break ;case REFTABLE_REF_VAL2 : -reftable_free (ref->value.val2.target_value); -reftable_free (ref->value.val2.value);break ;case REFTABLE_REF_VAL1 :break ;
@@ -401,11 +397,9 @@ static int reftable_ref_record_decode(void *rec, struct strbuf key,return -1 ; } - r->value.val2.value =reftable_malloc (hash_size);memcpy (r->value.val2.value, in.buf, hash_size);string_view_consume (&in, hash_size); - r->value.val2.target_value =reftable_malloc (hash_size);memcpy (r->value.val2.target_value, in.buf, hash_size);string_view_consume (&in, hash_size);break ;
reftable/record_test.c +0 -4
@@ -122,11 +122,7 @@ static void test_reftable_ref_record_roundtrip(void)set_hash (in.u.ref.value.val1,1 );break ;case REFTABLE_REF_VAL2 : - in.u.ref.value.val2.value = -reftable_malloc (GIT_SHA1_RAWSZ );set_hash (in.u.ref.value.val2.value,1 ); - in.u.ref.value.val2.target_value = -reftable_malloc (GIT_SHA1_RAWSZ );set_hash (in.u.ref.value.val2.target_value,2 );break ;case REFTABLE_REF_SYMREF :
reftable/reftable-record.h +2 -2
@@ -41,8 +41,8 @@ struct reftable_ref_record {union {unsigned char val1[GIT_MAX_RAWSZ ];struct { -uint8_t *value;/* first value, malloced hash */ -uint8_t *target_value;/* second value, malloced hash */ +unsigned char value[GIT_MAX_RAWSZ ];/* first hash */ +unsigned char target_value[GIT_MAX_RAWSZ ];/* second hash */ } val2;char *symref;/* referent, malloced 0-terminated string */ } value;
Signature · 1 line
2.43.GIT
PATCH v3 7/8 reftable/merged: really reuse buffers to compute record keys
In reply to Patrick SteinhardtIn 829231dc20 (reftable/merged: reuse buffer to compute record keys, 2023-12-11), we have refactored the merged iterator to reuse a pair of long-living strbufs by relying on the fact that reftable_record_key() tries to reuse already allocated strbufs by calling strbuf_reset(), which should give us significantly fewer reallocations compared to the old code that used on-stack strbufs that are allocated for each and every iteration. Unfortunately, we called strbuf_release() on these long-living strbufs that we meant to reuse on each iteration, defeating the optimization.
Fix this performance issue by not releasing those buffers on iteration anymore, where we instead rely on merged_iter_close() to release the buffers for us.
Using git show-ref --quiet in a repository with ~350k refs this leads to a significant drop in allocations. Before:
HEAP SUMMARY:
in use at exit: 21,163 bytes in 193 blocks
total heap usage: 1,410,148 allocs, 1,409,955 frees, 61,976,068 bytes allocated
After:
HEAP SUMMARY:
in use at exit: 21,163 bytes in 193 blocks
total heap usage: 708,058 allocs, 707,865 frees, 36,783,255 bytes allocated
--- reftable/merged.c | 2 -- 1 file changed, 2 deletions(-)
reftable/merged.c +0 -2
@@ -128,8 +128,6 @@ static int merged_iter_next_entry(struct merged_iter *mi, done:reftable_record_release (&entry.rec); -strbuf_release (&mi->entry_key); -strbuf_release (&mi->key);return err; }
Signature · 1 line
2.43.GIT
PATCH v3 8/8 reftable/merged: transfer ownership of records when iterating
In reply to Patrick SteinhardtWhen iterating over records with the merged iterator we put the records into a priority queue before yielding them to the caller. This means that we need to allocate the contents of these records before we can pass them over to the caller.
The handover to the caller is quite inefficient though because we first deallocate the record passed in by the caller and then copy over the new record, which requires us to reallocate memory.
Refactor the code to instead transfer ownership of the new record to the caller. So instead of reallocating all contents, we now release the old record and then copy contents of the new record into place.
The following benchmark of git show-ref --quiet in a repository with around 350k refs shows a clear improvement. Before:
HEAP SUMMARY:
in use at exit: 21,163 bytes in 193 blocks
total heap usage: 708,058 allocs, 707,865 frees, 36,783,255 bytes allocated
After:
HEAP SUMMARY:
in use at exit: 21,163 bytes in 193 blocks
total heap usage: 357,007 allocs, 356,814 frees, 24,193,602 bytes allocated
This shows that we now have roundabout a single allocation per record that we're yielding from the iterator. Ideally, we'd also get rid of this allocation so that the number of allocations doesn't scale with the number of refs anymore. This would require some larger surgery though because the memory is owned by the priority queue before transferring it over to the caller.
--- reftable/merged.c | 6 ++++-- 1 file changed, 4 insertions(+), 2 deletions(-)
reftable/merged.c +4 -2
@@ -124,10 +124,12 @@ static int merged_iter_next_entry(struct merged_iter *mi,reftable_record_release (&top.rec); } -reftable_record_copy_from (rec, &entry.rec,hash_size (mi->hash_id)); +reftable_record_release (rec); + *rec = entry.rec; done: -reftable_record_release (&entry.rec); +if (err) +reftable_record_release (&entry.rec);return err; }
Signature · 1 line
2.43.GIT
Re: [PATCH v3 5/8] reftable/record: store "val1" hashes as static arrays
In reply to Patrick SteinhardtQuoted 17 lines · Patrick Steinhardt
When reading ref records of type "val1", we store its object ID in an allocated array. This results in an additional allocation for every single ref record we read, which is rather inefficient especially when iterating over refs.
Refactor the code to instead use an embedded array of
GIT_MAX_RAWSZbytes. While this means thatstruct ref_recordis bigger now, we typically do not store all refs in an array anyway and instead only handle a limited number of records at the same point in time.Using
git show-ref --quietin a repository with ~350k refs this leads to a significant drop in allocations. Before:HEAP SUMMARY:
in use at exit: 21,098 bytes in 192 blocks
total heap usage: 2,116,683 allocs, 2,116,491 frees, 76,098,060 bytes allocated
Quoted 5 lines
After:
HEAP SUMMARY:
in use at exit: 21,098 bytes in 192 blocks
total heap usage: 1,419,031 allocs, 1,418,839 frees, 62,145,036 bytes allocated
Curious, did you also do perf benchmarking on this?
Patrick Steinhardt <[email protected]> writes:
Hello,
Quoted 5 lines
Hi,
this is the third version of my patch series that contains additional fixes and optimizations for the reftable library.
I have reviewed this version and have nothing to add. Thanks!
Re: [PATCH v3 5/8] reftable/record: store "val1" hashes as static arrays
In reply to Karthik NayakQuoted 19 lines · Karthik Nayak
Quoted 17 lines · Patrick Steinhardt
When reading ref records of type "val1", we store its object ID in an allocated array. This results in an additional allocation for every single ref record we read, which is rather inefficient especially when iterating over refs.
Refactor the code to instead use an embedded array of
GIT_MAX_RAWSZbytes. While this means thatstruct ref_recordis bigger now, we typically do not store all refs in an array anyway and instead only handle a limited number of records at the same point in time.Using
git show-ref --quietin a repository with ~350k refs this leads to a significant drop in allocations. Before:HEAP SUMMARY:
in use at exit: 21,098 bytes in 192 blocks
total heap usage: 2,116,683 allocs, 2,116,491 frees, 76,098,060 bytes allocated
Quoted 7 lines
Quoted 5 lines
After:
HEAP SUMMARY:
in use at exit: 21,098 bytes in 192 blocks
total heap usage: 1,419,031 allocs, 1,418,839 frees, 62,145,036 bytes allocatedCurious, did you also do perf benchmarking on this?
I didn't back then, but here you go. The following test shows a single ref matching a specific pattern out of 1 million refs:
Benchmark 1: show-ref: single matching ref (revision = HEAD~)
Time (mean ± σ): 191.1 ms ± 5.2 ms [User: 188.1 ms, System: 2.8 ms]
Range (min … max): 186.2 ms … 214.5 ms 100 runs
Benchmark 2: show-ref: single matching ref (revision = HEAD)
Time (mean ± σ): 189.7 ms ± 5.3 ms [User: 186.7 ms, System: 2.8 ms]
Range (min … max): 184.1 ms … 213.4 ms 100 runs
Summary
show-ref: single matching ref (revision = HEAD) ran
1.01 ± 0.04 times faster than show-ref: single matching ref (revision = HEAD~)
Not much of a win here, which is probably expected. On glibc the allocator seems to be really efficient churning out many small blocks of memory, which is also something I have noticed in other contexts. I do expect that other platorms might see more significant results.
Patrick
Re: [PATCH v3 1/8] reftable/stack: do not overwrite errors when compacting
In reply to Patrick SteinhardtGood catch!
Sorry for messing this up.
Quoted 2 lines
In the worst case,
this can lead to a compacted stack that is missing records.
Yeah, that would be an insidious corruption. Have you considered writing a test to reproduce this (and thus verify that the fix really fixes the problem?)
I think it wouldn't be too difficult: you could create a custom blocksource wrapper that returns I/O error on the Nth read, and then create a reftable with two ref blocks (could just be 2 records if you use a small blocksize and a large refname) and two log blocks. Merge that with an empty table, and see if the compacted result is what you got in. Loop over N to get coverage for all error paths.
Quoted 71 lines · Patrick Steinhardt
In order to compact multiple stacks we iterate through the merged ref and log records. When there is any error either when reading the records from the old merged table or when writing the records to the new table then we break out of the respective loops. When breaking out of the loop for the ref records though the error code will be overwritten, which may cause us to inadvertently skip over bad ref records. In the worst case, this can lead to a compacted stack that is missing records.
Fix the code by using
goto doneinstead so that any potential error codes are properly returned to the caller.Signed-off-by Patrick Steinhardt <[email protected]>--- reftable/stack.c | 20 ++++++++------------ 1 file changed, 8 insertions(+), 12 deletions(-)reftable/stack.c +8
-13@@ -801,18 +801,16 @@ static int stack_write_compact(struct reftable_stack *st, err =0 ;break ; } -if (err <0 ) { -break ; - } +if (err <0 ) + goto done;if (first ==0 &&reftable_ref_record_is_deletion (&ref)) {continue ; } err =reftable_writer_add_ref (wr, &ref); -if (err <0 ) { -break ; - } +if (err <0 ) + goto done; entries++; }reftable_iterator_destroy (&it);@@ -827,9 +825,8 @@ static int stack_write_compact(struct reftable_stack *st, err =0 ;break ; } -if (err <0 ) { -break ; - } +if (err <0 ) + goto done;if (first ==0 &&reftable_log_record_is_deletion (&log)) {continue ; }@@ -845,9 +842,8 @@ static int stack_write_compact(struct reftable_stack *st, } err =reftable_writer_add_log (wr, &log); -if (err <0 ) { -break ; - } +if (err <0 ) + goto done; entries++; } --2.43.GIT
Signature · 1 line
Han-Wen Nienhuys - [email protected] - http://www.xs4all.nl/~hanwen
Re: [PATCH v3 1/8] reftable/stack: do not overwrite errors when compacting
Quoted 3 lines · Han-Wen Nienhuys
Good catch!
Sorry for messing this up.
Nothing to be sorry about, bugs happen to all of us.
Quoted 7 lines
Quoted 2 lines
In the worst case,
this can lead to a compacted stack that is missing records.Yeah, that would be an insidious corruption. Have you considered writing a test to reproduce this (and thus verify that the fix really fixes the problem?)
Quoted 6 lines
I think it wouldn't be too difficult: you could create a custom blocksource wrapper that returns I/O error on the Nth read, and then create a reftable with two ref blocks (could just be 2 records if you use a small blocksize and a large refname) and two log blocks. Merge that with an empty table, and see if the compacted result is what you got in. Loop over N to get coverage for all error paths.
Ah, that's a feasible way to write such a test indeed. I may come back to it in the future and will add it to our backlog. Thanks!
Patrick