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