diff options
Diffstat (limited to 'firmware')
-rw-r--r-- | firmware/malloc/Makefile | 40 | ||||
-rw-r--r-- | firmware/malloc/README | 21 | ||||
-rw-r--r-- | firmware/malloc/THOUGHTS | 170 | ||||
-rw-r--r-- | firmware/malloc/bmalloc.c | 386 | ||||
-rw-r--r-- | firmware/malloc/bmalloc.h | 30 | ||||
-rw-r--r-- | firmware/malloc/bysize.c | 451 | ||||
-rw-r--r-- | firmware/malloc/bysize.h | 24 | ||||
-rw-r--r-- | firmware/malloc/dmalloc.c | 634 | ||||
-rw-r--r-- | firmware/malloc/dmalloc.h | 36 |
9 files changed, 0 insertions, 1792 deletions
diff --git a/firmware/malloc/Makefile b/firmware/malloc/Makefile deleted file mode 100644 index 4524d0630b..0000000000 --- a/firmware/malloc/Makefile +++ /dev/null | |||
@@ -1,40 +0,0 @@ | |||
1 | # __________ __ ___. | ||
2 | # Open \______ \ ____ ____ | | _\_ |__ _______ ___ | ||
3 | # Source | _// _ \_/ ___\| |/ /| __ \ / _ \ \/ / | ||
4 | # Jukebox | | ( <_> ) \___| < | \_\ ( <_> > < < | ||
5 | # Firmware |____|_ /\____/ \___ >__|_ \|___ /\____/__/\_ \ | ||
6 | # \/ \/ \/ \/ \/ | ||
7 | # $Id$ | ||
8 | # | ||
9 | # Copyright (C) 2002 by Daniel Stenberg | ||
10 | # | ||
11 | # All files in this archive are subject to the GNU General Public License. | ||
12 | # See the file COPYING in the source tree root for full license agreement. | ||
13 | # | ||
14 | # This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY | ||
15 | # KIND, either express or implied. | ||
16 | # | ||
17 | |||
18 | TARGET = libdmalloc.a | ||
19 | |||
20 | LIBOBJS = dmalloc.o bmalloc.o bysize.o | ||
21 | |||
22 | # define this to talk a lot in runtime | ||
23 | # -DDEBUG_VERBOSE | ||
24 | CFLAGS = -g -W -Wall -DDEBUG_MALLOC | ||
25 | CC = gcc | ||
26 | AR = ar | ||
27 | |||
28 | LDFLAGS = -L. -ldmalloc | ||
29 | |||
30 | all: $(TARGET) | ||
31 | |||
32 | clean: | ||
33 | rm -f core *~ $(TARGET) $(LIBOBJS) | ||
34 | |||
35 | $(TARGET): $(LIBOBJS) | ||
36 | $(AR) ruv $(TARGET) $(LIBOBJS) | ||
37 | |||
38 | bmalloc.o: bmalloc.c bysize.h | ||
39 | bysize.o: bysize.c | ||
40 | dmalloc.o: dmalloc.c | ||
diff --git a/firmware/malloc/README b/firmware/malloc/README deleted file mode 100644 index 336bd571ae..0000000000 --- a/firmware/malloc/README +++ /dev/null | |||
@@ -1,21 +0,0 @@ | |||
1 | Package: dbestfit - a dynamic best-fit memory allocator | ||
2 | Date: 1996 - 2002 | ||
3 | Version: 3.3 | ||
4 | Author: Daniel Stenberg <daniel@haxx.se> | ||
5 | License: MIT originally, files in the Rockbox project are GPL licensed. | ||
6 | |||
7 | I wrote the dmalloc part for small allocation sizes to improve the behavior | ||
8 | of the built-in (first-fit) allocator found in pSOS, during late 1996 and | ||
9 | spring 1997. | ||
10 | |||
11 | I wrote the bmalloc part (best-fit with optional splay-tree sorting) just for | ||
12 | the fun of it and to see how good malloc() implementation I could make. The | ||
13 | quality of my implementation is still left to be judged in real-world tests. | ||
14 | |||
15 | TODO: | ||
16 | * Remove the final not-so-very-nice loop in dmalloc.c that checks for a block | ||
17 | with free fragments (when the list gets longer too much time might be spent | ||
18 | in that loop). | ||
19 | |||
20 | * Make a separate application that samples the memory usage of a program | ||
21 | and is capable of replaying it (in order to test properly). | ||
diff --git a/firmware/malloc/THOUGHTS b/firmware/malloc/THOUGHTS deleted file mode 100644 index 27517361da..0000000000 --- a/firmware/malloc/THOUGHTS +++ /dev/null | |||
@@ -1,170 +0,0 @@ | |||
1 | ==================================== | ||
2 | Memory Allocation Algorithm Theories | ||
3 | ==================================== | ||
4 | |||
5 | GOAL | ||
6 | It is intended to be a 100% working memory allocation system. It should be | ||
7 | capable of replacing an ordinary Operating System's own routines. It should | ||
8 | work good in a multitasking, shared memory, non-virtual memory environment | ||
9 | without clogging the memory. Primary aimed for small machines, CPUs and | ||
10 | memory amounts. | ||
11 | |||
12 | I use a best-fit algorithm with a slight overhead in order to increase speed | ||
13 | a lot. It should remain scalable and work good with very large amount of | ||
14 | memory and free/used memory blocks too. | ||
15 | |||
16 | TERMINOLOGY | ||
17 | |||
18 | FRAGMENT - small identically sized parts of a larger BLOCK, they are _not_ | ||
19 | allocated when traversed in lists etc | ||
20 | BLOCK - large memory area, if used for FRAGMENTS, they are linked in a | ||
21 | lists. One list for each FRAGMENT size supported. | ||
22 | TOP - head struct that holds information about and points to a chain | ||
23 | of BLOCKS for a particular FRAGMENT size. | ||
24 | CHUNK - a contiguous area of free memory | ||
25 | |||
26 | MEMORY SYSTEM | ||
27 | |||
28 | We split the system in two parts. One part allocates small memory amounts | ||
29 | and one part allocates large memory amounts, but all allocations are done | ||
30 | "through" the small-part-system. There is an option to use only the small | ||
31 | system (and thus use the OS for large blocks) or the complete package. | ||
32 | |||
33 | ############################################################################## | ||
34 | SMALL SIZE ALLOCATIONS | ||
35 | ############################################################################## | ||
36 | |||
37 | Keywords for this system is 'Deferred Coalescing' and 'quick lists'. | ||
38 | |||
39 | ALLOC | ||
40 | |||
41 | * Small allocations are "aligned" upwards to a set of preset sizes. In the | ||
42 | current implementation I use 20, 28, 52, 116, 312, 580, 1016, 2032 bytes. | ||
43 | Memory allocations of these sizes are referred to as FRAGMENTS. | ||
44 | (The reason for these specific sizes is the requirement that they must be | ||
45 | 32-bit aligned and fit as good as possible within 4064 bytes.) | ||
46 | |||
47 | * Allocations larger than 2032 will get a BLOCK for that allocation only. | ||
48 | |||
49 | * Each of these sizes has it's own TOP. When a FRAGMENT is requested, a | ||
50 | larger BLOCK will be allocated and divided into many FRAGMENTS (all of the | ||
51 | same size). TOP points to a list with BLOCKS that contains FRAGMENTS of | ||
52 | the same size. Each BLOCK has a 'number of free FRAGMENTS' counter and so | ||
53 | has each TOP (for the entire chain). | ||
54 | |||
55 | * A BLOCK is around 4064 bytes plus the size of the information header. This | ||
56 | size is adjusted to make the allocation of the big block not require more | ||
57 | than 4096 bytes. (This might not be so easy to be sure of, if you don't | ||
58 | know how the big-block system works, but the BMALLOC system uses an | ||
59 | extra header of 12 bytes and the header for the FRAGMENT BLOCK is 20 bytes | ||
60 | in a general 32-bit environment.) | ||
61 | |||
62 | * In case the allocation of a BLOCK fails when a FRAGMENT is required, the | ||
63 | next size of FRAGMENTS will be checked for a free FRAGMENT. First when the | ||
64 | larger size lists have been tested without success it will fail for real. | ||
65 | |||
66 | FREE | ||
67 | |||
68 | * When FRAGMENTS are freed so that a BLOCK becomes non-used, it is returned | ||
69 | to the system. | ||
70 | |||
71 | * FREEing a fragment adds the buffer in a LIFO-order. That means that the | ||
72 | next request for a fragment from the same list, the last freed buffer will | ||
73 | be returned first. | ||
74 | |||
75 | REALLOC | ||
76 | |||
77 | * REALLOCATION of a FRAGMENT does first check if the new size would fit | ||
78 | within the same FRAGMENT and if it would use the same FRAGMENT size. If it | ||
79 | does and would, the same pointer is returned. | ||
80 | |||
81 | OVERHEAD | ||
82 | |||
83 | Yes, there is an overhead on small allocations (internal fragmentation). | ||
84 | Yet, I do believe that small allocations more often than larger ones are | ||
85 | used dynamically. I believe that a large overhead is not a big problem if it | ||
86 | remains only for a while. The big gain is with the extreme speed we can GET | ||
87 | and RETURN small allocations. This has yet to be proven. I am open to other | ||
88 | systems of dealing with the small ones, but I don`t believe in using the | ||
89 | same system for all sizes of allocations. | ||
90 | |||
91 | IMPROVEMENT | ||
92 | |||
93 | An addition to the above described algorithm is the `save-empty-BLOCKS-a- | ||
94 | while-afterwards`. It will be used when the last used FRAGMENT within a | ||
95 | BLOCK is freed. The BLOCK will then not get returned to the system until "a | ||
96 | few more" FRAGMENTS have been freed in case the last [few] freed FRAGMENTS | ||
97 | are allocated yet again (and thus prevent the huge overhead of making | ||
98 | FRAGMENTS in a BLOCK). The "only" drawback of such a SEBAWA concept is | ||
99 | that it would mean an even bigger overhead... | ||
100 | |||
101 | HEADERS (in allocated data) | ||
102 | |||
103 | FRAGMENTS - 32-bit pointer to its parent BLOCK (lowest bit must be 0) | ||
104 | BLOCK - 32-bit size (lowest bit must be 1 to separate this from | ||
105 | FRAGMENTS) | ||
106 | |||
107 | ############################################################################## | ||
108 | LARGER ALLOCATIONS | ||
109 | ############################################################################## | ||
110 | |||
111 | If the requested size is larger than the largest FRAGMENT size supported, | ||
112 | the allocation will be made for this memory area alone, or if a BLOCK is | ||
113 | allocated to fit lots of FRAGMENTS a large block is also desired. | ||
114 | |||
115 | * We add memory to the "system" with the add_pool() function call. It | ||
116 | specifies the start and size of the new block of memory that will be | ||
117 | used in this memory allocation system. Several add_pool() calls are | ||
118 | supported and they may or may not add contiguous memory. | ||
119 | |||
120 | * Make all blocks get allocated aligned to BLOCKSIZE (sometimes referred to | ||
121 | as 'grain size'), 64 bytes in my implementation. Reports tell us there is | ||
122 | no real gain in increasing the size of the align. | ||
123 | |||
124 | * We link *all* pieces of memory (AREAS), free or not free. We keep the list | ||
125 | in address order and thus when a FREE() occurs we know instantly if there | ||
126 | are FREE CHUNKS wall-to-wall. No list "travels" needed. Requires some | ||
127 | extra space in every allocated BLOCK. Still needs to put the new CHUNK in | ||
128 | the right place in size-sorted list/tree. All memory areas, allocated or | ||
129 | not, contain the following header: | ||
130 | - size of this memory area (31 bits) | ||
131 | - FREE status (1 bit) | ||
132 | - pointer to the next AREA closest in memory (32 bits) | ||
133 | - pointer to the prev AREA closest in memory (32 bits) | ||
134 | (Totally 12 bytes) | ||
135 | |||
136 | * Sort all FREE CHUNKS in size-order. We use a SPLAY TREE algorithm for | ||
137 | maximum speed. Data/structs used for the size-sorting functions are kept | ||
138 | in an abstraction layer away from this since it is really not changing | ||
139 | anything (except executing speed). | ||
140 | |||
141 | ALLOC (RSIZE - requested size, aligned properly) | ||
142 | |||
143 | * Fetch a CHUNK that RSIZE fits within. If the found CHUNK is larger than | ||
144 | RSIZE, split it and return the RSIZE to the caller. Link the new CHUNK | ||
145 | into the list/tree. | ||
146 | |||
147 | FREE (AREA - piece of memory that is returned to the system) | ||
148 | |||
149 | * Since the allocated BLOCK has kept its link-pointers, we can without | ||
150 | checking any list instantly see if there are any FREE CHUNKS that are | ||
151 | wall-to-wall with the AREA (both sides). If the AREA *is* wall-to-wall | ||
152 | with one or two CHUNKS that or they are unlinked from the lists, enlarged | ||
153 | and re-linked into the lists. | ||
154 | |||
155 | REALLOC | ||
156 | |||
157 | * There IS NO realloc() of large blocks, they are performed in the previous | ||
158 | layer (dmalloc). | ||
159 | |||
160 | |||
161 | ############################################################################## | ||
162 | FURTHER READING | ||
163 | ############################################################################## | ||
164 | |||
165 | * "Dynamic Storage Allocation: A Survey and Critical Review" (Paul R. Wilson, | ||
166 | Mark S. Johnstone, Michael Neely, David Boles) | ||
167 | ftp://ftp.cs.utexas.edu/pub/garbage/allocsrv.ps | ||
168 | |||
169 | * "A Memory Allocator" (Doug Lea) | ||
170 | http://g.oswego.edu/dl/html/malloc.html | ||
diff --git a/firmware/malloc/bmalloc.c b/firmware/malloc/bmalloc.c deleted file mode 100644 index 470ee49840..0000000000 --- a/firmware/malloc/bmalloc.c +++ /dev/null | |||
@@ -1,386 +0,0 @@ | |||
1 | /*************************************************************************** | ||
2 | * __________ __ ___. | ||
3 | * Open \______ \ ____ ____ | | _\_ |__ _______ ___ | ||
4 | * Source | _// _ \_/ ___\| |/ /| __ \ / _ \ \/ / | ||
5 | * Jukebox | | ( <_> ) \___| < | \_\ ( <_> > < < | ||
6 | * Firmware |____|_ /\____/ \___ >__|_ \|___ /\____/__/\_ \ | ||
7 | * \/ \/ \/ \/ \/ | ||
8 | * $Id$ | ||
9 | * | ||
10 | * Copyright (C) 2002 by Daniel Stenberg | ||
11 | * | ||
12 | * All files in this archive are subject to the GNU General Public License. | ||
13 | * See the file COPYING in the source tree root for full license agreement. | ||
14 | * | ||
15 | * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY | ||
16 | * KIND, either express or implied. | ||
17 | * | ||
18 | ****************************************************************************/ | ||
19 | /***************************************************************************** | ||
20 | * | ||
21 | * Big (best-fit) Memory Allocation | ||
22 | * | ||
23 | * Author: Daniel Stenberg <daniel@haxx.se> | ||
24 | * | ||
25 | * Read THOUGHTS for theories and details on implementation. | ||
26 | * | ||
27 | ****************************************************************************/ | ||
28 | |||
29 | #include <stdio.h> | ||
30 | #include <stdlib.h> | ||
31 | |||
32 | #include "bysize.h" | ||
33 | |||
34 | #ifndef TRUE | ||
35 | #define TRUE 1 | ||
36 | #endif | ||
37 | #ifndef FALSE | ||
38 | #define FALSE 0 | ||
39 | #endif | ||
40 | |||
41 | /* #define DEBUG_MALLOC */ | ||
42 | |||
43 | #define BMEM_ALIGN 64 /* resolution */ | ||
44 | |||
45 | #define BMEMERR_TOOSMALL -1 | ||
46 | |||
47 | /* this struct will be stored in all CHUNKS and AREAS */ | ||
48 | struct BlockInfo { | ||
49 | struct BlockInfo *lower; /* previous block in memory (lower address) */ | ||
50 | struct BlockInfo *higher; /* next block in memory (higher address) */ | ||
51 | unsigned long info; /* 31 bits size: 1 bit free boolean */ | ||
52 | #define INFO_FREE 1 | ||
53 | #define INFO_SIZE (~ INFO_FREE) /* inverted FREE bit pattern */ | ||
54 | |||
55 | /* FREE+SIZE Could be written to use ordinary bitfields if using a smart | ||
56 | (like gcc) compiler in a manner like: | ||
57 | int size:31; | ||
58 | int free:1; | ||
59 | |||
60 | The 'higher' pointer COULD be removed completely if the size is used as | ||
61 | an index to the higher one. This would then REQUIRE the entire memory | ||
62 | pool to be contiguous and it needs a 'terminating' "node" or an extra | ||
63 | flag that informs about the end of the list. | ||
64 | */ | ||
65 | }; | ||
66 | |||
67 | /* the BLOCK list should be sorted in a lower to higher address order */ | ||
68 | struct BlockInfo *blockHead=NULL; /* nothing from the start */ | ||
69 | |||
70 | void bmalloc_status(void); | ||
71 | |||
72 | |||
73 | /*********************************************************************** | ||
74 | * | ||
75 | * remove_block() | ||
76 | * | ||
77 | * Remove the block from the address-sorted list. | ||
78 | * | ||
79 | ***********************************************************************/ | ||
80 | |||
81 | static | ||
82 | void remove_block(struct BlockInfo *block) | ||
83 | { | ||
84 | if(block->lower) | ||
85 | block->lower->higher = block->higher; | ||
86 | else | ||
87 | blockHead = block->higher; | ||
88 | if(block->higher) | ||
89 | block->higher->lower = block->lower; | ||
90 | } | ||
91 | |||
92 | /**************************************************************************** | ||
93 | * | ||
94 | * add_blocktolists() | ||
95 | * | ||
96 | * Adds the specified block at the specified place in the address-sorted | ||
97 | * list and at the appropriate place in the size-sorted. | ||
98 | * | ||
99 | ***************************************************************************/ | ||
100 | static | ||
101 | void add_blocktolists(struct BlockInfo *block, | ||
102 | struct BlockInfo *newblock, | ||
103 | size_t newsize) | ||
104 | { | ||
105 | struct BlockInfo *temp; /* temporary storage variable */ | ||
106 | if(block) { | ||
107 | /* `block' is now a lower address than 'newblock' */ | ||
108 | |||
109 | /* | ||
110 | * Check if the new CHUNK is wall-to-wall with the lower addressed | ||
111 | * one (if *that* is free) | ||
112 | */ | ||
113 | if(block->info&INFO_FREE) { | ||
114 | if((char *)block + (block->info&INFO_SIZE) == (char *)newblock) { | ||
115 | /* yes sir, this is our lower address neighbour, enlarge that one | ||
116 | pick it out from the list and recursively add that chunk and | ||
117 | then we escape */ | ||
118 | |||
119 | /* remove from size-sorted list: */ | ||
120 | bmalloc_remove_chunksize((char*)block+sizeof(struct BlockInfo)); | ||
121 | |||
122 | block->info += newsize; /* newsize is an even number and thus the FREE | ||
123 | bit is untouched */ | ||
124 | |||
125 | remove_block(block); /* unlink the block address-wise */ | ||
126 | |||
127 | /* recursively check our lower friend(s) */ | ||
128 | add_blocktolists(block->lower, block, block->info&INFO_SIZE); | ||
129 | return; | ||
130 | } | ||
131 | } | ||
132 | |||
133 | temp = block->higher; | ||
134 | |||
135 | block->higher = newblock; | ||
136 | newblock->lower = block; | ||
137 | newblock->higher = temp; | ||
138 | } | ||
139 | else { | ||
140 | /* this block should preceed the heading one */ | ||
141 | temp = blockHead; | ||
142 | |||
143 | /* check if this is our higher addressed neighbour */ | ||
144 | if((char *)newblock + newsize == (char *)temp) { | ||
145 | |||
146 | /* yes, we are wall-to-wall with the higher CHUNK */ | ||
147 | if(temp->info&INFO_FREE) { | ||
148 | /* and the neighbour is even free, remove that one and enlarge | ||
149 | ourselves, call add_blocktolists() recursively and then escape */ | ||
150 | |||
151 | remove_block(temp); /* unlink 'temp' from list */ | ||
152 | |||
153 | /* remove from size-sorted list: */ | ||
154 | bmalloc_remove_chunksize((char*)temp+sizeof(struct BlockInfo) ); | ||
155 | |||
156 | /* add the upper block's size on ourselves */ | ||
157 | newsize += temp->info&INFO_SIZE; | ||
158 | |||
159 | /* add the new, bigger block */ | ||
160 | add_blocktolists(block, newblock, newsize); | ||
161 | return; | ||
162 | } | ||
163 | } | ||
164 | |||
165 | blockHead = newblock; | ||
166 | newblock->higher = temp; | ||
167 | newblock->lower = NULL; /* there is no lower one */ | ||
168 | } | ||
169 | |||
170 | newblock->info = newsize | INFO_FREE; /* we do assume size isn't using the | ||
171 | FREE bit */ | ||
172 | bmalloc_insert_bysize((char *)newblock+sizeof(struct BlockInfo), newsize); | ||
173 | } | ||
174 | |||
175 | /*********************************************************************** | ||
176 | * | ||
177 | * findblockbyaddr() | ||
178 | * | ||
179 | * Find the block that is just before the input block in memory. Returns NULL | ||
180 | * if none is. | ||
181 | * | ||
182 | ***********************************************************************/ | ||
183 | |||
184 | static | ||
185 | struct BlockInfo *findblockbyaddr(struct BlockInfo *block) | ||
186 | { | ||
187 | struct BlockInfo *test = blockHead; | ||
188 | struct BlockInfo *lower = NULL; | ||
189 | |||
190 | while(test && (test < block)) { | ||
191 | lower = test; | ||
192 | test = test->higher; | ||
193 | } | ||
194 | return lower; | ||
195 | } | ||
196 | |||
197 | /*********************************************************************** | ||
198 | * | ||
199 | * bmalloc_add_pool() | ||
200 | * | ||
201 | * This function should be the absolutely first function to call. It sets up | ||
202 | * the memory bounds of the [first] CHUNK(s). It is possible to call this | ||
203 | * function several times to add more CHUNKs to the pool of free memory. This | ||
204 | * allows the bmalloc system to deal with non-contigous memory areas. | ||
205 | * | ||
206 | * Returns non-zero if an error occured. The memory was not added then. | ||
207 | * | ||
208 | ***********************************************************************/ | ||
209 | |||
210 | int bmalloc_add_pool(void *start, | ||
211 | size_t size) | ||
212 | { | ||
213 | struct BlockInfo *newblock = (struct BlockInfo *)start; | ||
214 | struct BlockInfo *block; | ||
215 | |||
216 | if(size < BMEM_ALIGN) | ||
217 | return BMEMERR_TOOSMALL; | ||
218 | |||
219 | block = findblockbyaddr( newblock ); | ||
220 | /* `block' is now a lower address than 'newblock' or NULL */ | ||
221 | |||
222 | if(size&1) | ||
223 | size--; /* only add even sizes */ | ||
224 | |||
225 | add_blocktolists(block, newblock, size); | ||
226 | |||
227 | return 0; | ||
228 | } | ||
229 | |||
230 | |||
231 | #ifdef DEBUG_VERBOSE | ||
232 | static void bmalloc_failed(size_t size) | ||
233 | { | ||
234 | printf("*** " __FILE__ " Couldn't allocate %d bytes\n", size); | ||
235 | bmalloc_status(); | ||
236 | } | ||
237 | #else | ||
238 | #define bmalloc_failed(x) | ||
239 | #endif | ||
240 | |||
241 | void bmalloc_status(void) | ||
242 | { | ||
243 | #ifdef DEBUG_MALLOC | ||
244 | struct BlockInfo *block = blockHead; | ||
245 | long mem_free = 0; | ||
246 | long mem_used = 0; | ||
247 | |||
248 | printf("List of BLOCKS (in address order):\n"); | ||
249 | while(block) { | ||
250 | printf(" START %p END %p SIZE %ld FLAG %s\n", | ||
251 | block, | ||
252 | (char *)block+(block->info&INFO_SIZE), | ||
253 | block->info&INFO_SIZE, | ||
254 | (block->info&INFO_FREE)?"free":"used"); | ||
255 | if(block->info&INFO_FREE) | ||
256 | mem_free += block->info&INFO_SIZE; | ||
257 | else | ||
258 | mem_used += block->info&INFO_SIZE; | ||
259 | block = block->higher; | ||
260 | } | ||
261 | printf(" Used mem: %ld , free mem: %ld (total %ld)\n", | ||
262 | mem_used, mem_free, mem_used + mem_free); | ||
263 | bmalloc_print_sizes(); | ||
264 | #endif | ||
265 | } | ||
266 | |||
267 | |||
268 | void *bmalloc(size_t size) | ||
269 | { | ||
270 | void *mem; | ||
271 | |||
272 | #ifdef DEBUG_VERBOSE | ||
273 | { | ||
274 | static int count=0; | ||
275 | int realsize = size + sizeof(struct BlockInfo); | ||
276 | if(realsize%4096) | ||
277 | realsize = ((size / BMEM_ALIGN)+1) * BMEM_ALIGN; | ||
278 | printf("%d bmalloc(%d) [%d]\n", count++, size, realsize); | ||
279 | } | ||
280 | #endif | ||
281 | |||
282 | size += sizeof(struct BlockInfo); /* add memory for our header */ | ||
283 | |||
284 | if(size&(BMEM_ALIGN-1)) /* a lot faster than %BMEM_ALIGN but this MUST be | ||
285 | changed if the BLOCKSIZE is not 2^X ! */ | ||
286 | size = ((size / BMEM_ALIGN)+1) * BMEM_ALIGN; /* align like this */ | ||
287 | |||
288 | /* get a CHUNK from the list with this size */ | ||
289 | mem = bmalloc_obtainbysize ( size ); | ||
290 | if(mem) { | ||
291 | /* the memory block we have got is the "best-fit" and it is already | ||
292 | un-linked from the free list */ | ||
293 | |||
294 | /* now do the math to get the proper block pointer */ | ||
295 | struct BlockInfo *block= (struct BlockInfo *) | ||
296 | ((char *)mem - sizeof(struct BlockInfo)); | ||
297 | |||
298 | block->info &= ~INFO_FREE; | ||
299 | /* not free anymore */ | ||
300 | |||
301 | if( size != (block->info&INFO_SIZE)) { | ||
302 | /* split this chunk into two pieces and return the one that fits us */ | ||
303 | size_t othersize = (block->info&INFO_SIZE) - size; | ||
304 | |||
305 | if(othersize > BMEM_ALIGN) { | ||
306 | /* prevent losing small pieces of memory due to weird alignments | ||
307 | of the memory pool */ | ||
308 | |||
309 | block->info = size; /* set new size (leave FREE bit cleared) */ | ||
310 | |||
311 | /* Add the new chunk to the lists: */ | ||
312 | add_blocktolists(block->lower, | ||
313 | (struct BlockInfo *)((char *)block + size), | ||
314 | othersize ); | ||
315 | } | ||
316 | } | ||
317 | |||
318 | /* Return the memory our parent may use: */ | ||
319 | return (char *)block+sizeof(struct BlockInfo); | ||
320 | } | ||
321 | else { | ||
322 | bmalloc_failed(size); | ||
323 | return NULL; /* can't find any memory, fail hard */ | ||
324 | } | ||
325 | |||
326 | #ifdef DEBUG_VERBOSE | ||
327 | bmalloc_status(); | ||
328 | #endif | ||
329 | return mem; | ||
330 | } | ||
331 | |||
332 | void bfree(void *ptr) | ||
333 | { | ||
334 | struct BlockInfo *block = (struct BlockInfo *) | ||
335 | ((char *)ptr - sizeof(struct BlockInfo)); | ||
336 | size_t size; | ||
337 | |||
338 | /* setup our initial higher and lower pointers */ | ||
339 | struct BlockInfo *lower = block->lower; | ||
340 | struct BlockInfo *higher = block->higher; | ||
341 | |||
342 | #ifdef DEBUG_VERBOSE | ||
343 | static int freecount=0; | ||
344 | printf("%d bfree(%p)\n", freecount++, ptr); | ||
345 | #endif | ||
346 | /* bind together lower addressed FREE CHUNKS */ | ||
347 | if(lower && (lower->info&INFO_FREE) && | ||
348 | ((char *)lower + (lower->info&INFO_SIZE) == (char *)block)) { | ||
349 | size = block->info&INFO_SIZE; /* original size */ | ||
350 | |||
351 | /* remove from size-link: */ | ||
352 | bmalloc_remove_chunksize((char *)lower+sizeof(struct BlockInfo)); | ||
353 | |||
354 | remove_block(block); /* unlink from address list */ | ||
355 | block = lower; /* new base area pointer */ | ||
356 | block->info += size; /* append the new size (the FREE bit | ||
357 | will remain untouched) */ | ||
358 | |||
359 | lower = lower->lower; /* new lower pointer */ | ||
360 | } | ||
361 | /* bind together higher addressed FREE CHUNKS */ | ||
362 | if(higher && (higher->info&INFO_FREE) && | ||
363 | ((char *)block + (block->info&INFO_SIZE) == (char *)higher)) { | ||
364 | /* append higher size, the FREE bit won't be affected */ | ||
365 | block->info += (higher->info&INFO_SIZE); | ||
366 | |||
367 | /* unlink from size list: */ | ||
368 | bmalloc_remove_chunksize(higher+sizeof(struct BlockInfo)); | ||
369 | remove_block(higher); /* unlink from address list */ | ||
370 | higher = higher->higher; /* the new higher link */ | ||
371 | block->higher = higher; /* new higher link */ | ||
372 | } | ||
373 | block->info &= ~INFO_FREE; /* consider this FREE! */ | ||
374 | |||
375 | block->lower = lower; | ||
376 | block->higher = higher; | ||
377 | |||
378 | bmalloc_insert_bysize((char *)block+sizeof(struct BlockInfo), | ||
379 | block->info&INFO_SIZE); | ||
380 | |||
381 | #ifdef DEBUG_VERBOSE | ||
382 | bmalloc_status(); | ||
383 | #endif | ||
384 | |||
385 | } | ||
386 | |||
diff --git a/firmware/malloc/bmalloc.h b/firmware/malloc/bmalloc.h deleted file mode 100644 index 4bb89b9adb..0000000000 --- a/firmware/malloc/bmalloc.h +++ /dev/null | |||
@@ -1,30 +0,0 @@ | |||
1 | /*************************************************************************** | ||
2 | * __________ __ ___. | ||
3 | * Open \______ \ ____ ____ | | _\_ |__ _______ ___ | ||
4 | * Source | _// _ \_/ ___\| |/ /| __ \ / _ \ \/ / | ||
5 | * Jukebox | | ( <_> ) \___| < | \_\ ( <_> > < < | ||
6 | * Firmware |____|_ /\____/ \___ >__|_ \|___ /\____/__/\_ \ | ||
7 | * \/ \/ \/ \/ \/ | ||
8 | * $Id$ | ||
9 | * | ||
10 | * Copyright (C) 2002 by Daniel Stenberg | ||
11 | * | ||
12 | * All files in this archive are subject to the GNU General Public License. | ||
13 | * See the file COPYING in the source tree root for full license agreement. | ||
14 | * | ||
15 | * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY | ||
16 | * KIND, either express or implied. | ||
17 | * | ||
18 | ****************************************************************************/ | ||
19 | #ifndef _BMALLOC_H_ | ||
20 | #define _BMALLOC_H_ | ||
21 | |||
22 | #include <stdlib.h> | ||
23 | |||
24 | int bmalloc_add_pool(void *start, size_t size); | ||
25 | void bmalloc_status(void); | ||
26 | |||
27 | void *bmalloc(size_t size); | ||
28 | void bfree(void *ptr); | ||
29 | |||
30 | #endif | ||
diff --git a/firmware/malloc/bysize.c b/firmware/malloc/bysize.c deleted file mode 100644 index 437159579c..0000000000 --- a/firmware/malloc/bysize.c +++ /dev/null | |||
@@ -1,451 +0,0 @@ | |||
1 | /*************************************************************************** | ||
2 | * __________ __ ___. | ||
3 | * Open \______ \ ____ ____ | | _\_ |__ _______ ___ | ||
4 | * Source | _// _ \_/ ___\| |/ /| __ \ / _ \ \/ / | ||
5 | * Jukebox | | ( <_> ) \___| < | \_\ ( <_> > < < | ||
6 | * Firmware |____|_ /\____/ \___ >__|_ \|___ /\____/__/\_ \ | ||
7 | * \/ \/ \/ \/ \/ | ||
8 | * $Id$ | ||
9 | * | ||
10 | * Copyright (C) 2002 by Daniel Stenberg | ||
11 | * | ||
12 | * All files in this archive are subject to the GNU General Public License. | ||
13 | * See the file COPYING in the source tree root for full license agreement. | ||
14 | * | ||
15 | * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY | ||
16 | * KIND, either express or implied. | ||
17 | * | ||
18 | ****************************************************************************/ | ||
19 | /***************************************************************************** | ||
20 | * | ||
21 | * Size-sorted list/tree functions. | ||
22 | * | ||
23 | * Author: Daniel Stenberg | ||
24 | * Date: March 7, 1997 | ||
25 | * Version: 2.0 | ||
26 | * Email: daniel@haxx.se | ||
27 | * | ||
28 | * v2.0 | ||
29 | * - Added SPLAY TREE functionality. | ||
30 | * | ||
31 | * Adds and removes CHUNKS from a list or tree. | ||
32 | * | ||
33 | ****************************************************************************/ | ||
34 | |||
35 | #include <stdio.h> | ||
36 | #include <stdlib.h> | ||
37 | |||
38 | #define SPLAY /* we use the splay version as that is much faster when the | ||
39 | amount of blocks grow */ | ||
40 | |||
41 | #ifndef TRUE | ||
42 | #define TRUE 1 | ||
43 | #endif | ||
44 | #ifndef FALSE | ||
45 | #define FALSE 0 | ||
46 | #endif | ||
47 | |||
48 | #ifndef SPLAY /* these routines are for the non-splay version */ | ||
49 | |||
50 | struct ChunkInfo { | ||
51 | struct ChunkInfo *larger; | ||
52 | struct ChunkInfo *smaller; | ||
53 | size_t size; | ||
54 | }; | ||
55 | |||
56 | /* the CHUNK list anchor */ | ||
57 | struct ChunkInfo *chunkHead=NULL; | ||
58 | |||
59 | /*********************************************************************** | ||
60 | |||
61 | findchunkbysize() | ||
62 | |||
63 | Find the chunk that is smaller than the input size. Returns | ||
64 | NULL if none is. | ||
65 | |||
66 | **********************************************************************/ | ||
67 | |||
68 | static struct ChunkInfo *findchunkbysize(size_t size) | ||
69 | { | ||
70 | struct ChunkInfo *test = chunkHead; | ||
71 | struct ChunkInfo *smaller = NULL; | ||
72 | while(test && (test->size < size)) { | ||
73 | smaller = test; | ||
74 | test = test->larger; | ||
75 | } | ||
76 | return smaller; | ||
77 | } | ||
78 | |||
79 | /*********************************************************************** | ||
80 | |||
81 | remove_chunksize() | ||
82 | |||
83 | Remove the chunk from the size-sorted list. | ||
84 | ***********************************************************************/ | ||
85 | |||
86 | void bmalloc_remove_chunksize(void *data) | ||
87 | { | ||
88 | struct ChunkInfo *chunk = (struct ChunkInfo *)data; | ||
89 | if(chunk->smaller) | ||
90 | chunk->smaller->larger = chunk->larger; | ||
91 | else { | ||
92 | /* if this has no smaller, this is the head */ | ||
93 | chunkHead = chunk->larger; /* new head */ | ||
94 | } | ||
95 | if(chunk->larger) | ||
96 | chunk->larger->smaller = chunk->smaller; | ||
97 | } | ||
98 | |||
99 | void bmalloc_insert_bysize(char *data, size_t size) | ||
100 | { | ||
101 | struct ChunkInfo *newchunk = (struct ChunkInfo *)data; | ||
102 | struct ChunkInfo *chunk = findchunkbysize ( size ); | ||
103 | |||
104 | newchunk->size = size; | ||
105 | |||
106 | if(chunk) { | ||
107 | /* 'chunk' is smaller than size, append the new chunk ahead of this */ | ||
108 | newchunk->smaller = chunk; | ||
109 | newchunk->larger = chunk->larger; | ||
110 | if(chunk->larger) | ||
111 | chunk->larger->smaller = newchunk; | ||
112 | chunk->larger = newchunk; | ||
113 | } | ||
114 | else { | ||
115 | /* smallest CHUNK around, append first in the list */ | ||
116 | newchunk->larger = chunkHead; | ||
117 | newchunk->smaller = NULL; | ||
118 | |||
119 | if(chunkHead) | ||
120 | chunkHead->smaller = newchunk; | ||
121 | chunkHead = newchunk; | ||
122 | } | ||
123 | } | ||
124 | |||
125 | char *bmalloc_obtainbysize( size_t size) | ||
126 | { | ||
127 | struct ChunkInfo *chunk = findchunkbysize( size ); | ||
128 | |||
129 | if(!chunk) { | ||
130 | if(size <= (chunkHead->size)) | ||
131 | /* there is no smaller CHUNK, use the first one (if we fit within that) | ||
132 | */ | ||
133 | chunk = chunkHead; | ||
134 | } | ||
135 | else | ||
136 | /* we're on the last CHUNK that is smaller than requested, step onto | ||
137 | the bigger one */ | ||
138 | chunk = chunk->larger; | ||
139 | |||
140 | if(chunk) { | ||
141 | bmalloc_remove_chunksize( chunk ); /* unlink size-wise */ | ||
142 | return (char *)chunk; | ||
143 | } | ||
144 | else | ||
145 | return NULL; | ||
146 | } | ||
147 | |||
148 | void bmalloc_print_sizes(void) | ||
149 | { | ||
150 | struct ChunkInfo *chunk = chunkHead; | ||
151 | printf("List of CHUNKS (in size order):\n"); | ||
152 | #if 1 | ||
153 | while(chunk) { | ||
154 | printf(" START %p END %p SIZE %d\n", | ||
155 | chunk, (char *)chunk+chunk->size, chunk->size); | ||
156 | chunk = chunk->larger; | ||
157 | } | ||
158 | #endif | ||
159 | printf("End of CHUNKS:\n"); | ||
160 | } | ||
161 | |||
162 | #else /* Here follows all routines dealing with the SPLAY TREES */ | ||
163 | |||
164 | typedef struct tree_node Tree; | ||
165 | struct tree_node { | ||
166 | Tree *smaller; /* smaller node */ | ||
167 | Tree *larger; /* larger node */ | ||
168 | Tree *same; /* points to a node with identical key */ | ||
169 | int key; /* the "sort" key */ | ||
170 | }; | ||
171 | |||
172 | Tree *chunkHead = NULL; /* the root */ | ||
173 | |||
174 | #define compare(i,j) ((i)-(j)) | ||
175 | |||
176 | /* Set this to a key value that will *NEVER* appear otherwise */ | ||
177 | #define KEY_NOTUSED -1 | ||
178 | |||
179 | /* | ||
180 | * Splay using the key i (which may or may not be in the tree.) The starting | ||
181 | * root is t. Weight fields are maintained. | ||
182 | */ | ||
183 | static | ||
184 | Tree * splay (int i, Tree *t) | ||
185 | { | ||
186 | Tree N, *l, *r, *y; | ||
187 | int comp; | ||
188 | |||
189 | if (t == NULL) | ||
190 | return t; | ||
191 | N.smaller = N.larger = NULL; | ||
192 | l = r = &N; | ||
193 | |||
194 | for (;;) { | ||
195 | comp = compare(i, t->key); | ||
196 | if (comp < 0) { | ||
197 | if (t->smaller == NULL) | ||
198 | break; | ||
199 | if (compare(i, t->smaller->key) < 0) { | ||
200 | y = t->smaller; /* rotate smaller */ | ||
201 | t->smaller = y->larger; | ||
202 | y->larger = t; | ||
203 | |||
204 | t = y; | ||
205 | if (t->smaller == NULL) | ||
206 | break; | ||
207 | } | ||
208 | r->smaller = t; /* link smaller */ | ||
209 | r = t; | ||
210 | t = t->smaller; | ||
211 | } | ||
212 | else if (comp > 0) { | ||
213 | if (t->larger == NULL) | ||
214 | break; | ||
215 | if (compare(i, t->larger->key) > 0) { | ||
216 | y = t->larger; /* rotate larger */ | ||
217 | t->larger = y->smaller; | ||
218 | y->smaller = t; | ||
219 | t = y; | ||
220 | if (t->larger == NULL) | ||
221 | break; | ||
222 | } | ||
223 | l->larger = t; /* link larger */ | ||
224 | l = t; | ||
225 | t = t->larger; | ||
226 | } | ||
227 | else { | ||
228 | break; | ||
229 | } | ||
230 | } | ||
231 | |||
232 | l->larger = r->smaller = NULL; | ||
233 | |||
234 | l->larger = t->smaller; /* assemble */ | ||
235 | r->smaller = t->larger; | ||
236 | t->smaller = N.larger; | ||
237 | t->larger = N.smaller; | ||
238 | |||
239 | return t; | ||
240 | } | ||
241 | |||
242 | /* Insert key i into the tree t. Return a pointer to the resulting tree or | ||
243 | NULL if something went wrong. */ | ||
244 | static | ||
245 | Tree *insert(int i, Tree *t, Tree *new) | ||
246 | { | ||
247 | if (new == NULL) { | ||
248 | return t; | ||
249 | } | ||
250 | |||
251 | if (t != NULL) { | ||
252 | t = splay(i,t); | ||
253 | if (compare(i, t->key)==0) { | ||
254 | /* it already exists one of this size */ | ||
255 | |||
256 | new->same = t; | ||
257 | new->key = i; | ||
258 | new->smaller = t->smaller; | ||
259 | new->larger = t->larger; | ||
260 | |||
261 | t->smaller = new; | ||
262 | t->key = KEY_NOTUSED; | ||
263 | |||
264 | return new; /* new root node */ | ||
265 | } | ||
266 | } | ||
267 | |||
268 | if (t == NULL) { | ||
269 | new->smaller = new->larger = NULL; | ||
270 | } | ||
271 | else if (compare(i, t->key) < 0) { | ||
272 | new->smaller = t->smaller; | ||
273 | new->larger = t; | ||
274 | t->smaller = NULL; | ||
275 | } | ||
276 | else { | ||
277 | new->larger = t->larger; | ||
278 | new->smaller = t; | ||
279 | t->larger = NULL; | ||
280 | } | ||
281 | new->key = i; | ||
282 | |||
283 | new->same = NULL; /* no identical node (yet) */ | ||
284 | |||
285 | return new; | ||
286 | } | ||
287 | |||
288 | /* Finds and deletes the best-fit node from the tree. Return a pointer to the | ||
289 | resulting tree. best-fit means the smallest node that fits the requested | ||
290 | size. */ | ||
291 | static | ||
292 | Tree *removebestfit(int i, Tree *t, Tree **removed) | ||
293 | { | ||
294 | Tree *x; | ||
295 | |||
296 | if (t==NULL) | ||
297 | return NULL; | ||
298 | t = splay(i,t); | ||
299 | if(compare(i, t->key) > 0) { | ||
300 | /* too small node, try the larger chain */ | ||
301 | if(t->larger) | ||
302 | t=splay(t->larger->key, t); | ||
303 | else { | ||
304 | /* fail */ | ||
305 | *removed = NULL; | ||
306 | return t; | ||
307 | } | ||
308 | } | ||
309 | |||
310 | if (compare(i, t->key) <= 0) { /* found it */ | ||
311 | |||
312 | /* FIRST! Check if there is a list with identical sizes */ | ||
313 | x = t->same; | ||
314 | if(x) { | ||
315 | /* there is, pick one from the list */ | ||
316 | |||
317 | /* 'x' is the new root node */ | ||
318 | |||
319 | x->key = t->key; | ||
320 | x->larger = t->larger; | ||
321 | x->smaller = t->smaller; | ||
322 | *removed = t; | ||
323 | return x; /* new root */ | ||
324 | } | ||
325 | |||
326 | if (t->smaller == NULL) { | ||
327 | x = t->larger; | ||
328 | } | ||
329 | else { | ||
330 | x = splay(i, t->smaller); | ||
331 | x->larger = t->larger; | ||
332 | } | ||
333 | *removed = t; | ||
334 | |||
335 | return x; | ||
336 | } | ||
337 | else { | ||
338 | *removed = NULL; /* no match */ | ||
339 | return t; /* It wasn't there */ | ||
340 | } | ||
341 | } | ||
342 | |||
343 | |||
344 | /* Deletes the node we point out from the tree if it's there. Return a pointer | ||
345 | to the resulting tree. */ | ||
346 | static | ||
347 | Tree *removebyaddr(Tree *t, Tree *remove) | ||
348 | { | ||
349 | Tree *x; | ||
350 | |||
351 | if (!t || !remove) | ||
352 | return NULL; | ||
353 | |||
354 | if(KEY_NOTUSED == remove->key) { | ||
355 | /* just unlink ourselves nice and quickly: */ | ||
356 | remove->smaller->same = remove->same; | ||
357 | if(remove->same) | ||
358 | remove->same->smaller = remove->smaller; | ||
359 | /* voila, we're done! */ | ||
360 | return t; | ||
361 | } | ||
362 | |||
363 | t = splay(remove->key,t); | ||
364 | |||
365 | /* Check if there is a list with identical sizes */ | ||
366 | |||
367 | x = t->same; | ||
368 | if(x) { | ||
369 | /* 'x' is the new root node */ | ||
370 | |||
371 | x->key = t->key; | ||
372 | x->larger = t->larger; | ||
373 | x->smaller = t->smaller; | ||
374 | |||
375 | return x; /* new root */ | ||
376 | } | ||
377 | |||
378 | /* Remove the actualy root node: */ | ||
379 | |||
380 | if (t->smaller == NULL) { | ||
381 | x = t->larger; | ||
382 | } | ||
383 | else { | ||
384 | x = splay(remove->key, t->smaller); | ||
385 | x->larger = t->larger; | ||
386 | } | ||
387 | |||
388 | return x; | ||
389 | } | ||
390 | |||
391 | #ifdef DEBUG_MALLOC | ||
392 | static | ||
393 | int printtree(Tree * t, int d, char output) | ||
394 | { | ||
395 | int distance=0; | ||
396 | Tree *node; | ||
397 | int i; | ||
398 | if (t == NULL) | ||
399 | return 0; | ||
400 | distance += printtree(t->larger, d+1, output); | ||
401 | for (i=0; i<d; i++) | ||
402 | if(output) | ||
403 | printf(" "); | ||
404 | |||
405 | if(output) { | ||
406 | printf("%d[%d]", t->key, i); | ||
407 | } | ||
408 | |||
409 | for(node = t->same; node; node = node->same) { | ||
410 | distance += i; /* this has the same "virtual" distance */ | ||
411 | |||
412 | if(output) | ||
413 | printf(" [+]"); | ||
414 | } | ||
415 | if(output) | ||
416 | puts(""); | ||
417 | |||
418 | distance += i; | ||
419 | distance += printtree(t->smaller, d+1, output); | ||
420 | return distance; | ||
421 | } | ||
422 | #endif | ||
423 | |||
424 | /* Here follow the look-alike interface so that the tree-function names are | ||
425 | the same as the list-ones to enable easy interchange */ | ||
426 | |||
427 | void bmalloc_remove_chunksize(void *data) | ||
428 | { | ||
429 | chunkHead = removebyaddr(chunkHead, data); | ||
430 | } | ||
431 | |||
432 | void bmalloc_insert_bysize(char *data, size_t size) | ||
433 | { | ||
434 | chunkHead = insert(size, chunkHead, (Tree *)data); | ||
435 | } | ||
436 | |||
437 | char *bmalloc_obtainbysize( size_t size) | ||
438 | { | ||
439 | Tree *receive; | ||
440 | chunkHead = removebestfit(size, chunkHead, &receive); | ||
441 | return (char *)receive; | ||
442 | } | ||
443 | |||
444 | #ifdef DEBUG_MALLOC | ||
445 | void bmalloc_print_sizes(void) | ||
446 | { | ||
447 | printtree(chunkHead, 0, 1); | ||
448 | } | ||
449 | #endif | ||
450 | |||
451 | #endif | ||
diff --git a/firmware/malloc/bysize.h b/firmware/malloc/bysize.h deleted file mode 100644 index 34be8f9021..0000000000 --- a/firmware/malloc/bysize.h +++ /dev/null | |||
@@ -1,24 +0,0 @@ | |||
1 | /*************************************************************************** | ||
2 | * __________ __ ___. | ||
3 | * Open \______ \ ____ ____ | | _\_ |__ _______ ___ | ||
4 | * Source | _// _ \_/ ___\| |/ /| __ \ / _ \ \/ / | ||
5 | * Jukebox | | ( <_> ) \___| < | \_\ ( <_> > < < | ||
6 | * Firmware |____|_ /\____/ \___ >__|_ \|___ /\____/__/\_ \ | ||
7 | * \/ \/ \/ \/ \/ | ||
8 | * $Id$ | ||
9 | * | ||
10 | * Copyright (C) 2002 by Daniel Stenberg | ||
11 | * | ||
12 | * All files in this archive are subject to the GNU General Public License. | ||
13 | * See the file COPYING in the source tree root for full license agreement. | ||
14 | * | ||
15 | * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY | ||
16 | * KIND, either express or implied. | ||
17 | * | ||
18 | ****************************************************************************/ | ||
19 | void bmalloc_remove_chunksize(void *data); | ||
20 | void bmalloc_insert_bysize(char *data, size_t size); | ||
21 | char *bmalloc_obtainbysize( size_t size); | ||
22 | #ifdef DEBUG_MALLOC | ||
23 | void bmalloc_print_sizes(void); | ||
24 | #endif | ||
diff --git a/firmware/malloc/dmalloc.c b/firmware/malloc/dmalloc.c deleted file mode 100644 index 7f1690b221..0000000000 --- a/firmware/malloc/dmalloc.c +++ /dev/null | |||
@@ -1,634 +0,0 @@ | |||
1 | /*************************************************************************** | ||
2 | * __________ __ ___. | ||
3 | * Open \______ \ ____ ____ | | _\_ |__ _______ ___ | ||
4 | * Source | _// _ \_/ ___\| |/ /| __ \ / _ \ \/ / | ||
5 | * Jukebox | | ( <_> ) \___| < | \_\ ( <_> > < < | ||
6 | * Firmware |____|_ /\____/ \___ >__|_ \|___ /\____/__/\_ \ | ||
7 | * \/ \/ \/ \/ \/ | ||
8 | * $Id$ | ||
9 | * | ||
10 | * Copyright (C) 2002 by Daniel Stenberg | ||
11 | * | ||
12 | * All files in this archive are subject to the GNU General Public License. | ||
13 | * See the file COPYING in the source tree root for full license agreement. | ||
14 | * | ||
15 | * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY | ||
16 | * KIND, either express or implied. | ||
17 | * | ||
18 | ****************************************************************************/ | ||
19 | /***************************************************************************** | ||
20 | * | ||
21 | * Dynamic small-blocks Memory Allocation | ||
22 | * | ||
23 | * Author: Daniel Stenberg <daniel@haxx.se> | ||
24 | * | ||
25 | * Read THOUGHTS for theories and details on the implementation. | ||
26 | * | ||
27 | *****************************************************************************/ | ||
28 | |||
29 | #include <stdio.h> | ||
30 | #include <string.h> /* memcpy */ | ||
31 | |||
32 | #ifdef DEBUG_MALLOC | ||
33 | #include <stdarg.h> | ||
34 | #endif | ||
35 | |||
36 | #ifdef PSOS | ||
37 | #include <psos.h> | ||
38 | #define SEMAPHORE /* the PSOS routines use semaphore protection */ | ||
39 | #else | ||
40 | |||
41 | #endif | ||
42 | |||
43 | #define BMALLOC /* we use our own big-malloc system */ | ||
44 | |||
45 | #ifdef BMALLOC | ||
46 | #include "bmalloc.h" | ||
47 | #endif | ||
48 | |||
49 | /* Each TOP takes care of a chain of BLOCKS */ | ||
50 | struct MemTop { | ||
51 | struct MemBlock *chain; /* pointer to the BLOCK chain */ | ||
52 | long nfree; /* total number of free FRAGMENTS in the chain */ | ||
53 | short nmax; /* total number of FRAGMENTS in this kind of BLOCK */ | ||
54 | size_t fragsize; /* the size of each FRAGMENT */ | ||
55 | |||
56 | #ifdef SEMAPHORE /* if we're protecting the list with SEMAPHORES */ | ||
57 | long semaphore_id; /* semaphore used to lock this particular list */ | ||
58 | #endif | ||
59 | |||
60 | }; | ||
61 | |||
62 | /* Each BLOCK takes care of an amount of FRAGMENTS */ | ||
63 | struct MemBlock { | ||
64 | struct MemTop *top; /* our TOP struct */ | ||
65 | struct MemBlock *next; /* next BLOCK */ | ||
66 | struct MemBlock *prev; /* prev BLOCK */ | ||
67 | |||
68 | struct MemFrag *first; /* the first free FRAGMENT in this block */ | ||
69 | |||
70 | short nfree; /* number of free FRAGMENTS in this BLOCK */ | ||
71 | }; | ||
72 | |||
73 | /* This is the data kept in all _free_ FRAGMENTS */ | ||
74 | struct MemFrag { | ||
75 | struct MemFrag *next; /* next free FRAGMENT */ | ||
76 | struct MemFrag *prev; /* prev free FRAGMENT */ | ||
77 | }; | ||
78 | |||
79 | /* This is the data kept in all _allocated_ FRAGMENTS and BLOCKS. We add this | ||
80 | to the allocation size first thing in the ALLOC function to make room for | ||
81 | this smoothly. */ | ||
82 | |||
83 | struct MemInfo { | ||
84 | void *block; | ||
85 | /* which BLOCK is our father, if BLOCK_BIT is set it means this is a | ||
86 | stand-alone, large allocation and then the rest of the bits should be | ||
87 | treated as the size of the block */ | ||
88 | #define BLOCK_BIT 1 | ||
89 | }; | ||
90 | |||
91 | /* ---------------------------------------------------------------------- */ | ||
92 | /* Defines */ | ||
93 | /* ---------------------------------------------------------------------- */ | ||
94 | |||
95 | #ifdef DEBUG_VERBOSE | ||
96 | #define MEMINCR(addr,x) memchange(addr, x) | ||
97 | #define MEMDECR(addr,x) memchange(addr,-(x)) | ||
98 | #else | ||
99 | #define MEMINCR(a,x) | ||
100 | #define MEMDECR(a,x) | ||
101 | #endif | ||
102 | |||
103 | /* The low level functions used to get memory from the OS and to return memory | ||
104 | to the OS, we may also define a stub that does the actual allocation and | ||
105 | free, these are the defined function names used in the dmalloc system | ||
106 | anyway: */ | ||
107 | #ifdef PSOS | ||
108 | |||
109 | #ifdef DEBUG_MALLOC | ||
110 | #define DMEM_OSALLOCMEM(size,pointer,type) pointer=(type)dbgmalloc(size) | ||
111 | #define DMEM_OSFREEMEM(x) dbgfree(x) | ||
112 | #else | ||
113 | #define DMEM_OSALLOCMEM(size,pointer,type) rn_getseg(0,size,RN_NOWAIT,0,(void **)&pointer) | ||
114 | /* Similar, but this returns the memory */ | ||
115 | #define DMEM_OSFREEMEM(x) rn_retseg(0, x) | ||
116 | #endif | ||
117 | |||
118 | /* Argument: <id> */ | ||
119 | #define SEMAPHOREOBTAIN(x) sm_p(x, SM_WAIT, 0) | ||
120 | /* Argument: <id> */ | ||
121 | #define SEMAPHORERETURN(x) sm_v(x) | ||
122 | /* Argument: <name> <id-variable name> */ | ||
123 | #define SEMAPHORECREATE(x,y) sm_create(x, 1, SM_FIFO, (ULONG *)&(y)) | ||
124 | |||
125 | #else | ||
126 | #ifdef BMALLOC /* use our own big-memory-allocation system */ | ||
127 | #define DMEM_OSALLOCMEM(size,pointer,type) pointer=(type)bmalloc(size) | ||
128 | #define DMEM_OSFREEMEM(x) bfree(x) | ||
129 | #elif DEBUG_MALLOC | ||
130 | #define DMEM_OSALLOCMEM(size,pointer,type) pointer=(type)dbgmalloc(size) | ||
131 | #define DMEM_OSFREEMEM(x) dbgfree(x) | ||
132 | #else | ||
133 | #define DMEM_OSALLOCMEM(size,pointer,type) pointer=(type)malloc(size) | ||
134 | #define DMEM_OSFREEMEM(x) free(x) | ||
135 | #endif | ||
136 | #endif | ||
137 | |||
138 | |||
139 | /* the largest memory allocation that is made a FRAGMENT: (grab the highest | ||
140 | number from the list below) */ | ||
141 | #define DMEM_LARGESTSIZE 2032 | ||
142 | |||
143 | /* The total size of a BLOCK used for FRAGMENTS | ||
144 | In order to make this use only *1* even alignment from the big-block- | ||
145 | allocation-system (possible the bmalloc() system also written by me) | ||
146 | we need to subtract the [maximum] struct sizes that could get added all | ||
147 | the way through to the grab from the memory. */ | ||
148 | #define DMEM_BLOCKSIZE 4064 /* (4096 - sizeof(struct MemBlock) - 12) */ | ||
149 | |||
150 | /* Since the blocksize isn't an even 2^X story anymore, we make a table with | ||
151 | the FRAGMENT sizes and amounts that fills up a BLOCK nicely */ | ||
152 | |||
153 | /* a little 'bc' script that helps us maximize the usage: | ||
154 | - for 32-bit aligned addresses (SPARC crashes otherwise): | ||
155 | for(i=20; i<2040; i+=4) { a=4064/i; if(a*i >= 4060) { {i;} } } | ||
156 | |||
157 | I try to approximate a double of each size, starting with ~20. We don't do | ||
158 | ODD sizes since several CPU flavours dump core when accessing such | ||
159 | addresses. We try to do 32-bit aligned to make ALL kinds of CPUs to remain | ||
160 | happy with us. | ||
161 | */ | ||
162 | |||
163 | static const unsigned short qinfo[]= { | ||
164 | 20, 28, 52, 116, 312, 580, 1016, 2032 | ||
165 | }; | ||
166 | |||
167 | #define MIN(x,y) ((x)<(y)?(x):(y)) | ||
168 | |||
169 | /* ---------------------------------------------------------------------- */ | ||
170 | /* Globals */ | ||
171 | /* ---------------------------------------------------------------------- */ | ||
172 | |||
173 | /* keeper of the chain of BLOCKS */ | ||
174 | static struct MemTop top[ sizeof(qinfo)/sizeof(qinfo[0]) ]; | ||
175 | |||
176 | /* ---------------------------------------------------------------------- */ | ||
177 | /* Start of the real code */ | ||
178 | /* ---------------------------------------------------------------------- */ | ||
179 | |||
180 | #ifdef DEBUG_MALLOC | ||
181 | /************ | ||
182 | * A few functions that are verbose and tells us about the current status | ||
183 | * of the dmalloc system | ||
184 | ***********/ | ||
185 | |||
186 | void dmalloc_status(void) | ||
187 | { | ||
188 | unsigned int i; | ||
189 | int used; | ||
190 | int num; | ||
191 | int totalfree=0; | ||
192 | struct MemBlock *block; | ||
193 | for(i=0; i<sizeof(qinfo)/sizeof(qinfo[0]);i++) { | ||
194 | block = top[i].chain; | ||
195 | used = 0; | ||
196 | num = 0; | ||
197 | while(block) { | ||
198 | used += top[i].nmax-block->nfree; | ||
199 | num++; | ||
200 | block = block->next; | ||
201 | } | ||
202 | printf("Q %d (FRAG %4d), USED %4d FREE %4ld (SIZE %4ld) BLOCKS %d\n", | ||
203 | i, top[i].fragsize, used, top[i].nfree, | ||
204 | top[i].nfree*top[i].fragsize, num); | ||
205 | totalfree += top[i].nfree*top[i].fragsize; | ||
206 | } | ||
207 | printf("Total unused memory stolen by dmalloc: %d\n", totalfree); | ||
208 | } | ||
209 | #endif | ||
210 | |||
211 | #ifdef DEBUG_VERBOSE | ||
212 | static void dmalloc_failed(size_t size) | ||
213 | { | ||
214 | printf("*** " __FILE__ " Couldn't allocate %d bytes\n", size); | ||
215 | dmalloc_status(); | ||
216 | } | ||
217 | #else | ||
218 | #define dmalloc_failed(x) | ||
219 | #endif | ||
220 | |||
221 | #ifdef DEBUG_VERBOSE | ||
222 | |||
223 | #define DBG(x) syslog x | ||
224 | |||
225 | void syslog(char *fmt, ...) | ||
226 | { | ||
227 | va_list ap; | ||
228 | va_start(ap, fmt); | ||
229 | vfprintf(stdout, fmt, ap); | ||
230 | va_end(ap); | ||
231 | } | ||
232 | |||
233 | void memchange(void *a, int x) | ||
234 | { | ||
235 | static int memory=0; | ||
236 | static int count=0; | ||
237 | static int max=0; | ||
238 | if(memory > max) | ||
239 | max = memory; | ||
240 | memory += x; | ||
241 | DBG(("%d. PTR %p / %d TOTAL %d MAX %d\n", ++count, a, x, memory, max)); | ||
242 | } | ||
243 | #else | ||
244 | #define DBG(x) | ||
245 | #endif | ||
246 | |||
247 | /**************************************************************************** | ||
248 | * | ||
249 | * FragBlock() | ||
250 | * | ||
251 | * This function makes FRAGMENTS of the BLOCK sent as argument. | ||
252 | * | ||
253 | ***************************************************************************/ | ||
254 | |||
255 | static void FragBlock(char *memp, int size) | ||
256 | { | ||
257 | struct MemFrag *frag=(struct MemFrag *)memp; | ||
258 | struct MemFrag *prev=NULL; /* no previous in the first round */ | ||
259 | int count=0; | ||
260 | while((count+size) <= DMEM_BLOCKSIZE) { | ||
261 | frag->next = (struct MemFrag *)((char *)frag + size); | ||
262 | frag->prev = prev; | ||
263 | prev = frag; | ||
264 | (char *)frag += size; | ||
265 | count += size; | ||
266 | } | ||
267 | prev->next = NULL; /* the last one has no next struct */ | ||
268 | } | ||
269 | |||
270 | /*************************************************************************** | ||
271 | * | ||
272 | * dmalloc_initialize(); | ||
273 | * | ||
274 | * Call before the first dmalloc(). Inits a few memory things. | ||
275 | * | ||
276 | **************************************************************************/ | ||
277 | void dmalloc_initialize(void) | ||
278 | { | ||
279 | unsigned int i; | ||
280 | /* Setup the nmax and fragsize fields of the top structs */ | ||
281 | for(i=0; i< sizeof(qinfo)/sizeof(qinfo[0]); i++) { | ||
282 | top[i].fragsize = qinfo[i]; | ||
283 | top[i].nmax = DMEM_BLOCKSIZE/qinfo[i]; | ||
284 | |||
285 | #ifdef PSOS | ||
286 | /* for some reason, these aren't nulled from start: */ | ||
287 | top[i].chain = NULL; /* no BLOCKS */ | ||
288 | top[i].nfree = 0; /* no FRAGMENTS */ | ||
289 | #endif | ||
290 | #ifdef SEMAPHORE | ||
291 | { | ||
292 | char name[7]; | ||
293 | snprintf(name, 7, "MEM%d", i); | ||
294 | SEMAPHORECREATE(name, top[i].semaphore_id); | ||
295 | /* doesn't matter if it failed, we continue anyway ;-( */ | ||
296 | } | ||
297 | #endif | ||
298 | } | ||
299 | } | ||
300 | |||
301 | /**************************************************************************** | ||
302 | * | ||
303 | * fragfromblock() | ||
304 | * | ||
305 | * This should return a fragment from the block and mark it as used | ||
306 | * accordingly. | ||
307 | * | ||
308 | ***************************************************************************/ | ||
309 | |||
310 | static void *fragfromblock(struct MemBlock *block) | ||
311 | { | ||
312 | /* make frag point to the first free FRAGMENT */ | ||
313 | struct MemFrag *frag = block->first; | ||
314 | struct MemInfo *mem = (struct MemInfo *)frag; | ||
315 | |||
316 | /* | ||
317 | * Remove the FRAGMENT from the list and decrease the free counters. | ||
318 | */ | ||
319 | block->first = frag->next; /* new first free FRAGMENT */ | ||
320 | |||
321 | block->nfree--; /* BLOCK counter */ | ||
322 | block->top->nfree--; /* TOP counter */ | ||
323 | |||
324 | /* heal the FRAGMENT list */ | ||
325 | if(frag->prev) { | ||
326 | frag->prev->next = frag->next; | ||
327 | } | ||
328 | if(frag->next) { | ||
329 | frag->next->prev = frag->prev; | ||
330 | } | ||
331 | mem->block = block; /* no block bit set here */ | ||
332 | |||
333 | return ((char *)mem)+sizeof(struct MemInfo); | ||
334 | } | ||
335 | |||
336 | /*************************************************************************** | ||
337 | * | ||
338 | * dmalloc() | ||
339 | * | ||
340 | * This needs no explanation. A malloc() look-alike. | ||
341 | * | ||
342 | **************************************************************************/ | ||
343 | |||
344 | void *malloc(size_t size) | ||
345 | { | ||
346 | void *mem; | ||
347 | |||
348 | DBG(("malloc(%d)\n", size)); | ||
349 | |||
350 | /* First, we make room for the space needed in every allocation */ | ||
351 | size += sizeof(struct MemInfo); | ||
352 | |||
353 | if(size < DMEM_LARGESTSIZE) { | ||
354 | /* get a FRAGMENT */ | ||
355 | |||
356 | struct MemBlock *block=NULL; /* SAFE */ | ||
357 | struct MemBlock *newblock=NULL; /* SAFE */ | ||
358 | struct MemTop *memtop=NULL; /* SAFE */ | ||
359 | |||
360 | /* Determine which queue to use */ | ||
361 | unsigned int queue; | ||
362 | for(queue=0; size > qinfo[queue]; queue++) | ||
363 | ; | ||
364 | do { | ||
365 | /* This is the head master of our chain: */ | ||
366 | memtop = &top[queue]; | ||
367 | |||
368 | DBG(("Top info: CHAIN %p FREE %d MAX %d FRAGSIZE %d\n", | ||
369 | memtop->chain, | ||
370 | memtop->nfree, | ||
371 | memtop->nmax, | ||
372 | memtop->fragsize)); | ||
373 | |||
374 | #ifdef SEMAPHORE | ||
375 | if(SEMAPHOREOBTAIN(memtop->semaphore_id)) | ||
376 | return NULL; /* failed somehow */ | ||
377 | #endif | ||
378 | |||
379 | /* get the first BLOCK in the chain */ | ||
380 | block = memtop->chain; | ||
381 | |||
382 | /* check if we have a free FRAGMENT */ | ||
383 | if(memtop->nfree) { | ||
384 | /* there exists a free FRAGMENT in this chain */ | ||
385 | |||
386 | /**** We'd prefer to not have this loop here! ****/ | ||
387 | |||
388 | /* search for the free FRAGMENT */ | ||
389 | while(!block->nfree) | ||
390 | block = block->next; /* check next BLOCK */ | ||
391 | |||
392 | /* | ||
393 | * Now 'block' is the first BLOCK with a free FRAGMENT | ||
394 | */ | ||
395 | |||
396 | mem = fragfromblock(block); | ||
397 | |||
398 | } | ||
399 | else { | ||
400 | /* we do *not* have a free FRAGMENT but need to get us a new | ||
401 | * BLOCK */ | ||
402 | |||
403 | DMEM_OSALLOCMEM(DMEM_BLOCKSIZE + sizeof(struct MemBlock), | ||
404 | newblock, | ||
405 | struct MemBlock *); | ||
406 | if(!newblock) { | ||
407 | if(++queue < sizeof(qinfo)/sizeof(qinfo[0])) { | ||
408 | /* There are queues for bigger FRAGMENTS that we | ||
409 | * should check before we fail this for real */ | ||
410 | #ifdef DEBUG_VERBOSE | ||
411 | printf("*** " __FILE__ " Trying a bigger Q: %d\n", | ||
412 | queue); | ||
413 | #endif | ||
414 | mem = NULL; | ||
415 | } | ||
416 | else { | ||
417 | dmalloc_failed(size- sizeof(struct MemInfo)); | ||
418 | return NULL; /* not enough memory */ | ||
419 | } | ||
420 | } | ||
421 | else { | ||
422 | /* allocation of big BLOCK was successful */ | ||
423 | MEMINCR(newblock, DMEM_BLOCKSIZE + | ||
424 | sizeof(struct MemBlock)); | ||
425 | |||
426 | memtop->chain = newblock; /* attach this BLOCK to the | ||
427 | chain */ | ||
428 | newblock->next = block; /* point to the previous first | ||
429 | BLOCK */ | ||
430 | if(block) | ||
431 | block->prev = newblock; /* point back on this new | ||
432 | BLOCK */ | ||
433 | newblock->prev = NULL; /* no previous */ | ||
434 | newblock->top = memtop; /* our head master */ | ||
435 | |||
436 | /* point to the new first FRAGMENT */ | ||
437 | newblock->first = (struct MemFrag *) | ||
438 | ((char *)newblock+sizeof(struct MemBlock)); | ||
439 | |||
440 | /* create FRAGMENTS of the BLOCK: */ | ||
441 | FragBlock((char *)newblock->first, memtop->fragsize); | ||
442 | |||
443 | /* fix the nfree counters */ | ||
444 | newblock->nfree = memtop->nmax; | ||
445 | memtop->nfree += memtop->nmax; | ||
446 | |||
447 | /* get a FRAGMENT from the BLOCK */ | ||
448 | mem = fragfromblock(newblock); | ||
449 | } | ||
450 | } | ||
451 | #ifdef SEMAPHORE | ||
452 | SEMAPHORERETURN(memtop->semaphore_id); /* let it go */ | ||
453 | #endif | ||
454 | } while(NULL == mem); /* if we should retry a larger FRAGMENT */ | ||
455 | } | ||
456 | else { | ||
457 | /* get a stand-alone BLOCK */ | ||
458 | struct MemInfo *meminfo; | ||
459 | |||
460 | if(size&1) | ||
461 | /* don't leave this with an odd size since we'll use that bit for | ||
462 | information */ | ||
463 | size++; | ||
464 | |||
465 | DMEM_OSALLOCMEM(size, meminfo, struct MemInfo *); | ||
466 | |||
467 | if(meminfo) { | ||
468 | MEMINCR(meminfo, size); | ||
469 | meminfo->block = (void *)(size|BLOCK_BIT); | ||
470 | mem = (char *)meminfo + sizeof(struct MemInfo); | ||
471 | } | ||
472 | else { | ||
473 | dmalloc_failed(size); | ||
474 | mem = NULL; | ||
475 | } | ||
476 | } | ||
477 | return (void *)mem; | ||
478 | } | ||
479 | |||
480 | /*************************************************************************** | ||
481 | * | ||
482 | * dfree() | ||
483 | * | ||
484 | * This needs no explanation. A free() look-alike. | ||
485 | * | ||
486 | **************************************************************************/ | ||
487 | |||
488 | void free(void *memp) | ||
489 | { | ||
490 | struct MemInfo *meminfo = (struct MemInfo *) | ||
491 | ((char *)memp- sizeof(struct MemInfo)); | ||
492 | |||
493 | DBG(("free(%p)\n", memp)); | ||
494 | |||
495 | if(!((size_t)meminfo->block&BLOCK_BIT)) { | ||
496 | /* this is a FRAGMENT we have to deal with */ | ||
497 | |||
498 | struct MemBlock *block=meminfo->block; | ||
499 | struct MemTop *memtop = block->top; | ||
500 | |||
501 | #ifdef SEMAPHORE | ||
502 | SEMAPHOREOBTAIN(memtop->semaphore_id); | ||
503 | #endif | ||
504 | |||
505 | /* increase counters */ | ||
506 | block->nfree++; | ||
507 | memtop->nfree++; | ||
508 | |||
509 | /* is this BLOCK completely empty now? */ | ||
510 | if(block->nfree == memtop->nmax) { | ||
511 | /* yes, return the BLOCK to the system */ | ||
512 | if(block->prev) | ||
513 | block->prev->next = block->next; | ||
514 | else | ||
515 | memtop->chain = block->next; | ||
516 | if(block->next) | ||
517 | block->next->prev = block->prev; | ||
518 | |||
519 | memtop->nfree -= memtop->nmax; /* total counter subtraction */ | ||
520 | MEMDECR(block, DMEM_BLOCKSIZE + sizeof(struct MemBlock)); | ||
521 | DMEM_OSFREEMEM((void *)block); /* return the whole block */ | ||
522 | } | ||
523 | else { | ||
524 | /* there are still used FRAGMENTS in the BLOCK, link this one | ||
525 | into the chain of free ones */ | ||
526 | struct MemFrag *frag = (struct MemFrag *)meminfo; | ||
527 | frag->prev = NULL; | ||
528 | frag->next = block->first; | ||
529 | if(block->first) | ||
530 | block->first->prev = frag; | ||
531 | block->first = frag; | ||
532 | } | ||
533 | #ifdef SEMAPHORE | ||
534 | SEMAPHORERETURN(memtop->semaphore_id); | ||
535 | #endif | ||
536 | } | ||
537 | else { | ||
538 | /* big stand-alone block, just give it back to the OS: */ | ||
539 | |||
540 | /* clean BLOCK_BIT */ | ||
541 | MEMDECR(meminfo->block, (size_t)meminfo->block&~BLOCK_BIT); | ||
542 | DMEM_OSFREEMEM((void *)meminfo); | ||
543 | } | ||
544 | } | ||
545 | |||
546 | /*************************************************************************** | ||
547 | * | ||
548 | * drealloc() | ||
549 | * | ||
550 | * This needs no explanation. A realloc() look-alike. | ||
551 | * | ||
552 | **************************************************************************/ | ||
553 | |||
554 | void *realloc(void *ptr, size_t size) | ||
555 | { | ||
556 | struct MemInfo *meminfo = (struct MemInfo *) | ||
557 | ((char *)ptr- sizeof(struct MemInfo)); | ||
558 | /* | ||
559 | * ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ | ||
560 | * NOTE: the ->size field of the meminfo will now contain the MemInfo | ||
561 | * struct size too! | ||
562 | * ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ | ||
563 | */ | ||
564 | void *mem=NULL; /* SAFE */ | ||
565 | size_t prevsize; | ||
566 | |||
567 | /* NOTE that this is only valid if BLOCK_BIT isn't set: */ | ||
568 | struct MemBlock *block; | ||
569 | |||
570 | DBG(("realloc(%p, %d)\n", ptr, size)); | ||
571 | |||
572 | if(NULL == ptr) | ||
573 | return malloc( size ); | ||
574 | |||
575 | block = meminfo->block; | ||
576 | |||
577 | /* Here we check if this is a FRAGMENT and if the new size is | ||
578 | still smaller than the fragsize for this block. */ | ||
579 | if(!((size_t)block&BLOCK_BIT) && | ||
580 | (size + sizeof(struct MemInfo) < block->top->fragsize )) { | ||
581 | |||
582 | prevsize = block->top->fragsize; | ||
583 | /* This is a FRAGMENT and new size is possible to retain within the | ||
584 | same FRAGMENT */ | ||
585 | if((prevsize > qinfo[0]) && | ||
586 | /* this is not the smallest memory Q */ | ||
587 | (size < (block->top-1)->fragsize)) | ||
588 | /* This fits in a smaller fragment, so we will make a realloc | ||
589 | here */ | ||
590 | ; | ||
591 | else | ||
592 | mem = ptr; /* Just return the same pointer as we got in. */ | ||
593 | } | ||
594 | if(!mem) { | ||
595 | if((size_t)meminfo->block&BLOCK_BIT) { | ||
596 | /* This is a stand-alone BLOCK */ | ||
597 | prevsize = ((size_t)meminfo->block&~BLOCK_BIT) - | ||
598 | sizeof(struct MemInfo); | ||
599 | } | ||
600 | else | ||
601 | /* a FRAGMENT realloc that no longer fits within the same FRAGMENT | ||
602 | * or one that fits in a smaller */ | ||
603 | prevsize = block->top->fragsize; | ||
604 | |||
605 | /* No tricks involved here, just grab a new bite of memory, copy the | ||
606 | * data from the old place and free the old memory again. */ | ||
607 | mem = malloc(size); | ||
608 | if(mem) { | ||
609 | memcpy(mem, ptr, MIN(size, prevsize) ); | ||
610 | free(ptr); | ||
611 | } | ||
612 | } | ||
613 | return mem; | ||
614 | } | ||
615 | |||
616 | /*************************************************************************** | ||
617 | * | ||
618 | * dcalloc() | ||
619 | * | ||
620 | * This needs no explanation. A calloc() look-alike. | ||
621 | * | ||
622 | **************************************************************************/ | ||
623 | /* Allocate an array of NMEMB elements each SIZE bytes long. | ||
624 | The entire array is initialized to zeros. */ | ||
625 | void * | ||
626 | calloc (size_t nmemb, size_t size) | ||
627 | { | ||
628 | void *result = malloc (nmemb * size); | ||
629 | |||
630 | if (result != NULL) | ||
631 | memset (result, 0, nmemb * size); | ||
632 | |||
633 | return result; | ||
634 | } | ||
diff --git a/firmware/malloc/dmalloc.h b/firmware/malloc/dmalloc.h deleted file mode 100644 index 96772a46f5..0000000000 --- a/firmware/malloc/dmalloc.h +++ /dev/null | |||
@@ -1,36 +0,0 @@ | |||
1 | /*************************************************************************** | ||
2 | * __________ __ ___. | ||
3 | * Open \______ \ ____ ____ | | _\_ |__ _______ ___ | ||
4 | * Source | _// _ \_/ ___\| |/ /| __ \ / _ \ \/ / | ||
5 | * Jukebox | | ( <_> ) \___| < | \_\ ( <_> > < < | ||
6 | * Firmware |____|_ /\____/ \___ >__|_ \|___ /\____/__/\_ \ | ||
7 | * \/ \/ \/ \/ \/ | ||
8 | * $Id$ | ||
9 | * | ||
10 | * Copyright (C) 2002 by Daniel Stenberg | ||
11 | * | ||
12 | * All files in this archive are subject to the GNU General Public License. | ||
13 | * See the file COPYING in the source tree root for full license agreement. | ||
14 | * | ||
15 | * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY | ||
16 | * KIND, either express or implied. | ||
17 | * | ||
18 | ****************************************************************************/ | ||
19 | #ifndef _DMALLOC_H_ | ||
20 | #define _DMALLOC_H_ | ||
21 | |||
22 | #include <stdlib.h> | ||
23 | |||
24 | void *malloc(size_t); | ||
25 | void *calloc (size_t nmemb, size_t size); | ||
26 | void free(void *); | ||
27 | void *realloc(void *, size_t); | ||
28 | |||
29 | /* use this to intialize the internals of the dmalloc engine */ | ||
30 | void dmalloc_initialize(void); | ||
31 | |||
32 | #ifdef DEBUG | ||
33 | void dmalloc_status(void); | ||
34 | #endif | ||
35 | |||
36 | #endif | ||