From df6d61017a17efe67e4709028fea8e820b5efc5e Mon Sep 17 00:00:00 2001 From: Junio C Hamano Date: Fri, 1 Sep 2006 15:05:12 -0700 Subject: pack-objects: re-validate data we copy from elsewhere. When reusing data from an existing pack and from a new style loose objects, we used to just copy it staight into the resulting pack. Instead make sure they are not corrupt, but do so only when we are not streaming to stdout, in which case the receiving end will do the validation either by unpacking the stream or by constructing the .idx file. Signed-off-by: Junio C Hamano --- builtin-pack-objects.c | 67 +++++++++++++++++++++++++++++++++++++++++++++++--- 1 file changed, 63 insertions(+), 4 deletions(-) (limited to 'builtin-pack-objects.c') diff --git a/builtin-pack-objects.c b/builtin-pack-objects.c index 46f524dfc..11cc3c89f 100644 --- a/builtin-pack-objects.c +++ b/builtin-pack-objects.c @@ -65,6 +65,7 @@ static unsigned char pack_file_sha1[20]; static int progress = 1; static volatile sig_atomic_t progress_update; static int window = 10; +static int pack_to_stdout; /* * The object names in objects array are hashed with this hashtable, @@ -242,6 +243,58 @@ static int encode_header(enum object_type type, unsigned long size, unsigned cha return n; } +static int revalidate_one(struct object_entry *entry, + void *data, char *type, unsigned long size) +{ + int err; + if (!data) + return -1; + if (size != entry->size) + return -1; + err = check_sha1_signature(entry->sha1, data, size, + type_names[entry->type]); + free(data); + return err; +} + +/* + * we are going to reuse the existing pack entry data. make + * sure it is not corrupt. + */ +static int revalidate_pack_entry(struct object_entry *entry) +{ + void *data; + char type[20]; + unsigned long size; + struct pack_entry e; + + if (pack_to_stdout) + return 0; + + e.p = entry->in_pack; + e.offset = entry->in_pack_offset; + + /* the caller has already called use_packed_git() for us */ + data = unpack_entry_gently(&e, type, &size); + return revalidate_one(entry, data, type, size); +} + +static int revalidate_loose_object(struct object_entry *entry, + unsigned char *map, + unsigned long mapsize) +{ + /* we already know this is a loose object with new type header. */ + void *data; + char type[20]; + unsigned long size; + + if (pack_to_stdout) + return 0; + + data = unpack_sha1_file(map, mapsize, type, &size); + return revalidate_one(entry, data, type, size); +} + static unsigned long write_object(struct sha1file *f, struct object_entry *entry) { @@ -276,6 +329,9 @@ static unsigned long write_object(struct sha1file *f, map = map_sha1_file(entry->sha1, &mapsize); if (map && !legacy_loose_object(map)) { /* We can copy straight into the pack file */ + if (revalidate_loose_object(entry, map, mapsize)) + die("corrupt loose object %s", + sha1_to_hex(entry->sha1)); sha1write(f, map, mapsize); munmap(map, mapsize); written++; @@ -286,7 +342,7 @@ static unsigned long write_object(struct sha1file *f, munmap(map, mapsize); } - if (! to_reuse) { + if (!to_reuse) { buf = read_sha1_file(entry->sha1, type, &size); if (!buf) die("unable to read %s", sha1_to_hex(entry->sha1)); @@ -319,6 +375,9 @@ static unsigned long write_object(struct sha1file *f, datalen = find_packed_object_size(p, entry->in_pack_offset); buf = (char *) p->pack_base + entry->in_pack_offset; + + if (revalidate_pack_entry(entry)) + die("corrupt delta in pack %s", sha1_to_hex(entry->sha1)); sha1write(f, buf, datalen); unuse_packed_git(p); hdrlen = 0; /* not really */ @@ -1163,7 +1222,7 @@ static void prepare_pack(int window, int depth) find_deltas(sorted_by_type, window+1, depth); } -static int reuse_cached_pack(unsigned char *sha1, int pack_to_stdout) +static int reuse_cached_pack(unsigned char *sha1) { static const char cache[] = "pack-cache/pack-%s.%s"; char *cached_pack, *cached_idx; @@ -1247,7 +1306,7 @@ int cmd_pack_objects(int argc, const char **argv, const char *prefix) { SHA_CTX ctx; char line[40 + 1 + PATH_MAX + 2]; - int depth = 10, pack_to_stdout = 0; + int depth = 10; struct object_entry **list; int num_preferred_base = 0; int i; @@ -1367,7 +1426,7 @@ int cmd_pack_objects(int argc, const char **argv, const char *prefix) if (progress && (nr_objects != nr_result)) fprintf(stderr, "Result has %d objects.\n", nr_result); - if (reuse_cached_pack(object_list_sha1, pack_to_stdout)) + if (reuse_cached_pack(object_list_sha1)) ; else { if (nr_result) -- cgit v1.2.1 From 7042dbf7a1e9137eb856b3b086a062561c50b8a3 Mon Sep 17 00:00:00 2001 From: Junio C Hamano Date: Sun, 3 Sep 2006 14:44:46 -0700 Subject: pack-objects: fix thinko in revalidate code When revalidating an entry from an existing pack entry->size and entry->type are not necessarily the size of the final object when the entry is deltified, but for base objects they must match. Signed-off-by: Junio C Hamano --- builtin-pack-objects.c | 13 +++++++------ 1 file changed, 7 insertions(+), 6 deletions(-) (limited to 'builtin-pack-objects.c') diff --git a/builtin-pack-objects.c b/builtin-pack-objects.c index 11cc3c89f..5e42387a4 100644 --- a/builtin-pack-objects.c +++ b/builtin-pack-objects.c @@ -247,12 +247,13 @@ static int revalidate_one(struct object_entry *entry, void *data, char *type, unsigned long size) { int err; - if (!data) - return -1; - if (size != entry->size) - return -1; - err = check_sha1_signature(entry->sha1, data, size, - type_names[entry->type]); + if ((!data) || + ((entry->type != OBJ_DELTA) && + ( (size != entry->size) || + strcmp(type_names[entry->type], type)))) + err = -1; + else + err = check_sha1_signature(entry->sha1, data, size, type); free(data); return err; } -- cgit v1.2.1 From 72518e9c2623af0b5de864a7b66208ea94aacadb Mon Sep 17 00:00:00 2001 From: Junio C Hamano Date: Sun, 3 Sep 2006 21:09:18 -0700 Subject: more lightweight revalidation while reusing deflated stream in packing When copying from an existing pack and when copying from a loose object with new style header, the code makes sure that the piece we are going to copy out inflates well and inflate() consumes the data in full while doing so. The check to see if the xdelta really apply is quite expensive as you described, because you would need to have the image of the base object which can be represented as a delta against something else. Signed-off-by: Junio C Hamano --- builtin-pack-objects.c | 81 ++++++++++++++++++++++++++++++++------------------ 1 file changed, 52 insertions(+), 29 deletions(-) (limited to 'builtin-pack-objects.c') diff --git a/builtin-pack-objects.c b/builtin-pack-objects.c index 5e42387a4..149fa2839 100644 --- a/builtin-pack-objects.c +++ b/builtin-pack-objects.c @@ -243,41 +243,61 @@ static int encode_header(enum object_type type, unsigned long size, unsigned cha return n; } -static int revalidate_one(struct object_entry *entry, - void *data, char *type, unsigned long size) +static int check_inflate(unsigned char *data, unsigned long len, unsigned long expect) { - int err; - if ((!data) || - ((entry->type != OBJ_DELTA) && - ( (size != entry->size) || - strcmp(type_names[entry->type], type)))) - err = -1; - else - err = check_sha1_signature(entry->sha1, data, size, type); - free(data); - return err; + z_stream stream; + unsigned char fakebuf[4096]; + int st; + + memset(&stream, 0, sizeof(stream)); + stream.next_in = data; + stream.avail_in = len; + stream.next_out = fakebuf; + stream.avail_out = sizeof(fakebuf); + inflateInit(&stream); + + while (1) { + st = inflate(&stream, Z_FINISH); + if (st == Z_STREAM_END || st == Z_OK) { + st = (stream.total_out == expect && + stream.total_in == len) ? 0 : -1; + break; + } + if (st != Z_BUF_ERROR) { + st = -1; + break; + } + stream.next_out = fakebuf; + stream.avail_out = sizeof(fakebuf); + } + inflateEnd(&stream); + return st; } /* * we are going to reuse the existing pack entry data. make * sure it is not corrupt. */ -static int revalidate_pack_entry(struct object_entry *entry) +static int revalidate_pack_entry(struct object_entry *entry, unsigned char *data, unsigned long len) { - void *data; - char type[20]; - unsigned long size; - struct pack_entry e; + enum object_type type; + unsigned long size, used; if (pack_to_stdout) return 0; - e.p = entry->in_pack; - e.offset = entry->in_pack_offset; - - /* the caller has already called use_packed_git() for us */ - data = unpack_entry_gently(&e, type, &size); - return revalidate_one(entry, data, type, size); + /* the caller has already called use_packed_git() for us, + * so it is safe to access the pack data from mmapped location. + * make sure the entry inflates correctly. + */ + used = unpack_object_header_gently(data, len, &type, &size); + if (!used) + return -1; + if (type == OBJ_DELTA) + used += 20; /* skip base object name */ + data += used; + len -= used; + return check_inflate(data, len, entry->size); } static int revalidate_loose_object(struct object_entry *entry, @@ -285,15 +305,18 @@ static int revalidate_loose_object(struct object_entry *entry, unsigned long mapsize) { /* we already know this is a loose object with new type header. */ - void *data; - char type[20]; - unsigned long size; + enum object_type type; + unsigned long size, used; if (pack_to_stdout) return 0; - data = unpack_sha1_file(map, mapsize, type, &size); - return revalidate_one(entry, data, type, size); + used = unpack_object_header_gently(map, mapsize, &type, &size); + if (!used) + return -1; + map += used; + mapsize -= used; + return check_inflate(map, mapsize, size); } static unsigned long write_object(struct sha1file *f, @@ -377,7 +400,7 @@ static unsigned long write_object(struct sha1file *f, datalen = find_packed_object_size(p, entry->in_pack_offset); buf = (char *) p->pack_base + entry->in_pack_offset; - if (revalidate_pack_entry(entry)) + if (revalidate_pack_entry(entry, buf, datalen)) die("corrupt delta in pack %s", sha1_to_hex(entry->sha1)); sha1write(f, buf, datalen); unuse_packed_git(p); -- cgit v1.2.1 From b5d97e6b0a044b11b409250189c61d40209065f2 Mon Sep 17 00:00:00 2001 From: Junio C Hamano Date: Mon, 4 Sep 2006 23:47:39 -0700 Subject: pack-objects: run rev-list equivalent internally. Instead of piping the rev-list output from its standard input, you can say: pack-objects --all --unpacked --revs pack and feed the rev parameters you would otherwise give the rev-list on its command line from the standard input. In other words: echo 'master..next' | pack-objects --revs pack and rev-list --objects master..next | pack-objects pack are equivalent. Signed-off-by: Junio C Hamano --- builtin-pack-objects.c | 297 +++++++++++++++++++++++++++++++++++-------------- 1 file changed, 215 insertions(+), 82 deletions(-) (limited to 'builtin-pack-objects.c') diff --git a/builtin-pack-objects.c b/builtin-pack-objects.c index 149fa2839..b6e59609e 100644 --- a/builtin-pack-objects.c +++ b/builtin-pack-objects.c @@ -9,10 +9,13 @@ #include "pack.h" #include "csum-file.h" #include "tree-walk.h" +#include "diff.h" +#include "revision.h" +#include "list-objects.h" #include #include -static const char pack_usage[] = "git-pack-objects [-q] [--no-reuse-delta] [--non-empty] [--local] [--incremental] [--window=N] [--depth=N] {--stdout | base-name} < object-list"; +static const char pack_usage[] = "git-pack-objects [-q] [--no-reuse-delta] [--non-empty] [--local] [--incremental] [--window=N] [--depth=N] {--stdout | base-name} [--revs [--unpacked | --all]* parents; parents; parents = parents->next) { + struct commit *parent = parents->item; + if (!(parent->object.flags & UNINTERESTING)) + continue; + mark_tree_uninteresting(parent->tree); + } +} + +static void mark_edges_uninteresting(struct commit_list *list) +{ + for ( ; list; list = list->next) { + struct commit *commit = list->item; + + if (commit->object.flags & UNINTERESTING) { + mark_tree_uninteresting(commit->tree); + continue; + } + mark_edge_parents_uninteresting(commit); + } +} + +static void show_commit(struct commit *commit) +{ + unsigned hash = name_hash(""); + add_object_entry(commit->object.sha1, hash, 0); +} + +static void show_object(struct object_array_entry *p) +{ + unsigned hash = name_hash(p->name); + add_object_entry(p->item->sha1, hash, 0); +} + +static void get_object_list(int unpacked, int all) +{ + struct rev_info revs; + char line[1000]; + const char *av[6]; + int ac; + int flags = 0; + + av[0] = "pack-objects"; + av[1] = "--objects"; + ac = 2; + if (unpacked) + av[ac++] = "--unpacked"; + if (all) + av[ac++] = "--all"; + av[ac++] = "--stdin"; + av[ac] = NULL; + + init_revisions(&revs, NULL); + save_commit_buffer = 0; + track_object_refs = 0; + setup_revisions(ac, av, &revs, NULL); + + /* make sure we did not get pathspecs */ + if (revs.prune_data) + die("pathspec given"); + + while (fgets(line, sizeof(line), stdin) != NULL) { + int len = strlen(line); + if (line[len - 1] == '\n') + line[--len] = 0; + if (!len) + break; + if (*line == '-') { + if (!strcmp(line, "--not")) { + flags ^= UNINTERESTING; + continue; + } + die("not a rev '%s'", line); + } + if (handle_revision_arg(line, &revs, flags, 1)) + die("bad revision '%s'", line); + } + + prepare_revision_walk(&revs); + mark_edges_uninteresting(revs.commits); + + traverse_commit_list(&revs, show_commit, show_object); +} + +int cmd_pack_objects(int argc, const char **argv, const char *prefix) +{ + SHA_CTX ctx; + int depth = 10; + struct object_entry **list; + int use_internal_rev_list = 0; + int unpacked = 0; + int all = 0; + int i; + + git_config(git_pack_config); + + progress = isatty(2); + for (i = 1; i < argc; i++) { + const char *arg = argv[i]; + + if (*arg != '-') + break; + + if (!strcmp("--non-empty", arg)) { + non_empty = 1; + continue; + } + if (!strcmp("--local", arg)) { + local = 1; + continue; + } + if (!strcmp("--progress", arg)) { + progress = 1; + continue; + } + if (!strcmp("--incremental", arg)) { + incremental = 1; + continue; + } + if (!strncmp("--window=", arg, 9)) { + char *end; + window = strtoul(arg+9, &end, 0); + if (!arg[9] || *end) + usage(pack_usage); + continue; + } + if (!strncmp("--depth=", arg, 8)) { + char *end; + depth = strtoul(arg+8, &end, 0); + if (!arg[8] || *end) + usage(pack_usage); + continue; + } + if (!strcmp("--progress", arg)) { + progress = 1; + continue; + } + if (!strcmp("-q", arg)) { + progress = 0; + continue; + } + if (!strcmp("--no-reuse-delta", arg)) { + no_reuse_delta = 1; + continue; + } + if (!strcmp("--stdout", arg)) { + pack_to_stdout = 1; + continue; + } + if (!strcmp("--revs", arg)) { + use_internal_rev_list = 1; + continue; + } + if (!strcmp("--unpacked", arg)) { + unpacked = 1; + continue; + } + if (!strcmp("--all", arg)) { + all = 1; + continue; + } + usage(pack_usage); + } + + /* Traditionally "pack-objects [options] base extra" failed; + * we would however want to take refs parameter that would + * have been given to upstream rev-list ourselves, which means + * we somehow want to say what the base name is. So the + * syntax would be: + * + * pack-objects [options] base + * + * in other words, we would treat the first non-option as the + * base_name and send everything else to the internal revision + * walker. + */ + + if (!pack_to_stdout) + base_name = argv[i++]; + + if (pack_to_stdout != !base_name) + usage(pack_usage); + + /* --unpacked and --all makes sense only with --revs */ + if (!use_internal_rev_list && (unpacked || all)) + usage(pack_usage); + + prepare_packed_git(); + + if (progress) { + fprintf(stderr, "Generating pack...\n"); + setup_progress_signal(); + } + + if (!use_internal_rev_list) + read_object_list_from_stdin(); + else + get_object_list(unpacked, all); + if (progress) fprintf(stderr, "Done counting %d objects.\n", nr_objects); sorted_by_sha = create_final_object_list(); -- cgit v1.2.1 From 8d1d8f83b5d918c6071b606e321de9c31fed9e68 Mon Sep 17 00:00:00 2001 From: Junio C Hamano Date: Wed, 6 Sep 2006 01:42:23 -0700 Subject: pack-objects: further work on internal rev-list logic. This teaches the internal rev-list logic to understand options that are needed for pack handling: --all, --unpacked, and --thin. It also moves two functions from builtin-rev-list to list-objects so that the two programs can share more code. Signed-off-by: Junio C Hamano --- builtin-pack-objects.c | 99 ++++++++++++++++++++------------------------------ 1 file changed, 39 insertions(+), 60 deletions(-) (limited to 'builtin-pack-objects.c') diff --git a/builtin-pack-objects.c b/builtin-pack-objects.c index b6e59609e..753dd9a41 100644 --- a/builtin-pack-objects.c +++ b/builtin-pack-objects.c @@ -69,6 +69,7 @@ static int progress = 1; static volatile sig_atomic_t progress_update; static int window = 10; static int pack_to_stdout; +static int num_preferred_base; /* * The object names in objects array are hashed with this hashtable, @@ -841,7 +842,7 @@ static int check_pbase_path(unsigned hash) return 0; } -static void add_preferred_base_object(char *name, unsigned hash) +static void add_preferred_base_object(const char *name, unsigned hash) { struct pbase_tree *it; int cmplen = name_cmp_len(name); @@ -870,6 +871,9 @@ static void add_preferred_base(unsigned char *sha1) unsigned long size; unsigned char tree_sha1[20]; + if (window <= num_preferred_base++) + return; + data = read_object_with_reference(sha1, tree_type, &size, tree_sha1); if (!data) return; @@ -1331,7 +1335,6 @@ static int git_pack_config(const char *k, const char *v) static void read_object_list_from_stdin(void) { - int num_preferred_base = 0; char line[40 + 1 + PATH_MAX + 2]; unsigned char sha1[20]; unsigned hash; @@ -1351,8 +1354,7 @@ static void read_object_list_from_stdin(void) if (get_sha1_hex(line+1, sha1)) die("expected edge sha1, got garbage:\n %s", line); - if (num_preferred_base++ < window) - add_preferred_base(sha1); + add_preferred_base(sha1); continue; } if (get_sha1_hex(line, sha1)) @@ -1364,71 +1366,36 @@ static void read_object_list_from_stdin(void) } } -/* copied from rev-list but needs to do things slightly differently */ -static void mark_edge_parents_uninteresting(struct commit *commit) -{ - struct commit_list *parents; - - for (parents = commit->parents; parents; parents = parents->next) { - struct commit *parent = parents->item; - if (!(parent->object.flags & UNINTERESTING)) - continue; - mark_tree_uninteresting(parent->tree); - } -} - -static void mark_edges_uninteresting(struct commit_list *list) -{ - for ( ; list; list = list->next) { - struct commit *commit = list->item; - - if (commit->object.flags & UNINTERESTING) { - mark_tree_uninteresting(commit->tree); - continue; - } - mark_edge_parents_uninteresting(commit); - } -} - static void show_commit(struct commit *commit) { unsigned hash = name_hash(""); + add_preferred_base_object("", hash); add_object_entry(commit->object.sha1, hash, 0); } static void show_object(struct object_array_entry *p) { unsigned hash = name_hash(p->name); + add_preferred_base_object(p->name, hash); add_object_entry(p->item->sha1, hash, 0); } -static void get_object_list(int unpacked, int all) +static void show_edge(struct commit *commit) +{ + add_preferred_base(commit->object.sha1); +} + +static void get_object_list(int ac, const char **av) { struct rev_info revs; char line[1000]; - const char *av[6]; - int ac; int flags = 0; - av[0] = "pack-objects"; - av[1] = "--objects"; - ac = 2; - if (unpacked) - av[ac++] = "--unpacked"; - if (all) - av[ac++] = "--all"; - av[ac++] = "--stdin"; - av[ac] = NULL; - init_revisions(&revs, NULL); save_commit_buffer = 0; track_object_refs = 0; setup_revisions(ac, av, &revs, NULL); - /* make sure we did not get pathspecs */ - if (revs.prune_data) - die("pathspec given"); - while (fgets(line, sizeof(line), stdin) != NULL) { int len = strlen(line); if (line[len - 1] == '\n') @@ -1447,8 +1414,7 @@ static void get_object_list(int unpacked, int all) } prepare_revision_walk(&revs); - mark_edges_uninteresting(revs.commits); - + mark_edges_uninteresting(revs.commits, &revs, show_edge); traverse_commit_list(&revs, show_commit, show_object); } @@ -1458,9 +1424,14 @@ int cmd_pack_objects(int argc, const char **argv, const char *prefix) int depth = 10; struct object_entry **list; int use_internal_rev_list = 0; - int unpacked = 0; - int all = 0; + int thin = 0; int i; + const char *rp_av[64]; + int rp_ac; + + rp_av[0] = "pack-objects"; + rp_av[1] = "--objects"; /* --thin will make it --objects-edge */ + rp_ac = 2; git_config(git_pack_config); @@ -1521,12 +1492,19 @@ int cmd_pack_objects(int argc, const char **argv, const char *prefix) use_internal_rev_list = 1; continue; } - if (!strcmp("--unpacked", arg)) { - unpacked = 1; + if (!strcmp("--unpacked", arg) || + !strncmp("--unpacked=", arg, 11) || + !strcmp("--all", arg)) { + use_internal_rev_list = 1; + if (ARRAY_SIZE(rp_av) - 1 <= rp_ac) + die("too many internal rev-list options"); + rp_av[rp_ac++] = arg; continue; } - if (!strcmp("--all", arg)) { - all = 1; + if (!strcmp("--thin", arg)) { + use_internal_rev_list = 1; + thin = 1; + rp_av[1] = "--objects-edge"; continue; } usage(pack_usage); @@ -1551,9 +1529,8 @@ int cmd_pack_objects(int argc, const char **argv, const char *prefix) if (pack_to_stdout != !base_name) usage(pack_usage); - /* --unpacked and --all makes sense only with --revs */ - if (!use_internal_rev_list && (unpacked || all)) - usage(pack_usage); + if (!pack_to_stdout && thin) + die("--thin cannot be used to build an indexable pack."); prepare_packed_git(); @@ -1564,8 +1541,10 @@ int cmd_pack_objects(int argc, const char **argv, const char *prefix) if (!use_internal_rev_list) read_object_list_from_stdin(); - else - get_object_list(unpacked, all); + else { + rp_av[rp_ac] = NULL; + get_object_list(rp_ac, rp_av); + } if (progress) fprintf(stderr, "Done counting %d objects.\n", nr_objects); -- cgit v1.2.1 From 4321134cd85eabc5d4d07a7ce00d4cf6a02c38fb Mon Sep 17 00:00:00 2001 From: Junio C Hamano Date: Tue, 12 Sep 2006 22:59:15 -0700 Subject: pack-objects: document --revs, --unpacked and --all. Signed-off-by: Junio C Hamano --- builtin-pack-objects.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'builtin-pack-objects.c') diff --git a/builtin-pack-objects.c b/builtin-pack-objects.c index 753dd9a41..8d7a1209d 100644 --- a/builtin-pack-objects.c +++ b/builtin-pack-objects.c @@ -15,7 +15,7 @@ #include #include -static const char pack_usage[] = "git-pack-objects [-q] [--no-reuse-delta] [--non-empty] [--local] [--incremental] [--window=N] [--depth=N] {--stdout | base-name} [--revs [--unpacked | --all]* Date: Thu, 21 Sep 2006 00:05:37 -0400 Subject: many cleanups to sha1_file.c Those cleanups are mainly to set the table for the support of deltas with base objects referenced by offsets instead of sha1. This means that many pack lookup functions are converted to take a pack/offset tuple instead of a sha1. This eliminates many struct pack_entry usages since this structure carried redundent information in many cases, and it increased stack footprint needlessly for a couple recursively called functions that used to declare a local copy of it for every recursion loop. In the process, packed_object_info_detail() has been reorganized as well so to look much saner and more amenable to deltas with offset support. Finally the appropriate adjustments have been made to functions that depend on the above changes. But there is no functionality changes yet simply some code refactoring at this point. Signed-off-by: Nicolas Pitre Signed-off-by: Junio C Hamano --- builtin-pack-objects.c | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-) (limited to 'builtin-pack-objects.c') diff --git a/builtin-pack-objects.c b/builtin-pack-objects.c index 8d7a1209d..96c069a81 100644 --- a/builtin-pack-objects.c +++ b/builtin-pack-objects.c @@ -597,15 +597,15 @@ static int add_object_entry(const unsigned char *sha1, unsigned hash, int exclud if (!exclude) { for (p = packed_git; p; p = p->next) { - struct pack_entry e; - if (find_pack_entry_one(sha1, &e, p)) { + unsigned long offset = find_pack_entry_one(sha1, p); + if (offset) { if (incremental) return 0; if (local && !p->pack_local) return 0; if (!found_pack) { - found_offset = e.offset; - found_pack = e.p; + found_offset = offset; + found_pack = p; } } } -- cgit v1.2.1 From eb32d236df0c16b936b04f0c5402addb61cdb311 Mon Sep 17 00:00:00 2001 From: Nicolas Pitre Date: Thu, 21 Sep 2006 00:06:49 -0400 Subject: introduce delta objects with offset to base This adds a new object, namely OBJ_OFS_DELTA, renames OBJ_DELTA to OBJ_REF_DELTA to better make the distinction between those two delta objects, and adds support for the handling of those new delta objects in sha1_file.c only. The OBJ_OFS_DELTA contains a relative offset from the delta object's position in a pack instead of the 20-byte SHA1 reference to identify the base object. Since the base is likely to be not so far away, the relative offset is more likely to have a smaller encoding on average than an absolute offset. And for those delta objects the base must always be stored first because there is no way to know the distance of later objects when streaming a pack. Hence this relative offset is always meant to be negative. The offset encoding is slightly denser than the one used for object size -- credits to (whoever this is) for bringing it to my attention. This allows for pack size reduction between 3.2% (Linux-2.6) to over 5% (linux-historic). Runtime pack access should be faster too since delta replay does skip a search in the pack index for each delta in a chain. Signed-off-by: Nicolas Pitre Signed-off-by: Junio C Hamano --- builtin-pack-objects.c | 16 ++++++++-------- 1 file changed, 8 insertions(+), 8 deletions(-) (limited to 'builtin-pack-objects.c') diff --git a/builtin-pack-objects.c b/builtin-pack-objects.c index 96c069a81..c62734a2a 100644 --- a/builtin-pack-objects.c +++ b/builtin-pack-objects.c @@ -232,7 +232,7 @@ static int encode_header(enum object_type type, unsigned long size, unsigned cha int n = 1; unsigned char c; - if (type < OBJ_COMMIT || type > OBJ_DELTA) + if (type < OBJ_COMMIT || type > OBJ_REF_DELTA) die("bad type %d", type); c = (type << 4) | (size & 15); @@ -297,7 +297,7 @@ static int revalidate_pack_entry(struct object_entry *entry, unsigned char *data used = unpack_object_header_gently(data, len, &type, &size); if (!used) return -1; - if (type == OBJ_DELTA) + if (type == OBJ_REF_DELTA) used += 20; /* skip base object name */ data += used; len -= used; @@ -340,7 +340,7 @@ static unsigned long write_object(struct sha1file *f, obj_type = entry->type; if (! entry->in_pack) to_reuse = 0; /* can't reuse what we don't have */ - else if (obj_type == OBJ_DELTA) + else if (obj_type == OBJ_REF_DELTA) to_reuse = 1; /* check_object() decided it for us */ else if (obj_type != entry->in_pack_type) to_reuse = 0; /* pack has delta which is unusable */ @@ -380,7 +380,7 @@ static unsigned long write_object(struct sha1file *f, if (entry->delta) { buf = delta_against(buf, size, entry); size = entry->delta_size; - obj_type = OBJ_DELTA; + obj_type = OBJ_REF_DELTA; } /* * The object header is a byte of 'type' followed by zero or @@ -409,11 +409,11 @@ static unsigned long write_object(struct sha1file *f, sha1write(f, buf, datalen); unuse_packed_git(p); hdrlen = 0; /* not really */ - if (obj_type == OBJ_DELTA) + if (obj_type == OBJ_REF_DELTA) reused_delta++; reused++; } - if (obj_type == OBJ_DELTA) + if (obj_type == OBJ_REF_DELTA) written_delta++; written++; return hdrlen + datalen; @@ -916,7 +916,7 @@ static void check_object(struct object_entry *entry) * delta. */ if (!no_reuse_delta && - entry->in_pack_type == OBJ_DELTA && + entry->in_pack_type == OBJ_REF_DELTA && (base_entry = locate_object_entry(base)) && (!base_entry->preferred_base)) { @@ -929,7 +929,7 @@ static void check_object(struct object_entry *entry) /* uncompressed size of the delta data */ entry->size = entry->delta_size = size; entry->delta = base_entry; - entry->type = OBJ_DELTA; + entry->type = OBJ_REF_DELTA; entry->delta_sibling = base_entry->delta_child; base_entry->delta_child = entry; -- cgit v1.2.1 From be6b19145f64f62790049c06320c35011f7312a7 Mon Sep 17 00:00:00 2001 From: Nicolas Pitre Date: Thu, 21 Sep 2006 00:09:44 -0400 Subject: make git-pack-objects able to create deltas with offset to base This is enabled with --delta-base-offset only, and doesn't work with pack data reuse yet. The idea is to allow for the fetch protocol to use an extension flag to notify the remote end that --delta-base-offset can be used with git-pack-objects. Eventually git-repack will always provide this flag. With this, all delta base objects are now pushed before deltas that depend on them. This is a requirements for OBJ_OFS_DELTA. This is not a requirement for OBJ_REF_DELTA but always doing so makes the code simpler. Signed-off-by: Nicolas Pitre Signed-off-by: Junio C Hamano --- builtin-pack-objects.c | 47 +++++++++++++++++++++++++++++++++-------------- 1 file changed, 33 insertions(+), 14 deletions(-) (limited to 'builtin-pack-objects.c') diff --git a/builtin-pack-objects.c b/builtin-pack-objects.c index c62734a2a..221264916 100644 --- a/builtin-pack-objects.c +++ b/builtin-pack-objects.c @@ -60,6 +60,8 @@ static int non_empty; static int no_reuse_delta; static int local; static int incremental; +static int allow_ofs_delta; + static struct object_entry **sorted_by_sha, **sorted_by_type; static struct object_entry *objects; static int nr_objects, nr_alloc, nr_result; @@ -334,9 +336,6 @@ static unsigned long write_object(struct sha1file *f, enum object_type obj_type; int to_reuse = 0; - if (entry->preferred_base) - return 0; - obj_type = entry->type; if (! entry->in_pack) to_reuse = 0; /* can't reuse what we don't have */ @@ -380,18 +379,35 @@ static unsigned long write_object(struct sha1file *f, if (entry->delta) { buf = delta_against(buf, size, entry); size = entry->delta_size; - obj_type = OBJ_REF_DELTA; + obj_type = (allow_ofs_delta && entry->delta->offset) ? + OBJ_OFS_DELTA : OBJ_REF_DELTA; } /* * The object header is a byte of 'type' followed by zero or - * more bytes of length. For deltas, the 20 bytes of delta - * sha1 follows that. + * more bytes of length. */ hdrlen = encode_header(obj_type, size, header); sha1write(f, header, hdrlen); - if (entry->delta) { - sha1write(f, entry->delta, 20); + if (obj_type == OBJ_OFS_DELTA) { + /* + * Deltas with relative base contain an additional + * encoding of the relative offset for the delta + * base from this object's position in the pack. + */ + unsigned long ofs = entry->offset - entry->delta->offset; + unsigned pos = sizeof(header) - 1; + header[pos] = ofs & 127; + while (ofs >>= 7) + header[--pos] = 128 | (--ofs & 127); + sha1write(f, header + pos, sizeof(header) - pos); + hdrlen += sizeof(header) - pos; + } else if (obj_type == OBJ_REF_DELTA) { + /* + * Deltas with a base reference contain + * an additional 20 bytes for the base sha1. + */ + sha1write(f, entry->delta->sha1, 20); hdrlen += 20; } datalen = sha1write_compressed(f, buf, size); @@ -413,7 +429,7 @@ static unsigned long write_object(struct sha1file *f, reused_delta++; reused++; } - if (obj_type == OBJ_REF_DELTA) + if (entry->delta) written_delta++; written++; return hdrlen + datalen; @@ -423,17 +439,16 @@ static unsigned long write_one(struct sha1file *f, struct object_entry *e, unsigned long offset) { - if (e->offset) + if (e->offset || e->preferred_base) /* offset starts from header size and cannot be zero * if it is written already. */ return offset; - e->offset = offset; - offset += write_object(f, e); - /* if we are deltified, write out its base object. */ + /* if we are deltified, write out its base object first. */ if (e->delta) offset = write_one(f, e->delta, offset); - return offset; + e->offset = offset; + return offset + write_object(f, e); } static void write_pack_file(void) @@ -1484,6 +1499,10 @@ int cmd_pack_objects(int argc, const char **argv, const char *prefix) no_reuse_delta = 1; continue; } + if (!strcmp("--delta-base-offset", arg)) { + allow_ofs_delta = no_reuse_delta = 1; + continue; + } if (!strcmp("--stdout", arg)) { pack_to_stdout = 1; continue; -- cgit v1.2.1 From 780e6e735be189097dad4b223d8edeb18cce1928 Mon Sep 17 00:00:00 2001 From: Nicolas Pitre Date: Fri, 22 Sep 2006 21:25:04 -0400 Subject: make pack data reuse compatible with both delta types This is the missing part to git-pack-objects allowing it to reuse delta data to/from any of the two delta types. It can reuse delta from any type, and it outputs base offsets when --allow-delta-base-offset is provided and the base is also included in the pack. Otherwise it outputs base sha1 references just like it always did. Signed-off-by: Nicolas Pitre Signed-off-by: Junio C Hamano --- builtin-pack-objects.c | 204 +++++++++++++++++++++++++++++++------------------ 1 file changed, 130 insertions(+), 74 deletions(-) (limited to 'builtin-pack-objects.c') diff --git a/builtin-pack-objects.c b/builtin-pack-objects.c index 221264916..6db97b685 100644 --- a/builtin-pack-objects.c +++ b/builtin-pack-objects.c @@ -29,6 +29,7 @@ struct object_entry { enum object_type type; enum object_type in_pack_type; /* could be delta */ unsigned long delta_size; /* delta data size (uncompressed) */ +#define in_pack_header_size delta_size /* only when reusing pack data */ struct object_entry *delta; /* delta base object */ struct packed_git *in_pack; /* already in pack */ unsigned int in_pack_offset; @@ -86,17 +87,25 @@ static int object_ix_hashsz; * Pack index for existing packs give us easy access to the offsets into * corresponding pack file where each object's data starts, but the entries * do not store the size of the compressed representation (uncompressed - * size is easily available by examining the pack entry header). We build - * a hashtable of existing packs (pack_revindex), and keep reverse index - * here -- pack index file is sorted by object name mapping to offset; this - * pack_revindex[].revindex array is an ordered list of offsets, so if you - * know the offset of an object, next offset is where its packed - * representation ends. + * size is easily available by examining the pack entry header). It is + * also rather expensive to find the sha1 for an object given its offset. + * + * We build a hashtable of existing packs (pack_revindex), and keep reverse + * index here -- pack index file is sorted by object name mapping to offset; + * this pack_revindex[].revindex array is a list of offset/index_nr pairs + * ordered by offset, so if you know the offset of an object, next offset + * is where its packed representation ends and the index_nr can be used to + * get the object sha1 from the main index. */ +struct revindex_entry { + unsigned int offset; + unsigned int nr; +}; struct pack_revindex { struct packed_git *p; - unsigned long *revindex; -} *pack_revindex = NULL; + struct revindex_entry *revindex; +}; +static struct pack_revindex *pack_revindex; static int pack_revindex_hashsz; /* @@ -143,14 +152,9 @@ static void prepare_pack_ix(void) static int cmp_offset(const void *a_, const void *b_) { - unsigned long a = *(unsigned long *) a_; - unsigned long b = *(unsigned long *) b_; - if (a < b) - return -1; - else if (a == b) - return 0; - else - return 1; + const struct revindex_entry *a = a_; + const struct revindex_entry *b = b_; + return (a->offset < b->offset) ? -1 : (a->offset > b->offset) ? 1 : 0; } /* @@ -163,25 +167,27 @@ static void prepare_pack_revindex(struct pack_revindex *rix) int i; void *index = p->index_base + 256; - rix->revindex = xmalloc(sizeof(unsigned long) * (num_ent + 1)); + rix->revindex = xmalloc(sizeof(*rix->revindex) * (num_ent + 1)); for (i = 0; i < num_ent; i++) { unsigned int hl = *((unsigned int *)((char *) index + 24*i)); - rix->revindex[i] = ntohl(hl); + rix->revindex[i].offset = ntohl(hl); + rix->revindex[i].nr = i; } /* This knows the pack format -- the 20-byte trailer * follows immediately after the last object data. */ - rix->revindex[num_ent] = p->pack_size - 20; - qsort(rix->revindex, num_ent, sizeof(unsigned long), cmp_offset); + rix->revindex[num_ent].offset = p->pack_size - 20; + rix->revindex[num_ent].nr = -1; + qsort(rix->revindex, num_ent, sizeof(*rix->revindex), cmp_offset); } -static unsigned long find_packed_object_size(struct packed_git *p, - unsigned long ofs) +static struct revindex_entry * find_packed_object(struct packed_git *p, + unsigned int ofs) { int num; int lo, hi; struct pack_revindex *rix; - unsigned long *revindex; + struct revindex_entry *revindex; num = pack_revindex_ix(p); if (num < 0) die("internal error: pack revindex uninitialized"); @@ -193,10 +199,10 @@ static unsigned long find_packed_object_size(struct packed_git *p, hi = num_packed_objects(p) + 1; do { int mi = (lo + hi) / 2; - if (revindex[mi] == ofs) { - return revindex[mi+1] - ofs; + if (revindex[mi].offset == ofs) { + return revindex + mi; } - else if (ofs < revindex[mi]) + else if (ofs < revindex[mi].offset) hi = mi; else lo = mi + 1; @@ -204,6 +210,20 @@ static unsigned long find_packed_object_size(struct packed_git *p, die("internal error: pack revindex corrupt"); } +static unsigned long find_packed_object_size(struct packed_git *p, + unsigned long ofs) +{ + struct revindex_entry *entry = find_packed_object(p, ofs); + return entry[1].offset - ofs; +} + +static unsigned char *find_packed_object_name(struct packed_git *p, + unsigned long ofs) +{ + struct revindex_entry *entry = find_packed_object(p, ofs); + return (unsigned char *)(p->index_base + 256) + 24 * entry->nr + 4; +} + static void *delta_against(void *buf, unsigned long size, struct object_entry *entry) { unsigned long othersize, delta_size; @@ -249,6 +269,10 @@ static int encode_header(enum object_type type, unsigned long size, unsigned cha return n; } +/* + * we are going to reuse the existing object data as is. make + * sure it is not corrupt. + */ static int check_inflate(unsigned char *data, unsigned long len, unsigned long expect) { z_stream stream; @@ -280,32 +304,6 @@ static int check_inflate(unsigned char *data, unsigned long len, unsigned long e return st; } -/* - * we are going to reuse the existing pack entry data. make - * sure it is not corrupt. - */ -static int revalidate_pack_entry(struct object_entry *entry, unsigned char *data, unsigned long len) -{ - enum object_type type; - unsigned long size, used; - - if (pack_to_stdout) - return 0; - - /* the caller has already called use_packed_git() for us, - * so it is safe to access the pack data from mmapped location. - * make sure the entry inflates correctly. - */ - used = unpack_object_header_gently(data, len, &type, &size); - if (!used) - return -1; - if (type == OBJ_REF_DELTA) - used += 20; /* skip base object name */ - data += used; - len -= used; - return check_inflate(data, len, entry->size); -} - static int revalidate_loose_object(struct object_entry *entry, unsigned char *map, unsigned long mapsize) @@ -339,7 +337,7 @@ static unsigned long write_object(struct sha1file *f, obj_type = entry->type; if (! entry->in_pack) to_reuse = 0; /* can't reuse what we don't have */ - else if (obj_type == OBJ_REF_DELTA) + else if (obj_type == OBJ_REF_DELTA || obj_type == OBJ_OFS_DELTA) to_reuse = 1; /* check_object() decided it for us */ else if (obj_type != entry->in_pack_type) to_reuse = 0; /* pack has delta which is unusable */ @@ -415,18 +413,38 @@ static unsigned long write_object(struct sha1file *f, } else { struct packed_git *p = entry->in_pack; - use_packed_git(p); - datalen = find_packed_object_size(p, entry->in_pack_offset); - buf = (char *) p->pack_base + entry->in_pack_offset; + if (entry->delta) { + obj_type = (allow_ofs_delta && entry->delta->offset) ? + OBJ_OFS_DELTA : OBJ_REF_DELTA; + reused_delta++; + } + hdrlen = encode_header(obj_type, entry->size, header); + sha1write(f, header, hdrlen); + if (obj_type == OBJ_OFS_DELTA) { + unsigned long ofs = entry->offset - entry->delta->offset; + unsigned pos = sizeof(header) - 1; + header[pos] = ofs & 127; + while (ofs >>= 7) + header[--pos] = 128 | (--ofs & 127); + sha1write(f, header + pos, sizeof(header) - pos); + hdrlen += sizeof(header) - pos; + } else if (obj_type == OBJ_REF_DELTA) { + sha1write(f, entry->delta->sha1, 20); + hdrlen += 20; + } - if (revalidate_pack_entry(entry, buf, datalen)) + use_packed_git(p); + buf = (char *) p->pack_base + + entry->in_pack_offset + + entry->in_pack_header_size; + datalen = find_packed_object_size(p, entry->in_pack_offset) + - entry->in_pack_header_size; +//fprintf(stderr, "reusing %d at %d header %d size %d\n", obj_type, entry->in_pack_offset, entry->in_pack_header_size, datalen); + if (!pack_to_stdout && check_inflate(buf, datalen, entry->size)) die("corrupt delta in pack %s", sha1_to_hex(entry->sha1)); sha1write(f, buf, datalen); unuse_packed_git(p); - hdrlen = 0; /* not really */ - if (obj_type == OBJ_REF_DELTA) - reused_delta++; reused++; } if (entry->delta) @@ -914,26 +932,64 @@ static void check_object(struct object_entry *entry) char type[20]; if (entry->in_pack && !entry->preferred_base) { - unsigned char base[20]; - unsigned long size; - struct object_entry *base_entry; + struct packed_git *p = entry->in_pack; + unsigned long left = p->pack_size - entry->in_pack_offset; + unsigned long size, used; + unsigned char *buf; + struct object_entry *base_entry = NULL; + + use_packed_git(p); + buf = p->pack_base; + buf += entry->in_pack_offset; /* We want in_pack_type even if we do not reuse delta. * There is no point not reusing non-delta representations. */ - check_reuse_pack_delta(entry->in_pack, - entry->in_pack_offset, - base, &size, - &entry->in_pack_type); + used = unpack_object_header_gently(buf, left, + &entry->in_pack_type, &size); + if (!used || left - used <= 20) + die("corrupt pack for %s", sha1_to_hex(entry->sha1)); /* Check if it is delta, and the base is also an object * we are going to pack. If so we will reuse the existing * delta. */ - if (!no_reuse_delta && - entry->in_pack_type == OBJ_REF_DELTA && - (base_entry = locate_object_entry(base)) && - (!base_entry->preferred_base)) { + if (!no_reuse_delta) { + unsigned char c, *base_name; + unsigned long ofs; + /* there is at least 20 bytes left in the pack */ + switch (entry->in_pack_type) { + case OBJ_REF_DELTA: + base_name = buf + used; + used += 20; + break; + case OBJ_OFS_DELTA: + c = buf[used++]; + ofs = c & 127; + while (c & 128) { + ofs += 1; + if (!ofs || ofs & ~(~0UL >> 7)) + die("delta base offset overflow in pack for %s", + sha1_to_hex(entry->sha1)); + c = buf[used++]; + ofs = (ofs << 7) + (c & 127); + } + if (ofs >= entry->in_pack_offset) + die("delta base offset out of bound for %s", + sha1_to_hex(entry->sha1)); + ofs = entry->in_pack_offset - ofs; + base_name = find_packed_object_name(p, ofs); + break; + default: + base_name = NULL; + } + if (base_name) + base_entry = locate_object_entry(base_name); + } + unuse_packed_git(p); + entry->in_pack_header_size = used; + + if (base_entry && !base_entry->preferred_base) { /* Depth value does not matter - find_deltas() * will never consider reused delta as the @@ -942,9 +998,9 @@ static void check_object(struct object_entry *entry) */ /* uncompressed size of the delta data */ - entry->size = entry->delta_size = size; + entry->size = size; entry->delta = base_entry; - entry->type = OBJ_REF_DELTA; + entry->type = entry->in_pack_type; entry->delta_sibling = base_entry->delta_child; base_entry->delta_child = entry; @@ -1500,7 +1556,7 @@ int cmd_pack_objects(int argc, const char **argv, const char *prefix) continue; } if (!strcmp("--delta-base-offset", arg)) { - allow_ofs_delta = no_reuse_delta = 1; + allow_ofs_delta = 1; continue; } if (!strcmp("--stdout", arg)) { -- cgit v1.2.1 From f130446920b550a69716346fb9a9947c04fc7f90 Mon Sep 17 00:00:00 2001 From: Nicolas Pitre Date: Wed, 27 Sep 2006 15:30:21 -0400 Subject: zap a debug remnant Signed-off-by: Nicolas Pitre Signed-off-by: Junio C Hamano --- builtin-pack-objects.c | 1 - 1 file changed, 1 deletion(-) (limited to 'builtin-pack-objects.c') diff --git a/builtin-pack-objects.c b/builtin-pack-objects.c index 6db97b685..16e98f3f3 100644 --- a/builtin-pack-objects.c +++ b/builtin-pack-objects.c @@ -440,7 +440,6 @@ static unsigned long write_object(struct sha1file *f, + entry->in_pack_header_size; datalen = find_packed_object_size(p, entry->in_pack_offset) - entry->in_pack_header_size; -//fprintf(stderr, "reusing %d at %d header %d size %d\n", obj_type, entry->in_pack_offset, entry->in_pack_header_size, datalen); if (!pack_to_stdout && check_inflate(buf, datalen, entry->size)) die("corrupt delta in pack %s", sha1_to_hex(entry->sha1)); sha1write(f, buf, datalen); -- cgit v1.2.1 From a2700696995651322796e04092bf4a4bfed31b88 Mon Sep 17 00:00:00 2001 From: Nicolas Pitre Date: Wed, 27 Sep 2006 15:42:16 -0400 Subject: allow delta data reuse even if base object is a preferred base Signed-off-by: Nicolas Pitre Signed-off-by: Junio C Hamano --- builtin-pack-objects.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'builtin-pack-objects.c') diff --git a/builtin-pack-objects.c b/builtin-pack-objects.c index 16e98f3f3..ee5f031bc 100644 --- a/builtin-pack-objects.c +++ b/builtin-pack-objects.c @@ -988,7 +988,7 @@ static void check_object(struct object_entry *entry) unuse_packed_git(p); entry->in_pack_header_size = used; - if (base_entry && !base_entry->preferred_base) { + if (base_entry) { /* Depth value does not matter - find_deltas() * will never consider reused delta as the -- cgit v1.2.1 From 63fba759bc1d9405f362e73918096815bf8e2a15 Mon Sep 17 00:00:00 2001 From: Junio C Hamano Date: Tue, 10 Oct 2006 01:06:20 -0700 Subject: pack-objects: document --delta-base-offset option Signed-off-by: Junio C Hamano --- builtin-pack-objects.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'builtin-pack-objects.c') diff --git a/builtin-pack-objects.c b/builtin-pack-objects.c index ee5f031bc..41e1e7453 100644 --- a/builtin-pack-objects.c +++ b/builtin-pack-objects.c @@ -15,7 +15,7 @@ #include #include -static const char pack_usage[] = "git-pack-objects [-q] [--no-reuse-delta] [--non-empty] [--local] [--incremental] [--window=N] [--depth=N] [--revs [--unpacked | --all]*] [--stdout | base-name] Date: Tue, 31 Oct 2006 16:58:32 -0500 Subject: make git-push a bit more verbose Currently git-push displays progress status for the local packing of objects to send, but nothing once it starts to push it over the connection. Having progress status in that later case is especially nice when pushing lots of objects over a slow network link. Signed-off-by: Nicolas Pitre Signed-off-by: Junio C Hamano --- builtin-pack-objects.c | 18 +++++++++++------- 1 file changed, 11 insertions(+), 7 deletions(-) (limited to 'builtin-pack-objects.c') diff --git a/builtin-pack-objects.c b/builtin-pack-objects.c index 41e1e7453..270bcbded 100644 --- a/builtin-pack-objects.c +++ b/builtin-pack-objects.c @@ -15,7 +15,7 @@ #include #include -static const char pack_usage[] = "git-pack-objects [-q] [--no-reuse-delta] [--delta-base-offset] [--non-empty] [--local] [--incremental] [--window=N] [--depth=N] [--revs [--unpacked | --all]*] [--stdout | base-name] "); - else { + do_progress >>= 1; + } + else f = sha1create("%s-%s.%s", base_name, sha1_to_hex(object_list_sha1), "pack"); - do_progress = progress; - } if (do_progress) fprintf(stderr, "Writing %d objects.\n", nr_result); @@ -1524,6 +1524,10 @@ int cmd_pack_objects(int argc, const char **argv, const char *prefix) progress = 1; continue; } + if (!strcmp("--all-progress", arg)) { + progress = 2; + continue; + } if (!strcmp("--incremental", arg)) { incremental = 1; continue; @@ -1641,7 +1645,7 @@ int cmd_pack_objects(int argc, const char **argv, const char *prefix) else { if (nr_result) prepare_pack(window, depth); - if (progress && pack_to_stdout) { + if (progress == 1 && pack_to_stdout) { /* the other end usually displays progress itself */ struct itimerval v = {{0,},}; setitimer(ITIMER_REAL, &v, NULL); -- cgit v1.2.1 From 231f240b63bd6cb1313e8952448b3d5b9d2fdf26 Mon Sep 17 00:00:00 2001 From: Nicolas Pitre Date: Tue, 7 Nov 2006 10:51:23 -0500 Subject: git-pack-objects progress flag documentation and cleanup This adds documentation for --progress and --all-progress, remove a duplicate --progress handling and make usage string more readable. Signed-off-by: Nicolas Pitre Signed-off-by: Junio C Hamano --- builtin-pack-objects.c | 19 ++++++++++--------- 1 file changed, 10 insertions(+), 9 deletions(-) (limited to 'builtin-pack-objects.c') diff --git a/builtin-pack-objects.c b/builtin-pack-objects.c index 270bcbded..69e5dd39c 100644 --- a/builtin-pack-objects.c +++ b/builtin-pack-objects.c @@ -15,7 +15,12 @@ #include #include -static const char pack_usage[] = "git-pack-objects [-q] [--no-reuse-delta] [--delta-base-offset] [--non-empty] [--local] [--incremental] [--window=N] [--depth=N] [--all-progress] [--revs [--unpacked | --all]*] [--stdout | base-name] Date: Tue, 14 Nov 2006 22:18:31 -0800 Subject: pack-objects: tweak "do not even attempt delta" heuristics The heuristics to give up deltification when both the source and the target are both in the same pack affects negatively when we are repacking the subset of objects in the existing pack. This caused any incremental updates to use suboptimal packs. Tweak the heuristics to avoid this problem. Signed-off-by: Junio C Hamano --- builtin-pack-objects.c | 4 +++- 1 file changed, 3 insertions(+), 1 deletion(-) (limited to 'builtin-pack-objects.c') diff --git a/builtin-pack-objects.c b/builtin-pack-objects.c index 69e5dd39c..753bcd57b 100644 --- a/builtin-pack-objects.c +++ b/builtin-pack-objects.c @@ -1176,7 +1176,9 @@ static int try_delta(struct unpacked *trg, struct unpacked *src, * on an earlier try, but only when reusing delta data. */ if (!no_reuse_delta && trg_entry->in_pack && - trg_entry->in_pack == src_entry->in_pack) + trg_entry->in_pack == src_entry->in_pack && + trg_entry->in_pack_type != OBJ_REF_DELTA && + trg_entry->in_pack_type != OBJ_OFS_DELTA) return 0; /* -- cgit v1.2.1 From 67c08ce14fb488562666ab896541ad75f1bdcca6 Mon Sep 17 00:00:00 2001 From: Nicolas Pitre Date: Wed, 29 Nov 2006 17:15:48 -0500 Subject: pack-objects: remove redundent status information The final 'nr_result' and 'written' values must always be the same otherwise we're in deep trouble. So let's remove a redundent report. And for paranoia sake let's make sure those two variables are actually equal after all objects are written (one never knows). Signed-off-by: Nicolas Pitre Signed-off-by: Junio C Hamano --- builtin-pack-objects.c | 6 ++++-- 1 file changed, 4 insertions(+), 2 deletions(-) (limited to 'builtin-pack-objects.c') diff --git a/builtin-pack-objects.c b/builtin-pack-objects.c index 753bcd57b..a2dc7d1d9 100644 --- a/builtin-pack-objects.c +++ b/builtin-pack-objects.c @@ -514,6 +514,8 @@ static void write_pack_file(void) if (do_progress) fputc('\n', stderr); done: + if (written != nr_result) + die("wrote %d objects while expecting %d", written, nr_result); sha1close(f, pack_file_sha1, 1); } @@ -1662,7 +1664,7 @@ int cmd_pack_objects(int argc, const char **argv, const char *prefix) } } if (progress) - fprintf(stderr, "Total %d, written %d (delta %d), reused %d (delta %d)\n", - nr_result, written, written_delta, reused, reused_delta); + fprintf(stderr, "Total %d (delta %d), reused %d (delta %d)\n", + written, written_delta, reused, reused_delta); return 0; } -- cgit v1.2.1 From 85023577a8f4b540aa64aa37f6f44578c0c305a3 Mon Sep 17 00:00:00 2001 From: Junio C Hamano Date: Tue, 19 Dec 2006 14:34:12 -0800 Subject: simplify inclusion of system header files. This is a mechanical clean-up of the way *.c files include system header files. (1) sources under compat/, platform sha-1 implementations, and xdelta code are exempt from the following rules; (2) the first #include must be "git-compat-util.h" or one of our own header file that includes it first (e.g. config.h, builtin.h, pkt-line.h); (3) system headers that are included in "git-compat-util.h" need not be included in individual C source files. (4) "git-compat-util.h" does not have to include subsystem specific header files (e.g. expat.h). Signed-off-by: Junio C Hamano --- builtin-pack-objects.c | 2 -- 1 file changed, 2 deletions(-) (limited to 'builtin-pack-objects.c') diff --git a/builtin-pack-objects.c b/builtin-pack-objects.c index a2dc7d1d9..807be8c3f 100644 --- a/builtin-pack-objects.c +++ b/builtin-pack-objects.c @@ -12,8 +12,6 @@ #include "diff.h" #include "revision.h" #include "list-objects.h" -#include -#include static const char pack_usage[] = "\ git-pack-objects [{ -q | --progress | --all-progress }] \n\ -- cgit v1.2.1 From 63049292e083faf80e033eba4fa43efdbac3acad Mon Sep 17 00:00:00 2001 From: Junio C Hamano Date: Mon, 18 Dec 2006 17:25:28 -0800 Subject: Teach git-repack to preserve objects referred to by reflog entries. This adds a new option --reflog to pack-objects and revision machinery; do not bother documenting it for now, since this is only useful for local repacking. When the option is passed, objects reachable from reflog entries are marked as interesting while computing the set of objects to pack. Signed-off-by: Junio C Hamano --- builtin-pack-objects.c | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-) (limited to 'builtin-pack-objects.c') diff --git a/builtin-pack-objects.c b/builtin-pack-objects.c index 807be8c3f..9e15beb3b 100644 --- a/builtin-pack-objects.c +++ b/builtin-pack-objects.c @@ -17,7 +17,7 @@ static const char pack_usage[] = "\ git-pack-objects [{ -q | --progress | --all-progress }] \n\ [--local] [--incremental] [--window=N] [--depth=N] \n\ [--no-reuse-delta] [--delta-base-offset] [--non-empty] \n\ - [--revs [--unpacked | --all]*] [--stdout | base-name] \n\ + [--revs [--unpacked | --all]*] [--reflog] [--stdout | base-name] \n\ [ Date: Sat, 23 Dec 2006 02:33:44 -0500 Subject: Refactor packed_git to prepare for sliding mmap windows. The idea behind the sliding mmap window pack reader implementation is to have multiple mmap regions active against the same pack file, thereby allowing the process to mmap in only the active/hot sections of the pack and reduce overall virtual address space usage. To implement this we need to refactor the mmap related data (pack_base, pack_use_cnt) out of struct packed_git and move them into a new struct pack_window. We are refactoring the code to support a single struct pack_window per packfile, thereby emulating the prior behavior of mmap'ing the entire pack file. Signed-off-by: Shawn O. Pearce Signed-off-by: Junio C Hamano --- builtin-pack-objects.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'builtin-pack-objects.c') diff --git a/builtin-pack-objects.c b/builtin-pack-objects.c index 9e15beb3b..4a00a1206 100644 --- a/builtin-pack-objects.c +++ b/builtin-pack-objects.c @@ -438,7 +438,7 @@ static unsigned long write_object(struct sha1file *f, } use_packed_git(p); - buf = (char *) p->pack_base + buf = p->windows->base + entry->in_pack_offset + entry->in_pack_header_size; datalen = find_packed_object_size(p, entry->in_pack_offset) @@ -943,7 +943,7 @@ static void check_object(struct object_entry *entry) struct object_entry *base_entry = NULL; use_packed_git(p); - buf = p->pack_base; + buf = p->windows->base; buf += entry->in_pack_offset; /* We want in_pack_type even if we do not reuse delta. -- cgit v1.2.1 From 03e79c88aa34ce188eb4fb7509e6d127c79c507d Mon Sep 17 00:00:00 2001 From: "Shawn O. Pearce" Date: Sat, 23 Dec 2006 02:34:08 -0500 Subject: Replace use_packed_git with window cursors. Part of the implementation concept of the sliding mmap window for pack access is to permit multiple windows per pack to be mapped independently. Since the inuse_cnt is associated with the mmap and not with the file, this value is in struct pack_window and needs to be incremented/decremented for each pack_window accessed by any code. To faciliate that implementation we need to replace all uses of use_packed_git() and unuse_packed_git() with a different API that follows struct pack_window objects rather than struct packed_git. The way this works is when we need to start accessing a pack for the first time we should setup a new window 'cursor' by declaring a local and setting it to NULL: struct pack_windows *w_curs = NULL; To obtain the memory region which contains a specific section of the pack file we invoke use_pack(), supplying the address of our current window cursor: unsigned int len; unsigned char *addr = use_pack(p, &w_curs, offset, &len); the returned address `addr` will be the first byte at `offset` within the pack file. The optional variable len will also be updated with the number of bytes remaining following the address. Multiple calls to use_pack() with the same window cursor will update the window cursor, moving it from one window to another when necessary. In this way each window cursor variable maintains only one struct pack_window inuse at a time. Finally before exiting the scope which originally declared the window cursor we must invoke unuse_pack() to unuse the current window (which may be different from the one that was first obtained from use_pack): unuse_pack(&w_curs); This implementation is still not complete with regards to multiple windows, as only one window per pack file is supported right now. Signed-off-by: Shawn O. Pearce Signed-off-by: Junio C Hamano --- builtin-pack-objects.c | 16 +++++++--------- 1 file changed, 7 insertions(+), 9 deletions(-) (limited to 'builtin-pack-objects.c') diff --git a/builtin-pack-objects.c b/builtin-pack-objects.c index 4a00a1206..6d7ae7f1a 100644 --- a/builtin-pack-objects.c +++ b/builtin-pack-objects.c @@ -416,6 +416,7 @@ static unsigned long write_object(struct sha1file *f, } else { struct packed_git *p = entry->in_pack; + struct pack_window *w_curs = NULL; if (entry->delta) { obj_type = (allow_ofs_delta && entry->delta->offset) ? @@ -437,16 +438,14 @@ static unsigned long write_object(struct sha1file *f, hdrlen += 20; } - use_packed_git(p); - buf = p->windows->base - + entry->in_pack_offset - + entry->in_pack_header_size; + buf = use_pack(p, &w_curs, entry->in_pack_offset + + entry->in_pack_header_size, NULL); datalen = find_packed_object_size(p, entry->in_pack_offset) - entry->in_pack_header_size; if (!pack_to_stdout && check_inflate(buf, datalen, entry->size)) die("corrupt delta in pack %s", sha1_to_hex(entry->sha1)); sha1write(f, buf, datalen); - unuse_packed_git(p); + unuse_pack(&w_curs); reused++; } if (entry->delta) @@ -937,14 +936,13 @@ static void check_object(struct object_entry *entry) if (entry->in_pack && !entry->preferred_base) { struct packed_git *p = entry->in_pack; + struct pack_window *w_curs = NULL; unsigned long left = p->pack_size - entry->in_pack_offset; unsigned long size, used; unsigned char *buf; struct object_entry *base_entry = NULL; - use_packed_git(p); - buf = p->windows->base; - buf += entry->in_pack_offset; + buf = use_pack(p, &w_curs, entry->in_pack_offset, NULL); /* We want in_pack_type even if we do not reuse delta. * There is no point not reusing non-delta representations. @@ -990,7 +988,7 @@ static void check_object(struct object_entry *entry) if (base_name) base_entry = locate_object_entry(base_name); } - unuse_packed_git(p); + unuse_pack(&w_curs); entry->in_pack_header_size = used; if (base_entry) { -- cgit v1.2.1 From 079afb18fed078af01bd9ab02e2ebbe5d31893b1 Mon Sep 17 00:00:00 2001 From: "Shawn O. Pearce" Date: Sat, 23 Dec 2006 02:34:13 -0500 Subject: Loop over pack_windows when inflating/accessing data. When multiple mmaps start getting used for all pack file access it is not possible to get all data associated with a specific object in one contiguous memory region. This limitation prevents simply passing a single address and length to SHA1_Update or to inflate. Instead we need to loop until we have processed all data of interest. As we loop over the data we are always interested in reusing the same window 'cursor', as the prior window will no longer be of any use to us. This allows the use_pack() call to automatically decrement the use count of the prior window before setting up access for us to the next window. Within each loop we need to make use of the available length output parameter of use_pack() to tell us how many bytes are available in the current memory region, as we cannot tell otherwise. Signed-off-by: Shawn O. Pearce Signed-off-by: Junio C Hamano --- builtin-pack-objects.c | 58 ++++++++++++++++++++++++++++++++++++++++++++------ 1 file changed, 52 insertions(+), 6 deletions(-) (limited to 'builtin-pack-objects.c') diff --git a/builtin-pack-objects.c b/builtin-pack-objects.c index 6d7ae7f1a..afb926a34 100644 --- a/builtin-pack-objects.c +++ b/builtin-pack-objects.c @@ -276,7 +276,52 @@ static int encode_header(enum object_type type, unsigned long size, unsigned cha * we are going to reuse the existing object data as is. make * sure it is not corrupt. */ -static int check_inflate(unsigned char *data, unsigned long len, unsigned long expect) +static int check_pack_inflate(struct packed_git *p, + struct pack_window **w_curs, + unsigned long offset, + unsigned long len, + unsigned long expect) +{ + z_stream stream; + unsigned char fakebuf[4096], *in; + int st; + + memset(&stream, 0, sizeof(stream)); + inflateInit(&stream); + do { + in = use_pack(p, w_curs, offset, &stream.avail_in); + stream.next_in = in; + stream.next_out = fakebuf; + stream.avail_out = sizeof(fakebuf); + st = inflate(&stream, Z_FINISH); + offset += stream.next_in - in; + } while (st == Z_OK || st == Z_BUF_ERROR); + inflateEnd(&stream); + return (st == Z_STREAM_END && + stream.total_out == expect && + stream.total_in == len) ? 0 : -1; +} + +static void copy_pack_data(struct sha1file *f, + struct packed_git *p, + struct pack_window **w_curs, + unsigned long offset, + unsigned long len) +{ + unsigned char *in; + unsigned int avail; + + while (len) { + in = use_pack(p, w_curs, offset, &avail); + if (avail > len) + avail = len; + sha1write(f, in, avail); + offset += avail; + len -= avail; + } +} + +static int check_loose_inflate(unsigned char *data, unsigned long len, unsigned long expect) { z_stream stream; unsigned char fakebuf[4096]; @@ -323,7 +368,7 @@ static int revalidate_loose_object(struct object_entry *entry, return -1; map += used; mapsize -= used; - return check_inflate(map, mapsize, size); + return check_loose_inflate(map, mapsize, size); } static unsigned long write_object(struct sha1file *f, @@ -417,6 +462,7 @@ static unsigned long write_object(struct sha1file *f, else { struct packed_git *p = entry->in_pack; struct pack_window *w_curs = NULL; + unsigned long offset; if (entry->delta) { obj_type = (allow_ofs_delta && entry->delta->offset) ? @@ -438,13 +484,13 @@ static unsigned long write_object(struct sha1file *f, hdrlen += 20; } - buf = use_pack(p, &w_curs, entry->in_pack_offset - + entry->in_pack_header_size, NULL); + offset = entry->in_pack_offset + entry->in_pack_header_size; datalen = find_packed_object_size(p, entry->in_pack_offset) - entry->in_pack_header_size; - if (!pack_to_stdout && check_inflate(buf, datalen, entry->size)) + if (!pack_to_stdout && check_pack_inflate(p, &w_curs, + offset, datalen, entry->size)) die("corrupt delta in pack %s", sha1_to_hex(entry->sha1)); - sha1write(f, buf, datalen); + copy_pack_data(f, p, &w_curs, offset, datalen); unuse_pack(&w_curs); reused++; } -- cgit v1.2.1 From f5b1b5a07e2d715c5ee7c098e95bd3dbc8ee745d Mon Sep 17 00:00:00 2001 From: "Shawn O. Pearce" Date: Wed, 27 Dec 2006 02:46:23 -0500 Subject: Fix random segfaults in pack-objects. Junio noticed that 'non-trivial' pushes were failing if executed using the sliding window mmap changes. This was somewhat difficult to track down as the failure was appearing randomly. It turns out this was a failure caused by the delta base reference (either ref or offset format) spanning over the end of a mmap window. The error in pack-objects was we were not recalling use_pack after the object header was unpacked, and therefore we did not get the promise of at least 20 bytes in the buffer for the delta base parsing. This would case later memcmp() calls to walk into unassigned address space at the end of the window. The reason Junio and I had hard time tracking this down in current Git repositories is we were both probably packing with offset deltas, which minimized the odds of the delta base reference spanning over the end of the mmap window. Stepping back and repacking with version 1.3.3 (which only supported reference deltas) increased the likelyhood of seeing the bug. The correct technique (as used in sha1_file.c) is to invoke use_pack() after unpack_object_header_gently to ensure we have enough data available for the delta base decoding. Signed-off-by: Shawn O. Pearce Signed-off-by: Junio C Hamano --- builtin-pack-objects.c | 7 ++++--- 1 file changed, 4 insertions(+), 3 deletions(-) (limited to 'builtin-pack-objects.c') diff --git a/builtin-pack-objects.c b/builtin-pack-objects.c index afb926a34..e9a1804fa 100644 --- a/builtin-pack-objects.c +++ b/builtin-pack-objects.c @@ -995,8 +995,6 @@ static void check_object(struct object_entry *entry) */ used = unpack_object_header_gently(buf, left, &entry->in_pack_type, &size); - if (!used || left - used <= 20) - die("corrupt pack for %s", sha1_to_hex(entry->sha1)); /* Check if it is delta, and the base is also an object * we are going to pack. If so we will reuse the existing @@ -1008,10 +1006,13 @@ static void check_object(struct object_entry *entry) /* there is at least 20 bytes left in the pack */ switch (entry->in_pack_type) { case OBJ_REF_DELTA: - base_name = buf + used; + base_name = use_pack(p, &w_curs, + entry->in_pack_offset + used, NULL); used += 20; break; case OBJ_OFS_DELTA: + buf = use_pack(p, &w_curs, + entry->in_pack_offset + used, NULL); c = buf[used++]; ofs = c & 127; while (c & 128) { -- cgit v1.2.1 From 9c18df19073bad62e16d6b6b8e1939fd15424612 Mon Sep 17 00:00:00 2001 From: Junio C Hamano Date: Thu, 28 Dec 2006 22:29:06 -0800 Subject: pack-objects: fix use of use_pack(). The code calls use_pack() to make that the variably encoded offset fits in the mmap'ed window, but it forgot that the operation gives the pointer to the beginning of the asked region. Signed-off-by: Junio C Hamano --- builtin-pack-objects.c | 7 +++++-- 1 file changed, 5 insertions(+), 2 deletions(-) (limited to 'builtin-pack-objects.c') diff --git a/builtin-pack-objects.c b/builtin-pack-objects.c index e9a1804fa..42dd8c87a 100644 --- a/builtin-pack-objects.c +++ b/builtin-pack-objects.c @@ -1003,6 +1003,7 @@ static void check_object(struct object_entry *entry) if (!no_reuse_delta) { unsigned char c, *base_name; unsigned long ofs; + unsigned long used_0; /* there is at least 20 bytes left in the pack */ switch (entry->in_pack_type) { case OBJ_REF_DELTA: @@ -1013,14 +1014,15 @@ static void check_object(struct object_entry *entry) case OBJ_OFS_DELTA: buf = use_pack(p, &w_curs, entry->in_pack_offset + used, NULL); - c = buf[used++]; + used_0 = 0; + c = buf[used_0++]; ofs = c & 127; while (c & 128) { ofs += 1; if (!ofs || ofs & ~(~0UL >> 7)) die("delta base offset overflow in pack for %s", sha1_to_hex(entry->sha1)); - c = buf[used++]; + c = buf[used_0++]; ofs = (ofs << 7) + (c & 127); } if (ofs >= entry->in_pack_offset) @@ -1028,6 +1030,7 @@ static void check_object(struct object_entry *entry) sha1_to_hex(entry->sha1)); ofs = entry->in_pack_offset - ofs; base_name = find_packed_object_name(p, ofs); + used += used_0; break; default: base_name = NULL; -- cgit v1.2.1