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 34 namespace metaspace { 35 36 class Metachunk; 37 38 // Helper for Occupancy Bitmap. A type trait to give an all-bits-are-one-unsigned constant. 39 template <typename T> struct all_ones { static const T value; }; 40 template <> struct all_ones <uint64_t> { static const uint64_t value = 0xFFFFFFFFFFFFFFFFULL; }; 41 template <> 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). 49 class 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