From 4b7eb1792e9e593fdb9e5c37cbf58d552f0761eb Mon Sep 17 00:00:00 2001
From: Deomid Ryabkov <rojer@cesanta.com>
Date: Thu, 22 Mar 2018 14:58:20 +0000
Subject: [PATCH] Try to merge tail with next block when splitting
When splitting a memory block, check if the next block is free.
If it is, then just extend it upwards instead of creating a new block.
This fixes a bug where when shrinking existing allocations would result in irreversible free space fragmentation.
When testing on the host, test all the poisoning configurations.
---
components/heap/multi_heap.c | 75 ++++++++----
components/heap/multi_heap_config.h | 10 +-
components/heap/multi_heap_poisoning.c | 2 +
components/heap/test_multi_heap_host/Makefile | 59 +++-------
.../heap/test_multi_heap_host/Makefile.test | 49 ++++++++
.../test_multi_heap_host/test_multi_heap.cpp | 107 +++++++++++++++++-
6 files changed, 222 insertions(+), 80 deletions(-)
create mode 100644 components/heap/test_multi_heap_host/Makefile.test
diff --git a/components/heap/multi_heap.c b/components/heap/multi_heap.c
index 77dd9d82cc..39917f4af0 100644
--- a/components/heap/multi_heap.c
+++ b/components/heap/multi_heap.c
@@ -131,6 +131,12 @@ static inline bool is_free(const heap_block_t *block)
return block->header & BLOCK_FREE_FLAG;
}
+/* Return true if this block is the first in the heap */
+static inline bool is_first_block(const heap_t *heap, const heap_block_t *block)
+{
+ return (block == &heap->first_block);
+}
+
/* Return true if this block is the last_block in the heap
(the only block with no next pointer) */
static inline bool is_last_block(const heap_block_t *block)
@@ -175,7 +181,7 @@ static void assert_valid_block(const heap_t *heap, const heap_block_t *block)
*/
static heap_block_t *get_prev_free_block(heap_t *heap, const heap_block_t *block)
{
- assert(block != &heap->first_block); /* can't look for a block before first_block */
+ assert(!is_first_block(heap, block)); /* can't look for a block before first_block */
for (heap_block_t *b = &heap->first_block; b != NULL && b < block; b = b->next_free) {
MULTI_HEAP_ASSERT(is_free(b), b); // Block should be free
@@ -206,7 +212,7 @@ static heap_block_t *merge_adjacent(heap_t *heap, heap_block_t *a, heap_block_t
if (is_last_block(b)) {
return a;
}
- if (a == &heap->first_block) {
+ if (is_first_block(heap, a)) {
return b;
}
@@ -258,33 +264,52 @@ static heap_block_t *merge_adjacent(heap_t *heap, heap_block_t *a, heap_block_t
*/
static void split_if_necessary(heap_t *heap, heap_block_t *block, size_t size, heap_block_t *prev_free_block)
{
+ const size_t block_size = block_data_size(block);
MULTI_HEAP_ASSERT(!is_free(block), block); // split block shouldn't be free
- MULTI_HEAP_ASSERT(size <= block_data_size(block), block); // size should be valid
+ MULTI_HEAP_ASSERT(size <= block_size, block); // size should be valid
size = ALIGN_UP(size);
/* can't split the head or tail block */
- assert(block != &heap->first_block);
+ assert(!is_first_block(heap, block));
assert(!is_last_block(block));
- if (block_data_size(block) < size + sizeof(heap_block_t)) {
- /* Can't split 'block' if we're not going to get a usable free block afterwards */
- return;
- }
-
- /* Block is larger than it needs to be, insert a new free block after it */
heap_block_t *new_block = (heap_block_t *)(block->data + size);
- new_block->header = block->header | BLOCK_FREE_FLAG;
- block->header = (intptr_t)new_block;
-
- if (prev_free_block == NULL) {
- prev_free_block = get_prev_free_block(heap, block);
+ heap_block_t *next_block = get_next_block(block);
+
+ if (is_free(next_block) && !is_last_block(next_block)) {
+ /* The next block is free, just extend it upwards. */
+ new_block->header = next_block->header;
+ new_block->next_free = next_block->next_free;
+ if (prev_free_block == NULL) {
+ prev_free_block = get_prev_free_block(heap, block);
+ }
+ /* prev_free_block should point to the next block (which we found to be free). */
+ MULTI_HEAP_ASSERT(prev_free_block->next_free == next_block,
+ &prev_free_block->next_free); // free blocks should be in order
+ /* Note: We have not introduced a new block header, hence the simple math. */
+ heap->free_bytes += block_size - size;
+#ifdef MULTI_HEAP_POISONING_SLOW
+ /* next_block header needs to be replaced with a fill pattern */
+ multi_heap_internal_poison_fill_region(next_block, sizeof(heap_block_t), true /* free */);
+#endif
+ } else {
+ /* Insert a free block between the current and the next one. */
+ if (block_data_size(block) < size + sizeof(heap_block_t)) {
+ /* Can't split 'block' if we're not going to get a usable free block afterwards */
+ return;
+ }
+ if (prev_free_block == NULL) {
+ prev_free_block = get_prev_free_block(heap, block);
+ }
+ new_block->header = block->header | BLOCK_FREE_FLAG;
+ new_block->next_free = prev_free_block->next_free;
+ /* prev_free_block should point to a free block after new_block */
+ MULTI_HEAP_ASSERT(prev_free_block->next_free > new_block,
+ &prev_free_block->next_free); // free blocks should be in order
+ heap->free_bytes += block_data_size(new_block);
}
- /* prev_free_block should point to a free block after new_block */
- MULTI_HEAP_ASSERT(prev_free_block->next_free > new_block,
- &prev_free_block->next_free); // free blocks should be in order
- new_block->next_free = prev_free_block->next_free;
+ block->header = (intptr_t)new_block;
prev_free_block->next_free = new_block;
- heap->free_bytes += block_data_size(new_block);
}
void *multi_heap_get_block_address_impl(multi_heap_block_handle_t block)
@@ -448,7 +473,7 @@ void multi_heap_free_impl(multi_heap_handle_t heap, void *p)
assert_valid_block(heap, pb);
MULTI_HEAP_ASSERT(!is_free(pb), pb); // block should not be free
MULTI_HEAP_ASSERT(!is_last_block(pb), pb); // block should not be last block
- MULTI_HEAP_ASSERT(pb != &heap->first_block, pb); // block should not be first block
+ MULTI_HEAP_ASSERT(!is_first_block(heap, pb), pb); // block should not be first block
heap_block_t *next = get_next_block(pb);
@@ -604,19 +629,21 @@ bool multi_heap_check(multi_heap_handle_t heap, bool print_errors)
FAIL_PRINT("CORRUPT HEAP: Block %p is outside heap (last valid block %p)\n", b, prev);
goto done;
}
- prev = b;
-
if (is_free(b)) {
+ if (prev != NULL && is_free(prev) && !is_first_block(heap, prev) && !is_last_block(b)) {
+ FAIL_PRINT("CORRUPT HEAP: Two adjacent free blocks found, %p and %p\n", prev, b);
+ }
if (expected_free != NULL && expected_free != b) {
FAIL_PRINT("CORRUPT HEAP: Prev free block %p pointed to next free %p but this free block is %p\n",
prev_free, expected_free, b);
}
prev_free = b;
expected_free = b->next_free;
- if (b != &heap->first_block) {
+ if (!is_first_block(heap, b)) {
total_free_bytes += block_data_size(b);
}
}
+ prev = b;
#ifdef MULTI_HEAP_POISONING
if (!is_last_block(b)) {
diff --git a/components/heap/multi_heap_config.h b/components/heap/multi_heap_config.h
index f0873e956f..2759766005 100644
--- a/components/heap/multi_heap_config.h
+++ b/components/heap/multi_heap_config.h
@@ -14,8 +14,8 @@
#pragma once
#ifdef ESP_PLATFORM
-
#include "sdkconfig.h"
+#endif
/* Configuration macros for multi-heap */
@@ -27,11 +27,3 @@
#define MULTI_HEAP_POISONING
#define MULTI_HEAP_POISONING_SLOW
#endif
-
-#else /* !ESP_PLATFORM */
-
-/* Host-side tests, enable full poisoning */
-#define MULTI_HEAP_POISONING
-#define MULTI_HEAP_POISONING_SLOW
-
-#endif
diff --git a/components/heap/multi_heap_poisoning.c b/components/heap/multi_heap_poisoning.c
index 2405982220..1fdf586aa3 100644
--- a/components/heap/multi_heap_poisoning.c
+++ b/components/heap/multi_heap_poisoning.c
@@ -244,6 +244,8 @@ void *multi_heap_realloc(multi_heap_handle_t heap, void *p, size_t size)
place.)
For now we just malloc a new buffer, copy, and free. :|
+
+ Note: If this ever changes, multi_heap defrag realloc test should be enabled.
*/
size_t orig_alloc_size = head->alloc_size;
diff --git a/components/heap/test_multi_heap_host/Makefile b/components/heap/test_multi_heap_host/Makefile
index f0d5ab1fc1..9c9c09a5c7 100644
--- a/components/heap/test_multi_heap_host/Makefile
+++ b/components/heap/test_multi_heap_host/Makefile
@@ -1,49 +1,18 @@
-TEST_PROGRAM=test_multi_heap
-all: $(TEST_PROGRAM)
+test: test_poisoning_disabled \
+ test_poisoning_light \
+ test_poisoning_comprehensive
-SOURCE_FILES = $(abspath \
- ../multi_heap.c \
- ../multi_heap_poisoning.c \
- test_multi_heap.cpp \
- main.cpp \
- )
+test_poisoning_disabled:
+ @echo ==== HEAP_POISONING_DISABLED ====
+ CPPFLAGS= $(MAKE) -f Makefile.test clean test
-INCLUDE_FLAGS = -I../include -I../../../tools/catch
+test_poisoning_light:
+ @echo ==== HEAP_POISONING_LIGHT ====
+ CPPFLAGS=-DCONFIG_HEAP_POISONING_LIGHT $(MAKE) -f Makefile.test clean test
-GCOV ?= gcov
+test_poisoning_comprehensive:
+ @echo ==== HEAP_POISONING_COMPREHENSIVE ====
+ CPPFLAGS=-DCONFIG_HEAP_POISONING_COMPREHENSIVE $(MAKE) -f Makefile.test clean test
-CPPFLAGS += $(INCLUDE_FLAGS) -D CONFIG_LOG_DEFAULT_LEVEL -g -fstack-protector-all -m32
-CFLAGS += -Wall -Werror -fprofile-arcs -ftest-coverage
-CXXFLAGS += -std=c++11 -Wall -Werror -fprofile-arcs -ftest-coverage
-LDFLAGS += -lstdc++ -fprofile-arcs -ftest-coverage -m32
-
-OBJ_FILES = $(filter %.o, $(SOURCE_FILES:.cpp=.o) $(SOURCE_FILES:.c=.o))
-
-COVERAGE_FILES = $(OBJ_FILES:.o=.gc*)
-
-$(TEST_PROGRAM): $(OBJ_FILES)
- g++ $(LDFLAGS) -o $(TEST_PROGRAM) $(OBJ_FILES)
-
-$(OUTPUT_DIR):
- mkdir -p $(OUTPUT_DIR)
-
-test: $(TEST_PROGRAM)
- ./$(TEST_PROGRAM)
-
-$(COVERAGE_FILES): $(TEST_PROGRAM) test
-
-coverage.info: $(COVERAGE_FILES)
- find ../ -name "*.gcno" -exec $(GCOV) -r -pb {} +
- lcov --capture --directory $(abspath ../) --no-external --output-file coverage.info --gcov-tool $(GCOV)
-
-coverage_report: coverage.info
- genhtml coverage.info --output-directory coverage_report
- @echo "Coverage report is in coverage_report/index.html"
-
-clean:
- rm -f $(OBJ_FILES) $(TEST_PROGRAM)
- rm -f $(COVERAGE_FILES) *.gcov
- rm -rf coverage_report/
- rm -f coverage.info
-
-.PHONY: clean all test
+%:
+ CPPFLAGS=-DCONFIG_HEAP_POISONING_COMPREHENSIVE $(MAKE) -f Makefile.test $@
diff --git a/components/heap/test_multi_heap_host/Makefile.test b/components/heap/test_multi_heap_host/Makefile.test
new file mode 100644
index 0000000000..f0d5ab1fc1
--- /dev/null
+++ b/components/heap/test_multi_heap_host/Makefile.test
@@ -0,0 +1,49 @@
+TEST_PROGRAM=test_multi_heap
+all: $(TEST_PROGRAM)
+
+SOURCE_FILES = $(abspath \
+ ../multi_heap.c \
+ ../multi_heap_poisoning.c \
+ test_multi_heap.cpp \
+ main.cpp \
+ )
+
+INCLUDE_FLAGS = -I../include -I../../../tools/catch
+
+GCOV ?= gcov
+
+CPPFLAGS += $(INCLUDE_FLAGS) -D CONFIG_LOG_DEFAULT_LEVEL -g -fstack-protector-all -m32
+CFLAGS += -Wall -Werror -fprofile-arcs -ftest-coverage
+CXXFLAGS += -std=c++11 -Wall -Werror -fprofile-arcs -ftest-coverage
+LDFLAGS += -lstdc++ -fprofile-arcs -ftest-coverage -m32
+
+OBJ_FILES = $(filter %.o, $(SOURCE_FILES:.cpp=.o) $(SOURCE_FILES:.c=.o))
+
+COVERAGE_FILES = $(OBJ_FILES:.o=.gc*)
+
+$(TEST_PROGRAM): $(OBJ_FILES)
+ g++ $(LDFLAGS) -o $(TEST_PROGRAM) $(OBJ_FILES)
+
+$(OUTPUT_DIR):
+ mkdir -p $(OUTPUT_DIR)
+
+test: $(TEST_PROGRAM)
+ ./$(TEST_PROGRAM)
+
+$(COVERAGE_FILES): $(TEST_PROGRAM) test
+
+coverage.info: $(COVERAGE_FILES)
+ find ../ -name "*.gcno" -exec $(GCOV) -r -pb {} +
+ lcov --capture --directory $(abspath ../) --no-external --output-file coverage.info --gcov-tool $(GCOV)
+
+coverage_report: coverage.info
+ genhtml coverage.info --output-directory coverage_report
+ @echo "Coverage report is in coverage_report/index.html"
+
+clean:
+ rm -f $(OBJ_FILES) $(TEST_PROGRAM)
+ rm -f $(COVERAGE_FILES) *.gcov
+ rm -rf coverage_report/
+ rm -f coverage.info
+
+.PHONY: clean all test
diff --git a/components/heap/test_multi_heap_host/test_multi_heap.cpp b/components/heap/test_multi_heap_host/test_multi_heap.cpp
index def9accf41..133f12536b 100644
--- a/components/heap/test_multi_heap_host/test_multi_heap.cpp
+++ b/components/heap/test_multi_heap_host/test_multi_heap.cpp
@@ -76,7 +76,7 @@ TEST_CASE("multi_heap fragmentation", "[multi_heap]")
printf("allocated %p %p %p %p\n", p[0], p[1], p[2], p[3]);
- REQUIRE( multi_heap_malloc(heap, alloc_size * 3) == NULL ); /* no room to allocate 3*alloc_size now */
+ REQUIRE( multi_heap_malloc(heap, alloc_size * 5) == NULL ); /* no room to allocate 5*alloc_size now */
printf("4 allocations:\n");
multi_heap_dump(heap);
@@ -105,6 +105,103 @@ TEST_CASE("multi_heap fragmentation", "[multi_heap]")
multi_heap_free(heap, big);
}
+/* Test that malloc/free does not leave free space fragmented */
+TEST_CASE("multi_heap defrag", "[multi_heap]")
+{
+ void *p[4];
+ uint8_t small_heap[512];
+ multi_heap_info_t info, info2;
+ multi_heap_handle_t heap = multi_heap_register(small_heap, sizeof(small_heap));
+
+ printf("0 ---\n");
+ multi_heap_dump(heap);
+ REQUIRE( multi_heap_check(heap, true) );
+ multi_heap_get_info(heap, &info);
+ REQUIRE( 0 == info.allocated_blocks );
+ REQUIRE( 1 == info.free_blocks );
+
+ printf("1 ---\n");
+ p[0] = multi_heap_malloc(heap, 128);
+ p[1] = multi_heap_malloc(heap, 32);
+ multi_heap_dump(heap);
+ REQUIRE( multi_heap_check(heap, true) );
+
+ printf("2 ---\n");
+ multi_heap_free(heap, p[0]);
+ p[2] = multi_heap_malloc(heap, 64);
+ multi_heap_dump(heap);
+ REQUIRE( p[2] == p[0] );
+ REQUIRE( multi_heap_check(heap, true) );
+
+ printf("3 ---\n");
+ multi_heap_free(heap, p[2]);
+ p[3] = multi_heap_malloc(heap, 32);
+ multi_heap_dump(heap);
+ REQUIRE( p[3] == p[0] );
+ REQUIRE( multi_heap_check(heap, true) );
+
+ multi_heap_get_info(heap, &info2);
+ REQUIRE( 2 == info2.allocated_blocks );
+ REQUIRE( 2 == info2.free_blocks );
+
+ multi_heap_free(heap, p[0]);
+ multi_heap_free(heap, p[1]);
+ multi_heap_get_info(heap, &info2);
+ REQUIRE( 0 == info2.allocated_blocks );
+ REQUIRE( 1 == info2.free_blocks );
+ REQUIRE( info.total_free_bytes == info2.total_free_bytes );
+}
+
+/* Test that malloc/free does not leave free space fragmented
+ Note: With fancy poisoning, realloc is implemented as malloc-copy-free and this test does not apply.
+ */
+#ifndef MULTI_HEAP_POISONING_SLOW
+TEST_CASE("multi_heap defrag realloc", "[multi_heap]")
+{
+ void *p[4];
+ uint8_t small_heap[512];
+ multi_heap_info_t info, info2;
+ multi_heap_handle_t heap = multi_heap_register(small_heap, sizeof(small_heap));
+
+ printf("0 ---\n");
+ multi_heap_dump(heap);
+ REQUIRE( multi_heap_check(heap, true) );
+ multi_heap_get_info(heap, &info);
+ REQUIRE( 0 == info.allocated_blocks );
+ REQUIRE( 1 == info.free_blocks );
+
+ printf("1 ---\n");
+ p[0] = multi_heap_malloc(heap, 128);
+ p[1] = multi_heap_malloc(heap, 32);
+ multi_heap_dump(heap);
+ REQUIRE( multi_heap_check(heap, true) );
+
+ printf("2 ---\n");
+ p[2] = multi_heap_realloc(heap, p[0], 64);
+ multi_heap_dump(heap);
+ REQUIRE( p[2] == p[0] );
+ REQUIRE( multi_heap_check(heap, true) );
+
+ printf("3 ---\n");
+ p[3] = multi_heap_realloc(heap, p[2], 32);
+ multi_heap_dump(heap);
+ REQUIRE( p[3] == p[0] );
+ REQUIRE( multi_heap_check(heap, true) );
+
+ multi_heap_get_info(heap, &info2);
+ REQUIRE( 2 == info2.allocated_blocks );
+ REQUIRE( 2 == info2.free_blocks );
+
+ multi_heap_free(heap, p[0]);
+ multi_heap_free(heap, p[1]);
+ multi_heap_get_info(heap, &info2);
+ REQUIRE( 0 == info2.allocated_blocks );
+ REQUIRE( 1 == info2.free_blocks );
+ REQUIRE( info.total_free_bytes == info2.total_free_bytes );
+}
+#endif
+
+
TEST_CASE("multi_heap many random allocations", "[multi_heap]")
{
uint8_t big_heap[1024];
@@ -329,7 +426,13 @@ TEST_CASE("multi_heap_realloc()", "[multi_heap]")
REQUIRE( multi_heap_check(heap, true) );
REQUIRE( f == b ); /* 'b' should be extended in-place, over space formerly occupied by 'd' */
- uint32_t *g = (uint32_t *)multi_heap_realloc(heap, e, 128); /* not enough contiguous space left in the heap */
+#ifdef MULTI_HEAP_POISONING
+#define TOO_MUCH 92 + 1
+#else
+#define TOO_MUCH 128 + 1
+#endif
+ /* not enough contiguous space left in the heap */
+ uint32_t *g = (uint32_t *)multi_heap_realloc(heap, e, TOO_MUCH);
REQUIRE( g == NULL );
multi_heap_free(heap, f);
--
2.40.0