summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorPeter D'Hoye <peter.dhoye@gmail.com>2009-07-21 14:01:51 +0000
committerPeter D'Hoye <peter.dhoye@gmail.com>2009-07-21 14:01:51 +0000
commit1a4b0cadd66849f83eecd6be2c59df234a4eabc8 (patch)
tree078d6bf9c840f98ec6ab56fa746163ee85b54b98
parentc8195d80bf750d13ec37139a24bec915144d3109 (diff)
downloadrockbox-1a4b0cadd66849f83eecd6be2c59df234a4eabc8.tar.gz
rockbox-1a4b0cadd66849f83eecd6be2c59df234a4eabc8.zip
By Wincent Balin: add a new (better) memory allocation library for pdbox. Next commit will remove dbestfit and make pdbox use this one.
git-svn-id: svn://svn.rockbox.org/rockbox/trunk@21993 a1c6a512-1295-4272-9138-f99709370657
Diffstat
-rw-r--r--apps/plugins/pdbox/TLSF-2.4.4/COPYING23
-rw-r--r--apps/plugins/pdbox/TLSF-2.4.4/Changelog119
-rw-r--r--apps/plugins/pdbox/TLSF-2.4.4/README163
-rw-r--r--apps/plugins/pdbox/TLSF-2.4.4/TODO9
-rw-r--r--apps/plugins/pdbox/TLSF-2.4.4/src/target.h12
-rw-r--r--apps/plugins/pdbox/TLSF-2.4.4/src/tlsf.c995
-rw-r--r--apps/plugins/pdbox/TLSF-2.4.4/src/tlsf.h39
7 files changed, 1360 insertions, 0 deletions
diff --git a/apps/plugins/pdbox/TLSF-2.4.4/COPYING b/apps/plugins/pdbox/TLSF-2.4.4/COPYING
new file mode 100644
index 0000000000..78fdbdc061
--- /dev/null
+++ b/apps/plugins/pdbox/TLSF-2.4.4/COPYING
@@ -0,0 +1,23 @@
1 LICENSE INFORMATION
2
3TLSF is released as LGPL and GPL. A copy of both licences can be found in this
4directoy. For the GPL licence, the following exception applies.
5
6
7TLSF is free software; you can redistribute it and/or modify it under terms of
8the GNU General Public License as published by the Free Software Foundation;
9either version 2, or (at your option) any later version. TLSF is distributed
10in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the
11implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See
12the GNU General Public License for more details. You should have received a
13copy of the GNU General Public License along with TLSF; see file COPYING. If
14not, write to the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139,
15USA.
16
17As a special exception, including TLSF header files in a file, or linking with
18other files objects to produce an executable application, is merely considered
19normal use of the library, and does *not* fall under the heading of "derived
20work". Therfore does not by itself cause the resulting executable application
21to be covered by the GNU General Public License. This exception does not
22however invalidate any other reasons why the executable file might be covered
23by the GNU Public License.
diff --git a/apps/plugins/pdbox/TLSF-2.4.4/Changelog b/apps/plugins/pdbox/TLSF-2.4.4/Changelog
new file mode 100644
index 0000000000..0cdb34a8ab
--- /dev/null
+++ b/apps/plugins/pdbox/TLSF-2.4.4/Changelog
@@ -0,0 +1,119 @@
1 Version History
2 ---------------
3 -v2.4.4 (October 13 2008)
4 * Corrected minor syntactic bug on statistic gathering code.
5 Reported by Tim Cussins and P. Mantegazza.
6
7 -v2.4.3 (July 30 2008)
8 * Minor fixes to compile with the greenhills compiler.
9 Reported by "Kaya, Sinan SEA" <sinan.kaya@siemens.com>
10 * Small change in the license in order to include TLSF in the RTEMS
11 project.
12
13 -v2.4.2 (May 16 2008) (Herman ten Brugge)
14 * Memory usage statistics added again, with cleaner and more compacted
15 code.
16
17 -v2.4.1 (April 30 2008)
18 * Fixed a bug in the tlsf_realloc function: init the pool automatically
19 on the first call.
20 Reported by: Alejandro Mery <amery@geeks.cl>
21
22 -v2.4 (Feb 19 2008)
23 * "rtl_*" functions renamed to "tlsf_*".
24 * Added the add_new_area function to insert new memory areas to an
25 existing memory pool.
26 * A single TLSF pool can manage non-contiguous memory areas.
27 * Support for mmap and sbrk added.
28 * The init_memory_pool is not longer needed when used on a system
29 with mmap or sbrk.
30 * Removed the get_used_size counting.The same functionality can be
31 implemented outside the TLSF code.
32
33 -v2.3.2 (Sep 27 2007)
34 * Minor cosmetic code improvements.
35
36 -v2.3.1 (Jul 30 2007)
37 * Fixed some minor bugs in the version 2.3. Herman ten Brugge
38 <hermantenbrugge@home.nl>
39
40 -v2.3 (Jul 28 2007) Released a new version with all the contributions
41 received from Herman ten Brugge <hermantenbrugge@home.nl>
42 (This is his summary of changes in the TLSF's code):
43 * Add 64 bit support. It now runs on x86_64 and solaris64.
44 * I also tested this on vxworks/32 and solaris/32 and i386/32
45 processors.
46 * Remove assembly code. I could not measure any performance difference
47 on my core2 processor. This also makes the code more portable.
48 * Moved defines/typedefs from tlsf.h to tlsf.c
49 * Changed MIN_BLOCK_SIZE to sizeof (free_ptr_t) and BHDR_OVERHEAD to
50 (sizeof (bhdr_t) - MIN_BLOCK_SIZE). This does not change the fact
51 that the minumum size is still sizeof (bhdr_t).
52 * Changed all C++ comment style to C style. (// -> /* ... *./)
53 * Used ls_bit instead of ffs and ms_bit instead of fls. I did this to
54 avoid confusion with the standard ffs function which returns
55 different values.
56 * Created set_bit/clear_bit fuctions because they are not present
57 on x86_64.
58 * Added locking support + extra file target.h to show how to use it.
59 * Added get_used_size function
60 * Added rtl_realloc and rtl_calloc function
61 * Implemented realloc clever support.
62 * Added some test code in the example directory.
63
64 -- Thank you very much for your help Herman!
65
66 -v2.2.1 (Oct 23 2006)
67 * Support for ARMv5 implemented by Adam Scislowicz
68 <proteuskor@gmail.com>. Thank you for your contribution.
69
70 - v2.2.0 (Jun 30 2006) Miguel Masmano & Ismael Ripoll.
71
72 * Blocks smaller than 128 bytes are stored on a single
73 segregated list. The already existing bits maps and data
74 structures are used.
75 * Minor code speed-up improvements.
76 * Worst case response time both on malloc and free improved.
77 * External fragmantation also improved!.
78 * Segragared lists are AGAIN sorted by LIFO order. Version
79 2.1b was proven to be no better than 2.1.
80
81 - v2.1b: Allocation policy has been always a LIFO Good-Fit, that
82 is, between several free blocks in the same range, TLSF will
83 always allocate the most recently released. In this version of
84 TLSF, we have implemented a FIFO Good-Fit. However,
85 fragmentation doesn't seems to be altered so is it worth it?.
86
87 - v2.1: Realloc and calloc included again in TLSF 2.0.
88
89 - v2.0: In this version, TLSF has been programmed from scratch.
90 Now the allocator is provided as an unique file. Realloc and
91 calloc are not longer implemented.
92
93
94 - v1.4: Created the section "Version History". Studied real
95 behaviour of actual applications (regular applications tend
96 to require small memory blocks (less than 16 bytes) whereas
97 TLSF is optimised to be used with blocks larger than 16
98 bytes: Added special lists to deal with blocks smaller than
99 16 bytes.
100
101
102 - v1.3: Change of concept, now the main TLSF structure is created
103 inside of the beginning of the block instead of being an
104 static structure, allowing multiple TLSFs working at the
105 same time. Now, TLSF uses specific processor instructions to
106 deal with bitmaps. TLSF sanity functions added to find TLSF
107 overflows. The TLSF code will not be RTLinux-oriented any
108 more.
109
110 - v1.1 ... v1.2: Many little bugs fixed, code cleaned and splitted
111 in several files because of cosmetic requirements.
112 Starting from TLSF v1.1, MaRTE OS
113 (http://marte.unican.es) uses the TLSF allocator
114 as its default memory allocator.
115
116 - v0.1 ... v1.0: First implementations were created for testing and
117 research purposes. Basically TLSF is implemented to
118 be used by RTLinux-GPL (www.rtlinux-gpl.org), so
119 it is RTLinux-oriented.
diff --git a/apps/plugins/pdbox/TLSF-2.4.4/README b/apps/plugins/pdbox/TLSF-2.4.4/README
new file mode 100644
index 0000000000..d755905b16
--- /dev/null
+++ b/apps/plugins/pdbox/TLSF-2.4.4/README
@@ -0,0 +1,163 @@
1
2TLSF Memory Storage allocator implementation.
3Version 2.4 Feb 2008
4
5Authors: Miguel Masmano, Ismael Ripoll & Alfons Crespo.
6Copyright UPVLC, OCERA Consortium.
7
8TLSF is released in the GPL/LGPL licence. The exact terms of the licence
9are described in the COPYING file.
10
11This component provides basic memory allocation functions:
12malloc and free, as defined in the standard "C" library.
13
14This allocator was designed to provide real-time performance, that is:
151.- Bounded time malloc and free.
162.- Fast response time.
173.- Efficient memory management, that is low fragmentation.
18
19
20The worst response time for both malloc and free is O(1).
21
22
23
24How to use it:
25
26This code is prepared to be used as a stand-alone code that can be
27linked with a regular application or it can be compiled to be a Linux
28module (which required the BigPhysicalArea patch). Initially the
29module was designed to work jointly with RTLinux-GPL, but it can be
30used as a stand alone Linux module.
31
32When compiled as a regular linux process the API is:
33
34Initialisation and destruction functions
35----------------------------------------
36
37init_memory_pool may be called before any request or release call:
38
39- size_t init_memory_pool(size_t, void *);
40- void destroy_memory_pool(void *);
41
42Request and release functions
43-----------------------------
44
45As can be seen, there are two functions for each traditional memory
46allocation function (malloc, free, realloc, and calloc). One with the
47prefix "tlsf_" and the other with the suffix "_ex".
48
49The versions with the prefix "tlsf_" provides the expected behaviour,
50that is, allocating/releasing memory from the default memory pool. The
51default memory pool is the last pool initialised by the
52init_memory_pool function.
53
54On the other hand, the functions with the prefix "_ex" enable the use of several memory pools.
55
56- void *tlsf_malloc(size_t);
57- void *malloc_ex(size_t, void *);
58
59- void tlsf_free(void *ptr);
60- void free_ex(void *, void *);
61
62- void *tlsf_realloc(void *ptr, size_t size);
63- void *realloc_ex(void *, size_t, void *);
64
65- void *tlsf_calloc(size_t nelem, size_t elem_size);
66- void *calloc_ex(size_t, size_t, void *);
67
68EXAMPLE OF USE:
69
70char memory_pool[1024*1024];
71
72{
73 ...
74
75 init_memory_pool(1024*1024, memory_pool);
76
77 ...
78
79 ptr1=malloc_ex(100, memory_pool);
80 ptr2=tlsf_malloc(100); // This function will use memory_pool
81
82 ...
83
84 tlsf_free(ptr2);
85 free_ex(ptr1, memory_pool);
86}
87
88Growing the memory pool
89-----------------------
90
91Starting from the version 2.4, the function add_new_area adds an
92memory area to an existing memory pool.
93
94- size_t add_new_area(void *, size_t, void *);
95
96This feature is pretty useful when an existing memory pool is running
97low and we want to add more free memory to it.
98EXAMPLE OF USE:
99
100char memory_pool[1024*1024];
101char memory_pool2[1024*1024];
102
103{
104 ...
105
106 init_memory_pool(1024*1024, memory_pool);
107
108 ...
109
110 ptr[0]=malloc_ex(1024*256 memory_pool);
111 ptr[1]=malloc_ex(1024*512, memory_pool);
112 add_new_area(memory_pool2, 1024*1024, memory_pool);
113 // Now we have an extra free memory area of 1Mb
114 // The next malloc may not fail
115 ptr[2]=malloc_ex(1024*512, memory_pool);
116
117 ...
118
119}
120
121
122SBRK and MMAP support
123---------------------
124
125The version 2.4 can use the functions SBRK and MMAP to _automatically_
126growing the memory pool, before running out of memory.
127
128So, when this feature is enabled, unless the operating system were out
129of memory, a malloc operation would not fail due to an "out-of-memory"
130error.
131
132To enable this support, compile tlsf.c with the FLAGS -DUSE_MMAP=1 or
133-DUSE_SBRK=1 depending on whether you want to use "mmap" or "sbrk" or both.
134
135** By default (default Makefile) this feature is enabled.
136
137EXAMPLE OF USE:
138
139gcc -o tlsf.o -O2 -Wall -DUSE_MMAP=1 -DUSE_SBRK=1
140
141---
142
143If the sbrk/mmap support is enabled and we are _only_ going to use one
144memory pool, it is not necessary to call init_memory_pool
145
146EXAMPLE OF USE (with MMAP/SBRK support enabled):
147
148{
149 ...
150
151 ptr2=tlsf_malloc(100); // This function will use memory_pool
152
153 ...
154
155 tlsf_free(ptr2);
156}
157
158
159
160
161This work has been supported by the followin projects:
162EUROPEAN: IST-2001-35102(OCERA) http://www.ocera.org.
163SPANISH: TIN2005-08665-C3-03
diff --git a/apps/plugins/pdbox/TLSF-2.4.4/TODO b/apps/plugins/pdbox/TLSF-2.4.4/TODO
new file mode 100644
index 0000000000..d7c07b8421
--- /dev/null
+++ b/apps/plugins/pdbox/TLSF-2.4.4/TODO
@@ -0,0 +1,9 @@
1To do list
2==========
3
4* Add mmap/sbrk support (DONE - V2.4).
5
6* TLSF rounds-up request size to the head of a free list.
7 It has been shown to be a good policy for small blocks (<2048).
8 But for larger blocks this policy may cause excesive fragmentation.
9 A deeper analisys should be done.
diff --git a/apps/plugins/pdbox/TLSF-2.4.4/src/target.h b/apps/plugins/pdbox/TLSF-2.4.4/src/target.h
new file mode 100644
index 0000000000..1afd62aef2
--- /dev/null
+++ b/apps/plugins/pdbox/TLSF-2.4.4/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/plugins/pdbox/TLSF-2.4.4/src/tlsf.c b/apps/plugins/pdbox/TLSF-2.4.4/src/tlsf.c
new file mode 100644
index 0000000000..47b461bac5
--- /dev/null
+++ b/apps/plugins/pdbox/TLSF-2.4.4/src/tlsf.c
@@ -0,0 +1,995 @@
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#define PRINT_MSG(fmt, args...) printf(fmt, ## args)
168#define ERROR_MSG(fmt, args...) printf(fmt, ## args)
169
170typedef unsigned int u32_t; /* NOTE: Make sure that this type is 4 bytes long on your computer */
171typedef unsigned char u8_t; /* NOTE: Make sure that this type is 1 byte on your computer */
172
173typedef struct free_ptr_struct {
174 struct bhdr_struct *prev;
175 struct bhdr_struct *next;
176} free_ptr_t;
177
178typedef struct bhdr_struct {
179 /* This pointer is just valid if the first bit of size is set */
180 struct bhdr_struct *prev_hdr;
181 /* The size is stored in bytes */
182 size_t size; /* bit 0 indicates whether the block is used and */
183 /* bit 1 allows to know whether the previous block is free */
184 union {
185 struct free_ptr_struct free_ptr;
186 u8_t buffer[1]; /*sizeof(struct free_ptr_struct)]; */
187 } ptr;
188} bhdr_t;
189
190/* This structure is embedded at the beginning of each area, giving us
191 * enough information to cope with a set of areas */
192
193typedef struct area_info_struct {
194 bhdr_t *end;
195 struct area_info_struct *next;
196} area_info_t;
197
198typedef struct TLSF_struct {
199 /* the TLSF's structure signature */
200 u32_t tlsf_signature;
201
202#if TLSF_USE_LOCKS
203 TLSF_MLOCK_T lock;
204#endif
205
206#if TLSF_STATISTIC
207 /* These can not be calculated outside tlsf because we
208 * do not know the sizes when freeing/reallocing memory. */
209 size_t used_size;
210 size_t max_size;
211#endif
212
213 /* A linked list holding all the existing areas */
214 area_info_t *area_head;
215
216 /* the first-level bitmap */
217 /* This array should have a size of REAL_FLI bits */
218 u32_t fl_bitmap;
219
220 /* the second-level bitmap */
221 u32_t sl_bitmap[REAL_FLI];
222
223 bhdr_t *matrix[REAL_FLI][MAX_SLI];
224} tlsf_t;
225
226
227/******************************************************************/
228/************** Helping functions **************************/
229/******************************************************************/
230static __inline__ void set_bit(int nr, u32_t * addr);
231static __inline__ void clear_bit(int nr, u32_t * addr);
232static __inline__ int ls_bit(int x);
233static __inline__ int ms_bit(int x);
234static __inline__ void MAPPING_SEARCH(size_t * _r, int *_fl, int *_sl);
235static __inline__ void MAPPING_INSERT(size_t _r, int *_fl, int *_sl);
236static __inline__ bhdr_t *FIND_SUITABLE_BLOCK(tlsf_t * _tlsf, int *_fl, int *_sl);
237static __inline__ bhdr_t *process_area(void *area, size_t size);
238#if USE_SBRK || USE_MMAP
239static __inline__ void *get_new_area(size_t * size);
240#endif
241
242static const int table[] = {
243 -1, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4,
244 4, 4,
245 4, 4, 4, 4, 4, 4, 4,
246 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
247 5,
248 5, 5, 5, 5, 5, 5, 5,
249 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
250 6,
251 6, 6, 6, 6, 6, 6, 6,
252 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
253 6,
254 6, 6, 6, 6, 6, 6, 6,
255 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
256 7,
257 7, 7, 7, 7, 7, 7, 7,
258 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
259 7,
260 7, 7, 7, 7, 7, 7, 7,
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};
268
269static __inline__ int ls_bit(int i)
270{
271 unsigned int a;
272 unsigned int x = i & -i;
273
274 a = x <= 0xffff ? (x <= 0xff ? 0 : 8) : (x <= 0xffffff ? 16 : 24);
275 return table[x >> a] + a;
276}
277
278static __inline__ int ms_bit(int i)
279{
280 unsigned int a;
281 unsigned int x = (unsigned int) i;
282
283 a = x <= 0xffff ? (x <= 0xff ? 0 : 8) : (x <= 0xffffff ? 16 : 24);
284 return table[x >> a] + a;
285}
286
287static __inline__ void set_bit(int nr, u32_t * addr)
288{
289 addr[nr >> 5] |= 1 << (nr & 0x1f);
290}
291
292static __inline__ void clear_bit(int nr, u32_t * addr)
293{
294 addr[nr >> 5] &= ~(1 << (nr & 0x1f));
295}
296
297static __inline__ void MAPPING_SEARCH(size_t * _r, int *_fl, int *_sl)
298{
299 int _t;
300
301 if (*_r < SMALL_BLOCK) {
302 *_fl = 0;
303 *_sl = *_r / (SMALL_BLOCK / MAX_SLI);
304 } else {
305 _t = (1 << (ms_bit(*_r) - MAX_LOG2_SLI)) - 1;
306 *_r = *_r + _t;
307 *_fl = ms_bit(*_r);
308 *_sl = (*_r >> (*_fl - MAX_LOG2_SLI)) - MAX_SLI;
309 *_fl -= FLI_OFFSET;
310 /*if ((*_fl -= FLI_OFFSET) < 0) // FL wil be always >0!
311 *_fl = *_sl = 0;
312 */
313 *_r &= ~_t;
314 }
315}
316
317static __inline__ void MAPPING_INSERT(size_t _r, int *_fl, int *_sl)
318{
319 if (_r < SMALL_BLOCK) {
320 *_fl = 0;
321 *_sl = _r / (SMALL_BLOCK / MAX_SLI);
322 } else {
323 *_fl = ms_bit(_r);
324 *_sl = (_r >> (*_fl - MAX_LOG2_SLI)) - MAX_SLI;
325 *_fl -= FLI_OFFSET;
326 }
327}
328
329
330static __inline__ bhdr_t *FIND_SUITABLE_BLOCK(tlsf_t * _tlsf, int *_fl, int *_sl)
331{
332 u32_t _tmp = _tlsf->sl_bitmap[*_fl] & (~0 << *_sl);
333 bhdr_t *_b = NULL;
334
335 if (_tmp) {
336 *_sl = ls_bit(_tmp);
337 _b = _tlsf->matrix[*_fl][*_sl];
338 } else {
339 *_fl = ls_bit(_tlsf->fl_bitmap & (~0 << (*_fl + 1)));
340 if (*_fl > 0) { /* likely */
341 *_sl = ls_bit(_tlsf->sl_bitmap[*_fl]);
342 _b = _tlsf->matrix[*_fl][*_sl];
343 }
344 }
345 return _b;
346}
347
348
349#define EXTRACT_BLOCK_HDR(_b, _tlsf, _fl, _sl) do { \
350 _tlsf -> matrix [_fl] [_sl] = _b -> ptr.free_ptr.next; \
351 if (_tlsf -> matrix[_fl][_sl]) \
352 _tlsf -> matrix[_fl][_sl] -> ptr.free_ptr.prev = NULL; \
353 else { \
354 clear_bit (_sl, &_tlsf -> sl_bitmap [_fl]); \
355 if (!_tlsf -> sl_bitmap [_fl]) \
356 clear_bit (_fl, &_tlsf -> fl_bitmap); \
357 } \
358 _b -> ptr.free_ptr.prev = NULL; \
359 _b -> ptr.free_ptr.next = NULL; \
360 }while(0)
361
362
363#define EXTRACT_BLOCK(_b, _tlsf, _fl, _sl) do { \
364 if (_b -> ptr.free_ptr.next) \
365 _b -> ptr.free_ptr.next -> ptr.free_ptr.prev = _b -> ptr.free_ptr.prev; \
366 if (_b -> ptr.free_ptr.prev) \
367 _b -> ptr.free_ptr.prev -> ptr.free_ptr.next = _b -> ptr.free_ptr.next; \
368 if (_tlsf -> matrix [_fl][_sl] == _b) { \
369 _tlsf -> matrix [_fl][_sl] = _b -> ptr.free_ptr.next; \
370 if (!_tlsf -> matrix [_fl][_sl]) { \
371 clear_bit (_sl, &_tlsf -> sl_bitmap[_fl]); \
372 if (!_tlsf -> sl_bitmap [_fl]) \
373 clear_bit (_fl, &_tlsf -> fl_bitmap); \
374 } \
375 } \
376 _b -> ptr.free_ptr.prev = NULL; \
377 _b -> ptr.free_ptr.next = NULL; \
378 } while(0)
379
380#define INSERT_BLOCK(_b, _tlsf, _fl, _sl) do { \
381 _b -> ptr.free_ptr.prev = NULL; \
382 _b -> ptr.free_ptr.next = _tlsf -> matrix [_fl][_sl]; \
383 if (_tlsf -> matrix [_fl][_sl]) \
384 _tlsf -> matrix [_fl][_sl] -> ptr.free_ptr.prev = _b; \
385 _tlsf -> matrix [_fl][_sl] = _b; \
386 set_bit (_sl, &_tlsf -> sl_bitmap [_fl]); \
387 set_bit (_fl, &_tlsf -> fl_bitmap); \
388 } while(0)
389
390#if USE_SBRK || USE_MMAP
391static __inline__ void *get_new_area(size_t * size)
392{
393 void *area;
394
395#if USE_SBRK
396 area = (void *)sbrk(0);
397 if (((void *)sbrk(*size)) != ((void *) -1))
398 return area;
399#endif
400
401#if USE_MMAP
402 *size = ROUNDUP(*size, PAGE_SIZE);
403 if ((area = mmap(0, *size, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0)) != MAP_FAILED)
404 return area;
405#endif
406 return ((void *) ~0);
407}
408#endif
409
410static __inline__ bhdr_t *process_area(void *area, size_t size)
411{
412 bhdr_t *b, *lb, *ib;
413 area_info_t *ai;
414
415 ib = (bhdr_t *) area;
416 ib->size =
417 (sizeof(area_info_t) <
418 MIN_BLOCK_SIZE) ? MIN_BLOCK_SIZE : ROUNDUP_SIZE(sizeof(area_info_t)) | USED_BLOCK | PREV_USED;
419 b = (bhdr_t *) GET_NEXT_BLOCK(ib->ptr.buffer, ib->size & BLOCK_SIZE);
420 b->size = ROUNDDOWN_SIZE(size - 3 * BHDR_OVERHEAD - (ib->size & BLOCK_SIZE)) | USED_BLOCK | PREV_USED;
421 b->ptr.free_ptr.prev = b->ptr.free_ptr.next = 0;
422 lb = GET_NEXT_BLOCK(b->ptr.buffer, b->size & BLOCK_SIZE);
423 lb->prev_hdr = b;
424 lb->size = 0 | USED_BLOCK | PREV_FREE;
425 ai = (area_info_t *) ib->ptr.buffer;
426 ai->next = 0;
427 ai->end = lb;
428 return ib;
429}
430
431/******************************************************************/
432/******************** Begin of the allocator code *****************/
433/******************************************************************/
434
435static char *mp = NULL; /* Default memory pool. */
436
437/******************************************************************/
438size_t init_memory_pool(size_t mem_pool_size, void *mem_pool)
439{
440/******************************************************************/
441 tlsf_t *tlsf;
442 bhdr_t *b, *ib;
443
444 if (!mem_pool || !mem_pool_size || mem_pool_size < sizeof(tlsf_t) + BHDR_OVERHEAD * 8) {
445 ERROR_MSG("init_memory_pool (): memory_pool invalid\n");
446 return -1;
447 }
448
449 if (((unsigned long) mem_pool & PTR_MASK)) {
450 ERROR_MSG("init_memory_pool (): mem_pool must be aligned to a word\n");
451 return -1;
452 }
453 tlsf = (tlsf_t *) mem_pool;
454 /* Check if already initialised */
455 if (tlsf->tlsf_signature == TLSF_SIGNATURE) {
456 mp = mem_pool;
457 b = GET_NEXT_BLOCK(mp, ROUNDUP_SIZE(sizeof(tlsf_t)));
458 return b->size & BLOCK_SIZE;
459 }
460
461 mp = mem_pool;
462
463 /* Zeroing the memory pool */
464 memset(mem_pool, 0, sizeof(tlsf_t));
465
466 tlsf->tlsf_signature = TLSF_SIGNATURE;
467
468 TLSF_CREATE_LOCK(&tlsf->lock);
469
470 ib = process_area(GET_NEXT_BLOCK
471 (mem_pool, ROUNDUP_SIZE(sizeof(tlsf_t))), ROUNDDOWN_SIZE(mem_pool_size - sizeof(tlsf_t)));
472 b = GET_NEXT_BLOCK(ib->ptr.buffer, ib->size & BLOCK_SIZE);
473 free_ex(b->ptr.buffer, tlsf);
474 tlsf->area_head = (area_info_t *) ib->ptr.buffer;
475
476#if TLSF_STATISTIC
477 tlsf->used_size = mem_pool_size - (b->size & BLOCK_SIZE);
478 tlsf->max_size = tlsf->used_size;
479#endif
480
481 return (b->size & BLOCK_SIZE);
482}
483
484/******************************************************************/
485size_t add_new_area(void *area, size_t area_size, void *mem_pool)
486{
487/******************************************************************/
488 tlsf_t *tlsf = (tlsf_t *) mem_pool;
489 area_info_t *ptr, *ptr_prev, *ai;
490 bhdr_t *ib0, *b0, *lb0, *ib1, *b1, *lb1, *next_b;
491
492 memset(area, 0, area_size);
493 ptr = tlsf->area_head;
494 ptr_prev = 0;
495
496 ib0 = process_area(area, area_size);
497 b0 = GET_NEXT_BLOCK(ib0->ptr.buffer, ib0->size & BLOCK_SIZE);
498 lb0 = GET_NEXT_BLOCK(b0->ptr.buffer, b0->size & BLOCK_SIZE);
499
500 /* Before inserting the new area, we have to merge this area with the
501 already existing ones */
502
503 while (ptr) {
504 ib1 = (bhdr_t *) ((char *) ptr - BHDR_OVERHEAD);
505 b1 = GET_NEXT_BLOCK(ib1->ptr.buffer, ib1->size & BLOCK_SIZE);
506 lb1 = ptr->end;
507
508 /* Merging the new area with the next physically contigous one */
509 if ((unsigned long) ib1 == (unsigned long) lb0 + BHDR_OVERHEAD) {
510 if (tlsf->area_head == ptr) {
511 tlsf->area_head = ptr->next;
512 ptr = ptr->next;
513 } else {
514 ptr_prev->next = ptr->next;
515 ptr = ptr->next;
516 }
517
518 b0->size =
519 ROUNDDOWN_SIZE((b0->size & BLOCK_SIZE) +
520 (ib1->size & BLOCK_SIZE) + 2 * BHDR_OVERHEAD) | USED_BLOCK | PREV_USED;
521
522 b1->prev_hdr = b0;
523 lb0 = lb1;
524
525 continue;
526 }
527
528 /* Merging the new area with the previous physically contigous
529 one */
530 if ((unsigned long) lb1->ptr.buffer == (unsigned long) ib0) {
531 if (tlsf->area_head == ptr) {
532 tlsf->area_head = ptr->next;
533 ptr = ptr->next;
534 } else {
535 ptr_prev->next = ptr->next;
536 ptr = ptr->next;
537 }
538
539 lb1->size =
540 ROUNDDOWN_SIZE((b0->size & BLOCK_SIZE) +
541 (ib0->size & BLOCK_SIZE) + 2 * BHDR_OVERHEAD) | USED_BLOCK | (lb1->size & PREV_STATE);
542 next_b = GET_NEXT_BLOCK(lb1->ptr.buffer, lb1->size & BLOCK_SIZE);
543 next_b->prev_hdr = lb1;
544 b0 = lb1;
545 ib0 = ib1;
546
547 continue;
548 }
549 ptr_prev = ptr;
550 ptr = ptr->next;
551 }
552
553 /* Inserting the area in the list of linked areas */
554 ai = (area_info_t *) ib0->ptr.buffer;
555 ai->next = tlsf->area_head;
556 ai->end = lb0;
557 tlsf->area_head = ai;
558 free_ex(b0->ptr.buffer, mem_pool);
559 return (b0->size & BLOCK_SIZE);
560}
561
562
563/******************************************************************/
564size_t get_used_size(void *mem_pool)
565{
566/******************************************************************/
567#if TLSF_STATISTIC
568 return ((tlsf_t *) mem_pool)->used_size;
569#else
570 return 0;
571#endif
572}
573
574/******************************************************************/
575size_t get_max_size(void *mem_pool)
576{
577/******************************************************************/
578#if TLSF_STATISTIC
579 return ((tlsf_t *) mem_pool)->max_size;
580#else
581 return 0;
582#endif
583}
584
585/******************************************************************/
586void destroy_memory_pool(void *mem_pool)
587{
588/******************************************************************/
589 tlsf_t *tlsf = (tlsf_t *) mem_pool;
590
591 tlsf->tlsf_signature = 0;
592
593 TLSF_DESTROY_LOCK(&tlsf->lock);
594
595}
596
597
598/******************************************************************/
599void *tlsf_malloc(size_t size)
600{
601/******************************************************************/
602 void *ret;
603
604#if USE_MMAP || USE_SBRK
605 if (!mp) {
606 size_t area_size;
607 void *area;
608
609 area_size = sizeof(tlsf_t) + BHDR_OVERHEAD * 8; /* Just a safety constant */
610 area_size = (area_size > DEFAULT_AREA_SIZE) ? area_size : DEFAULT_AREA_SIZE;
611 area = get_new_area(&area_size);
612 if (area == ((void *) ~0))
613 return NULL; /* Not enough system memory */
614 init_memory_pool(area_size, area);
615 }
616#endif
617
618 TLSF_ACQUIRE_LOCK(&((tlsf_t *)mp)->lock);
619
620 ret = malloc_ex(size, mp);
621
622 TLSF_RELEASE_LOCK(&((tlsf_t *)mp)->lock);
623
624 return ret;
625}
626
627/******************************************************************/
628void tlsf_free(void *ptr)
629{
630/******************************************************************/
631
632 TLSF_ACQUIRE_LOCK(&((tlsf_t *)mp)->lock);
633
634 free_ex(ptr, mp);
635
636 TLSF_RELEASE_LOCK(&((tlsf_t *)mp)->lock);
637
638}
639
640/******************************************************************/
641void *tlsf_realloc(void *ptr, size_t size)
642{
643/******************************************************************/
644 void *ret;
645
646#if USE_MMAP || USE_SBRK
647 if (!mp) {
648 return tlsf_malloc(size);
649 }
650#endif
651
652 TLSF_ACQUIRE_LOCK(&((tlsf_t *)mp)->lock);
653
654 ret = realloc_ex(ptr, size, mp);
655
656 TLSF_RELEASE_LOCK(&((tlsf_t *)mp)->lock);
657
658 return ret;
659}
660
661/******************************************************************/
662void *tlsf_calloc(size_t nelem, size_t elem_size)
663{
664/******************************************************************/
665 void *ret;
666
667 TLSF_ACQUIRE_LOCK(&((tlsf_t *)mp)->lock);
668
669 ret = calloc_ex(nelem, elem_size, mp);
670
671 TLSF_RELEASE_LOCK(&((tlsf_t *)mp)->lock);
672
673 return ret;
674}
675
676/******************************************************************/
677void *malloc_ex(size_t size, void *mem_pool)
678{
679/******************************************************************/
680 tlsf_t *tlsf = (tlsf_t *) mem_pool;
681 bhdr_t *b, *b2, *next_b;
682 int fl, sl;
683 size_t tmp_size;
684
685 size = (size < MIN_BLOCK_SIZE) ? MIN_BLOCK_SIZE : ROUNDUP_SIZE(size);
686
687 /* Rounding up the requested size and calculating fl and sl */
688 MAPPING_SEARCH(&size, &fl, &sl);
689
690 /* Searching a free block, recall that this function changes the values of fl and sl,
691 so they are not longer valid when the function fails */
692 b = FIND_SUITABLE_BLOCK(tlsf, &fl, &sl);
693
694#if USE_MMAP || USE_SBRK
695 if (!b) {
696 size_t area_size;
697 void *area;
698 /* Growing the pool size when needed */
699 area_size = size + BHDR_OVERHEAD * 8; /* size plus enough room for the requered headers. */
700 area_size = (area_size > DEFAULT_AREA_SIZE) ? area_size : DEFAULT_AREA_SIZE;
701 area = get_new_area(&area_size); /* Call sbrk or mmap */
702 if (area == ((void *) ~0))
703 return NULL; /* Not enough system memory */
704 add_new_area(area, area_size, mem_pool);
705 /* Rounding up the requested size and calculating fl and sl */
706 MAPPING_SEARCH(&size, &fl, &sl);
707 /* Searching a free block */
708 b = FIND_SUITABLE_BLOCK(tlsf, &fl, &sl);
709 }
710#endif
711 if (!b)
712 return NULL; /* Not found */
713
714 EXTRACT_BLOCK_HDR(b, tlsf, fl, sl);
715
716 /*-- found: */
717 next_b = GET_NEXT_BLOCK(b->ptr.buffer, b->size & BLOCK_SIZE);
718 /* Should the block be split? */
719 tmp_size = (b->size & BLOCK_SIZE) - size;
720 if (tmp_size >= sizeof(bhdr_t)) {
721 tmp_size -= BHDR_OVERHEAD;
722 b2 = GET_NEXT_BLOCK(b->ptr.buffer, size);
723 b2->size = tmp_size | FREE_BLOCK | PREV_USED;
724 next_b->prev_hdr = b2;
725 MAPPING_INSERT(tmp_size, &fl, &sl);
726 INSERT_BLOCK(b2, tlsf, fl, sl);
727
728 b->size = size | (b->size & PREV_STATE);
729 } else {
730 next_b->size &= (~PREV_FREE);
731 b->size &= (~FREE_BLOCK); /* Now it's used */
732 }
733
734 TLSF_ADD_SIZE(tlsf, b);
735
736 return (void *) b->ptr.buffer;
737}
738
739/******************************************************************/
740void free_ex(void *ptr, void *mem_pool)
741{
742/******************************************************************/
743 tlsf_t *tlsf = (tlsf_t *) mem_pool;
744 bhdr_t *b, *tmp_b;
745 int fl = 0, sl = 0;
746
747 if (!ptr) {
748 return;
749 }
750 b = (bhdr_t *) ((char *) ptr - BHDR_OVERHEAD);
751 b->size |= FREE_BLOCK;
752
753 TLSF_REMOVE_SIZE(tlsf, b);
754
755 b->ptr.free_ptr.prev = NULL;
756 b->ptr.free_ptr.next = NULL;
757 tmp_b = GET_NEXT_BLOCK(b->ptr.buffer, b->size & BLOCK_SIZE);
758 if (tmp_b->size & FREE_BLOCK) {
759 MAPPING_INSERT(tmp_b->size & BLOCK_SIZE, &fl, &sl);
760 EXTRACT_BLOCK(tmp_b, tlsf, fl, sl);
761 b->size += (tmp_b->size & BLOCK_SIZE) + BHDR_OVERHEAD;
762 }
763 if (b->size & PREV_FREE) {
764 tmp_b = b->prev_hdr;
765 MAPPING_INSERT(tmp_b->size & BLOCK_SIZE, &fl, &sl);
766 EXTRACT_BLOCK(tmp_b, tlsf, fl, sl);
767 tmp_b->size += (b->size & BLOCK_SIZE) + BHDR_OVERHEAD;
768 b = tmp_b;
769 }
770 MAPPING_INSERT(b->size & BLOCK_SIZE, &fl, &sl);
771 INSERT_BLOCK(b, tlsf, fl, sl);
772
773 tmp_b = GET_NEXT_BLOCK(b->ptr.buffer, b->size & BLOCK_SIZE);
774 tmp_b->size |= PREV_FREE;
775 tmp_b->prev_hdr = b;
776}
777
778/******************************************************************/
779void *realloc_ex(void *ptr, size_t new_size, void *mem_pool)
780{
781/******************************************************************/
782 tlsf_t *tlsf = (tlsf_t *) mem_pool;
783 void *ptr_aux;
784 unsigned int cpsize;
785 bhdr_t *b, *tmp_b, *next_b;
786 int fl, sl;
787 size_t tmp_size;
788
789 if (!ptr) {
790 if (new_size)
791 return (void *) malloc_ex(new_size, mem_pool);
792 if (!new_size)
793 return NULL;
794 } else if (!new_size) {
795 free_ex(ptr, mem_pool);
796 return NULL;
797 }
798
799 b = (bhdr_t *) ((char *) ptr - BHDR_OVERHEAD);
800 next_b = GET_NEXT_BLOCK(b->ptr.buffer, b->size & BLOCK_SIZE);
801 new_size = (new_size < MIN_BLOCK_SIZE) ? MIN_BLOCK_SIZE : ROUNDUP_SIZE(new_size);
802 tmp_size = (b->size & BLOCK_SIZE);
803 if (new_size <= tmp_size) {
804 TLSF_REMOVE_SIZE(tlsf, b);
805 if (next_b->size & FREE_BLOCK) {
806 MAPPING_INSERT(next_b->size & BLOCK_SIZE, &fl, &sl);
807 EXTRACT_BLOCK(next_b, tlsf, fl, sl);
808 tmp_size += (next_b->size & BLOCK_SIZE) + BHDR_OVERHEAD;
809 next_b = GET_NEXT_BLOCK(next_b->ptr.buffer, next_b->size & BLOCK_SIZE);
810 /* We allways reenter this free block because tmp_size will
811 be greater then sizeof (bhdr_t) */
812 }
813 tmp_size -= new_size;
814 if (tmp_size >= sizeof(bhdr_t)) {
815 tmp_size -= BHDR_OVERHEAD;
816 tmp_b = GET_NEXT_BLOCK(b->ptr.buffer, new_size);
817 tmp_b->size = tmp_size | FREE_BLOCK | PREV_USED;
818 next_b->prev_hdr = tmp_b;
819 next_b->size |= PREV_FREE;
820 MAPPING_INSERT(tmp_size, &fl, &sl);
821 INSERT_BLOCK(tmp_b, tlsf, fl, sl);
822 b->size = new_size | (b->size & PREV_STATE);
823 }
824 TLSF_ADD_SIZE(tlsf, b);
825 return (void *) b->ptr.buffer;
826 }
827 if ((next_b->size & FREE_BLOCK)) {
828 if (new_size <= (tmp_size + (next_b->size & BLOCK_SIZE))) {
829 TLSF_REMOVE_SIZE(tlsf, b);
830 MAPPING_INSERT(next_b->size & BLOCK_SIZE, &fl, &sl);
831 EXTRACT_BLOCK(next_b, tlsf, fl, sl);
832 b->size += (next_b->size & BLOCK_SIZE) + BHDR_OVERHEAD;
833 next_b = GET_NEXT_BLOCK(b->ptr.buffer, b->size & BLOCK_SIZE);
834 next_b->prev_hdr = b;
835 next_b->size &= ~PREV_FREE;
836 tmp_size = (b->size & BLOCK_SIZE) - new_size;
837 if (tmp_size >= sizeof(bhdr_t)) {
838 tmp_size -= BHDR_OVERHEAD;
839 tmp_b = GET_NEXT_BLOCK(b->ptr.buffer, new_size);
840 tmp_b->size = tmp_size | FREE_BLOCK | PREV_USED;
841 next_b->prev_hdr = tmp_b;
842 next_b->size |= PREV_FREE;
843 MAPPING_INSERT(tmp_size, &fl, &sl);
844 INSERT_BLOCK(tmp_b, tlsf, fl, sl);
845 b->size = new_size | (b->size & PREV_STATE);
846 }
847 TLSF_ADD_SIZE(tlsf, b);
848 return (void *) b->ptr.buffer;
849 }
850 }
851
852 ptr_aux = malloc_ex(new_size, mem_pool);
853
854 cpsize = ((b->size & BLOCK_SIZE) > new_size) ? new_size : (b->size & BLOCK_SIZE);
855
856 memcpy(ptr_aux, ptr, cpsize);
857
858 free_ex(ptr, mem_pool);
859 return ptr_aux;
860}
861
862
863/******************************************************************/
864void *calloc_ex(size_t nelem, size_t elem_size, void *mem_pool)
865{
866/******************************************************************/
867 void *ptr;
868
869 if (nelem <= 0 || elem_size <= 0)
870 return NULL;
871
872 if (!(ptr = malloc_ex(nelem * elem_size, mem_pool)))
873 return NULL;
874 memset(ptr, 0, nelem * elem_size);
875
876 return ptr;
877}
878
879
880
881#if _DEBUG_TLSF_
882
883/*************** DEBUG FUNCTIONS **************/
884
885/* The following functions have been designed to ease the debugging of */
886/* the TLSF structure. For non-developing purposes, it may be they */
887/* haven't too much worth. To enable them, _DEBUG_TLSF_ must be set. */
888
889extern void dump_memory_region(unsigned char *mem_ptr, unsigned int size);
890extern void print_block(bhdr_t * b);
891extern void print_tlsf(tlsf_t * tlsf);
892void print_all_blocks(tlsf_t * tlsf);
893
894void dump_memory_region(unsigned char *mem_ptr, unsigned int size)
895{
896
897 unsigned long begin = (unsigned long) mem_ptr;
898 unsigned long end = (unsigned long) mem_ptr + size;
899 int column = 0;
900
901 begin >>= 2;
902 begin <<= 2;
903
904 end >>= 2;
905 end++;
906 end <<= 2;
907
908 PRINT_MSG("\nMemory region dumped: 0x%lx - 0x%lx\n\n", begin, end);
909
910 column = 0;
911 PRINT_MSG("0x%lx ", begin);
912
913 while (begin < end) {
914 if (((unsigned char *) begin)[0] == 0)
915 PRINT_MSG("00");
916 else
917 PRINT_MSG("%02x", ((unsigned char *) begin)[0]);
918 if (((unsigned char *) begin)[1] == 0)
919 PRINT_MSG("00 ");
920 else
921 PRINT_MSG("%02x ", ((unsigned char *) begin)[1]);
922 begin += 2;
923 column++;
924 if (column == 8) {
925 PRINT_MSG("\n0x%lx ", begin);
926 column = 0;
927 }
928
929 }
930 PRINT_MSG("\n\n");
931}
932
933void print_block(bhdr_t * b)
934{
935 if (!b)
936 return;
937 PRINT_MSG(">> [%p] (", b);
938 if ((b->size & BLOCK_SIZE))
939 PRINT_MSG("%lu bytes, ", (unsigned long) (b->size & BLOCK_SIZE));
940 else
941 PRINT_MSG("sentinel, ");
942 if ((b->size & BLOCK_STATE) == FREE_BLOCK)
943 PRINT_MSG("free [%p, %p], ", b->ptr.free_ptr.prev, b->ptr.free_ptr.next);
944 else
945 PRINT_MSG("used, ");
946 if ((b->size & PREV_STATE) == PREV_FREE)
947 PRINT_MSG("prev. free [%p])\n", b->prev_hdr);
948 else
949 PRINT_MSG("prev used)\n");
950}
951
952void print_tlsf(tlsf_t * tlsf)
953{
954 bhdr_t *next;
955 int i, j;
956
957 PRINT_MSG("\nTLSF at %p\n", tlsf);
958
959 PRINT_MSG("FL bitmap: 0x%x\n\n", (unsigned) tlsf->fl_bitmap);
960
961 for (i = 0; i < REAL_FLI; i++) {
962 if (tlsf->sl_bitmap[i])
963 PRINT_MSG("SL bitmap 0x%x\n", (unsigned) tlsf->sl_bitmap[i]);
964 for (j = 0; j < MAX_SLI; j++) {
965 next = tlsf->matrix[i][j];
966 if (next)
967 PRINT_MSG("-> [%d][%d]\n", i, j);
968 while (next) {
969 print_block(next);
970 next = next->ptr.free_ptr.next;
971 }
972 }
973 }
974}
975
976void print_all_blocks(tlsf_t * tlsf)
977{
978 area_info_t *ai;
979 bhdr_t *next;
980 PRINT_MSG("\nTLSF at %p\nALL BLOCKS\n\n", tlsf);
981 ai = tlsf->area_head;
982 while (ai) {
983 next = (bhdr_t *) ((char *) ai - BHDR_OVERHEAD);
984 while (next) {
985 print_block(next);
986 if ((next->size & BLOCK_SIZE))
987 next = GET_NEXT_BLOCK(next->ptr.buffer, next->size & BLOCK_SIZE);
988 else
989 next = NULL;
990 }
991 ai = ai->next;
992 }
993}
994
995#endif
diff --git a/apps/plugins/pdbox/TLSF-2.4.4/src/tlsf.h b/apps/plugins/pdbox/TLSF-2.4.4/src/tlsf.h
new file mode 100644
index 0000000000..5d016f4369
--- /dev/null
+++ b/apps/plugins/pdbox/TLSF-2.4.4/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-17 22:07:02 +0000