summaryrefslogtreecommitdiff
path: root/firmware/malloc/dmalloc.c
diff options
context:
space:
mode:
Diffstat (limited to 'firmware/malloc/dmalloc.c')
-rw-r--r--firmware/malloc/dmalloc.c634
1 files changed, 0 insertions, 634 deletions
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}
generated by cgit v1.2.3 (git 2.39.1) at 2024-09-23 22:30:41 +0000