summaryrefslogtreecommitdiff
path: root/apps/plugins/pdbox/dbestfit-3.3/dmalloc.c
diff options
context:
space:
mode:
Diffstat (limited to 'apps/plugins/pdbox/dbestfit-3.3/dmalloc.c')
-rw-r--r--apps/plugins/pdbox/dbestfit-3.3/dmalloc.c711
1 files changed, 0 insertions, 711 deletions
diff --git a/apps/plugins/pdbox/dbestfit-3.3/dmalloc.c b/apps/plugins/pdbox/dbestfit-3.3/dmalloc.c
deleted file mode 100644
index b46d4af926..0000000000
--- a/apps/plugins/pdbox/dbestfit-3.3/dmalloc.c
+++ /dev/null
@@ -1,711 +0,0 @@
1/*****************************************************************************
2 *
3 * Dynamic Memory Allocation
4 *
5 * Author: Daniel Stenberg
6 * Date: March 10, 1997
7 * Version: 2.3
8 * Email: Daniel.Stenberg@sth.frontec.se
9 *
10 *
11 * Read 'thoughts' for theories and details of this implementation.
12 *
13 * v2.1
14 * - I once again managed to gain some memory. BLOCK allocations now only use
15 * a 4 bytes header (instead of previos 8) just as FRAGMENTS.
16 *
17 * v2.2
18 * - Re-adjusted the fragment sizes to better fit into the somewhat larger
19 * block.
20 *
21 * v2.3
22 * - Made realloc(NULL, size) work as it should. Which is like a malloc(size)
23 *
24 *****************************************************************************/
25
26#ifdef ROCKBOX
27#include "plugin.h"
28#define memset rb->memset
29#define memcpy rb->memcpy
30#else /* ROCKBOX */
31#include <stdio.h>
32#include <string.h>
33#endif /* ROCKBOX */
34
35#ifdef DEBUG
36#include <stdarg.h>
37#endif
38
39#ifdef PSOS
40#include <psos.h>
41#define SEMAPHORE /* the PSOS routines use semaphore protection */
42#else
43#include <stdlib.h> /* makes the PSOS complain on the 'size_t' typedef */
44#endif
45
46#ifdef BMALLOC
47#include "bmalloc.h"
48#endif
49
50/* Each TOP takes care of a chain of BLOCKS */
51struct MemTop {
52 struct MemBlock *chain; /* pointer to the BLOCK chain */
53 long nfree; /* total number of free FRAGMENTS in the chain */
54 short nmax; /* total number of FRAGMENTS in this kind of BLOCK */
55 size_t fragsize; /* the size of each FRAGMENT */
56
57#ifdef SEMAPHORE /* if we're protecting the list with SEMAPHORES */
58 long semaphore_id; /* semaphore used to lock this particular list */
59#endif
60
61};
62
63/* Each BLOCK takes care of an amount of FRAGMENTS */
64struct MemBlock {
65 struct MemTop *top; /* our TOP struct */
66 struct MemBlock *next; /* next BLOCK */
67 struct MemBlock *prev; /* prev BLOCK */
68
69 struct MemFrag *first; /* the first free FRAGMENT in this block */
70
71 short nfree; /* number of free FRAGMENTS in this BLOCK */
72};
73
74/* This is the data kept in all _free_ FRAGMENTS */
75struct MemFrag {
76 struct MemFrag *next; /* next free FRAGMENT */
77 struct MemFrag *prev; /* prev free FRAGMENT */
78};
79
80/* This is the data kept in all _allocated_ FRAGMENTS and BLOCKS. We add this
81 to the allocation size first thing in the ALLOC function to make room for
82 this smoothly. */
83
84struct MemInfo {
85 void *block;
86 /* which BLOCK is our father, if BLOCK_BIT is set it means this is a
87 stand-alone, large allocation and then the rest of the bits should be
88 treated as the size of the block */
89#define BLOCK_BIT 1
90};
91
92/* ---------------------------------------------------------------------- */
93/* Defines */
94/* ---------------------------------------------------------------------- */
95
96#ifdef DEBUG
97#define MEMINCR(addr,x) memchange(addr, x)
98#define MEMDECR(addr,x) memchange(addr,-(x))
99#else
100#define MEMINCR(a,x)
101#define MEMDECR(a,x)
102#endif
103
104/* The low level functions used to get memory from the OS and to return memory
105 to the OS, we may also define a stub that does the actual allocation and
106 free, these are the defined function names used in the dmalloc system
107 anyway: */
108#ifdef PSOS
109
110#ifdef DEBUG
111#define DMEM_OSALLOCMEM(size,pointer,type) pointer=(type)dbgmalloc(size)
112#define DMEM_OSFREEMEM(x) dbgfree(x)
113#else
114#define DMEM_OSALLOCMEM(size,pointer,type) rn_getseg(0,size,RN_NOWAIT,0,(void **)&pointer)
115/* Similar, but this returns the memory */
116#define DMEM_OSFREEMEM(x) rn_retseg(0, x)
117#endif
118
119/* Argument: <id> */
120#define SEMAPHOREOBTAIN(x) sm_p(x, SM_WAIT, 0)
121/* Argument: <id> */
122#define SEMAPHORERETURN(x) sm_v(x)
123/* Argument: <name> <id-variable name> */
124#define SEMAPHORECREATE(x,y) sm_create(x, 1, SM_FIFO, (ULONG *)&(y))
125
126#else
127#ifdef BMALLOC /* use our own big-memory-allocation system */
128#define DMEM_OSALLOCMEM(size,pointer,type) pointer=(type)bmalloc(size)
129#define DMEM_OSFREEMEM(x) bfree(x)
130#elif DEBUG
131#define DMEM_OSALLOCMEM(size,pointer,type) pointer=(type)dbgmalloc(size)
132#define DMEM_OSFREEMEM(x) dbgfree(x)
133#else
134#define DMEM_OSALLOCMEM(size,pointer,type) pointer=(type)malloc(size)
135#define DMEM_OSFREEMEM(x) free(x)
136#endif
137#endif
138
139
140/* the largest memory allocation that is made a FRAGMENT: (grab the highest
141 number from the list below) */
142#define DMEM_LARGESTSIZE 2032
143
144/* The total size of a BLOCK used for FRAGMENTS
145 In order to make this use only *1* even alignment from the big-block-
146 allocation-system (possible the bmalloc() system also written by me)
147 we need to subtract the [maximum] struct sizes that could get added all
148 the way through to the grab from the memory. */
149#define DMEM_BLOCKSIZE 4064 /* (4096 - sizeof(struct MemBlock) - 12) */
150
151/* Since the blocksize isn't an even 2^X story anymore, we make a table with
152 the FRAGMENT sizes and amounts that fills up a BLOCK nicely */
153
154/* a little 'bc' script that helps us maximize the usage:
155 - for 32-bit aligned addresses (SPARC crashes otherwise):
156 for(i=20; i<2040; i++) { a=4064/i; if(a*i >= 4060) { if(i%4==0) {i;} } }
157
158
159 I try to approximate a double of each size, starting with ~20. We don't do
160 ODD sizes since several CPU flavours dump core when accessing such
161 addresses. We try to do 32-bit aligned to make ALL kinds of CPUs to remain
162 happy with us.
163 */
164
165#if defined(BIGBLOCKS) && BIGBLOCKS==4060 /* previously */
166#ifdef ROCKBOX
167unsigned
168#endif /* ROCKBOX */
169short qinfo[]= { 20, 28, 52, 116, 312, 580, 812, 2028 };
170#else
171#ifdef ROCKBOX
172unsigned
173#endif /* ROCKBOX */
174short qinfo[]= { 20, 28, 52, 116, 312, 580, 1016, 2032};
175/* 52 and 312 only make use of 4056 bytes, but without them there are too
176 wide gaps */
177#endif
178
179#ifndef ROCKBOX
180#define MIN(x,y) ((x)<(y)?(x):(y))
181#endif /* ROCKBOX */
182
183/* ---------------------------------------------------------------------- */
184/* Globals */
185/* ---------------------------------------------------------------------- */
186
187/* keeper of the chain of BLOCKS */
188static struct MemTop top[ sizeof(qinfo)/sizeof(qinfo[0]) ];
189
190/* are we experienced? */
191static char initialized = 0;
192
193/* ---------------------------------------------------------------------- */
194/* Start of the real code */
195/* ---------------------------------------------------------------------- */
196
197#ifdef DEBUG
198/************
199 * A few functions that are verbose and tells us about the current status
200 * of the dmalloc system
201 ***********/
202
203static void dmalloc_status()
204{
205 int i;
206 int used;
207 int num;
208 int totalfree=0;
209 struct MemBlock *block;
210 for(i=0; i<sizeof(qinfo)/sizeof(qinfo[0]);i++) {
211 block = top[i].chain;
212 used = 0;
213 num = 0;
214 while(block) {
215 used += top[i].nmax-block->nfree;
216 num++;
217 block = block->next;
218 }
219 printf("Q %d (FRAG %4d), USED %4d FREE %4ld (SIZE %4ld) BLOCKS %d\n",
220 i, top[i].fragsize, used, top[i].nfree,
221 top[i].nfree*top[i].fragsize, num);
222 totalfree += top[i].nfree*top[i].fragsize;
223 }
224 printf("Total unused memory stolen by dmalloc: %d\n", totalfree);
225}
226
227static void dmalloc_failed(size_t size)
228{
229 printf("*** " __FILE__ " Couldn't allocate %d bytes\n", size);
230 dmalloc_status();
231}
232#else
233#define dmalloc_failed(x)
234#endif
235
236#ifdef DEBUG
237
238#define BORDER 1200
239
240void *dbgmalloc(int size)
241{
242 char *mem;
243 size += BORDER;
244#ifdef PSOS
245 rn_getseg(0,size,RN_NOWAIT,0,(void **)&mem);
246#else
247 mem = malloc(size);
248#endif
249 if(mem) {
250 memset(mem, 0xaa, BORDER/2);
251 memset(mem+BORDER/2, 0xbb, size -BORDER);
252 memset(mem-BORDER/2+size, 0xcc, BORDER/2);
253 *(long *)mem = size;
254 mem += (BORDER/2);
255 }
256 printf("OSmalloc(%p)\n", mem);
257 return (void *)mem;
258}
259
260void checkmem(char *ptr)
261{
262 int i;
263 long size;
264 ptr -= BORDER/2;
265
266 for(i=4; i<(BORDER/2); i++)
267 if((unsigned char)ptr[i] != 0xaa) {
268 printf("########### ALERT ALERT\n");
269 break;
270 }
271 size = *(long *)ptr;
272 for(i=size-1; i>=(size - BORDER/2); i--)
273 if((unsigned char)ptr[i] != 0xcc) {
274 printf("********* POST ALERT\n");
275 break;
276 }
277}
278
279void dbgfree(char *ptr)
280{
281 long size;
282 checkmem(ptr);
283 ptr -= BORDER/2;
284 size = *(long *)ptr;
285
286 printf("OSfree(%ld)\n", size);
287#ifdef PSOS
288 rn_retseg(0, ptr);
289#else
290 free(ptr);
291#endif
292}
293
294
295#define DBG(x) syslog x
296
297void syslog(char *fmt, ...)
298{
299 va_list ap;
300 va_start(ap, fmt);
301 vfprintf(stdout, fmt, ap);
302 va_end(ap);
303}
304
305void memchange(void *a, int x)
306{
307 static int memory=0;
308 static int count=0;
309 static int max=0;
310 if(memory > max)
311 max = memory;
312 memory += x;
313 DBG(("%d. PTR %p / %d TOTAL %d MAX %d\n", ++count, a, x, memory, max));
314}
315#else
316#define DBG(x)
317#endif
318
319/****************************************************************************
320 *
321 * FragBlock()
322 *
323 * This function makes FRAGMENTS of the BLOCK sent as argument.
324 *
325 ***************************************************************************/
326
327static void FragBlock(char *memp, int size)
328{
329 struct MemFrag *frag=(struct MemFrag *)memp;
330 struct MemFrag *prev=NULL; /* no previous in the first round */
331 int count=0;
332 while((count+size) <= DMEM_BLOCKSIZE) {
333 memp += size;
334 frag->next = (struct MemFrag *)memp;
335 frag->prev = prev;
336 prev = frag;
337 frag = frag->next;
338 count += size;
339 }
340 prev->next = NULL; /* the last one has no next struct */
341}
342
343/***************************************************************************
344 *
345 * initialize();
346 *
347 * Called in the first dmalloc(). Inits a few memory things.
348 *
349 **************************************************************************/
350static void initialize(void)
351{
352#ifdef ROCKBOX
353 unsigned
354#endif /* ROCKBOX */
355 int i;
356 /* Setup the nmax and fragsize fields of the top structs */
357 for(i=0; i< sizeof(qinfo)/sizeof(qinfo[0]); i++) {
358 top[i].fragsize = qinfo[i];
359 top[i].nmax = DMEM_BLOCKSIZE/qinfo[i];
360
361#ifdef PSOS
362 /* for some reason, these aren't nulled from start: */
363 top[i].chain = NULL; /* no BLOCKS */
364 top[i].nfree = 0; /* no FRAGMENTS */
365#endif
366#ifdef SEMAPHORE
367 {
368 char name[7];
369 sprintf(name, "MEM%d", i);
370 SEMAPHORECREATE(name, top[i].semaphore_id);
371 /* doesn't matter if it failed, we continue anyway ;-( */
372 }
373#endif
374 }
375 initialized = 1;
376}
377
378/****************************************************************************
379 *
380 * FragFromBlock()
381 *
382 * This should return a fragment from the block and mark it as used
383 * accordingly.
384 *
385 ***************************************************************************/
386
387static void *FragFromBlock(struct MemBlock *block)
388{
389 /* make frag point to the first free FRAGMENT */
390 struct MemFrag *frag = block->first;
391 struct MemInfo *mem = (struct MemInfo *)frag;
392
393 /*
394 * Remove the FRAGMENT from the list and decrease the free counters.
395 */
396 block->first = frag->next; /* new first free FRAGMENT */
397
398 block->nfree--; /* BLOCK counter */
399 block->top->nfree--; /* TOP counter */
400
401 /* heal the FRAGMENT list */
402 if(frag->prev) {
403 frag->prev->next = frag->next;
404 }
405 if(frag->next) {
406 frag->next->prev = frag->prev;
407 }
408 mem->block = block; /* no block bit set here */
409
410 return ((char *)mem)+sizeof(struct MemInfo);
411}
412
413/***************************************************************************
414 *
415 * dmalloc()
416 *
417 * This needs no explanation. A malloc() look-alike.
418 *
419 **************************************************************************/
420
421void *dmalloc(size_t size)
422{
423 void *mem;
424
425 DBG(("dmalloc(%d)\n", size));
426
427 if(!initialized)
428 initialize();
429
430 /* First, we make room for the space needed in every allocation */
431 size += sizeof(struct MemInfo);
432
433 if(size < DMEM_LARGESTSIZE) {
434 /* get a FRAGMENT */
435
436 struct MemBlock *block=NULL; /* SAFE */
437 struct MemBlock *newblock=NULL; /* SAFE */
438 struct MemTop *memtop=NULL; /* SAFE */
439
440 /* Determine which queue to use */
441#ifdef ROCKBOX
442 unsigned
443#endif /* ROCKBOX */
444 int queue;
445
446 for(queue=0; size > qinfo[queue]; queue++)
447 ;
448 do {
449 /* This is the head master of our chain: */
450 memtop = &top[queue];
451
452 DBG(("Top info: %p %d %d %d\n",
453 memtop->chain,
454 memtop->nfree,
455 memtop->nmax,
456 memtop->fragsize));
457
458#ifdef SEMAPHORE
459 if(SEMAPHOREOBTAIN(memtop->semaphore_id))
460 return NULL; /* failed somehow */
461#endif
462
463 /* get the first BLOCK in the chain */
464 block = memtop->chain;
465
466 /* check if we have a free FRAGMENT */
467 if(memtop->nfree) {
468 /* there exists a free FRAGMENT in this chain */
469
470 /* I WANT THIS LOOP OUT OF HERE! */
471
472 /* search for the free FRAGMENT */
473 while(!block->nfree)
474 block = block->next; /* check next BLOCK */
475
476 /*
477 * Now 'block' is the first BLOCK with a free FRAGMENT
478 */
479
480 mem = FragFromBlock(block);
481
482 }
483 else {
484 /* we do *not* have a free FRAGMENT but need to get us a new BLOCK */
485
486 DMEM_OSALLOCMEM(DMEM_BLOCKSIZE + sizeof(struct MemBlock),
487 newblock,
488 struct MemBlock *);
489 if(!newblock) {
490 if(++queue < sizeof(qinfo)/sizeof(qinfo[0])) {
491 /* There are queues for bigger FRAGMENTS that we should check
492 before we fail this for real */
493#ifdef DEBUG
494 printf("*** " __FILE__ " Trying a bigger Q: %d\n", queue);
495#endif
496 mem = NULL;
497 }
498 else {
499 dmalloc_failed(size- sizeof(struct MemInfo));
500 return NULL; /* not enough memory */
501 }
502 }
503 else {
504 /* allocation of big BLOCK was successful */
505
506 MEMINCR(newblock, DMEM_BLOCKSIZE + sizeof(struct MemBlock));
507
508 memtop->chain = newblock; /* attach this BLOCK to the chain */
509 newblock->next = block; /* point to the previous first BLOCK */
510 if(block)
511 block->prev = newblock; /* point back on this new BLOCK */
512 newblock->prev = NULL; /* no previous */
513 newblock->top = memtop; /* our head master */
514
515 /* point to the new first FRAGMENT */
516 newblock->first = (struct MemFrag *)
517 ((char *)newblock+sizeof(struct MemBlock));
518
519 /* create FRAGMENTS of the BLOCK: */
520 FragBlock((char *)newblock->first, memtop->fragsize);
521
522#if defined(DEBUG) && !defined(BMALLOC)
523 checkmem((char *)newblock);
524#endif
525
526 /* fix the nfree counters */
527 newblock->nfree = memtop->nmax;
528 memtop->nfree += memtop->nmax;
529
530 /* get a FRAGMENT from the BLOCK */
531 mem = FragFromBlock(newblock);
532 }
533 }
534#ifdef SEMAPHORE
535 SEMAPHORERETURN(memtop->semaphore_id); /* let it go */
536#endif
537 } while(NULL == mem); /* if we should retry a larger FRAGMENT */
538 }
539 else {
540 /* get a stand-alone BLOCK */
541 struct MemInfo *meminfo;
542
543 if(size&1)
544 /* don't leave this with an odd size since we'll use that bit for
545 information */
546 size++;
547
548 DMEM_OSALLOCMEM(size, meminfo, struct MemInfo *);
549
550 if(meminfo) {
551 MEMINCR(meminfo, size);
552 meminfo->block = (void *)(size|BLOCK_BIT);
553 mem = (char *)meminfo + sizeof(struct MemInfo);
554 }
555 else {
556 dmalloc_failed(size);
557 mem = NULL;
558 }
559 }
560 return (void *)mem;
561}
562
563/***************************************************************************
564 *
565 * dfree()
566 *
567 * This needs no explanation. A free() look-alike.
568 *
569 **************************************************************************/
570
571void dfree(void *memp)
572{
573 struct MemInfo *meminfo = (struct MemInfo *)
574 ((char *)memp- sizeof(struct MemInfo));
575
576 DBG(("dfree(%p)\n", memp));
577
578 if(!((size_t)meminfo->block&BLOCK_BIT)) {
579 /* this is a FRAGMENT we have to deal with */
580
581 struct MemBlock *block=meminfo->block;
582 struct MemTop *memtop = block->top;
583
584#ifdef SEMAPHORE
585 SEMAPHOREOBTAIN(memtop->semaphore_id);
586#endif
587
588 /* increase counters */
589 block->nfree++;
590 memtop->nfree++;
591
592 /* is this BLOCK completely empty now? */
593 if(block->nfree == memtop->nmax) {
594 /* yes, return the BLOCK to the system */
595 if(block->prev)
596 block->prev->next = block->next;
597 else
598 memtop->chain = block->next;
599 if(block->next)
600 block->next->prev = block->prev;
601
602 memtop->nfree -= memtop->nmax; /* total counter subtraction */
603 MEMDECR(block, DMEM_BLOCKSIZE + sizeof(struct MemBlock));
604 DMEM_OSFREEMEM((void *)block); /* return the whole block */
605 }
606 else {
607 /* there are still used FRAGMENTS in the BLOCK, link this one
608 into the chain of free ones */
609 struct MemFrag *frag = (struct MemFrag *)meminfo;
610 frag->prev = NULL;
611 frag->next = block->first;
612 if(block->first)
613 block->first->prev = frag;
614 block->first = frag;
615 }
616#ifdef SEMAPHORE
617 SEMAPHORERETURN(memtop->semaphore_id);
618#endif
619 }
620 else {
621 /* big stand-alone block, just give it back to the OS: */
622 MEMDECR(&meminfo->block, (size_t)meminfo->block&~BLOCK_BIT); /* clean BLOCK_BIT */
623 DMEM_OSFREEMEM((void *)meminfo);
624 }
625}
626
627/***************************************************************************
628 *
629 * drealloc()
630 *
631 * This needs no explanation. A realloc() look-alike.
632 *
633 **************************************************************************/
634
635void *drealloc(char *ptr, size_t size)
636{
637 struct MemInfo *meminfo = (struct MemInfo *)
638 ((char *)ptr- sizeof(struct MemInfo));
639 /*
640 * ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
641 * NOTE: the ->size field of the meminfo will now contain the MemInfo
642 * struct size too!
643 * ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
644 */
645 void *mem=NULL; /* SAFE */
646 size_t prevsize = 0;
647
648 /* NOTE that this is only valid if BLOCK_BIT isn't set: */
649 struct MemBlock *block;
650
651 DBG(("drealloc(%p, %d)\n", ptr, size));
652
653 if(NULL == ptr)
654 return dmalloc( size );
655
656 block = meminfo->block;
657
658 if(!((size_t)meminfo->block&BLOCK_BIT) &&
659 (size + sizeof(struct MemInfo) <
660 (prevsize = block->top->fragsize) )) {
661 /* This is a FRAGMENT and new size is possible to retain within the same
662 FRAGMENT */
663 if((prevsize > qinfo[0]) &&
664 /* this is not the smallest memory Q */
665 (size < (block->top-1)->fragsize))
666 /* this fits in a smaller Q */
667 ;
668 else
669 mem = ptr; /* Just return the same pointer as we got in. */
670 }
671 if(!mem) {
672 /* This is a stand-alone BLOCK or a realloc that no longer fits within
673 the same FRAGMENT */
674
675 if((size_t)meminfo->block&BLOCK_BIT) {
676 prevsize = ((size_t)meminfo->block&~BLOCK_BIT) -
677 sizeof(struct MemInfo);
678 }
679 else
680 prevsize -= sizeof(struct MemInfo);
681
682 /* No tricks involved here, just grab a new bite of memory, copy the data
683 * from the old place and free the old memory again. */
684 mem = dmalloc(size);
685 if(mem) {
686 memcpy(mem, ptr, MIN(size, prevsize) );
687 dfree(ptr);
688 }
689 }
690 return mem;
691}
692
693/***************************************************************************
694 *
695 * dcalloc()
696 *
697 * This needs no explanation. A calloc() look-alike.
698 *
699 **************************************************************************/
700/* Allocate an array of NMEMB elements each SIZE bytes long.
701 The entire array is initialized to zeros. */
702void *
703dcalloc (size_t nmemb, size_t size)
704{
705 void *result = dmalloc (nmemb * size);
706
707 if (result != NULL)
708 memset (result, 0, nmemb * size);
709
710 return result;
711}
generated by cgit v1.2.3 (git 2.39.1) at 2024-09-25 11:19:47 +0000