1/*
2 * Copyright (c) 2018, 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#ifndef SHARE_GC_SHARED_OOPSTORAGE_INLINE_HPP
26#define SHARE_GC_SHARED_OOPSTORAGE_INLINE_HPP
27
28#include "gc/shared/oopStorage.hpp"
29#include "metaprogramming/conditional.hpp"
30#include "metaprogramming/isConst.hpp"
31#include "oops/oop.hpp"
32#include "runtime/safepoint.hpp"
33#include "utilities/align.hpp"
34#include "utilities/count_trailing_zeros.hpp"
35#include "utilities/debug.hpp"
36#include "utilities/globalDefinitions.hpp"
37
38// Array of all active blocks. Refcounted for lock-free reclaim of
39// old array when a new array is allocated for expansion.
40class OopStorage::ActiveArray {
41 friend class OopStorage::TestAccess;
42
43 size_t _size;
44 volatile size_t _block_count;
45 mutable volatile int _refcount;
46 // Block* _blocks[1]; // Pseudo flexible array member.
47
48 ActiveArray(size_t size);
49 ~ActiveArray();
50
51 // Noncopyable
52 ActiveArray(const ActiveArray&);
53 ActiveArray& operator=(const ActiveArray&);
54
55 static size_t blocks_offset();
56 Block* const* base_ptr() const;
57
58 Block* const* block_ptr(size_t index) const;
59 Block** block_ptr(size_t index);
60
61public:
62 static ActiveArray* create(size_t size, AllocFailType alloc_fail = AllocFailStrategy::EXIT_OOM);
63 static void destroy(ActiveArray* ba);
64
65 inline Block* at(size_t i) const;
66
67 size_t size() const;
68 size_t block_count() const;
69 size_t block_count_acquire() const;
70 void increment_refcount() const;
71 bool decrement_refcount() const; // Return true if zero, otherwise false
72
73 // Support for OopStorage::allocate.
74 // Add block to the end of the array. Updates block count at the
75 // end of the operation, with a release_store. Returns true if the
76 // block was added, false if there was no room available.
77 // precondition: owner's _allocation_mutex is locked, or at safepoint.
78 bool push(Block* block);
79
80 // Support OopStorage::delete_empty_blocks_xxx operations.
81 // Remove block from the array.
82 // precondition: block must be present at its active_index element.
83 void remove(Block* block);
84
85 void copy_from(const ActiveArray* from);
86};
87
88inline size_t OopStorage::ActiveArray::blocks_offset() {
89 return align_up(sizeof(ActiveArray), sizeof(Block*));
90}
91
92inline OopStorage::Block* const* OopStorage::ActiveArray::base_ptr() const {
93 const void* ptr = reinterpret_cast<const char*>(this) + blocks_offset();
94 return reinterpret_cast<Block* const*>(ptr);
95}
96
97inline OopStorage::Block* const* OopStorage::ActiveArray::block_ptr(size_t index) const {
98 return base_ptr() + index;
99}
100
101inline OopStorage::Block** OopStorage::ActiveArray::block_ptr(size_t index) {
102 return const_cast<Block**>(base_ptr() + index);
103}
104
105inline OopStorage::Block* OopStorage::ActiveArray::at(size_t index) const {
106 assert(index < _block_count, "precondition");
107 return *block_ptr(index);
108}
109
110// A Block has an embedded AllocationListEntry to provide the links between
111// Blocks in an AllocationList.
112class OopStorage::AllocationListEntry {
113 friend class OopStorage::AllocationList;
114
115 // Members are mutable, and we deal exclusively with pointers to
116 // const, to make const blocks easier to use; a block being const
117 // doesn't prevent modifying its list state.
118 mutable const Block* _prev;
119 mutable const Block* _next;
120
121 // Noncopyable.
122 AllocationListEntry(const AllocationListEntry&);
123 AllocationListEntry& operator=(const AllocationListEntry&);
124
125public:
126 AllocationListEntry();
127 ~AllocationListEntry();
128};
129
130// Fixed-sized array of oops, plus bookkeeping data.
131// All blocks are in the storage's _active_array, at the block's _active_index.
132// Non-full blocks are in the storage's _allocation_list, linked through the
133// block's _allocation_list_entry. Empty blocks are at the end of that list.
134class OopStorage::Block /* No base class, to avoid messing up alignment. */ {
135 // _data must be the first non-static data member, for alignment.
136 oop _data[BitsPerWord];
137 static const unsigned _data_pos = 0; // Position of _data.
138
139 volatile uintx _allocated_bitmask; // One bit per _data element.
140 const OopStorage* _owner;
141 void* _memory; // Unaligned storage containing block.
142 size_t _active_index;
143 AllocationListEntry _allocation_list_entry;
144 Block* volatile _deferred_updates_next;
145 volatile uintx _release_refcount;
146
147 Block(const OopStorage* owner, void* memory);
148 ~Block();
149
150 void check_index(unsigned index) const;
151 unsigned get_index(const oop* ptr) const;
152
153 template<typename F, typename BlockPtr>
154 static bool iterate_impl(F f, BlockPtr b);
155
156 // Noncopyable.
157 Block(const Block&);
158 Block& operator=(const Block&);
159
160public:
161 const AllocationListEntry& allocation_list_entry() const;
162
163 static size_t allocation_size();
164 static size_t allocation_alignment_shift();
165
166 oop* get_pointer(unsigned index);
167 const oop* get_pointer(unsigned index) const;
168
169 uintx bitmask_for_index(unsigned index) const;
170 uintx bitmask_for_entry(const oop* ptr) const;
171
172 // Allocation bitmask accessors are racy.
173 bool is_full() const;
174 bool is_empty() const;
175 uintx allocated_bitmask() const;
176
177 bool is_safe_to_delete() const;
178
179 Block* deferred_updates_next() const;
180 void set_deferred_updates_next(Block* new_next);
181
182 bool contains(const oop* ptr) const;
183
184 size_t active_index() const;
185 void set_active_index(size_t index);
186 static size_t active_index_safe(const Block* block); // Returns 0 if access fails.
187
188 // Returns NULL if ptr is not in a block or not allocated in that block.
189 static Block* block_for_ptr(const OopStorage* owner, const oop* ptr);
190
191 oop* allocate();
192 static Block* new_block(const OopStorage* owner);
193 static void delete_block(const Block& block);
194
195 void release_entries(uintx releasing, OopStorage* owner);
196
197 template<typename F> bool iterate(F f);
198 template<typename F> bool iterate(F f) const;
199}; // class Block
200
201inline OopStorage::Block* OopStorage::AllocationList::head() {
202 return const_cast<Block*>(_head);
203}
204
205inline OopStorage::Block* OopStorage::AllocationList::tail() {
206 return const_cast<Block*>(_tail);
207}
208
209inline const OopStorage::Block* OopStorage::AllocationList::chead() const {
210 return _head;
211}
212
213inline const OopStorage::Block* OopStorage::AllocationList::ctail() const {
214 return _tail;
215}
216
217inline OopStorage::Block* OopStorage::AllocationList::prev(Block& block) {
218 return const_cast<Block*>(block.allocation_list_entry()._prev);
219}
220
221inline OopStorage::Block* OopStorage::AllocationList::next(Block& block) {
222 return const_cast<Block*>(block.allocation_list_entry()._next);
223}
224
225inline const OopStorage::Block* OopStorage::AllocationList::prev(const Block& block) const {
226 return block.allocation_list_entry()._prev;
227}
228
229inline const OopStorage::Block* OopStorage::AllocationList::next(const Block& block) const {
230 return block.allocation_list_entry()._next;
231}
232
233template<typename Closure>
234class OopStorage::OopFn {
235public:
236 explicit OopFn(Closure* cl) : _cl(cl) {}
237
238 template<typename OopPtr> // [const] oop*
239 bool operator()(OopPtr ptr) const {
240 _cl->do_oop(ptr);
241 return true;
242 }
243
244private:
245 Closure* _cl;
246};
247
248template<typename Closure>
249inline OopStorage::OopFn<Closure> OopStorage::oop_fn(Closure* cl) {
250 return OopFn<Closure>(cl);
251}
252
253template<typename IsAlive, typename F>
254class OopStorage::IfAliveFn {
255public:
256 IfAliveFn(IsAlive* is_alive, F f) : _is_alive(is_alive), _f(f) {}
257
258 bool operator()(oop* ptr) const {
259 bool result = true;
260 oop v = *ptr;
261 if (v != NULL) {
262 if (_is_alive->do_object_b(v)) {
263 result = _f(ptr);
264 } else {
265 *ptr = NULL; // Clear dead value.
266 }
267 }
268 return result;
269 }
270
271private:
272 IsAlive* _is_alive;
273 F _f;
274};
275
276template<typename IsAlive, typename F>
277inline OopStorage::IfAliveFn<IsAlive, F> OopStorage::if_alive_fn(IsAlive* is_alive, F f) {
278 return IfAliveFn<IsAlive, F>(is_alive, f);
279}
280
281template<typename F>
282class OopStorage::SkipNullFn {
283public:
284 SkipNullFn(F f) : _f(f) {}
285
286 template<typename OopPtr> // [const] oop*
287 bool operator()(OopPtr ptr) const {
288 return (*ptr != NULL) ? _f(ptr) : true;
289 }
290
291private:
292 F _f;
293};
294
295template<typename F>
296inline OopStorage::SkipNullFn<F> OopStorage::skip_null_fn(F f) {
297 return SkipNullFn<F>(f);
298}
299
300// Inline Block accesses for use in iteration loops.
301
302inline const OopStorage::AllocationListEntry& OopStorage::Block::allocation_list_entry() const {
303 return _allocation_list_entry;
304}
305
306inline void OopStorage::Block::check_index(unsigned index) const {
307 assert(index < ARRAY_SIZE(_data), "Index out of bounds: %u", index);
308}
309
310inline oop* OopStorage::Block::get_pointer(unsigned index) {
311 check_index(index);
312 return &_data[index];
313}
314
315inline const oop* OopStorage::Block::get_pointer(unsigned index) const {
316 check_index(index);
317 return &_data[index];
318}
319
320inline uintx OopStorage::Block::allocated_bitmask() const {
321 return _allocated_bitmask;
322}
323
324inline uintx OopStorage::Block::bitmask_for_index(unsigned index) const {
325 check_index(index);
326 return uintx(1) << index;
327}
328
329// Provide const or non-const iteration, depending on whether BlockPtr
330// is const Block* or Block*, respectively.
331template<typename F, typename BlockPtr> // BlockPtr := [const] Block*
332inline bool OopStorage::Block::iterate_impl(F f, BlockPtr block) {
333 uintx bitmask = block->allocated_bitmask();
334 while (bitmask != 0) {
335 unsigned index = count_trailing_zeros(bitmask);
336 bitmask ^= block->bitmask_for_index(index);
337 if (!f(block->get_pointer(index))) {
338 return false;
339 }
340 }
341 return true;
342}
343
344template<typename F>
345inline bool OopStorage::Block::iterate(F f) {
346 return iterate_impl(f, this);
347}
348
349template<typename F>
350inline bool OopStorage::Block::iterate(F f) const {
351 return iterate_impl(f, this);
352}
353
354//////////////////////////////////////////////////////////////////////////////
355// Support for serial iteration, always at a safepoint.
356
357// Provide const or non-const iteration, depending on whether Storage is
358// const OopStorage* or OopStorage*, respectively.
359template<typename F, typename Storage> // Storage := [const] OopStorage
360inline bool OopStorage::iterate_impl(F f, Storage* storage) {
361 assert_at_safepoint();
362 // Propagate const/non-const iteration to the block layer, by using
363 // const or non-const blocks as corresponding to Storage.
364 typedef typename Conditional<IsConst<Storage>::value, const Block*, Block*>::type BlockPtr;
365 ActiveArray* blocks = storage->_active_array;
366 size_t limit = blocks->block_count();
367 for (size_t i = 0; i < limit; ++i) {
368 BlockPtr block = blocks->at(i);
369 if (!block->iterate(f)) {
370 return false;
371 }
372 }
373 return true;
374}
375
376template<typename F>
377inline bool OopStorage::iterate_safepoint(F f) {
378 return iterate_impl(f, this);
379}
380
381template<typename F>
382inline bool OopStorage::iterate_safepoint(F f) const {
383 return iterate_impl(f, this);
384}
385
386template<typename Closure>
387inline void OopStorage::oops_do(Closure* cl) {
388 iterate_safepoint(oop_fn(cl));
389}
390
391template<typename Closure>
392inline void OopStorage::oops_do(Closure* cl) const {
393 iterate_safepoint(oop_fn(cl));
394}
395
396template<typename Closure>
397inline void OopStorage::weak_oops_do(Closure* cl) {
398 iterate_safepoint(skip_null_fn(oop_fn(cl)));
399}
400
401template<typename IsAliveClosure, typename Closure>
402inline void OopStorage::weak_oops_do(IsAliveClosure* is_alive, Closure* cl) {
403 iterate_safepoint(if_alive_fn(is_alive, oop_fn(cl)));
404}
405
406#endif // SHARE_GC_SHARED_OOPSTORAGE_INLINE_HPP
407