?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
avoid a needless check for set membership in got_pack_repaint_parent_commits()
[got-portable.git] / lib / pack_create.c
blob9344a08b911bee2ed4f078b667d76dcfedc24c16
1 /*
2 * Copyright (c) 2020 Ori Bernstein
3 * Copyright (c) 2021 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 */
17
18 #include "got_compat.h"
19
20 #include <sys/types.h>
21 #include <sys/queue.h>
22 #include <sys/uio.h>
23 #include <sys/stat.h>
24 #include <sys/time.h>
25 #include <sys/mman.h>
26
27 #include <errno.h>
28 #include <stdint.h>
29 #include <inttypes.h>
30 #include <poll.h>
31 #include <stdio.h>
32 #include <stdlib.h>
33 #include <string.h>
34 #include <time.h>
35 #include <unistd.h>
36 #include <limits.h>
37 #include <zlib.h>
38
39 #include "got_error.h"
40 #include "got_cancel.h"
41 #include "got_object.h"
42 #include "got_path.h"
43 #include "got_reference.h"
44 #include "got_repository.h"
45 #include "got_repository_admin.h"
46
47 #include "got_lib_deltify.h"
48 #include "got_lib_delta.h"
49 #include "got_lib_hash.h"
50 #include "got_lib_object.h"
51 #include "got_lib_object_idset.h"
52 #include "got_lib_object_cache.h"
53 #include "got_lib_deflate.h"
54 #include "got_lib_ratelimit.h"
55 #include "got_lib_pack.h"
56 #include "got_lib_pack_create.h"
57 #include "got_lib_repository.h"
58 #include "got_lib_inflate.h"
59 #include "got_lib_poll.h"
60
61 #include "murmurhash2.h"
62
63 #ifndef MIN
64 #define MIN(_a,_b) ((_a) < (_b) ? (_a) : (_b))
65 #endif
66
67 #ifndef MAX
68 #define MAX(_a,_b) ((_a) > (_b) ? (_a) : (_b))
69 #endif
70
71 #ifndef nitems
72 #define nitems(_a) (sizeof((_a)) / sizeof((_a)[0]))
73 #endif
74
75 static const struct got_error *
76 alloc_meta(struct got_pack_meta **new, struct got_object_id *id,
77 const char *path, int obj_type, time_t mtime, uint32_t seed)
78 {
79 struct got_pack_meta *m;
80
81 *new = NULL;
82
83 m = calloc(1, sizeof(*m));
84 if (m == NULL)
85 return got_error_from_errno("calloc");
86
87 memcpy(&m->id, id, sizeof(m->id));
88
89 m->path_hash = murmurhash2(path, strlen(path), seed);
90 m->obj_type = obj_type;
91 m->mtime = mtime;
92 *new = m;
93 return NULL;
94 }
95
96 static void
97 clear_meta(struct got_pack_meta *meta)
98 {
99 if (meta == NULL)
100 return;
101 meta->path_hash = 0;
102 free(meta->delta_buf);
103 meta->delta_buf = NULL;
104 free(meta->base_obj_id);
105 meta->base_obj_id = NULL;
106 meta->reused_delta_offset = 0;
107 got_deltify_free(meta->dtab);
108 meta->dtab = NULL;
109 }
110
111 static void
112 free_nmeta(struct got_pack_meta **meta, int nmeta)
113 {
114 int i;
115
116 for (i = 0; i < nmeta; i++)
117 clear_meta(meta[i]);
118
119 free(meta);
120 }
121
122 static int
123 delta_order_cmp(const void *pa, const void *pb)
124 {
125 struct got_pack_meta *a, *b;
126
127 a = *(struct got_pack_meta **)pa;
128 b = *(struct got_pack_meta **)pb;
129
130 if (a->obj_type != b->obj_type)
131 return a->obj_type - b->obj_type;
132 if (a->path_hash < b->path_hash)
133 return -1;
134 if (a->path_hash > b->path_hash)
135 return 1;
136 if (a->mtime < b->mtime)
137 return -1;
138 if (a->mtime > b->mtime)
139 return 1;
140 return got_object_id_cmp(&a->id, &b->id);
141 }
142
143 static off_t
144 delta_size(struct got_delta_instruction *deltas, int ndeltas)
145 {
146 int i;
147 off_t size = 32;
148 for (i = 0; i < ndeltas; i++) {
149 if (deltas[i].copy)
150 size += GOT_DELTA_SIZE_SHIFT;
151 else
152 size += deltas[i].len + 1;
153 }
154 return size;
155 }
156
157 static const struct got_error *
158 append(unsigned char **p, size_t *len, off_t *sz, void *seg, int nseg)
159 {
160 char *n;
161
162 if (*len + nseg >= *sz) {
163 while (*len + nseg >= *sz)
164 *sz += *sz / 2;
165 n = realloc(*p, *sz);
166 if (n == NULL)
167 return got_error_from_errno("realloc");
168 *p = n;
169 }
170 memcpy(*p + *len, seg, nseg);
171 *len += nseg;
172 return NULL;
173 }
174
175 static const struct got_error *
176 encode_delta_in_mem(struct got_pack_meta *m, struct got_raw_object *o,
177 struct got_delta_instruction *deltas, int ndeltas,
178 off_t delta_size, off_t base_size)
179 {
180 const struct got_error *err;
181 unsigned char buf[16], *bp;
182 int i, j;
183 size_t len = 0, compressed_len;
184 off_t bufsize = delta_size;
185 off_t n;
186 struct got_delta_instruction *d;
187 uint8_t *delta_buf;
188
189 delta_buf = malloc(bufsize);
190 if (delta_buf == NULL)
191 return got_error_from_errno("malloc");
192
193 /* base object size */
194 buf[0] = base_size & GOT_DELTA_SIZE_VAL_MASK;
195 n = base_size >> GOT_DELTA_SIZE_SHIFT;
196 for (i = 1; n > 0; i++) {
197 buf[i - 1] |= GOT_DELTA_SIZE_MORE;
198 buf[i] = n & GOT_DELTA_SIZE_VAL_MASK;
199 n >>= GOT_DELTA_SIZE_SHIFT;
200 }
201 err = append(&delta_buf, &len, &bufsize, buf, i);
202 if (err)
203 goto done;
204
205 /* target object size */
206 buf[0] = o->size & GOT_DELTA_SIZE_VAL_MASK;
207 n = o->size >> GOT_DELTA_SIZE_SHIFT;
208 for (i = 1; n > 0; i++) {
209 buf[i - 1] |= GOT_DELTA_SIZE_MORE;
210 buf[i] = n & GOT_DELTA_SIZE_VAL_MASK;
211 n >>= GOT_DELTA_SIZE_SHIFT;
212 }
213 err = append(&delta_buf, &len, &bufsize, buf, i);
214 if (err)
215 goto done;
216
217 for (j = 0; j < ndeltas; j++) {
218 d = &deltas[j];
219 if (d->copy) {
220 n = d->offset;
221 bp = &buf[1];
222 buf[0] = GOT_DELTA_BASE_COPY;
223 for (i = 0; i < 4; i++) {
224 /* DELTA_COPY_OFF1 ... DELTA_COPY_OFF4 */
225 buf[0] |= 1 << i;
226 *bp++ = n & 0xff;
227 n >>= 8;
228 if (n == 0)
229 break;
230 }
231
232 n = d->len;
233 if (n != GOT_DELTA_COPY_DEFAULT_LEN) {
234 /* DELTA_COPY_LEN1 ... DELTA_COPY_LEN3 */
235 for (i = 0; i < 3 && n > 0; i++) {
236 buf[0] |= 1 << (i + 4);
237 *bp++ = n & 0xff;
238 n >>= 8;
239 }
240 }
241 err = append(&delta_buf, &len, &bufsize,
242 buf, bp - buf);
243 if (err)
244 goto done;
245 } else if (o->f == NULL) {
246 n = 0;
247 while (n != d->len) {
248 buf[0] = (d->len - n < 127) ? d->len - n : 127;
249 err = append(&delta_buf, &len, &bufsize,
250 buf, 1);
251 if (err)
252 goto done;
253 err = append(&delta_buf, &len, &bufsize,
254 o->data + o->hdrlen + d->offset + n,
255 buf[0]);
256 if (err)
257 goto done;
258 n += buf[0];
259 }
260 } else {
261 char content[128];
262 size_t r;
263 if (fseeko(o->f, o->hdrlen + d->offset, SEEK_SET) == -1) {
264 err = got_error_from_errno("fseeko");
265 goto done;
266 }
267 n = 0;
268 while (n != d->len) {
269 buf[0] = (d->len - n < 127) ? d->len - n : 127;
270 err = append(&delta_buf, &len, &bufsize,
271 buf, 1);
272 if (err)
273 goto done;
274 r = fread(content, 1, buf[0], o->f);
275 if (r != buf[0]) {
276 err = got_ferror(o->f, GOT_ERR_IO);
277 goto done;
278 }
279 err = append(&delta_buf, &len, &bufsize,
280 content, buf[0]);
281 if (err)
282 goto done;
283 n += buf[0];
284 }
285 }
286 }
287
288 err = got_deflate_to_mem_mmap(&m->delta_buf, &compressed_len,
289 NULL, NULL, delta_buf, 0, len);
290 if (err)
291 goto done;
292
293 m->delta_len = len;
294 m->delta_compressed_len = compressed_len;
295 done:
296 free(delta_buf);
297 return err;
298 }
299
300 static const struct got_error *
301 encode_delta(struct got_pack_meta *m, struct got_raw_object *o,
302 struct got_delta_instruction *deltas, int ndeltas,
303 off_t base_size, FILE *f)
304 {
305 const struct got_error *err;
306 unsigned char buf[16], *bp;
307 int i, j;
308 off_t n;
309 struct got_deflate_buf zb;
310 struct got_delta_instruction *d;
311 off_t delta_len = 0, compressed_len = 0;
312
313 err = got_deflate_init(&zb, NULL, GOT_DEFLATE_BUFSIZE);
314 if (err)
315 return err;
316
317 /* base object size */
318 buf[0] = base_size & GOT_DELTA_SIZE_VAL_MASK;
319 n = base_size >> GOT_DELTA_SIZE_SHIFT;
320 for (i = 1; n > 0; i++) {
321 buf[i - 1] |= GOT_DELTA_SIZE_MORE;
322 buf[i] = n & GOT_DELTA_SIZE_VAL_MASK;
323 n >>= GOT_DELTA_SIZE_SHIFT;
324 }
325
326 err = got_deflate_append_to_file_mmap(&zb, &compressed_len,
327 buf, 0, i, f, NULL);
328 if (err)
329 goto done;
330 delta_len += i;
331
332 /* target object size */
333 buf[0] = o->size & GOT_DELTA_SIZE_VAL_MASK;
334 n = o->size >> GOT_DELTA_SIZE_SHIFT;
335 for (i = 1; n > 0; i++) {
336 buf[i - 1] |= GOT_DELTA_SIZE_MORE;
337 buf[i] = n & GOT_DELTA_SIZE_VAL_MASK;
338 n >>= GOT_DELTA_SIZE_SHIFT;
339 }
340
341 err = got_deflate_append_to_file_mmap(&zb, &compressed_len,
342 buf, 0, i, f, NULL);
343 if (err)
344 goto done;
345 delta_len += i;
346
347 for (j = 0; j < ndeltas; j++) {
348 d = &deltas[j];
349 if (d->copy) {
350 n = d->offset;
351 bp = &buf[1];
352 buf[0] = GOT_DELTA_BASE_COPY;
353 for (i = 0; i < 4; i++) {
354 /* DELTA_COPY_OFF1 ... DELTA_COPY_OFF4 */
355 buf[0] |= 1 << i;
356 *bp++ = n & 0xff;
357 n >>= 8;
358 if (n == 0)
359 break;
360 }
361 n = d->len;
362 if (n != GOT_DELTA_COPY_DEFAULT_LEN) {
363 /* DELTA_COPY_LEN1 ... DELTA_COPY_LEN3 */
364 for (i = 0; i < 3 && n > 0; i++) {
365 buf[0] |= 1 << (i + 4);
366 *bp++ = n & 0xff;
367 n >>= 8;
368 }
369 }
370 err = got_deflate_append_to_file_mmap(&zb,
371 &compressed_len, buf, 0, bp - buf, f, NULL);
372 if (err)
373 goto done;
374 delta_len += (bp - buf);
375 } else if (o->f == NULL) {
376 n = 0;
377 while (n != d->len) {
378 buf[0] = (d->len - n < 127) ? d->len - n : 127;
379 err = got_deflate_append_to_file_mmap(&zb,
380 &compressed_len, buf, 0, 1, f, NULL);
381 if (err)
382 goto done;
383 delta_len++;
384 err = got_deflate_append_to_file_mmap(&zb,
385 &compressed_len,
386 o->data + o->hdrlen + d->offset + n, 0,
387 buf[0], f, NULL);
388 if (err)
389 goto done;
390 delta_len += buf[0];
391 n += buf[0];
392 }
393 } else {
394 char content[128];
395 size_t r;
396 if (fseeko(o->f, o->hdrlen + d->offset, SEEK_SET) == -1) {
397 err = got_error_from_errno("fseeko");
398 goto done;
399 }
400 n = 0;
401 while (n != d->len) {
402 buf[0] = (d->len - n < 127) ? d->len - n : 127;
403 err = got_deflate_append_to_file_mmap(&zb,
404 &compressed_len, buf, 0, 1, f, NULL);
405 if (err)
406 goto done;
407 delta_len++;
408 r = fread(content, 1, buf[0], o->f);
409 if (r != buf[0]) {
410 err = got_ferror(o->f, GOT_ERR_IO);
411 goto done;
412 }
413 err = got_deflate_append_to_file_mmap(&zb,
414 &compressed_len, content, 0, buf[0], f,
415 NULL);
416 if (err)
417 goto done;
418 delta_len += buf[0];
419 n += buf[0];
420 }
421 }
422 }
423
424 err = got_deflate_flush(&zb, f, NULL, &compressed_len);
425 if (err)
426 goto done;
427
428 /* sanity check */
429 if (compressed_len != ftello(f) - m->delta_offset) {
430 err = got_error(GOT_ERR_COMPRESSION);
431 goto done;
432 }
433
434 m->delta_len = delta_len;
435 m->delta_compressed_len = compressed_len;
436 done:
437 got_deflate_end(&zb);
438 return err;
439 }
440
441 const struct got_error *
442 got_pack_report_progress(got_pack_progress_cb progress_cb, void *progress_arg,
443 struct got_ratelimit *rl, int ncolored, int nfound, int ntrees,
444 off_t packfile_size, int ncommits, int nobj_total, int obj_deltify,
445 int nobj_written, int pack_done)
446 {
447 const struct got_error *err;
448 int elapsed;
449
450 if (progress_cb == NULL)
451 return NULL;
452
453 err = got_ratelimit_check(&elapsed, rl);
454 if (err || !elapsed)
455 return err;
456
457 return progress_cb(progress_arg, ncolored, nfound, ntrees,
458 packfile_size, ncommits, nobj_total, obj_deltify, nobj_written,
459 pack_done);
460 }
461
462 const struct got_error *
463 got_pack_add_meta(struct got_pack_meta *m, struct got_pack_metavec *v)
464 {
465 if (v->nmeta == v->metasz){
466 size_t newsize = 2 * v->metasz;
467 struct got_pack_meta **new;
468 new = reallocarray(v->meta, newsize, sizeof(*new));
469 if (new == NULL)
470 return got_error_from_errno("reallocarray");
471 v->meta = new;
472 v->metasz = newsize;
473 }
474
475 v->meta[v->nmeta++] = m;
476 return NULL;
477 }
478
479 const struct got_error *
480 got_pack_find_pack_for_reuse(struct got_packidx **best_packidx,
481 struct got_repository *repo)
482 {
483 const struct got_error *err = NULL;
484 struct got_pathlist_entry *pe;
485 const char *best_packidx_path = NULL;
486 int nobj_max = 0;
487
488 *best_packidx = NULL;
489
490 RB_FOREACH(pe, got_pathlist_head, &repo->packidx_paths) {
491 const char *path_packidx = pe->path;
492 struct got_packidx *packidx;
493 int nobj;
494
495 err = got_repo_get_packidx(&packidx, path_packidx, repo);
496 if (err)
497 break;
498
499 nobj = be32toh(packidx->hdr.fanout_table[0xff]);
500 if (nobj > nobj_max) {
501 best_packidx_path = path_packidx;
502 nobj_max = nobj;
503 }
504 }
505
506 if (best_packidx_path) {
507 err = got_repo_get_packidx(best_packidx, best_packidx_path,
508 repo);
509 }
510
511 return err;
512 }
513
514 const struct got_error *
515 got_pack_cache_pack_for_packidx(struct got_pack **pack,
516 struct got_packidx *packidx, struct got_repository *repo)
517 {
518 const struct got_error *err;
519 char *path_packfile = NULL;
520
521 err = got_packidx_get_packfile_path(&path_packfile,
522 packidx->path_packidx);
523 if (err)
524 return err;
525
526 *pack = got_repo_get_cached_pack(repo, path_packfile);
527 if (*pack == NULL) {
528 err = got_repo_cache_pack(pack, repo, path_packfile, packidx);
529 if (err)
530 goto done;
531 }
532 done:
533 free(path_packfile);
534 return err;
535 }
536
537 static const struct got_error *
538 pick_deltas(struct got_pack_meta **meta, int nmeta, int ncolored,
539 int nfound, int ntrees, int ncommits, int nreused, FILE *delta_cache,
540 struct got_repository *repo,
541 got_pack_progress_cb progress_cb, void *progress_arg,
542 struct got_ratelimit *rl, got_cancel_cb cancel_cb, void *cancel_arg)
543 {
544 const struct got_error *err = NULL;
545 struct got_pack_meta *m = NULL, *base = NULL;
546 struct got_raw_object *raw = NULL, *base_raw = NULL;
547 struct got_delta_instruction *deltas = NULL, *best_deltas = NULL;
548 int i, j, ndeltas, best_ndeltas;
549 off_t size, best_size;
550 const int max_base_candidates = 3;
551 size_t delta_memsize = 0;
552 const size_t max_delta_memsize = 4 * GOT_DELTA_RESULT_SIZE_CACHED_MAX;
553 int outfd = -1;
554 uint32_t delta_seed;
555
556 delta_seed = arc4random();
557
558 qsort(meta, nmeta, sizeof(struct got_pack_meta *), delta_order_cmp);
559 for (i = 0; i < nmeta; i++) {
560 if (cancel_cb) {
561 err = (*cancel_cb)(cancel_arg);
562 if (err)
563 break;
564 }
565 err = got_pack_report_progress(progress_cb, progress_arg, rl,
566 ncolored, nfound, ntrees, 0L, ncommits, nreused + nmeta,
567 nreused + i, 0, 0);
568 if (err)
569 goto done;
570 m = meta[i];
571
572 if (m->obj_type == GOT_OBJ_TYPE_COMMIT ||
573 m->obj_type == GOT_OBJ_TYPE_TAG)
574 continue;
575
576 err = got_object_raw_open(&raw, &outfd, repo, &m->id);
577 if (err)
578 goto done;
579 m->size = raw->size;
580
581 if (raw->f == NULL) {
582 err = got_deltify_init_mem(&m->dtab, raw->data,
583 raw->hdrlen, raw->size + raw->hdrlen, delta_seed);
584 } else {
585 err = got_deltify_init(&m->dtab, raw->f, raw->hdrlen,
586 raw->size + raw->hdrlen, delta_seed);
587 }
588 if (err)
589 goto done;
590
591 if (i > max_base_candidates) {
592 struct got_pack_meta *n = NULL;
593 n = meta[i - (max_base_candidates + 1)];
594 got_deltify_free(n->dtab);
595 n->dtab = NULL;
596 }
597
598 best_size = raw->size;
599 best_ndeltas = 0;
600 for (j = MAX(0, i - max_base_candidates); j < i; j++) {
601 if (cancel_cb) {
602 err = (*cancel_cb)(cancel_arg);
603 if (err)
604 goto done;
605 }
606 base = meta[j];
607 /* long chains make unpacking slow, avoid such bases */
608 if (base->nchain >= 128 ||
609 base->obj_type != m->obj_type)
610 continue;
611
612 err = got_object_raw_open(&base_raw, &outfd, repo,
613 &base->id);
614 if (err)
615 goto done;
616
617 if (raw->f == NULL && base_raw->f == NULL) {
618 err = got_deltify_mem_mem(&deltas, &ndeltas,
619 raw->data, raw->hdrlen,
620 raw->size + raw->hdrlen, delta_seed,
621 base->dtab, base_raw->data,
622 base_raw->hdrlen,
623 base_raw->size + base_raw->hdrlen);
624 } else if (raw->f == NULL) {
625 err = got_deltify_mem_file(&deltas, &ndeltas,
626 raw->data, raw->hdrlen,
627 raw->size + raw->hdrlen, delta_seed,
628 base->dtab, base_raw->f,
629 base_raw->hdrlen,
630 base_raw->size + base_raw->hdrlen);
631 } else if (base_raw->f == NULL) {
632 err = got_deltify_file_mem(&deltas, &ndeltas,
633 raw->f, raw->hdrlen,
634 raw->size + raw->hdrlen, delta_seed,
635 base->dtab, base_raw->data,
636 base_raw->hdrlen,
637 base_raw->size + base_raw->hdrlen);
638 } else {
639 err = got_deltify(&deltas, &ndeltas,
640 raw->f, raw->hdrlen,
641 raw->size + raw->hdrlen, delta_seed,
642 base->dtab, base_raw->f, base_raw->hdrlen,
643 base_raw->size + base_raw->hdrlen);
644 }
645 got_object_raw_close(base_raw);
646 base_raw = NULL;
647 if (err)
648 goto done;
649
650 size = delta_size(deltas, ndeltas);
651 if (size + 32 < best_size){
652 /*
653 * if we already picked a best delta,
654 * replace it.
655 */
656 best_size = size;
657 free(best_deltas);
658 best_deltas = deltas;
659 best_ndeltas = ndeltas;
660 deltas = NULL;
661 m->nchain = base->nchain + 1;
662 m->prev = base;
663 m->head = base->head;
664 if (m->head == NULL)
665 m->head = base;
666 } else {
667 free(deltas);
668 deltas = NULL;
669 ndeltas = 0;
670 }
671 }
672
673 if (best_ndeltas > 0) {
674 if (best_size <= GOT_DELTA_RESULT_SIZE_CACHED_MAX &&
675 delta_memsize + best_size <= max_delta_memsize) {
676 delta_memsize += best_size;
677 err = encode_delta_in_mem(m, raw, best_deltas,
678 best_ndeltas, best_size, m->prev->size);
679 } else {
680 m->delta_offset = ftello(delta_cache);
681 err = encode_delta(m, raw, best_deltas,
682 best_ndeltas, m->prev->size, delta_cache);
683 }
684 free(best_deltas);
685 best_deltas = NULL;
686 best_ndeltas = 0;
687 if (err)
688 goto done;
689 }
690
691 got_object_raw_close(raw);
692 raw = NULL;
693 }
694 done:
695 if (raw)
696 got_object_raw_close(raw);
697 if (base_raw)
698 got_object_raw_close(base_raw);
699 if (outfd != -1 && close(outfd) == -1 && err == NULL)
700 err = got_error_from_errno("close");
701 free(deltas);
702 free(best_deltas);
703 return err;
704 }
705
706 static const struct got_error *
707 search_packidx(int *found, struct got_object_id *id,
708 struct got_repository *repo)
709 {
710 const struct got_error *err = NULL;
711 struct got_packidx *packidx = NULL;
712 int idx;
713
714 *found = 0;
715
716 err = got_repo_search_packidx(&packidx, &idx, repo, id);
717 if (err == NULL)
718 *found = 1; /* object is already packed */
719 else if (err->code == GOT_ERR_NO_OBJ)
720 err = NULL;
721 return err;
722 }
723
724 const struct got_error *
725 got_pack_add_object(int want_meta, struct got_object_idset *idset,
726 struct got_object_id *id, const char *path, int obj_type,
727 time_t mtime, uint32_t seed, int loose_obj_only,
728 struct got_repository *repo, int *ncolored, int *nfound, int *ntrees,
729 got_pack_progress_cb progress_cb, void *progress_arg,
730 struct got_ratelimit *rl)
731 {
732 const struct got_error *err;
733 struct got_pack_meta *m = NULL;
734
735 if (loose_obj_only) {
736 int is_packed;
737 err = search_packidx(&is_packed, id, repo);
738 if (err)
739 return err;
740 if (is_packed && want_meta)
741 return NULL;
742 }
743
744 if (want_meta) {
745 err = alloc_meta(&m, id, path, obj_type, mtime, seed);
746 if (err)
747 return err;
748
749 (*nfound)++;
750 err = got_pack_report_progress(progress_cb, progress_arg, rl,
751 *ncolored, *nfound, *ntrees, 0L, 0, 0, 0, 0, 0);
752 if (err) {
753 clear_meta(m);
754 free(m);
755 return err;
756 }
757 }
758
759 err = got_object_idset_add(idset, id, m);
760 if (err) {
761 clear_meta(m);
762 free(m);
763 }
764 return err;
765 }
766
767 const struct got_error *
768 got_pack_load_tree_entries(struct got_object_id_queue *ids, int want_meta,
769 struct got_object_idset *idset, struct got_object_idset *idset_exclude,
770 struct got_tree_object *tree,
771 const char *dpath, time_t mtime, uint32_t seed, struct got_repository *repo,
772 int loose_obj_only, int *ncolored, int *nfound, int *ntrees,
773 got_pack_progress_cb progress_cb, void *progress_arg,
774 struct got_ratelimit *rl, got_cancel_cb cancel_cb, void *cancel_arg)
775 {
776 const struct got_error *err;
777 char *p = NULL;
778 int i;
779
780 (*ntrees)++;
781 err = got_pack_report_progress(progress_cb, progress_arg, rl,
782 *ncolored, *nfound, *ntrees, 0L, 0, 0, 0, 0, 0);
783 if (err)
784 return err;
785
786 for (i = 0; i < got_object_tree_get_nentries(tree); i++) {
787 struct got_tree_entry *e = got_object_tree_get_entry(tree, i);
788 struct got_object_id *id = got_tree_entry_get_id(e);
789 mode_t mode = got_tree_entry_get_mode(e);
790
791 if (cancel_cb) {
792 err = (*cancel_cb)(cancel_arg);
793 if (err)
794 break;
795 }
796
797 if (got_object_tree_entry_is_submodule(e) ||
798 got_object_idset_contains(idset, id) ||
799 got_object_idset_contains(idset_exclude, id))
800 continue;
801
802 /*
803 * If got-read-pack is crawling trees for us then
804 * we are only here to collect blob IDs.
805 */
806 if (ids == NULL && S_ISDIR(mode))
807 continue;
808
809 if (asprintf(&p, "%s%s%s", dpath,
810 got_path_is_root_dir(dpath) ? "" : "/",
811 got_tree_entry_get_name(e)) == -1) {
812 err = got_error_from_errno("asprintf");
813 break;
814 }
815
816 if (S_ISDIR(mode)) {
817 struct got_object_qid *qid;
818 err = got_object_qid_alloc(&qid, id);
819 if (err)
820 break;
821 qid->data = p;
822 p = NULL;
823 STAILQ_INSERT_TAIL(ids, qid, entry);
824 } else if (S_ISREG(mode) || S_ISLNK(mode)) {
825 err = got_pack_add_object(want_meta,
826 want_meta ? idset : idset_exclude, id, p,
827 GOT_OBJ_TYPE_BLOB, mtime, seed, loose_obj_only,
828 repo, ncolored, nfound, ntrees,
829 progress_cb, progress_arg, rl);
830 if (err)
831 break;
832 free(p);
833 p = NULL;
834 } else {
835 free(p);
836 p = NULL;
837 }
838 }
839
840 free(p);
841 return err;
842 }
843
844 const struct got_error *
845 got_pack_load_tree(int want_meta, struct got_object_idset *idset,
846 struct got_object_idset *idset_exclude,
847 struct got_object_id *tree_id, const char *dpath, time_t mtime,
848 uint32_t seed, struct got_repository *repo, int loose_obj_only,
849 int *ncolored, int *nfound, int *ntrees,
850 got_pack_progress_cb progress_cb, void *progress_arg,
851 struct got_ratelimit *rl, got_cancel_cb cancel_cb, void *cancel_arg)
852 {
853 const struct got_error *err = NULL;
854 struct got_object_id_queue tree_ids;
855 struct got_object_qid *qid;
856 struct got_tree_object *tree = NULL;
857
858 if (got_object_idset_contains(idset, tree_id) ||
859 got_object_idset_contains(idset_exclude, tree_id))
860 return NULL;
861
862 err = got_object_qid_alloc(&qid, tree_id);
863 if (err)
864 return err;
865 qid->data = strdup(dpath);
866 if (qid->data == NULL) {
867 err = got_error_from_errno("strdup");
868 got_object_qid_free(qid);
869 return err;
870 }
871
872 STAILQ_INIT(&tree_ids);
873 STAILQ_INSERT_TAIL(&tree_ids, qid, entry);
874
875 while (!STAILQ_EMPTY(&tree_ids)) {
876 const char *path;
877 if (cancel_cb) {
878 err = (*cancel_cb)(cancel_arg);
879 if (err)
880 break;
881 }
882
883 qid = STAILQ_FIRST(&tree_ids);
884 STAILQ_REMOVE_HEAD(&tree_ids, entry);
885 path = qid->data;
886
887 if (got_object_idset_contains(idset, &qid->id) ||
888 got_object_idset_contains(idset_exclude, &qid->id)) {
889 free(qid->data);
890 got_object_qid_free(qid);
891 continue;
892 }
893
894 err = got_pack_add_object(want_meta,
895 want_meta ? idset : idset_exclude,
896 &qid->id, path, GOT_OBJ_TYPE_TREE,
897 mtime, seed, loose_obj_only, repo,
898 ncolored, nfound, ntrees, progress_cb, progress_arg, rl);
899 if (err) {
900 free(qid->data);
901 got_object_qid_free(qid);
902 break;
903 }
904
905 err = got_object_open_as_tree(&tree, repo, &qid->id);
906 if (err) {
907 free(qid->data);
908 got_object_qid_free(qid);
909 break;
910 }
911
912 err = got_pack_load_tree_entries(&tree_ids, want_meta, idset,
913 idset_exclude, tree, path, mtime, seed, repo,
914 loose_obj_only, ncolored, nfound, ntrees,
915 progress_cb, progress_arg, rl,
916 cancel_cb, cancel_arg);
917 free(qid->data);
918 got_object_qid_free(qid);
919 if (err)
920 break;
921
922 got_object_tree_close(tree);
923 tree = NULL;
924 }
925
926 STAILQ_FOREACH(qid, &tree_ids, entry)
927 free(qid->data);
928 got_object_id_queue_free(&tree_ids);
929 if (tree)
930 got_object_tree_close(tree);
931 return err;
932 }
933
934 static const struct got_error *
935 load_commit(int want_meta, struct got_object_idset *idset,
936 struct got_object_idset *idset_exclude,
937 struct got_object_id *id, struct got_repository *repo, uint32_t seed,
938 int loose_obj_only, int *ncolored, int *nfound, int *ntrees,
939 got_pack_progress_cb progress_cb, void *progress_arg,
940 struct got_ratelimit *rl, got_cancel_cb cancel_cb, void *cancel_arg)
941 {
942 const struct got_error *err;
943 struct got_commit_object *commit;
944
945 if (got_object_idset_contains(idset, id) ||
946 got_object_idset_contains(idset_exclude, id))
947 return NULL;
948
949 if (loose_obj_only) {
950 int is_packed;
951 err = search_packidx(&is_packed, id, repo);
952 if (err)
953 return err;
954 if (is_packed && want_meta)
955 return NULL;
956 }
957
958 err = got_object_open_as_commit(&commit, repo, id);
959 if (err)
960 return err;
961
962 err = got_pack_add_object(want_meta,
963 want_meta ? idset : idset_exclude, id, "", GOT_OBJ_TYPE_COMMIT,
964 got_object_commit_get_committer_time(commit), seed,
965 loose_obj_only, repo,
966 ncolored, nfound, ntrees, progress_cb, progress_arg, rl);
967 if (err)
968 goto done;
969
970 err = got_pack_load_tree(want_meta, idset, idset_exclude,
971 got_object_commit_get_tree_id(commit),
972 "", got_object_commit_get_committer_time(commit), seed,
973 repo, loose_obj_only, ncolored, nfound, ntrees,
974 progress_cb, progress_arg, rl, cancel_cb, cancel_arg);
975 done:
976 got_object_commit_close(commit);
977 return err;
978 }
979
980 static const struct got_error *
981 load_tag(int want_meta, struct got_object_idset *idset,
982 struct got_object_idset *idset_exclude,
983 struct got_object_id *id, struct got_repository *repo, uint32_t seed,
984 int loose_obj_only, int *ncolored, int *nfound, int *ntrees,
985 got_pack_progress_cb progress_cb, void *progress_arg,
986 struct got_ratelimit *rl, got_cancel_cb cancel_cb, void *cancel_arg)
987 {
988 const struct got_error *err;
989 struct got_tag_object *tag = NULL;
990
991 if (got_object_idset_contains(idset, id) ||
992 got_object_idset_contains(idset_exclude, id))
993 return NULL;
994
995 if (loose_obj_only) {
996 int is_packed;
997 err = search_packidx(&is_packed, id, repo);
998 if (err)
999 return err;
1000 if (is_packed && want_meta)
1001 return NULL;
1002 }
1003
1004 err = got_object_open_as_tag(&tag, repo, id);
1005 if (err)
1006 return err;
1007
1008 err = got_pack_add_object(want_meta,
1009 want_meta ? idset : idset_exclude, id, "", GOT_OBJ_TYPE_TAG,
1010 got_object_tag_get_tagger_time(tag), seed, loose_obj_only, repo,
1011 ncolored, nfound, ntrees, progress_cb, progress_arg, rl);
1012 if (err)
1013 goto done;
1014
1015 switch (got_object_tag_get_object_type(tag)) {
1016 case GOT_OBJ_TYPE_COMMIT:
1017 err = load_commit(want_meta, idset, idset_exclude,
1018 got_object_tag_get_object_id(tag), repo, seed,
1019 loose_obj_only, ncolored, nfound, ntrees,
1020 progress_cb, progress_arg, rl, cancel_cb, cancel_arg);
1021 break;
1022 case GOT_OBJ_TYPE_TREE:
1023 err = got_pack_load_tree(want_meta, idset, idset_exclude,
1024 got_object_tag_get_object_id(tag), "",
1025 got_object_tag_get_tagger_time(tag), seed, repo,
1026 loose_obj_only, ncolored, nfound, ntrees,
1027 progress_cb, progress_arg, rl, cancel_cb, cancel_arg);
1028 break;
1029 default:
1030 break;
1031 }
1032
1033 done:
1034 got_object_tag_close(tag);
1035 return err;
1036 }
1037
1038 const struct got_error *
1039 got_pack_paint_commit(struct got_object_qid *qid, intptr_t color)
1040 {
1041 if (color < 0 || color >= COLOR_MAX)
1042 return got_error(GOT_ERR_RANGE);
1043
1044 qid->data = (void *)color;
1045 return NULL;
1046 }
1047
1048 const struct got_error *
1049 got_pack_repaint_parent_commits(struct got_object_id *commit_id, int color,
1050 struct got_object_idset *set, struct got_object_idset *skip,
1051 struct got_repository *repo)
1052 {
1053 const struct got_error *err;
1054 struct got_object_id_queue ids;
1055 struct got_object_qid *qid;
1056 struct got_commit_object *commit;
1057 const struct got_object_id_queue *parents;
1058
1059 STAILQ_INIT(&ids);
1060
1061 err = got_object_open_as_commit(&commit, repo, commit_id);
1062 if (err)
1063 return err;
1064
1065 while (commit) {
1066 parents = got_object_commit_get_parent_ids(commit);
1067 if (parents) {
1068 struct got_object_qid *pid;
1069 STAILQ_FOREACH(pid, parents, entry) {
1070 /*
1071 * No need to traverse parents which are
1072 * already in the desired set or are
1073 * marked for skipping already.
1074 */
1075 if (got_object_idset_contains(set, &pid->id))
1076 continue;
1077 if (skip != set &&
1078 got_object_idset_contains(skip, &pid->id))
1079 continue;
1080
1081 err = got_pack_queue_commit_id(&ids, &pid->id,
1082 color, repo);
1083 if (err)
1084 break;
1085 }
1086 }
1087 got_object_commit_close(commit);
1088 commit = NULL;
1089
1090 qid = STAILQ_FIRST(&ids);
1091 if (qid == NULL)
1092 break;
1093
1094 STAILQ_REMOVE_HEAD(&ids, entry);
1095 err = got_object_idset_add(set, &qid->id, NULL);
1096 if (err)
1097 break;
1098
1099 err = got_object_open_as_commit(&commit, repo, &qid->id);
1100 if (err)
1101 break;
1102
1103 got_object_qid_free(qid);
1104 qid = NULL;
1105 }
1106
1107 if (commit)
1108 got_object_commit_close(commit);
1109 if (qid)
1110 got_object_qid_free(qid);
1111 got_object_id_queue_free(&ids);
1112
1113 return err;
1114 }
1115
1116 const struct got_error *
1117 got_pack_queue_commit_id(struct got_object_id_queue *ids,
1118 struct got_object_id *id, intptr_t color, struct got_repository *repo)
1119 {
1120 const struct got_error *err;
1121 struct got_object_qid *qid;
1122
1123 err = got_object_qid_alloc(&qid, id);
1124 if (err)
1125 return err;
1126
1127 STAILQ_INSERT_TAIL(ids, qid, entry);
1128 return got_pack_paint_commit(qid, color);
1129 }
1130
1131 struct append_id_arg {
1132 struct got_object_id **array;
1133 int idx;
1134 struct got_object_idset *drop;
1135 struct got_object_idset *skip;
1136 };
1137
1138 static const struct got_error *
1139 append_id(struct got_object_id *id, void *data, void *arg)
1140 {
1141 struct append_id_arg *a = arg;
1142
1143 if (got_object_idset_contains(a->skip, id) ||
1144 got_object_idset_contains(a->drop, id))
1145 return NULL;
1146
1147 a->array[++a->idx] = got_object_id_dup(id);
1148 if (a->array[a->idx] == NULL)
1149 return got_error_from_errno("got_object_id_dup");
1150
1151 return NULL;
1152 }
1153
1154 static const struct got_error *
1155 free_meta(struct got_object_id *id, void *data, void *arg)
1156 {
1157 struct got_pack_meta *meta = data;
1158
1159 clear_meta(meta);
1160 free(meta);
1161 return NULL;
1162 }
1163
1164 static const struct got_error *
1165 queue_commit_or_tag_id(struct got_object_id *id, intptr_t color,
1166 struct got_object_id_queue *ids, struct got_repository *repo)
1167 {
1168 const struct got_error *err;
1169 struct got_tag_object *tag = NULL;
1170 int obj_type;
1171
1172 err = got_object_get_type(&obj_type, repo, id);
1173 if (err)
1174 return err;
1175
1176 if (obj_type == GOT_OBJ_TYPE_TAG) {
1177 err = got_object_open_as_tag(&tag, repo, id);
1178 if (err)
1179 return err;
1180 obj_type = got_object_tag_get_object_type(tag);
1181 id = got_object_tag_get_object_id(tag);
1182 }
1183
1184 if (obj_type == GOT_OBJ_TYPE_COMMIT) {
1185 err = got_pack_queue_commit_id(ids, id, color, repo);
1186 if (err)
1187 goto done;
1188 }
1189 done:
1190 if (tag)
1191 got_object_tag_close(tag);
1192 return err;
1193 }
1194
1195 const struct got_error *
1196 got_pack_find_pack_for_commit_painting(struct got_packidx **best_packidx,
1197 struct got_object_id_queue *ids, struct got_repository *repo)
1198 {
1199 const struct got_error *err = NULL;
1200 struct got_pathlist_entry *pe;
1201 const char *best_packidx_path = NULL;
1202 int nobj_max = 0;
1203 int ncommits_max = 0;
1204
1205 *best_packidx = NULL;
1206
1207 /*
1208 * Find the largest pack which contains at least some of the
1209 * commits we are interested in.
1210 */
1211 RB_FOREACH(pe, got_pathlist_head, &repo->packidx_paths) {
1212 const char *path_packidx = pe->path;
1213 struct got_packidx *packidx;
1214 int nobj, idx, ncommits = 0;
1215 struct got_object_qid *qid;
1216
1217 err = got_repo_get_packidx(&packidx, path_packidx, repo);
1218 if (err)
1219 break;
1220
1221 nobj = be32toh(packidx->hdr.fanout_table[0xff]);
1222 if (nobj <= nobj_max)
1223 continue;
1224
1225 STAILQ_FOREACH(qid, ids, entry) {
1226 idx = got_packidx_get_object_idx(packidx, &qid->id);
1227 if (idx != -1)
1228 ncommits++;
1229 }
1230 if (ncommits > ncommits_max) {
1231 best_packidx_path = path_packidx;
1232 nobj_max = nobj;
1233 ncommits_max = ncommits;
1234 }
1235 }
1236
1237 if (best_packidx_path && err == NULL) {
1238 err = got_repo_get_packidx(best_packidx, best_packidx_path,
1239 repo);
1240 }
1241
1242 return err;
1243 }
1244
1245 static const struct got_error *
1246 findtwixt(struct got_object_id ***res, int *nres, int *ncolored,
1247 struct got_object_id **head, int nhead,
1248 struct got_object_id **tail, int ntail,
1249 struct got_repository *repo,
1250 got_pack_progress_cb progress_cb, void *progress_arg,
1251 struct got_ratelimit *rl, got_cancel_cb cancel_cb, void *cancel_arg)
1252 {
1253 const struct got_error *err = NULL;
1254 struct got_object_id_queue ids;
1255 struct got_object_idset *keep, *drop, *skip = NULL;
1256 int i, nkeep, nqueued = 0;
1257
1258 STAILQ_INIT(&ids);
1259 *res = NULL;
1260 *nres = 0;
1261 *ncolored = 0;
1262
1263 keep = got_object_idset_alloc();
1264 if (keep == NULL)
1265 return got_error_from_errno("got_object_idset_alloc");
1266
1267 drop = got_object_idset_alloc();
1268 if (drop == NULL) {
1269 err = got_error_from_errno("got_object_idset_alloc");
1270 goto done;
1271 }
1272
1273 skip = got_object_idset_alloc();
1274 if (skip == NULL) {
1275 err = got_error_from_errno("got_object_idset_alloc");
1276 goto done;
1277 }
1278
1279 for (i = 0; i < nhead; i++) {
1280 struct got_object_id *id = head[i];
1281 if (id == NULL)
1282 continue;
1283 err = queue_commit_or_tag_id(id, COLOR_KEEP, &ids, repo);
1284 if (err)
1285 goto done;
1286 nqueued++;
1287 }
1288
1289 for (i = 0; i < ntail; i++) {
1290 struct got_object_id *id = tail[i];
1291 if (id == NULL)
1292 continue;
1293 err = queue_commit_or_tag_id(id, COLOR_DROP, &ids, repo);
1294 if (err)
1295 goto done;
1296 nqueued++;
1297 }
1298
1299 err = got_pack_paint_commits(ncolored, &ids, nqueued,
1300 keep, drop, skip, repo, progress_cb, progress_arg, rl,
1301 cancel_cb, cancel_arg);
1302 if (err)
1303 goto done;
1304
1305 nkeep = got_object_idset_num_elements(keep);
1306 if (nkeep > 0) {
1307 struct append_id_arg arg;
1308 arg.array = calloc(nkeep, sizeof(struct got_object_id *));
1309 if (arg.array == NULL) {
1310 err = got_error_from_errno("calloc");
1311 goto done;
1312 }
1313 arg.idx = -1;
1314 arg.skip = skip;
1315 arg.drop = drop;
1316 err = got_object_idset_for_each(keep, append_id, &arg);
1317 if (err) {
1318 free(arg.array);
1319 goto done;
1320 }
1321 *res = arg.array;
1322 *nres = arg.idx + 1;
1323 }
1324 done:
1325 got_object_idset_free(keep);
1326 got_object_idset_free(drop);
1327 if (skip)
1328 got_object_idset_free(skip);
1329 got_object_id_queue_free(&ids);
1330 return err;
1331 }
1332
1333 static const struct got_error *
1334 find_pack_for_enumeration(struct got_packidx **best_packidx,
1335 struct got_object_id **ids, int nids, struct got_repository *repo)
1336 {
1337 const struct got_error *err = NULL;
1338 struct got_pathlist_entry *pe;
1339 const char *best_packidx_path = NULL;
1340 int nobj_max = 0;
1341 int ncommits_max = 0;
1342
1343 *best_packidx = NULL;
1344
1345 /*
1346 * Find the largest pack which contains at least some of the
1347 * commits and tags we are interested in.
1348 */
1349 RB_FOREACH(pe, got_pathlist_head, &repo->packidx_paths) {
1350 const char *path_packidx = pe->path;
1351 struct got_packidx *packidx;
1352 int nobj, i, idx, ncommits = 0;
1353
1354 err = got_repo_get_packidx(&packidx, path_packidx, repo);
1355 if (err)
1356 break;
1357
1358 nobj = be32toh(packidx->hdr.fanout_table[0xff]);
1359 if (nobj <= nobj_max)
1360 continue;
1361
1362 for (i = 0; i < nids; i++) {
1363 idx = got_packidx_get_object_idx(packidx, ids[i]);
1364 if (idx != -1)
1365 ncommits++;
1366 }
1367 if (ncommits > ncommits_max) {
1368 best_packidx_path = path_packidx;
1369 nobj_max = nobj;
1370 ncommits_max = ncommits;
1371 }
1372 }
1373
1374 if (best_packidx_path && err == NULL) {
1375 err = got_repo_get_packidx(best_packidx, best_packidx_path,
1376 repo);
1377 }
1378
1379 return err;
1380 }
1381
1382 static const struct got_error *
1383 load_object_ids(int *ncolored, int *nfound, int *ntrees,
1384 struct got_object_idset *idset, struct got_object_id **theirs, int ntheirs,
1385 struct got_object_id **ours, int nours, struct got_repository *repo,
1386 uint32_t seed, int loose_obj_only, got_pack_progress_cb progress_cb,
1387 void *progress_arg, struct got_ratelimit *rl, got_cancel_cb cancel_cb,
1388 void *cancel_arg)
1389 {
1390 const struct got_error *err = NULL;
1391 struct got_object_id **ids = NULL;
1392 struct got_packidx *packidx = NULL;
1393 int i, nobj = 0, obj_type, found_all_objects = 0;
1394 struct got_object_idset *idset_exclude;
1395
1396 idset_exclude = got_object_idset_alloc();
1397 if (idset_exclude == NULL)
1398 return got_error_from_errno("got_object_idset_alloc");
1399
1400 *ncolored = 0;
1401 *nfound = 0;
1402 *ntrees = 0;
1403
1404 err = findtwixt(&ids, &nobj, ncolored, ours, nours, theirs, ntheirs,
1405 repo, progress_cb, progress_arg, rl, cancel_cb, cancel_arg);
1406 if (err)
1407 goto done;
1408
1409 err = find_pack_for_enumeration(&packidx, theirs, ntheirs, repo);
1410 if (err)
1411 goto done;
1412 if (packidx) {
1413 err = got_pack_load_packed_object_ids(&found_all_objects,
1414 theirs, ntheirs, NULL, 0, 0, seed, idset, idset_exclude,
1415 loose_obj_only, repo, packidx, ncolored, nfound, ntrees,
1416 progress_cb, progress_arg, rl, cancel_cb, cancel_arg);
1417 if (err)
1418 goto done;
1419 }
1420
1421 for (i = 0; i < ntheirs; i++) {
1422 struct got_object_id *id = theirs[i];
1423 if (id == NULL)
1424 continue;
1425 err = got_object_get_type(&obj_type, repo, id);
1426 if (err)
1427 return err;
1428 if (obj_type == GOT_OBJ_TYPE_COMMIT) {
1429 if (!found_all_objects) {
1430 err = load_commit(0, idset, idset_exclude,
1431 id, repo, seed, loose_obj_only,
1432 ncolored, nfound, ntrees,
1433 progress_cb, progress_arg, rl,
1434 cancel_cb, cancel_arg);
1435 if (err)
1436 goto done;
1437 }
1438 } else if (obj_type == GOT_OBJ_TYPE_TAG) {
1439 err = load_tag(0, idset, idset_exclude, id, repo,
1440 seed, loose_obj_only, ncolored, nfound, ntrees,
1441 progress_cb, progress_arg, rl,
1442 cancel_cb, cancel_arg);
1443 if (err)
1444 goto done;
1445 }
1446 }
1447
1448 found_all_objects = 0;
1449 err = find_pack_for_enumeration(&packidx, ids, nobj, repo);
1450 if (err)
1451 goto done;
1452 if (packidx) {
1453 err = got_pack_load_packed_object_ids(&found_all_objects, ids,
1454 nobj, theirs, ntheirs, 1, seed, idset, idset_exclude,
1455 loose_obj_only, repo, packidx, ncolored, nfound, ntrees,
1456 progress_cb, progress_arg, rl, cancel_cb, cancel_arg);
1457 if (err)
1458 goto done;
1459 }
1460
1461 if (!found_all_objects) {
1462 for (i = 0; i < nobj; i++) {
1463 err = load_commit(1, idset, idset_exclude, ids[i],
1464 repo, seed, loose_obj_only, ncolored, nfound,
1465 ntrees, progress_cb, progress_arg, rl,
1466 cancel_cb, cancel_arg);
1467 if (err)
1468 goto done;
1469 }
1470 }
1471
1472 for (i = 0; i < nours; i++) {
1473 struct got_object_id *id = ours[i];
1474 struct got_pack_meta *m;
1475 if (id == NULL)
1476 continue;
1477 m = got_object_idset_get(idset, id);
1478 if (m == NULL) {
1479 err = got_object_get_type(&obj_type, repo, id);
1480 if (err)
1481 goto done;
1482 } else
1483 obj_type = m->obj_type;
1484 if (obj_type != GOT_OBJ_TYPE_TAG)
1485 continue;
1486 err = load_tag(1, idset, idset_exclude, id, repo,
1487 seed, loose_obj_only, ncolored, nfound, ntrees,
1488 progress_cb, progress_arg, rl, cancel_cb, cancel_arg);
1489 if (err)
1490 goto done;
1491 }
1492 done:
1493 for (i = 0; i < nobj; i++) {
1494 free(ids[i]);
1495 }
1496 free(ids);
1497 got_object_idset_free(idset_exclude);
1498 return err;
1499 }
1500
1501 static const struct got_error *
1502 hwrite(int fd, const void *buf, off_t len, struct got_hash *ctx)
1503 {
1504 got_hash_update(ctx, buf, len);
1505 return got_poll_write_full(fd, buf, len);
1506 }
1507
1508 static const struct got_error *
1509 hcopy(FILE *fsrc, int fd_dst, off_t len, struct got_hash *ctx)
1510 {
1511 const struct got_error *err;
1512 unsigned char buf[65536];
1513 off_t remain = len;
1514 size_t n;
1515
1516 while (remain > 0) {
1517 size_t copylen = MIN(sizeof(buf), remain);
1518 n = fread(buf, 1, copylen, fsrc);
1519 if (n != copylen)
1520 return got_ferror(fsrc, GOT_ERR_IO);
1521 got_hash_update(ctx, buf, copylen);
1522 err = got_poll_write_full(fd_dst, buf, copylen);
1523 if (err)
1524 return err;
1525 remain -= copylen;
1526 }
1527
1528 return NULL;
1529 }
1530
1531 static const struct got_error *
1532 hcopy_mmap(uint8_t *src, off_t src_offset, size_t src_size,
1533 int fd, off_t len, struct got_hash *ctx)
1534 {
1535 if (src_offset + len > src_size)
1536 return got_error(GOT_ERR_RANGE);
1537
1538 got_hash_update(ctx, src + src_offset, len);
1539 return got_poll_write_full(fd, src + src_offset, len);
1540 }
1541
1542 static void
1543 putbe32(char *b, uint32_t n)
1544 {
1545 b[0] = n >> 24;
1546 b[1] = n >> 16;
1547 b[2] = n >> 8;
1548 b[3] = n >> 0;
1549 }
1550
1551 static int
1552 write_order_cmp(const void *pa, const void *pb)
1553 {
1554 struct got_pack_meta *a, *b, *ahd, *bhd;
1555
1556 a = *(struct got_pack_meta **)pa;
1557 b = *(struct got_pack_meta **)pb;
1558 ahd = (a->head == NULL) ? a : a->head;
1559 bhd = (b->head == NULL) ? b : b->head;
1560 if (bhd->mtime < ahd->mtime)
1561 return -1;
1562 if (bhd->mtime > ahd->mtime)
1563 return 1;
1564 if (bhd < ahd)
1565 return -1;
1566 if (bhd > ahd)
1567 return 1;
1568 if (a->nchain != b->nchain)
1569 return a->nchain - b->nchain;
1570 if (a->mtime < b->mtime)
1571 return -1;
1572 if (a->mtime > b->mtime)
1573 return 1;
1574 return got_object_id_cmp(&a->id, &b->id);
1575 }
1576
1577 static int
1578 reuse_write_order_cmp(const void *pa, const void *pb)
1579 {
1580 struct got_pack_meta *a, *b;
1581
1582 a = *(struct got_pack_meta **)pa;
1583 b = *(struct got_pack_meta **)pb;
1584
1585 if (a->reused_delta_offset < b->reused_delta_offset)
1586 return -1;
1587 if (a->reused_delta_offset > b->reused_delta_offset)
1588 return 1;
1589 return 0;
1590 }
1591
1592 static const struct got_error *
1593 packhdr(int *hdrlen, char *hdr, size_t bufsize, int obj_type, size_t len)
1594 {
1595 size_t i;
1596
1597 *hdrlen = 0;
1598
1599 hdr[0] = obj_type << 4;
1600 hdr[0] |= len & 0xf;
1601 len >>= 4;
1602 for (i = 1; len != 0; i++){
1603 if (i >= bufsize)
1604 return got_error(GOT_ERR_NO_SPACE);
1605 hdr[i - 1] |= GOT_DELTA_SIZE_MORE;
1606 hdr[i] = len & GOT_DELTA_SIZE_VAL_MASK;
1607 len >>= GOT_DELTA_SIZE_SHIFT;
1608 }
1609
1610 *hdrlen = i;
1611 return NULL;
1612 }
1613
1614 static int
1615 packoff(char *hdr, off_t off)
1616 {
1617 int i, j;
1618 char rbuf[8];
1619
1620 rbuf[0] = off & GOT_DELTA_SIZE_VAL_MASK;
1621 for (i = 1; (off >>= GOT_DELTA_SIZE_SHIFT) != 0; i++) {
1622 rbuf[i] = (--off & GOT_DELTA_SIZE_VAL_MASK) |
1623 GOT_DELTA_SIZE_MORE;
1624 }
1625
1626 j = 0;
1627 while (i > 0)
1628 hdr[j++] = rbuf[--i];
1629 return j;
1630 }
1631
1632 static const struct got_error *
1633 deltahdr(off_t *packfile_size, struct got_hash *ctx, int packfd,
1634 int force_refdelta, struct got_pack_meta *m)
1635 {
1636 const struct got_error *err;
1637 char buf[32];
1638 int nh;
1639 size_t digest_len = got_hash_digest_length(m->prev->id.algo);
1640
1641 if (m->prev->off != 0 && !force_refdelta) {
1642 err = packhdr(&nh, buf, sizeof(buf),
1643 GOT_OBJ_TYPE_OFFSET_DELTA, m->delta_len);
1644 if (err)
1645 return err;
1646 nh += packoff(buf + nh, m->off - m->prev->off);
1647 err = hwrite(packfd, buf, nh, ctx);
1648 if (err)
1649 return err;
1650 *packfile_size += nh;
1651 } else {
1652 err = packhdr(&nh, buf, sizeof(buf),
1653 GOT_OBJ_TYPE_REF_DELTA, m->delta_len);
1654 if (err)
1655 return err;
1656 err = hwrite(packfd, buf, nh, ctx);
1657 if (err)
1658 return err;
1659 *packfile_size += nh;
1660 err = hwrite(packfd, m->prev->id.hash, digest_len, ctx);
1661 if (err)
1662 return err;
1663 *packfile_size += digest_len;
1664 }
1665
1666 return NULL;
1667 }
1668
1669 static const struct got_error *
1670 write_packed_object(off_t *packfile_size, int packfd,
1671 FILE *delta_cache, uint8_t *delta_cache_map, size_t delta_cache_size,
1672 struct got_pack_meta *m, int *outfd, struct got_hash *ctx,
1673 struct got_repository *repo, int force_refdelta)
1674 {
1675 const struct got_error *err = NULL;
1676 struct got_deflate_checksum csum;
1677 char buf[32];
1678 int nh;
1679 struct got_raw_object *raw = NULL;
1680 off_t outlen, delta_offset;
1681
1682 memset(&csum, 0, sizeof(csum));
1683 csum.output_ctx = ctx;
1684
1685 if (m->reused_delta_offset)
1686 delta_offset = m->reused_delta_offset;
1687 else
1688 delta_offset = m->delta_offset;
1689
1690 m->off = *packfile_size;
1691 if (m->delta_len == 0) {
1692 err = got_object_raw_open(&raw, outfd, repo, &m->id);
1693 if (err)
1694 goto done;
1695 err = packhdr(&nh, buf, sizeof(buf),
1696 m->obj_type, raw->size);
1697 if (err)
1698 goto done;
1699 err = hwrite(packfd, buf, nh, ctx);
1700 if (err)
1701 goto done;
1702 *packfile_size += nh;
1703 if (raw->f == NULL) {
1704 err = got_deflate_to_fd_mmap(&outlen,
1705 raw->data + raw->hdrlen, 0, raw->size,
1706 packfd, &csum);
1707 if (err)
1708 goto done;
1709 } else {
1710 if (fseeko(raw->f, raw->hdrlen, SEEK_SET)
1711 == -1) {
1712 err = got_error_from_errno("fseeko");
1713 goto done;
1714 }
1715 err = got_deflate_to_fd(&outlen, raw->f,
1716 raw->size, packfd, &csum);
1717 if (err)
1718 goto done;
1719 }
1720 *packfile_size += outlen;
1721 got_object_raw_close(raw);
1722 raw = NULL;
1723 } else if (m->delta_buf) {
1724 err = deltahdr(packfile_size, ctx, packfd, force_refdelta, m);
1725 if (err)
1726 goto done;
1727 err = hwrite(packfd, m->delta_buf,
1728 m->delta_compressed_len, ctx);
1729 if (err)
1730 goto done;
1731 *packfile_size += m->delta_compressed_len;
1732 free(m->delta_buf);
1733 m->delta_buf = NULL;
1734 } else if (delta_cache_map) {
1735 err = deltahdr(packfile_size, ctx, packfd, force_refdelta, m);
1736 if (err)
1737 goto done;
1738 err = hcopy_mmap(delta_cache_map, delta_offset,
1739 delta_cache_size, packfd, m->delta_compressed_len,
1740 ctx);
1741 if (err)
1742 goto done;
1743 *packfile_size += m->delta_compressed_len;
1744 } else {
1745 if (fseeko(delta_cache, delta_offset, SEEK_SET) == -1) {
1746 err = got_error_from_errno("fseeko");
1747 goto done;
1748 }
1749 err = deltahdr(packfile_size, ctx, packfd, force_refdelta, m);
1750 if (err)
1751 goto done;
1752 err = hcopy(delta_cache, packfd,
1753 m->delta_compressed_len, ctx);
1754 if (err)
1755 goto done;
1756 *packfile_size += m->delta_compressed_len;
1757 }
1758 done:
1759 if (raw)
1760 got_object_raw_close(raw);
1761 return err;
1762 }
1763
1764 static const struct got_error *
1765 genpack(struct got_object_id *pack_hash, int packfd,
1766 struct got_pack *reuse_pack, FILE *delta_cache,
1767 struct got_pack_meta **deltify, int ndeltify,
1768 struct got_pack_meta **reuse, int nreuse,
1769 int ncolored, int nfound, int ntrees, int nours,
1770 struct got_repository *repo, int force_refdelta,
1771 got_pack_progress_cb progress_cb, void *progress_arg,
1772 struct got_ratelimit *rl,
1773 got_cancel_cb cancel_cb, void *cancel_arg)
1774 {
1775 const struct got_error *err = NULL;
1776 int i;
1777 struct got_hash ctx;
1778 struct got_pack_meta *m;
1779 char buf[32];
1780 off_t packfile_size = 0;
1781 int outfd = -1;
1782 int delta_cache_fd = -1;
1783 uint8_t *delta_cache_map = NULL;
1784 size_t delta_cache_size = 0;
1785 FILE *packfile = NULL;
1786 enum got_hash_algorithm algo;
1787 size_t digest_len;
1788
1789 algo = got_repo_get_object_format(repo);
1790 digest_len = got_hash_digest_length(algo);
1791 got_hash_init(&ctx, algo);
1792
1793 memset(pack_hash, 0, sizeof(*pack_hash));
1794 pack_hash->algo = algo;
1795
1796 #ifndef GOT_PACK_NO_MMAP
1797 delta_cache_fd = dup(fileno(delta_cache));
1798 if (delta_cache_fd != -1) {
1799 struct stat sb;
1800 if (fstat(delta_cache_fd, &sb) == -1) {
1801 err = got_error_from_errno("fstat");
1802 goto done;
1803 }
1804 if (sb.st_size > 0 && sb.st_size <= SIZE_MAX) {
1805 delta_cache_map = mmap(NULL, sb.st_size,
1806 PROT_READ, MAP_PRIVATE, delta_cache_fd, 0);
1807 if (delta_cache_map == MAP_FAILED) {
1808 if (errno != ENOMEM) {
1809 err = got_error_from_errno("mmap");
1810 goto done;
1811 }
1812 delta_cache_map = NULL; /* fallback on stdio */
1813 } else
1814 delta_cache_size = (size_t)sb.st_size;
1815 }
1816 }
1817 #endif
1818 err = hwrite(packfd, "PACK", 4, &ctx);
1819 if (err)
1820 goto done;
1821 putbe32(buf, GOT_PACKFILE_VERSION);
1822 err = hwrite(packfd, buf, 4, &ctx);
1823 if (err)
1824 goto done;
1825 putbe32(buf, ndeltify + nreuse);
1826 err = hwrite(packfd, buf, 4, &ctx);
1827 if (err)
1828 goto done;
1829
1830 qsort(deltify, ndeltify, sizeof(struct got_pack_meta *),
1831 write_order_cmp);
1832 for (i = 0; i < ndeltify; i++) {
1833 err = got_pack_report_progress(progress_cb, progress_arg, rl,
1834 ncolored, nfound, ntrees, packfile_size, nours,
1835 ndeltify + nreuse, ndeltify + nreuse, i, 0);
1836 if (err)
1837 goto done;
1838 m = deltify[i];
1839 err = write_packed_object(&packfile_size, packfd,
1840 delta_cache, delta_cache_map, delta_cache_size,
1841 m, &outfd, &ctx, repo, force_refdelta);
1842 if (err)
1843 goto done;
1844 }
1845
1846 qsort(reuse, nreuse, sizeof(struct got_pack_meta *),
1847 reuse_write_order_cmp);
1848 if (nreuse > 0 && reuse_pack->map == NULL) {
1849 int fd = dup(reuse_pack->fd);
1850 if (fd == -1) {
1851 err = got_error_from_errno("dup");
1852 goto done;
1853 }
1854 packfile = fdopen(fd, "r");
1855 if (packfile == NULL) {
1856 err = got_error_from_errno("fdopen");
1857 close(fd);
1858 goto done;
1859 }
1860 }
1861 for (i = 0; i < nreuse; i++) {
1862 err = got_pack_report_progress(progress_cb, progress_arg, rl,
1863 ncolored, nfound, ntrees, packfile_size, nours,
1864 ndeltify + nreuse, ndeltify + nreuse, ndeltify + i, 0);
1865 if (err)
1866 goto done;
1867 m = reuse[i];
1868 err = write_packed_object(&packfile_size, packfd,
1869 packfile, reuse_pack->map, reuse_pack->filesize,
1870 m, &outfd, &ctx, repo, force_refdelta);
1871 if (err)
1872 goto done;
1873 }
1874
1875 got_hash_final_object_id(&ctx, pack_hash);
1876 err = got_poll_write_full(packfd, pack_hash->hash, digest_len);
1877 if (err)
1878 goto done;
1879 packfile_size += digest_len;
1880 packfile_size += sizeof(struct got_packfile_hdr);
1881 if (progress_cb) {
1882 err = progress_cb(progress_arg, ncolored, nfound, ntrees,
1883 packfile_size, nours, ndeltify + nreuse,
1884 ndeltify + nreuse, ndeltify + nreuse, 1);
1885 if (err)
1886 goto done;
1887 }
1888 done:
1889 if (outfd != -1 && close(outfd) == -1 && err == NULL)
1890 err = got_error_from_errno("close");
1891 if (delta_cache_map && munmap(delta_cache_map, delta_cache_size) == -1)
1892 err = got_error_from_errno("munmap");
1893 if (delta_cache_fd != -1 && close(delta_cache_fd) == -1 && err == NULL)
1894 err = got_error_from_errno("close");
1895 if (packfile && fclose(packfile) == EOF && err == NULL)
1896 err = got_error_from_errno("fclose");
1897 return err;
1898 }
1899
1900 static const struct got_error *
1901 add_meta_idset_cb(struct got_object_id *id, void *data, void *arg)
1902 {
1903 struct got_pack_meta *m = data;
1904 struct got_pack_metavec *v = arg;
1905
1906 if (m->reused_delta_offset != 0)
1907 return NULL;
1908
1909 return got_pack_add_meta(m, v);
1910 }
1911
1912 const struct got_error *
1913 got_pack_create(struct got_object_id *packhash, int packfd, FILE *delta_cache,
1914 struct got_object_id **theirs, int ntheirs,
1915 struct got_object_id **ours, int nours,
1916 struct got_repository *repo, int loose_obj_only, int allow_empty,
1917 int force_refdelta, got_pack_progress_cb progress_cb, void *progress_arg,
1918 struct got_ratelimit *rl, got_cancel_cb cancel_cb, void *cancel_arg)
1919 {
1920 const struct got_error *err;
1921 struct got_object_idset *idset;
1922 struct got_packidx *reuse_packidx = NULL;
1923 struct got_pack *reuse_pack = NULL;
1924 struct got_pack_metavec deltify, reuse;
1925 int ncolored = 0, nfound = 0, ntrees = 0;
1926 size_t ndeltify;
1927 uint32_t seed;
1928
1929 seed = arc4random();
1930
1931 memset(&deltify, 0, sizeof(deltify));
1932 memset(&reuse, 0, sizeof(reuse));
1933
1934 idset = got_object_idset_alloc();
1935 if (idset == NULL)
1936 return got_error_from_errno("got_object_idset_alloc");
1937
1938 err = load_object_ids(&ncolored, &nfound, &ntrees, idset, theirs,
1939 ntheirs, ours, nours, repo, seed, loose_obj_only,
1940 progress_cb, progress_arg, rl, cancel_cb, cancel_arg);
1941 if (err)
1942 goto done;
1943
1944 if (progress_cb) {
1945 err = progress_cb(progress_arg, ncolored, nfound, ntrees,
1946 0L, nours, got_object_idset_num_elements(idset), 0, 0, 0);
1947 if (err)
1948 goto done;
1949 }
1950
1951 if (got_object_idset_num_elements(idset) == 0 && !allow_empty) {
1952 err = got_error(GOT_ERR_CANNOT_PACK);
1953 goto done;
1954 }
1955
1956 reuse.metasz = 64;
1957 reuse.meta = calloc(reuse.metasz,
1958 sizeof(struct got_pack_meta *));
1959 if (reuse.meta == NULL) {
1960 err = got_error_from_errno("calloc");
1961 goto done;
1962 }
1963
1964 err = got_pack_search_deltas(&reuse_packidx, &reuse_pack,
1965 &reuse, idset, ncolored, nfound, ntrees, nours,
1966 repo, progress_cb, progress_arg, rl, cancel_cb, cancel_arg);
1967 if (err)
1968 goto done;
1969
1970 if (reuse_packidx && reuse_pack) {
1971 err = got_repo_pin_pack(repo, reuse_packidx, reuse_pack);
1972 if (err)
1973 goto done;
1974 }
1975
1976 if (fseeko(delta_cache, 0L, SEEK_END) == -1) {
1977 err = got_error_from_errno("fseeko");
1978 goto done;
1979 }
1980
1981 ndeltify = got_object_idset_num_elements(idset) - reuse.nmeta;
1982 if (ndeltify > 0) {
1983 deltify.meta = calloc(ndeltify, sizeof(struct got_pack_meta *));
1984 if (deltify.meta == NULL) {
1985 err = got_error_from_errno("calloc");
1986 goto done;
1987 }
1988 deltify.metasz = ndeltify;
1989
1990 err = got_object_idset_for_each(idset, add_meta_idset_cb,
1991 &deltify);
1992 if (err)
1993 goto done;
1994 if (deltify.nmeta > 0) {
1995 err = pick_deltas(deltify.meta, deltify.nmeta,
1996 ncolored, nfound, ntrees, nours, reuse.nmeta,
1997 delta_cache, repo, progress_cb, progress_arg, rl,
1998 cancel_cb, cancel_arg);
1999 if (err)
2000 goto done;
2001 }
2002 }
2003
2004 if (fflush(delta_cache) == EOF) {
2005 err = got_error_from_errno("fflush");
2006 goto done;
2007 }
2008
2009 if (progress_cb) {
2010 /*
2011 * Report a 1-byte packfile write to indicate we are about
2012 * to start sending packfile data. gotd(8) needs this.
2013 */
2014 err = progress_cb(progress_arg, ncolored, nfound, ntrees,
2015 1 /* packfile_size */, nours,
2016 got_object_idset_num_elements(idset),
2017 deltify.nmeta + reuse.nmeta, 0, 0);
2018 if (err)
2019 goto done;
2020 }
2021
2022 /* Pinned pack may have moved to different cache slot. */
2023 reuse_pack = got_repo_get_pinned_pack(repo);
2024
2025 err = genpack(packhash, packfd, reuse_pack, delta_cache, deltify.meta,
2026 deltify.nmeta, reuse.meta, reuse.nmeta, ncolored, nfound, ntrees,
2027 nours, repo, force_refdelta, progress_cb, progress_arg, rl,
2028 cancel_cb, cancel_arg);
2029 if (err)
2030 goto done;
2031 done:
2032 free_nmeta(deltify.meta, deltify.nmeta);
2033 free_nmeta(reuse.meta, reuse.nmeta);
2034 got_object_idset_for_each(idset, free_meta, NULL);
2035 got_object_idset_free(idset);
2036 got_repo_unpin_pack(repo);
2037 return err;
2038 }
portable version of Game of Trees