l4/pkg/tlsf/lib/contrib/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 #define PRINT_MSG(fmt, args...) printf(fmt, ## args)
 168 #define ERROR_MSG(fmt, args...) printf(fmt, ## args)
 169
 170 typedef unsigned int u32_t;     /* NOTE: Make sure that this type is 4 bytes long on your computer */
 171 typedef unsigned char u8_t;     /* NOTE: Make sure that this type is 1 byte on your computer */
 172
 173 typedef struct free_ptr_struct {
 174     struct bhdr_struct *prev;
 175     struct bhdr_struct *next;
 176 } free_ptr_t;
 177
 178 typedef struct bhdr_struct {
 179     /* This pointer is just valid if the first bit of size is set */
 180     struct bhdr_struct *prev_hdr;
 181     /* The size is stored in bytes */
 182     size_t size;                /* bit 0 indicates whether the block is used and */
 183     /* bit 1 allows to know whether the previous block is free */
 184     union {
 185         struct free_ptr_struct free_ptr;
 186         u8_t buffer[1];         /*sizeof(struct free_ptr_struct)]; */
 187     } ptr;
 188 } bhdr_t;
 189
 190 /* This structure is embedded at the beginning of each area, giving us
 191  * enough information to cope with a set of areas */
 192
 193 typedef struct area_info_struct {
 194     bhdr_t *end;
 195     struct area_info_struct *next;
 196 } area_info_t;
 197
 198 typedef struct TLSF_struct {
 199     /* the TLSF's structure signature */
 200     u32_t tlsf_signature;
 201
 202 #if TLSF_USE_LOCKS
 203     TLSF_MLOCK_T lock;
 204 #endif
 205
 206 #if TLSF_STATISTIC
 207     /* These can not be calculated outside tlsf because we
 208      * do not know the sizes when freeing/reallocing memory. */
 209     size_t used_size;
 210     size_t max_size;
 211 #endif
 212
 213     /* A linked list holding all the existing areas */
 214     area_info_t *area_head;
 215
 216     /* the first-level bitmap */
 217     /* This array should have a size of REAL_FLI bits */
 218     u32_t fl_bitmap;
 219
 220     /* the second-level bitmap */
 221     u32_t sl_bitmap[REAL_FLI];
 222
 223     bhdr_t *matrix[REAL_FLI][MAX_SLI];
 224 } tlsf_t;
 225
 226
 227 /******************************************************************/
 228 /**************     Helping functions    **************************/
 229 /******************************************************************/
 230 static __inline__ void set_bit(int nr, u32_t * addr);
 231 static __inline__ void clear_bit(int nr, u32_t * addr);
 232 static __inline__ int ls_bit(int x);
 233 static __inline__ int ms_bit(int x);
 234 static __inline__ void MAPPING_SEARCH(size_t * _r, int *_fl, int *_sl);
 235 static __inline__ void MAPPING_INSERT(size_t _r, int *_fl, int *_sl);
 236 static __inline__ bhdr_t *FIND_SUITABLE_BLOCK(tlsf_t * _tlsf, int *_fl, int *_sl);
 237 static __inline__ bhdr_t *process_area(void *area, size_t size);
 238 #if USE_SBRK || USE_MMAP
 239 static __inline__ void *get_new_area(size_t * size);
 240 #endif
 241
 242 static const int table[] = {
 243     -1, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4,
 244     4, 4,
 245     4, 4, 4, 4, 4, 4, 4,
 246     5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
 247     5,
 248     5, 5, 5, 5, 5, 5, 5,
 249     6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
 250     6,
 251     6, 6, 6, 6, 6, 6, 6,
 252     6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
 253     6,
 254     6, 6, 6, 6, 6, 6, 6,
 255     7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
 256     7,
 257     7, 7, 7, 7, 7, 7, 7,
 258     7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
 259     7,
 260     7, 7, 7, 7, 7, 7, 7,
 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 };
 268
 269 static __inline__ int ls_bit(int i)
 270 {
 271     unsigned int a;
 272     unsigned int x = i & -i;
 273
 274     a = x <= 0xffff ? (x <= 0xff ? 0 : 8) : (x <= 0xffffff ? 16 : 24);
 275     return table[x >> a] + a;
 276 }
 277
 278 static __inline__ int ms_bit(int i)
 279 {
 280     unsigned int a;
 281     unsigned int x = (unsigned int) i;
 282
 283     a = x <= 0xffff ? (x <= 0xff ? 0 : 8) : (x <= 0xffffff ? 16 : 24);
 284     return table[x >> a] + a;
 285 }
 286
 287 static __inline__ void set_bit(int nr, u32_t * addr)
 288 {
 289     addr[nr >> 5] |= 1 << (nr & 0x1f);
 290 }
 291
 292 static __inline__ void clear_bit(int nr, u32_t * addr)
 293 {
 294     addr[nr >> 5] &= ~(1 << (nr & 0x1f));
 295 }
 296
 297 static __inline__ void MAPPING_SEARCH(size_t * _r, int *_fl, int *_sl)
 298 {
 299     int _t;
 300
 301     if (*_r < SMALL_BLOCK) {
 302         *_fl = 0;
 303         *_sl = *_r / (SMALL_BLOCK / MAX_SLI);
 304     } else {
 305         _t = (1 << (ms_bit(*_r) - MAX_LOG2_SLI)) - 1;
 306         *_r = *_r + _t;
 307         *_fl = ms_bit(*_r);
 308         *_sl = (*_r >> (*_fl - MAX_LOG2_SLI)) - MAX_SLI;
 309         *_fl -= FLI_OFFSET;
 310         /*if ((*_fl -= FLI_OFFSET) < 0) // FL wil be always >0!
 311          *_fl = *_sl = 0;
 312          */
 313         *_r &= ~_t;
 314     }
 315 }
 316
 317 static __inline__ void MAPPING_INSERT(size_t _r, int *_fl, int *_sl)
 318 {
 319     if (_r < SMALL_BLOCK) {
 320         *_fl = 0;
 321         *_sl = _r / (SMALL_BLOCK / MAX_SLI);
 322     } else {
 323         *_fl = ms_bit(_r);
 324         *_sl = (_r >> (*_fl - MAX_LOG2_SLI)) - MAX_SLI;
 325         *_fl -= FLI_OFFSET;
 326     }
 327 }
 328
 329
 330 static __inline__ bhdr_t *FIND_SUITABLE_BLOCK(tlsf_t * _tlsf, int *_fl, int *_sl)
 331 {
 332     u32_t _tmp = _tlsf->sl_bitmap[*_fl] & (~0 << *_sl);
 333     bhdr_t *_b = NULL;
 334
 335     if (_tmp) {
 336         *_sl = ls_bit(_tmp);
 337         _b = _tlsf->matrix[*_fl][*_sl];
 338     } else {
 339         *_fl = ls_bit(_tlsf->fl_bitmap & (~0 << (*_fl + 1)));
 340         if (*_fl > 0) {         /* likely */
 341             *_sl = ls_bit(_tlsf->sl_bitmap[*_fl]);
 342             _b = _tlsf->matrix[*_fl][*_sl];
 343         }
 344     }
 345     return _b;
 346 }
 347
 348
 349 #define EXTRACT_BLOCK_HDR(_b, _tlsf, _fl, _sl) do {                                     \
 350                 _tlsf -> matrix [_fl] [_sl] = _b -> ptr.free_ptr.next;          \
 351                 if (_tlsf -> matrix[_fl][_sl])                                                          \
 352                         _tlsf -> matrix[_fl][_sl] -> ptr.free_ptr.prev = NULL;  \
 353                 else {                                                                                                          \
 354                         clear_bit (_sl, &_tlsf -> sl_bitmap [_fl]);                             \
 355                         if (!_tlsf -> sl_bitmap [_fl])                                                  \
 356                                 clear_bit (_fl, &_tlsf -> fl_bitmap);                           \
 357                 }                                                                                                                       \
 358                 _b -> ptr.free_ptr.prev =  NULL;                                \
 359                 _b -> ptr.free_ptr.next =  NULL;                                \
 360         }while(0)
 361
 362
 363 #define EXTRACT_BLOCK(_b, _tlsf, _fl, _sl) do {                                                 \
 364                 if (_b -> ptr.free_ptr.next)                                                                    \
 365                         _b -> ptr.free_ptr.next -> ptr.free_ptr.prev = _b -> ptr.free_ptr.prev; \
 366                 if (_b -> ptr.free_ptr.prev)                                                                    \
 367                         _b -> ptr.free_ptr.prev -> ptr.free_ptr.next = _b -> ptr.free_ptr.next; \
 368                 if (_tlsf -> matrix [_fl][_sl] == _b) {                                                 \
 369                         _tlsf -> matrix [_fl][_sl] = _b -> ptr.free_ptr.next;           \
 370                         if (!_tlsf -> matrix [_fl][_sl]) {                                                      \
 371                                 clear_bit (_sl, &_tlsf -> sl_bitmap[_fl]);                              \
 372                                 if (!_tlsf -> sl_bitmap [_fl])                                                  \
 373                                         clear_bit (_fl, &_tlsf -> fl_bitmap);                           \
 374                         }                                                                                                                       \
 375                 }                                                                                                                               \
 376                 _b -> ptr.free_ptr.prev = NULL;                                 \
 377                 _b -> ptr.free_ptr.next = NULL;                                 \
 378         } while(0)
 379
 380 #define INSERT_BLOCK(_b, _tlsf, _fl, _sl) do {                                                  \
 381                 _b -> ptr.free_ptr.prev = NULL; \
 382                 _b -> ptr.free_ptr.next = _tlsf -> matrix [_fl][_sl]; \
 383                 if (_tlsf -> matrix [_fl][_sl])                                                                 \
 384                         _tlsf -> matrix [_fl][_sl] -> ptr.free_ptr.prev = _b;           \
 385                 _tlsf -> matrix [_fl][_sl] = _b;                                                                \
 386                 set_bit (_sl, &_tlsf -> sl_bitmap [_fl]);                                               \
 387                 set_bit (_fl, &_tlsf -> fl_bitmap);                                                             \
 388         } while(0)
 389
 390 #if USE_SBRK || USE_MMAP
 391 static __inline__ void *get_new_area(size_t * size)
 392 {
 393     void *area;
 394
 395 #if USE_SBRK
 396     area = (void *)sbrk(0);
 397     if (((void *)sbrk(*size)) != ((void *) -1))
 398         return area;
 399 #endif
 400
 401 #if USE_MMAP
 402     *size = ROUNDUP(*size, PAGE_SIZE);
 403     if ((area = mmap(0, *size, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0)) != MAP_FAILED)
 404         return area;
 405 #endif
 406     return ((void *) ~0);
 407 }
 408 #endif
 409
 410 static __inline__ bhdr_t *process_area(void *area, size_t size)
 411 {
 412     bhdr_t *b, *lb, *ib;
 413     area_info_t *ai;
 414
 415     ib = (bhdr_t *) area;
 416     ib->size =
 417         (sizeof(area_info_t) <
 418          MIN_BLOCK_SIZE) ? MIN_BLOCK_SIZE : ROUNDUP_SIZE(sizeof(area_info_t)) | USED_BLOCK | PREV_USED;
 419     b = (bhdr_t *) GET_NEXT_BLOCK(ib->ptr.buffer, ib->size & BLOCK_SIZE);
 420     b->size = ROUNDDOWN_SIZE(size - 3 * BHDR_OVERHEAD - (ib->size & BLOCK_SIZE)) | USED_BLOCK | PREV_USED;
 421     b->ptr.free_ptr.prev = b->ptr.free_ptr.next = 0;
 422     lb = GET_NEXT_BLOCK(b->ptr.buffer, b->size & BLOCK_SIZE);
 423     lb->prev_hdr = b;
 424     lb->size = 0 | USED_BLOCK | PREV_FREE;
 425     ai = (area_info_t *) ib->ptr.buffer;
 426     ai->next = 0;
 427     ai->end = lb;
 428     return ib;
 429 }
 430
 431 /******************************************************************/
 432 /******************** Begin of the allocator code *****************/
 433 /******************************************************************/
 434
 435 static char *mp = NULL;         /* Default memory pool. */
 436
 437 /******************************************************************/
 438 size_t init_memory_pool(size_t mem_pool_size, void *mem_pool)
 439 {
 440 /******************************************************************/
 441     tlsf_t *tlsf;
 442     bhdr_t *b, *ib;
 443
 444     if (!mem_pool || !mem_pool_size || mem_pool_size < sizeof(tlsf_t) + BHDR_OVERHEAD * 8) {
 445         ERROR_MSG("init_memory_pool (): memory_pool invalid\n");
 446         return -1;
 447     }
 448
 449     if (((unsigned long) mem_pool & PTR_MASK)) {
 450         ERROR_MSG("init_memory_pool (): mem_pool must be aligned to a word\n");
 451         return -1;
 452     }
 453     tlsf = (tlsf_t *) mem_pool;
 454     /* Check if already initialised */
 455     if (tlsf->tlsf_signature == TLSF_SIGNATURE) {
 456         mp = mem_pool;
 457         b = GET_NEXT_BLOCK(mp, ROUNDUP_SIZE(sizeof(tlsf_t)));
 458         return b->size & BLOCK_SIZE;
 459     }
 460
 461     mp = mem_pool;
 462
 463     /* Zeroing the memory pool */
 464     memset(mem_pool, 0, sizeof(tlsf_t));
 465
 466     tlsf->tlsf_signature = TLSF_SIGNATURE;
 467
 468     TLSF_CREATE_LOCK(&tlsf->lock);
 469
 470     ib = process_area(GET_NEXT_BLOCK
 471                       (mem_pool, ROUNDUP_SIZE(sizeof(tlsf_t))), ROUNDDOWN_SIZE(mem_pool_size - sizeof(tlsf_t)));
 472     b = GET_NEXT_BLOCK(ib->ptr.buffer, ib->size & BLOCK_SIZE);
 473     free_ex(b->ptr.buffer, tlsf);
 474     tlsf->area_head = (area_info_t *) ib->ptr.buffer;
 475
 476 #if TLSF_STATISTIC
 477     tlsf->used_size = mem_pool_size - (b->size & BLOCK_SIZE);
 478     tlsf->max_size = tlsf->used_size;
 479 #endif
 480
 481     return (b->size & BLOCK_SIZE);
 482 }
 483
 484 /******************************************************************/
 485 size_t add_new_area(void *area, size_t area_size, void *mem_pool)
 486 {
 487 /******************************************************************/
 488     tlsf_t *tlsf = (tlsf_t *) mem_pool;
 489     area_info_t *ptr, *ptr_prev, *ai;
 490     bhdr_t *ib0, *b0, *lb0, *ib1, *b1, *lb1, *next_b;
 491
 492     memset(area, 0, area_size);
 493     ptr = tlsf->area_head;
 494     ptr_prev = 0;
 495
 496     ib0 = process_area(area, area_size);
 497     b0 = GET_NEXT_BLOCK(ib0->ptr.buffer, ib0->size & BLOCK_SIZE);
 498     lb0 = GET_NEXT_BLOCK(b0->ptr.buffer, b0->size & BLOCK_SIZE);
 499
 500     /* Before inserting the new area, we have to merge this area with the
 501        already existing ones */
 502
 503     while (ptr) {
 504         ib1 = (bhdr_t *) ((char *) ptr - BHDR_OVERHEAD);
 505         b1 = GET_NEXT_BLOCK(ib1->ptr.buffer, ib1->size & BLOCK_SIZE);
 506         lb1 = ptr->end;
 507
 508         /* Merging the new area with the next physically contigous one */
 509         if ((unsigned long) ib1 == (unsigned long) lb0 + BHDR_OVERHEAD) {
 510             if (tlsf->area_head == ptr) {
 511                 tlsf->area_head = ptr->next;
 512                 ptr = ptr->next;
 513             } else {
 514                 ptr_prev->next = ptr->next;
 515                 ptr = ptr->next;
 516             }
 517
 518             b0->size =
 519                 ROUNDDOWN_SIZE((b0->size & BLOCK_SIZE) +
 520                                (ib1->size & BLOCK_SIZE) + 2 * BHDR_OVERHEAD) | USED_BLOCK | PREV_USED;
 521
 522             b1->prev_hdr = b0;
 523             lb0 = lb1;
 524
 525             continue;
 526         }
 527
 528         /* Merging the new area with the previous physically contigous
 529            one */
 530         if ((unsigned long) lb1->ptr.buffer == (unsigned long) ib0) {
 531             if (tlsf->area_head == ptr) {
 532                 tlsf->area_head = ptr->next;
 533                 ptr = ptr->next;
 534             } else {
 535                 ptr_prev->next = ptr->next;
 536                 ptr = ptr->next;
 537             }
 538
 539             lb1->size =
 540                 ROUNDDOWN_SIZE((b0->size & BLOCK_SIZE) +
 541                                (ib0->size & BLOCK_SIZE) + 2 * BHDR_OVERHEAD) | USED_BLOCK | (lb1->size & PREV_STATE);
 542             next_b = GET_NEXT_BLOCK(lb1->ptr.buffer, lb1->size & BLOCK_SIZE);
 543             next_b->prev_hdr = lb1;
 544             b0 = lb1;
 545             ib0 = ib1;
 546
 547             continue;
 548         }
 549         ptr_prev = ptr;
 550         ptr = ptr->next;
 551     }
 552
 553     /* Inserting the area in the list of linked areas */
 554     ai = (area_info_t *) ib0->ptr.buffer;
 555     ai->next = tlsf->area_head;
 556     ai->end = lb0;
 557     tlsf->area_head = ai;
 558     free_ex(b0->ptr.buffer, mem_pool);
 559     return (b0->size & BLOCK_SIZE);
 560 }
 561
 562
 563 /******************************************************************/
 564 size_t get_used_size(void *mem_pool)
 565 {
 566 /******************************************************************/
 567 #if TLSF_STATISTIC
 568     return ((tlsf_t *) mem_pool)->used_size;
 569 #else
 570     return 0;
 571 #endif
 572 }
 573
 574 /******************************************************************/
 575 size_t get_max_size(void *mem_pool)
 576 {
 577 /******************************************************************/
 578 #if TLSF_STATISTIC
 579     return ((tlsf_t *) mem_pool)->max_size;
 580 #else
 581     return 0;
 582 #endif
 583 }
 584
 585 /******************************************************************/
 586 void destroy_memory_pool(void *mem_pool)
 587 {
 588 /******************************************************************/
 589     tlsf_t *tlsf = (tlsf_t *) mem_pool;
 590
 591     tlsf->tlsf_signature = 0;
 592
 593     TLSF_DESTROY_LOCK(&tlsf->lock);
 594
 595 }
 596
 597
 598 /******************************************************************/
 599 void *tlsf_malloc(size_t size)
 600 {
 601 /******************************************************************/
 602     void *ret;
 603
 604 #if USE_MMAP || USE_SBRK
 605     if (!mp) {
 606         size_t area_size;
 607         void *area;
 608
 609         area_size = sizeof(tlsf_t) + BHDR_OVERHEAD * 8; /* Just a safety constant */
 610         area_size = (area_size > DEFAULT_AREA_SIZE) ? area_size : DEFAULT_AREA_SIZE;
 611         area = get_new_area(&area_size);
 612         if (area == ((void *) ~0))
 613             return NULL;        /* Not enough system memory */
 614         init_memory_pool(area_size, area);
 615     }
 616 #endif
 617
 618     TLSF_ACQUIRE_LOCK(&((tlsf_t *)mp)->lock);
 619
 620     ret = malloc_ex(size, mp);
 621
 622     TLSF_RELEASE_LOCK(&((tlsf_t *)mp)->lock);
 623
 624     return ret;
 625 }
 626
 627 /******************************************************************/
 628 void tlsf_free(void *ptr)
 629 {
 630 /******************************************************************/
 631
 632     TLSF_ACQUIRE_LOCK(&((tlsf_t *)mp)->lock);
 633
 634     free_ex(ptr, mp);
 635
 636     TLSF_RELEASE_LOCK(&((tlsf_t *)mp)->lock);
 637
 638 }
 639
 640 /******************************************************************/
 641 void *tlsf_realloc(void *ptr, size_t size)
 642 {
 643 /******************************************************************/
 644     void *ret;
 645
 646 #if USE_MMAP || USE_SBRK
 647         if (!mp) {
 648                 return tlsf_malloc(size);
 649         }
 650 #endif
 651
 652     TLSF_ACQUIRE_LOCK(&((tlsf_t *)mp)->lock);
 653
 654     ret = realloc_ex(ptr, size, mp);
 655
 656     TLSF_RELEASE_LOCK(&((tlsf_t *)mp)->lock);
 657
 658     return ret;
 659 }
 660
 661 /******************************************************************/
 662 void *tlsf_calloc(size_t nelem, size_t elem_size)
 663 {
 664 /******************************************************************/
 665     void *ret;
 666
 667     TLSF_ACQUIRE_LOCK(&((tlsf_t *)mp)->lock);
 668
 669     ret = calloc_ex(nelem, elem_size, mp);
 670
 671     TLSF_RELEASE_LOCK(&((tlsf_t *)mp)->lock);
 672
 673     return ret;
 674 }
 675
 676 /******************************************************************/
 677 void *malloc_ex(size_t size, void *mem_pool)
 678 {
 679 /******************************************************************/
 680     tlsf_t *tlsf = (tlsf_t *) mem_pool;
 681     bhdr_t *b, *b2, *next_b;
 682     int fl, sl;
 683     size_t tmp_size;
 684
 685     size = (size < MIN_BLOCK_SIZE) ? MIN_BLOCK_SIZE : ROUNDUP_SIZE(size);
 686
 687     /* Rounding up the requested size and calculating fl and sl */
 688     MAPPING_SEARCH(&size, &fl, &sl);
 689
 690     /* Searching a free block, recall that this function changes the values of fl and sl,
 691        so they are not longer valid when the function fails */
 692     b = FIND_SUITABLE_BLOCK(tlsf, &fl, &sl);
 693 #if USE_MMAP || USE_SBRK
 694     if (!b) {
 695         size_t area_size;
 696         void *area;
 697         /* Growing the pool size when needed */
 698         area_size = size + BHDR_OVERHEAD * 8;   /* size plus enough room for the requered headers. */
 699         area_size = (area_size > DEFAULT_AREA_SIZE) ? area_size : DEFAULT_AREA_SIZE;
 700         area = get_new_area(&area_size);        /* Call sbrk or mmap */
 701         if (area == ((void *) ~0))
 702             return NULL;        /* Not enough system memory */
 703         add_new_area(area, area_size, mem_pool);
 704         /* Rounding up the requested size and calculating fl and sl */
 705         MAPPING_SEARCH(&size, &fl, &sl);
 706         /* Searching a free block */
 707         b = FIND_SUITABLE_BLOCK(tlsf, &fl, &sl);
 708     }
 709 #endif
 710     if (!b)
 711         return NULL;            /* Not found */
 712
 713     EXTRACT_BLOCK_HDR(b, tlsf, fl, sl);
 714
 715     /*-- found: */
 716     next_b = GET_NEXT_BLOCK(b->ptr.buffer, b->size & BLOCK_SIZE);
 717     /* Should the block be split? */
 718     tmp_size = (b->size & BLOCK_SIZE) - size;
 719     if (tmp_size >= sizeof(bhdr_t)) {
 720         tmp_size -= BHDR_OVERHEAD;
 721         b2 = GET_NEXT_BLOCK(b->ptr.buffer, size);
 722         b2->size = tmp_size | FREE_BLOCK | PREV_USED;
 723         next_b->prev_hdr = b2;
 724         MAPPING_INSERT(tmp_size, &fl, &sl);
 725         INSERT_BLOCK(b2, tlsf, fl, sl);
 726
 727         b->size = size | (b->size & PREV_STATE);
 728     } else {
 729         next_b->size &= (~PREV_FREE);
 730         b->size &= (~FREE_BLOCK);       /* Now it's used */
 731     }
 732
 733     TLSF_ADD_SIZE(tlsf, b);
 734
 735     return (void *) b->ptr.buffer;
 736 }
 737
 738 /******************************************************************/
 739 void free_ex(void *ptr, void *mem_pool)
 740 {
 741 /******************************************************************/
 742     tlsf_t *tlsf = (tlsf_t *) mem_pool;
 743     bhdr_t *b, *tmp_b;
 744     int fl = 0, sl = 0;
 745
 746     if (!ptr) {
 747         return;
 748     }
 749     b = (bhdr_t *) ((char *) ptr - BHDR_OVERHEAD);
 750     b->size |= FREE_BLOCK;
 751
 752     TLSF_REMOVE_SIZE(tlsf, b);
 753
 754     b->ptr.free_ptr.prev = NULL;
 755     b->ptr.free_ptr.next = NULL;
 756     tmp_b = GET_NEXT_BLOCK(b->ptr.buffer, b->size & BLOCK_SIZE);
 757     if (tmp_b->size & FREE_BLOCK) {
 758         MAPPING_INSERT(tmp_b->size & BLOCK_SIZE, &fl, &sl);
 759         EXTRACT_BLOCK(tmp_b, tlsf, fl, sl);
 760         b->size += (tmp_b->size & BLOCK_SIZE) + BHDR_OVERHEAD;
 761     }
 762     if (b->size & PREV_FREE) {
 763         tmp_b = b->prev_hdr;
 764         MAPPING_INSERT(tmp_b->size & BLOCK_SIZE, &fl, &sl);
 765         EXTRACT_BLOCK(tmp_b, tlsf, fl, sl);
 766         tmp_b->size += (b->size & BLOCK_SIZE) + BHDR_OVERHEAD;
 767         b = tmp_b;
 768     }
 769     MAPPING_INSERT(b->size & BLOCK_SIZE, &fl, &sl);
 770     INSERT_BLOCK(b, tlsf, fl, sl);
 771
 772     tmp_b = GET_NEXT_BLOCK(b->ptr.buffer, b->size & BLOCK_SIZE);
 773     tmp_b->size |= PREV_FREE;
 774     tmp_b->prev_hdr = b;
 775 }
 776
 777 /******************************************************************/
 778 void *realloc_ex(void *ptr, size_t new_size, void *mem_pool)
 779 {
 780 /******************************************************************/
 781     tlsf_t *tlsf = (tlsf_t *) mem_pool;
 782     void *ptr_aux;
 783     unsigned int cpsize;
 784     bhdr_t *b, *tmp_b, *next_b;
 785     int fl, sl;
 786     size_t tmp_size;
 787
 788     if (!ptr) {
 789         if (new_size)
 790             return (void *) malloc_ex(new_size, mem_pool);
 791         if (!new_size)
 792             return NULL;
 793     } else if (!new_size) {
 794         free_ex(ptr, mem_pool);
 795         return NULL;
 796     }
 797
 798     b = (bhdr_t *) ((char *) ptr - BHDR_OVERHEAD);
 799     next_b = GET_NEXT_BLOCK(b->ptr.buffer, b->size & BLOCK_SIZE);
 800     new_size = (new_size < MIN_BLOCK_SIZE) ? MIN_BLOCK_SIZE : ROUNDUP_SIZE(new_size);
 801     tmp_size = (b->size & BLOCK_SIZE);
 802     if (new_size <= tmp_size) {
 803         TLSF_REMOVE_SIZE(tlsf, b);
 804         if (next_b->size & FREE_BLOCK) {
 805             MAPPING_INSERT(next_b->size & BLOCK_SIZE, &fl, &sl);
 806             EXTRACT_BLOCK(next_b, tlsf, fl, sl);
 807             tmp_size += (next_b->size & BLOCK_SIZE) + BHDR_OVERHEAD;
 808             next_b = GET_NEXT_BLOCK(next_b->ptr.buffer, next_b->size & BLOCK_SIZE);
 809             /* We allways reenter this free block because tmp_size will
 810                be greater then sizeof (bhdr_t) */
 811         }
 812         tmp_size -= new_size;
 813         if (tmp_size >= sizeof(bhdr_t)) {
 814             tmp_size -= BHDR_OVERHEAD;
 815             tmp_b = GET_NEXT_BLOCK(b->ptr.buffer, new_size);
 816             tmp_b->size = tmp_size | FREE_BLOCK | PREV_USED;
 817             next_b->prev_hdr = tmp_b;
 818             next_b->size |= PREV_FREE;
 819             MAPPING_INSERT(tmp_size, &fl, &sl);
 820             INSERT_BLOCK(tmp_b, tlsf, fl, sl);
 821             b->size = new_size | (b->size & PREV_STATE);
 822         }
 823         TLSF_ADD_SIZE(tlsf, b);
 824         return (void *) b->ptr.buffer;
 825     }
 826     if ((next_b->size & FREE_BLOCK)) {
 827         if (new_size <= (tmp_size + (next_b->size & BLOCK_SIZE))) {
 828                         TLSF_REMOVE_SIZE(tlsf, b);
 829             MAPPING_INSERT(next_b->size & BLOCK_SIZE, &fl, &sl);
 830             EXTRACT_BLOCK(next_b, tlsf, fl, sl);
 831             b->size += (next_b->size & BLOCK_SIZE) + BHDR_OVERHEAD;
 832             next_b = GET_NEXT_BLOCK(b->ptr.buffer, b->size & BLOCK_SIZE);
 833             next_b->prev_hdr = b;
 834             next_b->size &= ~PREV_FREE;
 835             tmp_size = (b->size & BLOCK_SIZE) - new_size;
 836             if (tmp_size >= sizeof(bhdr_t)) {
 837                 tmp_size -= BHDR_OVERHEAD;
 838                 tmp_b = GET_NEXT_BLOCK(b->ptr.buffer, new_size);
 839                 tmp_b->size = tmp_size | FREE_BLOCK | PREV_USED;
 840                 next_b->prev_hdr = tmp_b;
 841                 next_b->size |= PREV_FREE;
 842                 MAPPING_INSERT(tmp_size, &fl, &sl);
 843                 INSERT_BLOCK(tmp_b, tlsf, fl, sl);
 844                 b->size = new_size | (b->size & PREV_STATE);
 845             }
 846                         TLSF_ADD_SIZE(tlsf, b);
 847             return (void *) b->ptr.buffer;
 848         }
 849     }
 850
 851     ptr_aux = malloc_ex(new_size, mem_pool);
 852
 853     cpsize = ((b->size & BLOCK_SIZE) > new_size) ? new_size : (b->size & BLOCK_SIZE);
 854
 855     memcpy(ptr_aux, ptr, cpsize);
 856
 857     free_ex(ptr, mem_pool);
 858     return ptr_aux;
 859 }
 860
 861
 862 /******************************************************************/
 863 void *calloc_ex(size_t nelem, size_t elem_size, void *mem_pool)
 864 {
 865 /******************************************************************/
 866     void *ptr;
 867
 868     if (nelem <= 0 || elem_size <= 0)
 869         return NULL;
 870
 871     if (!(ptr = malloc_ex(nelem * elem_size, mem_pool)))
 872         return NULL;
 873     memset(ptr, 0, nelem * elem_size);
 874
 875     return ptr;
 876 }
 877
 878
 879
 880 #if _DEBUG_TLSF_
 881
 882 /***************  DEBUG FUNCTIONS   **************/
 883
 884 /* The following functions have been designed to ease the debugging of */
 885 /* the TLSF  structure.  For non-developing  purposes, it may  be they */
 886 /* haven't too much worth.  To enable them, _DEBUG_TLSF_ must be set.  */
 887
 888 extern void dump_memory_region(unsigned char *mem_ptr, unsigned int size);
 889 extern void print_block(bhdr_t * b);
 890 extern void print_tlsf(tlsf_t * tlsf);
 891 void print_all_blocks(tlsf_t * tlsf);
 892
 893 void dump_memory_region(unsigned char *mem_ptr, unsigned int size)
 894 {
 895
 896     unsigned long begin = (unsigned long) mem_ptr;
 897     unsigned long end = (unsigned long) mem_ptr + size;
 898     int column = 0;
 899
 900     begin >>= 2;
 901     begin <<= 2;
 902
 903     end >>= 2;
 904     end++;
 905     end <<= 2;
 906
 907     PRINT_MSG("\nMemory region dumped: 0x%lx - 0x%lx\n\n", begin, end);
 908
 909     column = 0;
 910     PRINT_MSG("0x%lx ", begin);
 911
 912     while (begin < end) {
 913         if (((unsigned char *) begin)[0] == 0)
 914             PRINT_MSG("00");
 915         else
 916             PRINT_MSG("%02x", ((unsigned char *) begin)[0]);
 917         if (((unsigned char *) begin)[1] == 0)
 918             PRINT_MSG("00 ");
 919         else
 920             PRINT_MSG("%02x ", ((unsigned char *) begin)[1]);
 921         begin += 2;
 922         column++;
 923         if (column == 8) {
 924             PRINT_MSG("\n0x%lx ", begin);
 925             column = 0;
 926         }
 927
 928     }
 929     PRINT_MSG("\n\n");
 930 }
 931
 932 void print_block(bhdr_t * b)
 933 {
 934     if (!b)
 935         return;
 936     PRINT_MSG(">> [%p] (", b);
 937     if ((b->size & BLOCK_SIZE))
 938         PRINT_MSG("%lu bytes, ", (unsigned long) (b->size & BLOCK_SIZE));
 939     else
 940         PRINT_MSG("sentinel, ");
 941     if ((b->size & BLOCK_STATE) == FREE_BLOCK)
 942         PRINT_MSG("free [%p, %p], ", b->ptr.free_ptr.prev, b->ptr.free_ptr.next);
 943     else
 944         PRINT_MSG("used, ");
 945     if ((b->size & PREV_STATE) == PREV_FREE)
 946         PRINT_MSG("prev. free [%p])\n", b->prev_hdr);
 947     else
 948         PRINT_MSG("prev used)\n");
 949 }
 950
 951 void print_tlsf(tlsf_t * tlsf)
 952 {
 953     bhdr_t *next;
 954     int i, j;
 955
 956     PRINT_MSG("\nTLSF at %p\n", tlsf);
 957
 958     PRINT_MSG("FL bitmap: 0x%x\n\n", (unsigned) tlsf->fl_bitmap);
 959
 960     for (i = 0; i < REAL_FLI; i++) {
 961         if (tlsf->sl_bitmap[i])
 962             PRINT_MSG("SL bitmap 0x%x\n", (unsigned) tlsf->sl_bitmap[i]);
 963         for (j = 0; j < MAX_SLI; j++) {
 964             next = tlsf->matrix[i][j];
 965             if (next)
 966                 PRINT_MSG("-> [%d][%d]\n", i, j);
 967             while (next) {
 968                 print_block(next);
 969                 next = next->ptr.free_ptr.next;
 970             }
 971         }
 972     }
 973 }
 974
 975 void print_all_blocks(tlsf_t * tlsf)
 976 {
 977     area_info_t *ai;
 978     bhdr_t *next;
 979     PRINT_MSG("\nTLSF at %p\nALL BLOCKS\n\n", tlsf);
 980     ai = tlsf->area_head;
 981     while (ai) {
 982         next = (bhdr_t *) ((char *) ai - BHDR_OVERHEAD);
 983         while (next) {
 984             print_block(next);
 985             if ((next->size & BLOCK_SIZE))
 986                 next = GET_NEXT_BLOCK(next->ptr.buffer, next->size & BLOCK_SIZE);
 987             else
 988                 next = NULL;
 989         }
 990         ai = ai->next;
 991     }
 992 }
 993
 994 #endif