git/list[1] front-page[2] threads[3] people[4] search[5] about
 

Re: [RFC PATCH 10/10] pack-objects: improve partial packfile reuse

From
JTJonathan Tan <jonathantanmy@google.com>
Date
Oct 10, 2019, 23:59 UTC
Message-ID
<20191010235952.174426-1-jonathantanmy@google.com>
In-Reply-To
<20190913130226.7449-11-chriscool@tuxfamily.org>
I'm going to start with pack-bitmap.h, then builtin/pack-objects.c.
Show 5 quoted lines
>  int reuse_partial_packfile_from_bitmap(struct bitmap_index *,
>  				       struct packed_git **packfile,
> -				       uint32_t *entries, off_t *up_to);
> +				       uint32_t *entries,
> +				       struct bitmap **bitmap);

Makes sense. The existing code determines if the given packfile is suitable, and if yes, the span of the packfile to use. With this patch, we resolve to use the given packfile, and want to compute which objects to use, storing the computation result in an uncompressed bitmap. (Resolving to use the given packfile is not that much different from existing behavior, as far as I know, since we currently only consider one packfile at most anyway.)

So replacing the out param makes sense, although a more descriptive name than "bitmap" would be nice.

Skipping pack-bitmaps.c for now.
OK, builtin/pack-objects.c.
Show 10 quoted lines
> +/*
> + * Record the offsets needed in our reused packfile chunks due to
> + * "gaps" where we omitted some objects.
> + */
> +static struct reused_chunk {
> +	off_t start;
> +	off_t offset;
> +} *reused_chunks;
> +static int reused_chunks_nr;
> +static int reused_chunks_alloc;

This makes sense - offsets may be different when we omit objects from the packfile. I think this can be computed by calculating the number of zero bits between the current object's index and the nth object prior (where n is the offset) in the bitmap resulting from reuse_partial_packfile_from_bitmap() above, thus eliminating the need for this array, but I haven't tested it.

Show 70 quoted lines
> +static void write_reused_pack_one(size_t pos, struct hashfile *out,
> +				  struct pack_window **w_curs)
> +{
> +	off_t offset, next, cur;
> +	enum object_type type;
> +	unsigned long size;
>  
> +	offset = reuse_packfile->revindex[pos].offset;
> +	next = reuse_packfile->revindex[pos + 1].offset;
>  
> +	record_reused_object(offset, offset - hashfile_total(out));
>  
> +	cur = offset;
> +	type = unpack_object_header(reuse_packfile, w_curs, &cur, &size);
> +	assert(type >= 0);
>  
> +	if (type == OBJ_OFS_DELTA) {
> +		off_t base_offset;
> +		off_t fixup;
> +
> +		unsigned char header[MAX_PACK_OBJECT_HEADER];
> +		unsigned len;
> +
> +		base_offset = get_delta_base(reuse_packfile, w_curs, &cur, type, offset);
> +		assert(base_offset != 0);
> +
> +		/* Convert to REF_DELTA if we must... */
> +		if (!allow_ofs_delta) {
> +			int base_pos = find_revindex_position(reuse_packfile, base_offset);
> +			const unsigned char *base_sha1 =
> +				nth_packed_object_sha1(reuse_packfile,
> +						       reuse_packfile->revindex[base_pos].nr);
> +
> +			len = encode_in_pack_object_header(header, sizeof(header),
> +							   OBJ_REF_DELTA, size);
> +			hashwrite(out, header, len);
> +			hashwrite(out, base_sha1, 20);
> +			copy_pack_data(out, reuse_packfile, w_curs, cur, next - cur);
> +			return;
> +		}
>  
> +		/* Otherwise see if we need to rewrite the offset... */
> +		fixup = find_reused_offset(offset) -
> +			find_reused_offset(base_offset);
> +		if (fixup) {
> +			unsigned char ofs_header[10];
> +			unsigned i, ofs_len;
> +			off_t ofs = offset - base_offset - fixup;
> +
> +			len = encode_in_pack_object_header(header, sizeof(header),
> +							   OBJ_OFS_DELTA, size);
> +
> +			i = sizeof(ofs_header) - 1;
> +			ofs_header[i] = ofs & 127;
> +			while (ofs >>= 7)
> +				ofs_header[--i] = 128 | (--ofs & 127);
> +
> +			ofs_len = sizeof(ofs_header) - i;
> +
> +			if (0) {
> +				off_t expected_size = cur - offset;
> +
> +				if (len + ofs_len < expected_size) {
> +					unsigned max_pad = (len >= 4) ? 9 : 5;
> +					header[len - 1] |= 0x80;
> +					while (len < max_pad && len + ofs_len < expected_size)
> +						header[len++] = 0x80;
> +					header[len - 1] &= 0x7F;
> +				}
> +			}
This if(0) should be deleted.
Show 12 quoted lines
> +
> +			hashwrite(out, header, len);
> +			hashwrite(out, ofs_header + sizeof(ofs_header) - ofs_len, ofs_len);
> +			copy_pack_data(out, reuse_packfile, w_curs, cur, next - cur);
> +			return;
> +		}
> +
> +		/* ...otherwise we have no fixup, and can write it verbatim */
> +	}
> +
> +	copy_pack_data(out, reuse_packfile, w_curs, offset, next - offset);
> +}

I didn't look into detail, but this looks like it's writing a single object. In particular, it can convert OFS into REF, something that the existing code cannot do.

Show 25 quoted lines
> +static size_t write_reused_pack_verbatim(struct hashfile *out,
> +					 struct pack_window **w_curs)
> +{
> +	size_t pos = 0;
> +
> +	while (pos < reuse_packfile_bitmap->word_alloc &&
> +			reuse_packfile_bitmap->words[pos] == (eword_t)~0)
> +		pos++;
> +
> +	if (pos) {
> +		off_t to_write;
> +
> +		written = (pos * BITS_IN_EWORD);
> +		to_write = reuse_packfile->revindex[written].offset
> +			- sizeof(struct pack_header);
> +
> +		record_reused_object(sizeof(struct pack_header), 0);
> +		hashflush(out);
> +		copy_pack_data(out, reuse_packfile, w_curs,
> +			sizeof(struct pack_header), to_write);
>  
>  		display_progress(progress_state, written);
>  	}
> +	return pos;
> +}

I presume this optimization is needed for the case where we are using *all* objects of a packfile, as is typical during a clone.

Show 25 quoted lines
> +static void write_reused_pack(struct hashfile *f)
> +{
> +	size_t i = 0;
> +	uint32_t offset;
> +	struct pack_window *w_curs = NULL;
> +
> +	if (allow_ofs_delta)
> +		i = write_reused_pack_verbatim(f, &w_curs);
> +
> +	for (; i < reuse_packfile_bitmap->word_alloc; ++i) {
> +		eword_t word = reuse_packfile_bitmap->words[i];
> +		size_t pos = (i * BITS_IN_EWORD);
> +
> +		for (offset = 0; offset < BITS_IN_EWORD; ++offset) {
> +			if ((word >> offset) == 0)
> +				break;
> +
> +			offset += ewah_bit_ctz64(word >> offset);
> +			write_reused_pack_one(pos + offset, f, &w_curs);
> +			display_progress(progress_state, ++written);
> +		}
> +	}
>  
> +	unuse_pack(&w_curs);
>  }
I didn't look into detail, but it looks like a straightforward loop.
Show 7 quoted lines
> @@ -1002,6 +1132,10 @@ static int have_duplicate_entry(const struct object_id *oid,
>  {
>  	struct object_entry *entry;
>  
> +	if (reuse_packfile_bitmap &&
> +	    bitmap_walk_contains(bitmap_git, reuse_packfile_bitmap, oid))
> +		return 1;

Hmm...why did we previously not need to check the reuse information, but we do now? I gave the code a cursory glance but couldn't find the answer.

Show 8 quoted lines
> @@ -2571,7 +2706,9 @@ static void ll_find_deltas(struct object_entry **list, unsigned list_size,
>  
>  static int obj_is_packed(const struct object_id *oid)
>  {
> -	return !!packlist_find(&to_pack, oid, NULL);
> +	return packlist_find(&to_pack, oid, NULL) ||
> +		(reuse_packfile_bitmap &&
> +		 bitmap_walk_contains(bitmap_git, reuse_packfile_bitmap, oid));
Same question here - why do we need to check the reuse information?
Show 8 quoted lines
> @@ -3061,7 +3199,6 @@ static void loosen_unused_packed_objects(void)
>  static int pack_options_allow_reuse(void)
>  {
>  	return pack_to_stdout &&
> -	       allow_ofs_delta &&
>  	       !ignore_packed_keep_on_disk &&
>  	       !ignore_packed_keep_in_core &&
>  	       (!local || !have_non_local_packs) &&

Relaxing of the allow_ofs_delta condition - makes sense given (as above) we can convert OFS to REF.

Overall I think that this makes sense, except for my unanswered questions (and the presence of reused_chunk).

Previous: Christian CouderNext: Christian Couder
Message 23 of 31 in “Rewrite packfile reuse code”
  1. 00/10 Rewrite packfile reuse codeChristian Couder, Sep 13, 2019
  2. 01/10 builtin/pack-objects: report reused packfile objectsChristian Couder, Sep 13, 2019
  3. 02/10 packfile: expose get_delta_base()Christian Couder, Sep 13, 2019
  4. 06/10 pack-bitmap: introduce bitmap_walk_contains()Christian Couder, Sep 13, 2019
  5. 04/10 ewah/bitmap: always allocate 2 more wordsChristian Couder, Sep 13, 2019
  6. Jonathan TanOct 10, 2019
  7. Christian CouderOct 11, 2019
  8. Jeff KingOct 11, 2019
  9. 07/10 csum-file: introduce hashfile_total()Christian Couder, Sep 13, 2019
  10. 08/10 pack-objects: introduce pack.allowPackReuseChristian Couder, Sep 13, 2019
  11. Junio C HamanoSep 13, 2019
  12. 03/10 ewah/bitmap: introduce bitmap_word_alloc()Christian Couder, Sep 13, 2019
  13. 05/10 pack-bitmap: don't rely on bitmap_git->reuse_objectsChristian Couder, Sep 13, 2019
  14. Jonathan TanOct 10, 2019
  15. Christian CouderOct 11, 2019
  16. 10/10 pack-objects: improve partial packfile reuseChristian Couder, Sep 13, 2019
  17. Junio C HamanoSep 13, 2019
  18. Jeff KingSep 14, 2019
  19. Junio C HamanoSep 14, 2019
  20. Jeff KingOct 2, 2019
  21. Junio C HamanoOct 3, 2019
  22. Christian CouderOct 3, 2019
  23. Jonathan TanOct 10, 2019
  24. Christian CouderOct 11, 2019
  25. Jeff KingOct 11, 2019
  26. Jonathan TanOct 11, 2019
  27. Junio C HamanoOct 12, 2019
  28. Jeff KingOct 13, 2019
  29. Junio C HamanoOct 17, 2019
  30. Jeff KingOct 17, 2019
  31. 09/10 builtin/pack-objects: introduce obj_is_packed()Christian Couder, Sep 13, 2019

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.