1 /*
  2  * Copyright (c) 2014, 2022, 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_JFR_LEAKPROFILER_CHAINS_BITSET_HPP
 26 #define SHARE_JFR_LEAKPROFILER_CHAINS_BITSET_HPP
 27 
 28 #include "memory/allocation.hpp"
 29 #include "oops/oop.hpp"
 30 #include "oops/oopsHierarchy.hpp"
 31 #include "utilities/bitMap.hpp"
 32 #include "utilities/hashtable.hpp"
 33 
 34 class JfrVirtualMemory;
 35 class MemRegion;
 36 
 37 class BitSet : public CHeapObj<mtTracing> {
 38   const static size_t _bitmap_granularity_shift = 26; // 64M
 39   const static size_t _bitmap_granularity_size = (size_t)1 << _bitmap_granularity_shift;
 40   const static size_t _bitmap_granularity_mask = _bitmap_granularity_size - 1;
 41 
 42   class BitMapFragment;
 43 
 44   class BitMapFragmentTable : public BasicHashtable<mtTracing> {
 45     class Entry : public BasicHashtableEntry<mtTracing> {
 46     public:
 47       uintptr_t _key;
 48       CHeapBitMap* _value;
 49 
 50       Entry* next() {
 51         return (Entry*)BasicHashtableEntry<mtTracing>::next();
 52       }
 53     };
 54 
 55   protected:
 56     Entry* bucket(int i) const;
 57 
 58     Entry* new_entry(unsigned int hashValue, uintptr_t key, CHeapBitMap* value);
 59 
 60     unsigned hash_segment(uintptr_t key) {
 61       unsigned hash = (unsigned)key;
 62       return hash ^ (hash >> 3);
 63     }
 64 
 65     unsigned hash_to_index(unsigned hash) {
 66       return hash & (BasicHashtable<mtTracing>::table_size() - 1);
 67     }
 68 
 69   public:
 70     BitMapFragmentTable(int table_size) : BasicHashtable<mtTracing>(table_size, sizeof(Entry)) {}
 71     ~BitMapFragmentTable();
 72     void add(uintptr_t key, CHeapBitMap* value);
 73     CHeapBitMap** lookup(uintptr_t key);
 74   };
 75 
 76   CHeapBitMap* get_fragment_bits(uintptr_t addr);
 77 
 78   BitMapFragmentTable _bitmap_fragments;
 79   BitMapFragment* _fragment_list;
 80   CHeapBitMap* _last_fragment_bits;
 81   uintptr_t _last_fragment_granule;
 82 
 83  public:
 84   BitSet();
 85   ~BitSet();
 86 
 87   BitMap::idx_t addr_to_bit(uintptr_t addr) const;
 88 
 89   void mark_obj(uintptr_t addr);
 90 
 91   void mark_obj(oop obj) {
 92     return mark_obj(cast_from_oop<uintptr_t>(obj));
 93   }
 94 
 95   bool is_marked(uintptr_t addr);
 96 
 97   bool is_marked(oop obj) {
 98     return is_marked(cast_from_oop<uintptr_t>(obj));
 99   }
100 };
101 
102 class BitSet::BitMapFragment : public CHeapObj<mtTracing> {
103   CHeapBitMap _bits;
104   BitMapFragment* _next;
105 
106 public:
107   BitMapFragment(uintptr_t granule, BitMapFragment* next);
108 
109   BitMapFragment* next() const {
110     return _next;
111   }
112 
113   CHeapBitMap* bits() {
114     return &_bits;
115   }
116 };
117 
118 #endif // SHARE_JFR_LEAKPROFILER_CHAINS_BITSET_HPP