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 
  26 #include "precompiled.hpp"
  27 #include "code/nmethod.hpp"
  28 #include "gc_implementation/g1/g1CodeCacheRemSet.hpp"
  29 #include "memory/iterator.hpp"
  30 
  31 PRAGMA_FORMAT_MUTE_WARNINGS_FOR_GCC
  32 
  33 G1CodeRootChunk::G1CodeRootChunk() : _top(NULL), _next(NULL), _prev(NULL), _free(NULL) {
  34   _top = bottom();
  35 }
  36 
  37 void G1CodeRootChunk::reset() {
  38   _next = _prev = NULL;
  39   _free = NULL;
  40   _top = bottom();
  41 }
  42 
  43 void G1CodeRootChunk::nmethods_do(CodeBlobClosure* cl) {
  44   NmethodOrLink* cur = bottom();
  45   while (cur != _top) {
  46     if (is_nmethod(cur)) {
  47       cl->do_code_blob(cur->_nmethod);
  48     }
  49     cur++;
  50   }
  51 }
  52 
  53 bool G1CodeRootChunk::remove_lock_free(nmethod* method) {
  54   NmethodOrLink* cur = bottom();
  55 
  56   for (NmethodOrLink* cur = bottom(); cur != _top; cur++) {
  57     if (cur->_nmethod == method) {
  58       bool result = Atomic::cmpxchg_ptr(NULL, &cur->_nmethod, method) == method;
  59 
  60       if (!result) {
  61         // Someone else cleared out this entry.
  62         return false;
  63       }
  64 
  65       // The method was cleared. Time to link it into the free list.
  66       NmethodOrLink* prev_free;
  67       do {
  68         prev_free = (NmethodOrLink*)_free;
  69         cur->_link = prev_free;
  70       } while (Atomic::cmpxchg_ptr(cur, &_free, prev_free) != prev_free);
  71 
  72       return true;
  73     }
  74   }
  75 
  76   return false;
  77 }
  78 
  79 G1CodeRootChunkManager::G1CodeRootChunkManager() : _free_list(), _num_chunks_handed_out(0) {
  80   _free_list.initialize();
  81   _free_list.set_size(G1CodeRootChunk::word_size());
  82 }
  83 
  84 size_t G1CodeRootChunkManager::fl_mem_size() {
  85   return _free_list.count() * _free_list.size();
  86 }
  87 
  88 void G1CodeRootChunkManager::free_all_chunks(FreeList<G1CodeRootChunk>* list) {
  89   _num_chunks_handed_out -= list->count();
  90   _free_list.prepend(list);
  91 }
  92 
  93 void G1CodeRootChunkManager::free_chunk(G1CodeRootChunk* chunk) {
  94   _free_list.return_chunk_at_head(chunk);
  95   _num_chunks_handed_out--;
  96 }
  97 
  98 void G1CodeRootChunkManager::purge_chunks(size_t keep_ratio) {
  99   size_t keep = _num_chunks_handed_out * keep_ratio / 100;
 100   if (keep >= (size_t)_free_list.count()) {
 101     return;
 102   }
 103 
 104   FreeList<G1CodeRootChunk> temp;
 105   temp.initialize();
 106   temp.set_size(G1CodeRootChunk::word_size());
 107 
 108   _free_list.getFirstNChunksFromList((size_t)_free_list.count() - keep, &temp);
 109 
 110   G1CodeRootChunk* cur = temp.get_chunk_at_head();
 111   while (cur != NULL) {
 112     delete cur;
 113     cur = temp.get_chunk_at_head();
 114   }
 115 }
 116 
 117 size_t G1CodeRootChunkManager::static_mem_size() {
 118   return sizeof(G1CodeRootChunkManager);
 119 }
 120 
 121 
 122 G1CodeRootChunk* G1CodeRootChunkManager::new_chunk() {
 123   G1CodeRootChunk* result = _free_list.get_chunk_at_head();
 124   if (result == NULL) {
 125     result = new G1CodeRootChunk();
 126   }
 127   _num_chunks_handed_out++;
 128   result->reset();
 129   return result;
 130 }
 131 
 132 #ifndef PRODUCT
 133 
 134 size_t G1CodeRootChunkManager::num_chunks_handed_out() const {
 135   return _num_chunks_handed_out;
 136 }
 137 
 138 size_t G1CodeRootChunkManager::num_free_chunks() const {
 139   return (size_t)_free_list.count();
 140 }
 141 
 142 #endif
 143 
 144 G1CodeRootChunkManager G1CodeRootSet::_default_chunk_manager;
 145 
 146 void G1CodeRootSet::purge_chunks(size_t keep_ratio) {
 147   _default_chunk_manager.purge_chunks(keep_ratio);
 148 }
 149 
 150 size_t G1CodeRootSet::free_chunks_static_mem_size() {
 151   return _default_chunk_manager.static_mem_size();
 152 }
 153 
 154 size_t G1CodeRootSet::free_chunks_mem_size() {
 155   return _default_chunk_manager.fl_mem_size();
 156 }
 157 
 158 G1CodeRootSet::G1CodeRootSet(G1CodeRootChunkManager* manager) : _manager(manager), _list(), _length(0) {
 159   if (_manager == NULL) {
 160     _manager = &_default_chunk_manager;
 161   }
 162   _list.initialize();
 163   _list.set_size(G1CodeRootChunk::word_size());
 164 }
 165 
 166 G1CodeRootSet::~G1CodeRootSet() {
 167   clear();
 168 }
 169 
 170 void G1CodeRootSet::add(nmethod* method) {
 171   if (!contains(method)) {
 172     // Find the first chunk that isn't full.
 173     G1CodeRootChunk* cur = _list.head();
 174     while (cur != NULL) {
 175       if (!cur->is_full()) {
 176         break;
 177       }
 178       cur = cur->next();
 179     }
 180 
 181     // All chunks are full, get a new chunk.
 182     if (cur == NULL) {
 183       cur = new_chunk();
 184       _list.return_chunk_at_head(cur);
 185     }
 186 
 187     // Add the nmethod.
 188     bool result = cur->add(method);
 189 
 190     guarantee(result, err_msg("Not able to add nmethod "PTR_FORMAT" to newly allocated chunk.", method));
 191 
 192     _length++;
 193   }
 194 }
 195 
 196 void G1CodeRootSet::remove_lock_free(nmethod* method) {
 197   G1CodeRootChunk* found = find(method);
 198   if (found != NULL) {
 199     bool result = found->remove_lock_free(method);
 200     if (result) {
 201       Atomic::dec_ptr((volatile intptr_t*)&_length);
 202     }
 203   }
 204   assert(!contains(method), err_msg(PTR_FORMAT" still contains nmethod "PTR_FORMAT, this, method));
 205 }
 206 
 207 nmethod* G1CodeRootSet::pop() {
 208   while (true) {
 209     G1CodeRootChunk* cur = _list.head();
 210     if (cur == NULL) {
 211       assert(_length == 0, "when there are no chunks, there should be no elements");
 212       return NULL;
 213     }
 214     nmethod* result = cur->pop();
 215     if (result != NULL) {
 216       _length--;
 217       return result;
 218     } else {
 219       free(_list.get_chunk_at_head());
 220     }
 221   }
 222 }
 223 
 224 G1CodeRootChunk* G1CodeRootSet::find(nmethod* method) {
 225   G1CodeRootChunk* cur = _list.head();
 226   while (cur != NULL) {
 227     if (cur->contains(method)) {
 228       return cur;
 229     }
 230     cur = (G1CodeRootChunk*)cur->next();
 231   }
 232   return NULL;
 233 }
 234 
 235 void G1CodeRootSet::free(G1CodeRootChunk* chunk) {
 236   free_chunk(chunk);
 237 }
 238 
 239 bool G1CodeRootSet::contains(nmethod* method) {
 240   return find(method) != NULL;
 241 }
 242 
 243 void G1CodeRootSet::clear() {
 244   free_all_chunks(&_list);
 245   _length = 0;
 246 }
 247 
 248 void G1CodeRootSet::nmethods_do(CodeBlobClosure* blk) const {
 249   G1CodeRootChunk* cur = _list.head();
 250   while (cur != NULL) {
 251     cur->nmethods_do(blk);
 252     cur = (G1CodeRootChunk*)cur->next();
 253   }
 254 }
 255 
 256 size_t G1CodeRootSet::static_mem_size() {
 257   return sizeof(G1CodeRootSet);
 258 }
 259 
 260 size_t G1CodeRootSet::mem_size() {
 261   return G1CodeRootSet::static_mem_size() + _list.count() * _list.size();
 262 }
 263 
 264 #ifndef PRODUCT
 265 
 266 void G1CodeRootSet::test() {
 267   G1CodeRootChunkManager mgr;
 268 
 269   assert(mgr.num_chunks_handed_out() == 0, "Must not have handed out chunks yet");
 270 
 271   assert(G1CodeRootChunkManager::static_mem_size() > sizeof(void*),
 272          err_msg("The chunk manager's static memory usage seems too small, is only "SIZE_FORMAT" bytes.", G1CodeRootChunkManager::static_mem_size()));
 273 
 274   // The number of chunks that we allocate for purge testing.
 275   size_t const num_chunks = 10;
 276 
 277   {
 278     G1CodeRootSet set1(&mgr);
 279     assert(set1.is_empty(), "Code root set must be initially empty but is not.");
 280 
 281     assert(G1CodeRootSet::static_mem_size() > sizeof(void*),
 282            err_msg("The code root set's static memory usage seems too small, is only "SIZE_FORMAT" bytes", G1CodeRootSet::static_mem_size()));
 283 
 284     set1.add((nmethod*)1);
 285     assert(mgr.num_chunks_handed_out() == 1,
 286            err_msg("Must have allocated and handed out one chunk, but handed out "
 287                    SIZE_FORMAT" chunks", mgr.num_chunks_handed_out()));
 288     assert(set1.length() == 1, err_msg("Added exactly one element, but set contains "
 289                                        SIZE_FORMAT" elements", set1.length()));
 290 
 291     // G1CodeRootChunk::word_size() is larger than G1CodeRootChunk::num_entries which
 292     // we cannot access.
 293     for (uint i = 0; i < G1CodeRootChunk::word_size() + 1; i++) {
 294       set1.add((nmethod*)1);
 295     }
 296     assert(mgr.num_chunks_handed_out() == 1,
 297            err_msg("Duplicate detection must have prevented allocation of further "
 298                    "chunks but allocated "SIZE_FORMAT, mgr.num_chunks_handed_out()));
 299     assert(set1.length() == 1,
 300            err_msg("Duplicate detection should not have increased the set size but "
 301                    "is "SIZE_FORMAT, set1.length()));
 302 
 303     size_t num_total_after_add = G1CodeRootChunk::word_size() + 1;
 304     for (size_t i = 0; i < num_total_after_add - 1; i++) {
 305       set1.add((nmethod*)(uintptr_t)(2 + i));
 306     }
 307     assert(mgr.num_chunks_handed_out() > 1,
 308            "After adding more code roots, more than one additional chunk should have been handed out");
 309     assert(set1.length() == num_total_after_add,
 310            err_msg("After adding in total "SIZE_FORMAT" distinct code roots, they "
 311                    "need to be in the set, but there are only "SIZE_FORMAT,
 312                    num_total_after_add, set1.length()));
 313 
 314     size_t num_popped = 0;
 315     while (set1.pop() != NULL) {
 316       num_popped++;
 317     }
 318     assert(num_popped == num_total_after_add,
 319            err_msg("Managed to pop "SIZE_FORMAT" code roots, but only "SIZE_FORMAT" "
 320                    "were added", num_popped, num_total_after_add));
 321     assert(mgr.num_chunks_handed_out() == 0,
 322            err_msg("After popping all elements, all chunks must have been returned "
 323                    "but there are still "SIZE_FORMAT" additional", mgr.num_chunks_handed_out()));
 324 
 325     mgr.purge_chunks(0);
 326     assert(mgr.num_free_chunks() == 0,
 327            err_msg("After purging everything, the free list must be empty but still "
 328                    "contains "SIZE_FORMAT" chunks", mgr.num_free_chunks()));
 329 
 330     // Add some more handed out chunks.
 331     size_t i = 0;
 332     while (mgr.num_chunks_handed_out() < num_chunks) {
 333       set1.add((nmethod*)i);
 334       i++;
 335     }
 336 
 337     {
 338       // Generate chunks on the free list.
 339       G1CodeRootSet set2(&mgr);
 340       size_t i = 0;
 341       while (mgr.num_chunks_handed_out() < (num_chunks * 2)) {
 342         set2.add((nmethod*)i);
 343         i++;
 344       }
 345       // Exit of the scope of the set2 object will call the destructor that generates
 346       // num_chunks elements on the free list.
 347     }
 348 
 349     assert(mgr.num_chunks_handed_out() == num_chunks,
 350            err_msg("Deletion of the second set must have resulted in giving back "
 351                    "those, but there are still "SIZE_FORMAT" additional handed out, expecting "
 352                    SIZE_FORMAT, mgr.num_chunks_handed_out(), num_chunks));
 353     assert(mgr.num_free_chunks() == num_chunks,
 354            err_msg("After freeing "SIZE_FORMAT" chunks, they must be on the free list "
 355                    "but there are only "SIZE_FORMAT, num_chunks, mgr.num_free_chunks()));
 356 
 357     size_t const test_percentage = 50;
 358     mgr.purge_chunks(test_percentage);
 359     assert(mgr.num_chunks_handed_out() == num_chunks,
 360            err_msg("Purging must not hand out chunks but there are "SIZE_FORMAT,
 361                    mgr.num_chunks_handed_out()));
 362     assert(mgr.num_free_chunks() == (size_t)(mgr.num_chunks_handed_out() * test_percentage / 100),
 363            err_msg("Must have purged "SIZE_FORMAT" percent of "SIZE_FORMAT" chunks"
 364                    "but there are "SIZE_FORMAT, test_percentage, num_chunks,
 365                    mgr.num_free_chunks()));
 366     // Purge the remainder of the chunks on the free list.
 367     mgr.purge_chunks(0);
 368     assert(mgr.num_free_chunks() == 0, "Free List must be empty");
 369     assert(mgr.num_chunks_handed_out() == num_chunks,
 370            err_msg("Expected to be "SIZE_FORMAT" chunks handed out from the first set "
 371                    "but there are "SIZE_FORMAT, num_chunks, mgr.num_chunks_handed_out()));
 372 
 373     // Exit of the scope of the set1 object will call the destructor that generates
 374     // num_chunks additional elements on the free list.
 375    }
 376 
 377   assert(mgr.num_chunks_handed_out() == 0,
 378          err_msg("Deletion of the only set must have resulted in no chunks handed "
 379                  "out, but there is still "SIZE_FORMAT" handed out", mgr.num_chunks_handed_out()));
 380   assert(mgr.num_free_chunks() == num_chunks,
 381          err_msg("After freeing "SIZE_FORMAT" chunks, they must be on the free list "
 382                  "but there are only "SIZE_FORMAT, num_chunks, mgr.num_free_chunks()));
 383 
 384   // Restore initial state.
 385   mgr.purge_chunks(0);
 386   assert(mgr.num_free_chunks() == 0, "Free List must be empty");
 387   assert(mgr.num_chunks_handed_out() == 0, "No additional elements must have been handed out yet");
 388 }
 389 
 390 void TestCodeCacheRemSet_test() {
 391   G1CodeRootSet::test();
 392 }
 393 #endif