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.
44 * - Bug fixed (discovered by the rockbox project: www.rockbox.org).
46 * (Oct 23 2006) Adam Scislowicz:
48 * - Support for ARMv5 implemented
52 //#define TLSF_STATISTIC 1
55 #define USE_PRINTF (1)
62 #ifndef TLSF_STATISTIC
63 #define TLSF_STATISTIC (0)
67 #define TLSF_ADD_SIZE(tlsf, b) do { \
68 tlsf->used_size += (b->size & BLOCK_SIZE) + BHDR_OVERHEAD; \
69 if (tlsf->used_size > tlsf->max_size) \
70 tlsf->max_size = tlsf->used_size; \
73 #define TLSF_REMOVE_SIZE(tlsf, b) do { \
74 tlsf->used_size -= (b->size & BLOCK_SIZE) + BHDR_OVERHEAD; \
77 #define TLSF_ADD_SIZE(tlsf, b) do{}while(0)
78 #define TLSF_REMOVE_SIZE(tlsf, b) do{}while(0)
83 #if !defined(__GNUC__)
89 /* The debug functions only can be used when _DEBUG_TLSF_ is set. */
91 #define _DEBUG_TLSF_ (0)
94 /*************************************************************************/
95 /* Definition of the structures used by TLSF */
98 /* Some IMPORTANT TLSF parameters */
99 /* Unlike the preview TLSF versions, now they are statics */
100 #define BLOCK_ALIGN (sizeof(void *) * 2)
103 #define MAX_LOG2_SLI (5)
104 #define MAX_SLI (1 << MAX_LOG2_SLI) /* MAX_SLI = 2^MAX_LOG2_SLI */
106 #define FLI_OFFSET (6) /* tlsf structure just will manage blocks bigger */
108 #define SMALL_BLOCK (128)
109 #define REAL_FLI (MAX_FLI - FLI_OFFSET)
110 #define MIN_BLOCK_SIZE (sizeof (free_ptr_t))
111 #define BHDR_OVERHEAD (sizeof (bhdr_t) - MIN_BLOCK_SIZE)
112 #define TLSF_SIGNATURE (0x2A59FA59)
114 #define PTR_MASK (sizeof(void *) - 1)
115 #define BLOCK_SIZE (0xFFFFFFFF - PTR_MASK)
117 #define GET_NEXT_BLOCK(_addr, _r) ((bhdr_t *) ((char *) (_addr) + (_r)))
118 #define MEM_ALIGN ((BLOCK_ALIGN) - 1)
119 #define ROUNDUP_SIZE(_r) (((_r) + MEM_ALIGN) & ~MEM_ALIGN)
120 #define ROUNDDOWN_SIZE(_r) ((_r) & ~MEM_ALIGN)
121 #define ROUNDUP(_x, _v) ((((~(_x)) + 1) & ((_v)-1)) + (_x))
123 #define BLOCK_STATE (0x1)
124 #define PREV_STATE (0x2)
126 /* bit 0 of the block size */
127 #define FREE_BLOCK (0x1)
128 #define USED_BLOCK (0x0)
130 /* bit 1 of the block size */
131 #define PREV_FREE (0x2)
132 #define PREV_USED (0x0)
137 # define PRINT_MSG(fmt, args...) printf(fmt, ## args)
138 # define ERROR_MSG(fmt, args...) printf(fmt, ## args)
140 # if !defined(PRINT_MSG)
141 # define PRINT_MSG(fmt, args...)
143 # if !defined(ERROR_MSG)
144 # define ERROR_MSG(fmt, args...)
148 typedef unsigned int u32_t; /* NOTE: Make sure that this type is 4 bytes long on your computer */
149 typedef unsigned char u8_t; /* NOTE: Make sure that this type is 1 byte on your computer */
151 typedef struct free_ptr_struct {
152 struct bhdr_struct *prev;
153 struct bhdr_struct *next;
156 typedef struct bhdr_struct {
157 /* This pointer is just valid if the first bit of size is set */
158 struct bhdr_struct *prev_hdr;
159 /* The size is stored in bytes */
160 size_t size; /* bit 0 indicates whether the block is used and */
161 /* bit 1 allows to know whether the previous block is free */
163 struct free_ptr_struct free_ptr;
164 u8_t buffer[1]; /*sizeof(struct free_ptr_struct)]; */
168 /* This structure is embedded at the beginning of each area, giving us
169 * enough information to cope with a set of areas */
171 typedef struct area_info_struct {
173 struct area_info_struct *next;
176 typedef struct TLSF_struct {
177 /* the TLSF's structure signature */
178 u32_t tlsf_signature;
181 /* These can not be calculated outside tlsf because we
182 * do not know the sizes when freeing/reallocing memory. */
187 /* A linked list holding all the existing areas */
188 area_info_t *area_head;
190 /* the first-level bitmap */
191 /* This array should have a size of REAL_FLI bits */
194 /* the second-level bitmap */
195 u32_t sl_bitmap[REAL_FLI];
197 bhdr_t *matrix[REAL_FLI][MAX_SLI];
201 /******************************************************************/
202 /************** Helping functions **************************/
203 /******************************************************************/
204 static __inline__ void set_bit(int nr, u32_t * addr);
205 static __inline__ void clear_bit(int nr, u32_t * addr);
206 static __inline__ int ls_bit(int x);
207 static __inline__ int ms_bit(int x);
208 static __inline__ void MAPPING_SEARCH(size_t * _r, int *_fl, int *_sl);
209 static __inline__ void MAPPING_INSERT(size_t _r, int *_fl, int *_sl);
210 static __inline__ bhdr_t *FIND_SUITABLE_BLOCK(tlsf_t * _tlsf, int *_fl, int *_sl);
211 static __inline__ bhdr_t *process_area(void *area, size_t size);
213 static const int table[] = {
214 -1, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4,
217 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
220 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
223 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
226 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
229 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
232 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
235 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
240 static __inline__ int ls_bit(int i)
243 unsigned int x = i & -i;
245 a = x <= 0xffff ? (x <= 0xff ? 0 : 8) : (x <= 0xffffff ? 16 : 24);
246 return table[x >> a] + a;
249 static __inline__ int ms_bit(int i)
252 unsigned int x = (unsigned int) i;
254 a = x <= 0xffff ? (x <= 0xff ? 0 : 8) : (x <= 0xffffff ? 16 : 24);
255 return table[x >> a] + a;
258 static __inline__ void set_bit(int nr, u32_t * addr)
260 addr[nr >> 5] |= 1 << (nr & 0x1f);
263 static __inline__ void clear_bit(int nr, u32_t * addr)
265 addr[nr >> 5] &= ~(1 << (nr & 0x1f));
268 static __inline__ void MAPPING_SEARCH(size_t * _r, int *_fl, int *_sl)
272 if (*_r < SMALL_BLOCK) {
274 *_sl = *_r / (SMALL_BLOCK / MAX_SLI);
276 _t = (1 << (ms_bit(*_r) - MAX_LOG2_SLI)) - 1;
279 *_sl = (*_r >> (*_fl - MAX_LOG2_SLI)) - MAX_SLI;
281 /*if ((*_fl -= FLI_OFFSET) < 0) // FL wil be always >0!
288 static __inline__ void MAPPING_INSERT(size_t _r, int *_fl, int *_sl)
290 if (_r < SMALL_BLOCK) {
292 *_sl = _r / (SMALL_BLOCK / MAX_SLI);
295 *_sl = (_r >> (*_fl - MAX_LOG2_SLI)) - MAX_SLI;
301 static __inline__ bhdr_t *FIND_SUITABLE_BLOCK(tlsf_t * _tlsf, int *_fl, int *_sl)
303 u32_t _tmp = _tlsf->sl_bitmap[*_fl] & (~0 << *_sl);
308 _b = _tlsf->matrix[*_fl][*_sl];
310 *_fl = ls_bit(_tlsf->fl_bitmap & (~0 << (*_fl + 1)));
311 if (*_fl > 0) { /* likely */
312 *_sl = ls_bit(_tlsf->sl_bitmap[*_fl]);
313 _b = _tlsf->matrix[*_fl][*_sl];
320 #define EXTRACT_BLOCK_HDR(_b, _tlsf, _fl, _sl) do { \
321 _tlsf -> matrix [_fl] [_sl] = _b -> ptr.free_ptr.next; \
322 if (_tlsf -> matrix[_fl][_sl]) \
323 _tlsf -> matrix[_fl][_sl] -> ptr.free_ptr.prev = NULL; \
325 clear_bit (_sl, &_tlsf -> sl_bitmap [_fl]); \
326 if (!_tlsf -> sl_bitmap [_fl]) \
327 clear_bit (_fl, &_tlsf -> fl_bitmap); \
329 _b -> ptr.free_ptr.prev = NULL; \
330 _b -> ptr.free_ptr.next = NULL; \
334 #define EXTRACT_BLOCK(_b, _tlsf, _fl, _sl) do { \
335 if (_b -> ptr.free_ptr.next) \
336 _b -> ptr.free_ptr.next -> ptr.free_ptr.prev = _b -> ptr.free_ptr.prev; \
337 if (_b -> ptr.free_ptr.prev) \
338 _b -> ptr.free_ptr.prev -> ptr.free_ptr.next = _b -> ptr.free_ptr.next; \
339 if (_tlsf -> matrix [_fl][_sl] == _b) { \
340 _tlsf -> matrix [_fl][_sl] = _b -> ptr.free_ptr.next; \
341 if (!_tlsf -> matrix [_fl][_sl]) { \
342 clear_bit (_sl, &_tlsf -> sl_bitmap[_fl]); \
343 if (!_tlsf -> sl_bitmap [_fl]) \
344 clear_bit (_fl, &_tlsf -> fl_bitmap); \
347 _b -> ptr.free_ptr.prev = NULL; \
348 _b -> ptr.free_ptr.next = NULL; \
351 #define INSERT_BLOCK(_b, _tlsf, _fl, _sl) do { \
352 _b -> ptr.free_ptr.prev = NULL; \
353 _b -> ptr.free_ptr.next = _tlsf -> matrix [_fl][_sl]; \
354 if (_tlsf -> matrix [_fl][_sl]) \
355 _tlsf -> matrix [_fl][_sl] -> ptr.free_ptr.prev = _b; \
356 _tlsf -> matrix [_fl][_sl] = _b; \
357 set_bit (_sl, &_tlsf -> sl_bitmap [_fl]); \
358 set_bit (_fl, &_tlsf -> fl_bitmap); \
361 static __inline__ bhdr_t *process_area(void *area, size_t size)
366 ib = (bhdr_t *) area;
368 (sizeof(area_info_t) <
369 MIN_BLOCK_SIZE) ? MIN_BLOCK_SIZE : ROUNDUP_SIZE(sizeof(area_info_t)) | USED_BLOCK | PREV_USED;
370 b = (bhdr_t *) GET_NEXT_BLOCK(ib->ptr.buffer, ib->size & BLOCK_SIZE);
371 b->size = ROUNDDOWN_SIZE(size - 3 * BHDR_OVERHEAD - (ib->size & BLOCK_SIZE)) | USED_BLOCK | PREV_USED;
372 b->ptr.free_ptr.prev = b->ptr.free_ptr.next = 0;
373 lb = GET_NEXT_BLOCK(b->ptr.buffer, b->size & BLOCK_SIZE);
375 lb->size = 0 | USED_BLOCK | PREV_FREE;
376 ai = (area_info_t *) ib->ptr.buffer;
382 /* ****************************************************************************/
384 #ifndef PLATFORM_WINDOWS
385 #include <sys/mman.h>
388 PBD::TLSF::TLSF (std::string name, size_t mem_pool_size)
391 mem_pool_size = ROUNDUP_SIZE (mem_pool_size);
392 char * mem_pool = (char*) ::malloc (mem_pool_size);
395 assert (mem_pool_size >= sizeof(tlsf_t) + BHDR_OVERHEAD * 8);
397 #ifndef __MINGW64__ // cast fails
398 assert (0 == (((unsigned long)mem_pool) & PTR_MASK));
401 #ifndef PLATFORM_WINDOWS
402 memset (mem_pool, 0, mem_pool_size); // make resident
403 mlock (mem_pool, mem_pool_size);
408 tlsf_t *tlsf = (tlsf_t *) mem_pool;
411 /* Zeroing the memory pool */
412 memset(_mp, 0, sizeof(tlsf_t));
414 tlsf->tlsf_signature = TLSF_SIGNATURE;
416 ib = process_area(GET_NEXT_BLOCK
417 (_mp, ROUNDUP_SIZE(sizeof(tlsf_t))), ROUNDDOWN_SIZE(mem_pool_size - sizeof(tlsf_t)));
418 b = GET_NEXT_BLOCK(ib->ptr.buffer, ib->size & BLOCK_SIZE);
419 _free(b->ptr.buffer);
420 tlsf->area_head = (area_info_t *) ib->ptr.buffer;
423 tlsf->used_size = mem_pool_size - (b->size & BLOCK_SIZE);
424 tlsf->max_size = tlsf->used_size;
425 PRINT_MSG ("TLSF '%s': free %ld, reserved: %ld [bytes]\n",
427 b->size & BLOCK_SIZE,
435 PRINT_MSG ("TLSF '%s': used: %ld, max: %ld [bytes]\n",
440 tlsf_t *tlsf = (tlsf_t *) _mp;
441 tlsf->tlsf_signature = 0;
447 PBD::TLSF::get_used_size () const
450 return ((tlsf_t *) _mp)->used_size;
457 PBD::TLSF::get_max_size () const
460 return ((tlsf_t *) _mp)->max_size;
467 PBD::TLSF::_malloc (size_t size)
469 tlsf_t *tlsf = (tlsf_t *) _mp;
470 bhdr_t *b, *b2, *next_b;
474 size = (size < MIN_BLOCK_SIZE) ? MIN_BLOCK_SIZE : ROUNDUP_SIZE(size);
476 /* Rounding up the requested size and calculating fl and sl */
477 MAPPING_SEARCH(&size, &fl, &sl);
479 /* Searching a free block, recall that this function changes the values of fl and sl,
480 so they are not longer valid when the function fails */
481 b = FIND_SUITABLE_BLOCK(tlsf, &fl, &sl);
483 return NULL; /* Not found */
485 EXTRACT_BLOCK_HDR(b, tlsf, fl, sl);
488 next_b = GET_NEXT_BLOCK(b->ptr.buffer, b->size & BLOCK_SIZE);
489 /* Should the block be split? */
490 tmp_size = (b->size & BLOCK_SIZE) - size;
491 if (tmp_size >= sizeof(bhdr_t)) {
492 tmp_size -= BHDR_OVERHEAD;
493 b2 = GET_NEXT_BLOCK(b->ptr.buffer, size);
494 b2->size = tmp_size | FREE_BLOCK | PREV_USED;
495 next_b->prev_hdr = b2;
496 MAPPING_INSERT(tmp_size, &fl, &sl);
497 INSERT_BLOCK(b2, tlsf, fl, sl);
499 b->size = size | (b->size & PREV_STATE);
501 next_b->size &= (~PREV_FREE);
502 b->size &= (~FREE_BLOCK); /* Now it's used */
505 TLSF_ADD_SIZE(tlsf, b);
507 return (void *) b->ptr.buffer;
511 PBD::TLSF::_free (void *ptr)
513 tlsf_t *tlsf = (tlsf_t *) _mp;
520 b = (bhdr_t *) ((char *) ptr - BHDR_OVERHEAD);
521 b->size |= FREE_BLOCK;
523 TLSF_REMOVE_SIZE(tlsf, b);
525 b->ptr.free_ptr.prev = NULL;
526 b->ptr.free_ptr.next = NULL;
527 tmp_b = GET_NEXT_BLOCK(b->ptr.buffer, b->size & BLOCK_SIZE);
528 if (tmp_b->size & FREE_BLOCK) {
529 MAPPING_INSERT(tmp_b->size & BLOCK_SIZE, &fl, &sl);
530 EXTRACT_BLOCK(tmp_b, tlsf, fl, sl);
531 b->size += (tmp_b->size & BLOCK_SIZE) + BHDR_OVERHEAD;
533 if (b->size & PREV_FREE) {
535 MAPPING_INSERT(tmp_b->size & BLOCK_SIZE, &fl, &sl);
536 EXTRACT_BLOCK(tmp_b, tlsf, fl, sl);
537 tmp_b->size += (b->size & BLOCK_SIZE) + BHDR_OVERHEAD;
540 MAPPING_INSERT(b->size & BLOCK_SIZE, &fl, &sl);
541 INSERT_BLOCK(b, tlsf, fl, sl);
543 tmp_b = GET_NEXT_BLOCK(b->ptr.buffer, b->size & BLOCK_SIZE);
544 tmp_b->size |= PREV_FREE;
549 PBD::TLSF::_realloc(void *ptr, size_t new_size)
551 tlsf_t *tlsf = (tlsf_t *) _mp;
554 bhdr_t *b, *tmp_b, *next_b;
560 return (void *) _malloc (new_size);
563 } else if (!new_size) {
568 b = (bhdr_t *) ((char *) ptr - BHDR_OVERHEAD);
569 next_b = GET_NEXT_BLOCK(b->ptr.buffer, b->size & BLOCK_SIZE);
570 new_size = (new_size < MIN_BLOCK_SIZE) ? MIN_BLOCK_SIZE : ROUNDUP_SIZE(new_size);
571 tmp_size = (b->size & BLOCK_SIZE);
572 if (new_size <= tmp_size) {
573 TLSF_REMOVE_SIZE(tlsf, b);
574 if (next_b->size & FREE_BLOCK) {
575 MAPPING_INSERT(next_b->size & BLOCK_SIZE, &fl, &sl);
576 EXTRACT_BLOCK(next_b, tlsf, fl, sl);
577 tmp_size += (next_b->size & BLOCK_SIZE) + BHDR_OVERHEAD;
578 next_b = GET_NEXT_BLOCK(next_b->ptr.buffer, next_b->size & BLOCK_SIZE);
579 /* We allways reenter this free block because tmp_size will
580 be greater then sizeof (bhdr_t) */
582 tmp_size -= new_size;
583 if (tmp_size >= sizeof(bhdr_t)) {
584 tmp_size -= BHDR_OVERHEAD;
585 tmp_b = GET_NEXT_BLOCK(b->ptr.buffer, new_size);
586 tmp_b->size = tmp_size | FREE_BLOCK | PREV_USED;
587 next_b->prev_hdr = tmp_b;
588 next_b->size |= PREV_FREE;
589 MAPPING_INSERT(tmp_size, &fl, &sl);
590 INSERT_BLOCK(tmp_b, tlsf, fl, sl);
591 b->size = new_size | (b->size & PREV_STATE);
593 TLSF_ADD_SIZE(tlsf, b);
594 return (void *) b->ptr.buffer;
596 if ((next_b->size & FREE_BLOCK)) {
597 if (new_size <= (tmp_size + (next_b->size & BLOCK_SIZE))) {
598 TLSF_REMOVE_SIZE(tlsf, b);
599 MAPPING_INSERT(next_b->size & BLOCK_SIZE, &fl, &sl);
600 EXTRACT_BLOCK(next_b, tlsf, fl, sl);
601 b->size += (next_b->size & BLOCK_SIZE) + BHDR_OVERHEAD;
602 next_b = GET_NEXT_BLOCK(b->ptr.buffer, b->size & BLOCK_SIZE);
603 next_b->prev_hdr = b;
604 next_b->size &= ~PREV_FREE;
605 tmp_size = (b->size & BLOCK_SIZE) - new_size;
606 if (tmp_size >= sizeof(bhdr_t)) {
607 tmp_size -= BHDR_OVERHEAD;
608 tmp_b = GET_NEXT_BLOCK(b->ptr.buffer, new_size);
609 tmp_b->size = tmp_size | FREE_BLOCK | PREV_USED;
610 next_b->prev_hdr = tmp_b;
611 next_b->size |= PREV_FREE;
612 MAPPING_INSERT(tmp_size, &fl, &sl);
613 INSERT_BLOCK(tmp_b, tlsf, fl, sl);
614 b->size = new_size | (b->size & PREV_STATE);
616 TLSF_ADD_SIZE(tlsf, b);
617 return (void *) b->ptr.buffer;
621 if (!(ptr_aux = _malloc (new_size))){
625 cpsize = ((b->size & BLOCK_SIZE) > new_size) ? new_size : (b->size & BLOCK_SIZE);
627 memcpy(ptr_aux, ptr, cpsize);