11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
23 * questions.
24 *
25 */
26
27 #ifndef SHARE_MEMORY_METASPACE_BINLIST_HPP
28 #define SHARE_MEMORY_METASPACE_BINLIST_HPP
29
30 #include "memory/metaspace/counters.hpp"
31 #include "memory/metaspace/metaspaceCommon.hpp"
32 #include "utilities/align.hpp"
33 #include "utilities/debug.hpp"
34 #include "utilities/globalDefinitions.hpp"
35
36 namespace metaspace {
37
38 // BinList is a data structure to manage small to very small memory blocks
39 // (only a few words). It is used to manage deallocated blocks - see
40 // class FreeBlocks.
41
42 // Memory blocks are kept in a vector of linked lists of equi-sized blocks:
43 //
44 // wordsize
45 //
46 // +---+ +---+ +---+ +---+
47 // 1 | |-->| |-->| |-...->| |
48 // +---+ +---+ +---+ +---+
49 //
50 // +----+ +----+ +----+ +----+
51 // 2 | |-->| |-->| |-...->| |
52 // +----+ +----+ +----+ +----+
53 //
54 // +-----+ +-----+ +-----+ +-----+
55 // 3 | |-->| |-->| |-...->| |
56 // +-----+ +-----+ +-----+ +-----+
57 // .
58 // .
59 // .
60 //
126 static const uintptr_t canary = 0xFFEEFFEE;
127 static void write_canary(MetaWord* p, size_t word_size) {
128 if (word_size > 1) { // 1-word-sized blocks have no space for a canary
129 ((uintptr_t*)p)[word_size - 1] = canary;
130 }
131 }
132 static bool check_canary(const Block* b, size_t word_size) {
133 return word_size == 1 || // 1-word-sized blocks have no space for a canary
134 ((const uintptr_t*)b)[word_size - 1] == canary;
135 }
136 #endif
137
138 public:
139
140 BinListImpl() {
141 for (int i = 0; i < num_lists; i++) {
142 _blocks[i] = nullptr;
143 }
144 }
145
146 void add_block(MetaWord* p, size_t word_size) {
147 assert(word_size >= MinWordSize &&
148 word_size <= MaxWordSize, "bad block size");
149 DEBUG_ONLY(write_canary(p, word_size);)
150 const int index = index_for_word_size(word_size);
151 Block* old_head = _blocks[index];
152 Block* new_head = new (p) Block(old_head);
153 _blocks[index] = new_head;
154 _counter.add(word_size);
155 }
156
157 // Given a word_size, searches and returns a block of at least that size.
158 // Block may be larger. Real block size is returned in *p_real_word_size.
159 MetaWord* remove_block(size_t word_size, size_t* p_real_word_size) {
160 assert(word_size >= MinWordSize &&
161 word_size <= MaxWordSize, "bad block size " SIZE_FORMAT ".", word_size);
162 int index = index_for_word_size(word_size);
163 index = index_for_next_non_empty_list(index);
164 if (index != -1) {
165 Block* b = _blocks[index];
166 const size_t real_word_size = word_size_for_index(index);
167 assert(b != nullptr, "Sanity");
168 assert(check_canary(b, real_word_size),
169 "bad block in list[%d] (" BLOCK_FORMAT ")", index, BLOCK_FORMAT_ARGS(b, real_word_size));
170 _blocks[index] = b->_next;
171 _counter.sub(real_word_size);
172 *p_real_word_size = real_word_size;
173 return (MetaWord*)b;
174 } else {
175 *p_real_word_size = 0;
176 return nullptr;
177 }
178 }
179
180 // Returns number of blocks in this structure
181 unsigned count() const { return _counter.count(); }
182
183 // Returns total size, in words, of all elements.
184 size_t total_size() const { return _counter.total_size(); }
185
186 bool is_empty() const { return count() == 0; }
187
188 #ifdef ASSERT
189 void verify() const {
190 MemRangeCounter local_counter;
191 for (int i = 0; i < num_lists; i++) {
192 const size_t s = word_size_for_index(i);
193 int pos = 0;
194 for (Block* b = _blocks[i]; b != nullptr; b = b->_next, pos++) {
195 assert(check_canary(b, s), "");
196 local_counter.add(s);
197 }
198 }
199 local_counter.check(_counter);
200 }
201 #endif // ASSERT
202
203 };
204
205 typedef BinListImpl<32> BinList32;
206
207 } // namespace metaspace
208
209 #endif // SHARE_MEMORY_METASPACE_BINLIST_HPP
|
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
23 * questions.
24 *
25 */
26
27 #ifndef SHARE_MEMORY_METASPACE_BINLIST_HPP
28 #define SHARE_MEMORY_METASPACE_BINLIST_HPP
29
30 #include "memory/metaspace/counters.hpp"
31 #include "memory/metaspace/metablock.hpp"
32 #include "memory/metaspace/metaspaceCommon.hpp"
33 #include "utilities/align.hpp"
34 #include "utilities/debug.hpp"
35 #include "utilities/globalDefinitions.hpp"
36
37 namespace metaspace {
38
39 // BinList is a data structure to manage small to very small memory blocks
40 // (only a few words). It is used to manage deallocated small blocks.
41
42 // Memory blocks are kept in a vector of linked lists of equi-sized blocks:
43 //
44 // wordsize
45 //
46 // +---+ +---+ +---+ +---+
47 // 1 | |-->| |-->| |-...->| |
48 // +---+ +---+ +---+ +---+
49 //
50 // +----+ +----+ +----+ +----+
51 // 2 | |-->| |-->| |-...->| |
52 // +----+ +----+ +----+ +----+
53 //
54 // +-----+ +-----+ +-----+ +-----+
55 // 3 | |-->| |-->| |-...->| |
56 // +-----+ +-----+ +-----+ +-----+
57 // .
58 // .
59 // .
60 //
126 static const uintptr_t canary = 0xFFEEFFEE;
127 static void write_canary(MetaWord* p, size_t word_size) {
128 if (word_size > 1) { // 1-word-sized blocks have no space for a canary
129 ((uintptr_t*)p)[word_size - 1] = canary;
130 }
131 }
132 static bool check_canary(const Block* b, size_t word_size) {
133 return word_size == 1 || // 1-word-sized blocks have no space for a canary
134 ((const uintptr_t*)b)[word_size - 1] == canary;
135 }
136 #endif
137
138 public:
139
140 BinListImpl() {
141 for (int i = 0; i < num_lists; i++) {
142 _blocks[i] = nullptr;
143 }
144 }
145
146 void add_block(MetaBlock mb) {
147 assert(!mb.is_empty(), "Don't add empty blocks");
148 const size_t word_size = mb.word_size();
149 MetaWord* const p = mb.base();
150 assert(word_size >= MinWordSize &&
151 word_size <= MaxWordSize, "bad block size");
152 DEBUG_ONLY(write_canary(p, word_size);)
153 const int index = index_for_word_size(word_size);
154 Block* old_head = _blocks[index];
155 Block* new_head = new (p) Block(old_head);
156 _blocks[index] = new_head;
157 _counter.add(word_size);
158 }
159
160 // Given a word_size, searches and returns a block of at least that size.
161 // Block may be larger.
162 MetaBlock remove_block(size_t word_size) {
163 assert(word_size >= MinWordSize &&
164 word_size <= MaxWordSize, "bad block size " SIZE_FORMAT ".", word_size);
165 MetaBlock result;
166 int index = index_for_word_size(word_size);
167 index = index_for_next_non_empty_list(index);
168 if (index != -1) {
169 Block* b = _blocks[index];
170 const size_t real_word_size = word_size_for_index(index);
171 assert(b != nullptr, "Sanity");
172 assert(check_canary(b, real_word_size),
173 "bad block in list[%d] (" BLOCK_FORMAT ")", index, BLOCK_FORMAT_ARGS(b, real_word_size));
174 _blocks[index] = b->_next;
175 _counter.sub(real_word_size);
176 result = MetaBlock((MetaWord*)b, real_word_size);
177 }
178 return result;
179 }
180
181 // Returns number of blocks in this structure
182 unsigned count() const { return _counter.count(); }
183
184 // Returns total size, in words, of all elements.
185 size_t total_size() const { return _counter.total_size(); }
186
187 bool is_empty() const { return count() == 0; }
188
189 #ifdef ASSERT
190 void verify() const {
191 MemRangeCounter local_counter;
192 for (int i = 0; i < num_lists; i++) {
193 const size_t s = word_size_for_index(i);
194 int pos = 0;
195 Block* b_last = nullptr; // catch simple circularities
196 for (Block* b = _blocks[i]; b != nullptr; b = b->_next, pos++) {
197 assert(check_canary(b, s), "");
198 assert(b != b_last, "Circle");
199 local_counter.add(s);
200 b_last = b;
201 }
202 if (UseNewCode)printf("\n");
203 }
204 local_counter.check(_counter);
205 }
206 #endif // ASSERT
207
208 };
209
210 typedef BinListImpl<32> BinList32;
211
212 } // namespace metaspace
213
214 #endif // SHARE_MEMORY_METASPACE_BINLIST_HPP
|