From: Junio C Hamano <gitster@pobox.com>
Date: Wed, 14 Dec 2011 06:04:50 +0000 (-0800)
Subject: Merge branch 'jc/maint-pack-object-cycle' into maint
X-Git-Tag: v1.7.8.1~11
X-Git-Url: https://git.lorimer.id.au/gitweb.git/diff_plain/2e8722fc9e34a53ae19f2b60b1d3038aa2af0ae6?ds=inline;hp=-c

Merge branch 'jc/maint-pack-object-cycle' into maint

* jc/maint-pack-object-cycle:
pack-object: tolerate broken packs that have duplicated objects

Conflicts:
builtin/pack-objects.c
---

2e8722fc9e34a53ae19f2b60b1d3038aa2af0ae6
diff --combined builtin/pack-objects.c
index 558cd34bcc,5ae808b8d9..b1895aaaa1
--- a/builtin/pack-objects.c
+++ b/builtin/pack-objects.c
@@@ -51,8 -51,6 +51,8 @@@ struct object_entry 
  				       * objects against.
  				       */
  	unsigned char no_try_delta;
 +	unsigned char tagged; /* near the very tip of refs */
 +	unsigned char filled; /* assigned write-order */
  };
  
  /*
@@@ -72,7 -70,6 +72,7 @@@ static int local
  static int incremental;
  static int ignore_packed_keep;
  static int allow_ofs_delta;
 +static struct pack_idx_option pack_idx_opts;
  static const char *base_name;
  static int progress = 1;
  static int window = 10;
@@@ -98,7 -95,6 +98,7 @@@ static unsigned long window_memory_limi
   */
  static int *object_ix;
  static int object_ix_hashsz;
 +static struct object_entry *locate_object_entry(const unsigned char *sha1);
  
  /*
   * stats
@@@ -203,7 -199,6 +203,7 @@@ static void copy_pack_data(struct sha1f
  	}
  }
  
 +/* Return 0 if we will bust the pack-size limit */
  static unsigned long write_object(struct sha1file *f,
  				  struct object_entry *entry,
  				  off_t write_offset)
@@@ -409,25 -404,56 +409,56 @@@
  	return hdrlen + datalen;
  }
  
- static int write_one(struct sha1file *f,
- 			       struct object_entry *e,
- 			       off_t *offset)
+ enum write_one_status {
+ 	WRITE_ONE_SKIP = -1, /* already written */
+ 	WRITE_ONE_BREAK = 0, /* writing this will bust the limit; not written */
+ 	WRITE_ONE_WRITTEN = 1, /* normal */
+ 	WRITE_ONE_RECURSIVE = 2 /* already scheduled to be written */
+ };
+ 
+ static enum write_one_status write_one(struct sha1file *f,
+ 				       struct object_entry *e,
+ 				       off_t *offset)
  {
  	unsigned long size;
+ 	int recursing;
  
- 	/* offset is non zero if object is written already. */
- 	if (e->idx.offset || e->preferred_base)
- 		return -1;
+ 	/*
+ 	 * we set offset to 1 (which is an impossible value) to mark
+ 	 * the fact that this object is involved in "write its base
+ 	 * first before writing a deltified object" recursion.
+ 	 */
+ 	recursing = (e->idx.offset == 1);
+ 	if (recursing) {
+ 		warning("recursive delta detected for object %s",
+ 			sha1_to_hex(e->idx.sha1));
+ 		return WRITE_ONE_RECURSIVE;
+ 	} else if (e->idx.offset || e->preferred_base) {
+ 		/* offset is non zero if object is written already. */
+ 		return WRITE_ONE_SKIP;
+ 	}
  
  	/* if we are deltified, write out base object first. */
- 	if (e->delta && !write_one(f, e->delta, offset))
- 		return 0;
+ 	if (e->delta) {
+ 		e->idx.offset = 1; /* now recurse */
+ 		switch (write_one(f, e->delta, offset)) {
+ 		case WRITE_ONE_RECURSIVE:
+ 			/* we cannot depend on this one */
+ 			e->delta = NULL;
+ 			break;
+ 		default:
+ 			break;
+ 		case WRITE_ONE_BREAK:
+ 			e->idx.offset = recursing;
+ 			return WRITE_ONE_BREAK;
+ 		}
+ 	}
  
  	e->idx.offset = *offset;
  	size = write_object(f, e, *offset);
  	if (!size) {
- 		e->idx.offset = 0;
- 		return 0;
+ 		e->idx.offset = recursing;
+ 		return WRITE_ONE_BREAK;
  	}
  	written_list[nr_written++] = &e->idx;
  
@@@ -435,173 -461,9 +466,173 @@@
  	if (signed_add_overflows(*offset, size))
  		die("pack too large for current definition of off_t");
  	*offset += size;
- 	return 1;
+ 	return WRITE_ONE_WRITTEN;
  }
  
 +static int mark_tagged(const char *path, const unsigned char *sha1, int flag,
 +		       void *cb_data)
 +{
 +	unsigned char peeled[20];
 +	struct object_entry *entry = locate_object_entry(sha1);
 +
 +	if (entry)
 +		entry->tagged = 1;
 +	if (!peel_ref(path, peeled)) {
 +		entry = locate_object_entry(peeled);
 +		if (entry)
 +			entry->tagged = 1;
 +	}
 +	return 0;
 +}
 +
 +static inline void add_to_write_order(struct object_entry **wo,
 +			       unsigned int *endp,
 +			       struct object_entry *e)
 +{
 +	if (e->filled)
 +		return;
 +	wo[(*endp)++] = e;
 +	e->filled = 1;
 +}
 +
 +static void add_descendants_to_write_order(struct object_entry **wo,
 +					   unsigned int *endp,
 +					   struct object_entry *e)
 +{
 +	int add_to_order = 1;
 +	while (e) {
 +		if (add_to_order) {
 +			struct object_entry *s;
 +			/* add this node... */
 +			add_to_write_order(wo, endp, e);
 +			/* all its siblings... */
 +			for (s = e->delta_sibling; s; s = s->delta_sibling) {
 +				add_to_write_order(wo, endp, s);
 +			}
 +		}
 +		/* drop down a level to add left subtree nodes if possible */
 +		if (e->delta_child) {
 +			add_to_order = 1;
 +			e = e->delta_child;
 +		} else {
 +			add_to_order = 0;
 +			/* our sibling might have some children, it is next */
 +			if (e->delta_sibling) {
 +				e = e->delta_sibling;
 +				continue;
 +			}
 +			/* go back to our parent node */
 +			e = e->delta;
 +			while (e && !e->delta_sibling) {
 +				/* we're on the right side of a subtree, keep
 +				 * going up until we can go right again */
 +				e = e->delta;
 +			}
 +			if (!e) {
 +				/* done- we hit our original root node */
 +				return;
 +			}
 +			/* pass it off to sibling at this level */
 +			e = e->delta_sibling;
 +		}
 +	};
 +}
 +
 +static void add_family_to_write_order(struct object_entry **wo,
 +				      unsigned int *endp,
 +				      struct object_entry *e)
 +{
 +	struct object_entry *root;
 +
 +	for (root = e; root->delta; root = root->delta)
 +		; /* nothing */
 +	add_descendants_to_write_order(wo, endp, root);
 +}
 +
 +static struct object_entry **compute_write_order(void)
 +{
 +	unsigned int i, wo_end, last_untagged;
 +
 +	struct object_entry **wo = xmalloc(nr_objects * sizeof(*wo));
 +
 +	for (i = 0; i < nr_objects; i++) {
 +		objects[i].tagged = 0;
 +		objects[i].filled = 0;
 +		objects[i].delta_child = NULL;
 +		objects[i].delta_sibling = NULL;
 +	}
 +
 +	/*
 +	 * Fully connect delta_child/delta_sibling network.
 +	 * Make sure delta_sibling is sorted in the original
 +	 * recency order.
 +	 */
 +	for (i = nr_objects; i > 0;) {
 +		struct object_entry *e = &objects[--i];
 +		if (!e->delta)
 +			continue;
 +		/* Mark me as the first child */
 +		e->delta_sibling = e->delta->delta_child;
 +		e->delta->delta_child = e;
 +	}
 +
 +	/*
 +	 * Mark objects that are at the tip of tags.
 +	 */
 +	for_each_tag_ref(mark_tagged, NULL);
 +
 +	/*
 +	 * Give the objects in the original recency order until
 +	 * we see a tagged tip.
 +	 */
 +	for (i = wo_end = 0; i < nr_objects; i++) {
 +		if (objects[i].tagged)
 +			break;
 +		add_to_write_order(wo, &wo_end, &objects[i]);
 +	}
 +	last_untagged = i;
 +
 +	/*
 +	 * Then fill all the tagged tips.
 +	 */
 +	for (; i < nr_objects; i++) {
 +		if (objects[i].tagged)
 +			add_to_write_order(wo, &wo_end, &objects[i]);
 +	}
 +
 +	/*
 +	 * And then all remaining commits and tags.
 +	 */
 +	for (i = last_untagged; i < nr_objects; i++) {
 +		if (objects[i].type != OBJ_COMMIT &&
 +		    objects[i].type != OBJ_TAG)
 +			continue;
 +		add_to_write_order(wo, &wo_end, &objects[i]);
 +	}
 +
 +	/*
 +	 * And then all the trees.
 +	 */
 +	for (i = last_untagged; i < nr_objects; i++) {
 +		if (objects[i].type != OBJ_TREE)
 +			continue;
 +		add_to_write_order(wo, &wo_end, &objects[i]);
 +	}
 +
 +	/*
 +	 * Finally all the rest in really tight order
 +	 */
 +	for (i = last_untagged; i < nr_objects; i++) {
 +		if (!objects[i].filled)
 +			add_family_to_write_order(wo, &wo_end, &objects[i]);
 +	}
 +
 +	if (wo_end != nr_objects)
 +		die("ordered %u objects, expected %"PRIu32, wo_end, nr_objects);
 +
 +	return wo;
 +}
 +
  static void write_pack_file(void)
  {
  	uint32_t i = 0, j;
@@@ -610,12 -472,10 +641,12 @@@
  	struct pack_header hdr;
  	uint32_t nr_remaining = nr_result;
  	time_t last_mtime = 0;
 +	struct object_entry **write_order;
  
  	if (progress > pack_to_stdout)
  		progress_state = start_progress("Writing objects", nr_result);
  	written_list = xmalloc(nr_objects * sizeof(*written_list));
 +	write_order = compute_write_order();
  
  	do {
  		unsigned char sha1[20];
@@@ -639,8 -499,7 +670,8 @@@
  		offset = sizeof(hdr);
  		nr_written = 0;
  		for (; i < nr_objects; i++) {
 -			if (write_one(f, objects + i, &offset) == WRITE_ONE_BREAK)
 +			struct object_entry *e = write_order[i];
- 			if (!write_one(f, e, &offset))
++			if (write_one(f, e, &offset) == WRITE_ONE_BREAK)
  				break;
  			display_progress(progress_state, written);
  		}
@@@ -665,8 -524,8 +696,8 @@@
  			const char *idx_tmp_name;
  			char tmpname[PATH_MAX];
  
 -			idx_tmp_name = write_idx_file(NULL, written_list,
 -						      nr_written, sha1);
 +			idx_tmp_name = write_idx_file(NULL, written_list, nr_written,
 +						      &pack_idx_opts, sha1);
  
  			snprintf(tmpname, sizeof(tmpname), "%s-%s.pack",
  				 base_name, sha1_to_hex(sha1));
@@@ -717,7 -576,6 +748,7 @@@
  	} while (nr_remaining && i < nr_objects);
  
  	free(written_list);
 +	free(write_order);
  	stop_progress(&progress_state);
  	if (written != nr_result)
  		die("wrote %"PRIu32" objects while expecting %"PRIu32,
@@@ -806,7 -664,7 +837,7 @@@ static int no_try_delta(const char *pat
  	struct git_attr_check check[1];
  
  	setup_delta_attr_check(check);
 -	if (git_checkattr(path, ARRAY_SIZE(check), check))
 +	if (git_check_attr(path, ARRAY_SIZE(check), check))
  		return 0;
  	if (ATTR_FALSE(check->value))
  		return 1;
@@@ -840,10 -698,6 +871,10 @@@ static int add_object_entry(const unsig
  		off_t offset = find_pack_entry_one(sha1, p);
  		if (offset) {
  			if (!found_pack) {
 +				if (!is_pack_valid(p)) {
 +					warning("packfile %s cannot be accessed", p->pack_name);
 +					continue;
 +				}
  				found_offset = offset;
  				found_pack = p;
  			}
@@@ -1015,7 -869,7 +1046,7 @@@ static void add_pbase_object(struct tre
  	while (tree_entry(tree,&entry)) {
  		if (S_ISGITLINK(entry.mode))
  			continue;
 -		cmp = tree_entry_len(entry.path, entry.sha1) != cmplen ? 1 :
 +		cmp = tree_entry_len(&entry) != cmplen ? 1 :
  		      memcmp(name, entry.path, cmplen);
  		if (cmp > 0)
  			continue;
@@@ -2061,10 -1915,10 +2092,10 @@@ static int git_pack_config(const char *
  		return 0;
  	}
  	if (!strcmp(k, "pack.indexversion")) {
 -		pack_idx_default_version = git_config_int(k, v);
 -		if (pack_idx_default_version > 2)
 +		pack_idx_opts.version = git_config_int(k, v);
 +		if (pack_idx_opts.version > 2)
  			die("bad pack.indexversion=%"PRIu32,
 -				pack_idx_default_version);
 +			    pack_idx_opts.version);
  		return 0;
  	}
  	if (!strcmp(k, "pack.packsizelimit")) {
@@@ -2113,9 -1967,7 +2144,9 @@@ static void show_commit(struct commit *
  	commit->object.flags |= OBJECT_ADDED;
  }
  
 -static void show_object(struct object *obj, const struct name_path *path, const char *last)
 +static void show_object(struct object *obj,
 +			const struct name_path *path, const char *last,
 +			void *data)
  {
  	char *name = path_name(path, last);
  
@@@ -2313,7 -2165,6 +2344,7 @@@ int cmd_pack_objects(int argc, const ch
  	rp_av[1] = "--objects"; /* --thin will make it --objects-edge */
  	rp_ac = 2;
  
 +	reset_pack_idx_option(&pack_idx_opts);
  	git_config(git_pack_config, NULL);
  	if (!pack_compression_seen && core_compression_seen)
  		pack_compression_level = core_compression_level;
@@@ -2458,12 -2309,12 +2489,12 @@@
  		}
  		if (!prefixcmp(arg, "--index-version=")) {
  			char *c;
 -			pack_idx_default_version = strtoul(arg + 16, &c, 10);
 -			if (pack_idx_default_version > 2)
 +			pack_idx_opts.version = strtoul(arg + 16, &c, 10);
 +			if (pack_idx_opts.version > 2)
  				die("bad %s", arg);
  			if (*c == ',')
 -				pack_idx_off32_limit = strtoul(c+1, &c, 0);
 -			if (*c || pack_idx_off32_limit & 0x80000000)
 +				pack_idx_opts.off32_limit = strtoul(c+1, &c, 0);
 +			if (*c || pack_idx_opts.off32_limit & 0x80000000)
  				die("bad %s", arg);
  			continue;
  		}