Re: [PATCH 01/23] ewah/ewah_bitmap.c: grow buffer past 1

From: Junio C Hamano <gitster@pobox.com>
To: Taylor Blau <me@ttaylorr.com>
Cc: git@vger.kernel.org, dstolee@microsoft.com, peff@peff.net
Subject: Re: [PATCH 01/23] ewah/ewah_bitmap.c: grow buffer past 1
Date: Sun, 22 Nov 2020 11:36:17 -0800
Message-ID: <xmqqblfpqj4e.fsf@gitster.c.googlers.com> (raw)
In-Reply-To: <36deaad366d66d10b96755dd6969bfe51123a2d4.1605123652.git.me@ttaylorr.com> (Taylor Blau's message of "Wed, 11 Nov 2020 14:41:44 -0500")

Taylor Blau <me@ttaylorr.com> writes:

> When the buffer size is exactly 1, we fail to grow it properly, since
> the integer truncation means that 1 * 3 / 2 = 1. This can cause a bad
> write on the line below.

When the buffer_size is exactly (alloc_size - 1), we can fit the new
element at the last word in the buffer array, but we still grow.  Is
this because we anticipate that we would need to add more soon?

> Bandaid this by first padding the buffer by 16, and then growing it.
> This still allows old blocks to fit into new ones, but fixes the case
> where the block size equals 1.

Adding 16 unconditionally is not "to pad".  If somebody really wants
"to pad", a likely implementation would be that the size resulting
from some computation (e.g. multiplying by 1.5) is round up to a
multiple of some number, than rounding up the original number before
multiplying it by 1.5, so the use of that verb in the explanation
did not help me understand what is going on.

Having said that, I see you used the word "bandaid" to signal that
we shouldn't worry about this being optimal or even correct and we
should be happy as long as it is not wrong ;-), but is there any
reason behind this 16 (as opposed to picking, say, 8 or 31), or is
that pulled out of thin air?

I think this probably mimics what alloc_nr() computes for ALLOC_GROW().
I wonder why buffer_grow() cannot be built around ALLOC_GROW() instead?

Nothing in the code is wrong per-se, but just what I noticed while
re-reading the patch.

Thanks.

> Co-authored-by: Jeff King <peff@peff.net>
> Signed-off-by: Jeff King <peff@peff.net>
> Signed-off-by: Taylor Blau <me@ttaylorr.com>
> ---
>  ewah/ewah_bitmap.c | 2 +-
>  1 file changed, 1 insertion(+), 1 deletion(-)
>
> diff --git a/ewah/ewah_bitmap.c b/ewah/ewah_bitmap.c
> index d59b1afe3d..3fae04ad00 100644
> --- a/ewah/ewah_bitmap.c
> +++ b/ewah/ewah_bitmap.c
> @@ -45,7 +45,7 @@ static inline void buffer_grow(struct ewah_bitmap *self, size_t new_size)
>  static inline void buffer_push(struct ewah_bitmap *self, eword_t value)
>  {
>  	if (self->buffer_size + 1 >= self->alloc_size)
> -		buffer_grow(self, self->buffer_size * 3 / 2);
> +		buffer_grow(self, (self->buffer_size + 16) * 3 / 2);
>  
>  	self->buffer[self->buffer_size++] = value;
>  }