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 "tlsf.h"
 108
 109 #if !defined(__GNUC__)
 110 #ifndef __inline__
 111 #define __inline__
 112 #endif
 113 #endif
 114
 115 /* The  debug functions  only can  be used  when _DEBUG_TLSF_  is set. */
 116 #ifndef _DEBUG_TLSF_
 117 #define _DEBUG_TLSF_  (0)
 118 #endif
 119
 120 /*************************************************************************/
 121 /* Definition of the structures used by TLSF */
 122
 123
 124 /* Some IMPORTANT TLSF parameters */
 125 /* Unlike the preview TLSF versions, now they are statics */
 126 #define BLOCK_ALIGN (sizeof(void *) * 2)
 127
 128 #define MAX_FLI         (30)
 129 #define MAX_LOG2_SLI    (5)
 130 #define MAX_SLI         (1 << MAX_LOG2_SLI)     /* MAX_SLI = 2^MAX_LOG2_SLI */
 131
 132 #define FLI_OFFSET      (6)     /* tlsf structure just will manage blocks bigger */
 133 /* than 128 bytes */
 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)
 139
 140 #define PTR_MASK        (sizeof(void *) - 1)
 141 #define BLOCK_SIZE      (0xFFFFFFFF - PTR_MASK)
 142
 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))
 148
 149 #define BLOCK_STATE     (0x1)
 150 #define PREV_STATE      (0x2)
 151
 152 /* bit 0 of the block size */
 153 #define FREE_BLOCK      (0x1)
 154 #define USED_BLOCK      (0x0)
 155
 156 /* bit 1 of the block size */
 157 #define PREV_FREE       (0x2)
 158 #define PREV_USED       (0x0)
 159
 160
 161 #define DEFAULT_AREA_SIZE (1024*10)
 162
 163 #ifdef USE_MMAP
 164 #define PAGE_SIZE (getpagesize())
 165 #endif
 166
 167 #if defined(ROCKBOX) && defined(SIMULATOR) || !defined(ROCKBOX)
 168 int printf(char*, ...);
 169 #define PRINT_MSG(fmt, args...) printf(fmt, ## args)
 170 #define ERROR_MSG(fmt, args...) printf(fmt, ## args)
 171 #else
 172 #define PRINT_MSG(fmt, args...)
 173 #define ERROR_MSG(fmt, args...)
 174 #endif
 175
 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 */
 178
 179 typedef struct free_ptr_struct {
 180     struct bhdr_struct *prev;
 181     struct bhdr_struct *next;
 182 } free_ptr_t;
 183
 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 */
 190     union {
 191         struct free_ptr_struct free_ptr;
 192         u8_t buffer[1];         /*sizeof(struct free_ptr_struct)]; */
 193     } ptr;
 194 } bhdr_t;
 195
 196 /* This structure is embedded at the beginning of each area, giving us
 197  * enough information to cope with a set of areas */
 198
 199 typedef struct area_info_struct {
 200     bhdr_t *end;
 201     struct area_info_struct *next;
 202 } area_info_t;
 203
 204 typedef struct TLSF_struct {
 205     /* the TLSF's structure signature */
 206     u32_t tlsf_signature;
 207
 208 #if TLSF_USE_LOCKS
 209     TLSF_MLOCK_T lock;
 210 #endif
 211
 212 #if TLSF_STATISTIC
 213     /* These can not be calculated outside tlsf because we
 214      * do not know the sizes when freeing/reallocing memory. */
 215     size_t used_size;
 216     size_t max_size;
 217 #endif
 218
 219     /* A linked list holding all the existing areas */
 220     area_info_t *area_head;
 221
 222     /* the first-level bitmap */
 223     /* This array should have a size of REAL_FLI bits */
 224     u32_t fl_bitmap;
 225
 226     /* the second-level bitmap */
 227     u32_t sl_bitmap[REAL_FLI];
 228
 229     bhdr_t *matrix[REAL_FLI][MAX_SLI];
 230 } tlsf_t;
 231
 232
 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);
 246 #endif
 247
 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,
 250     4, 4,
 251     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,
 253     5,
 254     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,
 256     6,
 257     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,
 259     6,
 260     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,
 262     7,
 263     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,
 265     7,
 266     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,
 268     7,
 269     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,
 271     7,
 272     7, 7, 7, 7, 7, 7, 7
 273 };
 274
 275 static __inline__ int ls_bit(int i)
 276 {
 277     unsigned int a;
 278     unsigned int x = i & -i;
 279
 280     a = x <= 0xffff ? (x <= 0xff ? 0 : 8) : (x <= 0xffffff ? 16 : 24);
 281     return table[x >> a] + a;
 282 }
 283
 284 static __inline__ int ms_bit(int i)
 285 {
 286     unsigned int a;
 287     unsigned int x = (unsigned int) i;
 288
 289     a = x <= 0xffff ? (x <= 0xff ? 0 : 8) : (x <= 0xffffff ? 16 : 24);
 290     return table[x >> a] + a;
 291 }
 292
 293 static __inline__ void set_bit(int nr, u32_t * addr)
 294 {
 295     addr[nr >> 5] |= 1 << (nr & 0x1f);
 296 }
 297
 298 static __inline__ void clear_bit(int nr, u32_t * addr)
 299 {
 300     addr[nr >> 5] &= ~(1 << (nr & 0x1f));
 301 }
 302
 303 static __inline__ void MAPPING_SEARCH(size_t * _r, int *_fl, int *_sl)
 304 {
 305     int _t;
 306
 307     if (*_r < SMALL_BLOCK) {
 308         *_fl = 0;
 309         *_sl = *_r / (SMALL_BLOCK / MAX_SLI);
 310     } else {
 311         _t = (1 << (ms_bit(*_r) - MAX_LOG2_SLI)) - 1;
 312         *_r = *_r + _t;
 313         *_fl = ms_bit(*_r);
 314         *_sl = (*_r >> (*_fl - MAX_LOG2_SLI)) - MAX_SLI;
 315         *_fl -= FLI_OFFSET;
 316         /*if ((*_fl -= FLI_OFFSET) < 0) // FL wil be always >0!
 317          *_fl = *_sl = 0;
 318          */
 319         *_r &= ~_t;
 320     }
 321 }
 322
 323 static __inline__ void MAPPING_INSERT(size_t _r, int *_fl, int *_sl)
 324 {
 325     if (_r < SMALL_BLOCK) {
 326         *_fl = 0;
 327         *_sl = _r / (SMALL_BLOCK / MAX_SLI);
 328     } else {
 329         *_fl = ms_bit(_r);
 330         *_sl = (_r >> (*_fl - MAX_LOG2_SLI)) - MAX_SLI;
 331         *_fl -= FLI_OFFSET;
 332     }
 333 }
 334
 335
 336 static __inline__ bhdr_t *FIND_SUITABLE_BLOCK(tlsf_t * _tlsf, int *_fl, int *_sl)
 337 {
 338     u32_t _tmp = _tlsf->sl_bitmap[*_fl] & (~0 << *_sl);
 339     bhdr_t *_b = NULL;
 340
 341     if (_tmp) {
 342         *_sl = ls_bit(_tmp);
 343         _b = _tlsf->matrix[*_fl][*_sl];
 344     } else {
 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];
 349         }
 350     }
 351     return _b;
 352 }
 353
 354
 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;  \
 359                 else {                                                                                                          \
 360                         clear_bit (_sl, &_tlsf -> sl_bitmap [_fl]);                             \
 361                         if (!_tlsf -> sl_bitmap [_fl])                                                  \
 362                                 clear_bit (_fl, &_tlsf -> fl_bitmap);                           \
 363                 }                                                                                                                       \
 364                 _b -> ptr.free_ptr.prev =  NULL;                                \
 365                 _b -> ptr.free_ptr.next =  NULL;                                \
 366         }while(0)
 367
 368
 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);                           \
 380                         }                                                                                                                       \
 381                 }                                                                                                                               \
 382                 _b -> ptr.free_ptr.prev = NULL;                                 \
 383                 _b -> ptr.free_ptr.next = NULL;                                 \
 384         } while(0)
 385
 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);                                                             \
 394         } while(0)
 395
 396 #if USE_SBRK || USE_MMAP
 397 static __inline__ void *get_new_area(size_t * size)
 398 {
 399     void *area;
 400
 401 #if USE_SBRK
 402     area = (void *)sbrk(0);
 403     if (((void *)sbrk(*size)) != ((void *) -1))
 404         return area;
 405 #endif
 406
 407 #if USE_MMAP
 408     *size = ROUNDUP(*size, PAGE_SIZE);
 409     if ((area = mmap(0, *size, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0)) != MAP_FAILED)
 410         return area;
 411 #endif
 412     return ((void *) ~0);
 413 }
 414 #endif
 415
 416 static __inline__ bhdr_t *process_area(void *area, size_t size)
 417 {
 418     bhdr_t *b, *lb, *ib;
 419     area_info_t *ai;
 420
 421     ib = (bhdr_t *) area;
 422     ib->size =
 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);
 429     lb->prev_hdr = b;
 430     lb->size = 0 | USED_BLOCK | PREV_FREE;
 431     ai = (area_info_t *) ib->ptr.buffer;
 432     ai->next = 0;
 433     ai->end = lb;
 434     return ib;
 435 }
 436
 437 /******************************************************************/
 438 /******************** Begin of the allocator code *****************/
 439 /******************************************************************/
 440
 441 static char *mp = NULL;         /* Default memory pool. */
 442
 443 /******************************************************************/
 444 size_t init_memory_pool(size_t mem_pool_size, void *mem_pool)
 445 {
 446 /******************************************************************/
 447     tlsf_t *tlsf;
 448     bhdr_t *b, *ib;
 449
 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");
 452         return -1;
 453     }
 454
 455     if (((unsigned long) mem_pool & PTR_MASK)) {
 456         ERROR_MSG("init_memory_pool (): mem_pool must be aligned to a word\n");
 457         return -1;
 458     }
 459     tlsf = (tlsf_t *) mem_pool;
 460     /* Check if already initialised */
 461     if (tlsf->tlsf_signature == TLSF_SIGNATURE) {
 462         mp = mem_pool;
 463         b = GET_NEXT_BLOCK(mp, ROUNDUP_SIZE(sizeof(tlsf_t)));
 464         return b->size & BLOCK_SIZE;
 465     }
 466
 467     mp = mem_pool;
 468
 469     /* Zeroing the memory pool */
 470     memset(mem_pool, 0, sizeof(tlsf_t));
 471
 472     tlsf->tlsf_signature = TLSF_SIGNATURE;
 473
 474     TLSF_CREATE_LOCK(&tlsf->lock);
 475
 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;
 481
 482 #if TLSF_STATISTIC
 483     tlsf->used_size = mem_pool_size - (b->size & BLOCK_SIZE);
 484     tlsf->max_size = tlsf->used_size;
 485 #endif
 486
 487     return (b->size & BLOCK_SIZE);
 488 }
 489
 490 /******************************************************************/
 491 size_t add_new_area(void *area, size_t area_size, void *mem_pool)
 492 {
 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;
 497
 498     memset(area, 0, area_size);
 499     ptr = tlsf->area_head;
 500     ptr_prev = 0;
 501
 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);
 505
 506     /* Before inserting the new area, we have to merge this area with the
 507        already existing ones */
 508
 509     while (ptr) {
 510         ib1 = (bhdr_t *) ((char *) ptr - BHDR_OVERHEAD);
 511         b1 = GET_NEXT_BLOCK(ib1->ptr.buffer, ib1->size & BLOCK_SIZE);
 512         lb1 = ptr->end;
 513
 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;
 518                 ptr = ptr->next;
 519             } else {
 520                 ptr_prev->next = ptr->next;
 521                 ptr = ptr->next;
 522             }
 523
 524             b0->size =
 525                 ROUNDDOWN_SIZE((b0->size & BLOCK_SIZE) +
 526                                (ib1->size & BLOCK_SIZE) + 2 * BHDR_OVERHEAD) | USED_BLOCK | PREV_USED;
 527
 528             b1->prev_hdr = b0;
 529             lb0 = lb1;
 530
 531             continue;
 532         }
 533
 534         /* Merging the new area with the previous physically contigous
 535            one */
 536         if ((unsigned long) lb1->ptr.buffer == (unsigned long) ib0) {
 537             if (tlsf->area_head == ptr) {
 538                 tlsf->area_head = ptr->next;
 539                 ptr = ptr->next;
 540             } else {
 541                 ptr_prev->next = ptr->next;
 542                 ptr = ptr->next;
 543             }
 544
 545             lb1->size =
 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;
 550             b0 = lb1;
 551             ib0 = ib1;
 552
 553             continue;
 554         }
 555         ptr_prev = ptr;
 556         ptr = ptr->next;
 557     }
 558
 559     /* Inserting the area in the list of linked areas */
 560     ai = (area_info_t *) ib0->ptr.buffer;
 561     ai->next = tlsf->area_head;
 562     ai->end = lb0;
 563     tlsf->area_head = ai;
 564     free_ex(b0->ptr.buffer, mem_pool);
 565     return (b0->size & BLOCK_SIZE);
 566 }
 567
 568
 569 /******************************************************************/
 570 size_t get_used_size(void *mem_pool)
 571 {
 572 /******************************************************************/
 573 #if TLSF_STATISTIC
 574     return ((tlsf_t *) mem_pool)->used_size;
 575 #else
 576 #ifdef ROCKBOX
 577     (void) mem_pool;
 578 #endif /* ROCKBOX */
 579     return 0;
 580 #endif
 581 }
 582
 583 /******************************************************************/
 584 size_t get_max_size(void *mem_pool)
 585 {
 586 /******************************************************************/
 587 #if TLSF_STATISTIC
 588     return ((tlsf_t *) mem_pool)->max_size;
 589 #else
 590 #ifdef ROCKBOX
 591     (void) mem_pool;
 592 #endif /* ROCKBOX */
 593     return 0;
 594 #endif
 595 }
 596
 597 /******************************************************************/
 598 void destroy_memory_pool(void *mem_pool)
 599 {
 600 /******************************************************************/
 601     tlsf_t *tlsf = (tlsf_t *) mem_pool;
 602
 603     tlsf->tlsf_signature = 0;
 604
 605     TLSF_DESTROY_LOCK(&tlsf->lock);
 606
 607 }
 608
 609
 610 /******************************************************************/
 611 void *tlsf_malloc(size_t size)
 612 {
 613 /******************************************************************/
 614     void *ret;
 615
 616 #if USE_MMAP || USE_SBRK
 617     if (!mp) {
 618         size_t area_size;
 619         void *area;
 620
 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);
 627     }
 628 #endif
 629
 630     TLSF_ACQUIRE_LOCK(&((tlsf_t *)mp)->lock);
 631
 632     ret = malloc_ex(size, mp);
 633
 634     TLSF_RELEASE_LOCK(&((tlsf_t *)mp)->lock);
 635
 636     return ret;
 637 }
 638
 639 /******************************************************************/
 640 void tlsf_free(void *ptr)
 641 {
 642 /******************************************************************/
 643
 644     TLSF_ACQUIRE_LOCK(&((tlsf_t *)mp)->lock);
 645
 646     free_ex(ptr, mp);
 647
 648     TLSF_RELEASE_LOCK(&((tlsf_t *)mp)->lock);
 649
 650 }
 651
 652 /******************************************************************/
 653 void *tlsf_realloc(void *ptr, size_t size)
 654 {
 655 /******************************************************************/
 656     void *ret;
 657
 658 #if USE_MMAP || USE_SBRK
 659         if (!mp) {
 660                 return tlsf_malloc(size);
 661         }
 662 #endif
 663
 664     TLSF_ACQUIRE_LOCK(&((tlsf_t *)mp)->lock);
 665
 666     ret = realloc_ex(ptr, size, mp);
 667
 668     TLSF_RELEASE_LOCK(&((tlsf_t *)mp)->lock);
 669
 670     return ret;
 671 }
 672
 673 /******************************************************************/
 674 void *tlsf_calloc(size_t nelem, size_t elem_size)
 675 {
 676 /******************************************************************/
 677     void *ret;
 678
 679     TLSF_ACQUIRE_LOCK(&((tlsf_t *)mp)->lock);
 680
 681     ret = calloc_ex(nelem, elem_size, mp);
 682
 683     TLSF_RELEASE_LOCK(&((tlsf_t *)mp)->lock);
 684
 685     return ret;
 686 }
 687
 688 /******************************************************************/
 689 void *malloc_ex(size_t size, void *mem_pool)
 690 {
 691 /******************************************************************/
 692     tlsf_t *tlsf = (tlsf_t *) mem_pool;
 693     bhdr_t *b, *b2, *next_b;
 694     int fl, sl;
 695     size_t tmp_size;
 696
 697     size = (size < MIN_BLOCK_SIZE) ? MIN_BLOCK_SIZE : ROUNDUP_SIZE(size);
 698
 699     /* Rounding up the requested size and calculating fl and sl */
 700     MAPPING_SEARCH(&size, &fl, &sl);
 701
 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);
 705
 706 #if USE_MMAP || USE_SBRK
 707     if (!b) {
 708         size_t area_size;
 709         void *area;
 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);
 721     }
 722 #endif
 723     if (!b)
 724         return NULL;            /* Not found */
 725
 726     EXTRACT_BLOCK_HDR(b, tlsf, fl, sl);
 727
 728     /*-- found: */
 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);
 739
 740         b->size = size | (b->size & PREV_STATE);
 741     } else {
 742         next_b->size &= (~PREV_FREE);
 743         b->size &= (~FREE_BLOCK);       /* Now it's used */
 744     }
 745
 746     TLSF_ADD_SIZE(tlsf, b);
 747
 748     return (void *) b->ptr.buffer;
 749 }
 750
 751 /******************************************************************/
 752 void free_ex(void *ptr, void *mem_pool)
 753 {
 754 /******************************************************************/
 755     tlsf_t *tlsf = (tlsf_t *) mem_pool;
 756     bhdr_t *b, *tmp_b;
 757     int fl = 0, sl = 0;
 758
 759     if (!ptr) {
 760         return;
 761     }
 762     b = (bhdr_t *) ((char *) ptr - BHDR_OVERHEAD);
 763     b->size |= FREE_BLOCK;
 764
 765     TLSF_REMOVE_SIZE(tlsf, b);
 766
 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;
 774     }
 775     if (b->size & PREV_FREE) {
 776         tmp_b = b->prev_hdr;
 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;
 780         b = tmp_b;
 781     }
 782     MAPPING_INSERT(b->size & BLOCK_SIZE, &fl, &sl);
 783     INSERT_BLOCK(b, tlsf, fl, sl);
 784
 785     tmp_b = GET_NEXT_BLOCK(b->ptr.buffer, b->size & BLOCK_SIZE);
 786     tmp_b->size |= PREV_FREE;
 787     tmp_b->prev_hdr = b;
 788 }
 789
 790 /******************************************************************/
 791 void *realloc_ex(void *ptr, size_t new_size, void *mem_pool)
 792 {
 793 /******************************************************************/
 794     tlsf_t *tlsf = (tlsf_t *) mem_pool;
 795     void *ptr_aux;
 796     unsigned int cpsize;
 797     bhdr_t *b, *tmp_b, *next_b;
 798     int fl, sl;
 799     size_t tmp_size;
 800
 801     if (!ptr) {
 802         if (new_size)
 803             return (void *) malloc_ex(new_size, mem_pool);
 804         if (!new_size)
 805             return NULL;
 806     } else if (!new_size) {
 807         free_ex(ptr, mem_pool);
 808         return NULL;
 809     }
 810
 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) */
 824         }
 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);
 835         }
 836         TLSF_ADD_SIZE(tlsf, b);
 837         return (void *) b->ptr.buffer;
 838     }
 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);
 858             }
 859                         TLSF_ADD_SIZE(tlsf, b);
 860             return (void *) b->ptr.buffer;
 861         }
 862     }
 863
 864     if (!(ptr_aux = malloc_ex(new_size, mem_pool)))
 865         return NULL;
 866
 867     cpsize = ((b->size & BLOCK_SIZE) > new_size) ? new_size : (b->size & BLOCK_SIZE);
 868
 869     memcpy(ptr_aux, ptr, cpsize);
 870
 871     free_ex(ptr, mem_pool);
 872     return ptr_aux;
 873 }
 874
 875
 876 /******************************************************************/
 877 void *calloc_ex(size_t nelem, size_t elem_size, void *mem_pool)
 878 {
 879 /******************************************************************/
 880     void *ptr;
 881
 882     if (nelem <= 0 || elem_size <= 0)
 883         return NULL;
 884
 885     if (!(ptr = malloc_ex(nelem * elem_size, mem_pool)))
 886         return NULL;
 887     memset(ptr, 0, nelem * elem_size);
 888
 889     return ptr;
 890 }
 891
 892
 893
 894 #if _DEBUG_TLSF_
 895
 896 /***************  DEBUG FUNCTIONS   **************/
 897
 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.  */
 901
 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);
 906
 907 void dump_memory_region(unsigned char *mem_ptr, unsigned int size)
 908 {
 909
 910     unsigned long begin = (unsigned long) mem_ptr;
 911     unsigned long end = (unsigned long) mem_ptr + size;
 912     int column = 0;
 913
 914     begin >>= 2;
 915     begin <<= 2;
 916
 917     end >>= 2;
 918     end++;
 919     end <<= 2;
 920
 921     PRINT_MSG("\nMemory region dumped: 0x%lx - 0x%lx\n\n", begin, end);
 922
 923     column = 0;
 924     PRINT_MSG("0x%lx ", begin);
 925
 926     while (begin < end) {
 927         if (((unsigned char *) begin)[0] == 0)
 928             PRINT_MSG("00");
 929         else
 930             PRINT_MSG("%02x", ((unsigned char *) begin)[0]);
 931         if (((unsigned char *) begin)[1] == 0)
 932             PRINT_MSG("00 ");
 933         else
 934             PRINT_MSG("%02x ", ((unsigned char *) begin)[1]);
 935         begin += 2;
 936         column++;
 937         if (column == 8) {
 938             PRINT_MSG("\n0x%lx ", begin);
 939             column = 0;
 940         }
 941
 942     }
 943     PRINT_MSG("\n\n");
 944 }
 945
 946 void print_block(bhdr_t * b)
 947 {
 948     if (!b)
 949         return;
 950     PRINT_MSG(">> [%p] (", b);
 951     if ((b->size & BLOCK_SIZE))
 952         PRINT_MSG("%lu bytes, ", (unsigned long) (b->size & BLOCK_SIZE));
 953     else
 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);
 957     else
 958         PRINT_MSG("used, ");
 959     if ((b->size & PREV_STATE) == PREV_FREE)
 960         PRINT_MSG("prev. free [%p])\n", b->prev_hdr);
 961     else
 962         PRINT_MSG("prev used)\n");
 963 }
 964
 965 void print_tlsf(tlsf_t * tlsf)
 966 {
 967     bhdr_t *next;
 968     int i, j;
 969
 970     PRINT_MSG("\nTLSF at %p\n", tlsf);
 971
 972     PRINT_MSG("FL bitmap: 0x%x\n\n", (unsigned) tlsf->fl_bitmap);
 973
 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];
 979             if (next)
 980                 PRINT_MSG("-> [%d][%d]\n", i, j);
 981             while (next) {
 982                 print_block(next);
 983                 next = next->ptr.free_ptr.next;
 984             }
 985         }
 986     }
 987 }
 988
 989 void print_all_blocks(tlsf_t * tlsf)
 990 {
 991     area_info_t *ai;
 992     bhdr_t *next;
 993     PRINT_MSG("\nTLSF at %p\nALL BLOCKS\n\n", tlsf);
 994     ai = tlsf->area_head;
 995     while (ai) {
 996         next = (bhdr_t *) ((char *) ai - BHDR_OVERHEAD);
 997         while (next) {
 998             print_block(next);
 999             if ((next->size & BLOCK_SIZE))
1000                 next = GET_NEXT_BLOCK(next->ptr.buffer, next->size & BLOCK_SIZE);
1001             else
1002                 next = NULL;
1003         }
1004         ai = ai->next;
1005     }
1006 }
1007
1008 #endif