Re: kernel.org and GIT tree rebuilding
From: Nicolas Pitre <hidden>
Date: 2016-06-15 22:42:00
Subsystem:
the rest · Maintainer:
Linus Torvalds
On Sun, 26 Jun 2005, Linus Torvalds wrote:
On Fri, 24 Jun 2005, Linus Torvalds wrote:quoted
yeah, it clearly needs some refining to be useful, but I think you can kind of see how it would work.Ok, here's how it works.
[...]
Nico? Chris? Interested in giving it a look? It's kind of a combination of your things, generalized and then made to have fast lookup with the index.
Wow ! Look away for a few days and when you look back your own stuff has been yanked out! But actually I like this packing thing. Certainly much nicer to work with and also more useful. And, since the pack file has its own checksum it is possible to use that pack format (without the index (which can be recreated from the pack file alone anyway) for network transfer. Here's one improvement to the pack format, breaking it early so it won't affect anyone at this point: compressed object header. Instead of the fixed 5 byte header, this patch convert it to a variable size granted most object are small enough to save on the storage of the significant size bytes which will be zero and packing the non-zero byte position with the object type. This can save up to 2% or 21KB on the test I performed with the git repository.
diff --git a/pack-objects.c b/pack-objects.c
--- a/pack-objects.c
+++ b/pack-objects.c@@ -7,7 +7,7 @@ static const char pack_usage[] = "git-pack-objects [--window=N] [--depth=N] base-name < object-list"; enum object_type { - OBJ_NONE, + OBJ_NONE = 0, OBJ_COMMIT, OBJ_TREE, OBJ_BLOB,
@@ -55,7 +55,7 @@ static unsigned long write_object(struct char type[10]; void *buf = read_sha1_file(entry->sha1, type, &size); char header[25]; - unsigned hdrlen, datalen; + unsigned hdrlen, datalen, bit; if (!buf) die("unable to read %s", sha1_to_hex(entry->sha1));
@@ -63,21 +63,33 @@ static unsigned long write_object(struct die("object %s size inconsistency (%lu vs %lu)", sha1_to_hex(entry->sha1), size, entry->size); /* - * The object header is a byte of 'type' followed by four bytes of - * length, except for deltas that has the 20 bytes of delta sha - * instead. + * The object header is one byte which low 4 bits represent the + * object type, the 4 upper bits indicates which of the following + * bytes are used to build the object size. For delta objects the + * sha1 of the reference object is also appended. */ - header[0] = ".CTB"[entry->type]; - hdrlen = 5; + header[0] = entry->type; if (entry->delta) { - header[0] = 'D'; - memcpy(header+5, entry->delta, 20); + header[0] = OBJ_DELTA; buf = delta_against(buf, size, entry); size = entry->delta_size; - hdrlen = 25; } - datalen = htonl(size); - memcpy(header+1, &datalen, 4); + hdrlen = 1; + bit = (1 << 4); + datalen = size; + do { + if (datalen & 0xff) { + header[0] |= bit; + header[hdrlen++] = datalen; + } + bit <<= 1; + datalen >>= 8; + } while (datalen); + if (entry->delta) { + memcpy(header+hdrlen, entry->delta, 20); + hdrlen += 20; + } + sha1write(f, header, hdrlen); datalen = sha1write_compressed(f, buf, size); free(buf);
diff --git a/unpack-objects.c b/unpack-objects.c
--- a/unpack-objects.c
+++ b/unpack-objects.c@@ -12,6 +12,16 @@ struct pack_entry { unsigned char sha1[20]; }; +enum object_type { + OBJ_NONE = 0, + OBJ_COMMIT, + OBJ_TREE, + OBJ_BLOB, + OBJ_DELTA +}; + +static char *type_s[] = { NULL, "commit", "tree", "blob", "delta" }; + static void *pack_base; static unsigned long pack_size; static void *index_base;
@@ -92,7 +102,7 @@ static int check_index(void) } static int unpack_non_delta_entry(struct pack_entry *entry, - int kind, + char *type, unsigned char *data, unsigned long size, unsigned long left)
@@ -101,9 +111,8 @@ static int unpack_non_delta_entry(struct z_stream stream; char *buffer; unsigned char sha1[20]; - char *type_s; - printf("%s %c %lu\n", sha1_to_hex(entry->sha1), kind, size); + printf("%s %s %lu\n", sha1_to_hex(entry->sha1), type, size); if (dry_run) return 0;
@@ -120,18 +129,12 @@ static int unpack_non_delta_entry(struct inflateEnd(&stream); if ((st != Z_STREAM_END) || stream.total_out != size) goto err_finish; - switch (kind) { - case 'C': type_s = "commit"; break; - case 'T': type_s = "tree"; break; - case 'B': type_s = "blob"; break; - default: goto err_finish; - } - if (write_sha1_file(buffer, size, type_s, sha1) < 0) + if (write_sha1_file(buffer, size, type, sha1) < 0) die("failed to write %s (%s)", - sha1_to_hex(entry->sha1), type_s); - printf("%s %s\n", sha1_to_hex(sha1), type_s); + sha1_to_hex(entry->sha1), type); + printf("%s %s\n", sha1_to_hex(sha1), type); if (memcmp(sha1, entry->sha1, 20)) - die("resulting %s have wrong SHA1", type_s); + die("resulting %s have wrong SHA1", type); finish: st = 0;
@@ -183,15 +186,13 @@ static int unpack_delta_entry(struct pac die("truncated pack file"); data = base_sha1 + 20; data_size = left - 20; - printf("%s D %lu", sha1_to_hex(entry->sha1), delta_size); + printf("%s delta %lu", sha1_to_hex(entry->sha1), delta_size); printf(" %s\n", sha1_to_hex(base_sha1)); if (dry_run) return 0; - /* pack+5 is the base sha1, unless we have it, we need to - * unpack it first. - */ + /* unless we have the base sha1, we need to unpack it first. */ if (!has_sha1_file(base_sha1)) { struct pack_entry *base; if (!find_pack_entry(base_sha1, &base))
@@ -236,7 +237,9 @@ static int unpack_delta_entry(struct pac static void unpack_entry(struct pack_entry *entry) { unsigned long offset, size, left; - unsigned char *pack; + unsigned char *pack, sizebits; + enum object_type type; + int i; /* Have we done this one already due to deltas based on it? */ if (lookup_object(entry->sha1))
@@ -246,14 +249,25 @@ static void unpack_entry(struct pack_ent if (offset > pack_size - 5) die("object offset outside of pack file"); pack = pack_base + offset; - size = (pack[1] << 24) + (pack[2] << 16) + (pack[3] << 8) + pack[4]; - left = pack_size - offset - 5; - switch (*pack) { - case 'C': case 'T': case 'B': - unpack_non_delta_entry(entry, *pack, pack+5, size, left); + sizebits = *pack++; + type = sizebits & 0x0f; + sizebits >>= 4; + i = size = 0; + while (sizebits) { + if (sizebits & 1) + size |= *pack++ << i; + i += 8; + sizebits >>= 1; + } + left = pack_size - ((void *)pack - pack_base); + switch (type) { + case OBJ_COMMIT: + case OBJ_TREE: + case OBJ_BLOB: + unpack_non_delta_entry(entry, type_s[type], pack, size, left); break; - case 'D': - unpack_delta_entry(entry, pack+5, size, left); + case OBJ_DELTA: + unpack_delta_entry(entry, pack, size, left); break; default: die("corrupted pack file");