OrocosComponentLibrary  2.7.0
tlsf.c
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