Re: [PATCH v2 2/8] pack-write.c: prepare to write 'pack-*.rev' files
- From
Jeff King <peff@peff.net>
- Date
- Jan 22, 2021, 23:24 UTC
- Message-ID
- <YAtey9krU32mgEBV@coredump.intra.peff.net>
- In-Reply-To
- <8648c87fa71aec427dc11afcba6548fb66a1413b.1610576805.git.me@ttaylorr.com>
On Wed, Jan 13, 2021 at 05:28:11PM -0500, Taylor Blau wrote:
Show 11 quoted lines
> +static void write_rev_index_positions(struct hashfile *f,
> + struct pack_idx_entry **objects,
> + uint32_t nr_objects)
> +{
> + uint32_t *pack_order;
> + uint32_t i;
> +
> + ALLOC_ARRAY(pack_order, nr_objects);
> + for (i = 0; i < nr_objects; i++)
> + pack_order[i] = i;
> + QSORT_S(pack_order, nr_objects, pack_order_cmp, objects);qsort? Don't we have a perfectly good radix sort for this exact purpose? :)
I guess it is awkward to use because it hard-codes the assumption that we are sorting revindex_entry structs, with their offsets directly available.
We _could_ actually just generate an in-memory revindex array, and then use that to write out the .rev file. That has the nice property that we'd continue exercising the fallback code in the tests.
But a revindex_entry is much larger than the uint32_t's we need here. So we'd be incurring extra memory costs during the generation, which is probably not worth it. If we want better test coverage, we probably should explicitly run a series of tests both with and without a .rev file.
It's possible we'd still benefit from using a more generalized radix sort, but it probably isn't worth the trouble. The timings from 8b8dfd5132 (pack-revindex: radix-sort the revindex, 2013-07-11) claim a 4x speedup on sorting 3M entries (the size matters because we are comparing an O(n) sort versus an O(n log n) one). We can imagine that at 10M entries for the current kernel, it might even be 8x. But the absolute numbers are pretty small. The radix sort takes ~150ms for linux.git on my machine. At 8x, that's 1.2s. For a repack of the kernel, that is mostly a drop in the bucket. It mattered a lot more when many processes were doing it on the fly.
Show 6 quoted lines
> +static int pack_order_cmp(const void *va, const void *vb, void *ctx)
> +{
> + struct pack_idx_entry **objects = ctx;
> +
> + off_t oa = objects[*(uint32_t*)va]->offset;
> + off_t ob = objects[*(uint32_t*)vb]->offset;Dereferencing a pointer to index another array always makes me nervous that we may have a bounds problem with bogus data.
In this case we know it is OK because we filled the array ourselves with in-bound numbers in write_rev_index_positions.
> +#define RIDX_SIGNATURE 0x52494458 /* "RIDX" */ > +#define RIDX_VERSION 1
I was surprised we didn't define these already on the reading side, but it looks like we didn't. In patch 1, we probably should be checking RIDX_SIGNATURE in load_revindex_from_disk(). But much more importantly, we should be checking that we find version 1, since that's what will make it safe to later invent a version 2.
Show 13 quoted lines
> +static void write_rev_header(struct hashfile *f)
> +{
> + uint32_t oid_version;
> + switch (hash_algo_by_ptr(the_hash_algo)) {
> + case GIT_HASH_SHA1:
> + oid_version = 1;
> + break;
> + case GIT_HASH_SHA256:
> + oid_version = 2;
> + break;
> + default:
> + die("write_rev_header: unknown hash version");
> + }I forgot to comment on this in patch 1, but: I think the format is really independent of the hash size. The contents are identical for a sha-1 versus sha-256 file.
That said, I don't overly mind having a hash identifier if it might help debug things (OTOH, how the heck do you end up with one that matches the trailer's packfile but _doesn't_ match the trailer's contents?).
If we do have it, should we also be checking it in the loading function?
Show 23 quoted lines
> +const char *write_rev_file(const char *rev_name,
> + struct pack_idx_entry **objects,
> + uint32_t nr_objects,
> + const unsigned char *hash,
> + unsigned flags)
> +{
> + struct hashfile *f;
> + int fd;
> +
> + if ((flags & WRITE_REV) && (flags & WRITE_REV_VERIFY))
> + die(_("cannot both write and verify reverse index"));
> +
> + if (flags & WRITE_REV) {
> + if (!rev_name) {
> + struct strbuf tmp_file = STRBUF_INIT;
> + fd = odb_mkstemp(&tmp_file, "pack/tmp_rev_XXXXXX");
> + rev_name = strbuf_detach(&tmp_file, NULL);
> + } else {
> + unlink(rev_name);
> + fd = open(rev_name, O_CREAT|O_EXCL|O_WRONLY, 0600);
> + if (fd < 0)
> + die_errno("unable to create '%s'", rev_name);
> + }So if the caller gave us a name, we force-overwrite it. That seemed weird to me at first, but it makes sense; the atomic rename-into-place writers will not be passing in the name. And this is exactly how write_idx_file() works.
I wonder if we could factor out some of this repeated logic, but I suspect it is mostly diminishing returns. Maybe this "open a pack file for writing" could become a helper function, though.
Show 10 quoted lines
> diff --git a/pack.h b/pack.h
> index 9fc0945ac9..30439e0784 100644
> --- a/pack.h
> +++ b/pack.h
> @@ -42,6 +42,8 @@ struct pack_idx_option {
> /* flag bits */
> #define WRITE_IDX_VERIFY 01 /* verify only, do not write the idx file */
> #define WRITE_IDX_STRICT 02
> +#define WRITE_REV 04
> +#define WRITE_REV_VERIFY 010It is a little funny that the write-rev function has both WRITE_REV and WRITE_REV_VERIFY (which we must be sure are not both provided), but we do not need both for the IDX.
I thought maybe the reason is that we'd pass these flags to write_idx_file() or similar, and it would need to know whether to write just an idx, or both. That doesn't seem to happen in this patch, but maybe it does in a future one...
-Peff