fast-import.c 87.4 KB
Newer Older
1
/*
2
(See Documentation/git-fast-import.txt for maintained documentation.)
3 4 5 6 7
Format of STDIN stream:

  stream ::= cmd*;

  cmd ::= new_blob
8
        | new_commit
9
        | new_tag
10
        | reset_branch
11
        | checkpoint
12
        | progress
13 14
        ;

15
  new_blob ::= 'blob' lf
16
    mark?
17 18
    file_content;
  file_content ::= data;
19

20
  new_commit ::= 'commit' sp ref_str lf
21
    mark?
22 23
    ('author' (sp name)? sp '<' email '>' sp when lf)?
    'committer' (sp name)? sp '<' email '>' sp when lf
24
    commit_msg
25 26
    ('from' sp committish lf)?
    ('merge' sp committish lf)*
David Barr's avatar
David Barr committed
27
    (file_change | ls)*
28
    lf?;
29
  commit_msg ::= data;
30

David Barr's avatar
David Barr committed
31 32
  ls ::= 'ls' sp '"' quoted(path) '"' lf;

33 34 35 36 37 38
  file_change ::= file_clr
    | file_del
    | file_rnm
    | file_cpy
    | file_obm
    | file_inm;
39
  file_clr ::= 'deleteall' lf;
40
  file_del ::= 'D' sp path_str lf;
41
  file_rnm ::= 'R' sp path_str sp path_str lf;
42
  file_cpy ::= 'C' sp path_str sp path_str lf;
43 44 45
  file_obm ::= 'M' sp mode sp (hexsha1 | idnum) sp path_str lf;
  file_inm ::= 'M' sp mode sp 'inline' sp path_str lf
    data;
46 47 48
  note_obm ::= 'N' sp (hexsha1 | idnum) sp committish lf;
  note_inm ::= 'N' sp 'inline' sp committish lf
    data;
49 50

  new_tag ::= 'tag' sp tag_str lf
51
    'from' sp committish lf
52
    ('tagger' (sp name)? sp '<' email '>' sp when lf)?
53 54 55
    tag_msg;
  tag_msg ::= data;

56
  reset_branch ::= 'reset' sp ref_str lf
57
    ('from' sp committish lf)?
58
    lf?;
59

60
  checkpoint ::= 'checkpoint' lf
61
    lf?;
62

63 64 65
  progress ::= 'progress' sp not_lf* lf
    lf?;

66 67 68
     # note: the first idnum in a stream should be 1 and subsequent
     # idnums should not have gaps between values as this will cause
     # the stream parser to reserve space for the gapped values.  An
69
     # idnum can be updated in the future to a new object by issuing
70
     # a new mark directive with the old idnum.
71
     #
72
  mark ::= 'mark' sp idnum lf;
73
  data ::= (delimited_data | exact_data)
74
    lf?;
75 76 77 78 79 80

    # note: delim may be any string but must not contain lf.
    # data_line may contain any data but must not be exactly
    # delim.
  delimited_data ::= 'data' sp '<<' delim lf
    (data_line lf)*
81
    delim lf;
82 83

     # note: declen indicates the length of binary_data in bytes.
84
     # declen does not include the lf preceding the binary data.
85
     #
86 87
  exact_data ::= 'data' sp declen lf
    binary_data;
88 89 90

     # note: quoted strings are C-style quoting supporting \c for
     # common escapes of 'c' (e..g \n, \t, \\, \") or \nnn where nnn
91
     # is the signed byte value in octal.  Note that the only
92 93
     # characters which must actually be escaped to protect the
     # stream formatting is: \, " and LF.  Otherwise these values
94
     # are UTF8.
95
     #
96
  committish  ::= (ref_str | hexsha1 | sha1exp_str | idnum);
97 98 99
  ref_str     ::= ref;
  sha1exp_str ::= sha1exp;
  tag_str     ::= tag;
100
  path_str    ::= path    | '"' quoted(path)    '"' ;
101 102
  mode        ::= '100644' | '644'
                | '100755' | '755'
Junio C Hamano's avatar
Junio C Hamano committed
103
                | '120000'
104
                ;
105 106

  declen ::= # unsigned 32 bit value, ascii base10 notation;
107
  bigint ::= # unsigned integer value, ascii base10 notation;
108
  binary_data ::= # file content, not interpreted;
109

110 111 112 113
  when         ::= raw_when | rfc2822_when;
  raw_when     ::= ts sp tz;
  rfc2822_when ::= # Valid RFC 2822 date and time;

114 115
  sp ::= # ASCII space character;
  lf ::= # ASCII newline (LF) character;
116 117

     # note: a colon (':') must precede the numerical value assigned to
118
     # an idnum.  This is to distinguish it from a ref or tag name as
119
     # GIT does not permit ':' in ref or tag strings.
120
     #
121
  idnum   ::= ':' bigint;
122 123 124
  path    ::= # GIT style file path, e.g. "a/b/c";
  ref     ::= # GIT ref name, e.g. "refs/heads/MOZ_GECKO_EXPERIMENT";
  tag     ::= # GIT tag name, e.g. "FIREFOX_1_5";
125 126
  sha1exp ::= # Any valid GIT SHA1 expression;
  hexsha1 ::= # SHA1 in hexadecimal format;
127 128

     # note: name and email are UTF8 strings, however name must not
129
     # contain '<' or lf and email must not contain any of the
130
     # following: '<', '>', lf.
131
     #
132
  name  ::= # valid GIT author/committer name;
133
  email ::= # valid GIT author/committer email;
134 135
  ts    ::= # time since the epoch in seconds, ascii base10 notation;
  tz    ::= # GIT style timezone;
136

David Barr's avatar
David Barr committed
137
     # note: comments, ls and cat requests may appear anywhere
138 139 140
     # in the input, except within a data command.  Any form
     # of the data command always escapes the related input
     # from comment processing.
141 142
     #
     # In case it is not clear, the '#' that starts the comment
143
     # must be the first character on that line (an lf
144
     # preceded it).
145
     #
David Barr's avatar
David Barr committed
146

147
  cat_blob ::= 'cat-blob' sp (hexsha1 | idnum) lf;
David Barr's avatar
David Barr committed
148
  ls_tree  ::= 'ls' sp (hexsha1 | idnum) sp path_str lf;
149

150 151
  comment ::= '#' not_lf* lf;
  not_lf  ::= # Any byte that is not ASCII newline (LF);
152 153
*/

154 155 156 157
#include "builtin.h"
#include "cache.h"
#include "object.h"
#include "blob.h"
158
#include "tree.h"
159
#include "commit.h"
160 161
#include "delta.h"
#include "pack.h"
162
#include "refs.h"
163
#include "csum-file.h"
164
#include "quote.h"
165
#include "exec_cmd.h"
166
#include "dir.h"
167

168 169
#define PACK_ID_BITS 16
#define MAX_PACK_ID ((1<<PACK_ID_BITS)-1)
170 171
#define DEPTH_BITS 13
#define MAX_DEPTH ((1<<DEPTH_BITS)-1)
172

173 174 175 176 177
/*
 * We abuse the setuid bit on directories to mean "do not delta".
 */
#define NO_DELTA S_ISUID

178
struct object_entry {
179
	struct pack_idx_entry idx;
180
	struct object_entry *next;
181 182 183
	uint32_t type : TYPE_BITS,
		pack_id : PACK_ID_BITS,
		depth : DEPTH_BITS;
184 185
};

186
struct object_entry_pool {
187
	struct object_entry_pool *next_pool;
188 189
	struct object_entry *next_free;
	struct object_entry *end;
190
	struct object_entry entries[FLEX_ARRAY]; /* more */
191 192
};

193
struct mark_set {
194 195 196 197
	union {
		struct object_entry *marked[1024];
		struct mark_set *sets[1024];
	} data;
198
	unsigned int shift;
199 200
};

201
struct last_object {
Pierre Habouzit's avatar
Pierre Habouzit committed
202
	struct strbuf data;
203
	off_t offset;
204
	unsigned int depth;
Pierre Habouzit's avatar
Pierre Habouzit committed
205
	unsigned no_swap : 1;
206 207
};

208
struct mem_pool {
209 210 211
	struct mem_pool *next_pool;
	char *next_free;
	char *end;
212
	uintmax_t space[FLEX_ARRAY]; /* more */
213 214
};

215
struct atom_str {
216
	struct atom_str *next_atom;
217
	unsigned short str_len;
218 219 220 221
	char str_dat[FLEX_ARRAY]; /* more */
};

struct tree_content;
222
struct tree_entry {
223
	struct tree_content *tree;
224
	struct atom_str *name;
225
	struct tree_entry_ms {
226
		uint16_t mode;
227 228
		unsigned char sha1[20];
	} versions[2];
229 230
};

231
struct tree_content {
232 233
	unsigned int entry_capacity; /* must match avail_tree_content */
	unsigned int entry_count;
234
	unsigned int delta_depth;
235 236 237
	struct tree_entry *entries[FLEX_ARRAY]; /* more */
};

238
struct avail_tree_content {
239 240
	unsigned int entry_capacity; /* must match tree_content */
	struct avail_tree_content *next_avail;
241 242
};

243
struct branch {
244 245
	struct branch *table_next_branch;
	struct branch *active_next_branch;
246
	const char *name;
247
	struct tree_entry branch_tree;
248
	uintmax_t last_commit;
249
	uintmax_t num_notes;
250 251
	unsigned active : 1;
	unsigned pack_id : PACK_ID_BITS;
252
	unsigned char sha1[20];
253 254
};

255
struct tag {
256 257
	struct tag *next_tag;
	const char *name;
258
	unsigned int pack_id;
259 260 261
	unsigned char sha1[20];
};

262
struct hash_list {
263 264 265
	struct hash_list *next;
	unsigned char sha1[20];
};
266

267 268 269
typedef enum {
	WHENSPEC_RAW = 1,
	WHENSPEC_RFC2822,
270
	WHENSPEC_NOW
271 272
} whenspec_type;

273
struct recent_command {
274 275 276 277 278
	struct recent_command *prev;
	struct recent_command *next;
	char *buf;
};

279
/* Configured limits on output */
280
static unsigned long max_depth = 10;
281
static off_t max_packsize;
282
static int force_update;
283 284
static int pack_compression_level = Z_DEFAULT_COMPRESSION;
static int pack_compression_seen;
285 286 287 288 289 290 291

/* Stats and misc. counters */
static uintmax_t alloc_count;
static uintmax_t marks_set_count;
static uintmax_t object_count_by_type[1 << TYPE_BITS];
static uintmax_t duplicate_count_by_type[1 << TYPE_BITS];
static uintmax_t delta_count_by_type[1 << TYPE_BITS];
292
static uintmax_t delta_count_attempts_by_type[1 << TYPE_BITS];
293
static unsigned long object_count;
294
static unsigned long branch_count;
295
static unsigned long branch_load_count;
296
static int failure;
297
static FILE *pack_edges;
298
static unsigned int show_stats = 1;
299 300
static int global_argc;
static const char **global_argv;
301

302 303 304 305 306
/* Memory pools */
static size_t mem_pool_alloc = 2*1024*1024 - sizeof(struct mem_pool);
static size_t total_allocd;
static struct mem_pool *mem_pool;

307
/* Atom management */
308 309 310 311 312
static unsigned int atom_table_sz = 4451;
static unsigned int atom_cnt;
static struct atom_str **atom_table;

/* The .pack file being generated */
313
static struct pack_idx_option pack_idx_opts;
314
static unsigned int pack_id;
315
static struct sha1file *pack_file;
316
static struct packed_git *pack_data;
317
static struct packed_git **all_packs;
318
static off_t pack_size;
319 320

/* Table of objects we've written. */
321
static unsigned int object_entry_alloc = 5000;
322 323
static struct object_entry_pool *blocks;
static struct object_entry *object_table[1 << 16];
324
static struct mark_set *marks;
325 326
static const char *export_marks_file;
static const char *import_marks_file;
327
static int import_marks_file_from_stream;
328
static int import_marks_file_ignore_missing;
329
static int relative_marks_paths;
330 331

/* Our last blob */
Pierre Habouzit's avatar
Pierre Habouzit committed
332
static struct last_object last_blob = { STRBUF_INIT, 0, 0, 0 };
333 334 335 336 337 338

/* Tree management */
static unsigned int tree_entry_alloc = 1000;
static void *avail_tree_entry;
static unsigned int avail_tree_table_sz = 100;
static struct avail_tree_content **avail_tree_table;
339 340
static struct strbuf old_tree = STRBUF_INIT;
static struct strbuf new_tree = STRBUF_INIT;
341

342
/* Branch data */
343 344 345
static unsigned long max_active_branches = 5;
static unsigned long cur_active_branches;
static unsigned long branch_table_sz = 1039;
346 347 348
static struct branch **branch_table;
static struct branch *active_branches;

349 350 351 352
/* Tag data */
static struct tag *first_tag;
static struct tag *last_tag;

353
/* Input stream parsing */
354
static whenspec_type whenspec = WHENSPEC_RAW;
355
static struct strbuf command_buf = STRBUF_INIT;
356
static int unread_command_buf;
357 358 359 360
static struct recent_command cmd_hist = {&cmd_hist, &cmd_hist, NULL};
static struct recent_command *cmd_tail = &cmd_hist;
static struct recent_command *rc_free;
static unsigned int cmd_save = 100;
361
static uintmax_t next_mark;
362
static struct strbuf new_data = STRBUF_INIT;
363
static int seen_data_command;
364
static int require_explicit_termination;
365

366 367 368
/* Signal handling */
static volatile sig_atomic_t checkpoint_requested;

369 370 371
/* Where to write output of cat-blob commands */
static int cat_blob_fd = STDOUT_FILENO;

372
static void parse_argv(void);
373
static void parse_cat_blob(void);
David Barr's avatar
David Barr committed
374
static void parse_ls(struct branch *b);
375

376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401
static void write_branch_report(FILE *rpt, struct branch *b)
{
	fprintf(rpt, "%s:\n", b->name);

	fprintf(rpt, "  status      :");
	if (b->active)
		fputs(" active", rpt);
	if (b->branch_tree.tree)
		fputs(" loaded", rpt);
	if (is_null_sha1(b->branch_tree.versions[1].sha1))
		fputs(" dirty", rpt);
	fputc('\n', rpt);

	fprintf(rpt, "  tip commit  : %s\n", sha1_to_hex(b->sha1));
	fprintf(rpt, "  old tree    : %s\n", sha1_to_hex(b->branch_tree.versions[0].sha1));
	fprintf(rpt, "  cur tree    : %s\n", sha1_to_hex(b->branch_tree.versions[1].sha1));
	fprintf(rpt, "  commit clock: %" PRIuMAX "\n", b->last_commit);

	fputs("  last pack   : ", rpt);
	if (b->pack_id < MAX_PACK_ID)
		fprintf(rpt, "%u", b->pack_id);
	fputc('\n', rpt);

	fputc('\n', rpt);
}

402 403
static void dump_marks_helper(FILE *, uintmax_t, struct mark_set *);

404
static void write_crash_report(const char *err)
405
{
406
	char *loc = git_path("fast_import_crash_%"PRIuMAX, (uintmax_t) getpid());
407 408 409
	FILE *rpt = fopen(loc, "w");
	struct branch *b;
	unsigned long lu;
410
	struct recent_command *rc;
411 412 413 414 415 416 417 418 419

	if (!rpt) {
		error("can't write crash report %s: %s", loc, strerror(errno));
		return;
	}

	fprintf(stderr, "fast-import: dumping crash report to %s\n", loc);

	fprintf(rpt, "fast-import crash report:\n");
420 421
	fprintf(rpt, "    fast-import process: %"PRIuMAX"\n", (uintmax_t) getpid());
	fprintf(rpt, "    parent process     : %"PRIuMAX"\n", (uintmax_t) getppid());
422 423 424 425
	fprintf(rpt, "    at %s\n", show_date(time(NULL), 0, DATE_LOCAL));
	fputc('\n', rpt);

	fputs("fatal: ", rpt);
426
	fputs(err, rpt);
427 428
	fputc('\n', rpt);

429 430 431 432 433 434 435 436 437 438 439 440
	fputc('\n', rpt);
	fputs("Most Recent Commands Before Crash\n", rpt);
	fputs("---------------------------------\n", rpt);
	for (rc = cmd_hist.next; rc != &cmd_hist; rc = rc->next) {
		if (rc->next == &cmd_hist)
			fputs("* ", rpt);
		else
			fputs("  ", rpt);
		fputs(rc->buf, rpt);
		fputc('\n', rpt);
	}

441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461
	fputc('\n', rpt);
	fputs("Active Branch LRU\n", rpt);
	fputs("-----------------\n", rpt);
	fprintf(rpt, "    active_branches = %lu cur, %lu max\n",
		cur_active_branches,
		max_active_branches);
	fputc('\n', rpt);
	fputs("  pos  clock name\n", rpt);
	fputs("  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n", rpt);
	for (b = active_branches, lu = 0; b; b = b->active_next_branch)
		fprintf(rpt, "  %2lu) %6" PRIuMAX" %s\n",
			++lu, b->last_commit, b->name);

	fputc('\n', rpt);
	fputs("Inactive Branches\n", rpt);
	fputs("-----------------\n", rpt);
	for (lu = 0; lu < branch_table_sz; lu++) {
		for (b = branch_table[lu]; b; b = b->table_next_branch)
			write_branch_report(rpt, b);
	}

462 463 464 465 466 467 468 469 470 471 472 473 474
	if (first_tag) {
		struct tag *tg;
		fputc('\n', rpt);
		fputs("Annotated Tags\n", rpt);
		fputs("--------------\n", rpt);
		for (tg = first_tag; tg; tg = tg->next_tag) {
			fputs(sha1_to_hex(tg->sha1), rpt);
			fputc(' ', rpt);
			fputs(tg->name, rpt);
			fputc('\n', rpt);
		}
	}

475 476 477
	fputc('\n', rpt);
	fputs("Marks\n", rpt);
	fputs("-----\n", rpt);
478 479
	if (export_marks_file)
		fprintf(rpt, "  exported to %s\n", export_marks_file);
480 481 482
	else
		dump_marks_helper(rpt, 0, marks);

483 484 485 486 487 488
	fputc('\n', rpt);
	fputs("-------------------\n", rpt);
	fputs("END OF CRASH REPORT\n", rpt);
	fclose(rpt);
}

489 490 491 492
static void end_packfile(void);
static void unkeep_all_packs(void);
static void dump_marks(void);

493 494 495
static NORETURN void die_nicely(const char *err, va_list params)
{
	static int zombie;
496
	char message[2 * PATH_MAX];
497

498
	vsnprintf(message, sizeof(message), err, params);
499
	fputs("fatal: ", stderr);
500
	fputs(message, stderr);
501 502 503 504
	fputc('\n', stderr);

	if (!zombie) {
		zombie = 1;
505
		write_crash_report(message);
506 507 508
		end_packfile();
		unkeep_all_packs();
		dump_marks();
509 510 511
	}
	exit(128);
}
512

513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538
#ifndef SIGUSR1	/* Windows, for example */

static void set_checkpoint_signal(void)
{
}

#else

static void checkpoint_signal(int signo)
{
	checkpoint_requested = 1;
}

static void set_checkpoint_signal(void)
{
	struct sigaction sa;

	memset(&sa, 0, sizeof(sa));
	sa.sa_handler = checkpoint_signal;
	sigemptyset(&sa.sa_mask);
	sa.sa_flags = SA_RESTART;
	sigaction(SIGUSR1, &sa, NULL);
}

#endif

539
static void alloc_objects(unsigned int cnt)
540
{
541
	struct object_entry_pool *b;
542

543
	b = xmalloc(sizeof(struct object_entry_pool)
544
		+ cnt * sizeof(struct object_entry));
545
	b->next_pool = blocks;
546 547 548 549 550
	b->next_free = b->entries;
	b->end = b->entries + cnt;
	blocks = b;
	alloc_count += cnt;
}
551

552
static struct object_entry *new_object(unsigned char *sha1)
553
{
554
	struct object_entry *e;
555

556
	if (blocks->next_free == blocks->end)
557
		alloc_objects(object_entry_alloc);
558

559
	e = blocks->next_free++;
560
	hashcpy(e->idx.sha1, sha1);
561
	return e;
562 563
}

564
static struct object_entry *find_object(unsigned char *sha1)
565 566 567 568
{
	unsigned int h = sha1[0] << 8 | sha1[1];
	struct object_entry *e;
	for (e = object_table[h]; e; e = e->next)
569
		if (!hashcmp(sha1, e->idx.sha1))
570 571 572 573
			return e;
	return NULL;
}

574
static struct object_entry *insert_object(unsigned char *sha1)
575 576
{
	unsigned int h = sha1[0] << 8 | sha1[1];
577
	struct object_entry *e = object_table[h];
578 579

	while (e) {
580
		if (!hashcmp(sha1, e->idx.sha1))
581 582 583 584 585
			return e;
		e = e->next;
	}

	e = new_object(sha1);
586
	e->next = object_table[h];
587
	e->idx.offset = 0;
588
	object_table[h] = e;
589 590
	return e;
}
591

592 593 594 595 596 597 598 599
static unsigned int hc_str(const char *s, size_t len)
{
	unsigned int r = 0;
	while (len-- > 0)
		r = r * 31 + *s++;
	return r;
}

600
static void *pool_alloc(size_t len)
601 602 603 604
{
	struct mem_pool *p;
	void *r;

605 606 607 608
	/* round up to a 'uintmax_t' alignment */
	if (len & (sizeof(uintmax_t) - 1))
		len += sizeof(uintmax_t) - (len & (sizeof(uintmax_t) - 1));

609 610 611 612 613 614 615 616 617 618 619 620
	for (p = mem_pool; p; p = p->next_pool)
		if ((p->end - p->next_free >= len))
			break;

	if (!p) {
		if (len >= (mem_pool_alloc/2)) {
			total_allocd += len;
			return xmalloc(len);
		}
		total_allocd += sizeof(struct mem_pool) + mem_pool_alloc;
		p = xmalloc(sizeof(struct mem_pool) + mem_pool_alloc);
		p->next_pool = mem_pool;
621
		p->next_free = (char *) p->space;
622 623 624 625 626 627 628 629 630
		p->end = p->next_free + mem_pool_alloc;
		mem_pool = p;
	}

	r = p->next_free;
	p->next_free += len;
	return r;
}

631
static void *pool_calloc(size_t count, size_t size)
632 633 634 635 636 637 638
{
	size_t len = count * size;
	void *r = pool_alloc(len);
	memset(r, 0, len);
	return r;
}

639
static char *pool_strdup(const char *s)
640 641 642 643 644 645
{
	char *r = pool_alloc(strlen(s) + 1);
	strcpy(r, s);
	return r;
}

646
static void insert_mark(uintmax_t idnum, struct object_entry *oe)
647 648 649 650 651 652 653 654 655
{
	struct mark_set *s = marks;
	while ((idnum >> s->shift) >= 1024) {
		s = pool_calloc(1, sizeof(struct mark_set));
		s->shift = marks->shift + 10;
		s->data.sets[0] = marks;
		marks = s;
	}
	while (s->shift) {
656
		uintmax_t i = idnum >> s->shift;
657 658 659 660 661 662 663 664 665 666 667 668
		idnum -= i << s->shift;
		if (!s->data.sets[i]) {
			s->data.sets[i] = pool_calloc(1, sizeof(struct mark_set));
			s->data.sets[i]->shift = s->shift - 10;
		}
		s = s->data.sets[i];
	}
	if (!s->data.marked[idnum])
		marks_set_count++;
	s->data.marked[idnum] = oe;
}

669
static struct object_entry *find_mark(uintmax_t idnum)
670
{
671
	uintmax_t orig_idnum = idnum;
672 673 674 675
	struct mark_set *s = marks;
	struct object_entry *oe = NULL;
	if ((idnum >> s->shift) < 1024) {
		while (s && s->shift) {
676
			uintmax_t i = idnum >> s->shift;
677 678 679 680 681 682 683
			idnum -= i << s->shift;
			s = s->data.sets[i];
		}
		if (s)
			oe = s->data.marked[idnum];
	}
	if (!oe)
684
		die("mark :%" PRIuMAX " not declared", orig_idnum);
685 686 687
	return oe;
}

688
static struct atom_str *to_atom(const char *s, unsigned short len)
689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706
{
	unsigned int hc = hc_str(s, len) % atom_table_sz;
	struct atom_str *c;

	for (c = atom_table[hc]; c; c = c->next_atom)
		if (c->str_len == len && !strncmp(s, c->str_dat, len))
			return c;

	c = pool_alloc(sizeof(struct atom_str) + len + 1);
	c->str_len = len;
	strncpy(c->str_dat, s, len);
	c->str_dat[len] = 0;
	c->next_atom = atom_table[hc];
	atom_table[hc] = c;
	atom_cnt++;
	return c;
}

707
static struct branch *lookup_branch(const char *name)
708 709 710 711 712 713 714 715 716 717
{
	unsigned int hc = hc_str(name, strlen(name)) % branch_table_sz;
	struct branch *b;

	for (b = branch_table[hc]; b; b = b->table_next_branch)
		if (!strcmp(name, b->name))
			return b;
	return NULL;
}

718
static struct branch *new_branch(const char *name)
719 720
{
	unsigned int hc = hc_str(name, strlen(name)) % branch_table_sz;
721
	struct branch *b = lookup_branch(name);
722 723 724

	if (b)
		die("Invalid attempt to create duplicate branch: %s", name);
725
	if (check_refname_format(name, REFNAME_ALLOW_ONELEVEL))
726
		die("Branch name doesn't conform to GIT standards: %s", name);
727 728 729 730

	b = pool_calloc(1, sizeof(struct branch));
	b->name = pool_strdup(name);
	b->table_next_branch = branch_table[hc];
731 732
	b->branch_tree.versions[0].mode = S_IFDIR;
	b->branch_tree.versions[1].mode = S_IFDIR;
733
	b->num_notes = 0;
734
	b->active = 0;
735
	b->pack_id = MAX_PACK_ID;
736 737 738 739 740 741 742 743 744 745 746
	branch_table[hc] = b;
	branch_count++;
	return b;
}

static unsigned int hc_entries(unsigned int cnt)
{
	cnt = cnt & 7 ? (cnt / 8) + 1 : cnt / 8;
	return cnt < avail_tree_table_sz ? cnt : avail_tree_table_sz - 1;
}

747
static struct tree_content *new_tree_content(unsigned int cnt)
748 749 750 751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767 768 769
{
	struct avail_tree_content *f, *l = NULL;
	struct tree_content *t;
	unsigned int hc = hc_entries(cnt);

	for (f = avail_tree_table[hc]; f; l = f, f = f->next_avail)
		if (f->entry_capacity >= cnt)
			break;

	if (f) {
		if (l)
			l->next_avail = f->next_avail;
		else
			avail_tree_table[hc] = f->next_avail;
	} else {
		cnt = cnt & 7 ? ((cnt / 8) + 1) * 8 : cnt;
		f = pool_alloc(sizeof(*t) + sizeof(t->entries[0]) * cnt);
		f->entry_capacity = cnt;
	}

	t = (struct tree_content*)f;
	t->entry_count = 0;
770
	t->delta_depth = 0;
771 772 773 774 775 776 777 778
	return t;
}

static void release_tree_entry(struct tree_entry *e);
static void release_tree_content(struct tree_content *t)
{
	struct avail_tree_content *f = (struct avail_tree_content*)t;
	unsigned int hc = hc_entries(f->entry_capacity);
779 780 781 782 783 784
	f->next_avail = avail_tree_table[hc];
	avail_tree_table[hc] = f;
}

static void release_tree_content_recursive(struct tree_content *t)
{
785 786 787
	unsigned int i;
	for (i = 0; i < t->entry_count; i++)
		release_tree_entry(t->entries[i]);
788
	release_tree_content(t);
789 790
}

791
static struct tree_content *grow_tree_content(
792 793 794 795 796
	struct tree_content *t,
	int amt)
{
	struct tree_content *r = new_tree_content(t->entry_count + amt);
	r->entry_count = t->entry_count;
797
	r->delta_depth = t->delta_depth;
798 799 800 801 802
	memcpy(r->entries,t->entries,t->entry_count*sizeof(t->entries[0]));
	release_tree_content(t);
	return r;
}

803
static struct tree_entry *new_tree_entry(void)
804 805 806 807 808
{
	struct tree_entry *e;

	if (!avail_tree_entry) {
		unsigned int n = tree_entry_alloc;
809
		total_allocd += n * sizeof(struct tree_entry);
810
		avail_tree_entry = e = xmalloc(n * sizeof(struct tree_entry));
811
		while (n-- > 1) {
812 813 814
			*((void**)e) = e + 1;
			e++;
		}
815
		*((void**)e) = NULL;
816 817 818 819 820 821 822 823 824 825
	}

	e = avail_tree_entry;
	avail_tree_entry = *((void**)e);
	return e;
}

static void release_tree_entry(struct tree_entry *e)
{
	if (e->tree)
826
		release_tree_content_recursive(e->tree);
827 828 829 830
	*((void**)e) = avail_tree_entry;
	avail_tree_entry = e;
}

831 832 833 834 835 836 837 838 839 840 841 842 843 844 845 846 847 848 849 850 851 852 853 854 855
static struct tree_content *dup_tree_content(struct tree_content *s)
{
	struct tree_content *d;
	struct tree_entry *a, *b;
	unsigned int i;

	if (!s)
		return NULL;
	d = new_tree_content(s->entry_count);
	for (i = 0; i < s->entry_count; i++) {
		a = s->entries[i];
		b = new_tree_entry();
		memcpy(b, a, sizeof(*a));
		if (a->tree && is_null_sha1(b->versions[1].sha1))
			b->tree = dup_tree_content(a->tree);
		else
			b->tree = NULL;
		d->entries[i] = b;
	}
	d->entry_count = s->entry_count;
	d->delta_depth = s->delta_depth;

	return d;
}

856
static void start_packfile(void)
857
{
858
	static char tmp_file[PATH_MAX];
859
	struct packed_git *p;
860
	struct pack_header hdr;
861
	int pack_fd;
862

863
	pack_fd = odb_mkstemp(tmp_file, sizeof(tmp_file),
864
			      "pack/tmp_pack_XXXXXX");
865 866
	p = xcalloc(1, sizeof(*p) + strlen(tmp_file) + 2);
	strcpy(p->pack_name, tmp_file);
867
	p->pack_fd = pack_fd;
868
	p->do_not_close = 1;
869
	pack_file = sha1fd(pack_fd, p->pack_name);
870 871 872 873

	hdr.hdr_signature = htonl(PACK_SIGNATURE);
	hdr.hdr_version = htonl(2);
	hdr.hdr_entries = 0;
874
	sha1write(pack_file, &hdr, sizeof(hdr));
875 876

	pack_data = p;
877 878
	pack_size = sizeof(hdr);
	object_count = 0;
879 880 881

	all_packs = xrealloc(all_packs, sizeof(*all_packs) * (pack_id + 1));
	all_packs[pack_id] = p;
882 883
}

884
static const char *create_index(void)
885
{
886 887 888
	const char *tmpfile;
	struct pack_idx_entry **idx, **c, **last;
	struct object_entry *e;
889 890
	struct object_entry_pool *o;

891 892
	/* Build the table of object IDs. */
	idx = xmalloc(object_count * sizeof(*idx));
893 894
	c = idx;
	for (o = blocks; o; o = o->next_pool)
895 896
		for (e = o->next_free; e-- != o->entries;)
			if (pack_id == e->pack_id)
897
				*c++ = &e->idx;
898
	last = idx + object_count;
899 900
	if (c != last)
		die("internal consistency error creating the index");
901

902
	tmpfile = write_idx_file(NULL, idx, object_count, &pack_idx_opts, pack_data->sha1);
903
	free(idx);
904 905 906
	return tmpfile;
}

907
static char *keep_pack(const char *curr_index_name)
908 909
{
	static char name[PATH_MAX];
910
	static const char *keep_msg = "fast-import";
911 912
	int keep_fd;

913
	keep_fd = odb_pack_keep(name, sizeof(name), pack_data->sha1);
914
	if (keep_fd < 0)
915
		die_errno("cannot create keep file");
916 917
	write_or_die(keep_fd, keep_msg, strlen(keep_msg));
	if (close(keep_fd))
918
		die_errno("failed to write keep file");
919 920 921 922 923 924 925 926 927 928

	snprintf(name, sizeof(name), "%s/pack/pack-%s.pack",
		 get_object_directory(), sha1_to_hex(pack_data->sha1));
	if (move_temp_to_file(pack_data->pack_name, name))
		die("cannot store pack file");

	snprintf(name, sizeof(name), "%s/pack/pack-%s.idx",
		 get_object_directory(), sha1_to_hex(pack_data->sha1));
	if (move_temp_to_file(curr_index_name, name))
		die("cannot store index file");
929
	free((void *)curr_index_name);
930 931 932
	return name;
}

933
static void unkeep_all_packs(void)
934 935 936 937 938 939 940 941
{
	static char name[PATH_MAX];
	int k;

	for (k = 0; k < pack_id; k++) {
		struct packed_git *p = all_packs[k];
		snprintf(name, sizeof(name), "%s/pack/pack-%s.keep",
			 get_object_directory(), sha1_to_hex(p->sha1));
942
		unlink_or_warn(name);
943
	}
944 945
}

946
static void end_packfile(void)
947
{
948 949
	struct packed_git *old_p = pack_data, *new_p;

950
	clear_delta_base_cache();
951
	if (object_count) {
952
		unsigned char cur_pack_sha1[20];
953
		char *idx_name;
954 955 956
		int i;
		struct branch *b;
		struct tag *t;
957

958
		close_pack_windows(pack_data);
959
		sha1close(pack_file, cur_pack_sha1, 0);
960
		fixup_pack_header_footer(pack_data->pack_fd, pack_data->sha1,
961
				    pack_data->pack_name, object_count,
962
				    cur_pack_sha1, pack_size);
963
		close(pack_data->pack_fd);
964
		idx_name = keep_pack(create_index());
965

966
		/* Register the packfile with core git's machinery. */
967 968 969
		new_p = add_packed_git(idx_name, strlen(idx_name), 1);
		if (!new_p)
			die("core git rejected index %s", idx_name);
970
		all_packs[pack_id] = new_p;
971
		install_packed_git(new_p);
972 973

		/* Print the boundary */
974 975 976 977 978 979 980
		if (pack_edges) {
			fprintf(pack_edges, "%s:", new_p->pack_name);
			for (i = 0; i < branch_table_sz; i++) {
				for (b = branch_table[i]; b; b = b->table_next_branch) {
					if (b->pack_id == pack_id)
						fprintf(pack_edges, " %s", sha1_to_hex(b->sha1));
				}
981
			}
982 983 984 985 986 987
			for (t = first_tag; t; t = t->next_tag) {
				if (t->pack_id == pack_id)
					fprintf(pack_edges, " %s", sha1_to_hex(t->sha1));
			}
			fputc('\n', pack_edges);
			fflush(pack_edges);
988 989 990
		}

		pack_id++;
991
	}
992 993
	else {
		close(old_p->pack_fd);
994
		unlink_or_warn(old_p->pack_name);
995
	}
996 997 998
	free(old_p);

	/* We can't carry a delta across packfiles. */
Pierre Habouzit's avatar
Pierre Habouzit committed
999
	strbuf_release(&last_blob.data);
1000 1001
	last_blob.offset = 0;
	last_blob.depth = 0;
1002 1003
}

1004
static void cycle_packfile(void)
1005 1006 1007 1008 1009
{
	end_packfile();
	start_packfile();
}

1010 1011
static int store_object(
	enum object_type type,
1012
	struct strbuf *dat,
1013
	struct last_object *last,
1014
	unsigned char *sha1out,
1015
	uintmax_t mark)
1016 1017
{
	void *out, *delta;
1018 1019 1020
	struct object_entry *e;
	unsigned char hdr[96];
	unsigned char sha1[20];
1021
	unsigned long hdrlen, deltalen;
1022
	git_SHA_CTX c;
1023
	git_zstream s;
1024

1025
	hdrlen = sprintf((char *)hdr,"%s %lu", typename(type),
1026
		(unsigned long)dat->len) + 1;
1027 1028 1029 1030
	git_SHA1_Init(&c);
	git_SHA1_Update(&