tlsf.c
Go to the documentation of this file.
00001 /*
00002  * Two Levels Segregate Fit memory allocator (TLSF)
00003  * Version 2.4.4
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 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  *
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 
00056 // needed for sbrk() and MAP_ANON in 10.6 (at least)
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 /* The  debug functions  only can  be used  when _DEBUG_TLSF_  is set. */
00128 #ifndef _DEBUG_TLSF_
00129 #define _DEBUG_TLSF_  (0)
00130 #endif
00131 
00132 /*************************************************************************/
00133 /* Definition of the structures used by TLSF */
00134 
00135 
00136 /* Some IMPORTANT TLSF parameters */
00137 /* Unlike the preview TLSF versions, now they are statics */
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)     /* MAX_SLI = 2^MAX_LOG2_SLI */
00143 
00144 #define FLI_OFFSET      (6)     /* tlsf structure just will manage blocks bigger */
00145 /* than 128 bytes */
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 /* bit 0 of the block size */
00165 #define FREE_BLOCK      (0x1)
00166 #define USED_BLOCK      (0x0)
00167 
00168 /* bit 1 of the block size */
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;     /* NOTE: Make sure that this type is 4 bytes long on your computer */
00183 typedef unsigned char u8_t;     /* NOTE: Make sure that this type is 1 byte on your computer */
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     /* This pointer is just valid if the first bit of size is set */
00192     struct bhdr_struct *prev_hdr;
00193     /* The size is stored in bytes */
00194     size_t size;                /* bit 0 indicates whether the block is used and */
00195     /* bit 1 allows to know whether the previous block is free */
00196     union {
00197         struct free_ptr_struct free_ptr;
00198         u8_t buffer[1];         /*sizeof(struct free_ptr_struct)]; */
00199     } ptr;
00200 } bhdr_t;
00201 
00202 /* This structure is embedded at the beginning of each area, giving us
00203  * enough information to cope with a set of areas */
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     /* the TLSF's structure signature */
00212     u32_t tlsf_signature;
00213 
00214 #if TLSF_USE_LOCKS
00215     TLSF_MLOCK_T lock;
00216 #endif
00217 
00218 #if TLSF_STATISTIC
00219     /* These can not be calculated outside tlsf because we
00220      * do not know the sizes when freeing/reallocing memory. */
00221     size_t used_size;
00222     size_t max_size;
00223 #endif
00224 
00225     /* A linked list holding all the existing areas */
00226     area_info_t *area_head;
00227 
00228     /* the first-level bitmap */
00229     /* This array should have a size of REAL_FLI bits */
00230     u32_t fl_bitmap;
00231 
00232     /* the second-level bitmap */
00233     u32_t sl_bitmap[REAL_FLI];
00234 
00235     bhdr_t *matrix[REAL_FLI][MAX_SLI];
00236 } tlsf_t;
00237 
00238 
00239 /******************************************************************/
00240 /**************     Helping functions    **************************/
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         /*if ((*_fl -= FLI_OFFSET) < 0) // FL wil be always >0!
00323          *_fl = *_sl = 0;
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) {         /* likely */
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 /******************** Begin of the allocator code *****************/
00445 /******************************************************************/
00446 
00447 static char *mp = NULL;         /* Default memory pool. */
00448 static int  init_check = 0;          /* Init detection */
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     /* Check if already initialised */
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     /* Zeroing the memory pool */
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     /* Before inserting the new area, we have to merge this area with the
00515        already existing ones */
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         /* Merging the new area with the next physically contigous one */
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         /* Merging the new area with the previous physically contigous
00543            one */
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     /* Inserting the area in the list of linked areas */
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 // use default memory pool
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 // use default memory pool
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; /* Just a safety constant */
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;        /* Not enough system memory */
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     /* Rounding up the requested size and calculating fl and sl */
00726     MAPPING_SEARCH(&size, &fl, &sl);
00727 
00728     /* Searching a free block, recall that this function changes the values of fl and sl,
00729        so they are not longer valid when the function fails */
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         /* Growing the pool size when needed */
00736         area_size = size + BHDR_OVERHEAD * 8;   /* size plus enough room for the requered headers. */
00737         area_size = (area_size > DEFAULT_AREA_SIZE) ? area_size : DEFAULT_AREA_SIZE;
00738         area = get_new_area(&area_size);        /* Call sbrk or mmap */
00739         if (area == ((void *) ~0))
00740             return NULL;        /* Not enough system memory */
00741         add_new_area(area, area_size, mem_pool);
00742         /* Rounding up the requested size and calculating fl and sl */
00743         MAPPING_SEARCH(&size, &fl, &sl);
00744         /* Searching a free block */
00745         b = FIND_SUITABLE_BLOCK(tlsf, &fl, &sl);
00746     }
00747 #endif
00748     if (!b)
00749         return NULL;            /* Not found */
00750 
00751     EXTRACT_BLOCK_HDR(b, tlsf, fl, sl);
00752 
00753     /*-- found: */
00754     next_b = GET_NEXT_BLOCK(b->ptr.buffer, b->size & BLOCK_SIZE);
00755     /* Should the block be split? */
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);       /* Now it's used */
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             /* We allways reenter this free block because tmp_size will
00848                be greater then sizeof (bhdr_t) */
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 /***************  DEBUG FUNCTIONS   **************/
00921 
00922 /* The following functions have been designed to ease the debugging of */
00923 /* the TLSF  structure.  For non-developing  purposes, it may  be they */
00924 /* haven't too much worth.  To enable them, _DEBUG_TLSF_ must be set.  */
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


rtt
Author(s): RTT Developers
autogenerated on Wed Aug 26 2015 16:16:19