Home | History | Annotate | Download | only in space 
      1 /*
      2  * Copyright (C) 2011 The Android Open Source Project
      3  *
      4  * Licensed under the Apache License, Version 2.0 (the "License");
      5  * you may not use this file except in compliance with the License.
      6  * You may obtain a copy of the License at
      7  *
      8  *      http://www.apache.org/licenses/LICENSE-2.0
      9  *
     10  * Unless required by applicable law or agreed to in writing, software
     11  * distributed under the License is distributed on an "AS IS" BASIS,
     12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
     13  * See the License for the specific language governing permissions and
     14  * limitations under the License.
     15  */
     16 
     17 #include "dlmalloc_space.h"
     18 #include "large_object_space.h"
     19 
     20 #include "common_test.h"
     21 #include "globals.h"
     22 #include "UniquePtr.h"
     23 
     24 #include <stdint.h>
     25 
     26 namespace art {
     27 namespace gc {
     28 namespace space {
     29 
     30 class SpaceTest : public CommonTest {
     31  public:
     32   void SizeFootPrintGrowthLimitAndTrimBody(DlMallocSpace* space, intptr_t object_size,
     33                                            int round, size_t growth_limit);
     34   void SizeFootPrintGrowthLimitAndTrimDriver(size_t object_size);
     35 
     36   void AddContinuousSpace(ContinuousSpace* space) {
     37     Runtime::Current()->GetHeap()->AddContinuousSpace(space);
     38   }
     39 };
     40 
     41 static size_t test_rand(size_t* seed) {
     42   *seed = *seed * 1103515245 + 12345;
     43   return *seed;
     44 }
     45 
     46 TEST_F(SpaceTest, Init) {
     47   {
     48     // Init < max == growth
     49     UniquePtr<Space> space(DlMallocSpace::Create("test", 16 * MB, 32 * MB, 32 * MB, NULL));
     50     EXPECT_TRUE(space.get() != NULL);
     51   }
     52   {
     53     // Init == max == growth
     54     UniquePtr<Space> space(DlMallocSpace::Create("test", 16 * MB, 16 * MB, 16 * MB, NULL));
     55     EXPECT_TRUE(space.get() != NULL);
     56   }
     57   {
     58     // Init > max == growth
     59     UniquePtr<Space> space(DlMallocSpace::Create("test", 32 * MB, 16 * MB, 16 * MB, NULL));
     60     EXPECT_TRUE(space.get() == NULL);
     61   }
     62   {
     63     // Growth == init < max
     64     UniquePtr<Space> space(DlMallocSpace::Create("test", 16 * MB, 16 * MB, 32 * MB, NULL));
     65     EXPECT_TRUE(space.get() != NULL);
     66   }
     67   {
     68     // Growth < init < max
     69     UniquePtr<Space> space(DlMallocSpace::Create("test", 16 * MB, 8 * MB, 32 * MB, NULL));
     70     EXPECT_TRUE(space.get() == NULL);
     71   }
     72   {
     73     // Init < growth < max
     74     UniquePtr<Space> space(DlMallocSpace::Create("test", 8 * MB, 16 * MB, 32 * MB, NULL));
     75     EXPECT_TRUE(space.get() != NULL);
     76   }
     77   {
     78     // Init < max < growth
     79     UniquePtr<Space> space(DlMallocSpace::Create("test", 8 * MB, 32 * MB, 16 * MB, NULL));
     80     EXPECT_TRUE(space.get() == NULL);
     81   }
     82 }
     83 
     84 // TODO: This test is not very good, we should improve it.
     85 // The test should do more allocations before the creation of the ZygoteSpace, and then do
     86 // allocations after the ZygoteSpace is created. The test should also do some GCs to ensure that
     87 // the GC works with the ZygoteSpace.
     88 TEST_F(SpaceTest, ZygoteSpace) {
     89     size_t dummy = 0;
     90     DlMallocSpace* space(DlMallocSpace::Create("test", 4 * MB, 16 * MB, 16 * MB, NULL));
     91     ASSERT_TRUE(space != NULL);
     92 
     93     // Make space findable to the heap, will also delete space when runtime is cleaned up
     94     AddContinuousSpace(space);
     95     Thread* self = Thread::Current();
     96 
     97     // Succeeds, fits without adjusting the footprint limit.
     98     mirror::Object* ptr1 = space->Alloc(self, 1 * MB, &dummy);
     99     EXPECT_TRUE(ptr1 != NULL);
    100 
    101     // Fails, requires a higher footprint limit.
    102     mirror::Object* ptr2 = space->Alloc(self, 8 * MB, &dummy);
    103     EXPECT_TRUE(ptr2 == NULL);
    104 
    105     // Succeeds, adjusts the footprint.
    106     size_t ptr3_bytes_allocated;
    107     mirror::Object* ptr3 = space->AllocWithGrowth(self, 8 * MB, &ptr3_bytes_allocated);
    108     EXPECT_TRUE(ptr3 != NULL);
    109     EXPECT_LE(8U * MB, ptr3_bytes_allocated);
    110 
    111     // Fails, requires a higher footprint limit.
    112     mirror::Object* ptr4 = space->Alloc(self, 8 * MB, &dummy);
    113     EXPECT_TRUE(ptr4 == NULL);
    114 
    115     // Also fails, requires a higher allowed footprint.
    116     mirror::Object* ptr5 = space->AllocWithGrowth(self, 8 * MB, &dummy);
    117     EXPECT_TRUE(ptr5 == NULL);
    118 
    119     // Release some memory.
    120     size_t free3 = space->AllocationSize(ptr3);
    121     EXPECT_EQ(free3, ptr3_bytes_allocated);
    122     EXPECT_EQ(free3, space->Free(self, ptr3));
    123     EXPECT_LE(8U * MB, free3);
    124 
    125     // Succeeds, now that memory has been freed.
    126     void* ptr6 = space->AllocWithGrowth(self, 9 * MB, &dummy);
    127     EXPECT_TRUE(ptr6 != NULL);
    128 
    129     // Final clean up.
    130     size_t free1 = space->AllocationSize(ptr1);
    131     space->Free(self, ptr1);
    132     EXPECT_LE(1U * MB, free1);
    133 
    134     // Make sure that the zygote space isn't directly at the start of the space.
    135     space->Alloc(self, 1U * MB, &dummy);
    136     space = space->CreateZygoteSpace("alloc space");
    137 
    138     // Make space findable to the heap, will also delete space when runtime is cleaned up
    139     AddContinuousSpace(space);
    140 
    141     // Succeeds, fits without adjusting the footprint limit.
    142     ptr1 = space->Alloc(self, 1 * MB, &dummy);
    143     EXPECT_TRUE(ptr1 != NULL);
    144 
    145     // Fails, requires a higher footprint limit.
    146     ptr2 = space->Alloc(self, 8 * MB, &dummy);
    147     EXPECT_TRUE(ptr2 == NULL);
    148 
    149     // Succeeds, adjusts the footprint.
    150     ptr3 = space->AllocWithGrowth(self, 2 * MB, &dummy);
    151     EXPECT_TRUE(ptr3 != NULL);
    152     space->Free(self, ptr3);
    153 
    154     // Final clean up.
    155     free1 = space->AllocationSize(ptr1);
    156     space->Free(self, ptr1);
    157     EXPECT_LE(1U * MB, free1);
    158 }
    159 
    160 TEST_F(SpaceTest, AllocAndFree) {
    161   size_t dummy = 0;
    162   DlMallocSpace* space(DlMallocSpace::Create("test", 4 * MB, 16 * MB, 16 * MB, NULL));
    163   ASSERT_TRUE(space != NULL);
    164   Thread* self = Thread::Current();
    165 
    166   // Make space findable to the heap, will also delete space when runtime is cleaned up
    167   AddContinuousSpace(space);
    168 
    169   // Succeeds, fits without adjusting the footprint limit.
    170   mirror::Object* ptr1 = space->Alloc(self, 1 * MB, &dummy);
    171   EXPECT_TRUE(ptr1 != NULL);
    172 
    173   // Fails, requires a higher footprint limit.
    174   mirror::Object* ptr2 = space->Alloc(self, 8 * MB, &dummy);
    175   EXPECT_TRUE(ptr2 == NULL);
    176 
    177   // Succeeds, adjusts the footprint.
    178   size_t ptr3_bytes_allocated;
    179   mirror::Object* ptr3 = space->AllocWithGrowth(self, 8 * MB, &ptr3_bytes_allocated);
    180   EXPECT_TRUE(ptr3 != NULL);
    181   EXPECT_LE(8U * MB, ptr3_bytes_allocated);
    182 
    183   // Fails, requires a higher footprint limit.
    184   mirror::Object* ptr4 = space->Alloc(self, 8 * MB, &dummy);
    185   EXPECT_TRUE(ptr4 == NULL);
    186 
    187   // Also fails, requires a higher allowed footprint.
    188   mirror::Object* ptr5 = space->AllocWithGrowth(self, 8 * MB, &dummy);
    189   EXPECT_TRUE(ptr5 == NULL);
    190 
    191   // Release some memory.
    192   size_t free3 = space->AllocationSize(ptr3);
    193   EXPECT_EQ(free3, ptr3_bytes_allocated);
    194   space->Free(self, ptr3);
    195   EXPECT_LE(8U * MB, free3);
    196 
    197   // Succeeds, now that memory has been freed.
    198   void* ptr6 = space->AllocWithGrowth(self, 9 * MB, &dummy);
    199   EXPECT_TRUE(ptr6 != NULL);
    200 
    201   // Final clean up.
    202   size_t free1 = space->AllocationSize(ptr1);
    203   space->Free(self, ptr1);
    204   EXPECT_LE(1U * MB, free1);
    205 }
    206 
    207 TEST_F(SpaceTest, LargeObjectTest) {
    208   size_t rand_seed = 0;
    209   for (size_t i = 0; i < 2; ++i) {
    210     LargeObjectSpace* los = NULL;
    211     if (i == 0) {
    212       los = space::LargeObjectMapSpace::Create("large object space");
    213     } else {
    214       los = space::FreeListSpace::Create("large object space", NULL, 128 * MB);
    215     }
    216 
    217     static const size_t num_allocations = 64;
    218     static const size_t max_allocation_size = 0x100000;
    219     std::vector<std::pair<mirror::Object*, size_t> > requests;
    220 
    221     for (size_t phase = 0; phase < 2; ++phase) {
    222       while (requests.size() < num_allocations) {
    223         size_t request_size = test_rand(&rand_seed) % max_allocation_size;
    224         size_t allocation_size = 0;
    225         mirror::Object* obj = los->Alloc(Thread::Current(), request_size, &allocation_size);
    226         ASSERT_TRUE(obj != NULL);
    227         ASSERT_EQ(allocation_size, los->AllocationSize(obj));
    228         ASSERT_GE(allocation_size, request_size);
    229         // Fill in our magic value.
    230         byte magic = (request_size & 0xFF) | 1;
    231         memset(obj, magic, request_size);
    232         requests.push_back(std::make_pair(obj, request_size));
    233       }
    234 
    235       // "Randomly" shuffle the requests.
    236       for (size_t k = 0; k < 10; ++k) {
    237         for (size_t j = 0; j < requests.size(); ++j) {
    238           std::swap(requests[j], requests[test_rand(&rand_seed) % requests.size()]);
    239         }
    240       }
    241 
    242       // Free 1 / 2 the allocations the first phase, and all the second phase.
    243       size_t limit = !phase ? requests.size() / 2 : 0;
    244       while (requests.size() > limit) {
    245         mirror::Object* obj = requests.back().first;
    246         size_t request_size = requests.back().second;
    247         requests.pop_back();
    248         byte magic = (request_size & 0xFF) | 1;
    249         for (size_t k = 0; k < request_size; ++k) {
    250           ASSERT_EQ(reinterpret_cast<const byte*>(obj)[k], magic);
    251         }
    252         ASSERT_GE(los->Free(Thread::Current(), obj), request_size);
    253       }
    254     }
    255 
    256     size_t bytes_allocated = 0;
    257     // Checks that the coalescing works.
    258     mirror::Object* obj = los->Alloc(Thread::Current(), 100 * MB, &bytes_allocated);
    259     EXPECT_TRUE(obj != NULL);
    260     los->Free(Thread::Current(), obj);
    261 
    262     EXPECT_EQ(0U, los->GetBytesAllocated());
    263     EXPECT_EQ(0U, los->GetObjectsAllocated());
    264     delete los;
    265   }
    266 }
    267 
    268 TEST_F(SpaceTest, AllocAndFreeList) {
    269   DlMallocSpace* space(DlMallocSpace::Create("test", 4 * MB, 16 * MB, 16 * MB, NULL));
    270   ASSERT_TRUE(space != NULL);
    271 
    272   // Make space findable to the heap, will also delete space when runtime is cleaned up
    273   AddContinuousSpace(space);
    274   Thread* self = Thread::Current();
    275 
    276   // Succeeds, fits without adjusting the max allowed footprint.
    277   mirror::Object* lots_of_objects[1024];
    278   for (size_t i = 0; i < arraysize(lots_of_objects); i++) {
    279     size_t allocation_size = 0;
    280     lots_of_objects[i] = space->Alloc(self, 16, &allocation_size);
    281     EXPECT_EQ(allocation_size, space->AllocationSize(lots_of_objects[i]));
    282     EXPECT_TRUE(lots_of_objects[i] != NULL);
    283   }
    284 
    285   // Release memory and check pointers are NULL
    286   space->FreeList(self, arraysize(lots_of_objects), lots_of_objects);
    287   for (size_t i = 0; i < arraysize(lots_of_objects); i++) {
    288     EXPECT_TRUE(lots_of_objects[i] == NULL);
    289   }
    290 
    291   // Succeeds, fits by adjusting the max allowed footprint.
    292   for (size_t i = 0; i < arraysize(lots_of_objects); i++) {
    293     size_t allocation_size = 0;
    294     lots_of_objects[i] = space->AllocWithGrowth(self, 1024, &allocation_size);
    295     EXPECT_EQ(allocation_size, space->AllocationSize(lots_of_objects[i]));
    296     EXPECT_TRUE(lots_of_objects[i] != NULL);
    297   }
    298 
    299   // Release memory and check pointers are NULL
    300   space->FreeList(self, arraysize(lots_of_objects), lots_of_objects);
    301   for (size_t i = 0; i < arraysize(lots_of_objects); i++) {
    302     EXPECT_TRUE(lots_of_objects[i] == NULL);
    303   }
    304 }
    305 
    306 void SpaceTest::SizeFootPrintGrowthLimitAndTrimBody(DlMallocSpace* space, intptr_t object_size,
    307                                                     int round, size_t growth_limit) {
    308   if (((object_size > 0 && object_size >= static_cast<intptr_t>(growth_limit))) ||
    309       ((object_size < 0 && -object_size >= static_cast<intptr_t>(growth_limit)))) {
    310     // No allocation can succeed
    311     return;
    312   }
    313   // Mspace for raw dlmalloc operations
    314   void* mspace = space->GetMspace();
    315 
    316   // mspace's footprint equals amount of resources requested from system
    317   size_t footprint = mspace_footprint(mspace);
    318 
    319   // mspace must at least have its book keeping allocated
    320   EXPECT_GT(footprint, 0u);
    321 
    322   // mspace but it shouldn't exceed the initial size
    323   EXPECT_LE(footprint, growth_limit);
    324 
    325   // space's size shouldn't exceed the initial size
    326   EXPECT_LE(space->Size(), growth_limit);
    327 
    328   // this invariant should always hold or else the mspace has grown to be larger than what the
    329   // space believes its size is (which will break invariants)
    330   EXPECT_GE(space->Size(), footprint);
    331 
    332   // Fill the space with lots of small objects up to the growth limit
    333   size_t max_objects = (growth_limit / (object_size > 0 ? object_size : 8)) + 1;
    334   UniquePtr<mirror::Object*[]> lots_of_objects(new mirror::Object*[max_objects]);
    335   size_t last_object = 0;  // last object for which allocation succeeded
    336   size_t amount_allocated = 0;  // amount of space allocated
    337   Thread* self = Thread::Current();
    338   size_t rand_seed = 123456789;
    339   for (size_t i = 0; i < max_objects; i++) {
    340     size_t alloc_fails = 0;  // number of failed allocations
    341     size_t max_fails = 30;  // number of times we fail allocation before giving up
    342     for (; alloc_fails < max_fails; alloc_fails++) {
    343       size_t alloc_size;
    344       if (object_size > 0) {
    345         alloc_size = object_size;
    346       } else {
    347         alloc_size = test_rand(&rand_seed) % static_cast<size_t>(-object_size);
    348         if (alloc_size < 8) {
    349           alloc_size = 8;
    350         }
    351       }
    352       mirror::Object* object;
    353       size_t bytes_allocated = 0;
    354       if (round <= 1) {
    355         object = space->Alloc(self, alloc_size, &bytes_allocated);
    356       } else {
    357         object = space->AllocWithGrowth(self, alloc_size, &bytes_allocated);
    358       }
    359       footprint = mspace_footprint(mspace);
    360       EXPECT_GE(space->Size(), footprint);  // invariant
    361       if (object != NULL) {  // allocation succeeded
    362         lots_of_objects.get()[i] = object;
    363         size_t allocation_size = space->AllocationSize(object);
    364         EXPECT_EQ(bytes_allocated, allocation_size);
    365         if (object_size > 0) {
    366           EXPECT_GE(allocation_size, static_cast<size_t>(object_size));
    367         } else {
    368           EXPECT_GE(allocation_size, 8u);
    369         }
    370         amount_allocated += allocation_size;
    371         break;
    372       }
    373     }
    374     if (alloc_fails == max_fails) {
    375       last_object = i;
    376       break;
    377     }
    378   }
    379   CHECK_NE(last_object, 0u);  // we should have filled the space
    380   EXPECT_GT(amount_allocated, 0u);
    381 
    382   // We shouldn't have gone past the growth_limit
    383   EXPECT_LE(amount_allocated, growth_limit);
    384   EXPECT_LE(footprint, growth_limit);
    385   EXPECT_LE(space->Size(), growth_limit);
    386 
    387   // footprint and size should agree with amount allocated
    388   EXPECT_GE(footprint, amount_allocated);
    389   EXPECT_GE(space->Size(), amount_allocated);
    390 
    391   // Release storage in a semi-adhoc manner
    392   size_t free_increment = 96;
    393   while (true) {
    394     // Give the space a haircut
    395     space->Trim();
    396 
    397     // Bounds sanity
    398     footprint = mspace_footprint(mspace);
    399     EXPECT_LE(amount_allocated, growth_limit);
    400     EXPECT_GE(footprint, amount_allocated);
    401     EXPECT_LE(footprint, growth_limit);
    402     EXPECT_GE(space->Size(), amount_allocated);
    403     EXPECT_LE(space->Size(), growth_limit);
    404 
    405     if (free_increment == 0) {
    406       break;
    407     }
    408 
    409     // Free some objects
    410     for (size_t i = 0; i < last_object; i += free_increment) {
    411       mirror::Object* object = lots_of_objects.get()[i];
    412       if (object == NULL) {
    413         continue;
    414       }
    415       size_t allocation_size = space->AllocationSize(object);
    416       if (object_size > 0) {
    417         EXPECT_GE(allocation_size, static_cast<size_t>(object_size));
    418       } else {
    419         EXPECT_GE(allocation_size, 8u);
    420       }
    421       space->Free(self, object);
    422       lots_of_objects.get()[i] = NULL;
    423       amount_allocated -= allocation_size;
    424       footprint = mspace_footprint(mspace);
    425       EXPECT_GE(space->Size(), footprint);  // invariant
    426     }
    427 
    428     free_increment >>= 1;
    429   }
    430 
    431   // All memory was released, try a large allocation to check freed memory is being coalesced
    432   mirror::Object* large_object;
    433   size_t three_quarters_space = (growth_limit / 2) + (growth_limit / 4);
    434   size_t bytes_allocated = 0;
    435   if (round <= 1) {
    436     large_object = space->Alloc(self, three_quarters_space, &bytes_allocated);
    437   } else {
    438     large_object = space->AllocWithGrowth(self, three_quarters_space, &bytes_allocated);
    439   }
    440   EXPECT_TRUE(large_object != NULL);
    441 
    442   // Sanity check footprint
    443   footprint = mspace_footprint(mspace);
    444   EXPECT_LE(footprint, growth_limit);
    445   EXPECT_GE(space->Size(), footprint);
    446   EXPECT_LE(space->Size(), growth_limit);
    447 
    448   // Clean up
    449   space->Free(self, large_object);
    450 
    451   // Sanity check footprint
    452   footprint = mspace_footprint(mspace);
    453   EXPECT_LE(footprint, growth_limit);
    454   EXPECT_GE(space->Size(), footprint);
    455   EXPECT_LE(space->Size(), growth_limit);
    456 }
    457 
    458 void SpaceTest::SizeFootPrintGrowthLimitAndTrimDriver(size_t object_size) {
    459   size_t initial_size = 4 * MB;
    460   size_t growth_limit = 8 * MB;
    461   size_t capacity = 16 * MB;
    462   DlMallocSpace* space(DlMallocSpace::Create("test", initial_size, growth_limit, capacity, NULL));
    463   ASSERT_TRUE(space != NULL);
    464 
    465   // Basic sanity
    466   EXPECT_EQ(space->Capacity(), growth_limit);
    467   EXPECT_EQ(space->NonGrowthLimitCapacity(), capacity);
    468 
    469   // Make space findable to the heap, will also delete space when runtime is cleaned up
    470   AddContinuousSpace(space);
    471 
    472   // In this round we don't allocate with growth and therefore can't grow past the initial size.
    473   // This effectively makes the growth_limit the initial_size, so assert this.
    474   SizeFootPrintGrowthLimitAndTrimBody(space, object_size, 1, initial_size);
    475   SizeFootPrintGrowthLimitAndTrimBody(space, object_size, 2, growth_limit);
    476   // Remove growth limit
    477   space->ClearGrowthLimit();
    478   EXPECT_EQ(space->Capacity(), capacity);
    479   SizeFootPrintGrowthLimitAndTrimBody(space, object_size, 3, capacity);
    480 }
    481 
    482 #define TEST_SizeFootPrintGrowthLimitAndTrim(name, size) \
    483   TEST_F(SpaceTest, SizeFootPrintGrowthLimitAndTrim_AllocationsOf_##name) { \
    484     SizeFootPrintGrowthLimitAndTrimDriver(size); \
    485   } \
    486   TEST_F(SpaceTest, SizeFootPrintGrowthLimitAndTrim_RandomAllocationsWithMax_##name) { \
    487     SizeFootPrintGrowthLimitAndTrimDriver(-size); \
    488   }
    489 
    490 // Each size test is its own test so that we get a fresh heap each time
    491 TEST_F(SpaceTest, SizeFootPrintGrowthLimitAndTrim_AllocationsOf_8B) {
    492   SizeFootPrintGrowthLimitAndTrimDriver(8);
    493 }
    494 TEST_SizeFootPrintGrowthLimitAndTrim(16B, 16)
    495 TEST_SizeFootPrintGrowthLimitAndTrim(24B, 24)
    496 TEST_SizeFootPrintGrowthLimitAndTrim(32B, 32)
    497 TEST_SizeFootPrintGrowthLimitAndTrim(64B, 64)
    498 TEST_SizeFootPrintGrowthLimitAndTrim(128B, 128)
    499 TEST_SizeFootPrintGrowthLimitAndTrim(1KB, 1 * KB)
    500 TEST_SizeFootPrintGrowthLimitAndTrim(4KB, 4 * KB)
    501 TEST_SizeFootPrintGrowthLimitAndTrim(1MB, 1 * MB)
    502 TEST_SizeFootPrintGrowthLimitAndTrim(4MB, 4 * MB)
    503 TEST_SizeFootPrintGrowthLimitAndTrim(8MB, 8 * MB)
    504 
    505 }  // namespace space
    506 }  // namespace gc
    507 }  // namespace art
    508