[inspect] Fix bug in VMO Heap
We were not properly checking that merging is possible between a block
and its buddy. When two blocks of order n are merged into order n+1, we
check the buddy of the new block for continued merging. We, however,
need to make sure to check that the new buddy is of the right order
before merging.
This caused subtle errors when the ordering of Free operations was such
that a block gets merged but what would be its new buddy is split to
blocks of order < n+1.
TEST=runtests -t inspect-test
Change-Id: Ic4180b900635ede1701af1170cf12e30c2e80b1b
diff --git a/system/ulib/inspect/heap.cpp b/system/ulib/inspect/heap.cpp
index d7affeb..118adc5 100644
--- a/system/ulib/inspect/heap.cpp
+++ b/system/ulib/inspect/heap.cpp
@@ -97,7 +97,8 @@
// Repeatedly merge buddies of the freed block until the buddy is
// not free or we hit the maximum block size.
- while (GetType(buddy) == BlockType::kFree && GetOrder(block) < kNumOrders - 1) {
+ while (GetType(buddy) == BlockType::kFree && GetOrder(block) < kNumOrders - 1 &&
+ GetOrder(block) == GetOrder(buddy)) {
RemoveFree(buddy_index);
if (buddy < block) {
// We must always merge into the lower index block.
diff --git a/system/ulib/inspect/test/heap_tests.cpp b/system/ulib/inspect/test/heap_tests.cpp
index 59f4bab..0360279 100644
--- a/system/ulib/inspect/test/heap_tests.cpp
+++ b/system/ulib/inspect/test/heap_tests.cpp
@@ -182,6 +182,52 @@
END_TEST;
}
+bool MergeBlockedByAllocation() {
+ BEGIN_TEST;
+
+ auto vmo = fzl::ResizeableVmoMapper::Create(4096, "test");
+ ASSERT_NE(nullptr, vmo.get());
+ Heap heap(std::move(vmo));
+
+ // Allocate 4 small blocks at the beginning of the buffer.
+ BlockIndex b;
+ EXPECT_EQ(ZX_OK, heap.Allocate(kMinAllocationSize, &b));
+ EXPECT_EQ(0, b);
+ EXPECT_EQ(ZX_OK, heap.Allocate(kMinAllocationSize, &b));
+ EXPECT_EQ(1, b);
+ EXPECT_EQ(ZX_OK, heap.Allocate(kMinAllocationSize, &b));
+ EXPECT_EQ(2, b);
+ EXPECT_EQ(ZX_OK, heap.Allocate(kMinAllocationSize, &b));
+ EXPECT_EQ(3, b);
+
+ // Free position 2 first, then 0 and 1.
+ // The final free sees a situation like:
+ // FREE | FREE | FREE | RESERVED
+ // The first two spaces will get merged into an order 1 block, but the
+ // reserved space will prevent merging into an order 2 block.
+ heap.Free(2);
+ heap.Free(0);
+ heap.Free(1);
+
+ EXPECT_TRUE(MatchDebugBlockVectors({{0, BlockType::kFree, 1},
+ {2, BlockType::kFree, 0},
+ {3, BlockType::kReserved, 0},
+ {4, BlockType::kFree, 2},
+ {8, BlockType::kFree, 3},
+ {16, BlockType::kFree, 4},
+ {32, BlockType::kFree, 5},
+ {64, BlockType::kFree, 6},
+ {128, BlockType::kFree, 7}},
+ dump(heap)));
+
+ heap.Free(3);
+
+ EXPECT_TRUE(
+ MatchDebugBlockVectors({{0, BlockType::kFree, 7}, {128, BlockType::kFree, 7}}, dump(heap)));
+
+ END_TEST;
+}
+
bool Extend() {
BEGIN_TEST;
@@ -274,6 +320,7 @@
BEGIN_TEST_CASE(HeapTests)
RUN_TEST(Create)
RUN_TEST(Allocate)
+RUN_TEST(MergeBlockedByAllocation)
RUN_TEST(Extend)
RUN_TEST(ExtendFailure)
END_TEST_CASE(HeapTests)
