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

[Taylor Blau <me@ttaylorr.com>]

On Sun, Nov 22, 2020 at 11:36:17AM -0800, Junio C Hamano wrote:
> 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?

Right; the check 'if (self->buffer_size + 1 >= self->alloc_size)' could
probably be written as a strict inequality, but that check dates back to
the original ewah implementation that Vicent added.

But, that is not quite the point of this patch: instead we want to stop
the integer math on that line from preventing us from growing the
buffer.

I think that this paragraph would be clarified by adding "and we need to
grow" to the end of "when the buffer size is exactly 1".

> > 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?

Any phrase that more accurately states what's going on is fine by me,
but...

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

I think that we probably could just use ALLOC_GROW() as you suggest.
Funny enough, reading through GitHub's chat logs, apparently this is
something that Peff and I talked about. So, 16 probably came from
alloc_nr(), but we probably stopped short of realizing that we could
just use ALLOC_GROW as-is.

So, maybe something along the lines of:

diff --git a/ewah/ewah_bitmap.c b/ewah/ewah_bitmap.c
index 3fae04ad00..9effcc0877 100644
--- a/ewah/ewah_bitmap.c
+++ b/ewah/ewah_bitmap.c
@@ -19,6 +19,7 @@
 #include "git-compat-util.h"
 #include "ewok.h"
 #include "ewok_rlw.h"
+#include "cache.h"

 static inline size_t min_size(size_t a, size_t b)
 {
@@ -33,12 +34,7 @@ static inline size_t max_size(size_t a, size_t b)
 static inline void buffer_grow(struct ewah_bitmap *self, size_t new_size)
 {
 	size_t rlw_offset = (uint8_t *)self->rlw - (uint8_t *)self->buffer;
-
-	if (self->alloc_size >= new_size)
-		return;
-
-	self->alloc_size = new_size;
-	REALLOC_ARRAY(self->buffer, self->alloc_size);
+	ALLOC_GROW(self->buffer, new_size, self->alloc_size);
 	self->rlw = self->buffer + (rlw_offset / sizeof(eword_t));
 }

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

Thanks,
Taylor