src/tlsf.c

   1 /*
   2  * netsniff-ng - the packet sniffing beast
   3  * By Daniel Borkmann <daniel@netsniff-ng.org>
   4  * Copyright 2011 Daniel Borkmann.
   5  * Subject to the GPL.
   6  */
   7
   8 /*
   9  * Two Levels Segregate Fit memory allocator (TLSF), Version 2.4.6
  10  * Written by Miguel Masmano Tello <mimastel@doctor.upv.es>
  11  * Thanks to Ismael Ripoll for his suggestions and reviews
  12  * Copyright (C) 2008, 2007, 2006, 2005, 2004
  13  * This code is released using a dual license strategy: GPL/LGPL
  14  * You can choose the licence that better fits your requirements.
  15  * Released under the terms of the GNU General Public License Version 2.0
  16  * Released under the terms of the GNU Lesser General Public License Version 2.1
  17  */
  18
  19 /*
  20  * Code contributions:
  21  * (Jul 28 2007)  Herman ten Brugge <hermantenbrugge@home.nl>:
  22  * - Add 64 bit support. It now runs on x86_64 and solaris64.
  23  * - I also tested this on vxworks/32and solaris/32 and i386/32 processors.
  24  * - Remove assembly code. I could not measure any performance difference
  25  *   on my core2 processor. This also makes the code more portable.
  26  * - Moved defines/typedefs from tlsf.h to tlsf.c
  27  * - Changed MIN_BLOCK_SIZE to sizeof (free_ptr_t) and BHDR_OVERHEAD to
  28  *   (sizeof (bhdr_t) - MIN_BLOCK_SIZE). This does not change the fact
  29  *    that the minumum size is still sizeof
  30  *   (bhdr_t).
  31  * - Changed all C++ comment style to C style. (// -> /.* ... *./)
  32  * - Used ls_bit instead of ffs and ms_bit instead of fls. I did this to
  33  *   avoid confusion with the standard ffs function which returns
  34  *   different values.
  35  * - Created set_bit/clear_bit fuctions because they are not present
  36  *   on x86_64.
  37  * - Added locking support + extra file target.h to show how to use it.
  38  * - Added get_used_size function (REMOVED in 2.4)
  39  * - Added rtl_realloc and rtl_calloc function
  40  * - Implemented realloc clever support.
  41  * - Added some test code in the example directory.
  42  * - Bug fixed (discovered by the rockbox project: www.rockbox.org).
  43  * (Oct 23 2006) Adam Scislowicz:
  44  * - Support for ARMv5 implemented
  45  */
  46
  47 /*#define USE_SBRK        (0) */
  48 /*#define USE_MMAP        (0) */
  49
  50 #ifndef USE_PRINTF
  51 #define USE_PRINTF      (1)
  52 #endif
  53
  54 #include <string.h>
  55
  56 #ifndef TLSF_USE_LOCKS
  57 #define TLSF_USE_LOCKS  (1)
  58 #endif
  59
  60 #ifndef TLSF_STATISTIC
  61 #define TLSF_STATISTIC  (0)
  62 #endif
  63
  64 #ifndef USE_MMAP
  65 #define USE_MMAP        (1)
  66 #endif
  67
  68 #ifndef USE_SBRK
  69 #define USE_SBRK        (1)
  70 #endif
  71
  72 #ifndef CHECK_DOUBLE_FREE
  73 #define CHECK_DOUBLE_FREE (0)
  74 #endif
  75
  76 #if TLSF_USE_LOCKS
  77 #include <pthread.h>
  78 #define TLSF_MLOCK_T            pthread_mutex_t
  79 #define TLSF_CREATE_LOCK(l)     pthread_mutex_init (l, NULL)
  80 #define TLSF_DESTROY_LOCK(l)    pthread_mutex_destroy(l)
  81 #define TLSF_ACQUIRE_LOCK(l)    pthread_mutex_lock(l)
  82 #define TLSF_RELEASE_LOCK(l)    pthread_mutex_unlock(l)
  83 #else
  84 #define TLSF_CREATE_LOCK(_unused_)   do{}while(0)
  85 #define TLSF_DESTROY_LOCK(_unused_)  do{}while(0)
  86 #define TLSF_ACQUIRE_LOCK(_unused_)  do{}while(0)
  87 #define TLSF_RELEASE_LOCK(_unused_)  do{}while(0)
  88 #endif
  89
  90 #if TLSF_STATISTIC
  91 #define TLSF_ADD_SIZE(tlsf, b) do {                                     \
  92         tlsf->used_size += (b->size & BLOCK_SIZE) + BHDR_OVERHEAD;      \
  93         if (tlsf->used_size > tlsf->max_size) {                         \
  94             tlsf->max_size = tlsf->used_size;                           \
  95         }                                                               \
  96     } while(0)
  97
  98 #define TLSF_REMOVE_SIZE(tlsf, b) do {                                  \
  99         tlsf->used_size -= (b->size & BLOCK_SIZE) + BHDR_OVERHEAD;      \
 100     } while(0)
 101 #else
 102 #define TLSF_ADD_SIZE(tlsf, b)       do{}while(0)
 103 #define TLSF_REMOVE_SIZE(tlsf, b)    do{}while(0)
 104 #endif
 105
 106 #if USE_MMAP || USE_SBRK
 107 #include <unistd.h>
 108 #endif
 109
 110 #if USE_MMAP
 111 #include <sys/mman.h>
 112 #endif
 113
 114 #include "tlsf.h"
 115
 116 #if !defined(__GNUC__)
 117 #ifndef __inline__
 118 #define __inline__
 119 #endif
 120 #endif
 121
 122 /* The  debug functions  only can  be used  when _DEBUG_TLSF_  is set. */
 123 #ifndef _DEBUG_TLSF_
 124 #define _DEBUG_TLSF_  (0)
 125 #endif
 126
 127 /*************************************************************************/
 128 /* Definition of the structures used by TLSF */
 129
 130 /* Some IMPORTANT TLSF parameters */
 131 /* Unlike the preview TLSF versions, now they are statics */
 132 #define BLOCK_ALIGN (sizeof(void *) * 2)
 133
 134 #define MAX_FLI         (30)
 135 #define MAX_LOG2_SLI    (5)
 136 #define MAX_SLI         (1 << MAX_LOG2_SLI)     /* MAX_SLI = 2^MAX_LOG2_SLI */
 137
 138 #define FLI_OFFSET      (6)     /* tlsf structure just will manage blocks bigger */
 139 /* than 128 bytes */
 140 #define SMALL_BLOCK     (128)
 141 #define REAL_FLI        (MAX_FLI - FLI_OFFSET)
 142 #define MIN_BLOCK_SIZE  (sizeof (free_ptr_t))
 143 #define BHDR_OVERHEAD   (sizeof (bhdr_t) - MIN_BLOCK_SIZE)
 144 #define TLSF_SIGNATURE  (0x2A59FA59)
 145
 146 #define PTR_MASK        (sizeof(void *) - 1)
 147 #define BLOCK_SIZE      (0xFFFFFFFF - PTR_MASK)
 148
 149 #define GET_NEXT_BLOCK(_addr, _r) ((bhdr_t *) ((char *) (_addr) + (_r)))
 150 #define MEM_ALIGN                 ((BLOCK_ALIGN) - 1)
 151 #define ROUNDUP_SIZE(_r)          (((_r) + MEM_ALIGN) & ~MEM_ALIGN)
 152 #define ROUNDDOWN_SIZE(_r)        ((_r) & ~MEM_ALIGN)
 153 #define ROUNDUP(_x, _v)           ((((~(_x)) + 1) & ((_v)-1)) + (_x))
 154
 155 #define BLOCK_STATE     (0x1)
 156 #define PREV_STATE      (0x2)
 157
 158 /* bit 0 of the block size */
 159 #define FREE_BLOCK      (0x1)
 160 #define USED_BLOCK      (0x0)
 161
 162 /* bit 1 of the block size */
 163 #define PREV_FREE       (0x2)
 164 #define PREV_USED       (0x0)
 165
 166 #define DEFAULT_AREA_SIZE (1024*10)
 167
 168 #ifdef USE_MMAP
 169 #define PAGE_SIZE (getpagesize())
 170 #endif
 171
 172 #ifdef USE_PRINTF
 173 #include <stdio.h>
 174 #define PRINT_MSG(fmt, args...) printf(fmt, ## args)
 175 #define ERROR_MSG(fmt, args...) fprintf(stderr, fmt, ## args)
 176 #else
 177 #if !defined(PRINT_MSG)
 178 #define PRINT_MSG(fmt, args...)
 179 #endif
 180 #if !defined(ERROR_MSG)
 181 #define ERROR_MSG(fmt, args...)
 182 #endif
 183 #endif
 184
 185 #ifndef ATTRIBUTE_UNUSED
 186 #if defined(__GNUC__)
 187 #define ATTRIBUTE_UNUSED        __attribute__ ((__unused__))
 188 #else
 189 #define ATTRIBUTE_UNUSED
 190 #endif
 191 #endif
 192
 193 typedef unsigned int u32_t;     /* NOTE: Make sure that this type is 4 bytes long on your computer */
 194 typedef unsigned char u8_t;     /* NOTE: Make sure that this type is 1 byte on your computer */
 195
 196 typedef struct free_ptr_struct {
 197         struct bhdr_struct *prev;
 198         struct bhdr_struct *next;
 199 } free_ptr_t;
 200
 201 typedef struct bhdr_struct {
 202         /* This pointer is just valid if the first bit of size is set */
 203         struct bhdr_struct *prev_hdr;
 204         /* The size is stored in bytes */
 205         size_t size;            /* bit 0 indicates whether the block is used and */
 206         /* bit 1 allows to know whether the previous block is free */
 207         union {
 208                 struct free_ptr_struct free_ptr;
 209                 u8_t buffer[1]; /*sizeof(struct free_ptr_struct)]; */
 210         } ptr;
 211 } bhdr_t;
 212
 213 /* This structure is embedded at the beginning of each area, giving us
 214  * enough information to cope with a set of areas */
 215
 216 typedef struct area_info_struct {
 217         bhdr_t *end;
 218         struct area_info_struct *next;
 219 } area_info_t;
 220
 221 typedef struct TLSF_struct {
 222         /* the TLSF's structure signature */
 223         u32_t tlsf_signature;
 224
 225 #if TLSF_USE_LOCKS
 226         TLSF_MLOCK_T lock;
 227 #endif
 228
 229 #if TLSF_STATISTIC
 230         /* These can not be calculated outside tlsf because we
 231          * do not know the sizes when freeing/reallocing memory. */
 232         size_t used_size;
 233         size_t max_size;
 234 #endif
 235
 236         /* A linked list holding all the existing areas */
 237         area_info_t *area_head;
 238
 239         /* the first-level bitmap */
 240         /* This array should have a size of REAL_FLI bits */
 241         u32_t fl_bitmap;
 242
 243         /* the second-level bitmap */
 244         u32_t sl_bitmap[REAL_FLI];
 245
 246         bhdr_t *matrix[REAL_FLI][MAX_SLI];
 247 } tlsf_t;
 248
 249 /******************************************************************/
 250 /**************     Helping functions    **************************/
 251 /******************************************************************/
 252 static __inline__ void set_bit(int nr, u32_t * addr);
 253 static __inline__ void clear_bit(int nr, u32_t * addr);
 254 static __inline__ int ls_bit(int x);
 255 static __inline__ int ms_bit(int x);
 256 static __inline__ void MAPPING_SEARCH(size_t * _r, int *_fl, int *_sl);
 257 static __inline__ void MAPPING_INSERT(size_t _r, int *_fl, int *_sl);
 258 static __inline__ bhdr_t *FIND_SUITABLE_BLOCK(tlsf_t * _tlsf, int *_fl,
 259                                               int *_sl);
 260 static __inline__ bhdr_t *process_area(void *area, size_t size);
 261 #if USE_SBRK || USE_MMAP
 262 static __inline__ void *get_new_area(size_t * size);
 263 #endif
 264
 265 static const int table[] = {
 266         -1, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4,
 267         4, 4,
 268         4, 4, 4, 4, 4, 4, 4,
 269         5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
 270         5,
 271         5, 5, 5, 5, 5, 5, 5,
 272         6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
 273         6,
 274         6, 6, 6, 6, 6, 6, 6,
 275         6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
 276         6,
 277         6, 6, 6, 6, 6, 6, 6,
 278         7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
 279         7,
 280         7, 7, 7, 7, 7, 7, 7,
 281         7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
 282         7,
 283         7, 7, 7, 7, 7, 7, 7,
 284         7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
 285         7,
 286         7, 7, 7, 7, 7, 7, 7,
 287         7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
 288         7,
 289         7, 7, 7, 7, 7, 7, 7
 290 };
 291
 292 static __inline__ int ls_bit(int i)
 293 {
 294         unsigned int a;
 295         unsigned int x = i & -i;
 296
 297         a = x <= 0xffff ? (x <= 0xff ? 0 : 8) : (x <= 0xffffff ? 16 : 24);
 298         return table[x >> a] + a;
 299 }
 300
 301 static __inline__ int ms_bit(int i)
 302 {
 303         unsigned int a;
 304         unsigned int x = (unsigned int)i;
 305
 306         a = x <= 0xffff ? (x <= 0xff ? 0 : 8) : (x <= 0xffffff ? 16 : 24);
 307         return table[x >> a] + a;
 308 }
 309
 310 static __inline__ void set_bit(int nr, u32_t * addr)
 311 {
 312         addr[nr >> 5] |= 1 << (nr & 0x1f);
 313 }
 314
 315 static __inline__ void clear_bit(int nr, u32_t * addr)
 316 {
 317         addr[nr >> 5] &= ~(1 << (nr & 0x1f));
 318 }
 319
 320 static __inline__ void MAPPING_SEARCH(size_t * _r, int *_fl, int *_sl)
 321 {
 322         int _t;
 323
 324         if (*_r < SMALL_BLOCK) {
 325                 *_fl = 0;
 326                 *_sl = *_r / (SMALL_BLOCK / MAX_SLI);
 327         } else {
 328                 _t = (1 << (ms_bit(*_r) - MAX_LOG2_SLI)) - 1;
 329                 *_r = *_r + _t;
 330                 *_fl = ms_bit(*_r);
 331                 *_sl = (*_r >> (*_fl - MAX_LOG2_SLI)) - MAX_SLI;
 332                 *_fl -= FLI_OFFSET;
 333                 /*if ((*_fl -= FLI_OFFSET) < 0) // FL wil be always >0!
 334                  *_fl = *_sl = 0;
 335                  */
 336                 *_r &= ~_t;
 337         }
 338 }
 339
 340 static __inline__ void MAPPING_INSERT(size_t _r, int *_fl, int *_sl)
 341 {
 342         if (_r < SMALL_BLOCK) {
 343                 *_fl = 0;
 344                 *_sl = _r / (SMALL_BLOCK / MAX_SLI);
 345         } else {
 346                 *_fl = ms_bit(_r);
 347                 *_sl = (_r >> (*_fl - MAX_LOG2_SLI)) - MAX_SLI;
 348                 *_fl -= FLI_OFFSET;
 349         }
 350 }
 351
 352 static __inline__ bhdr_t *FIND_SUITABLE_BLOCK(tlsf_t * _tlsf, int *_fl,
 353                                               int *_sl)
 354 {
 355         u32_t _tmp = _tlsf->sl_bitmap[*_fl] & (~0 << *_sl);
 356         bhdr_t *_b = NULL;
 357
 358         if (_tmp) {
 359                 *_sl = ls_bit(_tmp);
 360                 _b = _tlsf->matrix[*_fl][*_sl];
 361         } else {
 362                 *_fl = ls_bit(_tlsf->fl_bitmap & (~0 << (*_fl + 1)));
 363                 if (*_fl > 0) { /* likely */
 364                         *_sl = ls_bit(_tlsf->sl_bitmap[*_fl]);
 365                         _b = _tlsf->matrix[*_fl][*_sl];
 366                 }
 367         }
 368         return _b;
 369 }
 370
 371 #define EXTRACT_BLOCK_HDR(_b, _tlsf, _fl, _sl) do {                                     \
 372                 _tlsf -> matrix [_fl] [_sl] = _b -> ptr.free_ptr.next;          \
 373                 if (_tlsf -> matrix[_fl][_sl])                                                          \
 374                         _tlsf -> matrix[_fl][_sl] -> ptr.free_ptr.prev = NULL;  \
 375                 else {                                                                                                          \
 376                         clear_bit (_sl, &_tlsf -> sl_bitmap [_fl]);                             \
 377                         if (!_tlsf -> sl_bitmap [_fl])                                                  \
 378                                 clear_bit (_fl, &_tlsf -> fl_bitmap);                           \
 379                 }                                                                                                                       \
 380                 _b -> ptr.free_ptr.prev =  NULL;                                \
 381                 _b -> ptr.free_ptr.next =  NULL;                                \
 382         }while(0)
 383
 384 #define EXTRACT_BLOCK(_b, _tlsf, _fl, _sl) do {                                                 \
 385                 if (_b -> ptr.free_ptr.next)                                                                    \
 386                         _b -> ptr.free_ptr.next -> ptr.free_ptr.prev = _b -> ptr.free_ptr.prev; \
 387                 if (_b -> ptr.free_ptr.prev)                                                                    \
 388                         _b -> ptr.free_ptr.prev -> ptr.free_ptr.next = _b -> ptr.free_ptr.next; \
 389                 if (_tlsf -> matrix [_fl][_sl] == _b) {                                                 \
 390                         _tlsf -> matrix [_fl][_sl] = _b -> ptr.free_ptr.next;           \
 391                         if (!_tlsf -> matrix [_fl][_sl]) {                                                      \
 392                                 clear_bit (_sl, &_tlsf -> sl_bitmap[_fl]);                              \
 393                                 if (!_tlsf -> sl_bitmap [_fl])                                                  \
 394                                         clear_bit (_fl, &_tlsf -> fl_bitmap);                           \
 395                         }                                                                                                                       \
 396                 }                                                                                                                               \
 397                 _b -> ptr.free_ptr.prev = NULL;                                 \
 398                 _b -> ptr.free_ptr.next = NULL;                                 \
 399         } while(0)
 400
 401 #define INSERT_BLOCK(_b, _tlsf, _fl, _sl) do {                                                  \
 402                 _b -> ptr.free_ptr.prev = NULL; \
 403                 _b -> ptr.free_ptr.next = _tlsf -> matrix [_fl][_sl]; \
 404                 if (_tlsf -> matrix [_fl][_sl])                                                                 \
 405                         _tlsf -> matrix [_fl][_sl] -> ptr.free_ptr.prev = _b;           \
 406                 _tlsf -> matrix [_fl][_sl] = _b;                                                                \
 407                 set_bit (_sl, &_tlsf -> sl_bitmap [_fl]);                                               \
 408                 set_bit (_fl, &_tlsf -> fl_bitmap);                                                             \
 409         } while(0)
 410
 411 #if USE_SBRK || USE_MMAP
 412 static __inline__ void *get_new_area(size_t * size)
 413 {
 414         void *area;
 415
 416 #if USE_SBRK
 417         area = (void *)sbrk(0);
 418         if (((void *)sbrk(*size)) != ((void *)-1))
 419                 return area;
 420 #endif
 421
 422 #ifndef MAP_ANONYMOUS
 423 /* https://dev.openwrt.org/ticket/322 */
 424 #define MAP_ANONYMOUS MAP_ANON
 425 #endif
 426
 427 #if USE_MMAP
 428         *size = ROUNDUP(*size, PAGE_SIZE);
 429         if ((area =
 430              mmap(0, *size, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS,
 431                   -1, 0)) != MAP_FAILED)
 432                 return area;
 433 #endif
 434         return ((void *)~0);
 435 }
 436 #endif
 437
 438 static __inline__ bhdr_t *process_area(void *area, size_t size)
 439 {
 440         bhdr_t *b, *lb, *ib;
 441         area_info_t *ai;
 442
 443         ib = (bhdr_t *) area;
 444         ib->size =
 445             (sizeof(area_info_t) <
 446              MIN_BLOCK_SIZE) ? MIN_BLOCK_SIZE :
 447             ROUNDUP_SIZE(sizeof(area_info_t)) | USED_BLOCK | PREV_USED;
 448         b = (bhdr_t *) GET_NEXT_BLOCK(ib->ptr.buffer, ib->size & BLOCK_SIZE);
 449         b->size =
 450             ROUNDDOWN_SIZE(size - 3 * BHDR_OVERHEAD -
 451                            (ib->size & BLOCK_SIZE)) | USED_BLOCK | PREV_USED;
 452         b->ptr.free_ptr.prev = b->ptr.free_ptr.next = 0;
 453         lb = GET_NEXT_BLOCK(b->ptr.buffer, b->size & BLOCK_SIZE);
 454         lb->prev_hdr = b;
 455         lb->size = 0 | USED_BLOCK | PREV_FREE;
 456         ai = (area_info_t *) ib->ptr.buffer;
 457         ai->next = 0;
 458         ai->end = lb;
 459         return ib;
 460 }
 461
 462 /******************************************************************/
 463 /******************** Begin of the allocator code *****************/
 464 /******************************************************************/
 465
 466 static char *mp = NULL;         /* Default memory pool. */
 467
 468 /******************************************************************/
 469 size_t init_memory_pool(size_t mem_pool_size, void *mem_pool)
 470 {
 471 /******************************************************************/
 472         tlsf_t *tlsf;
 473         bhdr_t *b, *ib;
 474
 475         if (!mem_pool || !mem_pool_size
 476             || mem_pool_size < sizeof(tlsf_t) + BHDR_OVERHEAD * 8) {
 477                 ERROR_MSG("init_memory_pool (): memory_pool invalid\n");
 478                 return (size_t) - 1;
 479         }
 480
 481         if (((unsigned long)mem_pool & PTR_MASK)) {
 482                 ERROR_MSG
 483                     ("init_memory_pool (): mem_pool must be aligned to a word\n");
 484                 return (size_t) - 1;
 485         }
 486         tlsf = (tlsf_t *) mem_pool;
 487         /* Check if already initialised */
 488         if (tlsf->tlsf_signature == TLSF_SIGNATURE) {
 489                 mp = (char *)mem_pool;
 490                 b = GET_NEXT_BLOCK(mp, ROUNDUP_SIZE(sizeof(tlsf_t)));
 491                 return b->size & BLOCK_SIZE;
 492         }
 493
 494         mp = (char *)mem_pool;
 495
 496         /* Zeroing the memory pool */
 497         memset(mem_pool, 0, sizeof(tlsf_t));
 498
 499         tlsf->tlsf_signature = TLSF_SIGNATURE;
 500
 501         TLSF_CREATE_LOCK(&tlsf->lock);
 502
 503         ib = process_area(GET_NEXT_BLOCK
 504                           (mem_pool, ROUNDUP_SIZE(sizeof(tlsf_t))),
 505                           ROUNDDOWN_SIZE(mem_pool_size - sizeof(tlsf_t)));
 506         b = GET_NEXT_BLOCK(ib->ptr.buffer, ib->size & BLOCK_SIZE);
 507         free_ex(b->ptr.buffer, tlsf);
 508         tlsf->area_head = (area_info_t *) ib->ptr.buffer;
 509
 510 #if TLSF_STATISTIC
 511         tlsf->used_size = mem_pool_size - (b->size & BLOCK_SIZE);
 512         tlsf->max_size = tlsf->used_size;
 513 #endif
 514
 515         return (b->size & BLOCK_SIZE);
 516 }
 517
 518 /******************************************************************/
 519 size_t add_new_area(void *area, size_t area_size, void *mem_pool)
 520 {
 521 /******************************************************************/
 522         tlsf_t *tlsf = (tlsf_t *) mem_pool;
 523         area_info_t *ptr, *ptr_prev, *ai;
 524         bhdr_t *ib0, *b0, *lb0, *ib1, *b1, *lb1, *next_b;
 525
 526         memset(area, 0, area_size);
 527         ptr = tlsf->area_head;
 528         ptr_prev = 0;
 529
 530         ib0 = process_area(area, area_size);
 531         b0 = GET_NEXT_BLOCK(ib0->ptr.buffer, ib0->size & BLOCK_SIZE);
 532         lb0 = GET_NEXT_BLOCK(b0->ptr.buffer, b0->size & BLOCK_SIZE);
 533
 534         /* Before inserting the new area, we have to merge this area with the
 535            already existing ones */
 536
 537         while (ptr) {
 538                 ib1 = (bhdr_t *) ((char *)ptr - BHDR_OVERHEAD);
 539                 b1 = GET_NEXT_BLOCK(ib1->ptr.buffer, ib1->size & BLOCK_SIZE);
 540                 lb1 = ptr->end;
 541
 542                 /* Merging the new area with the next physically contigous one */
 543                 if ((unsigned long)ib1 == (unsigned long)lb0 + BHDR_OVERHEAD) {
 544                         if (tlsf->area_head == ptr) {
 545                                 tlsf->area_head = ptr->next;
 546                                 ptr = ptr->next;
 547                         } else {
 548                                 ptr_prev->next = ptr->next;
 549                                 ptr = ptr->next;
 550                         }
 551
 552                         b0->size =
 553                             ROUNDDOWN_SIZE((b0->size & BLOCK_SIZE) +
 554                                            (ib1->size & BLOCK_SIZE) +
 555                                            2 *
 556                                            BHDR_OVERHEAD) | USED_BLOCK |
 557                             PREV_USED;
 558
 559                         b1->prev_hdr = b0;
 560                         lb0 = lb1;
 561
 562                         continue;
 563                 }
 564
 565                 /* Merging the new area with the previous physically contigous
 566                    one */
 567                 if ((unsigned long)lb1->ptr.buffer == (unsigned long)ib0) {
 568                         if (tlsf->area_head == ptr) {
 569                                 tlsf->area_head = ptr->next;
 570                                 ptr = ptr->next;
 571                         } else {
 572                                 ptr_prev->next = ptr->next;
 573                                 ptr = ptr->next;
 574                         }
 575
 576                         lb1->size =
 577                             ROUNDDOWN_SIZE((b0->size & BLOCK_SIZE) +
 578                                            (ib0->size & BLOCK_SIZE) +
 579                                            2 *
 580                                            BHDR_OVERHEAD) | USED_BLOCK | (lb1->
 581                                                                           size &
 582                                                                           PREV_STATE);
 583                         next_b =
 584                             GET_NEXT_BLOCK(lb1->ptr.buffer,
 585                                            lb1->size & BLOCK_SIZE);
 586                         next_b->prev_hdr = lb1;
 587                         b0 = lb1;
 588                         ib0 = ib1;
 589
 590                         continue;
 591                 }
 592                 ptr_prev = ptr;
 593                 ptr = ptr->next;
 594         }
 595
 596         /* Inserting the area in the list of linked areas */
 597         ai = (area_info_t *) ib0->ptr.buffer;
 598         ai->next = tlsf->area_head;
 599         ai->end = lb0;
 600         tlsf->area_head = ai;
 601         free_ex(b0->ptr.buffer, mem_pool);
 602         return (b0->size & BLOCK_SIZE);
 603 }
 604
 605 /******************************************************************/
 606 size_t get_used_size(void *mem_pool ATTRIBUTE_UNUSED)
 607 {
 608 /******************************************************************/
 609 #if TLSF_STATISTIC
 610         return ((tlsf_t *) mem_pool)->used_size;
 611 #else
 612         return 0;
 613 #endif
 614 }
 615
 616 /******************************************************************/
 617 size_t get_max_size(void *mem_pool ATTRIBUTE_UNUSED)
 618 {
 619 /******************************************************************/
 620 #if TLSF_STATISTIC
 621         return ((tlsf_t *) mem_pool)->max_size;
 622 #else
 623         return 0;
 624 #endif
 625 }
 626
 627 /******************************************************************/
 628 void destroy_memory_pool(void *mem_pool)
 629 {
 630 /******************************************************************/
 631         tlsf_t *tlsf = (tlsf_t *) mem_pool;
 632
 633         tlsf->tlsf_signature = 0;
 634
 635         TLSF_DESTROY_LOCK(&tlsf->lock);
 636
 637 }
 638
 639 /******************************************************************/
 640 void *tlsf_malloc(size_t size)
 641 {
 642 /******************************************************************/
 643         void *ret;
 644
 645 #if USE_MMAP || USE_SBRK
 646         if (!mp) {
 647                 size_t area_size;
 648                 void *area;
 649
 650                 area_size = sizeof(tlsf_t) + BHDR_OVERHEAD * 8; /* Just a safety constant */
 651                 area_size =
 652                     (area_size >
 653                      DEFAULT_AREA_SIZE) ? area_size : DEFAULT_AREA_SIZE;
 654                 area = get_new_area(&area_size);
 655                 if (area == ((void *)~0))
 656                         return NULL;    /* Not enough system memory */
 657                 init_memory_pool(area_size, area);
 658         }
 659 #endif
 660
 661         TLSF_ACQUIRE_LOCK(&((tlsf_t *) mp)->lock);
 662
 663         ret = malloc_ex(size, mp);
 664
 665         TLSF_RELEASE_LOCK(&((tlsf_t *) mp)->lock);
 666
 667         return ret;
 668 }
 669
 670 /******************************************************************/
 671 void tlsf_free(void *ptr)
 672 {
 673 /******************************************************************/
 674
 675         TLSF_ACQUIRE_LOCK(&((tlsf_t *) mp)->lock);
 676
 677         free_ex(ptr, mp);
 678
 679         TLSF_RELEASE_LOCK(&((tlsf_t *) mp)->lock);
 680
 681 }
 682
 683 /******************************************************************/
 684 void *tlsf_realloc(void *ptr, size_t size)
 685 {
 686 /******************************************************************/
 687         void *ret;
 688
 689 #if USE_MMAP || USE_SBRK
 690         if (!mp) {
 691                 return tlsf_malloc(size);
 692         }
 693 #endif
 694
 695         TLSF_ACQUIRE_LOCK(&((tlsf_t *) mp)->lock);
 696
 697         ret = realloc_ex(ptr, size, mp);
 698
 699         TLSF_RELEASE_LOCK(&((tlsf_t *) mp)->lock);
 700
 701         return ret;
 702 }
 703
 704 /******************************************************************/
 705 void *tlsf_calloc(size_t nelem, size_t elem_size)
 706 {
 707 /******************************************************************/
 708         void *ret;
 709
 710         TLSF_ACQUIRE_LOCK(&((tlsf_t *) mp)->lock);
 711
 712         ret = calloc_ex(nelem, elem_size, mp);
 713
 714         TLSF_RELEASE_LOCK(&((tlsf_t *) mp)->lock);
 715
 716         return ret;
 717 }
 718
 719 /******************************************************************/
 720 void *malloc_ex(size_t size, void *mem_pool)
 721 {
 722 /******************************************************************/
 723         tlsf_t *tlsf = (tlsf_t *) mem_pool;
 724         bhdr_t *b, *b2, *next_b;
 725         int fl, sl;
 726         size_t tmp_size;
 727
 728         size = (size < MIN_BLOCK_SIZE) ? MIN_BLOCK_SIZE : ROUNDUP_SIZE(size);
 729
 730         /* Rounding up the requested size and calculating fl and sl */
 731         MAPPING_SEARCH(&size, &fl, &sl);
 732
 733         /* Searching a free block, recall that this function changes the values of fl and sl,
 734            so they are not longer valid when the function fails */
 735         b = FIND_SUITABLE_BLOCK(tlsf, &fl, &sl);
 736 #if USE_MMAP || USE_SBRK
 737         if (!b) {
 738                 size_t area_size;
 739                 void *area;
 740                 /* Growing the pool size when needed */
 741                 area_size = size + BHDR_OVERHEAD * 8;   /* size plus enough room for the requered headers. */
 742                 area_size =
 743                     (area_size >
 744                      DEFAULT_AREA_SIZE) ? area_size : DEFAULT_AREA_SIZE;
 745                 area = get_new_area(&area_size);        /* Call sbrk or mmap */
 746                 if (area == ((void *)~0))
 747                         return NULL;    /* Not enough system memory */
 748                 add_new_area(area, area_size, mem_pool);
 749                 /* Rounding up the requested size and calculating fl and sl */
 750                 MAPPING_SEARCH(&size, &fl, &sl);
 751                 /* Searching a free block */
 752                 b = FIND_SUITABLE_BLOCK(tlsf, &fl, &sl);
 753         }
 754 #endif
 755         if (!b)
 756                 return NULL;    /* Not found */
 757
 758         EXTRACT_BLOCK_HDR(b, tlsf, fl, sl);
 759
 760     /*-- found: */
 761         next_b = GET_NEXT_BLOCK(b->ptr.buffer, b->size & BLOCK_SIZE);
 762         /* Should the block be split? */
 763         tmp_size = (b->size & BLOCK_SIZE) - size;
 764         if (tmp_size >= sizeof(bhdr_t)) {
 765                 tmp_size -= BHDR_OVERHEAD;
 766                 b2 = GET_NEXT_BLOCK(b->ptr.buffer, size);
 767                 b2->size = tmp_size | FREE_BLOCK | PREV_USED;
 768                 next_b->prev_hdr = b2;
 769                 MAPPING_INSERT(tmp_size, &fl, &sl);
 770                 INSERT_BLOCK(b2, tlsf, fl, sl);
 771
 772                 b->size = size | (b->size & PREV_STATE);
 773         } else {
 774                 next_b->size &= (~PREV_FREE);
 775                 b->size &= (~FREE_BLOCK);       /* Now it's used */
 776         }
 777
 778         TLSF_ADD_SIZE(tlsf, b);
 779
 780         return (void *)b->ptr.buffer;
 781 }
 782
 783 /******************************************************************/
 784 void free_ex(void *ptr, void *mem_pool)
 785 {
 786 /******************************************************************/
 787         tlsf_t *tlsf = (tlsf_t *) mem_pool;
 788         bhdr_t *b, *tmp_b;
 789         int fl = 0, sl = 0;
 790
 791         if (!ptr) {
 792                 return;
 793         }
 794         b = (bhdr_t *) ((char *)ptr - BHDR_OVERHEAD);
 795
 796 #ifdef CHECK_DOUBLE_FREE
 797         if (b->size & FREE_BLOCK) {
 798                 ERROR_MSG("free_ex(): double free %p\n", ptr);
 799                 return;
 800         }
 801 #endif
 802
 803         b->size |= FREE_BLOCK;
 804
 805         TLSF_REMOVE_SIZE(tlsf, b);
 806
 807         b->ptr.free_ptr.prev = NULL;
 808         b->ptr.free_ptr.next = NULL;
 809         tmp_b = GET_NEXT_BLOCK(b->ptr.buffer, b->size & BLOCK_SIZE);
 810         if (tmp_b->size & FREE_BLOCK) {
 811                 MAPPING_INSERT(tmp_b->size & BLOCK_SIZE, &fl, &sl);
 812                 EXTRACT_BLOCK(tmp_b, tlsf, fl, sl);
 813                 b->size += (tmp_b->size & BLOCK_SIZE) + BHDR_OVERHEAD;
 814         }
 815         if (b->size & PREV_FREE) {
 816                 tmp_b = b->prev_hdr;
 817                 MAPPING_INSERT(tmp_b->size & BLOCK_SIZE, &fl, &sl);
 818                 EXTRACT_BLOCK(tmp_b, tlsf, fl, sl);
 819                 tmp_b->size += (b->size & BLOCK_SIZE) + BHDR_OVERHEAD;
 820                 b = tmp_b;
 821         }
 822         MAPPING_INSERT(b->size & BLOCK_SIZE, &fl, &sl);
 823         INSERT_BLOCK(b, tlsf, fl, sl);
 824
 825         tmp_b = GET_NEXT_BLOCK(b->ptr.buffer, b->size & BLOCK_SIZE);
 826         tmp_b->size |= PREV_FREE;
 827         tmp_b->prev_hdr = b;
 828 }
 829
 830 /******************************************************************/
 831 void *realloc_ex(void *ptr, size_t new_size, void *mem_pool)
 832 {
 833 /******************************************************************/
 834         tlsf_t *tlsf = (tlsf_t *) mem_pool;
 835         void *ptr_aux;
 836         unsigned int cpsize;
 837         bhdr_t *b, *tmp_b, *next_b;
 838         int fl, sl;
 839         size_t tmp_size;
 840
 841         if (!ptr) {
 842                 if (new_size)
 843                         return (void *)malloc_ex(new_size, mem_pool);
 844                 if (!new_size)
 845                         return NULL;
 846         } else if (!new_size) {
 847                 free_ex(ptr, mem_pool);
 848                 return NULL;
 849         }
 850
 851         b = (bhdr_t *) ((char *)ptr - BHDR_OVERHEAD);
 852
 853 #ifdef CHECK_DOUBLE_FREE
 854         if (b->size & FREE_BLOCK) {
 855                 ERROR_MSG("realloc_ex(): invalid pointer %p\n", ptr);
 856                 return (void *)malloc_ex(new_size, mem_pool);
 857         }
 858 #endif
 859
 860         next_b = GET_NEXT_BLOCK(b->ptr.buffer, b->size & BLOCK_SIZE);
 861         new_size =
 862             (new_size <
 863              MIN_BLOCK_SIZE) ? MIN_BLOCK_SIZE : ROUNDUP_SIZE(new_size);
 864         tmp_size = (b->size & BLOCK_SIZE);
 865         if (new_size <= tmp_size) {
 866                 TLSF_REMOVE_SIZE(tlsf, b);
 867                 if (next_b->size & FREE_BLOCK) {
 868                         MAPPING_INSERT(next_b->size & BLOCK_SIZE, &fl, &sl);
 869                         EXTRACT_BLOCK(next_b, tlsf, fl, sl);
 870                         tmp_size += (next_b->size & BLOCK_SIZE) + BHDR_OVERHEAD;
 871                         next_b =
 872                             GET_NEXT_BLOCK(next_b->ptr.buffer,
 873                                            next_b->size & BLOCK_SIZE);
 874                         /* We allways reenter this free block because tmp_size will
 875                            be greater then sizeof (bhdr_t) */
 876                 }
 877                 tmp_size -= new_size;
 878                 if (tmp_size >= sizeof(bhdr_t)) {
 879                         tmp_size -= BHDR_OVERHEAD;
 880                         tmp_b = GET_NEXT_BLOCK(b->ptr.buffer, new_size);
 881                         tmp_b->size = tmp_size | FREE_BLOCK | PREV_USED;
 882                         next_b->prev_hdr = tmp_b;
 883                         next_b->size |= PREV_FREE;
 884                         MAPPING_INSERT(tmp_size, &fl, &sl);
 885                         INSERT_BLOCK(tmp_b, tlsf, fl, sl);
 886                         b->size = new_size | (b->size & PREV_STATE);
 887                 }
 888                 TLSF_ADD_SIZE(tlsf, b);
 889                 return (void *)b->ptr.buffer;
 890         }
 891         if ((next_b->size & FREE_BLOCK)) {
 892                 if (new_size <= (tmp_size + (next_b->size & BLOCK_SIZE))) {
 893                         TLSF_REMOVE_SIZE(tlsf, b);
 894                         MAPPING_INSERT(next_b->size & BLOCK_SIZE, &fl, &sl);
 895                         EXTRACT_BLOCK(next_b, tlsf, fl, sl);
 896                         b->size += (next_b->size & BLOCK_SIZE) + BHDR_OVERHEAD;
 897                         next_b =
 898                             GET_NEXT_BLOCK(b->ptr.buffer, b->size & BLOCK_SIZE);
 899                         next_b->prev_hdr = b;
 900                         next_b->size &= ~PREV_FREE;
 901                         tmp_size = (b->size & BLOCK_SIZE) - new_size;
 902                         if (tmp_size >= sizeof(bhdr_t)) {
 903                                 tmp_size -= BHDR_OVERHEAD;
 904                                 tmp_b = GET_NEXT_BLOCK(b->ptr.buffer, new_size);
 905                                 tmp_b->size = tmp_size | FREE_BLOCK | PREV_USED;
 906                                 next_b->prev_hdr = tmp_b;
 907                                 next_b->size |= PREV_FREE;
 908                                 MAPPING_INSERT(tmp_size, &fl, &sl);
 909                                 INSERT_BLOCK(tmp_b, tlsf, fl, sl);
 910                                 b->size = new_size | (b->size & PREV_STATE);
 911                         }
 912                         TLSF_ADD_SIZE(tlsf, b);
 913                         return (void *)b->ptr.buffer;
 914                 }
 915         }
 916
 917         if (!(ptr_aux = malloc_ex(new_size, mem_pool))) {
 918                 return NULL;
 919         }
 920
 921         cpsize =
 922             ((b->size & BLOCK_SIZE) >
 923              new_size) ? new_size : (b->size & BLOCK_SIZE);
 924
 925         memcpy(ptr_aux, ptr, cpsize);
 926
 927         free_ex(ptr, mem_pool);
 928         return ptr_aux;
 929 }
 930
 931 /******************************************************************/
 932 void *calloc_ex(size_t nelem, size_t elem_size, void *mem_pool)
 933 {
 934 /******************************************************************/
 935         void *ptr;
 936
 937         if (nelem <= 0 || elem_size <= 0)
 938                 return NULL;
 939
 940         if (!(ptr = malloc_ex(nelem * elem_size, mem_pool)))
 941                 return NULL;
 942         memset(ptr, 0, nelem * elem_size);
 943
 944         return ptr;
 945 }
 946
 947 #if _DEBUG_TLSF_
 948
 949 /***************  DEBUG FUNCTIONS   **************/
 950
 951 /* The following functions have been designed to ease the debugging of */
 952 /* the TLSF  structure.  For non-developing  purposes, it may  be they */
 953 /* haven't too much worth.  To enable them, _DEBUG_TLSF_ must be set.  */
 954
 955 extern void dump_memory_region(unsigned char *mem_ptr, unsigned int size);
 956 extern void print_block(bhdr_t * b);
 957 extern void print_tlsf(tlsf_t * tlsf);
 958 void print_all_blocks(tlsf_t * tlsf);
 959
 960 void dump_memory_region(unsigned char *mem_ptr, unsigned int size)
 961 {
 962
 963         unsigned long begin = (unsigned long)mem_ptr;
 964         unsigned long end = (unsigned long)mem_ptr + size;
 965         int column = 0;
 966
 967         begin >>= 2;
 968         begin <<= 2;
 969
 970         end >>= 2;
 971         end++;
 972         end <<= 2;
 973
 974         PRINT_MSG("\nMemory region dumped: 0x%lx - 0x%lx\n\n", begin, end);
 975
 976         column = 0;
 977         PRINT_MSG("0x%lx ", begin);
 978
 979         while (begin < end) {
 980                 if (((unsigned char *)begin)[0] == 0)
 981                         PRINT_MSG("00");
 982                 else
 983                         PRINT_MSG("%02x", ((unsigned char *)begin)[0]);
 984                 if (((unsigned char *)begin)[1] == 0)
 985                         PRINT_MSG("00 ");
 986                 else
 987                         PRINT_MSG("%02x ", ((unsigned char *)begin)[1]);
 988                 begin += 2;
 989                 column++;
 990                 if (column == 8) {
 991                         PRINT_MSG("\n0x%lx ", begin);
 992                         column = 0;
 993                 }
 994
 995         }
 996         PRINT_MSG("\n\n");
 997 }
 998
 999 void print_block(bhdr_t * b)
1000 {
1001         if (!b)
1002                 return;
1003         PRINT_MSG(">> [%p] (", b);
1004         if ((b->size & BLOCK_SIZE))
1005                 PRINT_MSG("%lu bytes, ", (unsigned long)(b->size & BLOCK_SIZE));
1006         else
1007                 PRINT_MSG("sentinel, ");
1008         if ((b->size & BLOCK_STATE) == FREE_BLOCK)
1009                 PRINT_MSG("free [%p, %p], ", b->ptr.free_ptr.prev,
1010                           b->ptr.free_ptr.next);
1011         else
1012                 PRINT_MSG("used, ");
1013         if ((b->size & PREV_STATE) == PREV_FREE)
1014                 PRINT_MSG("prev. free [%p])\n", b->prev_hdr);
1015         else
1016                 PRINT_MSG("prev used)\n");
1017 }
1018
1019 void print_tlsf(tlsf_t * tlsf)
1020 {
1021         bhdr_t *next;
1022         int i, j;
1023
1024         PRINT_MSG("\nTLSF at %p\n", tlsf);
1025
1026         PRINT_MSG("FL bitmap: 0x%x\n\n", (unsigned)tlsf->fl_bitmap);
1027
1028         for (i = 0; i < REAL_FLI; i++) {
1029                 if (tlsf->sl_bitmap[i])
1030                         PRINT_MSG("SL bitmap 0x%x\n",
1031                                   (unsigned)tlsf->sl_bitmap[i]);
1032                 for (j = 0; j < MAX_SLI; j++) {
1033                         next = tlsf->matrix[i][j];
1034                         if (next)
1035                                 PRINT_MSG("-> [%d][%d]\n", i, j);
1036                         while (next) {
1037                                 print_block(next);
1038                                 next = next->ptr.free_ptr.next;
1039                         }
1040                 }
1041         }
1042 }
1043
1044 void print_all_blocks(tlsf_t * tlsf)
1045 {
1046         area_info_t *ai;
1047         bhdr_t *next;
1048         PRINT_MSG("\nTLSF at %p\nALL BLOCKS\n\n", tlsf);
1049         ai = tlsf->area_head;
1050         while (ai) {
1051                 next = (bhdr_t *) ((char *)ai - BHDR_OVERHEAD);
1052                 while (next) {
1053                         print_block(next);
1054                         if ((next->size & BLOCK_SIZE))
1055                                 next =
1056                                     GET_NEXT_BLOCK(next->ptr.buffer,
1057                                                    next->size & BLOCK_SIZE);
1058                         else
1059                                 next = NULL;
1060                 }
1061                 ai = ai->next;
1062         }
1063 }
1064
1065 #endif