tschatzl@6402: /*
tschatzl@6402:  * Copyright (c) 2014, Oracle and/or its affiliates. All rights reserved.
tschatzl@6402:  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
tschatzl@6402:  *
tschatzl@6402:  * This code is free software; you can redistribute it and/or modify it
tschatzl@6402:  * under the terms of the GNU General Public License version 2 only, as
tschatzl@6402:  * published by the Free Software Foundation.
tschatzl@6402:  *
tschatzl@6402:  * This code is distributed in the hope that it will be useful, but WITHOUT
tschatzl@6402:  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
tschatzl@6402:  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
tschatzl@6402:  * version 2 for more details (a copy is included in the LICENSE file that
tschatzl@6402:  * accompanied this code).
tschatzl@6402:  *
tschatzl@6402:  * You should have received a copy of the GNU General Public License version
tschatzl@6402:  * 2 along with this work; if not, write to the Free Software Foundation,
tschatzl@6402:  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
tschatzl@6402:  *
tschatzl@6402:  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
tschatzl@6402:  * or visit www.oracle.com if you need additional information or have any
tschatzl@6402:  * questions.
tschatzl@6402:  *
tschatzl@6402:  */
tschatzl@6402: 
tschatzl@6402: 
tschatzl@6402: #include "precompiled.hpp"
tschatzl@6402: #include "code/nmethod.hpp"
tschatzl@6402: #include "gc_implementation/g1/g1CodeCacheRemSet.hpp"
tschatzl@6402: #include "memory/iterator.hpp"
tschatzl@6402: 
drchase@6680: PRAGMA_FORMAT_MUTE_WARNINGS_FOR_GCC
drchase@6680: 
stefank@6992: G1CodeRootChunk::G1CodeRootChunk() : _top(NULL), _next(NULL), _prev(NULL), _free(NULL) {
tschatzl@6402:   _top = bottom();
tschatzl@6402: }
tschatzl@6402: 
tschatzl@6402: void G1CodeRootChunk::reset() {
tschatzl@6402:   _next = _prev = NULL;
stefank@6992:   _free = NULL;
tschatzl@6402:   _top = bottom();
tschatzl@6402: }
tschatzl@6402: 
tschatzl@6402: void G1CodeRootChunk::nmethods_do(CodeBlobClosure* cl) {
stefank@6992:   NmethodOrLink* cur = bottom();
tschatzl@6402:   while (cur != _top) {
stefank@6992:     if (is_nmethod(cur)) {
stefank@6992:       cl->do_code_blob(cur->_nmethod);
stefank@6992:     }
tschatzl@6402:     cur++;
tschatzl@6402:   }
tschatzl@6402: }
tschatzl@6402: 
stefank@6992: bool G1CodeRootChunk::remove_lock_free(nmethod* method) {
stefank@6992:   NmethodOrLink* cur = bottom();
stefank@6992: 
stefank@6992:   for (NmethodOrLink* cur = bottom(); cur != _top; cur++) {
stefank@6992:     if (cur->_nmethod == method) {
stefank@6992:       bool result = Atomic::cmpxchg_ptr(NULL, &cur->_nmethod, method) == method;
stefank@6992: 
stefank@6992:       if (!result) {
stefank@6992:         // Someone else cleared out this entry.
stefank@6992:         return false;
stefank@6992:       }
stefank@6992: 
stefank@6992:       // The method was cleared. Time to link it into the free list.
stefank@6992:       NmethodOrLink* prev_free;
stefank@6992:       do {
stefank@6992:         prev_free = (NmethodOrLink*)_free;
stefank@6992:         cur->_link = prev_free;
stefank@6992:       } while (Atomic::cmpxchg_ptr(cur, &_free, prev_free) != prev_free);
stefank@6992: 
stefank@6992:       return true;
stefank@6992:     }
stefank@6992:   }
stefank@6992: 
stefank@6992:   return false;
stefank@6992: }
stefank@6992: 
tschatzl@6925: G1CodeRootChunkManager::G1CodeRootChunkManager() : _free_list(), _num_chunks_handed_out(0) {
tschatzl@6925:   _free_list.initialize();
tschatzl@6925:   _free_list.set_size(G1CodeRootChunk::word_size());
tschatzl@6402: }
tschatzl@6402: 
tschatzl@6925: size_t G1CodeRootChunkManager::fl_mem_size() {
tschatzl@6925:   return _free_list.count() * _free_list.size();
tschatzl@6402: }
tschatzl@6402: 
tschatzl@6925: void G1CodeRootChunkManager::free_all_chunks(FreeList<G1CodeRootChunk>* list) {
tschatzl@6925:   _num_chunks_handed_out -= list->count();
tschatzl@6402:   _free_list.prepend(list);
tschatzl@6402: }
tschatzl@6402: 
tschatzl@6925: void G1CodeRootChunkManager::free_chunk(G1CodeRootChunk* chunk) {
tschatzl@6925:   _free_list.return_chunk_at_head(chunk);
tschatzl@6925:   _num_chunks_handed_out--;
tschatzl@6925: }
tschatzl@6402: 
tschatzl@6925: void G1CodeRootChunkManager::purge_chunks(size_t keep_ratio) {
tschatzl@6925:   size_t keep = _num_chunks_handed_out * keep_ratio / 100;
tschatzl@6402:   if (keep >= (size_t)_free_list.count()) {
tschatzl@6402:     return;
tschatzl@6402:   }
tschatzl@6402: 
tschatzl@6402:   FreeList<G1CodeRootChunk> temp;
tschatzl@6402:   temp.initialize();
tschatzl@6402:   temp.set_size(G1CodeRootChunk::word_size());
tschatzl@6402: 
tschatzl@6402:   _free_list.getFirstNChunksFromList((size_t)_free_list.count() - keep, &temp);
tschatzl@6402: 
tschatzl@6402:   G1CodeRootChunk* cur = temp.get_chunk_at_head();
tschatzl@6402:   while (cur != NULL) {
tschatzl@6402:     delete cur;
tschatzl@6402:     cur = temp.get_chunk_at_head();
tschatzl@6402:   }
tschatzl@6402: }
tschatzl@6402: 
tschatzl@6925: size_t G1CodeRootChunkManager::static_mem_size() {
tschatzl@6932:   return sizeof(G1CodeRootChunkManager);
tschatzl@6402: }
tschatzl@6402: 
tschatzl@6925: 
tschatzl@6925: G1CodeRootChunk* G1CodeRootChunkManager::new_chunk() {
tschatzl@6925:   G1CodeRootChunk* result = _free_list.get_chunk_at_head();
tschatzl@6925:   if (result == NULL) {
tschatzl@6925:     result = new G1CodeRootChunk();
tschatzl@6925:   }
tschatzl@6925:   _num_chunks_handed_out++;
tschatzl@6925:   result->reset();
tschatzl@6925:   return result;
tschatzl@6402: }
tschatzl@6402: 
tschatzl@6925: #ifndef PRODUCT
tschatzl@6925: 
tschatzl@6925: size_t G1CodeRootChunkManager::num_chunks_handed_out() const {
tschatzl@6925:   return _num_chunks_handed_out;
tschatzl@6402: }
tschatzl@6402: 
tschatzl@6925: size_t G1CodeRootChunkManager::num_free_chunks() const {
tschatzl@6925:   return (size_t)_free_list.count();
tschatzl@6925: }
tschatzl@6925: 
tschatzl@6925: #endif
tschatzl@6925: 
tschatzl@6925: G1CodeRootChunkManager G1CodeRootSet::_default_chunk_manager;
tschatzl@6925: 
tschatzl@6925: void G1CodeRootSet::purge_chunks(size_t keep_ratio) {
tschatzl@6925:   _default_chunk_manager.purge_chunks(keep_ratio);
tschatzl@6925: }
tschatzl@6925: 
tschatzl@6932: size_t G1CodeRootSet::free_chunks_static_mem_size() {
tschatzl@6925:   return _default_chunk_manager.static_mem_size();
tschatzl@6925: }
tschatzl@6925: 
tschatzl@6925: size_t G1CodeRootSet::free_chunks_mem_size() {
tschatzl@6925:   return _default_chunk_manager.fl_mem_size();
tschatzl@6925: }
tschatzl@6925: 
tschatzl@6925: G1CodeRootSet::G1CodeRootSet(G1CodeRootChunkManager* manager) : _manager(manager), _list(), _length(0) {
tschatzl@6925:   if (_manager == NULL) {
tschatzl@6925:     _manager = &_default_chunk_manager;
tschatzl@6925:   }
tschatzl@6402:   _list.initialize();
tschatzl@6402:   _list.set_size(G1CodeRootChunk::word_size());
tschatzl@6402: }
tschatzl@6402: 
tschatzl@6402: G1CodeRootSet::~G1CodeRootSet() {
tschatzl@6402:   clear();
tschatzl@6402: }
tschatzl@6402: 
tschatzl@6402: void G1CodeRootSet::add(nmethod* method) {
tschatzl@6402:   if (!contains(method)) {
stefank@6992:     // Find the first chunk thatisn't full.
stefank@6992:     G1CodeRootChunk* cur = _list.head();
stefank@6992:     while (cur != NULL) {
stefank@6992:       if (!cur->is_full()) {
stefank@6992:         break;
stefank@6992:       }
stefank@6992:       cur = cur->next();
stefank@6992:     }
stefank@6992: 
stefank@6992:     // All chunks are full, get a new chunk.
stefank@6992:     if (cur == NULL) {
stefank@6992:       cur = new_chunk();
tschatzl@6402:       _list.return_chunk_at_head(cur);
tschatzl@6402:     }
stefank@6992: 
stefank@6992:     // Add the nmethod.
stefank@6992:     bool result = cur->add(method);
stefank@6992: 
tschatzl@6402:     guarantee(result, err_msg("Not able to add nmethod "PTR_FORMAT" to newly allocated chunk.", method));
stefank@6992: 
tschatzl@6402:     _length++;
tschatzl@6402:   }
tschatzl@6402: }
tschatzl@6402: 
stefank@6992: void G1CodeRootSet::remove_lock_free(nmethod* method) {
tschatzl@6402:   G1CodeRootChunk* found = find(method);
tschatzl@6402:   if (found != NULL) {
stefank@6992:     bool result = found->remove_lock_free(method);
stefank@6992:     if (result) {
stefank@6992:       Atomic::dec_ptr((volatile intptr_t*)&_length);
tschatzl@6402:     }
tschatzl@6402:   }
tschatzl@6402:   assert(!contains(method), err_msg(PTR_FORMAT" still contains nmethod "PTR_FORMAT, this, method));
tschatzl@6402: }
tschatzl@6402: 
tschatzl@6402: nmethod* G1CodeRootSet::pop() {
stefank@6992:   while (true) {
tschatzl@6402:     G1CodeRootChunk* cur = _list.head();
tschatzl@6402:     if (cur == NULL) {
tschatzl@6402:       assert(_length == 0, "when there are no chunks, there should be no elements");
tschatzl@6402:       return NULL;
tschatzl@6402:     }
tschatzl@6402:     nmethod* result = cur->pop();
tschatzl@6402:     if (result != NULL) {
tschatzl@6402:       _length--;
tschatzl@6402:       return result;
tschatzl@6402:     } else {
tschatzl@6402:       free(_list.get_chunk_at_head());
tschatzl@6402:     }
stefank@6992:   }
tschatzl@6402: }
tschatzl@6402: 
tschatzl@6402: G1CodeRootChunk* G1CodeRootSet::find(nmethod* method) {
tschatzl@6402:   G1CodeRootChunk* cur = _list.head();
tschatzl@6402:   while (cur != NULL) {
tschatzl@6402:     if (cur->contains(method)) {
tschatzl@6402:       return cur;
tschatzl@6402:     }
tschatzl@6402:     cur = (G1CodeRootChunk*)cur->next();
tschatzl@6402:   }
tschatzl@6402:   return NULL;
tschatzl@6402: }
tschatzl@6402: 
tschatzl@6402: void G1CodeRootSet::free(G1CodeRootChunk* chunk) {
tschatzl@6402:   free_chunk(chunk);
tschatzl@6402: }
tschatzl@6402: 
tschatzl@6402: bool G1CodeRootSet::contains(nmethod* method) {
tschatzl@6402:   return find(method) != NULL;
tschatzl@6402: }
tschatzl@6402: 
tschatzl@6402: void G1CodeRootSet::clear() {
tschatzl@6402:   free_all_chunks(&_list);
tschatzl@6402:   _length = 0;
tschatzl@6402: }
tschatzl@6402: 
tschatzl@6402: void G1CodeRootSet::nmethods_do(CodeBlobClosure* blk) const {
tschatzl@6402:   G1CodeRootChunk* cur = _list.head();
tschatzl@6402:   while (cur != NULL) {
tschatzl@6402:     cur->nmethods_do(blk);
tschatzl@6402:     cur = (G1CodeRootChunk*)cur->next();
tschatzl@6402:   }
tschatzl@6402: }
tschatzl@6402: 
tschatzl@6932: size_t G1CodeRootSet::static_mem_size() {
tschatzl@6932:   return sizeof(G1CodeRootSet);
tschatzl@6932: }
tschatzl@6932: 
tschatzl@6402: size_t G1CodeRootSet::mem_size() {
tschatzl@6932:   return G1CodeRootSet::static_mem_size() + _list.count() * _list.size();
tschatzl@6402: }
tschatzl@6402: 
tschatzl@6402: #ifndef PRODUCT
tschatzl@6402: 
tschatzl@6402: void G1CodeRootSet::test() {
tschatzl@6925:   G1CodeRootChunkManager mgr;
tschatzl@6402: 
tschatzl@6925:   assert(mgr.num_chunks_handed_out() == 0, "Must not have handed out chunks yet");
tschatzl@6402: 
tschatzl@6932:   assert(G1CodeRootChunkManager::static_mem_size() > sizeof(void*),
tschatzl@6932:          err_msg("The chunk manager's static memory usage seems too small, is only "SIZE_FORMAT" bytes.", G1CodeRootChunkManager::static_mem_size()));
tschatzl@6932: 
tschatzl@6402:   // The number of chunks that we allocate for purge testing.
tschatzl@6402:   size_t const num_chunks = 10;
tschatzl@6925: 
tschatzl@6402:   {
tschatzl@6925:     G1CodeRootSet set1(&mgr);
tschatzl@6402:     assert(set1.is_empty(), "Code root set must be initially empty but is not.");
tschatzl@6402: 
tschatzl@6932:     assert(G1CodeRootSet::static_mem_size() > sizeof(void*),
tschatzl@6932:            err_msg("The code root set's static memory usage seems too small, is only "SIZE_FORMAT" bytes", G1CodeRootSet::static_mem_size()));
tschatzl@6932: 
tschatzl@6402:     set1.add((nmethod*)1);
tschatzl@6925:     assert(mgr.num_chunks_handed_out() == 1,
tschatzl@6402:            err_msg("Must have allocated and handed out one chunk, but handed out "
tschatzl@6925:                    SIZE_FORMAT" chunks", mgr.num_chunks_handed_out()));
tschatzl@6402:     assert(set1.length() == 1, err_msg("Added exactly one element, but set contains "
tschatzl@6402:                                        SIZE_FORMAT" elements", set1.length()));
tschatzl@6402: 
tschatzl@6402:     // G1CodeRootChunk::word_size() is larger than G1CodeRootChunk::num_entries which
tschatzl@6402:     // we cannot access.
tschatzl@6402:     for (uint i = 0; i < G1CodeRootChunk::word_size() + 1; i++) {
tschatzl@6402:       set1.add((nmethod*)1);
tschatzl@6402:     }
tschatzl@6925:     assert(mgr.num_chunks_handed_out() == 1,
tschatzl@6402:            err_msg("Duplicate detection must have prevented allocation of further "
tschatzl@6925:                    "chunks but allocated "SIZE_FORMAT, mgr.num_chunks_handed_out()));
tschatzl@6402:     assert(set1.length() == 1,
tschatzl@6402:            err_msg("Duplicate detection should not have increased the set size but "
tschatzl@6402:                    "is "SIZE_FORMAT, set1.length()));
tschatzl@6402: 
tschatzl@6402:     size_t num_total_after_add = G1CodeRootChunk::word_size() + 1;
tschatzl@6402:     for (size_t i = 0; i < num_total_after_add - 1; i++) {
tschatzl@6925:       set1.add((nmethod*)(uintptr_t)(2 + i));
tschatzl@6402:     }
tschatzl@6925:     assert(mgr.num_chunks_handed_out() > 1,
tschatzl@6925:            "After adding more code roots, more than one additional chunk should have been handed out");
tschatzl@6402:     assert(set1.length() == num_total_after_add,
tschatzl@6402:            err_msg("After adding in total "SIZE_FORMAT" distinct code roots, they "
tschatzl@6402:                    "need to be in the set, but there are only "SIZE_FORMAT,
tschatzl@6402:                    num_total_after_add, set1.length()));
tschatzl@6402: 
tschatzl@6402:     size_t num_popped = 0;
tschatzl@6402:     while (set1.pop() != NULL) {
tschatzl@6402:       num_popped++;
tschatzl@6402:     }
tschatzl@6402:     assert(num_popped == num_total_after_add,
tschatzl@6402:            err_msg("Managed to pop "SIZE_FORMAT" code roots, but only "SIZE_FORMAT" "
tschatzl@6402:                    "were added", num_popped, num_total_after_add));
tschatzl@6925:     assert(mgr.num_chunks_handed_out() == 0,
tschatzl@6402:            err_msg("After popping all elements, all chunks must have been returned "
tschatzl@6925:                    "but there are still "SIZE_FORMAT" additional", mgr.num_chunks_handed_out()));
tschatzl@6402: 
tschatzl@6925:     mgr.purge_chunks(0);
tschatzl@6925:     assert(mgr.num_free_chunks() == 0,
tschatzl@6402:            err_msg("After purging everything, the free list must be empty but still "
tschatzl@6925:                    "contains "SIZE_FORMAT" chunks", mgr.num_free_chunks()));
tschatzl@6402: 
tschatzl@6402:     // Add some more handed out chunks.
tschatzl@6402:     size_t i = 0;
tschatzl@6925:     while (mgr.num_chunks_handed_out() < num_chunks) {
tschatzl@6402:       set1.add((nmethod*)i);
tschatzl@6402:       i++;
tschatzl@6402:     }
tschatzl@6402: 
tschatzl@6402:     {
tschatzl@6402:       // Generate chunks on the free list.
tschatzl@6925:       G1CodeRootSet set2(&mgr);
tschatzl@6402:       size_t i = 0;
tschatzl@6925:       while (mgr.num_chunks_handed_out() < (num_chunks * 2)) {
tschatzl@6402:         set2.add((nmethod*)i);
tschatzl@6402:         i++;
tschatzl@6402:       }
tschatzl@6402:       // Exit of the scope of the set2 object will call the destructor that generates
tschatzl@6402:       // num_chunks elements on the free list.
tschatzl@6402:     }
tschatzl@6402: 
tschatzl@6925:     assert(mgr.num_chunks_handed_out() == num_chunks,
tschatzl@6402:            err_msg("Deletion of the second set must have resulted in giving back "
tschatzl@6925:                    "those, but there are still "SIZE_FORMAT" additional handed out, expecting "
tschatzl@6925:                    SIZE_FORMAT, mgr.num_chunks_handed_out(), num_chunks));
tschatzl@6925:     assert(mgr.num_free_chunks() == num_chunks,
tschatzl@6402:            err_msg("After freeing "SIZE_FORMAT" chunks, they must be on the free list "
tschatzl@6925:                    "but there are only "SIZE_FORMAT, num_chunks, mgr.num_free_chunks()));
tschatzl@6402: 
tschatzl@6402:     size_t const test_percentage = 50;
tschatzl@6925:     mgr.purge_chunks(test_percentage);
tschatzl@6925:     assert(mgr.num_chunks_handed_out() == num_chunks,
tschatzl@6402:            err_msg("Purging must not hand out chunks but there are "SIZE_FORMAT,
tschatzl@6925:                    mgr.num_chunks_handed_out()));
tschatzl@6925:     assert(mgr.num_free_chunks() == (size_t)(mgr.num_chunks_handed_out() * test_percentage / 100),
tschatzl@6402:            err_msg("Must have purged "SIZE_FORMAT" percent of "SIZE_FORMAT" chunks"
tschatzl@6925:                    "but there are "SIZE_FORMAT, test_percentage, num_chunks,
tschatzl@6925:                    mgr.num_free_chunks()));
tschatzl@6402:     // Purge the remainder of the chunks on the free list.
tschatzl@6925:     mgr.purge_chunks(0);
tschatzl@6925:     assert(mgr.num_free_chunks() == 0, "Free List must be empty");
tschatzl@6925:     assert(mgr.num_chunks_handed_out() == num_chunks,
tschatzl@6402:            err_msg("Expected to be "SIZE_FORMAT" chunks handed out from the first set "
tschatzl@6925:                    "but there are "SIZE_FORMAT, num_chunks, mgr.num_chunks_handed_out()));
tschatzl@6402: 
tschatzl@6402:     // Exit of the scope of the set1 object will call the destructor that generates
tschatzl@6402:     // num_chunks additional elements on the free list.
tschatzl@6925:    }
tschatzl@6402: 
tschatzl@6925:   assert(mgr.num_chunks_handed_out() == 0,
tschatzl@6402:          err_msg("Deletion of the only set must have resulted in no chunks handed "
tschatzl@6925:                  "out, but there is still "SIZE_FORMAT" handed out", mgr.num_chunks_handed_out()));
tschatzl@6925:   assert(mgr.num_free_chunks() == num_chunks,
tschatzl@6402:          err_msg("After freeing "SIZE_FORMAT" chunks, they must be on the free list "
tschatzl@6925:                  "but there are only "SIZE_FORMAT, num_chunks, mgr.num_free_chunks()));
tschatzl@6402: 
tschatzl@6402:   // Restore initial state.
tschatzl@6925:   mgr.purge_chunks(0);
tschatzl@6925:   assert(mgr.num_free_chunks() == 0, "Free List must be empty");
tschatzl@6925:   assert(mgr.num_chunks_handed_out() == 0, "No additional elements must have been handed out yet");
tschatzl@6402: }
tschatzl@6402: 
tschatzl@6402: void TestCodeCacheRemSet_test() {
tschatzl@6402:   G1CodeRootSet::test();
tschatzl@6402: }
tschatzl@6402: #endif