libs/pbd/tlsf.cc

   1 /*
   2  * Two Levels Segregate Fit memory allocator (TLSF)
   3  * Version 2.4.6
   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  * - Bug fixed (discovered by the rockbox project: www.rockbox.org).
  45  *
  46  * (Oct 23 2006) Adam Scislowicz:
  47  *
  48  * - Support for ARMv5 implemented
  49  *
  50  */
  51
  52 //#define TLSF_STATISTIC 1
  53
  54 #ifndef USE_PRINTF
  55 #define USE_PRINTF      (1)
  56 #endif
  57
  58 #include <assert.h>
  59 #include <stdlib.h>
  60 #include <string.h>
  61
  62 #ifndef TLSF_STATISTIC
  63 #define    TLSF_STATISTIC     (0)
  64 #endif
  65
  66 #if TLSF_STATISTIC
  67 #define TLSF_ADD_SIZE(tlsf, b) do {                                  \
  68         tlsf->used_size += (b->size & BLOCK_SIZE) + BHDR_OVERHEAD;   \
  69         if (tlsf->used_size > tlsf->max_size)                        \
  70             tlsf->max_size = tlsf->used_size;                        \
  71         } while(0)
  72
  73 #define TLSF_REMOVE_SIZE(tlsf, b) do {                                \
  74         tlsf->used_size -= (b->size & BLOCK_SIZE) + BHDR_OVERHEAD;    \
  75     } while(0)
  76 #else
  77 #define    TLSF_ADD_SIZE(tlsf, b)         do{}while(0)
  78 #define    TLSF_REMOVE_SIZE(tlsf, b)    do{}while(0)
  79 #endif
  80
  81 #include "pbd/tlsf.h"
  82
  83 #if !defined(__GNUC__)
  84 #ifndef __inline__
  85 #define __inline__
  86 #endif
  87 #endif
  88
  89 /* The  debug functions  only can  be used  when _DEBUG_TLSF_  is set. */
  90 #ifndef _DEBUG_TLSF_
  91 #define _DEBUG_TLSF_  (0)
  92 #endif
  93
  94 /*************************************************************************/
  95 /* Definition of the structures used by TLSF */
  96
  97
  98 /* Some IMPORTANT TLSF parameters */
  99 /* Unlike the preview TLSF versions, now they are statics */
 100 #define BLOCK_ALIGN (sizeof(void *) * 2)
 101
 102 #define MAX_FLI        (30)
 103 #define MAX_LOG2_SLI   (5)
 104 #define MAX_SLI        (1 << MAX_LOG2_SLI) /* MAX_SLI = 2^MAX_LOG2_SLI */
 105
 106 #define FLI_OFFSET     (6) /* tlsf structure just will manage blocks bigger */
 107 /* than 128 bytes */
 108 #define SMALL_BLOCK    (128)
 109 #define REAL_FLI       (MAX_FLI - FLI_OFFSET)
 110 #define MIN_BLOCK_SIZE (sizeof (free_ptr_t))
 111 #define BHDR_OVERHEAD  (sizeof (bhdr_t) - MIN_BLOCK_SIZE)
 112 #define TLSF_SIGNATURE (0x2A59FA59)
 113
 114 #define PTR_MASK       (sizeof(void *) - 1)
 115 #define BLOCK_SIZE     (0xFFFFFFFF - PTR_MASK)
 116
 117 #define GET_NEXT_BLOCK(_addr, _r) ((bhdr_t *) ((char *) (_addr) + (_r)))
 118 #define MEM_ALIGN          ((BLOCK_ALIGN) - 1)
 119 #define ROUNDUP_SIZE(_r)   (((_r) + MEM_ALIGN) & ~MEM_ALIGN)
 120 #define ROUNDDOWN_SIZE(_r) ((_r) & ~MEM_ALIGN)
 121 #define ROUNDUP(_x, _v)    ((((~(_x)) + 1) & ((_v)-1)) + (_x))
 122
 123 #define BLOCK_STATE  (0x1)
 124 #define PREV_STATE   (0x2)
 125
 126 /* bit 0 of the block size */
 127 #define FREE_BLOCK   (0x1)
 128 #define USED_BLOCK   (0x0)
 129
 130 /* bit 1 of the block size */
 131 #define PREV_FREE    (0x2)
 132 #define PREV_USED    (0x0)
 133
 134
 135 #ifdef USE_PRINTF
 136 #include <stdio.h>
 137 # define PRINT_MSG(fmt, args...) printf(fmt, ## args)
 138 # define ERROR_MSG(fmt, args...) printf(fmt, ## args)
 139 #else
 140 # if !defined(PRINT_MSG)
 141 #  define PRINT_MSG(fmt, args...)
 142 # endif
 143 # if !defined(ERROR_MSG)
 144 #  define ERROR_MSG(fmt, args...)
 145 # endif
 146 #endif
 147
 148 typedef unsigned int u32_t; /* NOTE: Make sure that this type is 4 bytes long on your computer */
 149 typedef unsigned char u8_t; /* NOTE: Make sure that this type is 1 byte on your computer */
 150
 151 typedef struct free_ptr_struct {
 152         struct bhdr_struct *prev;
 153         struct bhdr_struct *next;
 154 } free_ptr_t;
 155
 156 typedef struct bhdr_struct {
 157         /* This pointer is just valid if the first bit of size is set */
 158         struct bhdr_struct *prev_hdr;
 159         /* The size is stored in bytes */
 160         size_t size;      /* bit 0 indicates whether the block is used and */
 161         /* bit 1 allows to know whether the previous block is free */
 162         union {
 163                 struct free_ptr_struct free_ptr;
 164                 u8_t buffer[1]; /*sizeof(struct free_ptr_struct)]; */
 165         } ptr;
 166 } bhdr_t;
 167
 168 /* This structure is embedded at the beginning of each area, giving us
 169  * enough information to cope with a set of areas */
 170
 171 typedef struct area_info_struct {
 172         bhdr_t *end;
 173         struct area_info_struct *next;
 174 } area_info_t;
 175
 176 typedef struct TLSF_struct {
 177         /* the TLSF's structure signature */
 178         u32_t tlsf_signature;
 179
 180 #if TLSF_STATISTIC
 181         /* These can not be calculated outside tlsf because we
 182          * do not know the sizes when freeing/reallocing memory. */
 183         size_t used_size;
 184         size_t max_size;
 185 #endif
 186
 187         /* A linked list holding all the existing areas */
 188         area_info_t *area_head;
 189
 190         /* the first-level bitmap */
 191         /* This array should have a size of REAL_FLI bits */
 192         u32_t fl_bitmap;
 193
 194         /* the second-level bitmap */
 195         u32_t sl_bitmap[REAL_FLI];
 196
 197         bhdr_t *matrix[REAL_FLI][MAX_SLI];
 198 } tlsf_t;
 199
 200
 201 /******************************************************************/
 202 /**************     Helping functions    **************************/
 203 /******************************************************************/
 204 static __inline__ void set_bit(int nr, u32_t * addr);
 205 static __inline__ void clear_bit(int nr, u32_t * addr);
 206 static __inline__ int ls_bit(int x);
 207 static __inline__ int ms_bit(int x);
 208 static __inline__ void MAPPING_SEARCH(size_t * _r, int *_fl, int *_sl);
 209 static __inline__ void MAPPING_INSERT(size_t _r, int *_fl, int *_sl);
 210 static __inline__ bhdr_t *FIND_SUITABLE_BLOCK(tlsf_t * _tlsf, int *_fl, int *_sl);
 211 static __inline__ bhdr_t *process_area(void *area, size_t size);
 212
 213 static const int table[] = {
 214         -1, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4,
 215         4, 4,
 216         4, 4, 4, 4, 4, 4, 4,
 217         5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
 218         5,
 219         5, 5, 5, 5, 5, 5, 5,
 220         6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
 221         6,
 222         6, 6, 6, 6, 6, 6, 6,
 223         6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
 224         6,
 225         6, 6, 6, 6, 6, 6, 6,
 226         7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
 227         7,
 228         7, 7, 7, 7, 7, 7, 7,
 229         7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
 230         7,
 231         7, 7, 7, 7, 7, 7, 7,
 232         7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
 233         7,
 234         7, 7, 7, 7, 7, 7, 7,
 235         7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
 236         7,
 237         7, 7, 7, 7, 7, 7, 7
 238 };
 239
 240 static __inline__ int ls_bit(int i)
 241 {
 242         unsigned int a;
 243         unsigned int x = i & -i;
 244
 245         a = x <= 0xffff ? (x <= 0xff ? 0 : 8) : (x <= 0xffffff ? 16 : 24);
 246         return table[x >> a] + a;
 247 }
 248
 249 static __inline__ int ms_bit(int i)
 250 {
 251         unsigned int a;
 252         unsigned int x = (unsigned int) i;
 253
 254         a = x <= 0xffff ? (x <= 0xff ? 0 : 8) : (x <= 0xffffff ? 16 : 24);
 255         return table[x >> a] + a;
 256 }
 257
 258 static __inline__ void set_bit(int nr, u32_t * addr)
 259 {
 260         addr[nr >> 5] |= 1 << (nr & 0x1f);
 261 }
 262
 263 static __inline__ void clear_bit(int nr, u32_t * addr)
 264 {
 265         addr[nr >> 5] &= ~(1 << (nr & 0x1f));
 266 }
 267
 268 static __inline__ void MAPPING_SEARCH(size_t * _r, int *_fl, int *_sl)
 269 {
 270         int _t;
 271
 272         if (*_r < SMALL_BLOCK) {
 273                 *_fl = 0;
 274                 *_sl = *_r / (SMALL_BLOCK / MAX_SLI);
 275         } else {
 276                 _t = (1 << (ms_bit(*_r) - MAX_LOG2_SLI)) - 1;
 277                 *_r = *_r + _t;
 278                 *_fl = ms_bit(*_r);
 279                 *_sl = (*_r >> (*_fl - MAX_LOG2_SLI)) - MAX_SLI;
 280                 *_fl -= FLI_OFFSET;
 281                 /*if ((*_fl -= FLI_OFFSET) < 0) // FL wil be always >0!
 282                  *_fl = *_sl = 0;
 283                  */
 284                 *_r &= ~_t;
 285         }
 286 }
 287
 288 static __inline__ void MAPPING_INSERT(size_t _r, int *_fl, int *_sl)
 289 {
 290         if (_r < SMALL_BLOCK) {
 291                 *_fl = 0;
 292                 *_sl = _r / (SMALL_BLOCK / MAX_SLI);
 293         } else {
 294                 *_fl = ms_bit(_r);
 295                 *_sl = (_r >> (*_fl - MAX_LOG2_SLI)) - MAX_SLI;
 296                 *_fl -= FLI_OFFSET;
 297         }
 298 }
 299
 300
 301 static __inline__ bhdr_t *FIND_SUITABLE_BLOCK(tlsf_t * _tlsf, int *_fl, int *_sl)
 302 {
 303         u32_t _tmp = _tlsf->sl_bitmap[*_fl] & (~0 << *_sl);
 304         bhdr_t *_b = NULL;
 305
 306         if (_tmp) {
 307                 *_sl = ls_bit(_tmp);
 308                 _b = _tlsf->matrix[*_fl][*_sl];
 309         } else {
 310                 *_fl = ls_bit(_tlsf->fl_bitmap & (~0 << (*_fl + 1)));
 311                 if (*_fl > 0) {         /* likely */
 312                         *_sl = ls_bit(_tlsf->sl_bitmap[*_fl]);
 313                         _b = _tlsf->matrix[*_fl][*_sl];
 314                 }
 315         }
 316         return _b;
 317 }
 318
 319
 320 #define EXTRACT_BLOCK_HDR(_b, _tlsf, _fl, _sl) do {                  \
 321         _tlsf -> matrix [_fl] [_sl] = _b -> ptr.free_ptr.next;       \
 322         if (_tlsf -> matrix[_fl][_sl])                               \
 323             _tlsf -> matrix[_fl][_sl] -> ptr.free_ptr.prev = NULL;   \
 324         else {                                                       \
 325             clear_bit (_sl, &_tlsf -> sl_bitmap [_fl]);              \
 326             if (!_tlsf -> sl_bitmap [_fl])                           \
 327                 clear_bit (_fl, &_tlsf -> fl_bitmap);                \
 328         }                                                            \
 329         _b -> ptr.free_ptr.prev =  NULL;                             \
 330         _b -> ptr.free_ptr.next =  NULL;                             \
 331     }while(0)
 332
 333
 334 #define EXTRACT_BLOCK(_b, _tlsf, _fl, _sl) do {                                     \
 335         if (_b -> ptr.free_ptr.next)                                                \
 336             _b -> ptr.free_ptr.next -> ptr.free_ptr.prev = _b -> ptr.free_ptr.prev; \
 337         if (_b -> ptr.free_ptr.prev)                                                \
 338             _b -> ptr.free_ptr.prev -> ptr.free_ptr.next = _b -> ptr.free_ptr.next; \
 339         if (_tlsf -> matrix [_fl][_sl] == _b) {                                     \
 340             _tlsf -> matrix [_fl][_sl] = _b -> ptr.free_ptr.next;                   \
 341             if (!_tlsf -> matrix [_fl][_sl]) {                                      \
 342                 clear_bit (_sl, &_tlsf -> sl_bitmap[_fl]);                          \
 343                 if (!_tlsf -> sl_bitmap [_fl])                                      \
 344                     clear_bit (_fl, &_tlsf -> fl_bitmap);                           \
 345             }                                                                       \
 346         }                                                                           \
 347         _b -> ptr.free_ptr.prev = NULL;                                             \
 348         _b -> ptr.free_ptr.next = NULL;                                             \
 349     } while(0)
 350
 351 #define INSERT_BLOCK(_b, _tlsf, _fl, _sl) do {                       \
 352         _b -> ptr.free_ptr.prev = NULL;                              \
 353         _b -> ptr.free_ptr.next = _tlsf -> matrix [_fl][_sl];        \
 354         if (_tlsf -> matrix [_fl][_sl])                              \
 355             _tlsf -> matrix [_fl][_sl] -> ptr.free_ptr.prev = _b;    \
 356         _tlsf -> matrix [_fl][_sl] = _b;                             \
 357         set_bit (_sl, &_tlsf -> sl_bitmap [_fl]);                    \
 358         set_bit (_fl, &_tlsf -> fl_bitmap);                          \
 359     } while(0)
 360
 361 static __inline__ bhdr_t *process_area(void *area, size_t size)
 362 {
 363         bhdr_t *b, *lb, *ib;
 364         area_info_t *ai;
 365
 366         ib = (bhdr_t *) area;
 367         ib->size =
 368                 (sizeof(area_info_t) <
 369                  MIN_BLOCK_SIZE) ? MIN_BLOCK_SIZE : ROUNDUP_SIZE(sizeof(area_info_t)) | USED_BLOCK | PREV_USED;
 370         b = (bhdr_t *) GET_NEXT_BLOCK(ib->ptr.buffer, ib->size & BLOCK_SIZE);
 371         b->size = ROUNDDOWN_SIZE(size - 3 * BHDR_OVERHEAD - (ib->size & BLOCK_SIZE)) | USED_BLOCK | PREV_USED;
 372         b->ptr.free_ptr.prev = b->ptr.free_ptr.next = 0;
 373         lb = GET_NEXT_BLOCK(b->ptr.buffer, b->size & BLOCK_SIZE);
 374         lb->prev_hdr = b;
 375         lb->size = 0 | USED_BLOCK | PREV_FREE;
 376         ai = (area_info_t *) ib->ptr.buffer;
 377         ai->next = 0;
 378         ai->end = lb;
 379         return ib;
 380 }
 381
 382 /* ****************************************************************************/
 383
 384 #ifndef PLATFORM_WINDOWS
 385 #include <sys/mman.h>
 386 #endif
 387
 388 PBD::TLSF::TLSF (std::string name, size_t mem_pool_size)
 389     : _name (name)
 390 {
 391         mem_pool_size = ROUNDUP_SIZE (mem_pool_size);
 392         char * mem_pool = (char*) ::malloc (mem_pool_size);
 393
 394         assert (mem_pool);
 395         assert (mem_pool_size >= sizeof(tlsf_t) + BHDR_OVERHEAD * 8);
 396         assert (0 == (((unsigned long)mem_pool) & PTR_MASK));
 397
 398 #ifndef PLATFORM_WINDOWS
 399         memset (mem_pool, 0, mem_pool_size); // make resident
 400         mlock (mem_pool, mem_pool_size);
 401 #endif
 402
 403         bhdr_t *b, *ib;
 404
 405         tlsf_t *tlsf = (tlsf_t *) mem_pool;
 406         _mp = mem_pool;
 407
 408         /* Zeroing the memory pool */
 409         memset(_mp, 0, sizeof(tlsf_t));
 410
 411         tlsf->tlsf_signature = TLSF_SIGNATURE;
 412
 413         ib = process_area(GET_NEXT_BLOCK
 414                         (_mp, ROUNDUP_SIZE(sizeof(tlsf_t))), ROUNDDOWN_SIZE(mem_pool_size - sizeof(tlsf_t)));
 415         b = GET_NEXT_BLOCK(ib->ptr.buffer, ib->size & BLOCK_SIZE);
 416         _free(b->ptr.buffer);
 417         tlsf->area_head = (area_info_t *) ib->ptr.buffer;
 418
 419 #if TLSF_STATISTIC
 420         tlsf->used_size = mem_pool_size - (b->size & BLOCK_SIZE);
 421         tlsf->max_size = tlsf->used_size;
 422         PRINT_MSG ("TLSF '%s': free %ld, reserved: %ld [bytes]\n",
 423                         _name.c_str(),
 424                         b->size & BLOCK_SIZE,
 425                         get_used_size());
 426 #endif
 427 }
 428
 429 PBD::TLSF::~TLSF ()
 430 {
 431 #if TLSF_STATISTIC
 432         PRINT_MSG ("TLSF '%s': used: %ld, max: %ld [bytes]\n",
 433                         _name.c_str(),
 434                         get_used_size(),
 435                         get_max_size());
 436 #endif
 437         tlsf_t *tlsf = (tlsf_t *) _mp;
 438         tlsf->tlsf_signature = 0;
 439         ::free (_mp);
 440         _mp = NULL;
 441 }
 442
 443 size_t
 444 PBD::TLSF::get_used_size () const
 445 {
 446 #if TLSF_STATISTIC
 447         return ((tlsf_t *) _mp)->used_size;
 448 #else
 449         return 0;
 450 #endif
 451 }
 452
 453 size_t
 454 PBD::TLSF::get_max_size () const
 455 {
 456 #if TLSF_STATISTIC
 457         return ((tlsf_t *) _mp)->max_size;
 458 #else
 459         return 0;
 460 #endif
 461 }
 462
 463 void *
 464 PBD::TLSF::_malloc (size_t size)
 465 {
 466         tlsf_t *tlsf = (tlsf_t *) _mp;
 467         bhdr_t *b, *b2, *next_b;
 468         int fl, sl;
 469         size_t tmp_size;
 470
 471         size = (size < MIN_BLOCK_SIZE) ? MIN_BLOCK_SIZE : ROUNDUP_SIZE(size);
 472
 473         /* Rounding up the requested size and calculating fl and sl */
 474         MAPPING_SEARCH(&size, &fl, &sl);
 475
 476         /* Searching a free block, recall that this function changes the values of fl and sl,
 477                  so they are not longer valid when the function fails */
 478         b = FIND_SUITABLE_BLOCK(tlsf, &fl, &sl);
 479         if (!b)
 480                 return NULL; /* Not found */
 481
 482         EXTRACT_BLOCK_HDR(b, tlsf, fl, sl);
 483
 484         /*-- found: */
 485         next_b = GET_NEXT_BLOCK(b->ptr.buffer, b->size & BLOCK_SIZE);
 486         /* Should the block be split? */
 487         tmp_size = (b->size & BLOCK_SIZE) - size;
 488         if (tmp_size >= sizeof(bhdr_t)) {
 489                 tmp_size -= BHDR_OVERHEAD;
 490                 b2 = GET_NEXT_BLOCK(b->ptr.buffer, size);
 491                 b2->size = tmp_size | FREE_BLOCK | PREV_USED;
 492                 next_b->prev_hdr = b2;
 493                 MAPPING_INSERT(tmp_size, &fl, &sl);
 494                 INSERT_BLOCK(b2, tlsf, fl, sl);
 495
 496                 b->size = size | (b->size & PREV_STATE);
 497         } else {
 498                 next_b->size &= (~PREV_FREE);
 499                 b->size &= (~FREE_BLOCK); /* Now it's used */
 500         }
 501
 502         TLSF_ADD_SIZE(tlsf, b);
 503
 504         return (void *) b->ptr.buffer;
 505 }
 506
 507 void
 508 PBD::TLSF::_free (void *ptr)
 509 {
 510         tlsf_t *tlsf = (tlsf_t *) _mp;
 511         bhdr_t *b, *tmp_b;
 512         int fl = 0, sl = 0;
 513
 514         if (!ptr) {
 515                 return;
 516         }
 517         b = (bhdr_t *) ((char *) ptr - BHDR_OVERHEAD);
 518         b->size |= FREE_BLOCK;
 519
 520         TLSF_REMOVE_SIZE(tlsf, b);
 521
 522         b->ptr.free_ptr.prev = NULL;
 523         b->ptr.free_ptr.next = NULL;
 524         tmp_b = GET_NEXT_BLOCK(b->ptr.buffer, b->size & BLOCK_SIZE);
 525         if (tmp_b->size & FREE_BLOCK) {
 526                 MAPPING_INSERT(tmp_b->size & BLOCK_SIZE, &fl, &sl);
 527                 EXTRACT_BLOCK(tmp_b, tlsf, fl, sl);
 528                 b->size += (tmp_b->size & BLOCK_SIZE) + BHDR_OVERHEAD;
 529         }
 530         if (b->size & PREV_FREE) {
 531                 tmp_b = b->prev_hdr;
 532                 MAPPING_INSERT(tmp_b->size & BLOCK_SIZE, &fl, &sl);
 533                 EXTRACT_BLOCK(tmp_b, tlsf, fl, sl);
 534                 tmp_b->size += (b->size & BLOCK_SIZE) + BHDR_OVERHEAD;
 535                 b = tmp_b;
 536         }
 537         MAPPING_INSERT(b->size & BLOCK_SIZE, &fl, &sl);
 538         INSERT_BLOCK(b, tlsf, fl, sl);
 539
 540         tmp_b = GET_NEXT_BLOCK(b->ptr.buffer, b->size & BLOCK_SIZE);
 541         tmp_b->size |= PREV_FREE;
 542         tmp_b->prev_hdr = b;
 543 }
 544
 545 void*
 546 PBD::TLSF::_realloc(void *ptr, size_t new_size)
 547 {
 548         tlsf_t *tlsf = (tlsf_t *) _mp;
 549         void *ptr_aux;
 550         unsigned int cpsize;
 551         bhdr_t *b, *tmp_b, *next_b;
 552         int fl, sl;
 553         size_t tmp_size;
 554
 555         if (!ptr) {
 556                 if (new_size)
 557                         return (void *) _malloc (new_size);
 558                 if (!new_size)
 559                         return NULL;
 560         } else if (!new_size) {
 561                 _free(ptr);
 562                 return NULL;
 563         }
 564
 565         b = (bhdr_t *) ((char *) ptr - BHDR_OVERHEAD);
 566         next_b = GET_NEXT_BLOCK(b->ptr.buffer, b->size & BLOCK_SIZE);
 567         new_size = (new_size < MIN_BLOCK_SIZE) ? MIN_BLOCK_SIZE : ROUNDUP_SIZE(new_size);
 568         tmp_size = (b->size & BLOCK_SIZE);
 569         if (new_size <= tmp_size) {
 570                 TLSF_REMOVE_SIZE(tlsf, b);
 571                 if (next_b->size & FREE_BLOCK) {
 572                         MAPPING_INSERT(next_b->size & BLOCK_SIZE, &fl, &sl);
 573                         EXTRACT_BLOCK(next_b, tlsf, fl, sl);
 574                         tmp_size += (next_b->size & BLOCK_SIZE) + BHDR_OVERHEAD;
 575                         next_b = GET_NEXT_BLOCK(next_b->ptr.buffer, next_b->size & BLOCK_SIZE);
 576                         /* We allways reenter this free block because tmp_size will
 577                                  be greater then sizeof (bhdr_t) */
 578                 }
 579                 tmp_size -= new_size;
 580                 if (tmp_size >= sizeof(bhdr_t)) {
 581                         tmp_size -= BHDR_OVERHEAD;
 582                         tmp_b = GET_NEXT_BLOCK(b->ptr.buffer, new_size);
 583                         tmp_b->size = tmp_size | FREE_BLOCK | PREV_USED;
 584                         next_b->prev_hdr = tmp_b;
 585                         next_b->size |= PREV_FREE;
 586                         MAPPING_INSERT(tmp_size, &fl, &sl);
 587                         INSERT_BLOCK(tmp_b, tlsf, fl, sl);
 588                         b->size = new_size | (b->size & PREV_STATE);
 589                 }
 590                 TLSF_ADD_SIZE(tlsf, b);
 591                 return (void *) b->ptr.buffer;
 592         }
 593         if ((next_b->size & FREE_BLOCK)) {
 594                 if (new_size <= (tmp_size + (next_b->size & BLOCK_SIZE))) {
 595                         TLSF_REMOVE_SIZE(tlsf, b);
 596                         MAPPING_INSERT(next_b->size & BLOCK_SIZE, &fl, &sl);
 597                         EXTRACT_BLOCK(next_b, tlsf, fl, sl);
 598                         b->size += (next_b->size & BLOCK_SIZE) + BHDR_OVERHEAD;
 599                         next_b = GET_NEXT_BLOCK(b->ptr.buffer, b->size & BLOCK_SIZE);
 600                         next_b->prev_hdr = b;
 601                         next_b->size &= ~PREV_FREE;
 602                         tmp_size = (b->size & BLOCK_SIZE) - new_size;
 603                         if (tmp_size >= sizeof(bhdr_t)) {
 604                                 tmp_size -= BHDR_OVERHEAD;
 605                                 tmp_b = GET_NEXT_BLOCK(b->ptr.buffer, new_size);
 606                                 tmp_b->size = tmp_size | FREE_BLOCK | PREV_USED;
 607                                 next_b->prev_hdr = tmp_b;
 608                                 next_b->size |= PREV_FREE;
 609                                 MAPPING_INSERT(tmp_size, &fl, &sl);
 610                                 INSERT_BLOCK(tmp_b, tlsf, fl, sl);
 611                                 b->size = new_size | (b->size & PREV_STATE);
 612                         }
 613                         TLSF_ADD_SIZE(tlsf, b);
 614                         return (void *) b->ptr.buffer;
 615                 }
 616         }
 617
 618         if (!(ptr_aux = _malloc (new_size))){
 619                 return NULL;
 620         }
 621
 622         cpsize = ((b->size & BLOCK_SIZE) > new_size) ? new_size : (b->size & BLOCK_SIZE);
 623
 624         memcpy(ptr_aux, ptr, cpsize);
 625
 626         _free(ptr);
 627         return ptr_aux;
 628 }