10 #if defined(__cplusplus)
11 #define tlsf_decl inline
13 #define tlsf_decl static
38 #if defined(__alpha__) || defined(__ia64__) || defined(__x86_64__) || defined(_WIN64) || \
39 defined(__LP64__) || defined(__LLP64__)
47 #if defined(__GNUC__) && (__GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)) && \
48 defined(__GNUC_PATCHLEVEL__)
52 return __builtin_ffs(word) - 1;
57 const int bit = word ? 32 - __builtin_clz(word) : 0;
61 #if defined(TLSF_64BIT)
63 const int bit = size ? 64 - __builtin_clzl(size) : 0;
76 if (!(word & 0xffff0000)) {
80 if (!(word & 0xff000000)) {
84 if (!(word & 0xf0000000)) {
88 if (!(word & 0xc0000000)) {
92 if (!(word & 0x80000000)) {
110 #if defined(TLSF_64BIT)
112 int high = (int)(size >> 32);
117 bits =
tlsf_fls((
int)size & 0xffffffff);
124 #if !defined(TLSF_64BIT)
125 #define tlsf_fls_sizet tlsf_fls
145 #if defined(TLSF_64BIT)
165 #
if defined(TLSF_64BIT)
185 #define tlsf_cast(t, exp) ((t)(exp))
186 #define tlsf_min(a, b) ((a) < (b) ? (a) : (b))
187 #define tlsf_max(a, b) ((a) > (b) ? (a) : (b))
192 #if !defined(tlsf_assert)
193 #define tlsf_assert assert
200 #define _tlsf_glue2(x, y) x##y
201 #define _tlsf_glue(x, y) _tlsf_glue2(x, y)
202 #define tlsf_static_assert(exp) typedef char _tlsf_glue(static_assert, __LINE__)[(exp) ? 1 : -1]
268 #define TLSF_INCREASE_REAL_USED(control, increment) \
270 control->real_used += (increment); \
271 control->max_used = tlsf_max(control->real_used, control->max_used); \
273 #define TLSF_INCREASE_FRAGMENTS(control) \
275 control->fragments++; \
276 control->max_fragments = tlsf_max(control->fragments, control->max_fragments); \
310 const size_t oldsize = block->
size;
327 block->
size &= ~block_header_free_bit;
331 return tlsf_cast(
int, block->
size& block_header_prev_free_bit);
339 block->
size &= ~block_header_prev_free_bit;
390 tlsf_assert(0 == (align & (align - 1)) &&
"must align to a power of two");
391 return (x + (align - 1)) & ~(align - 1);
395 tlsf_assert(0 == (align & (align - 1)) &&
"must align to a power of two");
396 return x - (x & (align - 1));
400 const tlsfptr_t aligned = (
tlsf_cast(tlsfptr_t, ptr) + (align - 1)) & ~(align - 1);
401 tlsf_assert(0 == (align & (align - 1)) &&
"must align to a power of two");
411 if (size && size < block_size_max) {
412 const size_t aligned =
align_up(size, align);
413 adjust =
tlsf_max(aligned, block_size_min);
455 unsigned int sl_map = control->
sl_bitmap[fl] & (~0U << sl);
458 const unsigned int fl_map = control->
fl_bitmap & (~0U << (fl + 1));
468 tlsf_assert(sl_map &&
"internal error - second level bitmap is null");
473 return control->
blocks[fl][sl];
480 tlsf_assert(prev &&
"prev_free field can not be null");
481 tlsf_assert(next &&
"next_free field can not be null");
486 if (control->
blocks[fl][sl] == block) {
487 control->
blocks[fl][sl] = next;
504 tlsf_assert(current &&
"free list cannot have a null entry");
505 tlsf_assert(block &&
"cannot insert a null entry into the free list");
511 "block not aligned properly");
516 control->
blocks[fl][sl] = block;
548 "remaining block not aligned properly");
573 tlsf_assert(prev &&
"prev physical block can't be null");
585 tlsf_assert(next &&
"next physical block can't be null");
626 remaining_block =
block_split(block, size - block_header_overhead);
633 return remaining_block;
695 #define tlsf_insist(x) \
708 const size_t this_block_size =
block_size(block);
713 tlsf_insist(size == this_block_size &&
"block size incorrect");
728 const int fl_map = control->
fl_bitmap & (1 << i);
729 const int sl_list = control->
sl_bitmap[i];
730 const int sl_map = sl_list & (1 << j);
735 tlsf_insist(!sl_map &&
"second-level map must be null");
744 tlsf_insist(sl_list &&
"no free blocks in second-level map");
756 tlsf_insist(fli == i && sli == j &&
"block size indexed in wrong list");
757 block = block->next_free;
769 printf(
"\t%p %s size: %x (%p)\n",
771 used ?
"used" :
"free",
844 printf(
"tlsf_add_pool: Memory must be aligned by %u bytes.\n", (
unsigned int)ALIGN_SIZE);
848 if (pool_bytes < block_size_min || pool_bytes > block_size_max) {
849 #if defined(TLSF_64BIT)
850 printf(
"tlsf_add_pool: Memory size must be between 0x%x and 0x%x00 bytes.\n",
851 (
unsigned int)(pool_overhead + block_size_min),
852 (
unsigned int)((pool_overhead + block_size_max) / 256));
854 printf(
"tlsf_add_pool: Memory size must be between %u and %u bytes.\n",
855 (
unsigned int)(pool_overhead + block_size_min),
856 (
unsigned int)(pool_overhead + block_size_max));
904 rv += (
tlsf_ffs(0) == -1) ? 0 : 0x1;
905 rv += (
tlsf_fls(0) == -1) ? 0 : 0x2;
908 rv += (
tlsf_ffs(0x80000000) == 31) ? 0 : 0x10;
909 rv += (
tlsf_ffs(0x80008000) == 15) ? 0 : 0x20;
910 rv += (
tlsf_fls(0x80000008) == 31) ? 0 : 0x40;
911 rv += (
tlsf_fls(0x7FFFFFFF) == 30) ? 0 : 0x80;
913 #if defined(TLSF_64BIT)
920 printf(
"test_ffs_fls: %x ffs/fls tests failed.\n", rv);
928 if (test_ffs_fls()) {
934 printf(
"tlsf_create: Memory must be aligned to %u bytes.\n", (
unsigned int)ALIGN_SIZE);
988 ((
char*)ptr - (
char*)block
1017 if (ptr && size == 0) {
1037 if (adjust > cursize && (!
block_is_free(next) || adjust > combined)) {
1040 const size_t minsize =
tlsf_min(cursize, size);
1041 memcpy(p, ptr, minsize);
1048 if (adjust > cursize) {
static void block_set_size(block_header_t *block, size_t size)
struct block_header_t block_header_t
static block_header_t * block_from_ptr(const void *ptr)
static void remove_free_block(control_t *control, block_header_t *block, int fl, int sl)
static block_header_t * block_split(block_header_t *block, size_t size)
static void block_set_used(block_header_t *block)
void tlsf_walk_pool(pool_t pool, tlsf_walker walker, void *user)
static void block_mark_as_used(block_header_t *block)
static const size_t block_start_offset
static block_header_t * block_next(const block_header_t *block)
struct control_t control_t
static size_t align_up(size_t x, size_t align)
tlsf_decl int tlsf_ffs(unsigned int word)
tlsf_decl int tlsf_fls(unsigned int word)
int tlsf_check(tlsf_t tlsf)
static const size_t block_header_free_bit
block_header_t * blocks[FL_INDEX_COUNT][SL_INDEX_COUNT]
static block_header_t * block_trim_free_leading(control_t *control, block_header_t *block, size_t size)
static int block_can_split(block_header_t *block, size_t size)
#define tlsf_static_assert(exp)
static block_header_t * block_absorb(block_header_t *prev, block_header_t *block)
#define TLSF_INCREASE_REAL_USED(control, increment)
size_t tlsf_alloc_overhead(void)
static void block_remove(control_t *control, block_header_t *block)
static void block_set_prev_free(block_header_t *block)
static void block_mark_as_free(block_header_t *block)
static const size_t block_header_prev_free_bit
block_header_t block_null
void tlsf_destroy(tlsf_t tlsf)
static void * align_ptr(const void *ptr, size_t align)
size_t tlsf_block_size_min(void)
static block_header_t * offset_to_block(const void *ptr, size_t size)
#define TLSF_INCREASE_FRAGMENTS(control)
void tlsf_free(tlsf_t tlsf, void *ptr)
size_t tlsf_align_size(void)
pool_t tlsf_get_pool(tlsf_t tlsf)
static int block_is_free(const block_header_t *block)
size_t tlsf_pool_overhead(void)
unsigned int sl_bitmap[FL_INDEX_COUNT]
static size_t align_down(size_t x, size_t align)
static void mapping_insert(size_t size, int *fli, int *sli)
static void block_set_prev_used(block_header_t *block)
static int block_is_last(const block_header_t *block)
void * tlsf_mallocxz(tlsf_t tlsf, size_t bytes)
static void block_set_free(block_header_t *block)
static void mapping_search(size_t size, int *fli, int *sli)
static size_t adjust_request_size(size_t size, size_t align)
static size_t block_size(const block_header_t *block)
tlsf_t tlsf_create_with_pool(void *mem, size_t bytes)
static block_header_t * block_prev(const block_header_t *block)
#define tlsf_cast(t, exp)
struct integrity_t integrity_t
static block_header_t * search_suitable_block(control_t *control, int *fli, int *sli)
static void * block_prepare_used(control_t *control, block_header_t *block, size_t size)
pool_t tlsf_add_pool(tlsf_t tlsf, void *mem, size_t bytes)
size_t tlsf_block_size_max(void)
int tlsf_check_pool(pool_t pool)
static void * block_to_ptr(const block_header_t *block)
static int block_is_prev_free(const block_header_t *block)
static const size_t block_header_overhead
static void control_construct(control_t *control)
void(* tlsf_walker)(void *ptr, size_t size, int used, void *user)
static void integrity_walker(void *ptr, size_t size, int used, void *user)
static void block_trim_free(control_t *control, block_header_t *block, size_t size)
static block_header_t * block_locate_free(control_t *control, size_t size)
static block_header_t * block_merge_next(control_t *control, block_header_t *block)
tlsf_t tlsf_create(void *mem)
static void block_insert(control_t *control, block_header_t *block)
void * tlsf_malloc(tlsf_t tlsf, size_t bytes)
tlsf_decl int tlsf_fls_generic(unsigned int word)
static void default_walker(void *ptr, size_t size, int used, void *user)
size_t tlsf_block_size(void *ptr)
static void block_trim_used(control_t *control, block_header_t *block, size_t size)
static block_header_t * block_link_next(block_header_t *block)
static const size_t block_size_max
void * tlsf_reallocxf(tlsf_t tlsf, void *ptr, size_t size)
static block_header_t * block_merge_prev(control_t *control, block_header_t *block)
static const size_t block_size_min
void * tlsf_realloc(tlsf_t tlsf, void *ptr, size_t size)
static void insert_free_block(control_t *control, block_header_t *block, int fl, int sl)
void tlsf_remove_pool(tlsf_t tlsf, pool_t pool)