1 /*
   2  * Copyright (c) 2019, 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 
  25 #include "precompiled.hpp"
  26 #include "gc/g1/g1FreeIdSet.hpp"
  27 #include "memory/allocation.hpp"
  28 #include "runtime/atomic.hpp"
  29 #include "runtime/interfaceSupport.inline.hpp"
  30 #include "runtime/orderAccess.hpp"
  31 #include "runtime/semaphore.inline.hpp"
  32 #include "runtime/thread.hpp"
  33 #include "utilities/debug.hpp"
  34 #include "utilities/globalDefinitions.hpp"
  35 #include "utilities/ostream.hpp"
  36 #include "threadHelper.inline.hpp"
  37 #include "unittest.hpp"
  38 
  39 struct G1FreeIdSet::TestSupport : AllStatic {
  40   static uint next(const G1FreeIdSet& set, uint index) {
  41     assert(index < set._size, "precondition");
  42     return set._next[index];
  43   }
  44 
  45   static uint start(const G1FreeIdSet& set) { return set._start; }
  46   static uint size(const G1FreeIdSet& set) { return set._size; }
  47   static uintx mask(const G1FreeIdSet& set) { return set._head_index_mask; }
  48   static uintx head(const G1FreeIdSet& set) { return Atomic::load(&set._head); }
  49 
  50   static uint head_index(const G1FreeIdSet& set, uintx head) {
  51     return set.head_index(head);
  52   }
  53 };
  54 
  55 typedef G1FreeIdSet::TestSupport TestSupport;
  56 
  57 TEST_VM(G1FreeIdSetTest, initial_state) {
  58   const uint start = 5;
  59   const uint size = 4;
  60   G1FreeIdSet set(start, size);
  61 
  62   ASSERT_EQ(start, TestSupport::start(set));
  63   ASSERT_EQ(size, TestSupport::size(set));
  64   ASSERT_EQ(7u, TestSupport::mask(set));
  65   ASSERT_EQ(0u, TestSupport::head(set));
  66   for (uint i = 0; i < size; ++i) {
  67     ASSERT_EQ(i + 1, TestSupport::next(set, i));
  68   }
  69 }
  70 
  71 TEST_VM(G1FreeIdSetTest, non_blocking_ops) {
  72   const uint start = 5;
  73   const uint size = 3;
  74   G1FreeIdSet set(start, size);
  75 
  76   ASSERT_EQ(5u, set.claim_par_id());
  77   ASSERT_EQ(1u, TestSupport::head_index(set, TestSupport::head(set)));
  78   ASSERT_EQ(6u, set.claim_par_id());
  79   ASSERT_EQ(2u, TestSupport::head_index(set, TestSupport::head(set)));
  80   ASSERT_EQ(7u, set.claim_par_id());
  81   ASSERT_EQ(3u, TestSupport::head_index(set, TestSupport::head(set)));
  82 
  83   set.release_par_id(5u);
  84   set.release_par_id(6u);
  85   ASSERT_EQ(6u, set.claim_par_id());
  86   ASSERT_EQ(5u, set.claim_par_id());
  87 }
  88 
  89 class TestG1FreeIdSetThread : public JavaTestThread {
  90   G1FreeIdSet* _set;
  91   volatile size_t* _total_allocations;
  92   volatile bool* _continue_running;
  93   size_t _allocations;
  94   uint _thread_number;
  95 
  96 public:
  97   TestG1FreeIdSetThread(uint thread_number,
  98                         Semaphore* post,
  99                         G1FreeIdSet* set,
 100                         volatile size_t* total_allocations,
 101                         volatile bool* continue_running) :
 102     JavaTestThread(post),
 103     _set(set),
 104     _total_allocations(total_allocations),
 105     _continue_running(continue_running),
 106     _allocations(0),
 107     _thread_number(thread_number)
 108   {}
 109 
 110   virtual void main_run() {
 111     while (OrderAccess::load_acquire(_continue_running)) {
 112       uint id = _set->claim_par_id();
 113       _set->release_par_id(id);
 114       ++_allocations;
 115       ThreadBlockInVM tbiv(this); // Safepoint check.
 116     }
 117     tty->print_cr("%u allocations: " SIZE_FORMAT, _thread_number, _allocations);
 118     Atomic::add(_allocations, _total_allocations);
 119   }
 120 };
 121 
 122 TEST_VM(G1FreeIdSetTest, stress) {
 123   const uint start = 5;
 124   const uint size = 3;
 125   const uint nthreads = size + 1;
 126   const uint milliseconds_to_run = 1000;
 127 
 128   Semaphore post;
 129   volatile size_t total_allocations = 0;
 130   volatile bool continue_running = true;
 131 
 132   G1FreeIdSet set(start, size);
 133 
 134   TestG1FreeIdSetThread* threads[nthreads] = {};
 135   for (uint i = 0; i < nthreads; ++i) {
 136     threads[i] = new TestG1FreeIdSetThread(i,
 137                                            &post,
 138                                            &set,
 139                                            &total_allocations,
 140                                            &continue_running);
 141     threads[i]->doit();
 142   }
 143 
 144   JavaThread* this_thread = JavaThread::current();
 145   tty->print_cr("Stressing G1FreeIdSet for %u ms", milliseconds_to_run);
 146   {
 147     ThreadInVMfromNative invm(this_thread);
 148     os::sleep(this_thread, milliseconds_to_run, true);
 149   }
 150   OrderAccess::release_store(&continue_running, false);
 151   for (uint i = 0; i < nthreads; ++i) {
 152     ThreadInVMfromNative invm(this_thread);
 153     post.wait_with_safepoint_check(this_thread);
 154   }
 155   tty->print_cr("total allocations: " SIZE_FORMAT, total_allocations);
 156   tty->print_cr("final free list: ");
 157   uint ids[size] = {};
 158   for (uint i = 0; i < size; ++i) {
 159     uint id = set.claim_par_id();
 160     uint index = id - TestSupport::start(set);
 161     ASSERT_LT(index, TestSupport::size(set));
 162     tty->print_cr("  %u: %u", i, index);
 163   }
 164   ASSERT_EQ(size, TestSupport::head_index(set, TestSupport::head(set)));
 165 }