1 /* 2 * Copyright (c) 2011, 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_G1_HEAPREGIONSET_HPP 26 #define SHARE_GC_G1_HEAPREGIONSET_HPP 27 28 #include "gc/g1/heapRegion.hpp" 29 #include "utilities/macros.hpp" 30 31 #define assert_heap_region_set(p, message) \ 32 do { \ 33 assert((p), "[%s] %s ln: %u", \ 34 name(), message, length()); \ 35 } while (0) 36 37 #define guarantee_heap_region_set(p, message) \ 38 do { \ 39 guarantee((p), "[%s] %s ln: %u", \ 40 name(), message, length()); \ 41 } while (0) 42 43 #define assert_free_region_list(p, message) \ 44 do { \ 45 assert((p), "[%s] %s ln: %u hd: " PTR_FORMAT " tl: " PTR_FORMAT, \ 46 name(), message, length(), p2i(_head), p2i(_tail)); \ 47 } while (0) 48 49 50 // Interface collecting various instance specific verification methods of 51 // HeapRegionSets. 52 class HeapRegionSetChecker : public CHeapObj<mtGC> { 53 public: 54 // Verify MT safety for this HeapRegionSet. 55 virtual void check_mt_safety() = 0; 56 // Returns true if the given HeapRegion is of the correct type for this HeapRegionSet. 57 virtual bool is_correct_type(HeapRegion* hr) = 0; 58 // Return a description of the type of regions this HeapRegionSet contains. 59 virtual const char* get_description() = 0; 60 }; 61 62 // Base class for all the classes that represent heap region sets. It 63 // contains the basic attributes that each set needs to maintain 64 // (e.g., length, region num, used bytes sum) plus any shared 65 // functionality (e.g., verification). 66 67 class HeapRegionSetBase { 68 friend class VMStructs; 69 70 HeapRegionSetChecker* _checker; 71 72 protected: 73 // The number of regions in to the set. 74 uint _length; 75 76 const char* _name; 77 78 bool _verify_in_progress; 79 80 // verify_region() is used to ensure that the contents of a region 81 // added to / removed from a set are consistent. 82 void verify_region(HeapRegion* hr) PRODUCT_RETURN; 83 84 void check_mt_safety() { 85 if (_checker != NULL) { 86 _checker->check_mt_safety(); 87 } 88 } 89 90 HeapRegionSetBase(const char* name, HeapRegionSetChecker* verifier); 91 92 public: 93 const char* name() { return _name; } 94 95 uint length() const { return _length; } 96 97 bool is_empty() { return _length == 0; } 98 99 // It updates the fields of the set to reflect hr being added to 100 // the set and tags the region appropriately. 101 inline void add(HeapRegion* hr); 102 103 // It updates the fields of the set to reflect hr being removed 104 // from the set and tags the region appropriately. 105 inline void remove(HeapRegion* hr); 106 107 virtual void verify(); 108 void verify_start(); 109 void verify_next_region(HeapRegion* hr); 110 void verify_end(); 111 112 void verify_optional() { DEBUG_ONLY(verify();) } 113 114 virtual void print_on(outputStream* out, bool print_contents = false); 115 }; 116 117 // This class represents heap region sets whose members are not 118 // explicitly tracked. It's helpful to group regions using such sets 119 // so that we can reason about all the region groups in the heap using 120 // the same interface (namely, the HeapRegionSetBase API). 121 122 class HeapRegionSet : public HeapRegionSetBase { 123 public: 124 HeapRegionSet(const char* name, HeapRegionSetChecker* checker): 125 HeapRegionSetBase(name, checker) { 126 } 127 128 void bulk_remove(const uint removed) { 129 _length -= removed; 130 } 131 }; 132 133 // A set that links all the regions added to it in a doubly-linked 134 // sorted list. We should try to avoid doing operations that iterate over 135 // such lists in performance critical paths. Typically we should 136 // add / remove one region at a time or concatenate two lists. 137 138 class FreeRegionListIterator; 139 class G1NUMA; 140 141 class FreeRegionList : public HeapRegionSetBase { 142 friend class FreeRegionListIterator; 143 144 private: 145 146 // This class is only initialized if there are multiple active nodes. 147 class NodeInfo : public CHeapObj<mtGC> { 148 G1NUMA* _numa; 149 uint* _length_of_node; 150 uint _num_nodes; 151 152 public: 153 NodeInfo(); 154 ~NodeInfo(); 155 156 inline void increase_length(uint node_index); 157 inline void decrease_length(uint node_index); 158 159 inline uint length(uint index) const; 160 161 void clear(); 162 163 void add(NodeInfo* info); 164 }; 165 166 HeapRegion* _head; 167 HeapRegion* _tail; 168 169 // _last is used to keep track of where we added an element the last 170 // time. It helps to improve performance when adding several ordered items in a row. 171 HeapRegion* _last; 172 173 NodeInfo* _node_info; 174 175 static uint _unrealistically_long_length; 176 177 inline HeapRegion* remove_from_head_impl(); 178 inline HeapRegion* remove_from_tail_impl(); 179 180 inline void increase_length(uint node_index); 181 inline void decrease_length(uint node_index); 182 183 // Common checks for adding a list. 184 void add_list_common_start(FreeRegionList* from_list); 185 void add_list_common_end(FreeRegionList* from_list); 186 187 protected: 188 // See the comment for HeapRegionSetBase::clear() 189 virtual void clear(); 190 191 public: 192 FreeRegionList(const char* name, HeapRegionSetChecker* checker = NULL); 193 ~FreeRegionList(); 194 195 void verify_list(); 196 197 #ifdef ASSERT 198 bool contains(HeapRegion* hr) const { 199 return hr->containing_set() == this; 200 } 201 #endif 202 203 static void set_unrealistically_long_length(uint len); 204 205 // Add hr to the list. The region should not be a member of another set. 206 // Assumes that the list is ordered and will preserve that order. The order 207 // is determined by hrm_index. 208 inline void add_ordered(HeapRegion* hr); 209 // Same restrictions as above, but adds the region last in the list. 210 inline void add_to_tail(HeapRegion* region_to_add); 211 212 // Removes from head or tail based on the given argument. 213 HeapRegion* remove_region(bool from_head); 214 215 HeapRegion* remove_region_with_node_index(bool from_head, 216 uint requested_node_index); 217 218 // Merge two ordered lists. The result is also ordered. The order is 219 // determined by hrm_index. 220 void add_ordered(FreeRegionList* from_list); 221 void append_ordered(FreeRegionList* from_list); 222 223 // It empties the list by removing all regions from it. 224 void remove_all(); 225 226 // Abandon current free list. Requires that all regions in the current list 227 // are taken care of separately, to allow a rebuild. 228 void abandon(); 229 230 // Remove all (contiguous) regions from first to first + num_regions -1 from 231 // this list. 232 // Num_regions must be > 1. 233 void remove_starting_at(HeapRegion* first, uint num_regions); 234 235 virtual void verify(); 236 237 uint num_of_regions_in_range(uint start, uint end) const; 238 239 using HeapRegionSetBase::length; 240 uint length(uint node_index) const; 241 }; 242 243 // Iterator class that provides a convenient way to iterate over the 244 // regions of a FreeRegionList. 245 246 class FreeRegionListIterator : public StackObj { 247 private: 248 FreeRegionList* _list; 249 HeapRegion* _curr; 250 251 public: 252 bool more_available() { 253 return _curr != NULL; 254 } 255 256 HeapRegion* get_next() { 257 assert(more_available(), 258 "get_next() should be called when more regions are available"); 259 260 // If we are going to introduce a count in the iterator we should 261 // do the "cycle" check. 262 263 HeapRegion* hr = _curr; 264 _list->verify_region(hr); 265 _curr = hr->next(); 266 return hr; 267 } 268 269 FreeRegionListIterator(FreeRegionList* list) 270 : _list(list), 271 _curr(list->_head) { 272 } 273 }; 274 275 #endif // SHARE_GC_G1_HEAPREGIONSET_HPP