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 size_t get_max_size(void *mem_pool)
00590 {
00591 /******************************************************************/
00592 #if TLSF_STATISTIC
00593     return ((tlsf_t *) mem_pool)->max_size;
00594 #else
00595     return 0;
00596 #endif
00597 }
00598 
00599 /******************************************************************/
00600 void destroy_memory_pool(void *mem_pool)
00601 {
00602 /******************************************************************/
00603     tlsf_t *tlsf = (tlsf_t *) mem_pool;
00604 
00605     tlsf->tlsf_signature = 0;
00606 
00607     TLSF_DESTROY_LOCK(&tlsf->lock);
00608 
00609 }
00610 
00611 
00612 /******************************************************************/
00613 void *tlsf_malloc(size_t size)
00614 {
00615 /******************************************************************/
00616     void *ret;
00617 
00618 #if USE_MMAP || USE_SBRK
00619     if (!mp) {
00620         size_t area_size;
00621         void *area;
00622 
00623         area_size = sizeof(tlsf_t) + BHDR_OVERHEAD * 8; /* Just a safety constant */
00624         area_size = (area_size > DEFAULT_AREA_SIZE) ? area_size : DEFAULT_AREA_SIZE;
00625         area = get_new_area(&area_size);
00626         if (area == ((void *) ~0))
00627             return NULL;        /* Not enough system memory */
00628         init_memory_pool(area_size, area);
00629     }
00630 #endif
00631 
00632     TLSF_ACQUIRE_LOCK(&((tlsf_t *)mp)->lock);
00633 
00634     ret = malloc_ex(size, mp);
00635 
00636     TLSF_RELEASE_LOCK(&((tlsf_t *)mp)->lock);
00637 
00638     return ret;
00639 }
00640 
00641 /******************************************************************/
00642 void tlsf_free(void *ptr)
00643 {
00644 /******************************************************************/
00645 
00646     TLSF_ACQUIRE_LOCK(&((tlsf_t *)mp)->lock);
00647 
00648     free_ex(ptr, mp);
00649 
00650     TLSF_RELEASE_LOCK(&((tlsf_t *)mp)->lock);
00651 
00652 }
00653 
00654 /******************************************************************/
00655 void *tlsf_realloc(void *ptr, size_t size)
00656 {
00657 /******************************************************************/
00658     void *ret;
00659 
00660 #if USE_MMAP || USE_SBRK
00661         if (!mp) {
00662                 return tlsf_malloc(size);
00663         }
00664 #endif
00665 
00666     TLSF_ACQUIRE_LOCK(&((tlsf_t *)mp)->lock);
00667 
00668     ret = realloc_ex(ptr, size, mp);
00669 
00670     TLSF_RELEASE_LOCK(&((tlsf_t *)mp)->lock);
00671 
00672     return ret;
00673 }
00674 
00675 /******************************************************************/
00676 void *tlsf_calloc(size_t nelem, size_t elem_size)
00677 {
00678 /******************************************************************/
00679     void *ret;
00680 
00681     TLSF_ACQUIRE_LOCK(&((tlsf_t *)mp)->lock);
00682 
00683     ret = calloc_ex(nelem, elem_size, mp);
00684 
00685     TLSF_RELEASE_LOCK(&((tlsf_t *)mp)->lock);
00686 
00687     return ret;
00688 }
00689 
00690 /******************************************************************/
00691 void *malloc_ex(size_t size, void *mem_pool)
00692 {
00693 /******************************************************************/
00694     tlsf_t *tlsf = (tlsf_t *) mem_pool;
00695     bhdr_t *b, *b2, *next_b;
00696     int fl, sl;
00697     size_t tmp_size;
00698 
00699     size = (size < MIN_BLOCK_SIZE) ? MIN_BLOCK_SIZE : ROUNDUP_SIZE(size);
00700 
00701     /* Rounding up the requested size and calculating fl and sl */
00702     MAPPING_SEARCH(&size, &fl, &sl);
00703 
00704     /* Searching a free block, recall that this function changes the values of fl and sl,
00705        so they are not longer valid when the function fails */
00706     b = FIND_SUITABLE_BLOCK(tlsf, &fl, &sl);
00707 #if USE_MMAP || USE_SBRK
00708     if (!b) {
00709         size_t area_size;
00710         void *area;
00711         /* Growing the pool size when needed */
00712         area_size = size + BHDR_OVERHEAD * 8;   /* size plus enough room for the requered headers. */
00713         area_size = (area_size > DEFAULT_AREA_SIZE) ? area_size : DEFAULT_AREA_SIZE;
00714         area = get_new_area(&area_size);        /* Call sbrk or mmap */
00715         if (area == ((void *) ~0))
00716             return NULL;        /* Not enough system memory */
00717         add_new_area(area, area_size, mem_pool);
00718         /* Rounding up the requested size and calculating fl and sl */
00719         MAPPING_SEARCH(&size, &fl, &sl);
00720         /* Searching a free block */
00721         b = FIND_SUITABLE_BLOCK(tlsf, &fl, &sl);
00722     }
00723 #endif
00724     if (!b)
00725         return NULL;            /* Not found */
00726 
00727     EXTRACT_BLOCK_HDR(b, tlsf, fl, sl);
00728 
00729     /*-- found: */
00730     next_b = GET_NEXT_BLOCK(b->ptr.buffer, b->size & BLOCK_SIZE);
00731     /* Should the block be split? */
00732     tmp_size = (b->size & BLOCK_SIZE) - size;
00733     if (tmp_size >= sizeof(bhdr_t)) {
00734         tmp_size -= BHDR_OVERHEAD;
00735         b2 = GET_NEXT_BLOCK(b->ptr.buffer, size);
00736         b2->size = tmp_size | FREE_BLOCK | PREV_USED;
00737         next_b->prev_hdr = b2;
00738         MAPPING_INSERT(tmp_size, &fl, &sl);
00739         INSERT_BLOCK(b2, tlsf, fl, sl);
00740 
00741         b->size = size | (b->size & PREV_STATE);
00742     } else {
00743         next_b->size &= (~PREV_FREE);
00744         b->size &= (~FREE_BLOCK);       /* Now it's used */
00745     }
00746 
00747     TLSF_ADD_SIZE(tlsf, b);
00748 
00749     return (void *) b->ptr.buffer;
00750 }
00751 
00752 /******************************************************************/
00753 void free_ex(void *ptr, void *mem_pool)
00754 {
00755 /******************************************************************/
00756     tlsf_t *tlsf = (tlsf_t *) mem_pool;
00757     bhdr_t *b, *tmp_b;
00758     int fl = 0, sl = 0;
00759 
00760     if (!ptr) {
00761         return;
00762     }
00763     b = (bhdr_t *) ((char *) ptr - BHDR_OVERHEAD);
00764     b->size |= FREE_BLOCK;
00765 
00766     TLSF_REMOVE_SIZE(tlsf, b);
00767 
00768     b->ptr.free_ptr.prev = NULL;
00769     b->ptr.free_ptr.next = NULL;
00770     tmp_b = GET_NEXT_BLOCK(b->ptr.buffer, b->size & BLOCK_SIZE);
00771     if (tmp_b->size & FREE_BLOCK) {
00772         MAPPING_INSERT(tmp_b->size & BLOCK_SIZE, &fl, &sl);
00773         EXTRACT_BLOCK(tmp_b, tlsf, fl, sl);
00774         b->size += (tmp_b->size & BLOCK_SIZE) + BHDR_OVERHEAD;
00775     }
00776     if (b->size & PREV_FREE) {
00777         tmp_b = b->prev_hdr;
00778         MAPPING_INSERT(tmp_b->size & BLOCK_SIZE, &fl, &sl);
00779         EXTRACT_BLOCK(tmp_b, tlsf, fl, sl);
00780         tmp_b->size += (b->size & BLOCK_SIZE) + BHDR_OVERHEAD;
00781         b = tmp_b;
00782     }
00783     MAPPING_INSERT(b->size & BLOCK_SIZE, &fl, &sl);
00784     INSERT_BLOCK(b, tlsf, fl, sl);
00785 
00786     tmp_b = GET_NEXT_BLOCK(b->ptr.buffer, b->size & BLOCK_SIZE);
00787     tmp_b->size |= PREV_FREE;
00788     tmp_b->prev_hdr = b;
00789 }
00790 
00791 /******************************************************************/
00792 void *realloc_ex(void *ptr, size_t new_size, void *mem_pool)
00793 {
00794 /******************************************************************/
00795     tlsf_t *tlsf = (tlsf_t *) mem_pool;
00796     void *ptr_aux;
00797     unsigned int cpsize;
00798     bhdr_t *b, *tmp_b, *next_b;
00799     int fl, sl;
00800     size_t tmp_size;
00801 
00802     if (!ptr) {
00803         if (new_size)
00804             return (void *) malloc_ex(new_size, mem_pool);
00805         if (!new_size)
00806             return NULL;
00807     } else if (!new_size) {
00808         free_ex(ptr, mem_pool);
00809         return NULL;
00810     }
00811 
00812     b = (bhdr_t *) ((char *) ptr - BHDR_OVERHEAD);
00813     next_b = GET_NEXT_BLOCK(b->ptr.buffer, b->size & BLOCK_SIZE);
00814     new_size = (new_size < MIN_BLOCK_SIZE) ? MIN_BLOCK_SIZE : ROUNDUP_SIZE(new_size);
00815     tmp_size = (b->size & BLOCK_SIZE);
00816     if (new_size <= tmp_size) {
00817         TLSF_REMOVE_SIZE(tlsf, b);
00818         if (next_b->size & FREE_BLOCK) {
00819             MAPPING_INSERT(next_b->size & BLOCK_SIZE, &fl, &sl);
00820             EXTRACT_BLOCK(next_b, tlsf, fl, sl);
00821             tmp_size += (next_b->size & BLOCK_SIZE) + BHDR_OVERHEAD;
00822             next_b = GET_NEXT_BLOCK(next_b->ptr.buffer, next_b->size & BLOCK_SIZE);
00823             /* We allways reenter this free block because tmp_size will
00824                be greater then sizeof (bhdr_t) */
00825         }
00826         tmp_size -= new_size;
00827         if (tmp_size >= sizeof(bhdr_t)) {
00828             tmp_size -= BHDR_OVERHEAD;
00829             tmp_b = GET_NEXT_BLOCK(b->ptr.buffer, new_size);
00830             tmp_b->size = tmp_size | FREE_BLOCK | PREV_USED;
00831             next_b->prev_hdr = tmp_b;
00832             next_b->size |= PREV_FREE;
00833             MAPPING_INSERT(tmp_size, &fl, &sl);
00834             INSERT_BLOCK(tmp_b, tlsf, fl, sl);
00835             b->size = new_size | (b->size & PREV_STATE);
00836         }
00837         TLSF_ADD_SIZE(tlsf, b);
00838         return (void *) b->ptr.buffer;
00839     }
00840     if ((next_b->size & FREE_BLOCK)) {
00841         if (new_size <= (tmp_size + (next_b->size & BLOCK_SIZE))) {
00842                         TLSF_REMOVE_SIZE(tlsf, b);
00843             MAPPING_INSERT(next_b->size & BLOCK_SIZE, &fl, &sl);
00844             EXTRACT_BLOCK(next_b, tlsf, fl, sl);
00845             b->size += (next_b->size & BLOCK_SIZE) + BHDR_OVERHEAD;
00846             next_b = GET_NEXT_BLOCK(b->ptr.buffer, b->size & BLOCK_SIZE);
00847             next_b->prev_hdr = b;
00848             next_b->size &= ~PREV_FREE;
00849             tmp_size = (b->size & BLOCK_SIZE) - new_size;
00850             if (tmp_size >= sizeof(bhdr_t)) {
00851                 tmp_size -= BHDR_OVERHEAD;
00852                 tmp_b = GET_NEXT_BLOCK(b->ptr.buffer, new_size);
00853                 tmp_b->size = tmp_size | FREE_BLOCK | PREV_USED;
00854                 next_b->prev_hdr = tmp_b;
00855                 next_b->size |= PREV_FREE;
00856                 MAPPING_INSERT(tmp_size, &fl, &sl);
00857                 INSERT_BLOCK(tmp_b, tlsf, fl, sl);
00858                 b->size = new_size | (b->size & PREV_STATE);
00859             }
00860                         TLSF_ADD_SIZE(tlsf, b);
00861             return (void *) b->ptr.buffer;
00862         }
00863     }
00864 
00865     ptr_aux = malloc_ex(new_size, mem_pool);
00866 
00867     cpsize = ((b->size & BLOCK_SIZE) > new_size) ? new_size : (b->size & BLOCK_SIZE);
00868 
00869     memcpy(ptr_aux, ptr, cpsize);
00870 
00871     free_ex(ptr, mem_pool);
00872     return ptr_aux;
00873 }
00874 
00875 
00876 /******************************************************************/
00877 void *calloc_ex(size_t nelem, size_t elem_size, void *mem_pool)
00878 {
00879 /******************************************************************/
00880     void *ptr;
00881 
00882     if (nelem <= 0 || elem_size <= 0)
00883         return NULL;
00884 
00885     if (!(ptr = malloc_ex(nelem * elem_size, mem_pool)))
00886         return NULL;
00887     memset(ptr, 0, nelem * elem_size);
00888 
00889     return ptr;
00890 }
00891 
00892 
00893 
00894 #if _DEBUG_TLSF_
00895 
00896 /***************  DEBUG FUNCTIONS   **************/
00897 
00898 /* The following functions have been designed to ease the debugging of */
00899 /* the TLSF  structure.  For non-developing  purposes, it may  be they */
00900 /* haven't too much worth.  To enable them, _DEBUG_TLSF_ must be set.  */
00901 
00902 extern void dump_memory_region(unsigned char *mem_ptr, unsigned int size);
00903 extern void print_block(bhdr_t * b);
00904 extern void print_tlsf(tlsf_t * tlsf);
00905 void print_all_blocks(tlsf_t * tlsf);
00906 
00907 void dump_memory_region(unsigned char *mem_ptr, unsigned int size)
00908 {
00909 
00910     unsigned long begin = (unsigned long) mem_ptr;
00911     unsigned long end = (unsigned long) mem_ptr + size;
00912     int column = 0;
00913 
00914     begin >>= 2;
00915     begin <<= 2;
00916 
00917     end >>= 2;
00918     end++;
00919     end <<= 2;
00920 
00921     PRINT_MSG("\nMemory region dumped: 0x%lx - 0x%lx\n\n", begin, end);
00922 
00923     column = 0;
00924     PRINT_MSG("0x%lx ", begin);
00925 
00926     while (begin < end) {
00927         if (((unsigned char *) begin)[0] == 0)
00928             PRINT_MSG("00");
00929         else
00930             PRINT_MSG("%02x", ((unsigned char *) begin)[0]);
00931         if (((unsigned char *) begin)[1] == 0)
00932             PRINT_MSG("00 ");
00933         else
00934             PRINT_MSG("%02x ", ((unsigned char *) begin)[1]);
00935         begin += 2;
00936         column++;
00937         if (column == 8) {
00938             PRINT_MSG("\n0x%lx ", begin);
00939             column = 0;
00940         }
00941 
00942     }
00943     PRINT_MSG("\n\n");
00944 }
00945 
00946 void print_block(bhdr_t * b)
00947 {
00948     if (!b)
00949         return;
00950     PRINT_MSG(">> [%p] (", b);
00951     if ((b->size & BLOCK_SIZE))
00952         PRINT_MSG("%lu bytes, ", (unsigned long) (b->size & BLOCK_SIZE));
00953     else
00954         PRINT_MSG("sentinel, ");
00955     if ((b->size & BLOCK_STATE) == FREE_BLOCK)
00956         PRINT_MSG("free [%p, %p], ", b->ptr.free_ptr.prev, b->ptr.free_ptr.next);
00957     else
00958         PRINT_MSG("used, ");
00959     if ((b->size & PREV_STATE) == PREV_FREE)
00960         PRINT_MSG("prev. free [%p])\n", b->prev_hdr);
00961     else
00962         PRINT_MSG("prev used)\n");
00963 }
00964 
00965 void print_tlsf(tlsf_t * tlsf)
00966 {
00967     bhdr_t *next;
00968     int i, j;
00969 
00970     PRINT_MSG("\nTLSF at %p\n", tlsf);
00971 
00972     PRINT_MSG("FL bitmap: 0x%x\n\n", (unsigned) tlsf->fl_bitmap);
00973 
00974     for (i = 0; i < REAL_FLI; i++) {
00975         if (tlsf->sl_bitmap[i])
00976             PRINT_MSG("SL bitmap 0x%x\n", (unsigned) tlsf->sl_bitmap[i]);
00977         for (j = 0; j < MAX_SLI; j++) {
00978             next = tlsf->matrix[i][j];
00979             if (next)
00980                 PRINT_MSG("-> [%d][%d]\n", i, j);
00981             while (next) {
00982                 print_block(next);
00983                 next = next->ptr.free_ptr.next;
00984             }
00985         }
00986     }
00987 }
00988 
00989 void print_all_blocks(tlsf_t * tlsf)
00990 {
00991     area_info_t *ai;
00992     bhdr_t *next;
00993     PRINT_MSG("\nTLSF at %p\nALL BLOCKS\n\n", tlsf);
00994     ai = tlsf->area_head;
00995     while (ai) {
00996         next = (bhdr_t *) ((char *) ai - BHDR_OVERHEAD);
00997         while (next) {
00998             print_block(next);
00999             if ((next->size & BLOCK_SIZE))
01000                 next = GET_NEXT_BLOCK(next->ptr.buffer, next->size & BLOCK_SIZE);
01001             else
01002                 next = NULL;
01003         }
01004         ai = ai->next;
01005     }
01006 }
01007 
01008 #endif


rtt
Author(s): RTT Developers
autogenerated on Mon Oct 6 2014 03:13:55