From: Stefan Sperling Subject: speep up privsep packed object enumeration To: gameoftrees@openbsd.org Date: Fri, 13 Nov 2026 00:05:23 +0100 This patch improves the speed of 'gotadmin pack' during the phase where the main process asks got-read-pack to enumerate objects. Previously this code was using the standard tree object imsg data structures, which include information that is not needed when enumerating objects. For example, tree paths passed back from got-read-pack were run through a hash function once, and never used for anything else. It's cheaper to pass the 4 byte hash instead of the full path from one process to another. My patch introduces a dedicated message data structure to reduce such overhead as much as possible. My test case was running just the enumeration phase on a git.git repo which contains commit history up to Git's 1c00d2d8392f603a6263f11f1a50fde96ae5475e In this debug build, 'gotadmin pack' exits with "feature not implemented" as soon as object enumeration is done (a change not part of my diff below). Before: $ time gotadmin pack -a master 80846 commits colored; 399225 objects found; 160376 trees scanned gotadmin: feature not implemented 1m59.86s real 2m11.57s user 0m09.13s system After: $ time gotadmin pack -a master 80846 commits colored; 399225 objects found; 160376 trees scanned gotadmin: feature not implemented 1m29.78s real 1m39.55s user 0m06.81s system ok? I would let this wait until we have shipped another release to give us some more time to find regressions, just in case. M lib/got_lib_object.h | 4+ 2- M lib/got_lib_object_parse.h | 1+ 0- M lib/got_lib_pack_create.h | 2+ 2- M lib/got_lib_privsep.h | 19+ 5- M lib/object.c | 6+ 0- M lib/object_open_privsep.c | 4+ 3- M lib/pack_create.c | 19+ 20- M lib/pack_create_privsep.c | 56+ 33- M lib/privsep.c | 154+ 55- M libexec/got-fetch-pack/Makefile | 1+ 1- M libexec/got-index-pack/Makefile | 1+ 1- M libexec/got-read-blob/Makefile | 2+ 1- M libexec/got-read-commit/Makefile | 2+ 1- M libexec/got-read-gitconfig/Makefile | 2+ 1- M libexec/got-read-gotconfig/Makefile | 2+ 1- M libexec/got-read-object/Makefile | 1+ 1- M libexec/got-read-pack/Makefile | 2+ 1- M libexec/got-read-pack/got-read-pack.c | 17+ 8- M libexec/got-read-patch/Makefile | 1+ 1- M libexec/got-read-tag/Makefile | 1+ 1- M libexec/got-read-tree/Makefile | 1+ 1- M libexec/got-send-pack/Makefile | 1+ 1- 22 files changed, 299 insertions(+), 140 deletions(-) commit - 3b135bab5adc6aaaa9911f0198c31904e748863c936ce978c7c7b08fb39e707d commit + 0a5ca735e28279b47a3f2988c1abcbeaea593b1671338013f06eac3d12f48537 blob - 466de69000e375badc1529f54563086b9c3918212a251c7d701be8f835b8599b blob + ea71a0e6eb48907657929762e8eee02762de3dda8e69bff7c6a72f7dfb07b2ad --- lib/got_lib_object.h +++ lib/got_lib_object.h @@ -75,6 +75,7 @@ struct got_tree_entry { char name[NAME_MAX + 1 /* NUL */]; struct got_object_id id; int idx; + uint32_t path_hash; }; struct got_tree_object { @@ -142,6 +143,7 @@ const struct got_error *got_object_tag_open(struct got struct got_repository *, struct got_object *); const struct got_error *got_object_tree_entry_dup(struct got_tree_entry **, struct got_tree_entry *); +uint32_t got_tree_entry_get_path_hash(struct got_tree_entry *); const struct got_error *got_traverse_packed_commits( struct got_object_id_queue *, struct got_object_id *, const char *, @@ -150,13 +152,13 @@ const struct got_error *got_traverse_packed_commits( typedef const struct got_error *(*got_object_enumerate_commit_cb)(void *, time_t, struct got_object_id *, struct got_repository *); typedef const struct got_error *(*got_object_enumerate_tree_cb)(void *, - struct got_tree_object *, time_t, struct got_object_id *, const char *, + struct got_tree_object *, time_t, struct got_object_id *, uint32_t, struct got_repository *); const struct got_error *got_object_enumerate(int *, got_object_enumerate_commit_cb, got_object_enumerate_tree_cb, void *, struct got_object_id **, int, struct got_object_id **, int, - struct got_packidx *, struct got_repository *); + struct got_packidx *, uint32_t, struct got_repository *); const struct got_error *got_object_raw_alloc(struct got_raw_object **, uint8_t *, int *, size_t, size_t, off_t); blob - e9f1e54db514d0bd77135e022b9353b6d4ed77cff511badfcc6c5f8833452fa5 blob + 2497d379ee67dc4c40ea9258a43c970fac8d05dea51ab32cde4bd3e8245792dd --- lib/got_lib_object_parse.h +++ lib/got_lib_object_parse.h @@ -33,6 +33,7 @@ struct got_parsed_tree_entry { uint8_t *id; /* Points to ID in parsed tree buffer. */ size_t digest_len; int algo; + uint32_t path_hash; }; const struct got_error *got_object_parse_tree_entry( struct got_parsed_tree_entry *, size_t *, char *, size_t, size_t, enum got_hash_algorithm); blob - 2e29868d22b9f1a66c18c61a91f47618a0bd745f8d36a74d0f102a8b8b2cfa8c blob + 589712e679d6f92ea421ad230afaf30e2ae0d8e6289b72b83ca8f65424704945 --- lib/got_lib_pack_create.h +++ lib/got_lib_pack_create.h @@ -139,8 +139,8 @@ got_pack_load_tree(int want_meta, struct got_object_id const struct got_error * got_pack_add_object(int want_meta, struct got_object_idset *idset, - struct got_object_id *id, const char *path, int obj_type, - time_t mtime, uint32_t seed, int loose_obj_only, + struct got_object_id *id, uint32_t path_hash, int obj_type, + time_t mtime, int loose_obj_only, struct got_repository *repo, int *ncolored, int *nfound, int *ntrees, got_pack_progress_cb progress_cb, void *progress_arg, struct got_ratelimit *rl); blob - ade7a6256532fd819e304c6e7900937a8d39bd80934bb499c9d5f026e2cf3350 blob + d412683b9daab3a372fb45922d7782bd5dfc329576a82deaff0b10b5c3313a91 --- lib/got_lib_privsep.h +++ lib/got_lib_privsep.h @@ -146,6 +146,7 @@ enum got_imsg_type { GOT_IMSG_OBJECT_ENUMERATION_REQUEST, GOT_IMSG_ENUMERATED_COMMIT, GOT_IMSG_ENUMERATED_TREE, + GOT_IMSG_ENUMERATED_TREE_ENTRIES, GOT_IMSG_TREE_ENUMERATION_DONE, GOT_IMSG_OBJECT_ENUMERATION_DONE, GOT_IMSG_OBJECT_ENUMERATION_INCOMPLETE, @@ -622,10 +623,22 @@ struct got_imsg_enumerated_commit { struct got_imsg_enumerated_tree { struct got_object_id id; /* tree ID */ int nentries; /* number of tree entries */ + uint32_t path_hash; - /* Followed by tree's path in remaining data of imsg buffer. */ + /* Followed by nentries tree-entries in subsequent messages. */ +} __attribute__((__packed__)); - /* Followed by nentries * GOT_IMSG_TREE_ENTRY messages. */ +/* Structure for GOT_IMSG_ENUMERATED_TREE_ENTRIES */ +struct got_imsg_enumerated_tree_entries { + size_t nentries; /* Number of tree entries contained in this message. */ + + /* Followed by nentries * struct got_imsg_enumerated_tree_entry */ +}; + +struct got_imsg_enumerated_tree_entry { + char id[GOT_HASH_DIGEST_MAXLEN]; + mode_t mode; + uint32_t path_hash; } __attribute__((__packed__)); /* @@ -815,10 +828,10 @@ const struct got_error *got_privsep_recv_traversed_com struct got_commit_object **, struct got_object_id_queue *, struct imsgbuf *); const struct got_error *got_privsep_send_enumerated_tree(size_t *, - struct imsgbuf *, struct got_object_id *, const char *, + struct imsgbuf *, struct got_object_id *, const char *, uint32_t, struct got_parsed_tree_entry *, int); const struct got_error *got_privsep_send_object_enumeration_request( - struct imsgbuf *); + struct imsgbuf *, uint32_t); const struct got_error *got_privsep_send_object_enumeration_done( struct imsgbuf *); const struct got_error *got_privsep_send_object_enumeration_incomplete( @@ -827,7 +840,8 @@ const struct got_error *got_privsep_send_enumerated_co struct got_object_id *, time_t); const struct got_error *got_privsep_recv_enumerated_objects(int *, struct imsgbuf *, got_object_enumerate_commit_cb, - got_object_enumerate_tree_cb, void *, struct got_repository *); + got_object_enumerate_tree_cb, void *, struct got_repository *, + enum got_hash_algorithm); const struct got_error *got_privsep_send_raw_delta_req(struct imsgbuf *, int, struct got_object_id *); blob - 444fc618d9c701f076fdb776ddaf8bcfa69bc5e3fad8b660b6ed49c6410a689d blob + 4f685b225db3af133fb4a65a4c81d41cada812668c8184b237d06185458257ba --- lib/object.c +++ lib/object.c @@ -224,6 +224,12 @@ got_tree_entry_get_id(struct got_tree_entry *te) return &te->id; } +uint32_t +got_tree_entry_get_path_hash(struct got_tree_entry *te) +{ + return te->path_hash; +} + const struct got_error * got_object_blob_read_to_str(char **s, struct got_blob_object *blob) { blob - b3a1d145a308f92d8a155c08904fb679735e22c3e661c90248ed7ab96ae534bc blob + 0e174251d607ace24ec639e21fe05b9a504191110dc41be3da5ad7280d6a4834 --- lib/object_open_privsep.c +++ lib/object_open_privsep.c @@ -1282,7 +1282,7 @@ got_object_enumerate(int *found_all_objects, got_object_enumerate_tree_cb cb_tree, void *cb_arg, struct got_object_id **ours, int nours, struct got_object_id **theirs, int ntheirs, - struct got_packidx *packidx, struct got_repository *repo) + struct got_packidx *packidx, uint32_t seed, struct got_repository *repo) { const struct got_error *err = NULL; struct got_pack *pack; @@ -1307,7 +1307,7 @@ got_object_enumerate(int *found_all_objects, } err = got_privsep_send_object_enumeration_request( - pack->privsep_child->ibuf); + pack->privsep_child->ibuf, seed); if (err) goto done; @@ -1328,7 +1328,8 @@ got_object_enumerate(int *found_all_objects, goto done; err = got_privsep_recv_enumerated_objects(found_all_objects, - pack->privsep_child->ibuf, cb_commit, cb_tree, cb_arg, repo); + pack->privsep_child->ibuf, cb_commit, cb_tree, cb_arg, repo, + got_repo_get_hash_algo(repo)); done: free(path_packfile); return err; blob - 2ea2ba8a4bdaa85426537bb42be2a2c0999043202f43bc9ad53c97a9cd7b4720 blob + 167876f05813be7e7d49f6cc6a730916223efa6b82ecbfee9711a49db0f54db6 --- lib/pack_create.c +++ lib/pack_create.c @@ -78,7 +78,7 @@ static const struct got_error * alloc_meta(struct got_pack_meta **new, struct got_object_id *id, - const char *path, int obj_type, time_t mtime, uint32_t seed) + uint32_t path_hash, int obj_type, time_t mtime) { struct got_pack_meta *m; @@ -90,7 +90,7 @@ alloc_meta(struct got_pack_meta **new, struct got_obje memcpy(&m->id, id, sizeof(m->id)); - m->path_hash = murmurhash2(path, strlen(path), seed); + m->path_hash = path_hash; m->obj_type = obj_type; m->mtime = mtime; *new = m; @@ -746,8 +746,8 @@ search_packidx(int *found, struct got_object_id *id, const struct got_error * got_pack_add_object(int want_meta, struct got_object_idset *idset, - struct got_object_id *id, const char *path, int obj_type, - time_t mtime, uint32_t seed, int loose_obj_only, + struct got_object_id *id, uint32_t path_hash, int obj_type, + time_t mtime, int loose_obj_only, struct got_repository *repo, int *ncolored, int *nfound, int *ntrees, got_pack_progress_cb progress_cb, void *progress_arg, struct got_ratelimit *rl) @@ -765,7 +765,7 @@ got_pack_add_object(int want_meta, struct got_object_i } if (want_meta) { - err = alloc_meta(&m, id, path, obj_type, mtime, seed); + err = alloc_meta(&m, id, path_hash, obj_type, mtime); if (err) return err; @@ -843,13 +843,6 @@ got_pack_load_tree_entries(struct got_object_id_queue got_object_idset_contains(idset_exclude, id)) continue; - /* - * If got-read-pack is crawling trees for us then - * we are only here to collect blob IDs. - */ - if (ids == NULL && S_ISDIR(mode)) - continue; - ret = snprintf(p, psize, "%s%s%s", dpath, got_path_is_root_dir(dpath) ? "" : "/", got_tree_entry_get_name(e)); @@ -893,9 +886,12 @@ got_pack_load_tree_entries(struct got_object_id_queue } STAILQ_INSERT_TAIL(ids, qid, entry); } else if (S_ISREG(mode) || S_ISLNK(mode)) { + uint32_t path_hash; + + path_hash = murmurhash2(p, strlen(p), seed); err = got_pack_add_object(want_meta, - want_meta ? idset : idset_exclude, id, p, - GOT_OBJ_TYPE_BLOB, mtime, seed, loose_obj_only, + want_meta ? idset : idset_exclude, id, path_hash, + GOT_OBJ_TYPE_BLOB, mtime, loose_obj_only, repo, ncolored, nfound, ntrees, progress_cb, progress_arg, rl); if (err) @@ -940,6 +936,8 @@ got_pack_load_tree(int want_meta, struct got_object_id while (!STAILQ_EMPTY(&tree_ids)) { const char *path; + uint32_t path_hash; + if (cancel_cb) { err = (*cancel_cb)(cancel_arg); if (err) @@ -957,10 +955,11 @@ got_pack_load_tree(int want_meta, struct got_object_id continue; } + path_hash = murmurhash2(path, strlen(path), seed); err = got_pack_add_object(want_meta, want_meta ? idset : idset_exclude, - &qid->id, path, GOT_OBJ_TYPE_TREE, - mtime, seed, loose_obj_only, repo, + &qid->id, path_hash, GOT_OBJ_TYPE_TREE, + mtime, loose_obj_only, repo, ncolored, nfound, ntrees, progress_cb, progress_arg, rl); if (err) { free(qid->data); @@ -1053,8 +1052,8 @@ load_commit(int want_meta, struct got_object_idset *id err = got_pack_add_object(want_meta, want_meta ? idset : idset_exclude, - &qid->id, "", GOT_OBJ_TYPE_COMMIT, - got_object_commit_get_committer_time(commit), seed, + &qid->id, 0, GOT_OBJ_TYPE_COMMIT, + got_object_commit_get_committer_time(commit), loose_obj_only, repo, ncolored, nfound, ntrees, progress_cb, progress_arg, rl); if (err) @@ -1128,8 +1127,8 @@ load_tag(int want_meta, struct got_object_idset *idset return err; err = got_pack_add_object(want_meta, - want_meta ? idset : idset_exclude, id, "", GOT_OBJ_TYPE_TAG, - got_object_tag_get_tagger_time(tag), seed, loose_obj_only, repo, + want_meta ? idset : idset_exclude, id, 0, GOT_OBJ_TYPE_TAG, + got_object_tag_get_tagger_time(tag), loose_obj_only, repo, ncolored, nfound, ntrees, progress_cb, progress_arg, rl); if (err) goto done; blob - 2d3f72ec455ad24f8683a5641a379dbc088091ed0fd6c32375626b9d0d3ace47 blob + 6a4a0e258c032df33536c6290a7d49af96e88df84d93ac464a63ad7c8849ed9e --- lib/pack_create_privsep.c +++ lib/pack_create_privsep.c @@ -19,6 +19,7 @@ #include #include #include +#include #include #include @@ -50,6 +51,8 @@ #include "got_lib_pack_create.h" #include "got_lib_repository.h" +#include "murmurhash2.h" + struct send_id_arg { struct imsgbuf *ibuf; struct got_object_id *ids[GOT_IMSG_OBJ_ID_LIST_MAX_NIDS]; @@ -587,11 +590,9 @@ done: struct load_packed_obj_arg { /* output parameters: */ struct got_object_id *id; - char *dpath; time_t mtime; /* input parameters: */ - uint32_t seed; int want_meta; struct got_object_idset *idset; struct got_object_idset *idset_exclude; @@ -618,21 +619,21 @@ load_packed_commit_id(void *arg, time_t mtime, struct return got_pack_add_object(a->want_meta, a->want_meta ? a->idset : a->idset_exclude, - id, "", GOT_OBJ_TYPE_COMMIT, mtime, a->seed, a->loose_obj_only, + id, 0, GOT_OBJ_TYPE_COMMIT, mtime, a->loose_obj_only, repo, a->ncolored, a->nfound, a->ntrees, a->progress_cb, a->progress_arg, a->rl); } static const struct got_error * -load_packed_tree_ids(void *arg, struct got_tree_object *tree, time_t mtime, - struct got_object_id *id, const char *dpath, struct got_repository *repo) +load_packed_trees(void *arg, struct got_tree_object *tree, time_t mtime, + struct got_object_id *id, uint32_t path_hash, struct got_repository *repo) { const struct got_error *err; struct load_packed_obj_arg *a = arg; - const char *relpath; + int i; /* - * When we receive a tree's ID and path but not the tree itself, + * When we receive a tree's ID but not the tree itself then * this tree object was not found in the pack file. This is the * last time we are being called for this optimized traversal. * Return from here and switch to loading objects the slow way. @@ -642,20 +643,9 @@ load_packed_tree_ids(void *arg, struct got_tree_object a->id = got_object_id_dup(id); if (a->id == NULL) { err = got_error_from_errno("got_object_id_dup"); - free(a->dpath); - a->dpath = NULL; return err; } - free(a->dpath); - a->dpath = strdup(dpath); - if (a->dpath == NULL) { - err = got_error_from_errno("strdup"); - free(a->id); - a->id = NULL; - return err; - } - a->mtime = mtime; return NULL; } @@ -664,23 +654,58 @@ load_packed_tree_ids(void *arg, struct got_tree_object got_object_idset_contains(a->idset_exclude, id)) return NULL; - relpath = dpath; - while (relpath[0] == '/') - relpath++; - err = got_pack_add_object(a->want_meta, a->want_meta ? a->idset : a->idset_exclude, - id, relpath, GOT_OBJ_TYPE_TREE, mtime, a->seed, + id, path_hash, GOT_OBJ_TYPE_TREE, mtime, a->loose_obj_only, repo, a->ncolored, a->nfound, a->ntrees, a->progress_cb, a->progress_arg, a->rl); if (err) return err; - return got_pack_load_tree_entries(NULL, a->want_meta, a->idset, - a->idset_exclude, tree, id, dpath, mtime, a->seed, repo, - a->loose_obj_only, a->ncolored, a->nfound, a->ntrees, - a->progress_cb, a->progress_arg, a->rl, - a->cancel_cb, a->cancel_arg); + (*a->ntrees)++; + err = got_pack_report_progress(a->progress_cb, a->progress_arg, a->rl, + *a->ncolored, *a->nfound, *a->ntrees, 0L, 0, 0, 0, 0, 0); + if (err) + return err; + + for (i = 0; i < got_object_tree_get_nentries(tree); i++) { + struct got_tree_entry *e; + struct got_object_id *id; + mode_t mode; + + if (a->cancel_cb) { + err = (*a->cancel_cb)(a->cancel_arg); + if (err) + return err; + } + + e = got_object_tree_get_entry(tree, i); + if (e == NULL) /* should not happen */ + return got_error(GOT_ERR_NO_TREE_ENTRY); + + id = got_tree_entry_get_id(e); + + if (got_object_tree_entry_is_submodule(e) || + got_object_idset_contains(a->idset, id) || + got_object_idset_contains(a->idset_exclude, id)) + continue; + + mode = got_tree_entry_get_mode(e); + if (S_ISREG(mode) || S_ISLNK(mode)) { + err = got_pack_add_object(a->want_meta, + a->want_meta ? a->idset : a->idset_exclude, + id, got_tree_entry_get_path_hash(e), + GOT_OBJ_TYPE_BLOB, mtime, + a->loose_obj_only, repo, + a->ncolored, a->nfound, a->ntrees, + a->progress_cb, a->progress_arg, a->rl); + if (err) + return err; + } + + } + + return NULL; } const struct got_error * @@ -698,7 +723,6 @@ got_pack_load_packed_object_ids(int *found_all_objects struct load_packed_obj_arg lpa; memset(&lpa, 0, sizeof(lpa)); - lpa.seed = seed; lpa.want_meta = want_meta; lpa.idset = idset; lpa.idset_exclude = idset_exclude; @@ -714,8 +738,8 @@ got_pack_load_packed_object_ids(int *found_all_objects /* Attempt to load objects via got-read-pack, as far as possible. */ err = got_object_enumerate(found_all_objects, load_packed_commit_id, - load_packed_tree_ids, &lpa, ours, nours, theirs, ntheirs, - packidx, repo); + load_packed_trees, &lpa, ours, nours, theirs, ntheirs, + packidx, seed, repo); if (err) return err; @@ -728,10 +752,9 @@ got_pack_load_packed_object_ids(int *found_all_objects * Continue loading trees the slow way. */ err = got_pack_load_tree(want_meta, idset, idset_exclude, - lpa.id, lpa.dpath, lpa.mtime, seed, repo, loose_obj_only, + lpa.id, "/", lpa.mtime, seed, repo, loose_obj_only, ncolored, nfound, ntrees, progress_cb, progress_arg, rl, cancel_cb, cancel_arg); free(lpa.id); - free(lpa.dpath); return err; } blob - edbfb2be10c241fce8005f5589b6c3aeff4a755fa3a4f72f25af378fa2740cad blob + 1be166fb18e0fb01f0462abefaed0598f5ab52239d17cad14eebeaff5c9b61fa --- lib/privsep.c +++ lib/privsep.c @@ -53,6 +53,8 @@ #include "got_privsep.h" +#include "murmurhash2.h" + #ifndef MIN #define MIN(_a,_b) ((_a) < (_b) ? (_a) : (_b)) #endif @@ -2772,32 +2774,110 @@ got_privsep_recv_traversed_commits(struct got_commit_o return err; } +static const struct got_error * +send_enumerated_tree_entries_batch(struct imsgbuf *ibuf, + struct got_parsed_tree_entry *entries, int idx0, int idxN, size_t len) +{ + struct ibuf *wbuf; + struct got_imsg_enumerated_tree_entries ientries; + int i; + + memset(&ientries, 0, sizeof(ientries)); + + wbuf = imsg_create(ibuf, GOT_IMSG_ENUMERATED_TREE_ENTRIES, 0, 0, len); + if (wbuf == NULL) + return got_error_from_errno("imsg_create TREE_ENTRY"); + + ientries.nentries = idxN - idx0 + 1; + if (imsg_add(wbuf, &ientries, sizeof(ientries)) == -1) + return got_error_from_errno("imsg_add TREE_ENTRY"); + + for (i = idx0; i <= idxN; i++) { + static const char gap[12]; /* for sha1 inside sha256 align */ + struct got_parsed_tree_entry *pte = &entries[i]; + + /* + * Keep in sync with struct got_imsg_enumerated_tree_entry + * definition! + */ + if (imsg_add(wbuf, pte->id, pte->digest_len) == -1) + return got_error_from_errno("imsg_add TREE_ENTRY"); + if (pte->algo == GOT_HASH_SHA1 && + imsg_add(wbuf, gap, sizeof(gap)) == -1) + return got_error_from_errno("imsg_add TREE_ENTRY"); + if (imsg_add(wbuf, &pte->mode, sizeof(pte->mode)) == -1) + return got_error_from_errno("imsg_add TREE_ENTRY"); + if (imsg_add(wbuf, &pte->path_hash, + sizeof(pte->path_hash)) == -1) + return got_error_from_errno("imsg_add TREE_ENTRY"); + } + + imsg_close(ibuf, wbuf); + return NULL; +} + +static const struct got_error * +send_enumerated_tree_entries(struct imsgbuf *ibuf, + struct got_parsed_tree_entry *entries, int nentries) +{ + const struct got_error *err = NULL; + int i, j; + size_t entries_len = sizeof(struct got_imsg_enumerated_tree_entries); + + i = 0; + for (j = 0; j < nentries; j++) { + size_t len = sizeof(struct got_imsg_enumerated_tree_entry); + + if (j > 0 && + entries_len + len > MAX_IMSGSIZE - IMSG_HEADER_SIZE) { + err = send_enumerated_tree_entries_batch(ibuf, entries, + i, j - 1, entries_len); + if (err) + return err; + i = j; + entries_len = sizeof( + struct got_imsg_enumerated_tree_entries); + } + + entries_len += len; + } + + if (j > 0) { + err = send_enumerated_tree_entries_batch(ibuf, entries, + i, j - 1, entries_len); + if (err) + return err; + } + + return NULL; +} + const struct got_error * got_privsep_send_enumerated_tree(size_t *totlen, struct imsgbuf *ibuf, - struct got_object_id *tree_id, const char *path, + struct got_object_id *tree_id, const char *path, uint32_t seed, struct got_parsed_tree_entry *entries, int nentries) { const struct got_error *err = NULL; struct ibuf *wbuf; - size_t path_len = strlen(path); - size_t msglen; + uint32_t path_hash = murmurhash2(path, strlen(path), seed); - msglen = sizeof(struct got_imsg_enumerated_tree) + path_len; - wbuf = imsg_create(ibuf, GOT_IMSG_ENUMERATED_TREE, 0, 0, msglen); + wbuf = imsg_create(ibuf, GOT_IMSG_ENUMERATED_TREE, 0, 0, + sizeof(struct got_imsg_enumerated_tree)); if (wbuf == NULL) return got_error_from_errno("imsg_create ENUMERATED_TREE"); + /* Keep in sync with struct got_imsg_enumerated_tree! */ if (imsg_add(wbuf, tree_id, sizeof(*tree_id)) == -1) return got_error_from_errno("imsg_add ENUMERATED_TREE"); if (imsg_add(wbuf, &nentries, sizeof(nentries)) == -1) return got_error_from_errno("imsg_add ENUMERATED_TREE"); - if (imsg_add(wbuf, path, path_len) == -1) + if (imsg_add(wbuf, &path_hash, sizeof(path_hash)) == -1) return got_error_from_errno("imsg_add ENUMERATED_TREE"); imsg_close(ibuf, wbuf); if (entries) { - err = send_tree_entries(ibuf, entries, nentries); + err = send_enumerated_tree_entries(ibuf, entries, nentries); if (err) return err; } @@ -2806,10 +2886,10 @@ got_privsep_send_enumerated_tree(size_t *totlen, struc } const struct got_error * -got_privsep_send_object_enumeration_request(struct imsgbuf *ibuf) +got_privsep_send_object_enumeration_request(struct imsgbuf *ibuf, uint32_t seed) { if (imsg_compose(ibuf, GOT_IMSG_OBJECT_ENUMERATION_REQUEST, - 0, 0, -1, NULL, 0) == -1) + 0, 0, -1, &seed, sizeof(seed)) == -1) return got_error_from_errno("imsg_compose " "OBJECT_ENUMERATION_REQUEST"); @@ -2860,12 +2940,62 @@ got_privsep_send_enumerated_commit(struct imsgbuf *ibu return NULL; } +static const struct got_error * +recv_enumerated_tree_entries(void *data, size_t datalen, + struct got_tree_object *tree, int *nentries, int algo) +{ + const struct got_error *err = NULL; + struct got_imsg_enumerated_tree_entries *ientries; + struct got_tree_entry *te; + size_t te_offset; + size_t i; + + if (datalen <= sizeof(*ientries) || + datalen > MAX_IMSGSIZE - IMSG_HEADER_SIZE) + return got_error(GOT_ERR_PRIVSEP_LEN); + + ientries = (struct got_imsg_enumerated_tree_entries *)data; + if (ientries->nentries > INT_MAX) { + return got_error_msg(GOT_ERR_NO_SPACE, + "too many tree entries"); + } + + te_offset = sizeof(*ientries); + for (i = 0; i < ientries->nentries; i++) { + struct got_imsg_enumerated_tree_entry ite; + uint8_t *buf = (uint8_t *)data + te_offset; + + if (te_offset + sizeof(ite) > datalen) { + err = got_error(GOT_ERR_PRIVSEP_LEN); + break; + } + + /* Might not be aligned, size is ~40 bytes. */ + memcpy(&ite, buf, sizeof(ite)); + + if (*nentries >= tree->nentries) { + err = got_error(GOT_ERR_PRIVSEP_LEN); + break; + } + te = &tree->entries[*nentries]; + memcpy(te->id.hash, ite.id, sizeof(te->id.hash)); + te->id.algo = algo; + te->mode = ite.mode; + te->idx = *nentries; + (*nentries)++; + + te_offset += sizeof(ite); + } + + return err; +} + const struct got_error * got_privsep_recv_enumerated_objects(int *found_all_objects, struct imsgbuf *ibuf, got_object_enumerate_commit_cb cb_commit, got_object_enumerate_tree_cb cb_tree, void *cb_arg, - struct got_repository *repo) + struct got_repository *repo, enum got_hash_algorithm algo) { const struct got_error *err = NULL; struct imsg imsg; @@ -2876,8 +3006,8 @@ got_privsep_recv_enumerated_objects(int *found_all_obj struct got_tree_object tree; struct got_imsg_enumerated_tree *itree; struct got_object_id tree_id; - char *path = NULL, *canon_path = NULL; - size_t datalen, path_len; + uint32_t path_hash = 0; + size_t datalen; int nentries = -1; int done = 0; @@ -2911,47 +3041,18 @@ got_privsep_recv_enumerated_objects(int *found_all_obj err = got_error(GOT_ERR_PRIVSEP_MSG); break; } - if (datalen < sizeof(*itree)) { + if (datalen != sizeof(*itree)) { err = got_error(GOT_ERR_PRIVSEP_LEN); break; } itree = imsg.data; - path_len = datalen - sizeof(*itree); - if (path_len == 0) { - err = got_error(GOT_ERR_PRIVSEP_LEN); - break; - } memcpy(&tree_id, &itree->id, sizeof(tree_id)); - free(path); - path = strndup(imsg.data + sizeof(*itree), path_len); - if (path == NULL) { - err = got_error_from_errno("strndup"); + if (tree_id.algo != algo) { + err = got_error(GOT_ERR_HASH_ALGO); break; } - free(canon_path); - canon_path = malloc(path_len + 1); - if (canon_path == NULL) { - err = got_error_from_errno("malloc"); - break; - } - if (!got_path_is_absolute(path)) { - err = got_error(GOT_ERR_BAD_PATH); - break; - } - if (got_path_is_root_dir(path)) { - /* XXX check what got_canonpath() does wrong */ - canon_path[0] = '/'; - canon_path[1] = '\0'; - } else { - err = got_canonpath(path, canon_path, - path_len + 1); - if (err) - break; - } - if (strcmp(path, canon_path) != 0) { - err = got_error(GOT_ERR_BAD_PATH); - break; - } + memcpy(&path_hash, &itree->path_hash, + sizeof(path_hash)); if (nentries != -1) { err = got_error(GOT_ERR_PRIVSEP_MSG); break; @@ -2963,7 +3064,7 @@ got_privsep_recv_enumerated_objects(int *found_all_obj if (itree->nentries == -1) { /* Tree was not found in pack file. */ err = cb_tree(cb_arg, NULL, mtime, &tree_id, - path, repo); + path_hash, repo); break; } if (itree->nentries > INT_MAX) { @@ -2978,7 +3079,7 @@ got_privsep_recv_enumerated_objects(int *found_all_obj } if (itree->nentries == 0) { err = cb_tree(cb_arg, &tree, mtime, &tree_id, - path, repo); + path_hash, repo); if (err) break; @@ -2991,19 +3092,19 @@ got_privsep_recv_enumerated_objects(int *found_all_obj nentries = 0; } break; - case GOT_IMSG_TREE_ENTRIES: + case GOT_IMSG_ENUMERATED_TREE_ENTRIES: /* Should be preceeded by GOT_IMSG_ENUMERATED_TREE. */ if (nentries <= -1) { err = got_error(GOT_ERR_PRIVSEP_MSG); break; } - err = recv_tree_entries(imsg.data, datalen, - &tree, &nentries); + err = recv_enumerated_tree_entries(imsg.data, datalen, + &tree, &nentries, algo); if (err) break; if (tree.nentries == nentries) { err = cb_tree(cb_arg, &tree, mtime, &tree_id, - path, repo); + path_hash, repo); if (err) break; @@ -3015,7 +3116,7 @@ got_privsep_recv_enumerated_objects(int *found_all_obj break; case GOT_IMSG_TREE_ENUMERATION_DONE: /* All trees have been found and traversed. */ - if (!have_commit || path == NULL || nentries != -1) { + if (!have_commit || nentries != -1) { err = got_error(GOT_ERR_PRIVSEP_MSG); break; } @@ -3041,8 +3142,6 @@ got_privsep_recv_enumerated_objects(int *found_all_obj break; } - free(path); - free(canon_path); free(tree.entries); return err; } blob - 38ebbc8a7bb593a63a64b685ceeb581ec854d1945b3b4853ba70dcdbc8bb1559 blob + 53534769132cee786d810be9516e40233da69eebfccbcc50968e30fcdbb68a70 --- libexec/got-fetch-pack/Makefile +++ libexec/got-fetch-pack/Makefile @@ -5,7 +5,7 @@ PROG= got-fetch-pack SRCS= got-fetch-pack.c error.c inflate.c object_parse.c \ path.c privsep.c hash.c pkt.c gitproto.c ratelimit.c \ - pollfd.c object_qid.c + pollfd.c object_qid.c murmurhash2.c CPPFLAGS = -I${.CURDIR}/../../include -I${.CURDIR}/../../lib blob - c6579efc18f2b33d6b37852067c3972089d51152cb1475e9898f8514d8756f3c blob + d707c3efadbcade2c0a33398f0346217d8f5c61bc4740fe013ce53274d418bac --- libexec/got-index-pack/Makefile +++ libexec/got-index-pack/Makefile @@ -5,7 +5,7 @@ PROG= got-index-pack SRCS= got-index-pack.c error.c inflate.c object_parse.c object_idset.c \ delta_cache.c delta.c pack.c path.c privsep.c hash.c ratelimit.c \ - pack_index.c pollfd.c object_qid.c + pack_index.c pollfd.c object_qid.c murmurhash2.c CPPFLAGS = -I${.CURDIR}/../../include -I${.CURDIR}/../../lib blob - 69251d700dfce7cb832f7c7e5b2210bc7c83d5c11599ec7f033fd15587350377 blob + 8064e1634d3fd5c166834c9409843954fdfc164188fcaa58d87f03dc4de6b7b4 --- libexec/got-read-blob/Makefile +++ libexec/got-read-blob/Makefile @@ -4,7 +4,8 @@ PROG= got-read-blob SRCS= got-read-blob.c error.c inflate.c object_parse.c \ - object_qid.c path.c privsep.c hash.c pollfd.c + object_qid.c path.c privsep.c hash.c pollfd.c \ + murmurhash2.c CPPFLAGS = -I${.CURDIR}/../../include -I${.CURDIR}/../../lib blob - baf6898e5e81dc21c5bd058488fd6bf1fbfc1fa959ba323f343d81c4c21d811e blob + b860c568073f2d9f01f594b9eb343af3ff052c64c6ede2c7e69181c1e3e642f5 --- libexec/got-read-commit/Makefile +++ libexec/got-read-commit/Makefile @@ -4,7 +4,8 @@ PROG= got-read-commit SRCS= got-read-commit.c error.c inflate.c object_parse.c \ - object_qid.c path.c privsep.c hash.c pollfd.c + object_qid.c path.c privsep.c hash.c pollfd.c \ + murmurhash2.c CPPFLAGS = -I${.CURDIR}/../../include -I${.CURDIR}/../../lib blob - 2875902f87ac058f6cb1207df00e583aa2dc29c8756d8cca64f7473e39dc369c blob + f1404c991ebc5d3061735b7392d951cef7d203db789c821026d2077a289e0ac0 --- libexec/got-read-gitconfig/Makefile +++ libexec/got-read-gitconfig/Makefile @@ -4,7 +4,8 @@ PROG= got-read-gitconfig SRCS= got-read-gitconfig.c error.c inflate.c object_parse.c \ - path.c privsep.c hash.c gitconfig.c pollfd.c object_qid.c + path.c privsep.c hash.c gitconfig.c pollfd.c object_qid.c \ + murmurhash2.c CPPFLAGS = -I${.CURDIR}/../../include -I${.CURDIR}/../../lib blob - 123adf46a00ec9bdf79ccfc7c169dd021fb3884002977714bff2784043ae2db3 blob + 5938c6a3b4c180ad25fdf403aa40a767a102463406fa10982228822b8a9b0593 --- libexec/got-read-gotconfig/Makefile +++ libexec/got-read-gotconfig/Makefile @@ -4,7 +4,8 @@ PROG= got-read-gotconfig SRCS= got-read-gotconfig.c error.c inflate.c object_parse.c \ - path.c privsep.c hash.c parse.y pollfd.c object_qid.c + path.c privsep.c hash.c parse.y pollfd.c object_qid.c \ + murmurhash2.c CPPFLAGS = -I${.CURDIR}/../../include -I${.CURDIR}/../../lib -I${.CURDIR} YFLAGS = blob - bca85acf0c2df6134f79e46585f75b18b295a5af7f3933d1ac2e7db765093c37 blob + 30f0c22c9f7c72c824a43b308a560265d3c78b15c7d04473649599f5c644a54f --- libexec/got-read-object/Makefile +++ libexec/got-read-object/Makefile @@ -4,7 +4,7 @@ PROG= got-read-object SRCS= got-read-object.c error.c inflate.c object_parse.c \ - object_qid.c path.c privsep.c hash.c pollfd.c + object_qid.c path.c privsep.c hash.c pollfd.c murmurhash2.c CPPFLAGS = -I${.CURDIR}/../../include -I${.CURDIR}/../../lib blob - f66c3746d91e57b2304758663232eaef8e3bb2c5d1539654ca7eecd49085c6b0 blob + 24aead8e5067733d5b36fcd6d963a51ed8723fca31e81157f7d8eeab53807e18 --- libexec/got-read-pack/Makefile +++ libexec/got-read-pack/Makefile @@ -5,7 +5,8 @@ PROG= got-read-pack SRCS= got-read-pack.c delta.c error.c inflate.c object_cache.c \ object_idset.c object_parse.c opentemp.c pack.c path.c \ - privsep.c hash.c delta_cache.c pollfd.c object_qid.c + privsep.c hash.c delta_cache.c pollfd.c object_qid.c \ + murmurhash2.c CPPFLAGS = -I${.CURDIR}/../../include -I${.CURDIR}/../../lib blob - 648393cf062ff65d428f8c1726f76723fdc54f3b9d29550d1245a70678174ae9 blob + 9b649722260c35accfcb4b5de56c426f821490a5e33fcf1ae6f6ece62e30dce5 --- libexec/got-read-pack/got-read-pack.c +++ libexec/got-read-pack/got-read-pack.c @@ -51,6 +51,8 @@ #include "got_lib_privsep.h" #include "got_lib_pack.h" +#include "murmurhash2.h" + #ifndef nitems #define nitems(_a) (sizeof((_a)) / sizeof((_a)[0])) #endif @@ -1216,8 +1218,8 @@ struct enumerated_tree { static const struct got_error * enumerate_tree(int *have_all_entries, struct imsgbuf *ibuf, size_t *totlen, - struct got_object_id *tree_id, - const char *path, struct got_pack *pack, struct got_packidx *packidx, + struct got_object_id *tree_id, const char *path, uint32_t seed, + struct got_pack *pack, struct got_packidx *packidx, struct got_object_cache *objcache, struct got_object_idset *idset, struct enumerated_tree **trees, size_t *nalloc, size_t *ntrees) { @@ -1286,6 +1288,7 @@ enumerate_tree(int *have_all_entries, struct imsgbuf * struct got_object_qid *eqid = NULL; struct got_parsed_tree_entry *pte = &entries[i]; char *p; + size_t plen; if (!S_ISDIR(pte->mode)) continue; @@ -1301,13 +1304,15 @@ enumerate_tree(int *have_all_entries, struct imsgbuf * eqid->id.algo = pte->algo; memcpy(&eqid->id.hash, pte->id, pte->digest_len); - if (asprintf(&p, "%s%s%s", path, + plen = asprintf(&p, "%s%s%s", path, got_path_is_root_dir(path) ? "" : "/", - pte->name) == -1) { + pte->name); + if (plen == -1) { err = got_error_from_errno("asprintf"); got_object_qid_free(eqid); goto done; } + pte->path_hash = murmurhash2(p, plen, seed); eqid->data = p; STAILQ_INSERT_TAIL(&ids, eqid, entry); } @@ -1348,7 +1353,7 @@ enumerate_tree(int *have_all_entries, struct imsgbuf * for (i = 0; i < *ntrees; i++) { tree = &(*trees)[i]; err = got_privsep_send_enumerated_tree(totlen, - ibuf, &tree->id, tree->path, tree->entries, + ibuf, &tree->id, tree->path, seed, tree->entries, tree->nentries); if (err) goto done; @@ -1373,7 +1378,7 @@ enumerate_tree(int *have_all_entries, struct imsgbuf * * entire tree the slow way. */ err = got_privsep_send_enumerated_tree(totlen, ibuf, - tree_id, "/", NULL, -1); + tree_id, "/", 0, NULL, -1); if (err) goto done; } @@ -1467,9 +1472,13 @@ enumeration_request(struct imsg *imsg, struct imsgbuf int i, idx, have_all_entries = 1; struct enumerated_tree *trees = NULL; size_t ntrees = 0, nalloc = 16, nids = 0; + uint32_t seed; STAILQ_INIT(&commit_ids); + if (imsg_get_data(imsg, &seed, sizeof(seed)) == -1) + return got_error(GOT_ERR_PRIVSEP_LEN); + trees = calloc(nalloc, sizeof(*trees)); if (trees == NULL) return got_error_from_errno("calloc"); @@ -1570,7 +1579,7 @@ enumeration_request(struct imsg *imsg, struct imsgbuf if (idx == -1) { have_all_entries = 0; err = got_privsep_send_enumerated_tree(&totlen, ibuf, - tree_id, "/", NULL, -1); + tree_id, "/", 0, NULL, -1); if (err) goto done; break; @@ -1588,7 +1597,7 @@ enumeration_request(struct imsg *imsg, struct imsgbuf } err = enumerate_tree(&have_all_entries, ibuf, &totlen, - tree_id, "/", pack, packidx, objcache, idset, + tree_id, "/", seed, pack, packidx, objcache, idset, &trees, &nalloc, &ntrees); if (err) goto done; blob - ff6ec4d6af95e1a3db3807555902fc0738bc426fe0dbefc6a0d6aa2d88c4dcad blob + 5f4e4e43a8a6b6f383bf42ff56f023280351174e122b16dab47ea45db2eaa5e6 --- libexec/got-read-patch/Makefile +++ libexec/got-read-patch/Makefile @@ -4,7 +4,7 @@ PROG= got-read-patch SRCS= got-read-patch.c error.c inflate.c object_parse.c \ - path.c privsep.c hash.c pollfd.c object_qid.c + path.c privsep.c hash.c pollfd.c object_qid.c murmurhash2.c CPPFLAGS = -I${.CURDIR}/../../include -I${.CURDIR}/../../lib blob - 996e45896921e5e9bf9feb7bfbc403cb8c77478eac425e485499841236bdfbc4 blob + 2a6062de6ef36f4f249d11f3bcd65e5590f43ab620d06c8e7c56ebb81b0f3224 --- libexec/got-read-tag/Makefile +++ libexec/got-read-tag/Makefile @@ -4,7 +4,7 @@ PROG= got-read-tag SRCS= got-read-tag.c error.c inflate.c object_parse.c \ - object_qid.c path.c privsep.c hash.c pollfd.c + object_qid.c path.c privsep.c hash.c pollfd.c murmurhash2.c CPPFLAGS = -I${.CURDIR}/../../include -I${.CURDIR}/../../lib blob - b20fda233186b6ab3cc9cc62d159cfd4e84273c16cfc583f254740a42a73f052 blob + 647be2b660e6049f8bf5ebe5f920631b8f4e70609ffd5bde5cd71389234eccfe --- libexec/got-read-tree/Makefile +++ libexec/got-read-tree/Makefile @@ -4,7 +4,7 @@ PROG= got-read-tree SRCS= got-read-tree.c error.c inflate.c object_parse.c \ - object_qid.c path.c privsep.c hash.c pollfd.c + object_qid.c path.c privsep.c hash.c pollfd.c murmurhash2.c CPPFLAGS = -I${.CURDIR}/../../include -I${.CURDIR}/../../lib blob - 4c1c1586c6804815604ac182f4b30f2b43c1dc70476e9ce0f466ff081e20438f blob + 59eecabea04b192d03aeca3c7e4eca9402e02e81a2be40704407b461908a9965 --- libexec/got-send-pack/Makefile +++ libexec/got-send-pack/Makefile @@ -5,7 +5,7 @@ PROG= got-send-pack SRCS= got-send-pack.c error.c inflate.c object_parse.c \ path.c privsep.c hash.c pkt.c gitproto.c ratelimit.c \ - pollfd.c reference_parse.c object_qid.c + pollfd.c reference_parse.c object_qid.c murmurhash2.c CPPFLAGS = -I${.CURDIR}/../../include -I${.CURDIR}/../../lib