diff options
author | Magnus Holmgren <magnushol@gmail.com> | 2009-08-29 12:23:40 +0000 |
---|---|---|
committer | Magnus Holmgren <magnushol@gmail.com> | 2009-08-29 12:23:40 +0000 |
commit | 3fad1523c78e13f61283d7b81e0990f8803dc2f2 (patch) | |
tree | 6cdbc97688e782d13cf0ee406ac8356a2ae98047 /apps/codecs/lib/tlsf | |
parent | 260ed991392a387ff9ae5bbd8dba7afd10c1faef (diff) | |
download | rockbox-3fad1523c78e13f61283d7b81e0990f8803dc2f2.tar.gz rockbox-3fad1523c78e13f61283d7b81e0990f8803dc2f2.zip |
FS#10466: Introduce a real malloc for tremor.
git-svn-id: svn://svn.rockbox.org/rockbox/trunk@22528 a1c6a512-1295-4272-9138-f99709370657
Diffstat (limited to 'apps/codecs/lib/tlsf')
-rw-r--r-- | apps/codecs/lib/tlsf/COPYING | 23 | ||||
-rw-r--r-- | apps/codecs/lib/tlsf/Changelog | 119 | ||||
-rw-r--r-- | apps/codecs/lib/tlsf/README | 163 | ||||
-rw-r--r-- | apps/codecs/lib/tlsf/SOURCES | 3 | ||||
-rw-r--r-- | apps/codecs/lib/tlsf/TODO | 9 | ||||
-rw-r--r-- | apps/codecs/lib/tlsf/libtlsf.make | 28 |
6 files changed, 345 insertions, 0 deletions
diff --git a/apps/codecs/lib/tlsf/COPYING b/apps/codecs/lib/tlsf/COPYING new file mode 100644 index 0000000000..78fdbdc061 --- /dev/null +++ b/apps/codecs/lib/tlsf/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/codecs/lib/tlsf/Changelog b/apps/codecs/lib/tlsf/Changelog new file mode 100644 index 0000000000..0cdb34a8ab --- /dev/null +++ b/apps/codecs/lib/tlsf/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/codecs/lib/tlsf/README b/apps/codecs/lib/tlsf/README new file mode 100644 index 0000000000..d755905b16 --- /dev/null +++ b/apps/codecs/lib/tlsf/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/codecs/lib/tlsf/SOURCES b/apps/codecs/lib/tlsf/SOURCES new file mode 100644 index 0000000000..eb9d93756e --- /dev/null +++ b/apps/codecs/lib/tlsf/SOURCES | |||
@@ -0,0 +1,3 @@ | |||
1 | #if CONFIG_CODEC == SWCODEC /* software codec platforms */ | ||
2 | src/tlsf.c | ||
3 | #endif | ||
diff --git a/apps/codecs/lib/tlsf/TODO b/apps/codecs/lib/tlsf/TODO new file mode 100644 index 0000000000..d7c07b8421 --- /dev/null +++ b/apps/codecs/lib/tlsf/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/codecs/lib/tlsf/libtlsf.make b/apps/codecs/lib/tlsf/libtlsf.make new file mode 100644 index 0000000000..464487f87f --- /dev/null +++ b/apps/codecs/lib/tlsf/libtlsf.make | |||
@@ -0,0 +1,28 @@ | |||
1 | # __________ __ ___. | ||
2 | # Open \______ \ ____ ____ | | _\_ |__ _______ ___ | ||
3 | # Source | _// _ \_/ ___\| |/ /| __ \ / _ \ \/ / | ||
4 | # Jukebox | | ( <_> ) \___| < | \_\ ( <_> > < < | ||
5 | # Firmware |____|_ /\____/ \___ >__|_ \|___ /\____/__/\_ \ | ||
6 | # \/ \/ \/ \/ \/ | ||
7 | # $Id$ | ||
8 | # | ||
9 | |||
10 | TLSFLIB := $(CODECDIR)/libtlsf.a | ||
11 | TLSFLIB_SRC := $(call preprocess, $(APPSDIR)/codecs/lib/tlsf/SOURCES) | ||
12 | TLSFLIB_OBJ := $(call c2obj, $(TLSFLIB_SRC)) | ||
13 | OTHER_SRC += $(TLSFLIB_SRC) | ||
14 | |||
15 | $(TLSFLIB): $(TLSFLIB_OBJ) | ||
16 | $(SILENT)$(shell rm -f $@) | ||
17 | $(call PRINTS,AR $(@F))$(AR) rcs $@ $^ >/dev/null | ||
18 | |||
19 | TLSFLIBFLAGS = $(CODECFLAGS) -ffunction-sections | ||
20 | |||
21 | ifdef SIMVER | ||
22 | TLSFLIBFLAGS += -DTLSF_STATISTIC=1 | ||
23 | endif | ||
24 | |||
25 | $(CODECDIR)/lib/tlsf/src/%.o: $(APPSDIR)/codecs/lib/tlsf/src/%.c | ||
26 | $(SILENT)mkdir -p $(dir $@) | ||
27 | $(call PRINTS,CC $(subst $(ROOTDIR)/,,$<))$(CC) \ | ||
28 | -I$(dir $<) $(TLSFLIBFLAGS) -c $< -o $@ | ||