let got-read-pack be explicit about whether it could enumerate all objects This allows the main process to avoid looping over all object IDs again in case the pack file used for enumeration is complete. ok op@

fix error handling in find_pack_for_enumeration(); pointed out by op@

Bring back object enumeration inside got-read-pack as a fast path. The problem that was found in the earlier version has been fixed. ok op@

revert object enumeration in got-read-pack for now; needs more work This implementation marked commits and trees as enumerated before all trees which they depend on were enumerated. This behaviour leads to incomplete pack files when a tree is only partially packed and got-read-pack hits a missing tree entry as a result. The algorithm must be reworked such that packed leave nodes are marked enumerated first, then bubble-up. Found by op@

free id and path in load_packed_tree_ids() on error, else they would leak pointed out by op@

implement object enumeration support in got-read-pack ok op@

fix a bug in findwixt() which caused pack files with missing parent commits The 'nskip' variable is supposed to reflect commits which are waiting on the queue and have the 'skip' color. Only increment 'nskip' when adding such commits to the queue. Problem observed with got send -T and a tag pointing to a deleted branch. Test to reproduce the bug written by op@.

use random seeds for murmurhash2 change the three hardcoded seeds to fresh ones generated on demand via arc4random. Suggested/fixed by and ok stsp@

include header

shrink struct got_pack_meta a bit by removing the have_reused_delta flag This flag can be expressed as m->reused_delta_offset != 0 because all deltas in valid pack files will be written at a non-zero offset. We allocate a huge number of these structs during packing, so every little bit helps.

reduce the amount of memory used for caching deltas during deltification With files sorted properly for deltification we produce better deltas but end up consuming more memory and risk running into OpenBSD ulimits during packing. To compensate, reduce the threshold for the amount of delta data we store in memory, spooling more deltas into the cache file. ok op@

store a path hash instead of a verbatim path in pack meta data This reduces memory use by gotadmin pack. The goal is to sort files which share a path next to each other for deltification. A hash of the path is good enough for this purpose and consumes less memory than a verbatim copy of the path. Git does something similar. ok op@

fix paths stored in pack meta data, improving file deltification The old code was broken and stored an empty path or filenames, instead of a repository-relative path. Which means we didn't sort files for deltification as was intended. Fixing this provides much better deltas in large pack files written by gotadmin pack -a. In my test case, pack size changed from 2GB to 1.5GB. ok op@

plug a small memleak on error in got_pack_create()

map delta cache file into memory if possible while writing a pack file with a fix from + ok op@

fix load_object_ids() such that packing tags works if zero commits are packed reported by jrick and op

run the search for deltas to reuse in got-read-pack This significantly speeds up the deltification step of packing by avoiding imsg traffic. gotadmin no longer requests individual raw deltas from got-read-pack to check whether it can reuse them. Instead, got-read-pack obtains a list of objects we want to pack, and hands back the list of all deltas in its pack file which can be reused. Messages are now batched such that imsg buffers are filled as much as possible. Another advantage is that deltas we are not going to reuse will no longer be written to the delta cache file, saving disk space. Before this patch, any raw delta candidate was written to the delta cache file by got-read-pack, and the decision whether to reuse the delta happened afterwards in the gotadmin process. Code for reading individual raw deltas is now unused and could be removed at some point. ok op@

avoid 'remove unused' loop by storing excluded objects in a separate set ok op@

avoid loop over the ID set which removes objects IDs with reused deltas ok op@

store deltas in compressed form while packing, both in memory and cache file This reduces memory and disk space consumption during packing. with tweaks + memleak on error fix from op@ ok op@

avoid subtraction of values larger than int in qsort(3) comparison callbacks tweak + ok tb@

inline struct got_object_id in struct got_object_qid Saves us from doing a malloc/free call for every item on the list. ok op@

reimplement object-ID set data structure on top of a hash table Siphash suggested by jrick as a better alternative to murmurhash for this use case. with small fixes from and ok op@

speed up initial stage of packing by adding a "skip" commit color The skip color marks boundary commits and their ancestors. Boundary commits are reachable both via references which we want to exclude from the pack, and via references which we want to include in the pack. We continue processing commit history up to the point we are left with only skip commits on the queue. This can speed up findtwixt() significantly and avoids wrong results produced by the old algorithm which made no distinction between "drop" and "skip". This idea was first implemented by Michael Forney for git9: https://git.9front.org/plan9front/plan9front/2e47badb88312c5c045a8042dc2ef80148e5ab47/commit.html Michael's log message for git9 is reproduced below: git/query: refactor graph painting algorithm (findtwixt, lca) We now keep track of 3 sets during traversal: - keep: commits we've reached from head commits - drop: commits we've reached from tail commits - skip: ancestors of commits in both 'keep' and 'drop' Commits in 'keep' and/or 'drop' may be added later to the 'skip' set if we discover later that they are part of a common subgraph of the head and tail commits. From these sets we can calculate the commits we are interested in: lca commits are those in 'keep' and 'drop', but not in 'skip'. findtwixt commits are those in 'keep', but not in 'drop' or 'skip'. The "LCA" commit returned is a common ancestor such that there are no other common ancestors that can reach that commit. Although there can be multiple commits that meet this criteria, where one is technically lower on the commit-graph than the other, these cases only happen in complex merge arrangements and any choice is likely a decent merge base. Repainting is now done in paint() directly. When we find a boundary commit, we switch our paint color to 'skip'. 'skip' painting does not stop when it hits another color; we continue until we are left with only 'skip' commits on the queue. This fixes several mishandled cases in the current algorithm: 1. If we hit the common subgraph from tail commits first (if the tail commit was newer than the head commit), we ended up traversing the entire commit graph. This is because we couldn't distinguish between 'drop' commits that were part of the common subgraph, and those that were still looking for it. 2. If we traversed through an initial part of the common subgraph from head commits before reaching it from tail commits, these commits were returned from findtwixt even though they were also reachable from tail commits. 3. In the same case as 2, we might end up choosing an incorrect commit as the LCA, which is an ancestor of the real LCA.

make sure callers of got_object_idset_add() free data.