lib/pack_create.c

   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 <sys/types.h>
  19 #include <sys/queue.h>
  20 #include <sys/tree.h>
  21 #include <sys/uio.h>
  22 #include <sys/stat.h>
  23
  24 #include <stdint.h>
  25 #include <stdio.h>
  26 #include <stdlib.h>
  27 #include <string.h>
  28 #include <limits.h>
  29 #include <zlib.h>
  30
  31 #include "got_error.h"
  32 #include "got_cancel.h"
  33 #include "got_object.h"
  34 #include "got_path.h"
  35 #include "got_reference.h"
  36 #include "got_repository_admin.h"
  37 #include "got_opentemp.h"
  38
  39 #include "got_lib_deltify.h"
  40 #include "got_lib_delta.h"
  41 #include "got_lib_object.h"
  42 #include "got_lib_object_idset.h"
  43 #include "got_lib_object_cache.h"
  44 #include "got_lib_deflate.h"
  45 #include "got_lib_pack.h"
  46 #include "got_lib_privsep.h"
  47 #include "got_lib_repository.h"
  48
  49 #ifndef MAX
  50 #define MAX(_a,_b) ((_a) > (_b) ? (_a) : (_b))
  51 #endif
  52
  53 struct got_pack_meta {
  54         struct got_object_id id;
  55         char    *path;
  56         int     obj_type;
  57         time_t  mtime;
  58
  59         /* The best delta we picked */
  60         struct got_pack_meta *head;
  61         struct got_pack_meta *prev;
  62         struct got_delta_instruction *deltas;
  63         int     ndeltas;
  64         int     nchain;
  65
  66         /* Only used for delta window */
  67         struct got_delta_table *dtab;
  68
  69         /* Only used for writing offset deltas */
  70         off_t   off;
  71 };
  72
  73 struct got_pack_metavec {
  74         struct got_pack_meta **meta;
  75         int nmeta;
  76         int metasz;
  77 };
  78
  79 static const struct got_error *
  80 alloc_meta(struct got_pack_meta **new, struct got_object_id *id,
  81     const char *path, int obj_type, time_t mtime)
  82 {
  83         const struct got_error *err = NULL;
  84         struct got_pack_meta *m;
  85
  86         *new = NULL;
  87
  88         m = calloc(1, sizeof(*m));
  89         if (m == NULL)
  90                 return got_error_from_errno("calloc");
  91
  92         memcpy(&m->id, id, sizeof(m->id));
  93
  94         m->path = strdup(path);
  95         if (m->path == NULL) {
  96                 err = got_error_from_errno("strdup");
  97                 free(m);
  98                 return err;
  99         }
 100
 101         m->obj_type = obj_type;
 102         m->mtime = mtime;
 103         *new = m;
 104         return NULL;
 105 }
 106
 107 static void
 108 clear_meta(struct got_pack_meta *meta)
 109 {
 110         if (meta == NULL)
 111                 return;
 112         free(meta->deltas);
 113         meta->deltas = NULL;
 114         free(meta->path);
 115         meta->path = NULL;
 116 }
 117
 118 static void
 119 free_nmeta(struct got_pack_meta **meta, int nmeta)
 120 {
 121         int i;
 122
 123         for (i = 0; i < nmeta; i++)
 124                 clear_meta(meta[i]);
 125         free(meta);
 126 }
 127
 128 static int
 129 delta_order_cmp(const void *pa, const void *pb)
 130 {
 131         struct got_pack_meta *a, *b;
 132         int cmp;
 133
 134         a = *(struct got_pack_meta **)pa;
 135         b = *(struct got_pack_meta **)pb;
 136
 137         if (a->obj_type != b->obj_type)
 138                 return a->obj_type - b->obj_type;
 139         cmp = strcmp(a->path, b->path);
 140         if (cmp != 0)
 141                 return cmp;
 142         if (a->mtime != b->mtime)
 143                 return a->mtime - b->mtime;
 144         return got_object_id_cmp(&a->id, &b->id);
 145 }
 146
 147 static int
 148 delta_size(struct got_delta_instruction *deltas, int ndeltas)
 149 {
 150         int i, size = 32;
 151         for (i = 0; i < ndeltas; i++) {
 152                 if (deltas[i].copy)
 153                         size += GOT_DELTA_SIZE_SHIFT;
 154                 else
 155                         size += deltas[i].len + 1;
 156         }
 157         return size;
 158 }
 159
 160
 161 static const struct got_error *
 162 pick_deltas(struct got_pack_meta **meta, int nmeta, int nours,
 163     struct got_repository *repo,
 164     got_pack_progress_cb progress_cb, void *progress_arg,
 165     got_cancel_cb cancel_cb, void *cancel_arg)
 166 {
 167         const struct got_error *err = NULL;
 168         struct got_pack_meta *m = NULL, *base = NULL;
 169         struct got_raw_object *raw = NULL, *base_raw = NULL;
 170         struct got_delta_instruction *deltas;
 171         int i, j, size, ndeltas, best;
 172         const int max_base_candidates = 10;
 173
 174         qsort(meta, nmeta, sizeof(struct got_pack_meta *), delta_order_cmp);
 175         for (i = 0; i < nmeta; i++) {
 176                 if (cancel_cb) {
 177                         err = (*cancel_cb)(cancel_arg);
 178                         if (err)
 179                                 break;
 180                 }
 181                 if (progress_cb) {
 182                         err = progress_cb(progress_arg, 0L, nours, nmeta, i, 0);
 183                         if (err)
 184                                 goto done;
 185                 }
 186                 m = meta[i];
 187                 m->deltas = NULL;
 188                 m->ndeltas = 0;
 189
 190                 if (m->obj_type == GOT_OBJ_TYPE_COMMIT ||
 191                     m->obj_type == GOT_OBJ_TYPE_TAG)
 192                         continue;
 193
 194                 err = got_object_raw_open(&raw, repo, &m->id, 8192);
 195                 if (err)
 196                         goto done;
 197
 198                 err = got_deltify_init(&m->dtab, raw->f, raw->hdrlen,
 199                     raw->size + raw->hdrlen);
 200                 if (err)
 201                         goto done;
 202
 203                 if (i > max_base_candidates) {
 204                         struct got_pack_meta *n = NULL;
 205                         n = meta[i - (max_base_candidates + 1)];
 206                         got_deltify_free(n->dtab);
 207                         n->dtab = NULL;
 208                 }
 209
 210                 best = raw->size;
 211                 for (j = MAX(0, i - max_base_candidates); j < i; j++) {
 212                         if (cancel_cb) {
 213                                 err = (*cancel_cb)(cancel_arg);
 214                                 if (err)
 215                                         goto done;
 216                         }
 217                         base = meta[j];
 218                         /* long chains make unpacking slow, avoid such bases */
 219                         if (base->nchain >= 128 ||
 220                             base->obj_type != m->obj_type)
 221                                 continue;
 222
 223                         err = got_object_raw_open(&base_raw, repo, &base->id,
 224                             8192);
 225                         if (err)
 226                                 goto done;
 227                         err = got_deltify(&deltas, &ndeltas,
 228                             raw->f, raw->hdrlen, raw->size + raw->hdrlen,
 229                             base->dtab, base_raw->f, base_raw->hdrlen,
 230                             base_raw->size + base_raw->hdrlen);
 231                         got_object_raw_close(base_raw);
 232                         base_raw = NULL;
 233                         if (err)
 234                                 goto done;
 235
 236                         size = delta_size(deltas, ndeltas);
 237                         if (size + 32 < best){
 238                                 /*
 239                                  * if we already picked a best delta,
 240                                  * replace it.
 241                                  */
 242                                 free(m->deltas);
 243                                 best = size;
 244                                 m->deltas = deltas;
 245                                 m->ndeltas = ndeltas;
 246                                 m->nchain = base->nchain + 1;
 247                                 m->prev = base;
 248                                 m->head = base->head;
 249                                 if (m->head == NULL)
 250                                         m->head = base;
 251                         } else {
 252                                 free(deltas);
 253                                 deltas = NULL;
 254                                 ndeltas = 0;
 255                         }
 256                 }
 257
 258                 got_object_raw_close(raw);
 259                 raw = NULL;
 260         }
 261 done:
 262         for (i = MAX(0, nmeta - max_base_candidates); i < nmeta; i++) {
 263                 got_deltify_free(meta[i]->dtab);
 264                 meta[i]->dtab = NULL;
 265         }
 266         if (raw)
 267                 got_object_raw_close(raw);
 268         if (base_raw)
 269                 got_object_raw_close(base_raw);
 270         return err;
 271 }
 272
 273 static const struct got_error *
 274 search_packidx(int *found, struct got_object_id *id,
 275     struct got_repository *repo)
 276 {
 277         const struct got_error *err = NULL;
 278         struct got_packidx *packidx = NULL;
 279         int idx;
 280
 281         *found = 0;
 282
 283         err = got_repo_search_packidx(&packidx, &idx, repo, id);
 284         if (err == NULL)
 285                 *found = 1; /* object is already packed */
 286         else if (err->code == GOT_ERR_NO_OBJ)
 287                 err = NULL;
 288         return err;
 289 }
 290
 291 static const int obj_types[] = {
 292         GOT_OBJ_TYPE_ANY,
 293         GOT_OBJ_TYPE_COMMIT,
 294         GOT_OBJ_TYPE_TREE,
 295         GOT_OBJ_TYPE_BLOB,
 296         GOT_OBJ_TYPE_TAG,
 297         GOT_OBJ_TYPE_OFFSET_DELTA,
 298         GOT_OBJ_TYPE_REF_DELTA
 299 };
 300
 301 static const struct got_error *
 302 add_meta(struct got_pack_metavec *v, struct got_object_idset *idset,
 303     struct got_object_id *id, const char *path, int obj_type,
 304     time_t mtime, int loose_obj_only, struct got_repository *repo)
 305 {
 306         const struct got_error *err;
 307         struct got_pack_meta *m;
 308
 309         if (loose_obj_only) {
 310                 int is_packed;
 311                 err = search_packidx(&is_packed, id, repo);
 312                 if (err)
 313                         return err;
 314                 if (is_packed)
 315                         return NULL;
 316         }
 317
 318         err = got_object_idset_add(idset, id, (void *)&obj_types[obj_type]);
 319         if (err)
 320                 return err;
 321
 322         if (v == NULL)
 323                 return NULL;
 324
 325         err = alloc_meta(&m, id, path, obj_type, mtime);
 326         if (err)
 327                 goto done;
 328
 329         if (v->nmeta == v->metasz){
 330                 size_t newsize = 2 * v->metasz;
 331                 struct got_pack_meta **new;
 332                 new = reallocarray(v->meta, newsize, sizeof(*new));
 333                 if (new == NULL) {
 334                         err = got_error_from_errno("reallocarray");
 335                         goto done;
 336                 }
 337                 v->meta = new;
 338                 v->metasz = newsize;
 339         }
 340 done:
 341         if (err) {
 342                 clear_meta(m);
 343                 free(m);
 344         } else
 345                 v->meta[v->nmeta++] = m;
 346
 347         return err;
 348 }
 349
 350 static const struct got_error *
 351 load_tree_entries(struct got_object_id_queue *ids, struct got_pack_metavec *v,
 352     struct got_object_idset *idset, struct got_object_id *tree_id,
 353     const char *dpath, time_t mtime, struct got_repository *repo,
 354     int loose_obj_only, got_cancel_cb cancel_cb, void *cancel_arg)
 355 {
 356         const struct got_error *err;
 357         struct got_tree_object *tree;
 358         char *p = NULL;
 359         int i;
 360
 361         err = got_object_open_as_tree(&tree, repo, tree_id);
 362         if (err)
 363                 return err;
 364
 365         for (i = 0; i < got_object_tree_get_nentries(tree); i++) {
 366                 struct got_tree_entry *e = got_object_tree_get_entry(tree, i);
 367                 struct got_object_id *id = got_tree_entry_get_id(e);
 368                 mode_t mode = got_tree_entry_get_mode(e);
 369
 370                 if (cancel_cb) {
 371                         err = (*cancel_cb)(cancel_arg);
 372                         if (err)
 373                                 break;
 374                 }
 375
 376                 if (got_object_tree_entry_is_submodule(e) ||
 377                     got_object_idset_contains(idset, id))
 378                         continue;
 379
 380                 if (asprintf(&p, "%s%s%s", dpath, dpath[0] != '\0' ? "/" : "",
 381                     got_tree_entry_get_name(e)) == -1) {
 382                         err = got_error_from_errno("asprintf");
 383                         break;
 384                 }
 385
 386                 if (S_ISDIR(mode)) {
 387                         struct got_object_qid *qid;
 388                         err = got_object_qid_alloc(&qid, id);
 389                         if (err)
 390                                 break;
 391                         STAILQ_INSERT_TAIL(ids, qid, entry);
 392                 } else if (S_ISREG(mode) || S_ISLNK(mode)) {
 393                         err = add_meta(v, idset, id, p, GOT_OBJ_TYPE_BLOB,
 394                             mtime, loose_obj_only, repo);
 395                         if (err)
 396                                 break;
 397                 }
 398                 free(p);
 399                 p = NULL;
 400         }
 401
 402         got_object_tree_close(tree);
 403         free(p);
 404         return err;
 405 }
 406
 407 static const struct got_error *
 408 load_tree(struct got_pack_metavec *v, struct got_object_idset *idset,
 409     struct got_object_id *tree_id, const char *dpath, time_t mtime,
 410     int loose_obj_only, struct got_repository *repo,
 411     got_cancel_cb cancel_cb, void *cancel_arg)
 412 {
 413         const struct got_error *err = NULL;
 414         struct got_object_id_queue tree_ids;
 415         struct got_object_qid *qid;
 416
 417         if (got_object_idset_contains(idset, tree_id))
 418                 return NULL;
 419
 420         err = got_object_qid_alloc(&qid, tree_id);
 421         if (err)
 422                 return err;
 423
 424         STAILQ_INIT(&tree_ids);
 425         STAILQ_INSERT_TAIL(&tree_ids, qid, entry);
 426
 427         while (!STAILQ_EMPTY(&tree_ids)) {
 428                 if (cancel_cb) {
 429                         err = (*cancel_cb)(cancel_arg);
 430                         if (err)
 431                                 break;
 432                 }
 433
 434                 qid = STAILQ_FIRST(&tree_ids);
 435                 STAILQ_REMOVE_HEAD(&tree_ids, entry);
 436
 437                 if (got_object_idset_contains(idset, qid->id)) {
 438                         got_object_qid_free(qid);
 439                         continue;
 440                 }
 441
 442                 err = add_meta(v, idset, qid->id, dpath, GOT_OBJ_TYPE_TREE,
 443                     mtime, loose_obj_only, repo);
 444                 if (err) {
 445                         got_object_qid_free(qid);
 446                         break;
 447                 }
 448
 449                 err = load_tree_entries(&tree_ids, v, idset, qid->id, dpath,
 450                     mtime, repo, loose_obj_only, cancel_cb, cancel_arg);
 451                 got_object_qid_free(qid);
 452                 if (err)
 453                         break;
 454         }
 455
 456         got_object_id_queue_free(&tree_ids);
 457         return err;
 458 }
 459
 460 static const struct got_error *
 461 load_commit(struct got_pack_metavec *v, struct got_object_idset *idset,
 462     struct got_object_id *id, struct got_repository *repo, int loose_obj_only,
 463     got_cancel_cb cancel_cb, void *cancel_arg)
 464 {
 465         const struct got_error *err;
 466         struct got_commit_object *commit;
 467
 468         if (got_object_idset_contains(idset, id))
 469                 return NULL;
 470
 471         if (loose_obj_only) {
 472                 int is_packed;
 473                 err = search_packidx(&is_packed, id, repo);
 474                 if (err)
 475                         return err;
 476                 if (is_packed)
 477                         return NULL;
 478         }
 479
 480         err = got_object_open_as_commit(&commit, repo, id);
 481         if (err)
 482                 return err;
 483
 484         err = add_meta(v, idset, id, "", GOT_OBJ_TYPE_COMMIT,
 485             got_object_commit_get_committer_time(commit),
 486             loose_obj_only, repo);
 487         if (err)
 488                 goto done;
 489
 490         err = load_tree(v, idset, got_object_commit_get_tree_id(commit),
 491             "", got_object_commit_get_committer_time(commit),
 492             loose_obj_only, repo, cancel_cb, cancel_arg);
 493 done:
 494         got_object_commit_close(commit);
 495         return err;
 496 }
 497
 498 static const struct got_error *
 499 load_tag(struct got_pack_metavec *v, struct got_object_idset *idset,
 500     struct got_object_id *id, struct got_repository *repo, int loose_obj_only,
 501     got_cancel_cb cancel_cb, void *cancel_arg)
 502 {
 503         const struct got_error *err;
 504         struct got_tag_object *tag = NULL;
 505
 506         if (got_object_idset_contains(idset, id))
 507                 return NULL;
 508
 509         if (loose_obj_only) {
 510                 int is_packed;
 511                 err = search_packidx(&is_packed, id, repo);
 512                 if (err)
 513                         return err;
 514                 if (is_packed)
 515                         return NULL;
 516         }
 517
 518         err = got_object_open_as_tag(&tag, repo, id);
 519         if (err)
 520                 return err;
 521
 522         err = add_meta(v, idset, id, "", GOT_OBJ_TYPE_TAG,
 523             got_object_tag_get_tagger_time(tag),
 524             loose_obj_only, repo);
 525         if (err)
 526                 goto done;
 527
 528         switch (got_object_tag_get_object_type(tag)) {
 529         case GOT_OBJ_TYPE_COMMIT:
 530                 err = load_commit(v, idset,
 531                     got_object_tag_get_object_id(tag), repo,
 532                     loose_obj_only, cancel_cb, cancel_arg);
 533                 break;
 534         case GOT_OBJ_TYPE_TREE:
 535                 err = load_tree(v, idset, got_object_tag_get_object_id(tag),
 536                     "", got_object_tag_get_tagger_time(tag),
 537                     loose_obj_only, repo, cancel_cb, cancel_arg);
 538                 break;
 539         default:
 540                 break;
 541         }
 542
 543 done:
 544         got_object_tag_close(tag);
 545         return err;
 546 }
 547
 548 enum findtwixt_color {
 549         COLOR_KEEP = 0,
 550         COLOR_DROP,
 551         COLOR_BLANK,
 552 };
 553 static const int findtwixt_colors[] = {
 554         COLOR_KEEP,
 555         COLOR_DROP,
 556         COLOR_BLANK
 557 };
 558
 559 static const struct got_error *
 560 queue_commit_id(struct got_object_id_queue *ids, struct got_object_id *id,
 561     int color, struct got_repository *repo)
 562 {
 563         const struct got_error *err;
 564         struct got_object_qid *qid;
 565
 566         err = got_object_qid_alloc(&qid, id);
 567         if (err)
 568                 return err;
 569
 570         STAILQ_INSERT_TAIL(ids, qid, entry);
 571         qid->data = (void *)&findtwixt_colors[color];
 572         return NULL;
 573 }
 574
 575 static const struct got_error *
 576 drop_commit(struct got_object_idset *keep, struct got_object_idset *drop,
 577     struct got_object_id *id, struct got_repository *repo,
 578     got_cancel_cb cancel_cb, void *cancel_arg)
 579 {
 580         const struct got_error *err = NULL;
 581         struct got_commit_object *commit;
 582         const struct got_object_id_queue *parents;
 583         struct got_object_id_queue ids;
 584         struct got_object_qid *qid;
 585
 586         STAILQ_INIT(&ids);
 587
 588         err = got_object_qid_alloc(&qid, id);
 589         if (err)
 590                 return err;
 591         STAILQ_INSERT_HEAD(&ids, qid, entry);
 592
 593         while (!STAILQ_EMPTY(&ids)) {
 594                 if (cancel_cb) {
 595                         err = (*cancel_cb)(cancel_arg);
 596                         if (err)
 597                                 break;
 598                 }
 599
 600                 qid = STAILQ_FIRST(&ids);
 601                 STAILQ_REMOVE_HEAD(&ids, entry);
 602
 603                 if (got_object_idset_contains(drop, qid->id)) {
 604                         got_object_qid_free(qid);
 605                         continue;
 606                 }
 607
 608                 err = got_object_idset_add(drop, qid->id,
 609                     (void *)&obj_types[GOT_OBJ_TYPE_COMMIT]);
 610                 if (err) {
 611                         got_object_qid_free(qid);
 612                         break;
 613                 }
 614
 615                 if (!got_object_idset_contains(keep, qid->id)) {
 616                         got_object_qid_free(qid);
 617                         continue;
 618                 }
 619
 620                 err = got_object_open_as_commit(&commit, repo, qid->id);
 621                 got_object_qid_free(qid);
 622                 if (err)
 623                         break;
 624
 625                 parents = got_object_commit_get_parent_ids(commit);
 626                 if (parents) {
 627                         err = got_object_id_queue_copy(parents, &ids);
 628                         if (err) {
 629                                 got_object_commit_close(commit);
 630                                 break;
 631                         }
 632                 }
 633                 got_object_commit_close(commit);
 634         }
 635
 636         got_object_id_queue_free(&ids);
 637         return err;
 638 }
 639
 640 struct append_id_arg {
 641         struct got_object_id **array;
 642         int idx;
 643 };
 644
 645 static const struct got_error *
 646 append_id(struct got_object_id *id, void *data, void *arg)
 647 {
 648         struct append_id_arg *a = arg;
 649
 650         a->array[a->idx] = got_object_id_dup(id);
 651         if (a->array[a->idx] == NULL)
 652                 return got_error_from_errno("got_object_id_dup");
 653
 654         a->idx++;
 655         return NULL;
 656 }
 657
 658 static const struct got_error *
 659 findtwixt(struct got_object_id ***res, int *nres,
 660     struct got_object_id **head, int nhead,
 661     struct got_object_id **tail, int ntail,
 662     struct got_repository *repo,
 663     got_cancel_cb cancel_cb, void *cancel_arg)
 664 {
 665         const struct got_error *err = NULL;
 666         struct got_object_id_queue ids;
 667         struct got_object_idset *keep, *drop;
 668         struct got_object_qid *qid;
 669         int i, ncolor, nkeep, obj_type;
 670
 671         STAILQ_INIT(&ids);
 672         *res = NULL;
 673         *nres = 0;
 674
 675         keep = got_object_idset_alloc();
 676         if (keep == NULL)
 677                 return got_error_from_errno("got_object_idset_alloc");
 678
 679         drop = got_object_idset_alloc();
 680         if (drop == NULL) {
 681                 err = got_error_from_errno("got_object_idset_alloc");
 682                 goto done;
 683         }
 684
 685         for (i = 0; i < nhead; i++) {
 686                 struct got_object_id *id = head[i];
 687                 if (id == NULL)
 688                         continue;
 689                 err = got_object_get_type(&obj_type, repo, id);
 690                 if (err)
 691                         return err;
 692                 if (obj_type != GOT_OBJ_TYPE_COMMIT)
 693                         continue;
 694                 err = queue_commit_id(&ids, id, COLOR_KEEP, repo);
 695                 if (err)
 696                         goto done;
 697         }
 698         for (i = 0; i < ntail; i++) {
 699                 struct got_object_id *id = tail[i];
 700                 if (id == NULL)
 701                         continue;
 702                 err = got_object_get_type(&obj_type, repo, id);
 703                 if (err)
 704                         return err;
 705                 if (obj_type != GOT_OBJ_TYPE_COMMIT)
 706                         continue;
 707                 err = queue_commit_id(&ids, id, COLOR_DROP, repo);
 708                 if (err)
 709                         goto done;
 710         }
 711
 712         while (!STAILQ_EMPTY(&ids)) {
 713                 int qcolor;
 714                 qid = STAILQ_FIRST(&ids);
 715                 qcolor = *((int *)qid->data);
 716
 717                 if (got_object_idset_contains(drop, qid->id))
 718                         ncolor = COLOR_DROP;
 719                 else if (got_object_idset_contains(keep, qid->id))
 720                         ncolor = COLOR_KEEP;
 721                 else
 722                         ncolor = COLOR_BLANK;
 723
 724                 if (ncolor == COLOR_DROP || (ncolor == COLOR_KEEP &&
 725                     qcolor == COLOR_KEEP)) {
 726                         STAILQ_REMOVE_HEAD(&ids, entry);
 727                         got_object_qid_free(qid);
 728                         continue;
 729                 }
 730
 731                 if (ncolor == COLOR_KEEP && qcolor == COLOR_DROP) {
 732                         err = drop_commit(keep, drop, qid->id, repo,
 733                             cancel_cb, cancel_arg);
 734                         if (err)
 735                                 goto done;
 736                 } else if (ncolor == COLOR_BLANK) {
 737                         struct got_commit_object *commit;
 738                         struct got_object_id *id;
 739                         const struct got_object_id_queue *parents;
 740                         struct got_object_qid *pid;
 741
 742                         id = got_object_id_dup(qid->id);
 743                         if (id == NULL) {
 744                                 err = got_error_from_errno("got_object_id_dup");
 745                                 goto done;
 746                         }
 747                         if (qcolor == COLOR_KEEP)
 748                                 err = got_object_idset_add(keep, id,
 749                                     (void *)&obj_types[GOT_OBJ_TYPE_COMMIT]);
 750                         else
 751                                 err = got_object_idset_add(drop, id,
 752                                     (void *)&obj_types[GOT_OBJ_TYPE_COMMIT]);
 753                         if (err) {
 754                                 free(id);
 755                                 goto done;
 756                         }
 757
 758                         err = got_object_open_as_commit(&commit, repo, id);
 759                         if (err) {
 760                                 free(id);
 761                                 goto done;
 762                         }
 763                         parents = got_object_commit_get_parent_ids(commit);
 764                         if (parents) {
 765                                 STAILQ_FOREACH(pid, parents, entry) {
 766                                         err = queue_commit_id(&ids, pid->id,
 767                                             qcolor, repo);
 768                                         if (err) {
 769                                                 free(id);
 770                                                 goto done;
 771                                         }
 772                                 }
 773                         }
 774                         got_object_commit_close(commit);
 775                         commit = NULL;
 776                 } else {
 777                         /* should not happen */
 778                         err = got_error_fmt(GOT_ERR_NOT_IMPL,
 779                             "%s ncolor=%d qcolor=%d", __func__, ncolor, qcolor);
 780                         goto done;
 781                 }
 782
 783                 STAILQ_REMOVE_HEAD(&ids, entry);
 784                 got_object_qid_free(qid);
 785         }
 786
 787         nkeep = got_object_idset_num_elements(keep);
 788         if (nkeep > 0) {
 789                 struct append_id_arg arg;
 790                 arg.array = calloc(nkeep, sizeof(struct got_object_id *));
 791                 if (arg.array == NULL) {
 792                         err = got_error_from_errno("calloc");
 793                         goto done;
 794                 }
 795                 arg.idx = 0;
 796                 err = got_object_idset_for_each(keep, append_id, &arg);
 797                 if (err) {
 798                         free(arg.array);
 799                         goto done;
 800                 }
 801                 *res = arg.array;
 802                 *nres = nkeep;
 803         }
 804 done:
 805         got_object_idset_free(keep);
 806         got_object_idset_free(drop);
 807         got_object_id_queue_free(&ids);
 808         return err;
 809 }
 810
 811 static const struct got_error *
 812 read_meta(struct got_pack_meta ***meta, int *nmeta,
 813     struct got_object_id **theirs, int ntheirs,
 814     struct got_object_id **ours, int nours, struct got_repository *repo,
 815     int loose_obj_only, got_pack_progress_cb progress_cb, void *progress_arg,
 816     got_cancel_cb cancel_cb, void *cancel_arg)
 817 {
 818         const struct got_error *err = NULL;
 819         struct got_object_id **ids = NULL;
 820         struct got_object_idset *idset;
 821         int i, nobj = 0, obj_type;
 822         struct got_pack_metavec v;
 823
 824         *meta = NULL;
 825         *nmeta = 0;
 826
 827         idset = got_object_idset_alloc();
 828         if (idset == NULL)
 829                 return got_error_from_errno("got_object_idset_alloc");
 830
 831         v.nmeta = 0;
 832         v.metasz = 64;
 833         v.meta = calloc(v.metasz, sizeof(struct got_pack_meta *));
 834         if (v.meta == NULL) {
 835                 err = got_error_from_errno("calloc");
 836                 goto done;
 837         }
 838
 839         err = findtwixt(&ids, &nobj, ours, nours, theirs, ntheirs, repo,
 840             cancel_cb, cancel_arg);
 841         if (err || nobj == 0)
 842                 goto done;
 843
 844         for (i = 0; i < ntheirs; i++) {
 845                 struct got_object_id *id = theirs[i];
 846                 if (id == NULL)
 847                         continue;
 848                 err = got_object_get_type(&obj_type, repo, id);
 849                 if (err)
 850                         return err;
 851                 if (obj_type != GOT_OBJ_TYPE_COMMIT)
 852                         continue;
 853                 err = load_commit(NULL, idset, id, repo,
 854                     loose_obj_only, cancel_cb, cancel_arg);
 855                 if (err)
 856                         goto done;
 857                 if (progress_cb) {
 858                         err = progress_cb(progress_arg, 0L, nours,
 859                             v.nmeta, 0, 0);
 860                         if (err)
 861                                 goto done;
 862                 }
 863         }
 864
 865         for (i = 0; i < ntheirs; i++) {
 866                 struct got_object_id *id = theirs[i];
 867                 int *cached_type;
 868                 if (id == NULL)
 869                         continue;
 870                 cached_type = got_object_idset_get(idset, id);
 871                 if (cached_type == NULL) {
 872                         err = got_object_get_type(&obj_type, repo, id);
 873                         if (err)
 874                                 goto done;
 875                 } else
 876                         obj_type = *cached_type;
 877                 if (obj_type != GOT_OBJ_TYPE_TAG)
 878                         continue;
 879                 err = load_tag(NULL, idset, id, repo,
 880                     loose_obj_only, cancel_cb, cancel_arg);
 881                 if (err)
 882                         goto done;
 883                 if (progress_cb) {
 884                         err = progress_cb(progress_arg, 0L, nours,
 885                             v.nmeta, 0, 0);
 886                         if (err)
 887                                 goto done;
 888                 }
 889         }
 890
 891         for (i = 0; i < nobj; i++) {
 892                 err = load_commit(&v, idset, ids[i], repo,
 893                     loose_obj_only, cancel_cb, cancel_arg);
 894                 if (err)
 895                         goto done;
 896                 if (progress_cb) {
 897                         err = progress_cb(progress_arg, 0L, nours,
 898                             v.nmeta, 0, 0);
 899                         if (err)
 900                                 goto done;
 901                 }
 902         }
 903
 904         for (i = 0; i < nours; i++) {
 905                 struct got_object_id *id = ours[i];
 906                 int *cached_type;
 907                 if (id == NULL)
 908                         continue;
 909                 cached_type = got_object_idset_get(idset, id);
 910                 if (cached_type == NULL) {
 911                         err = got_object_get_type(&obj_type, repo, id);
 912                         if (err)
 913                                 goto done;
 914                 } else
 915                         obj_type = *cached_type;
 916                 if (obj_type != GOT_OBJ_TYPE_TAG)
 917                         continue;
 918                 err = load_tag(&v, idset, id, repo,
 919                     loose_obj_only, cancel_cb, cancel_arg);
 920                 if (err)
 921                         goto done;
 922                 if (progress_cb) {
 923                         err = progress_cb(progress_arg, 0L, nours,
 924                             v.nmeta, 0, 0);
 925                         if (err)
 926                                 goto done;
 927                 }
 928         }
 929
 930 done:
 931         for (i = 0; i < nobj; i++) {
 932                 free(ids[i]);
 933         }
 934         free(ids);
 935         got_object_idset_free(idset);
 936         if (err == NULL) {
 937                 *meta = v.meta;
 938                 *nmeta = v.nmeta;
 939         } else
 940                 free(v.meta);
 941
 942         return err;
 943 }
 944
 945 const struct got_error *
 946 hwrite(FILE *f, void *buf, int len, SHA1_CTX *ctx)
 947 {
 948         size_t n;
 949
 950         SHA1Update(ctx, buf, len);
 951         n = fwrite(buf, 1, len, f);
 952         if (n != len)
 953                 return got_ferror(f, GOT_ERR_IO);
 954         return NULL;
 955 }
 956
 957 static void
 958 putbe32(char *b, uint32_t n)
 959 {
 960         b[0] = n >> 24;
 961         b[1] = n >> 16;
 962         b[2] = n >> 8;
 963         b[3] = n >> 0;
 964 }
 965
 966 static int
 967 write_order_cmp(const void *pa, const void *pb)
 968 {
 969         struct got_pack_meta *a, *b, *ahd, *bhd;
 970
 971         a = *(struct got_pack_meta **)pa;
 972         b = *(struct got_pack_meta **)pb;
 973         ahd = (a->head == NULL) ? a : a->head;
 974         bhd = (b->head == NULL) ? b : b->head;
 975         if (ahd->mtime != bhd->mtime)
 976                 return bhd->mtime - ahd->mtime;
 977         if (ahd != bhd)
 978                 return (uintptr_t)bhd - (uintptr_t)ahd;
 979         if (a->nchain != b->nchain)
 980                 return a->nchain - b->nchain;
 981         return a->mtime - b->mtime;
 982 }
 983
 984 static const struct got_error *
 985 packhdr(int *hdrlen, char *hdr, size_t bufsize, int obj_type, size_t len)
 986 {
 987         size_t i;
 988
 989         *hdrlen = 0;
 990
 991         hdr[0] = obj_type << 4;
 992         hdr[0] |= len & 0xf;
 993         len >>= 4;
 994         for (i = 1; len != 0; i++){
 995                 if (i >= bufsize)
 996                         return got_error(GOT_ERR_NO_SPACE);
 997                 hdr[i - 1] |= GOT_DELTA_SIZE_MORE;
 998                 hdr[i] = len & GOT_DELTA_SIZE_VAL_MASK;
 999                 len >>= GOT_DELTA_SIZE_SHIFT;
1000         }
1001
1002         *hdrlen = i;
1003         return NULL;
1004 }
1005
1006 static const struct got_error *
1007 encodedelta(struct got_pack_meta *m, struct got_raw_object *o,
1008     off_t base_size, FILE *f)
1009 {
1010         unsigned char buf[16], *bp;
1011         int i, j;
1012         off_t n;
1013         size_t w;
1014         struct got_delta_instruction *d;
1015
1016         /* base object size */
1017         buf[0] = base_size & GOT_DELTA_SIZE_VAL_MASK;
1018         n = base_size >> GOT_DELTA_SIZE_SHIFT;
1019         for (i = 1; n > 0; i++) {
1020                 buf[i - 1] |= GOT_DELTA_SIZE_MORE;
1021                 buf[i] = n & GOT_DELTA_SIZE_VAL_MASK;
1022                 n >>= GOT_DELTA_SIZE_SHIFT;
1023         }
1024         w = fwrite(buf, 1, i, f);
1025         if (w != i)
1026                 return got_ferror(f, GOT_ERR_IO);
1027
1028         /* target object size */
1029         buf[0] = o->size & GOT_DELTA_SIZE_VAL_MASK;
1030         n = o->size >> GOT_DELTA_SIZE_SHIFT;
1031         for (i = 1; n > 0; i++) {
1032                 buf[i - 1] |= GOT_DELTA_SIZE_MORE;
1033                 buf[i] = n & GOT_DELTA_SIZE_VAL_MASK;
1034                 n >>= GOT_DELTA_SIZE_SHIFT;
1035         }
1036         w = fwrite(buf, 1, i, f);
1037         if (w != i)
1038                 return got_ferror(f, GOT_ERR_IO);
1039
1040         for (j = 0; j < m->ndeltas; j++) {
1041                 d = &m->deltas[j];
1042                 if (d->copy) {
1043                         n = d->offset;
1044                         bp = &buf[1];
1045                         buf[0] = GOT_DELTA_BASE_COPY;
1046                         for (i = 0; i < 4; i++) {
1047                                 /* DELTA_COPY_OFF1 ... DELTA_COPY_OFF4 */
1048                                 buf[0] |= 1 << i;
1049                                 *bp++ = n & 0xff;
1050                                 n >>= 8;
1051                                 if (n == 0)
1052                                         break;
1053                         }
1054
1055                         n = d->len;
1056                         if (n != GOT_DELTA_COPY_DEFAULT_LEN) {
1057                                 /* DELTA_COPY_LEN1 ... DELTA_COPY_LEN3 */
1058                                 for (i = 0; i < 3 && n > 0; i++) {
1059                                         buf[0] |= 1 << (i + 4);
1060                                         *bp++ = n & 0xff;
1061                                         n >>= 8;
1062                                 }
1063                         }
1064                         w = fwrite(buf, 1, bp - buf, f);
1065                         if (w != bp - buf)
1066                                 return got_ferror(f, GOT_ERR_IO);
1067                 } else {
1068                         char content[128];
1069                         size_t r;
1070                         if (fseeko(o->f, o->hdrlen + d->offset, SEEK_SET) == -1)
1071                                 return got_error_from_errno("fseeko");
1072                         n = 0;
1073                         while (n != d->len) {
1074                                 buf[0] = (d->len - n < 127) ? d->len - n : 127;
1075                                 w = fwrite(buf, 1, 1, f);
1076                                 if (w != 1)
1077                                         return got_ferror(f, GOT_ERR_IO);
1078                                 r = fread(content, 1, buf[0], o->f);
1079                                 if (r != buf[0])
1080                                         return got_ferror(o->f, GOT_ERR_IO);
1081                                 w = fwrite(content, 1, buf[0], f);
1082                                 if (w != buf[0])
1083                                         return got_ferror(f, GOT_ERR_IO);
1084                                 n += buf[0];
1085                         }
1086                 }
1087         }
1088
1089         return NULL;
1090 }
1091
1092 static int
1093 packoff(char *hdr, off_t off)
1094 {
1095         int i, j;
1096         char rbuf[8];
1097
1098         rbuf[0] = off & GOT_DELTA_SIZE_VAL_MASK;
1099         for (i = 1; (off >>= GOT_DELTA_SIZE_SHIFT) != 0; i++) {
1100                 rbuf[i] = (--off & GOT_DELTA_SIZE_VAL_MASK) |
1101                     GOT_DELTA_SIZE_MORE;
1102         }
1103
1104         j = 0;
1105         while (i > 0)
1106                 hdr[j++] = rbuf[--i];
1107         return j;
1108 }
1109
1110 static const struct got_error *
1111 genpack(uint8_t *pack_sha1, FILE *packfile,
1112     struct got_pack_meta **meta, int nmeta, int nours,
1113     int use_offset_deltas, struct got_repository *repo,
1114     got_pack_progress_cb progress_cb, void *progress_arg,
1115     got_cancel_cb cancel_cb, void *cancel_arg)
1116 {
1117         const struct got_error *err = NULL;
1118         int i, nh;
1119         off_t nd;
1120         SHA1_CTX ctx;
1121         struct got_pack_meta *m;
1122         struct got_raw_object *raw = NULL, *base_raw = NULL;
1123         FILE *delta_file = NULL;
1124         char buf[32];
1125         size_t outlen, n;
1126         struct got_deflate_checksum csum;
1127         off_t packfile_size = 0;
1128
1129         SHA1Init(&ctx);
1130         csum.output_sha1 = &ctx;
1131         csum.output_crc = NULL;
1132
1133         err = hwrite(packfile, "PACK", 4, &ctx);
1134         if (err)
1135                 return err;
1136         putbe32(buf, GOT_PACKFILE_VERSION);
1137         err = hwrite(packfile, buf, 4, &ctx);
1138         if (err)
1139                 goto done;
1140         putbe32(buf, nmeta);
1141         err = hwrite(packfile, buf, 4, &ctx);
1142         if (err)
1143                 goto done;
1144         qsort(meta, nmeta, sizeof(struct got_pack_meta *), write_order_cmp);
1145         for (i = 0; i < nmeta; i++) {
1146                 if (progress_cb) {
1147                         err = progress_cb(progress_arg, packfile_size, nours,
1148                             nmeta, nmeta, i);
1149                         if (err)
1150                                 goto done;
1151                 }
1152                 m = meta[i];
1153                 m->off = ftello(packfile);
1154                 err = got_object_raw_open(&raw, repo, &m->id, 8192);
1155                 if (err)
1156                         goto done;
1157                 if (m->deltas == NULL) {
1158                         err = packhdr(&nh, buf, sizeof(buf),
1159                             m->obj_type, raw->size);
1160                         if (err)
1161                                 goto done;
1162                         err = hwrite(packfile, buf, nh, &ctx);
1163                         if (err)
1164                                 goto done;
1165                         packfile_size += nh;
1166                         if (fseeko(raw->f, raw->hdrlen, SEEK_SET) == -1) {
1167                                 err = got_error_from_errno("fseeko");
1168                                 goto done;
1169                         }
1170                         err = got_deflate_to_file(&outlen, raw->f, packfile,
1171                             &csum);
1172                         if (err)
1173                                 goto done;
1174                         packfile_size += outlen;
1175                 } else {
1176                         if (delta_file == NULL) {
1177                                 delta_file = got_opentemp();
1178                                 if (delta_file == NULL) {
1179                                         err = got_error_from_errno(
1180                                             "got_opentemp");
1181                                         goto done;
1182                                 }
1183                         }
1184                         if (ftruncate(fileno(delta_file), 0L) == -1) {
1185                                 err = got_error_from_errno("ftruncate");
1186                                 goto done;
1187                         }
1188                         if (fseeko(delta_file, 0L, SEEK_SET) == -1) {
1189                                 err = got_error_from_errno("fseeko");
1190                                 goto done;
1191                         }
1192                         err = got_object_raw_open(&base_raw, repo,
1193                             &m->prev->id, 8192);
1194                         if (err)
1195                                 goto done;
1196                         err = encodedelta(m, raw, base_raw->size, delta_file);
1197                         if (err)
1198                                 goto done;
1199                         nd = ftello(delta_file);
1200                         if (fseeko(delta_file, 0L, SEEK_SET) == -1) {
1201                                 err = got_error_from_errno("fseeko");
1202                                 goto done;
1203                         }
1204                         got_object_raw_close(base_raw);
1205                         base_raw = NULL;
1206                         if (use_offset_deltas && m->prev->off != 0) {
1207                                 err = packhdr(&nh, buf, sizeof(buf),
1208                                     GOT_OBJ_TYPE_OFFSET_DELTA, nd);
1209                                 if (err)
1210                                         goto done;
1211                                 nh += packoff(buf + nh,
1212                                     m->off - m->prev->off);
1213                                 err = hwrite(packfile, buf, nh, &ctx);
1214                                 if (err)
1215                                         goto done;
1216                                 packfile_size += nh;
1217                         } else {
1218                                 err = packhdr(&nh, buf, sizeof(buf),
1219                                     GOT_OBJ_TYPE_REF_DELTA, nd);
1220                                 err = hwrite(packfile, buf, nh, &ctx);
1221                                 if (err)
1222                                         goto done;
1223                                 packfile_size += nh;
1224                                 err = hwrite(packfile, m->prev->id.sha1,
1225                                     sizeof(m->prev->id.sha1), &ctx);
1226                                 packfile_size += sizeof(m->prev->id.sha1);
1227                                 if (err)
1228                                         goto done;
1229                         }
1230                         err = got_deflate_to_file(&outlen, delta_file,
1231                             packfile, &csum);
1232                         if (err)
1233                                 goto done;
1234                         packfile_size += outlen;
1235                 }
1236                 got_object_raw_close(raw);
1237                 raw = NULL;
1238         }
1239         SHA1Final(pack_sha1, &ctx);
1240         n = fwrite(pack_sha1, 1, SHA1_DIGEST_LENGTH, packfile);
1241         if (n != SHA1_DIGEST_LENGTH)
1242                 err = got_ferror(packfile, GOT_ERR_IO);
1243         packfile_size += SHA1_DIGEST_LENGTH;
1244         packfile_size += sizeof(struct got_packfile_hdr);
1245         err = progress_cb(progress_arg, packfile_size, nours,
1246             nmeta, nmeta, nmeta);
1247         if (err)
1248                 goto done;
1249 done:
1250         if (delta_file && fclose(delta_file) == EOF && err == NULL)
1251                 err = got_error_from_errno("fclose");
1252         if (raw)
1253                 got_object_raw_close(raw);
1254         if (base_raw)
1255                 got_object_raw_close(base_raw);
1256         return err;
1257 }
1258
1259 const struct got_error *
1260 got_pack_create(uint8_t *packsha1, FILE *packfile,
1261     struct got_object_id **theirs, int ntheirs,
1262     struct got_object_id **ours, int nours,
1263     struct got_repository *repo, int loose_obj_only, int allow_empty,
1264     got_pack_progress_cb progress_cb, void *progress_arg,
1265     got_cancel_cb cancel_cb, void *cancel_arg)
1266 {
1267         const struct got_error *err;
1268         struct got_pack_meta **meta;
1269         int nmeta;
1270
1271         err = read_meta(&meta, &nmeta, theirs, ntheirs, ours, nours, repo,
1272             loose_obj_only, progress_cb, progress_arg, cancel_cb, cancel_arg);
1273         if (err)
1274                 return err;
1275
1276         if (nmeta == 0 && !allow_empty) {
1277                 err = got_error(GOT_ERR_CANNOT_PACK);
1278                 goto done;
1279         }
1280         if (nmeta > 0) {
1281                 err = pick_deltas(meta, nmeta, nours, repo,
1282                     progress_cb, progress_arg, cancel_cb, cancel_arg);
1283                 if (err)
1284                         goto done;
1285         }
1286
1287         err = genpack(packsha1, packfile, meta, nmeta, nours, 1, repo,
1288             progress_cb, progress_arg, cancel_cb, cancel_arg);
1289         if (err)
1290                 goto done;
1291 done:
1292         free_nmeta(meta, nmeta);
1293         return err;
1294 }