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

From: Patrick Steinhardt <ps@pks.im>
Date: Sep 24, 2025, 05:54 UTC
Message-ID: <aNOHl65jYyoNXou_@pks.im>
In-Reply-To: <20250918-228-reftable-introduce-consistency-checks-v3-4-271af03eb34d@gmail.com>

On Thu, Sep 18, 2025 at 10:11:45AM +0200, Karthik Nayak wrote:

Show 10 quoted lines

> 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