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