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>
109 #if !defined(__GNUC__)
115 /* The debug functions only can be used when _DEBUG_TLSF_ is set. */
117 #define _DEBUG_TLSF_ (0)
120 /*************************************************************************/
121 /* Definition of the structures used by TLSF */
124 /* Some IMPORTANT TLSF parameters */
125 /* Unlike the preview TLSF versions, now they are statics */
126 #define BLOCK_ALIGN (sizeof(void *) * 2)
129 #define MAX_LOG2_SLI (5)
130 #define MAX_SLI (1 << MAX_LOG2_SLI) /* MAX_SLI = 2^MAX_LOG2_SLI */
132 #define FLI_OFFSET (6) /* tlsf structure just will manage blocks bigger */
134 #define SMALL_BLOCK (128)
135 #define REAL_FLI (MAX_FLI - FLI_OFFSET)
136 #define MIN_BLOCK_SIZE (sizeof (free_ptr_t))
137 #define BHDR_OVERHEAD (sizeof (bhdr_t) - MIN_BLOCK_SIZE)
138 #define TLSF_SIGNATURE (0x2A59FA59)
140 #define PTR_MASK (sizeof(void *) - 1)
141 #define BLOCK_SIZE (0xFFFFFFFF - PTR_MASK)
143 #define GET_NEXT_BLOCK(_addr, _r) ((bhdr_t *) ((char *) (_addr) + (_r)))
144 #define MEM_ALIGN ((BLOCK_ALIGN) - 1)
145 #define ROUNDUP_SIZE(_r) (((_r) + MEM_ALIGN) & ~MEM_ALIGN)
146 #define ROUNDDOWN_SIZE(_r) ((_r) & ~MEM_ALIGN)
147 #define ROUNDUP(_x, _v) ((((~(_x)) + 1) & ((_v)-1)) + (_x))
149 #define BLOCK_STATE (0x1)
150 #define PREV_STATE (0x2)
152 /* bit 0 of the block size */
153 #define FREE_BLOCK (0x1)
154 #define USED_BLOCK (0x0)
156 /* bit 1 of the block size */
157 #define PREV_FREE (0x2)
158 #define PREV_USED (0x0)
161 #define DEFAULT_AREA_SIZE (1024*10)
164 #define PAGE_SIZE (getpagesize())
167 #if defined(ROCKBOX) && defined(SIMULATOR) || !defined(ROCKBOX)
168 int printf(const char* fmt
, ...);
169 #define PRINT_MSG(fmt, args...) printf(fmt, ## args)
170 #define ERROR_MSG(fmt, args...) printf(fmt, ## args)
172 #define PRINT_MSG(fmt, args...)
173 #define ERROR_MSG(fmt, args...)
176 typedef unsigned int u32_t
; /* NOTE: Make sure that this type is 4 bytes long on your computer */
177 typedef unsigned char u8_t
; /* NOTE: Make sure that this type is 1 byte on your computer */
179 typedef struct free_ptr_struct
{
180 struct bhdr_struct
*prev
;
181 struct bhdr_struct
*next
;
184 typedef struct bhdr_struct
{
185 /* This pointer is just valid if the first bit of size is set */
186 struct bhdr_struct
*prev_hdr
;
187 /* The size is stored in bytes */
188 size_t size
; /* bit 0 indicates whether the block is used and */
189 /* bit 1 allows to know whether the previous block is free */
191 struct free_ptr_struct free_ptr
;
192 u8_t buffer
[1]; /*sizeof(struct free_ptr_struct)]; */
196 /* This structure is embedded at the beginning of each area, giving us
197 * enough information to cope with a set of areas */
199 typedef struct area_info_struct
{
201 struct area_info_struct
*next
;
204 typedef struct TLSF_struct
{
205 /* the TLSF's structure signature */
206 u32_t tlsf_signature
;
213 /* These can not be calculated outside tlsf because we
214 * do not know the sizes when freeing/reallocing memory. */
219 /* A linked list holding all the existing areas */
220 area_info_t
*area_head
;
222 /* the first-level bitmap */
223 /* This array should have a size of REAL_FLI bits */
226 /* the second-level bitmap */
227 u32_t sl_bitmap
[REAL_FLI
];
229 bhdr_t
*matrix
[REAL_FLI
][MAX_SLI
];
233 /******************************************************************/
234 /************** Helping functions **************************/
235 /******************************************************************/
236 static __inline__
void set_bit(int nr
, u32_t
* addr
);
237 static __inline__
void clear_bit(int nr
, u32_t
* addr
);
238 static __inline__
int ls_bit(int x
);
239 static __inline__
int ms_bit(int x
);
240 static __inline__
void MAPPING_SEARCH(size_t * _r
, int *_fl
, int *_sl
);
241 static __inline__
void MAPPING_INSERT(size_t _r
, int *_fl
, int *_sl
);
242 static __inline__ bhdr_t
*FIND_SUITABLE_BLOCK(tlsf_t
* _tlsf
, int *_fl
, int *_sl
);
243 static __inline__ bhdr_t
*process_area(void *area
, size_t size
);
244 #if USE_SBRK || USE_MMAP
245 static __inline__
void *get_new_area(size_t * size
);
248 static const int table
[] = {
249 -1, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4,
252 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
255 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
258 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
261 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
264 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
267 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
270 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
275 static __inline__
int ls_bit(int i
)
278 unsigned int x
= i
& -i
;
280 a
= x
<= 0xffff ? (x
<= 0xff ? 0 : 8) : (x
<= 0xffffff ? 16 : 24);
281 return table
[x
>> a
] + a
;
284 static __inline__
int ms_bit(int i
)
287 unsigned int x
= (unsigned int) i
;
289 a
= x
<= 0xffff ? (x
<= 0xff ? 0 : 8) : (x
<= 0xffffff ? 16 : 24);
290 return table
[x
>> a
] + a
;
293 static __inline__
void set_bit(int nr
, u32_t
* addr
)
295 addr
[nr
>> 5] |= 1 << (nr
& 0x1f);
298 static __inline__
void clear_bit(int nr
, u32_t
* addr
)
300 addr
[nr
>> 5] &= ~(1 << (nr
& 0x1f));
303 static __inline__
void MAPPING_SEARCH(size_t * _r
, int *_fl
, int *_sl
)
307 if (*_r
< SMALL_BLOCK
) {
309 *_sl
= *_r
/ (SMALL_BLOCK
/ MAX_SLI
);
311 _t
= (1 << (ms_bit(*_r
) - MAX_LOG2_SLI
)) - 1;
314 *_sl
= (*_r
>> (*_fl
- MAX_LOG2_SLI
)) - MAX_SLI
;
316 /*if ((*_fl -= FLI_OFFSET) < 0) // FL wil be always >0!
323 static __inline__
void MAPPING_INSERT(size_t _r
, int *_fl
, int *_sl
)
325 if (_r
< SMALL_BLOCK
) {
327 *_sl
= _r
/ (SMALL_BLOCK
/ MAX_SLI
);
330 *_sl
= (_r
>> (*_fl
- MAX_LOG2_SLI
)) - MAX_SLI
;
336 static __inline__ bhdr_t
*FIND_SUITABLE_BLOCK(tlsf_t
* _tlsf
, int *_fl
, int *_sl
)
338 u32_t _tmp
= _tlsf
->sl_bitmap
[*_fl
] & (~0 << *_sl
);
343 _b
= _tlsf
->matrix
[*_fl
][*_sl
];
345 *_fl
= ls_bit(_tlsf
->fl_bitmap
& (~0 << (*_fl
+ 1)));
346 if (*_fl
> 0) { /* likely */
347 *_sl
= ls_bit(_tlsf
->sl_bitmap
[*_fl
]);
348 _b
= _tlsf
->matrix
[*_fl
][*_sl
];
355 #define EXTRACT_BLOCK_HDR(_b, _tlsf, _fl, _sl) do { \
356 _tlsf -> matrix [_fl] [_sl] = _b -> ptr.free_ptr.next; \
357 if (_tlsf -> matrix[_fl][_sl]) \
358 _tlsf -> matrix[_fl][_sl] -> ptr.free_ptr.prev = NULL; \
360 clear_bit (_sl, &_tlsf -> sl_bitmap [_fl]); \
361 if (!_tlsf -> sl_bitmap [_fl]) \
362 clear_bit (_fl, &_tlsf -> fl_bitmap); \
364 _b -> ptr.free_ptr.prev = NULL; \
365 _b -> ptr.free_ptr.next = NULL; \
369 #define EXTRACT_BLOCK(_b, _tlsf, _fl, _sl) do { \
370 if (_b -> ptr.free_ptr.next) \
371 _b -> ptr.free_ptr.next -> ptr.free_ptr.prev = _b -> ptr.free_ptr.prev; \
372 if (_b -> ptr.free_ptr.prev) \
373 _b -> ptr.free_ptr.prev -> ptr.free_ptr.next = _b -> ptr.free_ptr.next; \
374 if (_tlsf -> matrix [_fl][_sl] == _b) { \
375 _tlsf -> matrix [_fl][_sl] = _b -> ptr.free_ptr.next; \
376 if (!_tlsf -> matrix [_fl][_sl]) { \
377 clear_bit (_sl, &_tlsf -> sl_bitmap[_fl]); \
378 if (!_tlsf -> sl_bitmap [_fl]) \
379 clear_bit (_fl, &_tlsf -> fl_bitmap); \
382 _b -> ptr.free_ptr.prev = NULL; \
383 _b -> ptr.free_ptr.next = NULL; \
386 #define INSERT_BLOCK(_b, _tlsf, _fl, _sl) do { \
387 _b -> ptr.free_ptr.prev = NULL; \
388 _b -> ptr.free_ptr.next = _tlsf -> matrix [_fl][_sl]; \
389 if (_tlsf -> matrix [_fl][_sl]) \
390 _tlsf -> matrix [_fl][_sl] -> ptr.free_ptr.prev = _b; \
391 _tlsf -> matrix [_fl][_sl] = _b; \
392 set_bit (_sl, &_tlsf -> sl_bitmap [_fl]); \
393 set_bit (_fl, &_tlsf -> fl_bitmap); \
396 #if USE_SBRK || USE_MMAP
397 static __inline__
void *get_new_area(size_t * size
)
402 area
= (void *)sbrk(0);
403 if (((void *)sbrk(*size
)) != ((void *) -1))
408 *size
= ROUNDUP(*size
, PAGE_SIZE
);
409 if ((area
= mmap(0, *size
, PROT_READ
| PROT_WRITE
, MAP_PRIVATE
| MAP_ANONYMOUS
, -1, 0)) != MAP_FAILED
)
412 return ((void *) ~0);
416 static __inline__ bhdr_t
*process_area(void *area
, size_t size
)
421 ib
= (bhdr_t
*) area
;
423 (sizeof(area_info_t
) <
424 MIN_BLOCK_SIZE
) ? MIN_BLOCK_SIZE
: ROUNDUP_SIZE(sizeof(area_info_t
)) | USED_BLOCK
| PREV_USED
;
425 b
= (bhdr_t
*) GET_NEXT_BLOCK(ib
->ptr
.buffer
, ib
->size
& BLOCK_SIZE
);
426 b
->size
= ROUNDDOWN_SIZE(size
- 3 * BHDR_OVERHEAD
- (ib
->size
& BLOCK_SIZE
)) | USED_BLOCK
| PREV_USED
;
427 b
->ptr
.free_ptr
.prev
= b
->ptr
.free_ptr
.next
= 0;
428 lb
= GET_NEXT_BLOCK(b
->ptr
.buffer
, b
->size
& BLOCK_SIZE
);
430 lb
->size
= 0 | USED_BLOCK
| PREV_FREE
;
431 ai
= (area_info_t
*) ib
->ptr
.buffer
;
437 /******************************************************************/
438 /******************** Begin of the allocator code *****************/
439 /******************************************************************/
441 static char *mp
= NULL
; /* Default memory pool. */
443 /******************************************************************/
444 size_t init_memory_pool(size_t mem_pool_size
, void *mem_pool
)
446 /******************************************************************/
450 if (!mem_pool
|| !mem_pool_size
|| mem_pool_size
< sizeof(tlsf_t
) + BHDR_OVERHEAD
* 8) {
451 ERROR_MSG("init_memory_pool (): memory_pool invalid\n");
455 if (((unsigned long) mem_pool
& PTR_MASK
)) {
456 ERROR_MSG("init_memory_pool (): mem_pool must be aligned to a word\n");
459 tlsf
= (tlsf_t
*) mem_pool
;
460 /* Check if already initialised */
461 if (tlsf
->tlsf_signature
== TLSF_SIGNATURE
) {
463 b
= GET_NEXT_BLOCK(mp
, ROUNDUP_SIZE(sizeof(tlsf_t
)));
464 return b
->size
& BLOCK_SIZE
;
469 /* Zeroing the memory pool */
470 memset(mem_pool
, 0, sizeof(tlsf_t
));
472 tlsf
->tlsf_signature
= TLSF_SIGNATURE
;
474 TLSF_CREATE_LOCK(&tlsf
->lock
);
476 ib
= process_area(GET_NEXT_BLOCK
477 (mem_pool
, ROUNDUP_SIZE(sizeof(tlsf_t
))), ROUNDDOWN_SIZE(mem_pool_size
- sizeof(tlsf_t
)));
478 b
= GET_NEXT_BLOCK(ib
->ptr
.buffer
, ib
->size
& BLOCK_SIZE
);
479 free_ex(b
->ptr
.buffer
, tlsf
);
480 tlsf
->area_head
= (area_info_t
*) ib
->ptr
.buffer
;
483 tlsf
->used_size
= mem_pool_size
- (b
->size
& BLOCK_SIZE
);
484 tlsf
->max_size
= tlsf
->used_size
;
487 return (b
->size
& BLOCK_SIZE
);
490 /******************************************************************/
491 size_t add_new_area(void *area
, size_t area_size
, void *mem_pool
)
493 /******************************************************************/
494 tlsf_t
*tlsf
= (tlsf_t
*) mem_pool
;
495 area_info_t
*ptr
, *ptr_prev
, *ai
;
496 bhdr_t
*ib0
, *b0
, *lb0
, *ib1
, *b1
, *lb1
, *next_b
;
498 memset(area
, 0, area_size
);
499 ptr
= tlsf
->area_head
;
502 ib0
= process_area(area
, area_size
);
503 b0
= GET_NEXT_BLOCK(ib0
->ptr
.buffer
, ib0
->size
& BLOCK_SIZE
);
504 lb0
= GET_NEXT_BLOCK(b0
->ptr
.buffer
, b0
->size
& BLOCK_SIZE
);
506 /* Before inserting the new area, we have to merge this area with the
507 already existing ones */
510 ib1
= (bhdr_t
*) ((char *) ptr
- BHDR_OVERHEAD
);
511 b1
= GET_NEXT_BLOCK(ib1
->ptr
.buffer
, ib1
->size
& BLOCK_SIZE
);
514 /* Merging the new area with the next physically contigous one */
515 if ((unsigned long) ib1
== (unsigned long) lb0
+ BHDR_OVERHEAD
) {
516 if (tlsf
->area_head
== ptr
) {
517 tlsf
->area_head
= ptr
->next
;
520 ptr_prev
->next
= ptr
->next
;
525 ROUNDDOWN_SIZE((b0
->size
& BLOCK_SIZE
) +
526 (ib1
->size
& BLOCK_SIZE
) + 2 * BHDR_OVERHEAD
) | USED_BLOCK
| PREV_USED
;
534 /* Merging the new area with the previous physically contigous
536 if ((unsigned long) lb1
->ptr
.buffer
== (unsigned long) ib0
) {
537 if (tlsf
->area_head
== ptr
) {
538 tlsf
->area_head
= ptr
->next
;
541 ptr_prev
->next
= ptr
->next
;
546 ROUNDDOWN_SIZE((b0
->size
& BLOCK_SIZE
) +
547 (ib0
->size
& BLOCK_SIZE
) + 2 * BHDR_OVERHEAD
) | USED_BLOCK
| (lb1
->size
& PREV_STATE
);
548 next_b
= GET_NEXT_BLOCK(lb1
->ptr
.buffer
, lb1
->size
& BLOCK_SIZE
);
549 next_b
->prev_hdr
= lb1
;
559 /* Inserting the area in the list of linked areas */
560 ai
= (area_info_t
*) ib0
->ptr
.buffer
;
561 ai
->next
= tlsf
->area_head
;
563 tlsf
->area_head
= ai
;
564 free_ex(b0
->ptr
.buffer
, mem_pool
);
565 return (b0
->size
& BLOCK_SIZE
);
569 /******************************************************************/
570 size_t get_used_size(void *mem_pool
)
572 /******************************************************************/
574 return ((tlsf_t
*) mem_pool
)->used_size
;
583 /******************************************************************/
584 size_t get_max_size(void *mem_pool
)
586 /******************************************************************/
588 return ((tlsf_t
*) mem_pool
)->max_size
;
597 /******************************************************************/
598 void destroy_memory_pool(void *mem_pool
)
600 /******************************************************************/
601 tlsf_t
*tlsf
= (tlsf_t
*) mem_pool
;
603 tlsf
->tlsf_signature
= 0;
605 TLSF_DESTROY_LOCK(&tlsf
->lock
);
610 /******************************************************************/
611 void *tlsf_malloc(size_t size
)
613 /******************************************************************/
616 #if USE_MMAP || USE_SBRK
621 area_size
= sizeof(tlsf_t
) + BHDR_OVERHEAD
* 8; /* Just a safety constant */
622 area_size
= (area_size
> DEFAULT_AREA_SIZE
) ? area_size
: DEFAULT_AREA_SIZE
;
623 area
= get_new_area(&area_size
);
624 if (area
== ((void *) ~0))
625 return NULL
; /* Not enough system memory */
626 init_memory_pool(area_size
, area
);
630 TLSF_ACQUIRE_LOCK(&((tlsf_t
*)mp
)->lock
);
632 ret
= malloc_ex(size
, mp
);
634 TLSF_RELEASE_LOCK(&((tlsf_t
*)mp
)->lock
);
639 /******************************************************************/
640 void tlsf_free(void *ptr
)
642 /******************************************************************/
644 TLSF_ACQUIRE_LOCK(&((tlsf_t
*)mp
)->lock
);
648 TLSF_RELEASE_LOCK(&((tlsf_t
*)mp
)->lock
);
652 /******************************************************************/
653 void *tlsf_realloc(void *ptr
, size_t size
)
655 /******************************************************************/
658 #if USE_MMAP || USE_SBRK
660 return tlsf_malloc(size
);
664 TLSF_ACQUIRE_LOCK(&((tlsf_t
*)mp
)->lock
);
666 ret
= realloc_ex(ptr
, size
, mp
);
668 TLSF_RELEASE_LOCK(&((tlsf_t
*)mp
)->lock
);
673 /******************************************************************/
674 void *tlsf_calloc(size_t nelem
, size_t elem_size
)
676 /******************************************************************/
679 TLSF_ACQUIRE_LOCK(&((tlsf_t
*)mp
)->lock
);
681 ret
= calloc_ex(nelem
, elem_size
, mp
);
683 TLSF_RELEASE_LOCK(&((tlsf_t
*)mp
)->lock
);
688 /******************************************************************/
689 void *malloc_ex(size_t size
, void *mem_pool
)
691 /******************************************************************/
692 tlsf_t
*tlsf
= (tlsf_t
*) mem_pool
;
693 bhdr_t
*b
, *b2
, *next_b
;
697 size
= (size
< MIN_BLOCK_SIZE
) ? MIN_BLOCK_SIZE
: ROUNDUP_SIZE(size
);
699 /* Rounding up the requested size and calculating fl and sl */
700 MAPPING_SEARCH(&size
, &fl
, &sl
);
702 /* Searching a free block, recall that this function changes the values of fl and sl,
703 so they are not longer valid when the function fails */
704 b
= FIND_SUITABLE_BLOCK(tlsf
, &fl
, &sl
);
706 #if USE_MMAP || USE_SBRK
710 /* Growing the pool size when needed */
711 area_size
= size
+ BHDR_OVERHEAD
* 8; /* size plus enough room for the requered headers. */
712 area_size
= (area_size
> DEFAULT_AREA_SIZE
) ? area_size
: DEFAULT_AREA_SIZE
;
713 area
= get_new_area(&area_size
); /* Call sbrk or mmap */
714 if (area
== ((void *) ~0))
715 return NULL
; /* Not enough system memory */
716 add_new_area(area
, area_size
, mem_pool
);
717 /* Rounding up the requested size and calculating fl and sl */
718 MAPPING_SEARCH(&size
, &fl
, &sl
);
719 /* Searching a free block */
720 b
= FIND_SUITABLE_BLOCK(tlsf
, &fl
, &sl
);
724 return NULL
; /* Not found */
726 EXTRACT_BLOCK_HDR(b
, tlsf
, fl
, sl
);
729 next_b
= GET_NEXT_BLOCK(b
->ptr
.buffer
, b
->size
& BLOCK_SIZE
);
730 /* Should the block be split? */
731 tmp_size
= (b
->size
& BLOCK_SIZE
) - size
;
732 if (tmp_size
>= sizeof(bhdr_t
)) {
733 tmp_size
-= BHDR_OVERHEAD
;
734 b2
= GET_NEXT_BLOCK(b
->ptr
.buffer
, size
);
735 b2
->size
= tmp_size
| FREE_BLOCK
| PREV_USED
;
736 next_b
->prev_hdr
= b2
;
737 MAPPING_INSERT(tmp_size
, &fl
, &sl
);
738 INSERT_BLOCK(b2
, tlsf
, fl
, sl
);
740 b
->size
= size
| (b
->size
& PREV_STATE
);
742 next_b
->size
&= (~PREV_FREE
);
743 b
->size
&= (~FREE_BLOCK
); /* Now it's used */
746 TLSF_ADD_SIZE(tlsf
, b
);
748 return (void *) b
->ptr
.buffer
;
751 /******************************************************************/
752 void free_ex(void *ptr
, void *mem_pool
)
754 /******************************************************************/
755 tlsf_t
*tlsf
= (tlsf_t
*) mem_pool
;
762 b
= (bhdr_t
*) ((char *) ptr
- BHDR_OVERHEAD
);
763 b
->size
|= FREE_BLOCK
;
765 TLSF_REMOVE_SIZE(tlsf
, b
);
767 b
->ptr
.free_ptr
.prev
= NULL
;
768 b
->ptr
.free_ptr
.next
= NULL
;
769 tmp_b
= GET_NEXT_BLOCK(b
->ptr
.buffer
, b
->size
& BLOCK_SIZE
);
770 if (tmp_b
->size
& FREE_BLOCK
) {
771 MAPPING_INSERT(tmp_b
->size
& BLOCK_SIZE
, &fl
, &sl
);
772 EXTRACT_BLOCK(tmp_b
, tlsf
, fl
, sl
);
773 b
->size
+= (tmp_b
->size
& BLOCK_SIZE
) + BHDR_OVERHEAD
;
775 if (b
->size
& PREV_FREE
) {
777 MAPPING_INSERT(tmp_b
->size
& BLOCK_SIZE
, &fl
, &sl
);
778 EXTRACT_BLOCK(tmp_b
, tlsf
, fl
, sl
);
779 tmp_b
->size
+= (b
->size
& BLOCK_SIZE
) + BHDR_OVERHEAD
;
782 MAPPING_INSERT(b
->size
& BLOCK_SIZE
, &fl
, &sl
);
783 INSERT_BLOCK(b
, tlsf
, fl
, sl
);
785 tmp_b
= GET_NEXT_BLOCK(b
->ptr
.buffer
, b
->size
& BLOCK_SIZE
);
786 tmp_b
->size
|= PREV_FREE
;
790 /******************************************************************/
791 void *realloc_ex(void *ptr
, size_t new_size
, void *mem_pool
)
793 /******************************************************************/
794 tlsf_t
*tlsf
= (tlsf_t
*) mem_pool
;
797 bhdr_t
*b
, *tmp_b
, *next_b
;
803 return (void *) malloc_ex(new_size
, mem_pool
);
806 } else if (!new_size
) {
807 free_ex(ptr
, mem_pool
);
811 b
= (bhdr_t
*) ((char *) ptr
- BHDR_OVERHEAD
);
812 next_b
= GET_NEXT_BLOCK(b
->ptr
.buffer
, b
->size
& BLOCK_SIZE
);
813 new_size
= (new_size
< MIN_BLOCK_SIZE
) ? MIN_BLOCK_SIZE
: ROUNDUP_SIZE(new_size
);
814 tmp_size
= (b
->size
& BLOCK_SIZE
);
815 if (new_size
<= tmp_size
) {
816 TLSF_REMOVE_SIZE(tlsf
, b
);
817 if (next_b
->size
& FREE_BLOCK
) {
818 MAPPING_INSERT(next_b
->size
& BLOCK_SIZE
, &fl
, &sl
);
819 EXTRACT_BLOCK(next_b
, tlsf
, fl
, sl
);
820 tmp_size
+= (next_b
->size
& BLOCK_SIZE
) + BHDR_OVERHEAD
;
821 next_b
= GET_NEXT_BLOCK(next_b
->ptr
.buffer
, next_b
->size
& BLOCK_SIZE
);
822 /* We allways reenter this free block because tmp_size will
823 be greater then sizeof (bhdr_t) */
825 tmp_size
-= new_size
;
826 if (tmp_size
>= sizeof(bhdr_t
)) {
827 tmp_size
-= BHDR_OVERHEAD
;
828 tmp_b
= GET_NEXT_BLOCK(b
->ptr
.buffer
, new_size
);
829 tmp_b
->size
= tmp_size
| FREE_BLOCK
| PREV_USED
;
830 next_b
->prev_hdr
= tmp_b
;
831 next_b
->size
|= PREV_FREE
;
832 MAPPING_INSERT(tmp_size
, &fl
, &sl
);
833 INSERT_BLOCK(tmp_b
, tlsf
, fl
, sl
);
834 b
->size
= new_size
| (b
->size
& PREV_STATE
);
836 TLSF_ADD_SIZE(tlsf
, b
);
837 return (void *) b
->ptr
.buffer
;
839 if ((next_b
->size
& FREE_BLOCK
)) {
840 if (new_size
<= (tmp_size
+ (next_b
->size
& BLOCK_SIZE
))) {
841 TLSF_REMOVE_SIZE(tlsf
, b
);
842 MAPPING_INSERT(next_b
->size
& BLOCK_SIZE
, &fl
, &sl
);
843 EXTRACT_BLOCK(next_b
, tlsf
, fl
, sl
);
844 b
->size
+= (next_b
->size
& BLOCK_SIZE
) + BHDR_OVERHEAD
;
845 next_b
= GET_NEXT_BLOCK(b
->ptr
.buffer
, b
->size
& BLOCK_SIZE
);
846 next_b
->prev_hdr
= b
;
847 next_b
->size
&= ~PREV_FREE
;
848 tmp_size
= (b
->size
& BLOCK_SIZE
) - new_size
;
849 if (tmp_size
>= sizeof(bhdr_t
)) {
850 tmp_size
-= BHDR_OVERHEAD
;
851 tmp_b
= GET_NEXT_BLOCK(b
->ptr
.buffer
, new_size
);
852 tmp_b
->size
= tmp_size
| FREE_BLOCK
| PREV_USED
;
853 next_b
->prev_hdr
= tmp_b
;
854 next_b
->size
|= PREV_FREE
;
855 MAPPING_INSERT(tmp_size
, &fl
, &sl
);
856 INSERT_BLOCK(tmp_b
, tlsf
, fl
, sl
);
857 b
->size
= new_size
| (b
->size
& PREV_STATE
);
859 TLSF_ADD_SIZE(tlsf
, b
);
860 return (void *) b
->ptr
.buffer
;
864 if (!(ptr_aux
= malloc_ex(new_size
, mem_pool
)))
867 cpsize
= ((b
->size
& BLOCK_SIZE
) > new_size
) ? new_size
: (b
->size
& BLOCK_SIZE
);
869 memcpy(ptr_aux
, ptr
, cpsize
);
871 free_ex(ptr
, mem_pool
);
876 /******************************************************************/
877 void *calloc_ex(size_t nelem
, size_t elem_size
, void *mem_pool
)
879 /******************************************************************/
882 if (nelem
<= 0 || elem_size
<= 0)
885 if (!(ptr
= malloc_ex(nelem
* elem_size
, mem_pool
)))
887 memset(ptr
, 0, nelem
* elem_size
);
896 /*************** DEBUG FUNCTIONS **************/
898 /* The following functions have been designed to ease the debugging of */
899 /* the TLSF structure. For non-developing purposes, it may be they */
900 /* haven't too much worth. To enable them, _DEBUG_TLSF_ must be set. */
902 extern void dump_memory_region(unsigned char *mem_ptr
, unsigned int size
);
903 extern void print_block(bhdr_t
* b
);
904 extern void print_tlsf(tlsf_t
* tlsf
);
905 void print_all_blocks(tlsf_t
* tlsf
);
907 void dump_memory_region(unsigned char *mem_ptr
, unsigned int size
)
910 unsigned long begin
= (unsigned long) mem_ptr
;
911 unsigned long end
= (unsigned long) mem_ptr
+ size
;
921 PRINT_MSG("\nMemory region dumped: 0x%lx - 0x%lx\n\n", begin
, end
);
924 PRINT_MSG("0x%lx ", begin
);
926 while (begin
< end
) {
927 if (((unsigned char *) begin
)[0] == 0)
930 PRINT_MSG("%02x", ((unsigned char *) begin
)[0]);
931 if (((unsigned char *) begin
)[1] == 0)
934 PRINT_MSG("%02x ", ((unsigned char *) begin
)[1]);
938 PRINT_MSG("\n0x%lx ", begin
);
946 void print_block(bhdr_t
* b
)
950 PRINT_MSG(">> [%p] (", b
);
951 if ((b
->size
& BLOCK_SIZE
))
952 PRINT_MSG("%lu bytes, ", (unsigned long) (b
->size
& BLOCK_SIZE
));
954 PRINT_MSG("sentinel, ");
955 if ((b
->size
& BLOCK_STATE
) == FREE_BLOCK
)
956 PRINT_MSG("free [%p, %p], ", b
->ptr
.free_ptr
.prev
, b
->ptr
.free_ptr
.next
);
959 if ((b
->size
& PREV_STATE
) == PREV_FREE
)
960 PRINT_MSG("prev. free [%p])\n", b
->prev_hdr
);
962 PRINT_MSG("prev used)\n");
965 void print_tlsf(tlsf_t
* tlsf
)
970 PRINT_MSG("\nTLSF at %p\n", tlsf
);
972 PRINT_MSG("FL bitmap: 0x%x\n\n", (unsigned) tlsf
->fl_bitmap
);
974 for (i
= 0; i
< REAL_FLI
; i
++) {
975 if (tlsf
->sl_bitmap
[i
])
976 PRINT_MSG("SL bitmap 0x%x\n", (unsigned) tlsf
->sl_bitmap
[i
]);
977 for (j
= 0; j
< MAX_SLI
; j
++) {
978 next
= tlsf
->matrix
[i
][j
];
980 PRINT_MSG("-> [%d][%d]\n", i
, j
);
983 next
= next
->ptr
.free_ptr
.next
;
989 void print_all_blocks(tlsf_t
* tlsf
)
993 PRINT_MSG("\nTLSF at %p\nALL BLOCKS\n\n", tlsf
);
994 ai
= tlsf
->area_head
;
996 next
= (bhdr_t
*) ((char *) ai
- BHDR_OVERHEAD
);
999 if ((next
->size
& BLOCK_SIZE
))
1000 next
= GET_NEXT_BLOCK(next
->ptr
.buffer
, next
->size
& BLOCK_SIZE
);