kernel/lib/fbl/arena_tests.cpp - zircon - Git at Google

 // Copyright 2016 The Fuchsia Authors
 //
 // Use of this source code is governed by a MIT-style
 // license that can be found in the LICENSE file or at
 // https://opensource.org/licenses/MIT

 #include <fbl/arena.h>

 #include <fbl/alloc_checker.h>
 #include <lib/unittest/unittest.h>
 #include <vm/vm_aspace.h>

 using fbl::Arena;

 struct TestObj {
     int xx, yy, zz;
 };

 static bool init_null_name_succeeds() {
     BEGIN_TEST;
     Arena arena;
     EXPECT_EQ(ZX_OK, arena.Init(nullptr, sizeof(TestObj), 16), "");
     END_TEST;
 }

 static bool init_zero_ob_size_fails() {
     BEGIN_TEST;
     Arena arena;
     EXPECT_EQ(ZX_ERR_INVALID_ARGS, arena.Init("name", 0, 16), "");
     END_TEST;
 }

 static bool init_large_ob_size_fails() {
     BEGIN_TEST;
     Arena arena;
     EXPECT_EQ(ZX_ERR_INVALID_ARGS, arena.Init("name", PAGE_SIZE + 1, 16), "");
     END_TEST;
 }

 static bool init_zero_count_fails() {
     BEGIN_TEST;
     Arena arena;
     EXPECT_EQ(ZX_ERR_INVALID_ARGS, arena.Init("name", sizeof(TestObj), 0), "");
     END_TEST;
 }

 static bool start_and_end_look_good() {
     BEGIN_TEST;
     static const size_t num_slots = (2 * PAGE_SIZE) / sizeof(TestObj);
     static const size_t expected_size = num_slots * sizeof(TestObj);

     Arena arena;
     EXPECT_EQ(ZX_OK, arena.Init("name", sizeof(TestObj), num_slots), "");

     EXPECT_NONNULL(arena.start(), "");
     EXPECT_NONNULL(arena.end(), "");
     auto start = reinterpret_cast<vaddr_t>(arena.start());
     auto end = reinterpret_cast<vaddr_t>(arena.end());
     EXPECT_LT(start, end, "");
     EXPECT_GE(end - start, expected_size, "");
     END_TEST;
 }

 static bool in_range_tests() {
     BEGIN_TEST;
     static const size_t num_slots = (2 * PAGE_SIZE) / sizeof(TestObj);

     Arena arena;
     EXPECT_EQ(ZX_OK, arena.Init("name", sizeof(TestObj), num_slots), "");

     auto start = reinterpret_cast<char*>(arena.start());

     // Nothing is allocated yet, so not even the start address
     // should be in range.
     EXPECT_FALSE(arena.in_range(start), "");

     // Allocate some objects, and check that each is within range.
     static const int nobjs = 16;
     void* objs[nobjs];
     for (int i = 0; i < nobjs; i++) {
         char msg[32];
         snprintf(msg, sizeof(msg), "[%d]", i);
         objs[i] = arena.Alloc();
         EXPECT_NONNULL(objs[i], msg);
         // The allocated object should be in range.
         EXPECT_TRUE(arena.in_range(objs[i]), msg);
         // The slot just after this object should not be in range.
         // FRAGILE: assumes that objects are allocated in increasing order.
         EXPECT_FALSE(
             arena.in_range(reinterpret_cast<TestObj*>(objs[i]) + 1), msg);
         // The count should correspond to the number of times we have
         // allocated.
         EXPECT_EQ(static_cast<size_t>(i + 1), arena.DiagnosticCount(), msg);
     }

     // Deallocate the objects and check whether they're in range.
     for (int i = nobjs - 1; i >= 0; i--) {
         char msg[32];
         snprintf(msg, sizeof(msg), "[%d]", i);
         // The object should still be in range.
         EXPECT_TRUE(arena.in_range(objs[i]), msg);

         arena.Free(objs[i]);

         // The free slot will still be in range.
         // NOTE: If Arena ever learns to coalesce and decommit whole pages of
         // free objects, this test will need to change.
         EXPECT_TRUE(arena.in_range(objs[i]), msg);

         // The count should correspond to the number of times we have
         // deallocated.
         EXPECT_EQ(static_cast<size_t>(i), arena.DiagnosticCount(), msg);
     }
     END_TEST;
 }

 static bool out_of_memory() {
     BEGIN_TEST;
     static const size_t num_slots = (2 * PAGE_SIZE) / sizeof(TestObj);

     Arena arena;
     EXPECT_EQ(ZX_OK, arena.Init("name", sizeof(TestObj), num_slots), "");

     // Allocate all of the data objects.
     fbl::AllocChecker ac;
     fbl::unique_ptr<void*[]> objs = fbl::unique_ptr<void*[]>(new (&ac) void*[num_slots]);
     EXPECT_TRUE(ac.check(), "");
     void** top = &objs[0];
     for (size_t i = 0; i < num_slots; i++) {
         char msg[32];
         snprintf(msg, sizeof(msg), "[%zu]", i);
         *top++ = arena.Alloc();
         EXPECT_NONNULL(top[-1], msg);
     }

     // Any further allocations should return nullptr.
     EXPECT_NULL(arena.Alloc(), "");
     EXPECT_NULL(arena.Alloc(), "");
     EXPECT_NULL(arena.Alloc(), "");
     EXPECT_NULL(arena.Alloc(), "");

     // Free two objects.
     arena.Free(*--top);
     arena.Free(*--top);

     // Two allocations should succeed; any further should fail.
     *top++ = arena.Alloc();
     EXPECT_NONNULL(top[-1], "");
     *top++ = arena.Alloc();
     EXPECT_NONNULL(top[-1], "");
     EXPECT_NULL(arena.Alloc(), "");
     EXPECT_NULL(arena.Alloc(), "");

     // Free all objects.
     // Nothing much to check except that it doesn't crash.
     while (top > objs.get()) {
         arena.Free(*--top);
     }

     END_TEST;
 }

 // Test helper. Counts the number of committed and uncommitted pages in the
 // range. Returns {*committed, *uncommitted} = {0, 0} if |start| doesn't
 // correspond to a live VmMapping.
 static bool count_committed_pages(
     vaddr_t start, vaddr_t end, size_t* committed, size_t* uncommitted) {
     BEGIN_TEST; // Not a test, but we need these guards to use ASSERT_*
     *committed = 0;
     *uncommitted = 0;

     // Find the VmMapping that covers |start|. Assume that it covers |end-1|.
     const auto region = VmAspace::kernel_aspace()->FindRegion(start);
     ASSERT_NONNULL(region, "FindRegion");
     const auto mapping = region->as_vm_mapping();
     if (mapping == nullptr) {
         // It's a VMAR, not a mapping, so no pages are committed.
         // Return 0/0.
         return true;
     }

     // Ask the VMO how many pages it's allocated within the range.
     auto start_off = ROUNDDOWN(start, PAGE_SIZE) - mapping->base();
     auto end_off = ROUNDUP(end, PAGE_SIZE) - mapping->base();
     *committed = mapping->vmo()->AllocatedPagesInRange(
         start_off + mapping->object_offset(), end_off - start_off);
     *uncommitted = (end_off - start_off) / PAGE_SIZE - *committed;
     END_TEST;
 }

 static bool committing_tests() {
     BEGIN_TEST;
     static const size_t num_slots = (64 * PAGE_SIZE) / sizeof(TestObj);

     Arena arena;
     EXPECT_EQ(ZX_OK, arena.Init("name", sizeof(TestObj), num_slots), "");

     auto start = reinterpret_cast<vaddr_t>(arena.start());
     auto end = reinterpret_cast<vaddr_t>(arena.end());

     // Nothing is allocated yet, so no pages should be committed.
     size_t committed;
     size_t uncommitted;
     EXPECT_TRUE(
         count_committed_pages(start, end, &committed, &uncommitted), "");
     EXPECT_EQ(0u, committed, "");
     EXPECT_GT(uncommitted, 0u, "");

     // Allocate an object.
     auto obj = reinterpret_cast<vaddr_t>(arena.Alloc());
     EXPECT_NE(0u, obj, "");
     size_t atotal = sizeof(TestObj);

     // The page containing the object should be committed.
     auto ps = ROUNDDOWN(obj, PAGE_SIZE);
     auto pe = ROUNDUP(obj + sizeof(TestObj), PAGE_SIZE);
     EXPECT_TRUE(count_committed_pages(ps, pe, &committed, &uncommitted), "");
     EXPECT_GT(committed, 0u, "");
     EXPECT_EQ(0u, uncommitted, "");

     // The first handful of pages should also become committed, but the rest
     // should stay ucommitted.
     EXPECT_TRUE(
         count_committed_pages(start, end, &committed, &uncommitted), "");
     EXPECT_GT(committed, 0u, "");
     EXPECT_GT(uncommitted, 0u, "");

     // Fill the committed pages with objects; the set of committed pages
     // shouldn't change.
     auto orig_committed = committed;
     auto orig_uncommitted = uncommitted;
     while (atotal + sizeof(TestObj) <= orig_committed * PAGE_SIZE) {
         EXPECT_NONNULL(arena.Alloc(), "");
         atotal += sizeof(TestObj);
     }
     EXPECT_TRUE(
         count_committed_pages(start, end, &committed, &uncommitted), "");
     EXPECT_EQ(orig_committed, committed, "");
     EXPECT_EQ(orig_uncommitted, uncommitted, "");

     // Allocating one more object should cause more pages to be committed.
     EXPECT_NONNULL(arena.Alloc(), "");
     atotal += sizeof(TestObj);
     EXPECT_TRUE(
         count_committed_pages(start, end, &committed, &uncommitted), "");
     EXPECT_LT(orig_committed, committed, "");
     EXPECT_GT(orig_uncommitted, uncommitted, "");

     // TODO(dbort): Test uncommitting if Arena ever learns to decommit pages.
     END_TEST;
 }

 // Friend class that can see inside an Arena.
 namespace fbl {
 class ArenaTestFriend {
 public:
     ArenaTestFriend(const Arena& arena)
         : arena_(arena) {}

     constexpr static size_t control_slot_size() {
         return sizeof(Arena::Node);
     }

     vaddr_t control_start() const {
         return reinterpret_cast<vaddr_t>(arena_.control_.start());
     }

     vaddr_t control_end() const {
         return reinterpret_cast<vaddr_t>(arena_.control_.end());
     }

 private:
     const Arena& arena_;
 };
 } // namespace fbl
 using fbl::ArenaTestFriend;

 // Hit the decommit code path. We can't observe it without peeking inside the
 // control pool, since the data pool doesn't currently decommit.
 static bool uncommitting_tests() {
     BEGIN_TEST;
     // Create an arena with a 16-page control pool.
     static const size_t num_pages = 16;
     static const size_t num_slots =
         (num_pages * PAGE_SIZE) / ArenaTestFriend::control_slot_size();

     Arena arena;
     // Use a small data slot size (1) to keep our memory usage down.
     EXPECT_EQ(ZX_OK, arena.Init("name", 1, num_slots), "");

     // Get the extent of the control pool.
     vaddr_t start;
     vaddr_t end;
     {
         ArenaTestFriend atf(arena);
         start = reinterpret_cast<vaddr_t>(atf.control_start());
         end = reinterpret_cast<vaddr_t>(atf.control_end());
     }

     // Nothing is allocated yet, so no control pages should be committed.
     size_t committed;
     size_t uncommitted;
     EXPECT_TRUE(
         count_committed_pages(start, end, &committed, &uncommitted), "");
     EXPECT_EQ(num_pages, committed + uncommitted, "");
     EXPECT_EQ(0u, committed, "");
     EXPECT_GT(uncommitted, 0u, "");

     // Allocate all of the data objects. Hold onto the pointers so we can free
     // them.
     fbl::AllocChecker ac;
     fbl::unique_ptr<void*[]> objs = fbl::unique_ptr<void*[]>(new (&ac) void*[num_slots]);
     EXPECT_TRUE(ac.check(), "");
     void** top = &objs[0];
     for (size_t i = 0; i < num_slots; i++) {
         char msg[32];
         snprintf(msg, sizeof(msg), "[%zu]", i);
         *top++ = arena.Alloc();
         EXPECT_NONNULL(top[-1], msg);
     }

     // We still shouldn't see any control pages committed, becase no objects
     // have been freed yet.
     EXPECT_TRUE(
         count_committed_pages(start, end, &committed, &uncommitted), "");
     EXPECT_EQ(num_pages, committed + uncommitted, "");
     EXPECT_EQ(0u, committed, "");
     EXPECT_GT(uncommitted, 0u, "");

     // Demonstrate that we've allocated all of the data objects.
     void* no = arena.Alloc();
     EXPECT_NULL(no, "");

     // Free a data object.
     arena.Free(*--top);

     // We should now see some committed pages inside the control pool.
     EXPECT_TRUE(
         count_committed_pages(start, end, &committed, &uncommitted), "");
     EXPECT_EQ(num_pages, committed + uncommitted, "");
     EXPECT_GT(committed, 0u, "");
     EXPECT_GT(uncommitted, 0u, "");

     // Free all of the data objects.
     while (top > objs.get()) {
         arena.Free(*--top);
     }

     // All of the control pages should be committed.
     EXPECT_TRUE(
         count_committed_pages(start, end, &committed, &uncommitted), "");
     EXPECT_EQ(num_pages, committed + uncommitted, "");
     EXPECT_EQ(committed, num_pages, "");
     EXPECT_EQ(uncommitted, 0u, "");

     // Allocate half of the data objects, freeing up half of the free nodes
     // (and thus half of the control slots).
     auto orig_committed = committed;
     ASSERT_EQ(top, objs.get(), "");
     for (size_t i = 0; i < num_slots / 2; i++) {
         char msg[32];
         snprintf(msg, sizeof(msg), "[%zu]", i);
         *top++ = arena.Alloc();
         EXPECT_NONNULL(top[-1], msg);
     }

     // The number of committed pages should have dropped.
     EXPECT_TRUE(
         count_committed_pages(start, end, &committed, &uncommitted), "");
     EXPECT_EQ(num_pages, committed + uncommitted, "");
     EXPECT_LT(committed, orig_committed, "");
     EXPECT_GT(uncommitted, 0u, "");

     // Free more control slots (by allocating data objects) until we see more
     // unmapping happen.
     orig_committed = committed;
     for (size_t i = num_slots / 2; i < num_slots; i++) {
         char msg[32];
         snprintf(msg, sizeof(msg), "[%zu]", i);
         *top++ = arena.Alloc();
         EXPECT_NONNULL(top[-1], msg);

         EXPECT_TRUE(
             count_committed_pages(start, end, &committed, &uncommitted), "");
         if (committed != orig_committed) {
             break;
         }
     }
     EXPECT_GT(orig_committed, committed, "");

     // Allocating one more control slot (by freeing a data object) should not
     // cause the number of committed pages to change: there should be some
     // hysteresis built into the system to avoid flickering back and forth.
     orig_committed = committed;
     arena.Free(*--top);
     EXPECT_TRUE(
         count_committed_pages(start, end, &committed, &uncommitted), "");
     EXPECT_EQ(num_pages, committed + uncommitted, "");
     EXPECT_EQ(committed, orig_committed, "");
     EXPECT_GT(uncommitted, 0u, "");

     // Same for freeing a couple more control slots (by allocating more data
     // objects).
     *top++ = arena.Alloc();
     *top++ = arena.Alloc();
     EXPECT_TRUE(
         count_committed_pages(start, end, &committed, &uncommitted), "");
     EXPECT_EQ(num_pages, committed + uncommitted, "");
     EXPECT_EQ(committed, orig_committed, "");
     EXPECT_GT(uncommitted, 0u, "");

     END_TEST;
 }

 // Checks that destroying an arena unmaps all of its pages.
 static bool memory_cleanup() {
     BEGIN_TEST;
     static const size_t num_slots = (16 * PAGE_SIZE) / sizeof(TestObj);

     fbl::AllocChecker ac;
     Arena* arena = new (&ac) Arena();
     EXPECT_TRUE(ac.check(), "");
     EXPECT_EQ(ZX_OK, arena->Init("name", sizeof(TestObj), num_slots), "");

     auto start = reinterpret_cast<vaddr_t>(arena->start());
     auto end = reinterpret_cast<vaddr_t>(arena->end());

     // Allocate and leak a bunch of objects.
     for (size_t i = 0; i < num_slots; i++) {
         char msg[32];
         snprintf(msg, sizeof(msg), "[%zu]", i);
         EXPECT_NONNULL(arena->Alloc(), msg);
     }

     // Should see some committed pages.
     size_t committed;
     size_t uncommitted;
     EXPECT_TRUE(
         count_committed_pages(start, end, &committed, &uncommitted), "");
     EXPECT_GT(committed, 0u, "");

     // Destroying the Arena should destroy the underlying VmMapping,
     // along with all of its pages.
     delete arena;
     EXPECT_TRUE(
         count_committed_pages(start, end, &committed, &uncommitted), "");
     // 0/0 means "no mapping at this address".
     // FLAKY: Another thread could could come in and allocate a mapping at the
     // old location.
     EXPECT_EQ(committed, 0u, "");
     EXPECT_EQ(uncommitted, 0u, "");
     END_TEST;
 }

 // Basic checks that the contents of allocated objects stick around, aren't
 // stomped on.
 static bool content_preservation() {
     BEGIN_TEST;
     Arena arena;
     zx_status_t s = arena.Init("arena_tests", sizeof(TestObj), 1000);
     ASSERT_EQ(ZX_OK, s, "arena.Init()");

     const int count = 30;

     for (int times = 0; times != 5; ++times) {
         TestObj* afp[count] = {0};

         for (int ix = 0; ix != count; ++ix) {
             afp[ix] = reinterpret_cast<TestObj*>(arena.Alloc());
             ASSERT_NONNULL(afp[ix], "arena.Alloc()");
             *afp[ix] = {17, 5, ix + 100};
         }

         arena.Free(afp[3]);
         arena.Free(afp[4]);
         arena.Free(afp[5]);
         afp[3] = afp[4] = afp[5] = nullptr;

         afp[4] = reinterpret_cast<TestObj*>(arena.Alloc());
         ASSERT_NONNULL(afp[4], "arena.Alloc()");
         *afp[4] = {17, 5, 104};

         for (int ix = 0; ix != count; ++ix) {
             if (!afp[ix])
                 continue;

             EXPECT_EQ(17, afp[ix]->xx, "");
             EXPECT_EQ(5, afp[ix]->yy, "");
             EXPECT_EQ(ix + 100, afp[ix]->zz, "");

             arena.Free(afp[ix]);
         }

         // Leak a few objects.
         for (int ix = 0; ix != 7; ++ix) {
             TestObj* leak = reinterpret_cast<TestObj*>(arena.Alloc());
             ASSERT_NONNULL(leak, "arena.Alloc()");
             *leak = {2121, 77, 55};
         }
     }
     END_TEST;
 }

 #define ARENA_UNITTEST(fname) UNITTEST(#fname, fname)

 UNITTEST_START_TESTCASE(arena_tests)
 ARENA_UNITTEST(init_null_name_succeeds)
 ARENA_UNITTEST(init_zero_ob_size_fails)
 ARENA_UNITTEST(init_large_ob_size_fails)
 ARENA_UNITTEST(init_zero_count_fails)
 ARENA_UNITTEST(start_and_end_look_good)
 ARENA_UNITTEST(in_range_tests)
 ARENA_UNITTEST(out_of_memory)
 ARENA_UNITTEST(committing_tests)
 ARENA_UNITTEST(uncommitting_tests)
 ARENA_UNITTEST(memory_cleanup)
 ARENA_UNITTEST(content_preservation)
 UNITTEST_END_TESTCASE(arena_tests, "arenatests", "Arena allocator test");
	// Copyright 2016 The Fuchsia Authors
	//
	// Use of this source code is governed by a MIT-style
	// license that can be found in the LICENSE file or at
	// https://opensource.org/licenses/MIT

	#include <fbl/arena.h>

	#include <fbl/alloc_checker.h>
	#include <lib/unittest/unittest.h>
	#include <vm/vm_aspace.h>

	using fbl::Arena;

	struct TestObj {
	int xx, yy, zz;
	};

	static bool init_null_name_succeeds() {
	BEGIN_TEST;
	Arena arena;
	EXPECT_EQ(ZX_OK, arena.Init(nullptr, sizeof(TestObj), 16), "");
	END_TEST;
	}

	static bool init_zero_ob_size_fails() {
	BEGIN_TEST;
	Arena arena;
	EXPECT_EQ(ZX_ERR_INVALID_ARGS, arena.Init("name", 0, 16), "");
	END_TEST;
	}

	static bool init_large_ob_size_fails() {
	BEGIN_TEST;
	Arena arena;
	EXPECT_EQ(ZX_ERR_INVALID_ARGS, arena.Init("name", PAGE_SIZE + 1, 16), "");
	END_TEST;
	}

	static bool init_zero_count_fails() {
	BEGIN_TEST;
	Arena arena;
	EXPECT_EQ(ZX_ERR_INVALID_ARGS, arena.Init("name", sizeof(TestObj), 0), "");
	END_TEST;
	}

	static bool start_and_end_look_good() {
	BEGIN_TEST;
	static const size_t num_slots = (2 * PAGE_SIZE) / sizeof(TestObj);
	static const size_t expected_size = num_slots * sizeof(TestObj);

	Arena arena;
	EXPECT_EQ(ZX_OK, arena.Init("name", sizeof(TestObj), num_slots), "");

	EXPECT_NONNULL(arena.start(), "");
	EXPECT_NONNULL(arena.end(), "");
	auto start = reinterpret_cast<vaddr_t>(arena.start());
	auto end = reinterpret_cast<vaddr_t>(arena.end());
	EXPECT_LT(start, end, "");
	EXPECT_GE(end - start, expected_size, "");
	END_TEST;
	}

	static bool in_range_tests() {
	BEGIN_TEST;
	static const size_t num_slots = (2 * PAGE_SIZE) / sizeof(TestObj);

	Arena arena;
	EXPECT_EQ(ZX_OK, arena.Init("name", sizeof(TestObj), num_slots), "");

	auto start = reinterpret_cast<char*>(arena.start());

	// Nothing is allocated yet, so not even the start address
	// should be in range.
	EXPECT_FALSE(arena.in_range(start), "");

	// Allocate some objects, and check that each is within range.
	static const int nobjs = 16;
	void* objs[nobjs];
	for (int i = 0; i < nobjs; i++) {
	char msg[32];
	snprintf(msg, sizeof(msg), "[%d]", i);
	objs[i] = arena.Alloc();
	EXPECT_NONNULL(objs[i], msg);
	// The allocated object should be in range.
	EXPECT_TRUE(arena.in_range(objs[i]), msg);
	// The slot just after this object should not be in range.
	// FRAGILE: assumes that objects are allocated in increasing order.
	EXPECT_FALSE(
	arena.in_range(reinterpret_cast<TestObj*>(objs[i]) + 1), msg);
	// The count should correspond to the number of times we have
	// allocated.
	EXPECT_EQ(static_cast<size_t>(i + 1), arena.DiagnosticCount(), msg);
	}

	// Deallocate the objects and check whether they're in range.
	for (int i = nobjs - 1; i >= 0; i--) {
	char msg[32];
	snprintf(msg, sizeof(msg), "[%d]", i);
	// The object should still be in range.
	EXPECT_TRUE(arena.in_range(objs[i]), msg);

	arena.Free(objs[i]);

	// The free slot will still be in range.
	// NOTE: If Arena ever learns to coalesce and decommit whole pages of
	// free objects, this test will need to change.
	EXPECT_TRUE(arena.in_range(objs[i]), msg);

	// The count should correspond to the number of times we have
	// deallocated.
	EXPECT_EQ(static_cast<size_t>(i), arena.DiagnosticCount(), msg);
	}
	END_TEST;
	}

	static bool out_of_memory() {
	BEGIN_TEST;
	static const size_t num_slots = (2 * PAGE_SIZE) / sizeof(TestObj);

	Arena arena;
	EXPECT_EQ(ZX_OK, arena.Init("name", sizeof(TestObj), num_slots), "");

	// Allocate all of the data objects.
	fbl::AllocChecker ac;
	fbl::unique_ptr<void[]> objs = fbl::unique_ptr<void[]>(new (&ac) void*[num_slots]);
	EXPECT_TRUE(ac.check(), "");
	void** top = &objs[0];
	for (size_t i = 0; i < num_slots; i++) {
	char msg[32];
	snprintf(msg, sizeof(msg), "[%zu]", i);
	*top++ = arena.Alloc();
	EXPECT_NONNULL(top[-1], msg);
	}

	// Any further allocations should return nullptr.
	EXPECT_NULL(arena.Alloc(), "");
	EXPECT_NULL(arena.Alloc(), "");
	EXPECT_NULL(arena.Alloc(), "");
	EXPECT_NULL(arena.Alloc(), "");

	// Free two objects.
	arena.Free(*--top);
	arena.Free(*--top);

	// Two allocations should succeed; any further should fail.
	*top++ = arena.Alloc();
	EXPECT_NONNULL(top[-1], "");
	*top++ = arena.Alloc();
	EXPECT_NONNULL(top[-1], "");
	EXPECT_NULL(arena.Alloc(), "");
	EXPECT_NULL(arena.Alloc(), "");

	// Free all objects.
	// Nothing much to check except that it doesn't crash.
	while (top > objs.get()) {
	arena.Free(*--top);
	}

	END_TEST;
	}

	// Test helper. Counts the number of committed and uncommitted pages in the
	// range. Returns {committed, uncommitted} = {0, 0} if \|start\| doesn't
	// correspond to a live VmMapping.
	static bool count_committed_pages(
	vaddr_t start, vaddr_t end, size_t* committed, size_t* uncommitted) {
	BEGIN_TEST; // Not a test, but we need these guards to use ASSERT_*
	*committed = 0;
	*uncommitted = 0;

	// Find the VmMapping that covers \|start\|. Assume that it covers \|end-1\|.
	const auto region = VmAspace::kernel_aspace()->FindRegion(start);
	ASSERT_NONNULL(region, "FindRegion");
	const auto mapping = region->as_vm_mapping();
	if (mapping == nullptr) {
	// It's a VMAR, not a mapping, so no pages are committed.
	// Return 0/0.
	return true;
	}

	// Ask the VMO how many pages it's allocated within the range.
	auto start_off = ROUNDDOWN(start, PAGE_SIZE) - mapping->base();
	auto end_off = ROUNDUP(end, PAGE_SIZE) - mapping->base();
	*committed = mapping->vmo()->AllocatedPagesInRange(
	start_off + mapping->object_offset(), end_off - start_off);
	uncommitted = (end_off - start_off) / PAGE_SIZE - committed;
	END_TEST;
	}

	static bool committing_tests() {
	BEGIN_TEST;
	static const size_t num_slots = (64 * PAGE_SIZE) / sizeof(TestObj);

	Arena arena;
	EXPECT_EQ(ZX_OK, arena.Init("name", sizeof(TestObj), num_slots), "");

	auto start = reinterpret_cast<vaddr_t>(arena.start());
	auto end = reinterpret_cast<vaddr_t>(arena.end());

	// Nothing is allocated yet, so no pages should be committed.
	size_t committed;
	size_t uncommitted;
	EXPECT_TRUE(
	count_committed_pages(start, end, &committed, &uncommitted), "");
	EXPECT_EQ(0u, committed, "");
	EXPECT_GT(uncommitted, 0u, "");

	// Allocate an object.
	auto obj = reinterpret_cast<vaddr_t>(arena.Alloc());
	EXPECT_NE(0u, obj, "");
	size_t atotal = sizeof(TestObj);

	// The page containing the object should be committed.
	auto ps = ROUNDDOWN(obj, PAGE_SIZE);
	auto pe = ROUNDUP(obj + sizeof(TestObj), PAGE_SIZE);
	EXPECT_TRUE(count_committed_pages(ps, pe, &committed, &uncommitted), "");
	EXPECT_GT(committed, 0u, "");
	EXPECT_EQ(0u, uncommitted, "");

	// The first handful of pages should also become committed, but the rest
	// should stay ucommitted.
	EXPECT_TRUE(
	count_committed_pages(start, end, &committed, &uncommitted), "");
	EXPECT_GT(committed, 0u, "");
	EXPECT_GT(uncommitted, 0u, "");

	// Fill the committed pages with objects; the set of committed pages
	// shouldn't change.
	auto orig_committed = committed;
	auto orig_uncommitted = uncommitted;
	while (atotal + sizeof(TestObj) <= orig_committed * PAGE_SIZE) {
	EXPECT_NONNULL(arena.Alloc(), "");
	atotal += sizeof(TestObj);
	}
	EXPECT_TRUE(
	count_committed_pages(start, end, &committed, &uncommitted), "");
	EXPECT_EQ(orig_committed, committed, "");
	EXPECT_EQ(orig_uncommitted, uncommitted, "");

	// Allocating one more object should cause more pages to be committed.
	EXPECT_NONNULL(arena.Alloc(), "");
	atotal += sizeof(TestObj);
	EXPECT_TRUE(
	count_committed_pages(start, end, &committed, &uncommitted), "");
	EXPECT_LT(orig_committed, committed, "");
	EXPECT_GT(orig_uncommitted, uncommitted, "");

	// TODO(dbort): Test uncommitting if Arena ever learns to decommit pages.
	END_TEST;
	}

	// Friend class that can see inside an Arena.
	namespace fbl {
	class ArenaTestFriend {
	public:
	ArenaTestFriend(const Arena& arena)
	: arena_(arena) {}

	constexpr static size_t control_slot_size() {
	return sizeof(Arena::Node);
	}

	vaddr_t control_start() const {
	return reinterpret_cast<vaddr_t>(arena_.control_.start());
	}

	vaddr_t control_end() const {
	return reinterpret_cast<vaddr_t>(arena_.control_.end());
	}

	private:
	const Arena& arena_;
	};
	} // namespace fbl
	using fbl::ArenaTestFriend;

	// Hit the decommit code path. We can't observe it without peeking inside the
	// control pool, since the data pool doesn't currently decommit.
	static bool uncommitting_tests() {
	BEGIN_TEST;
	// Create an arena with a 16-page control pool.
	static const size_t num_pages = 16;
	static const size_t num_slots =
	(num_pages * PAGE_SIZE) / ArenaTestFriend::control_slot_size();

	Arena arena;
	// Use a small data slot size (1) to keep our memory usage down.
	EXPECT_EQ(ZX_OK, arena.Init("name", 1, num_slots), "");

	// Get the extent of the control pool.
	vaddr_t start;
	vaddr_t end;
	{
	ArenaTestFriend atf(arena);
	start = reinterpret_cast<vaddr_t>(atf.control_start());
	end = reinterpret_cast<vaddr_t>(atf.control_end());
	}

	// Nothing is allocated yet, so no control pages should be committed.
	size_t committed;
	size_t uncommitted;
	EXPECT_TRUE(
	count_committed_pages(start, end, &committed, &uncommitted), "");
	EXPECT_EQ(num_pages, committed + uncommitted, "");
	EXPECT_EQ(0u, committed, "");
	EXPECT_GT(uncommitted, 0u, "");

	// Allocate all of the data objects. Hold onto the pointers so we can free
	// them.
	fbl::AllocChecker ac;
	fbl::unique_ptr<void[]> objs = fbl::unique_ptr<void[]>(new (&ac) void*[num_slots]);
	EXPECT_TRUE(ac.check(), "");
	void** top = &objs[0];
	for (size_t i = 0; i < num_slots; i++) {
	char msg[32];
	snprintf(msg, sizeof(msg), "[%zu]", i);
	*top++ = arena.Alloc();
	EXPECT_NONNULL(top[-1], msg);
	}

	// We still shouldn't see any control pages committed, becase no objects
	// have been freed yet.
	EXPECT_TRUE(
	count_committed_pages(start, end, &committed, &uncommitted), "");
	EXPECT_EQ(num_pages, committed + uncommitted, "");
	EXPECT_EQ(0u, committed, "");
	EXPECT_GT(uncommitted, 0u, "");

	// Demonstrate that we've allocated all of the data objects.
	void* no = arena.Alloc();
	EXPECT_NULL(no, "");

	// Free a data object.
	arena.Free(*--top);

	// We should now see some committed pages inside the control pool.
	EXPECT_TRUE(
	count_committed_pages(start, end, &committed, &uncommitted), "");
	EXPECT_EQ(num_pages, committed + uncommitted, "");
	EXPECT_GT(committed, 0u, "");
	EXPECT_GT(uncommitted, 0u, "");

	// Free all of the data objects.
	while (top > objs.get()) {
	arena.Free(*--top);
	}

	// All of the control pages should be committed.
	EXPECT_TRUE(
	count_committed_pages(start, end, &committed, &uncommitted), "");
	EXPECT_EQ(num_pages, committed + uncommitted, "");
	EXPECT_EQ(committed, num_pages, "");
	EXPECT_EQ(uncommitted, 0u, "");

	// Allocate half of the data objects, freeing up half of the free nodes
	// (and thus half of the control slots).
	auto orig_committed = committed;
	ASSERT_EQ(top, objs.get(), "");
	for (size_t i = 0; i < num_slots / 2; i++) {
	char msg[32];
	snprintf(msg, sizeof(msg), "[%zu]", i);
	*top++ = arena.Alloc();
	EXPECT_NONNULL(top[-1], msg);
	}

	// The number of committed pages should have dropped.
	EXPECT_TRUE(
	count_committed_pages(start, end, &committed, &uncommitted), "");
	EXPECT_EQ(num_pages, committed + uncommitted, "");
	EXPECT_LT(committed, orig_committed, "");
	EXPECT_GT(uncommitted, 0u, "");

	// Free more control slots (by allocating data objects) until we see more
	// unmapping happen.
	orig_committed = committed;
	for (size_t i = num_slots / 2; i < num_slots; i++) {
	char msg[32];
	snprintf(msg, sizeof(msg), "[%zu]", i);
	*top++ = arena.Alloc();
	EXPECT_NONNULL(top[-1], msg);

	EXPECT_TRUE(
	count_committed_pages(start, end, &committed, &uncommitted), "");
	if (committed != orig_committed) {
	break;
	}
	}
	EXPECT_GT(orig_committed, committed, "");

	// Allocating one more control slot (by freeing a data object) should not
	// cause the number of committed pages to change: there should be some
	// hysteresis built into the system to avoid flickering back and forth.
	orig_committed = committed;
	arena.Free(*--top);
	EXPECT_TRUE(
	count_committed_pages(start, end, &committed, &uncommitted), "");
	EXPECT_EQ(num_pages, committed + uncommitted, "");
	EXPECT_EQ(committed, orig_committed, "");
	EXPECT_GT(uncommitted, 0u, "");

	// Same for freeing a couple more control slots (by allocating more data
	// objects).
	*top++ = arena.Alloc();
	*top++ = arena.Alloc();
	EXPECT_TRUE(
	count_committed_pages(start, end, &committed, &uncommitted), "");
	EXPECT_EQ(num_pages, committed + uncommitted, "");
	EXPECT_EQ(committed, orig_committed, "");
	EXPECT_GT(uncommitted, 0u, "");

	END_TEST;
	}

	// Checks that destroying an arena unmaps all of its pages.
	static bool memory_cleanup() {
	BEGIN_TEST;
	static const size_t num_slots = (16 * PAGE_SIZE) / sizeof(TestObj);

	fbl::AllocChecker ac;
	Arena* arena = new (&ac) Arena();
	EXPECT_TRUE(ac.check(), "");
	EXPECT_EQ(ZX_OK, arena->Init("name", sizeof(TestObj), num_slots), "");

	auto start = reinterpret_cast<vaddr_t>(arena->start());
	auto end = reinterpret_cast<vaddr_t>(arena->end());

	// Allocate and leak a bunch of objects.
	for (size_t i = 0; i < num_slots; i++) {
	char msg[32];
	snprintf(msg, sizeof(msg), "[%zu]", i);
	EXPECT_NONNULL(arena->Alloc(), msg);
	}

	// Should see some committed pages.
	size_t committed;
	size_t uncommitted;
	EXPECT_TRUE(
	count_committed_pages(start, end, &committed, &uncommitted), "");
	EXPECT_GT(committed, 0u, "");

	// Destroying the Arena should destroy the underlying VmMapping,
	// along with all of its pages.
	delete arena;
	EXPECT_TRUE(
	count_committed_pages(start, end, &committed, &uncommitted), "");
	// 0/0 means "no mapping at this address".
	// FLAKY: Another thread could could come in and allocate a mapping at the
	// old location.
	EXPECT_EQ(committed, 0u, "");
	EXPECT_EQ(uncommitted, 0u, "");
	END_TEST;
	}

	// Basic checks that the contents of allocated objects stick around, aren't
	// stomped on.
	static bool content_preservation() {
	BEGIN_TEST;
	Arena arena;
	zx_status_t s = arena.Init("arena_tests", sizeof(TestObj), 1000);
	ASSERT_EQ(ZX_OK, s, "arena.Init()");

	const int count = 30;

	for (int times = 0; times != 5; ++times) {
	TestObj* afp[count] = {0};

	for (int ix = 0; ix != count; ++ix) {
	afp[ix] = reinterpret_cast<TestObj*>(arena.Alloc());
	ASSERT_NONNULL(afp[ix], "arena.Alloc()");
	*afp[ix] = {17, 5, ix + 100};
	}

	arena.Free(afp[3]);
	arena.Free(afp[4]);
	arena.Free(afp[5]);
	afp[3] = afp[4] = afp[5] = nullptr;

	afp[4] = reinterpret_cast<TestObj*>(arena.Alloc());
	ASSERT_NONNULL(afp[4], "arena.Alloc()");
	*afp[4] = {17, 5, 104};

	for (int ix = 0; ix != count; ++ix) {
	if (!afp[ix])
	continue;

	EXPECT_EQ(17, afp[ix]->xx, "");
	EXPECT_EQ(5, afp[ix]->yy, "");
	EXPECT_EQ(ix + 100, afp[ix]->zz, "");

	arena.Free(afp[ix]);
	}

	// Leak a few objects.
	for (int ix = 0; ix != 7; ++ix) {
	TestObj* leak = reinterpret_cast<TestObj*>(arena.Alloc());
	ASSERT_NONNULL(leak, "arena.Alloc()");
	*leak = {2121, 77, 55};
	}
	}
	END_TEST;
	}

	#define ARENA_UNITTEST(fname) UNITTEST(#fname, fname)

	UNITTEST_START_TESTCASE(arena_tests)
	ARENA_UNITTEST(init_null_name_succeeds)
	ARENA_UNITTEST(init_zero_ob_size_fails)
	ARENA_UNITTEST(init_large_ob_size_fails)
	ARENA_UNITTEST(init_zero_count_fails)
	ARENA_UNITTEST(start_and_end_look_good)
	ARENA_UNITTEST(in_range_tests)
	ARENA_UNITTEST(out_of_memory)
	ARENA_UNITTEST(committing_tests)
	ARENA_UNITTEST(uncommitting_tests)
	ARENA_UNITTEST(memory_cleanup)
	ARENA_UNITTEST(content_preservation)
	UNITTEST_END_TESTCASE(arena_tests, "arenatests", "Arena allocator test");