[453] | 1 | /*
|
---|
| 2 | * Two Levels Segregate Fit memory allocator (TLSF)
|
---|
| 3 | * Version 2.4.6
|
---|
| 4 | *
|
---|
| 5 | * Written by Miguel Masmano Tello <mimastel@doctor.upv.es>
|
---|
| 6 | *
|
---|
| 7 | * Thanks to Ismael Ripoll for his suggestions and reviews
|
---|
| 8 | *
|
---|
| 9 | * Copyright (C) 2008, 2007, 2006, 2005, 2004
|
---|
| 10 | *
|
---|
| 11 | * This code is released using a dual license strategy: GPL/LGPL
|
---|
| 12 | * You can choose the licence that better fits your requirements.
|
---|
| 13 | *
|
---|
| 14 | * Released under the terms of the GNU General Public License Version 2.0
|
---|
| 15 | * Released under the terms of the GNU Lesser General Public License Version 2.1
|
---|
| 16 | *
|
---|
| 17 | */
|
---|
| 18 |
|
---|
| 19 | /*
|
---|
| 20 | * Code contributions:
|
---|
| 21 | *
|
---|
| 22 | * (Jul 28 2007) Herman ten Brugge <hermantenbrugge@home.nl>:
|
---|
| 23 | *
|
---|
| 24 | * - Add 64 bit support. It now runs on x86_64 and solaris64.
|
---|
| 25 | * - I also tested this on vxworks/32and solaris/32 and i386/32 processors.
|
---|
| 26 | * - Remove assembly code. I could not measure any performance difference
|
---|
| 27 | * on my core2 processor. This also makes the code more portable.
|
---|
| 28 | * - Moved defines/typedefs from tlsf.h to tlsf.c
|
---|
| 29 | * - Changed MIN_BLOCK_SIZE to sizeof (free_ptr_t) and BHDR_OVERHEAD to
|
---|
| 30 | * (sizeof (bhdr_t) - MIN_BLOCK_SIZE). This does not change the fact
|
---|
| 31 | * that the minumum size is still sizeof
|
---|
| 32 | * (bhdr_t).
|
---|
| 33 | * - Changed all C++ comment style to C style. (// -> /.* ... *./)
|
---|
| 34 | * - Used ls_bit instead of ffs and ms_bit instead of fls. I did this to
|
---|
| 35 | * avoid confusion with the standard ffs function which returns
|
---|
| 36 | * different values.
|
---|
| 37 | * - Created set_bit/clear_bit fuctions because they are not present
|
---|
| 38 | * on x86_64.
|
---|
| 39 | * - Added locking support + extra file target.h to show how to use it.
|
---|
| 40 | * - Added get_used_size function (REMOVED in 2.4)
|
---|
| 41 | * - Added rtl_realloc and rtl_calloc function
|
---|
| 42 | * - Implemented realloc clever support.
|
---|
| 43 | * - Added some test code in the example directory.
|
---|
| 44 | * - Bug fixed (discovered by the rockbox project: www.rockbox.org).
|
---|
| 45 | *
|
---|
| 46 | * (Oct 23 2006) Adam Scislowicz:
|
---|
| 47 | *
|
---|
| 48 | * - Support for ARMv5 implemented
|
---|
| 49 | *
|
---|
| 50 | */
|
---|
| 51 |
|
---|
| 52 | /*#define USE_SBRK (0) */
|
---|
| 53 | /*#define USE_MMAP (0) */
|
---|
| 54 |
|
---|
| 55 | #ifndef USE_PRINTF
|
---|
| 56 | #define USE_PRINTF (1)
|
---|
| 57 | #endif
|
---|
| 58 |
|
---|
| 59 | #include <string.h>
|
---|
| 60 |
|
---|
| 61 | #ifndef TLSF_USE_LOCKS
|
---|
| 62 | #define TLSF_USE_LOCKS (0)
|
---|
| 63 | #endif
|
---|
| 64 |
|
---|
| 65 | #ifndef TLSF_STATISTIC
|
---|
| 66 | #define TLSF_STATISTIC (0)
|
---|
| 67 | #endif
|
---|
| 68 |
|
---|
| 69 | #ifndef USE_MMAP
|
---|
| 70 | #define USE_MMAP (0)
|
---|
| 71 | #endif
|
---|
| 72 |
|
---|
| 73 | #ifndef USE_SBRK
|
---|
| 74 | #define USE_SBRK (0)
|
---|
| 75 | #endif
|
---|
| 76 |
|
---|
| 77 |
|
---|
| 78 | #if TLSF_USE_LOCKS
|
---|
| 79 | #include "kernel.h"
|
---|
| 80 | #include "kernel_cfg.h"
|
---|
| 81 | #define TLSF_MLOCK_T ID
|
---|
| 82 | #define TLSF_CREATE_LOCK(lock) (*lock = TLSF_SEM)
|
---|
| 83 | #define TLSF_DESTROY_LOCK(lock) ini_sem(*lock)
|
---|
| 84 | #define TLSF_ACQUIRE_LOCK(lock) wai_sem(*lock)
|
---|
| 85 | #define TLSF_RELEASE_LOCK(lock) sig_sem(*lock)
|
---|
| 86 | #else
|
---|
| 87 | #define TLSF_CREATE_LOCK(_unused_) do{}while(0)
|
---|
| 88 | #define TLSF_DESTROY_LOCK(_unused_) do{}while(0)
|
---|
| 89 | #define TLSF_ACQUIRE_LOCK(_unused_) do{}while(0)
|
---|
| 90 | #define TLSF_RELEASE_LOCK(_unused_) do{}while(0)
|
---|
| 91 | #endif
|
---|
| 92 |
|
---|
| 93 | #if TLSF_STATISTIC
|
---|
| 94 | #define TLSF_ADD_SIZE(tlsf, b) do { \
|
---|
| 95 | tlsf->used_size += (b->size & BLOCK_SIZE) + BHDR_OVERHEAD; \
|
---|
| 96 | if (tlsf->used_size > tlsf->max_size) \
|
---|
| 97 | tlsf->max_size = tlsf->used_size; \
|
---|
| 98 | } while(0)
|
---|
| 99 |
|
---|
| 100 | #define TLSF_REMOVE_SIZE(tlsf, b) do { \
|
---|
| 101 | tlsf->used_size -= (b->size & BLOCK_SIZE) + BHDR_OVERHEAD; \
|
---|
| 102 | } while(0)
|
---|
| 103 | #else
|
---|
| 104 | #define TLSF_ADD_SIZE(tlsf, b) do{}while(0)
|
---|
| 105 | #define TLSF_REMOVE_SIZE(tlsf, b) do{}while(0)
|
---|
| 106 | #endif
|
---|
| 107 |
|
---|
| 108 | #if USE_MMAP || USE_SBRK
|
---|
| 109 | #include <unistd.h>
|
---|
| 110 | #endif
|
---|
| 111 |
|
---|
| 112 | #if USE_MMAP
|
---|
| 113 | #include <sys/mman.h>
|
---|
| 114 | #endif
|
---|
| 115 |
|
---|
| 116 | #include "tlsf.h"
|
---|
| 117 |
|
---|
| 118 | #if !defined(__GNUC__)
|
---|
| 119 | #ifndef __inline__
|
---|
| 120 | #define __inline__
|
---|
| 121 | #endif
|
---|
| 122 | #endif
|
---|
| 123 |
|
---|
| 124 | /* The debug functions only can be used when _DEBUG_TLSF_ is set. */
|
---|
| 125 | #ifndef _DEBUG_TLSF_
|
---|
| 126 | #define _DEBUG_TLSF_ (0)
|
---|
| 127 | #endif
|
---|
| 128 |
|
---|
| 129 | /*************************************************************************/
|
---|
| 130 | /* Definition of the structures used by TLSF */
|
---|
| 131 |
|
---|
| 132 |
|
---|
| 133 | /* Some IMPORTANT TLSF parameters */
|
---|
| 134 | /* Unlike the preview TLSF versions, now they are statics */
|
---|
| 135 | #define BLOCK_ALIGN (sizeof(void *) * 2)
|
---|
| 136 |
|
---|
| 137 | #define MAX_FLI (30)
|
---|
| 138 | #define MAX_LOG2_SLI (5)
|
---|
| 139 | #define MAX_SLI (1 << MAX_LOG2_SLI) /* MAX_SLI = 2^MAX_LOG2_SLI */
|
---|
| 140 |
|
---|
| 141 | #define FLI_OFFSET (6) /* tlsf structure just will manage blocks bigger */
|
---|
| 142 | /* than 128 bytes */
|
---|
| 143 | #define SMALL_BLOCK (128)
|
---|
| 144 | #define REAL_FLI (MAX_FLI - FLI_OFFSET)
|
---|
| 145 | #define MIN_BLOCK_SIZE (sizeof (free_ptr_t))
|
---|
| 146 | #define BHDR_OVERHEAD (sizeof (bhdr_t) - MIN_BLOCK_SIZE)
|
---|
| 147 | #define TLSF_SIGNATURE (0x2A59FA59)
|
---|
| 148 |
|
---|
| 149 | #define PTR_MASK (sizeof(void *) - 1)
|
---|
| 150 | #define BLOCK_SIZE (0xFFFFFFFF - PTR_MASK)
|
---|
| 151 |
|
---|
| 152 | #define GET_NEXT_BLOCK(_addr, _r) ((bhdr_t *) ((char *) (_addr) + (_r)))
|
---|
| 153 | #define MEM_ALIGN ((BLOCK_ALIGN) - 1)
|
---|
| 154 | #define ROUNDUP_SIZE(_r) (((_r) + MEM_ALIGN) & ~MEM_ALIGN)
|
---|
| 155 | #define ROUNDDOWN_SIZE(_r) ((_r) & ~MEM_ALIGN)
|
---|
| 156 | #define ROUNDUP(_x, _v) ((((~(_x)) + 1) & ((_v)-1)) + (_x))
|
---|
| 157 |
|
---|
| 158 | #define BLOCK_STATE (0x1)
|
---|
| 159 | #define PREV_STATE (0x2)
|
---|
| 160 |
|
---|
| 161 | /* bit 0 of the block size */
|
---|
| 162 | #define FREE_BLOCK (0x1)
|
---|
| 163 | #define USED_BLOCK (0x0)
|
---|
| 164 |
|
---|
| 165 | /* bit 1 of the block size */
|
---|
| 166 | #define PREV_FREE (0x2)
|
---|
| 167 | #define PREV_USED (0x0)
|
---|
| 168 |
|
---|
| 169 |
|
---|
| 170 | #define DEFAULT_AREA_SIZE (1024*10)
|
---|
| 171 |
|
---|
| 172 | #ifdef USE_MMAP
|
---|
| 173 | #define PAGE_SIZE (getpagesize())
|
---|
| 174 | #endif
|
---|
| 175 |
|
---|
| 176 | #ifdef USE_PRINTF
|
---|
| 177 | #include <stdio.h>
|
---|
| 178 | #include <t_stddef.h>
|
---|
| 179 | #include <t_syslog.h>
|
---|
| 180 | #define PRINT_MSG(fmt, args...) syslog(LOG_ERROR, fmt, ## args)
|
---|
| 181 | #define ERROR_MSG(fmt, args...) syslog(LOG_ERROR, fmt, ## args)
|
---|
| 182 | #else
|
---|
| 183 | # if !defined(PRINT_MSG)
|
---|
| 184 | # define PRINT_MSG(fmt, args...)
|
---|
| 185 | # endif
|
---|
| 186 | # if !defined(ERROR_MSG)
|
---|
| 187 | # define ERROR_MSG(fmt, args...)
|
---|
| 188 | # endif
|
---|
| 189 | #endif
|
---|
| 190 |
|
---|
| 191 | typedef unsigned int u32_t; /* NOTE: Make sure that this type is 4 bytes long on your computer */
|
---|
| 192 | typedef unsigned char u8_t; /* NOTE: Make sure that this type is 1 byte on your computer */
|
---|
| 193 |
|
---|
| 194 | typedef struct free_ptr_struct {
|
---|
| 195 | struct bhdr_struct *prev;
|
---|
| 196 | struct bhdr_struct *next;
|
---|
| 197 | } free_ptr_t;
|
---|
| 198 |
|
---|
| 199 | typedef struct bhdr_struct {
|
---|
| 200 | /* This pointer is just valid if the first bit of size is set */
|
---|
| 201 | struct bhdr_struct *prev_hdr;
|
---|
| 202 | /* The size is stored in bytes */
|
---|
| 203 | size_t size; /* bit 0 indicates whether the block is used and */
|
---|
| 204 | /* bit 1 allows to know whether the previous block is free */
|
---|
| 205 | union {
|
---|
| 206 | struct free_ptr_struct free_ptr;
|
---|
| 207 | u8_t buffer[1]; /*sizeof(struct free_ptr_struct)]; */
|
---|
| 208 | } ptr;
|
---|
| 209 | } bhdr_t;
|
---|
| 210 |
|
---|
| 211 | /* This structure is embedded at the beginning of each area, giving us
|
---|
| 212 | * enough information to cope with a set of areas */
|
---|
| 213 |
|
---|
| 214 | typedef struct area_info_struct {
|
---|
| 215 | bhdr_t *end;
|
---|
| 216 | struct area_info_struct *next;
|
---|
| 217 | } area_info_t;
|
---|
| 218 |
|
---|
| 219 | typedef struct TLSF_struct {
|
---|
| 220 | /* the TLSF's structure signature */
|
---|
| 221 | u32_t tlsf_signature;
|
---|
| 222 |
|
---|
| 223 | #if TLSF_USE_LOCKS
|
---|
| 224 | TLSF_MLOCK_T lock;
|
---|
| 225 | #endif
|
---|
| 226 |
|
---|
| 227 | #if TLSF_STATISTIC
|
---|
| 228 | /* These can not be calculated outside tlsf because we
|
---|
| 229 | * do not know the sizes when freeing/reallocing memory. */
|
---|
| 230 | size_t used_size;
|
---|
| 231 | size_t max_size;
|
---|
| 232 | #endif
|
---|
| 233 |
|
---|
| 234 | /* A linked list holding all the existing areas */
|
---|
| 235 | area_info_t *area_head;
|
---|
| 236 |
|
---|
| 237 | /* the first-level bitmap */
|
---|
| 238 | /* This array should have a size of REAL_FLI bits */
|
---|
| 239 | u32_t fl_bitmap;
|
---|
| 240 |
|
---|
| 241 | /* the second-level bitmap */
|
---|
| 242 | u32_t sl_bitmap[REAL_FLI];
|
---|
| 243 |
|
---|
| 244 | bhdr_t *matrix[REAL_FLI][MAX_SLI];
|
---|
| 245 | } tlsf_t;
|
---|
| 246 |
|
---|
| 247 |
|
---|
| 248 | /******************************************************************/
|
---|
| 249 | /************** Helping functions **************************/
|
---|
| 250 | /******************************************************************/
|
---|
| 251 | static __inline__ void set_bit(int nr, u32_t * addr);
|
---|
| 252 | static __inline__ void clear_bit(int nr, u32_t * addr);
|
---|
| 253 | static __inline__ int ls_bit(int x);
|
---|
| 254 | static __inline__ int ms_bit(int x);
|
---|
| 255 | static __inline__ void MAPPING_SEARCH(size_t * _r, int *_fl, int *_sl);
|
---|
| 256 | static __inline__ void MAPPING_INSERT(size_t _r, int *_fl, int *_sl);
|
---|
| 257 | static __inline__ bhdr_t *FIND_SUITABLE_BLOCK(tlsf_t * _tlsf, int *_fl, int *_sl);
|
---|
| 258 | static __inline__ bhdr_t *process_area(void *area, size_t size);
|
---|
| 259 | #if USE_SBRK || USE_MMAP
|
---|
| 260 | static __inline__ void *get_new_area(size_t * size);
|
---|
| 261 | #endif
|
---|
| 262 |
|
---|
| 263 | static const int table[] = {
|
---|
| 264 | -1, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4,
|
---|
| 265 | 4, 4,
|
---|
| 266 | 4, 4, 4, 4, 4, 4, 4,
|
---|
| 267 | 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
|
---|
| 268 | 5,
|
---|
| 269 | 5, 5, 5, 5, 5, 5, 5,
|
---|
| 270 | 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
|
---|
| 271 | 6,
|
---|
| 272 | 6, 6, 6, 6, 6, 6, 6,
|
---|
| 273 | 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
|
---|
| 274 | 6,
|
---|
| 275 | 6, 6, 6, 6, 6, 6, 6,
|
---|
| 276 | 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
|
---|
| 277 | 7,
|
---|
| 278 | 7, 7, 7, 7, 7, 7, 7,
|
---|
| 279 | 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
|
---|
| 280 | 7,
|
---|
| 281 | 7, 7, 7, 7, 7, 7, 7,
|
---|
| 282 | 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
|
---|
| 283 | 7,
|
---|
| 284 | 7, 7, 7, 7, 7, 7, 7,
|
---|
| 285 | 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
|
---|
| 286 | 7,
|
---|
| 287 | 7, 7, 7, 7, 7, 7, 7
|
---|
| 288 | };
|
---|
| 289 |
|
---|
| 290 | static __inline__ int ls_bit(int i)
|
---|
| 291 | {
|
---|
| 292 | unsigned int a;
|
---|
| 293 | unsigned int x = i & -i;
|
---|
| 294 |
|
---|
| 295 | a = x <= 0xffff ? (x <= 0xff ? 0 : 8) : (x <= 0xffffff ? 16 : 24);
|
---|
| 296 | return table[x >> a] + a;
|
---|
| 297 | }
|
---|
| 298 |
|
---|
| 299 | static __inline__ int ms_bit(int i)
|
---|
| 300 | {
|
---|
| 301 | unsigned int a;
|
---|
| 302 | unsigned int x = (unsigned int) i;
|
---|
| 303 |
|
---|
| 304 | a = x <= 0xffff ? (x <= 0xff ? 0 : 8) : (x <= 0xffffff ? 16 : 24);
|
---|
| 305 | return table[x >> a] + a;
|
---|
| 306 | }
|
---|
| 307 |
|
---|
| 308 | static __inline__ void set_bit(int nr, u32_t * addr)
|
---|
| 309 | {
|
---|
| 310 | addr[nr >> 5] |= 1 << (nr & 0x1f);
|
---|
| 311 | }
|
---|
| 312 |
|
---|
| 313 | static __inline__ void clear_bit(int nr, u32_t * addr)
|
---|
| 314 | {
|
---|
| 315 | addr[nr >> 5] &= ~(1 << (nr & 0x1f));
|
---|
| 316 | }
|
---|
| 317 |
|
---|
| 318 | static __inline__ void MAPPING_SEARCH(size_t * _r, int *_fl, int *_sl)
|
---|
| 319 | {
|
---|
| 320 | int _t;
|
---|
| 321 |
|
---|
| 322 | if (*_r < SMALL_BLOCK) {
|
---|
| 323 | *_fl = 0;
|
---|
| 324 | *_sl = *_r / (SMALL_BLOCK / MAX_SLI);
|
---|
| 325 | } else {
|
---|
| 326 | _t = (1 << (ms_bit(*_r) - MAX_LOG2_SLI)) - 1;
|
---|
| 327 | *_r = *_r + _t;
|
---|
| 328 | *_fl = ms_bit(*_r);
|
---|
| 329 | *_sl = (*_r >> (*_fl - MAX_LOG2_SLI)) - MAX_SLI;
|
---|
| 330 | *_fl -= FLI_OFFSET;
|
---|
| 331 | /*if ((*_fl -= FLI_OFFSET) < 0) // FL wil be always >0!
|
---|
| 332 | *_fl = *_sl = 0;
|
---|
| 333 | */
|
---|
| 334 | *_r &= ~_t;
|
---|
| 335 | }
|
---|
| 336 | }
|
---|
| 337 |
|
---|
| 338 | static __inline__ void MAPPING_INSERT(size_t _r, int *_fl, int *_sl)
|
---|
| 339 | {
|
---|
| 340 | if (_r < SMALL_BLOCK) {
|
---|
| 341 | *_fl = 0;
|
---|
| 342 | *_sl = _r / (SMALL_BLOCK / MAX_SLI);
|
---|
| 343 | } else {
|
---|
| 344 | *_fl = ms_bit(_r);
|
---|
| 345 | *_sl = (_r >> (*_fl - MAX_LOG2_SLI)) - MAX_SLI;
|
---|
| 346 | *_fl -= FLI_OFFSET;
|
---|
| 347 | }
|
---|
| 348 | }
|
---|
| 349 |
|
---|
| 350 |
|
---|
| 351 | static __inline__ bhdr_t *FIND_SUITABLE_BLOCK(tlsf_t * _tlsf, int *_fl, int *_sl)
|
---|
| 352 | {
|
---|
| 353 | u32_t _tmp = _tlsf->sl_bitmap[*_fl] & (~0 << *_sl);
|
---|
| 354 | bhdr_t *_b = NULL;
|
---|
| 355 |
|
---|
| 356 | if (_tmp) {
|
---|
| 357 | *_sl = ls_bit(_tmp);
|
---|
| 358 | _b = _tlsf->matrix[*_fl][*_sl];
|
---|
| 359 | } else {
|
---|
| 360 | *_fl = ls_bit(_tlsf->fl_bitmap & (~0 << (*_fl + 1)));
|
---|
| 361 | if (*_fl > 0) { /* likely */
|
---|
| 362 | *_sl = ls_bit(_tlsf->sl_bitmap[*_fl]);
|
---|
| 363 | _b = _tlsf->matrix[*_fl][*_sl];
|
---|
| 364 | }
|
---|
| 365 | }
|
---|
| 366 | return _b;
|
---|
| 367 | }
|
---|
| 368 |
|
---|
| 369 |
|
---|
| 370 | #define EXTRACT_BLOCK_HDR(_b, _tlsf, _fl, _sl) do { \
|
---|
| 371 | _tlsf -> matrix [_fl] [_sl] = _b -> ptr.free_ptr.next; \
|
---|
| 372 | if (_tlsf -> matrix[_fl][_sl]) \
|
---|
| 373 | _tlsf -> matrix[_fl][_sl] -> ptr.free_ptr.prev = NULL; \
|
---|
| 374 | else { \
|
---|
| 375 | clear_bit (_sl, &_tlsf -> sl_bitmap [_fl]); \
|
---|
| 376 | if (!_tlsf -> sl_bitmap [_fl]) \
|
---|
| 377 | clear_bit (_fl, &_tlsf -> fl_bitmap); \
|
---|
| 378 | } \
|
---|
| 379 | _b -> ptr.free_ptr.prev = NULL; \
|
---|
| 380 | _b -> ptr.free_ptr.next = NULL; \
|
---|
| 381 | }while(0)
|
---|
| 382 |
|
---|
| 383 |
|
---|
| 384 | #define EXTRACT_BLOCK(_b, _tlsf, _fl, _sl) do { \
|
---|
| 385 | if (_b -> ptr.free_ptr.next) \
|
---|
| 386 | _b -> ptr.free_ptr.next -> ptr.free_ptr.prev = _b -> ptr.free_ptr.prev; \
|
---|
| 387 | if (_b -> ptr.free_ptr.prev) \
|
---|
| 388 | _b -> ptr.free_ptr.prev -> ptr.free_ptr.next = _b -> ptr.free_ptr.next; \
|
---|
| 389 | if (_tlsf -> matrix [_fl][_sl] == _b) { \
|
---|
| 390 | _tlsf -> matrix [_fl][_sl] = _b -> ptr.free_ptr.next; \
|
---|
| 391 | if (!_tlsf -> matrix [_fl][_sl]) { \
|
---|
| 392 | clear_bit (_sl, &_tlsf -> sl_bitmap[_fl]); \
|
---|
| 393 | if (!_tlsf -> sl_bitmap [_fl]) \
|
---|
| 394 | clear_bit (_fl, &_tlsf -> fl_bitmap); \
|
---|
| 395 | } \
|
---|
| 396 | } \
|
---|
| 397 | _b -> ptr.free_ptr.prev = NULL; \
|
---|
| 398 | _b -> ptr.free_ptr.next = NULL; \
|
---|
| 399 | } while(0)
|
---|
| 400 |
|
---|
| 401 | #define INSERT_BLOCK(_b, _tlsf, _fl, _sl) do { \
|
---|
| 402 | _b -> ptr.free_ptr.prev = NULL; \
|
---|
| 403 | _b -> ptr.free_ptr.next = _tlsf -> matrix [_fl][_sl]; \
|
---|
| 404 | if (_tlsf -> matrix [_fl][_sl]) \
|
---|
| 405 | _tlsf -> matrix [_fl][_sl] -> ptr.free_ptr.prev = _b; \
|
---|
| 406 | _tlsf -> matrix [_fl][_sl] = _b; \
|
---|
| 407 | set_bit (_sl, &_tlsf -> sl_bitmap [_fl]); \
|
---|
| 408 | set_bit (_fl, &_tlsf -> fl_bitmap); \
|
---|
| 409 | } while(0)
|
---|
| 410 |
|
---|
| 411 | #if USE_SBRK || USE_MMAP
|
---|
| 412 | static __inline__ void *get_new_area(size_t * size)
|
---|
| 413 | {
|
---|
| 414 | void *area;
|
---|
| 415 |
|
---|
| 416 | #if USE_SBRK
|
---|
| 417 | area = (void *)sbrk(0);
|
---|
| 418 | if (((void *)sbrk(*size)) != ((void *) -1))
|
---|
| 419 | return area;
|
---|
| 420 | #endif
|
---|
| 421 |
|
---|
| 422 | #ifndef MAP_ANONYMOUS
|
---|
| 423 | /* https://dev.openwrt.org/ticket/322 */
|
---|
| 424 | # define MAP_ANONYMOUS MAP_ANON
|
---|
| 425 | #endif
|
---|
| 426 |
|
---|
| 427 |
|
---|
| 428 | #if USE_MMAP
|
---|
| 429 | *size = ROUNDUP(*size, PAGE_SIZE);
|
---|
| 430 | if ((area = mmap(0, *size, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0)) != MAP_FAILED)
|
---|
| 431 | return area;
|
---|
| 432 | #endif
|
---|
| 433 | return ((void *) ~0);
|
---|
| 434 | }
|
---|
| 435 | #endif
|
---|
| 436 |
|
---|
| 437 | static __inline__ bhdr_t *process_area(void *area, size_t size)
|
---|
| 438 | {
|
---|
| 439 | bhdr_t *b, *lb, *ib;
|
---|
| 440 | area_info_t *ai;
|
---|
| 441 |
|
---|
| 442 | ib = (bhdr_t *) area;
|
---|
| 443 | ib->size =
|
---|
| 444 | (sizeof(area_info_t) <
|
---|
| 445 | MIN_BLOCK_SIZE) ? MIN_BLOCK_SIZE : ROUNDUP_SIZE(sizeof(area_info_t)) | USED_BLOCK | PREV_USED;
|
---|
| 446 | b = (bhdr_t *) GET_NEXT_BLOCK(ib->ptr.buffer, ib->size & BLOCK_SIZE);
|
---|
| 447 | b->size = ROUNDDOWN_SIZE(size - 3 * BHDR_OVERHEAD - (ib->size & BLOCK_SIZE)) | USED_BLOCK | PREV_USED;
|
---|
| 448 | b->ptr.free_ptr.prev = b->ptr.free_ptr.next = 0;
|
---|
| 449 | lb = GET_NEXT_BLOCK(b->ptr.buffer, b->size & BLOCK_SIZE);
|
---|
| 450 | lb->prev_hdr = b;
|
---|
| 451 | lb->size = 0 | USED_BLOCK | PREV_FREE;
|
---|
| 452 | ai = (area_info_t *) ib->ptr.buffer;
|
---|
| 453 | ai->next = 0;
|
---|
| 454 | ai->end = lb;
|
---|
| 455 | return ib;
|
---|
| 456 | }
|
---|
| 457 |
|
---|
| 458 | /******************************************************************/
|
---|
| 459 | /******************** Begin of the allocator code *****************/
|
---|
| 460 | /******************************************************************/
|
---|
| 461 |
|
---|
| 462 | static char *mp = NULL; /* Default memory pool. */
|
---|
| 463 |
|
---|
| 464 | /******************************************************************/
|
---|
| 465 | size_t init_memory_pool(size_t mem_pool_size, void *mem_pool)
|
---|
| 466 | {
|
---|
| 467 | /******************************************************************/
|
---|
| 468 | tlsf_t *tlsf;
|
---|
| 469 | bhdr_t *b, *ib;
|
---|
| 470 |
|
---|
| 471 | if (!mem_pool || !mem_pool_size || mem_pool_size < sizeof(tlsf_t) + BHDR_OVERHEAD * 8) {
|
---|
| 472 | ERROR_MSG("init_memory_pool (): memory_pool invalid\n");
|
---|
| 473 | return -1;
|
---|
| 474 | }
|
---|
| 475 |
|
---|
| 476 | if (((unsigned long) mem_pool & PTR_MASK)) {
|
---|
| 477 | ERROR_MSG("init_memory_pool (): mem_pool must be aligned to a word\n");
|
---|
| 478 | return -1;
|
---|
| 479 | }
|
---|
| 480 | tlsf = (tlsf_t *) mem_pool;
|
---|
| 481 | /* Check if already initialised */
|
---|
| 482 | if (tlsf->tlsf_signature == TLSF_SIGNATURE) {
|
---|
| 483 | mp = mem_pool;
|
---|
| 484 | b = GET_NEXT_BLOCK(mp, ROUNDUP_SIZE(sizeof(tlsf_t)));
|
---|
| 485 | return b->size & BLOCK_SIZE;
|
---|
| 486 | }
|
---|
| 487 |
|
---|
| 488 | mp = mem_pool;
|
---|
| 489 |
|
---|
| 490 | /* Zeroing the memory pool */
|
---|
| 491 | memset(mem_pool, 0, sizeof(tlsf_t));
|
---|
| 492 |
|
---|
| 493 | tlsf->tlsf_signature = TLSF_SIGNATURE;
|
---|
| 494 |
|
---|
| 495 | TLSF_CREATE_LOCK(&tlsf->lock);
|
---|
| 496 |
|
---|
| 497 | ib = process_area(GET_NEXT_BLOCK
|
---|
| 498 | (mem_pool, ROUNDUP_SIZE(sizeof(tlsf_t))), ROUNDDOWN_SIZE(mem_pool_size - sizeof(tlsf_t)));
|
---|
| 499 | b = GET_NEXT_BLOCK(ib->ptr.buffer, ib->size & BLOCK_SIZE);
|
---|
| 500 | free_ex(b->ptr.buffer, tlsf);
|
---|
| 501 | tlsf->area_head = (area_info_t *) ib->ptr.buffer;
|
---|
| 502 |
|
---|
| 503 | #if TLSF_STATISTIC
|
---|
| 504 | tlsf->used_size = mem_pool_size - (b->size & BLOCK_SIZE);
|
---|
| 505 | tlsf->max_size = tlsf->used_size;
|
---|
| 506 | #endif
|
---|
| 507 |
|
---|
| 508 | return (b->size & BLOCK_SIZE);
|
---|
| 509 | }
|
---|
| 510 |
|
---|
| 511 | /******************************************************************/
|
---|
| 512 | size_t add_new_area(void *area, size_t area_size, void *mem_pool)
|
---|
| 513 | {
|
---|
| 514 | /******************************************************************/
|
---|
| 515 | tlsf_t *tlsf = (tlsf_t *) mem_pool;
|
---|
| 516 | area_info_t *ptr, *ptr_prev, *ai;
|
---|
| 517 | bhdr_t *ib0, *b0, *lb0, *ib1, *b1, *lb1, *next_b;
|
---|
| 518 |
|
---|
| 519 | memset(area, 0, area_size);
|
---|
| 520 | ptr = tlsf->area_head;
|
---|
| 521 | ptr_prev = 0;
|
---|
| 522 |
|
---|
| 523 | ib0 = process_area(area, area_size);
|
---|
| 524 | b0 = GET_NEXT_BLOCK(ib0->ptr.buffer, ib0->size & BLOCK_SIZE);
|
---|
| 525 | lb0 = GET_NEXT_BLOCK(b0->ptr.buffer, b0->size & BLOCK_SIZE);
|
---|
| 526 |
|
---|
| 527 | /* Before inserting the new area, we have to merge this area with the
|
---|
| 528 | already existing ones */
|
---|
| 529 |
|
---|
| 530 | while (ptr) {
|
---|
| 531 | ib1 = (bhdr_t *) ((char *) ptr - BHDR_OVERHEAD);
|
---|
| 532 | b1 = GET_NEXT_BLOCK(ib1->ptr.buffer, ib1->size & BLOCK_SIZE);
|
---|
| 533 | lb1 = ptr->end;
|
---|
| 534 |
|
---|
| 535 | /* Merging the new area with the next physically contigous one */
|
---|
| 536 | if ((unsigned long) ib1 == (unsigned long) lb0 + BHDR_OVERHEAD) {
|
---|
| 537 | if (tlsf->area_head == ptr) {
|
---|
| 538 | tlsf->area_head = ptr->next;
|
---|
| 539 | ptr = ptr->next;
|
---|
| 540 | } else {
|
---|
| 541 | ptr_prev->next = ptr->next;
|
---|
| 542 | ptr = ptr->next;
|
---|
| 543 | }
|
---|
| 544 |
|
---|
| 545 | b0->size =
|
---|
| 546 | ROUNDDOWN_SIZE((b0->size & BLOCK_SIZE) +
|
---|
| 547 | (ib1->size & BLOCK_SIZE) + 2 * BHDR_OVERHEAD) | USED_BLOCK | PREV_USED;
|
---|
| 548 |
|
---|
| 549 | b1->prev_hdr = b0;
|
---|
| 550 | lb0 = lb1;
|
---|
| 551 |
|
---|
| 552 | continue;
|
---|
| 553 | }
|
---|
| 554 |
|
---|
| 555 | /* Merging the new area with the previous physically contigous
|
---|
| 556 | one */
|
---|
| 557 | if ((unsigned long) lb1->ptr.buffer == (unsigned long) ib0) {
|
---|
| 558 | if (tlsf->area_head == ptr) {
|
---|
| 559 | tlsf->area_head = ptr->next;
|
---|
| 560 | ptr = ptr->next;
|
---|
| 561 | } else {
|
---|
| 562 | ptr_prev->next = ptr->next;
|
---|
| 563 | ptr = ptr->next;
|
---|
| 564 | }
|
---|
| 565 |
|
---|
| 566 | lb1->size =
|
---|
| 567 | ROUNDDOWN_SIZE((b0->size & BLOCK_SIZE) +
|
---|
| 568 | (ib0->size & BLOCK_SIZE) + 2 * BHDR_OVERHEAD) | USED_BLOCK | (lb1->size & PREV_STATE);
|
---|
| 569 | next_b = GET_NEXT_BLOCK(lb1->ptr.buffer, lb1->size & BLOCK_SIZE);
|
---|
| 570 | next_b->prev_hdr = lb1;
|
---|
| 571 | b0 = lb1;
|
---|
| 572 | ib0 = ib1;
|
---|
| 573 |
|
---|
| 574 | continue;
|
---|
| 575 | }
|
---|
| 576 | ptr_prev = ptr;
|
---|
| 577 | ptr = ptr->next;
|
---|
| 578 | }
|
---|
| 579 |
|
---|
| 580 | /* Inserting the area in the list of linked areas */
|
---|
| 581 | ai = (area_info_t *) ib0->ptr.buffer;
|
---|
| 582 | ai->next = tlsf->area_head;
|
---|
| 583 | ai->end = lb0;
|
---|
| 584 | tlsf->area_head = ai;
|
---|
| 585 | free_ex(b0->ptr.buffer, mem_pool);
|
---|
| 586 | return (b0->size & BLOCK_SIZE);
|
---|
| 587 | }
|
---|
| 588 |
|
---|
| 589 |
|
---|
| 590 | /******************************************************************/
|
---|
| 591 | size_t get_used_size(void *mem_pool)
|
---|
| 592 | {
|
---|
| 593 | /******************************************************************/
|
---|
| 594 | #if TLSF_STATISTIC
|
---|
| 595 | return ((tlsf_t *) mem_pool)->used_size;
|
---|
| 596 | #else
|
---|
| 597 | return 0;
|
---|
| 598 | #endif
|
---|
| 599 | }
|
---|
| 600 |
|
---|
| 601 | /******************************************************************/
|
---|
| 602 | size_t get_max_size(void *mem_pool)
|
---|
| 603 | {
|
---|
| 604 | /******************************************************************/
|
---|
| 605 | #if TLSF_STATISTIC
|
---|
| 606 | return ((tlsf_t *) mem_pool)->max_size;
|
---|
| 607 | #else
|
---|
| 608 | return 0;
|
---|
| 609 | #endif
|
---|
| 610 | }
|
---|
| 611 |
|
---|
| 612 | /******************************************************************/
|
---|
| 613 | void destroy_memory_pool(void *mem_pool)
|
---|
| 614 | {
|
---|
| 615 | /******************************************************************/
|
---|
| 616 | tlsf_t *tlsf = (tlsf_t *) mem_pool;
|
---|
| 617 |
|
---|
| 618 | tlsf->tlsf_signature = 0;
|
---|
| 619 |
|
---|
| 620 | TLSF_DESTROY_LOCK(&tlsf->lock);
|
---|
| 621 |
|
---|
| 622 | }
|
---|
| 623 |
|
---|
| 624 |
|
---|
| 625 | /******************************************************************/
|
---|
| 626 | void *tlsf_malloc(size_t size)
|
---|
| 627 | {
|
---|
| 628 | /******************************************************************/
|
---|
| 629 | void *ret;
|
---|
| 630 |
|
---|
| 631 | #if USE_MMAP || USE_SBRK
|
---|
| 632 | if (!mp) {
|
---|
| 633 | size_t area_size;
|
---|
| 634 | void *area;
|
---|
| 635 |
|
---|
| 636 | area_size = sizeof(tlsf_t) + BHDR_OVERHEAD * 8; /* Just a safety constant */
|
---|
| 637 | area_size = (area_size > DEFAULT_AREA_SIZE) ? area_size : DEFAULT_AREA_SIZE;
|
---|
| 638 | area = get_new_area(&area_size);
|
---|
| 639 | if (area == ((void *) ~0))
|
---|
| 640 | return NULL; /* Not enough system memory */
|
---|
| 641 | init_memory_pool(area_size, area);
|
---|
| 642 | }
|
---|
| 643 | #endif
|
---|
| 644 |
|
---|
| 645 | TLSF_ACQUIRE_LOCK(&((tlsf_t *)mp)->lock);
|
---|
| 646 |
|
---|
| 647 | ret = malloc_ex(size, mp);
|
---|
| 648 |
|
---|
| 649 | TLSF_RELEASE_LOCK(&((tlsf_t *)mp)->lock);
|
---|
| 650 |
|
---|
| 651 | return ret;
|
---|
| 652 | }
|
---|
| 653 |
|
---|
| 654 | /******************************************************************/
|
---|
| 655 | void tlsf_free(void *ptr)
|
---|
| 656 | {
|
---|
| 657 | /******************************************************************/
|
---|
| 658 |
|
---|
| 659 | TLSF_ACQUIRE_LOCK(&((tlsf_t *)mp)->lock);
|
---|
| 660 |
|
---|
| 661 | free_ex(ptr, mp);
|
---|
| 662 |
|
---|
| 663 | TLSF_RELEASE_LOCK(&((tlsf_t *)mp)->lock);
|
---|
| 664 |
|
---|
| 665 | }
|
---|
| 666 |
|
---|
| 667 | /******************************************************************/
|
---|
| 668 | void *tlsf_realloc(void *ptr, size_t size)
|
---|
| 669 | {
|
---|
| 670 | /******************************************************************/
|
---|
| 671 | void *ret;
|
---|
| 672 |
|
---|
| 673 | #if USE_MMAP || USE_SBRK
|
---|
| 674 | if (!mp) {
|
---|
| 675 | return tlsf_malloc(size);
|
---|
| 676 | }
|
---|
| 677 | #endif
|
---|
| 678 |
|
---|
| 679 | TLSF_ACQUIRE_LOCK(&((tlsf_t *)mp)->lock);
|
---|
| 680 |
|
---|
| 681 | ret = realloc_ex(ptr, size, mp);
|
---|
| 682 |
|
---|
| 683 | TLSF_RELEASE_LOCK(&((tlsf_t *)mp)->lock);
|
---|
| 684 |
|
---|
| 685 | return ret;
|
---|
| 686 | }
|
---|
| 687 |
|
---|
| 688 | /******************************************************************/
|
---|
| 689 | void *tlsf_calloc(size_t nelem, size_t elem_size)
|
---|
| 690 | {
|
---|
| 691 | /******************************************************************/
|
---|
| 692 | void *ret;
|
---|
| 693 |
|
---|
| 694 | TLSF_ACQUIRE_LOCK(&((tlsf_t *)mp)->lock);
|
---|
| 695 |
|
---|
| 696 | ret = calloc_ex(nelem, elem_size, mp);
|
---|
| 697 |
|
---|
| 698 | TLSF_RELEASE_LOCK(&((tlsf_t *)mp)->lock);
|
---|
| 699 |
|
---|
| 700 | return ret;
|
---|
| 701 | }
|
---|
| 702 |
|
---|
| 703 | /******************************************************************/
|
---|
| 704 | void *malloc_ex(size_t size, void *mem_pool)
|
---|
| 705 | {
|
---|
| 706 | /******************************************************************/
|
---|
| 707 | tlsf_t *tlsf = (tlsf_t *) mem_pool;
|
---|
| 708 | bhdr_t *b, *b2, *next_b;
|
---|
| 709 | int fl, sl;
|
---|
| 710 | size_t tmp_size;
|
---|
| 711 |
|
---|
| 712 | size = (size < MIN_BLOCK_SIZE) ? MIN_BLOCK_SIZE : ROUNDUP_SIZE(size);
|
---|
| 713 |
|
---|
| 714 | /* Rounding up the requested size and calculating fl and sl */
|
---|
| 715 | MAPPING_SEARCH(&size, &fl, &sl);
|
---|
| 716 |
|
---|
| 717 | /* Searching a free block, recall that this function changes the values of fl and sl,
|
---|
| 718 | so they are not longer valid when the function fails */
|
---|
| 719 | b = FIND_SUITABLE_BLOCK(tlsf, &fl, &sl);
|
---|
| 720 | #if USE_MMAP || USE_SBRK
|
---|
| 721 | if (!b) {
|
---|
| 722 | size_t area_size;
|
---|
| 723 | void *area;
|
---|
| 724 | /* Growing the pool size when needed */
|
---|
| 725 | area_size = size + BHDR_OVERHEAD * 8; /* size plus enough room for the requered headers. */
|
---|
| 726 | area_size = (area_size > DEFAULT_AREA_SIZE) ? area_size : DEFAULT_AREA_SIZE;
|
---|
| 727 | area = get_new_area(&area_size); /* Call sbrk or mmap */
|
---|
| 728 | if (area == ((void *) ~0))
|
---|
| 729 | return NULL; /* Not enough system memory */
|
---|
| 730 | add_new_area(area, area_size, mem_pool);
|
---|
| 731 | /* Rounding up the requested size and calculating fl and sl */
|
---|
| 732 | MAPPING_SEARCH(&size, &fl, &sl);
|
---|
| 733 | /* Searching a free block */
|
---|
| 734 | b = FIND_SUITABLE_BLOCK(tlsf, &fl, &sl);
|
---|
| 735 | }
|
---|
| 736 | #endif
|
---|
| 737 | if (!b)
|
---|
| 738 | return NULL; /* Not found */
|
---|
| 739 |
|
---|
| 740 | EXTRACT_BLOCK_HDR(b, tlsf, fl, sl);
|
---|
| 741 |
|
---|
| 742 | /*-- found: */
|
---|
| 743 | next_b = GET_NEXT_BLOCK(b->ptr.buffer, b->size & BLOCK_SIZE);
|
---|
| 744 | /* Should the block be split? */
|
---|
| 745 | tmp_size = (b->size & BLOCK_SIZE) - size;
|
---|
| 746 | if (tmp_size >= sizeof(bhdr_t)) {
|
---|
| 747 | tmp_size -= BHDR_OVERHEAD;
|
---|
| 748 | b2 = GET_NEXT_BLOCK(b->ptr.buffer, size);
|
---|
| 749 | b2->size = tmp_size | FREE_BLOCK | PREV_USED;
|
---|
| 750 | next_b->prev_hdr = b2;
|
---|
| 751 | MAPPING_INSERT(tmp_size, &fl, &sl);
|
---|
| 752 | INSERT_BLOCK(b2, tlsf, fl, sl);
|
---|
| 753 |
|
---|
| 754 | b->size = size | (b->size & PREV_STATE);
|
---|
| 755 | } else {
|
---|
| 756 | next_b->size &= (~PREV_FREE);
|
---|
| 757 | b->size &= (~FREE_BLOCK); /* Now it's used */
|
---|
| 758 | }
|
---|
| 759 |
|
---|
| 760 | TLSF_ADD_SIZE(tlsf, b);
|
---|
| 761 |
|
---|
| 762 | return (void *) b->ptr.buffer;
|
---|
| 763 | }
|
---|
| 764 |
|
---|
| 765 | /******************************************************************/
|
---|
| 766 | void free_ex(void *ptr, void *mem_pool)
|
---|
| 767 | {
|
---|
| 768 | /******************************************************************/
|
---|
| 769 | tlsf_t *tlsf = (tlsf_t *) mem_pool;
|
---|
| 770 | bhdr_t *b, *tmp_b;
|
---|
| 771 | int fl = 0, sl = 0;
|
---|
| 772 |
|
---|
| 773 | if (!ptr) {
|
---|
| 774 | return;
|
---|
| 775 | }
|
---|
| 776 | b = (bhdr_t *) ((char *) ptr - BHDR_OVERHEAD);
|
---|
| 777 | b->size |= FREE_BLOCK;
|
---|
| 778 |
|
---|
| 779 | TLSF_REMOVE_SIZE(tlsf, b);
|
---|
| 780 |
|
---|
| 781 | b->ptr.free_ptr.prev = NULL;
|
---|
| 782 | b->ptr.free_ptr.next = NULL;
|
---|
| 783 | tmp_b = GET_NEXT_BLOCK(b->ptr.buffer, b->size & BLOCK_SIZE);
|
---|
| 784 | if (tmp_b->size & FREE_BLOCK) {
|
---|
| 785 | MAPPING_INSERT(tmp_b->size & BLOCK_SIZE, &fl, &sl);
|
---|
| 786 | EXTRACT_BLOCK(tmp_b, tlsf, fl, sl);
|
---|
| 787 | b->size += (tmp_b->size & BLOCK_SIZE) + BHDR_OVERHEAD;
|
---|
| 788 | }
|
---|
| 789 | if (b->size & PREV_FREE) {
|
---|
| 790 | tmp_b = b->prev_hdr;
|
---|
| 791 | MAPPING_INSERT(tmp_b->size & BLOCK_SIZE, &fl, &sl);
|
---|
| 792 | EXTRACT_BLOCK(tmp_b, tlsf, fl, sl);
|
---|
| 793 | tmp_b->size += (b->size & BLOCK_SIZE) + BHDR_OVERHEAD;
|
---|
| 794 | b = tmp_b;
|
---|
| 795 | }
|
---|
| 796 | MAPPING_INSERT(b->size & BLOCK_SIZE, &fl, &sl);
|
---|
| 797 | INSERT_BLOCK(b, tlsf, fl, sl);
|
---|
| 798 |
|
---|
| 799 | tmp_b = GET_NEXT_BLOCK(b->ptr.buffer, b->size & BLOCK_SIZE);
|
---|
| 800 | tmp_b->size |= PREV_FREE;
|
---|
| 801 | tmp_b->prev_hdr = b;
|
---|
| 802 | }
|
---|
| 803 |
|
---|
| 804 | /******************************************************************/
|
---|
| 805 | void *realloc_ex(void *ptr, size_t new_size, void *mem_pool)
|
---|
| 806 | {
|
---|
| 807 | /******************************************************************/
|
---|
| 808 | tlsf_t *tlsf = (tlsf_t *) mem_pool;
|
---|
| 809 | void *ptr_aux;
|
---|
| 810 | unsigned int cpsize;
|
---|
| 811 | bhdr_t *b, *tmp_b, *next_b;
|
---|
| 812 | int fl, sl;
|
---|
| 813 | size_t tmp_size;
|
---|
| 814 |
|
---|
| 815 | if (!ptr) {
|
---|
| 816 | if (new_size)
|
---|
| 817 | return (void *) malloc_ex(new_size, mem_pool);
|
---|
| 818 | if (!new_size)
|
---|
| 819 | return NULL;
|
---|
| 820 | } else if (!new_size) {
|
---|
| 821 | free_ex(ptr, mem_pool);
|
---|
| 822 | return NULL;
|
---|
| 823 | }
|
---|
| 824 |
|
---|
| 825 | b = (bhdr_t *) ((char *) ptr - BHDR_OVERHEAD);
|
---|
| 826 | next_b = GET_NEXT_BLOCK(b->ptr.buffer, b->size & BLOCK_SIZE);
|
---|
| 827 | new_size = (new_size < MIN_BLOCK_SIZE) ? MIN_BLOCK_SIZE : ROUNDUP_SIZE(new_size);
|
---|
| 828 | tmp_size = (b->size & BLOCK_SIZE);
|
---|
| 829 | if (new_size <= tmp_size) {
|
---|
| 830 | TLSF_REMOVE_SIZE(tlsf, b);
|
---|
| 831 | if (next_b->size & FREE_BLOCK) {
|
---|
| 832 | MAPPING_INSERT(next_b->size & BLOCK_SIZE, &fl, &sl);
|
---|
| 833 | EXTRACT_BLOCK(next_b, tlsf, fl, sl);
|
---|
| 834 | tmp_size += (next_b->size & BLOCK_SIZE) + BHDR_OVERHEAD;
|
---|
| 835 | next_b = GET_NEXT_BLOCK(next_b->ptr.buffer, next_b->size & BLOCK_SIZE);
|
---|
| 836 | /* We allways reenter this free block because tmp_size will
|
---|
| 837 | be greater then sizeof (bhdr_t) */
|
---|
| 838 | }
|
---|
| 839 | tmp_size -= new_size;
|
---|
| 840 | if (tmp_size >= sizeof(bhdr_t)) {
|
---|
| 841 | tmp_size -= BHDR_OVERHEAD;
|
---|
| 842 | tmp_b = GET_NEXT_BLOCK(b->ptr.buffer, new_size);
|
---|
| 843 | tmp_b->size = tmp_size | FREE_BLOCK | PREV_USED;
|
---|
| 844 | next_b->prev_hdr = tmp_b;
|
---|
| 845 | next_b->size |= PREV_FREE;
|
---|
| 846 | MAPPING_INSERT(tmp_size, &fl, &sl);
|
---|
| 847 | INSERT_BLOCK(tmp_b, tlsf, fl, sl);
|
---|
| 848 | b->size = new_size | (b->size & PREV_STATE);
|
---|
| 849 | }
|
---|
| 850 | TLSF_ADD_SIZE(tlsf, b);
|
---|
| 851 | return (void *) b->ptr.buffer;
|
---|
| 852 | }
|
---|
| 853 | if ((next_b->size & FREE_BLOCK)) {
|
---|
| 854 | if (new_size <= (tmp_size + (next_b->size & BLOCK_SIZE))) {
|
---|
| 855 | TLSF_REMOVE_SIZE(tlsf, b);
|
---|
| 856 | MAPPING_INSERT(next_b->size & BLOCK_SIZE, &fl, &sl);
|
---|
| 857 | EXTRACT_BLOCK(next_b, tlsf, fl, sl);
|
---|
| 858 | b->size += (next_b->size & BLOCK_SIZE) + BHDR_OVERHEAD;
|
---|
| 859 | next_b = GET_NEXT_BLOCK(b->ptr.buffer, b->size & BLOCK_SIZE);
|
---|
| 860 | next_b->prev_hdr = b;
|
---|
| 861 | next_b->size &= ~PREV_FREE;
|
---|
| 862 | tmp_size = (b->size & BLOCK_SIZE) - new_size;
|
---|
| 863 | if (tmp_size >= sizeof(bhdr_t)) {
|
---|
| 864 | tmp_size -= BHDR_OVERHEAD;
|
---|
| 865 | tmp_b = GET_NEXT_BLOCK(b->ptr.buffer, new_size);
|
---|
| 866 | tmp_b->size = tmp_size | FREE_BLOCK | PREV_USED;
|
---|
| 867 | next_b->prev_hdr = tmp_b;
|
---|
| 868 | next_b->size |= PREV_FREE;
|
---|
| 869 | MAPPING_INSERT(tmp_size, &fl, &sl);
|
---|
| 870 | INSERT_BLOCK(tmp_b, tlsf, fl, sl);
|
---|
| 871 | b->size = new_size | (b->size & PREV_STATE);
|
---|
| 872 | }
|
---|
| 873 | TLSF_ADD_SIZE(tlsf, b);
|
---|
| 874 | return (void *) b->ptr.buffer;
|
---|
| 875 | }
|
---|
| 876 | }
|
---|
| 877 |
|
---|
| 878 | if (!(ptr_aux = malloc_ex(new_size, mem_pool))){
|
---|
| 879 | return NULL;
|
---|
| 880 | }
|
---|
| 881 |
|
---|
| 882 | cpsize = ((b->size & BLOCK_SIZE) > new_size) ? new_size : (b->size & BLOCK_SIZE);
|
---|
| 883 |
|
---|
| 884 | memcpy(ptr_aux, ptr, cpsize);
|
---|
| 885 |
|
---|
| 886 | free_ex(ptr, mem_pool);
|
---|
| 887 | return ptr_aux;
|
---|
| 888 | }
|
---|
| 889 |
|
---|
| 890 |
|
---|
| 891 | /******************************************************************/
|
---|
| 892 | void *calloc_ex(size_t nelem, size_t elem_size, void *mem_pool)
|
---|
| 893 | {
|
---|
| 894 | /******************************************************************/
|
---|
| 895 | void *ptr;
|
---|
| 896 |
|
---|
| 897 | if (nelem <= 0 || elem_size <= 0)
|
---|
| 898 | return NULL;
|
---|
| 899 |
|
---|
| 900 | if (!(ptr = malloc_ex(nelem * elem_size, mem_pool)))
|
---|
| 901 | return NULL;
|
---|
| 902 | memset(ptr, 0, nelem * elem_size);
|
---|
| 903 |
|
---|
| 904 | return ptr;
|
---|
| 905 | }
|
---|
| 906 |
|
---|
| 907 |
|
---|
| 908 |
|
---|
| 909 | #if _DEBUG_TLSF_
|
---|
| 910 |
|
---|
| 911 | /*************** DEBUG FUNCTIONS **************/
|
---|
| 912 |
|
---|
| 913 | /* The following functions have been designed to ease the debugging of */
|
---|
| 914 | /* the TLSF structure. For non-developing purposes, it may be they */
|
---|
| 915 | /* haven't too much worth. To enable them, _DEBUG_TLSF_ must be set. */
|
---|
| 916 |
|
---|
| 917 | extern void dump_memory_region(unsigned char *mem_ptr, unsigned int size);
|
---|
| 918 | extern void print_block(bhdr_t * b);
|
---|
| 919 | extern void print_tlsf(tlsf_t * tlsf);
|
---|
| 920 | void print_all_blocks(tlsf_t * tlsf);
|
---|
| 921 |
|
---|
| 922 | void dump_memory_region(unsigned char *mem_ptr, unsigned int size)
|
---|
| 923 | {
|
---|
| 924 |
|
---|
| 925 | unsigned long begin = (unsigned long) mem_ptr;
|
---|
| 926 | unsigned long end = (unsigned long) mem_ptr + size;
|
---|
| 927 | int column = 0;
|
---|
| 928 |
|
---|
| 929 | begin >>= 2;
|
---|
| 930 | begin <<= 2;
|
---|
| 931 |
|
---|
| 932 | end >>= 2;
|
---|
| 933 | end++;
|
---|
| 934 | end <<= 2;
|
---|
| 935 |
|
---|
| 936 | PRINT_MSG("\nMemory region dumped: 0x%lx - 0x%lx\n\n", begin, end);
|
---|
| 937 |
|
---|
| 938 | column = 0;
|
---|
| 939 | PRINT_MSG("0x%lx ", begin);
|
---|
| 940 |
|
---|
| 941 | while (begin < end) {
|
---|
| 942 | if (((unsigned char *) begin)[0] == 0)
|
---|
| 943 | PRINT_MSG("00");
|
---|
| 944 | else
|
---|
| 945 | PRINT_MSG("%02x", ((unsigned char *) begin)[0]);
|
---|
| 946 | if (((unsigned char *) begin)[1] == 0)
|
---|
| 947 | PRINT_MSG("00 ");
|
---|
| 948 | else
|
---|
| 949 | PRINT_MSG("%02x ", ((unsigned char *) begin)[1]);
|
---|
| 950 | begin += 2;
|
---|
| 951 | column++;
|
---|
| 952 | if (column == 8) {
|
---|
| 953 | PRINT_MSG("\n0x%lx ", begin);
|
---|
| 954 | column = 0;
|
---|
| 955 | }
|
---|
| 956 |
|
---|
| 957 | }
|
---|
| 958 | PRINT_MSG("\n\n");
|
---|
| 959 | }
|
---|
| 960 |
|
---|
| 961 | void print_block(bhdr_t * b)
|
---|
| 962 | {
|
---|
| 963 | if (!b)
|
---|
| 964 | return;
|
---|
| 965 | PRINT_MSG(">> [%p] (", b);
|
---|
| 966 | if ((b->size & BLOCK_SIZE))
|
---|
| 967 | PRINT_MSG("%lu bytes, ", (unsigned long) (b->size & BLOCK_SIZE));
|
---|
| 968 | else
|
---|
| 969 | PRINT_MSG("sentinel, ");
|
---|
| 970 | if ((b->size & BLOCK_STATE) == FREE_BLOCK)
|
---|
| 971 | PRINT_MSG("free [%p, %p], ", b->ptr.free_ptr.prev, b->ptr.free_ptr.next);
|
---|
| 972 | else
|
---|
| 973 | PRINT_MSG("used, ");
|
---|
| 974 | if ((b->size & PREV_STATE) == PREV_FREE)
|
---|
| 975 | PRINT_MSG("prev. free [%p])\n", b->prev_hdr);
|
---|
| 976 | else
|
---|
| 977 | PRINT_MSG("prev used)\n");
|
---|
| 978 | }
|
---|
| 979 |
|
---|
| 980 | void print_tlsf(tlsf_t * tlsf)
|
---|
| 981 | {
|
---|
| 982 | bhdr_t *next;
|
---|
| 983 | int i, j;
|
---|
| 984 |
|
---|
| 985 | PRINT_MSG("\nTLSF at %p\n", tlsf);
|
---|
| 986 |
|
---|
| 987 | PRINT_MSG("FL bitmap: 0x%x\n\n", (unsigned) tlsf->fl_bitmap);
|
---|
| 988 |
|
---|
| 989 | for (i = 0; i < REAL_FLI; i++) {
|
---|
| 990 | if (tlsf->sl_bitmap[i])
|
---|
| 991 | PRINT_MSG("SL bitmap 0x%x\n", (unsigned) tlsf->sl_bitmap[i]);
|
---|
| 992 | for (j = 0; j < MAX_SLI; j++) {
|
---|
| 993 | next = tlsf->matrix[i][j];
|
---|
| 994 | if (next)
|
---|
| 995 | PRINT_MSG("-> [%d][%d]\n", i, j);
|
---|
| 996 | while (next) {
|
---|
| 997 | print_block(next);
|
---|
| 998 | next = next->ptr.free_ptr.next;
|
---|
| 999 | }
|
---|
| 1000 | }
|
---|
| 1001 | }
|
---|
| 1002 | }
|
---|
| 1003 |
|
---|
| 1004 | void print_all_blocks(tlsf_t * tlsf)
|
---|
| 1005 | {
|
---|
| 1006 | area_info_t *ai;
|
---|
| 1007 | bhdr_t *next;
|
---|
| 1008 | PRINT_MSG("\nTLSF at %p\nALL BLOCKS\n\n", tlsf);
|
---|
| 1009 | ai = tlsf->area_head;
|
---|
| 1010 | while (ai) {
|
---|
| 1011 | next = (bhdr_t *) ((char *) ai - BHDR_OVERHEAD);
|
---|
| 1012 | while (next) {
|
---|
| 1013 | print_block(next);
|
---|
| 1014 | if ((next->size & BLOCK_SIZE))
|
---|
| 1015 | next = GET_NEXT_BLOCK(next->ptr.buffer, next->size & BLOCK_SIZE);
|
---|
| 1016 | else
|
---|
| 1017 | next = NULL;
|
---|
| 1018 | }
|
---|
| 1019 | ai = ai->next;
|
---|
| 1020 | }
|
---|
| 1021 | }
|
---|
| 1022 |
|
---|
| 1023 | #endif
|
---|