OrocosComponentLibrary
2.7.0
|
00001 /* 00002 * Two Levels Segregate Fit memory allocator (TLSF) 00003 * Version 2.4.6 00004 * 00005 * Written by Miguel Masmano Tello <mimastel@doctor.upv.es> 00006 * 00007 * Thanks to Ismael Ripoll for his suggestions and reviews 00008 * 00009 * Copyright (C) 2008, 2007, 2006, 2005, 2004 00010 * 00011 * This code is released using a dual license strategy: GPL/LGPL 00012 * You can choose the licence that better fits your requirements. 00013 * 00014 * Released under the terms of the GNU General Public License Version 2.0 00015 * Released under the terms of the GNU Lesser General Public License Version 2.1 00016 * 00017 */ 00018 00019 /* 00020 * Code contributions: 00021 * 00022 * (Jul 28 2007) Herman ten Brugge <hermantenbrugge@home.nl>: 00023 * 00024 * - Add 64 bit support. It now runs on x86_64 and solaris64. 00025 * - I also tested this on vxworks/32and solaris/32 and i386/32 processors. 00026 * - Remove assembly code. I could not measure any performance difference 00027 * on my core2 processor. This also makes the code more portable. 00028 * - Moved defines/typedefs from tlsf.h to tlsf.c 00029 * - Changed MIN_BLOCK_SIZE to sizeof (free_ptr_t) and BHDR_OVERHEAD to 00030 * (sizeof (bhdr_t) - MIN_BLOCK_SIZE). This does not change the fact 00031 * that the minumum size is still sizeof 00032 * (bhdr_t). 00033 * - Changed all C++ comment style to C style. (// -> /.* ... *./) 00034 * - Used ls_bit instead of ffs and ms_bit instead of fls. I did this to 00035 * avoid confusion with the standard ffs function which returns 00036 * different values. 00037 * - Created set_bit/clear_bit fuctions because they are not present 00038 * on x86_64. 00039 * - Added locking support + extra file target.h to show how to use it. 00040 * - Added rtl_get_used_size function (REMOVED in 2.4) 00041 * - Added rtl_realloc and rtl_calloc function 00042 * - Implemented realloc clever support. 00043 * - Added some test code in the example directory. 00044 * - Bug fixed (discovered by the rockbox project: www.rockbox.org). 00045 * 00046 * (Oct 23 2006) Adam Scislowicz: 00047 * 00048 * - Support for ARMv5 implemented 00049 * 00050 */ 00051 00052 /*#define USE_SBRK (0) */ 00053 /*#define USE_MMAP (0) */ 00054 00055 #ifndef USE_PRINTF 00056 #define USE_PRINTF (1) 00057 #endif 00058 00059 #include <string.h> 00060 00061 #ifndef TLSF_USE_LOCKS 00062 #define TLSF_USE_LOCKS (0) 00063 #endif 00064 00065 #ifndef TLSF_STATISTIC 00066 #define TLSF_STATISTIC (0) 00067 #endif 00068 00069 #ifndef USE_MMAP 00070 #define USE_MMAP (0) 00071 #endif 00072 00073 #ifndef USE_SBRK 00074 #define USE_SBRK (0) 00075 #endif 00076 00077 #ifndef CHECK_DOUBLE_FREE 00078 #define CHECK_DOUBLE_FREE (0) 00079 #endif 00080 00081 #if TLSF_USE_LOCKS 00082 #include "target.h" 00083 #else 00084 #define TLSF_CREATE_LOCK(_unused_) do{}while(0) 00085 #define TLSF_DESTROY_LOCK(_unused_) do{}while(0) 00086 #define TLSF_ACQUIRE_LOCK(_unused_) do{}while(0) 00087 #define TLSF_RELEASE_LOCK(_unused_) do{}while(0) 00088 #endif 00089 00090 #if TLSF_STATISTIC 00091 #define TLSF_ADD_SIZE(tlsf, b) do { \ 00092 tlsf->used_size += (b->size & BLOCK_SIZE) + BHDR_OVERHEAD; \ 00093 if (tlsf->used_size > tlsf->max_size) { \ 00094 tlsf->max_size = tlsf->used_size; \ 00095 } \ 00096 } while(0) 00097 00098 #define TLSF_REMOVE_SIZE(tlsf, b) do { \ 00099 tlsf->used_size -= (b->size & BLOCK_SIZE) + BHDR_OVERHEAD; \ 00100 } while(0) 00101 #else 00102 #define TLSF_ADD_SIZE(tlsf, b) do{}while(0) 00103 #define TLSF_REMOVE_SIZE(tlsf, b) do{}while(0) 00104 #endif 00105 00106 #if USE_MMAP || USE_SBRK 00107 #include <unistd.h> 00108 #endif 00109 00110 #if USE_MMAP 00111 #include <sys/mman.h> 00112 #endif 00113 00114 #include "tlsf.h" 00115 00116 #if !defined(__GNUC__) 00117 #ifndef __inline__ 00118 #define __inline__ 00119 #endif 00120 #endif 00121 00122 /* The debug functions only can be used when _DEBUG_TLSF_ is set. */ 00123 #ifndef _DEBUG_TLSF_ 00124 #define _DEBUG_TLSF_ (0) 00125 #endif 00126 00127 /*************************************************************************/ 00128 /* Definition of the structures used by TLSF */ 00129 00130 00131 /* Some IMPORTANT TLSF parameters */ 00132 /* Unlike the preview TLSF versions, now they are statics */ 00133 #define BLOCK_ALIGN (sizeof(void *) * 2) 00134 00135 #define MAX_FLI (30) 00136 #define MAX_LOG2_SLI (5) 00137 #define MAX_SLI (1 << MAX_LOG2_SLI) /* MAX_SLI = 2^MAX_LOG2_SLI */ 00138 00139 #define FLI_OFFSET (6) /* tlsf structure just will manage blocks bigger */ 00140 /* than 128 bytes */ 00141 #define SMALL_BLOCK (128) 00142 #define REAL_FLI (MAX_FLI - FLI_OFFSET) 00143 #define MIN_BLOCK_SIZE (sizeof (free_ptr_t)) 00144 #define BHDR_OVERHEAD (sizeof (bhdr_t) - MIN_BLOCK_SIZE) 00145 #define TLSF_SIGNATURE (0x2A59FA59) 00146 00147 #define PTR_MASK (sizeof(void *) - 1) 00148 #define BLOCK_SIZE (0xFFFFFFFF - PTR_MASK) 00149 00150 #define GET_NEXT_BLOCK(_addr, _r) ((bhdr_t *) ((char *) (_addr) + (_r))) 00151 #define MEM_ALIGN ((BLOCK_ALIGN) - 1) 00152 #define ROUNDUP_SIZE(_r) (((_r) + MEM_ALIGN) & ~MEM_ALIGN) 00153 #define ROUNDDOWN_SIZE(_r) ((_r) & ~MEM_ALIGN) 00154 #define ROUNDUP(_x, _v) ((((~(_x)) + 1) & ((_v)-1)) + (_x)) 00155 00156 #define BLOCK_STATE (0x1) 00157 #define PREV_STATE (0x2) 00158 00159 /* bit 0 of the block size */ 00160 #define FREE_BLOCK (0x1) 00161 #define USED_BLOCK (0x0) 00162 00163 /* bit 1 of the block size */ 00164 #define PREV_FREE (0x2) 00165 #define PREV_USED (0x0) 00166 00167 00168 #define DEFAULT_AREA_SIZE (1024*10) 00169 00170 #ifdef USE_MMAP 00171 #define PAGE_SIZE (getpagesize()) 00172 #endif 00173 00174 #ifdef USE_PRINTF 00175 #include <stdio.h> 00176 # define PRINT_MSG(fmt, args...) printf(fmt, ## args) 00177 # define ERROR_MSG(fmt, args...) fprintf(stderr, fmt, ## args) 00178 #else 00179 # if !defined(PRINT_MSG) 00180 # define PRINT_MSG(fmt, args...) 00181 # endif 00182 # if !defined(ERROR_MSG) 00183 # define ERROR_MSG(fmt, args...) 00184 # endif 00185 #endif 00186 00187 #ifndef ATTRIBUTE_UNUSED 00188 #if defined(__GNUC__) 00189 #define ATTRIBUTE_UNUSED __attribute__ ((__unused__)) 00190 #else 00191 #define ATTRIBUTE_UNUSED 00192 #endif 00193 #endif 00194 00195 00196 typedef unsigned int u32_t; /* NOTE: Make sure that this type is 4 bytes long on your computer */ 00197 typedef unsigned char u8_t; /* NOTE: Make sure that this type is 1 byte on your computer */ 00198 00199 typedef struct free_ptr_struct { 00200 struct bhdr_struct *prev; 00201 struct bhdr_struct *next; 00202 } free_ptr_t; 00203 00204 typedef struct bhdr_struct { 00205 /* This pointer is just valid if the first bit of size is set */ 00206 struct bhdr_struct *prev_hdr; 00207 /* The size is stored in bytes */ 00208 size_t size; /* bit 0 indicates whether the block is used and */ 00209 /* bit 1 allows to know whether the previous block is free */ 00210 union { 00211 struct free_ptr_struct free_ptr; 00212 u8_t buffer[1]; /*sizeof(struct free_ptr_struct)]; */ 00213 } ptr; 00214 } bhdr_t; 00215 00216 /* This structure is embedded at the beginning of each area, giving us 00217 * enough information to cope with a set of areas */ 00218 00219 typedef struct area_info_struct { 00220 bhdr_t *end; 00221 struct area_info_struct *next; 00222 } area_info_t; 00223 00224 typedef struct TLSF_struct { 00225 /* the TLSF's structure signature */ 00226 u32_t tlsf_signature; 00227 00228 #if TLSF_USE_LOCKS 00229 TLSF_MLOCK_T lock; 00230 #endif 00231 00232 #if TLSF_STATISTIC 00233 /* These can not be calculated outside tlsf because we 00234 * do not know the sizes when freeing/reallocing memory. */ 00235 size_t used_size; 00236 size_t max_size; 00237 #endif 00238 00239 /* A linked list holding all the existing areas */ 00240 area_info_t *area_head; 00241 00242 /* the first-level bitmap */ 00243 /* This array should have a size of REAL_FLI bits */ 00244 u32_t fl_bitmap; 00245 00246 /* the second-level bitmap */ 00247 u32_t sl_bitmap[REAL_FLI]; 00248 00249 bhdr_t *matrix[REAL_FLI][MAX_SLI]; 00250 } tlsf_t; 00251 00252 00253 /******************************************************************/ 00254 /************** Helping functions **************************/ 00255 /******************************************************************/ 00256 static __inline__ void set_bit(int nr, u32_t * addr); 00257 static __inline__ void clear_bit(int nr, u32_t * addr); 00258 static __inline__ int ls_bit(int x); 00259 static __inline__ int ms_bit(int x); 00260 static __inline__ void MAPPING_SEARCH(size_t * _r, int *_fl, int *_sl); 00261 static __inline__ void MAPPING_INSERT(size_t _r, int *_fl, int *_sl); 00262 static __inline__ bhdr_t *FIND_SUITABLE_BLOCK(tlsf_t * _tlsf, int *_fl, int *_sl); 00263 static __inline__ bhdr_t *process_area(void *area, size_t size); 00264 #if USE_SBRK || USE_MMAP 00265 static __inline__ void *get_new_area(size_t * size); 00266 #endif 00267 00268 static const int table[] = { 00269 -1, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 00270 4, 4, 00271 4, 4, 4, 4, 4, 4, 4, 00272 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 00273 5, 00274 5, 5, 5, 5, 5, 5, 5, 00275 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 00276 6, 00277 6, 6, 6, 6, 6, 6, 6, 00278 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 00279 6, 00280 6, 6, 6, 6, 6, 6, 6, 00281 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 00282 7, 00283 7, 7, 7, 7, 7, 7, 7, 00284 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 00285 7, 00286 7, 7, 7, 7, 7, 7, 7, 00287 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 00288 7, 00289 7, 7, 7, 7, 7, 7, 7, 00290 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 00291 7, 00292 7, 7, 7, 7, 7, 7, 7 00293 }; 00294 00295 static __inline__ int ls_bit(int i) { 00296 unsigned int a; 00297 unsigned int x = i & -i; 00298 00299 a = x <= 0xffff ? (x <= 0xff ? 0 : 8) : (x <= 0xffffff ? 16 : 24); 00300 return table[x >> a] + a; 00301 } 00302 00303 static __inline__ int ms_bit(int i) { 00304 unsigned int a; 00305 unsigned int x = (unsigned int) i; 00306 00307 a = x <= 0xffff ? (x <= 0xff ? 0 : 8) : (x <= 0xffffff ? 16 : 24); 00308 return table[x >> a] + a; 00309 } 00310 00311 static __inline__ void set_bit(int nr, u32_t * addr) { 00312 addr[nr >> 5] |= 1 << (nr & 0x1f); 00313 } 00314 00315 static __inline__ void clear_bit(int nr, u32_t * addr) { 00316 addr[nr >> 5] &= ~(1 << (nr & 0x1f)); 00317 } 00318 00319 static __inline__ void MAPPING_SEARCH(size_t * _r, int *_fl, int *_sl) { 00320 int _t; 00321 00322 if (*_r < SMALL_BLOCK) { 00323 *_fl = 0; 00324 *_sl = *_r / (SMALL_BLOCK / MAX_SLI); 00325 } else { 00326 _t = (1 << (ms_bit(*_r) - MAX_LOG2_SLI)) - 1; 00327 *_r = *_r + _t; 00328 *_fl = ms_bit(*_r); 00329 *_sl = (*_r >> (*_fl - MAX_LOG2_SLI)) - MAX_SLI; 00330 *_fl -= FLI_OFFSET; 00331 /*if ((*_fl -= FLI_OFFSET) < 0) // FL wil be always >0! 00332 *_fl = *_sl = 0; 00333 */ 00334 *_r &= ~_t; 00335 } 00336 } 00337 00338 static __inline__ void MAPPING_INSERT(size_t _r, int *_fl, int *_sl) { 00339 if (_r < SMALL_BLOCK) { 00340 *_fl = 0; 00341 *_sl = _r / (SMALL_BLOCK / MAX_SLI); 00342 } else { 00343 *_fl = ms_bit(_r); 00344 *_sl = (_r >> (*_fl - MAX_LOG2_SLI)) - MAX_SLI; 00345 *_fl -= FLI_OFFSET; 00346 } 00347 } 00348 00349 00350 static __inline__ bhdr_t *FIND_SUITABLE_BLOCK(tlsf_t * _tlsf, int *_fl, int *_sl) { 00351 u32_t _tmp = _tlsf->sl_bitmap[*_fl] & (~0 << *_sl); 00352 bhdr_t *_b = NULL; 00353 00354 if (_tmp) { 00355 *_sl = ls_bit(_tmp); 00356 _b = _tlsf->matrix[*_fl][*_sl]; 00357 } else { 00358 *_fl = ls_bit(_tlsf->fl_bitmap & (~0 << (*_fl + 1))); 00359 if (*_fl > 0) { /* likely */ 00360 *_sl = ls_bit(_tlsf->sl_bitmap[*_fl]); 00361 _b = _tlsf->matrix[*_fl][*_sl]; 00362 } 00363 } 00364 return _b; 00365 } 00366 00367 00368 #define EXTRACT_BLOCK_HDR(_b, _tlsf, _fl, _sl) do { \ 00369 _tlsf -> matrix [_fl] [_sl] = _b -> ptr.free_ptr.next; \ 00370 if (_tlsf -> matrix[_fl][_sl]) \ 00371 _tlsf -> matrix[_fl][_sl] -> ptr.free_ptr.prev = NULL; \ 00372 else { \ 00373 clear_bit (_sl, &_tlsf -> sl_bitmap [_fl]); \ 00374 if (!_tlsf -> sl_bitmap [_fl]) \ 00375 clear_bit (_fl, &_tlsf -> fl_bitmap); \ 00376 } \ 00377 _b -> ptr.free_ptr.prev = NULL; \ 00378 _b -> ptr.free_ptr.next = NULL; \ 00379 }while(0) 00380 00381 00382 #define EXTRACT_BLOCK(_b, _tlsf, _fl, _sl) do { \ 00383 if (_b -> ptr.free_ptr.next) \ 00384 _b -> ptr.free_ptr.next -> ptr.free_ptr.prev = _b -> ptr.free_ptr.prev; \ 00385 if (_b -> ptr.free_ptr.prev) \ 00386 _b -> ptr.free_ptr.prev -> ptr.free_ptr.next = _b -> ptr.free_ptr.next; \ 00387 if (_tlsf -> matrix [_fl][_sl] == _b) { \ 00388 _tlsf -> matrix [_fl][_sl] = _b -> ptr.free_ptr.next; \ 00389 if (!_tlsf -> matrix [_fl][_sl]) { \ 00390 clear_bit (_sl, &_tlsf -> sl_bitmap[_fl]); \ 00391 if (!_tlsf -> sl_bitmap [_fl]) \ 00392 clear_bit (_fl, &_tlsf -> fl_bitmap); \ 00393 } \ 00394 } \ 00395 _b -> ptr.free_ptr.prev = NULL; \ 00396 _b -> ptr.free_ptr.next = NULL; \ 00397 } while(0) 00398 00399 #define INSERT_BLOCK(_b, _tlsf, _fl, _sl) do { \ 00400 _b -> ptr.free_ptr.prev = NULL; \ 00401 _b -> ptr.free_ptr.next = _tlsf -> matrix [_fl][_sl]; \ 00402 if (_tlsf -> matrix [_fl][_sl]) \ 00403 _tlsf -> matrix [_fl][_sl] -> ptr.free_ptr.prev = _b; \ 00404 _tlsf -> matrix [_fl][_sl] = _b; \ 00405 set_bit (_sl, &_tlsf -> sl_bitmap [_fl]); \ 00406 set_bit (_fl, &_tlsf -> fl_bitmap); \ 00407 } while(0) 00408 00409 #if USE_SBRK || USE_MMAP 00410 static __inline__ void *get_new_area(size_t * size) { 00411 void *area; 00412 00413 #if USE_SBRK 00414 area = (void *) sbrk(0); 00415 if (((void *) sbrk(*size)) != ((void *) -1)) 00416 return area; 00417 #endif 00418 00419 #ifndef MAP_ANONYMOUS 00420 /* https://dev.openwrt.org/ticket/322 */ 00421 # define MAP_ANONYMOUS MAP_ANON 00422 #endif 00423 00424 00425 #if USE_MMAP 00426 *size = ROUNDUP(*size, PAGE_SIZE); 00427 if ((area = 00428 mmap(0, *size, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0)) != MAP_FAILED) 00429 return area; 00430 #endif 00431 return ((void *) ~0); 00432 } 00433 #endif 00434 00435 static __inline__ bhdr_t *process_area(void *area, size_t size) { 00436 bhdr_t *b, *lb, *ib; 00437 area_info_t *ai; 00438 00439 ib = (bhdr_t *) area; 00440 ib->size = 00441 (sizeof(area_info_t) < 00442 MIN_BLOCK_SIZE) ? MIN_BLOCK_SIZE : ROUNDUP_SIZE(sizeof(area_info_t)) | USED_BLOCK | 00443 PREV_USED; 00444 b = (bhdr_t *) GET_NEXT_BLOCK(ib->ptr.buffer, ib->size & BLOCK_SIZE); 00445 b->size = 00446 ROUNDDOWN_SIZE(size - 3 * BHDR_OVERHEAD - (ib->size & BLOCK_SIZE)) | USED_BLOCK | PREV_USED; 00447 b->ptr.free_ptr.prev = b->ptr.free_ptr.next = 0; 00448 lb = GET_NEXT_BLOCK(b->ptr.buffer, b->size & BLOCK_SIZE); 00449 lb->prev_hdr = b; 00450 lb->size = 0 | USED_BLOCK | PREV_FREE; 00451 ai = (area_info_t *) ib->ptr.buffer; 00452 ai->next = 0; 00453 ai->end = lb; 00454 return ib; 00455 } 00456 00457 /******************************************************************/ 00458 /******************** Begin of the allocator code *****************/ 00459 /******************************************************************/ 00460 00461 static char *mp = NULL; /* Default memory pool. */ 00462 00463 /******************************************************************/ 00464 size_t rtl_init_memory_pool(size_t mem_pool_size, void *mem_pool) { 00465 /******************************************************************/ 00466 tlsf_t *tlsf; 00467 bhdr_t *b, *ib; 00468 00469 if (!mem_pool || !mem_pool_size || mem_pool_size < sizeof(tlsf_t) + BHDR_OVERHEAD * 8) { 00470 ERROR_MSG("rtl_init_memory_pool (): memory_pool invalid\n"); 00471 return (size_t) - 1; 00472 } 00473 00474 if (((unsigned long) mem_pool & PTR_MASK)) { 00475 ERROR_MSG("rtl_init_memory_pool (): mem_pool must be aligned to a word\n"); 00476 return (size_t) - 1; 00477 } 00478 tlsf = (tlsf_t *) mem_pool; 00479 /* Check if already initialised */ 00480 if (tlsf->tlsf_signature == TLSF_SIGNATURE) { 00481 mp = (char *) mem_pool; 00482 b = GET_NEXT_BLOCK(mp, ROUNDUP_SIZE(sizeof(tlsf_t))); 00483 return b->size & BLOCK_SIZE; 00484 } 00485 00486 mp = (char *) mem_pool; 00487 00488 /* Zeroing the memory pool */ 00489 memset(mem_pool, 0, sizeof(tlsf_t)); 00490 00491 tlsf->tlsf_signature = TLSF_SIGNATURE; 00492 00493 TLSF_CREATE_LOCK(&tlsf->lock); 00494 00495 ib = process_area(GET_NEXT_BLOCK 00496 (mem_pool, ROUNDUP_SIZE(sizeof(tlsf_t))), 00497 ROUNDDOWN_SIZE(mem_pool_size - sizeof(tlsf_t))); 00498 b = GET_NEXT_BLOCK(ib->ptr.buffer, ib->size & BLOCK_SIZE); 00499 rtl_free_ex(b->ptr.buffer, tlsf); 00500 tlsf->area_head = (area_info_t *) ib->ptr.buffer; 00501 00502 #if TLSF_STATISTIC 00503 tlsf->used_size = mem_pool_size - (b->size & BLOCK_SIZE); 00504 tlsf->max_size = tlsf->used_size; 00505 #endif 00506 00507 return (b->size & BLOCK_SIZE); 00508 } 00509 00510 /******************************************************************/ 00511 size_t rtl_add_new_area(void *area, size_t area_size, void *mem_pool) { 00512 /******************************************************************/ 00513 tlsf_t *tlsf = (tlsf_t *) mem_pool; 00514 area_info_t *ptr, *ptr_prev, *ai; 00515 bhdr_t *ib0, *b0, *lb0, *ib1, *b1, *lb1, *next_b; 00516 00517 #if TLSF_STATISTIC 00518 size_t savesz; 00519 savesz = tlsf->used_size; 00520 #endif 00521 00522 memset(area, 0, area_size); 00523 ptr = tlsf->area_head; 00524 ptr_prev = 0; 00525 00526 ib0 = process_area(area, area_size); 00527 b0 = GET_NEXT_BLOCK(ib0->ptr.buffer, ib0->size & BLOCK_SIZE); 00528 lb0 = GET_NEXT_BLOCK(b0->ptr.buffer, b0->size & BLOCK_SIZE); 00529 00530 /* Before inserting the new area, we have to merge this area with the 00531 already existing ones */ 00532 00533 while (ptr) { 00534 ib1 = (bhdr_t *) ((char *) ptr - BHDR_OVERHEAD); 00535 b1 = GET_NEXT_BLOCK(ib1->ptr.buffer, ib1->size & BLOCK_SIZE); 00536 lb1 = ptr->end; 00537 00538 /* Merging the new area with the next physically contigous one */ 00539 if ((unsigned long) ib1 == (unsigned long) lb0 + BHDR_OVERHEAD) { 00540 if (tlsf->area_head == ptr) { 00541 tlsf->area_head = ptr->next; 00542 ptr = ptr->next; 00543 } else { 00544 ptr_prev->next = ptr->next; 00545 ptr = ptr->next; 00546 } 00547 00548 b0->size = 00549 ROUNDDOWN_SIZE((b0->size & BLOCK_SIZE) + 00550 (ib1->size & BLOCK_SIZE) + 00551 2 * BHDR_OVERHEAD) | USED_BLOCK | PREV_USED; 00552 00553 b1->prev_hdr = b0; 00554 lb0 = lb1; 00555 00556 continue; 00557 } 00558 00559 /* Merging the new area with the previous physically contigous 00560 one */ 00561 if ((unsigned long) lb1->ptr.buffer == (unsigned long) ib0) { 00562 if (tlsf->area_head == ptr) { 00563 tlsf->area_head = ptr->next; 00564 ptr = ptr->next; 00565 } else { 00566 ptr_prev->next = ptr->next; 00567 ptr = ptr->next; 00568 } 00569 00570 lb1->size = 00571 ROUNDDOWN_SIZE((b0->size & BLOCK_SIZE) + 00572 (ib0->size & BLOCK_SIZE) + 00573 2 * BHDR_OVERHEAD) | USED_BLOCK | (lb1->size & PREV_STATE); 00574 next_b = GET_NEXT_BLOCK(lb1->ptr.buffer, lb1->size & BLOCK_SIZE); 00575 next_b->prev_hdr = lb1; 00576 b0 = lb1; 00577 ib0 = ib1; 00578 00579 continue; 00580 } 00581 ptr_prev = ptr; 00582 ptr = ptr->next; 00583 } 00584 00585 /* Inserting the area in the list of linked areas */ 00586 ai = (area_info_t *) ib0->ptr.buffer; 00587 ai->next = tlsf->area_head; 00588 ai->end = lb0; 00589 tlsf->area_head = ai; 00590 rtl_free_ex(b0->ptr.buffer, mem_pool); 00591 00592 #if TLSF_STATISTIC 00593 tlsf->used_size=savesz; 00594 #endif 00595 return (b0->size & BLOCK_SIZE); 00596 } 00597 00598 00599 /******************************************************************/ 00600 size_t rtl_get_used_size(void *mem_pool ATTRIBUTE_UNUSED) { 00601 /******************************************************************/ 00602 #if TLSF_STATISTIC 00603 return ((tlsf_t *) mem_pool)->used_size; 00604 #else 00605 return 0; 00606 #endif 00607 } 00608 00609 /******************************************************************/ 00610 size_t rtl_get_max_size(void *mem_pool ATTRIBUTE_UNUSED) { 00611 /******************************************************************/ 00612 #if TLSF_STATISTIC 00613 return ((tlsf_t *) mem_pool)->max_size; 00614 #else 00615 return 0; 00616 #endif 00617 } 00618 00619 /******************************************************************/ 00620 void rtl_destroy_memory_pool(void *mem_pool) { 00621 /******************************************************************/ 00622 tlsf_t *tlsf = (tlsf_t *) mem_pool; 00623 00624 tlsf->tlsf_signature = 0; 00625 00626 TLSF_DESTROY_LOCK(&tlsf->lock); 00627 00628 } 00629 00630 00631 /******************************************************************/ 00632 void *rtl_tlsf_malloc(size_t size) { 00633 /******************************************************************/ 00634 void *ret; 00635 00636 #if USE_MMAP || USE_SBRK 00637 if (!mp) { 00638 size_t area_size; 00639 void *area; 00640 00641 area_size = sizeof(tlsf_t) + BHDR_OVERHEAD * 8; /* Just a safety constant */ 00642 area_size = (area_size > DEFAULT_AREA_SIZE) ? area_size : DEFAULT_AREA_SIZE; 00643 area = get_new_area(&area_size); 00644 if (area == ((void *) ~0)) 00645 return NULL; /* Not enough system memory */ 00646 rtl_init_memory_pool(area_size, area); 00647 } 00648 #endif 00649 00650 TLSF_ACQUIRE_LOCK(&((tlsf_t *) mp)->lock); 00651 00652 ret = rtl_malloc_ex(size, mp); 00653 00654 TLSF_RELEASE_LOCK(&((tlsf_t *) mp)->lock); 00655 00656 return ret; 00657 } 00658 00659 /******************************************************************/ 00660 void rtl_tlsf_free(void *ptr) { 00661 /******************************************************************/ 00662 00663 TLSF_ACQUIRE_LOCK(&((tlsf_t *) mp)->lock); 00664 00665 rtl_free_ex(ptr, mp); 00666 00667 TLSF_RELEASE_LOCK(&((tlsf_t *) mp)->lock); 00668 00669 } 00670 00671 /******************************************************************/ 00672 void *rtl_tlsf_realloc(void *ptr, size_t size) { 00673 /******************************************************************/ 00674 void *ret; 00675 00676 #if USE_MMAP || USE_SBRK 00677 if (!mp) { 00678 return rtl_tlsf_malloc(size); 00679 } 00680 #endif 00681 00682 TLSF_ACQUIRE_LOCK(&((tlsf_t *) mp)->lock); 00683 00684 ret = rtl_realloc_ex(ptr, size, mp); 00685 00686 TLSF_RELEASE_LOCK(&((tlsf_t *) mp)->lock); 00687 00688 return ret; 00689 } 00690 00691 /******************************************************************/ 00692 void *rtl_tlsf_calloc(size_t nelem, size_t elem_size) { 00693 /******************************************************************/ 00694 void *ret; 00695 00696 TLSF_ACQUIRE_LOCK(&((tlsf_t *) mp)->lock); 00697 00698 ret = rtl_calloc_ex(nelem, elem_size, mp); 00699 00700 TLSF_RELEASE_LOCK(&((tlsf_t *) mp)->lock); 00701 00702 return ret; 00703 } 00704 00705 /******************************************************************/ 00706 void *rtl_malloc_ex(size_t size, void *mem_pool) { 00707 /******************************************************************/ 00708 tlsf_t *tlsf = (tlsf_t *) mem_pool; 00709 bhdr_t *b, *b2, *next_b; 00710 int fl, sl; 00711 size_t tmp_size; 00712 00713 size = (size < MIN_BLOCK_SIZE) ? MIN_BLOCK_SIZE : ROUNDUP_SIZE(size); 00714 00715 /* Rounding up the requested size and calculating fl and sl */ 00716 MAPPING_SEARCH(&size, &fl, &sl); 00717 00718 /* Searching a free block, recall that this function changes the values of fl and sl, 00719 so they are not longer valid when the function fails */ 00720 b = FIND_SUITABLE_BLOCK(tlsf, &fl, &sl); 00721 #if USE_MMAP || USE_SBRK 00722 if (!b) { 00723 size_t area_size; 00724 void *area; 00725 /* Growing the pool size when needed */ 00726 area_size = size + BHDR_OVERHEAD * 8; /* size plus enough room for the requered headers. */ 00727 area_size = (area_size > DEFAULT_AREA_SIZE) ? area_size : DEFAULT_AREA_SIZE; 00728 area = get_new_area(&area_size); /* Call sbrk or mmap */ 00729 if (area == ((void *) ~0)) 00730 return NULL; /* Not enough system memory */ 00731 rtl_add_new_area(area, area_size, mem_pool); 00732 /* Rounding up the requested size and calculating fl and sl */ 00733 MAPPING_SEARCH(&size, &fl, &sl); 00734 /* Searching a free block */ 00735 b = FIND_SUITABLE_BLOCK(tlsf, &fl, &sl); 00736 } 00737 #endif 00738 if (!b) 00739 return NULL; /* Not found */ 00740 00741 EXTRACT_BLOCK_HDR(b, tlsf, fl, sl); 00742 00743 /*-- found: */ 00744 next_b = GET_NEXT_BLOCK(b->ptr.buffer, b->size & BLOCK_SIZE); 00745 /* Should the block be split? */ 00746 tmp_size = (b->size & BLOCK_SIZE) - size; 00747 if (tmp_size >= sizeof(bhdr_t)) { 00748 tmp_size -= BHDR_OVERHEAD; 00749 b2 = GET_NEXT_BLOCK(b->ptr.buffer, size); 00750 b2->size = tmp_size | FREE_BLOCK | PREV_USED; 00751 next_b->prev_hdr = b2; 00752 MAPPING_INSERT(tmp_size, &fl, &sl); 00753 INSERT_BLOCK(b2, tlsf, fl, sl); 00754 00755 b->size = size | (b->size & PREV_STATE); 00756 } else { 00757 next_b->size &= (~PREV_FREE); 00758 b->size &= (~FREE_BLOCK); /* Now it's used */ 00759 } 00760 00761 TLSF_ADD_SIZE(tlsf, b); 00762 00763 return (void *) b->ptr.buffer; 00764 } 00765 00766 /******************************************************************/ 00767 void rtl_free_ex(void *ptr, void *mem_pool) { 00768 /******************************************************************/ 00769 tlsf_t *tlsf = (tlsf_t *) mem_pool; 00770 bhdr_t *b, *tmp_b; 00771 int fl = 0, sl = 0; 00772 00773 if (!ptr) { 00774 return; 00775 } 00776 b = (bhdr_t *) ((char *) ptr - BHDR_OVERHEAD); 00777 00778 #ifdef CHECK_DOUBLE_FREE 00779 if (b->size & FREE_BLOCK) { 00780 ERROR_MSG("rtl_free_ex(): double free %p\n", ptr); 00781 return; 00782 } 00783 #endif 00784 00785 b->size |= FREE_BLOCK; 00786 00787 TLSF_REMOVE_SIZE(tlsf, b); 00788 00789 b->ptr.free_ptr.prev = NULL; 00790 b->ptr.free_ptr.next = NULL; 00791 tmp_b = GET_NEXT_BLOCK(b->ptr.buffer, b->size & BLOCK_SIZE); 00792 if (tmp_b->size & FREE_BLOCK) { 00793 MAPPING_INSERT(tmp_b->size & BLOCK_SIZE, &fl, &sl); 00794 EXTRACT_BLOCK(tmp_b, tlsf, fl, sl); 00795 b->size += (tmp_b->size & BLOCK_SIZE) + BHDR_OVERHEAD; 00796 } 00797 if (b->size & PREV_FREE) { 00798 tmp_b = b->prev_hdr; 00799 MAPPING_INSERT(tmp_b->size & BLOCK_SIZE, &fl, &sl); 00800 EXTRACT_BLOCK(tmp_b, tlsf, fl, sl); 00801 tmp_b->size += (b->size & BLOCK_SIZE) + BHDR_OVERHEAD; 00802 b = tmp_b; 00803 } 00804 MAPPING_INSERT(b->size & BLOCK_SIZE, &fl, &sl); 00805 INSERT_BLOCK(b, tlsf, fl, sl); 00806 00807 tmp_b = GET_NEXT_BLOCK(b->ptr.buffer, b->size & BLOCK_SIZE); 00808 tmp_b->size |= PREV_FREE; 00809 tmp_b->prev_hdr = b; 00810 } 00811 00812 /******************************************************************/ 00813 void *rtl_realloc_ex(void *ptr, size_t new_size, void *mem_pool) { 00814 /******************************************************************/ 00815 tlsf_t *tlsf = (tlsf_t *) mem_pool; 00816 void *ptr_aux; 00817 unsigned int cpsize; 00818 bhdr_t *b, *tmp_b, *next_b; 00819 int fl, sl; 00820 size_t tmp_size; 00821 00822 if (!ptr) { 00823 if (new_size) 00824 return (void *) rtl_malloc_ex(new_size, mem_pool); 00825 if (!new_size) 00826 return NULL; 00827 } else if (!new_size) { 00828 rtl_free_ex(ptr, mem_pool); 00829 return NULL; 00830 } 00831 00832 b = (bhdr_t *) ((char *) ptr - BHDR_OVERHEAD); 00833 00834 #ifdef CHECK_DOUBLE_FREE 00835 if (b->size & FREE_BLOCK) { 00836 ERROR_MSG("rtl_realloc_ex(): invalid pointer %p\n", ptr); 00837 return (void *) rtl_malloc_ex(new_size, mem_pool); 00838 } 00839 #endif 00840 00841 next_b = GET_NEXT_BLOCK(b->ptr.buffer, b->size & BLOCK_SIZE); 00842 new_size = (new_size < MIN_BLOCK_SIZE) ? MIN_BLOCK_SIZE : ROUNDUP_SIZE(new_size); 00843 tmp_size = (b->size & BLOCK_SIZE); 00844 if (new_size <= tmp_size) { 00845 TLSF_REMOVE_SIZE(tlsf, b); 00846 if (next_b->size & FREE_BLOCK) { 00847 MAPPING_INSERT(next_b->size & BLOCK_SIZE, &fl, &sl); 00848 EXTRACT_BLOCK(next_b, tlsf, fl, sl); 00849 tmp_size += (next_b->size & BLOCK_SIZE) + BHDR_OVERHEAD; 00850 next_b = GET_NEXT_BLOCK(next_b->ptr.buffer, next_b->size & BLOCK_SIZE); 00851 /* We allways reenter this free block because tmp_size will 00852 be greater then sizeof (bhdr_t) */ 00853 } 00854 tmp_size -= new_size; 00855 if (tmp_size >= sizeof(bhdr_t)) { 00856 tmp_size -= BHDR_OVERHEAD; 00857 tmp_b = GET_NEXT_BLOCK(b->ptr.buffer, new_size); 00858 tmp_b->size = tmp_size | FREE_BLOCK | PREV_USED; 00859 next_b->prev_hdr = tmp_b; 00860 next_b->size |= PREV_FREE; 00861 MAPPING_INSERT(tmp_size, &fl, &sl); 00862 INSERT_BLOCK(tmp_b, tlsf, fl, sl); 00863 b->size = new_size | (b->size & PREV_STATE); 00864 } 00865 TLSF_ADD_SIZE(tlsf, b); 00866 return (void *) b->ptr.buffer; 00867 } 00868 if ((next_b->size & FREE_BLOCK)) { 00869 if (new_size <= (tmp_size + (next_b->size & BLOCK_SIZE))) { 00870 TLSF_REMOVE_SIZE(tlsf, b); 00871 MAPPING_INSERT(next_b->size & BLOCK_SIZE, &fl, &sl); 00872 EXTRACT_BLOCK(next_b, tlsf, fl, sl); 00873 b->size += (next_b->size & BLOCK_SIZE) + BHDR_OVERHEAD; 00874 next_b = GET_NEXT_BLOCK(b->ptr.buffer, b->size & BLOCK_SIZE); 00875 next_b->prev_hdr = b; 00876 next_b->size &= ~PREV_FREE; 00877 tmp_size = (b->size & BLOCK_SIZE) - new_size; 00878 if (tmp_size >= sizeof(bhdr_t)) { 00879 tmp_size -= BHDR_OVERHEAD; 00880 tmp_b = GET_NEXT_BLOCK(b->ptr.buffer, new_size); 00881 tmp_b->size = tmp_size | FREE_BLOCK | PREV_USED; 00882 next_b->prev_hdr = tmp_b; 00883 next_b->size |= PREV_FREE; 00884 MAPPING_INSERT(tmp_size, &fl, &sl); 00885 INSERT_BLOCK(tmp_b, tlsf, fl, sl); 00886 b->size = new_size | (b->size & PREV_STATE); 00887 } 00888 TLSF_ADD_SIZE(tlsf, b); 00889 return (void *) b->ptr.buffer; 00890 } 00891 } 00892 00893 if (!(ptr_aux = rtl_malloc_ex(new_size, mem_pool))) { 00894 return NULL; 00895 } 00896 00897 cpsize = ((b->size & BLOCK_SIZE) > new_size) ? new_size : (b->size & BLOCK_SIZE); 00898 00899 memcpy(ptr_aux, ptr, cpsize); 00900 00901 rtl_free_ex(ptr, mem_pool); 00902 return ptr_aux; 00903 } 00904 00905 00906 /******************************************************************/ 00907 void *rtl_calloc_ex(size_t nelem, size_t elem_size, void *mem_pool) { 00908 /******************************************************************/ 00909 void *ptr; 00910 00911 if (nelem <= 0 || elem_size <= 0) 00912 return NULL; 00913 00914 if (!(ptr = rtl_malloc_ex(nelem * elem_size, mem_pool))) 00915 return NULL; 00916 memset(ptr, 0, nelem * elem_size); 00917 00918 return ptr; 00919 } 00920 00921 00922 00923 #if _DEBUG_TLSF_ 00924 00925 /*************** DEBUG FUNCTIONS **************/ 00926 00927 /* The following functions have been designed to ease the debugging of */ 00928 /* the TLSF structure. For non-developing purposes, it may be they */ 00929 /* haven't too much worth. To enable them, _DEBUG_TLSF_ must be set. */ 00930 00931 extern void dump_memory_region(unsigned char *mem_ptr, unsigned int size); 00932 extern void print_block(bhdr_t * b); 00933 extern void print_tlsf(tlsf_t * tlsf); 00934 void print_all_blocks(tlsf_t * tlsf); 00935 00936 void dump_memory_region(unsigned char *mem_ptr, unsigned int size) { 00937 00938 unsigned long begin = (unsigned long) mem_ptr; 00939 unsigned long end = (unsigned long) mem_ptr + size; 00940 int column = 0; 00941 00942 begin >>= 2; 00943 begin <<= 2; 00944 00945 end >>= 2; 00946 end++; 00947 end <<= 2; 00948 00949 PRINT_MSG("\nMemory region dumped: 0x%lx - 0x%lx\n\n", begin, end); 00950 00951 column = 0; 00952 PRINT_MSG("0x%lx ", begin); 00953 00954 while (begin < end) { 00955 if (((unsigned char *) begin)[0] == 0) 00956 PRINT_MSG("00"); 00957 else 00958 PRINT_MSG("%02x", ((unsigned char *) begin)[0]); 00959 if (((unsigned char *) begin)[1] == 0) 00960 PRINT_MSG("00 "); 00961 else 00962 PRINT_MSG("%02x ", ((unsigned char *) begin)[1]); 00963 begin += 2; 00964 column++; 00965 if (column == 8) { 00966 PRINT_MSG("\n0x%lx ", begin); 00967 column = 0; 00968 } 00969 00970 } 00971 PRINT_MSG("\n\n"); 00972 } 00973 00974 void print_block(bhdr_t * b) { 00975 if (!b) 00976 return; 00977 PRINT_MSG(">> [%p] (", b); 00978 if ((b->size & BLOCK_SIZE)) 00979 PRINT_MSG("%lu bytes, ", (unsigned long) (b->size & BLOCK_SIZE)); 00980 else 00981 PRINT_MSG("sentinel, "); 00982 if ((b->size & BLOCK_STATE) == FREE_BLOCK) 00983 PRINT_MSG("free [%p, %p], ", b->ptr.free_ptr.prev, b->ptr.free_ptr.next); 00984 else 00985 PRINT_MSG("used, "); 00986 if ((b->size & PREV_STATE) == PREV_FREE) 00987 PRINT_MSG("prev. free [%p])\n", b->prev_hdr); 00988 else 00989 PRINT_MSG("prev used)\n"); 00990 } 00991 00992 void print_tlsf(tlsf_t * tlsf) { 00993 bhdr_t *next; 00994 int i, j; 00995 00996 PRINT_MSG("\nTLSF at %p\n", tlsf); 00997 00998 PRINT_MSG("FL bitmap: 0x%x\n\n", (unsigned) tlsf->fl_bitmap); 00999 01000 for (i = 0; i < REAL_FLI; i++) { 01001 if (tlsf->sl_bitmap[i]) 01002 PRINT_MSG("SL bitmap 0x%x\n", (unsigned) tlsf->sl_bitmap[i]); 01003 for (j = 0; j < MAX_SLI; j++) { 01004 next = tlsf->matrix[i][j]; 01005 if (next) 01006 PRINT_MSG("-> [%d][%d]\n", i, j); 01007 while (next) { 01008 print_block(next); 01009 next = next->ptr.free_ptr.next; 01010 } 01011 } 01012 } 01013 } 01014 01015 void print_all_blocks(tlsf_t * tlsf) { 01016 area_info_t *ai; 01017 bhdr_t *next; 01018 PRINT_MSG("\nTLSF at %p\nALL BLOCKS\n\n", tlsf); 01019 ai = tlsf->area_head; 01020 while (ai) { 01021 next = (bhdr_t *) ((char *) ai - BHDR_OVERHEAD); 01022 while (next) { 01023 print_block(next); 01024 if ((next->size & BLOCK_SIZE)) 01025 next = GET_NEXT_BLOCK(next->ptr.buffer, next->size & BLOCK_SIZE); 01026 else 01027 next = NULL; 01028 } 01029 ai = ai->next; 01030 } 01031 } 01032 01033 #endif