1 | /*---------------------------------------------------------------------------- |
2 | Copyright (c) 2018, Microsoft Research, Daan Leijen |
3 | This is free software; you can redistribute it and/or modify it under the |
4 | terms of the MIT license. A copy of the license can be found in the file |
5 | "LICENSE" at the root of this distribution. |
6 | -----------------------------------------------------------------------------*/ |
7 | |
8 | /* ----------------------------------------------------------- |
9 | Definition of page queues for each block size |
10 | ----------------------------------------------------------- */ |
11 | |
12 | #ifndef MI_IN_PAGE_C |
13 | #error "this file should be included from 'page.c'" |
14 | #endif |
15 | |
16 | /* ----------------------------------------------------------- |
17 | Minimal alignment in machine words (i.e. `sizeof(void*)`) |
18 | ----------------------------------------------------------- */ |
19 | |
20 | #if (MI_MAX_ALIGN_SIZE > 4*MI_INTPTR_SIZE) |
21 | #error "define alignment for more than 4x word size for this platform" |
22 | #elif (MI_MAX_ALIGN_SIZE > 2*MI_INTPTR_SIZE) |
23 | #define MI_ALIGN4W // 4 machine words minimal alignment |
24 | #elif (MI_MAX_ALIGN_SIZE > MI_INTPTR_SIZE) |
25 | #define MI_ALIGN2W // 2 machine words minimal alignment |
26 | #else |
27 | // ok, default alignment is 1 word |
28 | #endif |
29 | |
30 | |
31 | /* ----------------------------------------------------------- |
32 | Queue query |
33 | ----------------------------------------------------------- */ |
34 | |
35 | |
36 | static inline bool mi_page_queue_is_huge(const mi_page_queue_t* pq) { |
37 | return (pq->block_size == (MI_LARGE_OBJ_SIZE_MAX+sizeof(uintptr_t))); |
38 | } |
39 | |
40 | static inline bool mi_page_queue_is_full(const mi_page_queue_t* pq) { |
41 | return (pq->block_size == (MI_LARGE_OBJ_SIZE_MAX+(2*sizeof(uintptr_t)))); |
42 | } |
43 | |
44 | static inline bool mi_page_queue_is_special(const mi_page_queue_t* pq) { |
45 | return (pq->block_size > MI_LARGE_OBJ_SIZE_MAX); |
46 | } |
47 | |
48 | /* ----------------------------------------------------------- |
49 | Bins |
50 | ----------------------------------------------------------- */ |
51 | |
52 | // Bit scan reverse: return the index of the highest bit. |
53 | static inline uint8_t mi_bsr32(uint32_t x); |
54 | |
55 | #if defined(_MSC_VER) |
56 | #include <intrin.h> |
57 | static inline uint8_t mi_bsr32(uint32_t x) { |
58 | uint32_t idx; |
59 | _BitScanReverse((DWORD*)&idx, x); |
60 | return (uint8_t)idx; |
61 | } |
62 | #elif defined(__GNUC__) || defined(__clang__) |
63 | static inline uint8_t mi_bsr32(uint32_t x) { |
64 | return (31 - __builtin_clz(x)); |
65 | } |
66 | #else |
67 | static inline uint8_t mi_bsr32(uint32_t x) { |
68 | // de Bruijn multiplication, see <http://supertech.csail.mit.edu/papers/debruijn.pdf> |
69 | static const uint8_t debruijn[32] = { |
70 | 31, 0, 22, 1, 28, 23, 18, 2, 29, 26, 24, 10, 19, 7, 3, 12, |
71 | 30, 21, 27, 17, 25, 9, 6, 11, 20, 16, 8, 5, 15, 4, 14, 13, |
72 | }; |
73 | x |= x >> 1; |
74 | x |= x >> 2; |
75 | x |= x >> 4; |
76 | x |= x >> 8; |
77 | x |= x >> 16; |
78 | x++; |
79 | return debruijn[(x*0x076be629) >> 27]; |
80 | } |
81 | #endif |
82 | |
83 | // Bit scan reverse: return the index of the highest bit. |
84 | uint8_t _mi_bsr(uintptr_t x) { |
85 | if (x == 0) return 0; |
86 | #if MI_INTPTR_SIZE==8 |
87 | uint32_t hi = (x >> 32); |
88 | return (hi == 0 ? mi_bsr32((uint32_t)x) : 32 + mi_bsr32(hi)); |
89 | #elif MI_INTPTR_SIZE==4 |
90 | return mi_bsr32(x); |
91 | #else |
92 | # error "define bsr for non-32 or 64-bit platforms" |
93 | #endif |
94 | } |
95 | |
96 | // Return the bin for a given field size. |
97 | // Returns MI_BIN_HUGE if the size is too large. |
98 | // We use `wsize` for the size in "machine word sizes", |
99 | // i.e. byte size == `wsize*sizeof(void*)`. |
100 | extern inline uint8_t _mi_bin(size_t size) { |
101 | size_t wsize = _mi_wsize_from_size(size); |
102 | uint8_t bin; |
103 | if (wsize <= 1) { |
104 | bin = 1; |
105 | } |
106 | #if defined(MI_ALIGN4W) |
107 | else if (wsize <= 4) { |
108 | bin = (uint8_t)((wsize+1)&~1); // round to double word sizes |
109 | } |
110 | #elif defined(MI_ALIGN2W) |
111 | else if (wsize <= 8) { |
112 | bin = (uint8_t)((wsize+1)&~1); // round to double word sizes |
113 | } |
114 | #else |
115 | else if (wsize <= 8) { |
116 | bin = (uint8_t)wsize; |
117 | } |
118 | #endif |
119 | else if (wsize > MI_LARGE_OBJ_WSIZE_MAX) { |
120 | bin = MI_BIN_HUGE; |
121 | } |
122 | else { |
123 | #if defined(MI_ALIGN4W) |
124 | if (wsize <= 16) { wsize = (wsize+3)&~3; } // round to 4x word sizes |
125 | #endif |
126 | wsize--; |
127 | // find the highest bit |
128 | uint8_t b = mi_bsr32((uint32_t)wsize); |
129 | // and use the top 3 bits to determine the bin (~12.5% worst internal fragmentation). |
130 | // - adjust with 3 because we use do not round the first 8 sizes |
131 | // which each get an exact bin |
132 | bin = ((b << 2) + (uint8_t)((wsize >> (b - 2)) & 0x03)) - 3; |
133 | mi_assert_internal(bin < MI_BIN_HUGE); |
134 | } |
135 | mi_assert_internal(bin > 0 && bin <= MI_BIN_HUGE); |
136 | return bin; |
137 | } |
138 | |
139 | |
140 | |
141 | /* ----------------------------------------------------------- |
142 | Queue of pages with free blocks |
143 | ----------------------------------------------------------- */ |
144 | |
145 | size_t _mi_bin_size(uint8_t bin) { |
146 | return _mi_heap_empty.pages[bin].block_size; |
147 | } |
148 | |
149 | // Good size for allocation |
150 | size_t mi_good_size(size_t size) mi_attr_noexcept { |
151 | if (size <= MI_LARGE_OBJ_SIZE_MAX) { |
152 | return _mi_bin_size(_mi_bin(size)); |
153 | } |
154 | else { |
155 | return _mi_align_up(size,_mi_os_page_size()); |
156 | } |
157 | } |
158 | |
159 | #if (MI_DEBUG>1) |
160 | static bool mi_page_queue_contains(mi_page_queue_t* queue, const mi_page_t* page) { |
161 | mi_assert_internal(page != NULL); |
162 | mi_page_t* list = queue->first; |
163 | while (list != NULL) { |
164 | mi_assert_internal(list->next == NULL || list->next->prev == list); |
165 | mi_assert_internal(list->prev == NULL || list->prev->next == list); |
166 | if (list == page) break; |
167 | list = list->next; |
168 | } |
169 | return (list == page); |
170 | } |
171 | |
172 | #endif |
173 | |
174 | #if (MI_DEBUG>1) |
175 | static bool mi_heap_contains_queue(const mi_heap_t* heap, const mi_page_queue_t* pq) { |
176 | return (pq >= &heap->pages[0] && pq <= &heap->pages[MI_BIN_FULL]); |
177 | } |
178 | #endif |
179 | |
180 | static mi_page_queue_t* mi_page_queue_of(const mi_page_t* page) { |
181 | uint8_t bin = (mi_page_is_in_full(page) ? MI_BIN_FULL : _mi_bin(page->block_size)); |
182 | mi_heap_t* heap = page->heap; |
183 | mi_assert_internal(heap != NULL && bin <= MI_BIN_FULL); |
184 | mi_page_queue_t* pq = &heap->pages[bin]; |
185 | mi_assert_internal(bin >= MI_BIN_HUGE || page->block_size == pq->block_size); |
186 | mi_assert_expensive(mi_page_queue_contains(pq, page)); |
187 | return pq; |
188 | } |
189 | |
190 | static mi_page_queue_t* mi_heap_page_queue_of(mi_heap_t* heap, const mi_page_t* page) { |
191 | uint8_t bin = (mi_page_is_in_full(page) ? MI_BIN_FULL : _mi_bin(page->block_size)); |
192 | mi_assert_internal(bin <= MI_BIN_FULL); |
193 | mi_page_queue_t* pq = &heap->pages[bin]; |
194 | mi_assert_internal(mi_page_is_in_full(page) || page->block_size == pq->block_size); |
195 | return pq; |
196 | } |
197 | |
198 | // The current small page array is for efficiency and for each |
199 | // small size (up to 256) it points directly to the page for that |
200 | // size without having to compute the bin. This means when the |
201 | // current free page queue is updated for a small bin, we need to update a |
202 | // range of entries in `_mi_page_small_free`. |
203 | static inline void mi_heap_queue_first_update(mi_heap_t* heap, const mi_page_queue_t* pq) { |
204 | mi_assert_internal(mi_heap_contains_queue(heap,pq)); |
205 | size_t size = pq->block_size; |
206 | if (size > MI_SMALL_SIZE_MAX) return; |
207 | |
208 | mi_page_t* page = pq->first; |
209 | if (pq->first == NULL) page = (mi_page_t*)&_mi_page_empty; |
210 | |
211 | // find index in the right direct page array |
212 | size_t start; |
213 | size_t idx = _mi_wsize_from_size(size); |
214 | mi_page_t** pages_free = heap->pages_free_direct; |
215 | |
216 | if (pages_free[idx] == page) return; // already set |
217 | |
218 | // find start slot |
219 | if (idx<=1) { |
220 | start = 0; |
221 | } |
222 | else { |
223 | // find previous size; due to minimal alignment upto 3 previous bins may need to be skipped |
224 | uint8_t bin = _mi_bin(size); |
225 | const mi_page_queue_t* prev = pq - 1; |
226 | while( bin == _mi_bin(prev->block_size) && prev > &heap->pages[0]) { |
227 | prev--; |
228 | } |
229 | start = 1 + _mi_wsize_from_size(prev->block_size); |
230 | if (start > idx) start = idx; |
231 | } |
232 | |
233 | // set size range to the right page |
234 | mi_assert(start <= idx); |
235 | for (size_t sz = start; sz <= idx; sz++) { |
236 | pages_free[sz] = page; |
237 | } |
238 | } |
239 | |
240 | /* |
241 | static bool mi_page_queue_is_empty(mi_page_queue_t* queue) { |
242 | return (queue->first == NULL); |
243 | } |
244 | */ |
245 | |
246 | static void mi_page_queue_remove(mi_page_queue_t* queue, mi_page_t* page) { |
247 | mi_assert_internal(page != NULL); |
248 | mi_assert_expensive(mi_page_queue_contains(queue, page)); |
249 | mi_assert_internal(page->block_size == queue->block_size || (page->block_size > MI_LARGE_OBJ_SIZE_MAX && mi_page_queue_is_huge(queue)) || (mi_page_is_in_full(page) && mi_page_queue_is_full(queue))); |
250 | if (page->prev != NULL) page->prev->next = page->next; |
251 | if (page->next != NULL) page->next->prev = page->prev; |
252 | if (page == queue->last) queue->last = page->prev; |
253 | if (page == queue->first) { |
254 | queue->first = page->next; |
255 | // update first |
256 | mi_heap_t* heap = page->heap; |
257 | mi_assert_internal(mi_heap_contains_queue(heap, queue)); |
258 | mi_heap_queue_first_update(heap,queue); |
259 | } |
260 | page->heap->page_count--; |
261 | page->next = NULL; |
262 | page->prev = NULL; |
263 | mi_atomic_write_ptr(mi_atomic_cast(void*, &page->heap), NULL); |
264 | mi_page_set_in_full(page,false); |
265 | } |
266 | |
267 | |
268 | static void mi_page_queue_push(mi_heap_t* heap, mi_page_queue_t* queue, mi_page_t* page) { |
269 | mi_assert_internal(page->heap == NULL); |
270 | mi_assert_internal(!mi_page_queue_contains(queue, page)); |
271 | mi_assert_internal(_mi_page_segment(page)->page_kind != MI_PAGE_HUGE); |
272 | mi_assert_internal(page->block_size == queue->block_size || |
273 | (page->block_size > MI_LARGE_OBJ_SIZE_MAX && mi_page_queue_is_huge(queue)) || |
274 | (mi_page_is_in_full(page) && mi_page_queue_is_full(queue))); |
275 | |
276 | mi_page_set_in_full(page, mi_page_queue_is_full(queue)); |
277 | mi_atomic_write_ptr(mi_atomic_cast(void*, &page->heap), heap); |
278 | page->next = queue->first; |
279 | page->prev = NULL; |
280 | if (queue->first != NULL) { |
281 | mi_assert_internal(queue->first->prev == NULL); |
282 | queue->first->prev = page; |
283 | queue->first = page; |
284 | } |
285 | else { |
286 | queue->first = queue->last = page; |
287 | } |
288 | |
289 | // update direct |
290 | mi_heap_queue_first_update(heap, queue); |
291 | heap->page_count++; |
292 | } |
293 | |
294 | |
295 | static void mi_page_queue_enqueue_from(mi_page_queue_t* to, mi_page_queue_t* from, mi_page_t* page) { |
296 | mi_assert_internal(page != NULL); |
297 | mi_assert_expensive(mi_page_queue_contains(from, page)); |
298 | mi_assert_expensive(!mi_page_queue_contains(to, page)); |
299 | mi_assert_internal((page->block_size == to->block_size && page->block_size == from->block_size) || |
300 | (page->block_size == to->block_size && mi_page_queue_is_full(from)) || |
301 | (page->block_size == from->block_size && mi_page_queue_is_full(to)) || |
302 | (page->block_size > MI_LARGE_OBJ_SIZE_MAX && mi_page_queue_is_huge(to)) || |
303 | (page->block_size > MI_LARGE_OBJ_SIZE_MAX && mi_page_queue_is_full(to))); |
304 | |
305 | if (page->prev != NULL) page->prev->next = page->next; |
306 | if (page->next != NULL) page->next->prev = page->prev; |
307 | if (page == from->last) from->last = page->prev; |
308 | if (page == from->first) { |
309 | from->first = page->next; |
310 | // update first |
311 | mi_heap_t* heap = page->heap; |
312 | mi_assert_internal(mi_heap_contains_queue(heap, from)); |
313 | mi_heap_queue_first_update(heap, from); |
314 | } |
315 | |
316 | page->prev = to->last; |
317 | page->next = NULL; |
318 | if (to->last != NULL) { |
319 | mi_assert_internal(page->heap == to->last->heap); |
320 | to->last->next = page; |
321 | to->last = page; |
322 | } |
323 | else { |
324 | to->first = page; |
325 | to->last = page; |
326 | mi_heap_queue_first_update(page->heap, to); |
327 | } |
328 | |
329 | mi_page_set_in_full(page, mi_page_queue_is_full(to)); |
330 | } |
331 | |
332 | size_t _mi_page_queue_append(mi_heap_t* heap, mi_page_queue_t* pq, mi_page_queue_t* append) { |
333 | mi_assert_internal(mi_heap_contains_queue(heap,pq)); |
334 | mi_assert_internal(pq->block_size == append->block_size); |
335 | |
336 | if (append->first==NULL) return 0; |
337 | |
338 | // set append pages to new heap and count |
339 | size_t count = 0; |
340 | for (mi_page_t* page = append->first; page != NULL; page = page->next) { |
341 | mi_atomic_write_ptr(mi_atomic_cast(void*, &page->heap), heap); |
342 | count++; |
343 | } |
344 | |
345 | if (pq->last==NULL) { |
346 | // take over afresh |
347 | mi_assert_internal(pq->first==NULL); |
348 | pq->first = append->first; |
349 | pq->last = append->last; |
350 | mi_heap_queue_first_update(heap, pq); |
351 | } |
352 | else { |
353 | // append to end |
354 | mi_assert_internal(pq->last!=NULL); |
355 | mi_assert_internal(append->first!=NULL); |
356 | pq->last->next = append->first; |
357 | append->first->prev = pq->last; |
358 | pq->last = append->last; |
359 | } |
360 | return count; |
361 | } |
362 | |