path: root/t/helper
diff options
authorAbhishek Kumar <>2021-01-16 18:11:15 (GMT)
committerJunio C Hamano <>2021-01-19 00:21:18 (GMT)
commite8b63005c48696a26f976f5f9b0ccaf1983e439d (patch)
tree9aa436c9a75068c4a4612fd7a69c3a5ff65ae227 /t/helper
parentc1a09119f68d9800be53f544389f9ef83258ee7f (diff)
commit-graph: implement generation data chunk
As discovered by Ævar, we cannot increment graph version to distinguish between generation numbers v1 and v2 [1]. Thus, one of pre-requistes before implementing generation number v2 was to distinguish between graph versions in a backwards compatible manner. We are going to introduce a new chunk called Generation DATa chunk (or GDAT). GDAT will store corrected committer date offsets whereas CDAT will still store topological level. Old Git does not understand GDAT chunk and would ignore it, reading topological levels from CDAT. New Git can parse GDAT and take advantage of newer generation numbers, falling back to topological levels when GDAT chunk is missing (as it would happen with a commit-graph written by old Git). We introduce a test environment variable 'GIT_TEST_COMMIT_GRAPH_NO_GDAT' which forces commit-graph file to be written without generation data chunk to emulate a commit-graph file written by old Git. To minimize the space required to store corrrected commit date, Git stores corrected commit date offsets into the commit-graph file, instea of corrected commit dates. This saves us 4 bytes per commit, decreasing the GDAT chunk size by half, but it's possible for the offset to overflow the 4-bytes allocated for storage. As such overflows are and should be exceedingly rare, we use the following overflow management scheme: We introduce a new commit-graph chunk, Generation Data OVerflow ('GDOV') to store corrected commit dates for commits with offsets greater than GENERATION_NUMBER_V2_OFFSET_MAX. If the offset is greater than GENERATION_NUMBER_V2_OFFSET_MAX, we set the MSB of the offset and the other bits store the position of corrected commit date in GDOV chunk, similar to how Extra Edge List is maintained. We test the overflow-related code with the following repo history: F - N - U / \ U - N - U N \ / N - F - N Where the commits denoted by U have committer date of zero seconds since Unix epoch, the commits denoted by N have committer date of 1112354055 (default committer date for the test suite) seconds since Unix epoch and the commits denoted by F have committer date of (2 ^ 31 - 2) seconds since Unix epoch. The largest offset observed is 2 ^ 31, just large enough to overflow. [1]: Signed-off-by: Abhishek Kumar <> Reviewed-by: Taylor Blau <> Reviewed-by: Derrick Stolee <> Signed-off-by: Junio C Hamano <>
Diffstat (limited to 't/helper')
1 files changed, 4 insertions, 0 deletions
diff --git a/t/helper/test-read-graph.c b/t/helper/test-read-graph.c
index 5f585a1..75927b2 100644
--- a/t/helper/test-read-graph.c
+++ b/t/helper/test-read-graph.c
@@ -33,6 +33,10 @@ int cmd__read_graph(int argc, const char **argv)
printf(" oid_lookup");
if (graph->chunk_commit_data)
printf(" commit_metadata");
+ if (graph->chunk_generation_data)
+ printf(" generation_data");
+ if (graph->chunk_generation_data_overflow)
+ printf(" generation_data_overflow");
if (graph->chunk_extra_edges)
printf(" extra_edges");
if (graph->chunk_bloom_indexes)