test/hotspot/gtest/gc/shared/test_oopStorage.cpp
changeset 50954 f85092465b0c
parent 50513 7f166e010af4
child 52421 3021c1ad958b
equal deleted inserted replaced
50953:0fad17c646c9 50954:f85092465b0c
    50 
    50 
    51 // Access storage internals.
    51 // Access storage internals.
    52 class OopStorage::TestAccess : public AllStatic {
    52 class OopStorage::TestAccess : public AllStatic {
    53 public:
    53 public:
    54   typedef OopStorage::Block Block;
    54   typedef OopStorage::Block Block;
    55   typedef OopStorage::AllocateList AllocateList;
    55   typedef OopStorage::AllocationList AllocationList;
    56   typedef OopStorage::ActiveArray ActiveArray;
    56   typedef OopStorage::ActiveArray ActiveArray;
    57 
    57 
    58   static ActiveArray& active_array(const OopStorage& storage) {
    58   static ActiveArray& active_array(const OopStorage& storage) {
    59     return *storage._active_array;
    59     return *storage._active_array;
    60   }
    60   }
    61 
    61 
    62   static AllocateList& allocate_list(OopStorage& storage) {
    62   static AllocationList& allocation_list(OopStorage& storage) {
    63     return storage._allocate_list;
    63     return storage._allocation_list;
    64   }
    64   }
    65 
    65 
    66   static const AllocateList& allocate_list(const OopStorage& storage) {
    66   static const AllocationList& allocation_list(const OopStorage& storage) {
    67     return storage._allocate_list;
    67     return storage._allocation_list;
    68   }
    68   }
    69 
    69 
    70   static Mutex* allocate_mutex(const OopStorage& storage) {
    70   static Mutex* allocation_mutex(const OopStorage& storage) {
    71     return storage._allocate_mutex;
    71     return storage._allocation_mutex;
    72   }
    72   }
    73 
    73 
    74   static bool reduce_deferred_updates(OopStorage& storage) {
    74   static bool reduce_deferred_updates(OopStorage& storage) {
    75     return storage.reduce_deferred_updates();
    75     return storage.reduce_deferred_updates();
    76   }
    76   }
   107 
   107 
   108 // The "Oop" prefix is to avoid collision with similar opto names when
   108 // The "Oop" prefix is to avoid collision with similar opto names when
   109 // building with precompiled headers, or for consistency with that
   109 // building with precompiled headers, or for consistency with that
   110 // workaround.  There really should be an opto namespace.
   110 // workaround.  There really should be an opto namespace.
   111 typedef TestAccess::Block OopBlock;
   111 typedef TestAccess::Block OopBlock;
   112 typedef TestAccess::AllocateList AllocateList;
   112 typedef TestAccess::AllocationList AllocationList;
   113 typedef TestAccess::ActiveArray ActiveArray;
   113 typedef TestAccess::ActiveArray ActiveArray;
   114 
   114 
   115 // Using EXPECT_EQ can't use NULL directly. Otherwise AIX build breaks.
   115 // Using EXPECT_EQ can't use NULL directly. Otherwise AIX build breaks.
   116 const OopBlock* const NULL_BLOCK = NULL;
   116 const OopBlock* const NULL_BLOCK = NULL;
   117 
   117 
   118 static size_t list_length(const AllocateList& list) {
   118 static size_t list_length(const AllocationList& list) {
   119   size_t result = 0;
   119   size_t result = 0;
   120   for (const OopBlock* block = list.chead();
   120   for (const OopBlock* block = list.chead();
   121        block != NULL;
   121        block != NULL;
   122        block = list.next(*block)) {
   122        block = list.next(*block)) {
   123     ++result;
   123     ++result;
   124   }
   124   }
   125   return result;
   125   return result;
   126 }
   126 }
   127 
   127 
   128 static void clear_list(AllocateList& list) {
   128 static void clear_list(AllocationList& list) {
   129   OopBlock* next;
   129   OopBlock* next;
   130   for (OopBlock* block = list.head(); block != NULL; block = next) {
   130   for (OopBlock* block = list.head(); block != NULL; block = next) {
   131     next = list.next(*block);
   131     next = list.next(*block);
   132     list.unlink(*block);
   132     list.unlink(*block);
   133   }
   133   }
   134 }
   134 }
   135 
   135 
   136 static bool is_list_empty(const AllocateList& list) {
   136 static bool is_list_empty(const AllocationList& list) {
   137   return list.chead() == NULL;
   137   return list.chead() == NULL;
   138 }
   138 }
   139 
   139 
   140 static bool process_deferred_updates(OopStorage& storage) {
   140 static bool process_deferred_updates(OopStorage& storage) {
   141   MutexLockerEx ml(TestAccess::allocate_mutex(storage), Mutex::_no_safepoint_check_flag);
   141   MutexLockerEx ml(TestAccess::allocation_mutex(storage), Mutex::_no_safepoint_check_flag);
   142   bool result = false;
   142   bool result = false;
   143   while (TestAccess::reduce_deferred_updates(storage)) {
   143   while (TestAccess::reduce_deferred_updates(storage)) {
   144     result = true;
   144     result = true;
   145   }
   145   }
   146   return result;
   146   return result;
   153     process_deferred_updates(storage);
   153     process_deferred_updates(storage);
   154   }
   154   }
   155 }
   155 }
   156 
   156 
   157 static size_t empty_block_count(const OopStorage& storage) {
   157 static size_t empty_block_count(const OopStorage& storage) {
   158   const AllocateList& list = TestAccess::allocate_list(storage);
   158   const AllocationList& list = TestAccess::allocation_list(storage);
   159   size_t count = 0;
   159   size_t count = 0;
   160   for (const OopBlock* block = list.ctail();
   160   for (const OopBlock* block = list.ctail();
   161        (block != NULL) && block->is_empty();
   161        (block != NULL) && block->is_empty();
   162        ++count, block = list.prev(*block))
   162        ++count, block = list.prev(*block))
   163   {}
   163   {}
   181 class OopStorageTest : public ::testing::Test {
   181 class OopStorageTest : public ::testing::Test {
   182 public:
   182 public:
   183   OopStorageTest();
   183   OopStorageTest();
   184   ~OopStorageTest();
   184   ~OopStorageTest();
   185 
   185 
   186   Mutex _allocate_mutex;
   186   Mutex _allocation_mutex;
   187   Mutex _active_mutex;
   187   Mutex _active_mutex;
   188   OopStorage _storage;
   188   OopStorage _storage;
   189 
   189 
   190   static const int _active_rank = Mutex::leaf - 1;
   190   static const int _active_rank = Mutex::leaf - 1;
   191   static const int _allocate_rank = Mutex::leaf;
   191   static const int _allocate_rank = Mutex::leaf;
   193   class CountingIterateClosure;
   193   class CountingIterateClosure;
   194   template<bool is_const> class VM_CountAtSafepoint;
   194   template<bool is_const> class VM_CountAtSafepoint;
   195 };
   195 };
   196 
   196 
   197 OopStorageTest::OopStorageTest() :
   197 OopStorageTest::OopStorageTest() :
   198   _allocate_mutex(_allocate_rank,
   198   _allocation_mutex(_allocate_rank,
   199                   "test_OopStorage_allocate",
   199                     "test_OopStorage_allocation",
   200                   false,
   200                     false,
   201                   Mutex::_safepoint_check_never),
   201                     Mutex::_safepoint_check_never),
   202   _active_mutex(_active_rank,
   202   _active_mutex(_active_rank,
   203                 "test_OopStorage_active",
   203                 "test_OopStorage_active",
   204                 false,
   204                 false,
   205                 Mutex::_safepoint_check_never),
   205                 Mutex::_safepoint_check_never),
   206   _storage("Test Storage", &_allocate_mutex, &_active_mutex)
   206   _storage("Test Storage", &_allocation_mutex, &_active_mutex)
   207 { }
   207 { }
   208 
   208 
   209 OopStorageTest::~OopStorageTest() {
   209 OopStorageTest::~OopStorageTest() {
   210   clear_list(TestAccess::allocate_list(_storage));
   210   clear_list(TestAccess::allocation_list(_storage));
   211 }
   211 }
   212 
   212 
   213 class OopStorageTestWithAllocation : public OopStorageTest {
   213 class OopStorageTestWithAllocation : public OopStorageTest {
   214 public:
   214 public:
   215   OopStorageTestWithAllocation();
   215   OopStorageTestWithAllocation();
   241 
   241 
   242 private:
   242 private:
   243   OopStorage* _storage;
   243   OopStorage* _storage;
   244 };
   244 };
   245 
   245 
   246 static bool is_allocate_list_sorted(const OopStorage& storage) {
   246 static bool is_allocation_list_sorted(const OopStorage& storage) {
   247   // The allocate_list isn't strictly sorted.  Rather, all empty
   247   // The allocation_list isn't strictly sorted.  Rather, all empty
   248   // blocks are segregated to the end of the list.
   248   // blocks are segregated to the end of the list.
   249   const AllocateList& list = TestAccess::allocate_list(storage);
   249   const AllocationList& list = TestAccess::allocation_list(storage);
   250   const OopBlock* block = list.ctail();
   250   const OopBlock* block = list.ctail();
   251   for ( ; (block != NULL) && block->is_empty(); block = list.prev(*block)) {}
   251   for ( ; (block != NULL) && block->is_empty(); block = list.prev(*block)) {}
   252   for ( ; block != NULL; block = list.prev(*block)) {
   252   for ( ; block != NULL; block = list.prev(*block)) {
   253     if (block->is_empty()) {
   253     if (block->is_empty()) {
   254       return false;
   254       return false;
   267   return total_count;
   267   return total_count;
   268 }
   268 }
   269 
   269 
   270 TEST_VM_F(OopStorageTest, allocate_one) {
   270 TEST_VM_F(OopStorageTest, allocate_one) {
   271   EXPECT_EQ(0u, active_count(_storage));
   271   EXPECT_EQ(0u, active_count(_storage));
   272   EXPECT_TRUE(is_list_empty(TestAccess::allocate_list(_storage)));
   272   EXPECT_TRUE(is_list_empty(TestAccess::allocation_list(_storage)));
   273 
   273 
   274   oop* ptr = _storage.allocate();
   274   oop* ptr = _storage.allocate();
   275   EXPECT_TRUE(ptr != NULL);
   275   EXPECT_TRUE(ptr != NULL);
   276   EXPECT_EQ(1u, _storage.allocation_count());
   276   EXPECT_EQ(1u, _storage.allocation_count());
   277 
   277 
   278   EXPECT_EQ(1u, active_count(_storage));
   278   EXPECT_EQ(1u, active_count(_storage));
   279   EXPECT_EQ(1u, _storage.block_count());
   279   EXPECT_EQ(1u, _storage.block_count());
   280   EXPECT_EQ(1u, list_length(TestAccess::allocate_list(_storage)));
   280   EXPECT_EQ(1u, list_length(TestAccess::allocation_list(_storage)));
   281 
   281 
   282   EXPECT_EQ(0u, empty_block_count(_storage));
   282   EXPECT_EQ(0u, empty_block_count(_storage));
   283 
   283 
   284   const OopBlock* block = TestAccess::allocate_list(_storage).chead();
   284   const OopBlock* block = TestAccess::allocation_list(_storage).chead();
   285   EXPECT_NE(block, (OopBlock*)NULL);
   285   EXPECT_NE(block, (OopBlock*)NULL);
   286   EXPECT_EQ(block, active_head(_storage));
   286   EXPECT_EQ(block, active_head(_storage));
   287   EXPECT_FALSE(TestAccess::block_is_empty(*block));
   287   EXPECT_FALSE(TestAccess::block_is_empty(*block));
   288   EXPECT_FALSE(TestAccess::block_is_full(*block));
   288   EXPECT_FALSE(TestAccess::block_is_full(*block));
   289   EXPECT_EQ(1u, TestAccess::block_allocation_count(*block));
   289   EXPECT_EQ(1u, TestAccess::block_allocation_count(*block));
   291   release_entry(_storage, ptr);
   291   release_entry(_storage, ptr);
   292   EXPECT_EQ(0u, _storage.allocation_count());
   292   EXPECT_EQ(0u, _storage.allocation_count());
   293 
   293 
   294   EXPECT_EQ(1u, active_count(_storage));
   294   EXPECT_EQ(1u, active_count(_storage));
   295   EXPECT_EQ(1u, _storage.block_count());
   295   EXPECT_EQ(1u, _storage.block_count());
   296   EXPECT_EQ(1u, list_length(TestAccess::allocate_list(_storage)));
   296   EXPECT_EQ(1u, list_length(TestAccess::allocation_list(_storage)));
   297 
   297 
   298   EXPECT_EQ(1u, empty_block_count(_storage));
   298   EXPECT_EQ(1u, empty_block_count(_storage));
   299 
   299 
   300   const OopBlock* new_block = TestAccess::allocate_list(_storage).chead();
   300   const OopBlock* new_block = TestAccess::allocation_list(_storage).chead();
   301   EXPECT_EQ(block, new_block);
   301   EXPECT_EQ(block, new_block);
   302   EXPECT_EQ(block, active_head(_storage));
   302   EXPECT_EQ(block, active_head(_storage));
   303   EXPECT_TRUE(TestAccess::block_is_empty(*block));
   303   EXPECT_TRUE(TestAccess::block_is_empty(*block));
   304   EXPECT_FALSE(TestAccess::block_is_full(*block));
   304   EXPECT_FALSE(TestAccess::block_is_full(*block));
   305   EXPECT_EQ(0u, TestAccess::block_allocation_count(*block));
   305   EXPECT_EQ(0u, TestAccess::block_allocation_count(*block));
   307 
   307 
   308 TEST_VM_F(OopStorageTest, allocation_count) {
   308 TEST_VM_F(OopStorageTest, allocation_count) {
   309   static const size_t max_entries = 1000;
   309   static const size_t max_entries = 1000;
   310   oop* entries[max_entries];
   310   oop* entries[max_entries];
   311 
   311 
   312   AllocateList& allocate_list = TestAccess::allocate_list(_storage);
   312   AllocationList& allocation_list = TestAccess::allocation_list(_storage);
   313 
   313 
   314   EXPECT_EQ(0u, active_count(_storage));
   314   EXPECT_EQ(0u, active_count(_storage));
   315   EXPECT_EQ(0u, _storage.block_count());
   315   EXPECT_EQ(0u, _storage.block_count());
   316   EXPECT_TRUE(is_list_empty(allocate_list));
   316   EXPECT_TRUE(is_list_empty(allocation_list));
   317 
   317 
   318   size_t allocated = 0;
   318   size_t allocated = 0;
   319   for ( ; allocated < max_entries; ++allocated) {
   319   for ( ; allocated < max_entries; ++allocated) {
   320     EXPECT_EQ(allocated, _storage.allocation_count());
   320     EXPECT_EQ(allocated, _storage.allocation_count());
   321     if (active_count(_storage) != 0) {
   321     if (active_count(_storage) != 0) {
   324       const OopBlock& block = *TestAccess::active_array(_storage).at(0);
   324       const OopBlock& block = *TestAccess::active_array(_storage).at(0);
   325       EXPECT_EQ(allocated, TestAccess::block_allocation_count(block));
   325       EXPECT_EQ(allocated, TestAccess::block_allocation_count(block));
   326       if (TestAccess::block_is_full(block)) {
   326       if (TestAccess::block_is_full(block)) {
   327         break;
   327         break;
   328       } else {
   328       } else {
   329         EXPECT_FALSE(is_list_empty(allocate_list));
   329         EXPECT_FALSE(is_list_empty(allocation_list));
   330         EXPECT_EQ(&block, allocate_list.chead());
   330         EXPECT_EQ(&block, allocation_list.chead());
   331       }
   331       }
   332     }
   332     }
   333     entries[allocated] = _storage.allocate();
   333     entries[allocated] = _storage.allocate();
   334   }
   334   }
   335 
   335 
   336   EXPECT_EQ(allocated, _storage.allocation_count());
   336   EXPECT_EQ(allocated, _storage.allocation_count());
   337   EXPECT_EQ(1u, active_count(_storage));
   337   EXPECT_EQ(1u, active_count(_storage));
   338   EXPECT_EQ(1u, _storage.block_count());
   338   EXPECT_EQ(1u, _storage.block_count());
   339   EXPECT_TRUE(is_list_empty(allocate_list));
   339   EXPECT_TRUE(is_list_empty(allocation_list));
   340   const OopBlock& block = *TestAccess::active_array(_storage).at(0);
   340   const OopBlock& block = *TestAccess::active_array(_storage).at(0);
   341   EXPECT_TRUE(TestAccess::block_is_full(block));
   341   EXPECT_TRUE(TestAccess::block_is_full(block));
   342   EXPECT_EQ(allocated, TestAccess::block_allocation_count(block));
   342   EXPECT_EQ(allocated, TestAccess::block_allocation_count(block));
   343 
   343 
   344   for (size_t i = 0; i < allocated; ++i) {
   344   for (size_t i = 0; i < allocated; ++i) {
   345     release_entry(_storage, entries[i]);
   345     release_entry(_storage, entries[i]);
   346     size_t remaining = allocated - (i + 1);
   346     size_t remaining = allocated - (i + 1);
   347     EXPECT_EQ(remaining, TestAccess::block_allocation_count(block));
   347     EXPECT_EQ(remaining, TestAccess::block_allocation_count(block));
   348     EXPECT_EQ(remaining, _storage.allocation_count());
   348     EXPECT_EQ(remaining, _storage.allocation_count());
   349     EXPECT_FALSE(is_list_empty(allocate_list));
   349     EXPECT_FALSE(is_list_empty(allocation_list));
   350   }
   350   }
   351 }
   351 }
   352 
   352 
   353 TEST_VM_F(OopStorageTest, allocate_many) {
   353 TEST_VM_F(OopStorageTest, allocate_many) {
   354   static const size_t max_entries = 1000;
   354   static const size_t max_entries = 1000;
   355   oop* entries[max_entries];
   355   oop* entries[max_entries];
   356 
   356 
   357   AllocateList& allocate_list = TestAccess::allocate_list(_storage);
   357   AllocationList& allocation_list = TestAccess::allocation_list(_storage);
   358 
   358 
   359   EXPECT_EQ(0u, empty_block_count(_storage));
   359   EXPECT_EQ(0u, empty_block_count(_storage));
   360 
   360 
   361   entries[0] = _storage.allocate();
   361   entries[0] = _storage.allocate();
   362   ASSERT_TRUE(entries[0] != NULL);
   362   ASSERT_TRUE(entries[0] != NULL);
   363   EXPECT_EQ(1u, active_count(_storage));
   363   EXPECT_EQ(1u, active_count(_storage));
   364   EXPECT_EQ(1u, _storage.block_count());
   364   EXPECT_EQ(1u, _storage.block_count());
   365   EXPECT_EQ(1u, list_length(allocate_list));
   365   EXPECT_EQ(1u, list_length(allocation_list));
   366   EXPECT_EQ(0u, empty_block_count(_storage));
   366   EXPECT_EQ(0u, empty_block_count(_storage));
   367 
   367 
   368   const OopBlock* block = TestAccess::active_array(_storage).at(0);
   368   const OopBlock* block = TestAccess::active_array(_storage).at(0);
   369   EXPECT_EQ(1u, TestAccess::block_allocation_count(*block));
   369   EXPECT_EQ(1u, TestAccess::block_allocation_count(*block));
   370   EXPECT_EQ(block, allocate_list.chead());
   370   EXPECT_EQ(block, allocation_list.chead());
   371 
   371 
   372   for (size_t i = 1; i < max_entries; ++i) {
   372   for (size_t i = 1; i < max_entries; ++i) {
   373     entries[i] = _storage.allocate();
   373     entries[i] = _storage.allocate();
   374     EXPECT_EQ(i + 1, _storage.allocation_count());
   374     EXPECT_EQ(i + 1, _storage.allocation_count());
   375     ASSERT_TRUE(entries[i] != NULL);
   375     ASSERT_TRUE(entries[i] != NULL);
   376     EXPECT_EQ(0u, empty_block_count(_storage));
   376     EXPECT_EQ(0u, empty_block_count(_storage));
   377 
   377 
   378     if (block == NULL) {
   378     if (block == NULL) {
   379       ASSERT_FALSE(is_list_empty(allocate_list));
   379       ASSERT_FALSE(is_list_empty(allocation_list));
   380       EXPECT_EQ(1u, list_length(allocate_list));
   380       EXPECT_EQ(1u, list_length(allocation_list));
   381       block = allocate_list.chead();
   381       block = allocation_list.chead();
   382       EXPECT_EQ(1u, TestAccess::block_allocation_count(*block));
   382       EXPECT_EQ(1u, TestAccess::block_allocation_count(*block));
   383       EXPECT_EQ(block, active_head(_storage));
   383       EXPECT_EQ(block, active_head(_storage));
   384     } else if (TestAccess::block_is_full(*block)) {
   384     } else if (TestAccess::block_is_full(*block)) {
   385       EXPECT_TRUE(is_list_empty(allocate_list));
   385       EXPECT_TRUE(is_list_empty(allocation_list));
   386       block = NULL;
   386       block = NULL;
   387     } else {
   387     } else {
   388       EXPECT_FALSE(is_list_empty(allocate_list));
   388       EXPECT_FALSE(is_list_empty(allocation_list));
   389       EXPECT_EQ(block, allocate_list.chead());
   389       EXPECT_EQ(block, allocation_list.chead());
   390       EXPECT_EQ(block, active_head(_storage));
   390       EXPECT_EQ(block, active_head(_storage));
   391     }
   391     }
   392   }
   392   }
   393 
   393 
   394   if (block != NULL) {
   394   if (block != NULL) {
   395     EXPECT_NE(0u, TestAccess::block_allocation_count(*block));
   395     EXPECT_NE(0u, TestAccess::block_allocation_count(*block));
   396     EXPECT_FALSE(is_list_empty(allocate_list));
   396     EXPECT_FALSE(is_list_empty(allocation_list));
   397     EXPECT_EQ(block, allocate_list.chead());
   397     EXPECT_EQ(block, allocation_list.chead());
   398     EXPECT_EQ(block, active_head(_storage));
   398     EXPECT_EQ(block, active_head(_storage));
   399   }
   399   }
   400 
   400 
   401   for (size_t i = 0; i < max_entries; ++i) {
   401   for (size_t i = 0; i < max_entries; ++i) {
   402     release_entry(_storage, entries[i]);
   402     release_entry(_storage, entries[i]);
   403     EXPECT_TRUE(is_allocate_list_sorted(_storage));
   403     EXPECT_TRUE(is_allocation_list_sorted(_storage));
   404     EXPECT_EQ(max_entries - (i + 1), total_allocation_count(_storage));
   404     EXPECT_EQ(max_entries - (i + 1), total_allocation_count(_storage));
   405   }
   405   }
   406 
   406 
   407   EXPECT_EQ(active_count(_storage), list_length(allocate_list));
   407   EXPECT_EQ(active_count(_storage), list_length(allocation_list));
   408   EXPECT_EQ(active_count(_storage), _storage.block_count());
   408   EXPECT_EQ(active_count(_storage), _storage.block_count());
   409   EXPECT_EQ(active_count(_storage), empty_block_count(_storage));
   409   EXPECT_EQ(active_count(_storage), empty_block_count(_storage));
   410   for (const OopBlock* block = allocate_list.chead();
   410   for (const OopBlock* block = allocation_list.chead();
   411        block != NULL;
   411        block != NULL;
   412        block = allocate_list.next(*block)) {
   412        block = allocation_list.next(*block)) {
   413     EXPECT_TRUE(TestAccess::block_is_empty(*block));
   413     EXPECT_TRUE(TestAccess::block_is_empty(*block));
   414   }
   414   }
   415 }
   415 }
   416 
   416 
   417 TEST_VM_F(OopStorageTestWithAllocation, random_release) {
   417 TEST_VM_F(OopStorageTestWithAllocation, random_release) {
   418   static const size_t step = 11;
   418   static const size_t step = 11;
   419   ASSERT_NE(0u, _max_entries % step); // max_entries and step are mutually prime
   419   ASSERT_NE(0u, _max_entries % step); // max_entries and step are mutually prime
   420 
   420 
   421   EXPECT_EQ(0u, empty_block_count(_storage));
   421   EXPECT_EQ(0u, empty_block_count(_storage));
   422 
   422 
   423   AllocateList& allocate_list = TestAccess::allocate_list(_storage);
   423   AllocationList& allocation_list = TestAccess::allocation_list(_storage);
   424 
   424 
   425   EXPECT_EQ(_max_entries, total_allocation_count(_storage));
   425   EXPECT_EQ(_max_entries, total_allocation_count(_storage));
   426   EXPECT_GE(1u, list_length(allocate_list));
   426   EXPECT_GE(1u, list_length(allocation_list));
   427 
   427 
   428   // Release all entries in "random" order.
   428   // Release all entries in "random" order.
   429   size_t released = 0;
   429   size_t released = 0;
   430   for (size_t i = 0; released < _max_entries; i = (i + step) % _max_entries) {
   430   for (size_t i = 0; released < _max_entries; i = (i + step) % _max_entries) {
   431     if (_entries[i] != NULL) {
   431     if (_entries[i] != NULL) {
   432       release_entry(_storage, _entries[i]);
   432       release_entry(_storage, _entries[i]);
   433       _entries[i] = NULL;
   433       _entries[i] = NULL;
   434       ++released;
   434       ++released;
   435       EXPECT_EQ(_max_entries - released, total_allocation_count(_storage));
   435       EXPECT_EQ(_max_entries - released, total_allocation_count(_storage));
   436       EXPECT_TRUE(is_allocate_list_sorted(_storage));
   436       EXPECT_TRUE(is_allocation_list_sorted(_storage));
   437     }
   437     }
   438   }
   438   }
   439 
   439 
   440   EXPECT_EQ(active_count(_storage), list_length(allocate_list));
   440   EXPECT_EQ(active_count(_storage), list_length(allocation_list));
   441   EXPECT_EQ(active_count(_storage), _storage.block_count());
   441   EXPECT_EQ(active_count(_storage), _storage.block_count());
   442   EXPECT_EQ(0u, total_allocation_count(_storage));
   442   EXPECT_EQ(0u, total_allocation_count(_storage));
   443   EXPECT_EQ(list_length(allocate_list), empty_block_count(_storage));
   443   EXPECT_EQ(list_length(allocation_list), empty_block_count(_storage));
   444 }
   444 }
   445 
   445 
   446 TEST_VM_F(OopStorageTestWithAllocation, random_allocate_release) {
   446 TEST_VM_F(OopStorageTestWithAllocation, random_allocate_release) {
   447   static const size_t release_step = 11;
   447   static const size_t release_step = 11;
   448   static const size_t allocate_step = 5;
   448   static const size_t allocate_step = 5;
   449   ASSERT_NE(0u, _max_entries % release_step); // max_entries and step are mutually prime
   449   ASSERT_NE(0u, _max_entries % release_step); // max_entries and step are mutually prime
   450 
   450 
   451   EXPECT_EQ(0u, empty_block_count(_storage));
   451   EXPECT_EQ(0u, empty_block_count(_storage));
   452 
   452 
   453   AllocateList& allocate_list = TestAccess::allocate_list(_storage);
   453   AllocationList& allocation_list = TestAccess::allocation_list(_storage);
   454 
   454 
   455   EXPECT_EQ(_max_entries, total_allocation_count(_storage));
   455   EXPECT_EQ(_max_entries, total_allocation_count(_storage));
   456   EXPECT_GE(1u, list_length(allocate_list));
   456   EXPECT_GE(1u, list_length(allocation_list));
   457 
   457 
   458   // Release all entries in "random" order, "randomly" interspersed
   458   // Release all entries in "random" order, "randomly" interspersed
   459   // with additional allocations.
   459   // with additional allocations.
   460   size_t released = 0;
   460   size_t released = 0;
   461   size_t total_released = 0;
   461   size_t total_released = 0;
   464       release_entry(_storage, _entries[i]);
   464       release_entry(_storage, _entries[i]);
   465       _entries[i] = NULL;
   465       _entries[i] = NULL;
   466       ++released;
   466       ++released;
   467       ++total_released;
   467       ++total_released;
   468       EXPECT_EQ(_max_entries - released, total_allocation_count(_storage));
   468       EXPECT_EQ(_max_entries - released, total_allocation_count(_storage));
   469       EXPECT_TRUE(is_allocate_list_sorted(_storage));
   469       EXPECT_TRUE(is_allocation_list_sorted(_storage));
   470       if (total_released % allocate_step == 0) {
   470       if (total_released % allocate_step == 0) {
   471         _entries[i] = _storage.allocate();
   471         _entries[i] = _storage.allocate();
   472         --released;
   472         --released;
   473         EXPECT_EQ(_max_entries - released, total_allocation_count(_storage));
   473         EXPECT_EQ(_max_entries - released, total_allocation_count(_storage));
   474         EXPECT_TRUE(is_allocate_list_sorted(_storage));
   474         EXPECT_TRUE(is_allocation_list_sorted(_storage));
   475       }
   475       }
   476     }
   476     }
   477   }
   477   }
   478 
   478 
   479   EXPECT_EQ(active_count(_storage), list_length(allocate_list));
   479   EXPECT_EQ(active_count(_storage), list_length(allocation_list));
   480   EXPECT_EQ(active_count(_storage), _storage.block_count());
   480   EXPECT_EQ(active_count(_storage), _storage.block_count());
   481   EXPECT_EQ(0u, total_allocation_count(_storage));
   481   EXPECT_EQ(0u, total_allocation_count(_storage));
   482   EXPECT_EQ(list_length(allocate_list), empty_block_count(_storage));
   482   EXPECT_EQ(list_length(allocation_list), empty_block_count(_storage));
   483 }
   483 }
   484 
   484 
   485 template<bool sorted>
   485 template<bool sorted>
   486 class OopStorageTestBlockRelease : public OopStorageTestWithAllocation {
   486 class OopStorageTestBlockRelease : public OopStorageTestWithAllocation {
   487 public:
   487 public:
  1198 };
  1198 };
  1199 
  1199 
  1200 const size_t OopStorageBlockCollectionTest::nvalues;
  1200 const size_t OopStorageBlockCollectionTest::nvalues;
  1201 const void* const OopStorageBlockCollectionTest::_pseudo_owner[] = {};
  1201 const void* const OopStorageBlockCollectionTest::_pseudo_owner[] = {};
  1202 
  1202 
  1203 class OopStorageAllocateListTest : public OopStorageBlockCollectionTest {};
  1203 class OopStorageAllocationListTest : public OopStorageBlockCollectionTest {};
  1204 
  1204 
  1205 TEST_F(OopStorageAllocateListTest, empty_list) {
  1205 TEST_F(OopStorageAllocationListTest, empty_list) {
  1206   AllocateList list;
  1206   AllocationList list;
  1207 
  1207 
  1208   EXPECT_TRUE(is_list_empty(list));
  1208   EXPECT_TRUE(is_list_empty(list));
  1209   EXPECT_EQ(NULL_BLOCK, list.head());
  1209   EXPECT_EQ(NULL_BLOCK, list.head());
  1210   EXPECT_EQ(NULL_BLOCK, list.chead());
  1210   EXPECT_EQ(NULL_BLOCK, list.chead());
  1211   EXPECT_EQ(NULL_BLOCK, list.ctail());
  1211   EXPECT_EQ(NULL_BLOCK, list.ctail());
  1212 }
  1212 }
  1213 
  1213 
  1214 TEST_F(OopStorageAllocateListTest, push_back) {
  1214 TEST_F(OopStorageAllocationListTest, push_back) {
  1215   AllocateList list;
  1215   AllocationList list;
  1216 
  1216 
  1217   for (size_t i = 0; i < nvalues; ++i) {
  1217   for (size_t i = 0; i < nvalues; ++i) {
  1218     list.push_back(*values[i]);
  1218     list.push_back(*values[i]);
  1219     EXPECT_FALSE(is_list_empty(list));
  1219     EXPECT_FALSE(is_list_empty(list));
  1220     EXPECT_EQ(list.ctail(), values[i]);
  1220     EXPECT_EQ(list.ctail(), values[i]);
  1239   EXPECT_EQ(NULL_BLOCK, block);
  1239   EXPECT_EQ(NULL_BLOCK, block);
  1240 
  1240 
  1241   clear_list(list);
  1241   clear_list(list);
  1242 }
  1242 }
  1243 
  1243 
  1244 TEST_F(OopStorageAllocateListTest, push_front) {
  1244 TEST_F(OopStorageAllocationListTest, push_front) {
  1245   AllocateList list;
  1245   AllocationList list;
  1246 
  1246 
  1247   for (size_t i = 0; i < nvalues; ++i) {
  1247   for (size_t i = 0; i < nvalues; ++i) {
  1248     list.push_front(*values[i]);
  1248     list.push_front(*values[i]);
  1249     EXPECT_FALSE(is_list_empty(list));
  1249     EXPECT_FALSE(is_list_empty(list));
  1250     EXPECT_EQ(list.head(), values[i]);
  1250     EXPECT_EQ(list.head(), values[i]);
  1269   EXPECT_EQ(NULL_BLOCK, block);
  1269   EXPECT_EQ(NULL_BLOCK, block);
  1270 
  1270 
  1271   clear_list(list);
  1271   clear_list(list);
  1272 }
  1272 }
  1273 
  1273 
  1274 class OopStorageAllocateListTestWithList : public OopStorageAllocateListTest {
  1274 class OopStorageAllocationListTestWithList : public OopStorageAllocationListTest {
  1275 public:
  1275 public:
  1276   OopStorageAllocateListTestWithList() : list() {
  1276   OopStorageAllocationListTestWithList() : list() {
  1277     for (size_t i = 0; i < nvalues; ++i) {
  1277     for (size_t i = 0; i < nvalues; ++i) {
  1278       list.push_back(*values[i]);
  1278       list.push_back(*values[i]);
  1279     }
  1279     }
  1280   }
  1280   }
  1281 
  1281 
  1282   ~OopStorageAllocateListTestWithList() {
  1282   ~OopStorageAllocationListTestWithList() {
  1283     clear_list(list);
  1283     clear_list(list);
  1284   }
  1284   }
  1285 
  1285 
  1286   AllocateList list;
  1286   AllocationList list;
  1287 };
  1287 };
  1288 
  1288 
  1289 TEST_F(OopStorageAllocateListTestWithList, unlink_front) {
  1289 TEST_F(OopStorageAllocationListTestWithList, unlink_front) {
  1290   EXPECT_EQ(list.chead(), values[0]);
  1290   EXPECT_EQ(list.chead(), values[0]);
  1291   EXPECT_EQ(list.ctail(), values[nvalues - 1]);
  1291   EXPECT_EQ(list.ctail(), values[nvalues - 1]);
  1292 
  1292 
  1293   list.unlink(*values[0]);
  1293   list.unlink(*values[0]);
  1294   EXPECT_EQ(NULL_BLOCK, list.next(*values[0]));
  1294   EXPECT_EQ(NULL_BLOCK, list.next(*values[0]));
  1302     block = list.next(*block);
  1302     block = list.next(*block);
  1303   }
  1303   }
  1304   EXPECT_EQ(NULL_BLOCK, block);
  1304   EXPECT_EQ(NULL_BLOCK, block);
  1305 }
  1305 }
  1306 
  1306 
  1307 TEST_F(OopStorageAllocateListTestWithList, unlink_back) {
  1307 TEST_F(OopStorageAllocationListTestWithList, unlink_back) {
  1308   EXPECT_EQ(list.chead(), values[0]);
  1308   EXPECT_EQ(list.chead(), values[0]);
  1309 
  1309 
  1310   list.unlink(*values[nvalues - 1]);
  1310   list.unlink(*values[nvalues - 1]);
  1311   EXPECT_EQ(NULL_BLOCK, list.next(*values[nvalues - 1]));
  1311   EXPECT_EQ(NULL_BLOCK, list.next(*values[nvalues - 1]));
  1312   EXPECT_EQ(NULL_BLOCK, list.prev(*values[nvalues - 1]));
  1312   EXPECT_EQ(NULL_BLOCK, list.prev(*values[nvalues - 1]));
  1319     block = list.next(*block);
  1319     block = list.next(*block);
  1320   }
  1320   }
  1321   EXPECT_EQ(NULL_BLOCK, block);
  1321   EXPECT_EQ(NULL_BLOCK, block);
  1322 }
  1322 }
  1323 
  1323 
  1324 TEST_F(OopStorageAllocateListTestWithList, unlink_middle) {
  1324 TEST_F(OopStorageAllocationListTestWithList, unlink_middle) {
  1325   EXPECT_EQ(list.chead(), values[0]);
  1325   EXPECT_EQ(list.chead(), values[0]);
  1326 
  1326 
  1327   size_t index = nvalues / 2;
  1327   size_t index = nvalues / 2;
  1328 
  1328 
  1329   list.unlink(*values[index]);
  1329   list.unlink(*values[index]);
  1342     block = list.next(*block);
  1342     block = list.next(*block);
  1343   }
  1343   }
  1344   EXPECT_EQ(NULL_BLOCK, block);
  1344   EXPECT_EQ(NULL_BLOCK, block);
  1345 }
  1345 }
  1346 
  1346 
  1347 TEST_F(OopStorageAllocateListTest, single) {
  1347 TEST_F(OopStorageAllocationListTest, single) {
  1348   AllocateList list;
  1348   AllocationList list;
  1349 
  1349 
  1350   list.push_back(*values[0]);
  1350   list.push_back(*values[0]);
  1351   EXPECT_EQ(NULL_BLOCK, list.next(*values[0]));
  1351   EXPECT_EQ(NULL_BLOCK, list.next(*values[0]));
  1352   EXPECT_EQ(NULL_BLOCK, list.prev(*values[0]));
  1352   EXPECT_EQ(NULL_BLOCK, list.prev(*values[0]));
  1353   EXPECT_EQ(list.chead(), values[0]);
  1353   EXPECT_EQ(list.chead(), values[0]);