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