git.oblomov.eu Git - git/blob - commit-graph.c

   1 #include "cache.h"
   2 #include "config.h"
   3 #include "dir.h"
   4 #include "git-compat-util.h"
   5 #include "lockfile.h"
   6 #include "pack.h"
   7 #include "packfile.h"
   8 #include "commit.h"
   9 #include "object.h"
  10 #include "revision.h"
  11 #include "sha1-lookup.h"
  12 #include "commit-graph.h"
  13 #include "object-store.h"
  14 #include "alloc.h"
  15
  16 #define GRAPH_SIGNATURE 0x43475048 /* "CGPH" */
  17 #define GRAPH_CHUNKID_OIDFANOUT 0x4f494446 /* "OIDF" */
  18 #define GRAPH_CHUNKID_OIDLOOKUP 0x4f49444c /* "OIDL" */
  19 #define GRAPH_CHUNKID_DATA 0x43444154 /* "CDAT" */
  20 #define GRAPH_CHUNKID_LARGEEDGES 0x45444745 /* "EDGE" */
  21
  22 #define GRAPH_DATA_WIDTH 36
  23
  24 #define GRAPH_VERSION_1 0x1
  25 #define GRAPH_VERSION GRAPH_VERSION_1
  26
  27 #define GRAPH_OID_VERSION_SHA1 1
  28 #define GRAPH_OID_LEN_SHA1 GIT_SHA1_RAWSZ
  29 #define GRAPH_OID_VERSION GRAPH_OID_VERSION_SHA1
  30 #define GRAPH_OID_LEN GRAPH_OID_LEN_SHA1
  31
  32 #define GRAPH_OCTOPUS_EDGES_NEEDED 0x80000000
  33 #define GRAPH_PARENT_MISSING 0x7fffffff
  34 #define GRAPH_EDGE_LAST_MASK 0x7fffffff
  35 #define GRAPH_PARENT_NONE 0x70000000
  36
  37 #define GRAPH_LAST_EDGE 0x80000000
  38
  39 #define GRAPH_HEADER_SIZE 8
  40 #define GRAPH_FANOUT_SIZE (4 * 256)
  41 #define GRAPH_CHUNKLOOKUP_WIDTH 12
  42 #define GRAPH_MIN_SIZE (GRAPH_HEADER_SIZE + 4 * GRAPH_CHUNKLOOKUP_WIDTH \
  43                         + GRAPH_FANOUT_SIZE + GRAPH_OID_LEN)
  44
  45 char *get_commit_graph_filename(const char *obj_dir)
  46 {
  47         return xstrfmt("%s/info/commit-graph", obj_dir);
  48 }
  49
  50 static struct commit_graph *alloc_commit_graph(void)
  51 {
  52         struct commit_graph *g = xcalloc(1, sizeof(*g));
  53         g->graph_fd = -1;
  54
  55         return g;
  56 }
  57
  58 struct commit_graph *load_commit_graph_one(const char *graph_file)
  59 {
  60         void *graph_map;
  61         const unsigned char *data, *chunk_lookup;
  62         size_t graph_size;
  63         struct stat st;
  64         uint32_t i;
  65         struct commit_graph *graph;
  66         int fd = git_open(graph_file);
  67         uint64_t last_chunk_offset;
  68         uint32_t last_chunk_id;
  69         uint32_t graph_signature;
  70         unsigned char graph_version, hash_version;
  71
  72         if (fd < 0)
  73                 return NULL;
  74         if (fstat(fd, &st)) {
  75                 close(fd);
  76                 return NULL;
  77         }
  78         graph_size = xsize_t(st.st_size);
  79
  80         if (graph_size < GRAPH_MIN_SIZE) {
  81                 close(fd);
  82                 die("graph file %s is too small", graph_file);
  83         }
  84         graph_map = xmmap(NULL, graph_size, PROT_READ, MAP_PRIVATE, fd, 0);
  85         data = (const unsigned char *)graph_map;
  86
  87         graph_signature = get_be32(data);
  88         if (graph_signature != GRAPH_SIGNATURE) {
  89                 error("graph signature %X does not match signature %X",
  90                       graph_signature, GRAPH_SIGNATURE);
  91                 goto cleanup_fail;
  92         }
  93
  94         graph_version = *(unsigned char*)(data + 4);
  95         if (graph_version != GRAPH_VERSION) {
  96                 error("graph version %X does not match version %X",
  97                       graph_version, GRAPH_VERSION);
  98                 goto cleanup_fail;
  99         }
 100
 101         hash_version = *(unsigned char*)(data + 5);
 102         if (hash_version != GRAPH_OID_VERSION) {
 103                 error("hash version %X does not match version %X",
 104                       hash_version, GRAPH_OID_VERSION);
 105                 goto cleanup_fail;
 106         }
 107
 108         graph = alloc_commit_graph();
 109
 110         graph->hash_len = GRAPH_OID_LEN;
 111         graph->num_chunks = *(unsigned char*)(data + 6);
 112         graph->graph_fd = fd;
 113         graph->data = graph_map;
 114         graph->data_len = graph_size;
 115
 116         last_chunk_id = 0;
 117         last_chunk_offset = 8;
 118         chunk_lookup = data + 8;
 119         for (i = 0; i < graph->num_chunks; i++) {
 120                 uint32_t chunk_id = get_be32(chunk_lookup + 0);
 121                 uint64_t chunk_offset = get_be64(chunk_lookup + 4);
 122                 int chunk_repeated = 0;
 123
 124                 chunk_lookup += GRAPH_CHUNKLOOKUP_WIDTH;
 125
 126                 if (chunk_offset > graph_size - GIT_MAX_RAWSZ) {
 127                         error("improper chunk offset %08x%08x", (uint32_t)(chunk_offset >> 32),
 128                               (uint32_t)chunk_offset);
 129                         goto cleanup_fail;
 130                 }
 131
 132                 switch (chunk_id) {
 133                 case GRAPH_CHUNKID_OIDFANOUT:
 134                         if (graph->chunk_oid_fanout)
 135                                 chunk_repeated = 1;
 136                         else
 137                                 graph->chunk_oid_fanout = (uint32_t*)(data + chunk_offset);
 138                         break;
 139
 140                 case GRAPH_CHUNKID_OIDLOOKUP:
 141                         if (graph->chunk_oid_lookup)
 142                                 chunk_repeated = 1;
 143                         else
 144                                 graph->chunk_oid_lookup = data + chunk_offset;
 145                         break;
 146
 147                 case GRAPH_CHUNKID_DATA:
 148                         if (graph->chunk_commit_data)
 149                                 chunk_repeated = 1;
 150                         else
 151                                 graph->chunk_commit_data = data + chunk_offset;
 152                         break;
 153
 154                 case GRAPH_CHUNKID_LARGEEDGES:
 155                         if (graph->chunk_large_edges)
 156                                 chunk_repeated = 1;
 157                         else
 158                                 graph->chunk_large_edges = data + chunk_offset;
 159                         break;
 160                 }
 161
 162                 if (chunk_repeated) {
 163                         error("chunk id %08x appears multiple times", chunk_id);
 164                         goto cleanup_fail;
 165                 }
 166
 167                 if (last_chunk_id == GRAPH_CHUNKID_OIDLOOKUP)
 168                 {
 169                         graph->num_commits = (chunk_offset - last_chunk_offset)
 170                                              / graph->hash_len;
 171                 }
 172
 173                 last_chunk_id = chunk_id;
 174                 last_chunk_offset = chunk_offset;
 175         }
 176
 177         return graph;
 178
 179 cleanup_fail:
 180         munmap(graph_map, graph_size);
 181         close(fd);
 182         exit(1);
 183 }
 184
 185 /* global storage */
 186 static struct commit_graph *commit_graph = NULL;
 187
 188 static void prepare_commit_graph_one(const char *obj_dir)
 189 {
 190         char *graph_name;
 191
 192         if (commit_graph)
 193                 return;
 194
 195         graph_name = get_commit_graph_filename(obj_dir);
 196         commit_graph = load_commit_graph_one(graph_name);
 197
 198         FREE_AND_NULL(graph_name);
 199 }
 200
 201 static int prepare_commit_graph_run_once = 0;
 202 static void prepare_commit_graph(void)
 203 {
 204         struct alternate_object_database *alt;
 205         char *obj_dir;
 206
 207         if (prepare_commit_graph_run_once)
 208                 return;
 209         prepare_commit_graph_run_once = 1;
 210
 211         obj_dir = get_object_directory();
 212         prepare_commit_graph_one(obj_dir);
 213         prepare_alt_odb(the_repository);
 214         for (alt = the_repository->objects->alt_odb_list;
 215              !commit_graph && alt;
 216              alt = alt->next)
 217                 prepare_commit_graph_one(alt->path);
 218 }
 219
 220 static void close_commit_graph(void)
 221 {
 222         if (!commit_graph)
 223                 return;
 224
 225         if (commit_graph->graph_fd >= 0) {
 226                 munmap((void *)commit_graph->data, commit_graph->data_len);
 227                 commit_graph->data = NULL;
 228                 close(commit_graph->graph_fd);
 229         }
 230
 231         FREE_AND_NULL(commit_graph);
 232 }
 233
 234 static int bsearch_graph(struct commit_graph *g, struct object_id *oid, uint32_t *pos)
 235 {
 236         return bsearch_hash(oid->hash, g->chunk_oid_fanout,
 237                             g->chunk_oid_lookup, g->hash_len, pos);
 238 }
 239
 240 static struct commit_list **insert_parent_or_die(struct commit_graph *g,
 241                                                  uint64_t pos,
 242                                                  struct commit_list **pptr)
 243 {
 244         struct commit *c;
 245         struct object_id oid;
 246
 247         hashcpy(oid.hash, g->chunk_oid_lookup + g->hash_len * pos);
 248         c = lookup_commit(&oid);
 249         if (!c)
 250                 die("could not find commit %s", oid_to_hex(&oid));
 251         c->graph_pos = pos;
 252         return &commit_list_insert(c, pptr)->next;
 253 }
 254
 255 static void fill_commit_graph_info(struct commit *item, struct commit_graph *g, uint32_t pos)
 256 {
 257         const unsigned char *commit_data = g->chunk_commit_data + GRAPH_DATA_WIDTH * pos;
 258         item->graph_pos = pos;
 259         item->generation = get_be32(commit_data + g->hash_len + 8) >> 2;
 260 }
 261
 262 static int fill_commit_in_graph(struct commit *item, struct commit_graph *g, uint32_t pos)
 263 {
 264         uint32_t edge_value;
 265         uint32_t *parent_data_ptr;
 266         uint64_t date_low, date_high;
 267         struct commit_list **pptr;
 268         const unsigned char *commit_data = g->chunk_commit_data + (g->hash_len + 16) * pos;
 269
 270         item->object.parsed = 1;
 271         item->graph_pos = pos;
 272
 273         item->maybe_tree = NULL;
 274
 275         date_high = get_be32(commit_data + g->hash_len + 8) & 0x3;
 276         date_low = get_be32(commit_data + g->hash_len + 12);
 277         item->date = (timestamp_t)((date_high << 32) | date_low);
 278
 279         item->generation = get_be32(commit_data + g->hash_len + 8) >> 2;
 280
 281         pptr = &item->parents;
 282
 283         edge_value = get_be32(commit_data + g->hash_len);
 284         if (edge_value == GRAPH_PARENT_NONE)
 285                 return 1;
 286         pptr = insert_parent_or_die(g, edge_value, pptr);
 287
 288         edge_value = get_be32(commit_data + g->hash_len + 4);
 289         if (edge_value == GRAPH_PARENT_NONE)
 290                 return 1;
 291         if (!(edge_value & GRAPH_OCTOPUS_EDGES_NEEDED)) {
 292                 pptr = insert_parent_or_die(g, edge_value, pptr);
 293                 return 1;
 294         }
 295
 296         parent_data_ptr = (uint32_t*)(g->chunk_large_edges +
 297                           4 * (uint64_t)(edge_value & GRAPH_EDGE_LAST_MASK));
 298         do {
 299                 edge_value = get_be32(parent_data_ptr);
 300                 pptr = insert_parent_or_die(g,
 301                                             edge_value & GRAPH_EDGE_LAST_MASK,
 302                                             pptr);
 303                 parent_data_ptr++;
 304         } while (!(edge_value & GRAPH_LAST_EDGE));
 305
 306         return 1;
 307 }
 308
 309 static int find_commit_in_graph(struct commit *item, struct commit_graph *g, uint32_t *pos)
 310 {
 311         if (item->graph_pos != COMMIT_NOT_FROM_GRAPH) {
 312                 *pos = item->graph_pos;
 313                 return 1;
 314         } else {
 315                 return bsearch_graph(g, &(item->object.oid), pos);
 316         }
 317 }
 318
 319 static int parse_commit_in_graph_one(struct commit_graph *g, struct commit *item)
 320 {
 321         uint32_t pos;
 322
 323         if (!core_commit_graph)
 324                 return 0;
 325         if (item->object.parsed)
 326                 return 1;
 327
 328         if (find_commit_in_graph(item, g, &pos))
 329                 return fill_commit_in_graph(item, g, pos);
 330
 331         return 0;
 332 }
 333
 334 int parse_commit_in_graph(struct commit *item)
 335 {
 336         if (!core_commit_graph)
 337                 return 0;
 338
 339         prepare_commit_graph();
 340         if (commit_graph)
 341                 return parse_commit_in_graph_one(commit_graph, item);
 342         return 0;
 343 }
 344
 345 void load_commit_graph_info(struct commit *item)
 346 {
 347         uint32_t pos;
 348         if (!core_commit_graph)
 349                 return;
 350         prepare_commit_graph();
 351         if (commit_graph && find_commit_in_graph(item, commit_graph, &pos))
 352                 fill_commit_graph_info(item, commit_graph, pos);
 353 }
 354
 355 static struct tree *load_tree_for_commit(struct commit_graph *g, struct commit *c)
 356 {
 357         struct object_id oid;
 358         const unsigned char *commit_data = g->chunk_commit_data +
 359                                            GRAPH_DATA_WIDTH * (c->graph_pos);
 360
 361         hashcpy(oid.hash, commit_data);
 362         c->maybe_tree = lookup_tree(&oid);
 363
 364         return c->maybe_tree;
 365 }
 366
 367 static struct tree *get_commit_tree_in_graph_one(struct commit_graph *g,
 368                                                  const struct commit *c)
 369 {
 370         if (c->maybe_tree)
 371                 return c->maybe_tree;
 372         if (c->graph_pos == COMMIT_NOT_FROM_GRAPH)
 373                 BUG("get_commit_tree_in_graph_one called from non-commit-graph commit");
 374
 375         return load_tree_for_commit(g, (struct commit *)c);
 376 }
 377
 378 struct tree *get_commit_tree_in_graph(const struct commit *c)
 379 {
 380         return get_commit_tree_in_graph_one(commit_graph, c);
 381 }
 382
 383 static void write_graph_chunk_fanout(struct hashfile *f,
 384                                      struct commit **commits,
 385                                      int nr_commits)
 386 {
 387         int i, count = 0;
 388         struct commit **list = commits;
 389
 390         /*
 391          * Write the first-level table (the list is sorted,
 392          * but we use a 256-entry lookup to be able to avoid
 393          * having to do eight extra binary search iterations).
 394          */
 395         for (i = 0; i < 256; i++) {
 396                 while (count < nr_commits) {
 397                         if ((*list)->object.oid.hash[0] != i)
 398                                 break;
 399                         count++;
 400                         list++;
 401                 }
 402
 403                 hashwrite_be32(f, count);
 404         }
 405 }
 406
 407 static void write_graph_chunk_oids(struct hashfile *f, int hash_len,
 408                                    struct commit **commits, int nr_commits)
 409 {
 410         struct commit **list = commits;
 411         int count;
 412         for (count = 0; count < nr_commits; count++, list++)
 413                 hashwrite(f, (*list)->object.oid.hash, (int)hash_len);
 414 }
 415
 416 static const unsigned char *commit_to_sha1(size_t index, void *table)
 417 {
 418         struct commit **commits = table;
 419         return commits[index]->object.oid.hash;
 420 }
 421
 422 static void write_graph_chunk_data(struct hashfile *f, int hash_len,
 423                                    struct commit **commits, int nr_commits)
 424 {
 425         struct commit **list = commits;
 426         struct commit **last = commits + nr_commits;
 427         uint32_t num_extra_edges = 0;
 428
 429         while (list < last) {
 430                 struct commit_list *parent;
 431                 int edge_value;
 432                 uint32_t packedDate[2];
 433
 434                 parse_commit(*list);
 435                 hashwrite(f, get_commit_tree_oid(*list)->hash, hash_len);
 436
 437                 parent = (*list)->parents;
 438
 439                 if (!parent)
 440                         edge_value = GRAPH_PARENT_NONE;
 441                 else {
 442                         edge_value = sha1_pos(parent->item->object.oid.hash,
 443                                               commits,
 444                                               nr_commits,
 445                                               commit_to_sha1);
 446
 447                         if (edge_value < 0)
 448                                 edge_value = GRAPH_PARENT_MISSING;
 449                 }
 450
 451                 hashwrite_be32(f, edge_value);
 452
 453                 if (parent)
 454                         parent = parent->next;
 455
 456                 if (!parent)
 457                         edge_value = GRAPH_PARENT_NONE;
 458                 else if (parent->next)
 459                         edge_value = GRAPH_OCTOPUS_EDGES_NEEDED | num_extra_edges;
 460                 else {
 461                         edge_value = sha1_pos(parent->item->object.oid.hash,
 462                                               commits,
 463                                               nr_commits,
 464                                               commit_to_sha1);
 465                         if (edge_value < 0)
 466                                 edge_value = GRAPH_PARENT_MISSING;
 467                 }
 468
 469                 hashwrite_be32(f, edge_value);
 470
 471                 if (edge_value & GRAPH_OCTOPUS_EDGES_NEEDED) {
 472                         do {
 473                                 num_extra_edges++;
 474                                 parent = parent->next;
 475                         } while (parent);
 476                 }
 477
 478                 if (sizeof((*list)->date) > 4)
 479                         packedDate[0] = htonl(((*list)->date >> 32) & 0x3);
 480                 else
 481                         packedDate[0] = 0;
 482
 483                 packedDate[0] |= htonl((*list)->generation << 2);
 484
 485                 packedDate[1] = htonl((*list)->date);
 486                 hashwrite(f, packedDate, 8);
 487
 488                 list++;
 489         }
 490 }
 491
 492 static void write_graph_chunk_large_edges(struct hashfile *f,
 493                                           struct commit **commits,
 494                                           int nr_commits)
 495 {
 496         struct commit **list = commits;
 497         struct commit **last = commits + nr_commits;
 498         struct commit_list *parent;
 499
 500         while (list < last) {
 501                 int num_parents = 0;
 502                 for (parent = (*list)->parents; num_parents < 3 && parent;
 503                      parent = parent->next)
 504                         num_parents++;
 505
 506                 if (num_parents <= 2) {
 507                         list++;
 508                         continue;
 509                 }
 510
 511                 /* Since num_parents > 2, this initializer is safe. */
 512                 for (parent = (*list)->parents->next; parent; parent = parent->next) {
 513                         int edge_value = sha1_pos(parent->item->object.oid.hash,
 514                                                   commits,
 515                                                   nr_commits,
 516                                                   commit_to_sha1);
 517
 518                         if (edge_value < 0)
 519                                 edge_value = GRAPH_PARENT_MISSING;
 520                         else if (!parent->next)
 521                                 edge_value |= GRAPH_LAST_EDGE;
 522
 523                         hashwrite_be32(f, edge_value);
 524                 }
 525
 526                 list++;
 527         }
 528 }
 529
 530 static int commit_compare(const void *_a, const void *_b)
 531 {
 532         const struct object_id *a = (const struct object_id *)_a;
 533         const struct object_id *b = (const struct object_id *)_b;
 534         return oidcmp(a, b);
 535 }
 536
 537 struct packed_commit_list {
 538         struct commit **list;
 539         int nr;
 540         int alloc;
 541 };
 542
 543 struct packed_oid_list {
 544         struct object_id *list;
 545         int nr;
 546         int alloc;
 547 };
 548
 549 static int add_packed_commits(const struct object_id *oid,
 550                               struct packed_git *pack,
 551                               uint32_t pos,
 552                               void *data)
 553 {
 554         struct packed_oid_list *list = (struct packed_oid_list*)data;
 555         enum object_type type;
 556         off_t offset = nth_packed_object_offset(pack, pos);
 557         struct object_info oi = OBJECT_INFO_INIT;
 558
 559         oi.typep = &type;
 560         if (packed_object_info(the_repository, pack, offset, &oi) < 0)
 561                 die("unable to get type of object %s", oid_to_hex(oid));
 562
 563         if (type != OBJ_COMMIT)
 564                 return 0;
 565
 566         ALLOC_GROW(list->list, list->nr + 1, list->alloc);
 567         oidcpy(&(list->list[list->nr]), oid);
 568         list->nr++;
 569
 570         return 0;
 571 }
 572
 573 static void add_missing_parents(struct packed_oid_list *oids, struct commit *commit)
 574 {
 575         struct commit_list *parent;
 576         for (parent = commit->parents; parent; parent = parent->next) {
 577                 if (!(parent->item->object.flags & UNINTERESTING)) {
 578                         ALLOC_GROW(oids->list, oids->nr + 1, oids->alloc);
 579                         oidcpy(&oids->list[oids->nr], &(parent->item->object.oid));
 580                         oids->nr++;
 581                         parent->item->object.flags |= UNINTERESTING;
 582                 }
 583         }
 584 }
 585
 586 static void close_reachable(struct packed_oid_list *oids)
 587 {
 588         int i;
 589         struct commit *commit;
 590
 591         for (i = 0; i < oids->nr; i++) {
 592                 commit = lookup_commit(&oids->list[i]);
 593                 if (commit)
 594                         commit->object.flags |= UNINTERESTING;
 595         }
 596
 597         /*
 598          * As this loop runs, oids->nr may grow, but not more
 599          * than the number of missing commits in the reachable
 600          * closure.
 601          */
 602         for (i = 0; i < oids->nr; i++) {
 603                 commit = lookup_commit(&oids->list[i]);
 604
 605                 if (commit && !parse_commit(commit))
 606                         add_missing_parents(oids, commit);
 607         }
 608
 609         for (i = 0; i < oids->nr; i++) {
 610                 commit = lookup_commit(&oids->list[i]);
 611
 612                 if (commit)
 613                         commit->object.flags &= ~UNINTERESTING;
 614         }
 615 }
 616
 617 static void compute_generation_numbers(struct packed_commit_list* commits)
 618 {
 619         int i;
 620         struct commit_list *list = NULL;
 621
 622         for (i = 0; i < commits->nr; i++) {
 623                 if (commits->list[i]->generation != GENERATION_NUMBER_INFINITY &&
 624                     commits->list[i]->generation != GENERATION_NUMBER_ZERO)
 625                         continue;
 626
 627                 commit_list_insert(commits->list[i], &list);
 628                 while (list) {
 629                         struct commit *current = list->item;
 630                         struct commit_list *parent;
 631                         int all_parents_computed = 1;
 632                         uint32_t max_generation = 0;
 633
 634                         for (parent = current->parents; parent; parent = parent->next) {
 635                                 if (parent->item->generation == GENERATION_NUMBER_INFINITY ||
 636                                     parent->item->generation == GENERATION_NUMBER_ZERO) {
 637                                         all_parents_computed = 0;
 638                                         commit_list_insert(parent->item, &list);
 639                                         break;
 640                                 } else if (parent->item->generation > max_generation) {
 641                                         max_generation = parent->item->generation;
 642                                 }
 643                         }
 644
 645                         if (all_parents_computed) {
 646                                 current->generation = max_generation + 1;
 647                                 pop_commit(&list);
 648
 649                                 if (current->generation > GENERATION_NUMBER_MAX)
 650                                         current->generation = GENERATION_NUMBER_MAX;
 651                         }
 652                 }
 653         }
 654 }
 655
 656 void write_commit_graph(const char *obj_dir,
 657                         const char **pack_indexes,
 658                         int nr_packs,
 659                         const char **commit_hex,
 660                         int nr_commits,
 661                         int append)
 662 {
 663         struct packed_oid_list oids;
 664         struct packed_commit_list commits;
 665         struct hashfile *f;
 666         uint32_t i, count_distinct = 0;
 667         char *graph_name;
 668         struct lock_file lk = LOCK_INIT;
 669         uint32_t chunk_ids[5];
 670         uint64_t chunk_offsets[5];
 671         int num_chunks;
 672         int num_extra_edges;
 673         struct commit_list *parent;
 674
 675         oids.nr = 0;
 676         oids.alloc = approximate_object_count() / 4;
 677
 678         if (append) {
 679                 prepare_commit_graph_one(obj_dir);
 680                 if (commit_graph)
 681                         oids.alloc += commit_graph->num_commits;
 682         }
 683
 684         if (oids.alloc < 1024)
 685                 oids.alloc = 1024;
 686         ALLOC_ARRAY(oids.list, oids.alloc);
 687
 688         if (append && commit_graph) {
 689                 for (i = 0; i < commit_graph->num_commits; i++) {
 690                         const unsigned char *hash = commit_graph->chunk_oid_lookup +
 691                                 commit_graph->hash_len * i;
 692                         hashcpy(oids.list[oids.nr++].hash, hash);
 693                 }
 694         }
 695
 696         if (pack_indexes) {
 697                 struct strbuf packname = STRBUF_INIT;
 698                 int dirlen;
 699                 strbuf_addf(&packname, "%s/pack/", obj_dir);
 700                 dirlen = packname.len;
 701                 for (i = 0; i < nr_packs; i++) {
 702                         struct packed_git *p;
 703                         strbuf_setlen(&packname, dirlen);
 704                         strbuf_addstr(&packname, pack_indexes[i]);
 705                         p = add_packed_git(packname.buf, packname.len, 1);
 706                         if (!p)
 707                                 die("error adding pack %s", packname.buf);
 708                         if (open_pack_index(p))
 709                                 die("error opening index for %s", packname.buf);
 710                         for_each_object_in_pack(p, add_packed_commits, &oids);
 711                         close_pack(p);
 712                 }
 713                 strbuf_release(&packname);
 714         }
 715
 716         if (commit_hex) {
 717                 for (i = 0; i < nr_commits; i++) {
 718                         const char *end;
 719                         struct object_id oid;
 720                         struct commit *result;
 721
 722                         if (commit_hex[i] && parse_oid_hex(commit_hex[i], &oid, &end))
 723                                 continue;
 724
 725                         result = lookup_commit_reference_gently(&oid, 1);
 726
 727                         if (result) {
 728                                 ALLOC_GROW(oids.list, oids.nr + 1, oids.alloc);
 729                                 oidcpy(&oids.list[oids.nr], &(result->object.oid));
 730                                 oids.nr++;
 731                         }
 732                 }
 733         }
 734
 735         if (!pack_indexes && !commit_hex)
 736                 for_each_packed_object(add_packed_commits, &oids, 0);
 737
 738         close_reachable(&oids);
 739
 740         QSORT(oids.list, oids.nr, commit_compare);
 741
 742         count_distinct = 1;
 743         for (i = 1; i < oids.nr; i++) {
 744                 if (oidcmp(&oids.list[i-1], &oids.list[i]))
 745                         count_distinct++;
 746         }
 747
 748         if (count_distinct >= GRAPH_PARENT_MISSING)
 749                 die(_("the commit graph format cannot write %d commits"), count_distinct);
 750
 751         commits.nr = 0;
 752         commits.alloc = count_distinct;
 753         ALLOC_ARRAY(commits.list, commits.alloc);
 754
 755         num_extra_edges = 0;
 756         for (i = 0; i < oids.nr; i++) {
 757                 int num_parents = 0;
 758                 if (i > 0 && !oidcmp(&oids.list[i-1], &oids.list[i]))
 759                         continue;
 760
 761                 commits.list[commits.nr] = lookup_commit(&oids.list[i]);
 762                 parse_commit(commits.list[commits.nr]);
 763
 764                 for (parent = commits.list[commits.nr]->parents;
 765                      parent; parent = parent->next)
 766                         num_parents++;
 767
 768                 if (num_parents > 2)
 769                         num_extra_edges += num_parents - 1;
 770
 771                 commits.nr++;
 772         }
 773         num_chunks = num_extra_edges ? 4 : 3;
 774
 775         if (commits.nr >= GRAPH_PARENT_MISSING)
 776                 die(_("too many commits to write graph"));
 777
 778         compute_generation_numbers(&commits);
 779
 780         graph_name = get_commit_graph_filename(obj_dir);
 781         if (safe_create_leading_directories(graph_name))
 782                 die_errno(_("unable to create leading directories of %s"),
 783                           graph_name);
 784
 785         hold_lock_file_for_update(&lk, graph_name, LOCK_DIE_ON_ERROR);
 786         f = hashfd(lk.tempfile->fd, lk.tempfile->filename.buf);
 787
 788         hashwrite_be32(f, GRAPH_SIGNATURE);
 789
 790         hashwrite_u8(f, GRAPH_VERSION);
 791         hashwrite_u8(f, GRAPH_OID_VERSION);
 792         hashwrite_u8(f, num_chunks);
 793         hashwrite_u8(f, 0); /* unused padding byte */
 794
 795         chunk_ids[0] = GRAPH_CHUNKID_OIDFANOUT;
 796         chunk_ids[1] = GRAPH_CHUNKID_OIDLOOKUP;
 797         chunk_ids[2] = GRAPH_CHUNKID_DATA;
 798         if (num_extra_edges)
 799                 chunk_ids[3] = GRAPH_CHUNKID_LARGEEDGES;
 800         else
 801                 chunk_ids[3] = 0;
 802         chunk_ids[4] = 0;
 803
 804         chunk_offsets[0] = 8 + (num_chunks + 1) * GRAPH_CHUNKLOOKUP_WIDTH;
 805         chunk_offsets[1] = chunk_offsets[0] + GRAPH_FANOUT_SIZE;
 806         chunk_offsets[2] = chunk_offsets[1] + GRAPH_OID_LEN * commits.nr;
 807         chunk_offsets[3] = chunk_offsets[2] + (GRAPH_OID_LEN + 16) * commits.nr;
 808         chunk_offsets[4] = chunk_offsets[3] + 4 * num_extra_edges;
 809
 810         for (i = 0; i <= num_chunks; i++) {
 811                 uint32_t chunk_write[3];
 812
 813                 chunk_write[0] = htonl(chunk_ids[i]);
 814                 chunk_write[1] = htonl(chunk_offsets[i] >> 32);
 815                 chunk_write[2] = htonl(chunk_offsets[i] & 0xffffffff);
 816                 hashwrite(f, chunk_write, 12);
 817         }
 818
 819         write_graph_chunk_fanout(f, commits.list, commits.nr);
 820         write_graph_chunk_oids(f, GRAPH_OID_LEN, commits.list, commits.nr);
 821         write_graph_chunk_data(f, GRAPH_OID_LEN, commits.list, commits.nr);
 822         write_graph_chunk_large_edges(f, commits.list, commits.nr);
 823
 824         close_commit_graph();
 825         finalize_hashfile(f, NULL, CSUM_HASH_IN_STREAM | CSUM_FSYNC);
 826         commit_lock_file(&lk);
 827
 828         free(oids.list);
 829         oids.alloc = 0;
 830         oids.nr = 0;
 831 }
 832
 833 static int verify_commit_graph_error;
 834
 835 static void graph_report(const char *fmt, ...)
 836 {
 837         va_list ap;
 838
 839         verify_commit_graph_error = 1;
 840         va_start(ap, fmt);
 841         vfprintf(stderr, fmt, ap);
 842         fprintf(stderr, "\n");
 843         va_end(ap);
 844 }
 845
 846 int verify_commit_graph(struct repository *r, struct commit_graph *g)
 847 {
 848         uint32_t i, cur_fanout_pos = 0;
 849         struct object_id prev_oid, cur_oid;
 850
 851         if (!g) {
 852                 graph_report("no commit-graph file loaded");
 853                 return 1;
 854         }
 855
 856         verify_commit_graph_error = 0;
 857
 858         if (!g->chunk_oid_fanout)
 859                 graph_report("commit-graph is missing the OID Fanout chunk");
 860         if (!g->chunk_oid_lookup)
 861                 graph_report("commit-graph is missing the OID Lookup chunk");
 862         if (!g->chunk_commit_data)
 863                 graph_report("commit-graph is missing the Commit Data chunk");
 864
 865         if (verify_commit_graph_error)
 866                 return verify_commit_graph_error;
 867
 868         for (i = 0; i < g->num_commits; i++) {
 869                 struct commit *graph_commit;
 870
 871                 hashcpy(cur_oid.hash, g->chunk_oid_lookup + g->hash_len * i);
 872
 873                 if (i && oidcmp(&prev_oid, &cur_oid) >= 0)
 874                         graph_report("commit-graph has incorrect OID order: %s then %s",
 875                                      oid_to_hex(&prev_oid),
 876                                      oid_to_hex(&cur_oid));
 877
 878                 oidcpy(&prev_oid, &cur_oid);
 879
 880                 while (cur_oid.hash[0] > cur_fanout_pos) {
 881                         uint32_t fanout_value = get_be32(g->chunk_oid_fanout + cur_fanout_pos);
 882
 883                         if (i != fanout_value)
 884                                 graph_report("commit-graph has incorrect fanout value: fanout[%d] = %u != %u",
 885                                              cur_fanout_pos, fanout_value, i);
 886                         cur_fanout_pos++;
 887                 }
 888
 889                 graph_commit = lookup_commit(&cur_oid);
 890                 if (!parse_commit_in_graph_one(g, graph_commit))
 891                         graph_report("failed to parse %s from commit-graph",
 892                                      oid_to_hex(&cur_oid));
 893         }
 894
 895         while (cur_fanout_pos < 256) {
 896                 uint32_t fanout_value = get_be32(g->chunk_oid_fanout + cur_fanout_pos);
 897
 898                 if (g->num_commits != fanout_value)
 899                         graph_report("commit-graph has incorrect fanout value: fanout[%d] = %u != %u",
 900                                      cur_fanout_pos, fanout_value, i);
 901
 902                 cur_fanout_pos++;
 903         }
 904
 905         if (verify_commit_graph_error)
 906                 return verify_commit_graph_error;
 907
 908         for (i = 0; i < g->num_commits; i++) {
 909                 struct commit *graph_commit, *odb_commit;
 910
 911                 hashcpy(cur_oid.hash, g->chunk_oid_lookup + g->hash_len * i);
 912
 913                 graph_commit = lookup_commit(&cur_oid);
 914                 odb_commit = (struct commit *)create_object(r, cur_oid.hash, alloc_commit_node(r));
 915                 if (parse_commit_internal(odb_commit, 0, 0)) {
 916                         graph_report("failed to parse %s from object database",
 917                                      oid_to_hex(&cur_oid));
 918                         continue;
 919                 }
 920
 921                 if (oidcmp(&get_commit_tree_in_graph_one(g, graph_commit)->object.oid,
 922                            get_commit_tree_oid(odb_commit)))
 923                         graph_report("root tree OID for commit %s in commit-graph is %s != %s",
 924                                      oid_to_hex(&cur_oid),
 925                                      oid_to_hex(get_commit_tree_oid(graph_commit)),
 926                                      oid_to_hex(get_commit_tree_oid(odb_commit)));
 927         }
 928
 929         return verify_commit_graph_error;
 930 }