2 * Two Levels Segregate Fit memory allocator (TLSF)
5 * Written by Miguel Masmano Tello <mimastel@doctor.upv.es>
7 * Thanks to Ismael Ripoll for his suggestions and reviews
9 * Copyright (C) 2008, 2007, 2006, 2005, 2004
11 * This code is released using a dual license strategy: GPL/LGPL
12 * You can choose the licence that better fits your requirements.
14 * Released under the terms of the GNU General Public License Version 2.0
15 * Released under the terms of the GNU Lesser General Public License Version 2.1
22 * (Jul 28 2007) Herman ten Brugge <hermantenbrugge@home.nl>:
24 * - Add 64 bit support. It now runs on x86_64 and solaris64.
25 * - I also tested this on vxworks/32and solaris/32 and i386/32 processors.
26 * - Remove assembly code. I could not measure any performance difference
27 * on my core2 processor. This also makes the code more portable.
28 * - Moved defines/typedefs from tlsf.h to tlsf.c
29 * - Changed MIN_BLOCK_SIZE to sizeof (free_ptr_t) and BHDR_OVERHEAD to
30 * (sizeof (bhdr_t) - MIN_BLOCK_SIZE). This does not change the fact
31 * that the minumum size is still sizeof
33 * - Changed all C++ comment style to C style. (// -> /.* ... *./)
34 * - Used ls_bit instead of ffs and ms_bit instead of fls. I did this to
35 * avoid confusion with the standard ffs function which returns
37 * - Created set_bit/clear_bit fuctions because they are not present
39 * - Added locking support + extra file target.h to show how to use it.
40 * - Added get_used_size function (REMOVED in 2.4)
41 * - Added rtl_realloc and rtl_calloc function
42 * - Implemented realloc clever support.
43 * - Added some test code in the example directory.
46 * (Oct 23 2006) Adam Scislowicz:
48 * - Support for ARMv5 implemented
52 /*#define USE_SBRK (0) */
53 /*#define USE_MMAP (0) */
58 #ifndef TLSF_USE_LOCKS
59 #define TLSF_USE_LOCKS (0)
62 #ifndef TLSF_STATISTIC
63 #define TLSF_STATISTIC (0)
78 #define TLSF_CREATE_LOCK(_unused_) do{}while(0)
79 #define TLSF_DESTROY_LOCK(_unused_) do{}while(0)
80 #define TLSF_ACQUIRE_LOCK(_unused_) do{}while(0)
81 #define TLSF_RELEASE_LOCK(_unused_) do{}while(0)
85 #define TLSF_ADD_SIZE(tlsf, b) do { \
86 tlsf->used_size += (b->size & BLOCK_SIZE) + BHDR_OVERHEAD; \
87 if (tlsf->used_size > tlsf->max_size) \
88 tlsf->max_size = tlsf->used_size; \
91 #define TLSF_REMOVE_SIZE(tlsf, b) do { \
92 tlsf->used_size -= (b->size & BLOCK_SIZE) + BHDR_OVERHEAD; \
95 #define TLSF_ADD_SIZE(tlsf, b) do{}while(0)
96 #define TLSF_REMOVE_SIZE(tlsf, b) do{}while(0)
99 #if USE_MMAP || USE_SBRK
104 #include <sys/mman.h>
110 #if !defined(__GNUC__)
116 /* The debug functions only can be used when _DEBUG_TLSF_ is set. */
118 #define _DEBUG_TLSF_ (0)
121 /*************************************************************************/
122 /* Definition of the structures used by TLSF */
125 /* Some IMPORTANT TLSF parameters */
126 /* Unlike the preview TLSF versions, now they are statics */
127 #define BLOCK_ALIGN (sizeof(void *) * 2)
130 #define MAX_LOG2_SLI (5)
131 #define MAX_SLI (1 << MAX_LOG2_SLI) /* MAX_SLI = 2^MAX_LOG2_SLI */
133 #define FLI_OFFSET (6) /* tlsf structure just will manage blocks bigger */
135 #define SMALL_BLOCK (128)
136 #define REAL_FLI (MAX_FLI - FLI_OFFSET)
137 #define MIN_BLOCK_SIZE (sizeof (free_ptr_t))
138 #define BHDR_OVERHEAD (sizeof (bhdr_t) - MIN_BLOCK_SIZE)
139 #define TLSF_SIGNATURE (0x2A59FA59)
141 #define PTR_MASK (sizeof(void *) - 1)
142 #define BLOCK_SIZE (0xFFFFFFFF - PTR_MASK)
144 #define GET_NEXT_BLOCK(_addr, _r) ((bhdr_t *) ((char *) (_addr) + (_r)))
145 #define MEM_ALIGN ((BLOCK_ALIGN) - 1)
146 #define ROUNDUP_SIZE(_r) (((_r) + MEM_ALIGN) & ~MEM_ALIGN)
147 #define ROUNDDOWN_SIZE(_r) ((_r) & ~MEM_ALIGN)
148 #define ROUNDUP(_x, _v) ((((~(_x)) + 1) & ((_v)-1)) + (_x))
150 #define BLOCK_STATE (0x1)
151 #define PREV_STATE (0x2)
153 /* bit 0 of the block size */
154 #define FREE_BLOCK (0x1)
155 #define USED_BLOCK (0x0)
157 /* bit 1 of the block size */
158 #define PREV_FREE (0x2)
159 #define PREV_USED (0x0)
162 #define DEFAULT_AREA_SIZE (1024*10)
165 #define PAGE_SIZE (getpagesize())
168 #if defined(ROCKBOX) && (CONFIG_PLATFORM & PLATFORM_HOSTED) && defined(DEBUG) \
170 int printf(const char* fmt
, ...);
171 #define PRINT_MSG(fmt, args...) printf(fmt, ## args)
172 #define ERROR_MSG(fmt, args...) printf(fmt, ## args)
174 #define PRINT_MSG(fmt, args...)
175 #define ERROR_MSG(fmt, args...)
178 typedef unsigned int u32_t
; /* NOTE: Make sure that this type is 4 bytes long on your computer */
179 typedef unsigned char u8_t
; /* NOTE: Make sure that this type is 1 byte on your computer */
181 typedef struct free_ptr_struct
{
182 struct bhdr_struct
*prev
;
183 struct bhdr_struct
*next
;
186 typedef struct bhdr_struct
{
187 /* This pointer is just valid if the first bit of size is set */
188 struct bhdr_struct
*prev_hdr
;
189 /* The size is stored in bytes */
190 size_t size
; /* bit 0 indicates whether the block is used and */
191 /* bit 1 allows to know whether the previous block is free */
193 struct free_ptr_struct free_ptr
;
194 u8_t buffer
[1]; /*sizeof(struct free_ptr_struct)]; */
198 /* This structure is embedded at the beginning of each area, giving us
199 * enough information to cope with a set of areas */
201 typedef struct area_info_struct
{
203 struct area_info_struct
*next
;
206 typedef struct TLSF_struct
{
207 /* the TLSF's structure signature */
208 u32_t tlsf_signature
;
215 /* These can not be calculated outside tlsf because we
216 * do not know the sizes when freeing/reallocing memory. */
221 /* A linked list holding all the existing areas */
222 area_info_t
*area_head
;
224 /* the first-level bitmap */
225 /* This array should have a size of REAL_FLI bits */
228 /* the second-level bitmap */
229 u32_t sl_bitmap
[REAL_FLI
];
231 bhdr_t
*matrix
[REAL_FLI
][MAX_SLI
];
235 /******************************************************************/
236 /************** Helping functions **************************/
237 /******************************************************************/
238 static __inline__
void set_bit(int nr
, u32_t
* addr
);
239 static __inline__
void clear_bit(int nr
, u32_t
* addr
);
240 static __inline__
int ls_bit(int x
);
241 static __inline__
int ms_bit(int x
);
242 static __inline__
void MAPPING_SEARCH(size_t * _r
, int *_fl
, int *_sl
);
243 static __inline__
void MAPPING_INSERT(size_t _r
, int *_fl
, int *_sl
);
244 static __inline__ bhdr_t
*FIND_SUITABLE_BLOCK(tlsf_t
* _tlsf
, int *_fl
, int *_sl
);
245 static __inline__ bhdr_t
*process_area(void *area
, size_t size
);
246 #if USE_SBRK || USE_MMAP
247 static __inline__
void *get_new_area(size_t * size
);
250 static const int table
[] = {
251 -1, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4,
254 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
257 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
260 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
263 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
266 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
269 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
272 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
277 static __inline__
int ls_bit(int i
)
280 unsigned int x
= i
& -i
;
282 a
= x
<= 0xffff ? (x
<= 0xff ? 0 : 8) : (x
<= 0xffffff ? 16 : 24);
283 return table
[x
>> a
] + a
;
286 static __inline__
int ms_bit(int i
)
289 unsigned int x
= (unsigned int) i
;
291 a
= x
<= 0xffff ? (x
<= 0xff ? 0 : 8) : (x
<= 0xffffff ? 16 : 24);
292 return table
[x
>> a
] + a
;
295 static __inline__
void set_bit(int nr
, u32_t
* addr
)
297 addr
[nr
>> 5] |= 1 << (nr
& 0x1f);
300 static __inline__
void clear_bit(int nr
, u32_t
* addr
)
302 addr
[nr
>> 5] &= ~(1 << (nr
& 0x1f));
305 static __inline__
void MAPPING_SEARCH(size_t * _r
, int *_fl
, int *_sl
)
309 if (*_r
< SMALL_BLOCK
) {
311 *_sl
= *_r
/ (SMALL_BLOCK
/ MAX_SLI
);
313 _t
= (1 << (ms_bit(*_r
) - MAX_LOG2_SLI
)) - 1;
316 *_sl
= (*_r
>> (*_fl
- MAX_LOG2_SLI
)) - MAX_SLI
;
318 /*if ((*_fl -= FLI_OFFSET) < 0) // FL wil be always >0!
325 static __inline__
void MAPPING_INSERT(size_t _r
, int *_fl
, int *_sl
)
327 if (_r
< SMALL_BLOCK
) {
329 *_sl
= _r
/ (SMALL_BLOCK
/ MAX_SLI
);
332 *_sl
= (_r
>> (*_fl
- MAX_LOG2_SLI
)) - MAX_SLI
;
338 static __inline__ bhdr_t
*FIND_SUITABLE_BLOCK(tlsf_t
* _tlsf
, int *_fl
, int *_sl
)
340 u32_t _tmp
= _tlsf
->sl_bitmap
[*_fl
] & (~0 << *_sl
);
345 _b
= _tlsf
->matrix
[*_fl
][*_sl
];
347 *_fl
= ls_bit(_tlsf
->fl_bitmap
& (~0 << (*_fl
+ 1)));
348 if (*_fl
> 0) { /* likely */
349 *_sl
= ls_bit(_tlsf
->sl_bitmap
[*_fl
]);
350 _b
= _tlsf
->matrix
[*_fl
][*_sl
];
357 #define EXTRACT_BLOCK_HDR(_b, _tlsf, _fl, _sl) do { \
358 _tlsf -> matrix [_fl] [_sl] = _b -> ptr.free_ptr.next; \
359 if (_tlsf -> matrix[_fl][_sl]) \
360 _tlsf -> matrix[_fl][_sl] -> ptr.free_ptr.prev = NULL; \
362 clear_bit (_sl, &_tlsf -> sl_bitmap [_fl]); \
363 if (!_tlsf -> sl_bitmap [_fl]) \
364 clear_bit (_fl, &_tlsf -> fl_bitmap); \
366 _b -> ptr.free_ptr.prev = NULL; \
367 _b -> ptr.free_ptr.next = NULL; \
371 #define EXTRACT_BLOCK(_b, _tlsf, _fl, _sl) do { \
372 if (_b -> ptr.free_ptr.next) \
373 _b -> ptr.free_ptr.next -> ptr.free_ptr.prev = _b -> ptr.free_ptr.prev; \
374 if (_b -> ptr.free_ptr.prev) \
375 _b -> ptr.free_ptr.prev -> ptr.free_ptr.next = _b -> ptr.free_ptr.next; \
376 if (_tlsf -> matrix [_fl][_sl] == _b) { \
377 _tlsf -> matrix [_fl][_sl] = _b -> ptr.free_ptr.next; \
378 if (!_tlsf -> matrix [_fl][_sl]) { \
379 clear_bit (_sl, &_tlsf -> sl_bitmap[_fl]); \
380 if (!_tlsf -> sl_bitmap [_fl]) \
381 clear_bit (_fl, &_tlsf -> fl_bitmap); \
384 _b -> ptr.free_ptr.prev = NULL; \
385 _b -> ptr.free_ptr.next = NULL; \
388 #define INSERT_BLOCK(_b, _tlsf, _fl, _sl) do { \
389 _b -> ptr.free_ptr.prev = NULL; \
390 _b -> ptr.free_ptr.next = _tlsf -> matrix [_fl][_sl]; \
391 if (_tlsf -> matrix [_fl][_sl]) \
392 _tlsf -> matrix [_fl][_sl] -> ptr.free_ptr.prev = _b; \
393 _tlsf -> matrix [_fl][_sl] = _b; \
394 set_bit (_sl, &_tlsf -> sl_bitmap [_fl]); \
395 set_bit (_fl, &_tlsf -> fl_bitmap); \
398 #if USE_SBRK || USE_MMAP
399 static __inline__
void *get_new_area(size_t * size
)
404 area
= (void *)sbrk(0);
405 if (((void *)sbrk(*size
)) != ((void *) -1))
410 *size
= ROUNDUP(*size
, PAGE_SIZE
);
411 if ((area
= mmap(0, *size
, PROT_READ
| PROT_WRITE
, MAP_PRIVATE
| MAP_ANONYMOUS
, -1, 0)) != MAP_FAILED
)
414 return ((void *) ~0);
418 static __inline__ bhdr_t
*process_area(void *area
, size_t size
)
423 ib
= (bhdr_t
*) area
;
425 (sizeof(area_info_t
) <
426 MIN_BLOCK_SIZE
) ? MIN_BLOCK_SIZE
: ROUNDUP_SIZE(sizeof(area_info_t
)) | USED_BLOCK
| PREV_USED
;
427 b
= (bhdr_t
*) GET_NEXT_BLOCK(ib
->ptr
.buffer
, ib
->size
& BLOCK_SIZE
);
428 b
->size
= ROUNDDOWN_SIZE(size
- 3 * BHDR_OVERHEAD
- (ib
->size
& BLOCK_SIZE
)) | USED_BLOCK
| PREV_USED
;
429 b
->ptr
.free_ptr
.prev
= b
->ptr
.free_ptr
.next
= 0;
430 lb
= GET_NEXT_BLOCK(b
->ptr
.buffer
, b
->size
& BLOCK_SIZE
);
432 lb
->size
= 0 | USED_BLOCK
| PREV_FREE
;
433 ai
= (area_info_t
*) ib
->ptr
.buffer
;
439 /******************************************************************/
440 /******************** Begin of the allocator code *****************/
441 /******************************************************************/
443 static char *mp
= NULL
; /* Default memory pool. */
445 /******************************************************************/
446 size_t init_memory_pool(size_t mem_pool_size
, void *mem_pool
)
448 /******************************************************************/
452 if (!mem_pool
|| !mem_pool_size
|| mem_pool_size
< sizeof(tlsf_t
) + BHDR_OVERHEAD
* 8) {
453 ERROR_MSG("init_memory_pool (): memory_pool invalid\n");
457 if (((unsigned long) mem_pool
& PTR_MASK
)) {
458 ERROR_MSG("init_memory_pool (): mem_pool must be aligned to a word\n");
461 tlsf
= (tlsf_t
*) mem_pool
;
462 /* Check if already initialised */
463 if (tlsf
->tlsf_signature
== TLSF_SIGNATURE
) {
465 b
= GET_NEXT_BLOCK(mp
, ROUNDUP_SIZE(sizeof(tlsf_t
)));
466 return b
->size
& BLOCK_SIZE
;
471 /* Zeroing the memory pool */
472 memset(mem_pool
, 0, sizeof(tlsf_t
));
474 tlsf
->tlsf_signature
= TLSF_SIGNATURE
;
476 TLSF_CREATE_LOCK(&tlsf
->lock
);
478 ib
= process_area(GET_NEXT_BLOCK
479 (mem_pool
, ROUNDUP_SIZE(sizeof(tlsf_t
))), ROUNDDOWN_SIZE(mem_pool_size
- sizeof(tlsf_t
)));
480 b
= GET_NEXT_BLOCK(ib
->ptr
.buffer
, ib
->size
& BLOCK_SIZE
);
481 free_ex(b
->ptr
.buffer
, tlsf
);
482 tlsf
->area_head
= (area_info_t
*) ib
->ptr
.buffer
;
485 tlsf
->used_size
= mem_pool_size
- (b
->size
& BLOCK_SIZE
);
486 tlsf
->max_size
= tlsf
->used_size
;
489 return (b
->size
& BLOCK_SIZE
);
492 /******************************************************************/
493 size_t add_new_area(void *area
, size_t area_size
, void *mem_pool
)
495 /******************************************************************/
496 tlsf_t
*tlsf
= (tlsf_t
*) mem_pool
;
497 area_info_t
*ptr
, *ptr_prev
, *ai
;
498 bhdr_t
*ib0
, *b0
, *lb0
, *ib1
, *b1
, *lb1
, *next_b
;
500 memset(area
, 0, area_size
);
501 ptr
= tlsf
->area_head
;
504 ib0
= process_area(area
, area_size
);
505 b0
= GET_NEXT_BLOCK(ib0
->ptr
.buffer
, ib0
->size
& BLOCK_SIZE
);
506 lb0
= GET_NEXT_BLOCK(b0
->ptr
.buffer
, b0
->size
& BLOCK_SIZE
);
508 /* Before inserting the new area, we have to merge this area with the
509 already existing ones */
512 ib1
= (bhdr_t
*) ((char *) ptr
- BHDR_OVERHEAD
);
513 b1
= GET_NEXT_BLOCK(ib1
->ptr
.buffer
, ib1
->size
& BLOCK_SIZE
);
516 /* Merging the new area with the next physically contigous one */
517 if ((unsigned long) ib1
== (unsigned long) lb0
+ BHDR_OVERHEAD
) {
518 if (tlsf
->area_head
== ptr
) {
519 tlsf
->area_head
= ptr
->next
;
522 ptr_prev
->next
= ptr
->next
;
527 ROUNDDOWN_SIZE((b0
->size
& BLOCK_SIZE
) +
528 (ib1
->size
& BLOCK_SIZE
) + 2 * BHDR_OVERHEAD
) | USED_BLOCK
| PREV_USED
;
536 /* Merging the new area with the previous physically contigous
538 if ((unsigned long) lb1
->ptr
.buffer
== (unsigned long) ib0
) {
539 if (tlsf
->area_head
== ptr
) {
540 tlsf
->area_head
= ptr
->next
;
543 ptr_prev
->next
= ptr
->next
;
548 ROUNDDOWN_SIZE((b0
->size
& BLOCK_SIZE
) +
549 (ib0
->size
& BLOCK_SIZE
) + 2 * BHDR_OVERHEAD
) | USED_BLOCK
| (lb1
->size
& PREV_STATE
);
550 next_b
= GET_NEXT_BLOCK(lb1
->ptr
.buffer
, lb1
->size
& BLOCK_SIZE
);
551 next_b
->prev_hdr
= lb1
;
561 /* Inserting the area in the list of linked areas */
562 ai
= (area_info_t
*) ib0
->ptr
.buffer
;
563 ai
->next
= tlsf
->area_head
;
565 tlsf
->area_head
= ai
;
566 free_ex(b0
->ptr
.buffer
, mem_pool
);
567 return (b0
->size
& BLOCK_SIZE
);
571 /******************************************************************/
572 size_t get_used_size(void *mem_pool
)
574 /******************************************************************/
576 return ((tlsf_t
*) mem_pool
)->used_size
;
585 /******************************************************************/
586 size_t get_max_size(void *mem_pool
)
588 /******************************************************************/
590 return ((tlsf_t
*) mem_pool
)->max_size
;
599 /******************************************************************/
600 void destroy_memory_pool(void *mem_pool
)
602 /******************************************************************/
603 tlsf_t
*tlsf
= (tlsf_t
*) mem_pool
;
605 tlsf
->tlsf_signature
= 0;
607 TLSF_DESTROY_LOCK(&tlsf
->lock
);
612 /******************************************************************/
613 void *tlsf_malloc(size_t size
)
615 /******************************************************************/
618 #if USE_MMAP || USE_SBRK
623 area_size
= sizeof(tlsf_t
) + BHDR_OVERHEAD
* 8; /* Just a safety constant */
624 area_size
= (area_size
> DEFAULT_AREA_SIZE
) ? area_size
: DEFAULT_AREA_SIZE
;
625 area
= get_new_area(&area_size
);
626 if (area
== ((void *) ~0))
627 return NULL
; /* Not enough system memory */
628 init_memory_pool(area_size
, area
);
632 TLSF_ACQUIRE_LOCK(&((tlsf_t
*)mp
)->lock
);
634 ret
= malloc_ex(size
, mp
);
636 TLSF_RELEASE_LOCK(&((tlsf_t
*)mp
)->lock
);
641 /******************************************************************/
642 void tlsf_free(void *ptr
)
644 /******************************************************************/
646 TLSF_ACQUIRE_LOCK(&((tlsf_t
*)mp
)->lock
);
650 TLSF_RELEASE_LOCK(&((tlsf_t
*)mp
)->lock
);
654 /******************************************************************/
655 void *tlsf_realloc(void *ptr
, size_t size
)
657 /******************************************************************/
660 #if USE_MMAP || USE_SBRK
662 return tlsf_malloc(size
);
666 TLSF_ACQUIRE_LOCK(&((tlsf_t
*)mp
)->lock
);
668 ret
= realloc_ex(ptr
, size
, mp
);
670 TLSF_RELEASE_LOCK(&((tlsf_t
*)mp
)->lock
);
675 /******************************************************************/
676 void *tlsf_calloc(size_t nelem
, size_t elem_size
)
678 /******************************************************************/
681 TLSF_ACQUIRE_LOCK(&((tlsf_t
*)mp
)->lock
);
683 ret
= calloc_ex(nelem
, elem_size
, mp
);
685 TLSF_RELEASE_LOCK(&((tlsf_t
*)mp
)->lock
);
690 /******************************************************************/
691 void *malloc_ex(size_t size
, void *mem_pool
)
693 /******************************************************************/
694 tlsf_t
*tlsf
= (tlsf_t
*) mem_pool
;
695 bhdr_t
*b
, *b2
, *next_b
;
699 size
= (size
< MIN_BLOCK_SIZE
) ? MIN_BLOCK_SIZE
: ROUNDUP_SIZE(size
);
701 /* Rounding up the requested size and calculating fl and sl */
702 MAPPING_SEARCH(&size
, &fl
, &sl
);
704 /* Searching a free block, recall that this function changes the values of fl and sl,
705 so they are not longer valid when the function fails */
706 b
= FIND_SUITABLE_BLOCK(tlsf
, &fl
, &sl
);
708 #if USE_MMAP || USE_SBRK
712 /* Growing the pool size when needed */
713 area_size
= size
+ BHDR_OVERHEAD
* 8; /* size plus enough room for the requered headers. */
714 area_size
= (area_size
> DEFAULT_AREA_SIZE
) ? area_size
: DEFAULT_AREA_SIZE
;
715 area
= get_new_area(&area_size
); /* Call sbrk or mmap */
716 if (area
== ((void *) ~0))
717 return NULL
; /* Not enough system memory */
718 add_new_area(area
, area_size
, mem_pool
);
719 /* Rounding up the requested size and calculating fl and sl */
720 MAPPING_SEARCH(&size
, &fl
, &sl
);
721 /* Searching a free block */
722 b
= FIND_SUITABLE_BLOCK(tlsf
, &fl
, &sl
);
726 return NULL
; /* Not found */
728 EXTRACT_BLOCK_HDR(b
, tlsf
, fl
, sl
);
731 next_b
= GET_NEXT_BLOCK(b
->ptr
.buffer
, b
->size
& BLOCK_SIZE
);
732 /* Should the block be split? */
733 tmp_size
= (b
->size
& BLOCK_SIZE
) - size
;
734 if (tmp_size
>= sizeof(bhdr_t
)) {
735 tmp_size
-= BHDR_OVERHEAD
;
736 b2
= GET_NEXT_BLOCK(b
->ptr
.buffer
, size
);
737 b2
->size
= tmp_size
| FREE_BLOCK
| PREV_USED
;
738 next_b
->prev_hdr
= b2
;
739 MAPPING_INSERT(tmp_size
, &fl
, &sl
);
740 INSERT_BLOCK(b2
, tlsf
, fl
, sl
);
742 b
->size
= size
| (b
->size
& PREV_STATE
);
744 next_b
->size
&= (~PREV_FREE
);
745 b
->size
&= (~FREE_BLOCK
); /* Now it's used */
748 TLSF_ADD_SIZE(tlsf
, b
);
750 return (void *) b
->ptr
.buffer
;
753 /******************************************************************/
754 void free_ex(void *ptr
, void *mem_pool
)
756 /******************************************************************/
757 tlsf_t
*tlsf
= (tlsf_t
*) mem_pool
;
764 b
= (bhdr_t
*) ((char *) ptr
- BHDR_OVERHEAD
);
765 b
->size
|= FREE_BLOCK
;
767 TLSF_REMOVE_SIZE(tlsf
, b
);
769 b
->ptr
.free_ptr
.prev
= NULL
;
770 b
->ptr
.free_ptr
.next
= NULL
;
771 tmp_b
= GET_NEXT_BLOCK(b
->ptr
.buffer
, b
->size
& BLOCK_SIZE
);
772 if (tmp_b
->size
& FREE_BLOCK
) {
773 MAPPING_INSERT(tmp_b
->size
& BLOCK_SIZE
, &fl
, &sl
);
774 EXTRACT_BLOCK(tmp_b
, tlsf
, fl
, sl
);
775 b
->size
+= (tmp_b
->size
& BLOCK_SIZE
) + BHDR_OVERHEAD
;
777 if (b
->size
& PREV_FREE
) {
779 MAPPING_INSERT(tmp_b
->size
& BLOCK_SIZE
, &fl
, &sl
);
780 EXTRACT_BLOCK(tmp_b
, tlsf
, fl
, sl
);
781 tmp_b
->size
+= (b
->size
& BLOCK_SIZE
) + BHDR_OVERHEAD
;
784 MAPPING_INSERT(b
->size
& BLOCK_SIZE
, &fl
, &sl
);
785 INSERT_BLOCK(b
, tlsf
, fl
, sl
);
787 tmp_b
= GET_NEXT_BLOCK(b
->ptr
.buffer
, b
->size
& BLOCK_SIZE
);
788 tmp_b
->size
|= PREV_FREE
;
792 /******************************************************************/
793 void *realloc_ex(void *ptr
, size_t new_size
, void *mem_pool
)
795 /******************************************************************/
796 tlsf_t
*tlsf
= (tlsf_t
*) mem_pool
;
799 bhdr_t
*b
, *tmp_b
, *next_b
;
805 return (void *) malloc_ex(new_size
, mem_pool
);
808 } else if (!new_size
) {
809 free_ex(ptr
, mem_pool
);
813 b
= (bhdr_t
*) ((char *) ptr
- BHDR_OVERHEAD
);
814 next_b
= GET_NEXT_BLOCK(b
->ptr
.buffer
, b
->size
& BLOCK_SIZE
);
815 new_size
= (new_size
< MIN_BLOCK_SIZE
) ? MIN_BLOCK_SIZE
: ROUNDUP_SIZE(new_size
);
816 tmp_size
= (b
->size
& BLOCK_SIZE
);
817 if (new_size
<= tmp_size
) {
818 TLSF_REMOVE_SIZE(tlsf
, b
);
819 if (next_b
->size
& FREE_BLOCK
) {
820 MAPPING_INSERT(next_b
->size
& BLOCK_SIZE
, &fl
, &sl
);
821 EXTRACT_BLOCK(next_b
, tlsf
, fl
, sl
);
822 tmp_size
+= (next_b
->size
& BLOCK_SIZE
) + BHDR_OVERHEAD
;
823 next_b
= GET_NEXT_BLOCK(next_b
->ptr
.buffer
, next_b
->size
& BLOCK_SIZE
);
824 /* We allways reenter this free block because tmp_size will
825 be greater then sizeof (bhdr_t) */
827 tmp_size
-= new_size
;
828 if (tmp_size
>= sizeof(bhdr_t
)) {
829 tmp_size
-= BHDR_OVERHEAD
;
830 tmp_b
= GET_NEXT_BLOCK(b
->ptr
.buffer
, new_size
);
831 tmp_b
->size
= tmp_size
| FREE_BLOCK
| PREV_USED
;
832 next_b
->prev_hdr
= tmp_b
;
833 next_b
->size
|= PREV_FREE
;
834 MAPPING_INSERT(tmp_size
, &fl
, &sl
);
835 INSERT_BLOCK(tmp_b
, tlsf
, fl
, sl
);
836 b
->size
= new_size
| (b
->size
& PREV_STATE
);
838 TLSF_ADD_SIZE(tlsf
, b
);
839 return (void *) b
->ptr
.buffer
;
841 if ((next_b
->size
& FREE_BLOCK
)) {
842 if (new_size
<= (tmp_size
+ (next_b
->size
& BLOCK_SIZE
))) {
843 TLSF_REMOVE_SIZE(tlsf
, b
);
844 MAPPING_INSERT(next_b
->size
& BLOCK_SIZE
, &fl
, &sl
);
845 EXTRACT_BLOCK(next_b
, tlsf
, fl
, sl
);
846 b
->size
+= (next_b
->size
& BLOCK_SIZE
) + BHDR_OVERHEAD
;
847 next_b
= GET_NEXT_BLOCK(b
->ptr
.buffer
, b
->size
& BLOCK_SIZE
);
848 next_b
->prev_hdr
= b
;
849 next_b
->size
&= ~PREV_FREE
;
850 tmp_size
= (b
->size
& BLOCK_SIZE
) - new_size
;
851 if (tmp_size
>= sizeof(bhdr_t
)) {
852 tmp_size
-= BHDR_OVERHEAD
;
853 tmp_b
= GET_NEXT_BLOCK(b
->ptr
.buffer
, new_size
);
854 tmp_b
->size
= tmp_size
| FREE_BLOCK
| PREV_USED
;
855 next_b
->prev_hdr
= tmp_b
;
856 next_b
->size
|= PREV_FREE
;
857 MAPPING_INSERT(tmp_size
, &fl
, &sl
);
858 INSERT_BLOCK(tmp_b
, tlsf
, fl
, sl
);
859 b
->size
= new_size
| (b
->size
& PREV_STATE
);
861 TLSF_ADD_SIZE(tlsf
, b
);
862 return (void *) b
->ptr
.buffer
;
866 if (!(ptr_aux
= malloc_ex(new_size
, mem_pool
)))
869 cpsize
= ((b
->size
& BLOCK_SIZE
) > new_size
) ? new_size
: (b
->size
& BLOCK_SIZE
);
871 memcpy(ptr_aux
, ptr
, cpsize
);
873 free_ex(ptr
, mem_pool
);
878 /******************************************************************/
879 void *calloc_ex(size_t nelem
, size_t elem_size
, void *mem_pool
)
881 /******************************************************************/
884 if (nelem
<= 0 || elem_size
<= 0)
887 if (!(ptr
= malloc_ex(nelem
* elem_size
, mem_pool
)))
889 memset(ptr
, 0, nelem
* elem_size
);
898 /*************** DEBUG FUNCTIONS **************/
900 /* The following functions have been designed to ease the debugging of */
901 /* the TLSF structure. For non-developing purposes, it may be they */
902 /* haven't too much worth. To enable them, _DEBUG_TLSF_ must be set. */
904 extern void dump_memory_region(unsigned char *mem_ptr
, unsigned int size
);
905 extern void print_block(bhdr_t
* b
);
906 extern void print_tlsf(tlsf_t
* tlsf
);
907 void print_all_blocks(tlsf_t
* tlsf
);
909 void dump_memory_region(unsigned char *mem_ptr
, unsigned int size
)
912 unsigned long begin
= (unsigned long) mem_ptr
;
913 unsigned long end
= (unsigned long) mem_ptr
+ size
;
923 PRINT_MSG("\nMemory region dumped: 0x%lx - 0x%lx\n\n", begin
, end
);
926 PRINT_MSG("0x%lx ", begin
);
928 while (begin
< end
) {
929 if (((unsigned char *) begin
)[0] == 0)
932 PRINT_MSG("%02x", ((unsigned char *) begin
)[0]);
933 if (((unsigned char *) begin
)[1] == 0)
936 PRINT_MSG("%02x ", ((unsigned char *) begin
)[1]);
940 PRINT_MSG("\n0x%lx ", begin
);
948 void print_block(bhdr_t
* b
)
952 PRINT_MSG(">> [%p] (", b
);
953 if ((b
->size
& BLOCK_SIZE
))
954 PRINT_MSG("%lu bytes, ", (unsigned long) (b
->size
& BLOCK_SIZE
));
956 PRINT_MSG("sentinel, ");
957 if ((b
->size
& BLOCK_STATE
) == FREE_BLOCK
)
958 PRINT_MSG("free [%p, %p], ", b
->ptr
.free_ptr
.prev
, b
->ptr
.free_ptr
.next
);
961 if ((b
->size
& PREV_STATE
) == PREV_FREE
)
962 PRINT_MSG("prev. free [%p])\n", b
->prev_hdr
);
964 PRINT_MSG("prev used)\n");
967 void print_tlsf(tlsf_t
* tlsf
)
972 PRINT_MSG("\nTLSF at %p\n", tlsf
);
974 PRINT_MSG("FL bitmap: 0x%x\n\n", (unsigned) tlsf
->fl_bitmap
);
976 for (i
= 0; i
< REAL_FLI
; i
++) {
977 if (tlsf
->sl_bitmap
[i
])
978 PRINT_MSG("SL bitmap 0x%x\n", (unsigned) tlsf
->sl_bitmap
[i
]);
979 for (j
= 0; j
< MAX_SLI
; j
++) {
980 next
= tlsf
->matrix
[i
][j
];
982 PRINT_MSG("-> [%d][%d]\n", i
, j
);
985 next
= next
->ptr
.free_ptr
.next
;
991 void print_all_blocks(tlsf_t
* tlsf
)
995 PRINT_MSG("\nTLSF at %p\nALL BLOCKS\n\n", tlsf
);
996 ai
= tlsf
->area_head
;
998 next
= (bhdr_t
*) ((char *) ai
- BHDR_OVERHEAD
);
1001 if ((next
->size
& BLOCK_SIZE
))
1002 next
= GET_NEXT_BLOCK(next
->ptr
.buffer
, next
->size
& BLOCK_SIZE
);