1 /*
2 * Copyright (c) 2014, 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 #include "precompiled.hpp"
26 #include "code/codeCache.hpp"
27 #include "code/nmethod.hpp"
28 #include "gc_implementation/g1/g1CodeCacheRemSet.hpp"
29 #include "gc_implementation/g1/heapRegion.hpp"
30 #include "memory/heap.hpp"
31 #include "memory/iterator.hpp"
32 #include "oops/oop.inline.hpp"
33 #include "utilities/hashtable.inline.hpp"
34 #include "utilities/stack.inline.hpp"
35
36 PRAGMA_FORMAT_MUTE_WARNINGS_FOR_GCC
37
38 class CodeRootSetTable : public Hashtable<nmethod*, mtGC> {
39 friend class G1CodeRootSetTest;
40 typedef HashtableEntry<nmethod*, mtGC> Entry;
41
42 static CodeRootSetTable* volatile _purge_list;
43
44 CodeRootSetTable* _purge_next;
45
46 unsigned int compute_hash(nmethod* nm) {
47 uintptr_t hash = (uintptr_t)nm;
48 return hash ^ (hash >> 7); // code heap blocks are 128byte aligned
49 }
50
51 Entry* new_entry(nmethod* nm);
52
53 public:
54 CodeRootSetTable(int size) : Hashtable<nmethod*, mtGC>(size, sizeof(Entry)), _purge_next(NULL) {}
55 ~CodeRootSetTable();
56
57 bool add(nmethod* nm);
58 bool contains(nmethod* nm);
59
60 bool remove(nmethod* nm);
61 int entry_size() const { return BasicHashtable<mtGC>::entry_size(); }
62
63 void copy_to(CodeRootSetTable* new_table);
64 void nmethods_do(CodeBlobClosure* blk);
65
66 template<typename CB>
67 void remove_if(CB& should_remove);
68
69 static void purge_list_append(CodeRootSetTable* tbl);
70 static void purge();
71
72 static size_t static_mem_size() {
73 return sizeof(_purge_list);
74 }
75 };
76
77 CodeRootSetTable* volatile CodeRootSetTable::_purge_list = NULL;
78
79 CodeRootSetTable::Entry* CodeRootSetTable::new_entry(nmethod* nm) {
80 unsigned int hash = compute_hash(nm);
81 Entry* entry = (Entry*) new_entry_free_list();
82 if (entry == NULL) {
83 entry = (Entry*) NEW_C_HEAP_ARRAY2(char, entry_size(), mtGC, CURRENT_PC);
84 }
85 entry->set_next(NULL);
86 entry->set_hash(hash);
87 entry->set_literal(nm);
88 return entry;
89 }
90
91 CodeRootSetTable::~CodeRootSetTable() {
92 for (int index = 0; index < table_size(); ++index) {
93 for (Entry* e = bucket(index); e != NULL; ) {
94 Entry* to_remove = e;
95 // read next before freeing.
96 e = e->next();
97 unlink_entry(to_remove);
98 FREE_C_HEAP_ARRAY(char, to_remove, mtGC);
99 }
100 }
101 assert(number_of_entries() == 0, "should have removed all entries");
102 free_buckets();
103 for (BasicHashtableEntry<mtGC>* e = new_entry_free_list(); e != NULL; e = new_entry_free_list()) {
104 FREE_C_HEAP_ARRAY(char, e, mtGC);
105 }
106 }
107
108 bool CodeRootSetTable::add(nmethod* nm) {
109 if (!contains(nm)) {
110 Entry* e = new_entry(nm);
111 int index = hash_to_index(e->hash());
112 add_entry(index, e);
113 return true;
114 }
115 return false;
116 }
117
118 bool CodeRootSetTable::contains(nmethod* nm) {
119 int index = hash_to_index(compute_hash(nm));
120 for (Entry* e = bucket(index); e != NULL; e = e->next()) {
121 if (e->literal() == nm) {
122 return true;
123 }
124 }
125 return false;
126 }
127
128 bool CodeRootSetTable::remove(nmethod* nm) {
129 int index = hash_to_index(compute_hash(nm));
130 Entry* previous = NULL;
131 for (Entry* e = bucket(index); e != NULL; previous = e, e = e->next()) {
132 if (e->literal() == nm) {
133 if (previous != NULL) {
134 previous->set_next(e->next());
135 } else {
136 set_entry(index, e->next());
137 }
138 free_entry(e);
139 return true;
140 }
141 }
142 return false;
143 }
144
145 void CodeRootSetTable::copy_to(CodeRootSetTable* new_table) {
146 for (int index = 0; index < table_size(); ++index) {
147 for (Entry* e = bucket(index); e != NULL; e = e->next()) {
148 new_table->add(e->literal());
149 }
150 }
151 new_table->copy_freelist(this);
152 }
153
154 void CodeRootSetTable::nmethods_do(CodeBlobClosure* blk) {
155 for (int index = 0; index < table_size(); ++index) {
156 for (Entry* e = bucket(index); e != NULL; e = e->next()) {
157 blk->do_code_blob(e->literal());
158 }
159 }
160 }
161
162 template<typename CB>
163 void CodeRootSetTable::remove_if(CB& should_remove) {
164 for (int index = 0; index < table_size(); ++index) {
165 Entry* previous = NULL;
166 Entry* e = bucket(index);
167 while (e != NULL) {
168 Entry* next = e->next();
169 if (should_remove(e->literal())) {
170 if (previous != NULL) {
171 previous->set_next(next);
172 } else {
173 set_entry(index, next);
174 }
175 free_entry(e);
176 } else {
177 previous = e;
178 }
179 e = next;
180 }
181 }
182 }
183
184 G1CodeRootSet::~G1CodeRootSet() {
185 delete _table;
186 }
187
188 CodeRootSetTable* G1CodeRootSet::load_acquire_table() {
189 return (CodeRootSetTable*) OrderAccess::load_ptr_acquire(&_table);
190 }
191
192 void G1CodeRootSet::allocate_small_table() {
193 _table = new CodeRootSetTable(SmallSize);
194 }
195
196 void CodeRootSetTable::purge_list_append(CodeRootSetTable* table) {
197 for (;;) {
198 table->_purge_next = _purge_list;
199 CodeRootSetTable* old = (CodeRootSetTable*) Atomic::cmpxchg_ptr(table, &_purge_list, table->_purge_next);
200 if (old == table->_purge_next) {
201 break;
202 }
203 }
204 }
205
206 void CodeRootSetTable::purge() {
207 CodeRootSetTable* table = _purge_list;
208 _purge_list = NULL;
209 while (table != NULL) {
210 CodeRootSetTable* to_purge = table;
211 table = table->_purge_next;
212 delete to_purge;
213 }
214 }
215
216 void G1CodeRootSet::move_to_large() {
217 CodeRootSetTable* temp = new CodeRootSetTable(LargeSize);
218
219 _table->copy_to(temp);
220
221 CodeRootSetTable::purge_list_append(_table);
222
223 OrderAccess::release_store_ptr(&_table, temp);
224 }
225
226
227 void G1CodeRootSet::purge() {
228 CodeRootSetTable::purge();
229 }
230
231 size_t G1CodeRootSet::static_mem_size() {
232 return CodeRootSetTable::static_mem_size();
233 }
234
235 void G1CodeRootSet::add(nmethod* method) {
236 bool added = false;
237 if (is_empty()) {
238 allocate_small_table();
239 }
240 if (_table != NULL) {
241 added = _table->add(method);
242 if (_length == Threshold) {
243 move_to_large();
244 }
245 }
246 if (added) {
247 ++_length;
248 }
249 }
250
251 bool G1CodeRootSet::remove(nmethod* method) {
252 bool removed = false;
253 if (_table != NULL) {
254 removed = _table->remove(method);
255 }
256 if (removed) {
257 _length--;
258 if (_length == 0) {
259 clear();
260 }
261 }
262 return removed;
263 }
264
265 bool G1CodeRootSet::contains(nmethod* method) {
266 CodeRootSetTable* table = load_acquire_table();
267 if (table != NULL) {
268 return table->contains(method);
269 }
270 return false;
271 }
272
273 void G1CodeRootSet::clear() {
274 delete _table;
275 _table = NULL;
276 _length = 0;
277 }
278
279 size_t G1CodeRootSet::mem_size() {
280 return sizeof(*this) +
281 (_table != NULL ? sizeof(CodeRootSetTable) + _table->entry_size() * _length : 0);
282 }
283
284 void G1CodeRootSet::nmethods_do(CodeBlobClosure* blk) const {
285 if (_table != NULL) {
286 _table->nmethods_do(blk);
287 }
288 }
289
290 class PurgeCallback : public StackObj {
291 class PointsIntoHRDetectionClosure : public OopClosure {
292 HeapRegion* _hr;
293 public:
294 bool _points_into;
295 PointsIntoHRDetectionClosure(HeapRegion* hr) : _hr(hr), _points_into(false) {}
296
297 void do_oop(narrowOop* o) {
298 do_oop_work(o);
299 }
300
301 void do_oop(oop* o) {
302 do_oop_work(o);
303 }
304
305 template <typename T>
306 void do_oop_work(T* p) {
307 if (_hr->is_in(oopDesc::load_decode_heap_oop(p))) {
308 _points_into = true;
309 }
310 }
311 };
312
313 PointsIntoHRDetectionClosure _detector;
314 CodeBlobToOopClosure _blobs;
315
316 public:
317 PurgeCallback(HeapRegion* hr) : _detector(hr), _blobs(&_detector, !CodeBlobToOopClosure::FixRelocations) {}
318
319 bool operator() (nmethod* nm) {
320 _detector._points_into = false;
321 _blobs.do_code_blob(nm);
322 return _detector._points_into;
323 }
324 };
325
326 void G1CodeRootSet::rebuild(HeapRegion* owner) {
327 PurgeCallback should_purge(owner);
328 if (_table != NULL) {
329 _table->remove_if(should_purge);
330 }
331 }
332
333 #ifndef PRODUCT
334
335 class G1CodeRootSetTest {
336 public:
337 static void test() {
338 {
339 G1CodeRootSet set1;
340 assert(set1.is_empty(), "Code root set must be initially empty but is not.");
341
342 assert(G1CodeRootSet::static_mem_size() == sizeof(void*),
343 err_msg("The code root set's static memory usage is incorrect, "SIZE_FORMAT" bytes", G1CodeRootSet::static_mem_size()));
344
345 set1.add((nmethod*)1);
346 assert(set1.length() == 1, err_msg("Added exactly one element, but set contains "
347 SIZE_FORMAT" elements", set1.length()));
348
349 const size_t num_to_add = (size_t)G1CodeRootSet::Threshold + 1;
350
351 for (size_t i = 1; i <= num_to_add; i++) {
352 set1.add((nmethod*)1);
353 }
354 assert(set1.length() == 1,
355 err_msg("Duplicate detection should not have increased the set size but "
356 "is "SIZE_FORMAT, set1.length()));
357
358 for (size_t i = 2; i <= num_to_add; i++) {
359 set1.add((nmethod*)(uintptr_t)(i));
360 }
361 assert(set1.length() == num_to_add,
362 err_msg("After adding in total "SIZE_FORMAT" distinct code roots, they "
363 "need to be in the set, but there are only "SIZE_FORMAT,
364 num_to_add, set1.length()));
365
366 assert(CodeRootSetTable::_purge_list != NULL, "should have grown to large hashtable");
367
368 size_t num_popped = 0;
369 for (size_t i = 1; i <= num_to_add; i++) {
370 bool removed = set1.remove((nmethod*)i);
371 if (removed) {
372 num_popped += 1;
373 } else {
374 break;
375 }
376 }
377 assert(num_popped == num_to_add,
378 err_msg("Managed to pop "SIZE_FORMAT" code roots, but only "SIZE_FORMAT" "
379 "were added", num_popped, num_to_add));
380 assert(CodeRootSetTable::_purge_list != NULL, "should have grown to large hashtable");
381
382 G1CodeRootSet::purge();
383
384 assert(CodeRootSetTable::_purge_list == NULL, "should have purged old small tables");
385
386 }
387
388 }
389 };
390
391 void TestCodeCacheRemSet_test() {
392 G1CodeRootSetTest::test();
393 }
394
395 #endif