From f4609b896fac842433bd495c166d5987852a6a73 Mon Sep 17 00:00:00 2001 From: Vincent Ambo Date: Sat, 21 Nov 2020 19:20:35 +0100 Subject: merge(3p/git): Merge git subtree at v2.29.2 This also bumps the stable nixpkgs to 20.09 as of 2020-11-21, because there is some breakage in the git build related to the netrc credentials helper which someone has taken care of in nixpkgs. The stable channel is not used for anything other than git, so this should be fine. Change-Id: I3575a19dab09e1e9556cf8231d717de9890484fb --- third_party/git/builtin/index-pack.c | 527 +++++++++++++++++++---------------- 1 file changed, 293 insertions(+), 234 deletions(-) (limited to 'third_party/git/builtin/index-pack.c') diff --git a/third_party/git/builtin/index-pack.c b/third_party/git/builtin/index-pack.c index 0d55f73b0b44..0d03cb442df3 100644 --- a/third_party/git/builtin/index-pack.c +++ b/third_party/git/builtin/index-pack.c @@ -14,7 +14,7 @@ #include "thread-utils.h" #include "packfile.h" #include "object-store.h" -#include "fetch-object.h" +#include "promisor-remote.h" static const char index_pack_usage[] = "git index-pack [-v] [-o ] [--keep | --keep=] [--verify] [--strict] ( | --stdin [--fix-thin] [])"; @@ -33,19 +33,61 @@ struct object_stat { }; struct base_data { + /* Initialized by make_base(). */ struct base_data *base; - struct base_data *child; struct object_entry *obj; - void *data; - unsigned long size; int ref_first, ref_last; int ofs_first, ofs_last; + /* + * Threads should increment retain_data if they are about to call + * patch_delta() using this struct's data as a base, and decrement this + * when they are done. While retain_data is nonzero, this struct's data + * will not be freed even if the delta base cache limit is exceeded. + */ + int retain_data; + /* + * The number of direct children that have not been fully processed + * (entered work_head, entered done_head, left done_head). When this + * number reaches zero, this struct base_data can be freed. + */ + int children_remaining; + + /* Not initialized by make_base(). */ + struct list_head list; + void *data; + unsigned long size; }; +/* + * Stack of struct base_data that have unprocessed children. + * threaded_second_pass() uses this as a source of work (the other being the + * objects array). + * + * Guarded by work_mutex. + */ +static LIST_HEAD(work_head); + +/* + * Stack of struct base_data that have children, all of whom have been + * processed or are being processed, and at least one child is being processed. + * These struct base_data must be kept around until the last child is + * processed. + * + * Guarded by work_mutex. + */ +static LIST_HEAD(done_head); + +/* + * All threads share one delta base cache. + * + * base_cache_used is guarded by work_mutex, and base_cache_limit is read-only + * in a thread. + */ +static size_t base_cache_used; +static size_t base_cache_limit; + struct thread_local { pthread_t thread; - struct base_data *base_cache; - size_t base_cache_used; int pack_fd; }; @@ -117,10 +159,6 @@ static pthread_mutex_t deepest_delta_mutex; #define deepest_delta_lock() lock_mutex(&deepest_delta_mutex) #define deepest_delta_unlock() unlock_mutex(&deepest_delta_mutex) -static pthread_mutex_t type_cas_mutex; -#define type_cas_lock() lock_mutex(&type_cas_mutex) -#define type_cas_unlock() unlock_mutex(&type_cas_mutex) - static pthread_key_t key; static inline void lock_mutex(pthread_mutex_t *mutex) @@ -144,7 +182,6 @@ static void init_thread(void) init_recursive_mutex(&read_mutex); pthread_mutex_init(&counter_mutex, NULL); pthread_mutex_init(&work_mutex, NULL); - pthread_mutex_init(&type_cas_mutex, NULL); if (show_stat) pthread_mutex_init(&deepest_delta_mutex, NULL); pthread_key_create(&key, NULL); @@ -167,7 +204,6 @@ static void cleanup_thread(void) pthread_mutex_destroy(&read_mutex); pthread_mutex_destroy(&counter_mutex); pthread_mutex_destroy(&work_mutex); - pthread_mutex_destroy(&type_cas_mutex); if (show_stat) pthread_mutex_destroy(&deepest_delta_mutex); for (i = 0; i < nr_threads; i++) @@ -364,56 +400,42 @@ static void set_thread_data(struct thread_local *data) pthread_setspecific(key, data); } -static struct base_data *alloc_base_data(void) -{ - struct base_data *base = xcalloc(1, sizeof(struct base_data)); - base->ref_last = -1; - base->ofs_last = -1; - return base; -} - static void free_base_data(struct base_data *c) { if (c->data) { FREE_AND_NULL(c->data); - get_thread_data()->base_cache_used -= c->size; + base_cache_used -= c->size; } } static void prune_base_data(struct base_data *retain) { - struct base_data *b; - struct thread_local *data = get_thread_data(); - for (b = data->base_cache; - data->base_cache_used > delta_base_cache_limit && b; - b = b->child) { - if (b->data && b != retain) - free_base_data(b); - } -} + struct list_head *pos; -static void link_base_data(struct base_data *base, struct base_data *c) -{ - if (base) - base->child = c; - else - get_thread_data()->base_cache = c; + if (base_cache_used <= base_cache_limit) + return; - c->base = base; - c->child = NULL; - if (c->data) - get_thread_data()->base_cache_used += c->size; - prune_base_data(c); -} + list_for_each_prev(pos, &done_head) { + struct base_data *b = list_entry(pos, struct base_data, list); + if (b->retain_data || b == retain) + continue; + if (b->data) { + free_base_data(b); + if (base_cache_used <= base_cache_limit) + return; + } + } -static void unlink_base_data(struct base_data *c) -{ - struct base_data *base = c->base; - if (base) - base->child = NULL; - else - get_thread_data()->base_cache = NULL; - free_base_data(c); + list_for_each_prev(pos, &work_head) { + struct base_data *b = list_entry(pos, struct base_data, list); + if (b->retain_data || b == retain) + continue; + if (b->data) { + free_base_data(b); + if (base_cache_used <= base_cache_limit) + return; + } + } } static int is_delta_type(enum object_type type) @@ -614,7 +636,7 @@ static int compare_ofs_delta_bases(off_t offset1, off_t offset2, 0; } -static int find_ofs_delta(const off_t offset, enum object_type type) +static int find_ofs_delta(const off_t offset) { int first = 0, last = nr_ofs_deltas; @@ -624,7 +646,8 @@ static int find_ofs_delta(const off_t offset, enum object_type type) int cmp; cmp = compare_ofs_delta_bases(offset, delta->offset, - type, objects[delta->obj_no].type); + OBJ_OFS_DELTA, + objects[delta->obj_no].type); if (!cmp) return next; if (cmp < 0) { @@ -637,10 +660,9 @@ static int find_ofs_delta(const off_t offset, enum object_type type) } static void find_ofs_delta_children(off_t offset, - int *first_index, int *last_index, - enum object_type type) + int *first_index, int *last_index) { - int first = find_ofs_delta(offset, type); + int first = find_ofs_delta(offset); int last = first; int end = nr_ofs_deltas - 1; @@ -668,7 +690,7 @@ static int compare_ref_delta_bases(const struct object_id *oid1, return oidcmp(oid1, oid2); } -static int find_ref_delta(const struct object_id *oid, enum object_type type) +static int find_ref_delta(const struct object_id *oid) { int first = 0, last = nr_ref_deltas; @@ -678,7 +700,8 @@ static int find_ref_delta(const struct object_id *oid, enum object_type type) int cmp; cmp = compare_ref_delta_bases(oid, &delta->oid, - type, objects[delta->obj_no].type); + OBJ_REF_DELTA, + objects[delta->obj_no].type); if (!cmp) return next; if (cmp < 0) { @@ -691,10 +714,9 @@ static int find_ref_delta(const struct object_id *oid, enum object_type type) } static void find_ref_delta_children(const struct object_id *oid, - int *first_index, int *last_index, - enum object_type type) + int *first_index, int *last_index) { - int first = find_ref_delta(oid, type); + int first = find_ref_delta(oid); int last = first; int end = nr_ref_deltas - 1; @@ -757,7 +779,8 @@ static int check_collison(struct object_entry *entry) memset(&data, 0, sizeof(data)); data.entry = entry; - data.st = open_istream(&entry->idx.oid, &type, &size, NULL); + data.st = open_istream(the_repository, &entry->idx.oid, &type, &size, + NULL); if (!data.st) return -1; if (size != entry->size || type != entry->type) @@ -865,26 +888,15 @@ static void sha1_object(const void *data, struct object_entry *obj_entry, } /* - * This function is part of find_unresolved_deltas(). There are two - * walkers going in the opposite ways. - * - * The first one in find_unresolved_deltas() traverses down from - * parent node to children, deflating nodes along the way. However, - * memory for deflated nodes is limited by delta_base_cache_limit, so - * at some point parent node's deflated content may be freed. - * - * The second walker is this function, which goes from current node up - * to top parent if necessary to deflate the node. In normal - * situation, its parent node would be already deflated, so it just - * needs to apply delta. - * - * In the worst case scenario, parent node is no longer deflated because - * we're running out of delta_base_cache_limit; we need to re-deflate - * parents, possibly up to the top base. + * Ensure that this node has been reconstructed and return its contents. * - * All deflated objects here are subject to be freed if we exceed - * delta_base_cache_limit, just like in find_unresolved_deltas(), we - * just need to make sure the last node is not freed. + * In the typical and best case, this node would already be reconstructed + * (through the invocation to resolve_delta() in threaded_second_pass()) and it + * would not be pruned. However, if pruning of this node was necessary due to + * reaching delta_base_cache_limit, this function will find the closest + * ancestor with reconstructed data that has not been pruned (or if there is + * none, the ultimate base object), and reconstruct each node in the delta + * chain in order to generate the reconstructed data for this node. */ static void *get_base_data(struct base_data *c) { @@ -901,7 +913,7 @@ static void *get_base_data(struct base_data *c) if (!delta_nr) { c->data = get_data_from_pack(obj); c->size = obj->size; - get_thread_data()->base_cache_used += c->size; + base_cache_used += c->size; prune_base_data(c); } for (; delta_nr > 0; delta_nr--) { @@ -917,7 +929,7 @@ static void *get_base_data(struct base_data *c) free(raw); if (!c->data) bad_object(obj->idx.offset, _("failed to apply delta")); - get_thread_data()->base_cache_used += c->size; + base_cache_used += c->size; prune_base_data(c); } free(delta); @@ -925,10 +937,27 @@ static void *get_base_data(struct base_data *c) return c->data; } -static void resolve_delta(struct object_entry *delta_obj, - struct base_data *base, struct base_data *result) +static struct base_data *make_base(struct object_entry *obj, + struct base_data *parent) { - void *base_data, *delta_data; + struct base_data *base = xcalloc(1, sizeof(struct base_data)); + base->base = parent; + base->obj = obj; + find_ref_delta_children(&obj->idx.oid, + &base->ref_first, &base->ref_last); + find_ofs_delta_children(obj->idx.offset, + &base->ofs_first, &base->ofs_last); + base->children_remaining = base->ref_last - base->ref_first + + base->ofs_last - base->ofs_first + 2; + return base; +} + +static struct base_data *resolve_delta(struct object_entry *delta_obj, + struct base_data *base) +{ + void *delta_data, *result_data; + struct base_data *result; + unsigned long result_size; if (show_stat) { int i = delta_obj - objects; @@ -941,113 +970,26 @@ static void resolve_delta(struct object_entry *delta_obj, obj_stat[i].base_object_no = j; } delta_data = get_data_from_pack(delta_obj); - base_data = get_base_data(base); - result->obj = delta_obj; - result->data = patch_delta(base_data, base->size, - delta_data, delta_obj->size, &result->size); + assert(base->data); + result_data = patch_delta(base->data, base->size, + delta_data, delta_obj->size, &result_size); free(delta_data); - if (!result->data) + if (!result_data) bad_object(delta_obj->idx.offset, _("failed to apply delta")); - hash_object_file(result->data, result->size, + hash_object_file(the_hash_algo, result_data, result_size, type_name(delta_obj->real_type), &delta_obj->idx.oid); - sha1_object(result->data, NULL, result->size, delta_obj->real_type, + sha1_object(result_data, NULL, result_size, delta_obj->real_type, &delta_obj->idx.oid); + + result = make_base(delta_obj, base); + result->data = result_data; + result->size = result_size; + counter_lock(); nr_resolved_deltas++; counter_unlock(); -} - -/* - * Standard boolean compare-and-swap: atomically check whether "*type" is - * "want"; if so, swap in "set" and return true. Otherwise, leave it untouched - * and return false. - */ -static int compare_and_swap_type(signed char *type, - enum object_type want, - enum object_type set) -{ - enum object_type old; - - type_cas_lock(); - old = *type; - if (old == want) - *type = set; - type_cas_unlock(); - return old == want; -} - -static struct base_data *find_unresolved_deltas_1(struct base_data *base, - struct base_data *prev_base) -{ - if (base->ref_last == -1 && base->ofs_last == -1) { - find_ref_delta_children(&base->obj->idx.oid, - &base->ref_first, &base->ref_last, - OBJ_REF_DELTA); - - find_ofs_delta_children(base->obj->idx.offset, - &base->ofs_first, &base->ofs_last, - OBJ_OFS_DELTA); - - if (base->ref_last == -1 && base->ofs_last == -1) { - free(base->data); - return NULL; - } - - link_base_data(prev_base, base); - } - - if (base->ref_first <= base->ref_last) { - struct object_entry *child = objects + ref_deltas[base->ref_first].obj_no; - struct base_data *result = alloc_base_data(); - - if (!compare_and_swap_type(&child->real_type, OBJ_REF_DELTA, - base->obj->real_type)) - BUG("child->real_type != OBJ_REF_DELTA"); - - resolve_delta(child, base, result); - if (base->ref_first == base->ref_last && base->ofs_last == -1) - free_base_data(base); - - base->ref_first++; - return result; - } - - if (base->ofs_first <= base->ofs_last) { - struct object_entry *child = objects + ofs_deltas[base->ofs_first].obj_no; - struct base_data *result = alloc_base_data(); - - assert(child->real_type == OBJ_OFS_DELTA); - child->real_type = base->obj->real_type; - resolve_delta(child, base, result); - if (base->ofs_first == base->ofs_last) - free_base_data(base); - - base->ofs_first++; - return result; - } - - unlink_base_data(base); - return NULL; -} - -static void find_unresolved_deltas(struct base_data *base) -{ - struct base_data *new_base, *prev_base = NULL; - for (;;) { - new_base = find_unresolved_deltas_1(base, prev_base); - - if (new_base) { - prev_base = base; - base = new_base; - } else { - free(base); - base = prev_base; - if (!base) - return; - prev_base = base->base; - } - } + return result; } static int compare_ofs_delta_entry(const void *a, const void *b) @@ -1068,34 +1010,135 @@ static int compare_ref_delta_entry(const void *a, const void *b) return oidcmp(&delta_a->oid, &delta_b->oid); } -static void resolve_base(struct object_entry *obj) -{ - struct base_data *base_obj = alloc_base_data(); - base_obj->obj = obj; - base_obj->data = NULL; - find_unresolved_deltas(base_obj); -} - static void *threaded_second_pass(void *data) { - set_thread_data(data); + if (data) + set_thread_data(data); for (;;) { - int i; + struct base_data *parent = NULL; + struct object_entry *child_obj; + struct base_data *child; + counter_lock(); display_progress(progress, nr_resolved_deltas); counter_unlock(); + work_lock(); - while (nr_dispatched < nr_objects && - is_delta_type(objects[nr_dispatched].type)) - nr_dispatched++; - if (nr_dispatched >= nr_objects) { - work_unlock(); - break; + if (list_empty(&work_head)) { + /* + * Take an object from the object array. + */ + while (nr_dispatched < nr_objects && + is_delta_type(objects[nr_dispatched].type)) + nr_dispatched++; + if (nr_dispatched >= nr_objects) { + work_unlock(); + break; + } + child_obj = &objects[nr_dispatched++]; + } else { + /* + * Peek at the top of the stack, and take a child from + * it. + */ + parent = list_first_entry(&work_head, struct base_data, + list); + + if (parent->ref_first <= parent->ref_last) { + int offset = ref_deltas[parent->ref_first++].obj_no; + child_obj = objects + offset; + if (child_obj->real_type != OBJ_REF_DELTA) + die("REF_DELTA at offset %"PRIuMAX" already resolved (duplicate base %s?)", + (uintmax_t) child_obj->idx.offset, + oid_to_hex(&parent->obj->idx.oid)); + child_obj->real_type = parent->obj->real_type; + } else { + child_obj = objects + + ofs_deltas[parent->ofs_first++].obj_no; + assert(child_obj->real_type == OBJ_OFS_DELTA); + child_obj->real_type = parent->obj->real_type; + } + + if (parent->ref_first > parent->ref_last && + parent->ofs_first > parent->ofs_last) { + /* + * This parent has run out of children, so move + * it to done_head. + */ + list_del(&parent->list); + list_add(&parent->list, &done_head); + } + + /* + * Ensure that the parent has data, since we will need + * it later. + * + * NEEDSWORK: If parent data needs to be reloaded, this + * prolongs the time that the current thread spends in + * the mutex. A mitigating factor is that parent data + * needs to be reloaded only if the delta base cache + * limit is exceeded, so in the typical case, this does + * not happen. + */ + get_base_data(parent); + parent->retain_data++; } - i = nr_dispatched++; work_unlock(); - resolve_base(&objects[i]); + if (parent) { + child = resolve_delta(child_obj, parent); + if (!child->children_remaining) + FREE_AND_NULL(child->data); + } else { + child = make_base(child_obj, NULL); + if (child->children_remaining) { + /* + * Since this child has its own delta children, + * we will need this data in the future. + * Inflate now so that future iterations will + * have access to this object's data while + * outside the work mutex. + */ + child->data = get_data_from_pack(child_obj); + child->size = child_obj->size; + } + } + + work_lock(); + if (parent) + parent->retain_data--; + if (child->data) { + /* + * This child has its own children, so add it to + * work_head. + */ + list_add(&child->list, &work_head); + base_cache_used += child->size; + prune_base_data(NULL); + } else { + /* + * This child does not have its own children. It may be + * the last descendant of its ancestors; free those + * that we can. + */ + struct base_data *p = parent; + + while (p) { + struct base_data *next_p; + + p->children_remaining--; + if (p->children_remaining) + break; + + next_p = p->base; + free_base_data(p); + list_del(&p->list); + free(p); + + p = next_p; + } + } + work_unlock(); } return NULL; } @@ -1196,6 +1239,7 @@ static void resolve_deltas(void) nr_ref_deltas + nr_ofs_deltas); nr_dispatched = 0; + base_cache_limit = delta_base_cache_limit * nr_threads; if (nr_threads > 1 || getenv("GIT_FORCE_THREADS")) { init_thread(); for (i = 0; i < nr_threads; i++) { @@ -1210,15 +1254,7 @@ static void resolve_deltas(void) cleanup_thread(); return; } - - for (i = 0; i < nr_objects; i++) { - struct object_entry *obj = &objects[i]; - - if (is_delta_type(obj->type)) - continue; - resolve_base(obj); - display_progress(progress, nr_resolved_deltas); - } + threaded_second_pass(¬hread_data); } /* @@ -1352,7 +1388,7 @@ static void fix_unresolved_deltas(struct hashfile *f) sorted_by_pos[i] = &ref_deltas[i]; QSORT(sorted_by_pos, nr_ref_deltas, delta_pos_compare); - if (repository_format_partial_clone) { + if (has_promisor_remote()) { /* * Prefetch the delta bases. */ @@ -1365,30 +1401,36 @@ static void fix_unresolved_deltas(struct hashfile *f) continue; oid_array_append(&to_fetch, &d->oid); } - if (to_fetch.nr) - fetch_objects(repository_format_partial_clone, - to_fetch.oid, to_fetch.nr); + promisor_remote_get_direct(the_repository, + to_fetch.oid, to_fetch.nr); oid_array_clear(&to_fetch); } for (i = 0; i < nr_ref_deltas; i++) { struct ref_delta_entry *d = sorted_by_pos[i]; enum object_type type; - struct base_data *base_obj = alloc_base_data(); + void *data; + unsigned long size; if (objects[d->obj_no].real_type != OBJ_REF_DELTA) continue; - base_obj->data = read_object_file(&d->oid, &type, - &base_obj->size); - if (!base_obj->data) + data = read_object_file(&d->oid, &type, &size); + if (!data) continue; - if (check_object_signature(&d->oid, base_obj->data, - base_obj->size, type_name(type))) + if (check_object_signature(the_repository, &d->oid, + data, size, + type_name(type))) die(_("local object %s is corrupt"), oid_to_hex(&d->oid)); - base_obj->obj = append_obj_to_pack(f, d->oid.hash, - base_obj->data, base_obj->size, type); - find_unresolved_deltas(base_obj); + + /* + * Add this as an object to the objects array and call + * threaded_second_pass() (which will pick up the added + * object). + */ + append_obj_to_pack(f, d->oid.hash, data, size, type); + threaded_second_pass(NULL); + display_progress(progress, nr_resolved_deltas); } free(sorted_by_pos); @@ -1490,11 +1532,11 @@ static void final(const char *final_pack_name, const char *curr_pack_name, } if (!from_stdin) { - printf("%s\n", sha1_to_hex(hash)); + printf("%s\n", hash_to_hex(hash)); } else { struct strbuf buf = STRBUF_INIT; - strbuf_addf(&buf, "%s\t%s\n", report, sha1_to_hex(hash)); + strbuf_addf(&buf, "%s\t%s\n", report, hash_to_hex(hash)); write_or_die(1, buf.buf, buf.len); strbuf_release(&buf); @@ -1552,13 +1594,9 @@ static void read_v2_anomalous_offsets(struct packed_git *p, { const uint32_t *idx1, *idx2; uint32_t i; - const uint32_t hashwords = the_hash_algo->rawsz / sizeof(uint32_t); /* The address of the 4-byte offset table */ - idx1 = (((const uint32_t *)p->index_data) - + 2 /* 8-byte header */ - + 256 /* fan out */ - + hashwords * p->num_objects /* object ID table */ + idx1 = (((const uint32_t *)((const uint8_t *)p->index_data + p->crc_offset)) + p->num_objects /* CRC32 table */ ); @@ -1668,6 +1706,7 @@ int cmd_index_pack(int argc, const char **argv, const char *prefix) unsigned char pack_hash[GIT_MAX_RAWSZ]; unsigned foreign_nr = 1; /* zero is a "good" value, assume bad */ int report_end_of_input = 0; + int hash_algo = 0; /* * index-pack never needs to fetch missing objects except when @@ -1761,6 +1800,11 @@ int cmd_index_pack(int argc, const char **argv, const char *prefix) die(_("bad %s"), arg); } else if (skip_prefix(arg, "--max-input-size=", &arg)) { max_input_size = strtoumax(arg, NULL, 10); + } else if (skip_prefix(arg, "--object-format=", &arg)) { + hash_algo = hash_algo_by_name(arg); + if (hash_algo == GIT_HASH_UNKNOWN) + die(_("unknown hash algorithm '%s'"), arg); + repo_set_hash_algo(the_repository, hash_algo); } else usage(index_pack_usage); continue; @@ -1777,6 +1821,8 @@ int cmd_index_pack(int argc, const char **argv, const char *prefix) die(_("--fix-thin cannot be used without --stdin")); if (from_stdin && !startup_info->have_repository) die(_("--stdin requires a git repository")); + if (from_stdin && hash_algo) + die(_("--object-format cannot be used with --stdin")); if (!index_name && pack_name) index_name = derive_filename(pack_name, "idx", &index_name_buf); @@ -1791,9 +1837,22 @@ int cmd_index_pack(int argc, const char **argv, const char *prefix) if (HAVE_THREADS && !nr_threads) { nr_threads = online_cpus(); - /* An experiment showed that more threads does not mean faster */ - if (nr_threads > 3) - nr_threads = 3; + /* + * Experiments show that going above 20 threads doesn't help, + * no matter how many cores you have. Below that, we tend to + * max at half the number of online_cpus(), presumably because + * half of those are hyperthreads rather than full cores. We'll + * never reduce the level below "3", though, to match a + * historical value that nobody complained about. + */ + if (nr_threads < 4) + ; /* too few cores to consider capping */ + else if (nr_threads < 6) + nr_threads = 3; /* historic cap */ + else if (nr_threads < 40) + nr_threads /= 2; + else + nr_threads = 20; /* hard cap */ } curr_pack = open_pack_file(pack_name); -- cgit 1.4.1