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_INLINE_HPP
26 #define SHARE_GC_G1_HEAPREGIONSET_INLINE_HPP
27
28 #include "gc/g1/g1NUMA.hpp"
29 #include "gc/g1/heapRegionSet.hpp"
30
31 inline void HeapRegionSetBase::add(HeapRegion* hr) {
32 check_mt_safety();
33 assert_heap_region_set(hr->containing_set() == NULL, "should not already have a containing set");
34 assert_heap_region_set(hr->next() == NULL, "should not already be linked");
35 assert_heap_region_set(hr->prev() == NULL, "should not already be linked");
36
37 _length++;
38 hr->set_containing_set(this);
39 verify_region(hr);
40 }
41
42 inline void HeapRegionSetBase::remove(HeapRegion* hr) {
43 check_mt_safety();
44 verify_region(hr);
45 assert_heap_region_set(hr->next() == NULL, "should already be unlinked");
46 assert_heap_region_set(hr->prev() == NULL, "should already be unlinked");
47
48 hr->set_containing_set(NULL);
49 assert_heap_region_set(_length > 0, "pre-condition");
50 _length--;
51 }
52
53 inline void FreeRegionList::add_to_tail(HeapRegion* region_to_add) {
54 assert_free_region_list((length() == 0 && _head == NULL && _tail == NULL && _last == NULL) ||
55 (length() > 0 && _head != NULL && _tail != NULL && _tail->hrm_index() < region_to_add->hrm_index()),
56 "invariant");
57 // add() will verify the region and check mt safety.
58 add(region_to_add);
59
60 if (_head != NULL) {
61 // Link into list, next is already NULL, no need to set.
62 region_to_add->set_prev(_tail);
63 _tail->set_next(region_to_add);
64 _tail = region_to_add;
65 } else {
66 // Empty list, this region is now the list.
67 _head = region_to_add;
68 _tail = region_to_add;
69 }
70 increase_length(region_to_add->node_index());
71 }
72
73 inline void FreeRegionList::add_ordered(HeapRegion* hr) {
74 assert_free_region_list((length() == 0 && _head == NULL && _tail == NULL && _last == NULL) ||
75 (length() > 0 && _head != NULL && _tail != NULL),
76 "invariant");
77 // add() will verify the region and check mt safety.
78 add(hr);
79
80 // Now link the region
81 if (_head != NULL) {
82 HeapRegion* curr;
83
84 if (_last != NULL && _last->hrm_index() < hr->hrm_index()) {
85 curr = _last;
86 } else {
87 curr = _head;
88 }
89
90 // Find first entry with a Region Index larger than entry to insert.
91 while (curr != NULL && curr->hrm_index() < hr->hrm_index()) {
92 curr = curr->next();
93 }
94
95 hr->set_next(curr);
96
97 if (curr == NULL) {
98 // Adding at the end
99 hr->set_prev(_tail);
100 _tail->set_next(hr);
101 _tail = hr;
102 } else if (curr->prev() == NULL) {
103 // Adding at the beginning
104 hr->set_prev(NULL);
105 _head = hr;
106 curr->set_prev(hr);
107 } else {
108 hr->set_prev(curr->prev());
109 hr->prev()->set_next(hr);
110 curr->set_prev(hr);
111 }
112 } else {
113 // The list was empty
114 _tail = hr;
115 _head = hr;
116 }
117 _last = hr;
118
119 increase_length(hr->node_index());
120 }
121
122 inline HeapRegion* FreeRegionList::remove_from_head_impl() {
123 HeapRegion* result = _head;
124 _head = result->next();
125 if (_head == NULL) {
126 _tail = NULL;
127 } else {
128 _head->set_prev(NULL);
129 }
130 result->set_next(NULL);
131 return result;
132 }
133
134 inline HeapRegion* FreeRegionList::remove_from_tail_impl() {
135 HeapRegion* result = _tail;
136
137 _tail = result->prev();
138 if (_tail == NULL) {
139 _head = NULL;
140 } else {
141 _tail->set_next(NULL);
142 }
143 result->set_prev(NULL);
144 return result;
145 }
146
147 inline HeapRegion* FreeRegionList::remove_region(bool from_head) {
148 check_mt_safety();
149 verify_optional();
150
151 if (is_empty()) {
152 return NULL;
153 }
154 assert_free_region_list(length() > 0 && _head != NULL && _tail != NULL, "invariant");
155
156 HeapRegion* hr;
157
158 if (from_head) {
159 hr = remove_from_head_impl();
160 } else {
161 hr = remove_from_tail_impl();
162 }
163
164 if (_last == hr) {
165 _last = NULL;
166 }
167
168 // remove() will verify the region and check mt safety.
169 remove(hr);
170
171 decrease_length(hr->node_index());
172
173 return hr;
174 }
175
176 inline HeapRegion* FreeRegionList::remove_region_with_node_index(bool from_head,
177 uint requested_node_index) {
178 assert(UseNUMA, "Invariant");
179
180 const uint max_search_depth = G1NUMA::numa()->max_search_depth();
181 HeapRegion* cur;
182
183 // Find the region to use, searching from _head or _tail as requested.
184 size_t cur_depth = 0;
185 if (from_head) {
186 for (cur = _head;
187 cur != NULL && cur_depth < max_search_depth;
188 cur = cur->next(), ++cur_depth) {
189 if (requested_node_index == cur->node_index()) {
190 break;
191 }
192 }
193 } else {
194 for (cur = _tail;
195 cur != NULL && cur_depth < max_search_depth;
196 cur = cur->prev(), ++cur_depth) {
197 if (requested_node_index == cur->node_index()) {
198 break;
199 }
200 }
201 }
202
203 // Didn't find a region to use.
204 if (cur == NULL || cur_depth >= max_search_depth) {
205 return NULL;
206 }
207
208 // Splice the region out of the list.
209 HeapRegion* prev = cur->prev();
210 HeapRegion* next = cur->next();
211 if (prev == NULL) {
212 _head = next;
213 } else {
214 prev->set_next(next);
215 }
216 if (next == NULL) {
217 _tail = prev;
218 } else {
219 next->set_prev(prev);
220 }
221 cur->set_prev(NULL);
222 cur->set_next(NULL);
223
224 if (_last == cur) {
225 _last = NULL;
226 }
227
228 remove(cur);
229 decrease_length(cur->node_index());
230
231 return cur;
232 }
233
234 inline void FreeRegionList::NodeInfo::increase_length(uint node_index) {
235 if (node_index < _num_nodes) {
236 _length_of_node[node_index] += 1;
237 }
238 }
239
240 inline void FreeRegionList::NodeInfo::decrease_length(uint node_index) {
241 if (node_index < _num_nodes) {
242 assert(_length_of_node[node_index] > 0,
243 "Current length %u should be greater than zero for node %u",
244 _length_of_node[node_index], node_index);
245 _length_of_node[node_index] -= 1;
246 }
247 }
248
249 inline uint FreeRegionList::NodeInfo::length(uint node_index) const {
250 return _length_of_node[node_index];
251 }
252
253 inline void FreeRegionList::increase_length(uint node_index) {
254 if (_node_info != NULL) {
255 return _node_info->increase_length(node_index);
256 }
257 }
258
259 inline void FreeRegionList::decrease_length(uint node_index) {
260 if (_node_info != NULL) {
261 return _node_info->decrease_length(node_index);
262 }
263 }
264
265 inline uint FreeRegionList::length(uint node_index) const {
266 if (_node_info != NULL) {
267 return _node_info->length(node_index);
268 } else {
269 return 0;
270 }
271 }
272
273 #endif // SHARE_GC_G1_HEAPREGIONSET_INLINE_HPP