reftable: 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(-)

2.43.GIT

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(-)

index 16bab82063..bf869a6772 100644
@@ -304,69 +304,67 @@ static int tv_cmp(struct timeval *a, struct timeval *b)
 static int reftable_stack_reload_maybe_reuse(struct reftable_stack *st,
 					     int reuse_open)
 {
-	struct timeval deadline = { 0 };
-	int err = gettimeofday(&deadline, NULL);
+	char **names = NULL, **names_after = NULL;
+	struct timeval deadline;
 	int64_t delay = 0;
-	int tries = 0;
-	if (err < 0)
-		return err;
+	int tries = 0, err;
 
+	err = gettimeofday(&deadline, NULL);
+	if (err < 0)
+		goto out;
 	deadline.tv_sec += 3;
+
 	while (1) {
-		char **names = NULL;
-		char **names_after = NULL;
-		struct timeval now = { 0 };
-		int err = gettimeofday(&now, NULL);
-		int err2 = 0;
-		if (err < 0) {
-			return err;
-		}
+		struct timeval now;
 
-		/* Only look at deadlines after the first few times. This
-		   simplifies debugging in GDB */
+		err = gettimeofday(&now, NULL);
+		if (err < 0)
+			goto out;
+
+		/*
+		 * Only look at deadlines after the first few times. This
+		 * simplifies debugging in GDB.
+		 */
 		tries++;
-		if (tries > 3 && tv_cmp(&now, &deadline) >= 0) {
-			break;
-		}
+		if (tries > 3 && tv_cmp(&now, &deadline) >= 0)
+			goto out;
 
 		err = read_lines(st->list_file, &names);
-		if (err < 0) {
-			free_names(names);
-			return err;
-		}
+		if (err < 0)
+			goto out;
+
 		err = reftable_stack_reload_once(st, names, reuse_open);
-		if (err == 0) {
-			free_names(names);
+		if (!err)
 			break;
-		}
-		if (err != REFTABLE_NOT_EXIST_ERROR) {
-			free_names(names);
-			return err;
-		}
-
-		/* err == REFTABLE_NOT_EXIST_ERROR can be caused by a concurrent
-		   writer. Check if there was one by checking if the name list
-		   changed.
-		*/
-		err2 = read_lines(st->list_file, &names_after);
-		if (err2 < 0) {
-			free_names(names);
-			return err2;
-		}
-
+		if (err != REFTABLE_NOT_EXIST_ERROR)
+			goto out;
+
+		/*
+		 * REFTABLE_NOT_EXIST_ERROR can be caused by a concurrent
+		 * writer. Check if there was one by checking if the name list
+		 * changed.
+		 */
+		err = read_lines(st->list_file, &names_after);
+		if (err < 0)
+			goto out;
 		if (names_equal(names_after, names)) {
-			free_names(names);
-			free_names(names_after);
-			return err;
+			err = REFTABLE_NOT_EXIST_ERROR;
+			goto out;
 		}
+
 		free_names(names);
+		names = NULL;
 		free_names(names_after);
+		names_after = NULL;
 
 		delay = delay + (delay * rand()) / RAND_MAX + 1;
 		sleep_millisec(delay);
 	}
 
-	return 0;
+out:
+	free_names(names);
+	free_names(names_after);
+	return err;
 }
 
 /* -1 = error

2.43.GIT

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(-)

index bf869a6772..b1ee247601 100644
@@ -308,6 +308,7 @@ static int reftable_stack_reload_maybe_reuse(struct reftable_stack *st,
 	struct timeval deadline;
 	int64_t delay = 0;
 	int tries = 0, err;
+	int fd = -1;
 
 	err = gettimeofday(&deadline, NULL);
 	if (err < 0)

@@ -329,9 +330,19 @@ static int reftable_stack_reload_maybe_reuse(struct reftable_stack *st,
 		if (tries > 3 && tv_cmp(&now, &deadline) >= 0)
 			goto out;
 
-		err = read_lines(st->list_file, &names);
-		if (err < 0)
-			goto out;
+		fd = open(st->list_file, O_RDONLY);
+		if (fd < 0) {
+			if (errno != ENOENT) {
+				err = REFTABLE_IO_ERROR;
+				goto out;
+			}
+
+			names = reftable_calloc(sizeof(char *));
+		} else {
+			err = fd_read_lines(fd, &names);
+			if (err < 0)
+				goto out;
+		}
 
 		err = reftable_stack_reload_once(st, names, reuse_open);
 		if (!err)

@@ -356,12 +367,16 @@ static int reftable_stack_reload_maybe_reuse(struct reftable_stack *st,
 		names = NULL;
 		free_names(names_after);
 		names_after = NULL;
+		close(fd);
+		fd = -1;
 
 		delay = delay + (delay * rand()) / RAND_MAX + 1;
 		sleep_millisec(delay);
 	}
 
 out:
+	if (fd >= 0)
+		close(fd);
 	free_names(names);
 	free_names(names_after);
 	return err;

2.43.GIT

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(-)

index b1ee247601..a51a2dbf1f 100644
@@ -175,6 +175,7 @@ void reftable_stack_destroy(struct reftable_stack *st)
 		st->readers_len = 0;
 		FREE_AND_NULL(st->readers);
 	}
+	stat_validity_clear(&st->list_validity);
 	FREE_AND_NULL(st->list_file);
 	FREE_AND_NULL(st->reftable_dir);
 	reftable_free(st);

@@ -374,6 +375,8 @@ static int reftable_stack_reload_maybe_reuse(struct reftable_stack *st,
 		sleep_millisec(delay);
 	}
 
+	stat_validity_update(&st->list_validity, fd);
+
 out:
 	if (fd >= 0)
 		close(fd);

@@ -388,8 +391,13 @@ static int reftable_stack_reload_maybe_reuse(struct reftable_stack *st,
 static int stack_uptodate(struct reftable_stack *st)
 {
 	char **names = NULL;
-	int err = read_lines(st->list_file, &names);
+	int err;
 	int i = 0;
+
+	if (stat_validity_check(&st->list_validity, st->list_file))
+		return 0;
+
+	err = read_lines(st->list_file, &names);
 	if (err < 0)
 		return err;
 

index f57005846e..3f80cc598a 100644
@@ -14,6 +14,7 @@ license that can be found in the LICENSE file or at
 #include "reftable-stack.h"
 
 struct reftable_stack {
+	struct stat_validity list_validity;
 	char *list_file;
 	char *reftable_dir;
 	int disable_auto_compact;

index 6b74a81514..2cc7adf271 100644
@@ -12,6 +12,7 @@ license that can be found in the LICENSE file or at
 /* This header glues the reftable library to the rest of Git */
 
 #include "git-compat-util.h"
+#include "statinfo.h"
 #include "strbuf.h"
 #include "hash-ll.h" /* hash ID, sizes.*/
 #include "dir.h" /* remove_dir_recursively, for tests.*/

2.43.GIT

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(-)

index a1ea304429..5d3f3d264c 100644
@@ -13,6 +13,12 @@ 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)

@@ -78,6 +84,7 @@ struct reftable_block_source malloc_block_source(void)
 struct file_block_source {
 	int fd;
 	uint64_t size;
+	unsigned char *data;
 };
 
 static uint64_t file_size(void *b)

@@ -87,19 +94,23 @@ static uint64_t file_size(void *b)
 
 static void file_return_block(void *b, struct reftable_block *dest)
 {
-	if (dest->len)
-		memset(dest->data, 0xff, dest->len);
-	reftable_free(dest->data);
 }
 
-static void file_close(void *b)
+static void file_close(void *v)
 {
-	int fd = ((struct file_block_source *)b)->fd;
-	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;
+
 	reftable_free(b);
 }
 

@@ -108,9 +119,7 @@ static int file_read_block(void *v, struct reftable_block *dest, uint64_t off,
 {
 	struct file_block_source *b = v;
 	assert(off + size <= b->size);
-	dest->data = reftable_malloc(size);
-	if (pread_in_full(b->fd, dest->data, size, off) != size)
-		return -1;
+	dest->data = b->data + off;
 	dest->len = size;
 	return size;
 }

@@ -127,8 +136,10 @@ 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;

@@ -144,7 +155,18 @@ int reftable_block_source_from_file(struct reftable_block_source *bs,
 
 	p = reftable_calloc(sizeof(struct file_block_source));
 	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;
+	}
 
 	assert(!bs->ops);
 	bs->ops = &file_vtable;

2.43.GIT

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).

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.

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

Nice.

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.

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

Patrick

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

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 <[email protected]>
+
## 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 <[email protected]>
+
## 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 <[email protected]>

## 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 <[email protected]>
+
## 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

2.43.GIT

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(-)

index 16bab82063..bf869a6772 100644
@@ -304,69 +304,67 @@ static int tv_cmp(struct timeval *a, struct timeval *b)
 static int reftable_stack_reload_maybe_reuse(struct reftable_stack *st,
 					     int reuse_open)
 {
-	struct timeval deadline = { 0 };
-	int err = gettimeofday(&deadline, NULL);
+	char **names = NULL, **names_after = NULL;
+	struct timeval deadline;
 	int64_t delay = 0;
-	int tries = 0;
-	if (err < 0)
-		return err;
+	int tries = 0, err;
 
+	err = gettimeofday(&deadline, NULL);
+	if (err < 0)
+		goto out;
 	deadline.tv_sec += 3;
+
 	while (1) {
-		char **names = NULL;
-		char **names_after = NULL;
-		struct timeval now = { 0 };
-		int err = gettimeofday(&now, NULL);
-		int err2 = 0;
-		if (err < 0) {
-			return err;
-		}
+		struct timeval now;
 
-		/* Only look at deadlines after the first few times. This
-		   simplifies debugging in GDB */
+		err = gettimeofday(&now, NULL);
+		if (err < 0)
+			goto out;
+
+		/*
+		 * Only look at deadlines after the first few times. This
+		 * simplifies debugging in GDB.
+		 */
 		tries++;
-		if (tries > 3 && tv_cmp(&now, &deadline) >= 0) {
-			break;
-		}
+		if (tries > 3 && tv_cmp(&now, &deadline) >= 0)
+			goto out;
 
 		err = read_lines(st->list_file, &names);
-		if (err < 0) {
-			free_names(names);
-			return err;
-		}
+		if (err < 0)
+			goto out;
+
 		err = reftable_stack_reload_once(st, names, reuse_open);
-		if (err == 0) {
-			free_names(names);
+		if (!err)
 			break;
-		}
-		if (err != REFTABLE_NOT_EXIST_ERROR) {
-			free_names(names);
-			return err;
-		}
-
-		/* err == REFTABLE_NOT_EXIST_ERROR can be caused by a concurrent
-		   writer. Check if there was one by checking if the name list
-		   changed.
-		*/
-		err2 = read_lines(st->list_file, &names_after);
-		if (err2 < 0) {
-			free_names(names);
-			return err2;
-		}
-
+		if (err != REFTABLE_NOT_EXIST_ERROR)
+			goto out;
+
+		/*
+		 * REFTABLE_NOT_EXIST_ERROR can be caused by a concurrent
+		 * writer. Check if there was one by checking if the name list
+		 * changed.
+		 */
+		err = read_lines(st->list_file, &names_after);
+		if (err < 0)
+			goto out;
 		if (names_equal(names_after, names)) {
-			free_names(names);
-			free_names(names_after);
-			return err;
+			err = REFTABLE_NOT_EXIST_ERROR;
+			goto out;
 		}
+
 		free_names(names);
+		names = NULL;
 		free_names(names_after);
+		names_after = NULL;
 
 		delay = delay + (delay * rand()) / RAND_MAX + 1;
 		sleep_millisec(delay);
 	}
 
-	return 0;
+out:
+	free_names(names);
+	free_names(names_after);
+	return err;
 }
 
 /* -1 = error

2.43.GIT

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(-)

index bf869a6772..b1ee247601 100644
@@ -308,6 +308,7 @@ static int reftable_stack_reload_maybe_reuse(struct reftable_stack *st,
 	struct timeval deadline;
 	int64_t delay = 0;
 	int tries = 0, err;
+	int fd = -1;
 
 	err = gettimeofday(&deadline, NULL);
 	if (err < 0)

@@ -329,9 +330,19 @@ static int reftable_stack_reload_maybe_reuse(struct reftable_stack *st,
 		if (tries > 3 && tv_cmp(&now, &deadline) >= 0)
 			goto out;
 
-		err = read_lines(st->list_file, &names);
-		if (err < 0)
-			goto out;
+		fd = open(st->list_file, O_RDONLY);
+		if (fd < 0) {
+			if (errno != ENOENT) {
+				err = REFTABLE_IO_ERROR;
+				goto out;
+			}
+
+			names = reftable_calloc(sizeof(char *));
+		} else {
+			err = fd_read_lines(fd, &names);
+			if (err < 0)
+				goto out;
+		}
 
 		err = reftable_stack_reload_once(st, names, reuse_open);
 		if (!err)

@@ -356,12 +367,16 @@ static int reftable_stack_reload_maybe_reuse(struct reftable_stack *st,
 		names = NULL;
 		free_names(names_after);
 		names_after = NULL;
+		close(fd);
+		fd = -1;
 
 		delay = delay + (delay * rand()) / RAND_MAX + 1;
 		sleep_millisec(delay);
 	}
 
 out:
+	if (fd >= 0)
+		close(fd);
 	free_names(names);
 	free_names(names_after);
 	return err;

2.43.GIT

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~)

---
 reftable/stack.c  | 12 +++++++++++-
 reftable/stack.h  |  1 +
 reftable/system.h |  1 +
 3 files changed, 13 insertions(+), 1 deletion(-)

index b1ee247601..c28d82299d 100644
@@ -175,6 +175,7 @@ void reftable_stack_destroy(struct reftable_stack *st)
 		st->readers_len = 0;
 		FREE_AND_NULL(st->readers);
 	}
+	stat_validity_clear(&st->list_validity);
 	FREE_AND_NULL(st->list_file);
 	FREE_AND_NULL(st->reftable_dir);
 	reftable_free(st);

@@ -374,7 +375,11 @@ static int reftable_stack_reload_maybe_reuse(struct reftable_stack *st,
 		sleep_millisec(delay);
 	}
 
+	stat_validity_update(&st->list_validity, fd);
+
 out:
+	if (err)
+		stat_validity_clear(&st->list_validity);
 	if (fd >= 0)
 		close(fd);
 	free_names(names);

@@ -388,8 +393,13 @@ static int reftable_stack_reload_maybe_reuse(struct reftable_stack *st,
 static int stack_uptodate(struct reftable_stack *st)
 {
 	char **names = NULL;
-	int err = read_lines(st->list_file, &names);
+	int err;
 	int i = 0;
+
+	if (stat_validity_check(&st->list_validity, st->list_file))
+		return 0;
+
+	err = read_lines(st->list_file, &names);
 	if (err < 0)
 		return err;
 

index f57005846e..3f80cc598a 100644
@@ -14,6 +14,7 @@ license that can be found in the LICENSE file or at
 #include "reftable-stack.h"
 
 struct reftable_stack {
+	struct stat_validity list_validity;
 	char *list_file;
 	char *reftable_dir;
 	int disable_auto_compact;

index 6b74a81514..2cc7adf271 100644
@@ -12,6 +12,7 @@ license that can be found in the LICENSE file or at
 /* This header glues the reftable library to the rest of Git */
 
 #include "git-compat-util.h"
+#include "statinfo.h"
 #include "strbuf.h"
 #include "hash-ll.h" /* hash ID, sizes.*/
 #include "dir.h" /* remove_dir_recursively, for tests.*/

2.43.GIT

Refactor reftable_block_source_from_file() to match our coding style better.

---
 reftable/blocksource.c | 17 ++++++++---------
 1 file changed, 8 insertions(+), 9 deletions(-)

index a1ea304429..1e2fb5e9fd 100644
@@ -125,24 +125,23 @@ static struct reftable_block_source_vtable file_vtable = {
 int reftable_block_source_from_file(struct reftable_block_source *bs,
 				    const char *name)
 {
-	struct stat st = { 0 };
-	int err = 0;
-	int fd = open(name, O_RDONLY);
-	struct file_block_source *p = NULL;
+	struct file_block_source *p;
+	struct stat st;
+	int fd;
+
+	fd = open(name, O_RDONLY);
 	if (fd < 0) {
-		if (errno == ENOENT) {
+		if (errno == ENOENT)
 			return REFTABLE_NOT_EXIST_ERROR;
-		}
 		return -1;
 	}
 
-	err = fstat(fd, &st);
-	if (err < 0) {
+	if (fstat(fd, &st) < 0) {
 		close(fd);
 		return REFTABLE_IO_ERROR;
 	}
 
-	p = reftable_calloc(sizeof(struct file_block_source));
+	p = reftable_calloc(sizeof(*p));
 	p->size = st.st_size;
 	p->fd = fd;
 

2.43.GIT

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.

---
 reftable/blocksource.c | 22 +++++++---------------
 1 file changed, 7 insertions(+), 15 deletions(-)

index 1e2fb5e9fd..8c41e3c70f 100644
@@ -76,8 +76,8 @@ struct reftable_block_source malloc_block_source(void)
 }
 
 struct file_block_source {
-	int fd;
 	uint64_t size;
+	unsigned char *data;
 };
 
 static uint64_t file_size(void *b)

@@ -87,19 +87,12 @@ static uint64_t file_size(void *b)
 
 static void file_return_block(void *b, struct reftable_block *dest)
 {
-	if (dest->len)
-		memset(dest->data, 0xff, dest->len);
-	reftable_free(dest->data);
 }
 
-static void file_close(void *b)
+static void file_close(void *v)
 {
-	int fd = ((struct file_block_source *)b)->fd;
-	if (fd > 0) {
-		close(fd);
-		((struct file_block_source *)b)->fd = 0;
-	}
-
+	struct file_block_source *b = v;
+	munmap(b->data, b->size);
 	reftable_free(b);
 }
 

@@ -108,9 +101,7 @@ static int file_read_block(void *v, struct reftable_block *dest, uint64_t off,
 {
 	struct file_block_source *b = v;
 	assert(off + size <= b->size);
-	dest->data = reftable_malloc(size);
-	if (pread_in_full(b->fd, dest->data, size, off) != size)
-		return -1;
+	dest->data = b->data + off;
 	dest->len = size;
 	return size;
 }

@@ -143,7 +134,8 @@ int reftable_block_source_from_file(struct reftable_block_source *bs,
 
 	p = reftable_calloc(sizeof(*p));
 	p->size = st.st_size;
-	p->fd = fd;
+	p->data = xmmap(NULL, st.st_size, PROT_READ, MAP_PRIVATE, fd, 0);
+	close(fd);
 
 	assert(!bs->ops);
 	bs->ops = &file_vtable;

2.43.GIT

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:

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

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

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.