diff options
Diffstat (limited to 'firmware/malloc/bmalloc.c')
-rw-r--r-- | firmware/malloc/bmalloc.c | 386 |
1 files changed, 0 insertions, 386 deletions
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 | |||