summaryrefslogtreecommitdiff
path: root/firmware/malloc/bmalloc.c
diff options
context:
space:
mode:
Diffstat (limited to 'firmware/malloc/bmalloc.c')
-rw-r--r--firmware/malloc/bmalloc.c386
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 */
48struct 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 */
68struct BlockInfo *blockHead=NULL; /* nothing from the start */
69
70void bmalloc_status(void);
71
72
73/***********************************************************************
74 *
75 * remove_block()
76 *
77 * Remove the block from the address-sorted list.
78 *
79 ***********************************************************************/
80
81static
82void 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 ***************************************************************************/
100static
101void 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
184static
185struct 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
210int 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
232static 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
241void 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
268void *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
332void 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
generated by cgit v1.2.3 (git 2.39.1) at 2024-09-23 22:22:21 +0000