?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
remote unused parameter 'nids' from got_pack_find_pack_for_commit_painting()
[got-portable.git] / lib / pack_create.c
blob16bbbf96f3e4c7a6e191458f429e5e923e841e94
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) {
1092 STAILQ_REMOVE_HEAD(&ids, entry);
1093 if (!got_object_idset_contains(set, &qid->id)) {
1094 err = got_object_idset_add(set, &qid->id,
1095 NULL);
1096 if (err)
1097 break;
1098 }
1099
1100 err = got_object_open_as_commit(&commit, repo,
1101 &qid->id);
1102 if (err)
1103 break;
1104
1105 got_object_qid_free(qid);
1106 qid = NULL;
1107 }
1108 }
1109
1110 if (commit)
1111 got_object_commit_close(commit);
1112 if (qid)
1113 got_object_qid_free(qid);
1114 got_object_id_queue_free(&ids);
1115
1116 return err;
1117 }
1118
1119 const struct got_error *
1120 got_pack_queue_commit_id(struct got_object_id_queue *ids,
1121 struct got_object_id *id, intptr_t color, struct got_repository *repo)
1122 {
1123 const struct got_error *err;
1124 struct got_object_qid *qid;
1125
1126 err = got_object_qid_alloc(&qid, id);
1127 if (err)
1128 return err;
1129
1130 STAILQ_INSERT_TAIL(ids, qid, entry);
1131 return got_pack_paint_commit(qid, color);
1132 }
1133
1134 struct append_id_arg {
1135 struct got_object_id **array;
1136 int idx;
1137 struct got_object_idset *drop;
1138 struct got_object_idset *skip;
1139 };
1140
1141 static const struct got_error *
1142 append_id(struct got_object_id *id, void *data, void *arg)
1143 {
1144 struct append_id_arg *a = arg;
1145
1146 if (got_object_idset_contains(a->skip, id) ||
1147 got_object_idset_contains(a->drop, id))
1148 return NULL;
1149
1150 a->array[++a->idx] = got_object_id_dup(id);
1151 if (a->array[a->idx] == NULL)
1152 return got_error_from_errno("got_object_id_dup");
1153
1154 return NULL;
1155 }
1156
1157 static const struct got_error *
1158 free_meta(struct got_object_id *id, void *data, void *arg)
1159 {
1160 struct got_pack_meta *meta = data;
1161
1162 clear_meta(meta);
1163 free(meta);
1164 return NULL;
1165 }
1166
1167 static const struct got_error *
1168 queue_commit_or_tag_id(struct got_object_id *id, intptr_t color,
1169 struct got_object_id_queue *ids, struct got_repository *repo)
1170 {
1171 const struct got_error *err;
1172 struct got_tag_object *tag = NULL;
1173 int obj_type;
1174
1175 err = got_object_get_type(&obj_type, repo, id);
1176 if (err)
1177 return err;
1178
1179 if (obj_type == GOT_OBJ_TYPE_TAG) {
1180 err = got_object_open_as_tag(&tag, repo, id);
1181 if (err)
1182 return err;
1183 obj_type = got_object_tag_get_object_type(tag);
1184 id = got_object_tag_get_object_id(tag);
1185 }
1186
1187 if (obj_type == GOT_OBJ_TYPE_COMMIT) {
1188 err = got_pack_queue_commit_id(ids, id, color, repo);
1189 if (err)
1190 goto done;
1191 }
1192 done:
1193 if (tag)
1194 got_object_tag_close(tag);
1195 return err;
1196 }
1197
1198 const struct got_error *
1199 got_pack_find_pack_for_commit_painting(struct got_packidx **best_packidx,
1200 struct got_object_id_queue *ids, struct got_repository *repo)
1201 {
1202 const struct got_error *err = NULL;
1203 struct got_pathlist_entry *pe;
1204 const char *best_packidx_path = NULL;
1205 int nobj_max = 0;
1206 int ncommits_max = 0;
1207
1208 *best_packidx = NULL;
1209
1210 /*
1211 * Find the largest pack which contains at least some of the
1212 * commits we are interested in.
1213 */
1214 RB_FOREACH(pe, got_pathlist_head, &repo->packidx_paths) {
1215 const char *path_packidx = pe->path;
1216 struct got_packidx *packidx;
1217 int nobj, idx, ncommits = 0;
1218 struct got_object_qid *qid;
1219
1220 err = got_repo_get_packidx(&packidx, path_packidx, repo);
1221 if (err)
1222 break;
1223
1224 nobj = be32toh(packidx->hdr.fanout_table[0xff]);
1225 if (nobj <= nobj_max)
1226 continue;
1227
1228 STAILQ_FOREACH(qid, ids, entry) {
1229 idx = got_packidx_get_object_idx(packidx, &qid->id);
1230 if (idx != -1)
1231 ncommits++;
1232 }
1233 if (ncommits > ncommits_max) {
1234 best_packidx_path = path_packidx;
1235 nobj_max = nobj;
1236 ncommits_max = ncommits;
1237 }
1238 }
1239
1240 if (best_packidx_path && err == NULL) {
1241 err = got_repo_get_packidx(best_packidx, best_packidx_path,
1242 repo);
1243 }
1244
1245 return err;
1246 }
1247
1248 static const struct got_error *
1249 findtwixt(struct got_object_id ***res, int *nres, int *ncolored,
1250 struct got_object_id **head, int nhead,
1251 struct got_object_id **tail, int ntail,
1252 struct got_repository *repo,
1253 got_pack_progress_cb progress_cb, void *progress_arg,
1254 struct got_ratelimit *rl, got_cancel_cb cancel_cb, void *cancel_arg)
1255 {
1256 const struct got_error *err = NULL;
1257 struct got_object_id_queue ids;
1258 struct got_object_idset *keep, *drop, *skip = NULL;
1259 int i, nkeep;
1260
1261 STAILQ_INIT(&ids);
1262 *res = NULL;
1263 *nres = 0;
1264 *ncolored = 0;
1265
1266 keep = got_object_idset_alloc();
1267 if (keep == NULL)
1268 return got_error_from_errno("got_object_idset_alloc");
1269
1270 drop = got_object_idset_alloc();
1271 if (drop == NULL) {
1272 err = got_error_from_errno("got_object_idset_alloc");
1273 goto done;
1274 }
1275
1276 skip = got_object_idset_alloc();
1277 if (skip == NULL) {
1278 err = got_error_from_errno("got_object_idset_alloc");
1279 goto done;
1280 }
1281
1282 for (i = 0; i < nhead; i++) {
1283 struct got_object_id *id = head[i];
1284 if (id == NULL)
1285 continue;
1286 err = queue_commit_or_tag_id(id, COLOR_KEEP, &ids, repo);
1287 if (err)
1288 goto done;
1289 }
1290
1291 for (i = 0; i < ntail; i++) {
1292 struct got_object_id *id = tail[i];
1293 if (id == NULL)
1294 continue;
1295 err = queue_commit_or_tag_id(id, COLOR_DROP, &ids, repo);
1296 if (err)
1297 goto done;
1298 }
1299
1300 err = got_pack_paint_commits(ncolored, &ids, nhead + ntail,
1301 keep, drop, skip, repo, progress_cb, progress_arg, rl,
1302 cancel_cb, cancel_arg);
1303 if (err)
1304 goto done;
1305
1306 nkeep = got_object_idset_num_elements(keep);
1307 if (nkeep > 0) {
1308 struct append_id_arg arg;
1309 arg.array = calloc(nkeep, sizeof(struct got_object_id *));
1310 if (arg.array == NULL) {
1311 err = got_error_from_errno("calloc");
1312 goto done;
1313 }
1314 arg.idx = -1;
1315 arg.skip = skip;
1316 arg.drop = drop;
1317 err = got_object_idset_for_each(keep, append_id, &arg);
1318 if (err) {
1319 free(arg.array);
1320 goto done;
1321 }
1322 *res = arg.array;
1323 *nres = arg.idx + 1;
1324 }
1325 done:
1326 got_object_idset_free(keep);
1327 got_object_idset_free(drop);
1328 if (skip)
1329 got_object_idset_free(skip);
1330 got_object_id_queue_free(&ids);
1331 return err;
1332 }
1333
1334 static const struct got_error *
1335 find_pack_for_enumeration(struct got_packidx **best_packidx,
1336 struct got_object_id **ids, int nids, struct got_repository *repo)
1337 {
1338 const struct got_error *err = NULL;
1339 struct got_pathlist_entry *pe;
1340 const char *best_packidx_path = NULL;
1341 int nobj_max = 0;
1342 int ncommits_max = 0;
1343
1344 *best_packidx = NULL;
1345
1346 /*
1347 * Find the largest pack which contains at least some of the
1348 * commits and tags we are interested in.
1349 */
1350 RB_FOREACH(pe, got_pathlist_head, &repo->packidx_paths) {
1351 const char *path_packidx = pe->path;
1352 struct got_packidx *packidx;
1353 int nobj, i, idx, ncommits = 0;
1354
1355 err = got_repo_get_packidx(&packidx, path_packidx, repo);
1356 if (err)
1357 break;
1358
1359 nobj = be32toh(packidx->hdr.fanout_table[0xff]);
1360 if (nobj <= nobj_max)
1361 continue;
1362
1363 for (i = 0; i < nids; i++) {
1364 idx = got_packidx_get_object_idx(packidx, ids[i]);
1365 if (idx != -1)
1366 ncommits++;
1367 }
1368 if (ncommits > ncommits_max) {
1369 best_packidx_path = path_packidx;
1370 nobj_max = nobj;
1371 ncommits_max = ncommits;
1372 }
1373 }
1374
1375 if (best_packidx_path && err == NULL) {
1376 err = got_repo_get_packidx(best_packidx, best_packidx_path,
1377 repo);
1378 }
1379
1380 return err;
1381 }
1382
1383 static const struct got_error *
1384 load_object_ids(int *ncolored, int *nfound, int *ntrees,
1385 struct got_object_idset *idset, struct got_object_id **theirs, int ntheirs,
1386 struct got_object_id **ours, int nours, struct got_repository *repo,
1387 uint32_t seed, int loose_obj_only, got_pack_progress_cb progress_cb,
1388 void *progress_arg, struct got_ratelimit *rl, got_cancel_cb cancel_cb,
1389 void *cancel_arg)
1390 {
1391 const struct got_error *err = NULL;
1392 struct got_object_id **ids = NULL;
1393 struct got_packidx *packidx = NULL;
1394 int i, nobj = 0, obj_type, found_all_objects = 0;
1395 struct got_object_idset *idset_exclude;
1396
1397 idset_exclude = got_object_idset_alloc();
1398 if (idset_exclude == NULL)
1399 return got_error_from_errno("got_object_idset_alloc");
1400
1401 *ncolored = 0;
1402 *nfound = 0;
1403 *ntrees = 0;
1404
1405 err = findtwixt(&ids, &nobj, ncolored, ours, nours, theirs, ntheirs,
1406 repo, progress_cb, progress_arg, rl, cancel_cb, cancel_arg);
1407 if (err)
1408 goto done;
1409
1410 err = find_pack_for_enumeration(&packidx, theirs, ntheirs, repo);
1411 if (err)
1412 goto done;
1413 if (packidx) {
1414 err = got_pack_load_packed_object_ids(&found_all_objects,
1415 theirs, ntheirs, NULL, 0, 0, seed, idset, idset_exclude,
1416 loose_obj_only, repo, packidx, ncolored, nfound, ntrees,
1417 progress_cb, progress_arg, rl, cancel_cb, cancel_arg);
1418 if (err)
1419 goto done;
1420 }
1421
1422 for (i = 0; i < ntheirs; i++) {
1423 struct got_object_id *id = theirs[i];
1424 if (id == NULL)
1425 continue;
1426 err = got_object_get_type(&obj_type, repo, id);
1427 if (err)
1428 return err;
1429 if (obj_type == GOT_OBJ_TYPE_COMMIT) {
1430 if (!found_all_objects) {
1431 err = load_commit(0, idset, idset_exclude,
1432 id, repo, seed, loose_obj_only,
1433 ncolored, nfound, ntrees,
1434 progress_cb, progress_arg, rl,
1435 cancel_cb, cancel_arg);
1436 if (err)
1437 goto done;
1438 }
1439 } else if (obj_type == GOT_OBJ_TYPE_TAG) {
1440 err = load_tag(0, idset, idset_exclude, id, repo,
1441 seed, loose_obj_only, ncolored, nfound, ntrees,
1442 progress_cb, progress_arg, rl,
1443 cancel_cb, cancel_arg);
1444 if (err)
1445 goto done;
1446 }
1447 }
1448
1449 found_all_objects = 0;
1450 err = find_pack_for_enumeration(&packidx, ids, nobj, repo);
1451 if (err)
1452 goto done;
1453 if (packidx) {
1454 err = got_pack_load_packed_object_ids(&found_all_objects, ids,
1455 nobj, theirs, ntheirs, 1, seed, idset, idset_exclude,
1456 loose_obj_only, repo, packidx, ncolored, nfound, ntrees,
1457 progress_cb, progress_arg, rl, cancel_cb, cancel_arg);
1458 if (err)
1459 goto done;
1460 }
1461
1462 if (!found_all_objects) {
1463 for (i = 0; i < nobj; i++) {
1464 err = load_commit(1, idset, idset_exclude, ids[i],
1465 repo, seed, loose_obj_only, ncolored, nfound,
1466 ntrees, progress_cb, progress_arg, rl,
1467 cancel_cb, cancel_arg);
1468 if (err)
1469 goto done;
1470 }
1471 }
1472
1473 for (i = 0; i < nours; i++) {
1474 struct got_object_id *id = ours[i];
1475 struct got_pack_meta *m;
1476 if (id == NULL)
1477 continue;
1478 m = got_object_idset_get(idset, id);
1479 if (m == NULL) {
1480 err = got_object_get_type(&obj_type, repo, id);
1481 if (err)
1482 goto done;
1483 } else
1484 obj_type = m->obj_type;
1485 if (obj_type != GOT_OBJ_TYPE_TAG)
1486 continue;
1487 err = load_tag(1, idset, idset_exclude, id, repo,
1488 seed, loose_obj_only, ncolored, nfound, ntrees,
1489 progress_cb, progress_arg, rl, cancel_cb, cancel_arg);
1490 if (err)
1491 goto done;
1492 }
1493 done:
1494 for (i = 0; i < nobj; i++) {
1495 free(ids[i]);
1496 }
1497 free(ids);
1498 got_object_idset_free(idset_exclude);
1499 return err;
1500 }
1501
1502 static const struct got_error *
1503 hwrite(int fd, const void *buf, off_t len, struct got_hash *ctx)
1504 {
1505 got_hash_update(ctx, buf, len);
1506 return got_poll_write_full(fd, buf, len);
1507 }
1508
1509 static const struct got_error *
1510 hcopy(FILE *fsrc, int fd_dst, off_t len, struct got_hash *ctx)
1511 {
1512 const struct got_error *err;
1513 unsigned char buf[65536];
1514 off_t remain = len;
1515 size_t n;
1516
1517 while (remain > 0) {
1518 size_t copylen = MIN(sizeof(buf), remain);
1519 n = fread(buf, 1, copylen, fsrc);
1520 if (n != copylen)
1521 return got_ferror(fsrc, GOT_ERR_IO);
1522 got_hash_update(ctx, buf, copylen);
1523 err = got_poll_write_full(fd_dst, buf, copylen);
1524 if (err)
1525 return err;
1526 remain -= copylen;
1527 }
1528
1529 return NULL;
1530 }
1531
1532 static const struct got_error *
1533 hcopy_mmap(uint8_t *src, off_t src_offset, size_t src_size,
1534 int fd, off_t len, struct got_hash *ctx)
1535 {
1536 if (src_offset + len > src_size)
1537 return got_error(GOT_ERR_RANGE);
1538
1539 got_hash_update(ctx, src + src_offset, len);
1540 return got_poll_write_full(fd, src + src_offset, len);
1541 }
1542
1543 static void
1544 putbe32(char *b, uint32_t n)
1545 {
1546 b[0] = n >> 24;
1547 b[1] = n >> 16;
1548 b[2] = n >> 8;
1549 b[3] = n >> 0;
1550 }
1551
1552 static int
1553 write_order_cmp(const void *pa, const void *pb)
1554 {
1555 struct got_pack_meta *a, *b, *ahd, *bhd;
1556
1557 a = *(struct got_pack_meta **)pa;
1558 b = *(struct got_pack_meta **)pb;
1559 ahd = (a->head == NULL) ? a : a->head;
1560 bhd = (b->head == NULL) ? b : b->head;
1561 if (bhd->mtime < ahd->mtime)
1562 return -1;
1563 if (bhd->mtime > ahd->mtime)
1564 return 1;
1565 if (bhd < ahd)
1566 return -1;
1567 if (bhd > ahd)
1568 return 1;
1569 if (a->nchain != b->nchain)
1570 return a->nchain - b->nchain;
1571 if (a->mtime < b->mtime)
1572 return -1;
1573 if (a->mtime > b->mtime)
1574 return 1;
1575 return got_object_id_cmp(&a->id, &b->id);
1576 }
1577
1578 static int
1579 reuse_write_order_cmp(const void *pa, const void *pb)
1580 {
1581 struct got_pack_meta *a, *b;
1582
1583 a = *(struct got_pack_meta **)pa;
1584 b = *(struct got_pack_meta **)pb;
1585
1586 if (a->reused_delta_offset < b->reused_delta_offset)
1587 return -1;
1588 if (a->reused_delta_offset > b->reused_delta_offset)
1589 return 1;
1590 return 0;
1591 }
1592
1593 static const struct got_error *
1594 packhdr(int *hdrlen, char *hdr, size_t bufsize, int obj_type, size_t len)
1595 {
1596 size_t i;
1597
1598 *hdrlen = 0;
1599
1600 hdr[0] = obj_type << 4;
1601 hdr[0] |= len & 0xf;
1602 len >>= 4;
1603 for (i = 1; len != 0; i++){
1604 if (i >= bufsize)
1605 return got_error(GOT_ERR_NO_SPACE);
1606 hdr[i - 1] |= GOT_DELTA_SIZE_MORE;
1607 hdr[i] = len & GOT_DELTA_SIZE_VAL_MASK;
1608 len >>= GOT_DELTA_SIZE_SHIFT;
1609 }
1610
1611 *hdrlen = i;
1612 return NULL;
1613 }
1614
1615 static int
1616 packoff(char *hdr, off_t off)
1617 {
1618 int i, j;
1619 char rbuf[8];
1620
1621 rbuf[0] = off & GOT_DELTA_SIZE_VAL_MASK;
1622 for (i = 1; (off >>= GOT_DELTA_SIZE_SHIFT) != 0; i++) {
1623 rbuf[i] = (--off & GOT_DELTA_SIZE_VAL_MASK) |
1624 GOT_DELTA_SIZE_MORE;
1625 }
1626
1627 j = 0;
1628 while (i > 0)
1629 hdr[j++] = rbuf[--i];
1630 return j;
1631 }
1632
1633 static const struct got_error *
1634 deltahdr(off_t *packfile_size, struct got_hash *ctx, int packfd,
1635 int force_refdelta, struct got_pack_meta *m)
1636 {
1637 const struct got_error *err;
1638 char buf[32];
1639 int nh;
1640 size_t digest_len = got_hash_digest_length(m->prev->id.algo);
1641
1642 if (m->prev->off != 0 && !force_refdelta) {
1643 err = packhdr(&nh, buf, sizeof(buf),
1644 GOT_OBJ_TYPE_OFFSET_DELTA, m->delta_len);
1645 if (err)
1646 return err;
1647 nh += packoff(buf + nh, m->off - m->prev->off);
1648 err = hwrite(packfd, buf, nh, ctx);
1649 if (err)
1650 return err;
1651 *packfile_size += nh;
1652 } else {
1653 err = packhdr(&nh, buf, sizeof(buf),
1654 GOT_OBJ_TYPE_REF_DELTA, m->delta_len);
1655 if (err)
1656 return err;
1657 err = hwrite(packfd, buf, nh, ctx);
1658 if (err)
1659 return err;
1660 *packfile_size += nh;
1661 err = hwrite(packfd, m->prev->id.hash, digest_len, ctx);
1662 if (err)
1663 return err;
1664 *packfile_size += digest_len;
1665 }
1666
1667 return NULL;
1668 }
1669
1670 static const struct got_error *
1671 write_packed_object(off_t *packfile_size, int packfd,
1672 FILE *delta_cache, uint8_t *delta_cache_map, size_t delta_cache_size,
1673 struct got_pack_meta *m, int *outfd, struct got_hash *ctx,
1674 struct got_repository *repo, int force_refdelta)
1675 {
1676 const struct got_error *err = NULL;
1677 struct got_deflate_checksum csum;
1678 char buf[32];
1679 int nh;
1680 struct got_raw_object *raw = NULL;
1681 off_t outlen, delta_offset;
1682
1683 memset(&csum, 0, sizeof(csum));
1684 csum.output_ctx = ctx;
1685
1686 if (m->reused_delta_offset)
1687 delta_offset = m->reused_delta_offset;
1688 else
1689 delta_offset = m->delta_offset;
1690
1691 m->off = *packfile_size;
1692 if (m->delta_len == 0) {
1693 err = got_object_raw_open(&raw, outfd, repo, &m->id);
1694 if (err)
1695 goto done;
1696 err = packhdr(&nh, buf, sizeof(buf),
1697 m->obj_type, raw->size);
1698 if (err)
1699 goto done;
1700 err = hwrite(packfd, buf, nh, ctx);
1701 if (err)
1702 goto done;
1703 *packfile_size += nh;
1704 if (raw->f == NULL) {
1705 err = got_deflate_to_fd_mmap(&outlen,
1706 raw->data + raw->hdrlen, 0, raw->size,
1707 packfd, &csum);
1708 if (err)
1709 goto done;
1710 } else {
1711 if (fseeko(raw->f, raw->hdrlen, SEEK_SET)
1712 == -1) {
1713 err = got_error_from_errno("fseeko");
1714 goto done;
1715 }
1716 err = got_deflate_to_fd(&outlen, raw->f,
1717 raw->size, packfd, &csum);
1718 if (err)
1719 goto done;
1720 }
1721 *packfile_size += outlen;
1722 got_object_raw_close(raw);
1723 raw = NULL;
1724 } else if (m->delta_buf) {
1725 err = deltahdr(packfile_size, ctx, packfd, force_refdelta, m);
1726 if (err)
1727 goto done;
1728 err = hwrite(packfd, m->delta_buf,
1729 m->delta_compressed_len, ctx);
1730 if (err)
1731 goto done;
1732 *packfile_size += m->delta_compressed_len;
1733 free(m->delta_buf);
1734 m->delta_buf = NULL;
1735 } else if (delta_cache_map) {
1736 err = deltahdr(packfile_size, ctx, packfd, force_refdelta, m);
1737 if (err)
1738 goto done;
1739 err = hcopy_mmap(delta_cache_map, delta_offset,
1740 delta_cache_size, packfd, m->delta_compressed_len,
1741 ctx);
1742 if (err)
1743 goto done;
1744 *packfile_size += m->delta_compressed_len;
1745 } else {
1746 if (fseeko(delta_cache, delta_offset, SEEK_SET) == -1) {
1747 err = got_error_from_errno("fseeko");
1748 goto done;
1749 }
1750 err = deltahdr(packfile_size, ctx, packfd, force_refdelta, m);
1751 if (err)
1752 goto done;
1753 err = hcopy(delta_cache, packfd,
1754 m->delta_compressed_len, ctx);
1755 if (err)
1756 goto done;
1757 *packfile_size += m->delta_compressed_len;
1758 }
1759 done:
1760 if (raw)
1761 got_object_raw_close(raw);
1762 return err;
1763 }
1764
1765 static const struct got_error *
1766 genpack(struct got_object_id *pack_hash, int packfd,
1767 struct got_pack *reuse_pack, FILE *delta_cache,
1768 struct got_pack_meta **deltify, int ndeltify,
1769 struct got_pack_meta **reuse, int nreuse,
1770 int ncolored, int nfound, int ntrees, int nours,
1771 struct got_repository *repo, int force_refdelta,
1772 got_pack_progress_cb progress_cb, void *progress_arg,
1773 struct got_ratelimit *rl,
1774 got_cancel_cb cancel_cb, void *cancel_arg)
1775 {
1776 const struct got_error *err = NULL;
1777 int i;
1778 struct got_hash ctx;
1779 struct got_pack_meta *m;
1780 char buf[32];
1781 off_t packfile_size = 0;
1782 int outfd = -1;
1783 int delta_cache_fd = -1;
1784 uint8_t *delta_cache_map = NULL;
1785 size_t delta_cache_size = 0;
1786 FILE *packfile = NULL;
1787 enum got_hash_algorithm algo;
1788 size_t digest_len;
1789
1790 algo = got_repo_get_object_format(repo);
1791 digest_len = got_hash_digest_length(algo);
1792 got_hash_init(&ctx, algo);
1793
1794 memset(pack_hash, 0, sizeof(*pack_hash));
1795 pack_hash->algo = algo;
1796
1797 #ifndef GOT_PACK_NO_MMAP
1798 delta_cache_fd = dup(fileno(delta_cache));
1799 if (delta_cache_fd != -1) {
1800 struct stat sb;
1801 if (fstat(delta_cache_fd, &sb) == -1) {
1802 err = got_error_from_errno("fstat");
1803 goto done;
1804 }
1805 if (sb.st_size > 0 && sb.st_size <= SIZE_MAX) {
1806 delta_cache_map = mmap(NULL, sb.st_size,
1807 PROT_READ, MAP_PRIVATE, delta_cache_fd, 0);
1808 if (delta_cache_map == MAP_FAILED) {
1809 if (errno != ENOMEM) {
1810 err = got_error_from_errno("mmap");
1811 goto done;
1812 }
1813 delta_cache_map = NULL; /* fallback on stdio */
1814 } else
1815 delta_cache_size = (size_t)sb.st_size;
1816 }
1817 }
1818 #endif
1819 err = hwrite(packfd, "PACK", 4, &ctx);
1820 if (err)
1821 goto done;
1822 putbe32(buf, GOT_PACKFILE_VERSION);
1823 err = hwrite(packfd, buf, 4, &ctx);
1824 if (err)
1825 goto done;
1826 putbe32(buf, ndeltify + nreuse);
1827 err = hwrite(packfd, buf, 4, &ctx);
1828 if (err)
1829 goto done;
1830
1831 qsort(deltify, ndeltify, sizeof(struct got_pack_meta *),
1832 write_order_cmp);
1833 for (i = 0; i < ndeltify; i++) {
1834 err = got_pack_report_progress(progress_cb, progress_arg, rl,
1835 ncolored, nfound, ntrees, packfile_size, nours,
1836 ndeltify + nreuse, ndeltify + nreuse, i, 0);
1837 if (err)
1838 goto done;
1839 m = deltify[i];
1840 err = write_packed_object(&packfile_size, packfd,
1841 delta_cache, delta_cache_map, delta_cache_size,
1842 m, &outfd, &ctx, repo, force_refdelta);
1843 if (err)
1844 goto done;
1845 }
1846
1847 qsort(reuse, nreuse, sizeof(struct got_pack_meta *),
1848 reuse_write_order_cmp);
1849 if (nreuse > 0 && reuse_pack->map == NULL) {
1850 int fd = dup(reuse_pack->fd);
1851 if (fd == -1) {
1852 err = got_error_from_errno("dup");
1853 goto done;
1854 }
1855 packfile = fdopen(fd, "r");
1856 if (packfile == NULL) {
1857 err = got_error_from_errno("fdopen");
1858 close(fd);
1859 goto done;
1860 }
1861 }
1862 for (i = 0; i < nreuse; i++) {
1863 err = got_pack_report_progress(progress_cb, progress_arg, rl,
1864 ncolored, nfound, ntrees, packfile_size, nours,
1865 ndeltify + nreuse, ndeltify + nreuse, ndeltify + i, 0);
1866 if (err)
1867 goto done;
1868 m = reuse[i];
1869 err = write_packed_object(&packfile_size, packfd,
1870 packfile, reuse_pack->map, reuse_pack->filesize,
1871 m, &outfd, &ctx, repo, force_refdelta);
1872 if (err)
1873 goto done;
1874 }
1875
1876 got_hash_final_object_id(&ctx, pack_hash);
1877 err = got_poll_write_full(packfd, pack_hash->hash, digest_len);
1878 if (err)
1879 goto done;
1880 packfile_size += digest_len;
1881 packfile_size += sizeof(struct got_packfile_hdr);
1882 if (progress_cb) {
1883 err = progress_cb(progress_arg, ncolored, nfound, ntrees,
1884 packfile_size, nours, ndeltify + nreuse,
1885 ndeltify + nreuse, ndeltify + nreuse, 1);
1886 if (err)
1887 goto done;
1888 }
1889 done:
1890 if (outfd != -1 && close(outfd) == -1 && err == NULL)
1891 err = got_error_from_errno("close");
1892 if (delta_cache_map && munmap(delta_cache_map, delta_cache_size) == -1)
1893 err = got_error_from_errno("munmap");
1894 if (delta_cache_fd != -1 && close(delta_cache_fd) == -1 && err == NULL)
1895 err = got_error_from_errno("close");
1896 if (packfile && fclose(packfile) == EOF && err == NULL)
1897 err = got_error_from_errno("fclose");
1898 return err;
1899 }
1900
1901 static const struct got_error *
1902 add_meta_idset_cb(struct got_object_id *id, void *data, void *arg)
1903 {
1904 struct got_pack_meta *m = data;
1905 struct got_pack_metavec *v = arg;
1906
1907 if (m->reused_delta_offset != 0)
1908 return NULL;
1909
1910 return got_pack_add_meta(m, v);
1911 }
1912
1913 const struct got_error *
1914 got_pack_create(struct got_object_id *packhash, int packfd, FILE *delta_cache,
1915 struct got_object_id **theirs, int ntheirs,
1916 struct got_object_id **ours, int nours,
1917 struct got_repository *repo, int loose_obj_only, int allow_empty,
1918 int force_refdelta, got_pack_progress_cb progress_cb, void *progress_arg,
1919 struct got_ratelimit *rl, got_cancel_cb cancel_cb, void *cancel_arg)
1920 {
1921 const struct got_error *err;
1922 struct got_object_idset *idset;
1923 struct got_packidx *reuse_packidx = NULL;
1924 struct got_pack *reuse_pack = NULL;
1925 struct got_pack_metavec deltify, reuse;
1926 int ncolored = 0, nfound = 0, ntrees = 0;
1927 size_t ndeltify;
1928 uint32_t seed;
1929
1930 seed = arc4random();
1931
1932 memset(&deltify, 0, sizeof(deltify));
1933 memset(&reuse, 0, sizeof(reuse));
1934
1935 idset = got_object_idset_alloc();
1936 if (idset == NULL)
1937 return got_error_from_errno("got_object_idset_alloc");
1938
1939 err = load_object_ids(&ncolored, &nfound, &ntrees, idset, theirs,
1940 ntheirs, ours, nours, repo, seed, loose_obj_only,
1941 progress_cb, progress_arg, rl, cancel_cb, cancel_arg);
1942 if (err)
1943 goto done;
1944
1945 if (progress_cb) {
1946 err = progress_cb(progress_arg, ncolored, nfound, ntrees,
1947 0L, nours, got_object_idset_num_elements(idset), 0, 0, 0);
1948 if (err)
1949 goto done;
1950 }
1951
1952 if (got_object_idset_num_elements(idset) == 0 && !allow_empty) {
1953 err = got_error(GOT_ERR_CANNOT_PACK);
1954 goto done;
1955 }
1956
1957 reuse.metasz = 64;
1958 reuse.meta = calloc(reuse.metasz,
1959 sizeof(struct got_pack_meta *));
1960 if (reuse.meta == NULL) {
1961 err = got_error_from_errno("calloc");
1962 goto done;
1963 }
1964
1965 err = got_pack_search_deltas(&reuse_packidx, &reuse_pack,
1966 &reuse, idset, ncolored, nfound, ntrees, nours,
1967 repo, progress_cb, progress_arg, rl, cancel_cb, cancel_arg);
1968 if (err)
1969 goto done;
1970
1971 if (reuse_packidx && reuse_pack) {
1972 err = got_repo_pin_pack(repo, reuse_packidx, reuse_pack);
1973 if (err)
1974 goto done;
1975 }
1976
1977 if (fseeko(delta_cache, 0L, SEEK_END) == -1) {
1978 err = got_error_from_errno("fseeko");
1979 goto done;
1980 }
1981
1982 ndeltify = got_object_idset_num_elements(idset) - reuse.nmeta;
1983 if (ndeltify > 0) {
1984 deltify.meta = calloc(ndeltify, sizeof(struct got_pack_meta *));
1985 if (deltify.meta == NULL) {
1986 err = got_error_from_errno("calloc");
1987 goto done;
1988 }
1989 deltify.metasz = ndeltify;
1990
1991 err = got_object_idset_for_each(idset, add_meta_idset_cb,
1992 &deltify);
1993 if (err)
1994 goto done;
1995 if (deltify.nmeta > 0) {
1996 err = pick_deltas(deltify.meta, deltify.nmeta,
1997 ncolored, nfound, ntrees, nours, reuse.nmeta,
1998 delta_cache, repo, progress_cb, progress_arg, rl,
1999 cancel_cb, cancel_arg);
2000 if (err)
2001 goto done;
2002 }
2003 }
2004
2005 if (fflush(delta_cache) == EOF) {
2006 err = got_error_from_errno("fflush");
2007 goto done;
2008 }
2009
2010 if (progress_cb) {
2011 /*
2012 * Report a 1-byte packfile write to indicate we are about
2013 * to start sending packfile data. gotd(8) needs this.
2014 */
2015 err = progress_cb(progress_arg, ncolored, nfound, ntrees,
2016 1 /* packfile_size */, nours,
2017 got_object_idset_num_elements(idset),
2018 deltify.nmeta + reuse.nmeta, 0, 0);
2019 if (err)
2020 goto done;
2021 }
2022
2023 /* Pinned pack may have moved to different cache slot. */
2024 reuse_pack = got_repo_get_pinned_pack(repo);
2025
2026 err = genpack(packhash, packfd, reuse_pack, delta_cache, deltify.meta,
2027 deltify.nmeta, reuse.meta, reuse.nmeta, ncolored, nfound, ntrees,
2028 nours, repo, force_refdelta, progress_cb, progress_arg, rl,
2029 cancel_cb, cancel_arg);
2030 if (err)
2031 goto done;
2032 done:
2033 free_nmeta(deltify.meta, deltify.nmeta);
2034 free_nmeta(reuse.meta, reuse.nmeta);
2035 got_object_idset_for_each(idset, free_meta, NULL);
2036 got_object_idset_free(idset);
2037 got_repo_unpin_pack(repo);
2038 return err;
2039 }
portable version of Game of Trees