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