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


ocl
Author(s): OCL Development Team
autogenerated on Wed Jun 26 2019 19:26:27