1 /*
  2  * Copyright (c) 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_G1_G1CARDSETMEMORY_HPP
 26 #define SHARE_GC_G1_G1CARDSETMEMORY_HPP
 27 
 28 #include "gc/g1/g1CardSet.hpp"
 29 #include "gc/g1/g1CardSetContainers.hpp"
 30 #include "gc/g1/g1CardSetContainers.inline.hpp"
 31 #include "gc/g1/g1SegmentedArray.hpp"
 32 #include "memory/allocation.hpp"
 33 #include "utilities/growableArray.hpp"
 34 #include "utilities/lockFreeStack.hpp"
 35 
 36 class G1CardSetConfiguration;
 37 class outputStream;
 38 
 39 // Collects G1CardSetAllocator options/heuristics. Called by G1CardSetAllocator
 40 // to determine the next size of the allocated G1CardSetBuffer.
 41 class G1CardSetAllocOptions : public G1SegmentedArrayAllocOptions {
 42   static const uint MinimumBufferSize = 8;
 43   static const uint MaximumBufferSize =  UINT_MAX / 2;
 44 
 45   uint exponential_expand(uint prev_num_elems) const {
 46     return clamp(prev_num_elems * 2, _initial_num_elems, _max_num_elems);
 47   }
 48 
 49 public:
 50   static const uint BufferAlignment = 8;
 51 
 52   G1CardSetAllocOptions(uint elem_size, uint initial_num_elems = MinimumBufferSize, uint max_num_elems = MaximumBufferSize) :
 53     G1SegmentedArrayAllocOptions(align_up(elem_size, BufferAlignment), initial_num_elems, max_num_elems, BufferAlignment) {
 54   }
 55 
 56   virtual uint next_num_elems(uint prev_num_elems) const override {
 57     return exponential_expand(prev_num_elems);
 58   }
 59 };
 60 
 61 typedef G1SegmentedArrayBuffer<mtGCCardSet> G1CardSetBuffer;
 62 
 63 typedef G1SegmentedArrayBufferList<mtGCCardSet> G1CardSetBufferList;
 64 
 65 // Arena-like allocator for (card set) heap memory objects (Elem elements).
 66 //
 67 // Allocation and deallocation in the first phase on G1CardSetContainer basis
 68 // may occur by multiple threads at once.
 69 //
 70 // Allocation occurs from an internal free list of G1CardSetContainers first,
 71 // only then trying to bump-allocate from the current G1CardSetBuffer. If there is
 72 // none, this class allocates a new G1CardSetBuffer (allocated from the C heap,
 73 // asking the G1CardSetAllocOptions instance about sizes etc) and uses that one.
 74 //
 75 // The NodeStack free list is a linked list of G1CardSetContainers
 76 // within all G1CardSetBuffer instances allocated so far. It uses a separate
 77 // pending list and global synchronization to avoid the ABA problem when the
 78 // user frees a memory object.
 79 //
 80 // The class also manages a few counters for statistics using atomic operations.
 81 // Their values are only consistent within each other with extra global
 82 // synchronization.
 83 //
 84 // Since it is expected that every CardSet (and in extension each region) has its
 85 // own set of allocators, there is intentionally no padding between them to save
 86 // memory.
 87 template <class Elem>
 88 class G1CardSetAllocator {
 89   // G1CardSetBuffer management.
 90 
 91   typedef G1SegmentedArray<Elem, mtGCCardSet> SegmentedArray;
 92   // G1CardSetContainer node management within the G1CardSetBuffers allocated
 93   // by this allocator.
 94   static G1CardSetContainer* volatile* next_ptr(G1CardSetContainer& node);
 95   typedef LockFreeStack<G1CardSetContainer, &G1CardSetAllocator::next_ptr> NodeStack;
 96 
 97   SegmentedArray _segmented_array;
 98   volatile bool _transfer_lock;
 99   NodeStack _free_nodes_list;
100   NodeStack _pending_nodes_list;
101 
102   volatile uint _num_pending_nodes;   // Number of nodes in the pending list.
103   volatile uint _num_free_nodes;      // Number of nodes in the free list.
104 
105   // Try to transfer nodes from _pending_nodes_list to _free_nodes_list, with a
106   // synchronization delay for any in-progress pops from the _free_nodes_list
107   // to solve ABA here.
108   bool try_transfer_pending();
109 
110   uint num_free_elems() const;
111 
112 public:
113   G1CardSetAllocator(const char* name,
114                      const G1CardSetAllocOptions* buffer_options,
115                      G1CardSetBufferList* free_buffer_list);
116   ~G1CardSetAllocator();
117 
118   Elem* allocate();
119   void free(Elem* elem);
120 
121   // Deallocate all buffers to the free buffer list and reset this allocator. Must
122   // be called in a globally synchronized area.
123   void drop_all();
124 
125   size_t mem_size() const {
126     return sizeof(*this) +
127       _segmented_array.num_buffers() * sizeof(G1CardSetBuffer) + _segmented_array.num_available_nodes() * _segmented_array.elem_size();
128   }
129 
130   size_t wasted_mem_size() const {
131     return (_segmented_array.num_available_nodes() - (_segmented_array.num_allocated_nodes() - _num_pending_nodes)) * _segmented_array.elem_size();
132   }
133 
134   inline uint num_buffers() { return _segmented_array.num_buffers(); }
135 
136   void print(outputStream* os);
137 };
138 
139 // Statistics for a fixed set of buffer lists. Contains the number of buffers and memory
140 // used for each. Note that statistics are typically not taken atomically so there
141 // can be inconsistencies. The user must be prepared for them.
142 class G1CardSetMemoryStats {
143 public:
144 
145   size_t _num_mem_sizes[G1CardSetConfiguration::num_mem_object_types()];
146   size_t _num_buffers[G1CardSetConfiguration::num_mem_object_types()];
147 
148   // Returns all-zero statistics.
149   G1CardSetMemoryStats();
150 
151   void add(G1CardSetMemoryStats const other) {
152     STATIC_ASSERT(ARRAY_SIZE(_num_buffers) == ARRAY_SIZE(_num_mem_sizes));
153     for (uint i = 0; i < ARRAY_SIZE(_num_mem_sizes); i++) {
154       _num_mem_sizes[i] += other._num_mem_sizes[i];
155       _num_buffers[i] += other._num_buffers[i];
156     }
157   }
158 
159   void clear();
160 
161   uint num_pools() const { return G1CardSetConfiguration::num_mem_object_types(); }
162 };
163 
164 // A set of free lists holding memory buffers for use by G1CardSetAllocators.
165 class G1CardSetFreePool {
166   // The global free pool.
167   static G1CardSetFreePool _freelist_pool;
168 
169   const uint _num_free_lists;
170   G1CardSetBufferList* _free_lists;
171 
172 public:
173   static G1CardSetFreePool* free_list_pool() { return &_freelist_pool; }
174   static G1CardSetMemoryStats free_list_sizes() { return _freelist_pool.memory_sizes(); }
175 
176   class G1ReturnMemoryProcessor;
177   typedef GrowableArrayCHeap<G1ReturnMemoryProcessor*, mtGC> G1ReturnMemoryProcessorSet;
178 
179   static void update_unlink_processors(G1ReturnMemoryProcessorSet* unlink_processors);
180 
181   explicit G1CardSetFreePool(uint num_free_lists);
182   ~G1CardSetFreePool();
183 
184   G1CardSetBufferList* free_list(uint i) {
185     assert(i < _num_free_lists, "must be");
186     return &_free_lists[i];
187   }
188 
189   uint num_free_lists() const { return _num_free_lists; }
190 
191   G1CardSetMemoryStats memory_sizes() const;
192   size_t mem_size() const;
193 
194   void print_on(outputStream* out);
195 };
196 
197 // Data structure containing current in-progress state for returning memory to the
198 // operating system for a single G1CardSetBufferList.
199 class G1CardSetFreePool::G1ReturnMemoryProcessor : public CHeapObj<mtGC> {
200   G1CardSetBufferList* _source;
201   size_t _return_to_vm_size;
202 
203   G1CardSetBuffer* _first;
204   size_t _unlinked_bytes;
205   size_t _num_unlinked;
206 
207 public:
208   explicit G1ReturnMemoryProcessor(size_t return_to_vm) :
209     _source(nullptr), _return_to_vm_size(return_to_vm), _first(nullptr), _unlinked_bytes(0), _num_unlinked(0) {
210   }
211 
212   // Updates the instance members about the given card set buffer list for the purpose
213   // of giving back memory. Only necessary members are updated, e.g. if there is
214   // nothing to return to the VM, do not set the source list.
215   void visit_free_list(G1CardSetBufferList* source);
216 
217   bool finished_return_to_vm() const { return _return_to_vm_size == 0; }
218   bool finished_return_to_os() const { return _first == nullptr; }
219 
220   // Returns memory to the VM until the given deadline expires. Returns true if
221   // there is no more work. Guarantees forward progress, i.e. at least one buffer
222   // has been processed after returning.
223   // return_to_vm() re-adds buffers to the respective free list.
224   bool return_to_vm(jlong deadline);
225   // Returns memory to the VM until the given deadline expires. Returns true if
226   // there is no more work. Guarantees forward progress, i.e. at least one buffer
227   // has been processed after returning.
228   // return_to_os() gives back buffers to the OS.
229   bool return_to_os(jlong deadline);
230 };
231 
232 class G1CardSetMemoryManager : public CHeapObj<mtGCCardSet> {
233   G1CardSetConfiguration* _config;
234 
235   G1CardSetAllocator<G1CardSetContainer>* _allocators;
236 
237   uint num_mem_object_types() const;
238 public:
239   G1CardSetMemoryManager(G1CardSetConfiguration* config,
240                          G1CardSetFreePool* free_list_pool);
241 
242   virtual ~G1CardSetMemoryManager();
243 
244   // Allocate and free a memory object of given type.
245   inline uint8_t* allocate(uint type);
246   void free(uint type, void* value);
247 
248   // Allocate and free a hash table node.
249   inline uint8_t* allocate_node();
250   inline void free_node(void* value);
251 
252   void flush();
253 
254   void print(outputStream* os);
255 
256   size_t mem_size() const;
257   size_t wasted_mem_size() const;
258 
259   G1CardSetMemoryStats memory_stats() const;
260 };
261 
262 #endif // SHARE_GC_G1_G1CARDSETMEMORY_HPP