X-Git-Url: https://git.tokkee.org/?a=blobdiff_plain;f=builtin-pack-objects.c;h=a15906bdb2021e68a014344cad4e73e9de3367ca;hb=e5f4e214636f9c9bd36c2897634108d5ad5587a1;hp=ccb25f6a9c298bd977c5f55a84dd9a20a1e54e23;hpb=8009533070638490603eee06e1622f3e5aa3bfb2;p=git.git diff --git a/builtin-pack-objects.c b/builtin-pack-objects.c index ccb25f6a9..a15906bdb 100644 --- a/builtin-pack-objects.c +++ b/builtin-pack-objects.c @@ -15,20 +15,21 @@ #include "list-objects.h" #include "progress.h" +#ifdef THREADED_DELTA_SEARCH +#include +#endif + static const char pack_usage[] = "\ -git-pack-objects [{ -q | --progress | --all-progress }] [--max-pack-size=N] \n\ - [--local] [--incremental] [--window=N] [--depth=N] \n\ +git-pack-objects [{ -q | --progress | --all-progress }] \n\ + [--max-pack-size=N] [--local] [--incremental] \n\ + [--window=N] [--window-memory=N] [--depth=N] \n\ [--no-reuse-delta] [--no-reuse-object] [--delta-base-offset] \n\ - [--non-empty] [--revs [--unpacked | --all]*] [--reflog] \n\ + [--threads=N] [--non-empty] [--revs [--unpacked | --all]*] [--reflog] \n\ [--stdout | base-name] [delta->sha1, &type, &othersize); + void *otherbuf = read_sha1_file(entry->delta->idx.sha1, &type, &othersize); void *delta_buf; if (!otherbuf) - die("unable to read %s", sha1_to_hex(entry->delta->sha1)); + die("unable to read %s", sha1_to_hex(entry->delta->idx.sha1)); delta_buf = diff_delta(otherbuf, othersize, buf, size, &delta_size, 0); if (!delta_buf || delta_size != entry->delta_size) - die("delta size changed"); + die("delta size changed"); free(buf); free(otherbuf); return delta_buf; @@ -379,11 +383,11 @@ static unsigned long write_object(struct sha1file *f, /* yes if unlimited packfile */ !pack_size_limit ? 1 : /* no if base written to previous pack */ - entry->delta->offset == (off_t)-1 ? 0 : + entry->delta->idx.offset == (off_t)-1 ? 0 : /* otherwise double-check written to this * pack, like we do below */ - entry->delta->offset ? 1 : 0; + entry->delta->idx.offset ? 1 : 0; if (!pack_to_stdout) crc32_begin(f); @@ -411,22 +415,22 @@ static unsigned long write_object(struct sha1file *f, unsigned long maxsize; void *out; if (!usable_delta) { - buf = read_sha1_file(entry->sha1, &obj_type, &size); + buf = read_sha1_file(entry->idx.sha1, &obj_type, &size); if (!buf) - die("unable to read %s", sha1_to_hex(entry->sha1)); + die("unable to read %s", sha1_to_hex(entry->idx.sha1)); } else if (entry->delta_data) { size = entry->delta_size; buf = entry->delta_data; entry->delta_data = NULL; - obj_type = (allow_ofs_delta && entry->delta->offset) ? + obj_type = (allow_ofs_delta && entry->delta->idx.offset) ? OBJ_OFS_DELTA : OBJ_REF_DELTA; } else { - buf = read_sha1_file(entry->sha1, &type, &size); + buf = read_sha1_file(entry->idx.sha1, &type, &size); if (!buf) - die("unable to read %s", sha1_to_hex(entry->sha1)); + die("unable to read %s", sha1_to_hex(entry->idx.sha1)); buf = delta_against(buf, size, entry); size = entry->delta_size; - obj_type = (allow_ofs_delta && entry->delta->offset) ? + obj_type = (allow_ofs_delta && entry->delta->idx.offset) ? OBJ_OFS_DELTA : OBJ_REF_DELTA; } /* compress the data to store and put compressed length in datalen */ @@ -456,7 +460,7 @@ static unsigned long write_object(struct sha1file *f, * encoding of the relative offset for the delta * base from this object's position in the pack. */ - off_t ofs = entry->offset - entry->delta->offset; + off_t ofs = entry->idx.offset - entry->delta->idx.offset; unsigned pos = sizeof(dheader) - 1; dheader[pos] = ofs & 127; while (ofs >>= 7) @@ -480,7 +484,7 @@ static unsigned long write_object(struct sha1file *f, return 0; } sha1write(f, header, hdrlen); - sha1write(f, entry->delta->sha1, 20); + sha1write(f, entry->delta->idx.sha1, 20); hdrlen += 20; } else { if (limit && hdrlen + datalen + 20 >= limit) { @@ -501,7 +505,7 @@ static unsigned long write_object(struct sha1file *f, off_t offset; if (entry->delta) { - obj_type = (allow_ofs_delta && entry->delta->offset) ? + obj_type = (allow_ofs_delta && entry->delta->idx.offset) ? OBJ_OFS_DELTA : OBJ_REF_DELTA; reused_delta++; } @@ -511,11 +515,11 @@ static unsigned long write_object(struct sha1file *f, datalen = revidx[1].offset - offset; if (!pack_to_stdout && p->index_version > 1 && check_pack_crc(p, &w_curs, offset, datalen, revidx->nr)) - die("bad packed object CRC for %s", sha1_to_hex(entry->sha1)); + die("bad packed object CRC for %s", sha1_to_hex(entry->idx.sha1)); offset += entry->in_pack_header_size; datalen -= entry->in_pack_header_size; if (obj_type == OBJ_OFS_DELTA) { - off_t ofs = entry->offset - entry->delta->offset; + off_t ofs = entry->idx.offset - entry->delta->idx.offset; unsigned pos = sizeof(dheader) - 1; dheader[pos] = ofs & 127; while (ofs >>= 7) @@ -529,7 +533,7 @@ static unsigned long write_object(struct sha1file *f, if (limit && hdrlen + 20 + datalen + 20 >= limit) return 0; sha1write(f, header, hdrlen); - sha1write(f, entry->delta->sha1, 20); + sha1write(f, entry->delta->idx.sha1, 20); hdrlen += 20; } else { if (limit && hdrlen + datalen + 20 >= limit) @@ -539,7 +543,7 @@ static unsigned long write_object(struct sha1file *f, if (!pack_to_stdout && p->index_version == 1 && check_pack_inflate(p, &w_curs, offset, datalen, entry->size)) - die("corrupt packed object for %s", sha1_to_hex(entry->sha1)); + die("corrupt packed object for %s", sha1_to_hex(entry->idx.sha1)); copy_pack_data(f, p, &w_curs, offset, datalen); unuse_pack(&w_curs); reused++; @@ -548,7 +552,7 @@ static unsigned long write_object(struct sha1file *f, written_delta++; written++; if (!pack_to_stdout) - entry->crc32 = crc32_end(f); + entry->idx.crc32 = crc32_end(f); return hdrlen + datalen; } @@ -559,7 +563,7 @@ static off_t write_one(struct sha1file *f, unsigned long size; /* offset is non zero if object is written already. */ - if (e->offset || e->preferred_base) + if (e->idx.offset || e->preferred_base) return offset; /* if we are deltified, write out base object first. */ @@ -569,10 +573,10 @@ static off_t write_one(struct sha1file *f, return 0; } - e->offset = offset; + e->idx.offset = offset; size = write_object(f, e, offset); if (!size) { - e->offset = 0; + e->idx.offset = 0; return 0; } written_list[nr_written++] = e; @@ -586,11 +590,10 @@ static off_t write_one(struct sha1file *f, static int open_object_dir_tmp(const char *path) { snprintf(tmpname, sizeof(tmpname), "%s/%s", get_object_directory(), path); - return mkstemp(tmpname); + return xmkstemp(tmpname); } -/* forward declarations for write_pack_file */ -static void write_index_file(off_t last_obj_offset, unsigned char *sha1); +/* forward declaration for write_pack_file */ static int adjust_perm(const char *path, mode_t mode); static void write_pack_file(void) @@ -607,12 +610,12 @@ static void write_pack_file(void) written_list = xmalloc(nr_objects * sizeof(struct object_entry *)); do { + unsigned char sha1[20]; + if (pack_to_stdout) { f = sha1fd(1, ""); } else { int fd = open_object_dir_tmp("tmp_pack_XXXXXX"); - if (fd < 0) - die("unable to create %s: %s\n", tmpname, strerror(errno)); pack_tmp_name = xstrdup(tmpname); f = sha1fd(fd, pack_tmp_name); } @@ -638,23 +641,23 @@ static void write_pack_file(void) * If so, rewrite it like in fast-import */ if (pack_to_stdout || nr_written == nr_remaining) { - sha1close(f, pack_file_sha1, 1); + sha1close(f, sha1, 1); } else { - sha1close(f, pack_file_sha1, 0); - fixup_pack_header_footer(f->fd, pack_file_sha1, pack_tmp_name, nr_written); + sha1close(f, sha1, 0); + fixup_pack_header_footer(f->fd, sha1, pack_tmp_name, nr_written); close(f->fd); } if (!pack_to_stdout) { - unsigned char object_list_sha1[20]; mode_t mode = umask(0); umask(mode); mode = 0444 & ~mode; - write_index_file(last_obj_offset, object_list_sha1); + idx_tmp_name = write_idx_file(NULL, + (struct pack_idx_entry **) written_list, nr_written, sha1); snprintf(tmpname, sizeof(tmpname), "%s-%s.pack", - base_name, sha1_to_hex(object_list_sha1)); + base_name, sha1_to_hex(sha1)); if (adjust_perm(pack_tmp_name, mode)) die("unable to make temporary pack file readable: %s", strerror(errno)); @@ -662,19 +665,19 @@ static void write_pack_file(void) die("unable to rename temporary pack file: %s", strerror(errno)); snprintf(tmpname, sizeof(tmpname), "%s-%s.idx", - base_name, sha1_to_hex(object_list_sha1)); + base_name, sha1_to_hex(sha1)); if (adjust_perm(idx_tmp_name, mode)) die("unable to make temporary index file readable: %s", strerror(errno)); if (rename(idx_tmp_name, tmpname)) die("unable to rename temporary index file: %s", strerror(errno)); - puts(sha1_to_hex(object_list_sha1)); + puts(sha1_to_hex(sha1)); } /* mark written objects as written to previous pack */ for (j = 0; j < nr_written; j++) { - written_list[j]->offset = (off_t)-1; + written_list[j]->idx.offset = (off_t)-1; } nr_remaining -= nr_written; } while (nr_remaining && i < nr_objects); @@ -692,129 +695,12 @@ static void write_pack_file(void) */ for (j = 0; i < nr_objects; i++) { struct object_entry *e = objects + i; - j += !e->offset && !e->preferred_base; + j += !e->idx.offset && !e->preferred_base; } if (j) die("wrote %u objects as expected but %u unwritten", written, j); } -static int sha1_sort(const void *_a, const void *_b) -{ - const struct object_entry *a = *(struct object_entry **)_a; - const struct object_entry *b = *(struct object_entry **)_b; - return hashcmp(a->sha1, b->sha1); -} - -static uint32_t index_default_version = 1; -static uint32_t index_off32_limit = 0x7fffffff; - -static void write_index_file(off_t last_obj_offset, unsigned char *sha1) -{ - struct sha1file *f; - struct object_entry **sorted_by_sha, **list, **last; - uint32_t array[256]; - uint32_t i, index_version; - SHA_CTX ctx; - - int fd = open_object_dir_tmp("tmp_idx_XXXXXX"); - if (fd < 0) - die("unable to create %s: %s\n", tmpname, strerror(errno)); - idx_tmp_name = xstrdup(tmpname); - f = sha1fd(fd, idx_tmp_name); - - if (nr_written) { - sorted_by_sha = written_list; - qsort(sorted_by_sha, nr_written, sizeof(*sorted_by_sha), sha1_sort); - list = sorted_by_sha; - last = sorted_by_sha + nr_written; - } else - sorted_by_sha = list = last = NULL; - - /* if last object's offset is >= 2^31 we should use index V2 */ - index_version = (last_obj_offset >> 31) ? 2 : index_default_version; - - /* index versions 2 and above need a header */ - if (index_version >= 2) { - struct pack_idx_header hdr; - hdr.idx_signature = htonl(PACK_IDX_SIGNATURE); - hdr.idx_version = htonl(index_version); - sha1write(f, &hdr, sizeof(hdr)); - } - - /* - * Write the first-level table (the list is sorted, - * but we use a 256-entry lookup to be able to avoid - * having to do eight extra binary search iterations). - */ - for (i = 0; i < 256; i++) { - struct object_entry **next = list; - while (next < last) { - struct object_entry *entry = *next; - if (entry->sha1[0] != i) - break; - next++; - } - array[i] = htonl(next - sorted_by_sha); - list = next; - } - sha1write(f, array, 256 * 4); - - /* Compute the SHA1 hash of sorted object names. */ - SHA1_Init(&ctx); - - /* Write the actual SHA1 entries. */ - list = sorted_by_sha; - for (i = 0; i < nr_written; i++) { - struct object_entry *entry = *list++; - if (index_version < 2) { - uint32_t offset = htonl(entry->offset); - sha1write(f, &offset, 4); - } - sha1write(f, entry->sha1, 20); - SHA1_Update(&ctx, entry->sha1, 20); - } - - if (index_version >= 2) { - unsigned int nr_large_offset = 0; - - /* write the crc32 table */ - list = sorted_by_sha; - for (i = 0; i < nr_written; i++) { - struct object_entry *entry = *list++; - uint32_t crc32_val = htonl(entry->crc32); - sha1write(f, &crc32_val, 4); - } - - /* write the 32-bit offset table */ - list = sorted_by_sha; - for (i = 0; i < nr_written; i++) { - struct object_entry *entry = *list++; - uint32_t offset = (entry->offset <= index_off32_limit) ? - entry->offset : (0x80000000 | nr_large_offset++); - offset = htonl(offset); - sha1write(f, &offset, 4); - } - - /* write the large offset table */ - list = sorted_by_sha; - while (nr_large_offset) { - struct object_entry *entry = *list++; - uint64_t offset = entry->offset; - if (offset > index_off32_limit) { - uint32_t split[2]; - split[0] = htonl(offset >> 32); - split[1] = htonl(offset & 0xffffffff); - sha1write(f, split, 8); - nr_large_offset--; - } - } - } - - sha1write(f, pack_file_sha1, 20); - sha1close(f, NULL, 1); - SHA1_Final(sha1, &ctx); -} - static int locate_object_entry_hash(const unsigned char *sha1) { int i; @@ -822,7 +708,7 @@ static int locate_object_entry_hash(const unsigned char *sha1) memcpy(&ui, sha1, sizeof(unsigned int)); i = ui % object_ix_hashsz; while (0 < object_ix[i]) { - if (!hashcmp(sha1, objects[object_ix[i] - 1].sha1)) + if (!hashcmp(sha1, objects[object_ix[i] - 1].idx.sha1)) return i; if (++i == object_ix_hashsz) i = 0; @@ -854,7 +740,7 @@ static void rehash_objects(void) object_ix = xrealloc(object_ix, sizeof(int) * object_ix_hashsz); memset(object_ix, 0, sizeof(int) * object_ix_hashsz); for (i = 0, oe = objects; i < nr_objects; i++, oe++) { - int ix = locate_object_entry_hash(oe->sha1); + int ix = locate_object_entry_hash(oe->idx.sha1); if (0 <= ix) continue; ix = -1 - ix; @@ -948,7 +834,7 @@ static int add_object_entry(const unsigned char *sha1, enum object_type type, entry = objects + nr_objects++; memset(entry, 0, sizeof(*entry)); - hashcpy(entry->sha1, sha1); + hashcpy(entry->idx.sha1, sha1); entry->hash = hash; if (type) entry->type = type; @@ -1097,6 +983,8 @@ static void add_pbase_object(struct tree_desc *tree, int cmp; while (tree_entry(tree,&entry)) { + if (S_ISGITLINK(entry.mode)) + continue; cmp = tree_entry_len(entry.path, entry.sha1) != cmplen ? 1 : memcmp(name, entry.path, cmplen); if (cmp > 0) @@ -1268,13 +1156,13 @@ static void check_object(struct object_entry *entry) ofs += 1; if (!ofs || MSB(ofs, 7)) die("delta base offset overflow in pack for %s", - sha1_to_hex(entry->sha1)); + sha1_to_hex(entry->idx.sha1)); c = buf[used_0++]; 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)); + sha1_to_hex(entry->idx.sha1)); ofs = entry->in_pack_offset - ofs; if (!no_reuse_delta && !entry->preferred_base) base_ref = find_packed_object_name(p, ofs); @@ -1321,10 +1209,10 @@ static void check_object(struct object_entry *entry) unuse_pack(&w_curs); } - entry->type = sha1_object_info(entry->sha1, &entry->size); + entry->type = sha1_object_info(entry->idx.sha1, &entry->size); if (entry->type < 0) die("unable to get type of object %s", - sha1_to_hex(entry->sha1)); + sha1_to_hex(entry->idx.sha1)); } static int pack_offset_sort(const void *_a, const void *_b) @@ -1334,7 +1222,7 @@ static int pack_offset_sort(const void *_a, const void *_b) /* avoid filesystem trashing with loose objects */ if (!a->in_pack && !b->in_pack) - return hashcmp(a->sha1, b->sha1); + return hashcmp(a->idx.sha1, b->idx.sha1); if (a->in_pack < b->in_pack) return -1; @@ -1388,11 +1276,11 @@ struct unpacked { struct object_entry *entry; void *data; struct delta_index *index; + unsigned depth; }; -static int delta_cacheable(struct unpacked *trg, struct unpacked *src, - unsigned long src_size, unsigned long trg_size, - unsigned long delta_size) +static int delta_cacheable(unsigned long src_size, unsigned long trg_size, + unsigned long delta_size) { if (max_delta_cache_size && delta_cache_size + delta_size > max_delta_cache_size) return 0; @@ -1407,6 +1295,31 @@ static int delta_cacheable(struct unpacked *trg, struct unpacked *src, return 0; } +#ifdef THREADED_DELTA_SEARCH + +static pthread_mutex_t read_mutex = PTHREAD_MUTEX_INITIALIZER; +#define read_lock() pthread_mutex_lock(&read_mutex) +#define read_unlock() pthread_mutex_unlock(&read_mutex) + +static pthread_mutex_t cache_mutex = PTHREAD_MUTEX_INITIALIZER; +#define cache_lock() pthread_mutex_lock(&cache_mutex) +#define cache_unlock() pthread_mutex_unlock(&cache_mutex) + +static pthread_mutex_t progress_mutex = PTHREAD_MUTEX_INITIALIZER; +#define progress_lock() pthread_mutex_lock(&progress_mutex) +#define progress_unlock() pthread_mutex_unlock(&progress_mutex) + +#else + +#define read_lock() (void)0 +#define read_unlock() (void)0 +#define cache_lock() (void)0 +#define cache_unlock() (void)0 +#define progress_lock() (void)0 +#define progress_unlock() (void)0 + +#endif + /* * We search for deltas _backwards_ in a list sorted by type and * by size, so that we see progressively smaller and smaller files. @@ -1416,11 +1329,12 @@ static int delta_cacheable(struct unpacked *trg, struct unpacked *src, * one. */ static int try_delta(struct unpacked *trg, struct unpacked *src, - unsigned max_depth) + unsigned max_depth, unsigned long *mem_usage) { struct object_entry *trg_entry = trg->entry; struct object_entry *src_entry = src->entry; unsigned long trg_size, src_size, delta_size, sizediff, max_size, sz; + unsigned ref_depth; enum object_type type; void *delta_buf; @@ -1428,12 +1342,6 @@ static int try_delta(struct unpacked *trg, struct unpacked *src, if (trg_entry->type != src_entry->type) return -1; - /* We do not compute delta to *create* objects we are not - * going to pack. - */ - if (trg_entry->preferred_base) - return -1; - /* * We do not bother to try a delta that we discarded * on an earlier try, but only when reusing delta data. @@ -1445,34 +1353,53 @@ static int try_delta(struct unpacked *trg, struct unpacked *src, return 0; /* Let's not bust the allowed depth. */ - if (src_entry->depth >= max_depth) + if (src->depth >= max_depth) return 0; /* Now some size filtering heuristics. */ trg_size = trg_entry->size; - max_size = trg_size/2 - 20; - max_size = max_size * (max_depth - src_entry->depth) / max_depth; + if (!trg_entry->delta) { + max_size = trg_size/2 - 20; + ref_depth = 1; + } else { + max_size = trg_entry->delta_size; + ref_depth = trg->depth; + } + max_size = max_size * (max_depth - src->depth) / + (max_depth - ref_depth + 1); if (max_size == 0) return 0; - if (trg_entry->delta && trg_entry->delta_size <= max_size) - max_size = trg_entry->delta_size-1; src_size = src_entry->size; sizediff = src_size < trg_size ? trg_size - src_size : 0; if (sizediff >= max_size) return 0; + if (trg_size < src_size / 32) + return 0; /* Load data if not already done */ if (!trg->data) { - trg->data = read_sha1_file(trg_entry->sha1, &type, &sz); + read_lock(); + trg->data = read_sha1_file(trg_entry->idx.sha1, &type, &sz); + read_unlock(); + if (!trg->data) + die("object %s cannot be read", + sha1_to_hex(trg_entry->idx.sha1)); if (sz != trg_size) die("object %s inconsistent object length (%lu vs %lu)", - sha1_to_hex(trg_entry->sha1), sz, trg_size); + sha1_to_hex(trg_entry->idx.sha1), sz, trg_size); + *mem_usage += sz; } if (!src->data) { - src->data = read_sha1_file(src_entry->sha1, &type, &sz); + read_lock(); + src->data = read_sha1_file(src_entry->idx.sha1, &type, &sz); + read_unlock(); + if (!src->data) + die("object %s cannot be read", + sha1_to_hex(src_entry->idx.sha1)); if (sz != src_size) die("object %s inconsistent object length (%lu vs %lu)", - sha1_to_hex(src_entry->sha1), sz, src_size); + sha1_to_hex(src_entry->idx.sha1), sz, src_size); + *mem_usage += sz; } if (!src->index) { src->index = create_delta_index(src->data, src_size); @@ -1482,26 +1409,47 @@ static int try_delta(struct unpacked *trg, struct unpacked *src, warning("suboptimal pack - out of memory"); return 0; } + *mem_usage += sizeof_delta_index(src->index); } delta_buf = create_delta(src->index, trg->data, trg_size, &delta_size, max_size); if (!delta_buf) return 0; - if (trg_entry->delta_data) { - delta_cache_size -= trg_entry->delta_size; - free(trg_entry->delta_data); + if (trg_entry->delta) { + /* Prefer only shallower same-sized deltas. */ + if (delta_size == trg_entry->delta_size && + src->depth + 1 >= trg->depth) { + free(delta_buf); + return 0; + } } - trg_entry->delta_data = 0; + trg_entry->delta = src_entry; trg_entry->delta_size = delta_size; - trg_entry->depth = src_entry->depth + 1; + trg->depth = src->depth + 1; - if (delta_cacheable(src, trg, src_size, trg_size, delta_size)) { - trg_entry->delta_data = xrealloc(delta_buf, delta_size); + /* + * Handle memory allocation outside of the cache + * accounting lock. Compiler will optimize the strangeness + * away when THREADED_DELTA_SEARCH is not defined. + */ + if (trg_entry->delta_data) + free(trg_entry->delta_data); + cache_lock(); + if (trg_entry->delta_data) { + delta_cache_size -= trg_entry->delta_size; + trg_entry->delta_data = NULL; + } + if (delta_cacheable(src_size, trg_size, delta_size)) { delta_cache_size += trg_entry->delta_size; - } else + cache_unlock(); + trg_entry->delta_data = xrealloc(delta_buf, delta_size); + } else { + cache_unlock(); free(delta_buf); + } + return 1; } @@ -1518,48 +1466,59 @@ static unsigned int check_delta_limit(struct object_entry *me, unsigned int n) return m; } -static void find_deltas(struct object_entry **list, int window, int depth) +static unsigned long free_unpacked(struct unpacked *n) +{ + unsigned long freed_mem = sizeof_delta_index(n->index); + free_delta_index(n->index); + n->index = NULL; + if (n->data) { + freed_mem += n->entry->size; + free(n->data); + n->data = NULL; + } + n->entry = NULL; + n->depth = 0; + return freed_mem; +} + +static void find_deltas(struct object_entry **list, unsigned list_size, + int window, int depth, unsigned *processed) { - uint32_t i = nr_objects, idx = 0, processed = 0; + uint32_t i = list_size, idx = 0, count = 0; unsigned int array_size = window * sizeof(struct unpacked); struct unpacked *array; - int max_depth; + unsigned long mem_usage = 0; - if (!nr_objects) - return; array = xmalloc(array_size); memset(array, 0, array_size); - if (progress) - start_progress(&progress_state, "Deltifying %u objects...", "", nr_result); do { struct object_entry *entry = list[--i]; struct unpacked *n = array + idx; - int j; - - if (!entry->preferred_base) - processed++; + int j, max_depth, best_base = -1; - if (progress) - display_progress(&progress_state, processed); - - if (entry->delta) - /* This happens if we decided to reuse existing - * delta from a pack. "!no_reuse_delta &&" is implied. - */ - continue; + mem_usage -= free_unpacked(n); + n->entry = entry; - if (entry->size < 50) - continue; + while (window_memory_limit && + mem_usage > window_memory_limit && + count > 1) { + uint32_t tail = (idx + window - count) % window; + mem_usage -= free_unpacked(array + tail); + count--; + } - if (entry->no_try_delta) - continue; + /* We do not compute delta to *create* objects we are not + * going to pack. + */ + if (entry->preferred_base) + goto next; - free_delta_index(n->index); - n->index = NULL; - free(n->data); - n->data = NULL; - n->entry = entry; + progress_lock(); + (*processed)++; + if (progress) + display_progress(&progress_state, *processed); + progress_unlock(); /* * If the current object is at pack edge, take the depth the @@ -1575,6 +1534,7 @@ static void find_deltas(struct object_entry **list, int window, int depth) j = window; while (--j > 0) { + int ret; uint32_t other_idx = idx + j; struct unpacked *m; if (other_idx >= window) @@ -1582,26 +1542,45 @@ static void find_deltas(struct object_entry **list, int window, int depth) m = array + other_idx; if (!m->entry) break; - if (try_delta(n, m, max_depth) < 0) + ret = try_delta(n, m, max_depth, &mem_usage); + if (ret < 0) break; + else if (ret > 0) + best_base = other_idx; } /* 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. */ - if (entry->delta && depth <= entry->depth) + if (entry->delta && depth <= n->depth) continue; + /* + * Move the best delta base up in the window, after the + * currently deltified object, to keep it longer. It will + * be the first base object to be attempted next. + */ + if (entry->delta) { + struct unpacked swap = array[best_base]; + int dist = (window + idx - best_base) % window; + int dst = best_base; + while (dist--) { + int src = (dst + 1) % window; + array[dst] = array[src]; + dst = src; + } + array[dst] = swap; + } + next: idx++; + if (count + 1 < window) + count++; if (idx >= window) idx = 0; } while (i > 0); - if (progress) - stop_progress(&progress_state); - for (i = 0; i < window; ++i) { free_delta_index(array[i].index); free(array[i].data); @@ -1609,21 +1588,145 @@ static void find_deltas(struct object_entry **list, int window, int depth) free(array); } +#ifdef THREADED_DELTA_SEARCH + +struct thread_params { + pthread_t thread; + struct object_entry **list; + unsigned list_size; + int window; + int depth; + unsigned *processed; +}; + +static pthread_mutex_t data_request = PTHREAD_MUTEX_INITIALIZER; +static pthread_mutex_t data_ready = PTHREAD_MUTEX_INITIALIZER; +static pthread_mutex_t data_provider = PTHREAD_MUTEX_INITIALIZER; +static struct thread_params *data_requester; + +static void *threaded_find_deltas(void *arg) +{ + struct thread_params *me = arg; + + for (;;) { + pthread_mutex_lock(&data_request); + data_requester = me; + pthread_mutex_unlock(&data_provider); + pthread_mutex_lock(&data_ready); + pthread_mutex_unlock(&data_request); + + if (!me->list_size) + return NULL; + + find_deltas(me->list, me->list_size, + me->window, me->depth, me->processed); + } +} + +static void ll_find_deltas(struct object_entry **list, unsigned list_size, + int window, int depth, unsigned *processed) +{ + struct thread_params *target, p[delta_search_threads]; + int i, ret; + unsigned chunk_size; + + if (delta_search_threads <= 1) { + find_deltas(list, list_size, window, depth, processed); + return; + } + + pthread_mutex_lock(&data_provider); + pthread_mutex_lock(&data_ready); + + for (i = 0; i < delta_search_threads; i++) { + p[i].window = window; + p[i].depth = depth; + p[i].processed = processed; + ret = pthread_create(&p[i].thread, NULL, + threaded_find_deltas, &p[i]); + if (ret) + die("unable to create thread: %s", strerror(ret)); + } + + /* this should be auto-tuned somehow */ + chunk_size = window * 1000; + + do { + unsigned sublist_size = chunk_size; + if (sublist_size > list_size) + sublist_size = list_size; + + /* try to split chunks on "path" boundaries */ + while (sublist_size < list_size && list[sublist_size]->hash && + list[sublist_size]->hash == list[sublist_size-1]->hash) + sublist_size++; + + pthread_mutex_lock(&data_provider); + target = data_requester; + target->list = list; + target->list_size = sublist_size; + pthread_mutex_unlock(&data_ready); + + list += sublist_size; + list_size -= sublist_size; + if (!sublist_size) { + pthread_join(target->thread, NULL); + i--; + } + } while (i); +} + +#else +#define ll_find_deltas find_deltas +#endif + static void prepare_pack(int window, int depth) { struct object_entry **delta_list; - uint32_t i; + uint32_t i, n, nr_deltas; get_object_details(); - if (!window || !depth) + if (!nr_objects || !window || !depth) return; delta_list = xmalloc(nr_objects * sizeof(*delta_list)); - for (i = 0; i < nr_objects; i++) - delta_list[i] = objects + i; - qsort(delta_list, nr_objects, sizeof(*delta_list), type_size_sort); - find_deltas(delta_list, window+1, depth); + nr_deltas = n = 0; + + for (i = 0; i < nr_objects; i++) { + struct object_entry *entry = objects + i; + + if (entry->delta) + /* This happens if we decided to reuse existing + * delta from a pack. "!no_reuse_delta &&" is implied. + */ + continue; + + if (entry->size < 50) + continue; + + if (entry->no_try_delta) + continue; + + if (!entry->preferred_base) + nr_deltas++; + + delta_list[n++] = entry; + } + + if (nr_deltas) { + unsigned nr_done = 0; + if (progress) + start_progress(&progress_state, + "Deltifying %u objects...", "", + nr_deltas); + qsort(delta_list, n, sizeof(*delta_list), type_size_sort); + ll_find_deltas(delta_list, n, window+1, depth, &nr_done); + if (progress) + stop_progress(&progress_state); + if (nr_done != nr_deltas) + die("inconsistency with delta count"); + } free(delta_list); } @@ -1633,7 +1736,11 @@ static int git_pack_config(const char *k, const char *v) window = git_config_int(k, v); return 0; } - if(!strcmp(k, "pack.depth")) { + if (!strcmp(k, "pack.windowmemory")) { + window_memory_limit = git_config_ulong(k, v); + return 0; + } + if (!strcmp(k, "pack.depth")) { depth = git_config_int(k, v); return 0; } @@ -1655,6 +1762,17 @@ static int git_pack_config(const char *k, const char *v) cache_max_small_delta_size = git_config_int(k, v); return 0; } + if (!strcmp(k, "pack.threads")) { + delta_search_threads = git_config_int(k, v); + if (delta_search_threads < 1) + die("invalid number of threads specified (%d)", + delta_search_threads); +#ifndef THREADED_DELTA_SEARCH + if (delta_search_threads > 1) + warning("no threads support, ignoring %s", k); +#endif + return 0; + } return git_default_config(k, v); } @@ -1809,6 +1927,23 @@ int cmd_pack_objects(int argc, const char **argv, const char *prefix) usage(pack_usage); continue; } + if (!prefixcmp(arg, "--window-memory=")) { + if (!git_parse_ulong(arg+16, &window_memory_limit)) + usage(pack_usage); + continue; + } + if (!prefixcmp(arg, "--threads=")) { + char *end; + delta_search_threads = strtoul(arg+10, &end, 0); + if (!arg[10] || *end || delta_search_threads < 1) + usage(pack_usage); +#ifndef THREADED_DELTA_SEARCH + if (delta_search_threads > 1) + warning("no threads support, " + "ignoring %s", arg); +#endif + continue; + } if (!prefixcmp(arg, "--depth=")) { char *end; depth = strtoul(arg+8, &end, 0); @@ -1869,12 +2004,12 @@ int cmd_pack_objects(int argc, const char **argv, const char *prefix) } if (!prefixcmp(arg, "--index-version=")) { char *c; - index_default_version = strtoul(arg + 16, &c, 10); - if (index_default_version > 2) + pack_idx_default_version = strtoul(arg + 16, &c, 10); + if (pack_idx_default_version > 2) die("bad %s", arg); if (*c == ',') - index_off32_limit = strtoul(c+1, &c, 0); - if (*c || index_off32_limit & 0x80000000) + pack_idx_off32_limit = strtoul(c+1, &c, 0); + if (*c || pack_idx_off32_limit & 0x80000000) die("bad %s", arg); continue; }