patch, 4 partsreftable: optimize I/O patterns

Hi,

this patch series optimizes some I/O patterns that the reftable library uses:

  - Establish a stat(3P)-based caching mechanism to avoid re-reading
    "tables.list" all the time.

  - Convert the block source to use mmap(3P) instead of read(3P) to read
    data.

Combined these lead to a ~2.7x speedup when writing many refs.

Patrick

Patrick Steinhardt (4):
  reftable/stack: refactor stack reloading to have common exit path
  reftable/stack: refactor reloading to use file descriptor
  reftable/stack: use stat info to avoid re-reading stack list
  reftable/blocksource: use mmap to read tables

 reftable/blocksource.c |  48 +++++++++++++-----
 reftable/stack.c       | 111 ++++++++++++++++++++++++-----------------
 reftable/stack.h       |   1 +
 reftable/system.h      |   1 +
 4 files changed, 103 insertions(+), 58 deletions(-)

The `reftable_stack_reload_maybe_reuse()` function is responsible for reloading the reftable list from disk. The function is quite hard to follow though because it has a bunch of different exit paths, many of which have to free the same set of resources.

Refactor the function to have a common exit path. While at it, touch up
the style of this function a bit to match our usual coding style better.
---
 reftable/stack.c | 86 +++++++++++++++++++++++-------------------------
 1 file changed, 42 insertions(+), 44 deletions(-)

Patrick Steinhardt <ps@pks.im> writes:

Missing sign-off.

Other than that, I did not find anything questionable in the conversion. By sticking to the two simple invariants:

 - we use "err" as our return value when we jump to "out:"

 - we always keep "names" and "names_after" freeable, and free them
   when we jump to "out:".

the exit status and leak prevention are both very clear (and the behaviour is not changed---it is not like there are any existing leaks that are plugged by this restructuring of the loop).

On Wed, Jan 10, 2024 at 09:30:51AM -0800, Junio C Hamano wrote:

Ah, sorry, I forgot my usual `git rebase --signoff`. Will fix in v2.

Patrick

We're about to introduce a stat(3P)-based caching mechanism to reload the list of stacks only when it has changed. In order to avoid race conditions this requires us to have a file descriptor available that we can use to call fstat(3P) on.

Prepare for this by converting the code to use `fd_read_lines()` so that
we have the file descriptor readily available.
---
 reftable/stack.c | 21 ++++++++++++++++++---
 1 file changed, 18 insertions(+), 3 deletions(-)

Patrick Steinhardt <ps@pks.im> writes:

Missing sign-off.

Other than that, the change is a refactoring that is very faithful to the original. Instead of doing the "open - pretend we opened an empty file if it does not exist - read - close" dance all inside the read_lines() call, this sort-of open codes the helper in this caller, so that later steps of this series can look at the file descriptor open to it.

Looking good.

Whenever we call into the refs interfaces we potentially have to reload refs in case they have been concurrently modified, either in-process or externally. While this happens somewhat automatically for loose refs because we simply try to re-read the files, the "packed" backend will reload its snapshot of the packed-refs file in case its stat info has changed since last reading it.

In the reftable backend we have a similar mechanism that is provided by `reftable_stack_reload()`. This function will read the list of stacks from "tables.list" and, if they have changed from the currently stored list, reload the stacks. This is heavily inefficient though, as we have to check whether the stack is up-to-date on basically every read and thus keep on re-reading the file all the time even if it didn't change at all.

We can do better and use the same stat(3P)-based mechanism that the "packed" backend uses. Instead of reading the file, we will only open the file descriptor, fstat(3P) it, and then compare the info against the cached value from the last time we have updated the stack. This should always work alright because "tables.list" is updated atomically via a rename, so even if the ctime or mtime wasn't granular enough to identify a change, at least the inode number should have changed.

This change significantly speeds up operations where many refs are read, like when using git-update-ref(1). The following benchmark creates N refs in an otherwise-empty repository via `git update-ref --stdin`:

  Benchmark 1: update-ref: create many refs (refcount = 1, revision = HEAD~)
    Time (mean ± σ):       5.6 ms ±   0.2 ms    [User: 2.5 ms, System: 3.0 ms]
    Range (min … max):     5.2 ms …   6.0 ms    89 runs

  Benchmark 2: update-ref: create many refs (refcount = 100, revision = HEAD~)
    Time (mean ± σ):      19.2 ms ±   0.3 ms    [User: 8.6 ms, System: 10.4 ms]
    Range (min … max):    18.4 ms …  19.8 ms    63 runs

  Benchmark 3: update-ref: create many refs (refcount = 10000, revision = HEAD~)
    Time (mean ± σ):      1.310 s ±  0.014 s    [User: 0.566 s, System: 0.724 s]
    Range (min … max):    1.291 s …  1.342 s    10 runs

  Benchmark 4: update-ref: create many refs (refcount = 1, revision = HEAD)
    Time (mean ± σ):       5.7 ms ±   0.4 ms    [User: 2.6 ms, System: 3.1 ms]
    Range (min … max):     5.1 ms …   9.5 ms    91 runs

  Benchmark 5: update-ref: create many refs (refcount = 100, revision = HEAD)
    Time (mean ± σ):      15.2 ms ±   0.3 ms    [User: 7.0 ms, System: 8.1 ms]
    Range (min … max):    14.3 ms …  17.1 ms    71 runs

  Benchmark 6: update-ref: create many refs (refcount = 10000, revision = HEAD)
    Time (mean ± σ):     916.1 ms ±  11.0 ms    [User: 420.8 ms, System: 495.0 ms]
    Range (min … max):   906.9 ms … 943.8 ms    10 runs

  Summary
    update-ref: create many refs (refcount = 1, revision = HEAD~) ran
      1.01 ± 0.09 times faster than update-ref: create many refs (refcount = 1, revision = HEAD)
      2.72 ± 0.11 times faster than update-ref: create many refs (refcount = 100, revision = HEAD)
      3.42 ± 0.13 times faster than update-ref: create many refs (refcount = 100, revision = HEAD~)
    163.59 ± 5.62 times faster than update-ref: create many refs (refcount = 10000, revision = HEAD)
    233.91 ± 7.92 times faster than update-ref: create many refs (refcount = 10000, revision = HEAD~)
---
 reftable/stack.c  | 10 +++++++++-
 reftable/stack.h  |  1 +
 reftable/system.h |  1 +
 3 files changed, 11 insertions(+), 1 deletion(-)

Patrick Steinhardt <ps@pks.im> writes:

Or the file size. Let's keep in mind that many users get useless inum from their filesystem X-<.

Nice.

The stat_validity_update() does not happen in the error codepath.

Should we be clearing the validity of the list when somebody jumps to "out:" due to an error? Or by the time this function gets called, the caller would already have cleared the validity and an error that jumps to "out:" keeps the list invalid?

Other than the missing sign-off, the change looks very straight-forward.

On Wed, Jan 10, 2024 at 12:07:52PM -0800, Junio C Hamano wrote:

It likely does not matter much. This function only gets called when we have previously determined the stack to be out of date already. So unless we update the validity cache, we know that the next validity check would continue to treat the stack as outdated.

That being said I think it's good hygiene to clear the validity cache regardless of that.

Patrick

The blocksource interface provides an interface to read blocks from a reftable table. This interface is implemented using read(3P) calls on the underlying file descriptor. While this works alright, this pattern is very inefficient when repeatedly querying the reftable stack for one or more refs. This inefficiency can mostly be attributed to the fact that we often need to re-read the same blocks over and over again, and every single time we need to call read(3P) again.

A natural fit in this context is to use mmap(3P) instead of read(3P), which has a bunch of benefits:

  - We do not need to come up with a caching strategy for some of the
    blocks as this will be handled by the kernel already.

  - We can avoid the overhead of having to call into the read(3P)
    syscall repeatedly.

  - We do not need to allocate returned blocks repeatedly, but can
    instead hand out pointers into the mmapped region directly.

Using mmap comes with a significant drawback on Windows though, because mmapped files cannot be deleted and neither is it possible to rename files onto an mmapped file. But for one, the reftable library gracefully handles the case where auto-compaction cannot delete a still-open stack already and ignores any such errors. Also, `reftable_stack_clean()` will prune stale tables which are not referenced by "tables.list" anymore so that those files can eventually be pruned. And second, we never rewrite already-rewritten stacks, so it does not matter that we cannot rename a file over an mmaped file, either.

Another unfortunate property of mmap is that it is not supported by all systems. But given that the size of reftables should typically be rather limited (megabytes at most in the vast majority of repositories), we can provide an easy fallback by just reading the complete table into memory on such platforms. This is the same strategy that the "packed" backend uses in case the platform does not provide mmap.

While this change doesn't significantly improve performance in the case where we're seeking through stacks once (like e.g. git-for-each-ref(1) would). But it does speed up usecases where there is lots of random access to refs, e.g. when writing. The following benchmark demonstrates these savings with git-update-ref(1) creating N refs in an otherwise empty repository:

  Benchmark 1: update-ref: create many refs (refcount = 1, revision = HEAD~)
    Time (mean ± σ):       5.6 ms ±   0.2 ms    [User: 2.7 ms, System: 2.8 ms]
    Range (min … max):     5.1 ms …   6.0 ms    90 runs

  Benchmark 2: update-ref: create many refs (refcount = 100, revision = HEAD~)
    Time (mean ± σ):      15.1 ms ±   0.4 ms    [User: 7.1 ms, System: 8.0 ms]
    Range (min … max):    14.2 ms …  16.5 ms    71 runs

  Benchmark 3: update-ref: create many refs (refcount = 10000, revision = HEAD~)
    Time (mean ± σ):     919.4 ms ±  11.2 ms    [User: 427.5 ms, System: 491.7 ms]
    Range (min … max):   908.1 ms … 936.6 ms    10 runs

  Benchmark 4: update-ref: create many refs (refcount = 1, revision = HEAD)
    Time (mean ± σ):       5.5 ms ±   0.3 ms    [User: 2.4 ms, System: 3.1 ms]
    Range (min … max):     5.0 ms …   7.3 ms    89 runs

  Benchmark 5: update-ref: create many refs (refcount = 100, revision = HEAD)
    Time (mean ± σ):      10.4 ms ±   0.3 ms    [User: 5.1 ms, System: 5.3 ms]
    Range (min … max):     9.7 ms …  11.0 ms    78 runs

  Benchmark 6: update-ref: create many refs (refcount = 10000, revision = HEAD)
    Time (mean ± σ):     483.5 ms ±   6.3 ms    [User: 227.8 ms, System: 255.6 ms]
    Range (min … max):   477.5 ms … 498.8 ms    10 runs

  Summary
    update-ref: create many refs (refcount = 1, revision = HEAD) ran
      1.01 ± 0.06 times faster than update-ref: create many refs (refcount = 1, revision = HEAD~)
      1.89 ± 0.11 times faster than update-ref: create many refs (refcount = 100, revision = HEAD)
      2.73 ± 0.16 times faster than update-ref: create many refs (refcount = 100, revision = HEAD~)
     87.55 ± 4.65 times faster than update-ref: create many refs (refcount = 10000, revision = HEAD)
    166.48 ± 8.80 times faster than update-ref: create many refs (refcount = 10000, revision = HEAD~)

Theoretically, we could also replicate the strategy of the "packed"
backend where small tables are read into memory instead of using mmap.
Benchmarks did not confirm that this has a performance benefit though.
---
 reftable/blocksource.c | 48 ++++++++++++++++++++++++++++++------------
 1 file changed, 35 insertions(+), 13 deletions(-)

Patrick Steinhardt <ps@pks.im> writes:

I somehow thought that we use "read into an allocated memory and pretend as if we mapped" emulation on Windows, so all of that may be moot.

Is there (do you need) some externally controllable knob that the user can use to turn this off on a system that is compiled without NO_MMAP? Otherwise it is misleading to have this as a variable.

It would have been nicer to do this kind of "a void pointer is taken and we immediately cast it to a concrete and useful type upon entry" clean-up as a separate step that is purely clean-up, if there were many instances. It is the first such one in the series as far as I remember, so it is not a huge deal.

So, we used to delay the allocation and reading of a block until this function gets called. Now, by the time the control reaches the function, we are expected to have the data handy at b->data. That is ensured by reftable_block_source_from_file(), I presume?

This is a no-op clean-up that would have been better in a separate clean-up step. Again, not a huge deal.

This is a bit unusual for our use of mmap() where the norm is to close the file descriptor once we mapped (we only need the memory region itself and not the originating file descriptor to unmap it).

Is there a reason why we need to keep p->fd? Now the other side of this if/else preallocates the whole thing and slurps everything in core to allow the remainder of the code to mimic what happens on the mmaped block memory (e.g., we saw how file_read_block() assumes that b->data[0..b->size] are valid) and does not obviously need p->fd, can we just remove .fd member from the file_block_source structure?

That way, file_close() can also lose the conditional close() call.

For that matter, do we need any codepath in this file that is enabled by !use_mmap? Can't we just use xmmap() and let its "instead, we allocate, read into it and return" emulation?

Thanks.

On Wed, Jan 10, 2024 at 01:24:24PM -0800, Junio C Hamano wrote:

Ah, you're right in fact. I missed the definition of `git_mmap()` and `git_munmap()`.

No. The benefit of using a variable instead of using ifdefs is that we know that both code paths continue to compile just fine. We do the same thing in "refs/packed-backend.c".

But this code is not needed at all anyway, as you pointed out, because we can simply use the emulated mmap(3P) code.

Yeah, fair enough. One problem I have with the reftable library is that its coding style doesn't quite blend in with the rest of the Git code base, so I want to refactor code that I'm touching to match our coding style better. This means that there will be a lot of such smallish refactorings, and I'm often not sure whether to evict them into their own commit or whether to do the refactoring in the same step.

For small changes like this one here I think it's reasonable to do so in the same commit. But larger refactorings like e.g. the introduction of the common exit path in the first patch of this series I of course put into their own commit.

Not really, I'll update the code accordingly.

Thanks!

Patrick

Hi,

this is the second version of my patch series that optimizes some I/O patterns that the reftable library uses. Changes compared to v1:

  - Added missing signoffs.

  - The validity cache is now cleared when reloading the reftable stack
    fails.

  - Style fixes for `reftable_block_source_from_file()` are now in a
    separate commit.

  - We now use `xmmap()` exclusively, relying on its fallback code on
    NO_MMAP platforms.

  - The file descriptor is closed immediately after mmapping now.

Thanks for your review, Junio!

Patrick

Patrick Steinhardt (5):
  reftable/stack: refactor stack reloading to have common exit path
  reftable/stack: refactor reloading to use file descriptor
  reftable/stack: use stat info to avoid re-reading stack list
  reftable/blocksource: refactor code to match our coding style
  reftable/blocksource: use mmap to read tables

 reftable/blocksource.c |  39 ++++++--------
 reftable/stack.c       | 113 +++++++++++++++++++++++++----------------
 reftable/stack.h       |   1 +
 reftable/system.h      |   1 +
 4 files changed, 85 insertions(+), 69 deletions(-)

Range-diff against v1:
1:  01ece2626d ! 1:  4b7f52c415 reftable/stack: refactor stack reloading to have common exit path
    @@ Commit message
         Refactor the function to have a common exit path. While at it, touch up
         the style of this function a bit to match our usual coding style better.
     
    +    Signed-off-by: Patrick Steinhardt <ps@pks.im>
    +
      ## reftable/stack.c ##
     @@ reftable/stack.c: static int tv_cmp(struct timeval *a, struct timeval *b)
      static int reftable_stack_reload_maybe_reuse(struct reftable_stack *st,
2:  726d302d7b ! 2:  36b9f6b624 reftable/stack: refactor reloading to use file descriptor
    @@ Commit message
         Prepare for this by converting the code to use `fd_read_lines()` so that
         we have the file descriptor readily available.
     
    +    Signed-off-by: Patrick Steinhardt <ps@pks.im>
    +
      ## reftable/stack.c ##
     @@ reftable/stack.c: static int reftable_stack_reload_maybe_reuse(struct reftable_stack *st,
      	struct timeval deadline;
3:  4fabdc3d80 ! 3:  c0f7cec95b reftable/stack: use stat info to avoid re-reading stack list
    @@ Commit message
         cached value from the last time we have updated the stack. This should
         always work alright because "tables.list" is updated atomically via a
         rename, so even if the ctime or mtime wasn't granular enough to identify
    -    a change, at least the inode number should have changed.
    +    a change, at least the inode number or file size should have changed.
     
         This change significantly speeds up operations where many refs are read,
         like when using git-update-ref(1). The following benchmark creates N
         refs in an otherwise-empty repository via `git update-ref --stdin`:
     
           Benchmark 1: update-ref: create many refs (refcount = 1, revision = HEAD~)
    -        Time (mean ± σ):       5.6 ms ±   0.2 ms    [User: 2.5 ms, System: 3.0 ms]
    -        Range (min … max):     5.2 ms …   6.0 ms    89 runs
    +        Time (mean ± σ):       5.1 ms ±   0.2 ms    [User: 2.4 ms, System: 2.6 ms]
    +        Range (min … max):     4.8 ms …   7.2 ms    109 runs
     
           Benchmark 2: update-ref: create many refs (refcount = 100, revision = HEAD~)
    -        Time (mean ± σ):      19.2 ms ±   0.3 ms    [User: 8.6 ms, System: 10.4 ms]
    -        Range (min … max):    18.4 ms …  19.8 ms    63 runs
    +        Time (mean ± σ):      19.1 ms ±   0.9 ms    [User: 8.9 ms, System: 9.9 ms]
    +        Range (min … max):    18.4 ms …  26.7 ms    72 runs
     
           Benchmark 3: update-ref: create many refs (refcount = 10000, revision = HEAD~)
    -        Time (mean ± σ):      1.310 s ±  0.014 s    [User: 0.566 s, System: 0.724 s]
    -        Range (min … max):    1.291 s …  1.342 s    10 runs
    +        Time (mean ± σ):      1.336 s ±  0.018 s    [User: 0.590 s, System: 0.724 s]
    +        Range (min … max):    1.314 s …  1.373 s    10 runs
     
           Benchmark 4: update-ref: create many refs (refcount = 1, revision = HEAD)
    -        Time (mean ± σ):       5.7 ms ±   0.4 ms    [User: 2.6 ms, System: 3.1 ms]
    -        Range (min … max):     5.1 ms …   9.5 ms    91 runs
    +        Time (mean ± σ):       5.1 ms ±   0.2 ms    [User: 2.4 ms, System: 2.6 ms]
    +        Range (min … max):     4.8 ms …   7.2 ms    109 runs
     
           Benchmark 5: update-ref: create many refs (refcount = 100, revision = HEAD)
    -        Time (mean ± σ):      15.2 ms ±   0.3 ms    [User: 7.0 ms, System: 8.1 ms]
    -        Range (min … max):    14.3 ms …  17.1 ms    71 runs
    +        Time (mean ± σ):      14.8 ms ±   0.2 ms    [User: 7.1 ms, System: 7.5 ms]
    +        Range (min … max):    14.2 ms …  15.2 ms    82 runs
     
           Benchmark 6: update-ref: create many refs (refcount = 10000, revision = HEAD)
    -        Time (mean ± σ):     916.1 ms ±  11.0 ms    [User: 420.8 ms, System: 495.0 ms]
    -        Range (min … max):   906.9 ms … 943.8 ms    10 runs
    +        Time (mean ± σ):     927.6 ms ±   5.3 ms    [User: 437.8 ms, System: 489.5 ms]
    +        Range (min … max):   919.4 ms … 936.4 ms    10 runs
     
           Summary
    -        update-ref: create many refs (refcount = 1, revision = HEAD~) ran
    -          1.01 ± 0.09 times faster than update-ref: create many refs (refcount = 1, revision = HEAD)
    -          2.72 ± 0.11 times faster than update-ref: create many refs (refcount = 100, revision = HEAD)
    -          3.42 ± 0.13 times faster than update-ref: create many refs (refcount = 100, revision = HEAD~)
    -        163.59 ± 5.62 times faster than update-ref: create many refs (refcount = 10000, revision = HEAD)
    -        233.91 ± 7.92 times faster than update-ref: create many refs (refcount = 10000, revision = HEAD~)
    +        update-ref: create many refs (refcount = 1, revision = HEAD) ran
    +          1.00 ± 0.07 times faster than update-ref: create many refs (refcount = 1, revision = HEAD~)
    +          2.89 ± 0.14 times faster than update-ref: create many refs (refcount = 100, revision = HEAD)
    +          3.74 ± 0.25 times faster than update-ref: create many refs (refcount = 100, revision = HEAD~)
    +        181.26 ± 8.30 times faster than update-ref: create many refs (refcount = 10000, revision = HEAD)
    +        261.01 ± 12.35 times faster than update-ref: create many refs (refcount = 10000, revision = HEAD~)
    +
    +    Signed-off-by: Patrick Steinhardt <ps@pks.im>
     
      ## reftable/stack.c ##
     @@ reftable/stack.c: void reftable_stack_destroy(struct reftable_stack *st)
    @@ reftable/stack.c: static int reftable_stack_reload_maybe_reuse(struct reftable_s
     +	stat_validity_update(&st->list_validity, fd);
     +
      out:
    ++	if (err)
    ++		stat_validity_clear(&st->list_validity);
      	if (fd >= 0)
      		close(fd);
    + 	free_names(names);
     @@ reftable/stack.c: static int reftable_stack_reload_maybe_reuse(struct reftable_stack *st,
      static int stack_uptodate(struct reftable_stack *st)
      {
-:  ---------- > 4:  96e79dc3ba reftable/blocksource: refactor code to match our coding style
4:  a23f38a806 ! 5:  e53a20c8e1 reftable/blocksource: use mmap to read tables
    @@ Commit message
         already and ignores any such errors. Also, `reftable_stack_clean()` will
         prune stale tables which are not referenced by "tables.list" anymore so
         that those files can eventually be pruned. And second, we never rewrite
    -    already-rewritten stacks, so it does not matter that we cannot rename a
    +    already-written stacks, so it does not matter that we cannot rename a
         file over an mmaped file, either.
     
         Another unfortunate property of mmap is that it is not supported by all
         systems. But given that the size of reftables should typically be rather
         limited (megabytes at most in the vast majority of repositories), we can
    -    provide an easy fallback by just reading the complete table into memory
    -    on such platforms. This is the same strategy that the "packed" backend
    -    uses in case the platform does not provide mmap.
    +    use the fallback implementation provided by `git_mmap()` which reads the
    +    whole file into memory instead. This is the same strategy that the
    +    "packed" backend uses.
     
         While this change doesn't significantly improve performance in the case
         where we're seeking through stacks once (like e.g. git-for-each-ref(1)
    @@ Commit message
         empty repository:
     
           Benchmark 1: update-ref: create many refs (refcount = 1, revision = HEAD~)
    -        Time (mean ± σ):       5.6 ms ±   0.2 ms    [User: 2.7 ms, System: 2.8 ms]
    -        Range (min … max):     5.1 ms …   6.0 ms    90 runs
    +        Time (mean ± σ):       5.1 ms ±   0.2 ms    [User: 2.5 ms, System: 2.5 ms]
    +        Range (min … max):     4.8 ms …   7.1 ms    111 runs
     
           Benchmark 2: update-ref: create many refs (refcount = 100, revision = HEAD~)
    -        Time (mean ± σ):      15.1 ms ±   0.4 ms    [User: 7.1 ms, System: 8.0 ms]
    -        Range (min … max):    14.2 ms …  16.5 ms    71 runs
    +        Time (mean ± σ):      14.8 ms ±   0.5 ms    [User: 7.1 ms, System: 7.5 ms]
    +        Range (min … max):    14.1 ms …  18.7 ms    84 runs
     
           Benchmark 3: update-ref: create many refs (refcount = 10000, revision = HEAD~)
    -        Time (mean ± σ):     919.4 ms ±  11.2 ms    [User: 427.5 ms, System: 491.7 ms]
    -        Range (min … max):   908.1 ms … 936.6 ms    10 runs
    +        Time (mean ± σ):     926.4 ms ±   5.6 ms    [User: 448.5 ms, System: 477.7 ms]
    +        Range (min … max):   920.0 ms … 936.1 ms    10 runs
     
           Benchmark 4: update-ref: create many refs (refcount = 1, revision = HEAD)
    -        Time (mean ± σ):       5.5 ms ±   0.3 ms    [User: 2.4 ms, System: 3.1 ms]
    -        Range (min … max):     5.0 ms …   7.3 ms    89 runs
    +        Time (mean ± σ):       5.0 ms ±   0.2 ms    [User: 2.4 ms, System: 2.5 ms]
    +        Range (min … max):     4.7 ms …   5.4 ms    111 runs
     
           Benchmark 5: update-ref: create many refs (refcount = 100, revision = HEAD)
    -        Time (mean ± σ):      10.4 ms ±   0.3 ms    [User: 5.1 ms, System: 5.3 ms]
    -        Range (min … max):     9.7 ms …  11.0 ms    78 runs
    +        Time (mean ± σ):      10.5 ms ±   0.2 ms    [User: 5.0 ms, System: 5.3 ms]
    +        Range (min … max):    10.0 ms …  10.9 ms    93 runs
     
           Benchmark 6: update-ref: create many refs (refcount = 10000, revision = HEAD)
    -        Time (mean ± σ):     483.5 ms ±   6.3 ms    [User: 227.8 ms, System: 255.6 ms]
    -        Range (min … max):   477.5 ms … 498.8 ms    10 runs
    +        Time (mean ± σ):     529.6 ms ±   9.1 ms    [User: 268.0 ms, System: 261.4 ms]
    +        Range (min … max):   522.4 ms … 547.1 ms    10 runs
     
           Summary
             update-ref: create many refs (refcount = 1, revision = HEAD) ran
               1.01 ± 0.06 times faster than update-ref: create many refs (refcount = 1, revision = HEAD~)
    -          1.89 ± 0.11 times faster than update-ref: create many refs (refcount = 100, revision = HEAD)
    -          2.73 ± 0.16 times faster than update-ref: create many refs (refcount = 100, revision = HEAD~)
    -         87.55 ± 4.65 times faster than update-ref: create many refs (refcount = 10000, revision = HEAD)
    -        166.48 ± 8.80 times faster than update-ref: create many refs (refcount = 10000, revision = HEAD~)
    +          2.08 ± 0.07 times faster than update-ref: create many refs (refcount = 100, revision = HEAD)
    +          2.95 ± 0.14 times faster than update-ref: create many refs (refcount = 100, revision = HEAD~)
    +        105.33 ± 3.76 times faster than update-ref: create many refs (refcount = 10000, revision = HEAD)
    +        184.24 ± 5.89 times faster than update-ref: create many refs (refcount = 10000, revision = HEAD~)
     
         Theoretically, we could also replicate the strategy of the "packed"
         backend where small tables are read into memory instead of using mmap.
         Benchmarks did not confirm that this has a performance benefit though.
     
    +    Signed-off-by: Patrick Steinhardt <ps@pks.im>
    +
      ## reftable/blocksource.c ##
    -@@ reftable/blocksource.c: license that can be found in the LICENSE file or at
    - #include "reftable-blocksource.h"
    - #include "reftable-error.h"
    - 
    -+#if defined(NO_MMAP)
    -+static int use_mmap = 0;
    -+#else
    -+static int use_mmap = 1;
    -+#endif
    -+
    - static void strbuf_return_block(void *b, struct reftable_block *dest)
    - {
    - 	if (dest->len)
     @@ reftable/blocksource.c: struct reftable_block_source malloc_block_source(void)
    + }
    + 
      struct file_block_source {
    - 	int fd;
    +-	int fd;
      	uint64_t size;
     +	unsigned char *data;
      };
    @@ reftable/blocksource.c: static uint64_t file_size(void *b)
     -	if (fd > 0) {
     -		close(fd);
     -		((struct file_block_source *)b)->fd = 0;
    +-	}
    +-
     +	struct file_block_source *b = v;
    -+
    -+	if (b->fd >= 0) {
    -+		close(b->fd);
    -+		b->fd = -1;
    - 	}
    - 
    -+	if (use_mmap)
    -+		munmap(b->data, b->size);
    -+	else
    -+		reftable_free(b->data);
    -+	b->data = NULL;
    -+
    ++	munmap(b->data, b->size);
      	reftable_free(b);
      }
      
    @@ reftable/blocksource.c: static int file_read_block(void *v, struct reftable_bloc
      	return size;
      }
     @@ reftable/blocksource.c: int reftable_block_source_from_file(struct reftable_block_source *bs,
    - {
    - 	struct stat st = { 0 };
    - 	int err = 0;
    --	int fd = open(name, O_RDONLY);
    -+	int fd;
    - 	struct file_block_source *p = NULL;
    -+
    -+	fd = open(name, O_RDONLY);
    - 	if (fd < 0) {
    - 		if (errno == ENOENT) {
    - 			return REFTABLE_NOT_EXIST_ERROR;
    -@@ reftable/blocksource.c: int reftable_block_source_from_file(struct reftable_block_source *bs,
      
    - 	p = reftable_calloc(sizeof(struct file_block_source));
    + 	p = reftable_calloc(sizeof(*p));
      	p->size = st.st_size;
     -	p->fd = fd;
    -+	if (use_mmap) {
    -+		p->data = xmmap(NULL, st.st_size, PROT_READ, MAP_PRIVATE, fd, 0);
    -+		p->fd = fd;
    -+	} else {
    -+		p->data = xmalloc(st.st_size);
    -+		if (read_in_full(fd, p->data, st.st_size) != st.st_size) {
    -+			close(fd);
    -+			return -1;
    -+		}
    -+		close(fd);
    -+		p->fd = -1;
    -+	}
    ++	p->data = xmmap(NULL, st.st_size, PROT_READ, MAP_PRIVATE, fd, 0);
    ++	close(fd);
      
      	assert(!bs->ops);
      	bs->ops = &file_vtable;

base-commit: a54a84b333adbecf7bc4483c0e36ed5878cac17b

The `reftable_stack_reload_maybe_reuse()` function is responsible for reloading the reftable list from disk. The function is quite hard to follow though because it has a bunch of different exit paths, many of which have to free the same set of resources.

Refactor the function to have a common exit path. While at it, touch up the style of this function a bit to match our usual coding style better.

Signed-off-by: Patrick Steinhardt <ps@pks.im>
---
 reftable/stack.c | 86 +++++++++++++++++++++++-------------------------
 1 file changed, 42 insertions(+), 44 deletions(-)

We're about to introduce a stat(3P)-based caching mechanism to reload the list of stacks only when it has changed. In order to avoid race conditions this requires us to have a file descriptor available that we can use to call fstat(3P) on.

Prepare for this by converting the code to use `fd_read_lines()` so that we have the file descriptor readily available.

Signed-off-by: Patrick Steinhardt <ps@pks.im>
---
 reftable/stack.c | 21 ++++++++++++++++++---
 1 file changed, 18 insertions(+), 3 deletions(-)

On Thu, Jan 11, 2024 at 11:06:43AM +0100, Patrick Steinhardt wrote:

Coverity noted a case with this series where we might feed a negative value to fstat(). I'm not sure if it's a bug or not.

The issue is that here:

...we might end up with fd as "-1" after calling open() on the list file. For most errors we'll jump to "out", which makes sense. But if we get ENOENT, we keep going with an empty file-list, which makes sense.

But we then do other stuff with "fd". I think this case is OK:

We only get here if reftable_stack_reload_once() returned an error, which it won't do since we feed it a blank set of names (and anyway, close(-1) is a harmless noop).

But if we actually get to the end of the function, it's more questionable. As of this patch, it's OK:

But in the next patch we have this hunk:

which means we'll feed a negative value to stat_validity_update(). I think this may be OK, because I'd imagine the only sensible thing to do is call stat_validity_clear() instead. And using a negative fd means fstat() will fail, which will cause stat_validity_update() to clear the validity struct anyway. But I thought it was worth double-checking.

-Peff

On Sun, Jan 14, 2024 at 05:14:24AM -0500, Jeff King wrote:

Good catch, and thanks a lot for double-checking. I was briefly wondering whether this behaviour is actually specified by POSIX. In any case, fstat(3P) explicitly documents `EBADF` as:

  The fildes argument is not a valid file descriptor.

That makes me think that this code is indeed POSIX-compliant, as implementations are expected to handle invalid file descriptors via this error code.

So overall this works as intended, even though I would not consider it to be the cleanest way to handle this. Unless you or others think that this should be refactored I'll leave it as-is for now though.

Patrick

On Mon, Jan 15, 2024 at 11:03:37AM +0100, Patrick Steinhardt wrote:

Thanks for confirming. I think we can leave your patch as-is. If anything, I would say that stat_validity_update() should check for "fd < 0" itself. Not because I think fstat() is unlikely to behave differently on some platform, but simply because it more clearly documents the expectation.

-Peff

Jeff King <peff@peff.net> writes:

Thanks, I agree with your point that we should avoid calling system functions that take a file descriptor with a known-invalid (like negative) one.

Whenever we call into the refs interfaces we potentially have to reload refs in case they have been concurrently modified, either in-process or externally. While this happens somewhat automatically for loose refs because we simply try to re-read the files, the "packed" backend will reload its snapshot of the packed-refs file in case its stat info has changed since last reading it.

In the reftable backend we have a similar mechanism that is provided by `reftable_stack_reload()`. This function will read the list of stacks from "tables.list" and, if they have changed from the currently stored list, reload the stacks. This is heavily inefficient though, as we have to check whether the stack is up-to-date on basically every read and thus keep on re-reading the file all the time even if it didn't change at all.

We can do better and use the same stat(3P)-based mechanism that the "packed" backend uses. Instead of reading the file, we will only open the file descriptor, fstat(3P) it, and then compare the info against the cached value from the last time we have updated the stack. This should always work alright because "tables.list" is updated atomically via a rename, so even if the ctime or mtime wasn't granular enough to identify a change, at least the inode number or file size should have changed.

This change significantly speeds up operations where many refs are read, like when using git-update-ref(1). The following benchmark creates N refs in an otherwise-empty repository via `git update-ref --stdin`:

  Benchmark 1: update-ref: create many refs (refcount = 1, revision = HEAD~)
    Time (mean ± σ):       5.1 ms ±   0.2 ms    [User: 2.4 ms, System: 2.6 ms]
    Range (min … max):     4.8 ms …   7.2 ms    109 runs

  Benchmark 2: update-ref: create many refs (refcount = 100, revision = HEAD~)
    Time (mean ± σ):      19.1 ms ±   0.9 ms    [User: 8.9 ms, System: 9.9 ms]
    Range (min … max):    18.4 ms …  26.7 ms    72 runs

  Benchmark 3: update-ref: create many refs (refcount = 10000, revision = HEAD~)
    Time (mean ± σ):      1.336 s ±  0.018 s    [User: 0.590 s, System: 0.724 s]
    Range (min … max):    1.314 s …  1.373 s    10 runs

  Benchmark 4: update-ref: create many refs (refcount = 1, revision = HEAD)
    Time (mean ± σ):       5.1 ms ±   0.2 ms    [User: 2.4 ms, System: 2.6 ms]
    Range (min … max):     4.8 ms …   7.2 ms    109 runs

  Benchmark 5: update-ref: create many refs (refcount = 100, revision = HEAD)
    Time (mean ± σ):      14.8 ms ±   0.2 ms    [User: 7.1 ms, System: 7.5 ms]
    Range (min … max):    14.2 ms …  15.2 ms    82 runs

  Benchmark 6: update-ref: create many refs (refcount = 10000, revision = HEAD)
    Time (mean ± σ):     927.6 ms ±   5.3 ms    [User: 437.8 ms, System: 489.5 ms]
    Range (min … max):   919.4 ms … 936.4 ms    10 runs

  Summary
    update-ref: create many refs (refcount = 1, revision = HEAD) ran
      1.00 ± 0.07 times faster than update-ref: create many refs (refcount = 1, revision = HEAD~)
      2.89 ± 0.14 times faster than update-ref: create many refs (refcount = 100, revision = HEAD)
      3.74 ± 0.25 times faster than update-ref: create many refs (refcount = 100, revision = HEAD~)
    181.26 ± 8.30 times faster than update-ref: create many refs (refcount = 10000, revision = HEAD)
    261.01 ± 12.35 times faster than update-ref: create many refs (refcount = 10000, revision = HEAD~)

Signed-off-by: Patrick Steinhardt <ps@pks.im>
---
 reftable/stack.c  | 12 +++++++++++-
 reftable/stack.h  |  1 +
 reftable/system.h |  1 +
 3 files changed, 13 insertions(+), 1 deletion(-)

Refactor `reftable_block_source_from_file()` to match our coding style better.

Signed-off-by: Patrick Steinhardt <ps@pks.im>
---
 reftable/blocksource.c | 17 ++++++++---------
 1 file changed, 8 insertions(+), 9 deletions(-)

The blocksource interface provides an interface to read blocks from a reftable table. This interface is implemented using read(3P) calls on the underlying file descriptor. While this works alright, this pattern is very inefficient when repeatedly querying the reftable stack for one or more refs. This inefficiency can mostly be attributed to the fact that we often need to re-read the same blocks over and over again, and every single time we need to call read(3P) again.

A natural fit in this context is to use mmap(3P) instead of read(3P), which has a bunch of benefits:

  - We do not need to come up with a caching strategy for some of the
    blocks as this will be handled by the kernel already.

  - We can avoid the overhead of having to call into the read(3P)
    syscall repeatedly.

  - We do not need to allocate returned blocks repeatedly, but can
    instead hand out pointers into the mmapped region directly.

Using mmap comes with a significant drawback on Windows though, because mmapped files cannot be deleted and neither is it possible to rename files onto an mmapped file. But for one, the reftable library gracefully handles the case where auto-compaction cannot delete a still-open stack already and ignores any such errors. Also, `reftable_stack_clean()` will prune stale tables which are not referenced by "tables.list" anymore so that those files can eventually be pruned. And second, we never rewrite already-written stacks, so it does not matter that we cannot rename a file over an mmaped file, either.

Another unfortunate property of mmap is that it is not supported by all systems. But given that the size of reftables should typically be rather limited (megabytes at most in the vast majority of repositories), we can use the fallback implementation provided by `git_mmap()` which reads the whole file into memory instead. This is the same strategy that the "packed" backend uses.

While this change doesn't significantly improve performance in the case where we're seeking through stacks once (like e.g. git-for-each-ref(1) would). But it does speed up usecases where there is lots of random access to refs, e.g. when writing. The following benchmark demonstrates these savings with git-update-ref(1) creating N refs in an otherwise empty repository:

  Benchmark 1: update-ref: create many refs (refcount = 1, revision = HEAD~)
    Time (mean ± σ):       5.1 ms ±   0.2 ms    [User: 2.5 ms, System: 2.5 ms]
    Range (min … max):     4.8 ms …   7.1 ms    111 runs

  Benchmark 2: update-ref: create many refs (refcount = 100, revision = HEAD~)
    Time (mean ± σ):      14.8 ms ±   0.5 ms    [User: 7.1 ms, System: 7.5 ms]
    Range (min … max):    14.1 ms …  18.7 ms    84 runs

  Benchmark 3: update-ref: create many refs (refcount = 10000, revision = HEAD~)
    Time (mean ± σ):     926.4 ms ±   5.6 ms    [User: 448.5 ms, System: 477.7 ms]
    Range (min … max):   920.0 ms … 936.1 ms    10 runs

  Benchmark 4: update-ref: create many refs (refcount = 1, revision = HEAD)
    Time (mean ± σ):       5.0 ms ±   0.2 ms    [User: 2.4 ms, System: 2.5 ms]
    Range (min … max):     4.7 ms …   5.4 ms    111 runs

  Benchmark 5: update-ref: create many refs (refcount = 100, revision = HEAD)
    Time (mean ± σ):      10.5 ms ±   0.2 ms    [User: 5.0 ms, System: 5.3 ms]
    Range (min … max):    10.0 ms …  10.9 ms    93 runs

  Benchmark 6: update-ref: create many refs (refcount = 10000, revision = HEAD)
    Time (mean ± σ):     529.6 ms ±   9.1 ms    [User: 268.0 ms, System: 261.4 ms]
    Range (min … max):   522.4 ms … 547.1 ms    10 runs

  Summary
    update-ref: create many refs (refcount = 1, revision = HEAD) ran
      1.01 ± 0.06 times faster than update-ref: create many refs (refcount = 1, revision = HEAD~)
      2.08 ± 0.07 times faster than update-ref: create many refs (refcount = 100, revision = HEAD)
      2.95 ± 0.14 times faster than update-ref: create many refs (refcount = 100, revision = HEAD~)
    105.33 ± 3.76 times faster than update-ref: create many refs (refcount = 10000, revision = HEAD)
    184.24 ± 5.89 times faster than update-ref: create many refs (refcount = 10000, revision = HEAD~)

Theoretically, we could also replicate the strategy of the "packed" backend where small tables are read into memory instead of using mmap. Benchmarks did not confirm that this has a performance benefit though.

Signed-off-by: Patrick Steinhardt <ps@pks.im>
---
 reftable/blocksource.c | 22 +++++++---------------
 1 file changed, 7 insertions(+), 15 deletions(-)