refs: implement jump lists for packed backend
Get series with b4
b4 am [email protected]Versions newest first · linked by author and title
- v5 Latest16 patches 4 repliesIn review
- v416 patches 20 repliesSuperseded
- v316 patches 11 repliesSuperseded
Earlier versions · 2
| Version | Posted | Patches | Replies | Status |
|---|---|---|---|---|
| v2 | 16 patches | 8 replies | Superseded | |
| v1 | 15 patches | 22 replies | Superseded |
Patches in v5 No applies recorded yet
| # | Subject and files | Size | Replies | Applied |
|---|---|---|---|---|
| 1/16 | refs.c: rename `ref_filter`refs.c | +8 | 0 replies | |
| 2/16 | ref-filter.h: provide `REF_FILTER_INIT`builtin/ builtin/ builtin/ +2 more | +7 | 0 replies | |
| 3/16 | ref-filter: clear reachable list pointers after freeingref-filter.c | +7 | 0 replies | |
| 4/16 | ref-filter: add `ref_filter_clear()`builtin/ builtin/ builtin/ +4 more | +24 | 0 replies | |
| 5/16 | ref-filter.c: parameterize match functions over patternsref-filter.c | +10 | 0 replies | |
| 6/16 | builtin/for-each-ref.c: add `--exclude` optionDocumentation/ builtin/ ref-filter.c +2 more | +62 | 0 replies | |
| 7/16 | refs: plumb `exclude_patterns` argument throughoutls-refs.c ref-filter.c refs.c +6 more | +42 | 0 replies | |
| 8/16 | refs/packed-backend.c: refactor `find_reference_location()`refs/ | +22 | 0 replies | |
| 9/16 | refs/packed-backend.c: implement jump lists to avoid excluded pattern(s)ref-filter.c refs.h refs/ +2 more | +276 | 0 replies | |
| 10/16 | refs/packed-backend.c: add trace2 counters for jump listrefs/ t/ trace2.h +1 more | +49 | 0 replies | |
| 11/16 | revision.h: store hidden refs in a `strvec`builtin/ ls-refs.c refs.c +4 more | +22 | 0 replies | |
| 12/16 | refs.h: let `for_each_namespaced_ref()` take excluded patternshttp-backend.c refs.c refs.h +1 more | +13 | 0 replies | |
| 13/16 | refs.h: implement `hidden_refs_to_excludes()`refs.c refs.h | +30 | 0 replies | |
| 14/16 | builtin/receive-pack.c: avoid enumerating hidden referencesbuiltin/ | +3 | 0 replies | |
| 15/16 | upload-pack.c: avoid enumerating hidden refs where possibleupload-pack.c | +31 | 0 replies | |
| 16/16 | ls-refs.c: avoid enumerating hidden refs where possiblels-refs.c | +2 | 0 replies |
Reviews trailers per patch
None of the 16 patches has a Reviewed-by or Acked-by.
| Patch | Taylor Blau | Jeff King |
|---|---|---|
| 1/16 | ||
| 2/16 | ||
| 3/16 | ||
| 4/16 | ||
| 5/16 | Co-authored-by | |
| 6/16 | Co-authored-by | |
| 7/16 | ||
| 8/16 | Co-authored-by | |
| 9/16 | Co-authored-by | |
| 10/16 | ||
| 11/16 | ||
| 12/16 | ||
| 13/16 | ||
| 14/16 | ||
| 15/16 | ||
| 16/16 |
Trailers given in replies are filled; those carried in the patches from earlier versions are outlined with dashes.
Cover letter [PATCH v5 00/16] refs: implement jump lists for packed backend
Here is another reroll of my series to implement jump (née skip) lists for the packed refs backend, based on top of the current 'master'.
This responds to a review of the entire series that Peff gave a couple of weeks ago[1], which should satisfy all of the comments that he raised, most of which were relatively minor.
The notable changes from last time are:
- clarifying some commit messages, notably to explicitly state that certain clean-ups do not indicate existing bugs, but are defensive against potential future ones
- polishing up some of the API changes, to avoid having match_name_as_path() take a ref_filter pointer.
- more timing data and documentation in the first substantive patch
- clean-up in the upload-pack.c to make the changes clearer
As usual, a range-diff is included below for convenience.
Thanks in advance for your review!
[1]: https://lore.kernel.org/git/[email protected]/
Jeff King (5):
refs.c: rename ref_filter
ref-filter.h: provide REF_FILTER_INIT
ref-filter: clear reachable list pointers after freeing
ref-filter: add ref_filter_clear() ref-filter.c: parameterize match functions over patterns
Taylor Blau (11):
builtin/for-each-ref.c: add --exclude option
refs: plumb exclude_patterns argument throughout refs/packed-backend.c: refactor find_reference_location() refs/packed-backend.c: implement jump lists to avoid excluded
pattern(s)
refs/packed-backend.c: add trace2 counters for jump list revision.h: store hidden refs in a strvec
refs.h: let for_each_namespaced_ref() take excluded patterns refs.h: implement hidden_refs_to_excludes() builtin/receive-pack.c: avoid enumerating hidden references upload-pack.c: avoid enumerating hidden refs where possible ls-refs.c: avoid enumerating hidden refs where possible
Documentation/git-for-each-ref.txt | 6 + builtin/branch.c | 4 +- builtin/for-each-ref.c | 7 +- builtin/receive-pack.c | 8 +- builtin/tag.c | 4 +- http-backend.c | 2 +- ls-refs.c | 7 +- ref-filter.c | 66 +++++++--- ref-filter.h | 12 ++ refs.c | 85 ++++++++---- refs.h | 29 +++- refs/debug.c | 5 +- refs/files-backend.c | 5 +- refs/packed-backend.c | 204 +++++++++++++++++++++++++---- refs/refs-internal.h | 7 +- revision.c | 4 +- revision.h | 5 +- t/helper/test-reach.c | 2 +- t/helper/test-ref-store.c | 10 ++ t/t0041-usage.sh | 1 + t/t1419-exclude-refs.sh | 122 +++++++++++++++++ t/t3402-rebase-merge.sh | 1 + t/t6300-for-each-ref.sh | 35 +++++ trace2.h | 2 + trace2/tr2_ctr.c | 5 + upload-pack.c | 47 +++++-- 26 files changed, 579 insertions(+), 106 deletions(-) create mode 100755 t/t1419-exclude-refs.sh
Range-diff against v4:
1: c12def5a30a ! 1: 5b5ccc40d6b refs.c: rename ref_filter
@@ Commit message
refs.c: rename ref_filter
The refs machinery has its own implementation of a ref_filter (used by
- for-each-ref), which is distinct from the ref-filler.h API (also
+ for-each-ref), which is distinct from the ref-filter.h API (also
used by for-each-ref, among other things).
Rename the one within refs.c to more clearly indicate its purpose.
2: 7ce82b6a5a4 ! 2: 0c4e995f1d3 ref-filter.h: provide REF_FILTER_INIT
@@ Commit message
Provide a sane initialization value for struct ref_filter, which in a subsequent patch will be used to initialize a new field.
- In the meantime, fix a case in test-reach.c where its ref_filter is
- not even zero-initialized.
+ In the meantime, ensure that the ref_filter struct used in the
+ test-helper's cmd__reach() is zero-initialized. The lack of
+ initialization is OK, since commit_contains() only looks at the single
+ with_commit_tag_algo field that *is* initialized directly above.
+
+ So this does not fix a bug, but rather prevents one from biting us in
+ the future.
3: 7e6bf7766d0 ! 3: cea1e88d358 ref-filter: clear reachable list pointers after freeing
@@ Metadata
## Commit message ##
ref-filter: clear reachable list pointers after freeing
- In reach_filter(), we pop all commits from the reachable lists, leaving
- them empty. But because we're operating on a list pointer that was
- passed by value, the original filter.reachable_from pointer is left
- dangling.
+ In reach_filter(), we pop all commits from the reachable lists,
+ leaving them empty. But because we're operating on a list pointer that
+ was passed by value, the original filter.reachable_from and
+ filter.unreachable_from pointers are left dangling.
+
+ As is the case with the previous commit, nobody touches either of these
+ fields after calling reach_filter(), so leaving them dangling is OK.
+ But this future proofs against dangerous situations.
4: 777e71004d6 = 4: 00a4532d54d ref-filter: add `ref_filter_clear()`
5: 39e9b0f50d0 ! 5: 3ab03ac20df ref-filter.c: parameterize match functions over patterns
@@ ref-filter.c: static int get_ref_atom_value(struct ref_array_item *ref, int atom
*/
-static int match_pattern(const struct ref_filter *filter, const char *refname)
+static int match_pattern(const char **patterns, const char *refname,
-+ const int ignore_case)
++ int ignore_case)
{
- const char **patterns = filter->name_patterns;
unsigned flags = 0;
@@ ref-filter.c: static int match_pattern(const struct ref_filter *filter, const ch
* wildcard (e.g. the same ref matches "refs/heads/m*", too).
*/
-static int match_name_as_path(const struct ref_filter *filter, const char *refname)
-+static int match_name_as_path(const struct ref_filter *filter,
-+ const char **pattern,
-+ const char *refname)
++static int match_name_as_path(const char **pattern, const char *refname,
++ int ignore_case)
{
- const char **pattern = filter->name_patterns;
int namelen = strlen(refname);
unsigned flags = WM_PATHNAME;
+- if (filter->ignore_case)
++ if (ignore_case)
+ flags |= WM_CASEFOLD;
+
+ for (; *pattern; pattern++) {
@@ ref-filter.c: static int filter_pattern_match(struct ref_filter *filter, const char *refname)
if (!*filter->name_patterns)
return 1; /* No pattern always matches */
if (filter->match_as_path)
- return match_name_as_path(filter, refname);
- return match_pattern(filter, refname);
-+ return match_name_as_path(filter, filter->name_patterns, refname);
++ return match_name_as_path(filter->name_patterns, refname,
++ filter->ignore_case);
+ return match_pattern(filter->name_patterns, refname,
+ filter->ignore_case);
}
6: c4fd47fd750 ! 6: aa881ca06fa builtin/for-each-ref.c: add `--exclude` option
@@ ref-filter.c: static int filter_pattern_match(struct ref_filter *filter, const c
+ if (!filter->exclude.nr)
+ return 0;
+ if (filter->match_as_path)
-+ return match_name_as_path(filter, filter->exclude.v, refname);
++ return match_name_as_path(filter->exclude.v, refname,
++ filter->ignore_case);
+ return match_pattern(filter->exclude.v, refname, filter->ignore_case);
+}
+
7: e6b50c50219 = 7: 81e223de0c8 refs: plumb `exclude_patterns` argument throughout
8: a0990b2916c = 8: 25c099a528c refs/packed-backend.c: refactor `find_reference_location()`
9: 386ed468fa7 ! 9: af0ce43cc90 refs/packed-backend.c: implement jump lists to avoid excluded pattern(s)
@@ Commit message
$ hyperfine \
'git for-each-ref --format="%(objectname) %(refname)" | grep -vE "^[0-9a-f]{40} refs/pull/"' \
+ 'git.prev for-each-ref --format="%(objectname) %(refname)" --exclude="refs/pull"' \
'git.compile for-each-ref --format="%(objectname) %(refname)" --exclude="refs/pull"'
Benchmark 1: git for-each-ref --format="%(objectname) %(refname)" | grep -vE "^[0-9a-f]{40} refs/pull/"
- Time (mean ± σ): 802.7 ms ± 2.1 ms [User: 691.6 ms, System: 147.0 ms]
- Range (min … max): 800.0 ms … 807.7 ms 10 runs
+ Time (mean ± σ): 798.1 ms ± 3.3 ms [User: 687.6 ms, System: 146.4 ms]
+ Range (min … max): 794.5 ms … 805.5 ms 10 runs
- Benchmark 2: git.compile for-each-ref --format="%(objectname) %(refname)" --exclude="refs/pull"
- Time (mean ± σ): 4.7 ms ± 0.3 ms [User: 0.7 ms, System: 4.0 ms]
- Range (min … max): 4.3 ms … 6.7 ms 422 runs
+ Benchmark 2: git.prev for-each-ref --format="%(objectname) %(refname)" --exclude="refs/pull"
+ Time (mean ± σ): 98.9 ms ± 1.4 ms [User: 93.1 ms, System: 5.7 ms]
+ Range (min … max): 97.0 ms … 104.0 ms 29 runs
+
+ Benchmark 3: git.compile for-each-ref --format="%(objectname) %(refname)" --exclude="refs/pull"
+ Time (mean ± σ): 4.5 ms ± 0.2 ms [User: 0.7 ms, System: 3.8 ms]
+ Range (min … max): 4.1 ms … 5.8 ms 524 runs
Summary
'git.compile for-each-ref --format="%(objectname) %(refname)" --exclude="refs/pull"' ran
- 172.03 ± 9.60 times faster than 'git for-each-ref --format="%(objectname) %(refname)" | grep -vE "^[0-9a-f]{40} refs/pull/"'
+ 21.87 ± 1.05 times faster than 'git.prev for-each-ref --format="%(objectname) %(refname)" --exclude="refs/pull"'
+ 176.52 ± 8.19 times faster than 'git for-each-ref --format="%(objectname) %(refname)" | grep -vE "^[0-9a-f]{40} refs/pull/"'
+
+ (Comparing stock git and this patch isn't quite fair, since an earlier
+ commit in this series adds a naive implementation of the `--exclude`
+ option. `git.prev` is built from the previous commit and includes this
+ naive implementation).
Using the jump list is fairly straightforward (see the changes to
`refs/packed-backend.c::next_record()`), but constructing the list is
@@ ref-filter.c: static int for_each_fullref_in_pattern(struct ref_filter *filter,
/*
+ ## refs.h ##
+@@ refs.h: int for_each_ref(each_ref_fn fn, void *cb_data);
+ */
+ int for_each_ref_in(const char *prefix, each_ref_fn fn, void *cb_data);
+
++/*
++ * references matching any pattern in "exclude_patterns" are omitted from the
++ * result set on a best-effort basis.
++ */
+ int refs_for_each_fullref_in(struct ref_store *refs, const char *prefix,
+ const char **exclude_patterns,
+ each_ref_fn fn, void *cb_data);
+
## refs/packed-backend.c ##
@@ refs/packed-backend.c: static int cmp_packed_ref_records(const void *v1, const void *v2)
* Compare a snapshot record at `rec` to the specified NUL-terminated
@@ refs/packed-backend.c: struct packed_ref_iterator {
+ iter->jump_cur++;
+ if (iter->pos < curr->end) {
+ iter->pos = curr->end;
++ /* jumps are coalesced, so only one jump is necessary */
+ break;
+ }
+ }
@@ refs/packed-backend.c: static struct ref_iterator_vtable packed_ref_iterator_vta
+
+ 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/packed-backend.c: static struct ref_iterator_vtable packed_ref_iterator_vta
+ 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 = find_reference_location(snapshot, *pattern, 0);
-+ e->end = find_reference_location_end(snapshot, *pattern, 0);
++ e->start = start;
++ e->end = end;
+ }
+
+ if (!iter->jump_nr) {
@@ refs/packed-backend.c: static struct ref_iterator_vtable packed_ref_iterator_vta
+
+ for (i = 1, j = 1; i < iter->jump_nr; i++) {
+ struct jump_list_entry *ours = &iter->jump[i];
-+
-+ if (ours->start == ours->end) {
-+ /* ignore empty regions (no matching entries) */
-+ continue;
-+ } else if (ours->start <= last_disjoint->end) {
++ 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;
@@ refs/packed-backend.c: static struct ref_iterator_vtable packed_ref_iterator_vta
+ /* otherwise, insert a new region */
+ iter->jump[j++] = *ours;
+ last_disjoint = ours;
-+
+ }
+ }
+
10: 49c8f5173aa ! 10: e150941c1d1 refs/packed-backend.c: add trace2 counters for jump list
@@ Commit message
## refs/packed-backend.c ##
@@
- #include "../chdir-notify.h"
+ #include "../statinfo.h"
#include "../wrapper.h"
#include "../write-or-die.h"
+#include "../trace2.h"
@@ refs/packed-backend.c: static int next_record(struct packed_ref_iterator *iter)
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;
}
- }
## t/t1419-exclude-refs.sh ##
@@ t/t1419-exclude-refs.sh: TEST_PASSES_SANITIZE_LEAK=true
11: dd856a3982b = 11: a5093d52008 revision.h: store hidden refs in a `strvec`
12: 845904853ee < -: ----------- refs/packed-backend.c: ignore complicated hidden refs rules
13: 8d4d7cc22ee ! 12: 7e72c23c8a4 refs.h: let `for_each_namespaced_ref()` take excluded patterns
@@ refs.h: int for_each_glob_ref_in(each_ref_fn fn, const char *pattern,
int head_ref_namespaced(each_ref_fn fn, void *cb_data);
-int for_each_namespaced_ref(each_ref_fn fn, void *cb_data);
++/*
++ * references matching any pattern in "exclude_patterns" are omitted from the
++ * result set on a best-effort basis.
++ */
+int for_each_namespaced_ref(const char **exclude_patterns,
+ each_ref_fn fn, void *cb_data); -: ----------- > 13: f99d89d53b9 refs.h: implement `hidden_refs_to_excludes()`
14: 49c665f9f8f ! 14: 96aada36f9b builtin/receive-pack.c: avoid enumerating hidden references
@@ builtin/receive-pack.c: static void write_head_info(void)
- for_each_ref(show_ref_cb, &seen);
+ refs_for_each_fullref_in(get_main_ref_store(the_repository), "",
-+ hidden_refs.v, show_ref_cb, &seen);
++ hidden_refs_to_excludes(&hidden_refs),
++ show_ref_cb, &seen);
for_each_alternate_ref(show_one_alternate_ref, &seen);
oidset_clear(&seen);
if (!sent_capabilities)
15: 19bf4a52d69 ! 15: 8544a647798 upload-pack.c: avoid enumerating hidden refs where possible
@@ upload-pack.c: static int get_common_commits(struct upload_pack_data *data,
+static int allow_hidden_refs(enum allow_uor allow_uor)
+{
-+ return allow_uor & (ALLOW_TIP_SHA1 | ALLOW_REACHABLE_SHA1);
++ if ((allow_uor & ALLOW_ANY_SHA1) == ALLOW_ANY_SHA1)
++ return 1;
++ return !(allow_uor & (ALLOW_TIP_SHA1 | ALLOW_REACHABLE_SHA1));
+}
+
+static void for_each_namespaced_ref_1(each_ref_fn fn,
+ struct upload_pack_data *data)
+{
++ const char **excludes = NULL;
+ /*
+ * If `data->allow_uor` allows fetching hidden refs, we need to
+ * mark all references (including hidden ones), to check in
@@ upload-pack.c: static int get_common_commits(struct upload_pack_data *data,
+ * hidden references.
+ */
+ if (allow_hidden_refs(data->allow_uor))
-+ for_each_namespaced_ref(NULL, fn, data);
-+ else
-+ for_each_namespaced_ref(data->hidden_refs.v, fn, data);
++ excludes = hidden_refs_to_excludes(&data->hidden_refs);
++
++ for_each_namespaced_ref(excludes, fn, data);
+}
++
+
static int is_our_ref(struct object *o, enum allow_uor allow_uor)
{
- int allow_hidden_ref = (allow_uor &
- (ALLOW_TIP_SHA1 | ALLOW_REACHABLE_SHA1));
- return o->flags & ((allow_hidden_ref ? HIDDEN_REF : 0) | OUR_REF);
-+ return o->flags & ((allow_hidden_refs(allow_uor) ? HIDDEN_REF : 0) | OUR_REF);
++ return o->flags & ((allow_hidden_refs(allow_uor) ? 0 : HIDDEN_REF) | OUR_REF);
}
/*
16: ea6cbaf292f ! 16: dff068c469f ls-refs.c: avoid enumerating hidden refs where possible
@@ ls-refs.c: int ls_refs(struct repository *r, struct packet_reader *request)
refs_for_each_fullref_in_prefixes(get_main_ref_store(r),
get_git_namespace(), data.prefixes.v,
- NULL, send_ref, &data);
-+ data.hidden_refs.v, send_ref, &data);
++ hidden_refs_to_excludes(&data.hidden_refs),
++ send_ref, &data);
packet_fflush(stdout);
strvec_clear(&data.prefixes);
strbuf_release(&data.buf);Signature · 1 line
2.41.0.343.gdff068c469f