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

From: Patrick Steinhardt <[email-masked]>
Date: Wed, 24 Sep 2025 07:54:31 +0200

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.

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