Commit Graph

90 Commits (master)

Author SHA1 Message Date
Elijah Newren 0ff73d742b packfile.h: move pack_window and pack_entry from cache.h
Signed-off-by: Elijah Newren <>
Signed-off-by: Junio C Hamano <>
2023-04-24 12:47:31 -07:00
Junio C Hamano e7dca80692 Merge branch 'ab/remove-implicit-use-of-the-repository' into en/header-split-cache-h
* ab/remove-implicit-use-of-the-repository:
  libs: use "struct repository *" argument, not "the_repository"
  post-cocci: adjust comments for recent repo_* migration
  cocci: apply the "revision.h" part of "the_repository.pending"
  cocci: apply the "rerere.h" part of "the_repository.pending"
  cocci: apply the "refs.h" part of "the_repository.pending"
  cocci: apply the "promisor-remote.h" part of "the_repository.pending"
  cocci: apply the "packfile.h" part of "the_repository.pending"
  cocci: apply the "pretty.h" part of "the_repository.pending"
  cocci: apply the "object-store.h" part of "the_repository.pending"
  cocci: apply the "diff.h" part of "the_repository.pending"
  cocci: apply the "commit.h" part of "the_repository.pending"
  cocci: apply the "commit-reach.h" part of "the_repository.pending"
  cocci: apply the "cache.h" part of "the_repository.pending"
  cocci: add missing "the_repository" macros to "pending"
  cocci: sort "the_repository" rules by header
  cocci: fix incorrect & verbose "the_repository" rules
  cocci: remove dead rule from "the_repository.pending.cocci"
2023-04-04 08:25:52 -07:00
Ævar Arnfjörð Bjarmason afe27c8894 cocci: apply the "packfile.h" part of "the_repository.pending"
Apply the part of "the_repository.pending.cocci" pertaining to

Signed-off-by: Ævar Arnfjörð Bjarmason <>
Signed-off-by: Junio C Hamano <>
2023-03-28 07:36:45 -07:00
Elijah Newren a6dc3d364c treewide: remove unnecessary cache.h inclusion from a few headers
Ever since a64215b6cd ("object.h: stop depending on cache.h; make
cache.h depend on object.h", 2023-02-24), we have a few headers that
could have replaced their include of cache.h with an include of
object.h.  Make that change now.

Some C files had to start including cache.h after this change (or some
smaller header it had brought in), because the C files were depending
on things from cache.h but were only formerly implicitly getting
cache.h through one of these headers being modified in this patch.

Signed-off-by: Elijah Newren <>
Signed-off-by: Junio C Hamano <>
2023-03-21 10:56:50 -07:00
Junio C Hamano 79aee56c1e Merge branch 'tb/pack-revindex-on-disk-cleanup'
Code clean-up.

* tb/pack-revindex-on-disk-cleanup:
  packfile: make `close_pack_revindex()` static
2021-12-15 09:39:50 -08:00
Taylor Blau 0bf0de6cc7 packfile: make `close_pack_revindex()` static
Since its definition in 2f4ba2a867 (packfile: prepare for the existence
of '*.rev' files, 2021-01-25), the only caller of
`close_pack_revindex()` was within packfile.c.

Thus there is no need for this to be exposed via packfile.h, and instead
can remain static within packfile.c's compilation unit. While we're
here, move the function's opening brace onto its own line.

Noticed-by: Ramsay Jones <>
Signed-off-by: Taylor Blau <>
Signed-off-by: Junio C Hamano <>
2021-12-04 23:01:38 -08:00
René Scharfe 7407d733a4 packfile: convert has_packed_and_bad() to object_id
The single caller has a full object ID, so pass it on instead of just
its hash member.

Signed-off-by: René Scharfe <>
Signed-off-by: Junio C Hamano <>
2021-09-12 16:14:32 -07:00
René Scharfe 751530de5d packfile: convert mark_bad_packed_object() to object_id
All callers have full object IDs, so pass them on instead of just their
hash member.

Signed-off-by: René Scharfe <>
Signed-off-by: Junio C Hamano <>
2021-09-12 16:14:32 -07:00
Taylor Blau f62312e028 packfile: introduce 'find_kept_pack_entry()'
Future callers will want a function to fill a 'struct pack_entry' for a
given object id but _only_ from its position in any kept pack(s).

In particular, an new 'git repack' mode which ensures the resulting
packs form a geometric progress by object count will mark packs that it
does not want to repack as "kept in-core", and it will want to halt a
reachability traversal as soon as it visits an object in any of the kept
packs. But, it does not want to halt the traversal at non-kept, or
.keep packs.

The obvious alternative is 'find_pack_entry()', but this doesn't quite
suffice since it only returns the first pack it finds, which may or may
not be kept (and the mru cache makes it unpredictable which one you'll
get if there are options).

Short of that, you could walk over all packs looking for the object in
each one, but it scales with the number of packs, which may be

Introduce 'find_kept_pack_entry()', a function which is like
'find_pack_entry()', but only fills in objects in the kept packs.

Handle packs which have .keep files, as well as in-core kept packs
separately, since certain callers will want to distinguish one from the
other. (Though on-disk and in-core kept packs share the adjective
"kept", it is best to think of the two sets as independent.)

There is a gotcha when looking up objects that are duplicated in kept
and non-kept packs, particularly when the MIDX stores the non-kept
version and the caller asked for kept objects only. This could be
resolved by teaching the MIDX to resolve duplicates by always favoring
the kept pack (if one exists), but this breaks an assumption in existing
MIDXs, and so it would require a format change.

The benefit to changing the MIDX in this way is marginal, so we instead
have a more thorough check here which is explained with a comment.

Callers will be added in subsequent patches.

Co-authored-by: Jeff King <>
Signed-off-by: Jeff King <>
Signed-off-by: Taylor Blau <>
Reviewed-by: Jeff King <>
Signed-off-by: Junio C Hamano <>
2021-02-22 23:30:52 -08:00
Taylor Blau 2f4ba2a867 packfile: prepare for the existence of '*.rev' files
Specify the format of the on-disk reverse index 'pack-*.rev' file, as
well as prepare the code for the existence of such files.

The reverse index maps from pack relative positions (i.e., an index into
the array of object which is sorted by their offsets within the
packfile) to their position within the 'pack-*.idx' file. Today, this is
done by building up a list of (off_t, uint32_t) tuples for each object
(the off_t corresponding to that object's offset, and the uint32_t
corresponding to its position in the index). To convert between pack and
index position quickly, this array of tuples is radix sorted based on
its offset.

This has two major drawbacks:

First, the in-memory cost scales linearly with the number of objects in
a pack.  Each 'struct revindex_entry' is sizeof(off_t) +
sizeof(uint32_t) + padding bytes for a total of 16.

To observe this, force Git to load the reverse index by, for e.g.,
running 'git cat-file --batch-check="%(objectsize:disk)"'. When asking
for a single object in a fresh clone of the kernel, Git needs to
allocate 120+ MB of memory in order to hold the reverse index in memory.

Second, the cost to sort also scales with the size of the pack.
Luckily, this is a linear function since 'load_pack_revindex()' uses a
radix sort, but this cost still must be paid once per pack per process.

As an example, it takes ~60x longer to print the _size_ of an object as
it does to print that entire object's _contents_:

  Benchmark #1: git.compile cat-file --batch <obj
    Time (mean ± σ):       3.4 ms ±   0.1 ms    [User: 3.3 ms, System: 2.1 ms]
    Range (min … max):     3.2 ms …   3.7 ms    726 runs

  Benchmark #2: git.compile cat-file --batch-check="%(objectsize:disk)" <obj
    Time (mean ± σ):     210.3 ms ±   8.9 ms    [User: 188.2 ms, System: 23.2 ms]
    Range (min … max):   193.7 ms … 224.4 ms    13 runs

Instead, avoid computing and sorting the revindex once per process by
writing it to a file when the pack itself is generated.

The format is relatively straightforward. It contains an array of
uint32_t's, the length of which is equal to the number of objects in the
pack.  The ith entry in this table contains the index position of the
ith object in the pack, where "ith object in the pack" is determined by
pack offset.

One thing that the on-disk format does _not_ contain is the full (up to)
eight-byte offset corresponding to each object. This is something that
the in-memory revindex contains (it stores an off_t in 'struct
revindex_entry' along with the same uint32_t that the on-disk format
has). Omit it in the on-disk format, since knowing the index position
for some object is sufficient to get a constant-time lookup in the
pack-*.idx file to ask for an object's offset within the pack.

This trades off between the on-disk size of the 'pack-*.rev' file for
runtime to chase down the offset for some object. Even though the lookup
is constant time, the constant is heavier, since it can potentially
involve two pointer walks in v2 indexes (one to access the 4-byte offset
table, and potentially a second to access the double wide offset table).

Consider trying to map an object's pack offset to a relative position
within that pack. In a cold-cache scenario, more page faults occur while
switching between binary searching through the reverse index and
searching through the *.idx file for an object's offset. Sure enough,
with a cold cache (writing '3' into '/proc/sys/vm/drop_caches' after
'sync'ing), printing out the entire object's contents is still
marginally faster than printing its size:

  Benchmark #1: git.compile cat-file --batch-check="%(objectsize:disk)" <obj >/dev/null
    Time (mean ± σ):      22.6 ms ±   0.5 ms    [User: 2.4 ms, System: 7.9 ms]
    Range (min … max):    21.4 ms …  23.5 ms    41 runs

  Benchmark #2: git.compile cat-file --batch <obj >/dev/null
    Time (mean ± σ):      17.2 ms ±   0.7 ms    [User: 2.8 ms, System: 5.5 ms]
    Range (min … max):    15.6 ms …  18.2 ms    45 runs

(Numbers taken in the kernel after cheating and using the next patch to
generate a reverse index). There are a couple of approaches to improve
cold cache performance not pursued here:

  - We could include the object offsets in the reverse index format.
    Predictably, this does result in fewer page faults, but it triples
    the size of the file, while simultaneously duplicating a ton of data
    already available in the .idx file. (This was the original way I
    implemented the format, and it did show
    `--batch-check='%(objectsize:disk)'` winning out against `--batch`.)

    On the other hand, this increase in size also results in a large
    block-cache footprint, which could potentially hurt other workloads.

  - We could store the mapping from pack to index position in more
    cache-friendly way, like constructing a binary search tree from the
    table and writing the values in breadth-first order. This would
    result in much better locality, but the price you pay is trading
    O(1) lookup in 'pack_pos_to_index()' for an O(log n) one (since you
    can no longer directly index the table).

So, neither of these approaches are taken here. (Thankfully, the format
is versioned, so we are free to pursue these in the future.) But, cold
cache performance likely isn't interesting outside of one-off cases like
asking for the size of an object directly. In real-world usage, Git is
often performing many operations in the revindex (i.e., asking about
many objects rather than a single one).

The trade-off is worth it, since we will avoid the vast majority of the
cost of generating the revindex that the extra pointer chase will look
like noise in the following patch's benchmarks.

This patch describes the format and prepares callers (like in
pack-revindex.c) to be able to read *.rev files once they exist. An
implementation of the writer will appear in the next patch, and callers
will gradually begin to start using the writer in the patches that
follow after that.

Signed-off-by: Taylor Blau <>
Signed-off-by: Junio C Hamano <>
2021-01-25 18:32:43 -08:00
Taylor Blau 59552fb3e2 midx: traverse the local MIDX first
When a repository has an alternate object directory configured, callers
can traverse through each alternate's MIDX by walking the '->next'

But, when 'prepare_multi_pack_index_one()' loads multiple MIDXs, it
places the new ones at the front of this pointer chain, not at the end.
This can be confusing for callers such as 'git repack -ad', causing test
failures like in t7700.6 with 'GIT_TEST_MULTI_PACK_INDEX=1'.

The occurs when dropping a pack known to the local MIDX with alternates
configured that have their own MIDX. Since the alternate's MIDX is
returned via 'get_multi_pack_index()', 'midx_contains_pack()' returns
true (which is correct, since it traverses through the '->next' pointer
to find the MIDX in the chain that does contain the requested object).
But, we call 'clear_midx_file()' on 'the_repository', which drops the
MIDX at the path of the first MIDX in the chain, which (in the case of
t7700.6 is the one in the alternate).

This patch addresses that by:

  - placing the local MIDX first in the chain when calling
    'prepare_multi_pack_index_one()', and

  - introducing a new 'get_local_multi_pack_index()', which explicitly
    returns the repository-local MIDX, if any.

Don't impose an additional order on the MIDX's '->next' pointer beyond
that the first item in the chain must be local if one exists so that we
avoid a quadratic insertion.

Likewise, use 'get_local_multi_pack_index()' in
'remove_redundant_pack()' to fix the formerly broken t7700.6 when run

Finally, note that the MIDX ordering invariant is only preserved by the
insertion order in 'prepare_packed_git()', which traverses through the
ODB's '->next' pointer, meaning we visit the local object store first.
This fragility makes this an undesirable long-term solution if more
callers are added, but it is acceptable for now since this is the only

Helped-by: Jeff King <>
Signed-off-by: Jeff King <>
Signed-off-by: Taylor Blau <>
Signed-off-by: Junio C Hamano <>
2020-08-28 14:07:09 -07:00
Jeff King 2fecc48cad packfile: drop nth_packed_object_sha1()
Once upon a time, nth_packed_object_sha1() was the primary way to get
the oid of a packfile's index position. But these days we have the more
type-safe nth_packed_object_id() wrapper, and all callers have been

Let's drop the "sha1" version (turning the safer wrapper into a single
function) so that nobody is tempted to introduce new callers.

Signed-off-by: Jeff King <>
Signed-off-by: Junio C Hamano <>
2020-02-24 12:55:53 -08:00
Jeff King 0763671b8e nth_packed_object_oid(): use customary integer return
Our nth_packed_object_sha1() function returns NULL for error. So when we
wrapped it with nth_packed_object_oid(), we kept the same semantics. But
it's a bit funny, because the caller actually passes in an out
parameter, and the pointer we return is just that same struct they
passed to us (or NULL).

It's not too terrible, but it does make the interface a little
non-idiomatic. Let's switch to our usual "0 for success, negative for
error" return value. Most callers either don't check it, or are
trivially converted. The one that requires the biggest change is
actually improved, as we can ditch an extra aliased pointer variable.

Since we are changing the interface in a subtle way that the compiler
wouldn't catch, let's also change the name to catch any topics in
flight. We can drop the 'o' and make it nth_packed_object_id(). That's
slightly shorter, but also less redundant since the 'o' stands for
"object" already.

Signed-off-by: Jeff King <>
Signed-off-by: Junio C Hamano <>
2020-02-24 12:55:42 -08:00
Junio C Hamano a14aebeac3 Merge branch 'jk/packfile-reuse-cleanup'
The way "git pack-objects" reuses objects stored in existing pack
to generate its result has been improved.

* jk/packfile-reuse-cleanup:
  pack-bitmap: don't rely on bitmap_git->reuse_objects
  pack-objects: add checks for duplicate objects
  pack-objects: improve partial packfile reuse
  builtin/pack-objects: introduce obj_is_packed()
  pack-objects: introduce pack.allowPackReuse
  csum-file: introduce hashfile_total()
  pack-bitmap: simplify bitmap_has_oid_in_uninteresting()
  pack-bitmap: uninteresting oid can be outside bitmapped packfile
  pack-bitmap: introduce bitmap_walk_contains()
  ewah/bitmap: introduce bitmap_word_alloc()
  packfile: expose get_delta_base()
  builtin/pack-objects: report reused packfile objects
2020-02-14 12:54:19 -08:00
Jeff King 56d9cbe68b packfile: expose get_delta_base()
In a following commit get_delta_base() will be used outside
packfile.c, so let's make it non static and declare it in

Signed-off-by: Jeff King <>
Signed-off-by: Christian Couder <>
Signed-off-by: Junio C Hamano <>
2019-09-13 14:40:33 -07:00
Junio C Hamano 8ce8a63b46 Merge branch 'ds/midx-expire-repack'
Code cleanup.

* ds/midx-expire-repack:
  packfile.h: drop extern from function declaration
2019-09-09 12:26:38 -07:00
Denton Liu 415b770b88 packfile.h: drop extern from function declaration
In 336226c259 (packfile.h: drop extern from function declarations,
2019-04-05), `extern` was removed from function declarations because
it's redundant. However, in 8434e85d5f (repack: refactor pack deletion
for future use, 2019-06-10), an `extern` was mistakenly included.

Remove this spurious `extern`.

Signed-off-by: Denton Liu <>
Signed-off-by: Junio C Hamano <>
2019-08-20 11:29:31 -07:00
Junio C Hamano 4308d81d45 Merge branch 'ds/midx-expire-repack'
"git multi-pack-index" learned expire and repack subcommands.

* ds/midx-expire-repack:
  t5319: use 'test-tool path-utils' instead of 'ls -l' test batch size zero
  midx: add test that 'expire' respects .keep files
  multi-pack-index: test expire while adding packs
  midx: implement midx_repack()
  multi-pack-index: prepare 'repack' subcommand
  multi-pack-index: implement 'expire' subcommand
  midx: refactor permutation logic and pack sorting
  midx: simplify computation of pack name lengths
  multi-pack-index: prepare for 'expire' subcommand
  Docs: rearrange subcommands for multi-pack-index
  repack: refactor pack deletion for future use
2019-07-19 11:30:19 -07:00
Junio C Hamano 5cb7c73589 Merge branch 'ds/close-object-store'
The commit-graph file is now part of the "files that the runtime
may keep open file descriptors on, all of which would need to be
closed when done with the object store", and the file descriptor to
an existing commit-graph file now is closed before "gc" finalizes a
new instance to replace it.

* ds/close-object-store:
  packfile: rename close_all_packs to close_object_store
  packfile: close commit-graph in close_all_packs
  commit-graph: use raw_object_store when closing
2019-07-09 15:25:37 -07:00
Derrick Stolee 2d511cfc0b packfile: rename close_all_packs to close_object_store
The close_all_packs() method is now responsible for more than just pack-files.
It also closes the commit-graph and the multi-pack-index. Rename the function
to be more descriptive of its larger role. The name also fits because the
input parameter is a raw_object_store.

Signed-off-by: Derrick Stolee <>
Signed-off-by: Junio C Hamano <>
2019-06-12 11:33:54 -07:00
Derrick Stolee 8434e85d5f repack: refactor pack deletion for future use
The repack builtin deletes redundant pack-files and their
associated .idx, .promisor, .bitmap, and .keep files. We will want
to re-use this logic in the future for other types of repack, so
pull the logic into 'unlink_pack_path()' in packfile.c.

The 'ignore_keep' parameter is enabled for the use in repack, but
will be important for a future caller.

Signed-off-by: Derrick Stolee <>
Signed-off-by: Junio C Hamano <>
2019-06-11 10:34:40 -07:00
Junio C Hamano 0b179f3175 Merge branch 'nd/sha1-name-c-wo-the-repository'
Further code clean-up to allow the lowest level of name-to-object
mapping layer to work with a passed-in repository other than the
default one.

* nd/sha1-name-c-wo-the-repository: (34 commits)
  sha1-name.c: remove the_repo from get_oid_mb()
  sha1-name.c: remove the_repo from other get_oid_*
  sha1-name.c: remove the_repo from maybe_die_on_misspelt_object_name
  submodule-config.c: use repo_get_oid for reading .gitmodules
  sha1-name.c: add repo_get_oid()
  sha1-name.c: remove the_repo from get_oid_with_context_1()
  sha1-name.c: remove the_repo from resolve_relative_path()
  sha1-name.c: remove the_repo from diagnose_invalid_index_path()
  sha1-name.c: remove the_repo from handle_one_ref()
  sha1-name.c: remove the_repo from get_oid_1()
  sha1-name.c: remove the_repo from get_oid_basic()
  sha1-name.c: remove the_repo from get_describe_name()
  sha1-name.c: remove the_repo from get_oid_oneline()
  sha1-name.c: add repo_interpret_branch_name()
  sha1-name.c: remove the_repo from interpret_branch_mark()
  sha1-name.c: remove the_repo from interpret_nth_prior_checkout()
  sha1-name.c: remove the_repo from get_short_oid()
  sha1-name.c: add repo_for_each_abbrev()
  sha1-name.c: store and use repo in struct disambiguate_state
  sha1-name.c: add repo_find_unique_abbrev_r()
2019-05-09 00:37:25 +09:00
Junio C Hamano 776f3e1fb7 Merge branch 'jk/server-info-rabbit-hole'
Code clean-up around a much-less-important-than-it-used-to-be
update_server_info() funtion.

* jk/server-info-rabbit-hole:
  update_info_refs(): drop unused force parameter
  server-info: drop objdirlen pointer arithmetic
  server-info: drop nr_alloc struct member
  server-info: use strbuf to read old info/packs file
  server-info: simplify cleanup in parse_pack_def()
  server-info: fix blind pointer arithmetic
  http: simplify parsing of remote objects/info/packs
  packfile: fix pack basename computation
  midx: check both pack and index names for containment
  t5319: drop useless --buffer from cat-file
  t5319: fix bogus cat-file argument
  pack-revindex: open index if necessary
  packfile.h: drop extern from function declarations
2019-04-25 16:41:13 +09:00
Jeff King fc78915674 packfile: fix pack basename computation
When we have a multi-pack-index that covers many packfiles, we try to
avoid opening the .idx for those packfiles. To do that we feed the pack
name to midx_contains_pack(). But that function wants to see only the
basename, which we compute using strrchr() to find the final slash. But
that leaves an extra "/" at the start of our string.

We can fix this by incrementing the pointer. That also raises the
question of what to do when the name does not have a '/' at all. This
should generally not happen (we always find files in "pack/"), but it
doesn't hurt to be defensive here.

Let's wrap all of that up in a helper function and make it publicly
available, since a later patch will need to use it, too.

The tests don't notice because there's nothing about opening those .idx
files that would cause us to give incorrect output. It's just a little
slower. The new test checks this case by corrupting the covered .idx,
and then making sure we don't complain about it.

We also have to tweak t5570, which intentionally corrupts a .idx file
and expects us to notice it. When run with GIT_TEST_MULTI_PACK_INDEX,
this will fail since we now will (correctly) not bother opening the .idx
at all. We can fix that by unconditionally dropping any midx that's
there, which ensures we'll have to read the .idx.

Signed-off-by: Jeff King <>
Signed-off-by: Junio C Hamano <>
2019-04-16 16:58:21 +09:00
Jeff King 336226c259 packfile.h: drop extern from function declarations
As CodingGuidelines recommends, we do not need an "extern" when
declaring a public function. Let's drop these. Note that we leave the
extern on report_garbage(), as that is actually a function pointer, not
a function itself.

Signed-off-by: Jeff King <>
Signed-off-by: Junio C Hamano <>
2019-04-16 16:58:21 +09:00
Nguyễn Thái Ngọc Duy 5038de1937 packfile.c: add repo_approximate_object_count()
Signed-off-by: Nguyễn Thái Ngọc Duy <>
Signed-off-by: Junio C Hamano <>
2019-04-08 17:26:32 +09:00
Jeff Hostetler 5ae18df9d8 midx: during verify group objects by packfile to speed verification
Teach `multi-pack-index verify` to sort the set of object by
packfile so that only one packfile needs to be open at a time.

This is a performance improvement.  Previously, objects were
verified in OID order.  This essentially requires all packfiles
to be open at the same time.  If the number of packfiles exceeds
the open file limit, packfiles would be LRU-closed and re-opened
many times.

Signed-off-by: Jeff Hostetler <>
Signed-off-by: Junio C Hamano <>
2019-03-22 14:31:11 +09:00
Junio C Hamano b99a579f8e Merge branch 'sb/more-repo-in-api'
The in-core repository instances are passed through more codepaths.

* sb/more-repo-in-api: (23 commits)
  t/helper/test-repository: celebrate independence from the_repository
  path.h: make REPO_GIT_PATH_FUNC repository agnostic
  commit: prepare free_commit_buffer and release_commit_memory for any repo
  commit-graph: convert remaining functions to handle any repo
  submodule: don't add submodule as odb for push
  submodule: use submodule repos for object lookup
  pretty: prepare format_commit_message to handle arbitrary repositories
  commit: prepare logmsg_reencode to handle arbitrary repositories
  commit: prepare repo_unuse_commit_buffer to handle any repo
  commit: prepare get_commit_buffer to handle any repo
  commit-reach: prepare in_merge_bases[_many] to handle any repo
  commit-reach: prepare get_merge_bases to handle any repo
  commit-reach.c: allow get_merge_bases_many_0 to handle any repo
  commit-reach.c: allow remove_redundant to handle any repo
  commit-reach.c: allow merge_bases_many to handle any repo
  commit-reach.c: allow paint_down_to_common to handle any repo
  commit: allow parse_commit* to handle any repo
  object: parse_object to honor its repository argument
  object-store: prepare has_{sha1, object}_file to handle any repo
  object-store: prepare read_object_file to deal with any repo
2019-02-05 14:26:09 -08:00
Stefan Beller 33b94066f2 packfile: allow has_packed_and_bad to handle arbitrary repositories
has_packed_and_bad is not widely used, so just migrate it all at once.

Signed-off-by: Stefan Beller <>
Signed-off-by: Junio C Hamano <>
2018-10-19 16:21:10 +09:00
Josh Steadmon 1127a98cce fuzz: add fuzz testing for packfile indices.
Breaks the majority of check_packed_git_idx() into a separate function,
load_idx(). The latter function operates on arbitrary buffers, which
makes it suitable as a fuzzing test target.

Signed-off-by: Josh Steadmon <>
Signed-off-by: Junio C Hamano <>
2018-10-15 14:29:03 +09:00
Derrick Stolee 0bff5269d3 packfile: add all_packs list
If a repo contains a multi-pack-index, then the packed_git list
does not contain the packfiles that are covered by the multi-pack-index.
This is important for doing object lookups, abbreviations, and
approximating object count. However, there are many operations that
really want to iterate over all packfiles.

Create a new 'all_packs' linked list that contains this list, starting
with the packfiles in the multi-pack-index and then continuing along
the packed_git linked list.

Signed-off-by: Derrick Stolee <>
Signed-off-by: Junio C Hamano <>
2018-08-20 15:31:40 -07:00
Junio C Hamano c00ba2233e Sync 'ds/multi-pack-index' to v2.19.0-rc0
* ds/multi-pack-index: (23 commits)
  midx: clear midx on repack
  packfile: skip loading index if in multi-pack-index
  midx: prevent duplicate packfile loads
  midx: use midx in approximate_object_count
  midx: use existing midx when writing new one
  midx: use midx in abbreviation calculations
  midx: read objects from multi-pack-index
  config: create core.multiPackIndex setting
  midx: write object offsets
  midx: write object id fanout chunk
  midx: write object ids in a chunk
  midx: sort and deduplicate objects from packfiles
  midx: read pack names into array
  multi-pack-index: write pack names in chunk
  multi-pack-index: read packfile list
  packfile: generalize pack directory list
  t5319: expand test data
  multi-pack-index: load into memory
  midx: write header information to lockfile
  multi-pack-index: add 'write' verb
2018-08-20 15:29:54 -07:00
Junio C Hamano 0c54cdaf65 Merge branch 'jk/for-each-object-iteration'
The API to iterate over all objects learned to optionally list
objects in the order they appear in packfiles, which helps locality
of access if the caller accesses these objects while as objects are

* jk/for-each-object-iteration:
  for_each_*_object: move declarations to object-store.h
  cat-file: use a single strbuf for all output
  cat-file: split batch "buf" into two variables
  cat-file: use oidset check-and-insert
  cat-file: support "unordered" output for --batch-all-objects
  cat-file: rename batch_{loose,packed}_object callbacks
  t1006: test cat-file --batch-all-objects with duplicates
  for_each_packed_object: support iterating in pack-order
  for_each_*_object: give more comprehensive docstrings
  for_each_*_object: take flag arguments as enum
  for_each_*_object: store flag definitions in a single location
2018-08-20 11:33:52 -07:00
Jeff King 0889aae1cd for_each_*_object: move declarations to object-store.h
The for_each_loose_object() and for_each_packed_object()
functions are meant to be part of a unified interface: they
use the same set of for_each_object_flags, and it's not
inconceivable that we might one day add a single
for_each_object() wrapper around them.

Let's put them together in a single file, so we can avoid
awkwardness like saying "the flags for this function are
over in cache.h". Moving the loose functions to packfile.h
is silly. Moving the packed functions to cache.h works, but
makes the "cache.h is a kitchen sink" problem worse. The
best place is the recently-created object-store.h, since
these are quite obviously related to object storage.

The for_each_*_in_objdir() functions do not use the same
flags, but they are logically part of the same interface as
for_each_loose_object(), and share callback signatures. So
we'll move those, as well, as they also make sense in

Signed-off-by: Jeff King <>
Signed-off-by: Junio C Hamano <>
2018-08-14 12:29:57 -07:00
Jeff King 736eb88fdc for_each_packed_object: support iterating in pack-order
We currently iterate over objects within a pack in .idx
order, which uses the object hashes. That means that it
is effectively random with respect to the location of the
object within the pack. If you're going to access the actual
object data, there are two reasons to move linearly through
the pack itself:

  1. It improves the locality of access in the packfile. In
     the cold-cache case, this may mean fewer disk seeks, or
     better usage of disk cache.

  2. We store related deltas together in the packfile. Which
     means that the delta base cache can operate much more
     efficiently if we visit all of those related deltas in
     sequence, as the earlier items are likely to still be
     in the cache.  Whereas if we visit the objects in
     random order, our cache entries are much more likely to
     have been evicted by unrelated deltas in the meantime.

So in general, if you're going to access the object contents
pack order is generally going to end up more efficient.

But if you're simply generating a list of object names, or
if you're going to end up sorting the result anyway, you're
better off just using the .idx order, as finding the pack
order means generating the in-memory pack-revindex.
According to the numbers in 8b8dfd5132 (pack-revindex:
radix-sort the revindex, 2013-07-11), that takes about 200ms
for linux.git, and 20ms for git.git (those numbers are a few
years old but are still a good ballpark).

That makes it a good optimization for some cases (we can
save tens of seconds in git.git by having good locality of
delta access, for a 20ms cost), but a bad one for others
(e.g., right now "cat-file --batch-all-objects
--batch-check="%(objectname)" is 170ms in git.git, so adding
20ms to that is noticeable).

Hence this patch makes it an optional flag. You can't
actually do any interesting timings yet, as it's not plumbed
through to any user-facing tools like cat-file. That will
come in a later patch.

Signed-off-by: Jeff King <>
Signed-off-by: Junio C Hamano <>
2018-08-13 13:48:28 -07:00
Jeff King 8b36155190 for_each_*_object: give more comprehensive docstrings
We already mention the local/alternate behavior of these
functions, but we can help clarify a few other behaviors:

 - there's no need to mention LOCAL_ONLY specifically, since
   we already reference the flags by type (and as we add
   more flags, we don't want to have to mention each)

 - clarify that reachability doesn't matter here; this is
   all accessible objects

 - what ordering/uniqueness guarantees we give

 - how pack-specific flags are handled for the loose case

Signed-off-by: Jeff King <>
Signed-off-by: Junio C Hamano <>
2018-08-13 13:48:26 -07:00
Jeff King a7ff6f5a0f for_each_*_object: take flag arguments as enum
It's not wrong to pass our flags in an "unsigned", as we
know it will be at least as large as the enum.  However,
using the enum in the declaration makes it more obvious
where to find the list of flags.

While we're here, let's also drop the "extern" noise-words
from the declarations, per our modern coding style.

Signed-off-by: Jeff King <>
Signed-off-by: Junio C Hamano <>
2018-08-13 13:48:25 -07:00
Jeff King 202e7f1e16 for_each_*_object: store flag definitions in a single location
These flags were split between cache.h and packfile.h,
because some of the flags apply only to packs. However, they
share a single numeric namespace, since both are respected
for the packed variant. Let's make sure they're defined
together so that nobody accidentally adds a new flag in one
location that duplicates the other.

While we're here, let's also put them in an enum (which
helps debugger visibility) and use "(1<<n)" rather than
counting powers of 2 manually.

Signed-off-by: Jeff King <>
Signed-off-by: Junio C Hamano <>
2018-08-13 13:47:50 -07:00
Beat Bolli b42f98af09 packfile: ensure that enum object_type is defined
When compiling under Apple LLVM version 9.1.0 (clang-902.0.39.2) with
"make DEVELOPER=1 DEVOPTS=pedantic", the compiler says

    error: redeclaration of already-defined enum 'object_type' is a GNU
    extension [-Werror,-Wgnu-redeclared-enum]

According to
(section "Redeclaration"), a repeated declaration after the definition
is only legal for structs and unions, but not for enums.

Drop the belated declaration of enum object_type and include cache.h
instead to make sure the enum is defined.

Helped-by: Jonathan Nieder <>
Signed-off-by: Beat Bolli <>
Reviewed-by: Jonathan Nieder <>
Signed-off-by: Junio C Hamano <>
2018-07-26 10:36:26 -07:00
Derrick Stolee 8aac67a174 midx: use midx in abbreviation calculations
Signed-off-by: Derrick Stolee <>
Signed-off-by: Junio C Hamano <>
2018-07-20 11:27:28 -07:00
Derrick Stolee fe1ed56f5e midx: sort and deduplicate objects from packfiles
Before writing a list of objects and their offsets to a multi-pack-index,
we need to collect the list of objects contained in the packfiles. There
may be multiple copies of some objects, so this list must be deduplicated.

It is possible to artificially get into a state where there are many
duplicate copies of objects. That can create high memory pressure if we
are to create a list of all objects before de-duplication. To reduce
this memory pressure without a significant performance drop,
automatically group objects by the first byte of their object id. Use
the IDX fanout tables to group the data, copy to a local array, then

Copy only the de-duplicated entries. Select the duplicate based on the
most-recent modified time of a packfile containing the object.

Signed-off-by: Derrick Stolee <>
Signed-off-by: Junio C Hamano <>
2018-07-20 11:27:28 -07:00
Derrick Stolee 9208e318f5 packfile: generalize pack directory list
In anticipation of sharing the pack directory listing with the
multi-pack-index, generalize prepare_packed_git_one() into

Signed-off-by: Derrick Stolee <>
Signed-off-by: Junio C Hamano <>
2018-07-20 11:27:28 -07:00
Junio C Hamano 00624d608c Merge branch 'sb/object-store-grafts'
The conversion to pass "the_repository" and then "a_repository"
throughout the object access API continues.

* sb/object-store-grafts:
  commit: allow lookup_commit_graft to handle arbitrary repositories
  commit: allow prepare_commit_graft to handle arbitrary repositories
  shallow: migrate shallow information into the object parser
  path.c: migrate global git_path_* to take a repository argument
  cache: convert get_graft_file to handle arbitrary repositories
  commit: convert read_graft_file to handle arbitrary repositories
  commit: convert register_commit_graft to handle arbitrary repositories
  commit: convert commit_graft_pos() to handle arbitrary repositories
  shallow: add repository argument to is_repository_shallow
  shallow: add repository argument to check_shallow_file_for_update
  shallow: add repository argument to register_shallow
  shallow: add repository argument to set_alternate_shallow_file
  commit: add repository argument to lookup_commit_graft
  commit: add repository argument to prepare_commit_graft
  commit: add repository argument to read_graft_file
  commit: add repository argument to register_commit_graft
  commit: add repository argument to commit_graft_pos
  object: move grafts to object parser
  object-store: move object access functions to object-store.h
2018-07-18 12:20:28 -07:00
Junio C Hamano 42c8ce1c49 Merge branch 'bc/object-id'
Conversion from uchar[20] to struct object_id continues.

* bc/object-id: (42 commits)
  merge-one-file: compute empty blob object ID
  add--interactive: compute the empty tree value
  Update shell scripts to compute empty tree object ID
  sha1_file: only expose empty object constants through git_hash_algo
  dir: use the_hash_algo for empty blob object ID
  sequencer: use the_hash_algo for empty tree object ID
  cache-tree: use is_empty_tree_oid
  sha1_file: convert cached object code to struct object_id
  builtin/reset: convert use of EMPTY_TREE_SHA1_BIN
  builtin/receive-pack: convert one use of EMPTY_TREE_SHA1_HEX
  wt-status: convert two uses of EMPTY_TREE_SHA1_HEX
  submodule: convert several uses of EMPTY_TREE_SHA1_HEX
  sequencer: convert one use of EMPTY_TREE_SHA1_HEX
  merge: convert empty tree constant to the_hash_algo
  builtin/merge: switch tree functions to use object_id
  builtin/am: convert uses of EMPTY_TREE_SHA1_BIN to the_hash_algo
  sha1-file: add functions for hex empty tree and blob OIDs
  builtin/receive-pack: avoid hard-coded constants for push certs
  diff: specify abbreviation size in terms of the_hash_algo
  upload-pack: replace use of several hard-coded constants
2018-05-30 14:04:10 +09:00
Junio C Hamano fcb6df3254 Merge branch 'sb/oid-object-info'
The codepath around object-info API has been taught to take the
repository object (which in turn tells the API which object store
the objects are to be located).

* sb/oid-object-info:
  cache.h: allow oid_object_info to handle arbitrary repositories
  packfile: add repository argument to cache_or_unpack_entry
  packfile: add repository argument to unpack_entry
  packfile: add repository argument to read_object
  packfile: add repository argument to packed_object_info
  packfile: add repository argument to packed_to_object_type
  packfile: add repository argument to retry_bad_packed_offset
  cache.h: add repository argument to oid_object_info
  cache.h: add repository argument to oid_object_info_extended
2018-05-23 14:38:16 +09:00
Stefan Beller cbd53a2193 object-store: move object access functions to object-store.h
This should make these functions easier to find and cache.h less
overwhelming to read.

In particular, this moves:
- read_object_file
- oid_object_info
- write_object_file

As a result, most of the codebase needs to #include object-store.h.
In this patch the #include is only added to files that would fail to
compile otherwise.  It would be better to #include wherever
identifiers from the header are used.  That can happen later
when we have better tooling for it.

Signed-off-by: Stefan Beller <>
Signed-off-by: Junio C Hamano <>
2018-05-16 11:42:03 +09:00
Junio C Hamano b10edb2df5 Merge branch 'ds/commit-graph'
Precompute and store information necessary for ancestry traversal
in a separate file to optimize graph walking.

* ds/commit-graph:
  commit-graph: implement "--append" option
  commit-graph: build graph from starting commits
  commit-graph: read only from specific pack-indexes
  commit: integrate commit graph with commit parsing
  commit-graph: close under reachability
  commit-graph: add core.commitGraph setting
  commit-graph: implement git commit-graph read
  commit-graph: implement git-commit-graph write
  commit-graph: implement write_commit_graph()
  commit-graph: create git-commit-graph builtin
  graph: add commit graph design document
  commit-graph: add format document
  csum-file: refactor finalize_hashfile() method
  csum-file: rename hashclose() to finalize_hashfile()
2018-05-08 15:59:20 +09:00
brian m. carlson 544443cb3c packfile: convert find_pack_entry to object_id
Convert find_pack_entry and the static function fill_pack_entry to take
pointers to struct object_id.

Signed-off-by: brian m. carlson <>
Signed-off-by: Junio C Hamano <>
2018-05-02 13:59:49 +09:00
brian m. carlson 14c3c80c81 packfile: convert has_sha1_pack to object_id
Convert this function to take a pointer to struct object_id and rename
it has_object_pack for consistency with has_object_file.

Signed-off-by: brian m. carlson <>
Signed-off-by: Junio C Hamano <>
2018-05-02 13:59:49 +09:00
Stefan Beller 9d98354f48 cache.h: allow oid_object_info to handle arbitrary repositories
This involves also adapting oid_object_info_extended and a some
internal functions that are used to implement these. It all has to
happen in one patch, because of a single recursive chain of calls visits
all these functions.

oid_object_info_extended is also used in partial clones, which allow
fetching missing objects. As this series will not add the repository
struct to the transport code and fetch_object(), add a TODO note and
omit fetching if a user tries to use a partial clone in a repository
other than the_repository.

Among the functions modified to handle arbitrary repositories,
unpack_entry() is one of them. Note that it still references the globals
"delta_base_cache" and "delta_base_cached", but those are safe to be
referenced (the former is indexed partly by "struct packed_git *", which
is repo-specific, and the latter is only used to limit the size of the
former as an optimization).

Helped-by: Brandon Williams <>
Helped-by: Jonathan Tan <>
Signed-off-by: Jonathan Nieder <>
Signed-off-by: Stefan Beller <>
Reviewed-by: Jonathan Tan <>
Signed-off-by: Junio C Hamano <>
2018-04-26 10:54:28 +09:00