From: Taylor Blau <me@ttaylorr.com>
To: git@vger.kernel.org
Cc: Jeff King <peff@peff.net>, Elijah Newren <newren@gmail.com>,
Junio C Hamano <gitster@pobox.com>
Subject: [PATCH 16/24] pseudo-merge: implement support for reading pseudo-merge commits
Date: Wed, 20 Mar 2024 18:05:47 -0400 [thread overview]
Message-ID: <792cc863154a2671291efad6a64ac8a034dd4bb4.1710972293.git.me@ttaylorr.com> (raw)
In-Reply-To: <cover.1710972293.git.me@ttaylorr.com>
Implement the basic API for reading pseudo-merge bitmaps, which consists
of four basic functions:
- pseudo_merge_bitmap()
- use_pseudo_merge()
- apply_pseudo_merges_for_commit()
- cascade_pseudo_merges()
These functions are all documented in pseudo-merge.h, but their rough
descriptions are as follows:
- pseudo_merge_bitmap() reads and inflates the objects EWAH bitmap for
a given pseudo-merge
- use_pseudo_merge() does the same as pseudo_merge_bitmap(), but on
the commits EWAH bitmap, not the objects bitmap
- apply_pseudo_merges_for_commit() applies all satisfied pseudo-merge
commits for a given result set, and cascades any yet-unsatisfied
pseudo-merges if any were applied in the previous step
- cascade_pseudo_merges() applies all pseudo-merges which are
satisfied but have not been previously applied, repeating this
process until no more pseudo-merges can be applied
The core of the API is the latter two functions, which are responsible
for applying pseudo-merges during the object traversal implemented in
the pack-bitmap machinery.
The other two functions (pseudo_merge_bitmap(), and use_pseudo_merge())
are low-level ways to interact with the pseudo-merge machinery, which
will be useful in future commits.
Signed-off-by: Taylor Blau <me@ttaylorr.com>
---
pseudo-merge.c | 231 +++++++++++++++++++++++++++++++++++++++++++++++++
pseudo-merge.h | 44 ++++++++++
2 files changed, 275 insertions(+)
diff --git a/pseudo-merge.c b/pseudo-merge.c
index d18de0a266b..e111c9cd1a6 100644
--- a/pseudo-merge.c
+++ b/pseudo-merge.c
@@ -10,6 +10,7 @@
#include "commit.h"
#include "alloc.h"
#include "progress.h"
+#include "hex.h"
#define DEFAULT_PSEUDO_MERGE_DECAY 1.0f
#define DEFAULT_PSEUDO_MERGE_MAX_MERGES 64
@@ -451,3 +452,233 @@ void free_pseudo_merge_map(struct pseudo_merge_map *pm)
}
free(pm->v);
}
+
+struct pseudo_merge_commit_ext {
+ uint32_t nr;
+ const unsigned char *ptr;
+};
+
+static int pseudo_merge_ext_at(const struct pseudo_merge_map *pm,
+ struct pseudo_merge_commit_ext *ext, size_t at)
+{
+ if (at >= pm->map_size)
+ return error(_("extended pseudo-merge read out-of-bounds "
+ "(%"PRIuMAX" >= %"PRIuMAX")"),
+ (uintmax_t)at, (uintmax_t)pm->map_size);
+
+ ext->nr = get_be32(pm->map + at);
+ ext->ptr = pm->map + at + sizeof(uint32_t);
+
+ return 0;
+}
+
+struct ewah_bitmap *pseudo_merge_bitmap(const struct pseudo_merge_map *pm,
+ struct pseudo_merge *merge)
+{
+ if (!merge->loaded_commits)
+ BUG("cannot use unloaded pseudo-merge bitmap");
+
+ if (!merge->loaded_bitmap) {
+ size_t at = merge->bitmap_at;
+
+ merge->bitmap = read_bitmap(pm->map, pm->map_size, &at);
+ merge->loaded_bitmap = 1;
+ }
+
+ return merge->bitmap;
+}
+
+struct pseudo_merge *use_pseudo_merge(const struct pseudo_merge_map *pm,
+ struct pseudo_merge *merge)
+{
+ if (!merge->loaded_commits) {
+ size_t pos = merge->at;
+
+ merge->commits = read_bitmap(pm->map, pm->map_size, &pos);
+ merge->bitmap_at = pos;
+ merge->loaded_commits = 1;
+ }
+ return merge;
+}
+
+static struct pseudo_merge *pseudo_merge_at(const struct pseudo_merge_map *pm,
+ struct object_id *oid,
+ size_t want)
+{
+ size_t lo = 0;
+ size_t hi = pm->nr;
+
+ while (lo < hi) {
+ size_t mi = lo + (hi - lo) / 2;
+ size_t got = pm->v[mi].at;
+
+ if (got == want)
+ return use_pseudo_merge(pm, &pm->v[mi]);
+ else if (got < want)
+ hi = mi;
+ else
+ lo = mi + 1;
+ }
+
+ warning(_("could not find pseudo-merge for commit %s at offset %"PRIuMAX),
+ oid_to_hex(oid), (uintmax_t)want);
+
+ return NULL;
+}
+
+struct pseudo_merge_commit {
+ uint32_t commit_pos;
+ uint64_t pseudo_merge_ofs;
+};
+
+#define PSEUDO_MERGE_COMMIT_RAWSZ (sizeof(uint32_t)+sizeof(uint64_t))
+
+static void read_pseudo_merge_commit_at(struct pseudo_merge_commit *merge,
+ const unsigned char *at)
+{
+ merge->commit_pos = get_be32(at);
+ merge->pseudo_merge_ofs = get_be64(at + sizeof(uint32_t));
+}
+
+static int nth_pseudo_merge_ext(const struct pseudo_merge_map *pm,
+ struct pseudo_merge_commit_ext *ext,
+ struct pseudo_merge_commit *merge,
+ uint32_t n)
+{
+ size_t ofs;
+
+ if (n >= ext->nr)
+ return error(_("extended pseudo-merge lookup out-of-bounds "
+ "(%"PRIu32" >= %"PRIu32")"), n, ext->nr);
+
+ ofs = get_be64(ext->ptr + st_mult(n, sizeof(uint64_t)));
+ if (ofs >= pm->map_size)
+ return error(_("out-of-bounds read: (%"PRIuMAX" >= %"PRIuMAX")"),
+ (uintmax_t)ofs, (uintmax_t)pm->map_size);
+
+ read_pseudo_merge_commit_at(merge, pm->map + ofs);
+
+ return 0;
+}
+
+static unsigned apply_pseudo_merge(const struct pseudo_merge_map *pm,
+ struct pseudo_merge *merge,
+ struct bitmap *result,
+ struct bitmap *roots)
+{
+ if (merge->satisfied)
+ return 0;
+
+ if (!ewah_bitmap_is_subset(merge->commits, roots ? roots : result))
+ return 0;
+
+ bitmap_or_ewah(result, pseudo_merge_bitmap(pm, merge));
+ if (roots)
+ bitmap_or_ewah(roots, pseudo_merge_bitmap(pm, merge));
+ merge->satisfied = 1;
+
+ return 1;
+}
+
+static int pseudo_merge_commit_cmp(const void *va, const void *vb)
+{
+ struct pseudo_merge_commit merge;
+ uint32_t key = *(uint32_t*)va;
+
+ read_pseudo_merge_commit_at(&merge, vb);
+
+ if (key < merge.commit_pos)
+ return -1;
+ if (key > merge.commit_pos)
+ return 1;
+ return 0;
+}
+
+static struct pseudo_merge_commit *find_pseudo_merge(const struct pseudo_merge_map *pm,
+ uint32_t pos)
+{
+ if (!pm->commits_nr)
+ return NULL;
+
+ return bsearch(&pos, pm->commits, pm->commits_nr,
+ PSEUDO_MERGE_COMMIT_RAWSZ, pseudo_merge_commit_cmp);
+}
+
+int apply_pseudo_merges_for_commit(const struct pseudo_merge_map *pm,
+ struct bitmap *result,
+ struct commit *commit, uint32_t commit_pos)
+{
+ struct pseudo_merge *merge;
+ struct pseudo_merge_commit *merge_commit;
+ int ret = 0;
+
+ merge_commit = find_pseudo_merge(pm, commit_pos);
+ if (!merge_commit)
+ return 0;
+
+ if (merge_commit->pseudo_merge_ofs & ((uint64_t)1<<63)) {
+ struct pseudo_merge_commit_ext ext = { 0 };
+ off_t ofs = merge_commit->pseudo_merge_ofs & ~((uint64_t)1<<63);
+ uint32_t i;
+
+ if (pseudo_merge_ext_at(pm, &ext, ofs) < -1) {
+ warning(_("could not read extended pseudo-merge table "
+ "for commit %s"),
+ oid_to_hex(&commit->object.oid));
+ return ret;
+ }
+
+ for (i = 0; i < ext.nr; i++) {
+ if (nth_pseudo_merge_ext(pm, &ext, merge_commit, i) < 0)
+ return ret;
+
+ merge = pseudo_merge_at(pm, &commit->object.oid,
+ merge_commit->pseudo_merge_ofs);
+
+ if (!merge)
+ return ret;
+
+ if (apply_pseudo_merge(pm, merge, result, NULL))
+ ret++;
+ }
+ } else {
+ merge = pseudo_merge_at(pm, &commit->object.oid,
+ merge_commit->pseudo_merge_ofs);
+
+ if (!merge)
+ return ret;
+
+ if (apply_pseudo_merge(pm, merge, result, NULL))
+ ret++;
+ }
+
+ if (ret)
+ cascade_pseudo_merges(pm, result, NULL);
+
+ return ret;
+}
+
+int cascade_pseudo_merges(const struct pseudo_merge_map *pm,
+ struct bitmap *result,
+ struct bitmap *roots)
+{
+ unsigned any_satisfied;
+ int ret = 0;
+
+ do {
+ struct pseudo_merge *merge;
+ uint32_t i;
+
+ any_satisfied = 0;
+
+ for (i = 0; i < pm->nr; i++) {
+ merge = use_pseudo_merge(pm, &pm->v[i]);
+ if (apply_pseudo_merge(pm, merge, result, roots)) {
+ any_satisfied |= 1;
+ ret++;
+ }
+ }
+ } while (any_satisfied);
+
+ return ret;
+}
diff --git a/pseudo-merge.h b/pseudo-merge.h
index 2f652fc6767..cc14e947e86 100644
--- a/pseudo-merge.h
+++ b/pseudo-merge.h
@@ -164,4 +164,48 @@ struct pseudo_merge {
*/
void free_pseudo_merge_map(struct pseudo_merge_map *pm);
+/*
+ * Loads the bitmap corresponding to the given pseudo-merge from the
+ * map, if it has not already been loaded.
+ */
+struct ewah_bitmap *pseudo_merge_bitmap(const struct pseudo_merge_map *pm,
+ struct pseudo_merge *merge);
+
+/*
+ * Loads the pseudo-merge and its commits bitmap from the given
+ * pseudo-merge map, if it has not already been loaded.
+ */
+struct pseudo_merge *use_pseudo_merge(const struct pseudo_merge_map *pm,
+ struct pseudo_merge *merge);
+
+/*
+ * Applies pseudo-merge(s) containing the given commit to the bitmap
+ * "result".
+ *
+ * If any pseudo-merge(s) were satisfied, returns the number
+ * satisfied, otherwise returns 0. If any were satisfied, the
+ * remaining unsatisfied pseudo-merges are cascaded (see below).
+ */
+int apply_pseudo_merges_for_commit(const struct pseudo_merge_map *pm,
+ struct bitmap *result,
+ struct commit *commit, uint32_t commit_pos);
+
+/*
+ * Applies pseudo-merge(s) which are satisfied according to the
+ * current bitmap in result (or roots, see below). If any
+ * pseudo-merges were satisfied, repeat the process over unsatisfied
+ * pseudo-merge commits until no more pseudo-merges are satisfied.
+ *
+ * Result is the bitmap to which the pseudo-merge(s) are applied.
+ * Roots (if given) is a bitmap of the traversal tip(s) for either
+ * side of a reachability traversal.
+ *
+ * Roots may given instead of a populated results bitmap at the
+ * beginning of a traversal on either side where the reachability
+ * closure over tips is not yet known.
+ */
+int cascade_pseudo_merges(const struct pseudo_merge_map *pm,
+ struct bitmap *result,
+ struct bitmap *roots);
+
#endif
--
2.44.0.303.g1dc5e5b124c
next prev parent reply other threads:[~2024-03-20 22:07 UTC|newest]
Thread overview: 84+ messages / expand[flat|nested] mbox.gz Atom feed top
2024-03-20 22:04 [PATCH 00/24] pack-bitmap: pseudo-merge reachability bitmaps Taylor Blau
2024-03-20 22:05 ` [PATCH 01/24] Documentation/technical: describe pseudo-merge bitmaps format Taylor Blau
2024-03-21 21:24 ` Junio C Hamano
2024-03-21 22:13 ` Taylor Blau
2024-03-21 22:22 ` Junio C Hamano
2024-03-20 22:05 ` [PATCH 02/24] config: repo_config_get_expiry() Taylor Blau
2024-04-10 17:54 ` Jeff King
2024-04-29 19:39 ` Taylor Blau
2024-03-20 22:05 ` [PATCH 03/24] ewah: implement `ewah_bitmap_is_subset()` Taylor Blau
2024-04-10 18:05 ` Jeff King
2024-04-29 19:47 ` Taylor Blau
2024-03-20 22:05 ` [PATCH 04/24] pack-bitmap: drop unused `max_bitmaps` parameter Taylor Blau
2024-04-10 18:06 ` Jeff King
2024-03-20 22:05 ` [PATCH 05/24] pack-bitmap: move some initialization to `bitmap_writer_init()` Taylor Blau
2024-04-10 18:10 ` Jeff King
2024-03-20 22:05 ` [PATCH 06/24] pseudo-merge.ch: initial commit Taylor Blau
2024-03-20 22:05 ` [PATCH 07/24] pack-bitmap-write: support storing pseudo-merge commits Taylor Blau
2024-03-20 22:05 ` [PATCH 08/24] pack-bitmap: implement `bitmap_writer_has_bitmapped_object_id()` Taylor Blau
2024-03-20 22:05 ` [PATCH 09/24] pack-bitmap: make `bitmap_writer_push_bitmapped_commit()` public Taylor Blau
2024-03-20 22:05 ` [PATCH 10/24] pseudo-merge: implement support for selecting pseudo-merge commits Taylor Blau
2024-03-20 22:05 ` [PATCH 11/24] pack-bitmap-write.c: select " Taylor Blau
2024-03-20 22:05 ` [PATCH 12/24] pack-bitmap-write.c: write pseudo-merge table Taylor Blau
2024-03-20 22:05 ` [PATCH 13/24] pack-bitmap: extract `read_bitmap()` function Taylor Blau
2024-03-20 22:05 ` [PATCH 14/24] pseudo-merge: scaffolding for reads Taylor Blau
2024-03-20 22:05 ` [PATCH 15/24] pack-bitmap.c: read pseudo-merge extension Taylor Blau
2024-03-20 22:05 ` Taylor Blau [this message]
2024-03-20 22:05 ` [PATCH 17/24] ewah: implement `ewah_bitmap_popcount()` Taylor Blau
2024-03-20 22:05 ` [PATCH 18/24] pack-bitmap: implement test helpers for pseudo-merge Taylor Blau
2024-03-20 22:05 ` [PATCH 19/24] t/test-lib-functions.sh: support `--date` in `test_commit_bulk()` Taylor Blau
2024-03-20 22:05 ` [PATCH 20/24] pack-bitmap.c: use pseudo-merges during traversal Taylor Blau
2024-03-20 22:06 ` [PATCH 21/24] pack-bitmap: extra trace2 information Taylor Blau
2024-03-20 22:06 ` [PATCH 22/24] ewah: `bitmap_equals_ewah()` Taylor Blau
2024-03-20 22:06 ` [PATCH 23/24] pseudo-merge: implement support for finding existing merges Taylor Blau
2024-03-20 22:06 ` [PATCH 24/24] t/perf: implement performace tests for pseudo-merge bitmaps Taylor Blau
2024-03-21 19:50 ` [PATCH 00/24] pack-bitmap: pseudo-merge reachability bitmaps Junio C Hamano
2024-04-29 20:42 ` [PATCH v2 00/23] " Taylor Blau
2024-04-29 20:42 ` [PATCH v2 01/23] Documentation/technical: describe pseudo-merge bitmaps format Taylor Blau
2024-05-06 11:52 ` Patrick Steinhardt
2024-05-06 16:37 ` Taylor Blau
2024-05-10 11:46 ` Patrick Steinhardt
2024-05-13 19:47 ` Taylor Blau
2024-05-14 6:33 ` Patrick Steinhardt
2024-04-29 20:43 ` [PATCH v2 02/23] ewah: implement `ewah_bitmap_is_subset()` Taylor Blau
2024-04-29 20:43 ` [PATCH v2 03/23] pack-bitmap: drop unused `max_bitmaps` parameter Taylor Blau
2024-04-29 20:43 ` [PATCH v2 04/23] pack-bitmap: move some initialization to `bitmap_writer_init()` Taylor Blau
2024-05-06 11:52 ` Patrick Steinhardt
2024-05-06 18:24 ` Taylor Blau
2024-04-29 20:43 ` [PATCH v2 05/23] pseudo-merge.ch: initial commit Taylor Blau
2024-04-29 20:43 ` [PATCH v2 06/23] pack-bitmap-write: support storing pseudo-merge commits Taylor Blau
2024-05-06 11:52 ` Patrick Steinhardt
2024-05-06 18:48 ` Taylor Blau
2024-05-10 11:47 ` Patrick Steinhardt
2024-05-13 18:42 ` Jeff King
2024-05-13 20:19 ` Taylor Blau
2024-04-29 20:43 ` [PATCH v2 07/23] pack-bitmap: implement `bitmap_writer_has_bitmapped_object_id()` Taylor Blau
2024-04-29 20:43 ` [PATCH v2 08/23] pack-bitmap: make `bitmap_writer_push_bitmapped_commit()` public Taylor Blau
2024-05-13 18:50 ` Jeff King
2024-05-14 0:54 ` Taylor Blau
2024-04-29 20:43 ` [PATCH v2 09/23] pseudo-merge: implement support for selecting pseudo-merge commits Taylor Blau
2024-05-06 11:53 ` Patrick Steinhardt
2024-05-06 19:58 ` Taylor Blau
2024-05-13 19:03 ` Jeff King
2024-05-14 0:58 ` Taylor Blau
2024-05-16 8:07 ` Jeff King
2024-05-16 22:43 ` Junio C Hamano
2024-04-29 20:43 ` [PATCH v2 10/23] pack-bitmap-write.c: select " Taylor Blau
2024-05-06 11:53 ` Patrick Steinhardt
2024-05-06 20:05 ` Taylor Blau
2024-05-10 11:47 ` Patrick Steinhardt
2024-04-29 20:43 ` [PATCH v2 11/23] pack-bitmap-write.c: write pseudo-merge table Taylor Blau
2024-04-29 20:43 ` [PATCH v2 12/23] pack-bitmap: extract `read_bitmap()` function Taylor Blau
2024-04-29 20:43 ` [PATCH v2 13/23] pseudo-merge: scaffolding for reads Taylor Blau
2024-04-29 20:43 ` [PATCH v2 14/23] pack-bitmap.c: read pseudo-merge extension Taylor Blau
2024-04-29 20:44 ` [PATCH v2 15/23] pseudo-merge: implement support for reading pseudo-merge commits Taylor Blau
2024-04-29 20:44 ` [PATCH v2 16/23] ewah: implement `ewah_bitmap_popcount()` Taylor Blau
2024-04-29 20:44 ` [PATCH v2 17/23] pack-bitmap: implement test helpers for pseudo-merge Taylor Blau
2024-04-29 20:44 ` [PATCH v2 18/23] t/test-lib-functions.sh: support `--date` in `test_commit_bulk()` Taylor Blau
2024-04-29 20:44 ` [PATCH v2 19/23] pack-bitmap.c: use pseudo-merges during traversal Taylor Blau
2024-04-29 20:44 ` [PATCH v2 20/23] pack-bitmap: extra trace2 information Taylor Blau
2024-04-29 20:44 ` [PATCH v2 21/23] ewah: `bitmap_equals_ewah()` Taylor Blau
2024-04-29 20:44 ` [PATCH v2 22/23] pseudo-merge: implement support for finding existing merges Taylor Blau
2024-04-29 20:44 ` [PATCH v2 23/23] t/perf: implement performace tests for pseudo-merge bitmaps Taylor Blau
2024-04-30 20:03 ` [PATCH v2 00/23] pack-bitmap: pseudo-merge reachability bitmaps Junio C Hamano
2024-05-01 14:40 ` Taylor Blau
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
List information: http://vger.kernel.org/majordomo-info.html
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=792cc863154a2671291efad6a64ac8a034dd4bb4.1710972293.git.me@ttaylorr.com \
--to=me@ttaylorr.com \
--cc=git@vger.kernel.org \
--cc=gitster@pobox.com \
--cc=newren@gmail.com \
--cc=peff@peff.net \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
Code repositories for project(s) associated with this public inbox
https://80x24.org/mirrors/git.git
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).