a3073c5f0334baaec59c5c4a6650bbdb4e3de1fb
   1/*
   2Format of STDIN stream:
   3
   4  stream ::= cmd*;
   5
   6  cmd ::= new_blob
   7        | new_commit
   8        | new_tag
   9        | reset_branch
  10        ;
  11
  12  new_blob ::= 'blob' lf
  13        mark?
  14    file_content;
  15  file_content ::= data;
  16
  17  new_commit ::= 'commit' sp ref_str lf
  18    mark?
  19    ('author' sp name '<' email '>' ts tz lf)?
  20    'committer' sp name '<' email '>' ts tz lf
  21    commit_msg
  22    ('from' sp (ref_str | hexsha1 | sha1exp_str | idnum) lf)?
  23    ('merge' sp (ref_str | hexsha1 | sha1exp_str | idnum) lf)*
  24    file_change*
  25    lf;
  26  commit_msg ::= data;
  27
  28  file_change ::= 'M' sp mode sp (hexsha1 | idnum) sp path_str lf
  29                | 'D' sp path_str lf
  30                ;
  31  mode ::= '644' | '755';
  32
  33  new_tag ::= 'tag' sp tag_str lf
  34    'from' sp (ref_str | hexsha1 | sha1exp_str | idnum) lf
  35        'tagger' sp name '<' email '>' ts tz lf
  36    tag_msg;
  37  tag_msg ::= data;
  38
  39  reset_branch ::= 'reset' sp ref_str lf
  40    ('from' sp (ref_str | hexsha1 | sha1exp_str | idnum) lf)?
  41    lf;
  42
  43  checkpoint ::= 'checkpoint' lf
  44    lf;
  45
  46     # note: the first idnum in a stream should be 1 and subsequent
  47     # idnums should not have gaps between values as this will cause
  48     # the stream parser to reserve space for the gapped values.  An
  49         # idnum can be updated in the future to a new object by issuing
  50     # a new mark directive with the old idnum.
  51         #
  52  mark ::= 'mark' sp idnum lf;
  53
  54     # note: declen indicates the length of binary_data in bytes.
  55     # declen does not include the lf preceeding or trailing the
  56     # binary data.
  57     #
  58  data ::= 'data' sp declen lf
  59    binary_data
  60        lf;
  61
  62     # note: quoted strings are C-style quoting supporting \c for
  63     # common escapes of 'c' (e..g \n, \t, \\, \") or \nnn where nnn
  64         # is the signed byte value in octal.  Note that the only
  65     # characters which must actually be escaped to protect the
  66     # stream formatting is: \, " and LF.  Otherwise these values
  67         # are UTF8.
  68     #
  69  ref_str     ::= ref     | '"' quoted(ref)     '"' ;
  70  sha1exp_str ::= sha1exp | '"' quoted(sha1exp) '"' ;
  71  tag_str     ::= tag     | '"' quoted(tag)     '"' ;
  72  path_str    ::= path    | '"' quoted(path)    '"' ;
  73
  74  declen ::= # unsigned 32 bit value, ascii base10 notation;
  75  bigint ::= # unsigned integer value, ascii base10 notation;
  76  binary_data ::= # file content, not interpreted;
  77
  78  sp ::= # ASCII space character;
  79  lf ::= # ASCII newline (LF) character;
  80
  81     # note: a colon (':') must precede the numerical value assigned to
  82         # an idnum.  This is to distinguish it from a ref or tag name as
  83     # GIT does not permit ':' in ref or tag strings.
  84         #
  85  idnum   ::= ':' bigint;
  86  path    ::= # GIT style file path, e.g. "a/b/c";
  87  ref     ::= # GIT ref name, e.g. "refs/heads/MOZ_GECKO_EXPERIMENT";
  88  tag     ::= # GIT tag name, e.g. "FIREFOX_1_5";
  89  sha1exp ::= # Any valid GIT SHA1 expression;
  90  hexsha1 ::= # SHA1 in hexadecimal format;
  91
  92     # note: name and email are UTF8 strings, however name must not
  93         # contain '<' or lf and email must not contain any of the
  94     # following: '<', '>', lf.
  95         #
  96  name  ::= # valid GIT author/committer name;
  97  email ::= # valid GIT author/committer email;
  98  ts    ::= # time since the epoch in seconds, ascii base10 notation;
  99  tz    ::= # GIT style timezone;
 100*/
 101
 102#include "builtin.h"
 103#include "cache.h"
 104#include "object.h"
 105#include "blob.h"
 106#include "tree.h"
 107#include "delta.h"
 108#include "pack.h"
 109#include "refs.h"
 110#include "csum-file.h"
 111#include "strbuf.h"
 112#include "quote.h"
 113
 114#define PACK_ID_BITS 16
 115#define MAX_PACK_ID ((1<<PACK_ID_BITS)-1)
 116
 117struct object_entry
 118{
 119        struct object_entry *next;
 120        unsigned long offset;
 121        unsigned type : TYPE_BITS;
 122        unsigned pack_id : PACK_ID_BITS;
 123        unsigned char sha1[20];
 124};
 125
 126struct object_entry_pool
 127{
 128        struct object_entry_pool *next_pool;
 129        struct object_entry *next_free;
 130        struct object_entry *end;
 131        struct object_entry entries[FLEX_ARRAY]; /* more */
 132};
 133
 134struct mark_set
 135{
 136        union {
 137                struct object_entry *marked[1024];
 138                struct mark_set *sets[1024];
 139        } data;
 140        unsigned int shift;
 141};
 142
 143struct last_object
 144{
 145        void *data;
 146        unsigned long len;
 147        unsigned long offset;
 148        unsigned int depth;
 149        unsigned no_free:1;
 150};
 151
 152struct mem_pool
 153{
 154        struct mem_pool *next_pool;
 155        char *next_free;
 156        char *end;
 157        char space[FLEX_ARRAY]; /* more */
 158};
 159
 160struct atom_str
 161{
 162        struct atom_str *next_atom;
 163        unsigned int str_len;
 164        char str_dat[FLEX_ARRAY]; /* more */
 165};
 166
 167struct tree_content;
 168struct tree_entry
 169{
 170        struct tree_content *tree;
 171        struct atom_str* name;
 172        struct tree_entry_ms
 173        {
 174                unsigned int mode;
 175                unsigned char sha1[20];
 176        } versions[2];
 177};
 178
 179struct tree_content
 180{
 181        unsigned int entry_capacity; /* must match avail_tree_content */
 182        unsigned int entry_count;
 183        unsigned int delta_depth;
 184        struct tree_entry *entries[FLEX_ARRAY]; /* more */
 185};
 186
 187struct avail_tree_content
 188{
 189        unsigned int entry_capacity; /* must match tree_content */
 190        struct avail_tree_content *next_avail;
 191};
 192
 193struct branch
 194{
 195        struct branch *table_next_branch;
 196        struct branch *active_next_branch;
 197        const char *name;
 198        struct tree_entry branch_tree;
 199        uintmax_t last_commit;
 200        unsigned int pack_id;
 201        unsigned char sha1[20];
 202};
 203
 204struct tag
 205{
 206        struct tag *next_tag;
 207        const char *name;
 208        unsigned int pack_id;
 209        unsigned char sha1[20];
 210};
 211
 212struct dbuf
 213{
 214        void *buffer;
 215        size_t capacity;
 216};
 217
 218struct hash_list
 219{
 220        struct hash_list *next;
 221        unsigned char sha1[20];
 222};
 223
 224/* Configured limits on output */
 225static unsigned long max_depth = 10;
 226static unsigned long max_packsize = (1LL << 32) - 1;
 227static uintmax_t max_objects = -1;
 228
 229/* Stats and misc. counters */
 230static uintmax_t alloc_count;
 231static uintmax_t marks_set_count;
 232static uintmax_t object_count_by_type[1 << TYPE_BITS];
 233static uintmax_t duplicate_count_by_type[1 << TYPE_BITS];
 234static uintmax_t delta_count_by_type[1 << TYPE_BITS];
 235static unsigned long object_count;
 236static unsigned long branch_count;
 237static unsigned long branch_load_count;
 238
 239/* Memory pools */
 240static size_t mem_pool_alloc = 2*1024*1024 - sizeof(struct mem_pool);
 241static size_t total_allocd;
 242static struct mem_pool *mem_pool;
 243
 244/* Atom management */
 245static unsigned int atom_table_sz = 4451;
 246static unsigned int atom_cnt;
 247static struct atom_str **atom_table;
 248
 249/* The .pack file being generated */
 250static unsigned int pack_id;
 251static struct packed_git *pack_data;
 252static struct packed_git **all_packs;
 253static unsigned long pack_size;
 254
 255/* Table of objects we've written. */
 256static unsigned int object_entry_alloc = 5000;
 257static struct object_entry_pool *blocks;
 258static struct object_entry *object_table[1 << 16];
 259static struct mark_set *marks;
 260static const char* mark_file;
 261
 262/* Our last blob */
 263static struct last_object last_blob;
 264
 265/* Tree management */
 266static unsigned int tree_entry_alloc = 1000;
 267static void *avail_tree_entry;
 268static unsigned int avail_tree_table_sz = 100;
 269static struct avail_tree_content **avail_tree_table;
 270static struct dbuf old_tree;
 271static struct dbuf new_tree;
 272
 273/* Branch data */
 274static unsigned long max_active_branches = 5;
 275static unsigned long cur_active_branches;
 276static unsigned long branch_table_sz = 1039;
 277static struct branch **branch_table;
 278static struct branch *active_branches;
 279
 280/* Tag data */
 281static struct tag *first_tag;
 282static struct tag *last_tag;
 283
 284/* Input stream parsing */
 285static struct strbuf command_buf;
 286static uintmax_t next_mark;
 287static struct dbuf new_data;
 288static FILE* branch_log;
 289
 290
 291static void alloc_objects(unsigned int cnt)
 292{
 293        struct object_entry_pool *b;
 294
 295        b = xmalloc(sizeof(struct object_entry_pool)
 296                + cnt * sizeof(struct object_entry));
 297        b->next_pool = blocks;
 298        b->next_free = b->entries;
 299        b->end = b->entries + cnt;
 300        blocks = b;
 301        alloc_count += cnt;
 302}
 303
 304static struct object_entry* new_object(unsigned char *sha1)
 305{
 306        struct object_entry *e;
 307
 308        if (blocks->next_free == blocks->end)
 309                alloc_objects(object_entry_alloc);
 310
 311        e = blocks->next_free++;
 312        hashcpy(e->sha1, sha1);
 313        return e;
 314}
 315
 316static struct object_entry* find_object(unsigned char *sha1)
 317{
 318        unsigned int h = sha1[0] << 8 | sha1[1];
 319        struct object_entry *e;
 320        for (e = object_table[h]; e; e = e->next)
 321                if (!hashcmp(sha1, e->sha1))
 322                        return e;
 323        return NULL;
 324}
 325
 326static struct object_entry* insert_object(unsigned char *sha1)
 327{
 328        unsigned int h = sha1[0] << 8 | sha1[1];
 329        struct object_entry *e = object_table[h];
 330        struct object_entry *p = NULL;
 331
 332        while (e) {
 333                if (!hashcmp(sha1, e->sha1))
 334                        return e;
 335                p = e;
 336                e = e->next;
 337        }
 338
 339        e = new_object(sha1);
 340        e->next = NULL;
 341        e->offset = 0;
 342        if (p)
 343                p->next = e;
 344        else
 345                object_table[h] = e;
 346        return e;
 347}
 348
 349static unsigned int hc_str(const char *s, size_t len)
 350{
 351        unsigned int r = 0;
 352        while (len-- > 0)
 353                r = r * 31 + *s++;
 354        return r;
 355}
 356
 357static void* pool_alloc(size_t len)
 358{
 359        struct mem_pool *p;
 360        void *r;
 361
 362        for (p = mem_pool; p; p = p->next_pool)
 363                if ((p->end - p->next_free >= len))
 364                        break;
 365
 366        if (!p) {
 367                if (len >= (mem_pool_alloc/2)) {
 368                        total_allocd += len;
 369                        return xmalloc(len);
 370                }
 371                total_allocd += sizeof(struct mem_pool) + mem_pool_alloc;
 372                p = xmalloc(sizeof(struct mem_pool) + mem_pool_alloc);
 373                p->next_pool = mem_pool;
 374                p->next_free = p->space;
 375                p->end = p->next_free + mem_pool_alloc;
 376                mem_pool = p;
 377        }
 378
 379        r = p->next_free;
 380        /* round out to a pointer alignment */
 381        if (len & (sizeof(void*) - 1))
 382                len += sizeof(void*) - (len & (sizeof(void*) - 1));
 383        p->next_free += len;
 384        return r;
 385}
 386
 387static void* pool_calloc(size_t count, size_t size)
 388{
 389        size_t len = count * size;
 390        void *r = pool_alloc(len);
 391        memset(r, 0, len);
 392        return r;
 393}
 394
 395static char* pool_strdup(const char *s)
 396{
 397        char *r = pool_alloc(strlen(s) + 1);
 398        strcpy(r, s);
 399        return r;
 400}
 401
 402static void size_dbuf(struct dbuf *b, size_t maxlen)
 403{
 404        if (b->buffer) {
 405                if (b->capacity >= maxlen)
 406                        return;
 407                free(b->buffer);
 408        }
 409        b->capacity = ((maxlen / 1024) + 1) * 1024;
 410        b->buffer = xmalloc(b->capacity);
 411}
 412
 413static void insert_mark(uintmax_t idnum, struct object_entry *oe)
 414{
 415        struct mark_set *s = marks;
 416        while ((idnum >> s->shift) >= 1024) {
 417                s = pool_calloc(1, sizeof(struct mark_set));
 418                s->shift = marks->shift + 10;
 419                s->data.sets[0] = marks;
 420                marks = s;
 421        }
 422        while (s->shift) {
 423                uintmax_t i = idnum >> s->shift;
 424                idnum -= i << s->shift;
 425                if (!s->data.sets[i]) {
 426                        s->data.sets[i] = pool_calloc(1, sizeof(struct mark_set));
 427                        s->data.sets[i]->shift = s->shift - 10;
 428                }
 429                s = s->data.sets[i];
 430        }
 431        if (!s->data.marked[idnum])
 432                marks_set_count++;
 433        s->data.marked[idnum] = oe;
 434}
 435
 436static struct object_entry* find_mark(uintmax_t idnum)
 437{
 438        uintmax_t orig_idnum = idnum;
 439        struct mark_set *s = marks;
 440        struct object_entry *oe = NULL;
 441        if ((idnum >> s->shift) < 1024) {
 442                while (s && s->shift) {
 443                        uintmax_t i = idnum >> s->shift;
 444                        idnum -= i << s->shift;
 445                        s = s->data.sets[i];
 446                }
 447                if (s)
 448                        oe = s->data.marked[idnum];
 449        }
 450        if (!oe)
 451                die("mark :%ju not declared", orig_idnum);
 452        return oe;
 453}
 454
 455static struct atom_str* to_atom(const char *s, size_t len)
 456{
 457        unsigned int hc = hc_str(s, len) % atom_table_sz;
 458        struct atom_str *c;
 459
 460        for (c = atom_table[hc]; c; c = c->next_atom)
 461                if (c->str_len == len && !strncmp(s, c->str_dat, len))
 462                        return c;
 463
 464        c = pool_alloc(sizeof(struct atom_str) + len + 1);
 465        c->str_len = len;
 466        strncpy(c->str_dat, s, len);
 467        c->str_dat[len] = 0;
 468        c->next_atom = atom_table[hc];
 469        atom_table[hc] = c;
 470        atom_cnt++;
 471        return c;
 472}
 473
 474static struct branch* lookup_branch(const char *name)
 475{
 476        unsigned int hc = hc_str(name, strlen(name)) % branch_table_sz;
 477        struct branch *b;
 478
 479        for (b = branch_table[hc]; b; b = b->table_next_branch)
 480                if (!strcmp(name, b->name))
 481                        return b;
 482        return NULL;
 483}
 484
 485static struct branch* new_branch(const char *name)
 486{
 487        unsigned int hc = hc_str(name, strlen(name)) % branch_table_sz;
 488        struct branch* b = lookup_branch(name);
 489
 490        if (b)
 491                die("Invalid attempt to create duplicate branch: %s", name);
 492        if (check_ref_format(name))
 493                die("Branch name doesn't conform to GIT standards: %s", name);
 494
 495        b = pool_calloc(1, sizeof(struct branch));
 496        b->name = pool_strdup(name);
 497        b->table_next_branch = branch_table[hc];
 498        b->branch_tree.versions[0].mode = S_IFDIR;
 499        b->branch_tree.versions[1].mode = S_IFDIR;
 500        b->pack_id = MAX_PACK_ID;
 501        branch_table[hc] = b;
 502        branch_count++;
 503        return b;
 504}
 505
 506static unsigned int hc_entries(unsigned int cnt)
 507{
 508        cnt = cnt & 7 ? (cnt / 8) + 1 : cnt / 8;
 509        return cnt < avail_tree_table_sz ? cnt : avail_tree_table_sz - 1;
 510}
 511
 512static struct tree_content* new_tree_content(unsigned int cnt)
 513{
 514        struct avail_tree_content *f, *l = NULL;
 515        struct tree_content *t;
 516        unsigned int hc = hc_entries(cnt);
 517
 518        for (f = avail_tree_table[hc]; f; l = f, f = f->next_avail)
 519                if (f->entry_capacity >= cnt)
 520                        break;
 521
 522        if (f) {
 523                if (l)
 524                        l->next_avail = f->next_avail;
 525                else
 526                        avail_tree_table[hc] = f->next_avail;
 527        } else {
 528                cnt = cnt & 7 ? ((cnt / 8) + 1) * 8 : cnt;
 529                f = pool_alloc(sizeof(*t) + sizeof(t->entries[0]) * cnt);
 530                f->entry_capacity = cnt;
 531        }
 532
 533        t = (struct tree_content*)f;
 534        t->entry_count = 0;
 535        t->delta_depth = 0;
 536        return t;
 537}
 538
 539static void release_tree_entry(struct tree_entry *e);
 540static void release_tree_content(struct tree_content *t)
 541{
 542        struct avail_tree_content *f = (struct avail_tree_content*)t;
 543        unsigned int hc = hc_entries(f->entry_capacity);
 544        f->next_avail = avail_tree_table[hc];
 545        avail_tree_table[hc] = f;
 546}
 547
 548static void release_tree_content_recursive(struct tree_content *t)
 549{
 550        unsigned int i;
 551        for (i = 0; i < t->entry_count; i++)
 552                release_tree_entry(t->entries[i]);
 553        release_tree_content(t);
 554}
 555
 556static struct tree_content* grow_tree_content(
 557        struct tree_content *t,
 558        int amt)
 559{
 560        struct tree_content *r = new_tree_content(t->entry_count + amt);
 561        r->entry_count = t->entry_count;
 562        r->delta_depth = t->delta_depth;
 563        memcpy(r->entries,t->entries,t->entry_count*sizeof(t->entries[0]));
 564        release_tree_content(t);
 565        return r;
 566}
 567
 568static struct tree_entry* new_tree_entry(void)
 569{
 570        struct tree_entry *e;
 571
 572        if (!avail_tree_entry) {
 573                unsigned int n = tree_entry_alloc;
 574                total_allocd += n * sizeof(struct tree_entry);
 575                avail_tree_entry = e = xmalloc(n * sizeof(struct tree_entry));
 576                while (n-- > 1) {
 577                        *((void**)e) = e + 1;
 578                        e++;
 579                }
 580                *((void**)e) = NULL;
 581        }
 582
 583        e = avail_tree_entry;
 584        avail_tree_entry = *((void**)e);
 585        return e;
 586}
 587
 588static void release_tree_entry(struct tree_entry *e)
 589{
 590        if (e->tree)
 591                release_tree_content_recursive(e->tree);
 592        *((void**)e) = avail_tree_entry;
 593        avail_tree_entry = e;
 594}
 595
 596static void start_packfile(void)
 597{
 598        static char tmpfile[PATH_MAX];
 599        struct packed_git *p;
 600        struct pack_header hdr;
 601        int pack_fd;
 602
 603        snprintf(tmpfile, sizeof(tmpfile),
 604                "%s/pack_XXXXXX", get_object_directory());
 605        pack_fd = mkstemp(tmpfile);
 606        if (pack_fd < 0)
 607                die("Can't create %s: %s", tmpfile, strerror(errno));
 608        p = xcalloc(1, sizeof(*p) + strlen(tmpfile) + 2);
 609        strcpy(p->pack_name, tmpfile);
 610        p->pack_fd = pack_fd;
 611
 612        hdr.hdr_signature = htonl(PACK_SIGNATURE);
 613        hdr.hdr_version = htonl(2);
 614        hdr.hdr_entries = 0;
 615        write_or_die(p->pack_fd, &hdr, sizeof(hdr));
 616
 617        pack_data = p;
 618        pack_size = sizeof(hdr);
 619        object_count = 0;
 620
 621        all_packs = xrealloc(all_packs, sizeof(*all_packs) * (pack_id + 1));
 622        all_packs[pack_id] = p;
 623}
 624
 625static void fixup_header_footer(void)
 626{
 627        int pack_fd = pack_data->pack_fd;
 628        SHA_CTX c;
 629        char hdr[8];
 630        unsigned long cnt;
 631        char *buf;
 632
 633        if (lseek(pack_fd, 0, SEEK_SET) != 0)
 634                die("Failed seeking to start: %s", strerror(errno));
 635
 636        SHA1_Init(&c);
 637        if (read_in_full(pack_fd, hdr, 8) != 8)
 638                die("Unable to reread header of %s", pack_data->pack_name);
 639        SHA1_Update(&c, hdr, 8);
 640
 641        cnt = htonl(object_count);
 642        SHA1_Update(&c, &cnt, 4);
 643        write_or_die(pack_fd, &cnt, 4);
 644
 645        buf = xmalloc(128 * 1024);
 646        for (;;) {
 647                size_t n = xread(pack_fd, buf, 128 * 1024);
 648                if (n <= 0)
 649                        break;
 650                SHA1_Update(&c, buf, n);
 651        }
 652        free(buf);
 653
 654        SHA1_Final(pack_data->sha1, &c);
 655        write_or_die(pack_fd, pack_data->sha1, sizeof(pack_data->sha1));
 656        close(pack_fd);
 657}
 658
 659static int oecmp (const void *a_, const void *b_)
 660{
 661        struct object_entry *a = *((struct object_entry**)a_);
 662        struct object_entry *b = *((struct object_entry**)b_);
 663        return hashcmp(a->sha1, b->sha1);
 664}
 665
 666static char* create_index(void)
 667{
 668        static char tmpfile[PATH_MAX];
 669        SHA_CTX ctx;
 670        struct sha1file *f;
 671        struct object_entry **idx, **c, **last, *e;
 672        struct object_entry_pool *o;
 673        unsigned int array[256];
 674        int i, idx_fd;
 675
 676        /* Build the sorted table of object IDs. */
 677        idx = xmalloc(object_count * sizeof(struct object_entry*));
 678        c = idx;
 679        for (o = blocks; o; o = o->next_pool)
 680                for (e = o->next_free; e-- != o->entries;)
 681                        if (pack_id == e->pack_id)
 682                                *c++ = e;
 683        last = idx + object_count;
 684        if (c != last)
 685                die("internal consistency error creating the index");
 686        qsort(idx, object_count, sizeof(struct object_entry*), oecmp);
 687
 688        /* Generate the fan-out array. */
 689        c = idx;
 690        for (i = 0; i < 256; i++) {
 691                struct object_entry **next = c;;
 692                while (next < last) {
 693                        if ((*next)->sha1[0] != i)
 694                                break;
 695                        next++;
 696                }
 697                array[i] = htonl(next - idx);
 698                c = next;
 699        }
 700
 701        snprintf(tmpfile, sizeof(tmpfile),
 702                "%s/index_XXXXXX", get_object_directory());
 703        idx_fd = mkstemp(tmpfile);
 704        if (idx_fd < 0)
 705                die("Can't create %s: %s", tmpfile, strerror(errno));
 706        f = sha1fd(idx_fd, tmpfile);
 707        sha1write(f, array, 256 * sizeof(int));
 708        SHA1_Init(&ctx);
 709        for (c = idx; c != last; c++) {
 710                unsigned int offset = htonl((*c)->offset);
 711                sha1write(f, &offset, 4);
 712                sha1write(f, (*c)->sha1, sizeof((*c)->sha1));
 713                SHA1_Update(&ctx, (*c)->sha1, 20);
 714        }
 715        sha1write(f, pack_data->sha1, sizeof(pack_data->sha1));
 716        sha1close(f, NULL, 1);
 717        free(idx);
 718        SHA1_Final(pack_data->sha1, &ctx);
 719        return tmpfile;
 720}
 721
 722static char* keep_pack(char *curr_index_name)
 723{
 724        static char name[PATH_MAX];
 725        static char *keep_msg = "fast-import";
 726        int keep_fd;
 727
 728        chmod(pack_data->pack_name, 0444);
 729        chmod(curr_index_name, 0444);
 730
 731        snprintf(name, sizeof(name), "%s/pack/pack-%s.keep",
 732                 get_object_directory(), sha1_to_hex(pack_data->sha1));
 733        keep_fd = open(name, O_RDWR|O_CREAT|O_EXCL, 0600);
 734        if (keep_fd < 0)
 735                die("cannot create keep file");
 736        write(keep_fd, keep_msg, strlen(keep_msg));
 737        close(keep_fd);
 738
 739        snprintf(name, sizeof(name), "%s/pack/pack-%s.pack",
 740                 get_object_directory(), sha1_to_hex(pack_data->sha1));
 741        if (move_temp_to_file(pack_data->pack_name, name))
 742                die("cannot store pack file");
 743
 744        snprintf(name, sizeof(name), "%s/pack/pack-%s.idx",
 745                 get_object_directory(), sha1_to_hex(pack_data->sha1));
 746        if (move_temp_to_file(curr_index_name, name))
 747                die("cannot store index file");
 748        return name;
 749}
 750
 751static void unkeep_all_packs(void)
 752{
 753        static char name[PATH_MAX];
 754        int k;
 755
 756        for (k = 0; k < pack_id; k++) {
 757                struct packed_git *p = all_packs[k];
 758                snprintf(name, sizeof(name), "%s/pack/pack-%s.keep",
 759                         get_object_directory(), sha1_to_hex(p->sha1));
 760                unlink(name);
 761        }
 762}
 763
 764static void end_packfile(void)
 765{
 766        struct packed_git *old_p = pack_data, *new_p;
 767
 768        if (object_count) {
 769                char *idx_name;
 770                int i;
 771                struct branch *b;
 772                struct tag *t;
 773
 774                fixup_header_footer();
 775                idx_name = keep_pack(create_index());
 776
 777                /* Register the packfile with core git's machinary. */
 778                new_p = add_packed_git(idx_name, strlen(idx_name), 1);
 779                if (!new_p)
 780                        die("core git rejected index %s", idx_name);
 781                new_p->windows = old_p->windows;
 782                all_packs[pack_id] = new_p;
 783                install_packed_git(new_p);
 784
 785                /* Print the boundary */
 786                fprintf(stdout, "%s:", new_p->pack_name);
 787                for (i = 0; i < branch_table_sz; i++) {
 788                        for (b = branch_table[i]; b; b = b->table_next_branch) {
 789                                if (b->pack_id == pack_id)
 790                                        fprintf(stdout, " %s", sha1_to_hex(b->sha1));
 791                        }
 792                }
 793                for (t = first_tag; t; t = t->next_tag) {
 794                        if (t->pack_id == pack_id)
 795                                fprintf(stdout, " %s", sha1_to_hex(t->sha1));
 796                }
 797                fputc('\n', stdout);
 798
 799                pack_id++;
 800        }
 801        else
 802                unlink(old_p->pack_name);
 803        free(old_p);
 804
 805        /* We can't carry a delta across packfiles. */
 806        free(last_blob.data);
 807        last_blob.data = NULL;
 808        last_blob.len = 0;
 809        last_blob.offset = 0;
 810        last_blob.depth = 0;
 811}
 812
 813static void checkpoint(void)
 814{
 815        end_packfile();
 816        start_packfile();
 817}
 818
 819static size_t encode_header(
 820        enum object_type type,
 821        size_t size,
 822        unsigned char *hdr)
 823{
 824        int n = 1;
 825        unsigned char c;
 826
 827        if (type < OBJ_COMMIT || type > OBJ_REF_DELTA)
 828                die("bad type %d", type);
 829
 830        c = (type << 4) | (size & 15);
 831        size >>= 4;
 832        while (size) {
 833                *hdr++ = c | 0x80;
 834                c = size & 0x7f;
 835                size >>= 7;
 836                n++;
 837        }
 838        *hdr = c;
 839        return n;
 840}
 841
 842static int store_object(
 843        enum object_type type,
 844        void *dat,
 845        size_t datlen,
 846        struct last_object *last,
 847        unsigned char *sha1out,
 848        uintmax_t mark)
 849{
 850        void *out, *delta;
 851        struct object_entry *e;
 852        unsigned char hdr[96];
 853        unsigned char sha1[20];
 854        unsigned long hdrlen, deltalen;
 855        SHA_CTX c;
 856        z_stream s;
 857
 858        hdrlen = sprintf((char*)hdr,"%s %lu",type_names[type],datlen) + 1;
 859        SHA1_Init(&c);
 860        SHA1_Update(&c, hdr, hdrlen);
 861        SHA1_Update(&c, dat, datlen);
 862        SHA1_Final(sha1, &c);
 863        if (sha1out)
 864                hashcpy(sha1out, sha1);
 865
 866        e = insert_object(sha1);
 867        if (mark)
 868                insert_mark(mark, e);
 869        if (e->offset) {
 870                duplicate_count_by_type[type]++;
 871                return 1;
 872        }
 873
 874        if (last && last->data && last->depth < max_depth) {
 875                delta = diff_delta(last->data, last->len,
 876                        dat, datlen,
 877                        &deltalen, 0);
 878                if (delta && deltalen >= datlen) {
 879                        free(delta);
 880                        delta = NULL;
 881                }
 882        } else
 883                delta = NULL;
 884
 885        memset(&s, 0, sizeof(s));
 886        deflateInit(&s, zlib_compression_level);
 887        if (delta) {
 888                s.next_in = delta;
 889                s.avail_in = deltalen;
 890        } else {
 891                s.next_in = dat;
 892                s.avail_in = datlen;
 893        }
 894        s.avail_out = deflateBound(&s, s.avail_in);
 895        s.next_out = out = xmalloc(s.avail_out);
 896        while (deflate(&s, Z_FINISH) == Z_OK)
 897                /* nothing */;
 898        deflateEnd(&s);
 899
 900        /* Determine if we should auto-checkpoint. */
 901        if ((object_count + 1) > max_objects
 902                || (object_count + 1) < object_count
 903                || (pack_size + 60 + s.total_out) > max_packsize
 904                || (pack_size + 60 + s.total_out) < pack_size) {
 905
 906                /* This new object needs to *not* have the current pack_id. */
 907                e->pack_id = pack_id + 1;
 908                checkpoint();
 909
 910                /* We cannot carry a delta into the new pack. */
 911                if (delta) {
 912                        free(delta);
 913                        delta = NULL;
 914
 915                        memset(&s, 0, sizeof(s));
 916                        deflateInit(&s, zlib_compression_level);
 917                        s.next_in = dat;
 918                        s.avail_in = datlen;
 919                        s.avail_out = deflateBound(&s, s.avail_in);
 920                        s.next_out = out = xrealloc(out, s.avail_out);
 921                        while (deflate(&s, Z_FINISH) == Z_OK)
 922                                /* nothing */;
 923                        deflateEnd(&s);
 924                }
 925        }
 926
 927        e->type = type;
 928        e->pack_id = pack_id;
 929        e->offset = pack_size;
 930        object_count++;
 931        object_count_by_type[type]++;
 932
 933        if (delta) {
 934                unsigned long ofs = e->offset - last->offset;
 935                unsigned pos = sizeof(hdr) - 1;
 936
 937                delta_count_by_type[type]++;
 938                last->depth++;
 939
 940                hdrlen = encode_header(OBJ_OFS_DELTA, deltalen, hdr);
 941                write_or_die(pack_data->pack_fd, hdr, hdrlen);
 942                pack_size += hdrlen;
 943
 944                hdr[pos] = ofs & 127;
 945                while (ofs >>= 7)
 946                        hdr[--pos] = 128 | (--ofs & 127);
 947                write_or_die(pack_data->pack_fd, hdr + pos, sizeof(hdr) - pos);
 948                pack_size += sizeof(hdr) - pos;
 949        } else {
 950                if (last)
 951                        last->depth = 0;
 952                hdrlen = encode_header(type, datlen, hdr);
 953                write_or_die(pack_data->pack_fd, hdr, hdrlen);
 954                pack_size += hdrlen;
 955        }
 956
 957        write_or_die(pack_data->pack_fd, out, s.total_out);
 958        pack_size += s.total_out;
 959
 960        free(out);
 961        if (delta)
 962                free(delta);
 963        if (last) {
 964                if (last->data && !last->no_free)
 965                        free(last->data);
 966                last->data = dat;
 967                last->offset = e->offset;
 968                last->len = datlen;
 969        }
 970        return 0;
 971}
 972
 973static void *gfi_unpack_entry(
 974        struct object_entry *oe,
 975        unsigned long *sizep)
 976{
 977        static char type[20];
 978        struct packed_git *p = all_packs[oe->pack_id];
 979        if (p == pack_data)
 980                p->pack_size = pack_size + 20;
 981        return unpack_entry(p, oe->offset, type, sizep);
 982}
 983
 984static const char *get_mode(const char *str, unsigned int *modep)
 985{
 986        unsigned char c;
 987        unsigned int mode = 0;
 988
 989        while ((c = *str++) != ' ') {
 990                if (c < '0' || c > '7')
 991                        return NULL;
 992                mode = (mode << 3) + (c - '0');
 993        }
 994        *modep = mode;
 995        return str;
 996}
 997
 998static void load_tree(struct tree_entry *root)
 999{
1000        unsigned char* sha1 = root->versions[1].sha1;
1001        struct object_entry *myoe;
1002        struct tree_content *t;
1003        unsigned long size;
1004        char *buf;
1005        const char *c;
1006
1007        root->tree = t = new_tree_content(8);
1008        if (is_null_sha1(sha1))
1009                return;
1010
1011        myoe = find_object(sha1);
1012        if (myoe) {
1013                if (myoe->type != OBJ_TREE)
1014                        die("Not a tree: %s", sha1_to_hex(sha1));
1015                t->delta_depth = 0;
1016                buf = gfi_unpack_entry(myoe, &size);
1017        } else {
1018                char type[20];
1019                buf = read_sha1_file(sha1, type, &size);
1020                if (!buf || strcmp(type, tree_type))
1021                        die("Can't load tree %s", sha1_to_hex(sha1));
1022        }
1023
1024        c = buf;
1025        while (c != (buf + size)) {
1026                struct tree_entry *e = new_tree_entry();
1027
1028                if (t->entry_count == t->entry_capacity)
1029                        root->tree = t = grow_tree_content(t, 8);
1030                t->entries[t->entry_count++] = e;
1031
1032                e->tree = NULL;
1033                c = get_mode(c, &e->versions[1].mode);
1034                if (!c)
1035                        die("Corrupt mode in %s", sha1_to_hex(sha1));
1036                e->versions[0].mode = e->versions[1].mode;
1037                e->name = to_atom(c, strlen(c));
1038                c += e->name->str_len + 1;
1039                hashcpy(e->versions[0].sha1, (unsigned char*)c);
1040                hashcpy(e->versions[1].sha1, (unsigned char*)c);
1041                c += 20;
1042        }
1043        free(buf);
1044}
1045
1046static int tecmp0 (const void *_a, const void *_b)
1047{
1048        struct tree_entry *a = *((struct tree_entry**)_a);
1049        struct tree_entry *b = *((struct tree_entry**)_b);
1050        return base_name_compare(
1051                a->name->str_dat, a->name->str_len, a->versions[0].mode,
1052                b->name->str_dat, b->name->str_len, b->versions[0].mode);
1053}
1054
1055static int tecmp1 (const void *_a, const void *_b)
1056{
1057        struct tree_entry *a = *((struct tree_entry**)_a);
1058        struct tree_entry *b = *((struct tree_entry**)_b);
1059        return base_name_compare(
1060                a->name->str_dat, a->name->str_len, a->versions[1].mode,
1061                b->name->str_dat, b->name->str_len, b->versions[1].mode);
1062}
1063
1064static void mktree(struct tree_content *t,
1065        int v,
1066        unsigned long *szp,
1067        struct dbuf *b)
1068{
1069        size_t maxlen = 0;
1070        unsigned int i;
1071        char *c;
1072
1073        if (!v)
1074                qsort(t->entries,t->entry_count,sizeof(t->entries[0]),tecmp0);
1075        else
1076                qsort(t->entries,t->entry_count,sizeof(t->entries[0]),tecmp1);
1077
1078        for (i = 0; i < t->entry_count; i++) {
1079                if (t->entries[i]->versions[v].mode)
1080                        maxlen += t->entries[i]->name->str_len + 34;
1081        }
1082
1083        size_dbuf(b, maxlen);
1084        c = b->buffer;
1085        for (i = 0; i < t->entry_count; i++) {
1086                struct tree_entry *e = t->entries[i];
1087                if (!e->versions[v].mode)
1088                        continue;
1089                c += sprintf(c, "%o", e->versions[v].mode);
1090                *c++ = ' ';
1091                strcpy(c, e->name->str_dat);
1092                c += e->name->str_len + 1;
1093                hashcpy((unsigned char*)c, e->versions[v].sha1);
1094                c += 20;
1095        }
1096        *szp = c - (char*)b->buffer;
1097}
1098
1099static void store_tree(struct tree_entry *root)
1100{
1101        struct tree_content *t = root->tree;
1102        unsigned int i, j, del;
1103        unsigned long new_len;
1104        struct last_object lo;
1105        struct object_entry *le;
1106
1107        if (!is_null_sha1(root->versions[1].sha1))
1108                return;
1109
1110        for (i = 0; i < t->entry_count; i++) {
1111                if (t->entries[i]->tree)
1112                        store_tree(t->entries[i]);
1113        }
1114
1115        le = find_object(root->versions[0].sha1);
1116        if (!S_ISDIR(root->versions[0].mode)
1117                || !le
1118                || le->pack_id != pack_id) {
1119                lo.data = NULL;
1120                lo.depth = 0;
1121        } else {
1122                mktree(t, 0, &lo.len, &old_tree);
1123                lo.data = old_tree.buffer;
1124                lo.offset = le->offset;
1125                lo.depth = t->delta_depth;
1126                lo.no_free = 1;
1127        }
1128
1129        mktree(t, 1, &new_len, &new_tree);
1130        store_object(OBJ_TREE, new_tree.buffer, new_len,
1131                &lo, root->versions[1].sha1, 0);
1132
1133        t->delta_depth = lo.depth;
1134        for (i = 0, j = 0, del = 0; i < t->entry_count; i++) {
1135                struct tree_entry *e = t->entries[i];
1136                if (e->versions[1].mode) {
1137                        e->versions[0].mode = e->versions[1].mode;
1138                        hashcpy(e->versions[0].sha1, e->versions[1].sha1);
1139                        t->entries[j++] = e;
1140                } else {
1141                        release_tree_entry(e);
1142                        del++;
1143                }
1144        }
1145        t->entry_count -= del;
1146}
1147
1148static int tree_content_set(
1149        struct tree_entry *root,
1150        const char *p,
1151        const unsigned char *sha1,
1152        const unsigned int mode)
1153{
1154        struct tree_content *t = root->tree;
1155        const char *slash1;
1156        unsigned int i, n;
1157        struct tree_entry *e;
1158
1159        slash1 = strchr(p, '/');
1160        if (slash1)
1161                n = slash1 - p;
1162        else
1163                n = strlen(p);
1164
1165        for (i = 0; i < t->entry_count; i++) {
1166                e = t->entries[i];
1167                if (e->name->str_len == n && !strncmp(p, e->name->str_dat, n)) {
1168                        if (!slash1) {
1169                                if (e->versions[1].mode == mode
1170                                                && !hashcmp(e->versions[1].sha1, sha1))
1171                                        return 0;
1172                                e->versions[1].mode = mode;
1173                                hashcpy(e->versions[1].sha1, sha1);
1174                                if (e->tree) {
1175                                        release_tree_content_recursive(e->tree);
1176                                        e->tree = NULL;
1177                                }
1178                                hashclr(root->versions[1].sha1);
1179                                return 1;
1180                        }
1181                        if (!S_ISDIR(e->versions[1].mode)) {
1182                                e->tree = new_tree_content(8);
1183                                e->versions[1].mode = S_IFDIR;
1184                        }
1185                        if (!e->tree)
1186                                load_tree(e);
1187                        if (tree_content_set(e, slash1 + 1, sha1, mode)) {
1188                                hashclr(root->versions[1].sha1);
1189                                return 1;
1190                        }
1191                        return 0;
1192                }
1193        }
1194
1195        if (t->entry_count == t->entry_capacity)
1196                root->tree = t = grow_tree_content(t, 8);
1197        e = new_tree_entry();
1198        e->name = to_atom(p, n);
1199        e->versions[0].mode = 0;
1200        hashclr(e->versions[0].sha1);
1201        t->entries[t->entry_count++] = e;
1202        if (slash1) {
1203                e->tree = new_tree_content(8);
1204                e->versions[1].mode = S_IFDIR;
1205                tree_content_set(e, slash1 + 1, sha1, mode);
1206        } else {
1207                e->tree = NULL;
1208                e->versions[1].mode = mode;
1209                hashcpy(e->versions[1].sha1, sha1);
1210        }
1211        hashclr(root->versions[1].sha1);
1212        return 1;
1213}
1214
1215static int tree_content_remove(struct tree_entry *root, const char *p)
1216{
1217        struct tree_content *t = root->tree;
1218        const char *slash1;
1219        unsigned int i, n;
1220        struct tree_entry *e;
1221
1222        slash1 = strchr(p, '/');
1223        if (slash1)
1224                n = slash1 - p;
1225        else
1226                n = strlen(p);
1227
1228        for (i = 0; i < t->entry_count; i++) {
1229                e = t->entries[i];
1230                if (e->name->str_len == n && !strncmp(p, e->name->str_dat, n)) {
1231                        if (!slash1 || !S_ISDIR(e->versions[1].mode))
1232                                goto del_entry;
1233                        if (!e->tree)
1234                                load_tree(e);
1235                        if (tree_content_remove(e, slash1 + 1)) {
1236                                for (n = 0; n < e->tree->entry_count; n++) {
1237                                        if (e->tree->entries[n]->versions[1].mode) {
1238                                                hashclr(root->versions[1].sha1);
1239                                                return 1;
1240                                        }
1241                                }
1242                                goto del_entry;
1243                        }
1244                        return 0;
1245                }
1246        }
1247        return 0;
1248
1249del_entry:
1250        if (e->tree) {
1251                release_tree_content_recursive(e->tree);
1252                e->tree = NULL;
1253        }
1254        e->versions[1].mode = 0;
1255        hashclr(e->versions[1].sha1);
1256        hashclr(root->versions[1].sha1);
1257        return 1;
1258}
1259
1260static void dump_branches(void)
1261{
1262        static const char *msg = "fast-import";
1263        unsigned int i;
1264        struct branch *b;
1265        struct ref_lock *lock;
1266
1267        for (i = 0; i < branch_table_sz; i++) {
1268                for (b = branch_table[i]; b; b = b->table_next_branch) {
1269                        lock = lock_any_ref_for_update(b->name, NULL);
1270                        if (!lock || write_ref_sha1(lock, b->sha1, msg) < 0)
1271                                die("Can't write %s", b->name);
1272                }
1273        }
1274}
1275
1276static void dump_tags(void)
1277{
1278        static const char *msg = "fast-import";
1279        struct tag *t;
1280        struct ref_lock *lock;
1281        char path[PATH_MAX];
1282
1283        for (t = first_tag; t; t = t->next_tag) {
1284                sprintf(path, "refs/tags/%s", t->name);
1285                lock = lock_any_ref_for_update(path, NULL);
1286                if (!lock || write_ref_sha1(lock, t->sha1, msg) < 0)
1287                        die("Can't write %s", path);
1288        }
1289}
1290
1291static void dump_marks_helper(FILE *f,
1292        uintmax_t base,
1293        struct mark_set *m)
1294{
1295        uintmax_t k;
1296        if (m->shift) {
1297                for (k = 0; k < 1024; k++) {
1298                        if (m->data.sets[k])
1299                                dump_marks_helper(f, (base + k) << m->shift,
1300                                        m->data.sets[k]);
1301                }
1302        } else {
1303                for (k = 0; k < 1024; k++) {
1304                        if (m->data.marked[k])
1305                                fprintf(f, ":%ju %s\n", base + k,
1306                                        sha1_to_hex(m->data.marked[k]->sha1));
1307                }
1308        }
1309}
1310
1311static void dump_marks(void)
1312{
1313        if (mark_file)
1314        {
1315                FILE *f = fopen(mark_file, "w");
1316                dump_marks_helper(f, 0, marks);
1317                fclose(f);
1318        }
1319}
1320
1321static void read_next_command(void)
1322{
1323        read_line(&command_buf, stdin, '\n');
1324}
1325
1326static void cmd_mark(void)
1327{
1328        if (!strncmp("mark :", command_buf.buf, 6)) {
1329                next_mark = strtoumax(command_buf.buf + 6, NULL, 10);
1330                read_next_command();
1331        }
1332        else
1333                next_mark = 0;
1334}
1335
1336static void* cmd_data (size_t *size)
1337{
1338        size_t n = 0;
1339        void *buffer;
1340        size_t length;
1341
1342        if (strncmp("data ", command_buf.buf, 5))
1343                die("Expected 'data n' command, found: %s", command_buf.buf);
1344
1345        length = strtoul(command_buf.buf + 5, NULL, 10);
1346        buffer = xmalloc(length);
1347
1348        while (n < length) {
1349                size_t s = fread((char*)buffer + n, 1, length - n, stdin);
1350                if (!s && feof(stdin))
1351                        die("EOF in data (%lu bytes remaining)", length - n);
1352                n += s;
1353        }
1354
1355        if (fgetc(stdin) != '\n')
1356                die("An lf did not trail the binary data as expected.");
1357
1358        *size = length;
1359        return buffer;
1360}
1361
1362static void cmd_new_blob(void)
1363{
1364        size_t l;
1365        void *d;
1366
1367        read_next_command();
1368        cmd_mark();
1369        d = cmd_data(&l);
1370
1371        if (store_object(OBJ_BLOB, d, l, &last_blob, NULL, next_mark))
1372                free(d);
1373}
1374
1375static void unload_one_branch(void)
1376{
1377        while (cur_active_branches
1378                && cur_active_branches >= max_active_branches) {
1379                unsigned long min_commit = ULONG_MAX;
1380                struct branch *e, *l = NULL, *p = NULL;
1381
1382                for (e = active_branches; e; e = e->active_next_branch) {
1383                        if (e->last_commit < min_commit) {
1384                                p = l;
1385                                min_commit = e->last_commit;
1386                        }
1387                        l = e;
1388                }
1389
1390                if (p) {
1391                        e = p->active_next_branch;
1392                        p->active_next_branch = e->active_next_branch;
1393                } else {
1394                        e = active_branches;
1395                        active_branches = e->active_next_branch;
1396                }
1397                e->active_next_branch = NULL;
1398                if (e->branch_tree.tree) {
1399                        release_tree_content_recursive(e->branch_tree.tree);
1400                        e->branch_tree.tree = NULL;
1401                }
1402                cur_active_branches--;
1403        }
1404}
1405
1406static void load_branch(struct branch *b)
1407{
1408        load_tree(&b->branch_tree);
1409        b->active_next_branch = active_branches;
1410        active_branches = b;
1411        cur_active_branches++;
1412        branch_load_count++;
1413}
1414
1415static void file_change_m(struct branch *b)
1416{
1417        const char *p = command_buf.buf + 2;
1418        char *p_uq;
1419        const char *endp;
1420        struct object_entry *oe;
1421        unsigned char sha1[20];
1422        unsigned int mode;
1423        char type[20];
1424
1425        p = get_mode(p, &mode);
1426        if (!p)
1427                die("Corrupt mode: %s", command_buf.buf);
1428        switch (mode) {
1429        case S_IFREG | 0644:
1430        case S_IFREG | 0755:
1431        case S_IFLNK:
1432        case 0644:
1433        case 0755:
1434                /* ok */
1435                break;
1436        default:
1437                die("Corrupt mode: %s", command_buf.buf);
1438        }
1439
1440        if (*p == ':') {
1441                char *x;
1442                oe = find_mark(strtoumax(p + 1, &x, 10));
1443                hashcpy(sha1, oe->sha1);
1444                p = x;
1445        } else {
1446                if (get_sha1_hex(p, sha1))
1447                        die("Invalid SHA1: %s", command_buf.buf);
1448                oe = find_object(sha1);
1449                p += 40;
1450        }
1451        if (*p++ != ' ')
1452                die("Missing space after SHA1: %s", command_buf.buf);
1453
1454        p_uq = unquote_c_style(p, &endp);
1455        if (p_uq) {
1456                if (*endp)
1457                        die("Garbage after path in: %s", command_buf.buf);
1458                p = p_uq;
1459        }
1460
1461        if (oe) {
1462                if (oe->type != OBJ_BLOB)
1463                        die("Not a blob (actually a %s): %s",
1464                                command_buf.buf, type_names[oe->type]);
1465        } else {
1466                if (sha1_object_info(sha1, type, NULL))
1467                        die("Blob not found: %s", command_buf.buf);
1468                if (strcmp(blob_type, type))
1469                        die("Not a blob (actually a %s): %s",
1470                                command_buf.buf, type);
1471        }
1472
1473        tree_content_set(&b->branch_tree, p, sha1, S_IFREG | mode);
1474
1475        if (p_uq)
1476                free(p_uq);
1477}
1478
1479static void file_change_d(struct branch *b)
1480{
1481        const char *p = command_buf.buf + 2;
1482        char *p_uq;
1483        const char *endp;
1484
1485        p_uq = unquote_c_style(p, &endp);
1486        if (p_uq) {
1487                if (*endp)
1488                        die("Garbage after path in: %s", command_buf.buf);
1489                p = p_uq;
1490        }
1491        tree_content_remove(&b->branch_tree, p);
1492        if (p_uq)
1493                free(p_uq);
1494}
1495
1496static void cmd_from(struct branch *b)
1497{
1498        const char *from, *endp;
1499        char *str_uq;
1500        struct branch *s;
1501
1502        if (strncmp("from ", command_buf.buf, 5))
1503                return;
1504
1505        if (b->last_commit)
1506                die("Can't reinitailize branch %s", b->name);
1507
1508        from = strchr(command_buf.buf, ' ') + 1;
1509        str_uq = unquote_c_style(from, &endp);
1510        if (str_uq) {
1511                if (*endp)
1512                        die("Garbage after string in: %s", command_buf.buf);
1513                from = str_uq;
1514        }
1515
1516        s = lookup_branch(from);
1517        if (b == s)
1518                die("Can't create a branch from itself: %s", b->name);
1519        else if (s) {
1520                unsigned char *t = s->branch_tree.versions[1].sha1;
1521                hashcpy(b->sha1, s->sha1);
1522                hashcpy(b->branch_tree.versions[0].sha1, t);
1523                hashcpy(b->branch_tree.versions[1].sha1, t);
1524        } else if (*from == ':') {
1525                uintmax_t idnum = strtoumax(from + 1, NULL, 10);
1526                struct object_entry *oe = find_mark(idnum);
1527                unsigned long size;
1528                char *buf;
1529                if (oe->type != OBJ_COMMIT)
1530                        die("Mark :%ju not a commit", idnum);
1531                hashcpy(b->sha1, oe->sha1);
1532                buf = gfi_unpack_entry(oe, &size);
1533                if (!buf || size < 46)
1534                        die("Not a valid commit: %s", from);
1535                if (memcmp("tree ", buf, 5)
1536                        || get_sha1_hex(buf + 5, b->branch_tree.versions[1].sha1))
1537                        die("The commit %s is corrupt", sha1_to_hex(b->sha1));
1538                free(buf);
1539                hashcpy(b->branch_tree.versions[0].sha1,
1540                        b->branch_tree.versions[1].sha1);
1541        } else if (!get_sha1(from, b->sha1)) {
1542                if (is_null_sha1(b->sha1)) {
1543                        hashclr(b->branch_tree.versions[0].sha1);
1544                        hashclr(b->branch_tree.versions[1].sha1);
1545                } else {
1546                        unsigned long size;
1547                        char *buf;
1548
1549                        buf = read_object_with_reference(b->sha1,
1550                                type_names[OBJ_COMMIT], &size, b->sha1);
1551                        if (!buf || size < 46)
1552                                die("Not a valid commit: %s", from);
1553                        if (memcmp("tree ", buf, 5)
1554                                || get_sha1_hex(buf + 5, b->branch_tree.versions[1].sha1))
1555                                die("The commit %s is corrupt", sha1_to_hex(b->sha1));
1556                        free(buf);
1557                        hashcpy(b->branch_tree.versions[0].sha1,
1558                                b->branch_tree.versions[1].sha1);
1559                }
1560        } else
1561                die("Invalid ref name or SHA1 expression: %s", from);
1562
1563        read_next_command();
1564}
1565
1566static struct hash_list* cmd_merge(unsigned int *count)
1567{
1568        struct hash_list *list = NULL, *n, *e;
1569        const char *from, *endp;
1570        char *str_uq;
1571        struct branch *s;
1572
1573        *count = 0;
1574        while (!strncmp("merge ", command_buf.buf, 6)) {
1575                from = strchr(command_buf.buf, ' ') + 1;
1576                str_uq = unquote_c_style(from, &endp);
1577                if (str_uq) {
1578                        if (*endp)
1579                                die("Garbage after string in: %s", command_buf.buf);
1580                        from = str_uq;
1581                }
1582
1583                n = xmalloc(sizeof(*n));
1584                s = lookup_branch(from);
1585                if (s)
1586                        hashcpy(n->sha1, s->sha1);
1587                else if (*from == ':') {
1588                        uintmax_t idnum = strtoumax(from + 1, NULL, 10);
1589                        struct object_entry *oe = find_mark(idnum);
1590                        if (oe->type != OBJ_COMMIT)
1591                                die("Mark :%ju not a commit", idnum);
1592                        hashcpy(n->sha1, oe->sha1);
1593                } else if (get_sha1(from, n->sha1))
1594                        die("Invalid ref name or SHA1 expression: %s", from);
1595
1596                n->next = NULL;
1597                if (list)
1598                        e->next = n;
1599                else
1600                        list = n;
1601                e = n;
1602                *count++;
1603                read_next_command();
1604        }
1605        return list;
1606}
1607
1608static void cmd_new_commit(void)
1609{
1610        struct branch *b;
1611        void *msg;
1612        size_t msglen;
1613        char *str_uq;
1614        const char *endp;
1615        char *sp;
1616        char *author = NULL;
1617        char *committer = NULL;
1618        struct hash_list *merge_list = NULL;
1619        unsigned int merge_count;
1620
1621        /* Obtain the branch name from the rest of our command */
1622        sp = strchr(command_buf.buf, ' ') + 1;
1623        str_uq = unquote_c_style(sp, &endp);
1624        if (str_uq) {
1625                if (*endp)
1626                        die("Garbage after ref in: %s", command_buf.buf);
1627                sp = str_uq;
1628        }
1629        b = lookup_branch(sp);
1630        if (!b)
1631                b = new_branch(sp);
1632        if (str_uq)
1633                free(str_uq);
1634
1635        read_next_command();
1636        cmd_mark();
1637        if (!strncmp("author ", command_buf.buf, 7)) {
1638                author = strdup(command_buf.buf);
1639                read_next_command();
1640        }
1641        if (!strncmp("committer ", command_buf.buf, 10)) {
1642                committer = strdup(command_buf.buf);
1643                read_next_command();
1644        }
1645        if (!committer)
1646                die("Expected committer but didn't get one");
1647        msg = cmd_data(&msglen);
1648        read_next_command();
1649        cmd_from(b);
1650        merge_list = cmd_merge(&merge_count);
1651
1652        /* ensure the branch is active/loaded */
1653        if (!b->branch_tree.tree || !max_active_branches) {
1654                unload_one_branch();
1655                load_branch(b);
1656        }
1657
1658        /* file_change* */
1659        for (;;) {
1660                if (1 == command_buf.len)
1661                        break;
1662                else if (!strncmp("M ", command_buf.buf, 2))
1663                        file_change_m(b);
1664                else if (!strncmp("D ", command_buf.buf, 2))
1665                        file_change_d(b);
1666                else
1667                        die("Unsupported file_change: %s", command_buf.buf);
1668                read_next_command();
1669        }
1670
1671        /* build the tree and the commit */
1672        store_tree(&b->branch_tree);
1673        hashcpy(b->branch_tree.versions[0].sha1,
1674                b->branch_tree.versions[1].sha1);
1675        size_dbuf(&new_data, 97 + msglen
1676                + merge_count * 49
1677                + (author
1678                        ? strlen(author) + strlen(committer)
1679                        : 2 * strlen(committer)));
1680        sp = new_data.buffer;
1681        sp += sprintf(sp, "tree %s\n",
1682                sha1_to_hex(b->branch_tree.versions[1].sha1));
1683        if (!is_null_sha1(b->sha1))
1684                sp += sprintf(sp, "parent %s\n", sha1_to_hex(b->sha1));
1685        while (merge_list) {
1686                struct hash_list *next = merge_list->next;
1687                sp += sprintf(sp, "parent %s\n", sha1_to_hex(merge_list->sha1));
1688                free(merge_list);
1689                merge_list = next;
1690        }
1691        if (author)
1692                sp += sprintf(sp, "%s\n", author);
1693        else
1694                sp += sprintf(sp, "author %s\n", committer + 10);
1695        sp += sprintf(sp, "%s\n\n", committer);
1696        memcpy(sp, msg, msglen);
1697        sp += msglen;
1698        if (author)
1699                free(author);
1700        free(committer);
1701        free(msg);
1702
1703        if (!store_object(OBJ_COMMIT,
1704                new_data.buffer, sp - (char*)new_data.buffer,
1705                NULL, b->sha1, next_mark))
1706                b->pack_id = pack_id;
1707        b->last_commit = object_count_by_type[OBJ_COMMIT];
1708
1709        if (branch_log) {
1710                int need_dq = quote_c_style(b->name, NULL, NULL, 0);
1711                fprintf(branch_log, "commit ");
1712                if (need_dq) {
1713                        fputc('"', branch_log);
1714                        quote_c_style(b->name, NULL, branch_log, 0);
1715                        fputc('"', branch_log);
1716                } else
1717                        fprintf(branch_log, "%s", b->name);
1718                fprintf(branch_log," :%ju %s\n",next_mark,sha1_to_hex(b->sha1));
1719        }
1720}
1721
1722static void cmd_new_tag(void)
1723{
1724        char *str_uq;
1725        const char *endp;
1726        char *sp;
1727        const char *from;
1728        char *tagger;
1729        struct branch *s;
1730        void *msg;
1731        size_t msglen;
1732        struct tag *t;
1733        uintmax_t from_mark = 0;
1734        unsigned char sha1[20];
1735
1736        /* Obtain the new tag name from the rest of our command */
1737        sp = strchr(command_buf.buf, ' ') + 1;
1738        str_uq = unquote_c_style(sp, &endp);
1739        if (str_uq) {
1740                if (*endp)
1741                        die("Garbage after tag name in: %s", command_buf.buf);
1742                sp = str_uq;
1743        }
1744        t = pool_alloc(sizeof(struct tag));
1745        t->next_tag = NULL;
1746        t->name = pool_strdup(sp);
1747        if (last_tag)
1748                last_tag->next_tag = t;
1749        else
1750                first_tag = t;
1751        last_tag = t;
1752        if (str_uq)
1753                free(str_uq);
1754        read_next_command();
1755
1756        /* from ... */
1757        if (strncmp("from ", command_buf.buf, 5))
1758                die("Expected from command, got %s", command_buf.buf);
1759
1760        from = strchr(command_buf.buf, ' ') + 1;
1761        str_uq = unquote_c_style(from, &endp);
1762        if (str_uq) {
1763                if (*endp)
1764                        die("Garbage after string in: %s", command_buf.buf);
1765                from = str_uq;
1766        }
1767
1768        s = lookup_branch(from);
1769        if (s) {
1770                hashcpy(sha1, s->sha1);
1771        } else if (*from == ':') {
1772                from_mark = strtoumax(from + 1, NULL, 10);
1773                struct object_entry *oe = find_mark(from_mark);
1774                if (oe->type != OBJ_COMMIT)
1775                        die("Mark :%ju not a commit", from_mark);
1776                hashcpy(sha1, oe->sha1);
1777        } else if (!get_sha1(from, sha1)) {
1778                unsigned long size;
1779                char *buf;
1780
1781                buf = read_object_with_reference(sha1,
1782                        type_names[OBJ_COMMIT], &size, sha1);
1783                if (!buf || size < 46)
1784                        die("Not a valid commit: %s", from);
1785                free(buf);
1786        } else
1787                die("Invalid ref name or SHA1 expression: %s", from);
1788
1789        if (str_uq)
1790                free(str_uq);
1791        read_next_command();
1792
1793        /* tagger ... */
1794        if (strncmp("tagger ", command_buf.buf, 7))
1795                die("Expected tagger command, got %s", command_buf.buf);
1796        tagger = strdup(command_buf.buf);
1797
1798        /* tag payload/message */
1799        read_next_command();
1800        msg = cmd_data(&msglen);
1801
1802        /* build the tag object */
1803        size_dbuf(&new_data, 67+strlen(t->name)+strlen(tagger)+msglen);
1804        sp = new_data.buffer;
1805        sp += sprintf(sp, "object %s\n", sha1_to_hex(sha1));
1806        sp += sprintf(sp, "type %s\n", type_names[OBJ_COMMIT]);
1807        sp += sprintf(sp, "tag %s\n", t->name);
1808        sp += sprintf(sp, "%s\n\n", tagger);
1809        memcpy(sp, msg, msglen);
1810        sp += msglen;
1811        free(tagger);
1812        free(msg);
1813
1814        if (store_object(OBJ_TAG, new_data.buffer,
1815                sp - (char*)new_data.buffer,
1816                NULL, t->sha1, 0))
1817                t->pack_id = MAX_PACK_ID;
1818        else
1819                t->pack_id = pack_id;
1820
1821        if (branch_log) {
1822                int need_dq = quote_c_style(t->name, NULL, NULL, 0);
1823                fprintf(branch_log, "tag ");
1824                if (need_dq) {
1825                        fputc('"', branch_log);
1826                        quote_c_style(t->name, NULL, branch_log, 0);
1827                        fputc('"', branch_log);
1828                } else
1829                        fprintf(branch_log, "%s", t->name);
1830                fprintf(branch_log," :%ju %s\n",from_mark,sha1_to_hex(t->sha1));
1831        }
1832}
1833
1834static void cmd_reset_branch(void)
1835{
1836        struct branch *b;
1837        char *str_uq;
1838        const char *endp;
1839        char *sp;
1840
1841        /* Obtain the branch name from the rest of our command */
1842        sp = strchr(command_buf.buf, ' ') + 1;
1843        str_uq = unquote_c_style(sp, &endp);
1844        if (str_uq) {
1845                if (*endp)
1846                        die("Garbage after ref in: %s", command_buf.buf);
1847                sp = str_uq;
1848        }
1849        b = lookup_branch(sp);
1850        if (b) {
1851                b->last_commit = 0;
1852                if (b->branch_tree.tree) {
1853                        release_tree_content_recursive(b->branch_tree.tree);
1854                        b->branch_tree.tree = NULL;
1855                }
1856        }
1857        else
1858                b = new_branch(sp);
1859        if (str_uq)
1860                free(str_uq);
1861        read_next_command();
1862        cmd_from(b);
1863}
1864
1865static void cmd_checkpoint(void)
1866{
1867        if (object_count)
1868                checkpoint();
1869        read_next_command();
1870}
1871
1872static const char fast_import_usage[] =
1873"git-fast-import [--objects=n] [--depth=n] [--active-branches=n] [--export-marks=marks.file] [--branch-log=log]";
1874
1875int main(int argc, const char **argv)
1876{
1877        int i;
1878        uintmax_t est_obj_cnt = object_entry_alloc;
1879        uintmax_t total_count, duplicate_count;
1880
1881        setup_ident();
1882        git_config(git_default_config);
1883
1884        for (i = 1; i < argc; i++) {
1885                const char *a = argv[i];
1886
1887                if (*a != '-' || !strcmp(a, "--"))
1888                        break;
1889                else if (!strncmp(a, "--objects=", 10))
1890                        est_obj_cnt = strtoumax(a + 10, NULL, 0);
1891                else if (!strncmp(a, "--max-objects-per-pack=", 23))
1892                        max_objects = strtoumax(a + 23, NULL, 0);
1893                else if (!strncmp(a, "--max-pack-size=", 16))
1894                        max_packsize = strtoumax(a + 16, NULL, 0) * 1024 * 1024;
1895                else if (!strncmp(a, "--depth=", 8))
1896                        max_depth = strtoul(a + 8, NULL, 0);
1897                else if (!strncmp(a, "--active-branches=", 18))
1898                        max_active_branches = strtoul(a + 18, NULL, 0);
1899                else if (!strncmp(a, "--export-marks=", 15))
1900                        mark_file = a + 15;
1901                else if (!strncmp(a, "--branch-log=", 13)) {
1902                        branch_log = fopen(a + 13, "w");
1903                        if (!branch_log)
1904                                die("Can't create %s: %s", a + 13, strerror(errno));
1905                }
1906                else
1907                        die("unknown option %s", a);
1908        }
1909        if (i != argc)
1910                usage(fast_import_usage);
1911
1912        alloc_objects(est_obj_cnt);
1913        strbuf_init(&command_buf);
1914
1915        atom_table = xcalloc(atom_table_sz, sizeof(struct atom_str*));
1916        branch_table = xcalloc(branch_table_sz, sizeof(struct branch*));
1917        avail_tree_table = xcalloc(avail_tree_table_sz, sizeof(struct avail_tree_content*));
1918        marks = pool_calloc(1, sizeof(struct mark_set));
1919
1920        start_packfile();
1921        for (;;) {
1922                read_next_command();
1923                if (command_buf.eof)
1924                        break;
1925                else if (!strcmp("blob", command_buf.buf))
1926                        cmd_new_blob();
1927                else if (!strncmp("commit ", command_buf.buf, 7))
1928                        cmd_new_commit();
1929                else if (!strncmp("tag ", command_buf.buf, 4))
1930                        cmd_new_tag();
1931                else if (!strncmp("reset ", command_buf.buf, 6))
1932                        cmd_reset_branch();
1933                else if (!strcmp("checkpoint", command_buf.buf))
1934                        cmd_checkpoint();
1935                else
1936                        die("Unsupported command: %s", command_buf.buf);
1937        }
1938        end_packfile();
1939
1940        dump_branches();
1941        dump_tags();
1942        unkeep_all_packs();
1943        dump_marks();
1944        if (branch_log)
1945                fclose(branch_log);
1946
1947        total_count = 0;
1948        for (i = 0; i < ARRAY_SIZE(object_count_by_type); i++)
1949                total_count += object_count_by_type[i];
1950        duplicate_count = 0;
1951        for (i = 0; i < ARRAY_SIZE(duplicate_count_by_type); i++)
1952                duplicate_count += duplicate_count_by_type[i];
1953
1954        fprintf(stderr, "%s statistics:\n", argv[0]);
1955        fprintf(stderr, "---------------------------------------------------------------------\n");
1956        fprintf(stderr, "Alloc'd objects: %10ju (%10ju overflow  )\n", alloc_count, alloc_count - est_obj_cnt);
1957        fprintf(stderr, "Total objects:   %10ju (%10ju duplicates                  )\n", total_count, duplicate_count);
1958        fprintf(stderr, "      blobs  :   %10ju (%10ju duplicates %10ju deltas)\n", object_count_by_type[OBJ_BLOB], duplicate_count_by_type[OBJ_BLOB], delta_count_by_type[OBJ_BLOB]);
1959        fprintf(stderr, "      trees  :   %10ju (%10ju duplicates %10ju deltas)\n", object_count_by_type[OBJ_TREE], duplicate_count_by_type[OBJ_TREE], delta_count_by_type[OBJ_TREE]);
1960        fprintf(stderr, "      commits:   %10ju (%10ju duplicates %10ju deltas)\n", object_count_by_type[OBJ_COMMIT], duplicate_count_by_type[OBJ_COMMIT], delta_count_by_type[OBJ_COMMIT]);
1961        fprintf(stderr, "      tags   :   %10ju (%10ju duplicates %10ju deltas)\n", object_count_by_type[OBJ_TAG], duplicate_count_by_type[OBJ_TAG], delta_count_by_type[OBJ_TAG]);
1962        fprintf(stderr, "Total branches:  %10lu (%10lu loads     )\n", branch_count, branch_load_count);
1963        fprintf(stderr, "      marks:     %10ju (%10ju unique    )\n", (((uintmax_t)1) << marks->shift) * 1024, marks_set_count);
1964        fprintf(stderr, "      atoms:     %10u\n", atom_cnt);
1965        fprintf(stderr, "Memory total:    %10ju KiB\n", (total_allocd + alloc_count*sizeof(struct object_entry))/1024);
1966        fprintf(stderr, "       pools:    %10lu KiB\n", total_allocd/1024);
1967        fprintf(stderr, "     objects:    %10ju KiB\n", (alloc_count*sizeof(struct object_entry))/1024);
1968        fprintf(stderr, "---------------------------------------------------------------------\n");
1969        pack_report();
1970        fprintf(stderr, "---------------------------------------------------------------------\n");
1971        fprintf(stderr, "\n");
1972
1973        return 0;
1974}