Re: [PATCH 03/10] reftable/record: handle overflows when decoding varints

From: Patrick Steinhardt <ps@pks.im>
Date: Jan 20, 2025, 15:09 UTC
Message-ID: <Z45nMqLUHwMGEy11@pks.im>
In-Reply-To: <CAOLa=ZQxp=tmmBwAV2OR9ODLGf_VHLxG_50-YwN7-s7+c6pmNQ@mail.gmail.com>

On Mon, Jan 20, 2025 at 04:47:47AM -0500, Karthik Nayak wrote:

Show 34 quoted lines

> Patrick Steinhardt <ps@pks.im> writes:
> > diff --git a/reftable/record.c b/reftable/record.c
> > index 04429d23fe..4e6541c307 100644
> > --- a/reftable/record.c
> > +++ b/reftable/record.c
> > @@ -21,47 +21,40 @@ static void *reftable_record_data(struct reftable_record *rec);
> >
> >  int get_var_int(uint64_t *dest, struct string_view *in)
> >  {
> > -	int ptr = 0;
> > +	const unsigned char *buf = in->buf;
> > +	unsigned char c;
> >  	uint64_t val;
> >
> > -	if (in->len == 0)
> > +	if (!in->len)
> >  		return -1;
> > -	val = in->buf[ptr] & 0x7f;
> > -
> > -	while (in->buf[ptr] & 0x80) {
> > -		ptr++;
> > -		if (ptr > in->len) {
> > +	c = *buf++;
> > +	val = c & 0x7f;
> > +
> > +	while (c & 0x80) {
> > +		val += 1;
> 
> I was at first confused, I understand that we add 1 to check if there is
> an overflow before adding the next section. But this actually modifies
> the value itself, but looking below at `put_var_int()`, we did value--
> before storing each continuation byte. So during decoding.
> 
> Nit: it would be nice to explain that part a bit here with comments.

Yeah, I had to think about it a bit myself. It's quite a clever optimization: when the 0x80 bit is set, we know that the remaining value cannot be 0. We thus don't have to represent that value, which is why we can subtract 1 when encoding and re-add 1 when decoding. This allows us to save a byte in some edge cases.

[snip]

Show 26 quoted lines

> > -int put_var_int(struct string_view *dest, uint64_t val)
> > +int put_var_int(struct string_view *dest, uint64_t value)
> >  {
> > -	uint8_t buf[10] = { 0 };
> > -	int i = 9;
> > -	int n = 0;
> > -	buf[i] = (uint8_t)(val & 0x7f);
> > -	i--;
> > -	while (1) {
> > -		val >>= 7;
> > -		if (!val) {
> > -			break;
> > -		}
> > -		val--;
> > -		buf[i] = 0x80 | (uint8_t)(val & 0x7f);
> > -		i--;
> > -	}
> > -
> > -	n = sizeof(buf) - i - 1;
> > -	if (dest->len < n)
> > +	unsigned char varint[10];
> > +	unsigned pos = sizeof(varint) - 1;
> > +	varint[pos] = value & 127;
> 
> Nit: While the `get_var_int()` uses hexes, here we use ints. Would be
> nicer to use `0x7f` and so on and be consistent.

Yup, makes sense.

Show 21 quoted lines

> > +	while (value >>= 7)
> > +		varint[--pos] = 128 | (--value & 127);
> > +	if (dest->len < sizeof(varint) - pos)
> >  		return -1;
> > -	memcpy(dest->buf, &buf[i + 1], n);
> > -	return n;
> > +	memcpy(dest->buf, varint + pos, sizeof(varint) - pos);
> > +	return sizeof(varint) - pos;
> >  }
> >
> >  int reftable_is_block_type(uint8_t typ)
> > diff --git a/reftable/record.h b/reftable/record.h
> > index a24cb23bd4..721d6c949a 100644
> > --- a/reftable/record.h
> > +++ b/reftable/record.h
> > @@ -34,6 +34,10 @@ static inline void string_view_consume(struct string_view *s, int n)
> >
> >  /* utilities for de/encoding varints */
> >
> 
> We should remove this, no?

Yup, good catch.

Patrick