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
39struct 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
55typedef G1FreeIdSet::TestSupport TestSupport;
56
57TEST_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
71TEST_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
89class 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
96public:
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
122TEST_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}
166