diff options
author | Patrick Steinhardt <ps@pks.im> | 2019-09-19 12:46:37 +0200 |
---|---|---|
committer | Patrick Steinhardt <ps@pks.im> | 2020-03-26 16:20:18 +0100 |
commit | 93dc8a04ec89bea1e8401e2fd7a9d9ef31e67537 (patch) | |
tree | b589c6227ad5343a0d000922f231961bf8ac57bf | |
parent | 18ca62de01a5c1631f879a3ba0cb0ae0817c8e38 (diff) | |
download | libgit2-93dc8a04ec89bea1e8401e2fd7a9d9ef31e67537.tar.gz |
buffer: fix infinite loop when growing buffers
When growing buffers, we repeatedly multiply the currently allocated
number of bytes by 1.5 until it exceeds the requested number of bytes.
This has two major problems:
1. If the current number of bytes is tiny and one wishes to resize
to a comparatively huge number of bytes, then we may need to loop
thousands of times.
2. If resizing to a value close to `SIZE_MAX` (which would fail
anyway), then we probably hit an infinite loop as multiplying the
current amount of bytes will repeatedly result in integer
overflows.
When reallocating buffers, one typically chooses values close to 1.5 to
enable re-use of resulting memory holes in later reallocations. But
because of this, it really only makes sense to use a factor of 1.5
_once_, but not looping until we finally are able to fit it. Thus, we
can completely avoid the loop and just opt for the much simpler
algorithm of multiplying with 1.5 once and, if the result doesn't fit,
just use the target size. This avoids both problems of looping
extensively and hitting overflows.
This commit also adds a test that would've previously resulted in an
infinite loop.
-rw-r--r-- | src/buffer.c | 13 | ||||
-rw-r--r-- | tests/core/buffer.c | 22 |
2 files changed, 27 insertions, 8 deletions
diff --git a/src/buffer.c b/src/buffer.c index 8acf2accd..dff2c37eb 100644 --- a/src/buffer.c +++ b/src/buffer.c @@ -58,14 +58,17 @@ int git_buf_try_grow( new_ptr = NULL; } else { new_size = buf->asize; + /* + * Grow the allocated buffer by 1.5 to allow + * re-use of memory holes resulting from the + * realloc. If this is still too small, then just + * use the target size. + */ + if ((new_size = (new_size << 1) - (new_size >> 1)) < target_size) + new_size = target_size; new_ptr = buf->ptr; } - /* grow the buffer size by 1.5, until it's big enough - * to fit our target size */ - while (new_size < target_size) - new_size = (new_size << 1) - (new_size >> 1); - /* round allocation up to multiple of 8 */ new_size = (new_size + 7) & ~7; diff --git a/tests/core/buffer.c b/tests/core/buffer.c index b8a76b39c..4ef1274aa 100644 --- a/tests/core/buffer.c +++ b/tests/core/buffer.c @@ -231,9 +231,9 @@ check_buf_append( git_buf_puts(&tgt, data_b); cl_assert(git_buf_oom(&tgt) == 0); cl_assert_equal_s(expected_data, git_buf_cstr(&tgt)); - cl_assert(tgt.size == expected_size); + cl_assert_equal_i(tgt.size, expected_size); if (expected_asize > 0) - cl_assert(tgt.asize == expected_asize); + cl_assert_equal_i(tgt.asize, expected_asize); git_buf_dispose(&tgt); } @@ -308,7 +308,7 @@ void test_core_buffer__5(void) REP16("x") REP16("o"), 32, 40); check_buf_append(test_4096, "", test_4096, 4096, 4104); - check_buf_append(test_4096, test_4096, test_8192, 8192, 9240); + check_buf_append(test_4096, test_4096, test_8192, 8192, 8200); /* check sequences of appends */ check_buf_append_abc("a", "b", "c", @@ -1204,3 +1204,19 @@ void test_core_buffer__dont_grow_borrowed(void) cl_git_fail_with(GIT_EINVALID, git_buf_grow(&buf, 1024)); } + +void test_core_buffer__dont_hit_infinite_loop_when_resizing(void) +{ + git_buf buf = GIT_BUF_INIT; + + cl_git_pass(git_buf_puts(&buf, "foobar")); + /* + * We do not care whether this succeeds or fails, which + * would depend on platform-specific allocation + * semantics. We only want to know that the function + * actually returns. + */ + (void)git_buf_try_grow(&buf, SIZE_MAX, true); + + git_buf_dispose(&buf); +} |