Blob


1 /*
2 * Copyright (c) 2020 Ori Bernstein
3 * Copyright (c) 2021, 2022 Stefan Sperling <stsp@openbsd.org>
4 *
5 * Permission to use, copy, modify, and distribute this software for any
6 * purpose with or without fee is hereby granted, provided that the above
7 * copyright notice and this permission notice appear in all copies.
8 *
9 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
10 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
11 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
12 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
13 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
14 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
15 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
16 */
18 #include <sys/types.h>
19 #include <sys/queue.h>
20 #include <sys/tree.h>
21 #include <sys/uio.h>
23 #include <sha1.h>
24 #include <limits.h>
25 #include <stdio.h>
26 #include <stdint.h>
27 #include <stdlib.h>
28 #include <string.h>
29 #include <time.h>
30 #include <imsg.h>
31 #include <inttypes.h>
32 #include <unistd.h>
34 #include "got_error.h"
35 #include "got_cancel.h"
36 #include "got_object.h"
37 #include "got_reference.h"
38 #include "got_repository_admin.h"
39 #include "got_path.h"
41 #include "got_lib_delta.h"
42 #include "got_lib_object.h"
43 #include "got_lib_object_cache.h"
44 #include "got_lib_object_idset.h"
45 #include "got_lib_privsep.h"
46 #include "got_lib_ratelimit.h"
47 #include "got_lib_pack.h"
48 #include "got_lib_pack_create.h"
49 #include "got_lib_repository.h"
51 struct send_id_arg {
52 struct imsgbuf *ibuf;
53 struct got_object_id *ids[GOT_IMSG_OBJ_ID_LIST_MAX_NIDS];
54 size_t nids;
55 };
57 static const struct got_error *
58 send_id(struct got_object_id *id, void *data, void *arg)
59 {
60 const struct got_error *err = NULL;
61 struct send_id_arg *a = arg;
63 a->ids[a->nids++] = id;
65 if (a->nids >= GOT_IMSG_OBJ_ID_LIST_MAX_NIDS) {
66 err = got_privsep_send_object_idlist(a->ibuf, a->ids, a->nids);
67 if (err)
68 return err;
69 a->nids = 0;
70 }
72 return NULL;
73 }
75 static const struct got_error *
76 send_idset(struct imsgbuf *ibuf, struct got_object_idset *idset)
77 {
78 const struct got_error *err;
79 struct send_id_arg sia;
81 memset(&sia, 0, sizeof(sia));
82 sia.ibuf = ibuf;
83 err = got_object_idset_for_each(idset, send_id, &sia);
84 if (err)
85 return err;
87 if (sia.nids > 0) {
88 err = got_privsep_send_object_idlist(ibuf, sia.ids, sia.nids);
89 if (err)
90 return err;
91 }
93 return got_privsep_send_object_idlist_done(ibuf);
94 }
96 static const struct got_error *
97 recv_reused_delta(struct got_imsg_reused_delta *delta,
98 struct got_object_idset *idset, struct got_pack_metavec *v)
99 {
100 struct got_pack_meta *m, *base;
102 if (delta->delta_offset + delta->delta_size < delta->delta_offset ||
103 delta->delta_offset +
104 delta->delta_compressed_size < delta->delta_offset)
105 return got_error(GOT_ERR_BAD_PACKFILE);
107 m = got_object_idset_get(idset, &delta->id);
108 if (m == NULL)
109 return got_error(GOT_ERR_NO_OBJ);
111 base = got_object_idset_get(idset, &delta->base_id);
112 if (base == NULL)
113 return got_error(GOT_ERR_NO_OBJ);
115 m->delta_len = delta->delta_size;
116 m->delta_compressed_len = delta->delta_compressed_size;
117 m->delta_offset = 0;
118 m->prev = base;
119 m->size = delta->result_size;
120 m->reused_delta_offset = delta->delta_offset;
121 m->base_obj_id = got_object_id_dup(&delta->base_id);
122 if (m->base_obj_id == NULL)
123 return got_error_from_errno("got_object_id_dup");
125 return got_pack_add_meta(m, v);
128 const struct got_error *
129 got_pack_search_deltas(struct got_packidx **packidx, struct got_pack **pack,
130 struct got_pack_metavec *v, struct got_object_idset *idset,
131 int ncolored, int nfound, int ntrees, int ncommits,
132 struct got_repository *repo,
133 got_pack_progress_cb progress_cb, void *progress_arg,
134 struct got_ratelimit *rl, got_cancel_cb cancel_cb, void *cancel_arg)
136 const struct got_error *err = NULL;
137 struct got_imsg_reused_delta deltas[GOT_IMSG_REUSED_DELTAS_MAX_NDELTAS];
138 size_t ndeltas, i;
140 *packidx = NULL;
141 *pack = NULL;
143 err = got_pack_find_pack_for_reuse(packidx, repo);
144 if (err)
145 return err;
147 if (*packidx == NULL)
148 return NULL;
150 err = got_pack_cache_pack_for_packidx(pack, *packidx, repo);
151 if (err)
152 goto done;
154 if ((*pack)->privsep_child == NULL) {
155 err = got_pack_start_privsep_child(*pack, *packidx);
156 if (err)
157 goto done;
160 err = got_privsep_send_delta_reuse_req((*pack)->privsep_child->ibuf);
161 if (err)
162 goto done;
164 err = send_idset((*pack)->privsep_child->ibuf, idset);
165 if (err)
166 goto done;
168 for (;;) {
169 int done = 0;
171 if (cancel_cb) {
172 err = (*cancel_cb)(cancel_arg);
173 if (err)
174 break;
177 err = got_privsep_recv_reused_deltas(&done, deltas, &ndeltas,
178 (*pack)->privsep_child->ibuf);
179 if (err || done)
180 break;
182 for (i = 0; i < ndeltas; i++) {
183 struct got_imsg_reused_delta *delta = &deltas[i];
184 err = recv_reused_delta(delta, idset, v);
185 if (err)
186 goto done;
189 err = got_pack_report_progress(progress_cb, progress_arg, rl,
190 ncolored, nfound, ntrees, 0L, ncommits,
191 got_object_idset_num_elements(idset), v->nmeta, 0);
192 if (err)
193 break;
195 done:
196 return err;
199 struct recv_painted_commit_arg {
200 int *ncolored;
201 int *nqueued;
202 int *nskip;
203 struct got_object_id_queue *ids;
204 struct got_object_idset *keep;
205 struct got_object_idset *drop;
206 struct got_object_idset *skip;
207 got_pack_progress_cb progress_cb;
208 void *progress_arg;
209 struct got_ratelimit *rl;
210 got_cancel_cb cancel_cb;
211 void *cancel_arg;
212 };
214 static const struct got_error *
215 recv_painted_commit(void *arg, struct got_object_id *id, intptr_t color)
217 const struct got_error *err = NULL;
218 struct recv_painted_commit_arg *a = arg;
219 struct got_object_qid *qid, *tmp;
221 if (a->cancel_cb) {
222 err = a->cancel_cb(a->cancel_arg);
223 if (err)
224 return err;
227 switch (color) {
228 case COLOR_KEEP:
229 err = got_object_idset_add(a->keep, id, NULL);
230 if (err)
231 return err;
232 (*a->ncolored)++;
233 break;
234 case COLOR_DROP:
235 err = got_object_idset_add(a->drop, id, NULL);
236 if (err)
237 return err;
238 (*a->ncolored)++;
239 break;
240 case COLOR_SKIP:
241 err = got_object_idset_add(a->skip, id, NULL);
242 if (err)
243 return err;
244 break;
245 default:
246 /* should not happen */
247 return got_error_fmt(GOT_ERR_NOT_IMPL,
248 "%s invalid commit color %"PRIdPTR, __func__, color);
251 STAILQ_FOREACH_SAFE(qid, a->ids, entry, tmp) {
252 if (got_object_id_cmp(&qid->id, id) != 0)
253 continue;
254 STAILQ_REMOVE(a->ids, qid, got_object_qid, entry);
255 color = (intptr_t)qid->data;
256 got_object_qid_free(qid);
257 (*a->nqueued)--;
258 if (color == COLOR_SKIP)
259 (*a->nskip)--;
260 break;
263 return got_pack_report_progress(a->progress_cb, a->progress_arg, a->rl,
264 *a->ncolored, 0, 0, 0L, 0, 0, 0, 0);
267 static const struct got_error *
268 paint_packed_commits(struct got_pack *pack, struct got_object_id *id,
269 int idx, intptr_t color, int *ncolored, int *nqueued, int *nskip,
270 struct got_object_id_queue *ids,
271 struct got_object_idset *keep, struct got_object_idset *drop,
272 struct got_object_idset *skip, struct got_repository *repo,
273 got_pack_progress_cb progress_cb, void *progress_arg,
274 struct got_ratelimit *rl, got_cancel_cb cancel_cb, void *cancel_arg)
276 const struct got_error *err = NULL;
277 struct got_object_id_queue next_ids;
278 struct got_object_qid *qid, *tmp;
279 struct recv_painted_commit_arg arg;
281 STAILQ_INIT(&next_ids);
283 err = got_privsep_send_painting_request(pack->privsep_child->ibuf,
284 idx, id, color);
285 if (err)
286 return err;
288 arg.ncolored = ncolored;
289 arg.nqueued = nqueued;
290 arg.nskip = nskip;
291 arg.ids = ids;
292 arg.keep = keep;
293 arg.drop = drop;
294 arg.skip = skip;
295 arg.progress_cb = progress_cb;
296 arg.progress_arg = progress_arg;
297 arg.rl = rl;
298 arg.cancel_cb = cancel_cb;
299 arg.cancel_arg = cancel_arg;
300 err = got_privsep_recv_painted_commits(&next_ids,
301 recv_painted_commit, &arg, pack->privsep_child->ibuf);
302 if (err)
303 return err;
305 STAILQ_FOREACH_SAFE(qid, &next_ids, entry, tmp) {
306 struct got_object_qid *old_id;
307 intptr_t qcolor, ocolor;
308 STAILQ_FOREACH(old_id, ids, entry) {
309 if (got_object_id_cmp(&qid->id, &old_id->id))
310 continue;
311 qcolor = (intptr_t)qid->data;
312 ocolor = (intptr_t)old_id->data;
313 STAILQ_REMOVE(&next_ids, qid, got_object_qid, entry);
314 got_object_qid_free(qid);
315 qid = NULL;
316 if (qcolor != ocolor) {
317 got_pack_paint_commit(old_id, qcolor);
318 if (ocolor == COLOR_SKIP)
319 (*nskip)--;
320 else if (qcolor == COLOR_SKIP)
321 (*nskip)++;
323 break;
326 while (!STAILQ_EMPTY(&next_ids)) {
327 qid = STAILQ_FIRST(&next_ids);
328 STAILQ_REMOVE_HEAD(&next_ids, entry);
329 got_pack_paint_commit(qid, color);
330 STAILQ_INSERT_TAIL(ids, qid, entry);
331 (*nqueued)++;
332 if (color == COLOR_SKIP)
333 (*nskip)++;
336 return err;
339 const struct got_error *
340 got_pack_paint_commits(int *ncolored, struct got_object_id_queue *ids, int nids,
341 struct got_object_idset *keep, struct got_object_idset *drop,
342 struct got_object_idset *skip, struct got_repository *repo,
343 got_pack_progress_cb progress_cb, void *progress_arg,
344 struct got_ratelimit *rl, got_cancel_cb cancel_cb, void *cancel_arg)
346 const struct got_error *err = NULL;
347 struct got_commit_object *commit = NULL;
348 struct got_packidx *packidx = NULL;
349 struct got_pack *pack = NULL;
350 const struct got_object_id_queue *parents;
351 struct got_object_qid *qid = NULL;
352 int nqueued = nids, nskip = 0;
353 int idx;
355 while (!STAILQ_EMPTY(ids) && nskip != nqueued) {
356 intptr_t color;
358 if (cancel_cb) {
359 err = cancel_cb(cancel_arg);
360 if (err)
361 break;
364 qid = STAILQ_FIRST(ids);
365 STAILQ_REMOVE_HEAD(ids, entry);
366 nqueued--;
367 color = (intptr_t)qid->data;
368 if (color == COLOR_SKIP)
369 nskip--;
371 if (got_object_idset_contains(skip, &qid->id)) {
372 got_object_qid_free(qid);
373 qid = NULL;
374 continue;
376 if (color == COLOR_KEEP &&
377 got_object_idset_contains(keep, &qid->id)) {
378 got_object_qid_free(qid);
379 qid = NULL;
380 continue;
382 if (color == COLOR_DROP &&
383 got_object_idset_contains(drop, &qid->id)) {
384 got_object_qid_free(qid);
385 qid = NULL;
386 continue;
389 /* Pinned pack may have moved to different cache slot. */
390 pack = got_repo_get_pinned_pack(repo);
392 if (packidx && pack) {
393 idx = got_packidx_get_object_idx(packidx, &qid->id);
394 if (idx != -1) {
395 err = paint_packed_commits(pack, &qid->id,
396 idx, color, ncolored, &nqueued, &nskip,
397 ids, keep, drop, skip, repo,
398 progress_cb, progress_arg, rl,
399 cancel_cb, cancel_arg);
400 if (err)
401 break;
402 got_object_qid_free(qid);
403 qid = NULL;
404 continue;
408 switch (color) {
409 case COLOR_KEEP:
410 if (got_object_idset_contains(drop, &qid->id)) {
411 err = got_pack_paint_commit(qid, COLOR_SKIP);
412 if (err)
413 goto done;
414 } else
415 (*ncolored)++;
416 err = got_object_idset_add(keep, &qid->id, NULL);
417 if (err)
418 goto done;
419 break;
420 case COLOR_DROP:
421 if (got_object_idset_contains(keep, &qid->id)) {
422 err = got_pack_paint_commit(qid, COLOR_SKIP);
423 if (err)
424 goto done;
425 } else
426 (*ncolored)++;
427 err = got_object_idset_add(drop, &qid->id, NULL);
428 if (err)
429 goto done;
430 break;
431 case COLOR_SKIP:
432 if (!got_object_idset_contains(skip, &qid->id)) {
433 err = got_object_idset_add(skip, &qid->id,
434 NULL);
435 if (err)
436 goto done;
438 break;
439 default:
440 /* should not happen */
441 err = got_error_fmt(GOT_ERR_NOT_IMPL,
442 "%s invalid commit color %"PRIdPTR, __func__,
443 color);
444 goto done;
447 err = got_pack_report_progress(progress_cb, progress_arg, rl,
448 *ncolored, 0, 0, 0L, 0, 0, 0, 0);
449 if (err)
450 break;
452 err = got_object_open_as_commit(&commit, repo, &qid->id);
453 if (err)
454 break;
456 parents = got_object_commit_get_parent_ids(commit);
457 if (parents) {
458 struct got_object_qid *pid;
459 color = (intptr_t)qid->data;
460 STAILQ_FOREACH(pid, parents, entry) {
461 err = got_pack_queue_commit_id(ids, &pid->id,
462 color, repo);
463 if (err)
464 break;
465 nqueued++;
466 if (color == COLOR_SKIP)
467 nskip++;
471 if (pack == NULL && (commit->flags & GOT_COMMIT_FLAG_PACKED)) {
472 if (packidx == NULL) {
473 err = got_pack_find_pack_for_commit_painting(
474 &packidx, ids, nqueued, repo);
475 if (err)
476 goto done;
478 if (packidx != NULL) {
479 err = got_pack_cache_pack_for_packidx(&pack,
480 packidx, repo);
481 if (err)
482 goto done;
483 if (pack->privsep_child == NULL) {
484 err = got_pack_start_privsep_child(
485 pack, packidx);
486 if (err)
487 goto done;
489 err = got_privsep_init_commit_painting(
490 pack->privsep_child->ibuf);
491 if (err)
492 goto done;
493 err = send_idset(pack->privsep_child->ibuf,
494 keep);
495 if (err)
496 goto done;
497 err = send_idset(pack->privsep_child->ibuf, drop);
498 if (err)
499 goto done;
500 err = send_idset(pack->privsep_child->ibuf, skip);
501 if (err)
502 goto done;
503 err = got_repo_pin_pack(repo, packidx, pack);
504 if (err)
505 goto done;
509 got_object_commit_close(commit);
510 commit = NULL;
512 got_object_qid_free(qid);
513 qid = NULL;
515 done:
516 if (pack) {
517 const struct got_error *pack_err;
518 pack_err = got_privsep_send_painting_commits_done(
519 pack->privsep_child->ibuf);
520 if (err == NULL)
521 err = pack_err;
523 if (commit)
524 got_object_commit_close(commit);
525 got_object_qid_free(qid);
526 got_repo_unpin_pack(repo);
527 return err;
530 struct load_packed_obj_arg {
531 /* output parameters: */
532 struct got_object_id *id;
533 char *dpath;
534 time_t mtime;
536 /* input parameters: */
537 uint32_t seed;
538 int want_meta;
539 struct got_object_idset *idset;
540 struct got_object_idset *idset_exclude;
541 int loose_obj_only;
542 int *ncolored;
543 int *nfound;
544 int *ntrees;
545 got_pack_progress_cb progress_cb;
546 void *progress_arg;
547 struct got_ratelimit *rl;
548 got_cancel_cb cancel_cb;
549 void *cancel_arg;
550 };
552 static const struct got_error *
553 load_packed_commit_id(void *arg, time_t mtime, struct got_object_id *id,
554 struct got_repository *repo)
556 struct load_packed_obj_arg *a = arg;
558 if (got_object_idset_contains(a->idset, id) ||
559 got_object_idset_contains(a->idset_exclude, id))
560 return NULL;
562 return got_pack_add_object(a->want_meta,
563 a->want_meta ? a->idset : a->idset_exclude,
564 id, "", GOT_OBJ_TYPE_COMMIT, mtime, a->seed, a->loose_obj_only,
565 repo, a->ncolored, a->nfound, a->ntrees,
566 a->progress_cb, a->progress_arg, a->rl);
569 static const struct got_error *
570 load_packed_tree_ids(void *arg, struct got_tree_object *tree, time_t mtime,
571 struct got_object_id *id, const char *dpath, struct got_repository *repo)
573 const struct got_error *err;
574 struct load_packed_obj_arg *a = arg;
575 const char *relpath;
577 /*
578 * When we receive a tree's ID and path but not the tree itself,
579 * this tree object was not found in the pack file. This is the
580 * last time we are being called for this optimized traversal.
581 * Return from here and switch to loading objects the slow way.
582 */
583 if (tree == NULL) {
584 free(a->id);
585 a->id = got_object_id_dup(id);
586 if (a->id == NULL) {
587 err = got_error_from_errno("got_object_id_dup");
588 free(a->dpath);
589 a->dpath = NULL;
590 return err;
593 free(a->dpath);
594 a->dpath = strdup(dpath);
595 if (a->dpath == NULL) {
596 err = got_error_from_errno("strdup");
597 free(a->id);
598 a->id = NULL;
599 return err;
602 a->mtime = mtime;
603 return NULL;
606 if (got_object_idset_contains(a->idset, id) ||
607 got_object_idset_contains(a->idset_exclude, id))
608 return NULL;
610 relpath = dpath;
611 while (relpath[0] == '/')
612 relpath++;
614 err = got_pack_add_object(a->want_meta,
615 a->want_meta ? a->idset : a->idset_exclude,
616 id, relpath, GOT_OBJ_TYPE_TREE, mtime, a->seed,
617 a->loose_obj_only, repo, a->ncolored, a->nfound, a->ntrees,
618 a->progress_cb, a->progress_arg, a->rl);
619 if (err)
620 return err;
622 return got_pack_load_tree_entries(NULL, a->want_meta, a->idset,
623 a->idset_exclude, tree, dpath, mtime, a->seed, repo,
624 a->loose_obj_only, a->ncolored, a->nfound, a->ntrees,
625 a->progress_cb, a->progress_arg, a->rl,
626 a->cancel_cb, a->cancel_arg);
629 const struct got_error *
630 got_pack_load_packed_object_ids(int *found_all_objects,
631 struct got_object_id **ours, int nours,
632 struct got_object_id **theirs, int ntheirs,
633 int want_meta, uint32_t seed, struct got_object_idset *idset,
634 struct got_object_idset *idset_exclude, int loose_obj_only,
635 struct got_repository *repo, struct got_packidx *packidx,
636 int *ncolored, int *nfound, int *ntrees,
637 got_pack_progress_cb progress_cb, void *progress_arg,
638 struct got_ratelimit *rl, got_cancel_cb cancel_cb, void *cancel_arg)
640 const struct got_error *err = NULL;
641 struct load_packed_obj_arg lpa;
643 memset(&lpa, 0, sizeof(lpa));
644 lpa.seed = seed;
645 lpa.want_meta = want_meta;
646 lpa.idset = idset;
647 lpa.idset_exclude = idset_exclude;
648 lpa.loose_obj_only = loose_obj_only;
649 lpa.ncolored = ncolored;
650 lpa.nfound = nfound;
651 lpa.ntrees = ntrees;
652 lpa.progress_cb = progress_cb;
653 lpa.progress_arg = progress_arg;
654 lpa.rl = rl;
655 lpa.cancel_cb = cancel_cb;
656 lpa.cancel_arg = cancel_arg;
658 /* Attempt to load objects via got-read-pack, as far as possible. */
659 err = got_object_enumerate(found_all_objects, load_packed_commit_id,
660 load_packed_tree_ids, &lpa, ours, nours, theirs, ntheirs,
661 packidx, repo);
662 if (err)
663 return err;
665 if (lpa.id == NULL)
666 return NULL;
668 /*
669 * An incomplete tree hierarchy was present in the pack file
670 * and caused loading to be aborted.
671 * Continue loading trees the slow way.
672 */
673 err = got_pack_load_tree(want_meta, idset, idset_exclude,
674 lpa.id, lpa.dpath, lpa.mtime, seed, repo, loose_obj_only,
675 ncolored, nfound, ntrees, progress_cb, progress_arg, rl,
676 cancel_cb, cancel_arg);
677 free(lpa.id);
678 free(lpa.dpath);
679 return err;