gc/space/space_test.h

/*
 * Copyright (C) 2011 The Android Open Source Project
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

#ifndef ART_RUNTIME_GC_SPACE_SPACE_TEST_H_
#define ART_RUNTIME_GC_SPACE_SPACE_TEST_H_

#include "zygote_space.h"

#include <stdint.h>

#include "common_runtime_test.h"
#include "globals.h"
#include "UniquePtr.h"
#include "mirror/array-inl.h"
#include "mirror/object-inl.h"

namespace art {
namespace gc {
namespace space {

class SpaceTest : public CommonRuntimeTest {
 public:
  void AddSpace(ContinuousSpace* space) {
    // For RosAlloc, revoke the thread local runs before moving onto a
    // new alloc space.
    Runtime::Current()->GetHeap()->RevokeAllThreadLocalBuffers();
    Runtime::Current()->GetHeap()->AddSpace(space);
  }
  void InstallClass(SirtRef<mirror::Object>& o, size_t size)
      SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
    // Note the minimum size, which is the size of a zero-length byte array.
    EXPECT_GE(size, SizeOfZeroLengthByteArray());
    Thread* self = Thread::Current();
    SirtRef<mirror::ClassLoader> null_loader(self, nullptr);
    mirror::Class* byte_array_class = Runtime::Current()->GetClassLinker()->FindClass(self, "[B",
                                                                                      null_loader);
    EXPECT_TRUE(byte_array_class != nullptr);
    o->SetClass(byte_array_class);
    if (kUseBrooksPointer) {
      o->SetBrooksPointer(o.get());
    }
    mirror::Array* arr = o->AsArray<kVerifyNone>();
    size_t header_size = SizeOfZeroLengthByteArray();
    int32_t length = size - header_size;
    arr->SetLength(length);
    EXPECT_EQ(arr->SizeOf<kVerifyNone>(), size);
  }

  static size_t SizeOfZeroLengthByteArray() {
    return mirror::Array::DataOffset(Primitive::ComponentSize(Primitive::kPrimByte)).Uint32Value();
  }

  typedef MallocSpace* (*CreateSpaceFn)(const std::string& name, size_t initial_size, size_t growth_limit,
                                        size_t capacity, byte* requested_begin);
  void InitTestBody(CreateSpaceFn create_space);
  void ZygoteSpaceTestBody(CreateSpaceFn create_space);
  void AllocAndFreeTestBody(CreateSpaceFn create_space);
  void AllocAndFreeListTestBody(CreateSpaceFn create_space);

  void SizeFootPrintGrowthLimitAndTrimBody(MallocSpace* space, intptr_t object_size,
                                           int round, size_t growth_limit);
  void SizeFootPrintGrowthLimitAndTrimDriver(size_t object_size, CreateSpaceFn create_space);
};

static size_t test_rand(size_t* seed) {
  *seed = *seed * 1103515245 + 12345;
  return *seed;
}

void SpaceTest::InitTestBody(CreateSpaceFn create_space) {
  {
    // Init < max == growth
    UniquePtr<Space> space(create_space("test", 16 * MB, 32 * MB, 32 * MB, nullptr));
    EXPECT_TRUE(space.get() != nullptr);
  }
  {
    // Init == max == growth
    UniquePtr<Space> space(create_space("test", 16 * MB, 16 * MB, 16 * MB, nullptr));
    EXPECT_TRUE(space.get() != nullptr);
  }
  {
    // Init > max == growth
    UniquePtr<Space> space(create_space("test", 32 * MB, 16 * MB, 16 * MB, nullptr));
    EXPECT_TRUE(space.get() == nullptr);
  }
  {
    // Growth == init < max
    UniquePtr<Space> space(create_space("test", 16 * MB, 16 * MB, 32 * MB, nullptr));
    EXPECT_TRUE(space.get() != nullptr);
  }
  {
    // Growth < init < max
    UniquePtr<Space> space(create_space("test", 16 * MB, 8 * MB, 32 * MB, nullptr));
    EXPECT_TRUE(space.get() == nullptr);
  }
  {
    // Init < growth < max
    UniquePtr<Space> space(create_space("test", 8 * MB, 16 * MB, 32 * MB, nullptr));
    EXPECT_TRUE(space.get() != nullptr);
  }
  {
    // Init < max < growth
    UniquePtr<Space> space(create_space("test", 8 * MB, 32 * MB, 16 * MB, nullptr));
    EXPECT_TRUE(space.get() == nullptr);
  }
}

// TODO: This test is not very good, we should improve it.
// The test should do more allocations before the creation of the ZygoteSpace, and then do
// allocations after the ZygoteSpace is created. The test should also do some GCs to ensure that
// the GC works with the ZygoteSpace.
void SpaceTest::ZygoteSpaceTestBody(CreateSpaceFn create_space) {
  size_t dummy = 0;
  MallocSpace* space(create_space("test", 4 * MB, 16 * MB, 16 * MB, nullptr));
  ASSERT_TRUE(space != nullptr);

  // Make space findable to the heap, will also delete space when runtime is cleaned up
  AddSpace(space);
  Thread* self = Thread::Current();
  ScopedObjectAccess soa(self);

  // Succeeds, fits without adjusting the footprint limit.
  SirtRef<mirror::Object> ptr1(self, space->Alloc(self, 1 * MB, &dummy));
  EXPECT_TRUE(ptr1.get() != nullptr);
  InstallClass(ptr1, 1 * MB);

  // Fails, requires a higher footprint limit.
  mirror::Object* ptr2 = space->Alloc(self, 8 * MB, &dummy);
  EXPECT_TRUE(ptr2 == nullptr);

  // Succeeds, adjusts the footprint.
  size_t ptr3_bytes_allocated;
  SirtRef<mirror::Object> ptr3(self, space->AllocWithGrowth(self, 8 * MB, &ptr3_bytes_allocated));
  EXPECT_TRUE(ptr3.get() != nullptr);
  EXPECT_LE(8U * MB, ptr3_bytes_allocated);
  InstallClass(ptr3, 8 * MB);

  // Fails, requires a higher footprint limit.
  mirror::Object* ptr4 = space->Alloc(self, 8 * MB, &dummy);
  EXPECT_TRUE(ptr4 == nullptr);

  // Also fails, requires a higher allowed footprint.
  mirror::Object* ptr5 = space->AllocWithGrowth(self, 8 * MB, &dummy);
  EXPECT_TRUE(ptr5 == nullptr);

  // Release some memory.
  size_t free3 = space->AllocationSize(ptr3.get());
  EXPECT_EQ(free3, ptr3_bytes_allocated);
  EXPECT_EQ(free3, space->Free(self, ptr3.reset(nullptr)));
  EXPECT_LE(8U * MB, free3);

  // Succeeds, now that memory has been freed.
  SirtRef<mirror::Object> ptr6(self, space->AllocWithGrowth(self, 9 * MB, &dummy));
  EXPECT_TRUE(ptr6.get() != nullptr);
  InstallClass(ptr6, 9 * MB);

  // Final clean up.
  size_t free1 = space->AllocationSize(ptr1.get());
  space->Free(self, ptr1.reset(nullptr));
  EXPECT_LE(1U * MB, free1);

  // Make sure that the zygote space isn't directly at the start of the space.
  space->Alloc(self, 1U * MB, &dummy);

  gc::Heap* heap = Runtime::Current()->GetHeap();
  space::Space* old_space = space;
  heap->RemoveSpace(old_space);
  space::ZygoteSpace* zygote_space = space->CreateZygoteSpace("alloc space",
                                                              heap->IsLowMemoryMode(),
                                                              &space);
  delete old_space;
  // Add the zygote space.
  AddSpace(zygote_space);

  // Make space findable to the heap, will also delete space when runtime is cleaned up
  AddSpace(space);

  // Succeeds, fits without adjusting the footprint limit.
  ptr1.reset(space->Alloc(self, 1 * MB, &dummy));
  EXPECT_TRUE(ptr1.get() != nullptr);
  InstallClass(ptr1, 1 * MB);

  // Fails, requires a higher footprint limit.
  ptr2 = space->Alloc(self, 8 * MB, &dummy);
  EXPECT_TRUE(ptr2 == nullptr);

  // Succeeds, adjusts the footprint.
  ptr3.reset(space->AllocWithGrowth(self, 2 * MB, &dummy));
  EXPECT_TRUE(ptr3.get() != nullptr);
  InstallClass(ptr3, 2 * MB);
  space->Free(self, ptr3.reset(nullptr));

  // Final clean up.
  free1 = space->AllocationSize(ptr1.get());
  space->Free(self, ptr1.reset(nullptr));
  EXPECT_LE(1U * MB, free1);
}

void SpaceTest::AllocAndFreeTestBody(CreateSpaceFn create_space) {
  size_t dummy = 0;
  MallocSpace* space(create_space("test", 4 * MB, 16 * MB, 16 * MB, nullptr));
  ASSERT_TRUE(space != nullptr);
  Thread* self = Thread::Current();
  ScopedObjectAccess soa(self);

  // Make space findable to the heap, will also delete space when runtime is cleaned up
  AddSpace(space);

  // Succeeds, fits without adjusting the footprint limit.
  SirtRef<mirror::Object> ptr1(self, space->Alloc(self, 1 * MB, &dummy));
  EXPECT_TRUE(ptr1.get() != nullptr);
  InstallClass(ptr1, 1 * MB);

  // Fails, requires a higher footprint limit.
  mirror::Object* ptr2 = space->Alloc(self, 8 * MB, &dummy);
  EXPECT_TRUE(ptr2 == nullptr);

  // Succeeds, adjusts the footprint.
  size_t ptr3_bytes_allocated;
  SirtRef<mirror::Object> ptr3(self, space->AllocWithGrowth(self, 8 * MB, &ptr3_bytes_allocated));
  EXPECT_TRUE(ptr3.get() != nullptr);
  EXPECT_LE(8U * MB, ptr3_bytes_allocated);
  InstallClass(ptr3, 8 * MB);

  // Fails, requires a higher footprint limit.
  mirror::Object* ptr4 = space->Alloc(self, 8 * MB, &dummy);
  EXPECT_TRUE(ptr4 == nullptr);

  // Also fails, requires a higher allowed footprint.
  mirror::Object* ptr5 = space->AllocWithGrowth(self, 8 * MB, &dummy);
  EXPECT_TRUE(ptr5 == nullptr);

  // Release some memory.
  size_t free3 = space->AllocationSize(ptr3.get());
  EXPECT_EQ(free3, ptr3_bytes_allocated);
  space->Free(self, ptr3.reset(nullptr));
  EXPECT_LE(8U * MB, free3);

  // Succeeds, now that memory has been freed.
  SirtRef<mirror::Object> ptr6(self, space->AllocWithGrowth(self, 9 * MB, &dummy));
  EXPECT_TRUE(ptr6.get() != nullptr);
  InstallClass(ptr6, 9 * MB);

  // Final clean up.
  size_t free1 = space->AllocationSize(ptr1.get());
  space->Free(self, ptr1.reset(nullptr));
  EXPECT_LE(1U * MB, free1);
}

void SpaceTest::AllocAndFreeListTestBody(CreateSpaceFn create_space) {
  MallocSpace* space(create_space("test", 4 * MB, 16 * MB, 16 * MB, nullptr));
  ASSERT_TRUE(space != nullptr);

  // Make space findable to the heap, will also delete space when runtime is cleaned up
  AddSpace(space);
  Thread* self = Thread::Current();
  ScopedObjectAccess soa(self);

  // Succeeds, fits without adjusting the max allowed footprint.
  mirror::Object* lots_of_objects[1024];
  for (size_t i = 0; i < arraysize(lots_of_objects); i++) {
    size_t allocation_size = 0;
    size_t size_of_zero_length_byte_array = SizeOfZeroLengthByteArray();
    lots_of_objects[i] = space->Alloc(self, size_of_zero_length_byte_array, &allocation_size);
    EXPECT_TRUE(lots_of_objects[i] != nullptr);
    SirtRef<mirror::Object> obj(self, lots_of_objects[i]);
    InstallClass(obj, size_of_zero_length_byte_array);
    lots_of_objects[i] = obj.get();
    EXPECT_EQ(allocation_size, space->AllocationSize(lots_of_objects[i]));
  }

  // Release memory and check pointers are nullptr.
  space->FreeList(self, arraysize(lots_of_objects), lots_of_objects);
  for (size_t i = 0; i < arraysize(lots_of_objects); i++) {
    EXPECT_TRUE(lots_of_objects[i] == nullptr);
  }

  // Succeeds, fits by adjusting the max allowed footprint.
  for (size_t i = 0; i < arraysize(lots_of_objects); i++) {
    size_t allocation_size = 0;
    lots_of_objects[i] = space->AllocWithGrowth(self, 1024, &allocation_size);
    EXPECT_TRUE(lots_of_objects[i] != nullptr);
    SirtRef<mirror::Object> obj(self, lots_of_objects[i]);
    InstallClass(obj, 1024);
    lots_of_objects[i] = obj.get();
    EXPECT_EQ(allocation_size, space->AllocationSize(lots_of_objects[i]));
  }

  // Release memory and check pointers are nullptr
  // TODO: This isn't compaction safe, fix.
  space->FreeList(self, arraysize(lots_of_objects), lots_of_objects);
  for (size_t i = 0; i < arraysize(lots_of_objects); i++) {
    EXPECT_TRUE(lots_of_objects[i] == nullptr);
  }
}

void SpaceTest::SizeFootPrintGrowthLimitAndTrimBody(MallocSpace* 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;
  }

  // The space's footprint equals amount of resources requested from system
  size_t footprint = space->GetFootprint();

  // The space must at least have its book keeping allocated
  EXPECT_GT(footprint, 0u);

  // 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 space 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<mirror::Object*[]> lots_of_objects(new mirror::Object*[max_objects]);
  size_t last_object = 0;  // last object for which allocation succeeded
  size_t amount_allocated = 0;  // amount of space allocated
  Thread* self = Thread::Current();
  ScopedObjectAccess soa(self);
  size_t rand_seed = 123456789;
  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(&rand_seed) % static_cast<size_t>(-object_size);
        // Note the minimum size, which is the size of a zero-length byte array.
        size_t size_of_zero_length_byte_array = SizeOfZeroLengthByteArray();
        if (alloc_size < size_of_zero_length_byte_array) {
          alloc_size = size_of_zero_length_byte_array;
        }
      }
      SirtRef<mirror::Object> object(self, nullptr);
      size_t bytes_allocated = 0;
      if (round <= 1) {
        object.reset(space->Alloc(self, alloc_size, &bytes_allocated));
      } else {
        object.reset(space->AllocWithGrowth(self, alloc_size, &bytes_allocated));
      }
      footprint = space->GetFootprint();
      EXPECT_GE(space->Size(), footprint);  // invariant
      if (object.get() != nullptr) {  // allocation succeeded
        InstallClass(object, alloc_size);
        lots_of_objects[i] = object.get();
        size_t allocation_size = space->AllocationSize(object.get());
        EXPECT_EQ(bytes_allocated, allocation_size);
        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) {
    {
      ScopedThreadStateChange tsc(self, kNative);
      // Give the space a haircut.
      space->Trim();
    }

    // Bounds sanity
    footprint = space->GetFootprint();
    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) {
      mirror::Object* object = lots_of_objects.get()[i];
      if (object == nullptr) {
        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(self, object);
      lots_of_objects.get()[i] = nullptr;
      amount_allocated -= allocation_size;
      footprint = space->GetFootprint();
      EXPECT_GE(space->Size(), footprint);  // invariant
    }

    free_increment >>= 1;
  }

  // The space has become empty here before allocating a large object
  // below. For RosAlloc, revoke thread-local runs, which are kept
  // even when empty for a performance reason, so that they won't
  // cause the following large object allocation to fail due to
  // potential fragmentation. Note they are normally revoked at each
  // GC (but no GC here.)
  space->RevokeAllThreadLocalBuffers();

  // All memory was released, try a large allocation to check freed memory is being coalesced
  SirtRef<mirror::Object> large_object(self, nullptr);
  size_t three_quarters_space = (growth_limit / 2) + (growth_limit / 4);
  size_t bytes_allocated = 0;
  if (round <= 1) {
    large_object.reset(space->Alloc(self, three_quarters_space, &bytes_allocated));
  } else {
    large_object.reset(space->AllocWithGrowth(self, three_quarters_space, &bytes_allocated));
  }
  EXPECT_TRUE(large_object.get() != nullptr);
  InstallClass(large_object, three_quarters_space);

  // Sanity check footprint
  footprint = space->GetFootprint();
  EXPECT_LE(footprint, growth_limit);
  EXPECT_GE(space->Size(), footprint);
  EXPECT_LE(space->Size(), growth_limit);

  // Clean up
  space->Free(self, large_object.reset(nullptr));

  // Sanity check footprint
  footprint = space->GetFootprint();
  EXPECT_LE(footprint, growth_limit);
  EXPECT_GE(space->Size(), footprint);
  EXPECT_LE(space->Size(), growth_limit);
}

void SpaceTest::SizeFootPrintGrowthLimitAndTrimDriver(size_t object_size, CreateSpaceFn create_space) {
  if (object_size < SizeOfZeroLengthByteArray()) {
    // Too small for the object layout/model.
    return;
  }
  size_t initial_size = 4 * MB;
  size_t growth_limit = 8 * MB;
  size_t capacity = 16 * MB;
  MallocSpace* space(create_space("test", initial_size, growth_limit, capacity, nullptr));
  ASSERT_TRUE(space != nullptr);

  // 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
  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, spaceName, spaceFn, size) \
  TEST_F(spaceName##Test, SizeFootPrintGrowthLimitAndTrim_AllocationsOf_##name) { \
    SizeFootPrintGrowthLimitAndTrimDriver(size, spaceFn); \
  } \
  TEST_F(spaceName##Test, SizeFootPrintGrowthLimitAndTrim_RandomAllocationsWithMax_##name) { \
    SizeFootPrintGrowthLimitAndTrimDriver(-size, spaceFn); \
  }

#define TEST_SPACE_CREATE_FN(spaceName, spaceFn) \
  class spaceName##Test : public SpaceTest { \
  }; \
  \
  TEST_F(spaceName##Test, Init) { \
    InitTestBody(spaceFn); \
  } \
  TEST_F(spaceName##Test, ZygoteSpace) { \
    ZygoteSpaceTestBody(spaceFn); \
  } \
  TEST_F(spaceName##Test, AllocAndFree) { \
    AllocAndFreeTestBody(spaceFn); \
  } \
  TEST_F(spaceName##Test, AllocAndFreeList) { \
    AllocAndFreeListTestBody(spaceFn); \
  } \
  TEST_F(spaceName##Test, SizeFootPrintGrowthLimitAndTrim_AllocationsOf_12B) { \
    SizeFootPrintGrowthLimitAndTrimDriver(12, spaceFn); \
  } \
  TEST_SizeFootPrintGrowthLimitAndTrim(16B, spaceName, spaceFn, 16) \
  TEST_SizeFootPrintGrowthLimitAndTrim(24B, spaceName, spaceFn, 24) \
  TEST_SizeFootPrintGrowthLimitAndTrim(32B, spaceName, spaceFn, 32) \
  TEST_SizeFootPrintGrowthLimitAndTrim(64B, spaceName, spaceFn, 64) \
  TEST_SizeFootPrintGrowthLimitAndTrim(128B, spaceName, spaceFn, 128) \
  TEST_SizeFootPrintGrowthLimitAndTrim(1KB, spaceName, spaceFn, 1 * KB) \
  TEST_SizeFootPrintGrowthLimitAndTrim(4KB, spaceName, spaceFn, 4 * KB) \
  TEST_SizeFootPrintGrowthLimitAndTrim(1MB, spaceName, spaceFn, 1 * MB) \
  TEST_SizeFootPrintGrowthLimitAndTrim(4MB, spaceName, spaceFn, 4 * MB) \
  TEST_SizeFootPrintGrowthLimitAndTrim(8MB, spaceName, spaceFn, 8 * MB)

}  // namespace space
}  // namespace gc
}  // namespace art

#endif  // ART_RUNTIME_GC_SPACE_SPACE_TEST_H_