diff options
author | Junio C Hamano <gitster@pobox.com> | 2023-07-21 23:47:26 +0300 |
---|---|---|
committer | Junio C Hamano <gitster@pobox.com> | 2023-07-21 23:47:26 +0300 |
commit | 39fe402d6727efb6c98ddca19fae1f094ffaa6b3 (patch) | |
tree | 816dae9b193dd9a7521d2bc213c10ff8010c277a /refs/packed-backend.c | |
parent | cba07a324d2cda06dd7a7b35b4579f800de024aa (diff) | |
parent | 98456eff08069696708b24ab4f1152f06a3b47f9 (diff) |
Merge branch 'tb/refs-exclusion-and-packed-refs'
Enumerating refs in the packed-refs file, while excluding refs that
match certain patterns, has been optimized.
* tb/refs-exclusion-and-packed-refs:
ls-refs.c: avoid enumerating hidden refs where possible
upload-pack.c: avoid enumerating hidden refs where possible
builtin/receive-pack.c: avoid enumerating hidden references
refs.h: implement `hidden_refs_to_excludes()`
refs.h: let `for_each_namespaced_ref()` take excluded patterns
revision.h: store hidden refs in a `strvec`
refs/packed-backend.c: add trace2 counters for jump list
refs/packed-backend.c: implement jump lists to avoid excluded pattern(s)
refs/packed-backend.c: refactor `find_reference_location()`
refs: plumb `exclude_patterns` argument throughout
builtin/for-each-ref.c: add `--exclude` option
ref-filter.c: parameterize match functions over patterns
ref-filter: add `ref_filter_clear()`
ref-filter: clear reachable list pointers after freeing
ref-filter.h: provide `REF_FILTER_INIT`
refs.c: rename `ref_filter`
Diffstat (limited to 'refs/packed-backend.c')
-rw-r--r-- | refs/packed-backend.c | 204 |
1 files changed, 182 insertions, 22 deletions
diff --git a/refs/packed-backend.c b/refs/packed-backend.c index 27bd6339ff..59c78d7941 100644 --- a/refs/packed-backend.c +++ b/refs/packed-backend.c @@ -13,6 +13,7 @@ #include "../statinfo.h" #include "../wrapper.h" #include "../write-or-die.h" +#include "../trace2.h" enum mmap_strategy { /* @@ -304,7 +305,8 @@ static int cmp_packed_ref_records(const void *v1, const void *v2) * Compare a snapshot record at `rec` to the specified NUL-terminated * refname. */ -static int cmp_record_to_refname(const char *rec, const char *refname) +static int cmp_record_to_refname(const char *rec, const char *refname, + int start) { const char *r1 = rec + the_hash_algo->hexsz + 1; const char *r2 = refname; @@ -313,7 +315,7 @@ static int cmp_record_to_refname(const char *rec, const char *refname) if (*r1 == '\n') return *r2 ? -1 : 0; if (!*r2) - return 1; + return start ? 1 : -1; if (*r1 != *r2) return (unsigned char)*r1 < (unsigned char)*r2 ? -1 : +1; r1++; @@ -528,22 +530,9 @@ static int load_contents(struct snapshot *snapshot) return 1; } -/* - * Find the place in `snapshot->buf` where the start of the record for - * `refname` starts. If `mustexist` is true and the reference doesn't - * exist, then return NULL. If `mustexist` is false and the reference - * doesn't exist, then return the point where that reference would be - * inserted, or `snapshot->eof` (which might be NULL) if it would be - * inserted at the end of the file. In the latter mode, `refname` - * doesn't have to be a proper reference name; for example, one could - * search for "refs/replace/" to find the start of any replace - * references. - * - * The record is sought using a binary search, so `snapshot->buf` must - * be sorted. - */ -static const char *find_reference_location(struct snapshot *snapshot, - const char *refname, int mustexist) +static const char *find_reference_location_1(struct snapshot *snapshot, + const char *refname, int mustexist, + int start) { /* * This is not *quite* a garden-variety binary search, because @@ -573,7 +562,7 @@ static const char *find_reference_location(struct snapshot *snapshot, mid = lo + (hi - lo) / 2; rec = find_start_of_record(lo, mid); - cmp = cmp_record_to_refname(rec, refname); + cmp = cmp_record_to_refname(rec, refname, start); if (cmp < 0) { lo = find_end_of_record(mid, hi); } else if (cmp > 0) { @@ -590,6 +579,41 @@ static const char *find_reference_location(struct snapshot *snapshot, } /* + * Find the place in `snapshot->buf` where the start of the record for + * `refname` starts. If `mustexist` is true and the reference doesn't + * exist, then return NULL. If `mustexist` is false and the reference + * doesn't exist, then return the point where that reference would be + * inserted, or `snapshot->eof` (which might be NULL) if it would be + * inserted at the end of the file. In the latter mode, `refname` + * doesn't have to be a proper reference name; for example, one could + * search for "refs/replace/" to find the start of any replace + * references. + * + * The record is sought using a binary search, so `snapshot->buf` must + * be sorted. + */ +static const char *find_reference_location(struct snapshot *snapshot, + const char *refname, int mustexist) +{ + return find_reference_location_1(snapshot, refname, mustexist, 1); +} + +/* + * Find the place in `snapshot->buf` after the end of the record for + * `refname`. In other words, find the location of first thing *after* + * `refname`. + * + * Other semantics are identical to the ones in + * `find_reference_location()`. + */ +static const char *find_reference_location_end(struct snapshot *snapshot, + const char *refname, + int mustexist) +{ + return find_reference_location_1(snapshot, refname, mustexist, 0); +} + +/* * Create a newly-allocated `snapshot` of the `packed-refs` file in * its current state and return it. The return value will already have * its reference count incremented. @@ -780,6 +804,13 @@ struct packed_ref_iterator { /* The end of the part of the buffer that will be iterated over: */ const char *eof; + struct jump_list_entry { + const char *start; + const char *end; + } *jump; + size_t jump_nr, jump_alloc; + size_t jump_cur; + /* Scratch space for current values: */ struct object_id oid, peeled; struct strbuf refname_buf; @@ -797,14 +828,36 @@ struct packed_ref_iterator { */ static int next_record(struct packed_ref_iterator *iter) { - const char *p = iter->pos, *eol; + const char *p, *eol; strbuf_reset(&iter->refname_buf); + /* + * If iter->pos is contained within a skipped region, jump past + * it. + * + * Note that each skipped region is considered at most once, + * since they are ordered based on their starting position. + */ + while (iter->jump_cur < iter->jump_nr) { + struct jump_list_entry *curr = &iter->jump[iter->jump_cur]; + if (iter->pos < curr->start) + break; /* not to the next jump yet */ + + iter->jump_cur++; + if (iter->pos < curr->end) { + iter->pos = curr->end; + trace2_counter_add(TRACE2_COUNTER_ID_PACKED_REFS_JUMPS, 1); + /* jumps are coalesced, so only one jump is necessary */ + break; + } + } + if (iter->pos == iter->eof) return ITER_DONE; iter->base.flags = REF_ISPACKED; + p = iter->pos; if (iter->eof - p < the_hash_algo->hexsz + 2 || parse_oid_hex(p, &iter->oid, &p) || @@ -912,6 +965,7 @@ static int packed_ref_iterator_abort(struct ref_iterator *ref_iterator) int ok = ITER_DONE; strbuf_release(&iter->refname_buf); + free(iter->jump); release_snapshot(iter->snapshot); base_ref_iterator_free(ref_iterator); return ok; @@ -923,9 +977,112 @@ static struct ref_iterator_vtable packed_ref_iterator_vtable = { .abort = packed_ref_iterator_abort }; +static int jump_list_entry_cmp(const void *va, const void *vb) +{ + const struct jump_list_entry *a = va; + const struct jump_list_entry *b = vb; + + if (a->start < b->start) + return -1; + if (a->start > b->start) + return 1; + return 0; +} + +static int has_glob_special(const char *str) +{ + const char *p; + for (p = str; *p; p++) { + if (is_glob_special(*p)) + return 1; + } + return 0; +} + +static void populate_excluded_jump_list(struct packed_ref_iterator *iter, + struct snapshot *snapshot, + const char **excluded_patterns) +{ + size_t i, j; + const char **pattern; + struct jump_list_entry *last_disjoint; + + if (!excluded_patterns) + return; + + for (pattern = excluded_patterns; *pattern; pattern++) { + struct jump_list_entry *e; + const char *start, *end; + + /* + * We can't feed any excludes with globs in them to the + * refs machinery. It only understands prefix matching. + * We likewise can't even feed the string leading up to + * the first meta-character, as something like "foo[a]" + * should not exclude "foobar" (but the prefix "foo" + * would match that and mark it for exclusion). + */ + if (has_glob_special(*pattern)) + continue; + + start = find_reference_location(snapshot, *pattern, 0); + end = find_reference_location_end(snapshot, *pattern, 0); + + if (start == end) + continue; /* nothing to jump over */ + + ALLOC_GROW(iter->jump, iter->jump_nr + 1, iter->jump_alloc); + + e = &iter->jump[iter->jump_nr++]; + e->start = start; + e->end = end; + } + + if (!iter->jump_nr) { + /* + * Every entry in exclude_patterns has a meta-character, + * nothing to do here. + */ + return; + } + + QSORT(iter->jump, iter->jump_nr, jump_list_entry_cmp); + + /* + * As an optimization, merge adjacent entries in the jump list + * to jump forwards as far as possible when entering a skipped + * region. + * + * For example, if we have two skipped regions: + * + * [[A, B], [B, C]] + * + * we want to combine that into a single entry jumping from A to + * C. + */ + last_disjoint = iter->jump; + + for (i = 1, j = 1; i < iter->jump_nr; i++) { + struct jump_list_entry *ours = &iter->jump[i]; + if (ours->start <= last_disjoint->end) { + /* overlapping regions extend the previous one */ + last_disjoint->end = last_disjoint->end > ours->end + ? last_disjoint->end : ours->end; + } else { + /* otherwise, insert a new region */ + iter->jump[j++] = *ours; + last_disjoint = ours; + } + } + + iter->jump_nr = j; + iter->jump_cur = 0; +} + static struct ref_iterator *packed_ref_iterator_begin( struct ref_store *ref_store, - const char *prefix, unsigned int flags) + const char *prefix, const char **exclude_patterns, + unsigned int flags) { struct packed_ref_store *refs; struct snapshot *snapshot; @@ -957,6 +1114,9 @@ static struct ref_iterator *packed_ref_iterator_begin( ref_iterator = &iter->base; base_ref_iterator_init(ref_iterator, &packed_ref_iterator_vtable, 1); + if (exclude_patterns) + populate_excluded_jump_list(iter, snapshot, exclude_patterns); + iter->snapshot = snapshot; acquire_snapshot(snapshot); @@ -1150,7 +1310,7 @@ static int write_with_updates(struct packed_ref_store *refs, * list of refs is exhausted, set iter to NULL. When the list * of updates is exhausted, leave i set to updates->nr. */ - iter = packed_ref_iterator_begin(&refs->base, "", + iter = packed_ref_iterator_begin(&refs->base, "", NULL, DO_FOR_EACH_INCLUDE_BROKEN); if ((ok = ref_iterator_advance(iter)) != ITER_OK) iter = NULL; |