1/*
2 * Copyright (c) 2018, 2019, Oracle and/or its affiliates. All rights reserved.
3 * Copyright (c) 2018 SAP SE. All rights reserved.
4 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
5 *
6 * This code is free software; you can redistribute it and/or modify it
7 * under the terms of the GNU General Public License version 2 only, as
8 * published by the Free Software Foundation.
9 *
10 * This code is distributed in the hope that it will be useful, but WITHOUT
11 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
12 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
13 * version 2 for more details (a copy is included in the LICENSE file that
14 * accompanied this code).
15 *
16 * You should have received a copy of the GNU General Public License version
17 * 2 along with this work; if not, write to the Free Software Foundation,
18 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
19 *
20 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
21 * or visit www.oracle.com if you need additional information or have any
22 * questions.
23 *
24 */
25
26#ifndef SHARE_MEMORY_METASPACE_OCCUPANCYMAP_HPP
27#define SHARE_MEMORY_METASPACE_OCCUPANCYMAP_HPP
28
29#include "memory/allocation.hpp"
30#include "utilities/debug.hpp"
31#include "utilities/globalDefinitions.hpp"
32
33
34namespace metaspace {
35
36class Metachunk;
37
38// Helper for Occupancy Bitmap. A type trait to give an all-bits-are-one-unsigned constant.
39template <typename T> struct all_ones { static const T value; };
40template <> struct all_ones <uint64_t> { static const uint64_t value = 0xFFFFFFFFFFFFFFFFULL; };
41template <> struct all_ones <uint32_t> { static const uint32_t value = 0xFFFFFFFF; };
42
43// The OccupancyMap is a bitmap which, for a given VirtualSpaceNode,
44// keeps information about
45// - where a chunk starts
46// - whether a chunk is in-use or free
47// A bit in this bitmap represents one range of memory in the smallest
48// chunk size (SpecializedChunk or ClassSpecializedChunk).
49class OccupancyMap : public CHeapObj<mtInternal> {
50
51 // The address range this map covers.
52 const MetaWord* const _reference_address;
53 const size_t _word_size;
54
55 // The word size of a specialized chunk, aka the number of words one
56 // bit in this map represents.
57 const size_t _smallest_chunk_word_size;
58
59 // map data
60 // Data are organized in two bit layers:
61 // The first layer is the chunk-start-map. Here, a bit is set to mark
62 // the corresponding region as the head of a chunk.
63 // The second layer is the in-use-map. Here, a set bit indicates that
64 // the corresponding belongs to a chunk which is in use.
65 uint8_t* _map[2];
66
67 enum { layer_chunk_start_map = 0, layer_in_use_map = 1 };
68
69 // length, in bytes, of bitmap data
70 size_t _map_size;
71
72 // Returns true if bit at position pos at bit-layer layer is set.
73 bool get_bit_at_position(unsigned pos, unsigned layer) const {
74 assert(layer == 0 || layer == 1, "Invalid layer %d", layer);
75 const unsigned byteoffset = pos / 8;
76 assert(byteoffset < _map_size,
77 "invalid byte offset (%u), map size is " SIZE_FORMAT ".", byteoffset, _map_size);
78 const unsigned mask = 1 << (pos % 8);
79 return (_map[layer][byteoffset] & mask) > 0;
80 }
81
82 // Changes bit at position pos at bit-layer layer to value v.
83 void set_bit_at_position(unsigned pos, unsigned layer, bool v) {
84 assert(layer == 0 || layer == 1, "Invalid layer %d", layer);
85 const unsigned byteoffset = pos / 8;
86 assert(byteoffset < _map_size,
87 "invalid byte offset (%u), map size is " SIZE_FORMAT ".", byteoffset, _map_size);
88 const unsigned mask = 1 << (pos % 8);
89 if (v) {
90 _map[layer][byteoffset] |= mask;
91 } else {
92 _map[layer][byteoffset] &= ~mask;
93 }
94 }
95
96 // Optimized case of is_any_bit_set_in_region for 32/64bit aligned access:
97 // pos is 32/64 aligned and num_bits is 32/64.
98 // This is the typical case when coalescing to medium chunks, whose size is
99 // 32 or 64 times the specialized chunk size (depending on class or non class
100 // case), so they occupy 64 bits which should be 64bit aligned, because
101 // chunks are chunk-size aligned.
102 template <typename T>
103 bool is_any_bit_set_in_region_3264(unsigned pos, unsigned num_bits, unsigned layer) const {
104 assert(_map_size > 0, "not initialized");
105 assert(layer == 0 || layer == 1, "Invalid layer %d.", layer);
106 assert(pos % (sizeof(T) * 8) == 0, "Bit position must be aligned (%u).", pos);
107 assert(num_bits == (sizeof(T) * 8), "Number of bits incorrect (%u).", num_bits);
108 const size_t byteoffset = pos / 8;
109 assert(byteoffset <= (_map_size - sizeof(T)),
110 "Invalid byte offset (" SIZE_FORMAT "), map size is " SIZE_FORMAT ".", byteoffset, _map_size);
111 const T w = *(T*)(_map[layer] + byteoffset);
112 return w > 0 ? true : false;
113 }
114
115 // Returns true if any bit in region [pos1, pos1 + num_bits) is set in bit-layer layer.
116 bool is_any_bit_set_in_region(unsigned pos, unsigned num_bits, unsigned layer) const {
117 if (pos % 32 == 0 && num_bits == 32) {
118 return is_any_bit_set_in_region_3264<uint32_t>(pos, num_bits, layer);
119 } else if (pos % 64 == 0 && num_bits == 64) {
120 return is_any_bit_set_in_region_3264<uint64_t>(pos, num_bits, layer);
121 } else {
122 for (unsigned n = 0; n < num_bits; n ++) {
123 if (get_bit_at_position(pos + n, layer)) {
124 return true;
125 }
126 }
127 }
128 return false;
129 }
130
131 // Returns true if any bit in region [p, p+word_size) is set in bit-layer layer.
132 bool is_any_bit_set_in_region(MetaWord* p, size_t word_size, unsigned layer) const {
133 assert(word_size % _smallest_chunk_word_size == 0,
134 "Region size " SIZE_FORMAT " not a multiple of smallest chunk size.", word_size);
135 const unsigned pos = get_bitpos_for_address(p);
136 const unsigned num_bits = (unsigned) (word_size / _smallest_chunk_word_size);
137 return is_any_bit_set_in_region(pos, num_bits, layer);
138 }
139
140 // Optimized case of set_bits_of_region for 32/64bit aligned access:
141 // pos is 32/64 aligned and num_bits is 32/64.
142 // This is the typical case when coalescing to medium chunks, whose size
143 // is 32 or 64 times the specialized chunk size (depending on class or non
144 // class case), so they occupy 64 bits which should be 64bit aligned,
145 // because chunks are chunk-size aligned.
146 template <typename T>
147 void set_bits_of_region_T(unsigned pos, unsigned num_bits, unsigned layer, bool v) {
148 assert(pos % (sizeof(T) * 8) == 0, "Bit position must be aligned to %u (%u).",
149 (unsigned)(sizeof(T) * 8), pos);
150 assert(num_bits == (sizeof(T) * 8), "Number of bits incorrect (%u), expected %u.",
151 num_bits, (unsigned)(sizeof(T) * 8));
152 const size_t byteoffset = pos / 8;
153 assert(byteoffset <= (_map_size - sizeof(T)),
154 "invalid byte offset (" SIZE_FORMAT "), map size is " SIZE_FORMAT ".", byteoffset, _map_size);
155 T* const pw = (T*)(_map[layer] + byteoffset);
156 *pw = v ? all_ones<T>::value : (T) 0;
157 }
158
159 // Set all bits in a region starting at pos to a value.
160 void set_bits_of_region(unsigned pos, unsigned num_bits, unsigned layer, bool v) {
161 assert(_map_size > 0, "not initialized");
162 assert(layer == 0 || layer == 1, "Invalid layer %d.", layer);
163 if (pos % 32 == 0 && num_bits == 32) {
164 set_bits_of_region_T<uint32_t>(pos, num_bits, layer, v);
165 } else if (pos % 64 == 0 && num_bits == 64) {
166 set_bits_of_region_T<uint64_t>(pos, num_bits, layer, v);
167 } else {
168 for (unsigned n = 0; n < num_bits; n ++) {
169 set_bit_at_position(pos + n, layer, v);
170 }
171 }
172 }
173
174 // Helper: sets all bits in a region [p, p+word_size).
175 void set_bits_of_region(MetaWord* p, size_t word_size, unsigned layer, bool v) {
176 assert(word_size % _smallest_chunk_word_size == 0,
177 "Region size " SIZE_FORMAT " not a multiple of smallest chunk size.", word_size);
178 const unsigned pos = get_bitpos_for_address(p);
179 const unsigned num_bits = (unsigned) (word_size / _smallest_chunk_word_size);
180 set_bits_of_region(pos, num_bits, layer, v);
181 }
182
183 // Helper: given an address, return the bit position representing that address.
184 unsigned get_bitpos_for_address(const MetaWord* p) const {
185 assert(_reference_address != NULL, "not initialized");
186 assert(p >= _reference_address && p < _reference_address + _word_size,
187 "Address %p out of range for occupancy map [%p..%p).",
188 p, _reference_address, _reference_address + _word_size);
189 assert(is_aligned(p, _smallest_chunk_word_size * sizeof(MetaWord)),
190 "Address not aligned (%p).", p);
191 const ptrdiff_t d = (p - _reference_address) / _smallest_chunk_word_size;
192 assert(d >= 0 && (size_t)d < _map_size * 8, "Sanity.");
193 return (unsigned) d;
194 }
195
196 public:
197
198 OccupancyMap(const MetaWord* reference_address, size_t word_size, size_t smallest_chunk_word_size);
199 ~OccupancyMap();
200
201 // Returns true if at address x a chunk is starting.
202 bool chunk_starts_at_address(MetaWord* p) const {
203 const unsigned pos = get_bitpos_for_address(p);
204 return get_bit_at_position(pos, layer_chunk_start_map);
205 }
206
207 void set_chunk_starts_at_address(MetaWord* p, bool v) {
208 const unsigned pos = get_bitpos_for_address(p);
209 set_bit_at_position(pos, layer_chunk_start_map, v);
210 }
211
212 // Removes all chunk-start-bits inside a region, typically as a
213 // result of a chunk merge.
214 void wipe_chunk_start_bits_in_region(MetaWord* p, size_t word_size) {
215 set_bits_of_region(p, word_size, layer_chunk_start_map, false);
216 }
217
218 // Returns true if there are life (in use) chunks in the region limited
219 // by [p, p+word_size).
220 bool is_region_in_use(MetaWord* p, size_t word_size) const {
221 return is_any_bit_set_in_region(p, word_size, layer_in_use_map);
222 }
223
224 // Marks the region starting at p with the size word_size as in use
225 // or free, depending on v.
226 void set_region_in_use(MetaWord* p, size_t word_size, bool v) {
227 set_bits_of_region(p, word_size, layer_in_use_map, v);
228 }
229
230 // Verify occupancy map for the address range [from, to).
231 // We need to tell it the address range, because the memory the
232 // occupancy map is covering may not be fully comitted yet.
233 DEBUG_ONLY(void verify(MetaWord* from, MetaWord* to);)
234
235 // Verify that a given chunk is correctly accounted for in the bitmap.
236 DEBUG_ONLY(void verify_for_chunk(Metachunk* chunk);)
237
238};
239
240} // namespace metaspace
241
242#endif // SHARE_MEMORY_METASPACE_OCCUPANCYMAP_HPP
243