tschatzl@6402: /*
dbuck@9487:  * Copyright (c) 2014, 2018, 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: #include "precompiled.hpp"
mgerdin@7208: #include "code/codeCache.hpp"
tschatzl@6402: #include "code/nmethod.hpp"
tschatzl@6402: #include "gc_implementation/g1/g1CodeCacheRemSet.hpp"
mgerdin@7208: #include "gc_implementation/g1/heapRegion.hpp"
mgerdin@7208: #include "memory/heap.hpp"
tschatzl@6402: #include "memory/iterator.hpp"
mgerdin@7208: #include "oops/oop.inline.hpp"
mgerdin@7208: #include "utilities/hashtable.inline.hpp"
mgerdin@7208: #include "utilities/stack.inline.hpp"
tschatzl@6402: 
drchase@6680: PRAGMA_FORMAT_MUTE_WARNINGS_FOR_GCC
drchase@6680: 
mgerdin@7208: class CodeRootSetTable : public Hashtable<nmethod*, mtGC> {
mgerdin@7208:   friend class G1CodeRootSetTest;
mgerdin@7208:   typedef HashtableEntry<nmethod*, mtGC> Entry;
mgerdin@7208: 
mgerdin@7208:   static CodeRootSetTable* volatile _purge_list;
mgerdin@7208: 
mgerdin@7208:   CodeRootSetTable* _purge_next;
mgerdin@7208: 
mgerdin@7208:   unsigned int compute_hash(nmethod* nm) {
mgerdin@7208:     uintptr_t hash = (uintptr_t)nm;
mgerdin@7208:     return hash ^ (hash >> 7); // code heap blocks are 128byte aligned
mgerdin@7208:   }
mgerdin@7208: 
mgerdin@7209:   void remove_entry(Entry* e, Entry* previous);
mgerdin@7208:   Entry* new_entry(nmethod* nm);
mgerdin@7208: 
mgerdin@7208:  public:
mgerdin@7208:   CodeRootSetTable(int size) : Hashtable<nmethod*, mtGC>(size, sizeof(Entry)), _purge_next(NULL) {}
mgerdin@7208:   ~CodeRootSetTable();
mgerdin@7208: 
mgerdin@7208:   // Needs to be protected locks
mgerdin@7208:   bool add(nmethod* nm);
mgerdin@7208:   bool remove(nmethod* nm);
mgerdin@7208: 
mgerdin@7208:   // Can be called without locking
mgerdin@7208:   bool contains(nmethod* nm);
mgerdin@7208: 
mgerdin@7208:   int entry_size() const { return BasicHashtable<mtGC>::entry_size(); }
mgerdin@7208: 
mgerdin@7208:   void copy_to(CodeRootSetTable* new_table);
mgerdin@7208:   void nmethods_do(CodeBlobClosure* blk);
mgerdin@7208: 
mgerdin@7208:   template<typename CB>
mgerdin@7209:   int remove_if(CB& should_remove);
mgerdin@7208: 
mgerdin@7208:   static void purge_list_append(CodeRootSetTable* tbl);
mgerdin@7208:   static void purge();
mgerdin@7208: 
mgerdin@7208:   static size_t static_mem_size() {
mgerdin@7208:     return sizeof(_purge_list);
mgerdin@7208:   }
dbuck@9487: 
dbuck@9487:   size_t mem_size();
mgerdin@7208: };
mgerdin@7208: 
mgerdin@7208: CodeRootSetTable* volatile CodeRootSetTable::_purge_list = NULL;
mgerdin@7208: 
dbuck@9487: size_t CodeRootSetTable::mem_size() {
dbuck@9487:   return sizeof(CodeRootSetTable) + (entry_size() * number_of_entries()) + (sizeof(HashtableBucket<mtGC>) * table_size());
dbuck@9487: }
dbuck@9487: 
mgerdin@7208: CodeRootSetTable::Entry* CodeRootSetTable::new_entry(nmethod* nm) {
mgerdin@7208:   unsigned int hash = compute_hash(nm);
mgerdin@7208:   Entry* entry = (Entry*) new_entry_free_list();
mgerdin@7208:   if (entry == NULL) {
mgerdin@7208:     entry = (Entry*) NEW_C_HEAP_ARRAY2(char, entry_size(), mtGC, CURRENT_PC);
mgerdin@7208:   }
mgerdin@7208:   entry->set_next(NULL);
mgerdin@7208:   entry->set_hash(hash);
mgerdin@7208:   entry->set_literal(nm);
mgerdin@7208:   return entry;
tschatzl@6402: }
tschatzl@6402: 
mgerdin@7209: void CodeRootSetTable::remove_entry(Entry* e, Entry* previous) {
mgerdin@7209:   int index = hash_to_index(e->hash());
mgerdin@7209:   assert((e == bucket(index)) == (previous == NULL), "if e is the first entry then previous should be null");
mgerdin@7209: 
mgerdin@7209:   if (previous == NULL) {
mgerdin@7209:     set_entry(index, e->next());
mgerdin@7209:   } else {
mgerdin@7209:     previous->set_next(e->next());
mgerdin@7209:   }
mgerdin@7209:   free_entry(e);
mgerdin@7209: }
mgerdin@7209: 
mgerdin@7208: CodeRootSetTable::~CodeRootSetTable() {
mgerdin@7208:   for (int index = 0; index < table_size(); ++index) {
mgerdin@7208:     for (Entry* e = bucket(index); e != NULL; ) {
mgerdin@7208:       Entry* to_remove = e;
mgerdin@7208:       // read next before freeing.
mgerdin@7208:       e = e->next();
mgerdin@7208:       unlink_entry(to_remove);
mgerdin@7208:       FREE_C_HEAP_ARRAY(char, to_remove, mtGC);
stefank@6992:     }
mgerdin@7208:   }
mgerdin@7208:   assert(number_of_entries() == 0, "should have removed all entries");
mgerdin@7208:   free_buckets();
mgerdin@7208:   for (BasicHashtableEntry<mtGC>* e = new_entry_free_list(); e != NULL; e = new_entry_free_list()) {
mgerdin@7208:     FREE_C_HEAP_ARRAY(char, e, mtGC);
tschatzl@6402:   }
tschatzl@6402: }
tschatzl@6402: 
mgerdin@7208: bool CodeRootSetTable::add(nmethod* nm) {
mgerdin@7208:   if (!contains(nm)) {
mgerdin@7208:     Entry* e = new_entry(nm);
mgerdin@7208:     int index = hash_to_index(e->hash());
mgerdin@7208:     add_entry(index, e);
mgerdin@7208:     return true;
mgerdin@7208:   }
mgerdin@7208:   return false;
mgerdin@7208: }
stefank@6992: 
mgerdin@7208: bool CodeRootSetTable::contains(nmethod* nm) {
mgerdin@7208:   int index = hash_to_index(compute_hash(nm));
mgerdin@7208:   for (Entry* e = bucket(index); e != NULL; e = e->next()) {
mgerdin@7208:     if (e->literal() == nm) {
stefank@6992:       return true;
stefank@6992:     }
stefank@6992:   }
stefank@6992:   return false;
stefank@6992: }
stefank@6992: 
mgerdin@7208: bool CodeRootSetTable::remove(nmethod* nm) {
mgerdin@7208:   int index = hash_to_index(compute_hash(nm));
mgerdin@7208:   Entry* previous = NULL;
mgerdin@7208:   for (Entry* e = bucket(index); e != NULL; previous = e, e = e->next()) {
mgerdin@7208:     if (e->literal() == nm) {
mgerdin@7209:       remove_entry(e, previous);
mgerdin@7208:       return true;
mgerdin@7208:     }
mgerdin@7208:   }
mgerdin@7208:   return false;
tschatzl@6402: }
tschatzl@6402: 
mgerdin@7208: void CodeRootSetTable::copy_to(CodeRootSetTable* new_table) {
mgerdin@7208:   for (int index = 0; index < table_size(); ++index) {
mgerdin@7208:     for (Entry* e = bucket(index); e != NULL; e = e->next()) {
mgerdin@7208:       new_table->add(e->literal());
mgerdin@7208:     }
mgerdin@7208:   }
mgerdin@7208:   new_table->copy_freelist(this);
tschatzl@6402: }
tschatzl@6402: 
mgerdin@7208: void CodeRootSetTable::nmethods_do(CodeBlobClosure* blk) {
mgerdin@7208:   for (int index = 0; index < table_size(); ++index) {
mgerdin@7208:     for (Entry* e = bucket(index); e != NULL; e = e->next()) {
mgerdin@7208:       blk->do_code_blob(e->literal());
mgerdin@7208:     }
tschatzl@6402:   }
tschatzl@6402: }
tschatzl@6402: 
mgerdin@7208: template<typename CB>
mgerdin@7209: int CodeRootSetTable::remove_if(CB& should_remove) {
mgerdin@7209:   int num_removed = 0;
mgerdin@7208:   for (int index = 0; index < table_size(); ++index) {
mgerdin@7208:     Entry* previous = NULL;
mgerdin@7208:     Entry* e = bucket(index);
mgerdin@7208:     while (e != NULL) {
mgerdin@7208:       Entry* next = e->next();
mgerdin@7208:       if (should_remove(e->literal())) {
mgerdin@7209:         remove_entry(e, previous);
mgerdin@7209:         ++num_removed;
mgerdin@7208:       } else {
mgerdin@7208:         previous = e;
mgerdin@7208:       }
mgerdin@7208:       e = next;
mgerdin@7208:     }
mgerdin@7208:   }
mgerdin@7209:   return num_removed;
tschatzl@6402: }
tschatzl@6402: 
mgerdin@7208: G1CodeRootSet::~G1CodeRootSet() {
mgerdin@7208:   delete _table;
mgerdin@7208: }
tschatzl@6925: 
mgerdin@7208: CodeRootSetTable* G1CodeRootSet::load_acquire_table() {
mgerdin@7208:   return (CodeRootSetTable*) OrderAccess::load_ptr_acquire(&_table);
mgerdin@7208: }
mgerdin@7208: 
mgerdin@7208: void G1CodeRootSet::allocate_small_table() {
mgerdin@7208:   _table = new CodeRootSetTable(SmallSize);
mgerdin@7208: }
mgerdin@7208: 
mgerdin@7208: void CodeRootSetTable::purge_list_append(CodeRootSetTable* table) {
mgerdin@7208:   for (;;) {
mgerdin@7208:     table->_purge_next = _purge_list;
mgerdin@7208:     CodeRootSetTable* old = (CodeRootSetTable*) Atomic::cmpxchg_ptr(table, &_purge_list, table->_purge_next);
mgerdin@7208:     if (old == table->_purge_next) {
mgerdin@7208:       break;
mgerdin@7208:     }
tschatzl@6925:   }
mgerdin@7208: }
mgerdin@7208: 
mgerdin@7208: void CodeRootSetTable::purge() {
mgerdin@7208:   CodeRootSetTable* table = _purge_list;
mgerdin@7208:   _purge_list = NULL;
mgerdin@7208:   while (table != NULL) {
mgerdin@7208:     CodeRootSetTable* to_purge = table;
mgerdin@7208:     table = table->_purge_next;
mgerdin@7208:     delete to_purge;
mgerdin@7208:   }
mgerdin@7208: }
mgerdin@7208: 
mgerdin@7208: void G1CodeRootSet::move_to_large() {
mgerdin@7208:   CodeRootSetTable* temp = new CodeRootSetTable(LargeSize);
mgerdin@7208: 
mgerdin@7208:   _table->copy_to(temp);
mgerdin@7208: 
mgerdin@7208:   CodeRootSetTable::purge_list_append(_table);
mgerdin@7208: 
mgerdin@7208:   OrderAccess::release_store_ptr(&_table, temp);
mgerdin@7208: }
mgerdin@7208: 
mgerdin@7208: void G1CodeRootSet::purge() {
mgerdin@7208:   CodeRootSetTable::purge();
mgerdin@7208: }
mgerdin@7208: 
mgerdin@7208: size_t G1CodeRootSet::static_mem_size() {
mgerdin@7208:   return CodeRootSetTable::static_mem_size();
mgerdin@7208: }
mgerdin@7208: 
mgerdin@7208: void G1CodeRootSet::add(nmethod* method) {
mgerdin@7208:   bool added = false;
mgerdin@7208:   if (is_empty()) {
mgerdin@7208:     allocate_small_table();
mgerdin@7208:   }
mgerdin@7208:   added = _table->add(method);
mgerdin@7208:   if (added) {
dbuck@9487:     if (_length == Threshold) {
dbuck@9487:       move_to_large();
dbuck@9487:     }
mgerdin@7208:     ++_length;
mgerdin@7208:   }
dbuck@9487:   assert(_length == (size_t)_table->number_of_entries(), "sizes should match");
mgerdin@7208: }
mgerdin@7208: 
mgerdin@7208: bool G1CodeRootSet::remove(nmethod* method) {
mgerdin@7208:   bool removed = false;
mgerdin@7208:   if (_table != NULL) {
mgerdin@7208:     removed = _table->remove(method);
mgerdin@7208:   }
mgerdin@7208:   if (removed) {
mgerdin@7208:     _length--;
mgerdin@7208:     if (_length == 0) {
mgerdin@7208:       clear();
mgerdin@7208:     }
mgerdin@7208:   }
dbuck@9487:   assert((_length == 0 && _table == NULL) ||
dbuck@9487:          (_length == (size_t)_table->number_of_entries()), "sizes should match");
mgerdin@7208:   return removed;
mgerdin@7208: }
mgerdin@7208: 
mgerdin@7208: bool G1CodeRootSet::contains(nmethod* method) {
dbuck@9487:   CodeRootSetTable* table = load_acquire_table(); // contains() may be called outside of lock, so ensure mem sync.
mgerdin@7208:   if (table != NULL) {
mgerdin@7208:     return table->contains(method);
mgerdin@7208:   }
mgerdin@7208:   return false;
mgerdin@7208: }
mgerdin@7208: 
mgerdin@7208: void G1CodeRootSet::clear() {
mgerdin@7208:   delete _table;
mgerdin@7208:   _table = NULL;
mgerdin@7208:   _length = 0;
mgerdin@7208: }
mgerdin@7208: 
mgerdin@7208: size_t G1CodeRootSet::mem_size() {
dbuck@9487:   return sizeof(*this) + (_table != NULL ? _table->mem_size() : 0);
mgerdin@7208: }
mgerdin@7208: 
mgerdin@7208: void G1CodeRootSet::nmethods_do(CodeBlobClosure* blk) const {
mgerdin@7208:   if (_table != NULL) {
mgerdin@7208:     _table->nmethods_do(blk);
mgerdin@7208:   }
mgerdin@7208: }
mgerdin@7208: 
mgerdin@7208: class CleanCallback : public StackObj {
mgerdin@7208:   class PointsIntoHRDetectionClosure : public OopClosure {
mgerdin@7208:     HeapRegion* _hr;
mgerdin@7208:    public:
mgerdin@7208:     bool _points_into;
mgerdin@7208:     PointsIntoHRDetectionClosure(HeapRegion* hr) : _hr(hr), _points_into(false) {}
mgerdin@7208: 
mgerdin@7208:     void do_oop(narrowOop* o) {
mgerdin@7208:       do_oop_work(o);
mgerdin@7208:     }
mgerdin@7208: 
mgerdin@7208:     void do_oop(oop* o) {
mgerdin@7208:       do_oop_work(o);
mgerdin@7208:     }
mgerdin@7208: 
mgerdin@7208:     template <typename T>
mgerdin@7208:     void do_oop_work(T* p) {
mgerdin@7208:       if (_hr->is_in(oopDesc::load_decode_heap_oop(p))) {
mgerdin@7208:         _points_into = true;
mgerdin@7208:       }
mgerdin@7208:     }
mgerdin@7208:   };
mgerdin@7208: 
mgerdin@7208:   PointsIntoHRDetectionClosure _detector;
mgerdin@7208:   CodeBlobToOopClosure _blobs;
mgerdin@7208: 
mgerdin@7208:  public:
mgerdin@7208:   CleanCallback(HeapRegion* hr) : _detector(hr), _blobs(&_detector, !CodeBlobToOopClosure::FixRelocations) {}
mgerdin@7208: 
mgerdin@7208:   bool operator() (nmethod* nm) {
mgerdin@7208:     _detector._points_into = false;
mgerdin@7208:     _blobs.do_code_blob(nm);
mgerdin@7209:     return !_detector._points_into;
mgerdin@7208:   }
mgerdin@7208: };
mgerdin@7208: 
mgerdin@7208: void G1CodeRootSet::clean(HeapRegion* owner) {
mgerdin@7208:   CleanCallback should_clean(owner);
mgerdin@7208:   if (_table != NULL) {
mgerdin@7209:     int removed = _table->remove_if(should_clean);
mgerdin@7209:     assert((size_t)removed <= _length, "impossible");
mgerdin@7209:     _length -= removed;
mgerdin@7209:   }
mgerdin@7209:   if (_length == 0) {
mgerdin@7209:     clear();
mgerdin@7208:   }
tschatzl@6402: }
tschatzl@6402: 
tschatzl@6925: #ifndef PRODUCT
tschatzl@6925: 
mgerdin@7208: class G1CodeRootSetTest {
mgerdin@7208:  public:
mgerdin@7208:   static void test() {
mgerdin@7208:     {
mgerdin@7208:       G1CodeRootSet set1;
mgerdin@7208:       assert(set1.is_empty(), "Code root set must be initially empty but is not.");
tschatzl@6402: 
mgerdin@7208:       assert(G1CodeRootSet::static_mem_size() == sizeof(void*),
kevinw@9327:           err_msg("The code root set's static memory usage is incorrect, " SIZE_FORMAT " bytes", G1CodeRootSet::static_mem_size()));
mgerdin@7208: 
mgerdin@7208:       set1.add((nmethod*)1);
mgerdin@7208:       assert(set1.length() == 1, err_msg("Added exactly one element, but set contains "
kevinw@9327:           SIZE_FORMAT " elements", set1.length()));
mgerdin@7208: 
mgerdin@7208:       const size_t num_to_add = (size_t)G1CodeRootSet::Threshold + 1;
mgerdin@7208: 
mgerdin@7208:       for (size_t i = 1; i <= num_to_add; i++) {
mgerdin@7208:         set1.add((nmethod*)1);
mgerdin@7208:       }
mgerdin@7208:       assert(set1.length() == 1,
mgerdin@7208:           err_msg("Duplicate detection should not have increased the set size but "
kevinw@9327:               "is " SIZE_FORMAT, set1.length()));
mgerdin@7208: 
mgerdin@7208:       for (size_t i = 2; i <= num_to_add; i++) {
mgerdin@7208:         set1.add((nmethod*)(uintptr_t)(i));
mgerdin@7208:       }
mgerdin@7208:       assert(set1.length() == num_to_add,
kevinw@9327:           err_msg("After adding in total " SIZE_FORMAT " distinct code roots, they "
kevinw@9327:               "need to be in the set, but there are only " SIZE_FORMAT,
mgerdin@7208:               num_to_add, set1.length()));
mgerdin@7208: 
mgerdin@7208:       assert(CodeRootSetTable::_purge_list != NULL, "should have grown to large hashtable");
mgerdin@7208: 
mgerdin@7208:       size_t num_popped = 0;
mgerdin@7208:       for (size_t i = 1; i <= num_to_add; i++) {
mgerdin@7208:         bool removed = set1.remove((nmethod*)i);
mgerdin@7208:         if (removed) {
mgerdin@7208:           num_popped += 1;
mgerdin@7208:         } else {
mgerdin@7208:           break;
mgerdin@7208:         }
mgerdin@7208:       }
mgerdin@7208:       assert(num_popped == num_to_add,
kevinw@9327:           err_msg("Managed to pop " SIZE_FORMAT " code roots, but only " SIZE_FORMAT " "
mgerdin@7208:               "were added", num_popped, num_to_add));
mgerdin@7208:       assert(CodeRootSetTable::_purge_list != NULL, "should have grown to large hashtable");
mgerdin@7208: 
mgerdin@7208:       G1CodeRootSet::purge();
mgerdin@7208: 
mgerdin@7208:       assert(CodeRootSetTable::_purge_list == NULL, "should have purged old small tables");
mgerdin@7208: 
mgerdin@7208:     }
mgerdin@7208: 
mgerdin@7208:   }
mgerdin@7208: };
mgerdin@7208: 
mgerdin@7208: void TestCodeCacheRemSet_test() {
mgerdin@7208:   G1CodeRootSetTest::test();
tschatzl@6925: }
tschatzl@6925: 
tschatzl@6925: #endif