From: Derrick Stolee via GitGitGadget <hidden> Date: 2021-01-26 16:03:21
This is a restart on the topic previously submitted [1] but dropped because
ak/corrected-commit-date was still in progress. This version is based on
that branch.
[1]
https://lore.kernel.org/git/pull.804.git.1607012215.gitgitgadget@gmail.com/
This version also changes the approach to use a more dynamic interaction
with a struct chunkfile pointer. This idea is credited to Taylor Blau [2],
but I started again from scratch. I also go further to make struct chunkfile
anonymous to API consumers. It is defined only in chunk-format.c, which
should hopefully deter future users from interacting with that data
directly.
[2] https://lore.kernel.org/git/X8%2FI%2FRzXZksio+ri@nand.local/
This combined API is beneficial to reduce duplicated logic. Or rather, to
ensure that similar file formats have similar protections against bad data.
The multi-pack-index code did not have as many guards as the commit-graph
code did, but now they both share a common base that checks for things like
duplicate chunks or offsets outside the size of the file.
Here are some stats for the end-to-end change:
* 638 insertions(+), 456 deletions(-).
* commit-graph.c: 171 insertions(+), 192 deletions(-)
* midx.c: 196 insertions(+), 260 deletions(-)
While there is an overall increase to the code size, the consumers do get a
bit smaller. Boilerplate things like abstracting method to match
chunk_write_fn and chunk_read_fn make up a lot of these insertions. The
"interesting" code gets a lot smaller and cleaner.
Thanks, -Stolee
Derrick Stolee (17):
commit-graph: anonymize data in chunk_write_fn
chunk-format: create chunk format write API
commit-graph: use chunk-format write API
midx: rename pack_info to write_midx_context
midx: use context in write_midx_pack_names()
midx: add entries to write_midx_context
midx: add pack_perm to write_midx_context
midx: add num_large_offsets to write_midx_context
midx: return success/failure in chunk write methods
midx: drop chunk progress during write
midx: use chunk-format API in write_midx_internal()
chunk-format: create read chunk API
commit-graph: use chunk-format read API
midx: use chunk-format read API
midx: use 64-bit multiplication for chunk sizes
chunk-format: restore duplicate chunk checks
chunk-format: add technical docs
Documentation/technical/chunk-format.txt | 54 +++
.../technical/commit-graph-format.txt | 3 +
Documentation/technical/pack-format.txt | 3 +
Makefile | 1 +
chunk-format.c | 165 +++++++
chunk-format.h | 41 ++
commit-graph.c | 363 +++++++-------
midx.c | 456 ++++++++----------
t/t5318-commit-graph.sh | 2 +-
t/t5319-multi-pack-index.sh | 6 +-
10 files changed, 638 insertions(+), 456 deletions(-)
create mode 100644 Documentation/technical/chunk-format.txt
create mode 100644 chunk-format.c
create mode 100644 chunk-format.h
base-commit: 5a3b130cad0d5c770f766e3af6d32b41766374c0
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-848%2Fderrickstolee%2Fchunk-format%2Frefactor-v1
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-848/derrickstolee/chunk-format/refactor-v1
Pull-Request: https://github.com/gitgitgadget/git/pull/848
--
gitgitgadget
From: Derrick Stolee via GitGitGadget <hidden> Date: 2021-01-26 16:02:33
From: Derrick Stolee <redacted>
In anticipation of combining the logic from the commit-graph and
multi-pack-index file formats, create a new chunk-format API. Use a
'struct chunkfile' pointer to keep track of data that has been
registered for writes. This struct is anonymous outside of
chunk-format.c to ensure no user attempts to interfere with the data.
The next change will use this API in commit-graph.c, but the general
approach is:
1. initialize the chunkfile with init_chunkfile(f).
2. add chunks in the intended writing order with add_chunk().
3. write any header information to the hashfile f.
4. write the chunkfile data using write_chunkfile().
5. free the chunkfile struct using free_chunkfile().
Helped-by: Taylor Blau [off-list ref]
Signed-off-by: Derrick Stolee <redacted>
---
Makefile | 1 +
chunk-format.c | 91 ++++++++++++++++++++++++++++++++++++++++++++++++++
chunk-format.h | 20 +++++++++++
3 files changed, 112 insertions(+)
create mode 100644 chunk-format.c
create mode 100644 chunk-format.h
@@ -0,0 +1,91 @@+#include"cache.h"+#include"chunk-format.h"+#include"csum-file.h"+#define CHUNK_LOOKUP_WIDTH 12++/*+*Whenwritingachunk-basedfileformat,collectthechunksin+*anarrayofchunk_infostructs.Thesizestoresthe_expected_+*amountofdatathatwillbewrittenbywrite_fn.+*/+structchunk_info{+uint32_tid;+uint64_tsize;+chunk_write_fnwrite_fn;+};++structchunkfile{+structhashfile*f;++structchunk_info*chunks;+size_tchunks_nr;+size_tchunks_alloc;+};++structchunkfile*init_chunkfile(structhashfile*f)+{+structchunkfile*cf=xcalloc(1,sizeof(*cf));+cf->f=f;+returncf;+}++voidfree_chunkfile(structchunkfile*cf)+{+if(!cf)+return;+free(cf->chunks);+free(cf);+}++intget_num_chunks(structchunkfile*cf)+{+returncf->chunks_nr;+}++voidadd_chunk(structchunkfile*cf,+uint64_tid,+chunk_write_fnfn,+size_tsize)+{+ALLOC_GROW(cf->chunks,cf->chunks_nr+1,cf->chunks_alloc);++cf->chunks[cf->chunks_nr].id=id;+cf->chunks[cf->chunks_nr].write_fn=fn;+cf->chunks[cf->chunks_nr].size=size;+cf->chunks_nr++;+}++intwrite_chunkfile(structchunkfile*cf,void*data)+{+inti;+size_tcur_offset=cf->f->offset+cf->f->total;++/* Add the table of contents to the current offset */+cur_offset+=(cf->chunks_nr+1)*CHUNK_LOOKUP_WIDTH;++for(i=0;i<cf->chunks_nr;i++){+hashwrite_be32(cf->f,cf->chunks[i].id);+hashwrite_be64(cf->f,cur_offset);++cur_offset+=cf->chunks[i].size;+}++/* Trailing entry marks the end of the chunks */+hashwrite_be32(cf->f,0);+hashwrite_be64(cf->f,cur_offset);++for(i=0;i<cf->chunks_nr;i++){+uint64_tstart_offset=cf->f->total+cf->f->offset;+intresult=cf->chunks[i].write_fn(cf->f,data);++if(result)+returnresult;++if(cf->f->total+cf->f->offset!=start_offset+cf->chunks[i].size)+BUG("expected to write %"PRId64" bytes to chunk %"PRIx32", but wrote %"PRId64" instead",+cf->chunks[i].size,cf->chunks[i].id,+cf->f->total+cf->f->offset-start_offset);+}++return0;+}
From: Derrick Stolee via GitGitGadget <hidden> Date: 2021-01-26 16:03:21
From: Derrick Stolee <redacted>
In preparation for creating an API around file formats using chunks and
tables of contents, prepare the commit-graph write code to use
prototypes that will match this new API.
Specifically, convert chunk_write_fn to take a "void *data" parameter
instead of the commit-graph-specific "struct write_commit_graph_context"
pointer.
Signed-off-by: Derrick Stolee <redacted>
---
commit-graph.c | 38 ++++++++++++++++++++++++++++----------
1 file changed, 28 insertions(+), 10 deletions(-)
From: Derrick Stolee via GitGitGadget <hidden> Date: 2021-01-26 16:03:21
From: Derrick Stolee <redacted>
In an effort to align the write_midx_internal() to use the chunk-format
API, start converting chunk writing methods to match chunk_write_fn. The
first case is to convert write_midx_pack_names() to take "void *data".
We already have the necessary data in "struct write_midx_context", so
this conversion is rather mechanical.
Signed-off-by: Derrick Stolee <redacted>
---
midx.c | 21 ++++++++++-----------
1 file changed, 10 insertions(+), 11 deletions(-)
From: Derrick Stolee via GitGitGadget <hidden> Date: 2021-01-26 16:03:21
From: Derrick Stolee <redacted>
In an effort to align write_midx_internal() with the chunk-format API,
continue to group necessary data into "struct write_midx_context". This
change collects the "struct pack_midx_entry *entries" list and its count
into the context.
Update write_midx_oid_fanout() and write_midx_oid_lookup() to take the
context directly, as these are easy conversions with this new data.
Only the callers of write_midx_object_offsets() and
write_midx_large_offsets() are updated here, since additional data in
the context before those methods can match chunk_write_fn.
Signed-off-by: Derrick Stolee <redacted>
---
midx.c | 49 ++++++++++++++++++++++++++-----------------------
1 file changed, 26 insertions(+), 23 deletions(-)
From: Derrick Stolee via GitGitGadget <hidden> Date: 2021-01-26 16:03:57
From: Derrick Stolee <redacted>
In an effort to streamline our chunk-based file formats, align some of
the code structure in write_midx_internal() to be similar to the
patterns in write_commit_graph_file().
Specifically, let's create a "struct write_midx_context" that can be
used as a data parameter to abstract function types.
This change only renames "struct pack_info" to "struct
write_midx_context" and the names of instances from "packs" to "ctx". In
future changes, we will expand the data inside "struct
write_midx_context" and align our chunk-writing method with the
chunk-format API.
Signed-off-by: Derrick Stolee <redacted>
---
midx.c | 130 ++++++++++++++++++++++++++++-----------------------------
1 file changed, 65 insertions(+), 65 deletions(-)
@@ -463,37 +463,37 @@ struct pack_list {staticvoidadd_pack_to_midx(constchar*full_path,size_tfull_path_len,constchar*file_name,void*data){-structpack_list*packs=(structpack_list*)data;+structwrite_midx_context*ctx=(structwrite_midx_context*)data;if(ends_with(file_name,".idx")){-display_progress(packs->progress,++packs->pack_paths_checked);-if(packs->m&&midx_contains_pack(packs->m,file_name))+display_progress(ctx->progress,++ctx->pack_paths_checked);+if(ctx->m&&midx_contains_pack(ctx->m,file_name))return;-ALLOC_GROW(packs->info,packs->nr+1,packs->alloc);+ALLOC_GROW(ctx->info,ctx->nr+1,ctx->alloc);-packs->info[packs->nr].p=add_packed_git(full_path,-full_path_len,-0);+ctx->info[ctx->nr].p=add_packed_git(full_path,+full_path_len,+0);-if(!packs->info[packs->nr].p){+if(!ctx->info[ctx->nr].p){warning(_("failed to add packfile '%s'"),full_path);return;}-if(open_pack_index(packs->info[packs->nr].p)){+if(open_pack_index(ctx->info[ctx->nr].p)){warning(_("failed to open pack-index '%s'"),full_path);-close_pack(packs->info[packs->nr].p);-FREE_AND_NULL(packs->info[packs->nr].p);+close_pack(ctx->info[ctx->nr].p);+FREE_AND_NULL(ctx->info[ctx->nr].p);return;}-packs->info[packs->nr].pack_name=xstrdup(file_name);-packs->info[packs->nr].orig_pack_int_id=packs->nr;-packs->info[packs->nr].expired=0;-packs->nr++;+ctx->info[ctx->nr].pack_name=xstrdup(file_name);+ctx->info[ctx->nr].orig_pack_int_id=ctx->nr;+ctx->info[ctx->nr].expired=0;+ctx->nr++;}}
@@ -820,40 +820,40 @@ static int write_midx_internal(const char *object_dir, struct multi_pack_index *midx_name);if(m)-packs.m=m;+ctx.m=m;else-packs.m=load_multi_pack_index(object_dir,1);--packs.nr=0;-packs.alloc=packs.m?packs.m->num_packs:16;-packs.info=NULL;-ALLOC_ARRAY(packs.info,packs.alloc);--if(packs.m){-for(i=0;i<packs.m->num_packs;i++){-ALLOC_GROW(packs.info,packs.nr+1,packs.alloc);--packs.info[packs.nr].orig_pack_int_id=i;-packs.info[packs.nr].pack_name=xstrdup(packs.m->pack_names[i]);-packs.info[packs.nr].p=NULL;-packs.info[packs.nr].expired=0;-packs.nr++;+ctx.m=load_multi_pack_index(object_dir,1);++ctx.nr=0;+ctx.alloc=ctx.m?ctx.m->num_packs:16;+ctx.info=NULL;+ALLOC_ARRAY(ctx.info,ctx.alloc);++if(ctx.m){+for(i=0;i<ctx.m->num_packs;i++){+ALLOC_GROW(ctx.info,ctx.nr+1,ctx.alloc);++ctx.info[ctx.nr].orig_pack_int_id=i;+ctx.info[ctx.nr].pack_name=xstrdup(ctx.m->pack_names[i]);+ctx.info[ctx.nr].p=NULL;+ctx.info[ctx.nr].expired=0;+ctx.nr++;}}-packs.pack_paths_checked=0;+ctx.pack_paths_checked=0;if(flags&MIDX_PROGRESS)-packs.progress=start_delayed_progress(_("Adding packfiles to multi-pack-index"),0);+ctx.progress=start_delayed_progress(_("Adding packfiles to multi-pack-index"),0);else-packs.progress=NULL;+ctx.progress=NULL;-for_each_file_in_pack_dir(object_dir,add_pack_to_midx,&packs);-stop_progress(&packs.progress);+for_each_file_in_pack_dir(object_dir,add_pack_to_midx,&ctx);+stop_progress(&ctx.progress);-if(packs.m&&packs.nr==packs.m->num_packs&&!packs_to_drop)+if(ctx.m&&ctx.nr==ctx.m->num_packs&&!packs_to_drop)gotocleanup;-entries=get_sorted_entries(packs.m,packs.info,packs.nr,&nr_entries);+entries=get_sorted_entries(ctx.m,ctx.info,ctx.nr,&nr_entries);for(i=0;i<nr_entries;i++){if(entries[i].offset>0x7fffffff)
@@ -862,19 +862,19 @@ static int write_midx_internal(const char *object_dir, struct multi_pack_index *large_offsets_needed=1;}-QSORT(packs.info,packs.nr,pack_info_compare);+QSORT(ctx.info,ctx.nr,pack_info_compare);if(packs_to_drop&&packs_to_drop->nr){intdrop_index=0;intmissing_drops=0;-for(i=0;i<packs.nr&&drop_index<packs_to_drop->nr;i++){-intcmp=strcmp(packs.info[i].pack_name,+for(i=0;i<ctx.nr&&drop_index<packs_to_drop->nr;i++){+intcmp=strcmp(ctx.info[i].pack_name,packs_to_drop->items[drop_index].string);if(!cmp){drop_index++;-packs.info[i].expired=1;+ctx.info[i].expired=1;}elseif(cmp>0){error(_("did not see pack-file %s to drop"),packs_to_drop->items[drop_index].string);
From: Derrick Stolee via GitGitGadget <hidden> Date: 2021-01-26 16:04:56
From: Derrick Stolee <redacted>
The commit-graph write logic is ready to make use of the chunk-format
write API. Each chunk write method is already in the correct prototype.
We only need to use the 'struct chunkfile' pointer and the correct API
calls.
Signed-off-by: Derrick Stolee <redacted>
---
commit-graph.c | 118 ++++++++++++++++---------------------------------
1 file changed, 37 insertions(+), 81 deletions(-)
@@ -1767,27 +1768,17 @@ static int write_graph_chunk_base(struct hashfile *f,return0;}-typedefint(*chunk_write_fn)(structhashfile*f,-void*data);--structchunk_info{-uint32_tid;-uint64_tsize;-chunk_write_fnwrite_fn;-};-staticintwrite_commit_graph_file(structwrite_commit_graph_context*ctx){uint32_ti;intfd;structhashfile*f;structlock_filelk=LOCK_INIT;-structchunk_infochunks[MAX_NUM_CHUNKS+1];constunsignedhashsz=the_hash_algo->rawsz;structstrbufprogress_title=STRBUF_INIT;intnum_chunks=3;-uint64_tchunk_offset;structobject_idfile_hash;+structchunkfile*cf;if(ctx->split){structstrbuftmp_file=STRBUF_INIT;
@@ -1833,76 +1824,50 @@ static int write_commit_graph_file(struct write_commit_graph_context *ctx)f=hashfd(lk.tempfile->fd,lk.tempfile->filename.buf);}-chunks[0].id=GRAPH_CHUNKID_OIDFANOUT;-chunks[0].size=GRAPH_FANOUT_SIZE;-chunks[0].write_fn=write_graph_chunk_fanout;-chunks[1].id=GRAPH_CHUNKID_OIDLOOKUP;-chunks[1].size=hashsz*ctx->commits.nr;-chunks[1].write_fn=write_graph_chunk_oids;-chunks[2].id=GRAPH_CHUNKID_DATA;-chunks[2].size=(hashsz+16)*ctx->commits.nr;-chunks[2].write_fn=write_graph_chunk_data;+cf=init_chunkfile(f);++add_chunk(cf,GRAPH_CHUNKID_OIDFANOUT,+write_graph_chunk_fanout,GRAPH_FANOUT_SIZE);+add_chunk(cf,GRAPH_CHUNKID_OIDLOOKUP,+write_graph_chunk_oids,hashsz*ctx->commits.nr);+add_chunk(cf,GRAPH_CHUNKID_DATA,+write_graph_chunk_data,(hashsz+16)*ctx->commits.nr);if(git_env_bool(GIT_TEST_COMMIT_GRAPH_NO_GDAT,0))ctx->write_generation_data=0;-if(ctx->write_generation_data){-chunks[num_chunks].id=GRAPH_CHUNKID_GENERATION_DATA;-chunks[num_chunks].size=sizeof(uint32_t)*ctx->commits.nr;-chunks[num_chunks].write_fn=write_graph_chunk_generation_data;-num_chunks++;-}-if(ctx->num_generation_data_overflows){-chunks[num_chunks].id=GRAPH_CHUNKID_GENERATION_DATA_OVERFLOW;-chunks[num_chunks].size=sizeof(timestamp_t)*ctx->num_generation_data_overflows;-chunks[num_chunks].write_fn=write_graph_chunk_generation_data_overflow;-num_chunks++;-}-if(ctx->num_extra_edges){-chunks[num_chunks].id=GRAPH_CHUNKID_EXTRAEDGES;-chunks[num_chunks].size=4*ctx->num_extra_edges;-chunks[num_chunks].write_fn=write_graph_chunk_extra_edges;-num_chunks++;-}+if(ctx->write_generation_data)+add_chunk(cf,GRAPH_CHUNKID_GENERATION_DATA,+write_graph_chunk_generation_data,+sizeof(uint32_t)*ctx->commits.nr);+if(ctx->num_generation_data_overflows)+add_chunk(cf,GRAPH_CHUNKID_GENERATION_DATA_OVERFLOW,+write_graph_chunk_generation_data_overflow,+sizeof(timestamp_t)*ctx->num_generation_data_overflows);+if(ctx->num_extra_edges)+add_chunk(cf,GRAPH_CHUNKID_EXTRAEDGES,+write_graph_chunk_extra_edges,+4*ctx->num_extra_edges);if(ctx->changed_paths){-chunks[num_chunks].id=GRAPH_CHUNKID_BLOOMINDEXES;-chunks[num_chunks].size=sizeof(uint32_t)*ctx->commits.nr;-chunks[num_chunks].write_fn=write_graph_chunk_bloom_indexes;-num_chunks++;-chunks[num_chunks].id=GRAPH_CHUNKID_BLOOMDATA;-chunks[num_chunks].size=sizeof(uint32_t)*3-+ctx->total_bloom_filter_data_size;-chunks[num_chunks].write_fn=write_graph_chunk_bloom_data;-num_chunks++;-}-if(ctx->num_commit_graphs_after>1){-chunks[num_chunks].id=GRAPH_CHUNKID_BASE;-chunks[num_chunks].size=hashsz*(ctx->num_commit_graphs_after-1);-chunks[num_chunks].write_fn=write_graph_chunk_base;-num_chunks++;-}--chunks[num_chunks].id=0;-chunks[num_chunks].size=0;+add_chunk(cf,GRAPH_CHUNKID_BLOOMINDEXES,+write_graph_chunk_bloom_indexes,+sizeof(uint32_t)*ctx->commits.nr);+add_chunk(cf,GRAPH_CHUNKID_BLOOMDATA,+write_graph_chunk_bloom_data,+sizeof(uint32_t)*3++ctx->total_bloom_filter_data_size);+}+if(ctx->num_commit_graphs_after>1)+add_chunk(cf,GRAPH_CHUNKID_BASE,+write_graph_chunk_base,+hashsz*(ctx->num_commit_graphs_after-1));hashwrite_be32(f,GRAPH_SIGNATURE);hashwrite_u8(f,GRAPH_VERSION);hashwrite_u8(f,oid_version());-hashwrite_u8(f,num_chunks);+hashwrite_u8(f,get_num_chunks(cf));hashwrite_u8(f,ctx->num_commit_graphs_after-1);-chunk_offset=8+(num_chunks+1)*GRAPH_CHUNKLOOKUP_WIDTH;-for(i=0;i<=num_chunks;i++){-uint32_tchunk_write[3];--chunk_write[0]=htonl(chunks[i].id);-chunk_write[1]=htonl(chunk_offset>>32);-chunk_write[2]=htonl(chunk_offset&0xffffffff);-hashwrite(f,chunk_write,12);--chunk_offset+=chunks[i].size;-}-if(ctx->report_progress){strbuf_addf(&progress_title,Q_("Writing out commit graph in %d pass",
@@ -1914,17 +1879,7 @@ static int write_commit_graph_file(struct write_commit_graph_context *ctx)num_chunks*ctx->commits.nr);}-for(i=0;i<num_chunks;i++){-uint64_tstart_offset=f->total+f->offset;--if(chunks[i].write_fn(f,ctx))-return-1;--if(f->total+f->offset!=start_offset+chunks[i].size)-BUG("expected to write %"PRId64" bytes to chunk %"PRIx32", but wrote %"PRId64" instead",-chunks[i].size,chunks[i].id,-f->total+f->offset-start_offset);-}+write_chunkfile(cf,ctx);stop_progress(&ctx->progress);strbuf_release(&progress_title);
@@ -1941,6 +1896,7 @@ static int write_commit_graph_file(struct write_commit_graph_context *ctx)close_commit_graph(ctx->r->objects);finalize_hashfile(f,file_hash.hash,CSUM_HASH_IN_STREAM|CSUM_FSYNC);+free_chunkfile(cf);if(ctx->split){FILE*chainf=fdopen_lock_file(&lk,"w");
From: Derrick Stolee via GitGitGadget <hidden> Date: 2021-01-26 16:04:56
From: Derrick Stolee <redacted>
Instead of parsing the table of contents directly, use the chunk-format
API methods read_table_of_contents() and pair_chunk(). In particular, we
can use the return value of pair_chunk() to generate an error when a
required chunk is missing.
Signed-off-by: Derrick Stolee <redacted>
---
midx.c | 103 ++++++++++++++++++++----------------
t/t5319-multi-pack-index.sh | 6 +--
2 files changed, 60 insertions(+), 49 deletions(-)
@@ -54,6 +54,51 @@ static char *get_midx_filename(const char *object_dir)returnxstrfmt("%s/pack/multi-pack-index",object_dir);}+staticintmidx_read_pack_names(constunsignedchar*chunk_start,+size_tchunk_size,void*data)+{+structmulti_pack_index*m=(structmulti_pack_index*)data;+m->chunk_pack_names=chunk_start;+return0;+}++staticintmidx_read_oid_fanout(constunsignedchar*chunk_start,+size_tchunk_size,void*data)+{+structmulti_pack_index*m=(structmulti_pack_index*)data;+m->chunk_oid_fanout=(uint32_t*)chunk_start;++if(chunk_size!=4*256){+error(_("multi-pack-index OID fanout is of the wrong size"));+return1;+}+return0;+}++staticintmidx_read_oid_lookup(constunsignedchar*chunk_start,+size_tchunk_size,void*data)+{+structmulti_pack_index*m=(structmulti_pack_index*)data;+m->chunk_oid_lookup=chunk_start;+return0;+}++staticintmidx_read_offsets(constunsignedchar*chunk_start,+size_tchunk_size,void*data)+{+structmulti_pack_index*m=(structmulti_pack_index*)data;+m->chunk_object_offsets=chunk_start;+return0;+}++staticintmidx_read_large_offsets(constunsignedchar*chunk_start,+size_tchunk_size,void*data)+{+structmulti_pack_index*m=(structmulti_pack_index*)data;+m->chunk_large_offsets=chunk_start;+return0;+}+structmulti_pack_index*load_multi_pack_index(constchar*object_dir,intlocal){structmulti_pack_index*m=NULL;
From: Derrick Stolee via GitGitGadget <hidden> Date: 2021-01-26 16:04:56
From: Derrick Stolee <redacted>
The chunk-based file format is now an API in the code, but we should
also take time to document it as a file format. Specifically, it matches
the CHUNK LOOKUP sections of the commit-graph and multi-pack-index
files, but there are some commonalities that should be grouped in this
document.
Signed-off-by: Derrick Stolee <redacted>
---
Documentation/technical/chunk-format.txt | 54 +++++++++++++++++++
.../technical/commit-graph-format.txt | 3 ++
Documentation/technical/pack-format.txt | 3 ++
3 files changed, 60 insertions(+)
create mode 100644 Documentation/technical/chunk-format.txt
@@ -0,0 +1,54 @@+Chunk-based file formats+========================++Some file formats in Git use a common concept of "chunks" to describe+sections of the file. This allows structured access to a large file by+scanning a small "table of contents" for the remaining data. This common+format is used by the `commit-graph` and `multi-pack-index` files. See+link:technical/pack-format.html[the `multi-pack-index` format] and+link:technical/commit-graph-format.html[the `commit-graph` format] for+how they use the chunks to describe structured data.++A chunk-based file format begins with some header information custom to+that format. That header should include enough information to identify+the file type, format version, and number of chunks in the file. From this+information, that file can determine the start of the chunk-based region.++The chunk-based region starts with a table of contents describing where+each chunk starts and ends. This consists of (C+1) rows of 12 bytes each,+where C is the number of chunks. Consider the following table:++ | Chunk ID (4 bytes) | Chunk Offset (8 bytes) |+ |--------------------|------------------------|+ | ID[0] | OFFSET[0] |+ | ... | ... |+ | ID[C] | OFFSET[C] |+ | 0x0000 | OFFSET[C+1] |++Each row consists of a 4-byte chunk identifier (ID) and an 8-byte offset.+Each integer is stored in network-byte order.++The chunk identifier `ID[i]` is a label for the data stored within this+fill from `OFFSET[i]` (inclusive) to `OFFSET[i+1]` (exclusive). Thus, the+size of the `i`th chunk is equal to the difference between `OFFSET[i+1]`+and `OFFSET[i]`. This requires that the chunk data appears contiguously+in the same order as the table of contents.++The final entry in the table of contents must be four zero bytes. This+confirms that the table of contents is ending and provides the offset for+the end of the chunk-based data.++Note: The chunk-based format expects that the file contains _at least_ a+trailing hash after `OFFSET[C+1]`.++Functions for working with chunk-based file formats are declared in+`chunk-format.h`. Using these methods provide extra checks that assist+developers when creating new file formats, including:++ 1. Writing and reading the table of contents.++ 2. Verifying that the data written in a chunk matches the expected size+ that was recorded in the table of contents.++ 3. Checking that a table of contents describes offsets properly within+ the file boundaries.
@@ -61,6 +61,9 @@ CHUNK LOOKUP: the length using the next chunk position if necessary.) Each chunk ID appears at most once.+ The CHUNK LOOKUP matches the table of contents from+ link:technical/chunk-format.html[the chunk-based file format].+ The remaining data in the body is described one chunk at a time, and these chunks may be given in any order. Chunks are required unless otherwise specified.
@@ -301,6 +301,9 @@ CHUNK LOOKUP: (Chunks are provided in file-order, so you can infer the length using the next chunk position if necessary.)+ The CHUNK LOOKUP matches the table of contents from+ link:technical/chunk-format.html[the chunk-based file format].+ The remaining data in the body is described one chunk at a time, and these chunks may be given in any order. Chunks are required unless otherwise specified.
From: Derrick Stolee via GitGitGadget <hidden> Date: 2021-01-26 16:05:28
From: Derrick Stolee <redacted>
The chunk-format API allows writing the table of contents and all chunks
using the anonymous 'struct chunkfile' type. We only need to convert our
local chunk logic to this API for the multi-pack-index writes to share
that logic with the commit-graph file writes.
Signed-off-by: Derrick Stolee <redacted>
---
midx.c | 104 +++++++++++----------------------------------------------
1 file changed, 19 insertions(+), 85 deletions(-)
@@ -799,18 +800,15 @@ static int write_midx_large_offsets(struct hashfile *f,staticintwrite_midx_internal(constchar*object_dir,structmulti_pack_index*m,structstring_list*packs_to_drop,unsignedflags){-unsignedcharcur_chunk,num_chunks=0;char*midx_name;uint32_ti;structhashfile*f=NULL;structlock_filelk;structwrite_midx_contextctx={0};-uint64_theader_size=0;-uint32_tchunk_ids[MIDX_MAX_CHUNKS+1];-uint64_tchunk_offsets[MIDX_MAX_CHUNKS+1];intpack_name_concat_len=0;intdropped_packs=0;intresult=0;+structchunkfile*cf;midx_name=get_midx_filename(object_dir);if(safe_create_leading_directories(midx_name))
@@ -923,98 +921,34 @@ static int write_midx_internal(const char *object_dir, struct multi_pack_index *if(ctx.m)close_midx(ctx.m);-cur_chunk=0;-num_chunks=ctx.large_offsets_needed?5:4;-if(ctx.nr-dropped_packs==0){error(_("no pack files to index."));result=1;gotocleanup;}-header_size=write_midx_header(f,num_chunks,ctx.nr-dropped_packs);--chunk_ids[cur_chunk]=MIDX_CHUNKID_PACKNAMES;-chunk_offsets[cur_chunk]=header_size+(num_chunks+1)*MIDX_CHUNKLOOKUP_WIDTH;--cur_chunk++;-chunk_ids[cur_chunk]=MIDX_CHUNKID_OIDFANOUT;-chunk_offsets[cur_chunk]=chunk_offsets[cur_chunk-1]+pack_name_concat_len;--cur_chunk++;-chunk_ids[cur_chunk]=MIDX_CHUNKID_OIDLOOKUP;-chunk_offsets[cur_chunk]=chunk_offsets[cur_chunk-1]+MIDX_CHUNK_FANOUT_SIZE;--cur_chunk++;-chunk_ids[cur_chunk]=MIDX_CHUNKID_OBJECTOFFSETS;-chunk_offsets[cur_chunk]=chunk_offsets[cur_chunk-1]+ctx.entries_nr*the_hash_algo->rawsz;--cur_chunk++;-chunk_offsets[cur_chunk]=chunk_offsets[cur_chunk-1]+ctx.entries_nr*MIDX_CHUNK_OFFSET_WIDTH;-if(ctx.large_offsets_needed){-chunk_ids[cur_chunk]=MIDX_CHUNKID_LARGEOFFSETS;--cur_chunk++;-chunk_offsets[cur_chunk]=chunk_offsets[cur_chunk-1]+-ctx.num_large_offsets*MIDX_CHUNK_LARGE_OFFSET_WIDTH;-}--chunk_ids[cur_chunk]=0;--for(i=0;i<=num_chunks;i++){-if(i&&chunk_offsets[i]<chunk_offsets[i-1])-BUG("incorrect chunk offsets: %"PRIu64" before %"PRIu64,-chunk_offsets[i-1],-chunk_offsets[i]);--if(chunk_offsets[i]%MIDX_CHUNK_ALIGNMENT)-BUG("chunk offset %"PRIu64" is not properly aligned",-chunk_offsets[i]);--hashwrite_be32(f,chunk_ids[i]);-hashwrite_be64(f,chunk_offsets[i]);-}--for(i=0;i<num_chunks;i++){-if(f->total+f->offset!=chunk_offsets[i])-BUG("incorrect chunk offset (%"PRIu64" != %"PRIu64") for chunk id %"PRIx32,-chunk_offsets[i],-f->total+f->offset,-chunk_ids[i]);+cf=init_chunkfile(f);-switch(chunk_ids[i]){-caseMIDX_CHUNKID_PACKNAMES:-write_midx_pack_names(f,&ctx);-break;+add_chunk(cf,MIDX_CHUNKID_PACKNAMES,+write_midx_pack_names,pack_name_concat_len);+add_chunk(cf,MIDX_CHUNKID_OIDFANOUT,+write_midx_oid_fanout,MIDX_CHUNK_FANOUT_SIZE);+add_chunk(cf,MIDX_CHUNKID_OIDLOOKUP,+write_midx_oid_lookup,ctx.entries_nr*the_hash_algo->rawsz);+add_chunk(cf,MIDX_CHUNKID_OBJECTOFFSETS,+write_midx_object_offsets,+ctx.entries_nr*MIDX_CHUNK_OFFSET_WIDTH);-caseMIDX_CHUNKID_OIDFANOUT:-write_midx_oid_fanout(f,&ctx);-break;--caseMIDX_CHUNKID_OIDLOOKUP:-write_midx_oid_lookup(f,&ctx);-break;--caseMIDX_CHUNKID_OBJECTOFFSETS:-write_midx_object_offsets(f,&ctx);-break;--caseMIDX_CHUNKID_LARGEOFFSETS:-write_midx_large_offsets(f,&ctx);-break;--default:-BUG("trying to write unknown chunk id %"PRIx32,-chunk_ids[i]);-}-}+if(ctx.large_offsets_needed)+add_chunk(cf,MIDX_CHUNKID_LARGEOFFSETS,+write_midx_large_offsets,+ctx.num_large_offsets*MIDX_CHUNK_LARGE_OFFSET_WIDTH);-if(f->total+f->offset!=chunk_offsets[num_chunks])-BUG("incorrect final offset %"PRIu64" != %"PRIu64,-f->total+f->offset,-chunk_offsets[num_chunks]);+write_midx_header(f,get_num_chunks(cf),ctx.nr-dropped_packs);+write_chunkfile(cf,&ctx);finalize_hashfile(f,NULL,CSUM_FSYNC|CSUM_HASH_IN_STREAM);+free_chunkfile(cf);commit_lock_file(&lk);cleanup:
From: Derrick Stolee via GitGitGadget <hidden> Date: 2021-01-26 16:05:38
From: Derrick Stolee <redacted>
Before refactoring into the chunk-format API, the commit-graph parsing
logic included checks for duplicate chunks. It is unlikely that we would
desire a chunk-based file format that allows duplicate chunk IDs in the
table of contents, so add duplicate checks into
read_table_of_contents().
Signed-off-by: Derrick Stolee <redacted>
---
chunk-format.c | 10 ++++++++++
1 file changed, 10 insertions(+)
From: Derrick Stolee via GitGitGadget <hidden> Date: 2021-01-26 16:06:30
From: Derrick Stolee <redacted>
When calculating the sizes of certain chunks, we should use 64-bit
multiplication always. This allows us to properly predict the chunk
sizes without risk of overflow.
Signed-off-by: Derrick Stolee <redacted>
---
midx.c | 4 ++--
1 file changed, 2 insertions(+), 2 deletions(-)
From: Derrick Stolee via GitGitGadget <hidden> Date: 2021-01-26 16:06:30
From: Derrick Stolee <redacted>
In an effort to align write_midx_internal() with the chunk-format API,
continue to group necessary data into "struct write_midx_context". This
change collects the "uint32_t *pack_perm" and large_offsets_needed bit
into the context.
Update write_midx_object_offsets() to match chunk_write_fn.
Signed-off-by: Derrick Stolee <redacted>
---
midx.c | 40 +++++++++++++++++++++-------------------
1 file changed, 21 insertions(+), 19 deletions(-)
@@ -736,27 +739,27 @@ static size_t write_midx_oid_lookup(struct hashfile *f,returnwritten;}-staticsize_twrite_midx_object_offsets(structhashfile*f,intlarge_offset_needed,-uint32_t*perm,-structpack_midx_entry*objects,uint32_tnr_objects)+staticsize_twrite_midx_object_offsets(structhashfile*f,+void*data){-structpack_midx_entry*list=objects;+structwrite_midx_context*ctx=(structwrite_midx_context*)data;+structpack_midx_entry*list=ctx->entries;uint32_ti,nr_large_offset=0;size_twritten=0;-for(i=0;i<nr_objects;i++){+for(i=0;i<ctx->entries_nr;i++){structpack_midx_entry*obj=list++;-if(perm[obj->pack_int_id]==PACK_EXPIRED)+if(ctx->pack_perm[obj->pack_int_id]==PACK_EXPIRED)BUG("object %s is in an expired pack with int-id %d",oid_to_hex(&obj->oid),obj->pack_int_id);-hashwrite_be32(f,perm[obj->pack_int_id]);+hashwrite_be32(f,ctx->pack_perm[obj->pack_int_id]);-if(large_offset_needed&&obj->offset>>31)+if(ctx->large_offsets_needed&&obj->offset>>31)hashwrite_be32(f,MIDX_LARGE_OFFSET_NEEDED|nr_large_offset++);-elseif(!large_offset_needed&&obj->offset>>32)+elseif(!ctx->large_offsets_needed&&obj->offset>>32)BUG("object %s requires a large offset (%"PRIx64") but the MIDX is not writing large offsets!",oid_to_hex(&obj->oid),obj->offset);
From: Derrick Stolee via GitGitGadget <hidden> Date: 2021-01-26 16:06:30
From: Derrick Stolee <redacted>
Most expensive operations in write_midx_internal() use the context
struct's progress member, and these indicate the process of the
expensive operations within the chunk writing methods. However, there is
a competing progress struct that counts the progress over all chunks.
This is not very helpful compared to the others, so drop it.
This also reduces our barriers to combining the chunk writing code with
chunk-format.c.
Signed-off-by: Derrick Stolee <redacted>
---
midx.c | 7 -------
1 file changed, 7 deletions(-)
From: Derrick Stolee via GitGitGadget <hidden> Date: 2021-01-26 16:06:31
From: Derrick Stolee <redacted>
Historically, the chunk-writing methods in midx.c have returned the
amount of data written so the writer method could compare this with the
table of contents. This presents with some interesting issues:
1. If a chunk writing method has a bug that miscalculates the written
bytes, then we can satisfy the table of contents without actually
writing the right amount of data to the hashfile. The commit-graph
writing code checks the hashfile struct directly for a more robust
verification.
2. There is no way for a chunk writing method to gracefully fail.
Returning an int presents an opportunity to fail without a die().
3. The current pattern doesn't match chunk_write_fn type exactly, so we
cannot share code with commit-graph.c
For these reasons, convert the midx chunk writer methods to return an
'int'. Since none of them fail at the moment, they all return 0.
Signed-off-by: Derrick Stolee <redacted>
---
midx.c | 63 +++++++++++++++++++++++++---------------------------------
1 file changed, 27 insertions(+), 36 deletions(-)
From: Derrick Stolee via GitGitGadget <hidden> Date: 2021-01-26 16:07:03
From: Derrick Stolee <redacted>
In an effort to align write_midx_internal() with the chunk-format API,
continue to group necessary data into "struct write_midx_context". This
change collects the "uint32_t num_large_offsets" into the context. With
this new data, write_midx_large_offsets() now matches the
chunk_write_fn type.
Signed-off-by: Derrick Stolee <redacted>
---
midx.c | 17 ++++++++++-------
1 file changed, 10 insertions(+), 7 deletions(-)
From: Derrick Stolee via GitGitGadget <hidden> Date: 2021-01-26 16:07:03
From: Derrick Stolee <redacted>
Instead of parsing the table of contents directly, use the chunk-format
API methods read_table_of_contents() and pair_chunk(). While the current
implementation loses the duplicate-chunk detection, that will be added
in a future change.
Signed-off-by: Derrick Stolee <redacted>
---
commit-graph.c | 209 ++++++++++++++++++++--------------------
t/t5318-commit-graph.sh | 2 +-
2 files changed, 108 insertions(+), 103 deletions(-)
From: Derrick Stolee via GitGitGadget <hidden> Date: 2021-01-26 16:09:46
From: Derrick Stolee <redacted>
Add the capability to read the table of contents, then pair the chunks
with necessary logic using read_chunk_fn pointers. Callers will be added
in future changes, but the typical outline will be:
1. initialize a 'struct chunkfile' with init_chunkfile(NULL).
2. call read_table_of_contents().
3. for each chunk to parse, call pair_chunk() with appropriate pointers.
4. call free_chunkfile() to clear the 'struct chunkfile' data.
We are re-using the anonymous 'struct chunkfile' data, as it is internal
to the chunk-format API. This gives it essentially two modes: write and
read. If the same struct instance was used for both reads and writes,
then there would be failures.
Signed-off-by: Derrick Stolee <redacted>
---
chunk-format.c | 64 ++++++++++++++++++++++++++++++++++++++++++++++++++
chunk-format.h | 21 +++++++++++++++++
2 files changed, 85 insertions(+)
@@ -89,3 +91,65 @@ int write_chunkfile(struct chunkfile *cf, void *data)return0;}++intread_table_of_contents(structchunkfile*cf,+constunsignedchar*mfile,+size_tmfile_size,+uint64_ttoc_offset,+inttoc_length)+{+uint32_tchunk_id;+constunsignedchar*table_of_contents=mfile+toc_offset;++ALLOC_GROW(cf->chunks,toc_length,cf->chunks_alloc);++while(toc_length--){+uint64_tchunk_offset,next_chunk_offset;++chunk_id=get_be32(table_of_contents);+chunk_offset=get_be64(table_of_contents+4);++if(!chunk_id){+error(_("terminating chunk id appears earlier than expected"));+return1;+}++table_of_contents+=CHUNK_LOOKUP_WIDTH;+next_chunk_offset=get_be64(table_of_contents+4);++if(next_chunk_offset<chunk_offset||+next_chunk_offset>mfile_size-the_hash_algo->rawsz){+error(_("improper chunk offset(s) %"PRIx64" and %"PRIx64""),+chunk_offset,next_chunk_offset);+return-1;+}++cf->chunks[cf->chunks_nr].id=chunk_id;+cf->chunks[cf->chunks_nr].start=mfile+chunk_offset;+cf->chunks[cf->chunks_nr].size=next_chunk_offset-chunk_offset;+cf->chunks_nr++;+}++chunk_id=get_be32(table_of_contents);+if(chunk_id){+error(_("final chunk has non-zero id %"PRIx32""),chunk_id);+return-1;+}++return0;+}++intpair_chunk(structchunkfile*cf,+uint32_tchunk_id,+chunk_read_fnfn,+void*data)+{+inti;++for(i=0;i<cf->chunks_nr;i++){+if(cf->chunks[i].id==chunk_id)+returnfn(cf->chunks[i].start,cf->chunks[i].size,data);+}++returnCHUNK_NOT_FOUND;+}
Why bother with the cast on the last line here? In C,
conversion from `void *` to `struct whatever *` is fine.
(the change itself looks fine, btw)
Agreed. It's not a correctness issue, but I find these unnecessary casts
to detract from readability. If you do end up rerolling this series,
I'd rather see
struct write_commit_graph_context *ctx = data;
...but I don't think that this (non-)issue alone is worth a reroll.
Thanks,
Taylor
From: Taylor Blau <hidden> Date: 2021-01-27 03:59:17
On Tue, Jan 26, 2021 at 04:01:13PM +0000, Derrick Stolee via GitGitGadget wrote:
This change only renames "struct pack_info" to "struct
write_midx_context" and the names of instances from "packs" to "ctx". In
future changes, we will expand the data inside "struct
write_midx_context" and align our chunk-writing method with the
chunk-format API.
Thanks for saying that; that makes clear what is (and isn't) going on
here.
Same comments as earlier about the unnecessary cast on the right-hand
side of this (and the below) assignment.
Otherwise this patch looks obviously fine to me.
Thanks,
Taylor
It may be clearer to fold both of these into an anonymous union along
with an enum to indicate which mode we're in. But, I could also buy that
that is more error prone, so perhaps just a comment along the lines of
"exactly one of these is NULL" would suffice, too.
Assuming that mfile and mfile_size are a pointer to a memory mapped
region and its size? If so, a nit is that I'd expect "data" and "size"
instead of "mfile".
I think that it's probably going too far to have the chunkfile API
handle mapping its own memory, so in that way I don't think it's wrong
for the callers to be handling that.
OTOH, it does seem a little weird to temporarily hand off ownership like
this. I don't think I have a better suggestion, though.
The implementation of this function looks good to me.
quoted hunk
+int pair_chunk(struct chunkfile *cf,
+ uint32_t chunk_id,
+ chunk_read_fn fn,
+ void *data)
+{
+ int i;
+
+ for (i = 0; i < cf->chunks_nr; i++) {
+ if (cf->chunks[i].id == chunk_id)
+ return fn(cf->chunks[i].start, cf->chunks[i].size, data);
+ }
+
+ return CHUNK_NOT_FOUND;
+}
From reading the implementation, I take it that this function calls fn
with the location and size of the requested chunk, along with the user
supplied data.
I'm not sure that "pair" gives me that same sense. Maybe "read" or
"lookup" would be better?
Dunno.
Thanks,
Taylor
From: Taylor Blau <hidden> Date: 2021-01-27 04:16:43
On Tue, Jan 26, 2021 at 04:01:09PM +0000, Derrick Stolee via GitGitGadget wrote:
This version also changes the approach to use a more dynamic interaction
with a struct chunkfile pointer. This idea is credited to Taylor Blau [2],
but I started again from scratch. I also go further to make struct chunkfile
anonymous to API consumers. It is defined only in chunk-format.c, which
should hopefully deter future users from interacting with that data
directly.
[2] https://lore.kernel.org/git/X8%2FI%2FRzXZksio+ri@nand.local/
Great; I am very happy that you found my patch to be useful. I'm glad
that you decided to start from scratch, too, since as I recall there
were some unresolved test issues that I punted on in case you decided to
abandon the topic altogether.
This combined API is beneficial to reduce duplicated logic. Or rather, to
ensure that similar file formats have similar protections against bad data.
The multi-pack-index code did not have as many guards as the commit-graph
code did, but now they both share a common base that checks for things like
duplicate chunks or offsets outside the size of the file.
Definitely good.
Here are some stats for the end-to-end change:
* 638 insertions(+), 456 deletions(-).
* commit-graph.c: 171 insertions(+), 192 deletions(-)
* midx.c: 196 insertions(+), 260 deletions(-)
While there is an overall increase to the code size, the consumers do get a
bit smaller. Boilerplate things like abstracting method to match
chunk_write_fn and chunk_read_fn make up a lot of these insertions. The
"interesting" code gets a lot smaller and cleaner.
Like I said in [1], I don't think a net +182 line diff is reason alone
not to pursue this topic. I don't think that an chunked index v3 will
come as part of my work on the on-disk revindex format, but I do think
that it's something brian may be interested in. So, I'm feeling rather
certain that we'll eventually have new callers, at which point this will
reduce duplication overall.
[1]: https://lore.kernel.org/git/X8%2FK1dUgUmwp8ZOv@nand.local/
Thanks,
Taylor
From: Taylor Blau <hidden> Date: 2021-01-27 04:16:48
On Tue, Jan 26, 2021 at 04:01:11PM +0000, Derrick Stolee via GitGitGadget wrote:
+/*
+ * When writing a chunk-based file format, collect the chunks in
+ * an array of chunk_info structs. The size stores the _expected_
+ * amount of data that will be written by write_fn.
+ */
+struct chunk_info {
+ uint32_t id;
+ uint64_t size;
Hmm. Would we not want an off_t to indicate the size here?
I wondered briefly if we even needed a size field at all, since calling
write_fn would tell us the number of bytes written. But I suppose you
want to know ahead of time so that you can write the file in one pass
(beginning with the table of contents, which certainly needs to know the
size).
+ /* Trailing entry marks the end of the chunks */
+ hashwrite_be32(cf->f, 0);
+ hashwrite_be64(cf->f, cur_offset);
+
+ for (i = 0; i < cf->chunks_nr; i++) {
+ uint64_t start_offset = cf->f->total + cf->f->offset;
+ int result = cf->chunks[i].write_fn(cf->f, data);
+
+ if (result)
+ return result;
+
+ if (cf->f->total + cf->f->offset != start_offset + cf->chunks[i].size)
I don't think this is a practical concern, but a malicious caller could
overflow this by passing a bogus "size" parameter. Maybe:
uint64_t end_offset = ...;
if (end_offset - start_offset != cf->chunks[i].size)
BUG(...)
?
Why bother with the cast on the last line here? In C,
conversion from `void *` to `struct whatever *` is fine.
(the change itself looks fine, btw)
Chris
From: Taylor Blau <hidden> Date: 2021-01-27 04:17:50
On Tue, Jan 26, 2021 at 04:01:12PM +0000, Derrick Stolee via GitGitGadget wrote:
From: Derrick Stolee <redacted>
The commit-graph write logic is ready to make use of the chunk-format
write API. Each chunk write method is already in the correct prototype.
We only need to use the 'struct chunkfile' pointer and the correct API
calls.
Signed-off-by: Derrick Stolee <redacted>
Nicely done. The majority of this patch was remarkably easy to read,
which I attribute to you doing the necessary prep work to make the
callbacks usable by the new API. Thank you.
Since chunkfiles are so tightly coupled to hashfiles (i.e., you can only
"construct" a chunkfile given a 'struct hashfile*'), I wonder whether
this should be:
finalize_chunkfile(cf, ...)
instead. It seems kind of weird to give up ownership of 'f' down to the
chunkfile API only to reach down into it again.
I could even buy that you'd always want to finalize and free a chunkfile
at the same time, and so perhaps the calls could be combined, but that
may be a step too far.
Thanks,
Taylor
From: Taylor Blau <hidden> Date: 2021-01-27 06:50:50
On Tue, Jan 26, 2021 at 04:01:23PM +0000, Derrick Stolee via GitGitGadget wrote:
quoted hunk
From: Derrick Stolee <redacted>
Instead of parsing the table of contents directly, use the chunk-format
API methods read_table_of_contents() and pair_chunk(). In particular, we
can use the return value of pair_chunk() to generate an error when a
required chunk is missing.
Signed-off-by: Derrick Stolee <redacted>
---
midx.c | 103 ++++++++++++++++++++----------------
t/t5319-multi-pack-index.sh | 6 +--
2 files changed, 60 insertions(+), 49 deletions(-)
There are a lot of these callbacks that just assign some 'void **' to
point at chunk_start.
Maybe a good use of the "pair_chunk" name would be something like:
int pair_chunk(struct chunkfile *cf, uint32_t id, const unsigned char **p);
which does the same as what you wrote here. So instead of what you
wrote, you could instead:
pair_chunk(cf, MIDX_CHUNKID_PACKNAMES, &m->chunk_pack_names);
This would be in addition to the richer callback-style function which
allows the caller greater flexibility (e.g., for the Bloom filter
related readers in the commit-graph code).
Thanks,
Taylor
On Tue, Jan 26, 2021 at 04:01:11PM +0000, Derrick Stolee via GitGitGadget wrote:
quoted
+/*
+ * When writing a chunk-based file format, collect the chunks in
+ * an array of chunk_info structs. The size stores the _expected_
+ * amount of data that will be written by write_fn.
+ */
+struct chunk_info {
+ uint32_t id;
+ uint64_t size;
Hmm. Would we not want an off_t to indicate the size here?
I wondered briefly if we even needed a size field at all, since calling
write_fn would tell us the number of bytes written. But I suppose you
want to know ahead of time so that you can write the file in one pass
(beginning with the table of contents, which certainly needs to know the
size).
Is off_t 64-bits on a 32-bit machine? This is intentionally typed
to be "64 bits no matter what" because it correlates with the file
format's size for the chunk offsets.
quoted
+ if (cf->f->total + cf->f->offset != start_offset + cf->chunks[i].size)
I don't think this is a practical concern, but a malicious caller could
overflow this by passing a bogus "size" parameter. Maybe:
uint64_t end_offset = ...;
if (end_offset - start_offset != cf->chunks[i].size)
BUG(...)
On Tue, Jan 26, 2021 at 04:01:23PM +0000, Derrick Stolee via GitGitGadget wrote:
quoted
From: Derrick Stolee <redacted>
Instead of parsing the table of contents directly, use the chunk-format
API methods read_table_of_contents() and pair_chunk(). In particular, we
can use the return value of pair_chunk() to generate an error when a
required chunk is missing.
Signed-off-by: Derrick Stolee <redacted>
---
midx.c | 103 ++++++++++++++++++++----------------
t/t5319-multi-pack-index.sh | 6 +--
2 files changed, 60 insertions(+), 49 deletions(-)
There are a lot of these callbacks that just assign some 'void **' to
point at chunk_start.
Maybe a good use of the "pair_chunk" name would be something like:
int pair_chunk(struct chunkfile *cf, uint32_t id, const unsigned char **p);
which does the same as what you wrote here. So instead of what you
wrote, you could instead:
pair_chunk(cf, MIDX_CHUNKID_PACKNAMES, &m->chunk_pack_names);
This would be in addition to the richer callback-style function which
allows the caller greater flexibility (e.g., for the Bloom filter
related readers in the commit-graph code).
You're right that _most_ callers just want to assign a pointer,
so this mechanism would be better. I'll make a different function,
read_chunk() perhaps, that relies on a callback for advanced users.
Thanks,
-Stolee
From: Derrick Stolee via GitGitGadget <hidden> Date: 2021-01-27 15:07:23
From: Derrick Stolee <redacted>
In an effort to align the write_midx_internal() to use the chunk-format
API, start converting chunk writing methods to match chunk_write_fn. The
first case is to convert write_midx_pack_names() to take "void *data".
We already have the necessary data in "struct write_midx_context", so
this conversion is rather mechanical.
Signed-off-by: Derrick Stolee <redacted>
---
midx.c | 21 ++++++++++-----------
1 file changed, 10 insertions(+), 11 deletions(-)
From: Derrick Stolee via GitGitGadget <hidden> Date: 2021-01-27 15:07:24
From: Derrick Stolee <redacted>
The commit-graph write logic is ready to make use of the chunk-format
write API. Each chunk write method is already in the correct prototype.
We only need to use the 'struct chunkfile' pointer and the correct API
calls.
Signed-off-by: Derrick Stolee <redacted>
---
commit-graph.c | 118 ++++++++++++++++---------------------------------
1 file changed, 37 insertions(+), 81 deletions(-)
@@ -1758,27 +1759,17 @@ static int write_graph_chunk_base(struct hashfile *f,return0;}-typedefint(*chunk_write_fn)(structhashfile*f,-void*data);--structchunk_info{-uint32_tid;-uint64_tsize;-chunk_write_fnwrite_fn;-};-staticintwrite_commit_graph_file(structwrite_commit_graph_context*ctx){uint32_ti;intfd;structhashfile*f;structlock_filelk=LOCK_INIT;-structchunk_infochunks[MAX_NUM_CHUNKS+1];constunsignedhashsz=the_hash_algo->rawsz;structstrbufprogress_title=STRBUF_INIT;intnum_chunks=3;-uint64_tchunk_offset;structobject_idfile_hash;+structchunkfile*cf;if(ctx->split){structstrbuftmp_file=STRBUF_INIT;
@@ -1824,76 +1815,50 @@ static int write_commit_graph_file(struct write_commit_graph_context *ctx)f=hashfd(lk.tempfile->fd,lk.tempfile->filename.buf);}-chunks[0].id=GRAPH_CHUNKID_OIDFANOUT;-chunks[0].size=GRAPH_FANOUT_SIZE;-chunks[0].write_fn=write_graph_chunk_fanout;-chunks[1].id=GRAPH_CHUNKID_OIDLOOKUP;-chunks[1].size=hashsz*ctx->commits.nr;-chunks[1].write_fn=write_graph_chunk_oids;-chunks[2].id=GRAPH_CHUNKID_DATA;-chunks[2].size=(hashsz+16)*ctx->commits.nr;-chunks[2].write_fn=write_graph_chunk_data;+cf=init_chunkfile(f);++add_chunk(cf,GRAPH_CHUNKID_OIDFANOUT,+write_graph_chunk_fanout,GRAPH_FANOUT_SIZE);+add_chunk(cf,GRAPH_CHUNKID_OIDLOOKUP,+write_graph_chunk_oids,hashsz*ctx->commits.nr);+add_chunk(cf,GRAPH_CHUNKID_DATA,+write_graph_chunk_data,(hashsz+16)*ctx->commits.nr);if(git_env_bool(GIT_TEST_COMMIT_GRAPH_NO_GDAT,0))ctx->write_generation_data=0;-if(ctx->write_generation_data){-chunks[num_chunks].id=GRAPH_CHUNKID_GENERATION_DATA;-chunks[num_chunks].size=sizeof(uint32_t)*ctx->commits.nr;-chunks[num_chunks].write_fn=write_graph_chunk_generation_data;-num_chunks++;-}-if(ctx->num_generation_data_overflows){-chunks[num_chunks].id=GRAPH_CHUNKID_GENERATION_DATA_OVERFLOW;-chunks[num_chunks].size=sizeof(timestamp_t)*ctx->num_generation_data_overflows;-chunks[num_chunks].write_fn=write_graph_chunk_generation_data_overflow;-num_chunks++;-}-if(ctx->num_extra_edges){-chunks[num_chunks].id=GRAPH_CHUNKID_EXTRAEDGES;-chunks[num_chunks].size=4*ctx->num_extra_edges;-chunks[num_chunks].write_fn=write_graph_chunk_extra_edges;-num_chunks++;-}+if(ctx->write_generation_data)+add_chunk(cf,GRAPH_CHUNKID_GENERATION_DATA,+write_graph_chunk_generation_data,+sizeof(uint32_t)*ctx->commits.nr);+if(ctx->num_generation_data_overflows)+add_chunk(cf,GRAPH_CHUNKID_GENERATION_DATA_OVERFLOW,+write_graph_chunk_generation_data_overflow,+sizeof(timestamp_t)*ctx->num_generation_data_overflows);+if(ctx->num_extra_edges)+add_chunk(cf,GRAPH_CHUNKID_EXTRAEDGES,+write_graph_chunk_extra_edges,+4*ctx->num_extra_edges);if(ctx->changed_paths){-chunks[num_chunks].id=GRAPH_CHUNKID_BLOOMINDEXES;-chunks[num_chunks].size=sizeof(uint32_t)*ctx->commits.nr;-chunks[num_chunks].write_fn=write_graph_chunk_bloom_indexes;-num_chunks++;-chunks[num_chunks].id=GRAPH_CHUNKID_BLOOMDATA;-chunks[num_chunks].size=sizeof(uint32_t)*3-+ctx->total_bloom_filter_data_size;-chunks[num_chunks].write_fn=write_graph_chunk_bloom_data;-num_chunks++;-}-if(ctx->num_commit_graphs_after>1){-chunks[num_chunks].id=GRAPH_CHUNKID_BASE;-chunks[num_chunks].size=hashsz*(ctx->num_commit_graphs_after-1);-chunks[num_chunks].write_fn=write_graph_chunk_base;-num_chunks++;-}--chunks[num_chunks].id=0;-chunks[num_chunks].size=0;+add_chunk(cf,GRAPH_CHUNKID_BLOOMINDEXES,+write_graph_chunk_bloom_indexes,+sizeof(uint32_t)*ctx->commits.nr);+add_chunk(cf,GRAPH_CHUNKID_BLOOMDATA,+write_graph_chunk_bloom_data,+sizeof(uint32_t)*3++ctx->total_bloom_filter_data_size);+}+if(ctx->num_commit_graphs_after>1)+add_chunk(cf,GRAPH_CHUNKID_BASE,+write_graph_chunk_base,+hashsz*(ctx->num_commit_graphs_after-1));hashwrite_be32(f,GRAPH_SIGNATURE);hashwrite_u8(f,GRAPH_VERSION);hashwrite_u8(f,oid_version());-hashwrite_u8(f,num_chunks);+hashwrite_u8(f,get_num_chunks(cf));hashwrite_u8(f,ctx->num_commit_graphs_after-1);-chunk_offset=8+(num_chunks+1)*GRAPH_CHUNKLOOKUP_WIDTH;-for(i=0;i<=num_chunks;i++){-uint32_tchunk_write[3];--chunk_write[0]=htonl(chunks[i].id);-chunk_write[1]=htonl(chunk_offset>>32);-chunk_write[2]=htonl(chunk_offset&0xffffffff);-hashwrite(f,chunk_write,12);--chunk_offset+=chunks[i].size;-}-if(ctx->report_progress){strbuf_addf(&progress_title,Q_("Writing out commit graph in %d pass",
@@ -1905,17 +1870,7 @@ static int write_commit_graph_file(struct write_commit_graph_context *ctx)num_chunks*ctx->commits.nr);}-for(i=0;i<num_chunks;i++){-uint64_tstart_offset=f->total+f->offset;--if(chunks[i].write_fn(f,ctx))-return-1;--if(f->total+f->offset!=start_offset+chunks[i].size)-BUG("expected to write %"PRId64" bytes to chunk %"PRIx32", but wrote %"PRId64" instead",-chunks[i].size,chunks[i].id,-f->total+f->offset-start_offset);-}+write_chunkfile(cf,ctx);stop_progress(&ctx->progress);strbuf_release(&progress_title);
@@ -1932,6 +1887,7 @@ static int write_commit_graph_file(struct write_commit_graph_context *ctx)close_commit_graph(ctx->r->objects);finalize_hashfile(f,file_hash.hash,CSUM_HASH_IN_STREAM|CSUM_FSYNC);+free_chunkfile(cf);if(ctx->split){FILE*chainf=fdopen_lock_file(&lk,"w");
From: Derrick Stolee via GitGitGadget <hidden> Date: 2021-01-27 15:07:44
From: Derrick Stolee <redacted>
In an effort to align write_midx_internal() with the chunk-format API,
continue to group necessary data into "struct write_midx_context". This
change collects the "uint32_t *pack_perm" and large_offsets_needed bit
into the context.
Update write_midx_object_offsets() to match chunk_write_fn.
Signed-off-by: Derrick Stolee <redacted>
---
midx.c | 40 +++++++++++++++++++++-------------------
1 file changed, 21 insertions(+), 19 deletions(-)
@@ -736,27 +739,27 @@ static size_t write_midx_oid_lookup(struct hashfile *f,returnwritten;}-staticsize_twrite_midx_object_offsets(structhashfile*f,intlarge_offset_needed,-uint32_t*perm,-structpack_midx_entry*objects,uint32_tnr_objects)+staticsize_twrite_midx_object_offsets(structhashfile*f,+void*data){-structpack_midx_entry*list=objects;+structwrite_midx_context*ctx=data;+structpack_midx_entry*list=ctx->entries;uint32_ti,nr_large_offset=0;size_twritten=0;-for(i=0;i<nr_objects;i++){+for(i=0;i<ctx->entries_nr;i++){structpack_midx_entry*obj=list++;-if(perm[obj->pack_int_id]==PACK_EXPIRED)+if(ctx->pack_perm[obj->pack_int_id]==PACK_EXPIRED)BUG("object %s is in an expired pack with int-id %d",oid_to_hex(&obj->oid),obj->pack_int_id);-hashwrite_be32(f,perm[obj->pack_int_id]);+hashwrite_be32(f,ctx->pack_perm[obj->pack_int_id]);-if(large_offset_needed&&obj->offset>>31)+if(ctx->large_offsets_needed&&obj->offset>>31)hashwrite_be32(f,MIDX_LARGE_OFFSET_NEEDED|nr_large_offset++);-elseif(!large_offset_needed&&obj->offset>>32)+elseif(!ctx->large_offsets_needed&&obj->offset>>32)BUG("object %s requires a large offset (%"PRIx64") but the MIDX is not writing large offsets!",oid_to_hex(&obj->oid),obj->offset);
From: Derrick Stolee via GitGitGadget <hidden> Date: 2021-01-27 15:08:11
From: Derrick Stolee <redacted>
In anticipation of combining the logic from the commit-graph and
multi-pack-index file formats, create a new chunk-format API. Use a
'struct chunkfile' pointer to keep track of data that has been
registered for writes. This struct is anonymous outside of
chunk-format.c to ensure no user attempts to interfere with the data.
The next change will use this API in commit-graph.c, but the general
approach is:
1. initialize the chunkfile with init_chunkfile(f).
2. add chunks in the intended writing order with add_chunk().
3. write any header information to the hashfile f.
4. write the chunkfile data using write_chunkfile().
5. free the chunkfile struct using free_chunkfile().
Helped-by: Taylor Blau [off-list ref]
Signed-off-by: Derrick Stolee <redacted>
---
Makefile | 1 +
chunk-format.c | 91 ++++++++++++++++++++++++++++++++++++++++++++++++++
chunk-format.h | 20 +++++++++++
3 files changed, 112 insertions(+)
create mode 100644 chunk-format.c
create mode 100644 chunk-format.h
@@ -0,0 +1,91 @@+#include"cache.h"+#include"chunk-format.h"+#include"csum-file.h"+#define CHUNK_LOOKUP_WIDTH 12++/*+*Whenwritingachunk-basedfileformat,collectthechunksin+*anarrayofchunk_infostructs.Thesizestoresthe_expected_+*amountofdatathatwillbewrittenbywrite_fn.+*/+structchunk_info{+uint32_tid;+uint64_tsize;+chunk_write_fnwrite_fn;+};++structchunkfile{+structhashfile*f;++structchunk_info*chunks;+size_tchunks_nr;+size_tchunks_alloc;+};++structchunkfile*init_chunkfile(structhashfile*f)+{+structchunkfile*cf=xcalloc(1,sizeof(*cf));+cf->f=f;+returncf;+}++voidfree_chunkfile(structchunkfile*cf)+{+if(!cf)+return;+free(cf->chunks);+free(cf);+}++intget_num_chunks(structchunkfile*cf)+{+returncf->chunks_nr;+}++voidadd_chunk(structchunkfile*cf,+uint64_tid,+chunk_write_fnfn,+size_tsize)+{+ALLOC_GROW(cf->chunks,cf->chunks_nr+1,cf->chunks_alloc);++cf->chunks[cf->chunks_nr].id=id;+cf->chunks[cf->chunks_nr].write_fn=fn;+cf->chunks[cf->chunks_nr].size=size;+cf->chunks_nr++;+}++intwrite_chunkfile(structchunkfile*cf,void*data)+{+inti;+size_tcur_offset=cf->f->offset+cf->f->total;++/* Add the table of contents to the current offset */+cur_offset+=(cf->chunks_nr+1)*CHUNK_LOOKUP_WIDTH;++for(i=0;i<cf->chunks_nr;i++){+hashwrite_be32(cf->f,cf->chunks[i].id);+hashwrite_be64(cf->f,cur_offset);++cur_offset+=cf->chunks[i].size;+}++/* Trailing entry marks the end of the chunks */+hashwrite_be32(cf->f,0);+hashwrite_be64(cf->f,cur_offset);++for(i=0;i<cf->chunks_nr;i++){+uint64_tstart_offset=cf->f->total+cf->f->offset;+intresult=cf->chunks[i].write_fn(cf->f,data);++if(result)+returnresult;++if(cf->f->total+cf->f->offset-start_offset!=cf->chunks[i].size)+BUG("expected to write %"PRId64" bytes to chunk %"PRIx32", but wrote %"PRId64" instead",+cf->chunks[i].size,cf->chunks[i].id,+cf->f->total+cf->f->offset-start_offset);+}++return0;+}
From: Derrick Stolee via GitGitGadget <hidden> Date: 2021-01-27 15:35:27
From: Derrick Stolee <redacted>
When calculating the sizes of certain chunks, we should use 64-bit
multiplication always. This allows us to properly predict the chunk
sizes without risk of overflow.
Signed-off-by: Derrick Stolee <redacted>
---
midx.c | 4 ++--
1 file changed, 2 insertions(+), 2 deletions(-)
From: Derrick Stolee via GitGitGadget <hidden> Date: 2021-01-27 15:35:27
From: Derrick Stolee <redacted>
The chunk-based file format is now an API in the code, but we should
also take time to document it as a file format. Specifically, it matches
the CHUNK LOOKUP sections of the commit-graph and multi-pack-index
files, but there are some commonalities that should be grouped in this
document.
Signed-off-by: Derrick Stolee <redacted>
---
Documentation/technical/chunk-format.txt | 54 +++++++++++++++++++
.../technical/commit-graph-format.txt | 3 ++
Documentation/technical/pack-format.txt | 3 ++
3 files changed, 60 insertions(+)
create mode 100644 Documentation/technical/chunk-format.txt
@@ -0,0 +1,54 @@+Chunk-based file formats+========================++Some file formats in Git use a common concept of "chunks" to describe+sections of the file. This allows structured access to a large file by+scanning a small "table of contents" for the remaining data. This common+format is used by the `commit-graph` and `multi-pack-index` files. See+link:technical/pack-format.html[the `multi-pack-index` format] and+link:technical/commit-graph-format.html[the `commit-graph` format] for+how they use the chunks to describe structured data.++A chunk-based file format begins with some header information custom to+that format. That header should include enough information to identify+the file type, format version, and number of chunks in the file. From this+information, that file can determine the start of the chunk-based region.++The chunk-based region starts with a table of contents describing where+each chunk starts and ends. This consists of (C+1) rows of 12 bytes each,+where C is the number of chunks. Consider the following table:++ | Chunk ID (4 bytes) | Chunk Offset (8 bytes) |+ |--------------------|------------------------|+ | ID[0] | OFFSET[0] |+ | ... | ... |+ | ID[C] | OFFSET[C] |+ | 0x0000 | OFFSET[C+1] |++Each row consists of a 4-byte chunk identifier (ID) and an 8-byte offset.+Each integer is stored in network-byte order.++The chunk identifier `ID[i]` is a label for the data stored within this+fill from `OFFSET[i]` (inclusive) to `OFFSET[i+1]` (exclusive). Thus, the+size of the `i`th chunk is equal to the difference between `OFFSET[i+1]`+and `OFFSET[i]`. This requires that the chunk data appears contiguously+in the same order as the table of contents.++The final entry in the table of contents must be four zero bytes. This+confirms that the table of contents is ending and provides the offset for+the end of the chunk-based data.++Note: The chunk-based format expects that the file contains _at least_ a+trailing hash after `OFFSET[C+1]`.++Functions for working with chunk-based file formats are declared in+`chunk-format.h`. Using these methods provide extra checks that assist+developers when creating new file formats, including:++ 1. Writing and reading the table of contents.++ 2. Verifying that the data written in a chunk matches the expected size+ that was recorded in the table of contents.++ 3. Checking that a table of contents describes offsets properly within+ the file boundaries.
@@ -61,6 +61,9 @@ CHUNK LOOKUP: the length using the next chunk position if necessary.) Each chunk ID appears at most once.+ The CHUNK LOOKUP matches the table of contents from+ link:technical/chunk-format.html[the chunk-based file format].+ The remaining data in the body is described one chunk at a time, and these chunks may be given in any order. Chunks are required unless otherwise specified.
@@ -301,6 +301,9 @@ CHUNK LOOKUP: (Chunks are provided in file-order, so you can infer the length using the next chunk position if necessary.)+ The CHUNK LOOKUP matches the table of contents from+ link:technical/chunk-format.html[the chunk-based file format].+ The remaining data in the body is described one chunk at a time, and these chunks may be given in any order. Chunks are required unless otherwise specified.
From: Derrick Stolee via GitGitGadget <hidden> Date: 2021-01-27 15:35:28
From: Derrick Stolee <redacted>
Instead of parsing the table of contents directly, use the chunk-format
API methods read_table_of_contents() and pair_chunk(). In particular, we
can use the return value of pair_chunk() to generate an error when a
required chunk is missing.
Signed-off-by: Derrick Stolee <redacted>
---
midx.c | 71 +++++++++++++------------------------
t/t5319-multi-pack-index.sh | 6 ++--
2 files changed, 28 insertions(+), 49 deletions(-)
@@ -54,6 +54,19 @@ static char *get_midx_filename(const char *object_dir)returnxstrfmt("%s/pack/multi-pack-index",object_dir);}+staticintmidx_read_oid_fanout(constunsignedchar*chunk_start,+size_tchunk_size,void*data)+{+structmulti_pack_index*m=data;+m->chunk_oid_fanout=(uint32_t*)chunk_start;++if(chunk_size!=4*256){+error(_("multi-pack-index OID fanout is of the wrong size"));+return1;+}+return0;+}+structmulti_pack_index*load_multi_pack_index(constchar*object_dir,intlocal){structmulti_pack_index*m=NULL;
From: Derrick Stolee via GitGitGadget <hidden> Date: 2021-01-27 15:36:10
From: Derrick Stolee <redacted>
Instead of parsing the table of contents directly, use the chunk-format
API methods read_table_of_contents() and pair_chunk(). While the current
implementation loses the duplicate-chunk detection, that will be added
in a future change.
Signed-off-by: Derrick Stolee <redacted>
---
commit-graph.c | 154 ++++++++++++++--------------------------
t/t5318-commit-graph.sh | 2 +-
2 files changed, 53 insertions(+), 103 deletions(-)
From: Derrick Stolee via GitGitGadget <hidden> Date: 2021-01-27 15:36:11
From: Derrick Stolee <redacted>
Before refactoring into the chunk-format API, the commit-graph parsing
logic included checks for duplicate chunks. It is unlikely that we would
desire a chunk-based file format that allows duplicate chunk IDs in the
table of contents, so add duplicate checks into
read_table_of_contents().
Signed-off-by: Derrick Stolee <redacted>
---
chunk-format.c | 10 ++++++++++
1 file changed, 10 insertions(+)
From: Derrick Stolee via GitGitGadget <hidden> Date: 2021-01-27 15:36:13
From: Derrick Stolee <redacted>
The chunk-format API allows writing the table of contents and all chunks
using the anonymous 'struct chunkfile' type. We only need to convert our
local chunk logic to this API for the multi-pack-index writes to share
that logic with the commit-graph file writes.
Signed-off-by: Derrick Stolee <redacted>
---
midx.c | 104 +++++++++++----------------------------------------------
1 file changed, 19 insertions(+), 85 deletions(-)
@@ -799,18 +800,15 @@ static int write_midx_large_offsets(struct hashfile *f,staticintwrite_midx_internal(constchar*object_dir,structmulti_pack_index*m,structstring_list*packs_to_drop,unsignedflags){-unsignedcharcur_chunk,num_chunks=0;char*midx_name;uint32_ti;structhashfile*f=NULL;structlock_filelk;structwrite_midx_contextctx={0};-uint64_theader_size=0;-uint32_tchunk_ids[MIDX_MAX_CHUNKS+1];-uint64_tchunk_offsets[MIDX_MAX_CHUNKS+1];intpack_name_concat_len=0;intdropped_packs=0;intresult=0;+structchunkfile*cf;midx_name=get_midx_filename(object_dir);if(safe_create_leading_directories(midx_name))
@@ -923,98 +921,34 @@ static int write_midx_internal(const char *object_dir, struct multi_pack_index *if(ctx.m)close_midx(ctx.m);-cur_chunk=0;-num_chunks=ctx.large_offsets_needed?5:4;-if(ctx.nr-dropped_packs==0){error(_("no pack files to index."));result=1;gotocleanup;}-header_size=write_midx_header(f,num_chunks,ctx.nr-dropped_packs);--chunk_ids[cur_chunk]=MIDX_CHUNKID_PACKNAMES;-chunk_offsets[cur_chunk]=header_size+(num_chunks+1)*MIDX_CHUNKLOOKUP_WIDTH;--cur_chunk++;-chunk_ids[cur_chunk]=MIDX_CHUNKID_OIDFANOUT;-chunk_offsets[cur_chunk]=chunk_offsets[cur_chunk-1]+pack_name_concat_len;--cur_chunk++;-chunk_ids[cur_chunk]=MIDX_CHUNKID_OIDLOOKUP;-chunk_offsets[cur_chunk]=chunk_offsets[cur_chunk-1]+MIDX_CHUNK_FANOUT_SIZE;--cur_chunk++;-chunk_ids[cur_chunk]=MIDX_CHUNKID_OBJECTOFFSETS;-chunk_offsets[cur_chunk]=chunk_offsets[cur_chunk-1]+ctx.entries_nr*the_hash_algo->rawsz;--cur_chunk++;-chunk_offsets[cur_chunk]=chunk_offsets[cur_chunk-1]+ctx.entries_nr*MIDX_CHUNK_OFFSET_WIDTH;-if(ctx.large_offsets_needed){-chunk_ids[cur_chunk]=MIDX_CHUNKID_LARGEOFFSETS;--cur_chunk++;-chunk_offsets[cur_chunk]=chunk_offsets[cur_chunk-1]+-ctx.num_large_offsets*MIDX_CHUNK_LARGE_OFFSET_WIDTH;-}--chunk_ids[cur_chunk]=0;--for(i=0;i<=num_chunks;i++){-if(i&&chunk_offsets[i]<chunk_offsets[i-1])-BUG("incorrect chunk offsets: %"PRIu64" before %"PRIu64,-chunk_offsets[i-1],-chunk_offsets[i]);--if(chunk_offsets[i]%MIDX_CHUNK_ALIGNMENT)-BUG("chunk offset %"PRIu64" is not properly aligned",-chunk_offsets[i]);--hashwrite_be32(f,chunk_ids[i]);-hashwrite_be64(f,chunk_offsets[i]);-}--for(i=0;i<num_chunks;i++){-if(f->total+f->offset!=chunk_offsets[i])-BUG("incorrect chunk offset (%"PRIu64" != %"PRIu64") for chunk id %"PRIx32,-chunk_offsets[i],-f->total+f->offset,-chunk_ids[i]);+cf=init_chunkfile(f);-switch(chunk_ids[i]){-caseMIDX_CHUNKID_PACKNAMES:-write_midx_pack_names(f,&ctx);-break;+add_chunk(cf,MIDX_CHUNKID_PACKNAMES,+write_midx_pack_names,pack_name_concat_len);+add_chunk(cf,MIDX_CHUNKID_OIDFANOUT,+write_midx_oid_fanout,MIDX_CHUNK_FANOUT_SIZE);+add_chunk(cf,MIDX_CHUNKID_OIDLOOKUP,+write_midx_oid_lookup,ctx.entries_nr*the_hash_algo->rawsz);+add_chunk(cf,MIDX_CHUNKID_OBJECTOFFSETS,+write_midx_object_offsets,+ctx.entries_nr*MIDX_CHUNK_OFFSET_WIDTH);-caseMIDX_CHUNKID_OIDFANOUT:-write_midx_oid_fanout(f,&ctx);-break;--caseMIDX_CHUNKID_OIDLOOKUP:-write_midx_oid_lookup(f,&ctx);-break;--caseMIDX_CHUNKID_OBJECTOFFSETS:-write_midx_object_offsets(f,&ctx);-break;--caseMIDX_CHUNKID_LARGEOFFSETS:-write_midx_large_offsets(f,&ctx);-break;--default:-BUG("trying to write unknown chunk id %"PRIx32,-chunk_ids[i]);-}-}+if(ctx.large_offsets_needed)+add_chunk(cf,MIDX_CHUNKID_LARGEOFFSETS,+write_midx_large_offsets,+ctx.num_large_offsets*MIDX_CHUNK_LARGE_OFFSET_WIDTH);-if(f->total+f->offset!=chunk_offsets[num_chunks])-BUG("incorrect final offset %"PRIu64" != %"PRIu64,-f->total+f->offset,-chunk_offsets[num_chunks]);+write_midx_header(f,get_num_chunks(cf),ctx.nr-dropped_packs);+write_chunkfile(cf,&ctx);finalize_hashfile(f,NULL,CSUM_FSYNC|CSUM_HASH_IN_STREAM);+free_chunkfile(cf);commit_lock_file(&lk);cleanup:
From: Derrick Stolee via GitGitGadget <hidden> Date: 2021-01-27 15:36:16
From: Derrick Stolee <redacted>
Add the capability to read the table of contents, then pair the chunks
with necessary logic using read_chunk_fn pointers. Callers will be added
in future changes, but the typical outline will be:
1. initialize a 'struct chunkfile' with init_chunkfile(NULL).
2. call read_table_of_contents().
3. for each chunk to parse,
a. call pair_chunk() to assign a pointer with the chunk position, or
b. call read_chunk() to run a callback on the chunk start and size.
4. call free_chunkfile() to clear the 'struct chunkfile' data.
We are re-using the anonymous 'struct chunkfile' data, as it is internal
to the chunk-format API. This gives it essentially two modes: write and
read. If the same struct instance was used for both reads and writes,
then there would be failures.
Signed-off-by: Derrick Stolee <redacted>
---
chunk-format.c | 80 ++++++++++++++++++++++++++++++++++++++++++++++++++
chunk-format.h | 33 +++++++++++++++++++++
2 files changed, 113 insertions(+)
@@ -89,3 +91,81 @@ int write_chunkfile(struct chunkfile *cf, void *data)return0;}++intread_table_of_contents(structchunkfile*cf,+constunsignedchar*mfile,+size_tmfile_size,+uint64_ttoc_offset,+inttoc_length)+{+uint32_tchunk_id;+constunsignedchar*table_of_contents=mfile+toc_offset;++ALLOC_GROW(cf->chunks,toc_length,cf->chunks_alloc);++while(toc_length--){+uint64_tchunk_offset,next_chunk_offset;++chunk_id=get_be32(table_of_contents);+chunk_offset=get_be64(table_of_contents+4);++if(!chunk_id){+error(_("terminating chunk id appears earlier than expected"));+return1;+}++table_of_contents+=CHUNK_LOOKUP_WIDTH;+next_chunk_offset=get_be64(table_of_contents+4);++if(next_chunk_offset<chunk_offset||+next_chunk_offset>mfile_size-the_hash_algo->rawsz){+error(_("improper chunk offset(s) %"PRIx64" and %"PRIx64""),+chunk_offset,next_chunk_offset);+return-1;+}++cf->chunks[cf->chunks_nr].id=chunk_id;+cf->chunks[cf->chunks_nr].start=mfile+chunk_offset;+cf->chunks[cf->chunks_nr].size=next_chunk_offset-chunk_offset;+cf->chunks_nr++;+}++chunk_id=get_be32(table_of_contents);+if(chunk_id){+error(_("final chunk has non-zero id %"PRIx32""),chunk_id);+return-1;+}++return0;+}++intpair_chunk(structchunkfile*cf,+uint32_tchunk_id,+constunsignedchar**p)+{+inti;++for(i=0;i<cf->chunks_nr;i++){+if(cf->chunks[i].id==chunk_id){+*p=cf->chunks[i].start;+return0;+}+}++returnCHUNK_NOT_FOUND;+}++intread_chunk(structchunkfile*cf,+uint32_tchunk_id,+chunk_read_fnfn,+void*data)+{+inti;++for(i=0;i<cf->chunks_nr;i++){+if(cf->chunks[i].id==chunk_id)+returnfn(cf->chunks[i].start,cf->chunks[i].size,data);+}++returnCHUNK_NOT_FOUND;+}
From: Derrick Stolee via GitGitGadget <hidden> Date: 2021-01-27 15:36:43
From: Derrick Stolee <redacted>
Historically, the chunk-writing methods in midx.c have returned the
amount of data written so the writer method could compare this with the
table of contents. This presents with some interesting issues:
1. If a chunk writing method has a bug that miscalculates the written
bytes, then we can satisfy the table of contents without actually
writing the right amount of data to the hashfile. The commit-graph
writing code checks the hashfile struct directly for a more robust
verification.
2. There is no way for a chunk writing method to gracefully fail.
Returning an int presents an opportunity to fail without a die().
3. The current pattern doesn't match chunk_write_fn type exactly, so we
cannot share code with commit-graph.c
For these reasons, convert the midx chunk writer methods to return an
'int'. Since none of them fail at the moment, they all return 0.
Signed-off-by: Derrick Stolee <redacted>
---
midx.c | 63 +++++++++++++++++++++++++---------------------------------
1 file changed, 27 insertions(+), 36 deletions(-)
From: Derrick Stolee via GitGitGadget <hidden> Date: 2021-01-27 15:36:44
From: Derrick Stolee <redacted>
Most expensive operations in write_midx_internal() use the context
struct's progress member, and these indicate the process of the
expensive operations within the chunk writing methods. However, there is
a competing progress struct that counts the progress over all chunks.
This is not very helpful compared to the others, so drop it.
This also reduces our barriers to combining the chunk writing code with
chunk-format.c.
Signed-off-by: Derrick Stolee <redacted>
---
midx.c | 7 -------
1 file changed, 7 deletions(-)
From: Derrick Stolee via GitGitGadget <hidden> Date: 2021-01-27 15:57:36
From: Derrick Stolee <redacted>
In an effort to align write_midx_internal() with the chunk-format API,
continue to group necessary data into "struct write_midx_context". This
change collects the "struct pack_midx_entry *entries" list and its count
into the context.
Update write_midx_oid_fanout() and write_midx_oid_lookup() to take the
context directly, as these are easy conversions with this new data.
Only the callers of write_midx_object_offsets() and
write_midx_large_offsets() are updated here, since additional data in
the context before those methods can match chunk_write_fn.
Signed-off-by: Derrick Stolee <redacted>
---
midx.c | 49 ++++++++++++++++++++++++++-----------------------
1 file changed, 26 insertions(+), 23 deletions(-)
From: Derrick Stolee via GitGitGadget <hidden> Date: 2021-01-27 15:58:27
From: Derrick Stolee <redacted>
In an effort to align write_midx_internal() with the chunk-format API,
continue to group necessary data into "struct write_midx_context". This
change collects the "uint32_t num_large_offsets" into the context. With
this new data, write_midx_large_offsets() now matches the
chunk_write_fn type.
Signed-off-by: Derrick Stolee <redacted>
---
midx.c | 17 ++++++++++-------
1 file changed, 10 insertions(+), 7 deletions(-)
From: Derrick Stolee via GitGitGadget <hidden> Date: 2021-01-27 15:59:13
From: Derrick Stolee <redacted>
In an effort to streamline our chunk-based file formats, align some of
the code structure in write_midx_internal() to be similar to the
patterns in write_commit_graph_file().
Specifically, let's create a "struct write_midx_context" that can be
used as a data parameter to abstract function types.
This change only renames "struct pack_info" to "struct
write_midx_context" and the names of instances from "packs" to "ctx". In
future changes, we will expand the data inside "struct
write_midx_context" and align our chunk-writing method with the
chunk-format API.
Signed-off-by: Derrick Stolee <redacted>
---
midx.c | 130 ++++++++++++++++++++++++++++-----------------------------
1 file changed, 65 insertions(+), 65 deletions(-)
@@ -463,37 +463,37 @@ struct pack_list {staticvoidadd_pack_to_midx(constchar*full_path,size_tfull_path_len,constchar*file_name,void*data){-structpack_list*packs=(structpack_list*)data;+structwrite_midx_context*ctx=data;if(ends_with(file_name,".idx")){-display_progress(packs->progress,++packs->pack_paths_checked);-if(packs->m&&midx_contains_pack(packs->m,file_name))+display_progress(ctx->progress,++ctx->pack_paths_checked);+if(ctx->m&&midx_contains_pack(ctx->m,file_name))return;-ALLOC_GROW(packs->info,packs->nr+1,packs->alloc);+ALLOC_GROW(ctx->info,ctx->nr+1,ctx->alloc);-packs->info[packs->nr].p=add_packed_git(full_path,-full_path_len,-0);+ctx->info[ctx->nr].p=add_packed_git(full_path,+full_path_len,+0);-if(!packs->info[packs->nr].p){+if(!ctx->info[ctx->nr].p){warning(_("failed to add packfile '%s'"),full_path);return;}-if(open_pack_index(packs->info[packs->nr].p)){+if(open_pack_index(ctx->info[ctx->nr].p)){warning(_("failed to open pack-index '%s'"),full_path);-close_pack(packs->info[packs->nr].p);-FREE_AND_NULL(packs->info[packs->nr].p);+close_pack(ctx->info[ctx->nr].p);+FREE_AND_NULL(ctx->info[ctx->nr].p);return;}-packs->info[packs->nr].pack_name=xstrdup(file_name);-packs->info[packs->nr].orig_pack_int_id=packs->nr;-packs->info[packs->nr].expired=0;-packs->nr++;+ctx->info[ctx->nr].pack_name=xstrdup(file_name);+ctx->info[ctx->nr].orig_pack_int_id=ctx->nr;+ctx->info[ctx->nr].expired=0;+ctx->nr++;}}
@@ -820,40 +820,40 @@ static int write_midx_internal(const char *object_dir, struct multi_pack_index *midx_name);if(m)-packs.m=m;+ctx.m=m;else-packs.m=load_multi_pack_index(object_dir,1);--packs.nr=0;-packs.alloc=packs.m?packs.m->num_packs:16;-packs.info=NULL;-ALLOC_ARRAY(packs.info,packs.alloc);--if(packs.m){-for(i=0;i<packs.m->num_packs;i++){-ALLOC_GROW(packs.info,packs.nr+1,packs.alloc);--packs.info[packs.nr].orig_pack_int_id=i;-packs.info[packs.nr].pack_name=xstrdup(packs.m->pack_names[i]);-packs.info[packs.nr].p=NULL;-packs.info[packs.nr].expired=0;-packs.nr++;+ctx.m=load_multi_pack_index(object_dir,1);++ctx.nr=0;+ctx.alloc=ctx.m?ctx.m->num_packs:16;+ctx.info=NULL;+ALLOC_ARRAY(ctx.info,ctx.alloc);++if(ctx.m){+for(i=0;i<ctx.m->num_packs;i++){+ALLOC_GROW(ctx.info,ctx.nr+1,ctx.alloc);++ctx.info[ctx.nr].orig_pack_int_id=i;+ctx.info[ctx.nr].pack_name=xstrdup(ctx.m->pack_names[i]);+ctx.info[ctx.nr].p=NULL;+ctx.info[ctx.nr].expired=0;+ctx.nr++;}}-packs.pack_paths_checked=0;+ctx.pack_paths_checked=0;if(flags&MIDX_PROGRESS)-packs.progress=start_delayed_progress(_("Adding packfiles to multi-pack-index"),0);+ctx.progress=start_delayed_progress(_("Adding packfiles to multi-pack-index"),0);else-packs.progress=NULL;+ctx.progress=NULL;-for_each_file_in_pack_dir(object_dir,add_pack_to_midx,&packs);-stop_progress(&packs.progress);+for_each_file_in_pack_dir(object_dir,add_pack_to_midx,&ctx);+stop_progress(&ctx.progress);-if(packs.m&&packs.nr==packs.m->num_packs&&!packs_to_drop)+if(ctx.m&&ctx.nr==ctx.m->num_packs&&!packs_to_drop)gotocleanup;-entries=get_sorted_entries(packs.m,packs.info,packs.nr,&nr_entries);+entries=get_sorted_entries(ctx.m,ctx.info,ctx.nr,&nr_entries);for(i=0;i<nr_entries;i++){if(entries[i].offset>0x7fffffff)
@@ -862,19 +862,19 @@ static int write_midx_internal(const char *object_dir, struct multi_pack_index *large_offsets_needed=1;}-QSORT(packs.info,packs.nr,pack_info_compare);+QSORT(ctx.info,ctx.nr,pack_info_compare);if(packs_to_drop&&packs_to_drop->nr){intdrop_index=0;intmissing_drops=0;-for(i=0;i<packs.nr&&drop_index<packs_to_drop->nr;i++){-intcmp=strcmp(packs.info[i].pack_name,+for(i=0;i<ctx.nr&&drop_index<packs_to_drop->nr;i++){+intcmp=strcmp(ctx.info[i].pack_name,packs_to_drop->items[drop_index].string);if(!cmp){drop_index++;-packs.info[i].expired=1;+ctx.info[i].expired=1;}elseif(cmp>0){error(_("did not see pack-file %s to drop"),packs_to_drop->items[drop_index].string);
From: Derrick Stolee via GitGitGadget <hidden> Date: 2021-01-27 15:59:16
From: Derrick Stolee <redacted>
In preparation for creating an API around file formats using chunks and
tables of contents, prepare the commit-graph write code to use
prototypes that will match this new API.
Specifically, convert chunk_write_fn to take a "void *data" parameter
instead of the commit-graph-specific "struct write_commit_graph_context"
pointer.
Signed-off-by: Derrick Stolee <redacted>
---
commit-graph.c | 29 +++++++++++++++++++----------
1 file changed, 19 insertions(+), 10 deletions(-)
From: Taylor Blau <hidden> Date: 2021-01-27 16:06:44
On Wed, Jan 27, 2021 at 03:01:39PM +0000, Derrick Stolee via GitGitGadget wrote:
Updates in V2
=============
* The method pair_chunk() now automatically sets a pointer while
read_chunk() uses the callback. This greatly reduces the code size.
* Pointer casts are now implicit instead of explicit.
* Extra care is taken to not overflow when verifying chunk sizes on write.
Thanks, I read the range-diff between this version and the last and
appreciate you taking the time to address all of my concerns.
I think that this is ready to go, so please have my:
Reviewed-by: Taylor Blau [off-list ref]
Thanks,
Taylor
From: Derrick Stolee via GitGitGadget <hidden> Date: 2021-02-05 16:26:24
From: Derrick Stolee <redacted>
Most expensive operations in write_midx_internal() use the context
struct's progress member, and these indicate the process of the
expensive operations within the chunk writing methods. However, there is
a competing progress struct that counts the progress over all chunks.
This is not very helpful compared to the others, so drop it.
This also reduces our barriers to combining the chunk writing code with
chunk-format.c.
Signed-off-by: Derrick Stolee <redacted>
---
midx.c | 7 -------
1 file changed, 7 deletions(-)
From: Derrick Stolee via GitGitGadget <hidden> Date: 2021-02-05 16:33:20
From: Derrick Stolee <redacted>
The chunk-based file format is now an API in the code, but we should
also take time to document it as a file format. Specifically, it matches
the CHUNK LOOKUP sections of the commit-graph and multi-pack-index
files, but there are some commonalities that should be grouped in this
document.
Signed-off-by: Derrick Stolee <redacted>
---
Documentation/technical/chunk-format.txt | 116 ++++++++++++++++++
.../technical/commit-graph-format.txt | 3 +
Documentation/technical/pack-format.txt | 3 +
3 files changed, 122 insertions(+)
create mode 100644 Documentation/technical/chunk-format.txt
@@ -0,0 +1,116 @@+Chunk-based file formats+========================++Some file formats in Git use a common concept of "chunks" to describe+sections of the file. This allows structured access to a large file by+scanning a small "table of contents" for the remaining data. This common+format is used by the `commit-graph` and `multi-pack-index` files. See+link:technical/pack-format.html[the `multi-pack-index` format] and+link:technical/commit-graph-format.html[the `commit-graph` format] for+how they use the chunks to describe structured data.++A chunk-based file format begins with some header information custom to+that format. That header should include enough information to identify+the file type, format version, and number of chunks in the file. From this+information, that file can determine the start of the chunk-based region.++The chunk-based region starts with a table of contents describing where+each chunk starts and ends. This consists of (C+1) rows of 12 bytes each,+where C is the number of chunks. Consider the following table:++ | Chunk ID (4 bytes) | Chunk Offset (8 bytes) |+ |--------------------|------------------------|+ | ID[0] | OFFSET[0] |+ | ... | ... |+ | ID[C] | OFFSET[C] |+ | 0x0000 | OFFSET[C+1] |++Each row consists of a 4-byte chunk identifier (ID) and an 8-byte offset.+Each integer is stored in network-byte order.++The chunk identifier `ID[i]` is a label for the data stored within this+fill from `OFFSET[i]` (inclusive) to `OFFSET[i+1]` (exclusive). Thus, the+size of the `i`th chunk is equal to the difference between `OFFSET[i+1]`+and `OFFSET[i]`. This requires that the chunk data appears contiguously+in the same order as the table of contents.++The final entry in the table of contents must be four zero bytes. This+confirms that the table of contents is ending and provides the offset for+the end of the chunk-based data.++Note: The chunk-based format expects that the file contains _at least_ a+trailing hash after `OFFSET[C+1]`.++Functions for working with chunk-based file formats are declared in+`chunk-format.h`. Using these methods provide extra checks that assist+developers when creating new file formats.++Writing chunk-based file formats+--------------------------------++To write a chunk-based file format, create a `struct chunkfile` by+calling `init_chunkfile()` and pass a `struct hashfile` pointer. The+caller is responsible for opening the `hashfile` and writing header+information so the file format is identifiable before the chunk-based+format begins.++Then, call `add_chunk()` for each chunk that is intended for write. This+populates the `chunkfile` with information about the order and size of+each chunk to write. Provide a `chunk_write_fn` function pointer to+perform the write of the chunk data upon request.++Call `write_chunkfile()` to write the table of contents to the `hashfile`+followed by each of the chunks. This will verify that each chunk wrote+the expected amount of data so the table of contents is correct.++Finally, call `free_chunkfile()` to clear the `struct chunkfile` data. The+caller is responsible for finalizing the `hashfile` by writing the trailing+hash and closing the file.++Reading chunk-based file formats+--------------------------------++To read a chunk-based file format, the file must be opened as a+memory-mapped region. The chunk-format API expects that the entire file+is mapped as a contiguous memory region.++Initialize a `struct chunkfile` pointer with `init_chunkfile(NULL)`.++After reading the header information from the beginning of the file,+including the chunk count, call `read_table_of_contents()` to populate+the `struct chunkfile` with the list of chunks, their offsets, and their+sizes.++Extract the data information for each chunk using `pair_chunk()` or+`read_chunk()`:++* `pair_chunk()` assigns a given pointer with the location inside the+ memory-mapped file corresponding to that chunk's offset. If the chunk+ does not exist, then the pointer is not modified.++* `read_chunk()` takes a `chunk_read_fn` function pointer and calls it+ with the appropriate initial pointer and size information. The function+ is not called if the chunk does not exist. Use this method to read chunks+ if you need to perform immediate parsing or if you need to execute logic+ based on the size of the chunk.++After calling these methods, call `free_chunkfile()` to clear the+`struct chunkfile` data. This will not close the memory-mapped region.+Callers are expected to own that data for the timeframe the pointers into+the region are needed.++Examples+--------++These file formats use the chunk-format API, and can be used as examples+for future formats:++* *commit-graph:* see `write_commit_graph_file()` and `parse_commit_graph()`+ in `commit-graph.c` for how the chunk-format API is used to write and+ parse the commit-graph file format documented in+ link:technical/commit-graph-format.html[the commit-graph file format].++* *multi-pack-index:* see `write_midx_internal()` and `load_multi_pack_index()`+ in `midx.c` for how the chunk-format API is used to write and+ parse the multi-pack-index file format documented in+ link:technical/pack-format.html[the multi-pack-index file format].
@@ -61,6 +61,9 @@ CHUNK LOOKUP: the length using the next chunk position if necessary.) Each chunk ID appears at most once.+ The CHUNK LOOKUP matches the table of contents from+ link:technical/chunk-format.html[the chunk-based file format].+ The remaining data in the body is described one chunk at a time, and these chunks may be given in any order. Chunks are required unless otherwise specified.
@@ -301,6 +301,9 @@ CHUNK LOOKUP: (Chunks are provided in file-order, so you can infer the length using the next chunk position if necessary.)+ The CHUNK LOOKUP matches the table of contents from+ link:technical/chunk-format.html[the chunk-based file format].+ The remaining data in the body is described one chunk at a time, and these chunks may be given in any order. Chunks are required unless otherwise specified.
From: Derrick Stolee via GitGitGadget <hidden> Date: 2021-02-05 16:41:30
From: Derrick Stolee <redacted>
Historically, the chunk-writing methods in midx.c have returned the
amount of data written so the writer method could compare this with the
table of contents. This presents with some interesting issues:
1. If a chunk writing method has a bug that miscalculates the written
bytes, then we can satisfy the table of contents without actually
writing the right amount of data to the hashfile. The commit-graph
writing code checks the hashfile struct directly for a more robust
verification.
2. There is no way for a chunk writing method to gracefully fail.
Returning an int presents an opportunity to fail without a die().
3. The current pattern doesn't match chunk_write_fn type exactly, so we
cannot share code with commit-graph.c
For these reasons, convert the midx chunk writer methods to return an
'int'. Since none of them fail at the moment, they all return 0.
Signed-off-by: Derrick Stolee <redacted>
---
midx.c | 63 +++++++++++++++++++++++++---------------------------------
1 file changed, 27 insertions(+), 36 deletions(-)
From: Derrick Stolee via GitGitGadget <hidden> Date: 2021-02-05 21:44:23
From: Derrick Stolee <redacted>
When calculating the sizes of certain chunks, we should use 64-bit
multiplication always. This allows us to properly predict the chunk
sizes without risk of overflow.
Other possible overflows were discovered by evaluating each
multiplication in midx.c and ensuring that at least one side of the
operator was of type size_t or off_t.
Signed-off-by: Derrick Stolee <redacted>
---
midx.c | 11 ++++++-----
1 file changed, 6 insertions(+), 5 deletions(-)
From: Derrick Stolee via GitGitGadget <hidden> Date: 2021-02-05 22:01:40
From: Derrick Stolee <redacted>
In anticipation of combining the logic from the commit-graph and
multi-pack-index file formats, create a new chunk-format API. Use a
'struct chunkfile' pointer to keep track of data that has been
registered for writes. This struct is anonymous outside of
chunk-format.c to ensure no user attempts to interfere with the data.
The next change will use this API in commit-graph.c, but the general
approach is:
1. initialize the chunkfile with init_chunkfile(f).
2. add chunks in the intended writing order with add_chunk().
3. write any header information to the hashfile f.
4. write the chunkfile data using write_chunkfile().
5. free the chunkfile struct using free_chunkfile().
Helped-by: Taylor Blau [off-list ref]
Helped-by: Junio C Hamano [off-list ref]
Signed-off-by: Derrick Stolee <redacted>
---
Makefile | 1 +
chunk-format.c | 91 ++++++++++++++++++++++++++++++++++++++++++++++++++
chunk-format.h | 19 +++++++++++
3 files changed, 111 insertions(+)
create mode 100644 chunk-format.c
create mode 100644 chunk-format.h
@@ -0,0 +1,91 @@+#include"cache.h"+#include"chunk-format.h"+#include"csum-file.h"+#define CHUNK_LOOKUP_WIDTH 12++/*+*Whenwritingachunk-basedfileformat,collectthechunksin+*anarrayofchunk_infostructs.Thesizestoresthe_expected_+*amountofdatathatwillbewrittenbywrite_fn.+*/+structchunk_info{+uint32_tid;+uint64_tsize;+chunk_write_fnwrite_fn;+};++structchunkfile{+structhashfile*f;++structchunk_info*chunks;+size_tchunks_nr;+size_tchunks_alloc;+};++structchunkfile*init_chunkfile(structhashfile*f)+{+structchunkfile*cf=xcalloc(1,sizeof(*cf));+cf->f=f;+returncf;+}++voidfree_chunkfile(structchunkfile*cf)+{+if(!cf)+return;+free(cf->chunks);+free(cf);+}++intget_num_chunks(structchunkfile*cf)+{+returncf->chunks_nr;+}++voidadd_chunk(structchunkfile*cf,+uint32_tid,+size_tsize,+chunk_write_fnfn)+{+ALLOC_GROW(cf->chunks,cf->chunks_nr+1,cf->chunks_alloc);++cf->chunks[cf->chunks_nr].id=id;+cf->chunks[cf->chunks_nr].write_fn=fn;+cf->chunks[cf->chunks_nr].size=size;+cf->chunks_nr++;+}++intwrite_chunkfile(structchunkfile*cf,void*data)+{+inti;+uint64_tcur_offset=hashfile_total(cf->f);++/* Add the table of contents to the current offset */+cur_offset+=(cf->chunks_nr+1)*CHUNK_LOOKUP_WIDTH;++for(i=0;i<cf->chunks_nr;i++){+hashwrite_be32(cf->f,cf->chunks[i].id);+hashwrite_be64(cf->f,cur_offset);++cur_offset+=cf->chunks[i].size;+}++/* Trailing entry marks the end of the chunks */+hashwrite_be32(cf->f,0);+hashwrite_be64(cf->f,cur_offset);++for(i=0;i<cf->chunks_nr;i++){+off_tstart_offset=hashfile_total(cf->f);+intresult=cf->chunks[i].write_fn(cf->f,data);++if(result)+returnresult;++if(hashfile_total(cf->f)-start_offset!=cf->chunks[i].size)+BUG("expected to write %"PRId64" bytes to chunk %"PRIx32", but wrote %"PRId64" instead",+cf->chunks[i].size,cf->chunks[i].id,+hashfile_total(cf->f)-start_offset);+}++return0;+}
From: Derrick Stolee via GitGitGadget <hidden> Date: 2021-02-05 22:02:20
From: Derrick Stolee <redacted>
In an effort to align write_midx_internal() with the chunk-format API,
continue to group necessary data into "struct write_midx_context". This
change collects the "uint32_t num_large_offsets" into the context. With
this new data, write_midx_large_offsets() now matches the
chunk_write_fn type.
Signed-off-by: Derrick Stolee <redacted>
---
midx.c | 17 ++++++++++-------
1 file changed, 10 insertions(+), 7 deletions(-)
From: Derrick Stolee via GitGitGadget <hidden> Date: 2021-02-05 22:07:09
From: Derrick Stolee <redacted>
In an effort to align the write_midx_internal() to use the chunk-format
API, start converting chunk writing methods to match chunk_write_fn. The
first case is to convert write_midx_pack_names() to take "void *data".
We already have the necessary data in "struct write_midx_context", so
this conversion is rather mechanical.
Signed-off-by: Derrick Stolee <redacted>
---
midx.c | 21 ++++++++++-----------
1 file changed, 10 insertions(+), 11 deletions(-)
From: Derrick Stolee via GitGitGadget <hidden> Date: 2021-02-05 22:08:16
From: Derrick Stolee <redacted>
Instead of parsing the table of contents directly, use the chunk-format
API methods read_table_of_contents() and pair_chunk(). In particular, we
can use the return value of pair_chunk() to generate an error when a
required chunk is missing.
Signed-off-by: Derrick Stolee <redacted>
---
midx.c | 72 ++++++++++++++-----------------------
t/t5319-multi-pack-index.sh | 6 ++--
2 files changed, 29 insertions(+), 49 deletions(-)
@@ -54,6 +54,19 @@ static char *get_midx_filename(const char *object_dir)returnxstrfmt("%s/pack/multi-pack-index",object_dir);}+staticintmidx_read_oid_fanout(constunsignedchar*chunk_start,+size_tchunk_size,void*data)+{+structmulti_pack_index*m=data;+m->chunk_oid_fanout=(uint32_t*)chunk_start;++if(chunk_size!=4*256){+error(_("multi-pack-index OID fanout is of the wrong size"));+return1;+}+return0;+}+structmulti_pack_index*load_multi_pack_index(constchar*object_dir,intlocal){structmulti_pack_index*m=NULL;
From: Derrick Stolee via GitGitGadget <hidden> Date: 2021-02-05 22:12:52
From: Derrick Stolee <redacted>
In an effort to align write_midx_internal() with the chunk-format API,
continue to group necessary data into "struct write_midx_context". This
change collects the "uint32_t *pack_perm" and large_offsets_needed bit
into the context.
Update write_midx_object_offsets() to match chunk_write_fn.
Signed-off-by: Derrick Stolee <redacted>
---
midx.c | 40 +++++++++++++++++++++-------------------
1 file changed, 21 insertions(+), 19 deletions(-)
@@ -736,27 +739,27 @@ static size_t write_midx_oid_lookup(struct hashfile *f,returnwritten;}-staticsize_twrite_midx_object_offsets(structhashfile*f,intlarge_offset_needed,-uint32_t*perm,-structpack_midx_entry*objects,uint32_tnr_objects)+staticsize_twrite_midx_object_offsets(structhashfile*f,+void*data){-structpack_midx_entry*list=objects;+structwrite_midx_context*ctx=data;+structpack_midx_entry*list=ctx->entries;uint32_ti,nr_large_offset=0;size_twritten=0;-for(i=0;i<nr_objects;i++){+for(i=0;i<ctx->entries_nr;i++){structpack_midx_entry*obj=list++;-if(perm[obj->pack_int_id]==PACK_EXPIRED)+if(ctx->pack_perm[obj->pack_int_id]==PACK_EXPIRED)BUG("object %s is in an expired pack with int-id %d",oid_to_hex(&obj->oid),obj->pack_int_id);-hashwrite_be32(f,perm[obj->pack_int_id]);+hashwrite_be32(f,ctx->pack_perm[obj->pack_int_id]);-if(large_offset_needed&&obj->offset>>31)+if(ctx->large_offsets_needed&&obj->offset>>31)hashwrite_be32(f,MIDX_LARGE_OFFSET_NEEDED|nr_large_offset++);-elseif(!large_offset_needed&&obj->offset>>32)+elseif(!ctx->large_offsets_needed&&obj->offset>>32)BUG("object %s requires a large offset (%"PRIx64") but the MIDX is not writing large offsets!",oid_to_hex(&obj->oid),obj->offset);
From: Derrick Stolee via GitGitGadget <hidden> Date: 2021-02-05 22:12:52
From: Derrick Stolee <redacted>
In an effort to align write_midx_internal() with the chunk-format API,
continue to group necessary data into "struct write_midx_context". This
change collects the "struct pack_midx_entry *entries" list and its count
into the context.
Update write_midx_oid_fanout() and write_midx_oid_lookup() to take the
context directly, as these are easy conversions with this new data.
Only the callers of write_midx_object_offsets() and
write_midx_large_offsets() are updated here, since additional data in
the context before those methods can match chunk_write_fn.
Signed-off-by: Derrick Stolee <redacted>
---
midx.c | 49 ++++++++++++++++++++++++++-----------------------
1 file changed, 26 insertions(+), 23 deletions(-)
From: Derrick Stolee via GitGitGadget <hidden> Date: 2021-02-05 22:12:53
From: Derrick Stolee <redacted>
Before refactoring into the chunk-format API, the commit-graph parsing
logic included checks for duplicate chunks. It is unlikely that we would
desire a chunk-based file format that allows duplicate chunk IDs in the
table of contents, so add duplicate checks into
read_table_of_contents().
Signed-off-by: Derrick Stolee <redacted>
---
chunk-format.c | 9 +++++++++
1 file changed, 9 insertions(+)
From: Derrick Stolee via GitGitGadget <hidden> Date: 2021-02-05 22:14:04
This is a restart on the topic previously submitted [1] but dropped because
ak/corrected-commit-date was still in progress. This version is based on
that branch.
[1]
https://lore.kernel.org/git/pull.804.git.1607012215.gitgitgadget@gmail.com/
This version also changes the approach to use a more dynamic interaction
with a struct chunkfile pointer. This idea is credited to Taylor Blau [2],
but I started again from scratch. I also go further to make struct chunkfile
anonymous to API consumers. It is defined only in chunk-format.c, which
should hopefully deter future users from interacting with that data
directly.
[2] https://lore.kernel.org/git/X8%2FI%2FRzXZksio+ri@nand.local/
This combined API is beneficial to reduce duplicated logic. Or rather, to
ensure that similar file formats have similar protections against bad data.
The multi-pack-index code did not have as many guards as the commit-graph
code did, but now they both share a common base that checks for things like
duplicate chunks or offsets outside the size of the file.
Here are some stats for the end-to-end change:
* 570 insertions(+), 456 deletions(-).
* commit-graph.c: 107 insertions(+), 192 deletions(-)
* midx.c: 164 insertions(+), 260 deletions(-)
While there is an overall increase to the code size, the consumers do get
smaller. Boilerplate things like abstracting method to match chunk_write_fn
and chunk_read_fn make up a lot of these insertions. The "interesting" code
gets a lot smaller and cleaner.
Updates in V3
=============
* API methods use better types and changed their order to match internal
data more closely.
* Use hashfile_total() instead of internal data values.
* The implementation of pair_chunk() uses read_chunk().
* init_chunkfile() has an in-code doc comment warning against using the
same struct chunkfile for reads and writes.
* More multiplications are correctly cast in midx.c.
* The chunk-format technical docs are expanded.
Updates in V2
=============
* The method pair_chunk() now automatically sets a pointer while
read_chunk() uses the callback. This greatly reduces the code size.
* Pointer casts are now implicit instead of explicit.
* Extra care is taken to not overflow when verifying chunk sizes on write.
Thanks, -Stolee
Derrick Stolee (17):
commit-graph: anonymize data in chunk_write_fn
chunk-format: create chunk format write API
commit-graph: use chunk-format write API
midx: rename pack_info to write_midx_context
midx: use context in write_midx_pack_names()
midx: add entries to write_midx_context
midx: add pack_perm to write_midx_context
midx: add num_large_offsets to write_midx_context
midx: return success/failure in chunk write methods
midx: drop chunk progress during write
midx: use chunk-format API in write_midx_internal()
chunk-format: create read chunk API
commit-graph: use chunk-format read API
midx: use chunk-format read API
midx: use 64-bit multiplication for chunk sizes
chunk-format: restore duplicate chunk checks
chunk-format: add technical docs
Documentation/technical/chunk-format.txt | 116 +++++
.../technical/commit-graph-format.txt | 3 +
Documentation/technical/pack-format.txt | 3 +
Makefile | 1 +
chunk-format.c | 180 ++++++++
chunk-format.h | 65 +++
commit-graph.c | 299 +++++-------
midx.c | 431 +++++++-----------
t/t5318-commit-graph.sh | 2 +-
t/t5319-multi-pack-index.sh | 6 +-
10 files changed, 648 insertions(+), 458 deletions(-)
create mode 100644 Documentation/technical/chunk-format.txt
create mode 100644 chunk-format.c
create mode 100644 chunk-format.h
base-commit: 5a3b130cad0d5c770f766e3af6d32b41766374c0
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-848%2Fderrickstolee%2Fchunk-format%2Frefactor-v3
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-848/derrickstolee/chunk-format/refactor-v3
Pull-Request: https://github.com/gitgitgadget/git/pull/848
Range-diff vs v2:
1: 243dcec94368 = 1: 243dcec94368 commit-graph: anonymize data in chunk_write_fn
2: 814512f21671 ! 2: 16c37d2370cf chunk-format: create chunk format write API
@@ Commit message
5. free the chunkfile struct using free_chunkfile().
Helped-by: Taylor Blau [off-list ref]
+ Helped-by: Junio C Hamano [off-list ref]
Signed-off-by: Derrick Stolee [off-list ref]
## Makefile ##
@@ chunk-format.c (new)
+}
+
+void add_chunk(struct chunkfile *cf,
-+ uint64_t id,
-+ chunk_write_fn fn,
-+ size_t size)
++ uint32_t id,
++ size_t size,
++ chunk_write_fn fn)
+{
+ ALLOC_GROW(cf->chunks, cf->chunks_nr + 1, cf->chunks_alloc);
+
@@ chunk-format.c (new)
+int write_chunkfile(struct chunkfile *cf, void *data)
+{
+ int i;
-+ size_t cur_offset = cf->f->offset + cf->f->total;
++ uint64_t cur_offset = hashfile_total(cf->f);
+
+ /* Add the table of contents to the current offset */
+ cur_offset += (cf->chunks_nr + 1) * CHUNK_LOOKUP_WIDTH;
@@ chunk-format.c (new)
+ hashwrite_be64(cf->f, cur_offset);
+
+ for (i = 0; i < cf->chunks_nr; i++) {
-+ uint64_t start_offset = cf->f->total + cf->f->offset;
++ off_t start_offset = hashfile_total(cf->f);
+ int result = cf->chunks[i].write_fn(cf->f, data);
+
+ if (result)
+ return result;
+
-+ if (cf->f->total + cf->f->offset - start_offset != cf->chunks[i].size)
++ if (hashfile_total(cf->f) - start_offset != cf->chunks[i].size)
+ BUG("expected to write %"PRId64" bytes to chunk %"PRIx32", but wrote %"PRId64" instead",
+ cf->chunks[i].size, cf->chunks[i].id,
-+ cf->f->total + cf->f->offset - start_offset);
++ hashfile_total(cf->f) - start_offset);
+ }
+
+ return 0;
@@ chunk-format.h (new)
+struct chunkfile *init_chunkfile(struct hashfile *f);
+void free_chunkfile(struct chunkfile *cf);
+int get_num_chunks(struct chunkfile *cf);
-+typedef int (*chunk_write_fn)(struct hashfile *f,
-+ void *data);
++typedef int (*chunk_write_fn)(struct hashfile *f, void *data);
+void add_chunk(struct chunkfile *cf,
-+ uint64_t id,
-+ chunk_write_fn fn,
-+ size_t size);
++ uint32_t id,
++ size_t size,
++ chunk_write_fn fn);
+int write_chunkfile(struct chunkfile *cf, void *data);
+
+#endif
3: 70af6e3083f4 ! 3: e549e24d79af commit-graph: use chunk-format write API
@@ commit-graph.c: static int write_commit_graph_file(struct write_commit_graph_con
- chunks[2].write_fn = write_graph_chunk_data;
+ cf = init_chunkfile(f);
+
-+ add_chunk(cf, GRAPH_CHUNKID_OIDFANOUT,
-+ write_graph_chunk_fanout, GRAPH_FANOUT_SIZE);
-+ add_chunk(cf, GRAPH_CHUNKID_OIDLOOKUP,
-+ write_graph_chunk_oids, hashsz * ctx->commits.nr);
-+ add_chunk(cf, GRAPH_CHUNKID_DATA,
-+ write_graph_chunk_data, (hashsz + 16) * ctx->commits.nr);
++ add_chunk(cf, GRAPH_CHUNKID_OIDFANOUT, GRAPH_FANOUT_SIZE,
++ write_graph_chunk_fanout);
++ add_chunk(cf, GRAPH_CHUNKID_OIDLOOKUP, hashsz * ctx->commits.nr,
++ write_graph_chunk_oids);
++ add_chunk(cf, GRAPH_CHUNKID_DATA, (hashsz + 16) * ctx->commits.nr,
++ write_graph_chunk_data);
if (git_env_bool(GIT_TEST_COMMIT_GRAPH_NO_GDAT, 0))
ctx->write_generation_data = 0;
@@ commit-graph.c: static int write_commit_graph_file(struct write_commit_graph_con
- }
+ if (ctx->write_generation_data)
+ add_chunk(cf, GRAPH_CHUNKID_GENERATION_DATA,
-+ write_graph_chunk_generation_data,
-+ sizeof(uint32_t) * ctx->commits.nr);
++ sizeof(uint32_t) * ctx->commits.nr,
++ write_graph_chunk_generation_data);
+ if (ctx->num_generation_data_overflows)
+ add_chunk(cf, GRAPH_CHUNKID_GENERATION_DATA_OVERFLOW,
-+ write_graph_chunk_generation_data_overflow,
-+ sizeof(timestamp_t) * ctx->num_generation_data_overflows);
++ sizeof(timestamp_t) * ctx->num_generation_data_overflows,
++ write_graph_chunk_generation_data_overflow);
+ if (ctx->num_extra_edges)
+ add_chunk(cf, GRAPH_CHUNKID_EXTRAEDGES,
-+ write_graph_chunk_extra_edges,
-+ 4 * ctx->num_extra_edges);
++ 4 * ctx->num_extra_edges,
++ write_graph_chunk_extra_edges);
if (ctx->changed_paths) {
- chunks[num_chunks].id = GRAPH_CHUNKID_BLOOMINDEXES;
- chunks[num_chunks].size = sizeof(uint32_t) * ctx->commits.nr;
@@ commit-graph.c: static int write_commit_graph_file(struct write_commit_graph_con
- chunks[num_chunks].id = 0;
- chunks[num_chunks].size = 0;
+ add_chunk(cf, GRAPH_CHUNKID_BLOOMINDEXES,
-+ write_graph_chunk_bloom_indexes,
-+ sizeof(uint32_t) * ctx->commits.nr);
++ sizeof(uint32_t) * ctx->commits.nr,
++ write_graph_chunk_bloom_indexes);
+ add_chunk(cf, GRAPH_CHUNKID_BLOOMDATA,
-+ write_graph_chunk_bloom_data,
+ sizeof(uint32_t) * 3
-+ + ctx->total_bloom_filter_data_size);
++ + ctx->total_bloom_filter_data_size,
++ write_graph_chunk_bloom_data);
+ }
+ if (ctx->num_commit_graphs_after > 1)
+ add_chunk(cf, GRAPH_CHUNKID_BASE,
-+ write_graph_chunk_base,
-+ hashsz * (ctx->num_commit_graphs_after - 1));
++ hashsz * (ctx->num_commit_graphs_after - 1),
++ write_graph_chunk_base);
hashwrite_be32(f, GRAPH_SIGNATURE);
4: 0cac7890bed7 = 4: 66ff49ed9309 midx: rename pack_info to write_midx_context
5: 4a4e90b129ae = 5: 1d7484c0cffa midx: use context in write_midx_pack_names()
6: 30ad423997b7 = 6: ea0e7d40e537 midx: add entries to write_midx_context
7: 2f1c496f3ab5 = 7: b283a38fb775 midx: add pack_perm to write_midx_context
8: c4939548e51c = 8: e7064512ab7f midx: add num_large_offsets to write_midx_context
9: b3cc73c22567 ! 9: 7aa3242e15b7 midx: return success/failure in chunk write methods
@@ midx.c: static int write_midx_internal(const char *object_dir, struct multi_pack
stop_progress(&progress);
- if (written != chunk_offsets[num_chunks])
-+ if (f->total + f->offset != chunk_offsets[num_chunks])
++ if (hashfile_total(f) != chunk_offsets[num_chunks])
BUG("incorrect final offset %"PRIu64" != %"PRIu64,
- written,
-+ f->total + f->offset,
++ hashfile_total(f),
chunk_offsets[num_chunks]);
finalize_hashfile(f, NULL, CSUM_FSYNC | CSUM_HASH_IN_STREAM);
10: 78744d3b7016 ! 10: 70f68c95e479 midx: drop chunk progress during write
@@ midx.c: static int write_midx_internal(const char *object_dir, struct multi_pack
}
- stop_progress(&progress);
- if (f->total + f->offset != chunk_offsets[num_chunks])
+ if (hashfile_total(f) != chunk_offsets[num_chunks])
BUG("incorrect final offset %"PRIu64" != %"PRIu64,
11: 07dc0cf8c683 ! 11: 787cd7f18d2e midx: use chunk-format API in write_midx_internal()
@@ midx.c: static int write_midx_internal(const char *object_dir, struct multi_pack
- case MIDX_CHUNKID_PACKNAMES:
- write_midx_pack_names(f, &ctx);
- break;
-+ add_chunk(cf, MIDX_CHUNKID_PACKNAMES,
-+ write_midx_pack_names, pack_name_concat_len);
-+ add_chunk(cf, MIDX_CHUNKID_OIDFANOUT,
-+ write_midx_oid_fanout, MIDX_CHUNK_FANOUT_SIZE);
++ add_chunk(cf, MIDX_CHUNKID_PACKNAMES, pack_name_concat_len,
++ write_midx_pack_names);
++ add_chunk(cf, MIDX_CHUNKID_OIDFANOUT, MIDX_CHUNK_FANOUT_SIZE,
++ write_midx_oid_fanout);
+ add_chunk(cf, MIDX_CHUNKID_OIDLOOKUP,
-+ write_midx_oid_lookup, ctx.entries_nr * the_hash_algo->rawsz);
++ ctx.entries_nr * the_hash_algo->rawsz,
++ write_midx_oid_lookup);
+ add_chunk(cf, MIDX_CHUNKID_OBJECTOFFSETS,
-+ write_midx_object_offsets,
-+ ctx.entries_nr * MIDX_CHUNK_OFFSET_WIDTH);
++ ctx.entries_nr * MIDX_CHUNK_OFFSET_WIDTH,
++ write_midx_object_offsets);
- case MIDX_CHUNKID_OIDFANOUT:
- write_midx_oid_fanout(f, &ctx);
@@ midx.c: static int write_midx_internal(const char *object_dir, struct multi_pack
- }
+ if (ctx.large_offsets_needed)
+ add_chunk(cf, MIDX_CHUNKID_LARGEOFFSETS,
-+ write_midx_large_offsets,
-+ ctx.num_large_offsets * MIDX_CHUNK_LARGE_OFFSET_WIDTH);
++ ctx.num_large_offsets * MIDX_CHUNK_LARGE_OFFSET_WIDTH,
++ write_midx_large_offsets);
-- if (f->total + f->offset != chunk_offsets[num_chunks])
+- if (hashfile_total(f) != chunk_offsets[num_chunks])
- BUG("incorrect final offset %"PRIu64" != %"PRIu64,
-- f->total + f->offset,
+- hashfile_total(f),
- chunk_offsets[num_chunks]);
+ write_midx_header(f, get_num_chunks(cf), ctx.nr - dropped_packs);
+ write_chunkfile(cf, &ctx);
12: d8d8e9e2aa3f ! 12: 366eb2afee83 chunk-format: create read chunk API
@@ Commit message
read. If the same struct instance was used for both reads and writes,
then there would be failures.
+ Helped-by: Junio C Hamano [off-list ref]
Signed-off-by: Derrick Stolee [off-list ref]
## chunk-format.c ##
@@ chunk-format.c: int write_chunkfile(struct chunkfile *cf, void *data)
+ return 0;
+}
+
++static int pair_chunk_fn(const unsigned char *chunk_start,
++ size_t chunk_size,
++ void *data)
++{
++ const unsigned char **p = data;
++ *p = chunk_start;
++ return 0;
++}
++
+int pair_chunk(struct chunkfile *cf,
+ uint32_t chunk_id,
+ const unsigned char **p)
+{
-+ int i;
-+
-+ for (i = 0; i < cf->chunks_nr; i++) {
-+ if (cf->chunks[i].id == chunk_id) {
-+ *p = cf->chunks[i].start;
-+ return 0;
-+ }
-+ }
-+
-+ return CHUNK_NOT_FOUND;
++ return read_chunk(cf, chunk_id, pair_chunk_fn, p);
+}
+
+int read_chunk(struct chunkfile *cf,
@@ chunk-format.c: int write_chunkfile(struct chunkfile *cf, void *data)
+}
## chunk-format.h ##
+@@
+ struct hashfile;
+ struct chunkfile;
+
++/*
++ * Initialize a 'struct chunkfile' for writing _or_ reading a file
++ * with the chunk format.
++ *
++ * If writing a file, supply a non-NULL 'struct hashfile *' that will
++ * be used to write.
++ *
++ * If reading a file, then supply the memory-mapped data to the
++ * pair_chunk() or read_chunk() methods, as appropriate.
++ *
++ * DO NOT MIX THESE MODES. Use different 'struct chunkfile' instances
++ * for reading and writing.
++ */
+ struct chunkfile *init_chunkfile(struct hashfile *f);
+ void free_chunkfile(struct chunkfile *cf);
+ int get_num_chunks(struct chunkfile *cf);
@@ chunk-format.h: void add_chunk(struct chunkfile *cf,
- size_t size);
+ chunk_write_fn fn);
int write_chunkfile(struct chunkfile *cf, void *data);
+int read_table_of_contents(struct chunkfile *cf,
13: 8744d2785965 = 13: 7838ad32e2e0 commit-graph: use chunk-format read API
14: 750c03253c95 ! 14: 6bddd9e63b9b midx: use chunk-format read API
@@ midx.c: struct multi_pack_index *load_multi_pack_index(const char *object_dir, i
m->num_objects = ntohl(m->chunk_oid_fanout[255]);
m->pack_names = xcalloc(m->num_packs, sizeof(*m->pack_names));
+@@ midx.c: struct multi_pack_index *load_multi_pack_index(const char *object_dir, int local
+ cleanup_fail:
+ free(m);
+ free(midx_name);
++ free(cf);
+ if (midx_map)
+ munmap(midx_map, midx_size);
+ if (0 <= fd)
## t/t5319-multi-pack-index.sh ##
@@ t/t5319-multi-pack-index.sh: test_expect_success 'verify bad OID version' '
15: 83d292532a0f ! 15: 3cd97f389f1f midx: use 64-bit multiplication for chunk sizes
@@ Commit message
multiplication always. This allows us to properly predict the chunk
sizes without risk of overflow.
+ Other possible overflows were discovered by evaluating each
+ multiplication in midx.c and ensuring that at least one side of the
+ operator was of type size_t or off_t.
+
Signed-off-by: Derrick Stolee [off-list ref]
## midx.c ##
+@@ midx.c: static off_t nth_midxed_offset(struct multi_pack_index *m, uint32_t pos)
+ const unsigned char *offset_data;
+ uint32_t offset32;
+
+- offset_data = m->chunk_object_offsets + pos * MIDX_CHUNK_OFFSET_WIDTH;
++ offset_data = m->chunk_object_offsets + (off_t)pos * MIDX_CHUNK_OFFSET_WIDTH;
+ offset32 = get_be32(offset_data + sizeof(uint32_t));
+
+ if (m->chunk_large_offsets && offset32 & MIDX_LARGE_OFFSET_NEEDED) {
+@@ midx.c: static off_t nth_midxed_offset(struct multi_pack_index *m, uint32_t pos)
+
+ static uint32_t nth_midxed_pack_int_id(struct multi_pack_index *m, uint32_t pos)
+ {
+- return get_be32(m->chunk_object_offsets + pos * MIDX_CHUNK_OFFSET_WIDTH);
++ return get_be32(m->chunk_object_offsets +
++ (off_t)pos * MIDX_CHUNK_OFFSET_WIDTH);
+ }
+
+ static int nth_midxed_pack_entry(struct repository *r,
@@ midx.c: static int write_midx_internal(const char *object_dir, struct multi_pack_index *
- add_chunk(cf, MIDX_CHUNKID_OIDFANOUT,
- write_midx_oid_fanout, MIDX_CHUNK_FANOUT_SIZE);
+ add_chunk(cf, MIDX_CHUNKID_OIDFANOUT, MIDX_CHUNK_FANOUT_SIZE,
+ write_midx_oid_fanout);
add_chunk(cf, MIDX_CHUNKID_OIDLOOKUP,
-- write_midx_oid_lookup, ctx.entries_nr * the_hash_algo->rawsz);
-+ write_midx_oid_lookup, (uint64_t)ctx.entries_nr * the_hash_algo->rawsz);
+- ctx.entries_nr * the_hash_algo->rawsz,
++ (size_t)ctx.entries_nr * the_hash_algo->rawsz,
+ write_midx_oid_lookup);
add_chunk(cf, MIDX_CHUNKID_OBJECTOFFSETS,
- write_midx_object_offsets,
- ctx.entries_nr * MIDX_CHUNK_OFFSET_WIDTH);
-@@ midx.c: static int write_midx_internal(const char *object_dir, struct multi_pack_index *
+- ctx.entries_nr * MIDX_CHUNK_OFFSET_WIDTH,
++ (size_t)ctx.entries_nr * MIDX_CHUNK_OFFSET_WIDTH,
+ write_midx_object_offsets);
+
if (ctx.large_offsets_needed)
add_chunk(cf, MIDX_CHUNKID_LARGEOFFSETS,
- write_midx_large_offsets,
-- ctx.num_large_offsets * MIDX_CHUNK_LARGE_OFFSET_WIDTH);
-+ (uint64_t)ctx.num_large_offsets * MIDX_CHUNK_LARGE_OFFSET_WIDTH);
+- ctx.num_large_offsets * MIDX_CHUNK_LARGE_OFFSET_WIDTH,
++ (size_t)ctx.num_large_offsets * MIDX_CHUNK_LARGE_OFFSET_WIDTH,
+ write_midx_large_offsets);
write_midx_header(f, get_num_chunks(cf), ctx.nr - dropped_packs);
- write_chunkfile(cf, &ctx);
16: 669eeec707ab ! 16: b9a1bddf615f chunk-format: restore duplicate chunk checks
@@ Commit message
Signed-off-by: Derrick Stolee [off-list ref]
## chunk-format.c ##
-@@ chunk-format.c: struct chunk_info {
- chunk_write_fn write_fn;
-
- const void *start;
-+ unsigned found:1;
- };
-
- struct chunkfile {
@@ chunk-format.c: int read_table_of_contents(struct chunkfile *cf,
uint64_t toc_offset,
int toc_length)
17: 8f3985ab5df3 ! 17: 4c7d751f1e39 chunk-format: add technical docs
@@ Documentation/technical/chunk-format.txt (new)
+
+Functions for working with chunk-based file formats are declared in
+`chunk-format.h`. Using these methods provide extra checks that assist
-+developers when creating new file formats, including:
++developers when creating new file formats.
+
-+ 1. Writing and reading the table of contents.
++Writing chunk-based file formats
++--------------------------------
+
-+ 2. Verifying that the data written in a chunk matches the expected size
-+ that was recorded in the table of contents.
++To write a chunk-based file format, create a `struct chunkfile` by
++calling `init_chunkfile()` and pass a `struct hashfile` pointer. The
++caller is responsible for opening the `hashfile` and writing header
++information so the file format is identifiable before the chunk-based
++format begins.
+
-+ 3. Checking that a table of contents describes offsets properly within
-+ the file boundaries.
++Then, call `add_chunk()` for each chunk that is intended for write. This
++populates the `chunkfile` with information about the order and size of
++each chunk to write. Provide a `chunk_write_fn` function pointer to
++perform the write of the chunk data upon request.
++
++Call `write_chunkfile()` to write the table of contents to the `hashfile`
++followed by each of the chunks. This will verify that each chunk wrote
++the expected amount of data so the table of contents is correct.
++
++Finally, call `free_chunkfile()` to clear the `struct chunkfile` data. The
++caller is responsible for finalizing the `hashfile` by writing the trailing
++hash and closing the file.
++
++Reading chunk-based file formats
++--------------------------------
++
++To read a chunk-based file format, the file must be opened as a
++memory-mapped region. The chunk-format API expects that the entire file
++is mapped as a contiguous memory region.
++
++Initialize a `struct chunkfile` pointer with `init_chunkfile(NULL)`.
++
++After reading the header information from the beginning of the file,
++including the chunk count, call `read_table_of_contents()` to populate
++the `struct chunkfile` with the list of chunks, their offsets, and their
++sizes.
++
++Extract the data information for each chunk using `pair_chunk()` or
++`read_chunk()`:
++
++* `pair_chunk()` assigns a given pointer with the location inside the
++ memory-mapped file corresponding to that chunk's offset. If the chunk
++ does not exist, then the pointer is not modified.
++
++* `read_chunk()` takes a `chunk_read_fn` function pointer and calls it
++ with the appropriate initial pointer and size information. The function
++ is not called if the chunk does not exist. Use this method to read chunks
++ if you need to perform immediate parsing or if you need to execute logic
++ based on the size of the chunk.
++
++After calling these methods, call `free_chunkfile()` to clear the
++`struct chunkfile` data. This will not close the memory-mapped region.
++Callers are expected to own that data for the timeframe the pointers into
++the region are needed.
++
++Examples
++--------
++
++These file formats use the chunk-format API, and can be used as examples
++for future formats:
++
++* *commit-graph:* see `write_commit_graph_file()` and `parse_commit_graph()`
++ in `commit-graph.c` for how the chunk-format API is used to write and
++ parse the commit-graph file format documented in
++ link:technical/commit-graph-format.html[the commit-graph file format].
++
++* *multi-pack-index:* see `write_midx_internal()` and `load_multi_pack_index()`
++ in `midx.c` for how the chunk-format API is used to write and
++ parse the multi-pack-index file format documented in
++ link:technical/pack-format.html[the multi-pack-index file format].
## Documentation/technical/commit-graph-format.txt ##
@@ Documentation/technical/commit-graph-format.txt: CHUNK LOOKUP:
--
gitgitgadget
From: Derrick Stolee via GitGitGadget <hidden> Date: 2021-02-05 22:16:39
From: Derrick Stolee <redacted>
Instead of parsing the table of contents directly, use the chunk-format
API methods read_table_of_contents() and pair_chunk(). While the current
implementation loses the duplicate-chunk detection, that will be added
in a future change.
Signed-off-by: Derrick Stolee <redacted>
---
commit-graph.c | 154 ++++++++++++++--------------------------
t/t5318-commit-graph.sh | 2 +-
2 files changed, 53 insertions(+), 103 deletions(-)
From: Derrick Stolee via GitGitGadget <hidden> Date: 2021-02-05 22:17:29
From: Derrick Stolee <redacted>
In preparation for creating an API around file formats using chunks and
tables of contents, prepare the commit-graph write code to use
prototypes that will match this new API.
Specifically, convert chunk_write_fn to take a "void *data" parameter
instead of the commit-graph-specific "struct write_commit_graph_context"
pointer.
Signed-off-by: Derrick Stolee <redacted>
---
commit-graph.c | 29 +++++++++++++++++++----------
1 file changed, 19 insertions(+), 10 deletions(-)
From: Derrick Stolee via GitGitGadget <hidden> Date: 2021-02-05 22:18:13
From: Derrick Stolee <redacted>
The commit-graph write logic is ready to make use of the chunk-format
write API. Each chunk write method is already in the correct prototype.
We only need to use the 'struct chunkfile' pointer and the correct API
calls.
Signed-off-by: Derrick Stolee <redacted>
---
commit-graph.c | 118 ++++++++++++++++---------------------------------
1 file changed, 37 insertions(+), 81 deletions(-)
@@ -1758,27 +1759,17 @@ static int write_graph_chunk_base(struct hashfile *f,return0;}-typedefint(*chunk_write_fn)(structhashfile*f,-void*data);--structchunk_info{-uint32_tid;-uint64_tsize;-chunk_write_fnwrite_fn;-};-staticintwrite_commit_graph_file(structwrite_commit_graph_context*ctx){uint32_ti;intfd;structhashfile*f;structlock_filelk=LOCK_INIT;-structchunk_infochunks[MAX_NUM_CHUNKS+1];constunsignedhashsz=the_hash_algo->rawsz;structstrbufprogress_title=STRBUF_INIT;intnum_chunks=3;-uint64_tchunk_offset;structobject_idfile_hash;+structchunkfile*cf;if(ctx->split){structstrbuftmp_file=STRBUF_INIT;
@@ -1824,76 +1815,50 @@ static int write_commit_graph_file(struct write_commit_graph_context *ctx)f=hashfd(lk.tempfile->fd,lk.tempfile->filename.buf);}-chunks[0].id=GRAPH_CHUNKID_OIDFANOUT;-chunks[0].size=GRAPH_FANOUT_SIZE;-chunks[0].write_fn=write_graph_chunk_fanout;-chunks[1].id=GRAPH_CHUNKID_OIDLOOKUP;-chunks[1].size=hashsz*ctx->commits.nr;-chunks[1].write_fn=write_graph_chunk_oids;-chunks[2].id=GRAPH_CHUNKID_DATA;-chunks[2].size=(hashsz+16)*ctx->commits.nr;-chunks[2].write_fn=write_graph_chunk_data;+cf=init_chunkfile(f);++add_chunk(cf,GRAPH_CHUNKID_OIDFANOUT,GRAPH_FANOUT_SIZE,+write_graph_chunk_fanout);+add_chunk(cf,GRAPH_CHUNKID_OIDLOOKUP,hashsz*ctx->commits.nr,+write_graph_chunk_oids);+add_chunk(cf,GRAPH_CHUNKID_DATA,(hashsz+16)*ctx->commits.nr,+write_graph_chunk_data);if(git_env_bool(GIT_TEST_COMMIT_GRAPH_NO_GDAT,0))ctx->write_generation_data=0;-if(ctx->write_generation_data){-chunks[num_chunks].id=GRAPH_CHUNKID_GENERATION_DATA;-chunks[num_chunks].size=sizeof(uint32_t)*ctx->commits.nr;-chunks[num_chunks].write_fn=write_graph_chunk_generation_data;-num_chunks++;-}-if(ctx->num_generation_data_overflows){-chunks[num_chunks].id=GRAPH_CHUNKID_GENERATION_DATA_OVERFLOW;-chunks[num_chunks].size=sizeof(timestamp_t)*ctx->num_generation_data_overflows;-chunks[num_chunks].write_fn=write_graph_chunk_generation_data_overflow;-num_chunks++;-}-if(ctx->num_extra_edges){-chunks[num_chunks].id=GRAPH_CHUNKID_EXTRAEDGES;-chunks[num_chunks].size=4*ctx->num_extra_edges;-chunks[num_chunks].write_fn=write_graph_chunk_extra_edges;-num_chunks++;-}+if(ctx->write_generation_data)+add_chunk(cf,GRAPH_CHUNKID_GENERATION_DATA,+sizeof(uint32_t)*ctx->commits.nr,+write_graph_chunk_generation_data);+if(ctx->num_generation_data_overflows)+add_chunk(cf,GRAPH_CHUNKID_GENERATION_DATA_OVERFLOW,+sizeof(timestamp_t)*ctx->num_generation_data_overflows,+write_graph_chunk_generation_data_overflow);+if(ctx->num_extra_edges)+add_chunk(cf,GRAPH_CHUNKID_EXTRAEDGES,+4*ctx->num_extra_edges,+write_graph_chunk_extra_edges);if(ctx->changed_paths){-chunks[num_chunks].id=GRAPH_CHUNKID_BLOOMINDEXES;-chunks[num_chunks].size=sizeof(uint32_t)*ctx->commits.nr;-chunks[num_chunks].write_fn=write_graph_chunk_bloom_indexes;-num_chunks++;-chunks[num_chunks].id=GRAPH_CHUNKID_BLOOMDATA;-chunks[num_chunks].size=sizeof(uint32_t)*3-+ctx->total_bloom_filter_data_size;-chunks[num_chunks].write_fn=write_graph_chunk_bloom_data;-num_chunks++;-}-if(ctx->num_commit_graphs_after>1){-chunks[num_chunks].id=GRAPH_CHUNKID_BASE;-chunks[num_chunks].size=hashsz*(ctx->num_commit_graphs_after-1);-chunks[num_chunks].write_fn=write_graph_chunk_base;-num_chunks++;-}--chunks[num_chunks].id=0;-chunks[num_chunks].size=0;+add_chunk(cf,GRAPH_CHUNKID_BLOOMINDEXES,+sizeof(uint32_t)*ctx->commits.nr,+write_graph_chunk_bloom_indexes);+add_chunk(cf,GRAPH_CHUNKID_BLOOMDATA,+sizeof(uint32_t)*3++ctx->total_bloom_filter_data_size,+write_graph_chunk_bloom_data);+}+if(ctx->num_commit_graphs_after>1)+add_chunk(cf,GRAPH_CHUNKID_BASE,+hashsz*(ctx->num_commit_graphs_after-1),+write_graph_chunk_base);hashwrite_be32(f,GRAPH_SIGNATURE);hashwrite_u8(f,GRAPH_VERSION);hashwrite_u8(f,oid_version());-hashwrite_u8(f,num_chunks);+hashwrite_u8(f,get_num_chunks(cf));hashwrite_u8(f,ctx->num_commit_graphs_after-1);-chunk_offset=8+(num_chunks+1)*GRAPH_CHUNKLOOKUP_WIDTH;-for(i=0;i<=num_chunks;i++){-uint32_tchunk_write[3];--chunk_write[0]=htonl(chunks[i].id);-chunk_write[1]=htonl(chunk_offset>>32);-chunk_write[2]=htonl(chunk_offset&0xffffffff);-hashwrite(f,chunk_write,12);--chunk_offset+=chunks[i].size;-}-if(ctx->report_progress){strbuf_addf(&progress_title,Q_("Writing out commit graph in %d pass",
@@ -1905,17 +1870,7 @@ static int write_commit_graph_file(struct write_commit_graph_context *ctx)num_chunks*ctx->commits.nr);}-for(i=0;i<num_chunks;i++){-uint64_tstart_offset=f->total+f->offset;--if(chunks[i].write_fn(f,ctx))-return-1;--if(f->total+f->offset!=start_offset+chunks[i].size)-BUG("expected to write %"PRId64" bytes to chunk %"PRIx32", but wrote %"PRId64" instead",-chunks[i].size,chunks[i].id,-f->total+f->offset-start_offset);-}+write_chunkfile(cf,ctx);stop_progress(&ctx->progress);strbuf_release(&progress_title);
@@ -1932,6 +1887,7 @@ static int write_commit_graph_file(struct write_commit_graph_context *ctx)close_commit_graph(ctx->r->objects);finalize_hashfile(f,file_hash.hash,CSUM_HASH_IN_STREAM|CSUM_FSYNC);+free_chunkfile(cf);if(ctx->split){FILE*chainf=fdopen_lock_file(&lk,"w");
From: Derrick Stolee via GitGitGadget <hidden> Date: 2021-02-05 22:18:15
From: Derrick Stolee <redacted>
In an effort to streamline our chunk-based file formats, align some of
the code structure in write_midx_internal() to be similar to the
patterns in write_commit_graph_file().
Specifically, let's create a "struct write_midx_context" that can be
used as a data parameter to abstract function types.
This change only renames "struct pack_info" to "struct
write_midx_context" and the names of instances from "packs" to "ctx". In
future changes, we will expand the data inside "struct
write_midx_context" and align our chunk-writing method with the
chunk-format API.
Signed-off-by: Derrick Stolee <redacted>
---
midx.c | 130 ++++++++++++++++++++++++++++-----------------------------
1 file changed, 65 insertions(+), 65 deletions(-)
@@ -463,37 +463,37 @@ struct pack_list {staticvoidadd_pack_to_midx(constchar*full_path,size_tfull_path_len,constchar*file_name,void*data){-structpack_list*packs=(structpack_list*)data;+structwrite_midx_context*ctx=data;if(ends_with(file_name,".idx")){-display_progress(packs->progress,++packs->pack_paths_checked);-if(packs->m&&midx_contains_pack(packs->m,file_name))+display_progress(ctx->progress,++ctx->pack_paths_checked);+if(ctx->m&&midx_contains_pack(ctx->m,file_name))return;-ALLOC_GROW(packs->info,packs->nr+1,packs->alloc);+ALLOC_GROW(ctx->info,ctx->nr+1,ctx->alloc);-packs->info[packs->nr].p=add_packed_git(full_path,-full_path_len,-0);+ctx->info[ctx->nr].p=add_packed_git(full_path,+full_path_len,+0);-if(!packs->info[packs->nr].p){+if(!ctx->info[ctx->nr].p){warning(_("failed to add packfile '%s'"),full_path);return;}-if(open_pack_index(packs->info[packs->nr].p)){+if(open_pack_index(ctx->info[ctx->nr].p)){warning(_("failed to open pack-index '%s'"),full_path);-close_pack(packs->info[packs->nr].p);-FREE_AND_NULL(packs->info[packs->nr].p);+close_pack(ctx->info[ctx->nr].p);+FREE_AND_NULL(ctx->info[ctx->nr].p);return;}-packs->info[packs->nr].pack_name=xstrdup(file_name);-packs->info[packs->nr].orig_pack_int_id=packs->nr;-packs->info[packs->nr].expired=0;-packs->nr++;+ctx->info[ctx->nr].pack_name=xstrdup(file_name);+ctx->info[ctx->nr].orig_pack_int_id=ctx->nr;+ctx->info[ctx->nr].expired=0;+ctx->nr++;}}
@@ -820,40 +820,40 @@ static int write_midx_internal(const char *object_dir, struct multi_pack_index *midx_name);if(m)-packs.m=m;+ctx.m=m;else-packs.m=load_multi_pack_index(object_dir,1);--packs.nr=0;-packs.alloc=packs.m?packs.m->num_packs:16;-packs.info=NULL;-ALLOC_ARRAY(packs.info,packs.alloc);--if(packs.m){-for(i=0;i<packs.m->num_packs;i++){-ALLOC_GROW(packs.info,packs.nr+1,packs.alloc);--packs.info[packs.nr].orig_pack_int_id=i;-packs.info[packs.nr].pack_name=xstrdup(packs.m->pack_names[i]);-packs.info[packs.nr].p=NULL;-packs.info[packs.nr].expired=0;-packs.nr++;+ctx.m=load_multi_pack_index(object_dir,1);++ctx.nr=0;+ctx.alloc=ctx.m?ctx.m->num_packs:16;+ctx.info=NULL;+ALLOC_ARRAY(ctx.info,ctx.alloc);++if(ctx.m){+for(i=0;i<ctx.m->num_packs;i++){+ALLOC_GROW(ctx.info,ctx.nr+1,ctx.alloc);++ctx.info[ctx.nr].orig_pack_int_id=i;+ctx.info[ctx.nr].pack_name=xstrdup(ctx.m->pack_names[i]);+ctx.info[ctx.nr].p=NULL;+ctx.info[ctx.nr].expired=0;+ctx.nr++;}}-packs.pack_paths_checked=0;+ctx.pack_paths_checked=0;if(flags&MIDX_PROGRESS)-packs.progress=start_delayed_progress(_("Adding packfiles to multi-pack-index"),0);+ctx.progress=start_delayed_progress(_("Adding packfiles to multi-pack-index"),0);else-packs.progress=NULL;+ctx.progress=NULL;-for_each_file_in_pack_dir(object_dir,add_pack_to_midx,&packs);-stop_progress(&packs.progress);+for_each_file_in_pack_dir(object_dir,add_pack_to_midx,&ctx);+stop_progress(&ctx.progress);-if(packs.m&&packs.nr==packs.m->num_packs&&!packs_to_drop)+if(ctx.m&&ctx.nr==ctx.m->num_packs&&!packs_to_drop)gotocleanup;-entries=get_sorted_entries(packs.m,packs.info,packs.nr,&nr_entries);+entries=get_sorted_entries(ctx.m,ctx.info,ctx.nr,&nr_entries);for(i=0;i<nr_entries;i++){if(entries[i].offset>0x7fffffff)
@@ -862,19 +862,19 @@ static int write_midx_internal(const char *object_dir, struct multi_pack_index *large_offsets_needed=1;}-QSORT(packs.info,packs.nr,pack_info_compare);+QSORT(ctx.info,ctx.nr,pack_info_compare);if(packs_to_drop&&packs_to_drop->nr){intdrop_index=0;intmissing_drops=0;-for(i=0;i<packs.nr&&drop_index<packs_to_drop->nr;i++){-intcmp=strcmp(packs.info[i].pack_name,+for(i=0;i<ctx.nr&&drop_index<packs_to_drop->nr;i++){+intcmp=strcmp(ctx.info[i].pack_name,packs_to_drop->items[drop_index].string);if(!cmp){drop_index++;-packs.info[i].expired=1;+ctx.info[i].expired=1;}elseif(cmp>0){error(_("did not see pack-file %s to drop"),packs_to_drop->items[drop_index].string);
From: Derrick Stolee via GitGitGadget <hidden> Date: 2021-02-05 22:18:15
From: Derrick Stolee <redacted>
The chunk-format API allows writing the table of contents and all chunks
using the anonymous 'struct chunkfile' type. We only need to convert our
local chunk logic to this API for the multi-pack-index writes to share
that logic with the commit-graph file writes.
Signed-off-by: Derrick Stolee <redacted>
---
midx.c | 105 +++++++++++----------------------------------------------
1 file changed, 20 insertions(+), 85 deletions(-)
@@ -799,18 +800,15 @@ static int write_midx_large_offsets(struct hashfile *f,staticintwrite_midx_internal(constchar*object_dir,structmulti_pack_index*m,structstring_list*packs_to_drop,unsignedflags){-unsignedcharcur_chunk,num_chunks=0;char*midx_name;uint32_ti;structhashfile*f=NULL;structlock_filelk;structwrite_midx_contextctx={0};-uint64_theader_size=0;-uint32_tchunk_ids[MIDX_MAX_CHUNKS+1];-uint64_tchunk_offsets[MIDX_MAX_CHUNKS+1];intpack_name_concat_len=0;intdropped_packs=0;intresult=0;+structchunkfile*cf;midx_name=get_midx_filename(object_dir);if(safe_create_leading_directories(midx_name))
@@ -923,98 +921,35 @@ static int write_midx_internal(const char *object_dir, struct multi_pack_index *if(ctx.m)close_midx(ctx.m);-cur_chunk=0;-num_chunks=ctx.large_offsets_needed?5:4;-if(ctx.nr-dropped_packs==0){error(_("no pack files to index."));result=1;gotocleanup;}-header_size=write_midx_header(f,num_chunks,ctx.nr-dropped_packs);--chunk_ids[cur_chunk]=MIDX_CHUNKID_PACKNAMES;-chunk_offsets[cur_chunk]=header_size+(num_chunks+1)*MIDX_CHUNKLOOKUP_WIDTH;--cur_chunk++;-chunk_ids[cur_chunk]=MIDX_CHUNKID_OIDFANOUT;-chunk_offsets[cur_chunk]=chunk_offsets[cur_chunk-1]+pack_name_concat_len;--cur_chunk++;-chunk_ids[cur_chunk]=MIDX_CHUNKID_OIDLOOKUP;-chunk_offsets[cur_chunk]=chunk_offsets[cur_chunk-1]+MIDX_CHUNK_FANOUT_SIZE;--cur_chunk++;-chunk_ids[cur_chunk]=MIDX_CHUNKID_OBJECTOFFSETS;-chunk_offsets[cur_chunk]=chunk_offsets[cur_chunk-1]+ctx.entries_nr*the_hash_algo->rawsz;--cur_chunk++;-chunk_offsets[cur_chunk]=chunk_offsets[cur_chunk-1]+ctx.entries_nr*MIDX_CHUNK_OFFSET_WIDTH;-if(ctx.large_offsets_needed){-chunk_ids[cur_chunk]=MIDX_CHUNKID_LARGEOFFSETS;--cur_chunk++;-chunk_offsets[cur_chunk]=chunk_offsets[cur_chunk-1]+-ctx.num_large_offsets*MIDX_CHUNK_LARGE_OFFSET_WIDTH;-}--chunk_ids[cur_chunk]=0;--for(i=0;i<=num_chunks;i++){-if(i&&chunk_offsets[i]<chunk_offsets[i-1])-BUG("incorrect chunk offsets: %"PRIu64" before %"PRIu64,-chunk_offsets[i-1],-chunk_offsets[i]);--if(chunk_offsets[i]%MIDX_CHUNK_ALIGNMENT)-BUG("chunk offset %"PRIu64" is not properly aligned",-chunk_offsets[i]);--hashwrite_be32(f,chunk_ids[i]);-hashwrite_be64(f,chunk_offsets[i]);-}--for(i=0;i<num_chunks;i++){-if(f->total+f->offset!=chunk_offsets[i])-BUG("incorrect chunk offset (%"PRIu64" != %"PRIu64") for chunk id %"PRIx32,-chunk_offsets[i],-f->total+f->offset,-chunk_ids[i]);+cf=init_chunkfile(f);-switch(chunk_ids[i]){-caseMIDX_CHUNKID_PACKNAMES:-write_midx_pack_names(f,&ctx);-break;+add_chunk(cf,MIDX_CHUNKID_PACKNAMES,pack_name_concat_len,+write_midx_pack_names);+add_chunk(cf,MIDX_CHUNKID_OIDFANOUT,MIDX_CHUNK_FANOUT_SIZE,+write_midx_oid_fanout);+add_chunk(cf,MIDX_CHUNKID_OIDLOOKUP,+ctx.entries_nr*the_hash_algo->rawsz,+write_midx_oid_lookup);+add_chunk(cf,MIDX_CHUNKID_OBJECTOFFSETS,+ctx.entries_nr*MIDX_CHUNK_OFFSET_WIDTH,+write_midx_object_offsets);-caseMIDX_CHUNKID_OIDFANOUT:-write_midx_oid_fanout(f,&ctx);-break;--caseMIDX_CHUNKID_OIDLOOKUP:-write_midx_oid_lookup(f,&ctx);-break;--caseMIDX_CHUNKID_OBJECTOFFSETS:-write_midx_object_offsets(f,&ctx);-break;--caseMIDX_CHUNKID_LARGEOFFSETS:-write_midx_large_offsets(f,&ctx);-break;--default:-BUG("trying to write unknown chunk id %"PRIx32,-chunk_ids[i]);-}-}+if(ctx.large_offsets_needed)+add_chunk(cf,MIDX_CHUNKID_LARGEOFFSETS,+ctx.num_large_offsets*MIDX_CHUNK_LARGE_OFFSET_WIDTH,+write_midx_large_offsets);-if(hashfile_total(f)!=chunk_offsets[num_chunks])-BUG("incorrect final offset %"PRIu64" != %"PRIu64,-hashfile_total(f),-chunk_offsets[num_chunks]);+write_midx_header(f,get_num_chunks(cf),ctx.nr-dropped_packs);+write_chunkfile(cf,&ctx);finalize_hashfile(f,NULL,CSUM_FSYNC|CSUM_HASH_IN_STREAM);+free_chunkfile(cf);commit_lock_file(&lk);cleanup:
From: Derrick Stolee via GitGitGadget <hidden> Date: 2021-02-05 22:24:54
From: Derrick Stolee <redacted>
Add the capability to read the table of contents, then pair the chunks
with necessary logic using read_chunk_fn pointers. Callers will be added
in future changes, but the typical outline will be:
1. initialize a 'struct chunkfile' with init_chunkfile(NULL).
2. call read_table_of_contents().
3. for each chunk to parse,
a. call pair_chunk() to assign a pointer with the chunk position, or
b. call read_chunk() to run a callback on the chunk start and size.
4. call free_chunkfile() to clear the 'struct chunkfile' data.
We are re-using the anonymous 'struct chunkfile' data, as it is internal
to the chunk-format API. This gives it essentially two modes: write and
read. If the same struct instance was used for both reads and writes,
then there would be failures.
Helped-by: Junio C Hamano [off-list ref]
Signed-off-by: Derrick Stolee <redacted>
---
chunk-format.c | 80 ++++++++++++++++++++++++++++++++++++++++++++++++++
chunk-format.h | 46 +++++++++++++++++++++++++++++
2 files changed, 126 insertions(+)
@@ -89,3 +91,81 @@ int write_chunkfile(struct chunkfile *cf, void *data)return0;}++intread_table_of_contents(structchunkfile*cf,+constunsignedchar*mfile,+size_tmfile_size,+uint64_ttoc_offset,+inttoc_length)+{+uint32_tchunk_id;+constunsignedchar*table_of_contents=mfile+toc_offset;++ALLOC_GROW(cf->chunks,toc_length,cf->chunks_alloc);++while(toc_length--){+uint64_tchunk_offset,next_chunk_offset;++chunk_id=get_be32(table_of_contents);+chunk_offset=get_be64(table_of_contents+4);++if(!chunk_id){+error(_("terminating chunk id appears earlier than expected"));+return1;+}++table_of_contents+=CHUNK_LOOKUP_WIDTH;+next_chunk_offset=get_be64(table_of_contents+4);++if(next_chunk_offset<chunk_offset||+next_chunk_offset>mfile_size-the_hash_algo->rawsz){+error(_("improper chunk offset(s) %"PRIx64" and %"PRIx64""),+chunk_offset,next_chunk_offset);+return-1;+}++cf->chunks[cf->chunks_nr].id=chunk_id;+cf->chunks[cf->chunks_nr].start=mfile+chunk_offset;+cf->chunks[cf->chunks_nr].size=next_chunk_offset-chunk_offset;+cf->chunks_nr++;+}++chunk_id=get_be32(table_of_contents);+if(chunk_id){+error(_("final chunk has non-zero id %"PRIx32""),chunk_id);+return-1;+}++return0;+}++staticintpair_chunk_fn(constunsignedchar*chunk_start,+size_tchunk_size,+void*data)+{+constunsignedchar**p=data;+*p=chunk_start;+return0;+}++intpair_chunk(structchunkfile*cf,+uint32_tchunk_id,+constunsignedchar**p)+{+returnread_chunk(cf,chunk_id,pair_chunk_fn,p);+}++intread_chunk(structchunkfile*cf,+uint32_tchunk_id,+chunk_read_fnfn,+void*data)+{+inti;++for(i=0;i<cf->chunks_nr;i++){+if(cf->chunks[i].id==chunk_id)+returnfn(cf->chunks[i].start,cf->chunks[i].size,data);+}++returnCHUNK_NOT_FOUND;+}
From: SZEDER Gábor <hidden> Date: 2021-02-07 20:21:28
On Fri, Feb 05, 2021 at 02:30:47PM +0000, Derrick Stolee via GitGitGadget wrote:
From: Derrick Stolee <redacted>
Add the capability to read the table of contents, then pair the chunks
with necessary logic using read_chunk_fn pointers. Callers will be added
in future changes, but the typical outline will be:
1. initialize a 'struct chunkfile' with init_chunkfile(NULL).
2. call read_table_of_contents().
A reader should call read_table_of_contents(), noted.
3. for each chunk to parse,
a. call pair_chunk() to assign a pointer with the chunk position, or
b. call read_chunk() to run a callback on the chunk start and size.
4. call free_chunkfile() to clear the 'struct chunkfile' data.
How could a user of this API learn about all chunks present in the
chunkfile, including unrecognized chunks?
We are re-using the anonymous 'struct chunkfile' data, as it is internal
to the chunk-format API. This gives it essentially two modes: write and
read. If the same struct instance was used for both reads and writes,
then there would be failures.
Helped-by: Junio C Hamano [off-list ref]
Signed-off-by: Derrick Stolee <redacted>
+ *
+ * DO NOT MIX THESE MODES. Use different 'struct chunkfile' instances
+ * for reading and writing.
+ */
struct chunkfile *init_chunkfile(struct hashfile *f);
void free_chunkfile(struct chunkfile *cf);
int get_num_chunks(struct chunkfile *cf);
@@ -16,4 +29,37 @@ void add_chunk(struct chunkfile *cf, chunk_write_fn fn); int write_chunkfile(struct chunkfile *cf, void *data);+int read_table_of_contents(struct chunkfile *cf,+ const unsigned char *mfile,+ size_t mfile_size,+ uint64_t toc_offset,+ int toc_length);++#define CHUNK_NOT_FOUND (-2)++/*+ * Find 'chunk_id' in the given chunkfile and assign the+ * given pointer to the position in the mmap'd file where+ * that chunk begins.+ *+ * Returns CHUNK_NOT_FOUND if the chunk does not exist.+ */+int pair_chunk(struct chunkfile *cf,+ uint32_t chunk_id,+ const unsigned char **p);++typedef int (*chunk_read_fn)(const unsigned char *chunk_start,+ size_t chunk_size, void *data);+/*+ * Find 'chunk_id' in the given chunkfile and call the+ * given chunk_read_fn method with the information for+ * that chunk.+ *+ * Returns CHUNK_NOT_FOUND if the chunk does not exist.+ */+int read_chunk(struct chunkfile *cf,+ uint32_t chunk_id,+ chunk_read_fn fn,+ void *data);+ #endif
As this macro is defined in 'chunk-format.c' it's not part of the
chunkfile API. However, at the end of this patch series
'commit-graph.c' still contains:
#define GRAPH_CHUNKLOOKUP_WIDTH 12
and uses it in a couple of safety checks (that didn't became part of
the common chunkfile module; why?), while 'midx.c' contains:
#define MIDX_CHUNKLOOKUP_WIDTH (sizeof(uint32_t) + sizeof(uint64_t))
though it's not used anymore.
I think we should have only one such constant as part of the chunkfile
API; and preferably use the definition from 'midx.c' as it is more
informative than yet another magic number.
Furthermore, being called 'CHUNK_LOOKUP_WIDTH', I had to look up the
places where this constant is used to make sure that it indeed means
what I suspect it means. Perhaps CHUNK_TOC_ENTRY_SIZE would be a more
descriptive name for this constant.
On a somewhat related note: 'commit-graph.c' and 'midx.c' still
contains the constants MAX_NUM_CHUNKS and MIDX_MAX_CHUNKS,
respecticely, but neither of them is used anymore.
On Fri, Feb 05, 2021 at 02:30:47PM +0000, Derrick Stolee via GitGitGadget wrote:
quoted
From: Derrick Stolee <redacted>
Add the capability to read the table of contents, then pair the chunks
with necessary logic using read_chunk_fn pointers. Callers will be added
in future changes, but the typical outline will be:
1. initialize a 'struct chunkfile' with init_chunkfile(NULL).
2. call read_table_of_contents().
A reader should call read_table_of_contents(), noted.
quoted
3. for each chunk to parse,
a. call pair_chunk() to assign a pointer with the chunk position, or
b. call read_chunk() to run a callback on the chunk start and size.
4. call free_chunkfile() to clear the 'struct chunkfile' data.
How could a user of this API learn about all chunks present in the
chunkfile, including unrecognized chunks?
That could certainly be added (when needed) without modifying the data
structures.
quoted
+/*
+ * Initialize a 'struct chunkfile' for writing _or_ reading a file
+ * with the chunk format.
+ *
+ * If writing a file, supply a non-NULL 'struct hashfile *' that will
+ * be used to write.
+ *
+ * If reading a file, then supply the memory-mapped data to the
+ * pair_chunk() or read_chunk() methods, as appropriate.
As this macro is defined in 'chunk-format.c' it's not part of the
chunkfile API. However, at the end of this patch series
'commit-graph.c' still contains:
#define GRAPH_CHUNKLOOKUP_WIDTH 12
and uses it in a couple of safety checks (that didn't became part of
the common chunkfile module; why?),
Chunk-based files don't have a minimum size unless we know the header
size and a minimum number of required chunks. I suppose that we could
add this in the future to further simplify consumers of the API.
while 'midx.c' contains:
#define MIDX_CHUNKLOOKUP_WIDTH (sizeof(uint32_t) + sizeof(uint64_t))
though it's not used anymore.
I think we should have only one such constant as part of the chunkfile
API; and preferably use the definition from 'midx.c' as it is more
informative than yet another magic number.
Furthermore, being called 'CHUNK_LOOKUP_WIDTH', I had to look up the
places where this constant is used to make sure that it indeed means
what I suspect it means. Perhaps CHUNK_TOC_ENTRY_SIZE would be a more
descriptive name for this constant.
More descriptive, for sure.
On a somewhat related note: 'commit-graph.c' and 'midx.c' still
contains the constants MAX_NUM_CHUNKS and MIDX_MAX_CHUNKS,
respecticely, but neither of them is used anymore.
Thanks. The following patch can be added on top of this series
to clean up these dangling macros.
Thanks,
-Stolee
--- >8 ---
From 839b880ccee65eac63e8b77b12fab6531acc55b0 Mon Sep 17 00:00:00 2001
From: Derrick Stolee <redacted>
Date: Mon, 8 Feb 2021 08:38:47 -0500
Subject: [PATCH] chunk-format: remove outdated macro constants
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit
The following macros were needed by midx.c and commit-graph.c to handle
their independent implementations of the chunk-based file format, but
now the chunk-format API makes them obsolete:
* MAX_NUM_CHUNKS
* MIDX_MAX_CHUNKS
* MIX_CHUNKLOOKUP_WIDTH
Reported-by: SZEDER Gábor <redacted>
Signed-off-by: Derrick Stolee <redacted>
---
commit-graph.c | 1 -
midx.c | 2 --
2 files changed, 3 deletions(-)
From: SZEDER Gábor <hidden> Date: 2021-02-11 19:44:14
On Mon, Feb 08, 2021 at 08:44:06AM -0500, Derrick Stolee wrote:
On 2/7/2021 4:13 PM, SZEDER Gábor wrote:
quoted
quoted
+#define CHUNK_LOOKUP_WIDTH 12
As this macro is defined in 'chunk-format.c' it's not part of the
chunkfile API. However, at the end of this patch series
'commit-graph.c' still contains:
#define GRAPH_CHUNKLOOKUP_WIDTH 12
and uses it in a couple of safety checks (that didn't became part of
the common chunkfile module; why?),
Chunk-based files don't have a minimum size unless we know the header
size and a minimum number of required chunks. I suppose that we could
add this in the future to further simplify consumers of the API.
quoted
while 'midx.c' contains:
#define MIDX_CHUNKLOOKUP_WIDTH (sizeof(uint32_t) + sizeof(uint64_t))
though it's not used anymore.
I think we should have only one such constant as part of the chunkfile
API; and preferably use the definition from 'midx.c' as it is more
informative than yet another magic number.
Furthermore, being called 'CHUNK_LOOKUP_WIDTH', I had to look up the
places where this constant is used to make sure that it indeed means
what I suspect it means. Perhaps CHUNK_TOC_ENTRY_SIZE would be a more
descriptive name for this constant.
More descriptive, for sure.
quoted
On a somewhat related note: 'commit-graph.c' and 'midx.c' still
contains the constants MAX_NUM_CHUNKS and MIDX_MAX_CHUNKS,
respecticely, but neither of them is used anymore.
Thanks. The following patch can be added on top of this series
to clean up these dangling macros.
It would be better to squash this into the patches that removed the
last uses of each of those constants.
And it still leaves the magic number '12' duplicated in
'commit-graph.c' and 'chunk-format.c'.
quoted hunk
Thanks,
-Stolee
--- >8 ---
From 839b880ccee65eac63e8b77b12fab6531acc55b0 Mon Sep 17 00:00:00 2001
From: Derrick Stolee <redacted>
Date: Mon, 8 Feb 2021 08:38:47 -0500
Subject: [PATCH] chunk-format: remove outdated macro constants
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit
The following macros were needed by midx.c and commit-graph.c to handle
their independent implementations of the chunk-based file format, but
now the chunk-format API makes them obsolete:
* MAX_NUM_CHUNKS
* MIDX_MAX_CHUNKS
* MIX_CHUNKLOOKUP_WIDTH
Reported-by: SZEDER Gábor <redacted>
Signed-off-by: Derrick Stolee <redacted>
---
commit-graph.c | 1 -
midx.c | 2 --
2 files changed, 3 deletions(-)
From: Derrick Stolee via GitGitGadget <hidden> Date: 2021-02-18 16:45:15
From: Derrick Stolee <redacted>
In an effort to align write_midx_internal() with the chunk-format API,
continue to group necessary data into "struct write_midx_context". This
change collects the "uint32_t *pack_perm" and large_offsets_needed bit
into the context.
Update write_midx_object_offsets() to match chunk_write_fn.
Signed-off-by: Derrick Stolee <redacted>
---
midx.c | 40 +++++++++++++++++++++-------------------
1 file changed, 21 insertions(+), 19 deletions(-)
@@ -736,27 +739,27 @@ static size_t write_midx_oid_lookup(struct hashfile *f,returnwritten;}-staticsize_twrite_midx_object_offsets(structhashfile*f,intlarge_offset_needed,-uint32_t*perm,-structpack_midx_entry*objects,uint32_tnr_objects)+staticsize_twrite_midx_object_offsets(structhashfile*f,+void*data){-structpack_midx_entry*list=objects;+structwrite_midx_context*ctx=data;+structpack_midx_entry*list=ctx->entries;uint32_ti,nr_large_offset=0;size_twritten=0;-for(i=0;i<nr_objects;i++){+for(i=0;i<ctx->entries_nr;i++){structpack_midx_entry*obj=list++;-if(perm[obj->pack_int_id]==PACK_EXPIRED)+if(ctx->pack_perm[obj->pack_int_id]==PACK_EXPIRED)BUG("object %s is in an expired pack with int-id %d",oid_to_hex(&obj->oid),obj->pack_int_id);-hashwrite_be32(f,perm[obj->pack_int_id]);+hashwrite_be32(f,ctx->pack_perm[obj->pack_int_id]);-if(large_offset_needed&&obj->offset>>31)+if(ctx->large_offsets_needed&&obj->offset>>31)hashwrite_be32(f,MIDX_LARGE_OFFSET_NEEDED|nr_large_offset++);-elseif(!large_offset_needed&&obj->offset>>32)+elseif(!ctx->large_offsets_needed&&obj->offset>>32)BUG("object %s requires a large offset (%"PRIx64") but the MIDX is not writing large offsets!",oid_to_hex(&obj->oid),obj->offset);
From: Derrick Stolee via GitGitGadget <hidden> Date: 2021-02-18 16:45:15
From: Derrick Stolee <redacted>
In an effort to align the write_midx_internal() to use the chunk-format
API, start converting chunk writing methods to match chunk_write_fn. The
first case is to convert write_midx_pack_names() to take "void *data".
We already have the necessary data in "struct write_midx_context", so
this conversion is rather mechanical.
Signed-off-by: Derrick Stolee <redacted>
---
midx.c | 21 ++++++++++-----------
1 file changed, 10 insertions(+), 11 deletions(-)
From: Derrick Stolee via GitGitGadget <hidden> Date: 2021-02-18 16:45:16
From: Derrick Stolee <redacted>
The commit-graph write logic is ready to make use of the chunk-format
write API. Each chunk write method is already in the correct prototype.
We only need to use the 'struct chunkfile' pointer and the correct API
calls.
Signed-off-by: Derrick Stolee <redacted>
---
commit-graph.c | 119 +++++++++++++++----------------------------------
1 file changed, 37 insertions(+), 82 deletions(-)
@@ -1758,27 +1758,17 @@ static int write_graph_chunk_base(struct hashfile *f,return0;}-typedefint(*chunk_write_fn)(structhashfile*f,-void*data);--structchunk_info{-uint32_tid;-uint64_tsize;-chunk_write_fnwrite_fn;-};-staticintwrite_commit_graph_file(structwrite_commit_graph_context*ctx){uint32_ti;intfd;structhashfile*f;structlock_filelk=LOCK_INIT;-structchunk_infochunks[MAX_NUM_CHUNKS+1];constunsignedhashsz=the_hash_algo->rawsz;structstrbufprogress_title=STRBUF_INIT;intnum_chunks=3;-uint64_tchunk_offset;structobject_idfile_hash;+structchunkfile*cf;if(ctx->split){structstrbuftmp_file=STRBUF_INIT;
@@ -1824,76 +1814,50 @@ static int write_commit_graph_file(struct write_commit_graph_context *ctx)f=hashfd(lk.tempfile->fd,lk.tempfile->filename.buf);}-chunks[0].id=GRAPH_CHUNKID_OIDFANOUT;-chunks[0].size=GRAPH_FANOUT_SIZE;-chunks[0].write_fn=write_graph_chunk_fanout;-chunks[1].id=GRAPH_CHUNKID_OIDLOOKUP;-chunks[1].size=hashsz*ctx->commits.nr;-chunks[1].write_fn=write_graph_chunk_oids;-chunks[2].id=GRAPH_CHUNKID_DATA;-chunks[2].size=(hashsz+16)*ctx->commits.nr;-chunks[2].write_fn=write_graph_chunk_data;+cf=init_chunkfile(f);++add_chunk(cf,GRAPH_CHUNKID_OIDFANOUT,GRAPH_FANOUT_SIZE,+write_graph_chunk_fanout);+add_chunk(cf,GRAPH_CHUNKID_OIDLOOKUP,hashsz*ctx->commits.nr,+write_graph_chunk_oids);+add_chunk(cf,GRAPH_CHUNKID_DATA,(hashsz+16)*ctx->commits.nr,+write_graph_chunk_data);if(git_env_bool(GIT_TEST_COMMIT_GRAPH_NO_GDAT,0))ctx->write_generation_data=0;-if(ctx->write_generation_data){-chunks[num_chunks].id=GRAPH_CHUNKID_GENERATION_DATA;-chunks[num_chunks].size=sizeof(uint32_t)*ctx->commits.nr;-chunks[num_chunks].write_fn=write_graph_chunk_generation_data;-num_chunks++;-}-if(ctx->num_generation_data_overflows){-chunks[num_chunks].id=GRAPH_CHUNKID_GENERATION_DATA_OVERFLOW;-chunks[num_chunks].size=sizeof(timestamp_t)*ctx->num_generation_data_overflows;-chunks[num_chunks].write_fn=write_graph_chunk_generation_data_overflow;-num_chunks++;-}-if(ctx->num_extra_edges){-chunks[num_chunks].id=GRAPH_CHUNKID_EXTRAEDGES;-chunks[num_chunks].size=4*ctx->num_extra_edges;-chunks[num_chunks].write_fn=write_graph_chunk_extra_edges;-num_chunks++;-}+if(ctx->write_generation_data)+add_chunk(cf,GRAPH_CHUNKID_GENERATION_DATA,+sizeof(uint32_t)*ctx->commits.nr,+write_graph_chunk_generation_data);+if(ctx->num_generation_data_overflows)+add_chunk(cf,GRAPH_CHUNKID_GENERATION_DATA_OVERFLOW,+sizeof(timestamp_t)*ctx->num_generation_data_overflows,+write_graph_chunk_generation_data_overflow);+if(ctx->num_extra_edges)+add_chunk(cf,GRAPH_CHUNKID_EXTRAEDGES,+4*ctx->num_extra_edges,+write_graph_chunk_extra_edges);if(ctx->changed_paths){-chunks[num_chunks].id=GRAPH_CHUNKID_BLOOMINDEXES;-chunks[num_chunks].size=sizeof(uint32_t)*ctx->commits.nr;-chunks[num_chunks].write_fn=write_graph_chunk_bloom_indexes;-num_chunks++;-chunks[num_chunks].id=GRAPH_CHUNKID_BLOOMDATA;-chunks[num_chunks].size=sizeof(uint32_t)*3-+ctx->total_bloom_filter_data_size;-chunks[num_chunks].write_fn=write_graph_chunk_bloom_data;-num_chunks++;-}-if(ctx->num_commit_graphs_after>1){-chunks[num_chunks].id=GRAPH_CHUNKID_BASE;-chunks[num_chunks].size=hashsz*(ctx->num_commit_graphs_after-1);-chunks[num_chunks].write_fn=write_graph_chunk_base;-num_chunks++;-}--chunks[num_chunks].id=0;-chunks[num_chunks].size=0;+add_chunk(cf,GRAPH_CHUNKID_BLOOMINDEXES,+sizeof(uint32_t)*ctx->commits.nr,+write_graph_chunk_bloom_indexes);+add_chunk(cf,GRAPH_CHUNKID_BLOOMDATA,+sizeof(uint32_t)*3++ctx->total_bloom_filter_data_size,+write_graph_chunk_bloom_data);+}+if(ctx->num_commit_graphs_after>1)+add_chunk(cf,GRAPH_CHUNKID_BASE,+hashsz*(ctx->num_commit_graphs_after-1),+write_graph_chunk_base);hashwrite_be32(f,GRAPH_SIGNATURE);hashwrite_u8(f,GRAPH_VERSION);hashwrite_u8(f,oid_version());-hashwrite_u8(f,num_chunks);+hashwrite_u8(f,get_num_chunks(cf));hashwrite_u8(f,ctx->num_commit_graphs_after-1);-chunk_offset=8+(num_chunks+1)*GRAPH_CHUNKLOOKUP_WIDTH;-for(i=0;i<=num_chunks;i++){-uint32_tchunk_write[3];--chunk_write[0]=htonl(chunks[i].id);-chunk_write[1]=htonl(chunk_offset>>32);-chunk_write[2]=htonl(chunk_offset&0xffffffff);-hashwrite(f,chunk_write,12);--chunk_offset+=chunks[i].size;-}-if(ctx->report_progress){strbuf_addf(&progress_title,Q_("Writing out commit graph in %d pass",
@@ -1905,17 +1869,7 @@ static int write_commit_graph_file(struct write_commit_graph_context *ctx)num_chunks*ctx->commits.nr);}-for(i=0;i<num_chunks;i++){-uint64_tstart_offset=f->total+f->offset;--if(chunks[i].write_fn(f,ctx))-return-1;--if(f->total+f->offset!=start_offset+chunks[i].size)-BUG("expected to write %"PRId64" bytes to chunk %"PRIx32", but wrote %"PRId64" instead",-chunks[i].size,chunks[i].id,-f->total+f->offset-start_offset);-}+write_chunkfile(cf,ctx);stop_progress(&ctx->progress);strbuf_release(&progress_title);
@@ -1932,6 +1886,7 @@ static int write_commit_graph_file(struct write_commit_graph_context *ctx)close_commit_graph(ctx->r->objects);finalize_hashfile(f,file_hash.hash,CSUM_HASH_IN_STREAM|CSUM_FSYNC);+free_chunkfile(cf);if(ctx->split){FILE*chainf=fdopen_lock_file(&lk,"w");
From: Derrick Stolee via GitGitGadget <hidden> Date: 2021-02-18 16:45:16
From: Derrick Stolee <redacted>
In an effort to streamline our chunk-based file formats, align some of
the code structure in write_midx_internal() to be similar to the
patterns in write_commit_graph_file().
Specifically, let's create a "struct write_midx_context" that can be
used as a data parameter to abstract function types.
This change only renames "struct pack_info" to "struct
write_midx_context" and the names of instances from "packs" to "ctx". In
future changes, we will expand the data inside "struct
write_midx_context" and align our chunk-writing method with the
chunk-format API.
Signed-off-by: Derrick Stolee <redacted>
---
midx.c | 130 ++++++++++++++++++++++++++++-----------------------------
1 file changed, 65 insertions(+), 65 deletions(-)
@@ -463,37 +463,37 @@ struct pack_list {staticvoidadd_pack_to_midx(constchar*full_path,size_tfull_path_len,constchar*file_name,void*data){-structpack_list*packs=(structpack_list*)data;+structwrite_midx_context*ctx=data;if(ends_with(file_name,".idx")){-display_progress(packs->progress,++packs->pack_paths_checked);-if(packs->m&&midx_contains_pack(packs->m,file_name))+display_progress(ctx->progress,++ctx->pack_paths_checked);+if(ctx->m&&midx_contains_pack(ctx->m,file_name))return;-ALLOC_GROW(packs->info,packs->nr+1,packs->alloc);+ALLOC_GROW(ctx->info,ctx->nr+1,ctx->alloc);-packs->info[packs->nr].p=add_packed_git(full_path,-full_path_len,-0);+ctx->info[ctx->nr].p=add_packed_git(full_path,+full_path_len,+0);-if(!packs->info[packs->nr].p){+if(!ctx->info[ctx->nr].p){warning(_("failed to add packfile '%s'"),full_path);return;}-if(open_pack_index(packs->info[packs->nr].p)){+if(open_pack_index(ctx->info[ctx->nr].p)){warning(_("failed to open pack-index '%s'"),full_path);-close_pack(packs->info[packs->nr].p);-FREE_AND_NULL(packs->info[packs->nr].p);+close_pack(ctx->info[ctx->nr].p);+FREE_AND_NULL(ctx->info[ctx->nr].p);return;}-packs->info[packs->nr].pack_name=xstrdup(file_name);-packs->info[packs->nr].orig_pack_int_id=packs->nr;-packs->info[packs->nr].expired=0;-packs->nr++;+ctx->info[ctx->nr].pack_name=xstrdup(file_name);+ctx->info[ctx->nr].orig_pack_int_id=ctx->nr;+ctx->info[ctx->nr].expired=0;+ctx->nr++;}}
@@ -820,40 +820,40 @@ static int write_midx_internal(const char *object_dir, struct multi_pack_index *midx_name);if(m)-packs.m=m;+ctx.m=m;else-packs.m=load_multi_pack_index(object_dir,1);--packs.nr=0;-packs.alloc=packs.m?packs.m->num_packs:16;-packs.info=NULL;-ALLOC_ARRAY(packs.info,packs.alloc);--if(packs.m){-for(i=0;i<packs.m->num_packs;i++){-ALLOC_GROW(packs.info,packs.nr+1,packs.alloc);--packs.info[packs.nr].orig_pack_int_id=i;-packs.info[packs.nr].pack_name=xstrdup(packs.m->pack_names[i]);-packs.info[packs.nr].p=NULL;-packs.info[packs.nr].expired=0;-packs.nr++;+ctx.m=load_multi_pack_index(object_dir,1);++ctx.nr=0;+ctx.alloc=ctx.m?ctx.m->num_packs:16;+ctx.info=NULL;+ALLOC_ARRAY(ctx.info,ctx.alloc);++if(ctx.m){+for(i=0;i<ctx.m->num_packs;i++){+ALLOC_GROW(ctx.info,ctx.nr+1,ctx.alloc);++ctx.info[ctx.nr].orig_pack_int_id=i;+ctx.info[ctx.nr].pack_name=xstrdup(ctx.m->pack_names[i]);+ctx.info[ctx.nr].p=NULL;+ctx.info[ctx.nr].expired=0;+ctx.nr++;}}-packs.pack_paths_checked=0;+ctx.pack_paths_checked=0;if(flags&MIDX_PROGRESS)-packs.progress=start_delayed_progress(_("Adding packfiles to multi-pack-index"),0);+ctx.progress=start_delayed_progress(_("Adding packfiles to multi-pack-index"),0);else-packs.progress=NULL;+ctx.progress=NULL;-for_each_file_in_pack_dir(object_dir,add_pack_to_midx,&packs);-stop_progress(&packs.progress);+for_each_file_in_pack_dir(object_dir,add_pack_to_midx,&ctx);+stop_progress(&ctx.progress);-if(packs.m&&packs.nr==packs.m->num_packs&&!packs_to_drop)+if(ctx.m&&ctx.nr==ctx.m->num_packs&&!packs_to_drop)gotocleanup;-entries=get_sorted_entries(packs.m,packs.info,packs.nr,&nr_entries);+entries=get_sorted_entries(ctx.m,ctx.info,ctx.nr,&nr_entries);for(i=0;i<nr_entries;i++){if(entries[i].offset>0x7fffffff)
@@ -862,19 +862,19 @@ static int write_midx_internal(const char *object_dir, struct multi_pack_index *large_offsets_needed=1;}-QSORT(packs.info,packs.nr,pack_info_compare);+QSORT(ctx.info,ctx.nr,pack_info_compare);if(packs_to_drop&&packs_to_drop->nr){intdrop_index=0;intmissing_drops=0;-for(i=0;i<packs.nr&&drop_index<packs_to_drop->nr;i++){-intcmp=strcmp(packs.info[i].pack_name,+for(i=0;i<ctx.nr&&drop_index<packs_to_drop->nr;i++){+intcmp=strcmp(ctx.info[i].pack_name,packs_to_drop->items[drop_index].string);if(!cmp){drop_index++;-packs.info[i].expired=1;+ctx.info[i].expired=1;}elseif(cmp>0){error(_("did not see pack-file %s to drop"),packs_to_drop->items[drop_index].string);
From: Derrick Stolee via GitGitGadget <hidden> Date: 2021-02-18 16:46:29
From: Derrick Stolee <redacted>
In an effort to align write_midx_internal() with the chunk-format API,
continue to group necessary data into "struct write_midx_context". This
change collects the "struct pack_midx_entry *entries" list and its count
into the context.
Update write_midx_oid_fanout() and write_midx_oid_lookup() to take the
context directly, as these are easy conversions with this new data.
Only the callers of write_midx_object_offsets() and
write_midx_large_offsets() are updated here, since additional data in
the context before those methods can match chunk_write_fn.
Signed-off-by: Derrick Stolee <redacted>
---
midx.c | 49 ++++++++++++++++++++++++++-----------------------
1 file changed, 26 insertions(+), 23 deletions(-)