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