1 /*
2 * Copyright Amazon.com Inc. 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_GC_SHENANDOAH_SHENANDOAHSIMPLEBITMAP_HPP
26 #define SHARE_GC_SHENANDOAH_SHENANDOAHSIMPLEBITMAP_HPP
27
28 #include <cstddef>
29
30 #include "gc/shenandoah/shenandoahAsserts.hpp"
31
32 // TODO: Merge the enhanced capabilities of ShenandoahSimpleBitMap into src/hotspot/share/utilities/bitMap.hpp
33 // and deprecate ShenandoahSimpleBitMap. The key enhanced capabilities to be integrated include:
34 //
35 // 1. Allow searches from high to low memory (when biasing allocations towards the top of the heap)
36 // 2. Allow searches for clusters of contiguous set bits (to expedite allocation for humongous objects)
37 //
38 // idx_t is defined here as ssize_t. In src/hotspot/share/utiliities/bitMap.hpp, idx is defined as size_t.
39 // This is a significant incompatibility.
40 //
41 // The API and internal implementation of ShenandoahSimpleBitMap and ShenandoahRegionPartitions use idx_t to
42 // represent index, even though index is "inherently" unsigned. There are two reasons for this choice:
43 // 1. We use -1 as a sentinel value to represent empty partitions. This same value may be used to represent
44 // failure to find a previous set bit or previous range of set bits.
45 // 2. Certain loops are written most naturally if the iterator, which may hold the sentinel -1 value, can be
46 // declared as signed and the terminating condition can be < 0.
47
48 typedef ssize_t idx_t;
49
50 // ShenandoahSimpleBitMap resembles CHeapBitMap but adds missing support for find_first_consecutive_set_bits() and
51 // find_last_consecutive_set_bits. An alternative refactoring of code would subclass CHeapBitMap, but this might
52 // break abstraction rules, because efficient implementation requires assumptions about superclass internals that
53 // might be violated through future software maintenance.
54 class ShenandoahSimpleBitMap {
55 const idx_t _num_bits;
56 const size_t _num_words;
57 uintx* const _bitmap;
58
59 public:
60 ShenandoahSimpleBitMap(size_t num_bits);
61
62 ~ShenandoahSimpleBitMap();
63
64 void clear_all() {
65 for (size_t i = 0; i < _num_words; i++) {
66 _bitmap[i] = 0;
67 }
68 }
69
70 private:
71
72 // Count consecutive ones in forward order, starting from start_idx. Requires that there is at least one zero
73 // between start_idx and index value (_num_bits - 1), inclusive.
74 size_t count_leading_ones(idx_t start_idx) const;
75
76 // Count consecutive ones in reverse order, starting from last_idx. Requires that there is at least one zero
77 // between last_idx and index value zero, inclusive.
78 size_t count_trailing_ones(idx_t last_idx) const;
79
80 bool is_forward_consecutive_ones(idx_t start_idx, idx_t count) const;
81 bool is_backward_consecutive_ones(idx_t last_idx, idx_t count) const;
82
83 static inline uintx tail_mask(uintx bit_number);
84
85 public:
86
87 inline idx_t aligned_index(idx_t idx) const {
88 assert((idx >= 0) && (idx < _num_bits), "precondition");
89 idx_t array_idx = idx & ~(BitsPerWord - 1);
90 return array_idx;
91 }
92
93 inline constexpr idx_t alignment() const {
94 return BitsPerWord;
95 }
96
97 // For testing
98 inline idx_t size() const {
99 return _num_bits;
100 }
101
102 // Return the word that holds idx bit and its neighboring bits.
103 inline uintx bits_at(idx_t idx) const {
104 assert((idx >= 0) && (idx < _num_bits), "precondition");
105 idx_t array_idx = idx >> LogBitsPerWord;
106 return _bitmap[array_idx];
107 }
108
109 inline void set_bit(idx_t idx) {
110 assert((idx >= 0) && (idx < _num_bits), "precondition");
111 size_t array_idx = idx >> LogBitsPerWord;
112 uintx bit_number = idx & (BitsPerWord - 1);
113 uintx the_bit = nth_bit(bit_number);
114 _bitmap[array_idx] |= the_bit;
115 }
116
117 inline void clear_bit(idx_t idx) {
118 assert((idx >= 0) && (idx < _num_bits), "precondition");
119 assert(idx >= 0, "precondition");
120 size_t array_idx = idx >> LogBitsPerWord;
121 uintx bit_number = idx & (BitsPerWord - 1);
122 uintx the_bit = nth_bit(bit_number);
123 _bitmap[array_idx] &= ~the_bit;
124 }
125
126 inline bool is_set(idx_t idx) const {
127 assert((idx >= 0) && (idx < _num_bits), "precondition");
128 assert(idx >= 0, "precondition");
129 size_t array_idx = idx >> LogBitsPerWord;
130 uintx bit_number = idx & (BitsPerWord - 1);
131 uintx the_bit = nth_bit(bit_number);
132 return (_bitmap[array_idx] & the_bit) != 0;
133 }
134
135 // Return the index of the first set bit in the range [beg, size()), or size() if none found.
136 // precondition: beg and end form a valid range for the bitmap.
137 inline idx_t find_first_set_bit(idx_t beg) const;
138
139 // Return the index of the first set bit in the range [beg, end), or end if none found.
140 // precondition: beg and end form a valid range for the bitmap.
141 inline idx_t find_first_set_bit(idx_t beg, idx_t end) const;
142
143 // Return the index of the last set bit in the range (-1, end], or -1 if none found.
144 // precondition: beg and end form a valid range for the bitmap.
145 inline idx_t find_last_set_bit(idx_t end) const;
146
147 // Return the index of the last set bit in the range (beg, end], or beg if none found.
148 // precondition: beg and end form a valid range for the bitmap.
149 inline idx_t find_last_set_bit(idx_t beg, idx_t end) const;
150
151 // Return the start index of the first run of <num_bits> consecutive set bits for which the first set bit is within
152 // the range [beg, size()), or size() if the run of <num_bits> is not found within this range.
153 // precondition: beg is within the valid range for the bitmap.
154 inline idx_t find_first_consecutive_set_bits(idx_t beg, size_t num_bits) const;
155
156 // Return the start index of the first run of <num_bits> consecutive set bits for which the first set bit is within
157 // the range [beg, end), or end if the run of <num_bits> is not found within this range.
158 // precondition: beg and end form a valid range for the bitmap.
159 idx_t find_first_consecutive_set_bits(idx_t beg, idx_t end, size_t num_bits) const;
160
161 // Return the start index of the last run of <num_bits> consecutive set bits for which the entire run of set bits is within
162 // the range (-1, end], or -1 if the run of <num_bits> is not found within this range.
163 // precondition: end is within the valid range for the bitmap.
164 inline idx_t find_last_consecutive_set_bits(idx_t end, size_t num_bits) const;
165
166 // Return the start index of the first run of <num_bits> consecutive set bits for which the entire run of set bits is within
167 // the range (beg, end], or beg if the run of <num_bits> is not found within this range.
168 // precondition: beg and end form a valid range for the bitmap.
169 idx_t find_last_consecutive_set_bits(idx_t beg, idx_t end, size_t num_bits) const;
170 };
171
172 #endif // SHARE_GC_SHENANDOAH_SHENANDOAHSIMPLEBITMAP_HPP