10 #if defined(__cplusplus)
\r
11 #define tlsf_decl inline
\r
13 #define tlsf_decl static
\r
17 ** Architecture-specific bit manipulation routines.
\r
19 ** TLSF achieves O(1) cost for malloc and free operations by limiting
\r
20 ** the search for a free block to a free list of guaranteed size
\r
21 ** adequate to fulfill the request, combined with efficient free list
\r
22 ** queries using bitmasks and architecture-specific bit-manipulation
\r
25 ** Most modern processors provide instructions to count leading zeroes
\r
26 ** in a word, find the lowest and highest set bit, etc. These
\r
27 ** specific implementations will be used when available, falling back
\r
28 ** to a reasonably efficient generic implementation.
\r
30 ** NOTE: TLSF spec relies on ffs/fls returning value 0..31.
\r
31 ** ffs/fls return 1-32 by default, returning 0 for error.
\r
35 ** Detect whether or not we are building for a 32- or 64-bit (LP/LLP)
\r
36 ** architecture. There is no reliable portable method at compile-time.
\r
38 #if defined (__alpha__) || defined (__ia64__) || defined (__x86_64__) \
\r
39 || defined (_WIN64) || defined (__LP64__) || defined (__LLP64__)
\r
44 ** gcc 3.4 and above have builtin support, specialized for architecture.
\r
45 ** Some compilers masquerade as gcc; patchlevel test filters them out.
\r
47 #if defined (__GNUC__) && (__GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)) \
\r
48 && defined (__GNUC_PATCHLEVEL__)
\r
50 #if defined (__SNC__)
\r
51 /* SNC for Playstation 3. */
\r
53 tlsf_decl int tlsf_ffs(unsigned int word)
\r
55 const unsigned int reverse = word & (~word + 1);
\r
56 const int bit = 32 - __builtin_clz(reverse);
\r
62 tlsf_decl int tlsf_ffs(unsigned int word)
\r
64 return __builtin_ffs(word) - 1;
\r
69 tlsf_decl int tlsf_fls(unsigned int word)
\r
71 const int bit = word ? 32 - __builtin_clz(word) : 0;
\r
75 #elif defined (_MSC_VER) && (_MSC_VER >= 1400) && (defined (_M_IX86) || defined (_M_X64))
\r
76 /* Microsoft Visual C++ support on x86/X64 architectures. */
\r
80 #pragma intrinsic(_BitScanReverse)
\r
81 #pragma intrinsic(_BitScanForward)
\r
83 tlsf_decl int tlsf_fls(unsigned int word)
\r
85 unsigned long index;
\r
86 return _BitScanReverse(&index, word) ? index : -1;
\r
89 tlsf_decl int tlsf_ffs(unsigned int word)
\r
91 unsigned long index;
\r
92 return _BitScanForward(&index, word) ? index : -1;
\r
95 #elif defined (_MSC_VER) && defined (_M_PPC)
\r
96 /* Microsoft Visual C++ support on PowerPC architectures. */
\r
98 #include <ppcintrinsics.h>
\r
100 tlsf_decl int tlsf_fls(unsigned int word)
\r
102 const int bit = 32 - _CountLeadingZeros(word);
\r
106 tlsf_decl int tlsf_ffs(unsigned int word)
\r
108 const unsigned int reverse = word & (~word + 1);
\r
109 const int bit = 32 - _CountLeadingZeros(reverse);
\r
113 #elif defined (__ARMCC_VERSION)
\r
114 /* RealView Compilation Tools for ARM */
\r
116 tlsf_decl int tlsf_ffs(unsigned int word)
\r
118 const unsigned int reverse = word & (~word + 1);
\r
119 const int bit = 32 - __clz(reverse);
\r
123 tlsf_decl int tlsf_fls(unsigned int word)
\r
125 const int bit = word ? 32 - __clz(word) : 0;
\r
129 #elif defined (__ghs__)
\r
130 /* Green Hills support for PowerPC */
\r
132 #include <ppc_ghs.h>
\r
134 tlsf_decl int tlsf_ffs(unsigned int word)
\r
136 const unsigned int reverse = word & (~word + 1);
\r
137 const int bit = 32 - __CLZ32(reverse);
\r
141 tlsf_decl int tlsf_fls(unsigned int word)
\r
143 const int bit = word ? 32 - __CLZ32(word) : 0;
\r
148 /* Fall back to generic implementation. */
\r
150 tlsf_decl int tlsf_fls_generic(unsigned int word)
\r
154 if (!word) bit -= 1;
\r
155 if (!(word & 0xffff0000)) { word <<= 16; bit -= 16; }
\r
156 if (!(word & 0xff000000)) { word <<= 8; bit -= 8; }
\r
157 if (!(word & 0xf0000000)) { word <<= 4; bit -= 4; }
\r
158 if (!(word & 0xc0000000)) { word <<= 2; bit -= 2; }
\r
159 if (!(word & 0x80000000)) { word <<= 1; bit -= 1; }
\r
164 /* Implement ffs in terms of fls. */
\r
165 tlsf_decl int tlsf_ffs(unsigned int word)
\r
167 return tlsf_fls_generic(word & (~word + 1)) - 1;
\r
170 tlsf_decl int tlsf_fls(unsigned int word)
\r
172 return tlsf_fls_generic(word) - 1;
\r
177 /* Possibly 64-bit version of tlsf_fls. */
\r
178 #if defined (TLSF_64BIT)
\r
179 tlsf_decl int tlsf_fls_sizet(size_t size)
\r
181 int high = (int)(size >> 32);
\r
185 bits = 32 + tlsf_fls(high);
\r
189 bits = tlsf_fls((int)size & 0xffffffff);
\r
195 #define tlsf_fls_sizet tlsf_fls
\r
204 /* Public constants: may be modified. */
\r
207 /* log2 of number of linear subdivisions of block sizes. Larger
\r
208 ** values require more memory in the control structure. Values of
\r
209 ** 4 or 5 are typical.
\r
211 SL_INDEX_COUNT_LOG2 = 5,
\r
214 /* Private constants: do not modify. */
\r
217 #if defined (TLSF_64BIT)
\r
218 /* All allocation sizes and addresses are aligned to 8 bytes. */
\r
219 ALIGN_SIZE_LOG2 = 3,
\r
221 /* All allocation sizes and addresses are aligned to 4 bytes. */
\r
222 ALIGN_SIZE_LOG2 = 2,
\r
224 ALIGN_SIZE = (1 << ALIGN_SIZE_LOG2),
\r
227 ** We support allocations of sizes up to (1 << FL_INDEX_MAX) bits.
\r
228 ** However, because we linearly subdivide the second-level lists, and
\r
229 ** our minimum size granularity is 4 bytes, it doesn't make sense to
\r
230 ** create first-level lists for sizes smaller than SL_INDEX_COUNT * 4,
\r
231 ** or (1 << (SL_INDEX_COUNT_LOG2 + 2)) bytes, as there we will be
\r
232 ** trying to split size ranges into more slots than we have available.
\r
233 ** Instead, we calculate the minimum threshold size, and place all
\r
234 ** blocks below that size into the 0th first-level list.
\r
237 #if defined (TLSF_64BIT)
\r
239 ** TODO: We can increase this to support larger sizes, at the expense
\r
240 ** of more overhead in the TLSF structure.
\r
246 SL_INDEX_COUNT = (1 << SL_INDEX_COUNT_LOG2),
\r
247 FL_INDEX_SHIFT = (SL_INDEX_COUNT_LOG2 + ALIGN_SIZE_LOG2),
\r
248 FL_INDEX_COUNT = (FL_INDEX_MAX - FL_INDEX_SHIFT + 1),
\r
250 SMALL_BLOCK_SIZE = (1 << FL_INDEX_SHIFT),
\r
254 ** Cast and min/max macros.
\r
257 #define tlsf_cast(t, exp) ((t) (exp))
\r
258 #define tlsf_min(a, b) ((a) < (b) ? (a) : (b))
\r
259 #define tlsf_max(a, b) ((a) > (b) ? (a) : (b))
\r
262 ** Set assert macro, if it has not been provided by the user.
\r
264 #if !defined (tlsf_assert)
\r
265 #define tlsf_assert assert
\r
269 ** Static assertion mechanism.
\r
272 #define _tlsf_glue2(x, y) x ## y
\r
273 #define _tlsf_glue(x, y) _tlsf_glue2(x, y)
\r
274 #define tlsf_static_assert(exp) \
\r
275 typedef char _tlsf_glue(static_assert, __LINE__) [(exp) ? 1 : -1]
\r
277 /* This code has been tested on 32- and 64-bit (LP/LLP) architectures. */
\r
278 tlsf_static_assert(sizeof(int) * CHAR_BIT == 32);
\r
279 tlsf_static_assert(sizeof(size_t) * CHAR_BIT >= 32);
\r
280 tlsf_static_assert(sizeof(size_t) * CHAR_BIT <= 64);
\r
282 /* SL_INDEX_COUNT must be <= number of bits in sl_bitmap's storage type. */
\r
283 tlsf_static_assert(sizeof(unsigned int) * CHAR_BIT >= SL_INDEX_COUNT);
\r
285 /* Ensure we've properly tuned our sizes. */
\r
286 tlsf_static_assert(ALIGN_SIZE == SMALL_BLOCK_SIZE / SL_INDEX_COUNT);
\r
289 ** Data structures and associated constants.
\r
293 ** Block header structure.
\r
295 ** There are several implementation subtleties involved:
\r
296 ** - The prev_phys_block field is only valid if the previous block is free.
\r
297 ** - The prev_phys_block field is actually stored at the end of the
\r
298 ** previous block. It appears at the beginning of this structure only to
\r
299 ** simplify the implementation.
\r
300 ** - The next_free / prev_free fields are only valid if the block is free.
\r
302 typedef struct block_header_t
\r
304 /* Points to the previous physical block. */
\r
305 struct block_header_t* prev_phys_block;
\r
307 /* The size of this block, excluding the block header. */
\r
310 /* Next and previous free blocks. */
\r
311 struct block_header_t* next_free;
\r
312 struct block_header_t* prev_free;
\r
316 ** Since block sizes are always at least a multiple of 4, the two least
\r
317 ** significant bits of the size field are used to store the block status:
\r
318 ** - bit 0: whether block is busy or free
\r
319 ** - bit 1: whether previous block is busy or free
\r
321 static const size_t block_header_free_bit = 1 << 0;
\r
322 static const size_t block_header_prev_free_bit = 1 << 1;
\r
325 ** The size of the block header exposed to used blocks is the size field.
\r
326 ** The prev_phys_block field is stored *inside* the previous free block.
\r
328 static const size_t block_header_overhead = sizeof(size_t);
\r
330 /* User data starts directly after the size field in a used block. */
\r
331 static const size_t block_start_offset =
\r
332 offsetof(block_header_t, size) + sizeof(size_t);
\r
335 ** A free block must be large enough to store its header minus the size of
\r
336 ** the prev_phys_block field, and no larger than the number of addressable
\r
337 ** bits for FL_INDEX.
\r
339 static const size_t block_size_min =
\r
340 sizeof(block_header_t) - sizeof(block_header_t*);
\r
341 static const size_t block_size_max = tlsf_cast(size_t, 1) << FL_INDEX_MAX;
\r
344 /* The TLSF control structure. */
\r
345 typedef struct control_t
\r
347 /* Empty lists point at this block to indicate they are free. */
\r
348 block_header_t block_null;
\r
350 /* Bitmaps for free lists. */
\r
351 unsigned int fl_bitmap;
\r
352 unsigned int sl_bitmap[FL_INDEX_COUNT];
\r
354 /* Head of free lists. */
\r
355 block_header_t* blocks[FL_INDEX_COUNT][SL_INDEX_COUNT];
\r
358 /* A type used for casting when doing pointer arithmetic. */
\r
359 typedef ptrdiff_t tlsfptr_t;
\r
362 ** block_header_t member functions.
\r
365 static size_t block_size(const block_header_t* block)
\r
367 return block->size & ~(block_header_free_bit | block_header_prev_free_bit);
\r
370 static void block_set_size(block_header_t* block, size_t size)
\r
372 const size_t oldsize = block->size;
\r
373 block->size = size | (oldsize & (block_header_free_bit | block_header_prev_free_bit));
\r
376 static int block_is_last(const block_header_t* block)
\r
378 return block_size(block) == 0;
\r
381 static int block_is_free(const block_header_t* block)
\r
383 return tlsf_cast(int, block->size & block_header_free_bit);
\r
386 static void block_set_free(block_header_t* block)
\r
388 block->size |= block_header_free_bit;
\r
391 static void block_set_used(block_header_t* block)
\r
393 block->size &= ~block_header_free_bit;
\r
396 static int block_is_prev_free(const block_header_t* block)
\r
398 return tlsf_cast(int, block->size & block_header_prev_free_bit);
\r
401 static void block_set_prev_free(block_header_t* block)
\r
403 block->size |= block_header_prev_free_bit;
\r
406 static void block_set_prev_used(block_header_t* block)
\r
408 block->size &= ~block_header_prev_free_bit;
\r
411 static block_header_t* block_from_ptr(const void* ptr)
\r
413 return tlsf_cast(block_header_t*,
\r
414 tlsf_cast(unsigned char*, ptr) - block_start_offset);
\r
417 static void* block_to_ptr(const block_header_t* block)
\r
419 return tlsf_cast(void*,
\r
420 tlsf_cast(unsigned char*, block) + block_start_offset);
\r
423 /* Return location of next block after block of given size. */
\r
424 static block_header_t* offset_to_block(const void* ptr, size_t size)
\r
426 return tlsf_cast(block_header_t*, tlsf_cast(tlsfptr_t, ptr) + size);
\r
429 /* Return location of previous block. */
\r
430 static block_header_t* block_prev(const block_header_t* block)
\r
432 tlsf_assert(block_is_prev_free(block) && "previous block must be free");
\r
433 return block->prev_phys_block;
\r
436 /* Return location of next existing block. */
\r
437 static block_header_t* block_next(const block_header_t* block)
\r
439 block_header_t* next = offset_to_block(block_to_ptr(block),
\r
440 block_size(block) - block_header_overhead);
\r
441 tlsf_assert(!block_is_last(block));
\r
445 /* Link a new block with its physical neighbor, return the neighbor. */
\r
446 static block_header_t* block_link_next(block_header_t* block)
\r
448 block_header_t* next = block_next(block);
\r
449 next->prev_phys_block = block;
\r
453 static void block_mark_as_free(block_header_t* block)
\r
455 /* Link the block to the next block, first. */
\r
456 block_header_t* next = block_link_next(block);
\r
457 block_set_prev_free(next);
\r
458 block_set_free(block);
\r
461 static void block_mark_as_used(block_header_t* block)
\r
463 block_header_t* next = block_next(block);
\r
464 block_set_prev_used(next);
\r
465 block_set_used(block);
\r
468 static size_t align_up(size_t x, size_t align)
\r
470 tlsf_assert(0 == (align & (align - 1)) && "must align to a power of two");
\r
471 return (x + (align - 1)) & ~(align - 1);
\r
474 static size_t align_down(size_t x, size_t align)
\r
476 tlsf_assert(0 == (align & (align - 1)) && "must align to a power of two");
\r
477 return x - (x & (align - 1));
\r
480 static void* align_ptr(const void* ptr, size_t align)
\r
482 const tlsfptr_t aligned =
\r
483 (tlsf_cast(tlsfptr_t, ptr) + (align - 1)) & ~(align - 1);
\r
484 tlsf_assert(0 == (align & (align - 1)) && "must align to a power of two");
\r
485 return tlsf_cast(void*, aligned);
\r
489 ** Adjust an allocation size to be aligned to word size, and no smaller
\r
490 ** than internal minimum.
\r
492 static size_t adjust_request_size(size_t size, size_t align)
\r
497 const size_t aligned = align_up(size, align);
\r
499 /* aligned sized must not exceed block_size_max or we'll go out of bounds on sl_bitmap */
\r
500 if (aligned < block_size_max)
\r
502 adjust = tlsf_max(aligned, block_size_min);
\r
509 ** TLSF utility functions. In most cases, these are direct translations of
\r
510 ** the documentation found in the white paper.
\r
513 static void mapping_insert(size_t size, int* fli, int* sli)
\r
516 if (size < SMALL_BLOCK_SIZE)
\r
518 /* Store small blocks in first list. */
\r
520 sl = tlsf_cast(int, size) / (SMALL_BLOCK_SIZE / SL_INDEX_COUNT);
\r
524 fl = tlsf_fls_sizet(size);
\r
525 sl = tlsf_cast(int, size >> (fl - SL_INDEX_COUNT_LOG2)) ^ (1 << SL_INDEX_COUNT_LOG2);
\r
526 fl -= (FL_INDEX_SHIFT - 1);
\r
532 /* This version rounds up to the next block size (for allocations) */
\r
533 static void mapping_search(size_t size, int* fli, int* sli)
\r
535 if (size >= SMALL_BLOCK_SIZE)
\r
537 const size_t round = (1 << (tlsf_fls_sizet(size) - SL_INDEX_COUNT_LOG2)) - 1;
\r
540 mapping_insert(size, fli, sli);
\r
543 static block_header_t* search_suitable_block(control_t* control, int* fli, int* sli)
\r
549 ** First, search for a block in the list associated with the given
\r
552 unsigned int sl_map = control->sl_bitmap[fl] & (~0U << sl);
\r
555 /* No block exists. Search in the next largest first-level list. */
\r
556 const unsigned int fl_map = control->fl_bitmap & (~0U << (fl + 1));
\r
559 /* No free blocks available, memory has been exhausted. */
\r
563 fl = tlsf_ffs(fl_map);
\r
565 sl_map = control->sl_bitmap[fl];
\r
567 tlsf_assert(sl_map && "internal error - second level bitmap is null");
\r
568 sl = tlsf_ffs(sl_map);
\r
571 /* Return the first block in the free list. */
\r
572 return control->blocks[fl][sl];
\r
575 /* Remove a free block from the free list.*/
\r
576 static void remove_free_block(control_t* control, block_header_t* block, int fl, int sl)
\r
578 block_header_t* prev = block->prev_free;
\r
579 block_header_t* next = block->next_free;
\r
580 tlsf_assert(prev && "prev_free field can not be null");
\r
581 tlsf_assert(next && "next_free field can not be null");
\r
582 next->prev_free = prev;
\r
583 prev->next_free = next;
\r
585 /* If this block is the head of the free list, set new head. */
\r
586 if (control->blocks[fl][sl] == block)
\r
588 control->blocks[fl][sl] = next;
\r
590 /* If the new head is null, clear the bitmap. */
\r
591 if (next == &control->block_null)
\r
593 control->sl_bitmap[fl] &= ~(1U << sl);
\r
595 /* If the second bitmap is now empty, clear the fl bitmap. */
\r
596 if (!control->sl_bitmap[fl])
\r
598 control->fl_bitmap &= ~(1U << fl);
\r
604 /* Insert a free block into the free block list. */
\r
605 static void insert_free_block(control_t* control, block_header_t* block, int fl, int sl)
\r
607 block_header_t* current = control->blocks[fl][sl];
\r
608 tlsf_assert(current && "free list cannot have a null entry");
\r
609 tlsf_assert(block && "cannot insert a null entry into the free list");
\r
610 block->next_free = current;
\r
611 block->prev_free = &control->block_null;
\r
612 current->prev_free = block;
\r
614 tlsf_assert(block_to_ptr(block) == align_ptr(block_to_ptr(block), ALIGN_SIZE)
\r
615 && "block not aligned properly");
\r
617 ** Insert the new block at the head of the list, and mark the first-
\r
618 ** and second-level bitmaps appropriately.
\r
620 control->blocks[fl][sl] = block;
\r
621 control->fl_bitmap |= (1U << fl);
\r
622 control->sl_bitmap[fl] |= (1U << sl);
\r
625 /* Remove a given block from the free list. */
\r
626 static void block_remove(control_t* control, block_header_t* block)
\r
629 mapping_insert(block_size(block), &fl, &sl);
\r
630 remove_free_block(control, block, fl, sl);
\r
633 /* Insert a given block into the free list. */
\r
634 static void block_insert(control_t* control, block_header_t* block)
\r
637 mapping_insert(block_size(block), &fl, &sl);
\r
638 insert_free_block(control, block, fl, sl);
\r
641 static int block_can_split(block_header_t* block, size_t size)
\r
643 return block_size(block) >= sizeof(block_header_t) + size;
\r
646 /* Split a block into two, the second of which is free. */
\r
647 static block_header_t* block_split(block_header_t* block, size_t size)
\r
649 /* Calculate the amount of space left in the remaining block. */
\r
650 block_header_t* remaining =
\r
651 offset_to_block(block_to_ptr(block), size - block_header_overhead);
\r
653 const size_t remain_size = block_size(block) - (size + block_header_overhead);
\r
655 tlsf_assert(block_to_ptr(remaining) == align_ptr(block_to_ptr(remaining), ALIGN_SIZE)
\r
656 && "remaining block not aligned properly");
\r
658 tlsf_assert(block_size(block) == remain_size + size + block_header_overhead);
\r
659 block_set_size(remaining, remain_size);
\r
660 tlsf_assert(block_size(remaining) >= block_size_min && "block split with invalid size");
\r
662 block_set_size(block, size);
\r
663 block_mark_as_free(remaining);
\r
668 /* Absorb a free block's storage into an adjacent previous free block. */
\r
669 static block_header_t* block_absorb(block_header_t* prev, block_header_t* block)
\r
671 tlsf_assert(!block_is_last(prev) && "previous block can't be last");
\r
672 /* Note: Leaves flags untouched. */
\r
673 prev->size += block_size(block) + block_header_overhead;
\r
674 block_link_next(prev);
\r
678 /* Merge a just-freed block with an adjacent previous free block. */
\r
679 static block_header_t* block_merge_prev(control_t* control, block_header_t* block)
\r
681 if (block_is_prev_free(block))
\r
683 block_header_t* prev = block_prev(block);
\r
684 tlsf_assert(prev && "prev physical block can't be null");
\r
685 tlsf_assert(block_is_free(prev) && "prev block is not free though marked as such");
\r
686 block_remove(control, prev);
\r
687 block = block_absorb(prev, block);
\r
693 /* Merge a just-freed block with an adjacent free block. */
\r
694 static block_header_t* block_merge_next(control_t* control, block_header_t* block)
\r
696 block_header_t* next = block_next(block);
\r
697 tlsf_assert(next && "next physical block can't be null");
\r
699 if (block_is_free(next))
\r
701 tlsf_assert(!block_is_last(block) && "previous block can't be last");
\r
702 block_remove(control, next);
\r
703 block = block_absorb(block, next);
\r
709 /* Trim any trailing block space off the end of a block, return to pool. */
\r
710 static void block_trim_free(control_t* control, block_header_t* block, size_t size)
\r
712 tlsf_assert(block_is_free(block) && "block must be free");
\r
713 if (block_can_split(block, size))
\r
715 block_header_t* remaining_block = block_split(block, size);
\r
716 block_link_next(block);
\r
717 block_set_prev_free(remaining_block);
\r
718 block_insert(control, remaining_block);
\r
722 /* Trim any trailing block space off the end of a used block, return to pool. */
\r
723 static void block_trim_used(control_t* control, block_header_t* block, size_t size)
\r
725 tlsf_assert(!block_is_free(block) && "block must be used");
\r
726 if (block_can_split(block, size))
\r
728 /* If the next block is free, we must coalesce. */
\r
729 block_header_t* remaining_block = block_split(block, size);
\r
730 block_set_prev_used(remaining_block);
\r
732 remaining_block = block_merge_next(control, remaining_block);
\r
733 block_insert(control, remaining_block);
\r
737 static block_header_t* block_trim_free_leading(control_t* control, block_header_t* block, size_t size)
\r
739 block_header_t* remaining_block = block;
\r
740 if (block_can_split(block, size))
\r
742 /* We want the 2nd block. */
\r
743 remaining_block = block_split(block, size - block_header_overhead);
\r
744 block_set_prev_free(remaining_block);
\r
746 block_link_next(block);
\r
747 block_insert(control, block);
\r
750 return remaining_block;
\r
753 static block_header_t* block_locate_free(control_t* control, size_t size)
\r
755 int fl = 0, sl = 0;
\r
756 block_header_t* block = 0;
\r
760 mapping_search(size, &fl, &sl);
\r
763 ** mapping_search can futz with the size, so for excessively large sizes it can sometimes wind up
\r
764 ** with indices that are off the end of the block array.
\r
765 ** So, we protect against that here, since this is the only callsite of mapping_search.
\r
766 ** Note that we don't need to check sl, since it comes from a modulo operation that guarantees it's always in range.
\r
768 if (fl < FL_INDEX_COUNT)
\r
770 block = search_suitable_block(control, &fl, &sl);
\r
776 tlsf_assert(block_size(block) >= size);
\r
777 remove_free_block(control, block, fl, sl);
\r
783 static void* block_prepare_used(control_t* control, block_header_t* block, size_t size)
\r
788 tlsf_assert(size && "size must be non-zero");
\r
789 block_trim_free(control, block, size);
\r
790 block_mark_as_used(block);
\r
791 p = block_to_ptr(block);
\r
796 /* Clear structure and point all empty lists at the null block. */
\r
797 static void control_construct(control_t* control)
\r
801 control->block_null.next_free = &control->block_null;
\r
802 control->block_null.prev_free = &control->block_null;
\r
804 control->fl_bitmap = 0;
\r
805 for (i = 0; i < FL_INDEX_COUNT; ++i)
\r
807 control->sl_bitmap[i] = 0;
\r
808 for (j = 0; j < SL_INDEX_COUNT; ++j)
\r
810 control->blocks[i][j] = &control->block_null;
\r
816 ** Debugging utilities.
\r
819 typedef struct integrity_t
\r
825 #define tlsf_insist(x) { tlsf_assert(x); if (!(x)) { status--; } }
\r
827 static void integrity_walker(void* ptr, size_t size, int used, void* user)
\r
829 block_header_t* block = block_from_ptr(ptr);
\r
830 integrity_t* integ = tlsf_cast(integrity_t*, user);
\r
831 const int this_prev_status = block_is_prev_free(block) ? 1 : 0;
\r
832 const int this_status = block_is_free(block) ? 1 : 0;
\r
833 const size_t this_block_size = block_size(block);
\r
837 tlsf_insist(integ->prev_status == this_prev_status && "prev status incorrect");
\r
838 tlsf_insist(size == this_block_size && "block size incorrect");
\r
840 integ->prev_status = this_status;
\r
841 integ->status += status;
\r
844 int tlsf_check(tlsf_t tlsf)
\r
848 control_t* control = tlsf_cast(control_t*, tlsf);
\r
851 /* Check that the free lists and bitmaps are accurate. */
\r
852 for (i = 0; i < FL_INDEX_COUNT; ++i)
\r
854 for (j = 0; j < SL_INDEX_COUNT; ++j)
\r
856 const int fl_map = control->fl_bitmap & (1U << i);
\r
857 const int sl_list = control->sl_bitmap[i];
\r
858 const int sl_map = sl_list & (1U << j);
\r
859 const block_header_t* block = control->blocks[i][j];
\r
861 /* Check that first- and second-level lists agree. */
\r
864 tlsf_insist(!sl_map && "second-level map must be null");
\r
869 tlsf_insist(block == &control->block_null && "block list must be null");
\r
873 /* Check that there is at least one free block. */
\r
874 tlsf_insist(sl_list && "no free blocks in second-level map");
\r
875 tlsf_insist(block != &control->block_null && "block should not be null");
\r
877 while (block != &control->block_null)
\r
880 tlsf_insist(block_is_free(block) && "block should be free");
\r
881 tlsf_insist(!block_is_prev_free(block) && "blocks should have coalesced");
\r
882 tlsf_insist(!block_is_free(block_next(block)) && "blocks should have coalesced");
\r
883 tlsf_insist(block_is_prev_free(block_next(block)) && "block should be free");
\r
884 tlsf_insist(block_size(block) >= block_size_min && "block not minimum size");
\r
886 mapping_insert(block_size(block), &fli, &sli);
\r
887 tlsf_insist(fli == i && sli == j && "block size indexed in wrong list");
\r
888 block = block->next_free;
\r
898 static void default_walker(void* ptr, size_t size, int used, void* user)
\r
901 printf("\t%p %s size: %x (%p)\n", ptr, used ? "used" : "free", (unsigned int)size, block_from_ptr(ptr));
\r
904 void tlsf_walk_pool(pool_t pool, tlsf_walker walker, void* user)
\r
906 tlsf_walker pool_walker = walker ? walker : default_walker;
\r
907 block_header_t* block =
\r
908 offset_to_block(pool, -(int)block_header_overhead);
\r
910 while (block && !block_is_last(block))
\r
913 block_to_ptr(block),
\r
915 !block_is_free(block),
\r
917 block = block_next(block);
\r
921 size_t tlsf_block_size(void* ptr)
\r
926 const block_header_t* block = block_from_ptr(ptr);
\r
927 size = block_size(block);
\r
932 int tlsf_check_pool(pool_t pool)
\r
934 /* Check that the blocks are physically correct. */
\r
935 integrity_t integ = { 0, 0 };
\r
936 tlsf_walk_pool(pool, integrity_walker, &integ);
\r
938 return integ.status;
\r
942 ** Size of the TLSF structures in a given memory block passed to
\r
943 ** tlsf_create, equal to the size of a control_t
\r
945 size_t tlsf_size(void)
\r
947 return sizeof(control_t);
\r
950 size_t tlsf_align_size(void)
\r
955 size_t tlsf_block_size_min(void)
\r
957 return block_size_min;
\r
960 size_t tlsf_block_size_max(void)
\r
962 return block_size_max;
\r
966 ** Overhead of the TLSF structures in a given memory block passed to
\r
967 ** tlsf_add_pool, equal to the overhead of a free block and the
\r
970 size_t tlsf_pool_overhead(void)
\r
972 return 2 * block_header_overhead;
\r
975 size_t tlsf_alloc_overhead(void)
\r
977 return block_header_overhead;
\r
980 pool_t tlsf_add_pool(tlsf_t tlsf, void* mem, size_t bytes)
\r
982 block_header_t* block;
\r
983 block_header_t* next;
\r
985 const size_t pool_overhead = tlsf_pool_overhead();
\r
986 const size_t pool_bytes = align_down(bytes - pool_overhead, ALIGN_SIZE);
\r
988 if (((ptrdiff_t)mem % ALIGN_SIZE) != 0)
\r
990 printf("tlsf_add_pool: Memory must be aligned by %u bytes.\n",
\r
991 (unsigned int)ALIGN_SIZE);
\r
995 if (pool_bytes < block_size_min || pool_bytes > block_size_max)
\r
997 #if defined (TLSF_64BIT)
\r
998 printf("tlsf_add_pool: Memory size must be between 0x%x and 0x%x00 bytes.\n",
\r
999 (unsigned int)(pool_overhead + block_size_min),
\r
1000 (unsigned int)((pool_overhead + block_size_max) / 256));
\r
1002 printf("tlsf_add_pool: Memory size must be between %u and %u bytes.\n",
\r
1003 (unsigned int)(pool_overhead + block_size_min),
\r
1004 (unsigned int)(pool_overhead + block_size_max));
\r
1010 ** Create the main free block. Offset the start of the block slightly
\r
1011 ** so that the prev_phys_block field falls outside of the pool -
\r
1012 ** it will never be used.
\r
1014 block = offset_to_block(mem, -(tlsfptr_t)block_header_overhead);
\r
1015 block_set_size(block, pool_bytes);
\r
1016 block_set_free(block);
\r
1017 block_set_prev_used(block);
\r
1018 block_insert(tlsf_cast(control_t*, tlsf), block);
\r
1020 /* Split the block to create a zero-size sentinel block. */
\r
1021 next = block_link_next(block);
\r
1022 block_set_size(next, 0);
\r
1023 block_set_used(next);
\r
1024 block_set_prev_free(next);
\r
1029 void tlsf_remove_pool(tlsf_t tlsf, pool_t pool)
\r
1031 control_t* control = tlsf_cast(control_t*, tlsf);
\r
1032 block_header_t* block = offset_to_block(pool, -(int)block_header_overhead);
\r
1034 int fl = 0, sl = 0;
\r
1036 tlsf_assert(block_is_free(block) && "block should be free");
\r
1037 tlsf_assert(!block_is_free(block_next(block)) && "next block should not be free");
\r
1038 tlsf_assert(block_size(block_next(block)) == 0 && "next block size should be zero");
\r
1040 mapping_insert(block_size(block), &fl, &sl);
\r
1041 remove_free_block(control, block, fl, sl);
\r
1045 ** TLSF main interface.
\r
1049 int test_ffs_fls()
\r
1051 /* Verify ffs/fls work properly. */
\r
1053 rv += (tlsf_ffs(0) == -1) ? 0 : 0x1;
\r
1054 rv += (tlsf_fls(0) == -1) ? 0 : 0x2;
\r
1055 rv += (tlsf_ffs(1) == 0) ? 0 : 0x4;
\r
1056 rv += (tlsf_fls(1) == 0) ? 0 : 0x8;
\r
1057 rv += (tlsf_ffs(0x80000000) == 31) ? 0 : 0x10;
\r
1058 rv += (tlsf_ffs(0x80008000) == 15) ? 0 : 0x20;
\r
1059 rv += (tlsf_fls(0x80000008) == 31) ? 0 : 0x40;
\r
1060 rv += (tlsf_fls(0x7FFFFFFF) == 30) ? 0 : 0x80;
\r
1062 #if defined (TLSF_64BIT)
\r
1063 rv += (tlsf_fls_sizet(0x80000000) == 31) ? 0 : 0x100;
\r
1064 rv += (tlsf_fls_sizet(0x100000000) == 32) ? 0 : 0x200;
\r
1065 rv += (tlsf_fls_sizet(0xffffffffffffffff) == 63) ? 0 : 0x400;
\r
1070 printf("test_ffs_fls: %x ffs/fls tests failed.\n", rv);
\r
1076 tlsf_t tlsf_create(void* mem)
\r
1079 if (test_ffs_fls())
\r
1085 if (((tlsfptr_t)mem % ALIGN_SIZE) != 0)
\r
1087 printf("tlsf_create: Memory must be aligned to %u bytes.\n",
\r
1088 (unsigned int)ALIGN_SIZE);
\r
1092 control_construct(tlsf_cast(control_t*, mem));
\r
1094 return tlsf_cast(tlsf_t, mem);
\r
1097 tlsf_t tlsf_create_with_pool(void* mem, size_t bytes)
\r
1099 tlsf_t tlsf = tlsf_create(mem);
\r
1100 tlsf_add_pool(tlsf, (char*)mem + tlsf_size(), bytes - tlsf_size());
\r
1104 void tlsf_destroy(tlsf_t tlsf)
\r
1106 /* Nothing to do. */
\r
1110 pool_t tlsf_get_pool(tlsf_t tlsf)
\r
1112 return tlsf_cast(pool_t, (char*)tlsf + tlsf_size());
\r
1115 void* tlsf_malloc(tlsf_t tlsf, size_t size)
\r
1117 control_t* control = tlsf_cast(control_t*, tlsf);
\r
1118 const size_t adjust = adjust_request_size(size, ALIGN_SIZE);
\r
1119 block_header_t* block = block_locate_free(control, adjust);
\r
1120 return block_prepare_used(control, block, adjust);
\r
1123 void* tlsf_memalign(tlsf_t tlsf, size_t align, size_t size)
\r
1125 control_t* control = tlsf_cast(control_t*, tlsf);
\r
1126 const size_t adjust = adjust_request_size(size, ALIGN_SIZE);
\r
1129 ** We must allocate an additional minimum block size bytes so that if
\r
1130 ** our free block will leave an alignment gap which is smaller, we can
\r
1131 ** trim a leading free block and release it back to the pool. We must
\r
1132 ** do this because the previous physical block is in use, therefore
\r
1133 ** the prev_phys_block field is not valid, and we can't simply adjust
\r
1134 ** the size of that block.
\r
1136 const size_t gap_minimum = sizeof(block_header_t);
\r
1137 const size_t size_with_gap = adjust_request_size(adjust + align + gap_minimum, align);
\r
1140 ** If alignment is less than or equals base alignment, we're done.
\r
1141 ** If we requested 0 bytes, return null, as tlsf_malloc(0) does.
\r
1143 const size_t aligned_size = (adjust && align > ALIGN_SIZE) ? size_with_gap : adjust;
\r
1145 block_header_t* block = block_locate_free(control, aligned_size);
\r
1147 /* This can't be a static assert. */
\r
1148 tlsf_assert(sizeof(block_header_t) == block_size_min + block_header_overhead);
\r
1152 void* ptr = block_to_ptr(block);
\r
1153 void* aligned = align_ptr(ptr, align);
\r
1154 size_t gap = tlsf_cast(size_t,
\r
1155 tlsf_cast(tlsfptr_t, aligned) - tlsf_cast(tlsfptr_t, ptr));
\r
1157 /* If gap size is too small, offset to next aligned boundary. */
\r
1158 if (gap && gap < gap_minimum)
\r
1160 const size_t gap_remain = gap_minimum - gap;
\r
1161 const size_t offset = tlsf_max(gap_remain, align);
\r
1162 const void* next_aligned = tlsf_cast(void*,
\r
1163 tlsf_cast(tlsfptr_t, aligned) + offset);
\r
1165 aligned = align_ptr(next_aligned, align);
\r
1166 gap = tlsf_cast(size_t,
\r
1167 tlsf_cast(tlsfptr_t, aligned) - tlsf_cast(tlsfptr_t, ptr));
\r
1172 tlsf_assert(gap >= gap_minimum && "gap size too small");
\r
1173 block = block_trim_free_leading(control, block, gap);
\r
1177 return block_prepare_used(control, block, adjust);
\r
1180 void tlsf_free(tlsf_t tlsf, void* ptr)
\r
1182 /* Don't attempt to free a NULL pointer. */
\r
1185 control_t* control = tlsf_cast(control_t*, tlsf);
\r
1186 block_header_t* block = block_from_ptr(ptr);
\r
1187 tlsf_assert(!block_is_free(block) && "block already marked as free");
\r
1188 block_mark_as_free(block);
\r
1189 block = block_merge_prev(control, block);
\r
1190 block = block_merge_next(control, block);
\r
1191 block_insert(control, block);
\r
1196 ** The TLSF block information provides us with enough information to
\r
1197 ** provide a reasonably intelligent implementation of realloc, growing or
\r
1198 ** shrinking the currently allocated block as required.
\r
1200 ** This routine handles the somewhat esoteric edge cases of realloc:
\r
1201 ** - a non-zero size with a null pointer will behave like malloc
\r
1202 ** - a zero size with a non-null pointer will behave like free
\r
1203 ** - a request that cannot be satisfied will leave the original buffer
\r
1205 ** - an extended buffer size will leave the newly-allocated area with
\r
1206 ** contents undefined
\r
1208 void* tlsf_realloc(tlsf_t tlsf, void* ptr, size_t size)
\r
1210 control_t* control = tlsf_cast(control_t*, tlsf);
\r
1213 /* Zero-size requests are treated as free. */
\r
1214 if (ptr && size == 0)
\r
1216 tlsf_free(tlsf, ptr);
\r
1218 /* Requests with NULL pointers are treated as malloc. */
\r
1221 p = tlsf_malloc(tlsf, size);
\r
1225 block_header_t* block = block_from_ptr(ptr);
\r
1226 block_header_t* next = block_next(block);
\r
1228 const size_t cursize = block_size(block);
\r
1229 const size_t combined = cursize + block_size(next) + block_header_overhead;
\r
1230 const size_t adjust = adjust_request_size(size, ALIGN_SIZE);
\r
1232 tlsf_assert(!block_is_free(block) && "block already marked as free");
\r
1235 ** If the next block is used, or when combined with the current
\r
1236 ** block, does not offer enough space, we must reallocate and copy.
\r
1238 if (adjust > cursize && (!block_is_free(next) || adjust > combined))
\r
1240 p = tlsf_malloc(tlsf, size);
\r
1243 const size_t minsize = tlsf_min(cursize, size);
\r
1244 memcpy(p, ptr, minsize);
\r
1245 tlsf_free(tlsf, ptr);
\r
1250 /* Do we need to expand to the next block? */
\r
1251 if (adjust > cursize)
\r
1253 block_merge_next(control, block);
\r
1254 block_mark_as_used(block);
\r
1257 /* Trim the resulting block and return the original pointer. */
\r
1258 block_trim_used(control, block, adjust);
\r
notaz.gp2x.de / pcsx_rearmed.git / blob