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