From: Karthik Nayak Date: Wed, 24 Sep 2025 11:20:07 GMT Subject: Re: [PATCH v3 4/8] reftable: ensure tables in a stack use sequential update indices Message-ID: In-Reply-To: Patrick Steinhardt writes: > 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); > 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.