packed_ref_cache: don't use mmap() for small files

Take a hint from commit ea68b0ce9f8ce8da3e360aed3cbd6720159ffbee and use

read() instead of mmap() for small packed-refs files.

This also fixes the problem[1] where xmmap() returns NULL for zero length[2], for which munmap() later fails.

Alternatively, we could simply check for NULL before munmap(), or introduce an xmunmap() that could be used together with xmmap().

[1] https://github.com/git-for-windows/git/issues/1410
[2] Logic introduced in commit 9130ac1e1966adb9922e64f645730d0d45383495

Signed-off-by Kim Gybels <[email protected]>

---
 refs/packed-backend.c | 14 ++++++++------
 1 file changed, 8 insertions(+), 6 deletions(-)

refs/packed-backend.c +7 -2

index dab8a85d9a..7177e5bc2f 100644
@@ -455,6 +455,8 @@ static void verify_buffer_safe(struct snapshot *snapshot)
 				 last_line, eof - last_line);
 }
 
+#define SMALL_FILE_SIZE (32*1024)
+
 /*
  * Depending on `mmap_strategy`, either mmap or read the contents of
  * the `packed-refs` file into the snapshot. Return 1 if the file

@@ -489,21 +491,21 @@ static int load_contents(struct snapshot *snapshot)
 		die_errno("couldn't stat %s", snapshot->refs->path);
 	size = xsize_t(st.st_size);
 
-	switch (mmap_strategy) {
-	case MMAP_NONE:
+	if (!size) {
+		snapshot->buf = NULL;
+		snapshot->eof = NULL;
+		snapshot->mmapped = 0;
+	} else if (size <= SMALL_FILE_SIZE || mmap_strategy == MMAP_NONE) {
 		snapshot->buf = xmalloc(size);
 		bytes_read = read_in_full(fd, snapshot->buf, size);
 		if (bytes_read < 0 || bytes_read != size)
 			die_errno("couldn't read %s", snapshot->refs->path);
 		snapshot->eof = snapshot->buf + size;
 		snapshot->mmapped = 0;

Thanks for your patch. I haven't measured the performance difference of mmap() vs. read() for small packed-refs files, but it's not surprising that read() would be faster.

I especially like the fix for zero-length packed-refs files. (Even though AFAIK Git never writes such files, they are totally legitimate and shouldn't cause Git to fail.) With or without the additions mentioned below,

Reviewed-by Michael Haggerty <[email protected]>

While reviewing your patch, I realized that some areas of the existing code use constructs that are undefined according to the C standard, such as computing NULL + 0 and NULL - NULL. This was already wrong (and would come up more frequently after your change). Even though these are unlikely to be problems in the real world, it would be good to avoid them.

So I will follow up this email with three patches:

1. Mention that snapshot::buf can be NULL for empty files

I suggest squashing this into your patch, to make it clear that snapshot::buf and snapshot::eof can also be NULL if the packed-refs file is empty.

2. create_snapshot(): exit early if the file was empty

Avoid undefined behavior by returning early if snapshot->buf is NULL.

3. find_reference_location(): don't invoke if snapshot->buf is NULL

Avoid undefined behavior and confusing semantics by not calling find_reference_location() when snapshot->buf is NULL.

Michael

Michael Haggerty (3):
SQUASH? Mention that snapshot::buf can be NULL for empty files create_snapshot(): exit early if the file was empty find_reference_location(): don't invoke if snapshot->buf is NULL

So I will follow up this email with three patches:

1. Mention that snapshot::buf can be NULL for empty files

I suggest squashing this into your patch, to make it clear that snapshot::buf and snapshot::eof can also be NULL if the packed-refs file is empty.

2. create_snapshot(): exit early if the file was empty

Avoid undefined behavior by returning early if snapshot->buf is NULL.

3. find_reference_location(): don't invoke if snapshot->buf is NULL

Avoid undefined behavior and confusing semantics by not calling find_reference_location() when snapshot->buf is NULL.

Take a hint from commit ea68b0ce9f8ce8da3e360aed3cbd6720159ffbee and use read() instead of mmap() for small packed-refs files.

This also fixes the problem[1] where xmmap() returns NULL for zero length[2], for which munmap() later fails.

Alternatively, we could simply check for NULL before munmap(), or introduce an xmunmap() that could be used together with xmmap().

refs/packed-backend.c +1 -2

@@ -489,21 +491,21 @@ static int load_contents(struct snapshot *snapshot)
 		die_errno("couldn't stat %s", snapshot->refs->path);
 	size = xsize_t(st.st_size);
 
-	switch (mmap_strategy) {
-	case MMAP_NONE:
+	if (!size) {

Quoted 3 lines · Kim Gybels

Take a hint from commit ea68b0ce9f8ce8da3e360aed3cbd6720159ffbee and use read() instead of mmap() for small packed-refs files.

Quoted 5 lines

This also fixes the problem[1] where xmmap() returns NULL for zero length[2], for which munmap() later fails.

Alternatively, we could simply check for NULL before munmap(), or introduce an xmunmap() that could be used together with xmmap().

This looks good to me, and since it's a recent-ish regression, I think we should take the minimal fix here.

But it does make me wonder whether xmmap() ought to be doing this "small mmap" optimization for us. Obviously that only works when we do MAP_PRIVATE and never write to the result. But that's how we always use it anyway, and we're restricted to that to work with the NO_MMAP wrapper in compat/mmap.c.

Quoted 15 lines

refs/packed-backend.c +5 -2

@@ -489,21 +491,21 @@ static int load_contents(struct snapshot *snapshot)
 		die_errno("couldn't stat %s", snapshot->refs->path);
 	size = xsize_t(st.st_size);
 
-	switch (mmap_strategy) {
-	case MMAP_NONE:
+	if (!size) {
+		snapshot->buf = NULL;
+		snapshot->eof = NULL;
+		snapshot->mmapped = 0;
+	} else if (size <= SMALL_FILE_SIZE || mmap_strategy == MMAP_NONE) {
 		snapshot->buf = xmalloc(size);
 		bytes_read = read_in_full(fd, snapshot->buf, size);
 		if (bytes_read < 0 || bytes_read != size)
 			die_errno("couldn't read %s", snapshot->refs->path);

refs/packed-backend.c static int load_contents(struct snapshot *snapshot) · line 504

Quoted 2 lines

refs/packed-backend.c +0 -0

 		snapshot->eof = snapshot->buf + size;
 		snapshot->mmapped = 0;

If the "!size" case is just lumped in with "size <= SMALL_FILE_SIZE", then we'd try to xmalloc(0), which is guaranteed to work (we fallback to a 1-byte allocation if necessary). Would that make things simpler and more consistent for the rest of the code to always have snapshot->buf be a valid pointer (just based on seeing Michael's follow-up patches)?

Quoted 2 lines

This looks good to me, and since it's a recent-ish regression, I think we should take the minimal fix here.

The minimal fix being a simple NULL check before munmap()?

Quoted 5 lines

But it does make me wonder whether xmmap() ought to be doing this "small mmap" optimization for us. Obviously that only works when we do MAP_PRIVATE and never write to the result. But that's how we always use it anyway, and we're restricted to that to work with the NO_MMAP wrapper in compat/mmap.c.

Maybe I should have left the optimization for small files out of the patch for the zero length regression. After all, read() vs mmap() performance might depend on other factors than just size.

Quoted 5 lines

If the "!size" case is just lumped in with "size <= SMALL_FILE_SIZE", then we'd try to xmalloc(0), which is guaranteed to work (we fallback to a 1-byte allocation if necessary). Would that make things simpler and more consistent for the rest of the code to always have snapshot->buf be a valid pointer (just based on seeing Michael's follow-up patches)?

Indeed, all those patches are to avoid using the NULL pointers in ways that are undefined. We could also copy index_core's way of handling the zero length case:
ret = index_mem(sha1, "", size, type, path, flags);

Point to some static memory instead of NULL, then all the pointer arithmetic is defined.

Take a hint from commit ea68b0ce9f8 (hash-object: don't use mmap() for small files, 2010-02-21) and use read() instead of mmap() for small packed-refs files.

This also fixes the problem[1] where xmmap() returns NULL for zero length[2], for which munmap() later fails.

Alternatively, we could simply check for NULL before munmap(), or introduce xmunmap() that could be used together with xmmap(). However, always setting snapshot->buf to a valid pointer, by relying on xmalloc(0)'s fallback to 1-byte allocation, makes using snapshots easier.

[1] https://github.com/git-for-windows/git/issues/1410
[2] Logic introduced in commit 9130ac1e196 (Better error messages for

    corrupt databases, 2007-01-11)

Signed-off-by Kim Gybels <[email protected]>

---

Change since v2: removed separate case for zero length as suggested by Peff, ensuring that snapshot->buf is always a valid pointer.

Quoted 17 lines · Kim Gybels

Take a hint from commit ea68b0ce9f8 (hash-object: don't use mmap() for small files, 2010-02-21) and use read() instead of mmap() for small packed-refs files.

This also fixes the problem[1] where xmmap() returns NULL for zero length[2], for which munmap() later fails.

Alternatively, we could simply check for NULL before munmap(), or introduce xmunmap() that could be used together with xmmap(). However, always setting snapshot->buf to a valid pointer, by relying on xmalloc(0)'s fallback to 1-byte allocation, makes using snapshots easier.

[1] https://github.com/git-for-windows/git/issues/1410
[2] Logic introduced in commit 9130ac1e196 (Better error messages for

    corrupt databases, 2007-01-11)

Quoted 5 lines

Signed-off-by Kim Gybels <[email protected]>

---

Change since v2: removed separate case for zero length as suggested by Peff, ensuring that snapshot->buf is always a valid pointer.

Thanks, this looks fine to me (I'd be curious to hear from Michael if this eliminates the need for the other patches).

snapshot->buf can still be NULL if the packed-refs file didn't exist (see the earlier code path in load_contents()). So either that code path *also* has to get the xmalloc() treatment, or my third patch is still necessary. (My second patch wouldn't be necessary because the ENOENT case makes load_contents() return 0, triggering the early exit from create_snapshot().)

I don't have a strong preference either way.

Quoted 8 lines · Michael Haggerty

snapshot->buf can still be NULL if the packed-refs file didn't exist (see the earlier code path in load_contents()). So either that code path *also* has to get the xmalloc() treatment, or my third patch is still necessary. (My second patch wouldn't be necessary because the ENOENT case makes load_contents() return 0, triggering the early exit from create_snapshot().)

I don't have a strong preference either way.

Which would be a two-liner, like the attached, which does not look too bad by itself.

The direction, if we take this approach, means that we are declaring that .buf being NULL is an invalid state for a snapshot to be in, instead of saying "an empty snapshot looks exactly like one that was freshly initialized", which seems to be the intention of the original design.

After Kim's fix and with 3/3 in your follow-up series, various helpers are still unsafe against .buf being NULL, like sort_snapshot(), verify_buffer_safe(), clear_snapshot_buffer() (only when mmapped bit is set), find_reference_location().

packed_ref_iterator_begin() checks if snapshot->buf is NULL and returns early. At the first glance, this appears a useful short cut to optimize the empty case away, but the check also is acting as a guard to prevent a snapshot with NULL .buf from being fed to an unsafe find_reference_location(). An implicit guard like this feels a bit more brittle than my liking. If we ensure .buf is never NULL, that check can become a pure short-cut optimization and stop being a correctness thing.

So...

 refs/packed-backend.c | 9 ++++-----
 1 file changed, 4 insertions(+), 5 deletions(-)

refs/packed-backend.c +0 -3

index b6e2bc3c1d..1eeb5c7f80 100644
@@ -473,12 +473,11 @@ static int load_contents(struct snapshot *snapshot)
 	if (fd < 0) {
 		if (errno == ENOENT) {
 			/*
-			 * This is OK; it just means that no
-			 * "packed-refs" file has been written yet,
-			 * which is equivalent to it being empty,

This patch series fixes the handling of empty packed-refs snapshots (i.e., those with snapshot->buf and friends equal to NULL), partly by changing snapshot to store a pointer to the start of the post-header packed-refs content instead of header_len. It makes a couple of other improvements as well.

I'm not sure whether I like this approach better than the alternative of always setting snapshot->buf to a non-NULL value, by allocating a length-1 bit of RAM if necessary. The latter is less intrusive, though even if that approach is taken, I think patches 01, 02, and 04 from this patch series would be worthwhile improvements.

This patch series fixes the handling of empty packed-refs snapshots (i.e., those with snapshot->buf and friends equal to NULL), partly by changing snapshot to store a pointer to the start of the post-header packed-refs content instead of header_len. It makes a couple of other improvements as well.

I'm not sure whether I like this approach better than the alternative of always setting snapshot->buf to a non-NULL value, by allocating a length-1 bit of RAM if necessary. The latter is less intrusive, though even if that approach is taken, I think patches 01, 02, and 04 from this patch series would be worthwhile improvements.

This patch series fixes the handling of empty packed-refs snapshots (i.e., those with snapshot->buf and friends equal to NULL), partly by changing snapshot to store a pointer to the start of the post-header packed-refs content instead of header_len. It makes a couple of other improvements as well.

I'm not sure whether I like this approach better than the alternative of always setting snapshot->buf to a non-NULL value, by allocating a length-1 bit of RAM if necessary. The latter is less intrusive, though even if that approach is taken, I think patches 01, 02, and 04 from this patch series would be worthwhile improvements.

Store a pointer to the start of the actual references within the packed-refs contents rather than storing the length of the header. This is more convenient for most users of this field.

Quoted 9 lines · Michael Haggerty

refs/packed-backend.c +0 -0

index 08698de6ea..361affd7ad 100644
[...]

@@ -551,7 +553,7 @@ static const char *find_reference_location(struct snapshot *snapshot,
 	 */
 	const char *hi = snapshot->eof;
 

refs/packed-backend.c static const char *find_reference_location(struct snapshot *snapshot, · line 558

Quoted 4 lines

refs/packed-backend.c +1 -1

-	while (lo < hi) {
+	while (lo != hi) {
 		const char *mid, *rec;
 		int cmp;

This tightens the binary search termination condition. If we ever did see "hi > lo", we'd want to terminate the loop. Is that ever possible?

I think the answer is "no". Our "hi" here is an exclusive bound, so we should never go past it via find_end_of_record() when assigning "lo". And "hi" is always assigned from the start of the current record. That can never cross "lo", because find_start_of_record() ensures it.

So I think it's fine, but I wanted to double check.

Quoted 2 lines

This tightens the binary search termination condition. If we ever did see "hi > lo", we'd want to terminate the loop. Is that ever possible?

I think you meant "lo > hi", but I shared the same "Huh?" moment.

Because "While lo is strictly lower than hi" is a so well established binary search pattern, even though we know that it is equivalent to "While lo and hi is different" due to your analysis below, the new code looks somewhat strange at the first glance.

Quoted 6 lines

I think the answer is "no". Our "hi" here is an exclusive bound, so we should never go past it via find_end_of_record() when assigning "lo". And "hi" is always assigned from the start of the current record. That can never cross "lo", because find_start_of_record() ensures it.

So I think it's fine, but I wanted to double check.

It would be much simpler to reason about if we instead do

	#define is_empty_snapshot(s) ((s)->start == NULL)

	if (is_empty_snapshot(snapshot))
		return NULL;

or something like that upfront.

We can return an empty iterator not only if the packed-refs file is missing, but also if it is empty or if there are no references whose names succeed prefix. Optimize away those cases as well by moving the call to find_reference_location() higher in the function and checking whether the determined start position is the same as snapshot->eof. (This is possible now because the previous commit made find_reference_location() robust against empty snapshots.)

The change to using read() rather than mmap() for small packed-refs feels like it should be an improvement, but it occurred to me that the performance numbers quoted in ea68b0ce9f8 (hash-object:
don't use mmap() for small files, 2010-02-21) are not directly

applicable to the packed-refs file. As far as I understand, the file mmapped in index_fd() is always read in full, whereas the main point of mmapping the packed-refs file is to avoid having to read the whole file at all in some situations. That being said, a 32 KiB file would only be 8 pages (assuming a page size of 4 KiB), and by the time you've read the header and binary-searched to find the desired record, you've probably paged in most of the file anyway. Reading the whole file at once, in order, is almost certainly cheaper.