Subject: Re: [PATCH v3 22/30] pseudo-merge: implement support for reading pseudo-merge commits

From: Taylor Blau <[email-masked]>
Date: Thu, 23 May 2024 14:09:27 -0400

On Thu, May 23, 2024 at 06:40:00AM -0400, Jeff King wrote:
> OK, so I think this commit is getting into the meat of how the new
> bitmaps will be used. Just to restate it from a high-level to make sure
> I understand, I think it is:
>
>   1. When we are traversing (or even before we traverse and just know
>      our tips), we can always say "hey, I have a commit in the bitmap;
>      does this satisfy any pseudo-merges?". Where "satisfy" is "all of
>      the commits pseudo-merged for that bitmap are already in our
>      result". And if so, then we can use the pseudo-merge bitmap by
>      OR-ing it in.
>
>      And that's apply_pseudo_merges_for_commit().
>
>   2. That "OR" operation may likewise open up new options, so we
>      recurse. And that's the "cascade" function.

Exactly. I think implicit in the above is that your (2) is also a
recursive step, since each cascade step may open us up to new
pseudo-merges, which themselves may reach objects which satisfy other
pseudo-merges, and so on.

> > +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;
> > +}
>
> I was happy to see the boundary check here. Do we need a length check,
> too? We'd need at least four bytes here for the uint32_t. Does map_size
> include the trailing hash? If not, then it might provide a bit of slop
> (we'd read garbage, but never go outside the mmap).
>
> I guess the ">=" in the size check implies that we have at least one
> byte, but I don't think anything promises that we're correctly 4-byte
> aligned.

Yeah, we could read into the trailing hash area, which would just be
garbage from our perspective. But I think that adding a length check is
easy enough to do, something like:

--- 8< ---
diff --git a/pseudo-merge.c b/pseudo-merge.c
index b539791396..7d13101149 100644
--- a/pseudo-merge.c
+++ b/pseudo-merge.c
@@ -478,6 +478,10 @@ static int pseudo_merge_ext_at(const struct pseudo_merge_map *pm,
 		return error(_("extended pseudo-merge read out-of-bounds "
 			       "(%"PRIuMAX" >= %"PRIuMAX")"),
 			     (uintmax_t)at, (uintmax_t)pm->map_size);
+	if (at + 4 >= pm->map_size)
+		return error(_("extended pseudo-merge entry is too short "
+			       "(%"PRIuMAX" >= %"PRIuMAX")"),
+			     (uintmax_t)(at + 4), (uintmax_t)pm->map_size);

 	ext->nr = get_be32(pm->map + at);
 	ext->ptr = pm->map + at + sizeof(uint32_t);
--- >8 ---

> The rest of the length check is here:
>
> > +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;
> > +}
>
> When we call read_bitmap(), it knows where the end is, and it's
> careful to avoid reading past it. Good.

Yep, thanks for double checking.

Thanks,
Taylor