apps/codecs/lib/tlsf/src/tlsf.c

   1 /*
   2  * Two Levels Segregate Fit memory allocator (TLSF)
   3  * Version 2.4.4
   4  *
   5  * Written by Miguel Masmano Tello <mimastel@doctor.upv.es>
   6  *
   7  * Thanks to Ismael Ripoll for his suggestions and reviews
   8  *
   9  * Copyright (C) 2008, 2007, 2006, 2005, 2004
  10  *
  11  * This code is released using a dual license strategy: GPL/LGPL
  12  * You can choose the licence that better fits your requirements.
  13  *
  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
  16  *
  17  */
  18
  19 /*
  20  * Code contributions:
  21  *
  22  * (Jul 28 2007)  Herman ten Brugge <hermantenbrugge@home.nl>:
  23  *
  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
  32  *   (bhdr_t).
  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
  36  *   different values.
  37  * - Created set_bit/clear_bit fuctions because they are not present
  38  *   on x86_64.
  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  *
  45  *
  46  * (Oct 23 2006) Adam Scislowicz:
  47  *
  48  * - Support for ARMv5 implemented
  49  *
  50  */
  51
  52 /*#define USE_SBRK        (0) */
  53 /*#define USE_MMAP        (0) */
  54
  55 #include <stdio.h>
  56 #include <string.h>
  57
  58 #ifndef TLSF_USE_LOCKS
  59 #define TLSF_USE_LOCKS  (0)
  60 #endif
  61
  62 #ifndef TLSF_STATISTIC
  63 #define TLSF_STATISTIC  (0)
  64 #endif
  65
  66 #ifndef USE_MMAP
  67 #define USE_MMAP    (0)
  68 #endif
  69
  70 #ifndef USE_SBRK
  71 #define USE_SBRK    (0)
  72 #endif
  73
  74
  75 #if TLSF_USE_LOCKS
  76 #include "target.h"
  77 #else
  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)
  82 #endif
  83
  84 #if TLSF_STATISTIC
  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;                       \
  89         } while(0)
  90
  91 #define TLSF_REMOVE_SIZE(tlsf, b) do {                              \
  92         tlsf->used_size -= (b->size & BLOCK_SIZE) + BHDR_OVERHEAD;  \
  93     } while(0)
  94 #else
  95 #define TLSF_ADD_SIZE(tlsf, b)       do{}while(0)
  96 #define TLSF_REMOVE_SIZE(tlsf, b)    do{}while(0)
  97 #endif
  98
  99 #if USE_MMAP || USE_SBRK
 100 #include <unistd.h>
 101 #endif
 102
 103 #if USE_MMAP
 104 #include <sys/mman.h>
 105 #endif
 106
 107 #include "config.h"
 108 #include "tlsf.h"
 109
 110 #if !defined(__GNUC__)
 111 #ifndef __inline__
 112 #define __inline__
 113 #endif
 114 #endif
 115
 116 /* The  debug functions  only can  be used  when _DEBUG_TLSF_  is set. */
 117 #ifndef _DEBUG_TLSF_
 118 #define _DEBUG_TLSF_  (0)
 119 #endif
 120
 121 /*************************************************************************/
 122 /* Definition of the structures used by TLSF */
 123
 124
 125 /* Some IMPORTANT TLSF parameters */
 126 /* Unlike the preview TLSF versions, now they are statics */
 127 #define BLOCK_ALIGN (sizeof(void *) * 2)
 128
 129 #define MAX_FLI     (30)
 130 #define MAX_LOG2_SLI    (5)
 131 #define MAX_SLI     (1 << MAX_LOG2_SLI)     /* MAX_SLI = 2^MAX_LOG2_SLI */
 132
 133 #define FLI_OFFSET  (6)     /* tlsf structure just will manage blocks bigger */
 134 /* than 128 bytes */
 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)
 140
 141 #define PTR_MASK    (sizeof(void *) - 1)
 142 #define BLOCK_SIZE  (0xFFFFFFFF - PTR_MASK)
 143
 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))
 149
 150 #define BLOCK_STATE (0x1)
 151 #define PREV_STATE  (0x2)
 152
 153 /* bit 0 of the block size */
 154 #define FREE_BLOCK  (0x1)
 155 #define USED_BLOCK  (0x0)
 156
 157 /* bit 1 of the block size */
 158 #define PREV_FREE   (0x2)
 159 #define PREV_USED   (0x0)
 160
 161
 162 #define DEFAULT_AREA_SIZE (1024*10)
 163
 164 #ifdef USE_MMAP
 165 #define PAGE_SIZE (getpagesize())
 166 #endif
 167
 168 #if defined(ROCKBOX) && (CONFIG_PLATFORM & PLATFORM_HOSTED) && defined(DEBUG) \
 169     || !defined(ROCKBOX)
 170 int printf(const char* fmt, ...);
 171 #define PRINT_MSG(fmt, args...) printf(fmt, ## args)
 172 #define ERROR_MSG(fmt, args...) printf(fmt, ## args)
 173 #else
 174 #define PRINT_MSG(fmt, args...)
 175 #define ERROR_MSG(fmt, args...)
 176 #endif
 177
 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 */
 180
 181 typedef struct free_ptr_struct {
 182     struct bhdr_struct *prev;
 183     struct bhdr_struct *next;
 184 } free_ptr_t;
 185
 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 */
 192     union {
 193         struct free_ptr_struct free_ptr;
 194         u8_t buffer[1];         /*sizeof(struct free_ptr_struct)]; */
 195     } ptr;
 196 } bhdr_t;
 197
 198 /* This structure is embedded at the beginning of each area, giving us
 199  * enough information to cope with a set of areas */
 200
 201 typedef struct area_info_struct {
 202     bhdr_t *end;
 203     struct area_info_struct *next;
 204 } area_info_t;
 205
 206 typedef struct TLSF_struct {
 207     /* the TLSF's structure signature */
 208     u32_t tlsf_signature;
 209
 210 #if TLSF_USE_LOCKS
 211     TLSF_MLOCK_T lock;
 212 #endif
 213
 214 #if TLSF_STATISTIC
 215     /* These can not be calculated outside tlsf because we
 216      * do not know the sizes when freeing/reallocing memory. */
 217     size_t used_size;
 218     size_t max_size;
 219 #endif
 220
 221     /* A linked list holding all the existing areas */
 222     area_info_t *area_head;
 223
 224     /* the first-level bitmap */
 225     /* This array should have a size of REAL_FLI bits */
 226     u32_t fl_bitmap;
 227
 228     /* the second-level bitmap */
 229     u32_t sl_bitmap[REAL_FLI];
 230
 231     bhdr_t *matrix[REAL_FLI][MAX_SLI];
 232 } tlsf_t;
 233
 234
 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);
 248 #endif
 249
 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,
 252     4, 4,
 253     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,
 255     5,
 256     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,
 258     6,
 259     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,
 261     6,
 262     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,
 264     7,
 265     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,
 267     7,
 268     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,
 270     7,
 271     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,
 273     7,
 274     7, 7, 7, 7, 7, 7, 7
 275 };
 276
 277 static __inline__ int ls_bit(int i)
 278 {
 279     unsigned int a;
 280     unsigned int x = i & -i;
 281
 282     a = x <= 0xffff ? (x <= 0xff ? 0 : 8) : (x <= 0xffffff ? 16 : 24);
 283     return table[x >> a] + a;
 284 }
 285
 286 static __inline__ int ms_bit(int i)
 287 {
 288     unsigned int a;
 289     unsigned int x = (unsigned int) i;
 290
 291     a = x <= 0xffff ? (x <= 0xff ? 0 : 8) : (x <= 0xffffff ? 16 : 24);
 292     return table[x >> a] + a;
 293 }
 294
 295 static __inline__ void set_bit(int nr, u32_t * addr)
 296 {
 297     addr[nr >> 5] |= 1 << (nr & 0x1f);
 298 }
 299
 300 static __inline__ void clear_bit(int nr, u32_t * addr)
 301 {
 302     addr[nr >> 5] &= ~(1 << (nr & 0x1f));
 303 }
 304
 305 static __inline__ void MAPPING_SEARCH(size_t * _r, int *_fl, int *_sl)
 306 {
 307     int _t;
 308
 309     if (*_r < SMALL_BLOCK) {
 310         *_fl = 0;
 311         *_sl = *_r / (SMALL_BLOCK / MAX_SLI);
 312     } else {
 313         _t = (1 << (ms_bit(*_r) - MAX_LOG2_SLI)) - 1;
 314         *_r = *_r + _t;
 315         *_fl = ms_bit(*_r);
 316         *_sl = (*_r >> (*_fl - MAX_LOG2_SLI)) - MAX_SLI;
 317         *_fl -= FLI_OFFSET;
 318         /*if ((*_fl -= FLI_OFFSET) < 0) // FL wil be always >0!
 319          *_fl = *_sl = 0;
 320          */
 321         *_r &= ~_t;
 322     }
 323 }
 324
 325 static __inline__ void MAPPING_INSERT(size_t _r, int *_fl, int *_sl)
 326 {
 327     if (_r < SMALL_BLOCK) {
 328         *_fl = 0;
 329         *_sl = _r / (SMALL_BLOCK / MAX_SLI);
 330     } else {
 331         *_fl = ms_bit(_r);
 332         *_sl = (_r >> (*_fl - MAX_LOG2_SLI)) - MAX_SLI;
 333         *_fl -= FLI_OFFSET;
 334     }
 335 }
 336
 337
 338 static __inline__ bhdr_t *FIND_SUITABLE_BLOCK(tlsf_t * _tlsf, int *_fl, int *_sl)
 339 {
 340     u32_t _tmp = _tlsf->sl_bitmap[*_fl] & (~0 << *_sl);
 341     bhdr_t *_b = NULL;
 342
 343     if (_tmp) {
 344         *_sl = ls_bit(_tmp);
 345         _b = _tlsf->matrix[*_fl][*_sl];
 346     } else {
 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];
 351         }
 352     }
 353     return _b;
 354 }
 355
 356
 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;  \
 361         else {                                                      \
 362             clear_bit (_sl, &_tlsf -> sl_bitmap [_fl]);             \
 363             if (!_tlsf -> sl_bitmap [_fl])                          \
 364                 clear_bit (_fl, &_tlsf -> fl_bitmap);               \
 365         }                                                           \
 366         _b -> ptr.free_ptr.prev =  NULL;                \
 367         _b -> ptr.free_ptr.next =  NULL;                \
 368     }while(0)
 369
 370
 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);               \
 382             }                                                           \
 383         }                                                               \
 384         _b -> ptr.free_ptr.prev = NULL;                 \
 385         _b -> ptr.free_ptr.next = NULL;                 \
 386     } while(0)
 387
 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);                             \
 396     } while(0)
 397
 398 #if USE_SBRK || USE_MMAP
 399 static __inline__ void *get_new_area(size_t * size)
 400 {
 401     void *area;
 402
 403 #if USE_SBRK
 404     area = (void *)sbrk(0);
 405     if (((void *)sbrk(*size)) != ((void *) -1))
 406         return area;
 407 #endif
 408
 409 #if USE_MMAP
 410     *size = ROUNDUP(*size, PAGE_SIZE);
 411     if ((area = mmap(0, *size, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0)) != MAP_FAILED)
 412         return area;
 413 #endif
 414     return ((void *) ~0);
 415 }
 416 #endif
 417
 418 static __inline__ bhdr_t *process_area(void *area, size_t size)
 419 {
 420     bhdr_t *b, *lb, *ib;
 421     area_info_t *ai;
 422
 423     ib = (bhdr_t *) area;
 424     ib->size =
 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);
 431     lb->prev_hdr = b;
 432     lb->size = 0 | USED_BLOCK | PREV_FREE;
 433     ai = (area_info_t *) ib->ptr.buffer;
 434     ai->next = 0;
 435     ai->end = lb;
 436     return ib;
 437 }
 438
 439 /******************************************************************/
 440 /******************** Begin of the allocator code *****************/
 441 /******************************************************************/
 442
 443 static char *mp = NULL;         /* Default memory pool. */
 444
 445 /******************************************************************/
 446 size_t init_memory_pool(size_t mem_pool_size, void *mem_pool)
 447 {
 448 /******************************************************************/
 449     tlsf_t *tlsf;
 450     bhdr_t *b, *ib;
 451
 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");
 454         return -1;
 455     }
 456
 457     if (((unsigned long) mem_pool & PTR_MASK)) {
 458         ERROR_MSG("init_memory_pool (): mem_pool must be aligned to a word\n");
 459         return -1;
 460     }
 461     tlsf = (tlsf_t *) mem_pool;
 462     /* Check if already initialised */
 463     if (tlsf->tlsf_signature == TLSF_SIGNATURE) {
 464         mp = mem_pool;
 465         b = GET_NEXT_BLOCK(mp, ROUNDUP_SIZE(sizeof(tlsf_t)));
 466         return b->size & BLOCK_SIZE;
 467     }
 468
 469     mp = mem_pool;
 470
 471     /* Zeroing the memory pool */
 472     memset(mem_pool, 0, sizeof(tlsf_t));
 473
 474     tlsf->tlsf_signature = TLSF_SIGNATURE;
 475
 476     TLSF_CREATE_LOCK(&tlsf->lock);
 477
 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;
 483
 484 #if TLSF_STATISTIC
 485     tlsf->used_size = mem_pool_size - (b->size & BLOCK_SIZE);
 486     tlsf->max_size = tlsf->used_size;
 487 #endif
 488
 489     return (b->size & BLOCK_SIZE);
 490 }
 491
 492 /******************************************************************/
 493 size_t add_new_area(void *area, size_t area_size, void *mem_pool)
 494 {
 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;
 499
 500     memset(area, 0, area_size);
 501     ptr = tlsf->area_head;
 502     ptr_prev = 0;
 503
 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);
 507
 508     /* Before inserting the new area, we have to merge this area with the
 509        already existing ones */
 510
 511     while (ptr) {
 512         ib1 = (bhdr_t *) ((char *) ptr - BHDR_OVERHEAD);
 513         b1 = GET_NEXT_BLOCK(ib1->ptr.buffer, ib1->size & BLOCK_SIZE);
 514         lb1 = ptr->end;
 515
 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;
 520                 ptr = ptr->next;
 521             } else {
 522                 ptr_prev->next = ptr->next;
 523                 ptr = ptr->next;
 524             }
 525
 526             b0->size =
 527                 ROUNDDOWN_SIZE((b0->size & BLOCK_SIZE) +
 528                                (ib1->size & BLOCK_SIZE) + 2 * BHDR_OVERHEAD) | USED_BLOCK | PREV_USED;
 529
 530             b1->prev_hdr = b0;
 531             lb0 = lb1;
 532
 533             continue;
 534         }
 535
 536         /* Merging the new area with the previous physically contigous
 537            one */
 538         if ((unsigned long) lb1->ptr.buffer == (unsigned long) ib0) {
 539             if (tlsf->area_head == ptr) {
 540                 tlsf->area_head = ptr->next;
 541                 ptr = ptr->next;
 542             } else {
 543                 ptr_prev->next = ptr->next;
 544                 ptr = ptr->next;
 545             }
 546
 547             lb1->size =
 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;
 552             b0 = lb1;
 553             ib0 = ib1;
 554
 555             continue;
 556         }
 557         ptr_prev = ptr;
 558         ptr = ptr->next;
 559     }
 560
 561     /* Inserting the area in the list of linked areas */
 562     ai = (area_info_t *) ib0->ptr.buffer;
 563     ai->next = tlsf->area_head;
 564     ai->end = lb0;
 565     tlsf->area_head = ai;
 566     free_ex(b0->ptr.buffer, mem_pool);
 567     return (b0->size & BLOCK_SIZE);
 568 }
 569
 570
 571 /******************************************************************/
 572 size_t get_used_size(void *mem_pool)
 573 {
 574 /******************************************************************/
 575 #if TLSF_STATISTIC
 576     return ((tlsf_t *) mem_pool)->used_size;
 577 #else
 578 #ifdef ROCKBOX
 579     (void) mem_pool;
 580 #endif /* ROCKBOX */
 581     return 0;
 582 #endif
 583 }
 584
 585 /******************************************************************/
 586 size_t get_max_size(void *mem_pool)
 587 {
 588 /******************************************************************/
 589 #if TLSF_STATISTIC
 590     return ((tlsf_t *) mem_pool)->max_size;
 591 #else
 592 #ifdef ROCKBOX
 593     (void) mem_pool;
 594 #endif /* ROCKBOX */
 595     return 0;
 596 #endif
 597 }
 598
 599 /******************************************************************/
 600 void destroy_memory_pool(void *mem_pool)
 601 {
 602 /******************************************************************/
 603     tlsf_t *tlsf = (tlsf_t *) mem_pool;
 604
 605     tlsf->tlsf_signature = 0;
 606
 607     TLSF_DESTROY_LOCK(&tlsf->lock);
 608
 609 }
 610
 611
 612 /******************************************************************/
 613 void *tlsf_malloc(size_t size)
 614 {
 615 /******************************************************************/
 616     void *ret;
 617
 618 #if USE_MMAP || USE_SBRK
 619     if (!mp) {
 620         size_t area_size;
 621         void *area;
 622
 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);
 629     }
 630 #endif
 631
 632     TLSF_ACQUIRE_LOCK(&((tlsf_t *)mp)->lock);
 633
 634     ret = malloc_ex(size, mp);
 635
 636     TLSF_RELEASE_LOCK(&((tlsf_t *)mp)->lock);
 637
 638     return ret;
 639 }
 640
 641 /******************************************************************/
 642 void tlsf_free(void *ptr)
 643 {
 644 /******************************************************************/
 645
 646     TLSF_ACQUIRE_LOCK(&((tlsf_t *)mp)->lock);
 647
 648     free_ex(ptr, mp);
 649
 650     TLSF_RELEASE_LOCK(&((tlsf_t *)mp)->lock);
 651
 652 }
 653
 654 /******************************************************************/
 655 void *tlsf_realloc(void *ptr, size_t size)
 656 {
 657 /******************************************************************/
 658     void *ret;
 659
 660 #if USE_MMAP || USE_SBRK
 661     if (!mp) {
 662         return tlsf_malloc(size);
 663     }
 664 #endif
 665
 666     TLSF_ACQUIRE_LOCK(&((tlsf_t *)mp)->lock);
 667
 668     ret = realloc_ex(ptr, size, mp);
 669
 670     TLSF_RELEASE_LOCK(&((tlsf_t *)mp)->lock);
 671
 672     return ret;
 673 }
 674
 675 /******************************************************************/
 676 void *tlsf_calloc(size_t nelem, size_t elem_size)
 677 {
 678 /******************************************************************/
 679     void *ret;
 680
 681     TLSF_ACQUIRE_LOCK(&((tlsf_t *)mp)->lock);
 682
 683     ret = calloc_ex(nelem, elem_size, mp);
 684
 685     TLSF_RELEASE_LOCK(&((tlsf_t *)mp)->lock);
 686
 687     return ret;
 688 }
 689
 690 /******************************************************************/
 691 void *malloc_ex(size_t size, void *mem_pool)
 692 {
 693 /******************************************************************/
 694     tlsf_t *tlsf = (tlsf_t *) mem_pool;
 695     bhdr_t *b, *b2, *next_b;
 696     int fl, sl;
 697     size_t tmp_size;
 698
 699     size = (size < MIN_BLOCK_SIZE) ? MIN_BLOCK_SIZE : ROUNDUP_SIZE(size);
 700
 701     /* Rounding up the requested size and calculating fl and sl */
 702     MAPPING_SEARCH(&size, &fl, &sl);
 703
 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);
 707
 708 #if USE_MMAP || USE_SBRK
 709     if (!b) {
 710         size_t area_size;
 711         void *area;
 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);
 723     }
 724 #endif
 725     if (!b)
 726         return NULL;            /* Not found */
 727
 728     EXTRACT_BLOCK_HDR(b, tlsf, fl, sl);
 729
 730     /*-- found: */
 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);
 741
 742         b->size = size | (b->size & PREV_STATE);
 743     } else {
 744         next_b->size &= (~PREV_FREE);
 745         b->size &= (~FREE_BLOCK);       /* Now it's used */
 746     }
 747
 748     TLSF_ADD_SIZE(tlsf, b);
 749
 750     return (void *) b->ptr.buffer;
 751 }
 752
 753 /******************************************************************/
 754 void free_ex(void *ptr, void *mem_pool)
 755 {
 756 /******************************************************************/
 757     tlsf_t *tlsf = (tlsf_t *) mem_pool;
 758     bhdr_t *b, *tmp_b;
 759     int fl = 0, sl = 0;
 760
 761     if (!ptr) {
 762         return;
 763     }
 764     b = (bhdr_t *) ((char *) ptr - BHDR_OVERHEAD);
 765     b->size |= FREE_BLOCK;
 766
 767     TLSF_REMOVE_SIZE(tlsf, b);
 768
 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;
 776     }
 777     if (b->size & PREV_FREE) {
 778         tmp_b = b->prev_hdr;
 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;
 782         b = tmp_b;
 783     }
 784     MAPPING_INSERT(b->size & BLOCK_SIZE, &fl, &sl);
 785     INSERT_BLOCK(b, tlsf, fl, sl);
 786
 787     tmp_b = GET_NEXT_BLOCK(b->ptr.buffer, b->size & BLOCK_SIZE);
 788     tmp_b->size |= PREV_FREE;
 789     tmp_b->prev_hdr = b;
 790 }
 791
 792 /******************************************************************/
 793 void *realloc_ex(void *ptr, size_t new_size, void *mem_pool)
 794 {
 795 /******************************************************************/
 796     tlsf_t *tlsf = (tlsf_t *) mem_pool;
 797     void *ptr_aux;
 798     unsigned int cpsize;
 799     bhdr_t *b, *tmp_b, *next_b;
 800     int fl, sl;
 801     size_t tmp_size;
 802
 803     if (!ptr) {
 804         if (new_size)
 805             return (void *) malloc_ex(new_size, mem_pool);
 806         if (!new_size)
 807             return NULL;
 808     } else if (!new_size) {
 809         free_ex(ptr, mem_pool);
 810         return NULL;
 811     }
 812
 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) */
 826         }
 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);
 837         }
 838     TLSF_ADD_SIZE(tlsf, b);
 839         return (void *) b->ptr.buffer;
 840     }
 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);
 860             }
 861             TLSF_ADD_SIZE(tlsf, b);
 862             return (void *) b->ptr.buffer;
 863         }
 864     }
 865
 866     if (!(ptr_aux = malloc_ex(new_size, mem_pool)))
 867         return NULL;
 868
 869     cpsize = ((b->size & BLOCK_SIZE) > new_size) ? new_size : (b->size & BLOCK_SIZE);
 870
 871     memcpy(ptr_aux, ptr, cpsize);
 872
 873     free_ex(ptr, mem_pool);
 874     return ptr_aux;
 875 }
 876
 877
 878 /******************************************************************/
 879 void *calloc_ex(size_t nelem, size_t elem_size, void *mem_pool)
 880 {
 881 /******************************************************************/
 882     void *ptr;
 883
 884     if (nelem <= 0 || elem_size <= 0)
 885         return NULL;
 886
 887     if (!(ptr = malloc_ex(nelem * elem_size, mem_pool)))
 888         return NULL;
 889     memset(ptr, 0, nelem * elem_size);
 890
 891     return ptr;
 892 }
 893
 894
 895
 896 #if _DEBUG_TLSF_
 897
 898 /***************  DEBUG FUNCTIONS   **************/
 899
 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.  */
 903
 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);
 908
 909 void dump_memory_region(unsigned char *mem_ptr, unsigned int size)
 910 {
 911
 912     unsigned long begin = (unsigned long) mem_ptr;
 913     unsigned long end = (unsigned long) mem_ptr + size;
 914     int column = 0;
 915
 916     begin >>= 2;
 917     begin <<= 2;
 918
 919     end >>= 2;
 920     end++;
 921     end <<= 2;
 922
 923     PRINT_MSG("\nMemory region dumped: 0x%lx - 0x%lx\n\n", begin, end);
 924
 925     column = 0;
 926     PRINT_MSG("0x%lx ", begin);
 927
 928     while (begin < end) {
 929         if (((unsigned char *) begin)[0] == 0)
 930             PRINT_MSG("00");
 931         else
 932             PRINT_MSG("%02x", ((unsigned char *) begin)[0]);
 933         if (((unsigned char *) begin)[1] == 0)
 934             PRINT_MSG("00 ");
 935         else
 936             PRINT_MSG("%02x ", ((unsigned char *) begin)[1]);
 937         begin += 2;
 938         column++;
 939         if (column == 8) {
 940             PRINT_MSG("\n0x%lx ", begin);
 941             column = 0;
 942         }
 943
 944     }
 945     PRINT_MSG("\n\n");
 946 }
 947
 948 void print_block(bhdr_t * b)
 949 {
 950     if (!b)
 951         return;
 952     PRINT_MSG(">> [%p] (", b);
 953     if ((b->size & BLOCK_SIZE))
 954         PRINT_MSG("%lu bytes, ", (unsigned long) (b->size & BLOCK_SIZE));
 955     else
 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);
 959     else
 960         PRINT_MSG("used, ");
 961     if ((b->size & PREV_STATE) == PREV_FREE)
 962         PRINT_MSG("prev. free [%p])\n", b->prev_hdr);
 963     else
 964         PRINT_MSG("prev used)\n");
 965 }
 966
 967 void print_tlsf(tlsf_t * tlsf)
 968 {
 969     bhdr_t *next;
 970     int i, j;
 971
 972     PRINT_MSG("\nTLSF at %p\n", tlsf);
 973
 974     PRINT_MSG("FL bitmap: 0x%x\n\n", (unsigned) tlsf->fl_bitmap);
 975
 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];
 981             if (next)
 982                 PRINT_MSG("-> [%d][%d]\n", i, j);
 983             while (next) {
 984                 print_block(next);
 985                 next = next->ptr.free_ptr.next;
 986             }
 987         }
 988     }
 989 }
 990
 991 void print_all_blocks(tlsf_t * tlsf)
 992 {
 993     area_info_t *ai;
 994     bhdr_t *next;
 995     PRINT_MSG("\nTLSF at %p\nALL BLOCKS\n\n", tlsf);
 996     ai = tlsf->area_head;
 997     while (ai) {
 998         next = (bhdr_t *) ((char *) ai - BHDR_OVERHEAD);
 999         while (next) {
1000             print_block(next);
1001             if ((next->size & BLOCK_SIZE))
1002                 next = GET_NEXT_BLOCK(next->ptr.buffer, next->size & BLOCK_SIZE);
1003             else
1004                 next = NULL;
1005         }
1006         ai = ai->next;
1007     }
1008 }
1009
1010 #endif