Re: [PATCH v3 4/8] reftable: ensure tables in a stack use sequential update indices

From: Karthik Nayak <karthik.188@gmail.com>
Date: Sep 24, 2025, 11:20 UTC
Message-ID: <CAOLa=ZTf7KL23+=Fggfg=4LXt1Dsd6nRCFg3q_Dhuom2Bk+L7A@mail.gmail.com>
In-Reply-To: <aNOHl65jYyoNXou_@pks.im>

Patrick Steinhardt <ps@pks.im> writes:

Show 37 quoted lines

> On Thu, Sep 18, 2025 at 10:11:45AM +0200, Karthik Nayak wrote:
>> diff --git a/reftable/stack.c b/reftable/stack.c
>> index 955be1edb6..a458f5a4c5 100644
>> --- a/reftable/stack.c
>> +++ b/reftable/stack.c
>> @@ -317,6 +318,14 @@ static int reftable_stack_reload_once(struct reftable_stack *st,
>>
>>  		new_tables[new_tables_len] = table;
>>  		new_tables_len++;
>> +
>> +		/* table's update indices must be sequential */
>
> Let's make this a full sentence starting with an upper-case letter and a
> period.
>
>> +		if (prev_table && (prev_table->max_update_index != table->min_update_index - 1)) {
>
> I wonder whether this check is too strict. It _must_ be true that the
> new table's minimum update index is greater than the previous table's
> maximum update index. But in theory, there is no reason why there cannot
> be a gap between those.
>
> The reason why this makes me a bit uneasy is stack compaction. Say we
> have three different tables:
>
>   - A base table with record r1 with update index 1.
>   - A second table with record r2 with update index 2.
>   - A third table with a deletion record d(r2) and a new record r3 with
>     update index 3.
>
> Now if we compact the second and the third table, the compaction will
> realize that r2 is deleted and thus no longer needs to be part of the
> compacted table. So the new state is:
>
>   - A base table with record r1 and update index r1.
>   - The compacted table with record r3 with update index 3.
>

That's a good counter example. I didn't know this was possible with the reftable format. From 'reftable/stack.c: stack_compact_locked()', we use the min,max index from the first, last table being compacted for the table name.

  err = format_name(&next_name,
reftable_table_min_update_index(st->tables[first]),
			  reftable_table_max_update_index(st->tables[last]));

we also set the writer's limit in 'reftable/stack.c: stack_write_compact()' similarly, which sets the min,max index for the writer:

  err = reftable_writer_set_limits(wr, st->tables[first]->min_update_index,
					 st->tables[last]->max_update_index);

Show 10 quoted lines

> I'm not too certain how the minimum update index of that second table
> would be encoded in the header. In theory, both minimum and maximum
> update index of that table could truthfully be 3, and the result would
> still be both valid and sensible. The new check you introduce would
> trigger though, as there now is a gap between those two tables.
>
> So I think we should loosen that condition to ensure that we have proper
> ordering of update indices, but not a gapless order.
>
> Patrick

So currently it does seem like our implementation, still uses the first and last table's indices to set the min,max index of the new table.

However, I think your point holds. I do think eventually we could optimize this to ensure that we do something like you described.

I will make changes accordingly.