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