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 violatee 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 public:
84
85 inline idx_t aligned_index(idx_t idx) const {
86 assert((idx >= 0) && (idx < _num_bits), "precondition");
87 idx_t array_idx = idx & ~right_n_bits(LogBitsPerWord);
88 return array_idx;
89 }
90
91 inline constexpr idx_t alignment() const {
92 return BitsPerWord;
93 }
94
95 // For testing
96 inline idx_t size() const {
97 return _num_bits;
98 }
99
100 // Return the word that holds idx bit and its neighboring bits.
101 inline uintx bits_at(idx_t idx) const {
102 assert((idx >= 0) && (idx < _num_bits), "precondition");
103 idx_t array_idx = idx >> LogBitsPerWord;
104 return _bitmap[array_idx];
105 }
106
107 inline void set_bit(idx_t idx) {
108 assert((idx >= 0) && (idx < _num_bits), "precondition");
109 size_t array_idx = idx >> LogBitsPerWord;
110 uintx bit_number = idx & right_n_bits(LogBitsPerWord);
111 uintx the_bit = nth_bit(bit_number);
112 _bitmap[array_idx] |= the_bit;
113 }
114
115 inline void clear_bit(idx_t idx) {
116 assert((idx >= 0) && (idx < _num_bits), "precondition");
117 assert(idx >= 0, "precondition");
118 size_t array_idx = idx >> LogBitsPerWord;
119 uintx bit_number = idx & right_n_bits(LogBitsPerWord);
120 uintx the_bit = nth_bit(bit_number);
121 _bitmap[array_idx] &= ~the_bit;
122 }
123
124 inline bool is_set(idx_t idx) const {
125 assert((idx >= 0) && (idx < _num_bits), "precondition");
126 assert(idx >= 0, "precondition");
127 size_t array_idx = idx >> LogBitsPerWord;
128 uintx bit_number = idx & right_n_bits(LogBitsPerWord);
129 uintx the_bit = nth_bit(bit_number);
130 return (_bitmap[array_idx] & the_bit)? true: false;
131 }
132
133 // Return the index of the first set bit in the range [beg, size()), or size() if none found.
134 // precondition: beg and end form a valid range for the bitmap.
135 inline idx_t find_first_set_bit(idx_t beg) const;
136
137 // Return the index of the first set bit in the range [beg, end), or end if none found.
138 // precondition: beg and end form a valid range for the bitmap.
139 inline idx_t find_first_set_bit(idx_t beg, idx_t end) const;
140
141 // Return the index of the last set bit in the range (-1, end], or -1 if none found.
142 // precondition: beg and end form a valid range for the bitmap.
143 inline idx_t find_last_set_bit(idx_t end) const;
144
145 // Return the index of the last set bit in the range (beg, end], or beg if none found.
146 // precondition: beg and end form a valid range for the bitmap.
147 inline idx_t find_last_set_bit(idx_t beg, idx_t end) const;
148
149 // Return the start index of the first run of <num_bits> consecutive set bits for which the first set bit is within
150 // the range [beg, size()), or size() if the run of <num_bits> is not found within this range.
151 // precondition: beg is within the valid range for the bitmap.
152 inline idx_t find_first_consecutive_set_bits(idx_t beg, size_t num_bits) const;
153
154 // Return the start index of the first run of <num_bits> consecutive set bits for which the first set bit is within
155 // the range [beg, end), or end if the run of <num_bits> is not found within this range.
156 // precondition: beg and end form a valid range for the bitmap.
157 idx_t find_first_consecutive_set_bits(idx_t beg, idx_t end, size_t num_bits) const;
158
159 // Return the start index of the last run of <num_bits> consecutive set bits for which the entire run of set bits is within
160 // the range (-1, end], or -1 if the run of <num_bits> is not found within this range.
161 // precondition: end is within the valid range for the bitmap.
162 inline idx_t find_last_consecutive_set_bits(idx_t end, size_t num_bits) const;
163
164 // Return the start index of the first run of <num_bits> consecutive set bits for which the entire run of set bits is within
165 // the range (beg, end], or beg if the run of <num_bits> is not found within this range.
166 // precondition: beg and end form a valid range for the bitmap.
167 idx_t find_last_consecutive_set_bits(idx_t beg, idx_t end, size_t num_bits) const;
168 };
169
170 #endif // SHARE_GC_SHENANDOAH_SHENANDOAHSIMPLEBITMAP_HPP