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
 397 #ifndef __MINGW64__ // cast fails
 398         assert (0 == (((unsigned long)mem_pool) & PTR_MASK));
 399 #endif
 400
 401 #ifndef PLATFORM_WINDOWS
 402         memset (mem_pool, 0, mem_pool_size); // make resident
 403         mlock (mem_pool, mem_pool_size);
 404 #endif
 405
 406         bhdr_t *b, *ib;
 407
 408         tlsf_t *tlsf = (tlsf_t *) mem_pool;
 409         _mp = mem_pool;
 410
 411         /* Zeroing the memory pool */
 412         memset(_mp, 0, sizeof(tlsf_t));
 413
 414         tlsf->tlsf_signature = TLSF_SIGNATURE;
 415
 416         ib = process_area(GET_NEXT_BLOCK
 417                         (_mp, ROUNDUP_SIZE(sizeof(tlsf_t))), ROUNDDOWN_SIZE(mem_pool_size - sizeof(tlsf_t)));
 418         b = GET_NEXT_BLOCK(ib->ptr.buffer, ib->size & BLOCK_SIZE);
 419         _free(b->ptr.buffer);
 420         tlsf->area_head = (area_info_t *) ib->ptr.buffer;
 421
 422 #if TLSF_STATISTIC
 423         tlsf->used_size = mem_pool_size - (b->size & BLOCK_SIZE);
 424         tlsf->max_size = tlsf->used_size;
 425         PRINT_MSG ("TLSF '%s': free %ld, reserved: %ld [bytes]\n",
 426                         _name.c_str(),
 427                         b->size & BLOCK_SIZE,
 428                         get_used_size());
 429 #endif
 430 }
 431
 432 PBD::TLSF::~TLSF ()
 433 {
 434 #if TLSF_STATISTIC
 435         PRINT_MSG ("TLSF '%s': used: %ld, max: %ld [bytes]\n",
 436                         _name.c_str(),
 437                         get_used_size(),
 438                         get_max_size());
 439 #endif
 440         tlsf_t *tlsf = (tlsf_t *) _mp;
 441         tlsf->tlsf_signature = 0;
 442         ::free (_mp);
 443         _mp = NULL;
 444 }
 445
 446 size_t
 447 PBD::TLSF::get_used_size () const
 448 {
 449 #if TLSF_STATISTIC
 450         return ((tlsf_t *) _mp)->used_size;
 451 #else
 452         return 0;
 453 #endif
 454 }
 455
 456 size_t
 457 PBD::TLSF::get_max_size () const
 458 {
 459 #if TLSF_STATISTIC
 460         return ((tlsf_t *) _mp)->max_size;
 461 #else
 462         return 0;
 463 #endif
 464 }
 465
 466 void *
 467 PBD::TLSF::_malloc (size_t size)
 468 {
 469         tlsf_t *tlsf = (tlsf_t *) _mp;
 470         bhdr_t *b, *b2, *next_b;
 471         int fl, sl;
 472         size_t tmp_size;
 473
 474         size = (size < MIN_BLOCK_SIZE) ? MIN_BLOCK_SIZE : ROUNDUP_SIZE(size);
 475
 476         /* Rounding up the requested size and calculating fl and sl */
 477         MAPPING_SEARCH(&size, &fl, &sl);
 478
 479         /* Searching a free block, recall that this function changes the values of fl and sl,
 480                  so they are not longer valid when the function fails */
 481         b = FIND_SUITABLE_BLOCK(tlsf, &fl, &sl);
 482         if (!b)
 483                 return NULL; /* Not found */
 484
 485         EXTRACT_BLOCK_HDR(b, tlsf, fl, sl);
 486
 487         /*-- found: */
 488         next_b = GET_NEXT_BLOCK(b->ptr.buffer, b->size & BLOCK_SIZE);
 489         /* Should the block be split? */
 490         tmp_size = (b->size & BLOCK_SIZE) - size;
 491         if (tmp_size >= sizeof(bhdr_t)) {
 492                 tmp_size -= BHDR_OVERHEAD;
 493                 b2 = GET_NEXT_BLOCK(b->ptr.buffer, size);
 494                 b2->size = tmp_size | FREE_BLOCK | PREV_USED;
 495                 next_b->prev_hdr = b2;
 496                 MAPPING_INSERT(tmp_size, &fl, &sl);
 497                 INSERT_BLOCK(b2, tlsf, fl, sl);
 498
 499                 b->size = size | (b->size & PREV_STATE);
 500         } else {
 501                 next_b->size &= (~PREV_FREE);
 502                 b->size &= (~FREE_BLOCK); /* Now it's used */
 503         }
 504
 505         TLSF_ADD_SIZE(tlsf, b);
 506
 507         return (void *) b->ptr.buffer;
 508 }
 509
 510 void
 511 PBD::TLSF::_free (void *ptr)
 512 {
 513         tlsf_t *tlsf = (tlsf_t *) _mp;
 514         bhdr_t *b, *tmp_b;
 515         int fl = 0, sl = 0;
 516
 517         if (!ptr) {
 518                 return;
 519         }
 520         b = (bhdr_t *) ((char *) ptr - BHDR_OVERHEAD);
 521         b->size |= FREE_BLOCK;
 522
 523         TLSF_REMOVE_SIZE(tlsf, b);
 524
 525         b->ptr.free_ptr.prev = NULL;
 526         b->ptr.free_ptr.next = NULL;
 527         tmp_b = GET_NEXT_BLOCK(b->ptr.buffer, b->size & BLOCK_SIZE);
 528         if (tmp_b->size & FREE_BLOCK) {
 529                 MAPPING_INSERT(tmp_b->size & BLOCK_SIZE, &fl, &sl);
 530                 EXTRACT_BLOCK(tmp_b, tlsf, fl, sl);
 531                 b->size += (tmp_b->size & BLOCK_SIZE) + BHDR_OVERHEAD;
 532         }
 533         if (b->size & PREV_FREE) {
 534                 tmp_b = b->prev_hdr;
 535                 MAPPING_INSERT(tmp_b->size & BLOCK_SIZE, &fl, &sl);
 536                 EXTRACT_BLOCK(tmp_b, tlsf, fl, sl);
 537                 tmp_b->size += (b->size & BLOCK_SIZE) + BHDR_OVERHEAD;
 538                 b = tmp_b;
 539         }
 540         MAPPING_INSERT(b->size & BLOCK_SIZE, &fl, &sl);
 541         INSERT_BLOCK(b, tlsf, fl, sl);
 542
 543         tmp_b = GET_NEXT_BLOCK(b->ptr.buffer, b->size & BLOCK_SIZE);
 544         tmp_b->size |= PREV_FREE;
 545         tmp_b->prev_hdr = b;
 546 }
 547
 548 void*
 549 PBD::TLSF::_realloc(void *ptr, size_t new_size)
 550 {
 551         tlsf_t *tlsf = (tlsf_t *) _mp;
 552         void *ptr_aux;
 553         unsigned int cpsize;
 554         bhdr_t *b, *tmp_b, *next_b;
 555         int fl, sl;
 556         size_t tmp_size;
 557
 558         if (!ptr) {
 559                 if (new_size)
 560                         return (void *) _malloc (new_size);
 561                 if (!new_size)
 562                         return NULL;
 563         } else if (!new_size) {
 564                 _free(ptr);
 565                 return NULL;
 566         }
 567
 568         b = (bhdr_t *) ((char *) ptr - BHDR_OVERHEAD);
 569         next_b = GET_NEXT_BLOCK(b->ptr.buffer, b->size & BLOCK_SIZE);
 570         new_size = (new_size < MIN_BLOCK_SIZE) ? MIN_BLOCK_SIZE : ROUNDUP_SIZE(new_size);
 571         tmp_size = (b->size & BLOCK_SIZE);
 572         if (new_size <= tmp_size) {
 573                 TLSF_REMOVE_SIZE(tlsf, b);
 574                 if (next_b->size & FREE_BLOCK) {
 575                         MAPPING_INSERT(next_b->size & BLOCK_SIZE, &fl, &sl);
 576                         EXTRACT_BLOCK(next_b, tlsf, fl, sl);
 577                         tmp_size += (next_b->size & BLOCK_SIZE) + BHDR_OVERHEAD;
 578                         next_b = GET_NEXT_BLOCK(next_b->ptr.buffer, next_b->size & BLOCK_SIZE);
 579                         /* We allways reenter this free block because tmp_size will
 580                                  be greater then sizeof (bhdr_t) */
 581                 }
 582                 tmp_size -= new_size;
 583                 if (tmp_size >= sizeof(bhdr_t)) {
 584                         tmp_size -= BHDR_OVERHEAD;
 585                         tmp_b = GET_NEXT_BLOCK(b->ptr.buffer, new_size);
 586                         tmp_b->size = tmp_size | FREE_BLOCK | PREV_USED;
 587                         next_b->prev_hdr = tmp_b;
 588                         next_b->size |= PREV_FREE;
 589                         MAPPING_INSERT(tmp_size, &fl, &sl);
 590                         INSERT_BLOCK(tmp_b, tlsf, fl, sl);
 591                         b->size = new_size | (b->size & PREV_STATE);
 592                 }
 593                 TLSF_ADD_SIZE(tlsf, b);
 594                 return (void *) b->ptr.buffer;
 595         }
 596         if ((next_b->size & FREE_BLOCK)) {
 597                 if (new_size <= (tmp_size + (next_b->size & BLOCK_SIZE))) {
 598                         TLSF_REMOVE_SIZE(tlsf, b);
 599                         MAPPING_INSERT(next_b->size & BLOCK_SIZE, &fl, &sl);
 600                         EXTRACT_BLOCK(next_b, tlsf, fl, sl);
 601                         b->size += (next_b->size & BLOCK_SIZE) + BHDR_OVERHEAD;
 602                         next_b = GET_NEXT_BLOCK(b->ptr.buffer, b->size & BLOCK_SIZE);
 603                         next_b->prev_hdr = b;
 604                         next_b->size &= ~PREV_FREE;
 605                         tmp_size = (b->size & BLOCK_SIZE) - new_size;
 606                         if (tmp_size >= sizeof(bhdr_t)) {
 607                                 tmp_size -= BHDR_OVERHEAD;
 608                                 tmp_b = GET_NEXT_BLOCK(b->ptr.buffer, new_size);
 609                                 tmp_b->size = tmp_size | FREE_BLOCK | PREV_USED;
 610                                 next_b->prev_hdr = tmp_b;
 611                                 next_b->size |= PREV_FREE;
 612                                 MAPPING_INSERT(tmp_size, &fl, &sl);
 613                                 INSERT_BLOCK(tmp_b, tlsf, fl, sl);
 614                                 b->size = new_size | (b->size & PREV_STATE);
 615                         }
 616                         TLSF_ADD_SIZE(tlsf, b);
 617                         return (void *) b->ptr.buffer;
 618                 }
 619         }
 620
 621         if (!(ptr_aux = _malloc (new_size))){
 622                 return NULL;
 623         }
 624
 625         cpsize = ((b->size & BLOCK_SIZE) > new_size) ? new_size : (b->size & BLOCK_SIZE);
 626
 627         memcpy(ptr_aux, ptr, cpsize);
 628
 629         _free(ptr);
 630         return ptr_aux;
 631 }