reftable: fixes and optimizations (pt.2)

PATCH Superseded Patrick Steinhardt 4 participants 36 messages Dec 20, 2023 – Feb 15, 2024

lore

Share & tools

lore

Patrick Steinhardt

author

2023-12-20 09:17 UTC #0 lore raw

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

Patrick Steinhardt

author

2023-12-20 09:17 UTC #1 lore raw

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.

Signed-off-by Patrick Steinhardt <[email protected]>

---
 reftable/stack.c | 20 ++++++++------------
 1 file changed, 8 insertions(+), 12 deletions(-)

reftable/stack.c +8 ~~-12~~

index 16bab82063..8729508dc3 100644
@@ -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

Patrick Steinhardt

author

2023-12-20 09:17 UTC #2 lore raw

PATCH 2/7 reftable/writer: fix index corruption when writing multiple indices

In reply to Patrick Steinhardt

Each 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.

Signed-off-by Patrick Steinhardt <[email protected]>

---
 reftable/readwrite_test.c | 80 +++++++++++++++++++++++++++++++++++++++
 reftable/writer.c         |  4 +-
 2 files changed, 82 insertions(+), 2 deletions(-)

reftable/readwrite_test.c +80 -0

index 278663f22d..9c16e0504e 100644
@@ -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

index 2e322a5683..ee4590e20f 100644
@@ -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

Patrick Steinhardt

author

2023-12-20 09:17 UTC #3 lore raw

PATCH 3/7 reftable/record: constify some parts of the interface

In reply to Patrick Steinhardt

We'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.

Signed-off-by Patrick Steinhardt <[email protected]>

---
 reftable/record.c          | 8 ++++----
 reftable/reftable-record.h | 4 ++--
 2 files changed, 6 insertions(+), 6 deletions(-)

reftable/record.c +4 -4

index fbaa1fbef5..5e258c734b 100644
@@ -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

index 67104f8fbf..f7eb2d6015 100644
@@ -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

Patrick Steinhardt

author

2023-12-20 09:17 UTC #4 lore raw

PATCH 4/7 reftable/record: store "val1" hashes as static arrays

In reply to 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_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

Signed-off-by Patrick Steinhardt <[email protected]>

---
 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

index c00bbc8aed..dedb05c7d8 100644
@@ -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~~

index d08c16abef..b3927a5d73 100644
@@ -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

index 9c16e0504e..56c0b4db5d 100644
@@ -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

index 5e258c734b..a67a6b4d8a 100644
@@ -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

index 70ae78feca..5c94d26e35 100644
@@ -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

index f7eb2d6015..44b5125445 100644
@@ -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

index 14a3fc11ee..feab49d7f7 100644
@@ -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

Patrick Steinhardt

author

2023-12-20 09:25 UTC #5 lore raw

Re: [PATCH 4/7] reftable/record: store "val1" hashes as static arrays

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 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

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 allocated
Signed-off-by Patrick Steinhardt <[email protected]>

I screwed up the rebase. The following diff is required on top:

reftable/readwrite_test.c +1 -2

index 56c0b4db5d..87b238105c 100644
@@ -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

Patrick Steinhardt

author

2023-12-20 09:17 UTC #6 lore raw

PATCH 5/7 reftable/record: store "val2" hashes as static arrays

In reply to Patrick Steinhardt

Similar 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.

Signed-off-by Patrick Steinhardt <[email protected]>

---
 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

index 56c0b4db5d..900afc1b70 100644
@@ -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

index a67a6b4d8a..5c3fbb7b2a 100644
@@ -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

index 5c94d26e35..2876db7d27 100644
@@ -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

index 44b5125445..83d252ec2c 100644
@@ -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

Patrick Steinhardt

author

2023-12-20 09:17 UTC #7 lore raw

PATCH 6/7 reftable/merged: really reuse buffers to compute record keys

In reply to 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.

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

Signed-off-by Patrick Steinhardt <[email protected]>

---
 reftable/merged.c | 2 --
 1 file changed, 2 deletions(-)

reftable/merged.c +0 -2

index 556bb5c556..a28bb99aaf 100644
@@ -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

Patrick Steinhardt

author

2023-12-20 09:17 UTC #8 lore raw

PATCH 7/7 reftable/merged: transfer ownership of records when iterating

In reply to Patrick Steinhardt

When 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.

Signed-off-by Patrick Steinhardt <[email protected]>

---
 reftable/merged.c | 6 ++++--
 1 file changed, 4 insertions(+), 2 deletions(-)

reftable/merged.c +4 -2

index a28bb99aaf..a52914d667 100644
@@ -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

Junio C Hamano

2023-12-20 19:10 UTC #9 lore raw

In reply to Patrick Steinhardt

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

index 83d252ec2c..fd1160615c 100644
@@ -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

index 1b602dda58..50b1a4f4dd 100644
@@ -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"
 
 /*

Patrick Steinhardt

author

2023-12-28 06:27 UTC #10 lore raw

v2 cover reftable: fixes and optimizations (pt.2)

In reply to Patrick Steinhardt

Hi,

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

Patrick Steinhardt

author

2023-12-28 06:27 UTC #11 lore raw

PATCH v2 1/8 reftable/stack: do not overwrite errors when compacting

Fix the code by using goto done instead 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 ~~-12~~

index 16bab82063..8729508dc3 100644
@@ -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

Patrick Steinhardt

author

2023-12-28 06:27 UTC #12 lore raw

PATCH v2 2/8 reftable/stack: do not auto-compact twice in `reftable_stack_add()`

In reply to Patrick Steinhardt

In 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.

Reported-by Han-Wen Nienhuys <[email protected]>

Signed-off-by Patrick Steinhardt <[email protected]>

---
 reftable/stack.c | 3 ---
 1 file changed, 3 deletions(-)

reftable/stack.c +0 -3

index 8729508dc3..7ffeb3ee10 100644
@@ -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

Patrick Steinhardt

author

2023-12-28 06:27 UTC #13 lore raw

PATCH v2 3/8 reftable/writer: fix index corruption when writing multiple indices

In reply to Patrick Steinhardt

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.

Fix this corruption by clearing the index after having written the last block.

Signed-off-by Patrick Steinhardt <[email protected]>

---
 reftable/readwrite_test.c | 80 +++++++++++++++++++++++++++++++++++++++
 reftable/writer.c         |  4 +-
 2 files changed, 82 insertions(+), 2 deletions(-)

reftable/readwrite_test.c +80 -0

index 278663f22d..9c16e0504e 100644
@@ -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

index 2e322a5683..ee4590e20f 100644
@@ -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

Patrick Steinhardt

author

2023-12-28 06:27 UTC #14 lore raw

PATCH v2 4/8 reftable/record: constify some parts of the interface

In reply to Patrick Steinhardt

We'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.

Signed-off-by Patrick Steinhardt <[email protected]>

---
 reftable/record.c          | 8 ++++----
 reftable/reftable-record.h | 4 ++--
 2 files changed, 6 insertions(+), 6 deletions(-)

reftable/record.c +4 -4

index fbaa1fbef5..5e258c734b 100644
@@ -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

index 67104f8fbf..f7eb2d6015 100644
@@ -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

Patrick Steinhardt

author

2023-12-28 06:27 UTC #15 lore raw

PATCH v2 5/8 reftable/record: store "val1" hashes as static arrays

In reply to Patrick Steinhardt

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

Signed-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

index c00bbc8aed..dedb05c7d8 100644
@@ -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~~

index d08c16abef..b3927a5d73 100644
@@ -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~~

index 9c16e0504e..87b238105c 100644
@@ -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

index 5e258c734b..a67a6b4d8a 100644
@@ -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

index 70ae78feca..5c94d26e35 100644
@@ -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

index f7eb2d6015..7f3a0df635 100644
@@ -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

index 14a3fc11ee..feab49d7f7 100644
@@ -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

Junio C Hamano

2023-12-28 17:03 UTC #16 lore raw

Re: [PATCH v2 5/8] reftable/record: store "val1" hashes as static arrays

Quoted 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_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.

Nicely explained.

Quoted 251 lines

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

Signed-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

index c00bbc8aed..dedb05c7d8 100644
@@ -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~~

index d08c16abef..b3927a5d73 100644
@@ -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~~

index 9c16e0504e..87b238105c 100644
@@ -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

index 5e258c734b..a67a6b4d8a 100644
@@ -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

index 70ae78feca..5c94d26e35 100644
@@ -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

index f7eb2d6015..7f3a0df635 100644
@@ -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

index 14a3fc11ee..feab49d7f7 100644
@@ -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);
 		}

Patrick Steinhardt

author

2023-12-28 06:28 UTC #17 lore raw

PATCH v2 6/8 reftable/record: store "val2" hashes as static arrays

In reply to Patrick Steinhardt

Similar 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

Signed-off-by Patrick Steinhardt <[email protected]>

---
 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

index 87b238105c..178766dfa8 100644
@@ -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

index a67a6b4d8a..5c3fbb7b2a 100644
@@ -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

index 5c94d26e35..2876db7d27 100644
@@ -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

index 7f3a0df635..bb6e99acd3 100644
@@ -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

Patrick Steinhardt

author

2023-12-28 06:28 UTC #18 lore raw

PATCH v2 7/8 reftable/merged: really reuse buffers to compute record keys

In reply to Patrick Steinhardt

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

Signed-off-by Patrick Steinhardt <[email protected]>

---
 reftable/merged.c | 2 --
 1 file changed, 2 deletions(-)

reftable/merged.c +0 -2

index 556bb5c556..a28bb99aaf 100644
@@ -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

Junio C Hamano

2023-12-28 17:03 UTC #19 lore raw

Re: [PATCH v2 7/8] reftable/merged: really reuse buffers to compute record keys

Quoted 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 --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
Signed-off-by Patrick Steinhardt <[email protected]>
---
 reftable/merged.c | 2 --
 1 file changed, 2 deletions(-)
reftable/merged.c +0 -2
index 556bb5c556..a28bb99aaf 100644
@@ -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;
 }

Patrick Steinhardt

author

2023-12-28 06:28 UTC #20 lore raw

PATCH v2 8/8 reftable/merged: transfer ownership of records when iterating

In reply to Patrick Steinhardt

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.

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

Signed-off-by Patrick Steinhardt <[email protected]>

---
 reftable/merged.c | 6 ++++--
 1 file changed, 4 insertions(+), 2 deletions(-)

reftable/merged.c +4 -2

index a28bb99aaf..a52914d667 100644
@@ -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

Junio C Hamano

2023-12-28 17:04 UTC #21 lore raw

Re: [PATCH v2 8/8] reftable/merged: transfer ownership of records when iterating

Quoted 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.

Patrick Steinhardt

author

2024-01-03 06:22 UTC #22 lore raw

v3 cover reftable: fixes and optimizations (pt.2)

In reply to Patrick Steinhardt

Hi,

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

 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

Patrick Steinhardt

author

2024-01-03 06:22 UTC #23 lore raw

PATCH v3 1/8 reftable/stack: do not overwrite errors when compacting

Fix the code by using goto done instead 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 ~~-12~~

index 16bab82063..8729508dc3 100644
@@ -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

Han-Wen Nienhuys

2024-02-14 15:13 UTC #24 lore raw

Re: [PATCH v3 1/8] reftable/stack: do not overwrite errors when compacting

Good 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

Fix the code by using goto done instead 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~~

index 16bab82063..8729508dc3 100644
@@ -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

Patrick Steinhardt

author

2024-02-15 07:43 UTC #25 lore raw

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

Patrick Steinhardt

author

2024-01-03 06:22 UTC #26 lore raw

PATCH v3 2/8 reftable/stack: do not auto-compact twice in `reftable_stack_add()`

In reply to Patrick Steinhardt

- 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.

Reported-by Han-Wen Nienhuys <[email protected]>

Signed-off-by Patrick Steinhardt <[email protected]>

---
 reftable/stack.c | 3 ---
 1 file changed, 3 deletions(-)

reftable/stack.c +0 -3

index 8729508dc3..7ffeb3ee10 100644
@@ -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

Patrick Steinhardt

author

2024-01-03 06:22 UTC #27 lore raw

PATCH v3 3/8 reftable/writer: fix index corruption when writing multiple indices

In reply to Patrick Steinhardt

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.

Fix this corruption by clearing the index after having written the last block.

Signed-off-by Patrick Steinhardt <[email protected]>

---
 reftable/readwrite_test.c | 80 +++++++++++++++++++++++++++++++++++++++
 reftable/writer.c         |  4 +-
 2 files changed, 82 insertions(+), 2 deletions(-)

reftable/readwrite_test.c +80 -0

index 278663f22d..9c16e0504e 100644
@@ -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

index 2e322a5683..ee4590e20f 100644
@@ -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

Patrick Steinhardt

author

2024-01-03 06:22 UTC #28 lore raw

PATCH v3 4/8 reftable/record: constify some parts of the interface

In reply to Patrick Steinhardt

We'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.

Signed-off-by Patrick Steinhardt <[email protected]>

---
 reftable/record.c          | 8 ++++----
 reftable/reftable-record.h | 4 ++--
 2 files changed, 6 insertions(+), 6 deletions(-)

reftable/record.c +4 -4

index fbaa1fbef5..5e258c734b 100644
@@ -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

index 67104f8fbf..f7eb2d6015 100644
@@ -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

Patrick Steinhardt

author

2024-01-03 06:22 UTC #29 lore raw

PATCH v3 5/8 reftable/record: store "val1" hashes as static arrays

In reply to 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_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

Signed-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

index c00bbc8aed..dedb05c7d8 100644
@@ -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~~

index d08c16abef..b3927a5d73 100644
@@ -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~~

index 9c16e0504e..87b238105c 100644
@@ -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

index 5e258c734b..a67a6b4d8a 100644
@@ -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

index 70ae78feca..5c94d26e35 100644
@@ -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

index f7eb2d6015..7f3a0df635 100644
@@ -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

index 14a3fc11ee..feab49d7f7 100644
@@ -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

Karthik Nayak

2024-02-05 11:39 UTC #30 lore raw

Re: [PATCH v3 5/8] reftable/record: store "val1" hashes as static arrays

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_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

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

author

2024-02-06 06:03 UTC #31 lore raw

Re: [PATCH v3 5/8] reftable/record: store "val1" hashes as static arrays

Quoted 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_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

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 allocated
Curious, 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

Patrick Steinhardt

author

2024-01-03 06:22 UTC #32 lore raw

PATCH v3 6/8 reftable/record: store "val2" hashes as static arrays

In reply to Patrick Steinhardt

Similar 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

Signed-off-by Patrick Steinhardt <[email protected]>

---
 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

index 87b238105c..178766dfa8 100644
@@ -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

index a67a6b4d8a..5c3fbb7b2a 100644
@@ -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

index 5c94d26e35..2876db7d27 100644
@@ -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

index 7f3a0df635..bb6e99acd3 100644
@@ -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

Patrick Steinhardt

author

2024-01-03 06:22 UTC #33 lore raw

PATCH v3 7/8 reftable/merged: really reuse buffers to compute record keys

In reply to Patrick Steinhardt

In 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

Signed-off-by Patrick Steinhardt <[email protected]>

---
 reftable/merged.c | 2 --
 1 file changed, 2 deletions(-)

reftable/merged.c +0 -2

index 556bb5c556..a28bb99aaf 100644
@@ -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

Patrick Steinhardt

author

2024-01-03 06:22 UTC #34 lore raw

PATCH v3 8/8 reftable/merged: transfer ownership of records when iterating

In reply to Patrick Steinhardt

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.

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.

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

Signed-off-by Patrick Steinhardt <[email protected]>

---
 reftable/merged.c | 6 ++++--
 1 file changed, 4 insertions(+), 2 deletions(-)

reftable/merged.c +4 -2

index a28bb99aaf..a52914d667 100644
@@ -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

Karthik Nayak

2024-02-05 13:08 UTC #35 lore raw

In reply to Patrick Steinhardt

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!