1 /*
   2  * Copyright (c) 2018, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.
   8  *
   9  * This code is distributed in the hope that it will be useful, but WITHOUT
  10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  11  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  12  * version 2 for more details (a copy is included in the LICENSE file that
  13  * accompanied this code).
  14  *
  15  * You should have received a copy of the GNU General Public License version
  16  * 2 along with this work; if not, write to the Free Software Foundation,
  17  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  18  *
  19  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  20  * or visit www.oracle.com if you need additional information or have any
  21  * questions.
  22  */
  23 
  24 #include "precompiled.hpp"
  25 #include "gc/shared/oopStorage.inline.hpp"
  26 #include "gc/shared/oopStorageParState.inline.hpp"
  27 #include "gc/shared/workgroup.hpp"
  28 #include "memory/allocation.inline.hpp"
  29 #include "memory/resourceArea.hpp"
  30 #include "metaprogramming/conditional.hpp"
  31 #include "metaprogramming/enableIf.hpp"
  32 #include "runtime/handles.inline.hpp"
  33 #include "runtime/interfaceSupport.inline.hpp"
  34 #include "runtime/mutex.hpp"
  35 #include "runtime/mutexLocker.hpp"
  36 #include "runtime/thread.hpp"
  37 #include "runtime/vm_operations.hpp"
  38 #include "runtime/vmThread.hpp"
  39 #include "utilities/align.hpp"
  40 #include "utilities/ostream.hpp"
  41 #include "utilities/quickSort.hpp"
  42 #include "unittest.hpp"
  43 
  44 // --- FIXME: Disable some tests on 32bit Windows, because SafeFetch
  45 //     (which is used by allocation_status) doesn't currently provide
  46 //     protection in the context where gtests are run; see JDK-8185734.
  47 #ifdef _WIN32
  48 #define DISABLE_GARBAGE_ALLOCATION_STATUS_TESTS
  49 #endif
  50 
  51 // Access storage internals.
  52 class OopStorage::TestAccess : public AllStatic {
  53 public:
  54   typedef OopStorage::Block Block;
  55   typedef OopStorage::BlockList BlockList;
  56 
  57   static BlockList& active_list(OopStorage& storage) {
  58     return storage._active_list;
  59   }
  60 
  61   static BlockList& allocate_list(OopStorage& storage) {
  62     return storage._allocate_list;
  63   }
  64 
  65   static const BlockList& allocate_list(const OopStorage& storage) {
  66     return storage._allocate_list;
  67   }
  68 
  69   static Mutex* allocate_mutex(const OopStorage& storage) {
  70     return storage._allocate_mutex;
  71   }
  72 
  73   static bool reduce_deferred_updates(OopStorage& storage) {
  74     return storage.reduce_deferred_updates();
  75   }
  76 
  77   static bool block_is_empty(const Block& block) {
  78     return block.is_empty();
  79   }
  80 
  81   static bool block_is_full(const Block& block) {
  82     return block.is_full();
  83   }
  84 
  85   static unsigned block_allocation_count(const Block& block) {
  86     uintx bitmask = block.allocated_bitmask();
  87     unsigned count = 0;
  88     for ( ; bitmask != 0; bitmask >>= 1) {
  89       if ((bitmask & 1) != 0) {
  90         ++count;
  91       }
  92     }
  93     return count;
  94   }
  95 
  96   static size_t memory_per_block() {
  97     return Block::allocation_size();
  98   }
  99 };
 100 
 101 typedef OopStorage::TestAccess TestAccess;
 102 // --- FIXME: Should be just Block, but that collides with opto Block
 103 //     when building with precompiled headers.  There really should be
 104 //     an opto namespace.
 105 typedef TestAccess::Block OopBlock;
 106 // --- FIXME: Similarly, this typedef collides with opto BlockList.
 107 // typedef TestAccess::BlockList BlockList;
 108 
 109 // Using EXPECT_EQ can't use NULL directly. Otherwise AIX build breaks.
 110 const OopBlock* const NULL_BLOCK = NULL;
 111 
 112 static size_t list_length(const TestAccess::BlockList& list) {
 113   size_t result = 0;
 114   for (const OopBlock* block = list.chead();
 115        block != NULL;
 116        block = list.next(*block)) {
 117     ++result;
 118   }
 119   return result;
 120 }
 121 
 122 static void clear_list(TestAccess::BlockList& list) {
 123   OopBlock* next;
 124   for (OopBlock* block = list.head(); block != NULL; block = next) {
 125     next = list.next(*block);
 126     list.unlink(*block);
 127   }
 128 }
 129 
 130 static bool is_list_empty(const TestAccess::BlockList& list) {
 131   return list.chead() == NULL;
 132 }
 133 
 134 static bool process_deferred_updates(OopStorage& storage) {
 135   MutexLockerEx ml(TestAccess::allocate_mutex(storage), Mutex::_no_safepoint_check_flag);
 136   bool result = false;
 137   while (TestAccess::reduce_deferred_updates(storage)) {
 138     result = true;
 139   }
 140   return result;
 141 }
 142 
 143 static void release_entry(OopStorage& storage, oop* entry, bool process_deferred = true) {
 144   *entry = NULL;
 145   storage.release(entry);
 146   if (process_deferred) {
 147     process_deferred_updates(storage);
 148   }
 149 }
 150 
 151 static size_t empty_block_count(const OopStorage& storage) {
 152   const TestAccess::BlockList& list = TestAccess::allocate_list(storage);
 153   size_t count = 0;
 154   for (const OopBlock* block = list.ctail();
 155        (block != NULL) && block->is_empty();
 156        ++count, block = list.prev(*block))
 157   {}
 158   return count;
 159 }
 160 
 161 class OopStorageTest : public ::testing::Test {
 162 public:
 163   OopStorageTest();
 164   ~OopStorageTest();
 165 
 166   Mutex _allocate_mutex;
 167   Mutex _active_mutex;
 168   OopStorage _storage;
 169 
 170   static const int _active_rank = Mutex::leaf - 1;
 171   static const int _allocate_rank = Mutex::leaf;
 172 
 173   class CountingIterateClosure;
 174   template<bool is_const> class VM_CountAtSafepoint;
 175 };
 176 
 177 OopStorageTest::OopStorageTest() :
 178   _allocate_mutex(_allocate_rank,
 179                   "test_OopStorage_allocate",
 180                   false,
 181                   Mutex::_safepoint_check_never),
 182   _active_mutex(_active_rank,
 183                 "test_OopStorage_active",
 184                 false,
 185                 Mutex::_safepoint_check_never),
 186   _storage("Test Storage", &_allocate_mutex, &_active_mutex)
 187 { }
 188 
 189 OopStorageTest::~OopStorageTest() {
 190   clear_list(TestAccess::allocate_list(_storage));
 191   clear_list(TestAccess::active_list(_storage));
 192 }
 193 
 194 class OopStorageTestWithAllocation : public OopStorageTest {
 195 public:
 196   OopStorageTestWithAllocation();
 197 
 198   static const size_t _max_entries = 1000;
 199   oop* _entries[_max_entries];
 200 
 201   class VM_DeleteBlocksAtSafepoint;
 202 };
 203 
 204 OopStorageTestWithAllocation::OopStorageTestWithAllocation() {
 205   for (size_t i = 0; i < _max_entries; ++i) {
 206     _entries[i] = _storage.allocate();
 207     EXPECT_TRUE(_entries[i] != NULL);
 208     EXPECT_EQ(i + 1, _storage.allocation_count());
 209   }
 210 };
 211 
 212 const size_t OopStorageTestWithAllocation::_max_entries;
 213 
 214 class OopStorageTestWithAllocation::VM_DeleteBlocksAtSafepoint
 215   : public VM_GTestExecuteAtSafepoint {
 216 public:
 217   VM_DeleteBlocksAtSafepoint(OopStorage* storage) : _storage(storage) {}
 218 
 219   void doit() {
 220     _storage->delete_empty_blocks_safepoint();
 221   }
 222 
 223 private:
 224   OopStorage* _storage;
 225 };
 226 
 227 static bool is_allocate_list_sorted(const OopStorage& storage) {
 228   // The allocate_list isn't strictly sorted.  Rather, all empty
 229   // blocks are segregated to the end of the list.
 230   const TestAccess::BlockList& list = TestAccess::allocate_list(storage);
 231   const OopBlock* block = list.ctail();
 232   for ( ; (block != NULL) && block->is_empty(); block = list.prev(*block)) {}
 233   for ( ; block != NULL; block = list.prev(*block)) {
 234     if (block->is_empty()) {
 235       return false;
 236     }
 237   }
 238   return true;
 239 }
 240 
 241 static size_t total_allocation_count(const TestAccess::BlockList& list) {
 242   size_t total_count = 0;
 243   for (const OopBlock* block = list.chead();
 244        block != NULL;
 245        block = list.next(*block)) {
 246     total_count += TestAccess::block_allocation_count(*block);
 247   }
 248   return total_count;
 249 }
 250 
 251 TEST_VM_F(OopStorageTest, allocate_one) {
 252   EXPECT_TRUE(is_list_empty(TestAccess::active_list(_storage)));
 253   EXPECT_TRUE(is_list_empty(TestAccess::allocate_list(_storage)));
 254 
 255   oop* ptr = _storage.allocate();
 256   EXPECT_TRUE(ptr != NULL);
 257   EXPECT_EQ(1u, _storage.allocation_count());
 258 
 259   EXPECT_EQ(1u, list_length(TestAccess::active_list(_storage)));
 260   EXPECT_EQ(1u, _storage.block_count());
 261   EXPECT_EQ(1u, list_length(TestAccess::allocate_list(_storage)));
 262 
 263   EXPECT_EQ(0u, empty_block_count(_storage));
 264 
 265   const OopBlock* block = TestAccess::allocate_list(_storage).chead();
 266   EXPECT_NE(block, (OopBlock*)NULL);
 267   EXPECT_EQ(block, (TestAccess::active_list(_storage).chead()));
 268   EXPECT_FALSE(TestAccess::block_is_empty(*block));
 269   EXPECT_FALSE(TestAccess::block_is_full(*block));
 270   EXPECT_EQ(1u, TestAccess::block_allocation_count(*block));
 271 
 272   release_entry(_storage, ptr);
 273   EXPECT_EQ(0u, _storage.allocation_count());
 274 
 275   EXPECT_EQ(1u, list_length(TestAccess::active_list(_storage)));
 276   EXPECT_EQ(1u, _storage.block_count());
 277   EXPECT_EQ(1u, list_length(TestAccess::allocate_list(_storage)));
 278 
 279   EXPECT_EQ(1u, empty_block_count(_storage));
 280 
 281   const OopBlock* new_block = TestAccess::allocate_list(_storage).chead();
 282   EXPECT_EQ(block, new_block);
 283   EXPECT_EQ(block, (TestAccess::active_list(_storage).chead()));
 284   EXPECT_TRUE(TestAccess::block_is_empty(*block));
 285   EXPECT_FALSE(TestAccess::block_is_full(*block));
 286   EXPECT_EQ(0u, TestAccess::block_allocation_count(*block));
 287 }
 288 
 289 TEST_VM_F(OopStorageTest, allocation_count) {
 290   static const size_t max_entries = 1000;
 291   oop* entries[max_entries];
 292 
 293   TestAccess::BlockList& active_list = TestAccess::active_list(_storage);
 294   TestAccess::BlockList& allocate_list = TestAccess::allocate_list(_storage);
 295 
 296   EXPECT_TRUE(is_list_empty(active_list));
 297   EXPECT_EQ(0u, _storage.block_count());
 298   EXPECT_TRUE(is_list_empty(allocate_list));
 299 
 300   size_t allocated = 0;
 301   for ( ; allocated < max_entries; ++allocated) {
 302     EXPECT_EQ(allocated, _storage.allocation_count());
 303     if (!is_list_empty(active_list)) {
 304       EXPECT_EQ(1u, list_length(active_list));
 305       EXPECT_EQ(1u, _storage.block_count());
 306       const OopBlock& block = *active_list.chead();
 307       EXPECT_EQ(allocated, TestAccess::block_allocation_count(block));
 308       if (TestAccess::block_is_full(block)) {
 309         break;
 310       } else {
 311         EXPECT_FALSE(is_list_empty(allocate_list));
 312         EXPECT_EQ(&block, allocate_list.chead());
 313       }
 314     }
 315     entries[allocated] = _storage.allocate();
 316   }
 317 
 318   EXPECT_EQ(allocated, _storage.allocation_count());
 319   EXPECT_EQ(1u, list_length(active_list));
 320   EXPECT_EQ(1u, _storage.block_count());
 321   EXPECT_TRUE(is_list_empty(allocate_list));
 322   const OopBlock& block = *active_list.chead();
 323   EXPECT_TRUE(TestAccess::block_is_full(block));
 324   EXPECT_EQ(allocated, TestAccess::block_allocation_count(block));
 325 
 326   for (size_t i = 0; i < allocated; ++i) {
 327     release_entry(_storage, entries[i]);
 328     size_t remaining = allocated - (i + 1);
 329     EXPECT_EQ(remaining, TestAccess::block_allocation_count(block));
 330     EXPECT_EQ(remaining, _storage.allocation_count());
 331     EXPECT_FALSE(is_list_empty(allocate_list));
 332   }
 333 }
 334 
 335 TEST_VM_F(OopStorageTest, allocate_many) {
 336   static const size_t max_entries = 1000;
 337   oop* entries[max_entries];
 338 
 339   TestAccess::BlockList& active_list = TestAccess::active_list(_storage);
 340   TestAccess::BlockList& allocate_list = TestAccess::allocate_list(_storage);
 341 
 342   EXPECT_EQ(0u, empty_block_count(_storage));
 343 
 344   entries[0] = _storage.allocate();
 345   ASSERT_TRUE(entries[0] != NULL);
 346   EXPECT_EQ(1u, list_length(active_list));
 347   EXPECT_EQ(1u, _storage.block_count());
 348   EXPECT_EQ(1u, list_length(allocate_list));
 349   EXPECT_EQ(0u, empty_block_count(_storage));
 350 
 351   const OopBlock* block = active_list.chead();
 352   EXPECT_EQ(1u, TestAccess::block_allocation_count(*block));
 353   EXPECT_EQ(block, allocate_list.chead());
 354 
 355   for (size_t i = 1; i < max_entries; ++i) {
 356     entries[i] = _storage.allocate();
 357     EXPECT_EQ(i + 1, _storage.allocation_count());
 358     ASSERT_TRUE(entries[i] != NULL);
 359     EXPECT_EQ(0u, empty_block_count(_storage));
 360 
 361     if (block == NULL) {
 362       ASSERT_FALSE(is_list_empty(allocate_list));
 363       EXPECT_EQ(1u, list_length(allocate_list));
 364       block = allocate_list.chead();
 365       EXPECT_EQ(1u, TestAccess::block_allocation_count(*block));
 366       EXPECT_EQ(block, active_list.chead());
 367     } else if (TestAccess::block_is_full(*block)) {
 368       EXPECT_TRUE(is_list_empty(allocate_list));
 369       block = NULL;
 370     } else {
 371       EXPECT_FALSE(is_list_empty(allocate_list));
 372       EXPECT_EQ(block, allocate_list.chead());
 373       EXPECT_EQ(block, active_list.chead());
 374     }
 375   }
 376 
 377   if (block != NULL) {
 378     EXPECT_NE(0u, TestAccess::block_allocation_count(*block));
 379     EXPECT_FALSE(is_list_empty(allocate_list));
 380     EXPECT_EQ(block, allocate_list.chead());
 381     EXPECT_EQ(block, active_list.chead());
 382   }
 383 
 384   size_t active_count = list_length(active_list);
 385 
 386   for (size_t i = 0; i < max_entries; ++i) {
 387     release_entry(_storage, entries[i]);
 388     EXPECT_TRUE(is_allocate_list_sorted(_storage));
 389     EXPECT_EQ(max_entries - (i + 1), total_allocation_count(active_list));
 390   }
 391 
 392   EXPECT_EQ(list_length(active_list), list_length(allocate_list));
 393   EXPECT_EQ(list_length(active_list), _storage.block_count());
 394   EXPECT_EQ(list_length(active_list), empty_block_count(_storage));
 395   for (const OopBlock* block = allocate_list.chead();
 396        block != NULL;
 397        block = allocate_list.next(*block)) {
 398     EXPECT_TRUE(TestAccess::block_is_empty(*block));
 399   }
 400 }
 401 
 402 TEST_VM_F(OopStorageTestWithAllocation, random_release) {
 403   static const size_t step = 11;
 404   ASSERT_NE(0u, _max_entries % step); // max_entries and step are mutually prime
 405 
 406   EXPECT_EQ(0u, empty_block_count(_storage));
 407 
 408   TestAccess::BlockList& active_list = TestAccess::active_list(_storage);
 409   TestAccess::BlockList& allocate_list = TestAccess::allocate_list(_storage);
 410 
 411   EXPECT_EQ(_max_entries, total_allocation_count(active_list));
 412   EXPECT_GE(1u, list_length(allocate_list));
 413 
 414   // Release all entries in "random" order.
 415   size_t released = 0;
 416   for (size_t i = 0; released < _max_entries; i = (i + step) % _max_entries) {
 417     if (_entries[i] != NULL) {
 418       release_entry(_storage, _entries[i]);
 419       _entries[i] = NULL;
 420       ++released;
 421       EXPECT_EQ(_max_entries - released, total_allocation_count(active_list));
 422       EXPECT_TRUE(is_allocate_list_sorted(_storage));
 423     }
 424   }
 425 
 426   EXPECT_EQ(list_length(active_list), list_length(allocate_list));
 427   EXPECT_EQ(list_length(active_list), _storage.block_count());
 428   EXPECT_EQ(0u, total_allocation_count(active_list));
 429   EXPECT_EQ(list_length(allocate_list), empty_block_count(_storage));
 430 }
 431 
 432 TEST_VM_F(OopStorageTestWithAllocation, random_allocate_release) {
 433   static const size_t release_step = 11;
 434   static const size_t allocate_step = 5;
 435   ASSERT_NE(0u, _max_entries % release_step); // max_entries and step are mutually prime
 436 
 437   EXPECT_EQ(0u, empty_block_count(_storage));
 438 
 439   TestAccess::BlockList& active_list = TestAccess::active_list(_storage);
 440   TestAccess::BlockList& allocate_list = TestAccess::allocate_list(_storage);
 441 
 442   EXPECT_EQ(_max_entries, total_allocation_count(active_list));
 443   EXPECT_GE(1u, list_length(allocate_list));
 444 
 445   // Release all entries in "random" order, "randomly" interspersed
 446   // with additional allocations.
 447   size_t released = 0;
 448   size_t total_released = 0;
 449   for (size_t i = 0; released < _max_entries; i = (i + release_step) % _max_entries) {
 450     if (_entries[i] != NULL) {
 451       release_entry(_storage, _entries[i]);
 452       _entries[i] = NULL;
 453       ++released;
 454       ++total_released;
 455       EXPECT_EQ(_max_entries - released, total_allocation_count(active_list));
 456       EXPECT_TRUE(is_allocate_list_sorted(_storage));
 457       if (total_released % allocate_step == 0) {
 458         _entries[i] = _storage.allocate();
 459         --released;
 460         EXPECT_EQ(_max_entries - released, total_allocation_count(active_list));
 461         EXPECT_TRUE(is_allocate_list_sorted(_storage));
 462       }
 463     }
 464   }
 465 
 466   EXPECT_EQ(list_length(active_list), list_length(allocate_list));
 467   EXPECT_EQ(list_length(active_list), _storage.block_count());
 468   EXPECT_EQ(0u, total_allocation_count(active_list));
 469   EXPECT_EQ(list_length(allocate_list), empty_block_count(_storage));
 470 }
 471 
 472 template<bool sorted>
 473 class OopStorageTestBlockRelease : public OopStorageTestWithAllocation {
 474 public:
 475   void SetUp() {
 476     size_t nrelease = _max_entries / 2;
 477     oop** to_release = NEW_C_HEAP_ARRAY(oop*, nrelease, mtInternal);
 478 
 479     for (size_t i = 0; i < nrelease; ++i) {
 480       to_release[i] = _entries[2 * i];
 481       *to_release[i] = NULL;
 482     }
 483     if (sorted) {
 484       QuickSort::sort(to_release, nrelease, PointerCompare(), false);
 485     }
 486 
 487     _storage.release(to_release, nrelease);
 488     EXPECT_EQ(_max_entries - nrelease, _storage.allocation_count());
 489 
 490     for (size_t i = 0; i < nrelease; ++i) {
 491       release_entry(_storage, _entries[2 * i + 1], false);
 492       EXPECT_EQ(_max_entries - nrelease - (i + 1), _storage.allocation_count());
 493     }
 494     EXPECT_TRUE(process_deferred_updates(_storage));
 495 
 496     EXPECT_EQ(_storage.block_count(), empty_block_count(_storage));
 497 
 498     FREE_C_HEAP_ARRAY(oop*, to_release);
 499   }
 500 
 501   struct PointerCompare {
 502     int operator()(const void* p, const void* q) const {
 503       return (p < q) ? -1 : int(p != q);
 504     }
 505   };
 506 };
 507 
 508 typedef OopStorageTestBlockRelease<true> OopStorageTestBlockReleaseSorted;
 509 typedef OopStorageTestBlockRelease<false> OopStorageTestBlockReleaseUnsorted;
 510 
 511 TEST_VM_F(OopStorageTestBlockReleaseSorted, block_release) {}
 512 TEST_VM_F(OopStorageTestBlockReleaseUnsorted, block_release) {}
 513 
 514 #ifndef DISABLE_GARBAGE_ALLOCATION_STATUS_TESTS
 515 TEST_VM_F(OopStorageTest, invalid_pointer) {
 516   {
 517     char* mem = NEW_C_HEAP_ARRAY(char, 1000, mtInternal);
 518     oop* ptr = reinterpret_cast<oop*>(align_down(mem + 250, sizeof(oop)));
 519     // Predicate returns false for some malloc'ed block.
 520     EXPECT_EQ(OopStorage::INVALID_ENTRY, _storage.allocation_status(ptr));
 521     FREE_C_HEAP_ARRAY(char, mem);
 522   }
 523 
 524   {
 525     oop obj;
 526     oop* ptr = &obj;
 527     // Predicate returns false for some "random" location.
 528     EXPECT_EQ(OopStorage::INVALID_ENTRY, _storage.allocation_status(ptr));
 529   }
 530 }
 531 #endif // DISABLE_GARBAGE_ALLOCATION_STATUS_TESTS
 532 
 533 class OopStorageTest::CountingIterateClosure {
 534 public:
 535   size_t _const_count;
 536   size_t _const_non_null;
 537   size_t _non_const_count;
 538   size_t _non_const_non_null;
 539 
 540   void do_oop(const oop* ptr) {
 541     ++_const_count;
 542     if (*ptr != NULL) {
 543       ++_const_non_null;
 544     }
 545   }
 546 
 547   void do_oop(oop* ptr) {
 548     ++_non_const_count;
 549     if (*ptr != NULL) {
 550       ++_non_const_non_null;
 551     }
 552   }
 553 
 554   CountingIterateClosure() :
 555     _const_count(0),
 556     _const_non_null(0),
 557     _non_const_count(0),
 558     _non_const_non_null(0)
 559   {}
 560 };
 561 
 562 template<bool is_const>
 563 class OopStorageTest::VM_CountAtSafepoint : public VM_GTestExecuteAtSafepoint {
 564 public:
 565   typedef typename Conditional<is_const,
 566                                const OopStorage,
 567                                OopStorage>::type Storage;
 568 
 569   VM_CountAtSafepoint(Storage* storage, CountingIterateClosure* cl) :
 570     _storage(storage), _cl(cl)
 571   {}
 572 
 573   void doit() { _storage->oops_do(_cl); }
 574 
 575 private:
 576   Storage* _storage;
 577   CountingIterateClosure* _cl;
 578 };
 579 
 580 TEST_VM_F(OopStorageTest, simple_iterate) {
 581   // Dummy oop value.
 582   intptr_t dummy_oop_value = 0xbadbeaf;
 583   oop dummy_oop = reinterpret_cast<oopDesc*>(&dummy_oop_value);
 584 
 585   const size_t max_entries = 1000;
 586   oop* entries[max_entries];
 587 
 588   size_t allocated = 0;
 589   size_t entries_with_values = 0;
 590   for (size_t i = 0; i < max_entries; i += 10) {
 591     for ( ; allocated < i; ++allocated) {
 592       entries[allocated] = _storage.allocate();
 593       ASSERT_TRUE(entries[allocated] != NULL);
 594       if ((allocated % 3) != 0) {
 595         *entries[allocated] = dummy_oop;
 596         ++entries_with_values;
 597       }
 598     }
 599 
 600     {
 601       CountingIterateClosure cl;
 602       VM_CountAtSafepoint<false> op(&_storage, &cl);
 603       {
 604         ThreadInVMfromNative invm(JavaThread::current());
 605         VMThread::execute(&op);
 606       }
 607       EXPECT_EQ(allocated, cl._non_const_count);
 608       EXPECT_EQ(entries_with_values, cl._non_const_non_null);
 609       EXPECT_EQ(0u, cl._const_count);
 610       EXPECT_EQ(0u, cl._const_non_null);
 611     }
 612 
 613     {
 614       CountingIterateClosure cl;
 615       VM_CountAtSafepoint<true> op(&_storage, &cl);
 616       {
 617         ThreadInVMfromNative invm(JavaThread::current());
 618         VMThread::execute(&op);
 619       }
 620       EXPECT_EQ(allocated, cl._const_count);
 621       EXPECT_EQ(entries_with_values, cl._const_non_null);
 622       EXPECT_EQ(0u, cl._non_const_count);
 623       EXPECT_EQ(0u, cl._non_const_non_null);
 624     }
 625   }
 626 
 627   while (allocated > 0) {
 628     release_entry(_storage, entries[--allocated], false);
 629   }
 630   process_deferred_updates(_storage);
 631 }
 632 
 633 class OopStorageTestIteration : public OopStorageTestWithAllocation {
 634 public:
 635   static const size_t _max_workers = 2;
 636   unsigned char _states[_max_workers][_max_entries];
 637 
 638   static const unsigned char mark_released  = 1u << 0;
 639   static const unsigned char mark_invalid   = 1u << 1;
 640   static const unsigned char mark_const     = 1u << 2;
 641   static const unsigned char mark_non_const = 1u << 3;
 642 
 643   virtual void SetUp() {
 644     OopStorageTestWithAllocation::SetUp();
 645 
 646     memset(_states, 0, sizeof(_states));
 647 
 648     size_t initial_release = 0;
 649     for ( ; empty_block_count(_storage) < 2; ++initial_release) {
 650       ASSERT_GT(_max_entries, initial_release);
 651       release_entry(_storage, _entries[initial_release]);
 652       _states[0][initial_release] = mark_released;
 653     }
 654 
 655     for (size_t i = initial_release; i < _max_entries; i += 3) {
 656       release_entry(_storage, _entries[i], false);
 657       _states[0][i] = mark_released;
 658     }
 659     process_deferred_updates(_storage);
 660   }
 661 
 662   class VerifyState;
 663   class VerifyFn;
 664   template<bool is_const> class VM_Verify;
 665 
 666   class VerifyClosure;
 667   class VM_VerifyUsingOopsDo;
 668 };
 669 
 670 const unsigned char OopStorageTestIteration::mark_released;
 671 const unsigned char OopStorageTestIteration::mark_invalid;
 672 const unsigned char OopStorageTestIteration::mark_const;
 673 const unsigned char OopStorageTestIteration::mark_non_const;
 674 
 675 class OopStorageTestIteration::VerifyState {
 676 public:
 677   unsigned char _expected_mark;
 678   const oop* const* _entries;
 679   unsigned char (&_states)[_max_workers][_max_entries];
 680 
 681   VerifyState(unsigned char expected_mark,
 682               const oop* const* entries,
 683               unsigned char (&states)[_max_workers][_max_entries]) :
 684     _expected_mark(expected_mark),
 685     _entries(entries),
 686     _states(states)
 687   { }
 688 
 689   bool update(const oop* ptr, uint worker_id, unsigned char mark) const {
 690     size_t index = 0;
 691     bool found = find_entry(ptr, &index);
 692     EXPECT_TRUE(found);
 693     EXPECT_GT(_max_entries, index);
 694     EXPECT_GT(_max_workers, worker_id);
 695     if (!found) {
 696       return false;
 697     } else if (index >= _max_entries) {
 698       return false;
 699     } else if (worker_id >= _max_workers) {
 700       return false;
 701     } else {
 702       EXPECT_EQ(0, _states[worker_id][index]);
 703       if (_states[worker_id][index] != 0) {
 704         _states[worker_id][index] |= mark_invalid;
 705         return false;
 706       } else {
 707         _states[worker_id][index] |= mark;
 708         return true;
 709       }
 710     }
 711   }
 712 
 713   void check() const {
 714     for (size_t i = 0; i < _max_entries; ++i) {
 715       unsigned char mark = 0;
 716       for (size_t w = 0; w < _max_workers; ++w) {
 717         if (mark == 0) {
 718           mark = _states[w][i];
 719         } else {
 720           EXPECT_EQ(0u, _states[w][i]);
 721         }
 722       }
 723       if (mark == 0) {
 724         EXPECT_NE(0u, mark);
 725       } else if ((mark & mark_released) != 0) {
 726         EXPECT_EQ(mark_released, mark);
 727       } else {
 728         EXPECT_EQ(_expected_mark, mark);
 729       }
 730     }
 731   }
 732 
 733 private:
 734   bool find_entry(const oop* ptr, size_t* index) const {
 735     for (size_t i = 0; i < _max_entries; ++i) {
 736       if (ptr == _entries[i]) {
 737         *index = i;
 738         return true;
 739       }
 740     }
 741     return false;
 742   }
 743 };
 744 
 745 class OopStorageTestIteration::VerifyFn {
 746 public:
 747   VerifyFn(VerifyState* state, uint worker_id = 0) :
 748     _state(state),
 749     _worker_id(worker_id)
 750   {}
 751 
 752   bool operator()(      oop* ptr) const {
 753     return _state->update(ptr, _worker_id, mark_non_const);
 754   }
 755 
 756   bool operator()(const oop* ptr) const {
 757     return _state->update(ptr, _worker_id, mark_const);
 758   }
 759 
 760 private:
 761   VerifyState* _state;
 762   uint _worker_id;
 763 };
 764 
 765 class OopStorageTestIteration::VerifyClosure {
 766 public:
 767   VerifyClosure(VerifyState* state, uint worker_id = 0) :
 768     _state(state),
 769     _worker_id(worker_id)
 770   {}
 771 
 772   void do_oop(oop* ptr) {
 773     _state->update(ptr, _worker_id, mark_non_const);
 774   }
 775 
 776   void do_oop(const oop* ptr) {
 777     _state->update(ptr, _worker_id, mark_const);
 778   }
 779 
 780 private:
 781   VerifyState* _state;
 782   uint _worker_id;
 783 };
 784 
 785 const size_t OopStorageTestIteration::_max_workers;
 786 
 787 template<bool is_const>
 788 class OopStorageTestIteration::VM_Verify : public VM_GTestExecuteAtSafepoint {
 789 public:
 790   typedef typename Conditional<is_const,
 791                                const OopStorage,
 792                                OopStorage>::type Storage;
 793 
 794   VM_Verify(Storage* storage, VerifyState* vstate) :
 795     _storage(storage), _vstate(vstate), _result(false)
 796   {}
 797 
 798   void doit() {
 799     VerifyFn verifier(_vstate);
 800     _result = _storage->iterate_safepoint(verifier);
 801   }
 802 
 803   bool result() const { return _result; }
 804 
 805 private:
 806   Storage* _storage;
 807   VerifyState* _vstate;
 808   bool _result;
 809 };
 810 
 811 class OopStorageTestIteration::VM_VerifyUsingOopsDo : public VM_GTestExecuteAtSafepoint {
 812 public:
 813   VM_VerifyUsingOopsDo(OopStorage* storage, VerifyState* vstate) :
 814     _storage(storage), _vstate(vstate)
 815   {}
 816 
 817   void doit() {
 818     VerifyClosure verifier(_vstate);
 819     _storage->oops_do(&verifier);
 820   }
 821 
 822 private:
 823   OopStorage* _storage;
 824   VerifyState* _vstate;
 825 };
 826 
 827 TEST_VM_F(OopStorageTestIteration, iterate_safepoint) {
 828   VerifyState vstate(mark_non_const, _entries, _states);
 829   VM_Verify<false> op(&_storage, &vstate);
 830   {
 831     ThreadInVMfromNative invm(JavaThread::current());
 832     VMThread::execute(&op);
 833   }
 834   EXPECT_TRUE(op.result());
 835   vstate.check();
 836 }
 837 
 838 TEST_VM_F(OopStorageTestIteration, const_iterate_safepoint) {
 839   VerifyState vstate(mark_const, _entries, _states);
 840   VM_Verify<true> op(&_storage, &vstate);
 841   {
 842     ThreadInVMfromNative invm(JavaThread::current());
 843     VMThread::execute(&op);
 844   }
 845   EXPECT_TRUE(op.result());
 846   vstate.check();
 847 }
 848 
 849 TEST_VM_F(OopStorageTestIteration, oops_do) {
 850   VerifyState vstate(mark_non_const, _entries, _states);
 851   VM_VerifyUsingOopsDo op(&_storage, &vstate);
 852   {
 853     ThreadInVMfromNative invm(JavaThread::current());
 854     VMThread::execute(&op);
 855   }
 856   vstate.check();
 857 }
 858 
 859 // Parallel iteration not available unless INCLUDE_ALL_GCS
 860 #if INCLUDE_ALL_GCS
 861 
 862 class OopStorageTestParIteration : public OopStorageTestIteration {
 863 public:
 864   WorkGang* workers();
 865 
 866   class VM_ParStateVerify;
 867 
 868   template<bool concurrent, bool is_const> class Task;
 869   template<bool concurrent, bool is_const> class TaskUsingOopsDo;
 870 
 871 private:
 872   static WorkGang* _workers;
 873 };
 874 
 875 WorkGang* OopStorageTestParIteration::_workers = NULL;
 876 
 877 WorkGang* OopStorageTestParIteration::workers() {
 878   if (_workers == NULL) {
 879     _workers = new WorkGang("OopStorageTestParIteration workers",
 880                             _max_workers,
 881                             false,
 882                             false);
 883     _workers->initialize_workers();
 884     _workers->update_active_workers(_max_workers);
 885   }
 886   return _workers;
 887 }
 888 
 889 template<bool concurrent, bool is_const>
 890 class OopStorageTestParIteration::Task : public AbstractGangTask {
 891   typedef OopStorage::ParState<concurrent, is_const> StateType;
 892 
 893   typedef typename Conditional<is_const,
 894                                const OopStorage,
 895                                OopStorage>::type Storage;
 896 
 897 public:
 898   Task(const char* name, Storage* storage, VerifyState* vstate) :
 899     AbstractGangTask(name),
 900     _state(storage),
 901     _vstate(vstate)
 902   {}
 903 
 904   virtual void work(uint worker_id) {
 905     VerifyFn verifier(_vstate, worker_id);
 906     _state.iterate(verifier);
 907   }
 908 
 909 private:
 910   StateType _state;
 911   VerifyState* _vstate;
 912 };
 913 
 914 template<bool concurrent, bool is_const>
 915 class OopStorageTestParIteration::TaskUsingOopsDo : public AbstractGangTask {
 916 public:
 917   TaskUsingOopsDo(const char* name, OopStorage* storage, VerifyState* vstate) :
 918     AbstractGangTask(name),
 919     _state(storage),
 920     _vstate(vstate)
 921   {}
 922 
 923   virtual void work(uint worker_id) {
 924     VerifyClosure verifier(_vstate, worker_id);
 925     _state.oops_do(&verifier);
 926   }
 927 
 928 private:
 929   OopStorage::ParState<concurrent, is_const> _state;
 930   VerifyState* _vstate;
 931 };
 932 
 933 class OopStorageTestParIteration::VM_ParStateVerify : public VM_GTestExecuteAtSafepoint {
 934 public:
 935   VM_ParStateVerify(WorkGang* workers, AbstractGangTask* task) :
 936     _workers(workers), _task(task)
 937   {}
 938 
 939   void doit() {
 940     _workers->run_task(_task);
 941   }
 942 
 943 private:
 944   WorkGang* _workers;
 945   AbstractGangTask* _task;
 946 };
 947 
 948 TEST_VM_F(OopStorageTestParIteration, par_state_safepoint_iterate) {
 949   VerifyState vstate(mark_non_const, _entries, _states);
 950   Task<false, false> task("test", &_storage, &vstate);
 951   VM_ParStateVerify op(workers(), &task);
 952   {
 953     ThreadInVMfromNative invm(JavaThread::current());
 954     VMThread::execute(&op);
 955   }
 956   vstate.check();
 957 }
 958 
 959 TEST_VM_F(OopStorageTestParIteration, par_state_safepoint_const_iterate) {
 960   VerifyState vstate(mark_const, _entries, _states);
 961   Task<false, true> task("test", &_storage, &vstate);
 962   VM_ParStateVerify op(workers(), &task);
 963   {
 964     ThreadInVMfromNative invm(JavaThread::current());
 965     VMThread::execute(&op);
 966   }
 967   vstate.check();
 968 }
 969 
 970 TEST_VM_F(OopStorageTestParIteration, par_state_safepoint_oops_do) {
 971   VerifyState vstate(mark_non_const, _entries, _states);
 972   TaskUsingOopsDo<false, false> task("test", &_storage, &vstate);
 973   VM_ParStateVerify op(workers(), &task);
 974   {
 975     ThreadInVMfromNative invm(JavaThread::current());
 976     VMThread::execute(&op);
 977   }
 978   vstate.check();
 979 }
 980 
 981 TEST_VM_F(OopStorageTestParIteration, par_state_safepoint_const_oops_do) {
 982   VerifyState vstate(mark_const, _entries, _states);
 983   TaskUsingOopsDo<false, true> task("test", &_storage, &vstate);
 984   VM_ParStateVerify op(workers(), &task);
 985   {
 986     ThreadInVMfromNative invm(JavaThread::current());
 987     VMThread::execute(&op);
 988   }
 989   vstate.check();
 990 }
 991 
 992 TEST_VM_F(OopStorageTestParIteration, par_state_concurrent_iterate) {
 993   VerifyState vstate(mark_non_const, _entries, _states);
 994   Task<true, false> task("test", &_storage, &vstate);
 995   workers()->run_task(&task);
 996   vstate.check();
 997 }
 998 
 999 TEST_VM_F(OopStorageTestParIteration, par_state_concurrent_const_iterate) {
1000   VerifyState vstate(mark_const, _entries, _states);
1001   Task<true, true> task("test", &_storage, &vstate);
1002   workers()->run_task(&task);
1003   vstate.check();
1004 }
1005 
1006 TEST_VM_F(OopStorageTestParIteration, par_state_concurrent_oops_do) {
1007   VerifyState vstate(mark_non_const, _entries, _states);
1008   TaskUsingOopsDo<true, false> task("test", &_storage, &vstate);
1009   workers()->run_task(&task);
1010   vstate.check();
1011 }
1012 
1013 TEST_VM_F(OopStorageTestParIteration, par_state_concurrent_const_oops_do) {
1014   VerifyState vstate(mark_const, _entries, _states);
1015   TaskUsingOopsDo<true, true> task("test", &_storage, &vstate);
1016   workers()->run_task(&task);
1017   vstate.check();
1018 }
1019 
1020 #endif // INCLUDE_ALL_GCS
1021 
1022 TEST_VM_F(OopStorageTestWithAllocation, delete_empty_blocks_safepoint) {
1023   TestAccess::BlockList& active_list = TestAccess::active_list(_storage);
1024 
1025   size_t initial_active_size = list_length(active_list);
1026   EXPECT_EQ(initial_active_size, _storage.block_count());
1027   ASSERT_LE(3u, initial_active_size); // Need at least 3 blocks for test
1028 
1029   for (size_t i = 0; empty_block_count(_storage) < 3; ++i) {
1030     ASSERT_GT(_max_entries, i);
1031     release_entry(_storage, _entries[i]);
1032   }
1033 
1034   EXPECT_EQ(initial_active_size, list_length(active_list));
1035   EXPECT_EQ(initial_active_size, _storage.block_count());
1036   EXPECT_EQ(3u, empty_block_count(_storage));
1037 
1038   {
1039     ThreadInVMfromNative invm(JavaThread::current());
1040     VM_DeleteBlocksAtSafepoint op(&_storage);
1041     VMThread::execute(&op);
1042   }
1043   EXPECT_EQ(0u, empty_block_count(_storage));
1044   EXPECT_EQ(initial_active_size - 3, list_length(active_list));
1045   EXPECT_EQ(initial_active_size - 3, _storage.block_count());
1046 }
1047 
1048 TEST_VM_F(OopStorageTestWithAllocation, delete_empty_blocks_concurrent) {
1049   TestAccess::BlockList& active_list = TestAccess::active_list(_storage);
1050 
1051   size_t initial_active_size = list_length(active_list);
1052   EXPECT_EQ(initial_active_size, _storage.block_count());
1053   ASSERT_LE(3u, initial_active_size); // Need at least 3 blocks for test
1054 
1055   for (size_t i = 0; empty_block_count(_storage) < 3; ++i) {
1056     ASSERT_GT(_max_entries, i);
1057     release_entry(_storage, _entries[i]);
1058   }
1059 
1060   EXPECT_EQ(initial_active_size, list_length(active_list));
1061   EXPECT_EQ(initial_active_size, _storage.block_count());
1062   EXPECT_EQ(3u, empty_block_count(_storage));
1063 
1064   _storage.delete_empty_blocks_concurrent();
1065   EXPECT_EQ(0u, empty_block_count(_storage));
1066   EXPECT_EQ(initial_active_size - 3, list_length(active_list));
1067   EXPECT_EQ(initial_active_size - 3, _storage.block_count());
1068 }
1069 
1070 TEST_VM_F(OopStorageTestWithAllocation, allocation_status) {
1071   oop* retained = _entries[200];
1072   oop* released = _entries[300];
1073   oop* garbage = reinterpret_cast<oop*>(1024 * 1024);
1074   release_entry(_storage, released);
1075 
1076   EXPECT_EQ(OopStorage::ALLOCATED_ENTRY, _storage.allocation_status(retained));
1077   EXPECT_EQ(OopStorage::UNALLOCATED_ENTRY, _storage.allocation_status(released));
1078 #ifndef DISABLE_GARBAGE_ALLOCATION_STATUS_TESTS
1079   EXPECT_EQ(OopStorage::INVALID_ENTRY, _storage.allocation_status(garbage));
1080 #endif
1081 
1082   for (size_t i = 0; i < _max_entries; ++i) {
1083     if ((_entries[i] != retained) && (_entries[i] != released)) {
1084       // Leave deferred release updates to block deletion.
1085       release_entry(_storage, _entries[i], false);
1086     }
1087   }
1088 
1089   {
1090     ThreadInVMfromNative invm(JavaThread::current());
1091     VM_DeleteBlocksAtSafepoint op(&_storage);
1092     VMThread::execute(&op);
1093   }
1094   EXPECT_EQ(OopStorage::ALLOCATED_ENTRY, _storage.allocation_status(retained));
1095 #ifndef DISABLE_GARBAGE_ALLOCATION_STATUS_TESTS
1096   EXPECT_EQ(OopStorage::INVALID_ENTRY, _storage.allocation_status(released));
1097   EXPECT_EQ(OopStorage::INVALID_ENTRY, _storage.allocation_status(garbage));
1098 #endif // DISABLE_GARBAGE_ALLOCATION_STATUS_TESTS
1099 }
1100 
1101 TEST_VM_F(OopStorageTest, usage_info) {
1102   size_t goal_blocks = 5;
1103   oop* entries[1000];
1104   size_t allocated = 0;
1105 
1106   EXPECT_EQ(0u, _storage.block_count());
1107   // There is non-block overhead, so always some usage.
1108   EXPECT_LT(0u, _storage.total_memory_usage());
1109 
1110   while (_storage.block_count() < goal_blocks) {
1111     size_t this_count = _storage.block_count();
1112     while (_storage.block_count() == this_count) {
1113       ASSERT_GT(ARRAY_SIZE(entries), allocated);
1114       entries[allocated] = _storage.allocate();
1115       ASSERT_TRUE(entries[allocated] != NULL);
1116       ++allocated;
1117     }
1118     EXPECT_NE(0u, _storage.block_count());
1119     EXPECT_NE(0u, _storage.total_memory_usage());
1120   }
1121 
1122   EXPECT_LT(TestAccess::memory_per_block() * _storage.block_count(),
1123             _storage.total_memory_usage());
1124 }
1125 
1126 #ifndef PRODUCT
1127 
1128 TEST_VM_F(OopStorageTestWithAllocation, print_storage) {
1129   // Release the first 1/2
1130   for (size_t i = 0; i < (_max_entries / 2); ++i) {
1131     // Deferred updates don't affect print output.
1132     release_entry(_storage, _entries[i], false);
1133     _entries[i] = NULL;
1134   }
1135   // Release every other remaining
1136   for (size_t i = _max_entries / 2; i < _max_entries; i += 2) {
1137     // Deferred updates don't affect print output.
1138     release_entry(_storage, _entries[i], false);
1139     _entries[i] = NULL;
1140   }
1141 
1142   size_t expected_entries = _max_entries / 4;
1143   EXPECT_EQ(expected_entries, _storage.allocation_count());
1144 
1145   size_t entries_per_block = BitsPerWord;
1146   size_t expected_blocks = (_max_entries + entries_per_block - 1) / entries_per_block;
1147   EXPECT_EQ(expected_blocks, _storage.block_count());
1148 
1149   double expected_usage = (100.0 * expected_entries) / (expected_blocks * entries_per_block);
1150 
1151   {
1152     ResourceMark rm;
1153     stringStream expected_st;
1154     expected_st.print("Test Storage: " SIZE_FORMAT
1155                       " entries in " SIZE_FORMAT
1156                       " blocks (%.F%%), " SIZE_FORMAT " bytes",
1157                       expected_entries,
1158                       expected_blocks,
1159                       expected_usage,
1160                       _storage.total_memory_usage());
1161     stringStream st;
1162     _storage.print_on(&st);
1163     EXPECT_STREQ(expected_st.as_string(), st.as_string());
1164   }
1165 }
1166 
1167 #endif // !PRODUCT
1168 
1169 //////////////////////////////////////////////////////////////////////////////
1170 // Unit tests for block lists
1171 
1172 class OopStorageBlockListTest : public ::testing::Test {
1173 public:
1174   OopStorageBlockListTest() {
1175     for (size_t i = 0; i < nvalues; ++i) {
1176       values[i] = OopBlock::new_block(pseudo_owner());
1177     }
1178   }
1179 
1180   ~OopStorageBlockListTest() {
1181     for (size_t i = 0; i < nvalues; ++i) {
1182       OopBlock::delete_block(*values[i]);
1183     }
1184   }
1185 
1186   static const size_t nvalues = 10;
1187   OopBlock* values[nvalues];
1188 
1189 private:
1190   // The only thing we actually care about is the address of the owner.
1191   static const size_t pseudo_owner_size = sizeof(OopStorage) / sizeof(void*);
1192   static const void* const _pseudo_owner[pseudo_owner_size];
1193   static const OopStorage* pseudo_owner() {
1194     return reinterpret_cast<const OopStorage*>(&_pseudo_owner);
1195   }
1196 };
1197 
1198 const size_t OopStorageBlockListTest::nvalues;
1199 const void* const OopStorageBlockListTest::_pseudo_owner[] = {};
1200 
1201 TEST_F(OopStorageBlockListTest, empty_list) {
1202   TestAccess::BlockList list(&OopBlock::get_active_entry);
1203 
1204   EXPECT_TRUE(is_list_empty(list));
1205   EXPECT_EQ(NULL_BLOCK, list.head());
1206   EXPECT_EQ(NULL_BLOCK, list.chead());
1207   EXPECT_EQ(NULL_BLOCK, list.ctail());
1208 }
1209 
1210 TEST_F(OopStorageBlockListTest, push_back) {
1211   TestAccess::BlockList list(&OopBlock::get_active_entry);
1212 
1213   for (size_t i = 0; i < nvalues; ++i) {
1214     list.push_back(*values[i]);
1215     EXPECT_FALSE(is_list_empty(list));
1216     EXPECT_EQ(list.ctail(), values[i]);
1217   }
1218 
1219   EXPECT_EQ(list.chead(), list.head());
1220   EXPECT_EQ(list.chead(), values[0]);
1221   EXPECT_EQ(list.ctail(), values[nvalues - 1]);
1222 
1223   const OopBlock* block = list.chead();
1224   for (size_t i = 0; i < nvalues; ++i) {
1225     EXPECT_EQ(block, values[i]);
1226     block = list.next(*block);
1227   }
1228   EXPECT_EQ(NULL_BLOCK, block);
1229 
1230   block = list.ctail();
1231   for (size_t i = 0; i < nvalues; ++i) {
1232     EXPECT_EQ(block, values[nvalues - i - 1]);
1233     block = list.prev(*block);
1234   }
1235   EXPECT_EQ(NULL_BLOCK, block);
1236 
1237   clear_list(list);
1238 }
1239 
1240 TEST_F(OopStorageBlockListTest, push_front) {
1241   TestAccess::BlockList list(&OopBlock::get_active_entry);
1242 
1243   for (size_t i = 0; i < nvalues; ++i) {
1244     list.push_front(*values[i]);
1245     EXPECT_FALSE(is_list_empty(list));
1246     EXPECT_EQ(list.head(), values[i]);
1247   }
1248 
1249   EXPECT_EQ(list.chead(), list.head());
1250   EXPECT_EQ(list.chead(), values[nvalues - 1]);
1251   EXPECT_EQ(list.ctail(), values[0]);
1252 
1253   const OopBlock* block = list.chead();
1254   for (size_t i = 0; i < nvalues; ++i) {
1255     EXPECT_EQ(block, values[nvalues - i - 1]);
1256     block = list.next(*block);
1257   }
1258   EXPECT_EQ(NULL_BLOCK, block);
1259 
1260   block = list.ctail();
1261   for (size_t i = 0; i < nvalues; ++i) {
1262     EXPECT_EQ(block, values[i]);
1263     block = list.prev(*block);
1264   }
1265   EXPECT_EQ(NULL_BLOCK, block);
1266 
1267   clear_list(list);
1268 }
1269 
1270 class OopStorageBlockListTestWithList : public OopStorageBlockListTest {
1271 public:
1272   OopStorageBlockListTestWithList() : list(&OopBlock::get_active_entry) {
1273     for (size_t i = 0; i < nvalues; ++i) {
1274       list.push_back(*values[i]);
1275     }
1276   }
1277 
1278   ~OopStorageBlockListTestWithList() {
1279     clear_list(list);
1280   }
1281 
1282   TestAccess::BlockList list;
1283 };
1284 
1285 TEST_F(OopStorageBlockListTestWithList, unlink_front) {
1286   EXPECT_EQ(list.chead(), values[0]);
1287   EXPECT_EQ(list.ctail(), values[nvalues - 1]);
1288 
1289   list.unlink(*values[0]);
1290   EXPECT_EQ(NULL_BLOCK, list.next(*values[0]));
1291   EXPECT_EQ(NULL_BLOCK, list.prev(*values[0]));
1292   EXPECT_EQ(list.chead(), values[1]);
1293   EXPECT_EQ(list.ctail(), values[nvalues - 1]);
1294 
1295   const OopBlock* block = list.chead();
1296   for (size_t i = 1; i < nvalues; ++i) {
1297     EXPECT_EQ(block, values[i]);
1298     block = list.next(*block);
1299   }
1300   EXPECT_EQ(NULL_BLOCK, block);
1301 }
1302 
1303 TEST_F(OopStorageBlockListTestWithList, unlink_back) {
1304   EXPECT_EQ(list.chead(), values[0]);
1305 
1306   list.unlink(*values[nvalues - 1]);
1307   EXPECT_EQ(NULL_BLOCK, list.next(*values[nvalues - 1]));
1308   EXPECT_EQ(NULL_BLOCK, list.prev(*values[nvalues - 1]));
1309   EXPECT_EQ(list.chead(), values[0]);
1310   EXPECT_EQ(list.ctail(), values[nvalues - 2]);
1311 
1312   const OopBlock* block = list.chead();
1313   for (size_t i = 0; i < nvalues - 1; ++i) {
1314     EXPECT_EQ(block, values[i]);
1315     block = list.next(*block);
1316   }
1317   EXPECT_EQ(NULL_BLOCK, block);
1318 }
1319 
1320 TEST_F(OopStorageBlockListTestWithList, unlink_middle) {
1321   EXPECT_EQ(list.chead(), values[0]);
1322 
1323   size_t index = nvalues / 2;
1324 
1325   list.unlink(*values[index]);
1326   EXPECT_EQ(NULL_BLOCK, list.next(*values[index]));
1327   EXPECT_EQ(NULL_BLOCK, list.prev(*values[index]));
1328   EXPECT_EQ(list.chead(), values[0]);
1329   EXPECT_EQ(list.ctail(), values[nvalues - 1]);
1330 
1331   const OopBlock* block = list.chead();
1332   for (size_t i = 0; i < index; ++i) {
1333     EXPECT_EQ(block, values[i]);
1334     block = list.next(*block);
1335   }
1336   for (size_t i = index + 1; i < nvalues; ++i) {
1337     EXPECT_EQ(block, values[i]);
1338     block = list.next(*block);
1339   }
1340   EXPECT_EQ(NULL_BLOCK, block);
1341 }
1342 
1343 TEST_F(OopStorageBlockListTest, single) {
1344   TestAccess::BlockList list(&OopBlock::get_active_entry);
1345 
1346   list.push_back(*values[0]);
1347   EXPECT_EQ(NULL_BLOCK, list.next(*values[0]));
1348   EXPECT_EQ(NULL_BLOCK, list.prev(*values[0]));
1349   EXPECT_EQ(list.chead(), values[0]);
1350   EXPECT_EQ(list.ctail(), values[0]);
1351 
1352   list.unlink(*values[0]);
1353   EXPECT_EQ(NULL_BLOCK, list.next(*values[0]));
1354   EXPECT_EQ(NULL_BLOCK, list.prev(*values[0]));
1355   EXPECT_EQ(NULL_BLOCK, list.chead());
1356   EXPECT_EQ(NULL_BLOCK, list.ctail());
1357 }
1358 
1359 TEST_F(OopStorageBlockListTestWithList, two_lists) {
1360   TestAccess::BlockList list2(&OopBlock::get_allocate_entry);
1361   for (size_t i = 0; i < nvalues; ++i) {
1362     list2.push_front(*values[i]);
1363   }
1364 
1365   const OopBlock* active_block = list.chead();
1366   const OopBlock* allocate_block = list2.ctail();
1367   for (size_t i = 0; i < nvalues; ++i) {
1368     EXPECT_EQ(active_block, allocate_block);
1369     active_block = list.next(*active_block);
1370     allocate_block = list2.prev(*allocate_block);
1371   }
1372   EXPECT_EQ(NULL_BLOCK, active_block);
1373   EXPECT_EQ(NULL_BLOCK, allocate_block);
1374 
1375   for (size_t i = 0; i < nvalues; ++i) {
1376     list2.unlink(*values[i]);
1377   }
1378   EXPECT_TRUE(is_list_empty(list2));
1379 
1380   active_block = list.chead();
1381   for (size_t i = 0; i < nvalues; ++i) {
1382     EXPECT_EQ(active_block, values[i]);
1383     active_block = list.next(*active_block);
1384   }
1385   EXPECT_EQ(NULL_BLOCK, active_block);
1386 }
1387