15 /* Public constants: may be modified. */
18 /* log2 of number of linear subdivisions of block sizes. */
19 SL_INDEX_COUNT_LOG2
= 5,
22 /* Private constants: do not modify. */
25 #if defined (TLSF_64BIT)
26 /* All allocation sizes and addresses are aligned to 8 bytes. */
29 /* All allocation sizes and addresses are aligned to 4 bytes. */
32 ALIGN_SIZE
= (1 << ALIGN_SIZE_LOG2
),
35 ** We support allocations of sizes up to (1 << FL_INDEX_MAX) bits.
36 ** However, because we linearly subdivide the second-level lists, and
37 ** our minimum size granularity is 4 bytes, it doesn't make sense to
38 ** create first-level lists for sizes smaller than SL_INDEX_COUNT * 4,
39 ** or (1 << (SL_INDEX_COUNT_LOG2 + 2)) bytes, as there we will be
40 ** trying to split size ranges into more slots than we have available.
41 ** Instead, we calculate the minimum threshold size, and place all
42 ** blocks below that size into the 0th first-level list.
45 #if defined (TLSF_64BIT)
47 ** TODO: We can increase this to support larger sizes, at the expense
48 ** of more overhead in the TLSF structure.
54 SL_INDEX_COUNT
= (1 << SL_INDEX_COUNT_LOG2
),
55 FL_INDEX_SHIFT
= (SL_INDEX_COUNT_LOG2
+ ALIGN_SIZE_LOG2
),
56 FL_INDEX_COUNT
= (FL_INDEX_MAX
- FL_INDEX_SHIFT
+ 1),
58 SMALL_BLOCK_SIZE
= (1 << FL_INDEX_SHIFT
),
62 ** Cast and min/max macros.
65 #define tlsf_cast(t, exp) ((t) (exp))
66 #define tlsf_min(a, b) ((a) < (b) ? (a) : (b))
67 #define tlsf_max(a, b) ((a) > (b) ? (a) : (b))
70 ** Set assert macro, if it has not been provided by the user.
72 #if !defined (tlsf_assert)
73 #define tlsf_assert assert
77 ** Static assertion mechanism.
80 #define _tlsf_glue2(x, y) x ## y
81 #define _tlsf_glue(x, y) _tlsf_glue2(x, y)
82 #define tlsf_static_assert(exp) \
83 typedef char _tlsf_glue(static_assert, __LINE__) [(exp) ? 1 : -1]
85 /* This code has been tested on 32- and 64-bit (LP/LLP) architectures. */
86 tlsf_static_assert(sizeof(int) * CHAR_BIT
== 32);
87 tlsf_static_assert(sizeof(size_t) * CHAR_BIT
>= 32);
88 tlsf_static_assert(sizeof(size_t) * CHAR_BIT
<= 64);
90 /* SL_INDEX_COUNT must be <= number of bits in sl_bitmap's storage type. */
91 tlsf_static_assert(sizeof(unsigned int) * CHAR_BIT
>= SL_INDEX_COUNT
);
93 /* Ensure we've properly tuned our sizes. */
94 tlsf_static_assert(ALIGN_SIZE
== SMALL_BLOCK_SIZE
/ SL_INDEX_COUNT
);
97 ** Data structures and associated constants.
101 ** Block header structure.
103 ** There are several implementation subtleties involved:
104 ** - The prev_phys_block field is only valid if the previous block is free.
105 ** - The prev_phys_block field is actually stored at the end of the
106 ** previous block. It appears at the beginning of this structure only to
107 ** simplify the implementation.
108 ** - The next_free / prev_free fields are only valid if the block is free.
110 typedef struct block_header_t
112 /* Points to the previous physical block. */
113 struct block_header_t
* prev_phys_block
;
115 /* The size of this block, excluding the block header. */
118 /* Next and previous free blocks. */
119 struct block_header_t
* next_free
;
120 struct block_header_t
* prev_free
;
124 ** Since block sizes are always at least a multiple of 4, the two least
125 ** significant bits of the size field are used to store the block status:
126 ** - bit 0: whether block is busy or free
127 ** - bit 1: whether previous block is busy or free
129 static const size_t block_header_free_bit
= 1 << 0;
130 static const size_t block_header_prev_free_bit
= 1 << 1;
133 ** The size of the block header exposed to used blocks is the size field.
134 ** The prev_phys_block field is stored *inside* the previous free block.
136 static const size_t block_header_overhead
= sizeof(size_t);
138 /* User data starts directly after the size field in a used block. */
139 static const size_t block_start_offset
=
140 offsetof(block_header_t
, size
) + sizeof(size_t);
143 ** A free block must be large enough to store its header minus the size of
144 ** the prev_phys_block field, and no larger than the number of addressable
145 ** bits for FL_INDEX.
147 static const size_t block_size_min
=
148 sizeof(block_header_t
) - sizeof(block_header_t
*);
149 static const size_t block_size_max
= tlsf_cast(size_t, 1) << FL_INDEX_MAX
;
152 /* The TLSF control structure. */
153 typedef struct control_t
155 /* Empty lists point at this block to indicate they are free. */
156 block_header_t block_null
;
158 /* Bitmaps for free lists. */
159 unsigned int fl_bitmap
;
160 unsigned int sl_bitmap
[FL_INDEX_COUNT
];
162 /* Head of free lists. */
163 block_header_t
* blocks
[FL_INDEX_COUNT
][SL_INDEX_COUNT
];
166 /* A type used for casting when doing pointer arithmetic. */
167 typedef ptrdiff_t tlsfptr_t
;
170 ** block_header_t member functions.
173 static size_t block_size(const block_header_t
* block
)
175 return block
->size
& ~(block_header_free_bit
| block_header_prev_free_bit
);
178 static void block_set_size(block_header_t
* block
, size_t size
)
180 const size_t oldsize
= block
->size
;
181 block
->size
= size
| (oldsize
& (block_header_free_bit
| block_header_prev_free_bit
));
184 static int block_is_last(const block_header_t
* block
)
186 return 0 == block_size(block
);
189 static int block_is_free(const block_header_t
* block
)
191 return tlsf_cast(int, block
->size
& block_header_free_bit
);
194 static void block_set_free(block_header_t
* block
)
196 block
->size
|= block_header_free_bit
;
199 static void block_set_used(block_header_t
* block
)
201 block
->size
&= ~block_header_free_bit
;
204 static int block_is_prev_free(const block_header_t
* block
)
206 return tlsf_cast(int, block
->size
& block_header_prev_free_bit
);
209 static void block_set_prev_free(block_header_t
* block
)
211 block
->size
|= block_header_prev_free_bit
;
214 static void block_set_prev_used(block_header_t
* block
)
216 block
->size
&= ~block_header_prev_free_bit
;
219 static block_header_t
* block_from_ptr(const void* ptr
)
221 return tlsf_cast(block_header_t
*,
222 tlsf_cast(unsigned char*, ptr
) - block_start_offset
);
225 static void* block_to_ptr(const block_header_t
* block
)
227 return tlsf_cast(void*,
228 tlsf_cast(unsigned char*, block
) + block_start_offset
);
231 /* Return location of next block after block of given size. */
232 static block_header_t
* offset_to_block(const void* ptr
, size_t size
)
234 return tlsf_cast(block_header_t
*, tlsf_cast(tlsfptr_t
, ptr
) + size
);
237 /* Return location of previous block. */
238 static block_header_t
* block_prev(const block_header_t
* block
)
240 return block
->prev_phys_block
;
243 /* Return location of next existing block. */
244 static block_header_t
* block_next(const block_header_t
* block
)
246 block_header_t
* next
= offset_to_block(block_to_ptr(block
),
247 block_size(block
) - block_header_overhead
);
248 tlsf_assert(!block_is_last(block
));
252 /* Link a new block with its physical neighbor, return the neighbor. */
253 static block_header_t
* block_link_next(block_header_t
* block
)
255 block_header_t
* next
= block_next(block
);
256 next
->prev_phys_block
= block
;
260 static void block_mark_as_free(block_header_t
* block
)
262 /* Link the block to the next block, first. */
263 block_header_t
* next
= block_link_next(block
);
264 block_set_prev_free(next
);
265 block_set_free(block
);
268 static void block_mark_as_used(block_header_t
* block
)
270 block_header_t
* next
= block_next(block
);
271 block_set_prev_used(next
);
272 block_set_used(block
);
275 static size_t align_up(size_t x
, size_t align
)
277 tlsf_assert(0 == (align
& (align
- 1)) && "must align to a power of two");
278 return (x
+ (align
- 1)) & ~(align
- 1);
281 static size_t align_down(size_t x
, size_t align
)
283 tlsf_assert(0 == (align
& (align
- 1)) && "must align to a power of two");
284 return x
- (x
& (align
- 1));
287 static void* align_ptr(const void* ptr
, size_t align
)
289 const tlsfptr_t aligned
=
290 (tlsf_cast(tlsfptr_t
, ptr
) + (align
- 1)) & ~(align
- 1);
291 tlsf_assert(0 == (align
& (align
- 1)) && "must align to a power of two");
292 return tlsf_cast(void*, aligned
);
296 ** Adjust an allocation size to be aligned to word size, and no smaller
297 ** than internal minimum.
299 static size_t adjust_request_size(size_t size
, size_t align
)
302 if (size
&& size
< block_size_max
)
304 const size_t aligned
= align_up(size
, align
);
305 adjust
= tlsf_max(aligned
, block_size_min
);
311 ** TLSF utility functions. In most cases, these are direct translations of
312 ** the documentation found in the white paper.
315 static void mapping_insert(size_t size
, int* fli
, int* sli
)
318 if (size
< SMALL_BLOCK_SIZE
)
320 /* Store small blocks in first list. */
322 sl
= tlsf_cast(int, size
) / (SMALL_BLOCK_SIZE
/ SL_INDEX_COUNT
);
326 fl
= tlsf_fls_sizet(size
);
327 sl
= tlsf_cast(int, size
>> (fl
- SL_INDEX_COUNT_LOG2
)) ^ (1 << SL_INDEX_COUNT_LOG2
);
328 fl
-= (FL_INDEX_SHIFT
- 1);
334 /* This version rounds up to the next block size (for allocations) */
335 static void mapping_search(size_t size
, int* fli
, int* sli
)
337 if (size
>= (1 << SL_INDEX_COUNT_LOG2
))
339 const size_t round
= (1 << (tlsf_fls_sizet(size
) - SL_INDEX_COUNT_LOG2
)) - 1;
342 mapping_insert(size
, fli
, sli
);
345 static block_header_t
* search_suitable_block(control_t
* control
, int* fli
, int* sli
)
351 ** First, search for a block in the list associated with the given
354 unsigned int sl_map
= control
->sl_bitmap
[fl
] & (~0 << sl
);
357 /* No block exists. Search in the next largest first-level list. */
358 const unsigned int fl_map
= control
->fl_bitmap
& (~0 << (fl
+ 1));
361 /* No free blocks available, memory has been exhausted. */
365 fl
= tlsf_ffs(fl_map
);
367 sl_map
= control
->sl_bitmap
[fl
];
369 tlsf_assert(sl_map
&& "internal error - second level bitmap is null");
370 sl
= tlsf_ffs(sl_map
);
373 /* Return the first block in the free list. */
374 return control
->blocks
[fl
][sl
];
377 /* Remove a free block from the free list.*/
378 static void remove_free_block(control_t
* control
, block_header_t
* block
, int fl
, int sl
)
380 block_header_t
* prev
= block
->prev_free
;
381 block_header_t
* next
= block
->next_free
;
382 tlsf_assert(prev
&& "prev_free field can not be null");
383 tlsf_assert(next
&& "next_free field can not be null");
384 next
->prev_free
= prev
;
385 prev
->next_free
= next
;
387 /* If this block is the head of the free list, set new head. */
388 if (control
->blocks
[fl
][sl
] == block
)
390 control
->blocks
[fl
][sl
] = next
;
392 /* If the new head is null, clear the bitmap. */
393 if (next
== &control
->block_null
)
395 control
->sl_bitmap
[fl
] &= ~(1 << sl
);
397 /* If the second bitmap is now empty, clear the fl bitmap. */
398 if (!control
->sl_bitmap
[fl
])
400 control
->fl_bitmap
&= ~(1 << fl
);
406 /* Insert a free block into the free block list. */
407 static void insert_free_block(control_t
* control
, block_header_t
* block
, int fl
, int sl
)
409 block_header_t
* current
= control
->blocks
[fl
][sl
];
410 tlsf_assert(current
&& "free list cannot have a null entry");
411 tlsf_assert(block
&& "cannot insert a null entry into the free list");
412 block
->next_free
= current
;
413 block
->prev_free
= &control
->block_null
;
414 current
->prev_free
= block
;
416 tlsf_assert(block_to_ptr(block
) == align_ptr(block_to_ptr(block
), ALIGN_SIZE
)
417 && "block not aligned properly");
419 ** Insert the new block at the head of the list, and mark the first-
420 ** and second-level bitmaps appropriately.
422 control
->blocks
[fl
][sl
] = block
;
423 control
->fl_bitmap
|= (1 << fl
);
424 control
->sl_bitmap
[fl
] |= (1 << sl
);
427 /* Remove a given block from the free list. */
428 static void block_remove(control_t
* control
, block_header_t
* block
)
431 mapping_insert(block_size(block
), &fl
, &sl
);
432 remove_free_block(control
, block
, fl
, sl
);
435 /* Insert a given block into the free list. */
436 static void block_insert(control_t
* control
, block_header_t
* block
)
439 mapping_insert(block_size(block
), &fl
, &sl
);
440 insert_free_block(control
, block
, fl
, sl
);
443 static int block_can_split(block_header_t
* block
, size_t size
)
445 return block_size(block
) >= sizeof(block_header_t
) + size
;
448 /* Split a block into two, the second of which is free. */
449 static block_header_t
* block_split(block_header_t
* block
, size_t size
)
451 /* Calculate the amount of space left in the remaining block. */
452 block_header_t
* remaining
=
453 offset_to_block(block_to_ptr(block
), size
- block_header_overhead
);
455 const size_t remain_size
= block_size(block
) - (size
+ block_header_overhead
);
457 tlsf_assert(block_to_ptr(remaining
) == align_ptr(block_to_ptr(remaining
), ALIGN_SIZE
)
458 && "remaining block not aligned properly");
460 tlsf_assert(block_size(block
) == remain_size
+ size
+ block_header_overhead
);
461 block_set_size(remaining
, remain_size
);
462 tlsf_assert(block_size(remaining
) >= block_size_min
&& "block split with invalid size");
464 block_set_size(block
, size
);
465 block_mark_as_free(remaining
);
470 /* Absorb a free block's storage into an adjacent previous free block. */
471 static block_header_t
* block_absorb(block_header_t
* prev
, block_header_t
* block
)
473 tlsf_assert(!block_is_last(prev
) && "previous block can't be last!");
474 /* Note: Leaves flags untouched. */
475 prev
->size
+= block_size(block
) + block_header_overhead
;
476 block_link_next(prev
);
480 /* Merge a just-freed block with an adjacent previous free block. */
481 static block_header_t
* block_merge_prev(control_t
* control
, block_header_t
* block
)
483 if (block_is_prev_free(block
))
485 block_header_t
* prev
= block_prev(block
);
486 tlsf_assert(prev
&& "prev physical block can't be null");
487 tlsf_assert(block_is_free(prev
) && "prev block is not free though marked as such");
488 block_remove(control
, prev
);
489 block
= block_absorb(prev
, block
);
495 /* Merge a just-freed block with an adjacent free block. */
496 static block_header_t
* block_merge_next(control_t
* control
, block_header_t
* block
)
498 block_header_t
* next
= block_next(block
);
499 tlsf_assert(next
&& "next physical block can't be null");
501 if (block_is_free(next
))
503 tlsf_assert(!block_is_last(block
) && "previous block can't be last!");
504 block_remove(control
, next
);
505 block
= block_absorb(block
, next
);
511 /* Trim any trailing block space off the end of a block, return to pool. */
512 static void block_trim_free(control_t
* control
, block_header_t
* block
, size_t size
)
514 tlsf_assert(block_is_free(block
) && "block must be free");
515 if (block_can_split(block
, size
))
517 block_header_t
* remaining_block
= block_split(block
, size
);
518 block_link_next(block
);
519 block_set_prev_free(remaining_block
);
520 block_insert(control
, remaining_block
);
524 /* Trim any trailing block space off the end of a used block, return to pool. */
525 static void block_trim_used(control_t
* control
, block_header_t
* block
, size_t size
)
527 tlsf_assert(!block_is_free(block
) && "block must be used");
528 if (block_can_split(block
, size
))
530 /* If the next block is free, we must coalesce. */
531 block_header_t
* remaining_block
= block_split(block
, size
);
532 block_set_prev_used(remaining_block
);
534 remaining_block
= block_merge_next(control
, remaining_block
);
535 block_insert(control
, remaining_block
);
539 static block_header_t
* block_trim_free_leading(control_t
* control
, block_header_t
* block
, size_t size
)
541 block_header_t
* remaining_block
= block
;
542 if (block_can_split(block
, size
))
544 /* We want the 2nd block. */
545 remaining_block
= block_split(block
, size
- block_header_overhead
);
546 block_set_prev_free(remaining_block
);
548 block_link_next(block
);
549 block_insert(control
, block
);
552 return remaining_block
;
555 static block_header_t
* block_locate_free(control_t
* control
, size_t size
)
558 block_header_t
* block
= 0;
562 mapping_search(size
, &fl
, &sl
);
563 block
= search_suitable_block(control
, &fl
, &sl
);
564 if(block
&& !block
->size
)
571 tlsf_assert(block_size(block
) >= size
);
572 remove_free_block(control
, block
, fl
, sl
);
578 static void* block_prepare_used(control_t
* control
, block_header_t
* block
, size_t size
)
583 block_trim_free(control
, block
, size
);
584 block_mark_as_used(block
);
585 p
= block_to_ptr(block
);
590 /* Clear structure and point all empty lists at the null block. */
591 static void control_construct(control_t
* control
)
595 control
->block_null
.next_free
= &control
->block_null
;
596 control
->block_null
.prev_free
= &control
->block_null
;
598 control
->fl_bitmap
= 0;
599 for (i
= 0; i
< FL_INDEX_COUNT
; ++i
)
601 control
->sl_bitmap
[i
] = 0;
602 for (j
= 0; j
< SL_INDEX_COUNT
; ++j
)
604 control
->blocks
[i
][j
] = &control
->block_null
;
610 ** Debugging utilities.
613 typedef struct integrity_t
619 #define tlsf_insist(x) { tlsf_assert(x); if (!(x)) { status--; } }
621 static void integrity_walker(void* ptr
, size_t size
, int used
, void* user
)
624 block_header_t
* block
= block_from_ptr(ptr
);
625 integrity_t
* integ
= tlsf_cast(integrity_t
*, user
);
626 const int this_prev_status
= block_is_prev_free(block
) ? 1 : 0;
627 const int this_status
= block_is_free(block
) ? 1 : 0;
628 const size_t this_block_size
= block_size(block
);
631 tlsf_insist(integ
->prev_status
== this_prev_status
&& "prev status incorrect");
632 tlsf_insist(size
== this_block_size
&& "block size incorrect");
634 integ
->prev_status
= this_status
;
635 integ
->status
+= status
;
638 int tlsf_check(tlsf_t tlsf
)
642 control_t
* control
= tlsf_cast(control_t
*, tlsf
);
645 /* Check that the free lists and bitmaps are accurate. */
646 for (i
= 0; i
< FL_INDEX_COUNT
; ++i
)
648 for (j
= 0; j
< SL_INDEX_COUNT
; ++j
)
650 const int fl_map
= control
->fl_bitmap
& (1 << i
);
651 const int sl_list
= control
->sl_bitmap
[i
];
652 const int sl_map
= sl_list
& (1 << j
);
653 const block_header_t
* block
= control
->blocks
[i
][j
];
655 /* Check that first- and second-level lists agree. */
658 tlsf_insist(!sl_map
&& "second-level map must be null");
663 tlsf_insist(block
== &control
->block_null
&& "block list must be null");
667 /* Check that there is at least one free block. */
668 tlsf_insist(sl_list
&& "no free blocks in second-level map");
669 tlsf_insist(block
!= &control
->block_null
&& "block should not be null");
671 while (block
!= &control
->block_null
)
674 tlsf_insist(block_is_free(block
) && "block should be free");
675 tlsf_insist(!block_is_prev_free(block
) && "blocks should have coalesced");
676 tlsf_insist(!block_is_free(block_next(block
)) && "blocks should have coalesced");
677 tlsf_insist(block_is_prev_free(block_next(block
)) && "block should be free");
678 tlsf_insist(block_size(block
) >= block_size_min
&& "block not minimum size");
680 mapping_insert(block_size(block
), &fli
, &sli
);
681 tlsf_insist(fli
== i
&& sli
== j
&& "block size indexed in wrong list");
682 block
= block
->next_free
;
692 static void default_walker(void* ptr
, size_t size
, int used
, void* user
)
695 printf("\t%p %s size: %x (%p)\n", ptr
, used
? "used" : "free", (unsigned int)size
, block_from_ptr(ptr
));
698 void tlsf_walk_pool(pool_t pool
, tlsf_walker walker
, void* user
)
700 tlsf_walker pool_walker
= walker
? walker
: default_walker
;
701 block_header_t
* block
=
702 offset_to_block(pool
, -(int)block_header_overhead
);
704 while (block
&& !block_is_last(block
))
709 !block_is_free(block
),
711 block
= block_next(block
);
715 size_t tlsf_block_size(void* ptr
)
720 const block_header_t
* block
= block_from_ptr(ptr
);
721 size
= block_size(block
);
726 int tlsf_check_pool(pool_t pool
)
728 /* Check that the blocks are physically correct. */
729 integrity_t integ
= { 0, 0 };
730 tlsf_walk_pool(pool
, integrity_walker
, &integ
);
736 ** Size of the TLSF structures in a given memory block passed to
737 ** tlsf_create, equal to the size of a control_t
741 return sizeof(control_t
);
744 size_t tlsf_align_size()
749 size_t tlsf_block_size_min()
751 return block_size_min
;
754 size_t tlsf_block_size_max()
756 return block_size_max
;
760 ** Overhead of the TLSF structures in a given memory block passes to
761 ** tlsf_add_pool, equal to the overhead of a free block and the
764 size_t tlsf_pool_overhead()
766 return 2 * block_header_overhead
;
769 size_t tlsf_alloc_overhead()
771 return block_header_overhead
;
774 pool_t
tlsf_add_pool(tlsf_t tlsf
, void* mem
, size_t bytes
)
776 block_header_t
* block
;
777 block_header_t
* next
;
779 const size_t pool_overhead
= tlsf_pool_overhead();
780 const size_t pool_bytes
= align_down(bytes
- pool_overhead
, ALIGN_SIZE
);
782 if (((ptrdiff_t)mem
% ALIGN_SIZE
) != 0)
784 printf("tlsf_add_pool: Memory must be aligned by %u bytes.\n",
785 (unsigned int)ALIGN_SIZE
);
789 if (pool_bytes
< block_size_min
|| pool_bytes
> block_size_max
)
791 #if defined (TLSF_64BIT)
792 printf("tlsf_add_pool: Memory size must be between 0x%x and 0x%x00 bytes.\n",
793 (unsigned int)(pool_overhead
+ block_size_min
),
794 (unsigned int)((pool_overhead
+ block_size_max
) / 256));
796 printf("tlsf_add_pool: Memory size must be between %u and %u bytes.\n",
797 (unsigned int)(pool_overhead
+ block_size_min
),
798 (unsigned int)(pool_overhead
+ block_size_max
));
804 ** Create the main free block. Offset the start of the block slightly
805 ** so that the prev_phys_block field falls outside of the pool -
806 ** it will never be used.
808 block
= offset_to_block(mem
, -(tlsfptr_t
)block_header_overhead
);
809 block_set_size(block
, pool_bytes
);
810 block_set_free(block
);
811 block_set_prev_used(block
);
812 block_insert(tlsf_cast(control_t
*, tlsf
), block
);
814 /* Split the block to create a zero-size sentinel block. */
815 next
= block_link_next(block
);
816 block_set_size(next
, 0);
817 block_set_used(next
);
818 block_set_prev_free(next
);
823 void tlsf_remove_pool(tlsf_t tlsf
, pool_t pool
)
825 control_t
* control
= tlsf_cast(control_t
*, tlsf
);
826 block_header_t
* block
= offset_to_block(pool
, -(int)block_header_overhead
);
830 tlsf_assert(block_is_free(block
) && "block should be free");
831 tlsf_assert(!block_is_free(block_next(block
)) && "next block should not be free");
832 tlsf_assert(block_size(block_next(block
)) == 0 && "next block size should be zero");
834 mapping_insert(block_size(block
), &fl
, &sl
);
835 remove_free_block(control
, block
, fl
, sl
);
839 ** TLSF main interface.
845 /* Verify ffs/fls work properly. */
847 rv
+= (tlsf_ffs(0) == -1) ? 0 : 0x1;
848 rv
+= (tlsf_fls(0) == -1) ? 0 : 0x2;
849 rv
+= (tlsf_ffs(1) == 0) ? 0 : 0x4;
850 rv
+= (tlsf_fls(1) == 0) ? 0 : 0x8;
851 rv
+= (tlsf_ffs(0x80000000) == 31) ? 0 : 0x10;
852 rv
+= (tlsf_ffs(0x80008000) == 15) ? 0 : 0x20;
853 rv
+= (tlsf_fls(0x80000008) == 31) ? 0 : 0x40;
854 rv
+= (tlsf_fls(0x7FFFFFFF) == 30) ? 0 : 0x80;
856 #if defined (TLSF_64BIT)
857 rv
+= (tlsf_fls_sizet(0x80000000) == 31) ? 0 : 0x100;
858 rv
+= (tlsf_fls_sizet(0x100000000) == 32) ? 0 : 0x200;
859 rv
+= (tlsf_fls_sizet(0xffffffffffffffff) == 63) ? 0 : 0x400;
864 printf("tlsf_create: %x ffs/fls tests failed!\n", rv
);
870 tlsf_t
tlsf_create(void* mem
)
879 if (((tlsfptr_t
)mem
% ALIGN_SIZE
) != 0)
881 printf("tlsf_create: Memory must be aligned to %u bytes.\n",
882 (unsigned int)ALIGN_SIZE
);
886 control_construct(tlsf_cast(control_t
*, mem
));
888 return tlsf_cast(tlsf_t
, mem
);
891 tlsf_t
tlsf_create_with_pool(void* mem
, size_t bytes
)
893 tlsf_t tlsf
= tlsf_create(mem
);
894 tlsf_add_pool(tlsf
, (char*)mem
+ tlsf_size(), bytes
- tlsf_size());
898 void tlsf_destroy(tlsf_t tlsf
)
904 pool_t
tlsf_get_pool(tlsf_t tlsf
)
906 return tlsf_cast(pool_t
, (char*)tlsf
+ tlsf_size());
909 void* tlsf_malloc(tlsf_t tlsf
, size_t size
)
911 control_t
* control
= tlsf_cast(control_t
*, tlsf
);
912 const size_t adjust
= adjust_request_size(size
, ALIGN_SIZE
);
913 block_header_t
* block
= block_locate_free(control
, adjust
);
914 return block_prepare_used(control
, block
, adjust
);
917 void* tlsf_memalign(tlsf_t tlsf
, size_t align
, size_t size
)
919 control_t
* control
= tlsf_cast(control_t
*, tlsf
);
920 const size_t adjust
= adjust_request_size(size
, ALIGN_SIZE
);
923 ** We must allocate an additional minimum block size bytes so that if
924 ** our free block will leave an alignment gap which is smaller, we can
925 ** trim a leading free block and release it back to the pool. We must
926 ** do this because the previous physical block is in use, therefore
927 ** the prev_phys_block field is not valid, and we can't simply adjust
928 ** the size of that block.
930 const size_t gap_minimum
= sizeof(block_header_t
);
931 const size_t size_with_gap
= adjust_request_size(adjust
+ align
+ gap_minimum
, align
);
933 /* If alignment is less than or equals base alignment, we're done. */
934 const size_t aligned_size
= (align
<= ALIGN_SIZE
) ? adjust
: size_with_gap
;
936 block_header_t
* block
= block_locate_free(control
, aligned_size
);
938 /* This can't be a static assert. */
939 tlsf_assert(sizeof(block_header_t
) == block_size_min
+ block_header_overhead
);
943 void* ptr
= block_to_ptr(block
);
944 void* aligned
= align_ptr(ptr
, align
);
945 size_t gap
= tlsf_cast(size_t,
946 tlsf_cast(tlsfptr_t
, aligned
) - tlsf_cast(tlsfptr_t
, ptr
));
948 /* If gap size is too small, offset to next aligned boundary. */
949 if (gap
&& gap
< gap_minimum
)
951 const size_t gap_remain
= gap_minimum
- gap
;
952 const size_t offset
= tlsf_max(gap_remain
, align
);
953 const void* next_aligned
= tlsf_cast(void*,
954 tlsf_cast(tlsfptr_t
, aligned
) + offset
);
956 aligned
= align_ptr(next_aligned
, align
);
957 gap
= tlsf_cast(size_t,
958 tlsf_cast(tlsfptr_t
, aligned
) - tlsf_cast(tlsfptr_t
, ptr
));
963 tlsf_assert(gap
>= gap_minimum
&& "gap size too small");
964 block
= block_trim_free_leading(control
, block
, gap
);
968 return block_prepare_used(control
, block
, adjust
);
971 void tlsf_free(tlsf_t tlsf
, void* ptr
)
973 /* Don't attempt to free a NULL pointer. */
976 control_t
* control
= tlsf_cast(control_t
*, tlsf
);
977 block_header_t
* block
= block_from_ptr(ptr
);
978 tlsf_assert(!block_is_free(block
) && "block already marked as free");
979 block_mark_as_free(block
);
980 block
= block_merge_prev(control
, block
);
981 block
= block_merge_next(control
, block
);
982 block_insert(control
, block
);
987 ** The TLSF block information provides us with enough information to
988 ** provide a reasonably intelligent implementation of realloc, growing or
989 ** shrinking the currently allocated block as required.
991 ** This routine handles the somewhat esoteric edge cases of realloc:
992 ** - a non-zero size with a null pointer will behave like malloc
993 ** - a zero size with a non-null pointer will behave like free
994 ** - a request that cannot be satisfied will leave the original buffer
996 ** - an extended buffer size will leave the newly-allocated area with
997 ** contents undefined
999 void* tlsf_realloc(tlsf_t tlsf
, void* ptr
, size_t size
)
1001 control_t
* control
= tlsf_cast(control_t
*, tlsf
);
1004 /* Zero-size requests are treated as free. */
1005 if (ptr
&& size
== 0)
1007 tlsf_free(tlsf
, ptr
);
1009 /* Requests with NULL pointers are treated as malloc. */
1012 p
= tlsf_malloc(tlsf
, size
);
1016 block_header_t
* block
= block_from_ptr(ptr
);
1017 block_header_t
* next
= block_next(block
);
1019 const size_t cursize
= block_size(block
);
1020 const size_t combined
= cursize
+ block_size(next
) + block_header_overhead
;
1021 const size_t adjust
= adjust_request_size(size
, ALIGN_SIZE
);
1023 tlsf_assert(!block_is_free(block
) && "block already marked as free");
1026 ** If the next block is used, or when combined with the current
1027 ** block, does not offer enough space, we must reallocate and copy.
1029 if (adjust
> cursize
&& (!block_is_free(next
) || adjust
> combined
))
1031 p
= tlsf_malloc(tlsf
, size
);
1034 const size_t minsize
= tlsf_min(cursize
, size
);
1035 memcpy(p
, ptr
, minsize
);
1036 tlsf_free(tlsf
, ptr
);
1041 /* Do we need to expand to the next block? */
1042 if (adjust
> cursize
)
1044 block_merge_next(control
, block
);
1045 block_mark_as_used(block
);
1048 /* Trim the resulting block and return the original pointer. */
1049 block_trim_used(control
, block
, adjust
);