- From:
- Stefan Sperling <stsp@stsp.name>
- Subject:
- speep up privsep packed object enumeration
- To:
- gameoftrees@openbsd.org
- Date:
- Fri, 13 Nov 2026 00:05:23 +0100
Download raw body.
Thread
speep up privsep packed object enumeration
Download raw body.
speep up privsep packed object enumeration
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 <sys/queue.h>
#include <sys/tree.h>
#include <sys/uio.h>
+#include <sys/stat.h>
#include <sha1.h>
#include <sha2.h>
@@ -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
speep up privsep packed object enumeration