00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041
00042
00043
00044
00045
00046
00047
00048
00049
00050
00051
00052
00053
00054
00055
00056
00057 #ifdef __APPLE__
00058 #define _DARWIN_C_SOURCE
00059 #else
00060 #include "../fosi.h"
00061 #endif
00062
00063 #include <string.h>
00064
00065 #define TLSF_USE_LOCKS (1)
00066
00067 #ifndef TLSF_STATISTIC
00068 #define TLSF_STATISTIC (0)
00069 #endif
00070
00071 #ifndef USE_MMAP
00072 #define USE_MMAP (0)
00073 #endif
00074
00075 #ifndef USE_SBRK
00076 #define USE_SBRK (0)
00077 #endif
00078
00079
00080 #if TLSF_USE_LOCKS
00081 #include "target.h"
00082 #else
00083 #define TLSF_CREATE_LOCK(_unused_) do{}while(0)
00084 #define TLSF_DESTROY_LOCK(_unused_) do{}while(0)
00085 #define TLSF_ACQUIRE_LOCK(_unused_) do{}while(0)
00086 #define TLSF_RELEASE_LOCK(_unused_) do{}while(0)
00087 #endif
00088
00089 #if TLSF_STATISTIC
00090 #define TLSF_ADD_SIZE(tlsf, b) do { \
00091 tlsf->used_size += (b->size & BLOCK_SIZE) + BHDR_OVERHEAD; \
00092 if (tlsf->used_size > tlsf->max_size) \
00093 tlsf->max_size = tlsf->used_size; \
00094 } while(0)
00095
00096 #define TLSF_REMOVE_SIZE(tlsf, b) do { \
00097 tlsf->used_size -= (b->size & BLOCK_SIZE) + BHDR_OVERHEAD; \
00098 } while(0)
00099 #else
00100 #define TLSF_ADD_SIZE(tlsf, b) do{}while(0)
00101 #define TLSF_REMOVE_SIZE(tlsf, b) do{}while(0)
00102 #endif
00103
00104 #if USE_MMAP || USE_SBRK
00105 #include <unistd.h>
00106 #endif
00107
00108 #if USE_MMAP
00109 #include <sys/mman.h>
00110
00111 #ifdef __APPLE__
00112 #define TLSF_MAP MAP_PRIVATE | MAP_ANON
00113 #else
00114 #define TLSF_MAP MAP_PRIVATE | MAP_ANONYMOUS
00115 #endif
00116 #endif
00117
00118 #define ORO_MEMORY_POOL
00119 #include "tlsf.h"
00120
00121 #if !defined(__GNUC__)
00122 #ifndef __inline__
00123 #define __inline__
00124 #endif
00125 #endif
00126
00127
00128 #ifndef _DEBUG_TLSF_
00129 #define _DEBUG_TLSF_ (0)
00130 #endif
00131
00132
00133
00134
00135
00136
00137
00138 #define BLOCK_ALIGN (sizeof(void *) * 2)
00139
00140 #define MAX_FLI (30)
00141 #define MAX_LOG2_SLI (5)
00142 #define MAX_SLI (1 << MAX_LOG2_SLI)
00143
00144 #define FLI_OFFSET (6)
00145
00146 #define SMALL_BLOCK (128)
00147 #define REAL_FLI (MAX_FLI - FLI_OFFSET)
00148 #define MIN_BLOCK_SIZE (sizeof (free_ptr_t))
00149 #define BHDR_OVERHEAD (sizeof (bhdr_t) - MIN_BLOCK_SIZE)
00150 #define TLSF_SIGNATURE (0x2A59FA59)
00151
00152 #define PTR_MASK (sizeof(void *) - 1)
00153 #define BLOCK_SIZE (0xFFFFFFFF - PTR_MASK)
00154
00155 #define GET_NEXT_BLOCK(_addr, _r) ((bhdr_t *) ((char *) (_addr) + (_r)))
00156 #define MEM_ALIGN ((BLOCK_ALIGN) - 1)
00157 #define ROUNDUP_SIZE(_r) (((_r) + MEM_ALIGN) & ~MEM_ALIGN)
00158 #define ROUNDDOWN_SIZE(_r) ((_r) & ~MEM_ALIGN)
00159 #define ROUNDUP(_x, _v) ((((~(_x)) + 1) & ((_v)-1)) + (_x))
00160
00161 #define BLOCK_STATE (0x1)
00162 #define PREV_STATE (0x2)
00163
00164
00165 #define FREE_BLOCK (0x1)
00166 #define USED_BLOCK (0x0)
00167
00168
00169 #define PREV_FREE (0x2)
00170 #define PREV_USED (0x0)
00171
00172
00173 #define DEFAULT_AREA_SIZE (1024*10)
00174
00175 #if USE_MMAP
00176 #define TLSF_PAGE_SIZE (getpagesize())
00177 #endif
00178
00179 #define PRINT_MSG(fmt, args...) printf(fmt, ## args)
00180 #define ERROR_MSG(fmt, args...) printf(fmt, ## args)
00181
00182 typedef unsigned int u32_t;
00183 typedef unsigned char u8_t;
00184
00185 typedef struct free_ptr_struct {
00186 struct bhdr_struct *prev;
00187 struct bhdr_struct *next;
00188 } free_ptr_t;
00189
00190 typedef struct bhdr_struct {
00191
00192 struct bhdr_struct *prev_hdr;
00193
00194 size_t size;
00195
00196 union {
00197 struct free_ptr_struct free_ptr;
00198 u8_t buffer[1];
00199 } ptr;
00200 } bhdr_t;
00201
00202
00203
00204
00205 typedef struct area_info_struct {
00206 bhdr_t *end;
00207 struct area_info_struct *next;
00208 } area_info_t;
00209
00210 typedef struct TLSF_struct {
00211
00212 u32_t tlsf_signature;
00213
00214 #if TLSF_USE_LOCKS
00215 TLSF_MLOCK_T lock;
00216 #endif
00217
00218 #if TLSF_STATISTIC
00219
00220
00221 size_t used_size;
00222 size_t max_size;
00223 #endif
00224
00225
00226 area_info_t *area_head;
00227
00228
00229
00230 u32_t fl_bitmap;
00231
00232
00233 u32_t sl_bitmap[REAL_FLI];
00234
00235 bhdr_t *matrix[REAL_FLI][MAX_SLI];
00236 } tlsf_t;
00237
00238
00239
00240
00241
00242 static __inline__ void set_bit(int nr, u32_t * addr);
00243 static __inline__ void clear_bit(int nr, u32_t * addr);
00244 static __inline__ int ls_bit(int x);
00245 static __inline__ int ms_bit(int x);
00246 static __inline__ void MAPPING_SEARCH(size_t * _r, int *_fl, int *_sl);
00247 static __inline__ void MAPPING_INSERT(size_t _r, int *_fl, int *_sl);
00248 static __inline__ bhdr_t *FIND_SUITABLE_BLOCK(tlsf_t * _tlsf, int *_fl, int *_sl);
00249 static __inline__ bhdr_t *process_area(void *area, size_t size);
00250 #if USE_SBRK || USE_MMAP
00251 static __inline__ void *get_new_area(size_t * size);
00252 #endif
00253
00254 static const int table[] = {
00255 -1, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4,
00256 4, 4,
00257 4, 4, 4, 4, 4, 4, 4,
00258 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
00259 5,
00260 5, 5, 5, 5, 5, 5, 5,
00261 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
00262 6,
00263 6, 6, 6, 6, 6, 6, 6,
00264 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
00265 6,
00266 6, 6, 6, 6, 6, 6, 6,
00267 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
00268 7,
00269 7, 7, 7, 7, 7, 7, 7,
00270 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
00271 7,
00272 7, 7, 7, 7, 7, 7, 7,
00273 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
00274 7,
00275 7, 7, 7, 7, 7, 7, 7,
00276 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
00277 7,
00278 7, 7, 7, 7, 7, 7, 7
00279 };
00280
00281 static __inline__ int ls_bit(int i)
00282 {
00283 unsigned int a;
00284 unsigned int x = i & -i;
00285
00286 a = x <= 0xffff ? (x <= 0xff ? 0 : 8) : (x <= 0xffffff ? 16 : 24);
00287 return table[x >> a] + a;
00288 }
00289
00290 static __inline__ int ms_bit(int i)
00291 {
00292 unsigned int a;
00293 unsigned int x = (unsigned int) i;
00294
00295 a = x <= 0xffff ? (x <= 0xff ? 0 : 8) : (x <= 0xffffff ? 16 : 24);
00296 return table[x >> a] + a;
00297 }
00298
00299 static __inline__ void set_bit(int nr, u32_t * addr)
00300 {
00301 addr[nr >> 5] |= 1 << (nr & 0x1f);
00302 }
00303
00304 static __inline__ void clear_bit(int nr, u32_t * addr)
00305 {
00306 addr[nr >> 5] &= ~(1 << (nr & 0x1f));
00307 }
00308
00309 static __inline__ void MAPPING_SEARCH(size_t * _r, int *_fl, int *_sl)
00310 {
00311 int _t;
00312
00313 if (*_r < SMALL_BLOCK) {
00314 *_fl = 0;
00315 *_sl = *_r / (SMALL_BLOCK / MAX_SLI);
00316 } else {
00317 _t = (1 << (ms_bit(*_r) - MAX_LOG2_SLI)) - 1;
00318 *_r = *_r + _t;
00319 *_fl = ms_bit(*_r);
00320 *_sl = (*_r >> (*_fl - MAX_LOG2_SLI)) - MAX_SLI;
00321 *_fl -= FLI_OFFSET;
00322
00323
00324
00325 *_r &= ~_t;
00326 }
00327 }
00328
00329 static __inline__ void MAPPING_INSERT(size_t _r, int *_fl, int *_sl)
00330 {
00331 if (_r < SMALL_BLOCK) {
00332 *_fl = 0;
00333 *_sl = _r / (SMALL_BLOCK / MAX_SLI);
00334 } else {
00335 *_fl = ms_bit(_r);
00336 *_sl = (_r >> (*_fl - MAX_LOG2_SLI)) - MAX_SLI;
00337 *_fl -= FLI_OFFSET;
00338 }
00339 }
00340
00341
00342 static __inline__ bhdr_t *FIND_SUITABLE_BLOCK(tlsf_t * _tlsf, int *_fl, int *_sl)
00343 {
00344 u32_t _tmp = _tlsf->sl_bitmap[*_fl] & (~0 << *_sl);
00345 bhdr_t *_b = NULL;
00346
00347 if (_tmp) {
00348 *_sl = ls_bit(_tmp);
00349 _b = _tlsf->matrix[*_fl][*_sl];
00350 } else {
00351 *_fl = ls_bit(_tlsf->fl_bitmap & (~0 << (*_fl + 1)));
00352 if (*_fl > 0) {
00353 *_sl = ls_bit(_tlsf->sl_bitmap[*_fl]);
00354 _b = _tlsf->matrix[*_fl][*_sl];
00355 }
00356 }
00357 return _b;
00358 }
00359
00360
00361 #define EXTRACT_BLOCK_HDR(_b, _tlsf, _fl, _sl) do { \
00362 _tlsf -> matrix [_fl] [_sl] = _b -> ptr.free_ptr.next; \
00363 if (_tlsf -> matrix[_fl][_sl]) \
00364 _tlsf -> matrix[_fl][_sl] -> ptr.free_ptr.prev = NULL; \
00365 else { \
00366 clear_bit (_sl, &_tlsf -> sl_bitmap [_fl]); \
00367 if (!_tlsf -> sl_bitmap [_fl]) \
00368 clear_bit (_fl, &_tlsf -> fl_bitmap); \
00369 } \
00370 _b -> ptr.free_ptr.prev = NULL; \
00371 _b -> ptr.free_ptr.next = NULL; \
00372 }while(0)
00373
00374
00375 #define EXTRACT_BLOCK(_b, _tlsf, _fl, _sl) do { \
00376 if (_b -> ptr.free_ptr.next) \
00377 _b -> ptr.free_ptr.next -> ptr.free_ptr.prev = _b -> ptr.free_ptr.prev; \
00378 if (_b -> ptr.free_ptr.prev) \
00379 _b -> ptr.free_ptr.prev -> ptr.free_ptr.next = _b -> ptr.free_ptr.next; \
00380 if (_tlsf -> matrix [_fl][_sl] == _b) { \
00381 _tlsf -> matrix [_fl][_sl] = _b -> ptr.free_ptr.next; \
00382 if (!_tlsf -> matrix [_fl][_sl]) { \
00383 clear_bit (_sl, &_tlsf -> sl_bitmap[_fl]); \
00384 if (!_tlsf -> sl_bitmap [_fl]) \
00385 clear_bit (_fl, &_tlsf -> fl_bitmap); \
00386 } \
00387 } \
00388 _b -> ptr.free_ptr.prev = NULL; \
00389 _b -> ptr.free_ptr.next = NULL; \
00390 } while(0)
00391
00392 #define INSERT_BLOCK(_b, _tlsf, _fl, _sl) do { \
00393 _b -> ptr.free_ptr.prev = NULL; \
00394 _b -> ptr.free_ptr.next = _tlsf -> matrix [_fl][_sl]; \
00395 if (_tlsf -> matrix [_fl][_sl]) \
00396 _tlsf -> matrix [_fl][_sl] -> ptr.free_ptr.prev = _b; \
00397 _tlsf -> matrix [_fl][_sl] = _b; \
00398 set_bit (_sl, &_tlsf -> sl_bitmap [_fl]); \
00399 set_bit (_fl, &_tlsf -> fl_bitmap); \
00400 } while(0)
00401
00402 #if USE_SBRK || USE_MMAP
00403 static __inline__ void *get_new_area(size_t * size)
00404 {
00405 void *area;
00406
00407 #if USE_SBRK
00408 area = (void *)sbrk(0);
00409 if (((void *)sbrk(*size)) != ((void *) -1))
00410 return area;
00411 #endif
00412
00413 #if USE_MMAP
00414 *size = ROUNDUP(*size, TLSF_PAGE_SIZE);
00415 if ((area = mmap(0, *size, PROT_READ | PROT_WRITE, TLSF_MAP, -1, 0)) != MAP_FAILED)
00416 return area;
00417 #endif
00418 return ((void *) ~0);
00419 }
00420 #endif
00421
00422 static __inline__ bhdr_t *process_area(void *area, size_t size)
00423 {
00424 bhdr_t *b, *lb, *ib;
00425 area_info_t *ai;
00426
00427 ib = (bhdr_t *) area;
00428 ib->size =
00429 (sizeof(area_info_t) <
00430 MIN_BLOCK_SIZE) ? MIN_BLOCK_SIZE : ROUNDUP_SIZE(sizeof(area_info_t)) | USED_BLOCK | PREV_USED;
00431 b = (bhdr_t *) GET_NEXT_BLOCK(ib->ptr.buffer, ib->size & BLOCK_SIZE);
00432 b->size = ROUNDDOWN_SIZE(size - 3 * BHDR_OVERHEAD - (ib->size & BLOCK_SIZE)) | USED_BLOCK | PREV_USED;
00433 b->ptr.free_ptr.prev = b->ptr.free_ptr.next = 0;
00434 lb = GET_NEXT_BLOCK(b->ptr.buffer, b->size & BLOCK_SIZE);
00435 lb->prev_hdr = b;
00436 lb->size = 0 | USED_BLOCK | PREV_FREE;
00437 ai = (area_info_t *) ib->ptr.buffer;
00438 ai->next = 0;
00439 ai->end = lb;
00440 return ib;
00441 }
00442
00443
00444
00445
00446
00447 static char *mp = NULL;
00448 static int init_check = 0;
00449
00450
00451 size_t init_memory_pool(size_t mem_pool_size, void *mem_pool)
00452 {
00453
00454 tlsf_t *tlsf;
00455 bhdr_t *b, *ib;
00456
00457 if (!mem_pool || !mem_pool_size || mem_pool_size < sizeof(tlsf_t) + BHDR_OVERHEAD * 8) {
00458 ERROR_MSG("init_memory_pool (): memory_pool invalid\n");
00459 return -1;
00460 }
00461
00462 if (((unsigned long) mem_pool & PTR_MASK)) {
00463 ERROR_MSG("init_memory_pool (): mem_pool must be aligned to a word\n");
00464 return -1;
00465 }
00466 tlsf = (tlsf_t *) mem_pool;
00467
00468 if (init_check) {
00469 mp = mem_pool;
00470 b = GET_NEXT_BLOCK(mp, ROUNDUP_SIZE(sizeof(tlsf_t)));
00471 return b->size & BLOCK_SIZE;
00472 }
00473
00474 mp = mem_pool;
00475
00476
00477 memset(mem_pool, 0, sizeof(tlsf_t));
00478
00479 tlsf->tlsf_signature = TLSF_SIGNATURE;
00480 init_check = 1;
00481
00482 TLSF_CREATE_LOCK(&tlsf->lock);
00483
00484 ib = process_area(GET_NEXT_BLOCK
00485 (mem_pool, ROUNDUP_SIZE(sizeof(tlsf_t))), ROUNDDOWN_SIZE(mem_pool_size - sizeof(tlsf_t)));
00486 b = GET_NEXT_BLOCK(ib->ptr.buffer, ib->size & BLOCK_SIZE);
00487 free_ex(b->ptr.buffer, tlsf);
00488 tlsf->area_head = (area_info_t *) ib->ptr.buffer;
00489
00490 #if TLSF_STATISTIC
00491 tlsf->used_size = mem_pool_size - (b->size & BLOCK_SIZE);
00492 tlsf->max_size = tlsf->used_size;
00493 #endif
00494
00495 return (b->size & BLOCK_SIZE);
00496 }
00497
00498
00499 size_t add_new_area(void *area, size_t area_size, void *mem_pool)
00500 {
00501
00502 tlsf_t *tlsf = (tlsf_t *) mem_pool;
00503 area_info_t *ptr, *ptr_prev, *ai;
00504 bhdr_t *ib0, *b0, *lb0, *ib1, *b1, *lb1, *next_b;
00505
00506 memset(area, 0, area_size);
00507 ptr = tlsf->area_head;
00508 ptr_prev = 0;
00509
00510 ib0 = process_area(area, area_size);
00511 b0 = GET_NEXT_BLOCK(ib0->ptr.buffer, ib0->size & BLOCK_SIZE);
00512 lb0 = GET_NEXT_BLOCK(b0->ptr.buffer, b0->size & BLOCK_SIZE);
00513
00514
00515
00516
00517 while (ptr) {
00518 ib1 = (bhdr_t *) ((char *) ptr - BHDR_OVERHEAD);
00519 b1 = GET_NEXT_BLOCK(ib1->ptr.buffer, ib1->size & BLOCK_SIZE);
00520 lb1 = ptr->end;
00521
00522
00523 if ((unsigned long) ib1 == (unsigned long) lb0 + BHDR_OVERHEAD) {
00524 if (tlsf->area_head == ptr) {
00525 tlsf->area_head = ptr->next;
00526 ptr = ptr->next;
00527 } else {
00528 ptr_prev->next = ptr->next;
00529 ptr = ptr->next;
00530 }
00531
00532 b0->size =
00533 ROUNDDOWN_SIZE((b0->size & BLOCK_SIZE) +
00534 (ib1->size & BLOCK_SIZE) + 2 * BHDR_OVERHEAD) | USED_BLOCK | PREV_USED;
00535
00536 b1->prev_hdr = b0;
00537 lb0 = lb1;
00538
00539 continue;
00540 }
00541
00542
00543
00544 if ((unsigned long) lb1->ptr.buffer == (unsigned long) ib0) {
00545 if (tlsf->area_head == ptr) {
00546 tlsf->area_head = ptr->next;
00547 ptr = ptr->next;
00548 } else {
00549 ptr_prev->next = ptr->next;
00550 ptr = ptr->next;
00551 }
00552
00553 lb1->size =
00554 ROUNDDOWN_SIZE((b0->size & BLOCK_SIZE) +
00555 (ib0->size & BLOCK_SIZE) + 2 * BHDR_OVERHEAD) | USED_BLOCK | (lb1->size & PREV_STATE);
00556 next_b = GET_NEXT_BLOCK(lb1->ptr.buffer, lb1->size & BLOCK_SIZE);
00557 next_b->prev_hdr = lb1;
00558 b0 = lb1;
00559 ib0 = ib1;
00560
00561 continue;
00562 }
00563 ptr_prev = ptr;
00564 ptr = ptr->next;
00565 }
00566
00567
00568 ai = (area_info_t *) ib0->ptr.buffer;
00569 ai->next = tlsf->area_head;
00570 ai->end = lb0;
00571 tlsf->area_head = ai;
00572 free_ex(b0->ptr.buffer, mem_pool);
00573 return (b0->size & BLOCK_SIZE);
00574 }
00575
00576
00577
00578 size_t get_used_size(void *mem_pool)
00579 {
00580
00581 #if TLSF_STATISTIC
00582 return ((tlsf_t *) mem_pool)->used_size;
00583 #else
00584 return 0;
00585 #endif
00586 }
00587
00588
00589
00590 size_t get_used_size_mp()
00591 {
00592
00593 #if TLSF_STATISTIC
00594 return (mp ? ((tlsf_t *) mp)->used_size : 0);
00595 #else
00596 return 0;
00597 #endif
00598 }
00599
00600
00601 size_t get_max_size(void *mem_pool)
00602 {
00603
00604 #if TLSF_STATISTIC
00605 return ((tlsf_t *) mem_pool)->max_size;
00606 #else
00607 return 0;
00608 #endif
00609 }
00610
00611
00612
00613 size_t get_max_size_mp()
00614 {
00615
00616 #if TLSF_STATISTIC
00617 return (mp ? ((tlsf_t *) mp)->max_size : 0);
00618 #else
00619 return 0;
00620 #endif
00621 }
00622
00623
00624 void destroy_memory_pool(void *mem_pool)
00625 {
00626
00627 tlsf_t *tlsf = (tlsf_t *) mem_pool;
00628
00629 tlsf->tlsf_signature = 0;
00630
00631 TLSF_DESTROY_LOCK(&tlsf->lock);
00632
00633 }
00634
00635
00636
00637 void *tlsf_malloc(size_t size)
00638 {
00639
00640 void *ret;
00641
00642 #if USE_MMAP || USE_SBRK
00643 if (!mp) {
00644 size_t area_size;
00645 void *area;
00646
00647 area_size = sizeof(tlsf_t) + BHDR_OVERHEAD * 8;
00648 area_size = (area_size > DEFAULT_AREA_SIZE) ? area_size : DEFAULT_AREA_SIZE;
00649 area = get_new_area(&area_size);
00650 if (area == ((void *) ~0))
00651 return NULL;
00652 init_memory_pool(area_size, area);
00653 }
00654 #endif
00655
00656 TLSF_ACQUIRE_LOCK(&((tlsf_t *)mp)->lock);
00657
00658 ret = malloc_ex(size, mp);
00659
00660 TLSF_RELEASE_LOCK(&((tlsf_t *)mp)->lock);
00661
00662 return ret;
00663 }
00664
00665
00666 void tlsf_free(void *ptr)
00667 {
00668
00669
00670 TLSF_ACQUIRE_LOCK(&((tlsf_t *)mp)->lock);
00671
00672 free_ex(ptr, mp);
00673
00674 TLSF_RELEASE_LOCK(&((tlsf_t *)mp)->lock);
00675
00676 }
00677
00678
00679 void *tlsf_realloc(void *ptr, size_t size)
00680 {
00681
00682 void *ret;
00683
00684 #if USE_MMAP || USE_SBRK
00685 if (!mp) {
00686 return tlsf_malloc(size);
00687 }
00688 #endif
00689
00690 TLSF_ACQUIRE_LOCK(&((tlsf_t *)mp)->lock);
00691
00692 ret = realloc_ex(ptr, size, mp);
00693
00694 TLSF_RELEASE_LOCK(&((tlsf_t *)mp)->lock);
00695
00696 return ret;
00697 }
00698
00699
00700 void *tlsf_calloc(size_t nelem, size_t elem_size)
00701 {
00702
00703 void *ret;
00704
00705 TLSF_ACQUIRE_LOCK(&((tlsf_t *)mp)->lock);
00706
00707 ret = calloc_ex(nelem, elem_size, mp);
00708
00709 TLSF_RELEASE_LOCK(&((tlsf_t *)mp)->lock);
00710
00711 return ret;
00712 }
00713
00714
00715 void *malloc_ex(size_t size, void *mem_pool)
00716 {
00717
00718 tlsf_t *tlsf = (tlsf_t *) mem_pool;
00719 bhdr_t *b, *b2, *next_b;
00720 int fl, sl;
00721 size_t tmp_size;
00722
00723 size = (size < MIN_BLOCK_SIZE) ? MIN_BLOCK_SIZE : ROUNDUP_SIZE(size);
00724
00725
00726 MAPPING_SEARCH(&size, &fl, &sl);
00727
00728
00729
00730 b = FIND_SUITABLE_BLOCK(tlsf, &fl, &sl);
00731 #if USE_MMAP || USE_SBRK
00732 if (!b) {
00733 size_t area_size;
00734 void *area;
00735
00736 area_size = size + BHDR_OVERHEAD * 8;
00737 area_size = (area_size > DEFAULT_AREA_SIZE) ? area_size : DEFAULT_AREA_SIZE;
00738 area = get_new_area(&area_size);
00739 if (area == ((void *) ~0))
00740 return NULL;
00741 add_new_area(area, area_size, mem_pool);
00742
00743 MAPPING_SEARCH(&size, &fl, &sl);
00744
00745 b = FIND_SUITABLE_BLOCK(tlsf, &fl, &sl);
00746 }
00747 #endif
00748 if (!b)
00749 return NULL;
00750
00751 EXTRACT_BLOCK_HDR(b, tlsf, fl, sl);
00752
00753
00754 next_b = GET_NEXT_BLOCK(b->ptr.buffer, b->size & BLOCK_SIZE);
00755
00756 tmp_size = (b->size & BLOCK_SIZE) - size;
00757 if (tmp_size >= sizeof(bhdr_t)) {
00758 tmp_size -= BHDR_OVERHEAD;
00759 b2 = GET_NEXT_BLOCK(b->ptr.buffer, size);
00760 b2->size = tmp_size | FREE_BLOCK | PREV_USED;
00761 next_b->prev_hdr = b2;
00762 MAPPING_INSERT(tmp_size, &fl, &sl);
00763 INSERT_BLOCK(b2, tlsf, fl, sl);
00764
00765 b->size = size | (b->size & PREV_STATE);
00766 } else {
00767 next_b->size &= (~PREV_FREE);
00768 b->size &= (~FREE_BLOCK);
00769 }
00770
00771 TLSF_ADD_SIZE(tlsf, b);
00772
00773 return (void *) b->ptr.buffer;
00774 }
00775
00776
00777 void free_ex(void *ptr, void *mem_pool)
00778 {
00779
00780 tlsf_t *tlsf = (tlsf_t *) mem_pool;
00781 bhdr_t *b, *tmp_b;
00782 int fl = 0, sl = 0;
00783
00784 if (!ptr) {
00785 return;
00786 }
00787 b = (bhdr_t *) ((char *) ptr - BHDR_OVERHEAD);
00788 b->size |= FREE_BLOCK;
00789
00790 TLSF_REMOVE_SIZE(tlsf, b);
00791
00792 b->ptr.free_ptr.prev = NULL;
00793 b->ptr.free_ptr.next = NULL;
00794 tmp_b = GET_NEXT_BLOCK(b->ptr.buffer, b->size & BLOCK_SIZE);
00795 if (tmp_b->size & FREE_BLOCK) {
00796 MAPPING_INSERT(tmp_b->size & BLOCK_SIZE, &fl, &sl);
00797 EXTRACT_BLOCK(tmp_b, tlsf, fl, sl);
00798 b->size += (tmp_b->size & BLOCK_SIZE) + BHDR_OVERHEAD;
00799 }
00800 if (b->size & PREV_FREE) {
00801 tmp_b = b->prev_hdr;
00802 MAPPING_INSERT(tmp_b->size & BLOCK_SIZE, &fl, &sl);
00803 EXTRACT_BLOCK(tmp_b, tlsf, fl, sl);
00804 tmp_b->size += (b->size & BLOCK_SIZE) + BHDR_OVERHEAD;
00805 b = tmp_b;
00806 }
00807 MAPPING_INSERT(b->size & BLOCK_SIZE, &fl, &sl);
00808 INSERT_BLOCK(b, tlsf, fl, sl);
00809
00810 tmp_b = GET_NEXT_BLOCK(b->ptr.buffer, b->size & BLOCK_SIZE);
00811 tmp_b->size |= PREV_FREE;
00812 tmp_b->prev_hdr = b;
00813 }
00814
00815
00816 void *realloc_ex(void *ptr, size_t new_size, void *mem_pool)
00817 {
00818
00819 tlsf_t *tlsf = (tlsf_t *) mem_pool;
00820 void *ptr_aux;
00821 unsigned int cpsize;
00822 bhdr_t *b, *tmp_b, *next_b;
00823 int fl, sl;
00824 size_t tmp_size;
00825
00826 if (!ptr) {
00827 if (new_size)
00828 return (void *) malloc_ex(new_size, mem_pool);
00829 if (!new_size)
00830 return NULL;
00831 } else if (!new_size) {
00832 free_ex(ptr, mem_pool);
00833 return NULL;
00834 }
00835
00836 b = (bhdr_t *) ((char *) ptr - BHDR_OVERHEAD);
00837 next_b = GET_NEXT_BLOCK(b->ptr.buffer, b->size & BLOCK_SIZE);
00838 new_size = (new_size < MIN_BLOCK_SIZE) ? MIN_BLOCK_SIZE : ROUNDUP_SIZE(new_size);
00839 tmp_size = (b->size & BLOCK_SIZE);
00840 if (new_size <= tmp_size) {
00841 TLSF_REMOVE_SIZE(tlsf, b);
00842 if (next_b->size & FREE_BLOCK) {
00843 MAPPING_INSERT(next_b->size & BLOCK_SIZE, &fl, &sl);
00844 EXTRACT_BLOCK(next_b, tlsf, fl, sl);
00845 tmp_size += (next_b->size & BLOCK_SIZE) + BHDR_OVERHEAD;
00846 next_b = GET_NEXT_BLOCK(next_b->ptr.buffer, next_b->size & BLOCK_SIZE);
00847
00848
00849 }
00850 tmp_size -= new_size;
00851 if (tmp_size >= sizeof(bhdr_t)) {
00852 tmp_size -= BHDR_OVERHEAD;
00853 tmp_b = GET_NEXT_BLOCK(b->ptr.buffer, new_size);
00854 tmp_b->size = tmp_size | FREE_BLOCK | PREV_USED;
00855 next_b->prev_hdr = tmp_b;
00856 next_b->size |= PREV_FREE;
00857 MAPPING_INSERT(tmp_size, &fl, &sl);
00858 INSERT_BLOCK(tmp_b, tlsf, fl, sl);
00859 b->size = new_size | (b->size & PREV_STATE);
00860 }
00861 TLSF_ADD_SIZE(tlsf, b);
00862 return (void *) b->ptr.buffer;
00863 }
00864 if ((next_b->size & FREE_BLOCK)) {
00865 if (new_size <= (tmp_size + (next_b->size & BLOCK_SIZE))) {
00866 TLSF_REMOVE_SIZE(tlsf, b);
00867 MAPPING_INSERT(next_b->size & BLOCK_SIZE, &fl, &sl);
00868 EXTRACT_BLOCK(next_b, tlsf, fl, sl);
00869 b->size += (next_b->size & BLOCK_SIZE) + BHDR_OVERHEAD;
00870 next_b = GET_NEXT_BLOCK(b->ptr.buffer, b->size & BLOCK_SIZE);
00871 next_b->prev_hdr = b;
00872 next_b->size &= ~PREV_FREE;
00873 tmp_size = (b->size & BLOCK_SIZE) - new_size;
00874 if (tmp_size >= sizeof(bhdr_t)) {
00875 tmp_size -= BHDR_OVERHEAD;
00876 tmp_b = GET_NEXT_BLOCK(b->ptr.buffer, new_size);
00877 tmp_b->size = tmp_size | FREE_BLOCK | PREV_USED;
00878 next_b->prev_hdr = tmp_b;
00879 next_b->size |= PREV_FREE;
00880 MAPPING_INSERT(tmp_size, &fl, &sl);
00881 INSERT_BLOCK(tmp_b, tlsf, fl, sl);
00882 b->size = new_size | (b->size & PREV_STATE);
00883 }
00884 TLSF_ADD_SIZE(tlsf, b);
00885 return (void *) b->ptr.buffer;
00886 }
00887 }
00888
00889 ptr_aux = malloc_ex(new_size, mem_pool);
00890
00891 cpsize = ((b->size & BLOCK_SIZE) > new_size) ? new_size : (b->size & BLOCK_SIZE);
00892
00893 memcpy(ptr_aux, ptr, cpsize);
00894
00895 free_ex(ptr, mem_pool);
00896 return ptr_aux;
00897 }
00898
00899
00900
00901 void *calloc_ex(size_t nelem, size_t elem_size, void *mem_pool)
00902 {
00903
00904 void *ptr;
00905
00906 if (nelem <= 0 || elem_size <= 0)
00907 return NULL;
00908
00909 if (!(ptr = malloc_ex(nelem * elem_size, mem_pool)))
00910 return NULL;
00911 memset(ptr, 0, nelem * elem_size);
00912
00913 return ptr;
00914 }
00915
00916
00917
00918 #if _DEBUG_TLSF_
00919
00920
00921
00922
00923
00924
00925
00926 extern void dump_memory_region(unsigned char *mem_ptr, unsigned int size);
00927 extern void print_block(bhdr_t * b);
00928 extern void print_tlsf(tlsf_t * tlsf);
00929 void print_all_blocks(tlsf_t * tlsf);
00930
00931 void dump_memory_region(unsigned char *mem_ptr, unsigned int size)
00932 {
00933
00934 unsigned long begin = (unsigned long) mem_ptr;
00935 unsigned long end = (unsigned long) mem_ptr + size;
00936 int column = 0;
00937
00938 begin >>= 2;
00939 begin <<= 2;
00940
00941 end >>= 2;
00942 end++;
00943 end <<= 2;
00944
00945 PRINT_MSG("\nMemory region dumped: 0x%lx - 0x%lx\n\n", begin, end);
00946
00947 column = 0;
00948 PRINT_MSG("0x%lx ", begin);
00949
00950 while (begin < end) {
00951 if (((unsigned char *) begin)[0] == 0)
00952 PRINT_MSG("00");
00953 else
00954 PRINT_MSG("%02x", ((unsigned char *) begin)[0]);
00955 if (((unsigned char *) begin)[1] == 0)
00956 PRINT_MSG("00 ");
00957 else
00958 PRINT_MSG("%02x ", ((unsigned char *) begin)[1]);
00959 begin += 2;
00960 column++;
00961 if (column == 8) {
00962 PRINT_MSG("\n0x%lx ", begin);
00963 column = 0;
00964 }
00965
00966 }
00967 PRINT_MSG("\n\n");
00968 }
00969
00970 void print_block(bhdr_t * b)
00971 {
00972 if (!b)
00973 return;
00974 PRINT_MSG(">> [%p] (", b);
00975 if ((b->size & BLOCK_SIZE))
00976 PRINT_MSG("%lu bytes, ", (unsigned long) (b->size & BLOCK_SIZE));
00977 else
00978 PRINT_MSG("sentinel, ");
00979 if ((b->size & BLOCK_STATE) == FREE_BLOCK)
00980 PRINT_MSG("free [%p, %p], ", b->ptr.free_ptr.prev, b->ptr.free_ptr.next);
00981 else
00982 PRINT_MSG("used, ");
00983 if ((b->size & PREV_STATE) == PREV_FREE)
00984 PRINT_MSG("prev. free [%p])\n", b->prev_hdr);
00985 else
00986 PRINT_MSG("prev used)\n");
00987 }
00988
00989 void print_tlsf(tlsf_t * tlsf)
00990 {
00991 bhdr_t *next;
00992 int i, j;
00993
00994 PRINT_MSG("\nTLSF at %p\n", tlsf);
00995
00996 PRINT_MSG("FL bitmap: 0x%x\n\n", (unsigned) tlsf->fl_bitmap);
00997
00998 for (i = 0; i < REAL_FLI; i++) {
00999 if (tlsf->sl_bitmap[i])
01000 PRINT_MSG("SL bitmap 0x%x\n", (unsigned) tlsf->sl_bitmap[i]);
01001 for (j = 0; j < MAX_SLI; j++) {
01002 next = tlsf->matrix[i][j];
01003 if (next)
01004 PRINT_MSG("-> [%d][%d]\n", i, j);
01005 while (next) {
01006 print_block(next);
01007 next = next->ptr.free_ptr.next;
01008 }
01009 }
01010 }
01011 }
01012
01013 void print_all_blocks(tlsf_t * tlsf)
01014 {
01015 area_info_t *ai;
01016 bhdr_t *next;
01017 PRINT_MSG("\nTLSF at %p\nALL BLOCKS\n\n", tlsf);
01018 ai = tlsf->area_head;
01019 while (ai) {
01020 next = (bhdr_t *) ((char *) ai - BHDR_OVERHEAD);
01021 while (next) {
01022 print_block(next);
01023 if ((next->size & BLOCK_SIZE))
01024 next = GET_NEXT_BLOCK(next->ptr.buffer, next->size & BLOCK_SIZE);
01025 else
01026 next = NULL;
01027 }
01028 ai = ai->next;
01029 }
01030 }
01031
01032 #endif