git/list[1] front-page[2] threads[3] people[4] search[5] about
 

Re: [PATCH 04/16] reftable/block: simplify how we track restart points

From
Patrick Steinhardt <ps@pks.im>
Date
Apr 7, 2025, 12:31 UTC
Message-ID
<Z_PFi4-B3ACD5hmq@pks.im>
In-Reply-To
<CAOLa=ZRwRkV56HAxtfX3EM1Lr3D938bY7d-zv+xUF4G40f-O2A@mail.gmail.com>
On Thu, Apr 03, 2025 at 08:17:50AM -0700, Karthik Nayak wrote:
Show 27 quoted lines
> Patrick Steinhardt <ps@pks.im> writes:
> 
> > Restart points record the location of reftable records that do not use
> > prefix compression and are used to perform a binary search inside of a
> > block. These restart points are encoded at the end of a block, between
> > the record data and the footer of a table.
> >
> > The block structure contains three different variables related to these
> > restart points:
> >
> >   - The block length contains the length of the reftable block up to the
> >     restart points.
> >
> >   - The restart count contains the number of restart points contained in
> >     the block.
> >
> >   - The restart bytes variable tracks where the restart point data
> >     begins.
> >
> > Tracking all three of these variables is unnecessary though as the data
> > can be derived from one another: the block length without restart points
> > is the exact same as the offset of the restart count data, which we
> > already track via the `restart_bytes` data.
> >
> 
> Nit: This para makes it seem as if we'd eliminate 'block length' in
> support of having/keeping `restart_bytes`, but we remove both.

We don't, we only remove the block length. The restart bytes are retained, but they are renamed to `restart_off` to better reflect what it actually contains. The next paragraph tries to explain this:

Show 30 quoted lines
> > Refactor the code so that we track the location of restart bytes not as
> > a pointer, but instead as an offset. This allows us to trivially get rid
> > of the `block_len` variable as described above. This avoids having the
> > confusing `block_len` variable and allows us to do less bookkeeping
> > overall.
> >
> > Signed-off-by: Patrick Steinhardt <ps@pks.im>
> > ---
> >  reftable/block.c | 25 ++++++++++++-------------
> >  reftable/block.h |  8 +++++---
> >  reftable/table.c |  2 +-
> >  3 files changed, 18 insertions(+), 17 deletions(-)
> >
> > diff --git a/reftable/block.c b/reftable/block.c
> > index 97740187259..f2567a8f0fd 100644
> > --- a/reftable/block.c
> > +++ b/reftable/block.c
> > @@ -216,10 +216,9 @@ int block_reader_init(struct block_reader *br, struct reftable_block *block,
> >  	uint32_t full_block_size = table_block_size;
> >  	uint8_t typ = block->data[header_off];
> >  	uint32_t sz = reftable_get_be24(block->data + header_off + 1);
> > -	int err = 0;
> > -	uint16_t restart_count = 0;
> > -	uint32_t restart_start = 0;
> > -	uint8_t *restart_bytes = NULL;
> > +	uint16_t restart_count;
> > +	uint32_t restart_off;
> 
> Nit: I guess this is to be consistent with `header_off`, but I would
> think spelling it out as `header_offset` is much easier to understand.

Yeah, I'm not much of a fan of such abbreviations, either. But I'd like to retain this abbreviation for the sake of consistency.

Patrick
Previous: Karthik NayakNext: Patrick Steinhardt
Message 10 of 55 in “reftable: overhaul the API to expose access to blocks”
  1. 00/16 reftable: overhaul the API to expose access to blocksPatrick Steinhardt, Mar 31, 2025
  2. 01/16 reftable: fix formatting of the license headerPatrick Steinhardt, Mar 31, 2025
  3. 03/16 reftable/blocksource: consolidate code into a single filePatrick Steinhardt, Mar 31, 2025
  4. Justin ToblerApr 2, 2025
  5. Karthik NayakApr 3, 2025
  6. 02/16 reftable/reader: rename data structure to "table"Patrick Steinhardt, Mar 31, 2025
  7. 04/16 reftable/block: simplify how we track restart pointsPatrick Steinhardt, Mar 31, 2025
  8. Justin ToblerApr 2, 2025
  9. Karthik NayakApr 3, 2025
  10. Patrick SteinhardtApr 7, 2025
  11. 05/16 reftable/table: move reading block into block readerPatrick Steinhardt, Mar 31, 2025
  12. Justin ToblerApr 2, 2025
  13. Patrick SteinhardtApr 7, 2025
  14. 06/16 reftable/block: rename `block` to `block_data`Patrick Steinhardt, Mar 31, 2025
  15. Justin ToblerApr 2, 2025
  16. Patrick SteinhardtApr 7, 2025
  17. 07/16 reftable/block: rename `block_reader` to `reftable_block`Patrick Steinhardt, Mar 31, 2025
  18. Justin ToblerApr 2, 2025
  19. Patrick SteinhardtApr 7, 2025
  20. 08/16 git-zlib: use `struct z_stream_s` instead of typedefPatrick Steinhardt, Mar 31, 2025
  21. 10/16 reftable/block: store block pointer in the block iteratorPatrick Steinhardt, Mar 31, 2025
  22. Justin ToblerApr 2, 2025
  23. Patrick SteinhardtApr 7, 2025
  24. 09/16 reftable/block: create public interface for reading blocksPatrick Steinhardt, Mar 31, 2025
  25. 11/16 reftable/block: make block iterators reseekablePatrick Steinhardt, Mar 31, 2025
  26. Justin ToblerApr 2, 2025
  27. Patrick SteinhardtApr 7, 2025
  28. 12/16 reftable/block: expose a generic iterator over reftable recordsPatrick Steinhardt, Mar 31, 2025
  29. 13/16 reftable/table: add `reftable_table` to the public interfacePatrick Steinhardt, Mar 31, 2025
  30. 14/16 reftable/table: introduce iterator for table blocksPatrick Steinhardt, Mar 31, 2025
  31. Junio C HamanoApr 1, 2025
  32. Patrick SteinhardtApr 2, 2025
  33. Justin ToblerApr 2, 2025
  34. Patrick SteinhardtApr 7, 2025
  35. 15/16 reftable/constants: make block types part of the public interfacePatrick Steinhardt, Mar 31, 2025
  36. 16/16 reftable/table: move printing logic into test helperPatrick Steinhardt, Mar 31, 2025
  37. Justin ToblerApr 2, 2025
  38. 00/16 reftable: overhaul the API to expose access to blocksPatrick Steinhardt, Apr 7, 2025
  39. 01/16 reftable: fix formatting of the license headerPatrick Steinhardt, Apr 7, 2025
  40. 03/16 reftable/blocksource: consolidate code into a single filePatrick Steinhardt, Apr 7, 2025
  41. 02/16 reftable/reader: rename data structure to "table"Patrick Steinhardt, Apr 7, 2025
  42. 04/16 reftable/block: simplify how we track restart pointsPatrick Steinhardt, Apr 7, 2025
  43. 06/16 reftable/block: rename `block` to `block_data`Patrick Steinhardt, Apr 7, 2025
  44. 05/16 reftable/table: move reading block into block readerPatrick Steinhardt, Apr 7, 2025
  45. 07/16 reftable/block: rename `block_reader` to `reftable_block`Patrick Steinhardt, Apr 7, 2025
  46. 08/16 git-zlib: use `struct z_stream_s` instead of typedefPatrick Steinhardt, Apr 7, 2025
  47. 09/16 reftable/block: create public interface for reading blocksPatrick Steinhardt, Apr 7, 2025
  48. 10/16 reftable/block: store block pointer in the block iteratorPatrick Steinhardt, Apr 7, 2025
  49. 11/16 reftable/block: make block iterators reseekablePatrick Steinhardt, Apr 7, 2025
  50. 12/16 reftable/block: expose a generic iterator over reftable recordsPatrick Steinhardt, Apr 7, 2025
  51. 13/16 reftable/table: add `reftable_table` to the public interfacePatrick Steinhardt, Apr 7, 2025
  52. 14/16 reftable/table: introduce iterator for table blocksPatrick Steinhardt, Apr 7, 2025
  53. 15/16 reftable/constants: make block types part of the public interfacePatrick Steinhardt, Apr 7, 2025
  54. 16/16 reftable/table: move printing logic into test helperPatrick Steinhardt, Apr 7, 2025
  55. Justin ToblerApr 14, 2025

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.