diff options
author | Peter D'Hoye <peter.dhoye@gmail.com> | 2009-07-21 14:01:51 +0000 |
---|---|---|
committer | Peter D'Hoye <peter.dhoye@gmail.com> | 2009-07-21 14:01:51 +0000 |
commit | 1a4b0cadd66849f83eecd6be2c59df234a4eabc8 (patch) | |
tree | 078d6bf9c840f98ec6ab56fa746163ee85b54b98 /apps | |
parent | c8195d80bf750d13ec37139a24bec915144d3109 (diff) | |
download | rockbox-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 (limited to 'apps')
-rw-r--r-- | apps/plugins/pdbox/TLSF-2.4.4/COPYING | 23 | ||||
-rw-r--r-- | apps/plugins/pdbox/TLSF-2.4.4/Changelog | 119 | ||||
-rw-r--r-- | apps/plugins/pdbox/TLSF-2.4.4/README | 163 | ||||
-rw-r--r-- | apps/plugins/pdbox/TLSF-2.4.4/TODO | 9 | ||||
-rw-r--r-- | apps/plugins/pdbox/TLSF-2.4.4/src/target.h | 12 | ||||
-rw-r--r-- | apps/plugins/pdbox/TLSF-2.4.4/src/tlsf.c | 995 | ||||
-rw-r--r-- | apps/plugins/pdbox/TLSF-2.4.4/src/tlsf.h | 39 |
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 | |||
3 | TLSF is released as LGPL and GPL. A copy of both licences can be found in this | ||
4 | directoy. For the GPL licence, the following exception applies. | ||
5 | |||
6 | |||
7 | TLSF is free software; you can redistribute it and/or modify it under terms of | ||
8 | the GNU General Public License as published by the Free Software Foundation; | ||
9 | either version 2, or (at your option) any later version. TLSF is distributed | ||
10 | in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the | ||
11 | implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See | ||
12 | the GNU General Public License for more details. You should have received a | ||
13 | copy of the GNU General Public License along with TLSF; see file COPYING. If | ||
14 | not, write to the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, | ||
15 | USA. | ||
16 | |||
17 | As a special exception, including TLSF header files in a file, or linking with | ||
18 | other files objects to produce an executable application, is merely considered | ||
19 | normal use of the library, and does *not* fall under the heading of "derived | ||
20 | work". Therfore does not by itself cause the resulting executable application | ||
21 | to be covered by the GNU General Public License. This exception does not | ||
22 | however invalidate any other reasons why the executable file might be covered | ||
23 | by 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 | |||
2 | TLSF Memory Storage allocator implementation. | ||
3 | Version 2.4 Feb 2008 | ||
4 | |||
5 | Authors: Miguel Masmano, Ismael Ripoll & Alfons Crespo. | ||
6 | Copyright UPVLC, OCERA Consortium. | ||
7 | |||
8 | TLSF is released in the GPL/LGPL licence. The exact terms of the licence | ||
9 | are described in the COPYING file. | ||
10 | |||
11 | This component provides basic memory allocation functions: | ||
12 | malloc and free, as defined in the standard "C" library. | ||
13 | |||
14 | This allocator was designed to provide real-time performance, that is: | ||
15 | 1.- Bounded time malloc and free. | ||
16 | 2.- Fast response time. | ||
17 | 3.- Efficient memory management, that is low fragmentation. | ||
18 | |||
19 | |||
20 | The worst response time for both malloc and free is O(1). | ||
21 | |||
22 | |||
23 | |||
24 | How to use it: | ||
25 | |||
26 | This code is prepared to be used as a stand-alone code that can be | ||
27 | linked with a regular application or it can be compiled to be a Linux | ||
28 | module (which required the BigPhysicalArea patch). Initially the | ||
29 | module was designed to work jointly with RTLinux-GPL, but it can be | ||
30 | used as a stand alone Linux module. | ||
31 | |||
32 | When compiled as a regular linux process the API is: | ||
33 | |||
34 | Initialisation and destruction functions | ||
35 | ---------------------------------------- | ||
36 | |||
37 | init_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 | |||
42 | Request and release functions | ||
43 | ----------------------------- | ||
44 | |||
45 | As can be seen, there are two functions for each traditional memory | ||
46 | allocation function (malloc, free, realloc, and calloc). One with the | ||
47 | prefix "tlsf_" and the other with the suffix "_ex". | ||
48 | |||
49 | The versions with the prefix "tlsf_" provides the expected behaviour, | ||
50 | that is, allocating/releasing memory from the default memory pool. The | ||
51 | default memory pool is the last pool initialised by the | ||
52 | init_memory_pool function. | ||
53 | |||
54 | On 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 | |||
68 | EXAMPLE OF USE: | ||
69 | |||
70 | char 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 | |||
88 | Growing the memory pool | ||
89 | ----------------------- | ||
90 | |||
91 | Starting from the version 2.4, the function add_new_area adds an | ||
92 | memory area to an existing memory pool. | ||
93 | |||
94 | - size_t add_new_area(void *, size_t, void *); | ||
95 | |||
96 | This feature is pretty useful when an existing memory pool is running | ||
97 | low and we want to add more free memory to it. | ||
98 | EXAMPLE OF USE: | ||
99 | |||
100 | char memory_pool[1024*1024]; | ||
101 | char 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 | |||
122 | SBRK and MMAP support | ||
123 | --------------------- | ||
124 | |||
125 | The version 2.4 can use the functions SBRK and MMAP to _automatically_ | ||
126 | growing the memory pool, before running out of memory. | ||
127 | |||
128 | So, when this feature is enabled, unless the operating system were out | ||
129 | of memory, a malloc operation would not fail due to an "out-of-memory" | ||
130 | error. | ||
131 | |||
132 | To 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 | |||
137 | EXAMPLE OF USE: | ||
138 | |||
139 | gcc -o tlsf.o -O2 -Wall -DUSE_MMAP=1 -DUSE_SBRK=1 | ||
140 | |||
141 | --- | ||
142 | |||
143 | If the sbrk/mmap support is enabled and we are _only_ going to use one | ||
144 | memory pool, it is not necessary to call init_memory_pool | ||
145 | |||
146 | EXAMPLE 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 | |||
161 | This work has been supported by the followin projects: | ||
162 | EUROPEAN: IST-2001-35102(OCERA) http://www.ocera.org. | ||
163 | SPANISH: 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 @@ | |||
1 | To 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 | |||
170 | typedef unsigned int u32_t; /* NOTE: Make sure that this type is 4 bytes long on your computer */ | ||
171 | typedef unsigned char u8_t; /* NOTE: Make sure that this type is 1 byte on your computer */ | ||
172 | |||
173 | typedef struct free_ptr_struct { | ||
174 | struct bhdr_struct *prev; | ||
175 | struct bhdr_struct *next; | ||
176 | } free_ptr_t; | ||
177 | |||
178 | typedef 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 | |||
193 | typedef struct area_info_struct { | ||
194 | bhdr_t *end; | ||
195 | struct area_info_struct *next; | ||
196 | } area_info_t; | ||
197 | |||
198 | typedef 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 | /******************************************************************/ | ||
230 | static __inline__ void set_bit(int nr, u32_t * addr); | ||
231 | static __inline__ void clear_bit(int nr, u32_t * addr); | ||
232 | static __inline__ int ls_bit(int x); | ||
233 | static __inline__ int ms_bit(int x); | ||
234 | static __inline__ void MAPPING_SEARCH(size_t * _r, int *_fl, int *_sl); | ||
235 | static __inline__ void MAPPING_INSERT(size_t _r, int *_fl, int *_sl); | ||
236 | static __inline__ bhdr_t *FIND_SUITABLE_BLOCK(tlsf_t * _tlsf, int *_fl, int *_sl); | ||
237 | static __inline__ bhdr_t *process_area(void *area, size_t size); | ||
238 | #if USE_SBRK || USE_MMAP | ||
239 | static __inline__ void *get_new_area(size_t * size); | ||
240 | #endif | ||
241 | |||
242 | static 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 | |||
269 | static __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 | |||
278 | static __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 | |||
287 | static __inline__ void set_bit(int nr, u32_t * addr) | ||
288 | { | ||
289 | addr[nr >> 5] |= 1 << (nr & 0x1f); | ||
290 | } | ||
291 | |||
292 | static __inline__ void clear_bit(int nr, u32_t * addr) | ||
293 | { | ||
294 | addr[nr >> 5] &= ~(1 << (nr & 0x1f)); | ||
295 | } | ||
296 | |||
297 | static __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 | |||
317 | static __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 | |||
330 | static __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 | ||
391 | static __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 | |||
410 | static __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 | |||
435 | static char *mp = NULL; /* Default memory pool. */ | ||
436 | |||
437 | /******************************************************************/ | ||
438 | size_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 | /******************************************************************/ | ||
485 | size_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 | /******************************************************************/ | ||
564 | size_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 | /******************************************************************/ | ||
575 | size_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 | /******************************************************************/ | ||
586 | void 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 | /******************************************************************/ | ||
599 | void *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 | /******************************************************************/ | ||
628 | void 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 | /******************************************************************/ | ||
641 | void *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 | /******************************************************************/ | ||
662 | void *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 | /******************************************************************/ | ||
677 | void *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 | /******************************************************************/ | ||
740 | void 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 | /******************************************************************/ | ||
779 | void *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 | /******************************************************************/ | ||
864 | void *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 | |||
889 | extern void dump_memory_region(unsigned char *mem_ptr, unsigned int size); | ||
890 | extern void print_block(bhdr_t * b); | ||
891 | extern void print_tlsf(tlsf_t * tlsf); | ||
892 | void print_all_blocks(tlsf_t * tlsf); | ||
893 | |||
894 | void 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 | |||
933 | void 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 | |||
952 | void 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 | |||
976 | void 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 | |||
24 | extern size_t init_memory_pool(size_t, void *); | ||
25 | extern size_t get_used_size(void *); | ||
26 | extern size_t get_max_size(void *); | ||
27 | extern void destroy_memory_pool(void *); | ||
28 | extern size_t add_new_area(void *, size_t, void *); | ||
29 | extern void *malloc_ex(size_t, void *); | ||
30 | extern void free_ex(void *, void *); | ||
31 | extern void *realloc_ex(void *, size_t, void *); | ||
32 | extern void *calloc_ex(size_t, size_t, void *); | ||
33 | |||
34 | extern void *tlsf_malloc(size_t size); | ||
35 | extern void tlsf_free(void *ptr); | ||
36 | extern void *tlsf_realloc(void *ptr, size_t size); | ||
37 | extern void *tlsf_calloc(size_t nelem, size_t elem_size); | ||
38 | |||
39 | #endif | ||