X-Git-Url: https://git.octo.it/?a=blobdiff_plain;f=pack-objects.c;h=49357c67357fdc96e0d98b193b88e2137453c7c8;hb=acb725772964ee11656543a28c303e9aa6d092c5;hp=af3bdf5d358b8a47ed23bcb7e9721e956eb59d60;hpb=b925410d10fce5e0d4182847f99e8c2df048bde1;p=git.git diff --git a/pack-objects.c b/pack-objects.c index af3bdf5d..49357c67 100644 --- a/pack-objects.c +++ b/pack-objects.c @@ -5,6 +5,7 @@ #include "csum-file.h" #include "diff.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"; @@ -31,9 +32,6 @@ struct object_entry { * be used as the base objectto delta huge * objects against. */ - int based_on_preferred; /* current delta candidate is a preferred - * one, or delta against a preferred one. - */ }; /* @@ -60,6 +58,7 @@ static int nr_objects = 0, nr_alloc = 0, nr_result = 0; static const char *base_name; static unsigned char pack_file_sha1[20]; static int progress = 1; +static volatile int progress_update = 0; /* * The object names in objects array are hashed with this hashtable, @@ -97,7 +96,7 @@ static int reused_delta = 0; static int pack_revindex_ix(struct packed_git *p) { - unsigned int ui = (unsigned int) p; + unsigned long ui = (unsigned long)p; int i; ui = ui ^ (ui >> 16); /* defeat structure alignment */ @@ -334,20 +333,41 @@ static void write_pack_file(void) struct sha1file *f; unsigned long offset; struct pack_header hdr; + unsigned last_percent = 999; + int do_progress = 0; if (!base_name) f = sha1fd(1, ""); - else + 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); + hdr.hdr_signature = htonl(PACK_SIGNATURE); hdr.hdr_version = htonl(PACK_VERSION); hdr.hdr_entries = htonl(nr_result); sha1write(f, &hdr, sizeof(hdr)); offset = sizeof(hdr); - for (i = 0; i < nr_objects; i++) + if (!nr_result) + goto done; + for (i = 0; i < nr_objects; i++) { offset = write_one(f, objects + i, offset); - + if (do_progress) { + unsigned percent = written * 100 / nr_result; + if (progress_update || percent != last_percent) { + fprintf(stderr, "%4u%% (%u/%u) done\r", + percent, written, nr_result); + progress_update = 0; + last_percent = percent; + } + } + } + if (do_progress) + fputc('\n', stderr); + done: sha1close(f, pack_file_sha1, 1); } @@ -439,9 +459,68 @@ static void rehash_objects(void) } } -static int add_object_entry(const unsigned char *sha1, const char *name, int exclude) +struct name_path { + struct name_path *up; + const char *elem; + int len; +}; + +#define DIRBITS 12 + +static unsigned name_hash(struct name_path *path, const char *name) +{ + struct name_path *p = path; + const char *n = name + strlen(name); + unsigned hash = 0, name_hash = 0, name_done = 0; + + if (n != name && n[-1] == '\n') + n--; + while (name <= --n) { + unsigned char c = *n; + if (c == '/' && !name_done) { + name_hash = hash; + name_done = 1; + hash = 0; + } + hash = hash * 11 + c; + } + if (!name_done) { + name_hash = hash; + hash = 0; + } + for (p = path; p; p = p->up) { + hash = hash * 11 + '/'; + n = p->elem + p->len; + while (p->elem <= --n) { + unsigned char c = *n; + hash = hash * 11 + c; + } + } + /* + * Make sure "Makefile" and "t/Makefile" are hashed separately + * but close enough. + */ + hash = (name_hash<up) { + fputc('/', stderr); + n = p->elem + p->len; + while (p->elem <= --n) + fputc(*n, stderr); + } + fprintf(stderr, "\t%08x\n", hash); + } + return hash; +} + +static int add_object_entry(const unsigned char *sha1, unsigned hash, int exclude) { - unsigned int hash = 0; unsigned int idx = nr_objects; struct object_entry *entry; struct packed_git *p; @@ -467,13 +546,6 @@ static int add_object_entry(const unsigned char *sha1, const char *name, int exc if ((entry = locate_object_entry(sha1)) != NULL) goto already_added; - while (*name) { - unsigned char c = *name++; - if (isspace(c)) - continue; - hash = hash * 11 + c; - } - if (idx >= nr_alloc) { unsigned int needed = (idx + 1024) * 3 / 2; objects = xrealloc(objects, needed * sizeof(*entry)); @@ -496,6 +568,10 @@ static int add_object_entry(const unsigned char *sha1, const char *name, int exc status = 1; already_added: + if (progress_update) { + fprintf(stderr, "Counting objects...%d\r", nr_objects); + progress_update = 0; + } if (exclude) entry->preferred_base = 1; else { @@ -507,12 +583,12 @@ static int add_object_entry(const unsigned char *sha1, const char *name, int exc return status; } -static void add_pbase_tree(struct tree_desc *tree) +static void add_pbase_tree(struct tree_desc *tree, struct name_path *up) { while (tree->size) { const unsigned char *sha1; const char *name; - unsigned mode; + unsigned mode, hash; unsigned long size; char type[20]; @@ -523,16 +599,22 @@ static void add_pbase_tree(struct tree_desc *tree) if (sha1_object_info(sha1, type, &size)) continue; - if (!add_object_entry(sha1, name, 1)) + hash = name_hash(up, name); + if (!add_object_entry(sha1, hash, 1)) continue; if (!strcmp(type, "tree")) { struct tree_desc sub; void *elem; + struct name_path me; + elem = read_sha1_file(sha1, type, &sub.size); sub.buf = elem; if (sub.buf) { - add_pbase_tree(&sub); + me.up = up; + me.elem = name; + me.len = strlen(name); + add_pbase_tree(&sub, &me); free(elem); } } @@ -543,12 +625,13 @@ static void add_preferred_base(unsigned char *sha1) { struct tree_desc tree; void *elem; + elem = read_object_with_reference(sha1, "tree", &tree.size, NULL); tree.buf = elem; if (!tree.buf) return; - if (add_object_entry(sha1, "", 1)) - add_pbase_tree(&tree); + if (add_object_entry(sha1, name_hash(NULL, ""), 1)) + add_pbase_tree(&tree, NULL); free(elem); } @@ -635,10 +718,23 @@ static void get_object_details(void) prepare_pack_ix(); for (i = 0, entry = objects; i < nr_objects; i++, entry++) check_object(entry); - for (i = 0, entry = objects; i < nr_objects; i++, entry++) - if (!entry->delta && entry->delta_child) - entry->delta_limit = - check_delta_limit(entry, 1); + + if (nr_objects == nr_result) { + /* + * Depth of objects that depend on the entry -- this + * is subtracted from depth-max to break too deep + * delta chain because of delta data reusing. + * However, we loosen this restriction when we know we + * are creating a thin pack -- it will have to be + * expanded on the other end anyway, so do not + * artificially cut the delta chain and let it go as + * deep as it wants. + */ + for (i = 0, entry = objects; i < nr_objects; i++, entry++) + if (!entry->delta && entry->delta_child) + entry->delta_limit = + check_delta_limit(entry, 1); + } } typedef int (*entry_sort_t)(const struct object_entry *, const struct object_entry *); @@ -669,7 +765,7 @@ static int sha1_sort(const struct object_entry *a, const struct object_entry *b) return memcmp(a->sha1, b->sha1, 20); } -static struct object_entry **create_final_object_list() +static struct object_entry **create_final_object_list(void) { struct object_entry **list; int i, j; @@ -725,8 +821,6 @@ static int try_delta(struct unpacked *cur, struct unpacked *old, unsigned max_de { struct object_entry *cur_entry = cur->entry; struct object_entry *old_entry = old->entry; - int old_preferred = (old_entry->preferred_base || - old_entry->based_on_preferred); unsigned long size, oldsize, delta_size, sizediff; long max_size; void *delta_buf; @@ -752,11 +846,10 @@ static int try_delta(struct unpacked *cur, struct unpacked *old, unsigned max_de } size = cur_entry->size; - if (size < 50) - return -1; oldsize = old_entry->size; sizediff = oldsize > size ? oldsize - size : size - oldsize; - if (sizediff > size / 8) + + if (size < 50) return -1; if (old_entry->depth >= max_depth) return 0; @@ -769,27 +862,8 @@ static int try_delta(struct unpacked *cur, struct unpacked *old, unsigned max_de * delete). */ max_size = size / 2 - 20; - if (cur_entry->delta) { - if (cur_entry->based_on_preferred) { - if (old_preferred) - max_size = cur_entry->delta_size-1; - else - /* trying with non-preferred one when we - * already have a delta based on preferred - * one is pointless. - */ - return -1; - } - else if (!old_preferred) - max_size = cur_entry->delta_size-1; - else - /* otherwise... even if delta with a - * preferred one produces a bigger result than - * what we currently have, which is based on a - * non-preferred one, it is OK. - */ - ; - } + if (cur_entry->delta) + max_size = cur_entry->delta_size-1; if (sizediff >= max_size) return -1; delta_buf = diff_delta(old->data, oldsize, @@ -799,22 +873,29 @@ static int try_delta(struct unpacked *cur, struct unpacked *old, unsigned max_de cur_entry->delta = old_entry; cur_entry->delta_size = delta_size; cur_entry->depth = old_entry->depth + 1; - cur_entry->based_on_preferred = old_preferred; free(delta_buf); return 0; } +static void progress_interval(int signum) +{ + signal(SIGALRM, progress_interval); + progress_update = 1; +} + static void find_deltas(struct object_entry **list, int window, int depth) { int i, idx; unsigned int array_size = window * sizeof(struct unpacked); struct unpacked *array = xmalloc(array_size); - int eye_candy; + unsigned processed = 0; + unsigned last_percent = 999; memset(array, 0, array_size); i = nr_objects; idx = 0; - eye_candy = i - (nr_objects / 20); + if (progress) + fprintf(stderr, "Deltifying %d objects.\n", nr_result); while (--i >= 0) { struct object_entry *entry = list[i]; @@ -823,9 +904,17 @@ static void find_deltas(struct object_entry **list, int window, int depth) char type[10]; int j; - if (progress && i <= eye_candy) { - eye_candy -= nr_objects / 20; - fputc('.', stderr); + if (!entry->preferred_base) + processed++; + + if (progress) { + unsigned percent = processed * 100 / nr_result; + if (percent != last_percent || progress_update) { + fprintf(stderr, "%4u%% (%u/%u) done\r", + percent, processed, nr_result); + progress_update = 0; + last_percent = percent; + } } if (entry->delta) @@ -852,11 +941,23 @@ static void find_deltas(struct object_entry **list, int window, int depth) if (try_delta(n, m, depth) < 0) break; } +#if 0 + /* if we made n a delta, and if n is already at max + * depth, leaving it in the window is pointless. we + * should evict it first. + * ... in theory only; somehow this makes things worse. + */ + if (entry->delta && depth <= entry->depth) + continue; +#endif idx++; if (idx >= window) idx = 0; } + if (progress) + fputc('\n', stderr); + for (i = 0; i < window; ++i) free(array[i].data); free(array); @@ -864,18 +965,10 @@ static void find_deltas(struct object_entry **list, int window, int depth) static void prepare_pack(int window, int depth) { - if (progress) - fprintf(stderr, "Packing %d objects", nr_result); get_object_details(); - if (progress) - fputc('.', stderr); - sorted_by_type = create_sorted_list(type_size_sort); if (window && depth) find_deltas(sorted_by_type, window+1, depth); - if (progress) - fputc('\n', stderr); - write_pack_file(); } static int reuse_cached_pack(unsigned char *sha1, int pack_to_stdout) @@ -939,10 +1032,6 @@ int main(int argc, char **argv) int window = 10, depth = 10, pack_to_stdout = 0; struct object_entry **list; int i; - struct timeval prev_tv; - int eye_candy = 0; - int eye_candy_incr = 500; - setup_git_directory(); @@ -999,29 +1088,20 @@ int main(int argc, char **argv) usage(pack_usage); prepare_packed_git(); + if (progress) { + struct itimerval v; + v.it_interval.tv_sec = 1; + v.it_interval.tv_usec = 0; + v.it_value = v.it_interval; + signal(SIGALRM, progress_interval); + setitimer(ITIMER_REAL, &v, NULL); fprintf(stderr, "Generating pack...\n"); - gettimeofday(&prev_tv, NULL); } + while (fgets(line, sizeof(line), stdin) != NULL) { unsigned char sha1[20]; - if (progress && (eye_candy <= nr_objects)) { - fprintf(stderr, "Counting objects...%d\r", nr_objects); - if (eye_candy && (50 <= eye_candy_incr)) { - struct timeval tv; - int time_diff; - gettimeofday(&tv, NULL); - time_diff = (tv.tv_sec - prev_tv.tv_sec); - time_diff <<= 10; - time_diff += (tv.tv_usec - prev_tv.tv_usec); - if ((1 << 9) < time_diff) - eye_candy_incr += 50; - else if (50 < eye_candy_incr) - eye_candy_incr -= 50; - } - eye_candy += eye_candy_incr; - } if (line[0] == '-') { if (get_sha1_hex(line+1, sha1)) die("expected edge sha1, got garbage:\n %s", @@ -1031,14 +1111,14 @@ int main(int argc, char **argv) } if (get_sha1_hex(line, sha1)) die("expected sha1, got garbage:\n %s", line); - add_object_entry(sha1, line+40, 0); + add_object_entry(sha1, name_hash(NULL, line+41), 0); } if (progress) fprintf(stderr, "Done counting %d objects.\n", nr_objects); - if (non_empty && !nr_objects) + sorted_by_sha = create_final_object_list(); + if (non_empty && !nr_result) return 0; - sorted_by_sha = create_final_object_list(); SHA1_Init(&ctx); list = sorted_by_sha; for (i = 0; i < nr_result; i++) { @@ -1052,7 +1132,16 @@ int main(int argc, char **argv) if (reuse_cached_pack(object_list_sha1, pack_to_stdout)) ; else { - prepare_pack(window, depth); + if (nr_result) + prepare_pack(window, depth); + if (progress && pack_to_stdout) { + /* the other end usually displays progress itself */ + struct itimerval v = {{0,},}; + setitimer(ITIMER_REAL, &v, NULL); + signal(SIGALRM, SIG_IGN ); + progress_update = 0; + } + write_pack_file(); if (!pack_to_stdout) { write_index_file(); puts(sha1_to_hex(object_list_sha1));