commit ca6e02acaa175cf833a3424ff1c4842445c0109f from: Stefan Sperling date: Tue Jan 07 11:14:52 2020 UTC add support for first-parent history traversal to got-read-pack commit - 33147df7bc894e4498cffb3b04fd04080132c5ce commit + ca6e02acaa175cf833a3424ff1c4842445c0109f blob - 29c3af82ae5c984d7253f7b989561cb43f705e69 blob + 29a4d2fb492f107dfe0f7c24c53f0e54de0dda9c --- lib/commit_graph.c +++ lib/commit_graph.c @@ -40,9 +40,9 @@ struct got_commit_graph_node { struct got_object_id id; - time_t timestamp; - /* Used during graph iteration. */ + /* Used only during iteration. */ + time_t timestamp; TAILQ_ENTRY(got_commit_graph_node) entry; }; @@ -147,10 +147,12 @@ done: static void add_node_to_iter_list(struct got_commit_graph *graph, - struct got_commit_graph_node *node) + struct got_commit_graph_node *node, time_t committer_time) { struct got_commit_graph_node *n, *next; + node->timestamp = committer_time; + n = TAILQ_FIRST(&graph->iter_list); while (n) { next = TAILQ_NEXT(n, entry); @@ -164,6 +166,79 @@ add_node_to_iter_list(struct got_commit_graph *graph, } static const struct got_error * +add_node(struct got_commit_graph_node **new_node, + struct got_commit_graph *graph, struct got_object_id *commit_id, + struct got_repository *repo) +{ + const struct got_error *err = NULL; + struct got_commit_graph_node *node; + + *new_node = NULL; + + node = calloc(1, sizeof(*node)); + if (node == NULL) + return got_error_from_errno("calloc"); + + memcpy(&node->id, commit_id, sizeof(node->id)); + err = got_object_idset_add(graph->node_ids, &node->id, NULL); + if (err) + free(node); + else + *new_node = node; + return err; +} + +/* + * Ask got-read-pack to traverse first-parent history until a commit is + * encountered which modified graph->path, or until the pack file runs + * out of relevant commits. This is faster than sending an individual + * request for each commit stored in the pack file. + */ +static const struct got_error * +packed_first_parent_traversal(int *ncommits_traversed, + struct got_commit_graph *graph, struct got_object_id *commit_id, + struct got_repository *repo) +{ + const struct got_error *err = NULL; + struct got_object_id_queue traversed_commits; + struct got_object_qid *qid; + + SIMPLEQ_INIT(&traversed_commits); + *ncommits_traversed = 0; + + err = got_traverse_packed_commits(&traversed_commits, + commit_id, graph->path, repo); + if (err) + return err; + + /* Add all traversed commits to the graph... */ + SIMPLEQ_FOREACH(qid, &traversed_commits, entry) { + struct got_commit_graph_node *node; + + if (got_object_idset_contains(graph->open_branches, qid->id)) + continue; + if (got_object_idset_contains(graph->node_ids, qid->id)) + continue; + + (*ncommits_traversed)++; + + /* ... except the last commit is the new branch tip. */ + if (SIMPLEQ_NEXT(qid, entry) == NULL) { + err = got_object_idset_add(graph->open_branches, + qid->id, NULL); + break; + } + + err = add_node(&node, graph, qid->id, repo); + if (err) + break; + } + + got_object_id_queue_free(&traversed_commits); + return err; +} + +static const struct got_error * close_branch(struct got_commit_graph *graph, struct got_object_id *commit_id) { const struct got_error *err; @@ -190,6 +265,22 @@ advance_branch(struct got_commit_graph *graph, struct if (qid == NULL || got_object_idset_contains(graph->open_branches, qid->id)) return NULL; + /* + * The root directory always changes by definition, and when + * logging the root we want to traverse consecutive commits + * even if they point at the same tree. + * But if we are looking for a specific path then we can avoid + * fetching packed commits which did not modify the path and + * only fetch their IDs. This speeds up 'got blame'. + */ + if (!got_path_is_root_dir(graph->path) && + (commit->flags & GOT_COMMIT_FLAG_PACKED)) { + int ncommits = 0; + err = packed_first_parent_traversal(&ncommits, + graph, qid->id, repo); + if (err || ncommits > 0) + return err; + } return got_object_idset_add(graph->open_branches, qid->id, NULL); } @@ -282,33 +373,6 @@ advance_branch(struct got_commit_graph *graph, struct } return NULL; -} - -static const struct got_error * -add_node(struct got_commit_graph_node **new_node, - struct got_commit_graph *graph, - struct got_object_id *commit_id, - struct got_commit_object *commit, - struct got_repository *repo) -{ - const struct got_error *err = NULL; - struct got_commit_graph_node *node; - - *new_node = NULL; - - node = calloc(1, sizeof(*node)); - if (node == NULL) - return got_error_from_errno("calloc"); - - memcpy(&node->id, commit_id, sizeof(node->id)); - node->timestamp = commit->committer_time; - - err = got_object_idset_add(graph->node_ids, &node->id, NULL); - if (err) - free(node); - else - *new_node = node; - return err; } const struct got_error * @@ -370,7 +434,7 @@ add_branch_tip(struct got_object_id *commit_id, void * if (err) return err; - err = add_node(&new_node, a->graph, commit_id, commit, a->repo); + err = add_node(&new_node, a->graph, commit_id, a->repo); if (err) return err; @@ -444,7 +508,8 @@ fetch_commits_from_open_branches(struct got_commit_gra continue; } if (changed) - add_node_to_iter_list(graph, new_node); + add_node_to_iter_list(graph, new_node, + got_object_commit_get_committer_time(commit)); err = advance_branch(graph, commit_id, commit, repo); if (err) break; blob - 2f3281ac854ba937676647e70436adc7c7b38175 blob + 989af7a5c391e8d6a066b2235aecd6c3246aa0d3 --- lib/got_lib_object.h +++ lib/got_lib_object.h @@ -47,6 +47,9 @@ struct got_commit_object { time_t committer_gmtoff; char *logmsg; int refcnt; /* > 0 if open and/or cached */ + + int flags; +#define GOT_COMMIT_FLAG_PACKED 0x01 }; struct got_tree_entry { @@ -102,3 +105,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 *); + +const struct got_error *got_traverse_packed_commits( + struct got_object_id_queue *, struct got_object_id *, const char *, + struct got_repository *); blob - aa15a4c961b9caec70632114eb8f2f50b71d5df7 blob + 363157f9fa862d3d8847f8e39601526a53ece92d --- lib/got_lib_pack.h +++ lib/got_lib_pack.h @@ -162,6 +162,7 @@ const struct got_error *got_packidx_init_hdr(struct go const struct got_error *got_packidx_open(struct got_packidx **, const char *, int); const struct got_error *got_packidx_close(struct got_packidx *); +int got_packidx_get_object_idx_sha1(struct got_packidx *, uint8_t *); int got_packidx_get_object_idx(struct got_packidx *, struct got_object_id *); const struct got_error *got_packidx_match_id_str_prefix( struct got_object_id_queue *, struct got_packidx *, const char *); blob - b27325da498aa72413f8377303ba76d4012c7813 blob + 08d4c9dc4e0493c2c7ecc0d939c2320f04ae787f --- lib/got_lib_privsep.h +++ lib/got_lib_privsep.h @@ -102,6 +102,9 @@ enum got_imsg_type { GOT_IMSG_PACKIDX, GOT_IMSG_PACK, GOT_IMSG_PACKED_OBJECT_REQUEST, + GOT_IMSG_COMMIT_TRAVERSAL_REQUEST, + GOT_IMSG_TRAVERSED_COMMITS, + GOT_IMSG_COMMIT_TRAVERSAL_DONE, /* Message sending file descriptor to a temporary file. */ GOT_IMSG_TMPFD, @@ -232,6 +235,20 @@ struct got_imsg_packed_object { int idx; } __attribute__((__packed__)); +/* Structure for GOT_IMSG_COMMIT_TRAVERSAL_REQUEST */ +struct got_imsg_commit_traversal_request { + uint8_t id[SHA1_DIGEST_LENGTH]; + int idx; + size_t path_len; + /* Followed by path_len bytes of path data */ +} __attribute__((__packed__)); + +/* Structure for GOT_IMSG_TRAVERSED_COMMITS */ +struct got_imsg_traversed_commits { + size_t ncommits; + /* Followed by ncommit IDs of SHA1_DIGEST_LENGTH each */ +} __attribute__((__packed__)); + /* * Structure for GOT_IMSG_GITCONFIG_REMOTE data. */ @@ -319,4 +336,14 @@ const struct got_error *got_privsep_send_gitconfig_rem const struct got_error *got_privsep_recv_gitconfig_remotes( struct got_remote_repo **, int *, struct imsgbuf *); +const struct got_error *got_privsep_send_commit_traversal_request( + struct imsgbuf *, struct got_object_id *, int, const char *); +const struct got_error *got_privsep_recv_traversed_commits( + struct got_commit_object **, struct got_object_id **, + struct got_object_id_queue *, struct imsgbuf *); +const struct got_error *got_privsep_send_traversed_commits( + struct got_object_id *, size_t, struct imsgbuf *); +const struct got_error *got_privsep_send_commit_traversal_done( + struct imsgbuf *); + void got_privsep_exec_child(int[2], const char *, const char *); blob - 4aaeb8a3199435ce3b95f7218a552f6375558752 blob + 4f98167915dd8661414656d1b92c2624248f1519 --- lib/object.c +++ lib/object.c @@ -56,18 +56,6 @@ #ifndef MIN #define MIN(_a,_b) ((_a) < (_b) ? (_a) : (_b)) #endif - -struct got_object_id * -got_object_id_dup(struct got_object_id *id1) -{ - struct got_object_id *id2; - - id2 = malloc(sizeof(*id2)); - if (id2 == NULL) - return NULL; - memcpy(id2, id1, sizeof(*id2)); - return id2; -} struct got_object_id * got_object_get_id(struct got_object *obj) @@ -480,7 +468,12 @@ request_packed_commit(struct got_commit_object **commi if (err) return err; - return got_privsep_recv_commit(commit, pack->privsep_child->ibuf); + err = got_privsep_recv_commit(commit, pack->privsep_child->ibuf); + if (err) + return err; + + (*commit)->flags |= GOT_COMMIT_FLAG_PACKED; + return NULL; } static const struct got_error * @@ -1748,4 +1741,67 @@ int got_object_tree_entry_is_submodule(struct got_tree_entry *te) { return (te->mode & S_IFMT) == (S_IFDIR | S_IFLNK); +} + +const struct got_error * +got_traverse_packed_commits(struct got_object_id_queue *traversed_commits, + struct got_object_id *commit_id, const char *path, + struct got_repository *repo) +{ + const struct got_error *err = NULL; + struct got_pack *pack = NULL; + struct got_packidx *packidx = NULL; + char *path_packfile = NULL; + struct got_commit_object *changed_commit = NULL; + struct got_object_id *changed_commit_id = NULL; + int idx; + + err = got_repo_search_packidx(&packidx, &idx, repo, commit_id); + if (err) { + if (err->code != GOT_ERR_NO_OBJ) + return err; + return NULL; + } + + err = get_packfile_path(&path_packfile, packidx); + if (err) + return err; + + pack = got_repo_get_cached_pack(repo, path_packfile); + if (pack == NULL) { + err = got_repo_cache_pack(&pack, repo, path_packfile, packidx); + if (err) + goto done; + } + + if (pack->privsep_child == NULL) { + err = start_pack_privsep_child(pack, packidx); + if (err) + goto done; + } + + err = got_privsep_send_commit_traversal_request( + pack->privsep_child->ibuf, commit_id, idx, path); + if (err) + goto done; + + err = got_privsep_recv_traversed_commits(&changed_commit, + &changed_commit_id, traversed_commits, pack->privsep_child->ibuf); + if (err) + goto done; + + if (changed_commit) { + /* + * Cache the commit in which the path was changed. + * This commit might be opened again soon. + */ + changed_commit->refcnt++; + err = got_repo_cache_commit(repo, changed_commit_id, + changed_commit); + got_object_commit_close(changed_commit); + } +done: + free(path_packfile); + free(changed_commit_id); + return err; } blob - 32d44fbf7ceea77198e8a62d8d0c0cf604e2ed8c blob + d3584125c591dde528f7c8eb8d1eb44dd9728c86 --- lib/object_parse.c +++ lib/object_parse.c @@ -54,6 +54,18 @@ #ifndef nitems #define nitems(_a) (sizeof(_a) / sizeof((_a)[0])) #endif + +struct got_object_id * +got_object_id_dup(struct got_object_id *id1) +{ + struct got_object_id *id2; + + id2 = malloc(sizeof(*id2)); + if (id2 == NULL) + return NULL; + memcpy(id2, id1, sizeof(*id2)); + return id2; +} int got_object_id_cmp(const struct got_object_id *id1, blob - ea83c44496699701bf12591fb8784e500ac8b797 blob + 938d4cf659ed6d1195e4bea48877dd45cc539555 --- lib/pack.c +++ lib/pack.c @@ -430,9 +430,9 @@ get_object_offset(struct got_packidx *packidx, int idx } int -got_packidx_get_object_idx(struct got_packidx *packidx, struct got_object_id *id) +got_packidx_get_object_idx_sha1(struct got_packidx *packidx, uint8_t *sha1) { - u_int8_t id0 = id->sha1[0]; + u_int8_t id0 = sha1[0]; uint32_t totobj = betoh32(packidx->hdr.fanout_table[0xff]); int left = 0, right = totobj - 1; @@ -445,7 +445,7 @@ got_packidx_get_object_idx(struct got_packidx *packidx i = ((left + right) / 2); oid = &packidx->hdr.sorted_ids[i]; - cmp = memcmp(id->sha1, oid->sha1, SHA1_DIGEST_LENGTH); + cmp = memcmp(sha1, oid->sha1, SHA1_DIGEST_LENGTH); if (cmp == 0) return i; else if (cmp > 0) @@ -455,6 +455,12 @@ got_packidx_get_object_idx(struct got_packidx *packidx } return -1; +} + +int +got_packidx_get_object_idx(struct got_packidx *packidx, struct got_object_id *id) +{ + return got_packidx_get_object_idx_sha1(packidx, id->sha1); } const struct got_error * blob - 0e15115f6c894362a4e3046ee857ca73f6637802 blob + a2566dac4aee1eadf39748a400c7710ebdd34828 --- lib/privsep.c +++ lib/privsep.c @@ -549,143 +549,155 @@ done: return err; } -const struct got_error * -got_privsep_recv_commit(struct got_commit_object **commit, struct imsgbuf *ibuf) +static const struct got_error * +get_commit_from_imsg(struct got_commit_object **commit, + struct imsg *imsg, size_t datalen, struct imsgbuf *ibuf) { const struct got_error *err = NULL; - struct imsg imsg; struct got_imsg_commit_object *icommit; - size_t len, datalen; + size_t len = 0; int i; - const size_t min_datalen = - MIN(sizeof(struct got_imsg_error), - sizeof(struct got_imsg_commit_object)); - *commit = NULL; - - err = got_privsep_recv_imsg(&imsg, ibuf, min_datalen); - if (err) - return err; + if (datalen < sizeof(*icommit)) + return got_error(GOT_ERR_PRIVSEP_LEN); - datalen = imsg.hdr.len - IMSG_HEADER_SIZE; - len = 0; + icommit = imsg->data; + if (datalen != sizeof(*icommit) + icommit->author_len + + icommit->committer_len + + icommit->nparents * SHA1_DIGEST_LENGTH) + return got_error(GOT_ERR_PRIVSEP_LEN); - switch (imsg.hdr.type) { - case GOT_IMSG_COMMIT: - if (datalen < sizeof(*icommit)) { - err = got_error(GOT_ERR_PRIVSEP_LEN); - break; - } - icommit = imsg.data; - if (datalen != sizeof(*icommit) + icommit->author_len + - icommit->committer_len + - icommit->nparents * SHA1_DIGEST_LENGTH) { - err = got_error(GOT_ERR_PRIVSEP_LEN); - break; - } - if (icommit->nparents < 0) { - err = got_error(GOT_ERR_PRIVSEP_LEN); - break; - } - len += sizeof(*icommit); + if (icommit->nparents < 0) + return got_error(GOT_ERR_PRIVSEP_LEN); + + len += sizeof(*icommit); - *commit = got_object_commit_alloc_partial(); - if (*commit == NULL) { - err = got_error_from_errno( - "got_object_commit_alloc_partial"); - break; + *commit = got_object_commit_alloc_partial(); + if (*commit == NULL) + return got_error_from_errno( + "got_object_commit_alloc_partial"); + + memcpy((*commit)->tree_id->sha1, icommit->tree_id, + SHA1_DIGEST_LENGTH); + (*commit)->author_time = icommit->author_time; + (*commit)->author_gmtoff = icommit->author_gmtoff; + (*commit)->committer_time = icommit->committer_time; + (*commit)->committer_gmtoff = icommit->committer_gmtoff; + + if (icommit->author_len == 0) { + (*commit)->author = strdup(""); + if ((*commit)->author == NULL) { + err = got_error_from_errno("strdup"); + goto done; } + } else { + (*commit)->author = malloc(icommit->author_len + 1); + if ((*commit)->author == NULL) { + err = got_error_from_errno("malloc"); + goto done; + } + memcpy((*commit)->author, imsg->data + len, + icommit->author_len); + (*commit)->author[icommit->author_len] = '\0'; + } + len += icommit->author_len; - memcpy((*commit)->tree_id->sha1, icommit->tree_id, - SHA1_DIGEST_LENGTH); - (*commit)->author_time = icommit->author_time; - (*commit)->author_gmtoff = icommit->author_gmtoff; - (*commit)->committer_time = icommit->committer_time; - (*commit)->committer_gmtoff = icommit->committer_gmtoff; - - if (icommit->author_len == 0) { - (*commit)->author = strdup(""); - if ((*commit)->author == NULL) { - err = got_error_from_errno("strdup"); - break; - } - } else { - (*commit)->author = malloc(icommit->author_len + 1); - if ((*commit)->author == NULL) { - err = got_error_from_errno("malloc"); - break; - } - memcpy((*commit)->author, imsg.data + len, - icommit->author_len); - (*commit)->author[icommit->author_len] = '\0'; + if (icommit->committer_len == 0) { + (*commit)->committer = strdup(""); + if ((*commit)->committer == NULL) { + err = got_error_from_errno("strdup"); + goto done; + } + } else { + (*commit)->committer = + malloc(icommit->committer_len + 1); + if ((*commit)->committer == NULL) { + err = got_error_from_errno("malloc"); + goto done; + } + memcpy((*commit)->committer, imsg->data + len, + icommit->committer_len); + (*commit)->committer[icommit->committer_len] = '\0'; + } + len += icommit->committer_len; + + if (icommit->logmsg_len == 0) { + (*commit)->logmsg = strdup(""); + if ((*commit)->logmsg == NULL) { + err = got_error_from_errno("strdup"); + goto done; + } + } else { + size_t offset = 0, remain = icommit->logmsg_len; + + (*commit)->logmsg = malloc(icommit->logmsg_len + 1); + if ((*commit)->logmsg == NULL) { + err = got_error_from_errno("malloc"); + goto done; } - len += icommit->author_len; + while (remain > 0) { + struct imsg imsg_log; + size_t n = MIN(MAX_IMSGSIZE - IMSG_HEADER_SIZE, + remain); - if (icommit->committer_len == 0) { - (*commit)->committer = strdup(""); - if ((*commit)->committer == NULL) { - err = got_error_from_errno("strdup"); - break; - } - } else { - (*commit)->committer = - malloc(icommit->committer_len + 1); - if ((*commit)->committer == NULL) { - err = got_error_from_errno("malloc"); - break; - } - memcpy((*commit)->committer, imsg.data + len, - icommit->committer_len); - (*commit)->committer[icommit->committer_len] = '\0'; - } - len += icommit->committer_len; + err = got_privsep_recv_imsg(&imsg_log, ibuf, n); + if (err) + goto done; - if (icommit->logmsg_len == 0) { - (*commit)->logmsg = strdup(""); - if ((*commit)->logmsg == NULL) { - err = got_error_from_errno("strdup"); - break; + if (imsg_log.hdr.type != GOT_IMSG_COMMIT_LOGMSG) { + err = got_error(GOT_ERR_PRIVSEP_MSG); + goto done; } - } else { - size_t offset = 0, remain = icommit->logmsg_len; - (*commit)->logmsg = malloc(icommit->logmsg_len + 1); - if ((*commit)->logmsg == NULL) { - err = got_error_from_errno("malloc"); - break; - } - while (remain > 0) { - struct imsg imsg_log; - size_t n = MIN(MAX_IMSGSIZE - IMSG_HEADER_SIZE, - remain); - - err = got_privsep_recv_imsg(&imsg_log, ibuf, n); - if (err) - return err; - - if (imsg_log.hdr.type != GOT_IMSG_COMMIT_LOGMSG) - return got_error(GOT_ERR_PRIVSEP_MSG); - - memcpy((*commit)->logmsg + offset, - imsg_log.data, n); - imsg_free(&imsg_log); - offset += n; - remain -= n; - } - (*commit)->logmsg[icommit->logmsg_len] = '\0'; + memcpy((*commit)->logmsg + offset, + imsg_log.data, n); + imsg_free(&imsg_log); + offset += n; + remain -= n; } + (*commit)->logmsg[icommit->logmsg_len] = '\0'; + } - for (i = 0; i < icommit->nparents; i++) { - struct got_object_qid *qid; + for (i = 0; i < icommit->nparents; i++) { + struct got_object_qid *qid; - err = got_object_qid_alloc_partial(&qid); - if (err) - break; - memcpy(qid->id, imsg.data + len + - i * SHA1_DIGEST_LENGTH, sizeof(*qid->id)); - SIMPLEQ_INSERT_TAIL(&(*commit)->parent_ids, qid, entry); - (*commit)->nparents++; - } + err = got_object_qid_alloc_partial(&qid); + if (err) + break; + memcpy(qid->id, imsg->data + len + + i * SHA1_DIGEST_LENGTH, sizeof(*qid->id)); + SIMPLEQ_INSERT_TAIL(&(*commit)->parent_ids, qid, entry); + (*commit)->nparents++; + } +done: + if (err) { + got_object_commit_close(*commit); + *commit = NULL; + } + return err; +} + +const struct got_error * +got_privsep_recv_commit(struct got_commit_object **commit, struct imsgbuf *ibuf) +{ + const struct got_error *err = NULL; + struct imsg imsg; + size_t datalen; + const size_t min_datalen = + MIN(sizeof(struct got_imsg_error), + sizeof(struct got_imsg_commit_object)); + + *commit = NULL; + + err = got_privsep_recv_imsg(&imsg, ibuf, min_datalen); + if (err) + return err; + + datalen = imsg.hdr.len - IMSG_HEADER_SIZE; + + switch (imsg.hdr.type) { + case GOT_IMSG_COMMIT: + err = get_commit_from_imsg(commit, &imsg, datalen, ibuf); break; default: err = got_error(GOT_ERR_PRIVSEP_MSG); @@ -1545,9 +1557,165 @@ got_privsep_recv_gitconfig_remotes(struct got_remote_r *nremotes = 0; } return err; +} + +const struct got_error * +got_privsep_send_commit_traversal_request(struct imsgbuf *ibuf, + struct got_object_id *id, int idx, const char *path) +{ + const struct got_error *err = NULL; + struct ibuf *wbuf; + size_t path_len = strlen(path) + 1; + + wbuf = imsg_create(ibuf, GOT_IMSG_COMMIT_TRAVERSAL_REQUEST, 0, 0, + sizeof(struct got_imsg_commit_traversal_request) + path_len); + if (wbuf == NULL) + return got_error_from_errno( + "imsg_create COMMIT_TRAVERSAL_REQUEST"); + if (imsg_add(wbuf, id->sha1, SHA1_DIGEST_LENGTH) == -1) { + err = got_error_from_errno("imsg_add COMMIT_TRAVERSAL_REQUEST"); + ibuf_free(wbuf); + return err; + } + if (imsg_add(wbuf, &idx, sizeof(idx)) == -1) { + err = got_error_from_errno("imsg_add COMMIT_TRAVERSAL_REQUEST"); + ibuf_free(wbuf); + return err; + } + if (imsg_add(wbuf, path, path_len) == -1) { + err = got_error_from_errno("imsg_add COMMIT_TRAVERSAL_REQUEST"); + ibuf_free(wbuf); + return err; + } + + wbuf->fd = -1; + imsg_close(ibuf, wbuf); + + return flush_imsg(ibuf); } const struct got_error * +got_privsep_send_traversed_commits(struct got_object_id *commit_ids, + size_t ncommits, struct imsgbuf *ibuf) +{ + const struct got_error *err; + struct ibuf *wbuf; + int i; + + wbuf = imsg_create(ibuf, GOT_IMSG_TRAVERSED_COMMITS, 0, 0, + sizeof(struct got_imsg_traversed_commits) + + ncommits * SHA1_DIGEST_LENGTH); + if (wbuf == NULL) + return got_error_from_errno("imsg_create TRAVERSED_COMMITS"); + + if (imsg_add(wbuf, &ncommits, sizeof(ncommits)) == -1) { + err = got_error_from_errno("imsg_add TRAVERSED_COMMITS"); + ibuf_free(wbuf); + return err; + } + for (i = 0; i < ncommits; i++) { + struct got_object_id *id = &commit_ids[i]; + if (imsg_add(wbuf, id->sha1, SHA1_DIGEST_LENGTH) == -1) { + err = got_error_from_errno( + "imsg_add TRAVERSED_COMMITS"); + ibuf_free(wbuf); + return err; + } + } + + wbuf->fd = -1; + imsg_close(ibuf, wbuf); + + return flush_imsg(ibuf); +} + +const struct got_error * +got_privsep_recv_traversed_commits(struct got_commit_object **changed_commit, + struct got_object_id **changed_commit_id, + struct got_object_id_queue *commit_ids, struct imsgbuf *ibuf) +{ + const struct got_error *err = NULL; + struct imsg imsg; + struct got_imsg_traversed_commits *icommits; + size_t datalen; + int i, done = 0; + + *changed_commit = NULL; + *changed_commit_id = NULL; + + while (!done) { + err = got_privsep_recv_imsg(&imsg, ibuf, 0); + if (err) + return err; + + datalen = imsg.hdr.len - IMSG_HEADER_SIZE; + switch (imsg.hdr.type) { + case GOT_IMSG_TRAVERSED_COMMITS: + icommits = imsg.data; + if (datalen != sizeof(*icommits) + + icommits->ncommits * SHA1_DIGEST_LENGTH) { + err = got_error(GOT_ERR_PRIVSEP_LEN); + break; + } + for (i = 0; i < icommits->ncommits; i++) { + struct got_object_qid *qid; + uint8_t *sha1 = (uint8_t *)imsg.data + + sizeof(*icommits) + i * SHA1_DIGEST_LENGTH; + err = got_object_qid_alloc_partial(&qid); + if (err) + break; + memcpy(qid->id->sha1, sha1, SHA1_DIGEST_LENGTH); + SIMPLEQ_INSERT_TAIL(commit_ids, qid, entry); + + /* The last commit may contain a change. */ + if (i == icommits->ncommits - 1) { + *changed_commit_id = + got_object_id_dup(qid->id); + if (*changed_commit_id == NULL) { + err = got_error_from_errno( + "got_object_id_dup"); + break; + } + } + } + break; + case GOT_IMSG_COMMIT: + if (*changed_commit_id == NULL) { + err = got_error(GOT_ERR_PRIVSEP_MSG); + break; + } + err = get_commit_from_imsg(changed_commit, &imsg, + datalen, ibuf); + break; + case GOT_IMSG_COMMIT_TRAVERSAL_DONE: + done = 1; + break; + default: + err = got_error(GOT_ERR_PRIVSEP_MSG); + break; + } + + imsg_free(&imsg); + if (err) + break; + } + + if (err) + got_object_id_queue_free(commit_ids); + return err; +} + +const struct got_error * +got_privsep_send_commit_traversal_done(struct imsgbuf *ibuf) +{ + if (imsg_compose(ibuf, GOT_IMSG_COMMIT_TRAVERSAL_DONE, 0, 0, -1, + NULL, 0) == -1) + return got_error_from_errno("imsg_compose TRAVERSAL_DONE"); + + return flush_imsg(ibuf); +} + +const struct got_error * got_privsep_unveil_exec_helpers(void) { const char *helpers[] = { blob - b10c699ebc8f5fe4fa7e3e5e9e256811a3a11687 blob + 49133597718c2ff09eff39bb48313bb803aea2e4 --- libexec/got-read-pack/got-read-pack.c +++ libexec/got-read-pack/got-read-pack.c @@ -106,30 +106,23 @@ done: return err; } -static const struct got_error * -commit_request(struct imsg *imsg, struct imsgbuf *ibuf, struct got_pack *pack, - struct got_packidx *packidx, struct got_object_cache *objcache) +const struct got_error * +open_commit(struct got_commit_object **commit, struct got_pack *pack, + struct got_packidx *packidx, int obj_idx, struct got_object_id *id, + struct got_object_cache *objcache) { const struct got_error *err = NULL; - struct got_imsg_packed_object iobj; struct got_object *obj = NULL; - struct got_commit_object *commit = NULL; uint8_t *buf = NULL; size_t len; - struct got_object_id id; - size_t datalen; - datalen = imsg->hdr.len - IMSG_HEADER_SIZE; - if (datalen != sizeof(iobj)) - return got_error(GOT_ERR_PRIVSEP_LEN); - memcpy(&iobj, imsg->data, sizeof(iobj)); - memcpy(id.sha1, iobj.id, SHA1_DIGEST_LENGTH); + *commit = NULL; - obj = got_object_cache_get(objcache, &id); + obj = got_object_cache_get(objcache, id); if (obj) { obj->refcnt++; } else { - err = open_object(&obj, pack, packidx, iobj.idx, &id, + err = open_object(&obj, pack, packidx, obj_idx, id, objcache); if (err) return err; @@ -140,14 +133,36 @@ commit_request(struct imsg *imsg, struct imsgbuf *ibuf goto done; obj->size = len; - err = got_object_parse_commit(&commit, buf, len); + + err = got_object_parse_commit(commit, buf, len); +done: + got_object_close(obj); + free(buf); + return err; +} + +static const struct got_error * +commit_request(struct imsg *imsg, struct imsgbuf *ibuf, struct got_pack *pack, + struct got_packidx *packidx, struct got_object_cache *objcache) +{ + const struct got_error *err = NULL; + struct got_imsg_packed_object iobj; + struct got_commit_object *commit = NULL; + struct got_object_id id; + size_t datalen; + + datalen = imsg->hdr.len - IMSG_HEADER_SIZE; + if (datalen != sizeof(iobj)) + return got_error(GOT_ERR_PRIVSEP_LEN); + memcpy(&iobj, imsg->data, sizeof(iobj)); + memcpy(id.sha1, iobj.id, SHA1_DIGEST_LENGTH); + + err = open_commit(&commit, pack, packidx, iobj.idx, &id, objcache); if (err) goto done; err = got_privsep_send_commit(ibuf, commit); done: - free(buf); - got_object_close(obj); if (commit) got_object_commit_close(commit); if (err) { @@ -160,17 +175,53 @@ done: return err; } +const struct got_error * +open_tree(uint8_t **buf, struct got_pathlist_head *entries, int *nentries, + struct got_pack *pack, struct got_packidx *packidx, int obj_idx, + struct got_object_id *id, struct got_object_cache *objcache) +{ + const struct got_error *err = NULL; + struct got_object *obj = NULL; + size_t len; + + *buf = NULL; + *nentries = 0; + + obj = got_object_cache_get(objcache, id); + if (obj) { + obj->refcnt++; + } else { + err = open_object(&obj, pack, packidx, obj_idx, id, + objcache); + if (err) + return err; + } + + err = got_packfile_extract_object_to_mem(buf, &len, obj, pack); + if (err) + goto done; + + obj->size = len; + + err = got_object_parse_tree(entries, nentries, *buf, len); +done: + got_object_close(obj); + if (err) { + free(*buf); + *buf = NULL; + } + return err; +} + static const struct got_error * tree_request(struct imsg *imsg, struct imsgbuf *ibuf, struct got_pack *pack, struct got_packidx *packidx, struct got_object_cache *objcache) { const struct got_error *err = NULL; struct got_imsg_packed_object iobj; - struct got_object *obj = NULL; struct got_pathlist_head entries; int nentries = 0; uint8_t *buf = NULL; - size_t len; struct got_object_id id; size_t datalen; @@ -182,30 +233,14 @@ tree_request(struct imsg *imsg, struct imsgbuf *ibuf, memcpy(&iobj, imsg->data, sizeof(iobj)); memcpy(id.sha1, iobj.id, SHA1_DIGEST_LENGTH); - obj = got_object_cache_get(objcache, &id); - if (obj) { - obj->refcnt++; - } else { - err = open_object(&obj, pack, packidx, iobj.idx, &id, - objcache); - if (err) - return err; - } - - err = got_packfile_extract_object_to_mem(&buf, &len, obj, pack); + err = open_tree(&buf, &entries, &nentries, pack, packidx, iobj.idx, + &id, objcache); if (err) - goto done; + return err; - obj->size = len; - err = got_object_parse_tree(&entries, &nentries, buf, len); - if (err) - goto done; - err = got_privsep_send_tree(ibuf, &entries, nentries); -done: got_object_parsed_tree_entries_free(&entries); free(buf); - got_object_close(obj); if (err) { if (err->code == GOT_ERR_PRIVSEP_PIPE) err = NULL; @@ -368,6 +403,325 @@ done: got_object_close(obj); if (tag) got_object_tag_close(tag); + if (err) { + if (err->code == GOT_ERR_PRIVSEP_PIPE) + err = NULL; + else + got_privsep_send_error(ibuf, err); + } + + return err; +} + +static struct got_parsed_tree_entry * +find_entry_by_name(struct got_pathlist_head *entries, int nentries, + const char *name, size_t len) +{ + struct got_pathlist_entry *pe; + + /* Note that tree entries are sorted in strncmp() order. */ + TAILQ_FOREACH(pe, entries, entry) { + int cmp = strncmp(pe->path, name, len); + if (cmp < 0) + continue; + if (cmp > 0) + break; + if (pe->path[len] == '\0') + return (struct got_parsed_tree_entry *)pe->data; + } + return NULL; +} + +const struct got_error * +tree_path_changed(int *changed, uint8_t **buf1, uint8_t **buf2, + struct got_pathlist_head *entries1, int *nentries1, + struct got_pathlist_head *entries2, int *nentries2, + const char *path, struct got_pack *pack, struct got_packidx *packidx, + struct imsgbuf *ibuf, struct got_object_cache *objcache) +{ + const struct got_error *err = NULL; + struct got_parsed_tree_entry *pte1 = NULL, *pte2 = NULL; + const char *seg, *s; + size_t seglen; + + *changed = 0; + + /* We are expecting an absolute in-repository path. */ + if (path[0] != '/') + return got_error(GOT_ERR_NOT_ABSPATH); + + /* We not do support comparing the root path. */ + if (path[1] == '\0') + return got_error(GOT_ERR_BAD_PATH); + + s = path; + s++; /* skip leading '/' */ + seg = s; + seglen = 0; + while (*s) { + if (*s != '/') { + s++; + seglen++; + if (*s) + continue; + } + + pte1 = find_entry_by_name(entries1, *nentries1, seg, seglen); + if (pte1 == NULL) { + err = got_error(GOT_ERR_NO_OBJ); + break; + } + + pte2 = find_entry_by_name(entries2, *nentries2, seg, seglen); + if (pte2 == NULL) { + *changed = 1; + break; + } + + if (pte1->mode != pte2->mode) { + *changed = 1; + break; + } + + if (memcmp(pte1->id, pte2->id, SHA1_DIGEST_LENGTH) == 0) { + *changed = 0; + break; + } + + if (*s == '\0') { /* final path element */ + *changed = 1; + break; + } + + seg = s + 1; + s++; + seglen = 0; + if (*s) { + struct got_object_id id1, id2; + int idx; + + idx = got_packidx_get_object_idx_sha1(packidx, + pte1->id); + if (idx == -1) { + err = got_error(GOT_ERR_NO_OBJ); + break; + } + memcpy(id1.sha1, pte1->id, SHA1_DIGEST_LENGTH); + got_object_parsed_tree_entries_free(entries1); + *nentries1 = 0; + free(*buf1); + *buf1 = NULL; + err = open_tree(buf1, entries1, nentries1, pack, + packidx, idx, &id1, objcache); + pte1 = NULL; + if (err) + break; + + idx = got_packidx_get_object_idx_sha1(packidx, + pte2->id); + if (idx == -1) { + err = got_error(GOT_ERR_NO_OBJ); + break; + } + memcpy(id2.sha1, pte2->id, SHA1_DIGEST_LENGTH); + got_object_parsed_tree_entries_free(entries2); + *nentries2 = 0; + free(*buf2); + *buf2 = NULL; + err = open_tree(buf2, entries2, nentries2, pack, + packidx, idx, &id2, objcache); + pte2 = NULL; + if (err) + break; + } + } + + return err; +} + +static const struct got_error * +commit_traversal_request(struct imsg *imsg, struct imsgbuf *ibuf, + struct got_pack *pack, struct got_packidx *packidx, + struct got_object_cache *objcache) +{ + const struct got_error *err = NULL; + struct got_imsg_packed_object iobj; + struct got_object_qid *pid; + struct got_commit_object *commit = NULL, *pcommit = NULL; + struct got_pathlist_head entries, pentries; + int nentries = 0, pnentries = 0; + struct got_object_id id; + size_t datalen, path_len; + char *path = NULL; + const int min_alloc = 64; + int changed = 0, ncommits = 0, nallocated = 0; + struct got_object_id *commit_ids = NULL; + + TAILQ_INIT(&entries); + TAILQ_INIT(&pentries); + + datalen = imsg->hdr.len - IMSG_HEADER_SIZE; + if (datalen < sizeof(iobj)) + return got_error(GOT_ERR_PRIVSEP_LEN); + memcpy(&iobj, imsg->data, sizeof(iobj)); + memcpy(id.sha1, iobj.id, SHA1_DIGEST_LENGTH); + + path_len = datalen - sizeof(iobj) - 1; + if (path_len < 0) + return got_error(GOT_ERR_PRIVSEP_LEN); + if (path_len > 0) { + path = imsg->data + sizeof(iobj); + if (path[path_len] != '\0') + return got_error(GOT_ERR_PRIVSEP_LEN); + } + + nallocated = min_alloc; + commit_ids = reallocarray(NULL, nallocated, sizeof(*commit_ids)); + if (commit_ids == NULL) + return got_error_from_errno("reallocarray"); + + do { + const size_t max_datalen = MAX_IMSGSIZE - IMSG_HEADER_SIZE; + int idx; + + if (sigint_received) { + err = got_error(GOT_ERR_CANCELLED); + goto done; + } + + if (commit == NULL) { + idx = got_packidx_get_object_idx(packidx, &id); + if (idx == -1) + break; + err = open_commit(&commit, pack, packidx, + idx, &id, objcache); + if (err) { + if (err->code != GOT_ERR_NO_OBJ) + goto done; + err = NULL; + break; + } + } + + if (sizeof(struct got_imsg_traversed_commits) + + ncommits * SHA1_DIGEST_LENGTH >= max_datalen) { + err = got_privsep_send_traversed_commits(commit_ids, + ncommits, ibuf); + if (err) + goto done; + ncommits = 0; + } + ncommits++; + if (ncommits > nallocated) { + struct got_object_id *new; + nallocated += min_alloc; + new = reallocarray(commit_ids, nallocated, + sizeof(*commit_ids)); + if (new == NULL) { + err = got_error_from_errno("reallocarray"); + goto done; + } + commit_ids = new; + } + memcpy(commit_ids[ncommits - 1].sha1, id.sha1, + SHA1_DIGEST_LENGTH); + + pid = SIMPLEQ_FIRST(&commit->parent_ids); + if (pid == NULL) + break; + + idx = got_packidx_get_object_idx(packidx, pid->id); + if (idx == -1) + break; + + err = open_commit(&pcommit, pack, packidx, idx, pid->id, + objcache); + if (err) { + if (err->code != GOT_ERR_NO_OBJ) + goto done; + err = NULL; + break; + } + + if (path[0] == '/' && path[1] == '\0') { + if (got_object_id_cmp(pcommit->tree_id, + commit->tree_id) != 0) { + changed = 1; + break; + } + } else { + int pidx; + uint8_t *buf = NULL, *pbuf = NULL; + + idx = got_packidx_get_object_idx(packidx, + commit->tree_id); + if (idx == -1) + break; + pidx = got_packidx_get_object_idx(packidx, + pcommit->tree_id); + if (pidx == -1) + break; + + err = open_tree(&buf, &entries, &nentries, pack, + packidx, idx, commit->tree_id, objcache); + if (err) + goto done; + err = open_tree(&pbuf, &pentries, &pnentries, pack, + packidx, pidx, pcommit->tree_id, objcache); + if (err) { + free(buf); + goto done; + } + + err = tree_path_changed(&changed, &buf, &pbuf, + &entries, &nentries, &pentries, &pnentries, path, + pack, packidx, ibuf, objcache); + + got_object_parsed_tree_entries_free(&entries); + nentries = 0; + free(buf); + got_object_parsed_tree_entries_free(&pentries); + pnentries = 0; + free(pbuf); + if (err) { + if (err->code != GOT_ERR_NO_OBJ) + goto done; + err = NULL; + break; + } + } + + if (!changed) { + memcpy(id.sha1, pid->id->sha1, SHA1_DIGEST_LENGTH); + got_object_commit_close(commit); + commit = pcommit; + pcommit = NULL; + } + } while (!changed); + + if (ncommits > 0) { + err = got_privsep_send_traversed_commits(commit_ids, + ncommits, ibuf); + if (err) + goto done; + + if (changed) { + err = got_privsep_send_commit(ibuf, commit); + if (err) + goto done; + } + } + err = got_privsep_send_commit_traversal_done(ibuf); +done: + free(commit_ids); + if (commit) + got_object_commit_close(commit); + if (pcommit) + got_object_commit_close(pcommit); + if (nentries != 0) + got_object_parsed_tree_entries_free(&entries); + if (pnentries != 0) + got_object_parsed_tree_entries_free(&pentries); if (err) { if (err->code == GOT_ERR_PRIVSEP_PIPE) err = NULL; @@ -606,6 +960,10 @@ main(int argc, char *argv[]) err = tag_request(&imsg, &ibuf, pack, packidx, &objcache); break; + case GOT_IMSG_COMMIT_TRAVERSAL_REQUEST: + err = commit_traversal_request(&imsg, &ibuf, pack, + packidx, &objcache); + break; default: err = got_error(GOT_ERR_PRIVSEP_MSG); break;