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