1/*----------------------------------------------------------------------------
2Copyright (c) 2018, Microsoft Research, Daan Leijen
3This is free software; you can redistribute it and/or modify it under the
4terms 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
36static 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
40static 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
44static 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.
53static inline uint8_t mi_bsr32(uint32_t x);
54
55#if defined(_MSC_VER)
56#include <intrin.h>
57static 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__)
63static inline uint8_t mi_bsr32(uint32_t x) {
64 return (31 - __builtin_clz(x));
65}
66#else
67static 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.
84uint8_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*)`.
100extern 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
145size_t _mi_bin_size(uint8_t bin) {
146 return _mi_heap_empty.pages[bin].block_size;
147}
148
149// Good size for allocation
150size_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)
160static 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)
175static 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
180static 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
190static 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`.
203static 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/*
241static bool mi_page_queue_is_empty(mi_page_queue_t* queue) {
242 return (queue->first == NULL);
243}
244*/
245
246static 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
268static 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
295static 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
332size_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