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_UTILITIES_OBJECTBITSET_HPP
26 #define SHARE_UTILITIES_OBJECTBITSET_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 MemRegion;
35
36 /*
37 * ObjectBitSet is a sparse bitmap for marking objects in the Java heap.
38 * It holds one bit per ObjAlignmentInBytes-aligned address. Its underlying backing memory is
39 * allocated on-demand only, in fragments covering 64M heap ranges. Fragments are never deleted
40 * during the lifetime of the ObjectBitSet. The underlying memory is allocated from C-Heap.
41 */
42 template<MEMFLAGS F>
43 class ObjectBitSet : public CHeapObj<F> {
44 const static size_t _bitmap_granularity_shift = 26; // 64M
45 const static size_t _bitmap_granularity_size = (size_t)1 << _bitmap_granularity_shift;
46 const static size_t _bitmap_granularity_mask = _bitmap_granularity_size - 1;
47
48 class BitMapFragment;
49
50 class BitMapFragmentTable : public BasicHashtable<F> {
51 class Entry : public BasicHashtableEntry<F> {
52 public:
53 uintptr_t _key;
54 CHeapBitMap* _value;
55
56 Entry* next() {
57 return (Entry*)BasicHashtableEntry<F>::next();
58 }
59 };
60
61 protected:
62 Entry* bucket(int i) const;
63
64 Entry* new_entry(unsigned int hashValue, uintptr_t key, CHeapBitMap* value);
65
66 unsigned hash_segment(uintptr_t key) {
67 unsigned hash = (unsigned)key;
68 return hash ^ (hash >> 3);
69 }
70
71 unsigned hash_to_index(unsigned hash) {
72 return hash & (BasicHashtable<F>::table_size() - 1);
73 }
74
75 public:
76 BitMapFragmentTable(int table_size) : BasicHashtable<F>(table_size, sizeof(Entry)) {}
77 ~BitMapFragmentTable();
78 void add(uintptr_t key, CHeapBitMap* value);
79 CHeapBitMap** lookup(uintptr_t key);
80 };
81
82 CHeapBitMap* get_fragment_bits(uintptr_t addr);
83
84 BitMapFragmentTable _bitmap_fragments;
85 BitMapFragment* _fragment_list;
86 CHeapBitMap* _last_fragment_bits;
87 uintptr_t _last_fragment_granule;
88
89 public:
90 ObjectBitSet();
91 ~ObjectBitSet();
92
93 BitMap::idx_t addr_to_bit(uintptr_t addr) const;
94
95 void mark_obj(uintptr_t addr);
96
97 void mark_obj(oop obj) {
98 return mark_obj(cast_from_oop<uintptr_t>(obj));
99 }
100
101 bool is_marked(uintptr_t addr);
102
103 bool is_marked(oop obj) {
104 return is_marked(cast_from_oop<uintptr_t>(obj));
105 }
106 };
107
108 template<MEMFLAGS F>
109 class ObjectBitSet<F>::BitMapFragment : public CHeapObj<F> {
110 CHeapBitMap _bits;
111 BitMapFragment* _next;
112
113 public:
114 BitMapFragment(uintptr_t granule, BitMapFragment* next);
115
116 BitMapFragment* next() const {
117 return _next;
118 }
119
120 CHeapBitMap* bits() {
121 return &_bits;
122 }
123 };
124
125 #endif // SHARE_UTILITIES_OBJECTBITSET_HPP