patch, 4 partsreftable/stack: don't perform auto-compaction with less than two tables

Hi,

this small patch series fixes out-of-memory errors on NonStop with the reftable backend. These errors are caused by zero-sized allocations, which return `NULL` pointers on NonStop.

Thanks!

Patrick

---
Patrick Steinhardt (4):
      reftable/stack: don't perform auto-compaction with less than two tables
      reftable/merged: fix zero-sized allocation when there are no readers
      reftable/stack: fix zero-sized allocation when there are no readers
      reftable/basics: return NULL on zero-sized allocations

 reftable/basics.c |  7 +++++++
 reftable/merged.c | 12 +++++++-----
 reftable/stack.c  | 47 ++++++++++++++++++++++++++---------------------
 3 files changed, 40 insertions(+), 26 deletions(-)

--- base-commit: ff795a5c5ed2e2d07c688c217a615d89e3f5733b change-id: 20241220-b4-pks-reftable-oom-fix-without-readers-c7d8fda0694d

In order to compact tables we need at least two tables. Bail out early from `reftable_stack_auto_compact()` in case we have less than two tables.

This is mostly defense in depth: `stack_table_sizes_for_compaction()` may try to allocate a zero-byte object when there aren't any readers, and that may lead to a `NULL` pointer on some platforms like NonStop which causes us to bail out with an out-of-memory error.

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

Patrick Steinhardt <ps@pks.im> writes:

While that is very true, bailing out on "< 2" would change the behaviour. Where there were only one table, earlier we still went ahead and exercised compaction code path, but now we no longer do. The end result of having just a single table might logically be the same with this change, but if we were relying on some side effects of exercising the compaction code path, do we know that the rest of the code is OK?

That's the kind of questions I would ask, if this were somebody who hasn't been deeply involved in the reftable code and came this deep in the pre-release period. But since we all know you have been the main driver for this effort, we'd take your word for it ;-)

Thanks, will queue.

Junio C Hamano <gitster@pobox.com> writes:

And with code inspection, it can trivially seen that this change is perfectly fine.

In the original, when "== 1", stack_table_sizes_for_compaction(st) yields an array with a single element, suggest_compaction_segment() gives back segment with .start and .end both set to 0, for which segment_size() returns 0 hence we do not call stack_compact_range(). The original code happens to do the same when "== 0" (and 0-sized allocation does not give back NULL).

So bypassing all of these when "== 1" is a no-op change, an optimization to avoid allocating a single-element array and then immediately freeing it. Doing so when "== 0" is a strict improvement on a platform with malloc that returns NULL for 0-sized allocation. So bypassing when "< 2" is totally safe and justifyable change.

Thanks.

On Sat, Dec 21, 2024 at 09:51:34AM -0800, Junio C Hamano wrote:

Indeed. I'll include an explanation in v2 of this patch series.

Patrick

It was reported [1c that Git started to fail with an out-of-memory error when initializing repositories with the reftable backend on NonStop platforms. A bisect led to 802c0646ac (reftable/merged: handle allocation failures in `merged_table_init_iter()`, 2024-10-02), which changed how we allocate memory when initializing a merged table.

The root cause of this seems to be that NonStop returns a `NULL` pointer when doing a zero-sized allocation. This would've already happened before the above change, but we never noticed because we did not check the result. Now that we do we notice and thus return an out-of-memory error to the caller.

Fix the issue by skipping the allocation altogether in case there are no readers.

[1]: <00ad01db5017$aa9ce340$ffd6a9c0$@nexbridge.com>

Reported-by: Randall S. Becker <rsbecker@nexbridge.com>
Signed-off-by: Patrick Steinhardt <ps@pks.im>
---
 reftable/merged.c | 12 +++++++-----
 1 file changed, 7 insertions(+), 5 deletions(-)

Hi

On Sat, Dec 21, 2024, at 12:50, Patrick Steinhardt wrote:

A Neo user, I see.

s/c/]/

s/Now that we do we/Now we do notice/

Repeat of “we”. And “that” can’t be be used since it has nothing to connect to.

On Sat, Dec 21, 2024 at 01:40:32PM +0100, Kristoffer Haugsbakk wrote:

There are dozens of us!

Oh, I even saw that typo, but obviously forgot to fix it.

Indeed. Will wait a bit to hear back from Randall before sending another version. Thanks!

Patrick

"Kristoffer Haugsbakk" <kristofferhaugsbakk@fastmail.com> writes:

I read "Now that we do, we notice and ..." a perfectly sensible construct, though.

Thanks.

Similar as the preceding commit, we may try to do a zero-sized allocation when reloading a reftable stack that ain't got any tables. It is implementation-defined whether malloc(3p) returns a NULL pointer in that case or a zero-sized object. In case it does return a NULL pointer though it causes us to think we have run into an out-of-memory situation, and thus we return an error.

Fix this by only allocating arrays when they have at least one entry. Refactor the code so that we don't try to access those arrays in case they are empty.

Reported-by: Randall S. Becker <rsbecker@nexbridge.com>
Signed-off-by: Patrick Steinhardt <ps@pks.im>
---
 reftable/stack.c | 44 +++++++++++++++++++++++---------------------
 1 file changed, 23 insertions(+), 21 deletions(-)

Patrick Steinhardt <ps@pks.im> writes:

This somehow did not cleanly apply, so I whiggled it in manually.

I probably wouldn't mixed the "size_t i" changes into this fix if I were doing it. To avoid "while (*names)" loop, I would have made it to "for (size_t j = 0; j < names_len; j++)" and kept the existing use of "i" intact, instead. And reintroducing for() scoped "i" three times did not seem to make it easier to read the result.

I am not convinced we need to avoid "while (*names)", by the way. If "names" were NULL, names_length() would already have segfaulted anyway, and basics.c:parse_names(), when not returning NULL (which would have been caught by the sole caller of reload_once() as an error), makes sure it gives its caller a NULL-terminated array.

But other than that, this seems to make sure that we avoid unnecessary work when cur_len or new_readers is zero and avoids asking for 0-sized allocation as a side effect of doing so, which is good.

Will queue.  Thanks.

Junio C Hamano <gitster@pobox.com> writes:

That is because I usually ignore author-supplied base, and this time I used the tip of ps/reftable-alloc-failures topic, which brings all the text these four patches touch, in my initial attempt.

Applying these on the author-supplied base (ff795a5c5e) yields the same tree as the result of merging my manual application of these four patches to ps/reftable-alloc-failures into the same base.

On December 21, 2024 12:57 PM, Junio C Hamano wrote:

the tip of

patches touch, in

tree as

ps/reftable-

Ready to test this. Please let me know when and I will report results.

<rsbecker@nexbridge.com> writes:

If you want to start sooner

    $ git checkout -b test ff795a5c5ed2e2d07c688c217a615d89e3f5733b
    $ git am ... these four patches ...

should give you the fix without anything else mixed in. I'll push out the usual four branches after integration testing, but it will be queued in 'seen' (just above the point that corresponds to 'next') first, before merging it to 'next' (and then down to 'master' before -rc1).

Thanks.

On December 21, 2024 1:31 PM, Junio C Hamano wrote:

Becker'

there are no

usual four

above the

before -rc1).

FYI: 'seen' looks better now. I am having issues in t0211-trace2-perf.sh
with
undefined SSL symbols (SSL_get0_group_name), but am able to use git init
again.

On December 22, 2024 12:48 PM, I wrote:

Becker'

before -rc1).

with

again.

'seen' looks good. Operator error on trace2-perf.sh - used the wrong version of OpenSSL.

Thanks, Randall

On Sun, Dec 22, 2024 at 01:17:15PM -0500, rsbecker@nexbridge.com wrote:

Thanks for confirming!

Patrick

Patrick Steinhardt <ps@pks.im> writes:

Thanks, all.

On Sat, Dec 21, 2024 at 09:36:54AM -0800, Junio C Hamano wrote:

True. I was initially erring on the side of being overly cautious here because I didn't yet have the idea to adapt `reftable_malloc()` and `reftable_realloc()` so that they have the same behaviour as NonStop. Let me redo this change and reduce it to the minimum required one.

Patrick

In the preceding commits we have fixed a couple of issues when allocating zero-sized objects. These issues were masked by implementation-defined behaviour. Quoting malloc(3p):

  If size is 0, either:

    * A null pointer shall be returned and errno may be set to an
      implementation-defined value, or

    * A pointer to the allocated space shall be returned. The
      application shall ensure that the pointer is not used to access an
      object.

So it is perfectly valid that implementations of this function may or may not return a NULL pointer in such a case.

Adapt both `reftable_malloc()` and `reftable_realloc()` so that they return NULL pointers on zero-sized allocations. This should remove any implementation-defined behaviour in our allocators and thus allows us to detect such platform-specific issues more easily going forward.

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

On Sat, Dec 21, 2024, at 12:50, Patrick Steinhardt wrote:

Nice commit message.

On December 21, 2024 6:50 AM, Patrick Steinhardt wrote:

From the malloc man page: "If size is 0, then malloc() returns either NULL, or a unique pointer value that can later be successfully passed to free()."

Thank you for this series. I think the problem may not be limited only to NonStop based on the documented ambiguous behaviour of malloc.

--Randall

Randall Becker <randall.becker@nexbridge.ca> writes:

Yes, an implementation is allowed to return NULL when asked to allocate 0 bytes. On the Git side, we sidestep the problem in exactly the opposite way---our malloc() wrapper makes another request to allocate 1-byte block after seeing NULL from a request for 0-byte allocation. The reftable code takes an approach to eliminate the need to requiest 0-sized allocation in the first place, which is an arguably more valid solution.

Thanks, both, for finding and fixing the issue.

Patrick Steinhardt <ps@pks.im> writes:

Interesting. Git side has long been aware of this issue, but because being able to get something out of zero-byte allocation was somehow deemed so useful (and I do not either remember the reasons, nor if I were asked today, I do not know if I agree), our xmalloc() and friends ensure that we never return NULL for 0-sized allocation.

I looked at the patches the places they touch and they are sensible changes to avoid asking 0-sized allocations. Which is the opposite approach from what Git takes *and* which may be more sensible. The callers should know better what they want to do when they have zero sized request. E.g., if they have 0 records to write to in a format that has num-records followed by an array of entries, they may want to make it a no-op, or they may want to explicitly write 0 followed by no entries, to record the fact that such a request was made.

One possible downside of the approach is that all API functions must be vetted for their response to a request that might end up leading to a zero-sized allocation and told to special case such a request, but that is something better donw sooner rather than later.

Will queue.  Thanks.

Hi,

this small patch series fixes out-of-memory errors on NonStop with the reftable backend. These errors are caused by zero-sized allocations, which return `NULL` pointers on NonStop.

Changes in v2:

  - Some small touchups to commit messages.
  - Explain why it is safe to stop auto-compacting with less than two
    tables.
  - Adapt `reftable_stack_reload_once()` so that we only do the minimum
    changes required to fix issue.
  - Link to v1: https://lore.kernel.org/r/20241221-b4-pks-reftable-oom-fix-without-readers-v1-0-12db83a3267c@pks.im

Thanks!

Patrick

---
Patrick Steinhardt (4):
      reftable/stack: don't perform auto-compaction with less than two tables
      reftable/merged: fix zero-sized allocation when there are no readers
      reftable/stack: fix zero-sized allocation when there are no readers
      reftable/basics: return NULL on zero-sized allocations

 reftable/basics.c |  7 +++++++
 reftable/merged.c | 12 +++++++-----
 reftable/stack.c  | 27 +++++++++++++++++----------
 3 files changed, 31 insertions(+), 15 deletions(-)

Range-diff versus v1:

1:  9fcd452995 ! 1:  a7c5b7c52e reftable/stack: don't perform auto-compaction with less than two tables
    @@ Commit message
         from `reftable_stack_auto_compact()` in case we have less than two
         tables.
     
    -    This is mostly defense in depth: `stack_table_sizes_for_compaction()`
    -    may try to allocate a zero-byte object when there aren't any readers,
    -    and that may lead to a `NULL` pointer on some platforms like NonStop
    -    which causes us to bail out with an out-of-memory error.
    +    In the original, `stack_table_sizes_for_compaction()` yields an array
    +    that has the same length as the number of tables. This array is then
    +    passed on to `suggest_compaction_segment()`, which returns an empty
    +    segment in case we have less than two tables. The segment is then passed
    +    to `segment_size()`, which will return `0` because both start and end of
    +    the segment are `0`. And because we only call `stack_compact_range()` in
    +    case we have a positive segment size we don't perform auto-compaction at
    +    all. Consequently, this change does not result in a user-visible change
    +    in behaviour when called with a single table.
    +
    +    But when called with no tables this protects us against a potential
    +    out-of-memory error: `stack_table_sizes_for_compaction()` would try to
    +    allocate a zero-byte object when there aren't any tables, and that may
    +    lead to a `NULL` pointer on some platforms like NonStop which causes us
    +    to bail out with an out-of-memory error.
     
         Signed-off-by: Patrick Steinhardt <ps@pks.im>
     
2:  0703e520de ! 2:  1ca81345ce reftable/merged: fix zero-sized allocation when there are no readers
    @@ Metadata
      ## Commit message ##
         reftable/merged: fix zero-sized allocation when there are no readers
     
    -    It was reported [1c that Git started to fail with an out-of-memory error
    +    It was reported [1] that Git started to fail with an out-of-memory error
         when initializing repositories with the reftable backend on NonStop
         platforms. A bisect led to 802c0646ac (reftable/merged: handle
         allocation failures in `merged_table_init_iter()`, 2024-10-02), which
    @@ Commit message
         The root cause of this seems to be that NonStop returns a `NULL` pointer
         when doing a zero-sized allocation. This would've already happened
         before the above change, but we never noticed because we did not check
    -    the result. Now that we do we notice and thus return an out-of-memory
    -    error to the caller.
    +    the result. Now we do notice and thus return an out-of-memory error to
    +    the caller.
     
         Fix the issue by skipping the allocation altogether in case there are no
         readers.
3:  67baf67817 ! 3:  9be3c6e6c1 reftable/stack: fix zero-sized allocation when there are no readers
    @@ Commit message
         situation, and thus we return an error.
     
         Fix this by only allocating arrays when they have at least one entry.
    -    Refactor the code so that we don't try to access those arrays in case
    -    they are empty.
     
         Reported-by: Randall S. Becker <rsbecker@nexbridge.com>
         Signed-off-by: Patrick Steinhardt <ps@pks.im>
    @@ reftable/stack.c: static int reftable_stack_reload_once(struct reftable_stack *s
      	size_t reused_len = 0, reused_alloc = 0, names_len;
      	size_t new_readers_len = 0;
      	struct reftable_merged_table *new_merged = NULL;
    - 	struct reftable_buf table_path = REFTABLE_BUF_INIT;
    +@@ reftable/stack.c: static int reftable_stack_reload_once(struct reftable_stack *st,
      	int err = 0;
    --	size_t i;
    + 	size_t i;
      
     -	cur = stack_copy_readers(st, cur_len);
     -	if (!cur) {
    @@ reftable/stack.c: static int reftable_stack_reload_once(struct reftable_stack *s
      	}
      
      	names_len = names_length(names);
    --
    + 
     -	new_readers = reftable_calloc(names_len, sizeof(*new_readers));
     -	if (!new_readers) {
     -		err = REFTABLE_OUT_OF_MEMORY_ERROR;
    @@ reftable/stack.c: static int reftable_stack_reload_once(struct reftable_stack *s
     +		}
      	}
      
    --	while (*names) {
    -+	for (size_t i = 0; i < names_len; i++) {
    - 		struct reftable_reader *rd = NULL;
    --		const char *name = *names++;
    -+		const char *name = names[i];
    - 
    - 		/* this is linear; we assume compaction keeps the number of
    - 		   tables under control so this is not quadratic. */
    --		for (i = 0; reuse_open && i < cur_len; i++) {
    --			if (cur[i] && 0 == strcmp(cur[i]->name, name)) {
    --				rd = cur[i];
    --				cur[i] = NULL;
    -+		for (size_t j = 0; reuse_open && j < cur_len; j++) {
    -+			if (cur[j] && 0 == strcmp(cur[j]->name, name)) {
    -+				rd = cur[j];
    -+				cur[j] = NULL;
    - 
    - 				/*
    - 				 * When reloading the stack fails, we end up
    -@@ reftable/stack.c: static int reftable_stack_reload_once(struct reftable_stack *st,
    - 	 * file of such an open reader wouldn't have been possible to be
    - 	 * unlinked by the compacting process.
    - 	 */
    --	for (i = 0; i < cur_len; i++) {
    -+	for (size_t i = 0; i < cur_len; i++) {
    - 		if (cur[i]) {
    - 			const char *name = reader_name(cur[i]);
    - 
    -@@ reftable/stack.c: static int reftable_stack_reload_once(struct reftable_stack *st,
    - 	 * happen on the successful case, because on the unsuccessful one we
    - 	 * decrement their refcount via `new_readers`.
    - 	 */
    --	for (i = 0; i < reused_len; i++)
    -+	for (size_t i = 0; i < reused_len; i++)
    - 		reftable_reader_decref(reused[i]);
    - 
    - done:
    --	for (i = 0; i < new_readers_len; i++)
    -+	for (size_t i = 0; i < new_readers_len; i++)
    - 		reftable_reader_decref(new_readers[i]);
    - 	reftable_free(new_readers);
    - 	reftable_free(reused);
    + 	while (*names) {
4:  16ae8201b1 = 4:  8028e2cf68 reftable/basics: return NULL on zero-sized allocations

--- base-commit: ff795a5c5ed2e2d07c688c217a615d89e3f5733b change-id: 20241220-b4-pks-reftable-oom-fix-without-readers-c7d8fda0694d

In order to compact tables we need at least two tables. Bail out early from `reftable_stack_auto_compact()` in case we have less than two tables.

In the original, `stack_table_sizes_for_compaction()` yields an array that has the same length as the number of tables. This array is then passed on to `suggest_compaction_segment()`, which returns an empty segment in case we have less than two tables. The segment is then passed to `segment_size()`, which will return `0` because both start and end of the segment are `0`. And because we only call `stack_compact_range()` in case we have a positive segment size we don't perform auto-compaction at all. Consequently, this change does not result in a user-visible change in behaviour when called with a single table.

But when called with no tables this protects us against a potential out-of-memory error: `stack_table_sizes_for_compaction()` would try to allocate a zero-byte object when there aren't any tables, and that may lead to a `NULL` pointer on some platforms like NonStop which causes us to bail out with an out-of-memory error.

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

It was reported [1] that Git started to fail with an out-of-memory error when initializing repositories with the reftable backend on NonStop platforms. A bisect led to 802c0646ac (reftable/merged: handle allocation failures in `merged_table_init_iter()`, 2024-10-02), which changed how we allocate memory when initializing a merged table.

The root cause of this seems to be that NonStop returns a `NULL` pointer when doing a zero-sized allocation. This would've already happened before the above change, but we never noticed because we did not check the result. Now we do notice and thus return an out-of-memory error to the caller.

Fix the issue by skipping the allocation altogether in case there are no readers.

[1]: <00ad01db5017$aa9ce340$ffd6a9c0$@nexbridge.com>

Reported-by: Randall S. Becker <rsbecker@nexbridge.com>
Signed-off-by: Patrick Steinhardt <ps@pks.im>
---
 reftable/merged.c | 12 +++++++-----
 1 file changed, 7 insertions(+), 5 deletions(-)

Similar as the preceding commit, we may try to do a zero-sized allocation when reloading a reftable stack that ain't got any tables. It is implementation-defined whether malloc(3p) returns a NULL pointer in that case or a zero-sized object. In case it does return a NULL pointer though it causes us to think we have run into an out-of-memory situation, and thus we return an error.

Fix this by only allocating arrays when they have at least one entry.

Reported-by: Randall S. Becker <rsbecker@nexbridge.com>
Signed-off-by: Patrick Steinhardt <ps@pks.im>
---
 reftable/stack.c | 24 ++++++++++++++----------
 1 file changed, 14 insertions(+), 10 deletions(-)

In the preceding commits we have fixed a couple of issues when allocating zero-sized objects. These issues were masked by implementation-defined behaviour. Quoting malloc(3p):

  If size is 0, either:

    * A null pointer shall be returned and errno may be set to an
      implementation-defined value, or

    * A pointer to the allocated space shall be returned. The
      application shall ensure that the pointer is not used to access an
      object.

So it is perfectly valid that implementations of this function may or may not return a NULL pointer in such a case.

Adapt both `reftable_malloc()` and `reftable_realloc()` so that they return NULL pointers on zero-sized allocations. This should remove any implementation-defined behaviour in our allocators and thus allows us to detect such platform-specific issues more easily going forward.

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

Patrick Steinhardt <ps@pks.im> writes:

Thanks.  All four patches looked good.

Will merge to 'next' and then to 'master'.