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.hpp"

    26 #include "gc/shared/workgroup.hpp"

    27 #include "memory/allocation.inline.hpp"

    28 #include "memory/resourceArea.hpp"

    29 #include "metaprogramming/conditional.hpp"

    30 #include "metaprogramming/enableIf.hpp"

    31 #include "runtime/handles.inline.hpp"

    32 #include "runtime/interfaceSupport.hpp"

    33 #include "runtime/mutex.hpp"

    34 #include "runtime/mutexLocker.hpp"

    35 #include "runtime/thread.hpp"

    36 #include "runtime/vm_operations.hpp"

    37 #include "runtime/vmThread.hpp"

    38 #include "utilities/align.hpp"

    39 #include "utilities/ostream.hpp"

    40 #include "utilities/quickSort.hpp"

    41 #include "unittest.hpp"

    42 

    43 // --- FIXME: Disable some tests on 32bit Windows, because SafeFetch

    44 //     (which is used by allocation_status) doesn't currently provide

    45 //     protection in the context where gtests are run; see JDK-8185734.

    46 #ifdef _WIN32

    47 #define DISABLE_GARBAGE_ALLOCATION_STATUS_TESTS

    48 #endif

    49 

    50 // Access storage internals.

    51 class OopStorage::TestAccess : public AllStatic {

    52 public:

    53   typedef OopStorage::Block Block;

    54   typedef OopStorage::BlockList BlockList;

    55 

    56   static BlockList& active_list(OopStorage& storage) {

    57     return storage._active_list;

    58   }

    59 

    60   static BlockList& allocate_list(OopStorage& storage) {

    61     return storage._allocate_list;

    62   }

    63 

    64   static const BlockList& allocate_list(const OopStorage& storage) {

    65     return storage._allocate_list;

    66   }

    67 

    68   static Mutex* allocate_mutex(const OopStorage& storage) {

    69     return storage._allocate_mutex;

    70   }

    71 

    72   static bool block_is_empty(const Block& block) {

    73     return block.is_empty();

    74   }

    75 

    76   static bool block_is_full(const Block& block) {

    77     return block.is_full();

    78   }

    79 

    80   static unsigned block_allocation_count(const Block& block) {

    81     uintx bitmask = block.allocated_bitmask();

    82     unsigned count = 0;

    83     for ( ; bitmask != 0; bitmask >>= 1) {

    84       if ((bitmask & 1) != 0) {

    85         ++count;

    86       }

    87     }

    88     return count;

    89   }

    90 

    91   static size_t memory_per_block() {

    92     return Block::allocation_size();

    93   }

    94 };

    95 

    96 typedef OopStorage::TestAccess TestAccess;

    97 // --- FIXME: Should be just Block, but that collides with opto Block

    98 //     when building with precompiled headers.  There really should be

    99 //     an opto namespace.

   100 typedef TestAccess::Block OopBlock;

   101 // --- FIXME: Similarly, this typedef collides with opto BlockList.

   102 // typedef TestAccess::BlockList BlockList;

   103 

   104 static size_t list_length(const TestAccess::BlockList& list) {

   105   size_t result = 0;

   106   for (const OopBlock* block = list.chead();

   107        block != NULL;

   108        block = list.next(*block)) {

   109     ++result;

   110   }

   111   return result;

   112 }

   113 

   114 static void clear_list(TestAccess::BlockList& list) {

   115   OopBlock* next;

   116   for (OopBlock* block = list.head(); block != NULL; block = next) {

   117     next = list.next(*block);

   118     list.unlink(*block);

   119   }

   120 }

   121 

   122 static bool is_list_empty(const TestAccess::BlockList& list) {

   123   return list.chead() == NULL;

   124 }

   125 

   126 static void release_entry(OopStorage& storage, oop* entry) {

   127   *entry = NULL;

   128   storage.release(entry);

   129 }

   130 

   131 class OopStorageTest : public ::testing::Test {

   132 public:

   133   OopStorageTest();

   134   ~OopStorageTest();

   135 

   136   Mutex _allocate_mutex;

   137   Mutex _active_mutex;

   138   OopStorage _storage;

   139 

   140   static const int _active_rank = Mutex::leaf - 1;

   141   static const int _allocate_rank = Mutex::leaf;

   142 

   143   class CountingIterateClosure;

   144   template<bool is_const> class VM_CountAtSafepoint;

   145 };

   146 

   147 OopStorageTest::OopStorageTest() :

   148   _allocate_mutex(_allocate_rank,

   149                   "test_OopStorage_allocate",

   150                   false,

   151                   Mutex::_safepoint_check_never),

   152   _active_mutex(_active_rank,

   153                 "test_OopStorage_active",

   154                 false,

   155                 Mutex::_safepoint_check_never),

   156   _storage("Test Storage", &_allocate_mutex, &_active_mutex)

   157 { }

   158 

   159 OopStorageTest::~OopStorageTest() {

   160   clear_list(TestAccess::allocate_list(_storage));

   161   clear_list(TestAccess::active_list(_storage));

   162 }

   163 

   164 class OopStorageTestWithAllocation : public OopStorageTest {

   165 public:

   166   OopStorageTestWithAllocation();

   167 

   168   static const size_t _max_entries = 1000;

   169   oop* _entries[_max_entries];

   170 

   171   class VM_DeleteBlocksAtSafepoint;

   172 };

   173 

   174 OopStorageTestWithAllocation::OopStorageTestWithAllocation() {

   175   for (size_t i = 0; i < _max_entries; ++i) {

   176     _entries[i] = _storage.allocate();

   177     EXPECT_TRUE(_entries[i] != NULL);

   178     EXPECT_EQ(i + 1, _storage.allocation_count());

   179   }

   180 };

   181 

   182 const size_t OopStorageTestWithAllocation::_max_entries;

   183 

   184 class OopStorageTestWithAllocation::VM_DeleteBlocksAtSafepoint

   185   : public VM_GTestExecuteAtSafepoint {

   186 public:

   187   VM_DeleteBlocksAtSafepoint(OopStorage* storage, size_t retain) :

   188     _storage(storage), _retain(retain)

   189   {}

   190 

   191   void doit() {

   192     _storage->delete_empty_blocks_safepoint(_retain);

   193   }

   194 

   195 private:

   196   OopStorage* _storage;

   197   size_t _retain;

   198 };

   199 

   200 static bool is_allocate_list_sorted(const OopStorage& storage) {

   201   // The allocate_list isn't strictly sorted.  Rather, all empty

   202   // blocks are segregated to the end of the list.  And the number of

   203   // empty blocks should match empty_block_count().

   204   size_t expected_empty = storage.empty_block_count();

   205   const TestAccess::BlockList& list = TestAccess::allocate_list(storage);

   206   const OopBlock* block = list.ctail();

   207   for (size_t i = 0; i < expected_empty; ++i, block = list.prev(*block)) {

   208     if ((block == NULL) || !block->is_empty()) {

   209       return false;

   210     }

   211   }

   212   for ( ; block != NULL; block = list.prev(*block)) {

   213     if (block->is_empty()) {

   214       return false;

   215     }

   216   }

   217   return true;

   218 }

   219 

   220 static size_t total_allocation_count(const TestAccess::BlockList& list) {

   221   size_t total_count = 0;

   222   for (const OopBlock* block = list.chead();

   223        block != NULL;

   224        block = list.next(*block)) {

   225     total_count += TestAccess::block_allocation_count(*block);

   226   }

   227   return total_count;

   228 }

   229 

   230 TEST_VM_F(OopStorageTest, allocate_one) {

   231   EXPECT_TRUE(is_list_empty(TestAccess::active_list(_storage)));

   232   EXPECT_TRUE(is_list_empty(TestAccess::allocate_list(_storage)));

   233 

   234   oop* ptr = _storage.allocate();

   235   EXPECT_TRUE(ptr != NULL);

   236   EXPECT_EQ(1u, _storage.allocation_count());

   237 

   238   EXPECT_EQ(1u, list_length(TestAccess::active_list(_storage)));

   239   EXPECT_EQ(1u, _storage.block_count());

   240   EXPECT_EQ(1u, list_length(TestAccess::allocate_list(_storage)));

   241 

   242   EXPECT_EQ(0u, _storage.empty_block_count());

   243 

   244   const OopBlock* block = TestAccess::allocate_list(_storage).chead();

   245   EXPECT_NE(block, (OopBlock*)NULL);

   246   EXPECT_EQ(block, (TestAccess::active_list(_storage).chead()));

   247   EXPECT_FALSE(TestAccess::block_is_empty(*block));

   248   EXPECT_FALSE(TestAccess::block_is_full(*block));

   249   EXPECT_EQ(1u, TestAccess::block_allocation_count(*block));

   250 

   251   release_entry(_storage, ptr);

   252   EXPECT_EQ(0u, _storage.allocation_count());

   253 

   254   EXPECT_EQ(1u, list_length(TestAccess::active_list(_storage)));

   255   EXPECT_EQ(1u, _storage.block_count());

   256   EXPECT_EQ(1u, list_length(TestAccess::allocate_list(_storage)));

   257 

   258   EXPECT_EQ(1u, _storage.empty_block_count());

   259 

   260   const OopBlock* new_block = TestAccess::allocate_list(_storage).chead();

   261   EXPECT_EQ(block, new_block);

   262   EXPECT_EQ(block, (TestAccess::active_list(_storage).chead()));

   263   EXPECT_TRUE(TestAccess::block_is_empty(*block));

   264   EXPECT_FALSE(TestAccess::block_is_full(*block));

   265   EXPECT_EQ(0u, TestAccess::block_allocation_count(*block));

   266 }

   267 

   268 TEST_VM_F(OopStorageTest, allocation_count) {

   269   static const size_t max_entries = 1000;

   270   oop* entries[max_entries];

   271 

   272   TestAccess::BlockList& active_list = TestAccess::active_list(_storage);

   273   TestAccess::BlockList& allocate_list = TestAccess::allocate_list(_storage);

   274 

   275   EXPECT_TRUE(is_list_empty(active_list));

   276   EXPECT_EQ(0u, _storage.block_count());

   277   EXPECT_TRUE(is_list_empty(allocate_list));

   278 

   279   size_t allocated = 0;

   280   for ( ; allocated < max_entries; ++allocated) {

   281     EXPECT_EQ(allocated, _storage.allocation_count());

   282     if (!is_list_empty(active_list)) {

   283       EXPECT_EQ(1u, list_length(active_list));

   284       EXPECT_EQ(1u, _storage.block_count());

   285       const OopBlock& block = *active_list.chead();

   286       EXPECT_EQ(allocated, TestAccess::block_allocation_count(block));

   287       if (TestAccess::block_is_full(block)) {

   288         break;

   289       } else {

   290         EXPECT_FALSE(is_list_empty(allocate_list));

   291         EXPECT_EQ(&block, allocate_list.chead());

   292       }

   293     }

   294     entries[allocated] = _storage.allocate();

   295   }

   296 

   297   EXPECT_EQ(allocated, _storage.allocation_count());

   298   EXPECT_EQ(1u, list_length(active_list));

   299   EXPECT_EQ(1u, _storage.block_count());

   300   EXPECT_TRUE(is_list_empty(allocate_list));

   301   const OopBlock& block = *active_list.chead();

   302   EXPECT_TRUE(TestAccess::block_is_full(block));

   303   EXPECT_EQ(allocated, TestAccess::block_allocation_count(block));

   304 

   305   for (size_t i = 0; i < allocated; ++i) {

   306     release_entry(_storage, entries[i]);

   307     size_t remaining = allocated - (i + 1);

   308     EXPECT_EQ(remaining, TestAccess::block_allocation_count(block));

   309     EXPECT_EQ(remaining, _storage.allocation_count());

   310     EXPECT_FALSE(is_list_empty(allocate_list));

   311   }

   312 }

   313 

   314 TEST_VM_F(OopStorageTest, allocate_many) {

   315   static const size_t max_entries = 1000;

   316   oop* entries[max_entries];

   317 

   318   TestAccess::BlockList& active_list = TestAccess::active_list(_storage);

   319   TestAccess::BlockList& allocate_list = TestAccess::allocate_list(_storage);

   320 

   321   EXPECT_EQ(0u, _storage.empty_block_count());

   322 

   323   entries[0] = _storage.allocate();

   324   ASSERT_TRUE(entries[0] != NULL);

   325   EXPECT_EQ(1u, list_length(active_list));

   326   EXPECT_EQ(1u, _storage.block_count());

   327   EXPECT_EQ(1u, list_length(allocate_list));

   328   EXPECT_EQ(0u, _storage.empty_block_count());

   329 

   330   const OopBlock* block = active_list.chead();

   331   EXPECT_EQ(1u, TestAccess::block_allocation_count(*block));

   332   EXPECT_EQ(block, allocate_list.chead());

   333 

   334   for (size_t i = 1; i < max_entries; ++i) {

   335     entries[i] = _storage.allocate();

   336     EXPECT_EQ(i + 1, _storage.allocation_count());

   337     ASSERT_TRUE(entries[i] != NULL);

   338     EXPECT_EQ(0u, _storage.empty_block_count());

   339 

   340     if (block == NULL) {

   341       ASSERT_FALSE(is_list_empty(allocate_list));

   342       EXPECT_EQ(1u, list_length(allocate_list));

   343       block = allocate_list.chead();

   344       EXPECT_EQ(1u, TestAccess::block_allocation_count(*block));

   345       EXPECT_EQ(block, active_list.chead());

   346     } else if (TestAccess::block_is_full(*block)) {

   347       EXPECT_TRUE(is_list_empty(allocate_list));

   348       block = NULL;

   349     } else {

   350       EXPECT_FALSE(is_list_empty(allocate_list));

   351       EXPECT_EQ(block, allocate_list.chead());

   352       EXPECT_EQ(block, active_list.chead());

   353     }

   354   }

   355 

   356   if (block != NULL) {

   357     EXPECT_NE(0u, TestAccess::block_allocation_count(*block));

   358     EXPECT_FALSE(is_list_empty(allocate_list));

   359     EXPECT_EQ(block, allocate_list.chead());

   360     EXPECT_EQ(block, active_list.chead());

   361   }

   362 

   363   size_t active_count = list_length(active_list);

   364 

   365   for (size_t i = 0; i < max_entries; ++i) {

   366     release_entry(_storage, entries[i]);

   367     EXPECT_TRUE(is_allocate_list_sorted(_storage));

   368     EXPECT_EQ(max_entries - (i + 1), total_allocation_count(active_list));

   369   }

   370 

   371   EXPECT_EQ(list_length(active_list), list_length(allocate_list));

   372   EXPECT_EQ(list_length(active_list), _storage.block_count());

   373   EXPECT_EQ(list_length(active_list), _storage.empty_block_count());

   374   for (const OopBlock* block = allocate_list.chead();

   375        block != NULL;

   376        block = allocate_list.next(*block)) {

   377     EXPECT_TRUE(TestAccess::block_is_empty(*block));

   378   }

   379 }

   380 

   381 TEST_VM_F(OopStorageTestWithAllocation, random_release) {

   382   static const size_t step = 11;

   383   ASSERT_NE(0u, _max_entries % step); // max_entries and step are mutually prime

   384 

   385   EXPECT_EQ(0u, _storage.empty_block_count());

   386 

   387   TestAccess::BlockList& active_list = TestAccess::active_list(_storage);

   388   TestAccess::BlockList& allocate_list = TestAccess::allocate_list(_storage);

   389 

   390   EXPECT_EQ(_max_entries, total_allocation_count(active_list));

   391   EXPECT_GE(1u, list_length(allocate_list));

   392 

   393   // Release all entries in "random" order.

   394   size_t released = 0;

   395   for (size_t i = 0; released < _max_entries; i = (i + step) % _max_entries) {

   396     if (_entries[i] != NULL) {

   397       release_entry(_storage, _entries[i]);

   398       _entries[i] = NULL;

   399       ++released;

   400       EXPECT_EQ(_max_entries - released, total_allocation_count(active_list));

   401       EXPECT_TRUE(is_allocate_list_sorted(_storage));

   402     }

   403   }

   404 

   405   EXPECT_EQ(list_length(active_list), list_length(allocate_list));

   406   EXPECT_EQ(list_length(active_list), _storage.block_count());

   407   EXPECT_EQ(0u, total_allocation_count(active_list));

   408   EXPECT_EQ(list_length(allocate_list), _storage.empty_block_count());

   409 }

   410 

   411 TEST_VM_F(OopStorageTestWithAllocation, random_allocate_release) {

   412   static const size_t release_step = 11;

   413   static const size_t allocate_step = 5;

   414   ASSERT_NE(0u, _max_entries % release_step); // max_entries and step are mutually prime

   415 

   416   EXPECT_EQ(0u, _storage.empty_block_count());

   417 

   418   TestAccess::BlockList& active_list = TestAccess::active_list(_storage);

   419   TestAccess::BlockList& allocate_list = TestAccess::allocate_list(_storage);

   420 

   421   EXPECT_EQ(_max_entries, total_allocation_count(active_list));

   422   EXPECT_GE(1u, list_length(allocate_list));

   423 

   424   // Release all entries in "random" order, "randomly" interspersed

   425   // with additional allocations.

   426   size_t released = 0;

   427   size_t total_released = 0;

   428   for (size_t i = 0; released < _max_entries; i = (i + release_step) % _max_entries) {

   429     if (_entries[i] != NULL) {

   430       release_entry(_storage, _entries[i]);

   431       _entries[i] = NULL;

   432       ++released;

   433       ++total_released;

   434       EXPECT_EQ(_max_entries - released, total_allocation_count(active_list));

   435       EXPECT_TRUE(is_allocate_list_sorted(_storage));

   436       if (total_released % allocate_step == 0) {

   437         _entries[i] = _storage.allocate();

   438         --released;

   439         EXPECT_EQ(_max_entries - released, total_allocation_count(active_list));

   440         EXPECT_TRUE(is_allocate_list_sorted(_storage));

   441       }

   442     }

   443   }

   444 

   445   EXPECT_EQ(list_length(active_list), list_length(allocate_list));

   446   EXPECT_EQ(list_length(active_list), _storage.block_count());

   447   EXPECT_EQ(0u, total_allocation_count(active_list));

   448   EXPECT_EQ(list_length(allocate_list), _storage.empty_block_count());

   449 }

   450 

   451 template<bool sorted>

   452 class OopStorageTestBlockRelease : public OopStorageTestWithAllocation {

   453 public:

   454   void SetUp() {

   455     size_t nrelease = _max_entries / 2;

   456     oop** to_release = NEW_C_HEAP_ARRAY(oop*, nrelease, mtInternal);

   457 

   458     for (size_t i = 0; i < nrelease; ++i) {

   459       to_release[i] = _entries[2 * i];

   460       *to_release[i] = NULL;

   461     }

   462     if (sorted) {

   463       QuickSort::sort(to_release, nrelease, PointerCompare(), false);

   464     }

   465 

   466     _storage.release(to_release, nrelease);

   467     EXPECT_EQ(_max_entries - nrelease, _storage.allocation_count());

   468 

   469     for (size_t i = 0; i < nrelease; ++i) {

   470       release_entry(_storage, _entries[2 * i + 1]);

   471       EXPECT_EQ(_max_entries - nrelease - (i + 1), _storage.allocation_count());

   472     }

   473 

   474     EXPECT_EQ(_storage.block_count(), _storage.empty_block_count());

   475 

   476     FREE_C_HEAP_ARRAY(oop*, to_release);

   477   }

   478 

   479   struct PointerCompare {

   480     int operator()(const void* p, const void* q) const {

   481       return (p < q) ? -1 : int(p != q);

   482     }

   483   };

   484 };

   485 

   486 typedef OopStorageTestBlockRelease<true> OopStorageTestBlockReleaseSorted;

   487 typedef OopStorageTestBlockRelease<false> OopStorageTestBlockReleaseUnsorted;

   488 

   489 TEST_VM_F(OopStorageTestBlockReleaseSorted, block_release) {}

   490 TEST_VM_F(OopStorageTestBlockReleaseUnsorted, block_release) {}

   491 

   492 #ifndef DISABLE_GARBAGE_ALLOCATION_STATUS_TESTS

   493 TEST_VM_F(OopStorageTest, invalid_pointer) {

   494   {

   495     char* mem = NEW_C_HEAP_ARRAY(char, 1000, mtInternal);

   496     oop* ptr = reinterpret_cast<oop*>(align_down(mem + 250, sizeof(oop)));

   497     // Predicate returns false for some malloc'ed block.

   498     EXPECT_EQ(OopStorage::INVALID_ENTRY, _storage.allocation_status(ptr));

   499     FREE_C_HEAP_ARRAY(char, mem);

   500   }

   501 

   502   {

   503     oop obj;

   504     oop* ptr = &obj;

   505     // Predicate returns false for some "random" location.

   506     EXPECT_EQ(OopStorage::INVALID_ENTRY, _storage.allocation_status(ptr));

   507   }

   508 }

   509 #endif // DISABLE_GARBAGE_ALLOCATION_STATUS_TESTS

   510 

   511 class OopStorageTest::CountingIterateClosure VALUE_OBJ_CLASS_SPEC {

   512 public:

   513   size_t _const_count;

   514   size_t _const_non_null;

   515   size_t _non_const_count;

   516   size_t _non_const_non_null;

   517 

   518   void do_oop(const oop* ptr) {

   519     ++_const_count;

   520     if (*ptr != NULL) {

   521       ++_const_non_null;

   522     }

   523   }

   524 

   525   void do_oop(oop* ptr) {

   526     ++_non_const_count;

   527     if (*ptr != NULL) {

   528       ++_non_const_non_null;

   529     }

   530   }

   531 

   532   CountingIterateClosure() :

   533     _const_count(0),

   534     _const_non_null(0),

   535     _non_const_count(0),

   536     _non_const_non_null(0)

   537   {}

   538 };

   539 

   540 template<bool is_const>

   541 class OopStorageTest::VM_CountAtSafepoint : public VM_GTestExecuteAtSafepoint {

   542 public:

   543   typedef typename Conditional<is_const,

   544                                const OopStorage,

   545                                OopStorage>::type Storage;

   546 

   547   VM_CountAtSafepoint(Storage* storage, CountingIterateClosure* cl) :

   548     _storage(storage), _cl(cl)

   549   {}

   550 

   551   void doit() { _storage->oops_do(_cl); }

   552 

   553 private:

   554   Storage* _storage;

   555   CountingIterateClosure* _cl;

   556 };

   557 

   558 TEST_VM_F(OopStorageTest, simple_iterate) {

   559   // Dummy oop value.

   560   intptr_t dummy_oop_value = 0xbadbeaf;

   561   oop dummy_oop = reinterpret_cast<oopDesc*>(&dummy_oop_value);

   562 

   563   const size_t max_entries = 1000;

   564   oop* entries[max_entries];

   565 

   566   size_t allocated = 0;

   567   size_t entries_with_values = 0;

   568   for (size_t i = 0; i < max_entries; i += 10) {

   569     for ( ; allocated < i; ++allocated) {

   570       entries[allocated] = _storage.allocate();

   571       ASSERT_TRUE(entries[allocated] != NULL);

   572       if ((allocated % 3) != 0) {

   573         *entries[allocated] = dummy_oop;

   574         ++entries_with_values;

   575       }

   576     }

   577 

   578     {

   579       CountingIterateClosure cl;

   580       VM_CountAtSafepoint<false> op(&_storage, &cl);

   581       {

   582         ThreadInVMfromNative invm(JavaThread::current());

   583         VMThread::execute(&op);

   584       }

   585       EXPECT_EQ(allocated, cl._non_const_count);

   586       EXPECT_EQ(entries_with_values, cl._non_const_non_null);

   587       EXPECT_EQ(0u, cl._const_count);

   588       EXPECT_EQ(0u, cl._const_non_null);

   589     }

   590 

   591     {

   592       CountingIterateClosure cl;

   593       VM_CountAtSafepoint<true> op(&_storage, &cl);

   594       {

   595         ThreadInVMfromNative invm(JavaThread::current());

   596         VMThread::execute(&op);

   597       }

   598       EXPECT_EQ(allocated, cl._const_count);

   599       EXPECT_EQ(entries_with_values, cl._const_non_null);

   600       EXPECT_EQ(0u, cl._non_const_count);

   601       EXPECT_EQ(0u, cl._non_const_non_null);

   602     }

   603   }

   604 

   605   while (allocated > 0) {

   606     release_entry(_storage, entries[--allocated]);

   607   }

   608 }

   609 

   610 class OopStorageTestIteration : public OopStorageTestWithAllocation {

   611 public:

   612   static const size_t _max_workers = 2;

   613   unsigned char _states[_max_workers][_max_entries];

   614 

   615   static const unsigned char mark_released  = 1u << 0;

   616   static const unsigned char mark_invalid   = 1u << 1;

   617   static const unsigned char mark_const     = 1u << 2;

   618   static const unsigned char mark_non_const = 1u << 3;

   619 

   620   virtual void SetUp() {

   621     OopStorageTestWithAllocation::SetUp();

   622 

   623     memset(_states, 0, sizeof(_states));

   624 

   625     size_t initial_release = 0;

   626     for ( ; _storage.empty_block_count() < 2; ++initial_release) {

   627       ASSERT_GT(_max_entries, initial_release);

   628       release_entry(_storage, _entries[initial_release]);

   629       _states[0][initial_release] = mark_released;

   630     }

   631 

   632     for (size_t i = initial_release; i < _max_entries; i += 3) {

   633       release_entry(_storage, _entries[i]);

   634       _states[0][i] = mark_released;

   635     }

   636   }

   637 

   638   class VerifyState;

   639   class VerifyFn;

   640   template<bool is_const> class VM_Verify;

   641 

   642   class VerifyClosure;

   643   class VM_VerifyUsingOopsDo;

   644 };

   645 

   646 const unsigned char OopStorageTestIteration::mark_released;

   647 const unsigned char OopStorageTestIteration::mark_invalid;

   648 const unsigned char OopStorageTestIteration::mark_const;

   649 const unsigned char OopStorageTestIteration::mark_non_const;

   650 

   651 class OopStorageTestIteration::VerifyState VALUE_OBJ_CLASS_SPEC {

   652 public:

   653   unsigned char _expected_mark;

   654   const oop* const* _entries;

   655   unsigned char (&_states)[_max_workers][_max_entries];

   656 

   657   VerifyState(unsigned char expected_mark,

   658               const oop* const* entries,

   659               unsigned char (&states)[_max_workers][_max_entries]) :

   660     _expected_mark(expected_mark),

   661     _entries(entries),

   662     _states(states)

   663   { }

   664 

   665   bool update(const oop* ptr, uint worker_id, unsigned char mark) const {

   666     size_t index = 0;

   667     bool found = find_entry(ptr, &index);

   668     EXPECT_TRUE(found);

   669     EXPECT_GT(_max_entries, index);

   670     EXPECT_GT(_max_workers, worker_id);

   671     if (!found) {

   672       return false;

   673     } else if (index >= _max_entries) {

   674       return false;

   675     } else if (worker_id >= _max_workers) {

   676       return false;

   677     } else {

   678       EXPECT_EQ(0, _states[worker_id][index]);

   679       if (_states[worker_id][index] != 0) {

   680         _states[worker_id][index] |= mark_invalid;

   681         return false;

   682       } else {

   683         _states[worker_id][index] |= mark;

   684         return true;

   685       }

   686     }

   687   }

   688 

   689   void check() const {

   690     for (size_t i = 0; i < _max_entries; ++i) {

   691       unsigned char mark = 0;

   692       for (size_t w = 0; w < _max_workers; ++w) {

   693         if (mark == 0) {

   694           mark = _states[w][i];

   695         } else {

   696           EXPECT_EQ(0u, _states[w][i]);

   697         }

   698       }

   699       if (mark == 0) {

   700         EXPECT_NE(0u, mark);

   701       } else if ((mark & mark_released) != 0) {

   702         EXPECT_EQ(mark_released, mark);

   703       } else {

   704         EXPECT_EQ(_expected_mark, mark);

   705       }

   706     }

   707   }

   708 

   709 private:

   710   bool find_entry(const oop* ptr, size_t* index) const {

   711     for (size_t i = 0; i < _max_entries; ++i) {

   712       if (ptr == _entries[i]) {

   713         *index = i;

   714         return true;

   715       }

   716     }

   717     return false;

   718   }

   719 };

   720 

   721 class OopStorageTestIteration::VerifyFn VALUE_OBJ_CLASS_SPEC {

   722 public:

   723   VerifyFn(VerifyState* state, uint worker_id = 0) :

   724     _state(state),

   725     _worker_id(worker_id)

   726   {}

   727 

   728   bool operator()(      oop* ptr) const {

   729     return _state->update(ptr, _worker_id, mark_non_const);

   730   }

   731 

   732   bool operator()(const oop* ptr) const {

   733     return _state->update(ptr, _worker_id, mark_const);

   734   }

   735 

   736 private:

   737   VerifyState* _state;

   738   uint _worker_id;

   739 };

   740 

   741 class OopStorageTestIteration::VerifyClosure VALUE_OBJ_CLASS_SPEC {

   742 public:

   743   VerifyClosure(VerifyState* state, uint worker_id = 0) :

   744     _state(state),

   745     _worker_id(worker_id)

   746   {}

   747 

   748   void do_oop(oop* ptr) {

   749     _state->update(ptr, _worker_id, mark_non_const);

   750   }

   751 

   752   void do_oop(const oop* ptr) {

   753     _state->update(ptr, _worker_id, mark_const);

   754   }

   755 

   756 private:

   757   VerifyState* _state;

   758   uint _worker_id;

   759 };

   760 

   761 const size_t OopStorageTestIteration::_max_workers;

   762 

   763 template<bool is_const>

   764 class OopStorageTestIteration::VM_Verify : public VM_GTestExecuteAtSafepoint {

   765 public:

   766   typedef typename Conditional<is_const,

   767                                const OopStorage,

   768                                OopStorage>::type Storage;

   769 

   770   VM_Verify(Storage* storage, VerifyState* vstate) :

   771     _storage(storage), _vstate(vstate), _result(false)

   772   {}

   773 

   774   void doit() {

   775     VerifyFn verifier(_vstate);

   776     _result = _storage->iterate_safepoint(verifier);

   777   }

   778 

   779   bool result() const { return _result; }

   780 

   781 private:

   782   Storage* _storage;

   783   VerifyState* _vstate;

   784   bool _result;

   785 };

   786 

   787 class OopStorageTestIteration::VM_VerifyUsingOopsDo : public VM_GTestExecuteAtSafepoint {

   788 public:

   789   VM_VerifyUsingOopsDo(OopStorage* storage, VerifyState* vstate) :

   790     _storage(storage), _vstate(vstate)

   791   {}

   792 

   793   void doit() {

   794     VerifyClosure verifier(_vstate);

   795     _storage->oops_do(&verifier);

   796   }

   797 

   798 private:

   799   OopStorage* _storage;

   800   VerifyState* _vstate;

   801 };

   802 

   803 TEST_VM_F(OopStorageTestIteration, iterate_safepoint) {

   804   VerifyState vstate(mark_non_const, _entries, _states);

   805   VM_Verify<false> op(&_storage, &vstate);

   806   {

   807     ThreadInVMfromNative invm(JavaThread::current());

   808     VMThread::execute(&op);

   809   }

   810   EXPECT_TRUE(op.result());

   811   vstate.check();

   812 }

   813 

   814 TEST_VM_F(OopStorageTestIteration, const_iterate_safepoint) {

   815   VerifyState vstate(mark_const, _entries, _states);

   816   VM_Verify<true> op(&_storage, &vstate);

   817   {

   818     ThreadInVMfromNative invm(JavaThread::current());

   819     VMThread::execute(&op);

   820   }

   821   EXPECT_TRUE(op.result());

   822   vstate.check();

   823 }

   824 

   825 TEST_VM_F(OopStorageTestIteration, oops_do) {

   826   VerifyState vstate(mark_non_const, _entries, _states);

   827   VM_VerifyUsingOopsDo op(&_storage, &vstate);

   828   {

   829     ThreadInVMfromNative invm(JavaThread::current());

   830     VMThread::execute(&op);

   831   }

   832   vstate.check();

   833 }

   834 

   835 // Parallel iteration not available unless INCLUDE_ALL_GCS

   836 #if INCLUDE_ALL_GCS

   837 

   838 class OopStorageTestParIteration : public OopStorageTestIteration {

   839 public:

   840   WorkGang* workers();

   841 

   842   class VM_ParStateVerify;

   843 

   844   template<bool concurrent, bool is_const> class Task;

   845   template<bool concurrent, bool is_const> class TaskUsingOopsDo;

   846 

   847 private:

   848   static WorkGang* _workers;

   849 };

   850 

   851 WorkGang* OopStorageTestParIteration::_workers = NULL;

   852 

   853 WorkGang* OopStorageTestParIteration::workers() {

   854   if (_workers == NULL) {

   855     _workers = new WorkGang("OopStorageTestParIteration workers",

   856                             _max_workers,

   857                             false,

   858                             false);

   859     _workers->initialize_workers();

   860     _workers->update_active_workers(_max_workers);

   861   }

   862   return _workers;

   863 }

   864 

   865 template<bool concurrent, bool is_const>

   866 class OopStorageTestParIteration::Task : public AbstractGangTask {

   867   typedef OopStorage::ParState<concurrent, is_const> StateType;

   868 

   869   typedef typename Conditional<is_const,

   870                                const OopStorage,

   871                                OopStorage>::type Storage;

   872 

   873 public:

   874   Task(const char* name, Storage* storage, VerifyState* vstate) :

   875     AbstractGangTask(name, GCId::undefined()),

   876     _state(storage),

   877     _vstate(vstate)

   878   {}

   879 

   880   virtual void work(uint worker_id) {

   881     VerifyFn verifier(_vstate, worker_id);

   882     _state.iterate(verifier);

   883   }

   884 

   885 private:

   886   StateType _state;

   887   VerifyState* _vstate;

   888 };

   889 

   890 template<bool concurrent, bool is_const>

   891 class OopStorageTestParIteration::TaskUsingOopsDo : public AbstractGangTask {

   892 public:

   893   TaskUsingOopsDo(const char* name, OopStorage* storage, VerifyState* vstate) :

   894     AbstractGangTask(name, GCId::undefined()),

   895     _state(storage),

   896     _vstate(vstate)

   897   {}

   898 

   899   virtual void work(uint worker_id) {

   900     VerifyClosure verifier(_vstate, worker_id);

   901     _state.oops_do(&verifier);

   902   }

   903 

   904 private:

   905   OopStorage::ParState<concurrent, is_const> _state;

   906   VerifyState* _vstate;

   907 };

   908 

   909 class OopStorageTestParIteration::VM_ParStateVerify : public VM_GTestExecuteAtSafepoint {

   910 public:

   911   VM_ParStateVerify(WorkGang* workers, AbstractGangTask* task) :

   912     _workers(workers), _task(task)

   913   {}

   914 

   915   void doit() {

   916     _workers->run_task(_task);

   917   }

   918 

   919 private:

   920   WorkGang* _workers;

   921   AbstractGangTask* _task;

   922 };

   923 

   924 TEST_VM_F(OopStorageTestParIteration, par_state_safepoint_iterate) {

   925   VerifyState vstate(mark_non_const, _entries, _states);

   926   Task<false, false> task("test", &_storage, &vstate);

   927   VM_ParStateVerify op(workers(), &task);

   928   {

   929     ThreadInVMfromNative invm(JavaThread::current());

   930     VMThread::execute(&op);

   931   }

   932   vstate.check();

   933 }

   934 

   935 TEST_VM_F(OopStorageTestParIteration, par_state_safepoint_const_iterate) {

   936   VerifyState vstate(mark_const, _entries, _states);

   937   Task<false, true> task("test", &_storage, &vstate);

   938   VM_ParStateVerify op(workers(), &task);

   939   {

   940     ThreadInVMfromNative invm(JavaThread::current());

   941     VMThread::execute(&op);

   942   }

   943   vstate.check();

   944 }

   945 

   946 TEST_VM_F(OopStorageTestParIteration, par_state_safepoint_oops_do) {

   947   VerifyState vstate(mark_non_const, _entries, _states);

   948   TaskUsingOopsDo<false, false> task("test", &_storage, &vstate);

   949   VM_ParStateVerify op(workers(), &task);

   950   {

   951     ThreadInVMfromNative invm(JavaThread::current());

   952     VMThread::execute(&op);

   953   }

   954   vstate.check();

   955 }

   956 

   957 TEST_VM_F(OopStorageTestParIteration, par_state_safepoint_const_oops_do) {

   958   VerifyState vstate(mark_const, _entries, _states);

   959   TaskUsingOopsDo<false, true> task("test", &_storage, &vstate);

   960   VM_ParStateVerify op(workers(), &task);

   961   {

   962     ThreadInVMfromNative invm(JavaThread::current());

   963     VMThread::execute(&op);

   964   }

   965   vstate.check();

   966 }

   967 

   968 TEST_VM_F(OopStorageTestParIteration, par_state_concurrent_iterate) {

   969   VerifyState vstate(mark_non_const, _entries, _states);

   970   Task<true, false> task("test", &_storage, &vstate);

   971   workers()->run_task(&task);

   972   vstate.check();

   973 }

   974 

   975 TEST_VM_F(OopStorageTestParIteration, par_state_concurrent_const_iterate) {

   976   VerifyState vstate(mark_const, _entries, _states);

   977   Task<true, true> task("test", &_storage, &vstate);

   978   workers()->run_task(&task);

   979   vstate.check();

   980 }

   981 

   982 TEST_VM_F(OopStorageTestParIteration, par_state_concurrent_oops_do) {

   983   VerifyState vstate(mark_non_const, _entries, _states);

   984   TaskUsingOopsDo<true, false> task("test", &_storage, &vstate);

   985   workers()->run_task(&task);

   986   vstate.check();

   987 }

   988 

   989 TEST_VM_F(OopStorageTestParIteration, par_state_concurrent_const_oops_do) {

   990   VerifyState vstate(mark_const, _entries, _states);

   991   TaskUsingOopsDo<true, true> task("test", &_storage, &vstate);

   992   workers()->run_task(&task);

   993   vstate.check();

   994 }

   995 

   996 #endif // INCLUDE_ALL_GCS

   997 

   998 TEST_VM_F(OopStorageTestWithAllocation, delete_empty_blocks_safepoint) {

   999   TestAccess::BlockList& active_list = TestAccess::active_list(_storage);

  1000 

  1001   size_t initial_active_size = list_length(active_list);

  1002   EXPECT_EQ(initial_active_size, _storage.block_count());

  1003   ASSERT_LE(3u, initial_active_size); // Need at least 3 blocks for test

  1004 

  1005   for (size_t i = 0; _storage.empty_block_count() < 3; ++i) {

  1006     ASSERT_GT(_max_entries, i);

  1007     release_entry(_storage, _entries[i]);

  1008   }

  1009 

  1010   EXPECT_EQ(initial_active_size, list_length(active_list));

  1011   EXPECT_EQ(initial_active_size, _storage.block_count());

  1012   EXPECT_EQ(3u, _storage.empty_block_count());

  1013 

  1014   {

  1015     ThreadInVMfromNative invm(JavaThread::current());

  1016     VM_DeleteBlocksAtSafepoint op(&_storage, 2);

  1017     VMThread::execute(&op);

  1018   }

  1019   EXPECT_EQ(2u, _storage.empty_block_count());

  1020   EXPECT_EQ(initial_active_size - 1, list_length(active_list));

  1021   EXPECT_EQ(initial_active_size - 1, _storage.block_count());

  1022 

  1023   {

  1024     ThreadInVMfromNative invm(JavaThread::current());

  1025     VM_DeleteBlocksAtSafepoint op(&_storage, 0);

  1026     VMThread::execute(&op);

  1027   }

  1028   EXPECT_EQ(0u, _storage.empty_block_count());

  1029   EXPECT_EQ(initial_active_size - 3, list_length(active_list));

  1030   EXPECT_EQ(initial_active_size - 3, _storage.block_count());

  1031 }

  1032 

  1033 TEST_VM_F(OopStorageTestWithAllocation, delete_empty_blocks_concurrent) {

  1034   TestAccess::BlockList& active_list = TestAccess::active_list(_storage);

  1035 

  1036   size_t initial_active_size = list_length(active_list);

  1037   EXPECT_EQ(initial_active_size, _storage.block_count());

  1038   ASSERT_LE(3u, initial_active_size); // Need at least 3 blocks for test

  1039 

  1040   for (size_t i = 0; _storage.empty_block_count() < 3; ++i) {

  1041     ASSERT_GT(_max_entries, i);

  1042     release_entry(_storage, _entries[i]);

  1043   }

  1044 

  1045   EXPECT_EQ(initial_active_size, list_length(active_list));

  1046   EXPECT_EQ(initial_active_size, _storage.block_count());

  1047   EXPECT_EQ(3u, _storage.empty_block_count());

  1048 

  1049   _storage.delete_empty_blocks_concurrent(2);

  1050   EXPECT_EQ(2u, _storage.empty_block_count());

  1051   EXPECT_EQ(initial_active_size - 1, list_length(active_list));

  1052   EXPECT_EQ(initial_active_size - 1, _storage.block_count());

  1053 

  1054   _storage.delete_empty_blocks_concurrent(0);

  1055   EXPECT_EQ(0u, _storage.empty_block_count());

  1056   EXPECT_EQ(initial_active_size - 3, list_length(active_list));

  1057   EXPECT_EQ(initial_active_size - 3, _storage.block_count());

  1058 }

  1059 

  1060 TEST_VM_F(OopStorageTestWithAllocation, allocation_status) {

  1061   oop* retained = _entries[200];

  1062   oop* released = _entries[300];

  1063   oop* garbage = reinterpret_cast<oop*>(1024 * 1024);

  1064   release_entry(_storage, released);

  1065 

  1066   EXPECT_EQ(OopStorage::ALLOCATED_ENTRY, _storage.allocation_status(retained));

  1067   EXPECT_EQ(OopStorage::UNALLOCATED_ENTRY, _storage.allocation_status(released));

  1068 #ifndef DISABLE_GARBAGE_ALLOCATION_STATUS_TESTS

  1069   EXPECT_EQ(OopStorage::INVALID_ENTRY, _storage.allocation_status(garbage));

  1070 #endif

  1071 

  1072   for (size_t i = 0; i < _max_entries; ++i) {

  1073     if ((_entries[i] != retained) && (_entries[i] != released)) {

  1074       release_entry(_storage, _entries[i]);

  1075     }

  1076   }

  1077 

  1078   {

  1079     ThreadInVMfromNative invm(JavaThread::current());

  1080     VM_DeleteBlocksAtSafepoint op(&_storage, 0);

  1081     VMThread::execute(&op);

  1082   }

  1083   EXPECT_EQ(OopStorage::ALLOCATED_ENTRY, _storage.allocation_status(retained));

  1084 #ifndef DISABLE_GARBAGE_ALLOCATION_STATUS_TESTS

  1085   EXPECT_EQ(OopStorage::INVALID_ENTRY, _storage.allocation_status(released));

  1086   EXPECT_EQ(OopStorage::INVALID_ENTRY, _storage.allocation_status(garbage));

  1087 #endif // DISABLE_GARBAGE_ALLOCATION_STATUS_TESTS

  1088 }

  1089 

  1090 TEST_VM_F(OopStorageTest, usage_info) {

  1091   size_t goal_blocks = 5;

  1092   oop* entries[1000];

  1093   size_t allocated = 0;

  1094 

  1095   EXPECT_EQ(0u, _storage.block_count());

  1096   // There is non-block overhead, so always some usage.

  1097   EXPECT_LT(0u, _storage.total_memory_usage());

  1098 

  1099   while (_storage.block_count() < goal_blocks) {

  1100     size_t this_count = _storage.block_count();

  1101     while (_storage.block_count() == this_count) {

  1102       ASSERT_GT(ARRAY_SIZE(entries), allocated);

  1103       entries[allocated] = _storage.allocate();

  1104       ASSERT_TRUE(entries[allocated] != NULL);

  1105       ++allocated;

  1106     }

  1107     EXPECT_NE(0u, _storage.block_count());

  1108     EXPECT_NE(0u, _storage.total_memory_usage());

  1109   }

  1110 

  1111   EXPECT_LT(TestAccess::memory_per_block() * _storage.block_count(),

  1112             _storage.total_memory_usage());

  1113 }

  1114 

  1115 #ifndef PRODUCT

  1116 

  1117 TEST_VM_F(OopStorageTestWithAllocation, print_storage) {

  1118   // Release the first 1/2

  1119   for (size_t i = 0; i < (_max_entries / 2); ++i) {

  1120     release_entry(_storage, _entries[i]);

  1121     _entries[i] = NULL;

  1122   }

  1123   // Release every other remaining

  1124   for (size_t i = _max_entries / 2; i < _max_entries; i += 2) {

  1125     release_entry(_storage, _entries[i]);

  1126     _entries[i] = NULL;

  1127   }

  1128 

  1129   size_t expected_entries = _max_entries / 4;

  1130   EXPECT_EQ(expected_entries, _storage.allocation_count());

  1131 

  1132   size_t entries_per_block = BitsPerWord;

  1133   size_t expected_blocks = (_max_entries + entries_per_block - 1) / entries_per_block;

  1134   EXPECT_EQ(expected_blocks, _storage.block_count());

  1135