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