Space trim and other unit tests. General space clean up.
The space unit tests now include checks on space invariants, in
particular relating to footprint and size.
Out-of-date comments have been removed.
This patch adds PrettySize and PrettyDuration methods to make these
strings more human readable.
Change-Id: I6bc05b2db0d0115b97d666b832fce57bcdd2e091
diff --git a/src/space_test.cc b/src/space_test.cc
index f6d1191..4025805 100644
--- a/src/space_test.cc
+++ b/src/space_test.cc
@@ -3,12 +3,20 @@
#include "space.h"
#include "common_test.h"
+#include "dlmalloc.h"
#include "globals.h"
#include "UniquePtr.h"
+#include <stdint.h>
+
namespace art {
-class SpaceTest : public CommonTest {};
+class SpaceTest : public CommonTest {
+ public:
+ void SizeFootPrintGrowthLimitAndTrimBody(AllocSpace* space, intptr_t object_size,
+ int round, size_t growth_limit);
+ void SizeFootPrintGrowthLimitAndTrimDriver(size_t object_size);
+};
TEST_F(SpaceTest, Init) {
{
@@ -52,14 +60,14 @@
AllocSpace* space(Space::CreateAllocSpace("test", 4 * MB, 16 * MB, 16 * MB, NULL));
ASSERT_TRUE(space != NULL);
- // Make space findable to the heap, will also delete class when runtime is cleaned up
+ // Make space findable to the heap, will also delete space when runtime is cleaned up
Heap::AddSpace(space);
- // Succeeds, fits without adjusting the max allowed footprint.
+ // Succeeds, fits without adjusting the footprint limit.
Object* ptr1 = space->AllocWithoutGrowth(1 * MB);
EXPECT_TRUE(ptr1 != NULL);
- // Fails, requires a higher allowed footprint.
+ // Fails, requires a higher footprint limit.
Object* ptr2 = space->AllocWithoutGrowth(8 * MB);
EXPECT_TRUE(ptr2 == NULL);
@@ -67,13 +75,13 @@
Object* ptr3 = space->AllocWithGrowth(8 * MB);
EXPECT_TRUE(ptr3 != NULL);
- // Fails, requires a higher allowed footprint.
+ // Fails, requires a higher footprint limit.
Object* ptr4 = space->AllocWithoutGrowth(8 * MB);
- EXPECT_FALSE(ptr4 != NULL);
+ EXPECT_TRUE(ptr4 == NULL);
// Also fails, requires a higher allowed footprint.
Object* ptr5 = space->AllocWithGrowth(8 * MB);
- EXPECT_FALSE(ptr5 != NULL);
+ EXPECT_TRUE(ptr5 == NULL);
// Release some memory.
size_t free3 = space->AllocationSize(ptr3);
@@ -90,4 +98,236 @@
EXPECT_LE(1U * MB, free1);
}
+TEST_F(SpaceTest, AllocAndFreeList) {
+ AllocSpace* space(Space::CreateAllocSpace("test", 4 * MB, 16 * MB, 16 * MB, NULL));
+ ASSERT_TRUE(space != NULL);
+
+ // Make space findable to the heap, will also delete space when runtime is cleaned up
+ Heap::AddSpace(space);
+
+ // Succeeds, fits without adjusting the max allowed footprint.
+ Object* lots_of_objects[1024];
+ for(size_t i = 0; i < arraysize(lots_of_objects); i++) {
+ lots_of_objects[i] = space->AllocWithoutGrowth(16);
+ EXPECT_TRUE(lots_of_objects[i] != NULL);
+ }
+
+ // Release memory and check pointers are NULL
+ space->FreeList(arraysize(lots_of_objects), lots_of_objects);
+ for(size_t i = 0; i < arraysize(lots_of_objects); i++) {
+ EXPECT_TRUE(lots_of_objects[i] == NULL);
+ }
+
+ // Succeeds, fits by adjusting the max allowed footprint.
+ for(size_t i = 0; i < arraysize(lots_of_objects); i++) {
+ lots_of_objects[i] = space->AllocWithGrowth(1024);
+ EXPECT_TRUE(lots_of_objects[i] != NULL);
+ }
+
+ // Release memory and check pointers are NULL
+ space->FreeList(arraysize(lots_of_objects), lots_of_objects);
+ for(size_t i = 0; i < arraysize(lots_of_objects); i++) {
+ EXPECT_TRUE(lots_of_objects[i] == NULL);
+ }
+}
+
+static size_t test_rand() {
+ // TODO: replace this with something random yet deterministic
+ return rand();
+}
+
+void SpaceTest::SizeFootPrintGrowthLimitAndTrimBody(AllocSpace* space, intptr_t object_size,
+ int round, size_t growth_limit) {
+ if (((object_size > 0 && object_size >= static_cast<intptr_t>(growth_limit))) ||
+ ((object_size < 0 && -object_size >= static_cast<intptr_t>(growth_limit)))) {
+ // No allocation can succeed
+ return;
+ }
+ // Mspace for raw dlmalloc operations
+ void* mspace = space->GetMspace();
+
+ // mspace's footprint equals amount of resources requested from system
+ size_t footprint = mspace_footprint(mspace);
+
+ // mspace must at least have its book keeping allocated
+ EXPECT_GT(footprint, 0u);
+
+ // mspace but it shouldn't exceed the initial size
+ EXPECT_LE(footprint, growth_limit);
+
+ // space's size shouldn't exceed the initial size
+ EXPECT_LE(space->Size(), growth_limit);
+
+ // this invariant should always hold or else the mspace has grown to be larger than what the
+ // space believes its size is (which will break invariants)
+ EXPECT_GE(space->Size(), footprint);
+
+ // Fill the space with lots of small objects up to the growth limit
+ size_t max_objects = (growth_limit / (object_size > 0 ? object_size : 8)) + 1;
+ UniquePtr<Object*> lots_of_objects(new Object*[max_objects]);
+ size_t last_object = 0; // last object for which allocation succeeded
+ size_t amount_allocated = 0; // amount of space allocated
+ for(size_t i = 0; i < max_objects; i++) {
+ size_t alloc_fails = 0; // number of failed allocations
+ size_t max_fails = 30; // number of times we fail allocation before giving up
+ for (; alloc_fails < max_fails; alloc_fails++) {
+ size_t alloc_size;
+ if (object_size > 0) {
+ alloc_size = object_size;
+ } else {
+ alloc_size = test_rand() % static_cast<size_t>(-object_size);
+ if (alloc_size < 8) {
+ alloc_size = 8;
+ }
+ }
+ Object* object;
+ if (round <= 1) {
+ object = space->AllocWithoutGrowth(alloc_size);
+ } else {
+ object = space->AllocWithGrowth(alloc_size);
+ }
+ footprint = mspace_footprint(mspace);
+ EXPECT_GE(space->Size(), footprint); // invariant
+ if(object != NULL) { // allocation succeeded
+ lots_of_objects.get()[i] = object;
+ size_t allocation_size = space->AllocationSize(object);
+ if (object_size > 0) {
+ EXPECT_GE(allocation_size, static_cast<size_t>(object_size));
+ } else {
+ EXPECT_GE(allocation_size, 8u);
+ }
+ amount_allocated += allocation_size;
+ break;
+ }
+ }
+ if (alloc_fails == max_fails) {
+ last_object = i;
+ break;
+ }
+ }
+ CHECK_NE(last_object, 0u); // we should have filled the space
+ EXPECT_GT(amount_allocated, 0u);
+
+ // We shouldn't have gone past the growth_limit
+ EXPECT_LE(amount_allocated, growth_limit);
+ EXPECT_LE(footprint, growth_limit);
+ EXPECT_LE(space->Size(), growth_limit);
+
+ // footprint and size should agree with amount allocated
+ EXPECT_GE(footprint, amount_allocated);
+ EXPECT_GE(space->Size(), amount_allocated);
+
+ // Release storage in a semi-adhoc manner
+ size_t free_increment = 96;
+ while(true) {
+ // Give the space a haircut
+ space->Trim();
+
+ // Bounds sanity
+ footprint = mspace_footprint(mspace);
+ EXPECT_LE(amount_allocated, growth_limit);
+ EXPECT_GE(footprint, amount_allocated);
+ EXPECT_LE(footprint, growth_limit);
+ EXPECT_GE(space->Size(), amount_allocated);
+ EXPECT_LE(space->Size(), growth_limit);
+
+ if (free_increment == 0) {
+ break;
+ }
+
+ // Free some objects
+ for(size_t i = 0; i < last_object; i += free_increment) {
+ Object* object = lots_of_objects.get()[i];
+ if (object == NULL) {
+ continue;
+ }
+ size_t allocation_size = space->AllocationSize(object);
+ if (object_size > 0) {
+ EXPECT_GE(allocation_size, static_cast<size_t>(object_size));
+ } else {
+ EXPECT_GE(allocation_size, 8u);
+ }
+ space->Free(object);
+ lots_of_objects.get()[i] = NULL;
+ amount_allocated -= allocation_size;
+ footprint = mspace_footprint(mspace);
+ EXPECT_GE(space->Size(), footprint); // invariant
+ }
+
+ free_increment >>= 1;
+ }
+
+ // All memory was released, try a large allocation to check freed memory is being coalesced
+ Object* large_object;
+ size_t three_quarters_space = (growth_limit / 2) + (growth_limit / 4);
+ if (round <= 1) {
+ large_object = space->AllocWithoutGrowth(three_quarters_space);
+ } else {
+ large_object = space->AllocWithGrowth(three_quarters_space);
+ }
+ EXPECT_TRUE(large_object != NULL);
+
+ // Sanity check footprint
+ footprint = mspace_footprint(mspace);
+ EXPECT_LE(footprint, growth_limit);
+ EXPECT_GE(space->Size(), footprint);
+ EXPECT_LE(space->Size(), growth_limit);
+
+ // Clean up
+ space->Free(large_object);
+
+ // Sanity check footprint
+ footprint = mspace_footprint(mspace);
+ EXPECT_LE(footprint, growth_limit);
+ EXPECT_GE(space->Size(), footprint);
+ EXPECT_LE(space->Size(), growth_limit);
+}
+
+void SpaceTest::SizeFootPrintGrowthLimitAndTrimDriver(size_t object_size) {
+ size_t initial_size = 4 * MB;
+ size_t growth_limit = 8 * MB;
+ size_t capacity = 16 * MB;
+ AllocSpace* space(Space::CreateAllocSpace("test", initial_size, growth_limit, capacity, NULL));
+ ASSERT_TRUE(space != NULL);
+
+ // Basic sanity
+ EXPECT_EQ(space->Capacity(), growth_limit);
+ EXPECT_EQ(space->NonGrowthLimitCapacity(), capacity);
+
+ // Make space findable to the heap, will also delete space when runtime is cleaned up
+ Heap::AddSpace(space);
+
+ // In this round we don't allocate with growth and therefore can't grow past the initial size.
+ // This effectively makes the growth_limit the initial_size, so assert this.
+ SizeFootPrintGrowthLimitAndTrimBody(space, object_size, 1, initial_size);
+ SizeFootPrintGrowthLimitAndTrimBody(space, object_size, 2, growth_limit);
+ // Remove growth limit
+ space->ClearGrowthLimit();
+ EXPECT_EQ(space->Capacity(), capacity);
+ SizeFootPrintGrowthLimitAndTrimBody(space, object_size, 3, capacity);
+}
+
+#define TEST_SizeFootPrintGrowthLimitAndTrim(name, size) \
+ TEST_F(SpaceTest, SizeFootPrintGrowthLimitAndTrim_AllocationsOf_##name) { \
+ SizeFootPrintGrowthLimitAndTrimDriver(size); \
+ } \
+ TEST_F(SpaceTest, SizeFootPrintGrowthLimitAndTrim_RandomAllocationsWithMax_##name) { \
+ SizeFootPrintGrowthLimitAndTrimDriver(-size); \
+ }
+
+// Each size test is its own test so that we get a fresh heap each time
+TEST_F(SpaceTest, SizeFootPrintGrowthLimitAndTrim_AllocationsOf_8B) {
+ SizeFootPrintGrowthLimitAndTrimDriver(8);
+}
+TEST_SizeFootPrintGrowthLimitAndTrim(16B, 16)
+TEST_SizeFootPrintGrowthLimitAndTrim(24B, 24)
+TEST_SizeFootPrintGrowthLimitAndTrim(32B, 32)
+TEST_SizeFootPrintGrowthLimitAndTrim(64B, 64)
+TEST_SizeFootPrintGrowthLimitAndTrim(128B, 128)
+TEST_SizeFootPrintGrowthLimitAndTrim(1KB, 1 * KB)
+TEST_SizeFootPrintGrowthLimitAndTrim(4KB, 4 * KB)
+TEST_SizeFootPrintGrowthLimitAndTrim(1MB, 1 * MB)
+TEST_SizeFootPrintGrowthLimitAndTrim(4MB, 4 * MB)
+TEST_SizeFootPrintGrowthLimitAndTrim(8MB, 8 * MB)
+
} // namespace art