summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorDaniel Stenberg <daniel@haxx.se>2004-01-08 15:42:18 +0000
committerDaniel Stenberg <daniel@haxx.se>2004-01-08 15:42:18 +0000
commit21fba08fc3a66c7f395b2a95b3e6dd3dfd9c8002 (patch)
treec09efc5f6b49743bf2aa5d1ce6076982057b4eb5
parente428647018d98a0e9678120ceb4b8b0d538a0099 (diff)
downloadrockbox-21fba08fc3a66c7f395b2a95b3e6dd3dfd9c8002.tar.gz
rockbox-21fba08fc3a66c7f395b2a95b3e6dd3dfd9c8002.zip
not used
git-svn-id: svn://svn.rockbox.org/rockbox/trunk@4209 a1c6a512-1295-4272-9138-f99709370657
Diffstat
-rw-r--r--firmware/malloc/Makefile40
-rw-r--r--firmware/malloc/README21
-rw-r--r--firmware/malloc/THOUGHTS170
-rw-r--r--firmware/malloc/bmalloc.c386
-rw-r--r--firmware/malloc/bmalloc.h30
-rw-r--r--firmware/malloc/bysize.c451
-rw-r--r--firmware/malloc/bysize.h24
-rw-r--r--firmware/malloc/dmalloc.c634
-rw-r--r--firmware/malloc/dmalloc.h36
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
18TARGET = libdmalloc.a
19
20LIBOBJS = dmalloc.o bmalloc.o bysize.o
21
22# define this to talk a lot in runtime
23# -DDEBUG_VERBOSE
24CFLAGS = -g -W -Wall -DDEBUG_MALLOC
25CC = gcc
26AR = ar
27
28LDFLAGS = -L. -ldmalloc
29
30all: $(TARGET)
31
32clean:
33 rm -f core *~ $(TARGET) $(LIBOBJS)
34
35$(TARGET): $(LIBOBJS)
36 $(AR) ruv $(TARGET) $(LIBOBJS)
37
38bmalloc.o: bmalloc.c bysize.h
39bysize.o: bysize.c
40dmalloc.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 @@
1Package: dbestfit - a dynamic best-fit memory allocator
2Date: 1996 - 2002
3Version: 3.3
4Author: Daniel Stenberg <daniel@haxx.se>
5License: 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
8of the built-in (first-fit) allocator found in pSOS, during late 1996 and
9spring 1997.
10
11 I wrote the bmalloc part (best-fit with optional splay-tree sorting) just for
12the fun of it and to see how good malloc() implementation I could make. The
13quality of my implementation is still left to be judged in real-world tests.
14
15TODO:
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
5GOAL
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
16TERMINOLOGY
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
26MEMORY 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 */
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
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
24int bmalloc_add_pool(void *start, size_t size);
25void bmalloc_status(void);
26
27void *bmalloc(size_t size);
28void 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
50struct ChunkInfo {
51 struct ChunkInfo *larger;
52 struct ChunkInfo *smaller;
53 size_t size;
54};
55
56/* the CHUNK list anchor */
57struct 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
68static 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
86void 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
99void 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
125char *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
148void 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
164typedef struct tree_node Tree;
165struct 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
172Tree *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 */
183static
184Tree * 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. */
244static
245Tree *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. */
291static
292Tree *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. */
346static
347Tree *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
392static
393int 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
427void bmalloc_remove_chunksize(void *data)
428{
429 chunkHead = removebyaddr(chunkHead, data);
430}
431
432void bmalloc_insert_bysize(char *data, size_t size)
433{
434 chunkHead = insert(size, chunkHead, (Tree *)data);
435}
436
437char *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
445void 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 ****************************************************************************/
19void bmalloc_remove_chunksize(void *data);
20void bmalloc_insert_bysize(char *data, size_t size);
21char *bmalloc_obtainbysize( size_t size);
22#ifdef DEBUG_MALLOC
23void 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 */
50struct 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 */
63struct 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 */
74struct 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
83struct 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
163static 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 */
174static 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
186void 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
212static 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
225void syslog(char *fmt, ...)
226{
227 va_list ap;
228 va_start(ap, fmt);
229 vfprintf(stdout, fmt, ap);
230 va_end(ap);
231}
232
233void 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
255static 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 **************************************************************************/
277void 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
310static 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
344void *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
488void 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
554void *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. */
625void *
626calloc (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
24void *malloc(size_t);
25void *calloc (size_t nmemb, size_t size);
26void free(void *);
27void *realloc(void *, size_t);
28
29/* use this to intialize the internals of the dmalloc engine */
30void dmalloc_initialize(void);
31
32#ifdef DEBUG
33void dmalloc_status(void);
34#endif
35
36#endif
generated by cgit v1.2.3 (git 2.39.1) at 2024-09-23 20:15:38 +0000