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.c1380
1 files changed, 1380 insertions, 0 deletions
diff --git a/apps/plugins/pdbox/dbestfit-3.3/dmalloc.c b/apps/plugins/pdbox/dbestfit-3.3/dmalloc.c
new file mode 100644
index 0000000000..9336276883
--- /dev/null
+++ b/apps/plugins/pdbox/dbestfit-3.3/dmalloc.c
@@ -0,0 +1,1380 @@
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#include <stdio.h>
27#include <string.h>
28
29#ifdef DEBUG
30#include <stdarg.h>
31#endif
32
33#ifdef PSOS
34#include <psos.h>
35#define SEMAPHORE /* the PSOS routines use semaphore protection */
36#else
37#include <stdlib.h> /* makes the PSOS complain on the 'size_t' typedef */
38#endif
39
40#ifdef BMALLOC
41#include "bmalloc.h"
42#endif
43
44/* Each TOP takes care of a chain of BLOCKS */
45struct MemTop {
46 struct MemBlock *chain; /* pointer to the BLOCK chain */
47 long nfree; /* total number of free FRAGMENTS in the chain */
48 short nmax; /* total number of FRAGMENTS in this kind of BLOCK */
49 size_t fragsize; /* the size of each FRAGMENT */
50
51#ifdef SEMAPHORE /* if we're protecting the list with SEMAPHORES */
52 long semaphore_id; /* semaphore used to lock this particular list */
53#endif
54
55};
56
57/* Each BLOCK takes care of an amount of FRAGMENTS */
58struct MemBlock {
59 struct MemTop *top; /* our TOP struct */
60 struct MemBlock *next; /* next BLOCK */
61 struct MemBlock *prev; /* prev BLOCK */
62
63 struct MemFrag *first; /* the first free FRAGMENT in this block */
64
65 short nfree; /* number of free FRAGMENTS in this BLOCK */
66};
67
68/* This is the data kept in all _free_ FRAGMENTS */
69struct MemFrag {
70 struct MemFrag *next; /* next free FRAGMENT */
71 struct MemFrag *prev; /* prev free FRAGMENT */
72};
73
74/* This is the data kept in all _allocated_ FRAGMENTS and BLOCKS. We add this
75 to the allocation size first thing in the ALLOC function to make room for
76 this smoothly. */
77
78struct MemInfo {
79 void *block;
80 /* which BLOCK is our father, if BLOCK_BIT is set it means this is a
81 stand-alone, large allocation and then the rest of the bits should be
82 treated as the size of the block */
83#define BLOCK_BIT 1
84};
85
86/* ---------------------------------------------------------------------- */
87/* Defines */
88/* ---------------------------------------------------------------------- */
89
90#ifdef DEBUG
91#define MEMINCR(addr,x) memchange(addr, x)
92#define MEMDECR(addr,x) memchange(addr,-(x))
93#else
94#define MEMINCR(a,x)
95#define MEMDECR(a,x)
96#endif
97
98/* The low level functions used to get memory from the OS and to return memory
99 to the OS, we may also define a stub that does the actual allocation and
100 free, these are the defined function names used in the dmalloc system
101 anyway: */
102#ifdef PSOS
103
104#ifdef DEBUG
105#define DMEM_OSALLOCMEM(size,pointer,type) pointer=(type)dbgmalloc(size)
106#define DMEM_OSFREEMEM(x) dbgfree(x)
107#else
108#define DMEM_OSALLOCMEM(size,pointer,type) rn_getseg(0,size,RN_NOWAIT,0,(void **)&pointer)
109/* Similar, but this returns the memory */
110#define DMEM_OSFREEMEM(x) rn_retseg(0, x)
111#endif
112
113/* Argument: <id> */
114#define SEMAPHOREOBTAIN(x) sm_p(x, SM_WAIT, 0)
115/* Argument: <id> */
116#define SEMAPHORERETURN(x) sm_v(x)
117/* Argument: <name> <id-variable name> */
118#define SEMAPHORECREATE(x,y) sm_create(x, 1, SM_FIFO, (ULONG *)&(y))
119
120#else
121#ifdef BMALLOC /* use our own big-memory-allocation system */
122#define DMEM_OSALLOCMEM(size,pointer,type) pointer=(type)bmalloc(size)
123#define DMEM_OSFREEMEM(x) bfree(x)
124#elif DEBUG
125#define DMEM_OSALLOCMEM(size,pointer,type) pointer=(type)dbgmalloc(size)
126#define DMEM_OSFREEMEM(x) dbgfree(x)
127#else
128#define DMEM_OSALLOCMEM(size,pointer,type) pointer=(type)malloc(size)
129#define DMEM_OSFREEMEM(x) free(x)
130#endif
131#endif
132
133
134/* the largest memory allocation that is made a FRAGMENT: (grab the highest
135 number from the list below) */
136#define DMEM_LARGESTSIZE 2032
137
138/* The total size of a BLOCK used for FRAGMENTS
139 In order to make this use only *1* even alignment from the big-block-
140 allocation-system (possible the bmalloc() system also written by me)
141 we need to subtract the [maximum] struct sizes that could get added all
142 the way through to the grab from the memory. */
143#define DMEM_BLOCKSIZE 4064 /* (4096 - sizeof(struct MemBlock) - 12) */
144
145/* Since the blocksize isn't an even 2^X story anymore, we make a table with
146 the FRAGMENT sizes and amounts that fills up a BLOCK nicely */
147
148/* a little 'bc' script that helps us maximize the usage:
149 - for 32-bit aligned addresses (SPARC crashes otherwise):
150 for(i=20; i<2040; i++) { a=4064/i; if(a*i >= 4060) { if(i%4==0) {i;} } }
151
152
153 I try to approximate a double of each size, starting with ~20. We don't do
154 ODD sizes since several CPU flavours dump core when accessing such
155 addresses. We try to do 32-bit aligned to make ALL kinds of CPUs to remain
156 happy with us.
157 */
158
159#if BIGBLOCKS==4060 /* previously */
160short qinfo[]= { 20, 28, 52, 116, 312, 580, 812, 2028 };
161#else
162short qinfo[]= { 20, 28, 52, 116, 312, 580, 1016, 2032};
163/* 52 and 312 only make use of 4056 bytes, but without them there are too
164 wide gaps */
165#endif
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/* are we experienced? */
177static char initialized = 0;
178
179/* ---------------------------------------------------------------------- */
180/* Start of the real code */
181/* ---------------------------------------------------------------------- */
182
183#ifdef DEBUG
184/************
185 * A few functions that are verbose and tells us about the current status
186 * of the dmalloc system
187 ***********/
188
189static void dmalloc_status()
190{
191 int i;
192 int used;
193 int num;
194 int totalfree=0;
195 struct MemBlock *block;
196 for(i=0; i<sizeof(qinfo)/sizeof(qinfo[0]);i++) {
197 block = top[i].chain;
198 used = 0;
199 num = 0;
200 while(block) {
201 used += top[i].nmax-block->nfree;
202 num++;
203 block = block->next;
204 }
205 printf("Q %d (FRAG %4d), USED %4d FREE %4ld (SIZE %4ld) BLOCKS %d\n",
206 i, top[i].fragsize, used, top[i].nfree,
207 top[i].nfree*top[i].fragsize, num);
208 totalfree += top[i].nfree*top[i].fragsize;
209 }
210 printf("Total unused memory stolen by dmalloc: %d\n", totalfree);
211}
212
213static void dmalloc_failed(size_t size)
214{
215 printf("*** " __FILE__ " Couldn't allocate %d bytes\n", size);
216 dmalloc_status();
217}
218#else
219#define dmalloc_failed(x)
220#endif
221
222#ifdef DEBUG
223
224#define BORDER 1200
225
226void *dbgmalloc(int size)
227{
228 char *mem;
229 size += BORDER;
230#ifdef PSOS
231 rn_getseg(0,size,RN_NOWAIT,0,(void **)&mem);
232#else
233 mem = malloc(size);
234#endif
235 if(mem) {
236 memset(mem, 0xaa, BORDER/2);
237 memset(mem+BORDER/2, 0xbb, size -BORDER);
238 memset(mem-BORDER/2+size, 0xcc, BORDER/2);
239 *(long *)mem = size;
240 mem += (BORDER/2);
241 }
242 printf("OSmalloc(%p)\n", mem);
243 return (void *)mem;
244}
245
246void checkmem(char *ptr)
247{
248 int i;
249 long size;
250 ptr -= BORDER/2;
251
252 for(i=4; i<(BORDER/2); i++)
253 if((unsigned char)ptr[i] != 0xaa) {
254 printf("########### ALERT ALERT\n");
255 break;
256 }
257 size = *(long *)ptr;
258 for(i=size-1; i>=(size - BORDER/2); i--)
259 if((unsigned char)ptr[i] != 0xcc) {
260 printf("********* POST ALERT\n");
261 break;
262 }
263}
264
265void dbgfree(char *ptr)
266{
267 long size;
268 checkmem(ptr);
269 ptr -= BORDER/2;
270 size = *(long *)ptr;
271
272 printf("OSfree(%ld)\n", size);
273#ifdef PSOS
274 rn_retseg(0, ptr);
275#else
276 free(ptr);
277#endif
278}
279
280
281#define DBG(x) syslog x
282
283void syslog(char *fmt, ...)
284{
285 va_list ap;
286 va_start(ap, fmt);
287 vfprintf(stdout, fmt, ap);
288 va_end(ap);
289}
290
291void memchange(void *a, int x)
292{
293 static int memory=0;
294 static int count=0;
295 static int max=0;
296 if(memory > max)
297 max = memory;
298 memory += x;
299 DBG(("%d. PTR %p / %d TOTAL %d MAX %d\n", ++count, a, x, memory, max));
300}
301#else
302#define DBG(x)
303#endif
304
305/****************************************************************************
306 *
307 * FragBlock()
308 *
309 * This function makes FRAGMENTS of the BLOCK sent as argument.
310 *
311 ***************************************************************************/
312
313static void FragBlock(char *memp, int size)
314{
315 struct MemFrag *frag=(struct MemFrag *)memp;
316 struct MemFrag *prev=NULL; /* no previous in the first round */
317 int count=0;
318 while((count+size) <= DMEM_BLOCKSIZE) {
319 memp += size;
320 frag->next = (struct MemFrag *)memp;
321 frag->prev = prev;
322 prev = frag;
323 frag = frag->next;
324 count += size;
325 }
326 prev->next = NULL; /* the last one has no next struct */
327}
328
329/***************************************************************************
330 *
331 * initialize();
332 *
333 * Called in the first dmalloc(). Inits a few memory things.
334 *
335 **************************************************************************/
336static void initialize(void)
337{
338 int i;
339 /* Setup the nmax and fragsize fields of the top structs */
340 for(i=0; i< sizeof(qinfo)/sizeof(qinfo[0]); i++) {
341 top[i].fragsize = qinfo[i];
342 top[i].nmax = DMEM_BLOCKSIZE/qinfo[i];
343
344#ifdef PSOS
345 /* for some reason, these aren't nulled from start: */
346 top[i].chain = NULL; /* no BLOCKS */
347 top[i].nfree = 0; /* no FRAGMENTS */
348#endif
349#ifdef SEMAPHORE
350 {
351 char name[7];
352 sprintf(name, "MEM%d", i);
353 SEMAPHORECREATE(name, top[i].semaphore_id);
354 /* doesn't matter if it failed, we continue anyway ;-( */
355 }
356#endif
357 }
358 initialized = 1;
359}
360
361/****************************************************************************
362 *
363 * FragFromBlock()
364 *
365 * This should return a fragment from the block and mark it as used
366 * accordingly.
367 *
368 ***************************************************************************/
369
370static void *FragFromBlock(struct MemBlock *block)
371{
372 /* make frag point to the first free FRAGMENT */
373 struct MemFrag *frag = block->first;
374 struct MemInfo *mem = (struct MemInfo *)frag;
375
376 /*
377 * Remove the FRAGMENT from the list and decrease the free counters.
378 */
379 block->first = frag->next; /* new first free FRAGMENT */
380
381 block->nfree--; /* BLOCK counter */
382 block->top->nfree--; /* TOP counter */
383
384 /* heal the FRAGMENT list */
385 if(frag->prev) {
386 frag->prev->next = frag->next;
387 }
388 if(frag->next) {
389 frag->next->prev = frag->prev;
390 }
391 mem->block = block; /* no block bit set here */
392
393 return ((char *)mem)+sizeof(struct MemInfo);
394}
395
396/***************************************************************************
397 *
398 * dmalloc()
399 *
400 * This needs no explanation. A malloc() look-alike.
401 *
402 **************************************************************************/
403
404void *dmalloc(size_t size)
405{
406 void *mem;
407
408 DBG(("dmalloc(%d)\n", size));
409
410 if(!initialized)
411 initialize();
412
413 /* First, we make room for the space needed in every allocation */
414 size += sizeof(struct MemInfo);
415
416 if(size < DMEM_LARGESTSIZE) {
417 /* get a FRAGMENT */
418
419 struct MemBlock *block=NULL; /* SAFE */
420 struct MemBlock *newblock=NULL; /* SAFE */
421 struct MemTop *memtop=NULL; /* SAFE */
422
423 /* Determine which queue to use */
424 int queue;
425 for(queue=0; size > qinfo[queue]; queue++)
426 ;
427 do {
428 /* This is the head master of our chain: */
429 memtop = &top[queue];
430
431 DBG(("Top info: %p %d %d %d\n",
432 memtop->chain,
433 memtop->nfree,
434 memtop->nmax,
435 memtop->fragsize));
436
437#ifdef SEMAPHORE
438 if(SEMAPHOREOBTAIN(memtop->semaphore_id))
439 return NULL; /* failed somehow */
440#endif
441
442 /* get the first BLOCK in the chain */
443 block = memtop->chain;
444
445 /* check if we have a free FRAGMENT */
446 if(memtop->nfree) {
447 /* there exists a free FRAGMENT in this chain */
448
449 /* I WANT THIS LOOP OUT OF HERE! */
450
451 /* search for the free FRAGMENT */
452 while(!block->nfree)
453 block = block->next; /* check next BLOCK */
454
455 /*
456 * Now 'block' is the first BLOCK with a free FRAGMENT
457 */
458
459 mem = FragFromBlock(block);
460
461 }
462 else {
463 /* we do *not* have a free FRAGMENT but need to get us a new BLOCK */
464
465 DMEM_OSALLOCMEM(DMEM_BLOCKSIZE + sizeof(struct MemBlock),
466 newblock,
467 struct MemBlock *);
468 if(!newblock) {
469 if(++queue < sizeof(qinfo)/sizeof(qinfo[0])) {
470 /* There are queues for bigger FRAGMENTS that we should check
471 before we fail this for real */
472#ifdef DEBUG
473 printf("*** " __FILE__ " Trying a bigger Q: %d\n", queue);
474#endif
475 mem = NULL;
476 }
477 else {
478 dmalloc_failed(size- sizeof(struct MemInfo));
479 return NULL; /* not enough memory */
480 }
481 }
482 else {
483 /* allocation of big BLOCK was successful */
484
485 MEMINCR(newblock, DMEM_BLOCKSIZE + sizeof(struct MemBlock));
486
487 memtop->chain = newblock; /* attach this BLOCK to the chain */
488 newblock->next = block; /* point to the previous first BLOCK */
489 if(block)
490 block->prev = newblock; /* point back on this new BLOCK */
491 newblock->prev = NULL; /* no previous */
492 newblock->top = memtop; /* our head master */
493
494 /* point to the new first FRAGMENT */
495 newblock->first = (struct MemFrag *)
496 ((char *)newblock+sizeof(struct MemBlock));
497
498 /* create FRAGMENTS of the BLOCK: */
499 FragBlock((char *)newblock->first, memtop->fragsize);
500
501#if defined(DEBUG) && !defined(BMALLOC)
502 checkmem((char *)newblock);
503#endif
504
505 /* fix the nfree counters */
506 newblock->nfree = memtop->nmax;
507 memtop->nfree += memtop->nmax;
508
509 /* get a FRAGMENT from the BLOCK */
510 mem = FragFromBlock(newblock);
511 }
512 }
513#ifdef SEMAPHORE
514 SEMAPHORERETURN(memtop->semaphore_id); /* let it go */
515#endif
516 } while(NULL == mem); /* if we should retry a larger FRAGMENT */
517 }
518 else {
519 /* get a stand-alone BLOCK */
520 struct MemInfo *meminfo;
521
522 if(size&1)
523 /* don't leave this with an odd size since we'll use that bit for
524 information */
525 size++;
526
527 DMEM_OSALLOCMEM(size, meminfo, struct MemInfo *);
528
529 if(meminfo) {
530 MEMINCR(meminfo, size);
531 meminfo->block = (void *)(size|BLOCK_BIT);
532 mem = (char *)meminfo + sizeof(struct MemInfo);
533 }
534 else {
535 dmalloc_failed(size);
536 mem = NULL;
537 }
538 }
539 return (void *)mem;
540}
541
542/***************************************************************************
543 *
544 * dfree()
545 *
546 * This needs no explanation. A free() look-alike.
547 *
548 **************************************************************************/
549
550void dfree(void *memp)
551{
552 struct MemInfo *meminfo = (struct MemInfo *)
553 ((char *)memp- sizeof(struct MemInfo));
554
555 DBG(("dfree(%p)\n", memp));
556
557 if(!((size_t)meminfo->block&BLOCK_BIT)) {
558 /* this is a FRAGMENT we have to deal with */
559
560 struct MemBlock *block=meminfo->block;
561 struct MemTop *memtop = block->top;
562
563#ifdef SEMAPHORE
564 SEMAPHOREOBTAIN(memtop->semaphore_id);
565#endif
566
567 /* increase counters */
568 block->nfree++;
569 memtop->nfree++;
570
571 /* is this BLOCK completely empty now? */
572 if(block->nfree == memtop->nmax) {
573 /* yes, return the BLOCK to the system */
574 if(block->prev)
575 block->prev->next = block->next;
576 else
577 memtop->chain = block->next;
578 if(block->next)
579 block->next->prev = block->prev;
580
581 memtop->nfree -= memtop->nmax; /* total counter subtraction */
582 MEMDECR(block, DMEM_BLOCKSIZE + sizeof(struct MemBlock));
583 DMEM_OSFREEMEM((void *)block); /* return the whole block */
584 }
585 else {
586 /* there are still used FRAGMENTS in the BLOCK, link this one
587 into the chain of free ones */
588 struct MemFrag *frag = (struct MemFrag *)meminfo;
589 frag->prev = NULL;
590 frag->next = block->first;
591 if(block->first)
592 block->first->prev = frag;
593 block->first = frag;
594 }
595#ifdef SEMAPHORE
596 SEMAPHORERETURN(memtop->semaphore_id);
597#endif
598 }
599 else {
600 /* big stand-alone block, just give it back to the OS: */
601 MEMDECR(&meminfo->block, (size_t)meminfo->block&~BLOCK_BIT); /* clean BLOCK_BIT */
602 DMEM_OSFREEMEM((void *)meminfo);
603 }
604}
605
606/***************************************************************************
607 *
608 * drealloc()
609 *
610 * This needs no explanation. A realloc() look-alike.
611 *
612 **************************************************************************/
613
614void *drealloc(char *ptr, size_t size)
615{
616 struct MemInfo *meminfo = (struct MemInfo *)
617 ((char *)ptr- sizeof(struct MemInfo));
618 /*
619 * ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
620 * NOTE: the ->size field of the meminfo will now contain the MemInfo
621 * struct size too!
622 * ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
623 */
624 void *mem=NULL; /* SAFE */
625 size_t prevsize;
626
627 /* NOTE that this is only valid if BLOCK_BIT isn't set: */
628 struct MemBlock *block;
629
630 DBG(("drealloc(%p, %d)\n", ptr, size));
631
632 if(NULL == ptr)
633 return dmalloc( size );
634
635 block = meminfo->block;
636
637 if(!((size_t)meminfo->block&BLOCK_BIT) &&
638 (size + sizeof(struct MemInfo) <
639 (prevsize = block->top->fragsize) )) {
640 /* This is a FRAGMENT and new size is possible to retain within the same
641 FRAGMENT */
642 if((prevsize > qinfo[0]) &&
643 /* this is not the smallest memory Q */
644 (size < (block->top-1)->fragsize))
645 /* this fits in a smaller Q */
646 ;
647 else
648 mem = ptr; /* Just return the same pointer as we got in. */
649 }
650 if(!mem) {
651 /* This is a stand-alone BLOCK or a realloc that no longer fits within
652 the same FRAGMENT */
653
654 if((size_t)meminfo->block&BLOCK_BIT) {
655 prevsize = ((size_t)meminfo->block&~BLOCK_BIT) -
656 sizeof(struct MemInfo);
657 }
658 else
659 prevsize -= sizeof(struct MemInfo);
660
661 /* No tricks involved here, just grab a new bite of memory, copy the data
662 * from the old place and free the old memory again. */
663 mem = dmalloc(size);
664 if(mem) {
665 memcpy(mem, ptr, MIN(size, prevsize) );
666 dfree(ptr);
667 }
668 }
669 return mem;
670}
671
672/***************************************************************************
673 *
674 * dcalloc()
675 *
676 * This needs no explanation. A calloc() look-alike.
677 *
678 **************************************************************************/
679/* Allocate an array of NMEMB elements each SIZE bytes long.
680 The entire array is initialized to zeros. */
681void *
682dcalloc (size_t nmemb, size_t size)
683{
684 void *result = dmalloc (nmemb * size);
685
686 if (result != NULL)
687 memset (result, 0, nmemb * size);
688
689 return result;
690}
691/*****************************************************************************
692 *
693 * Dynamic Memory Allocation
694 *
695 * Author: Daniel Stenberg
696 * Date: March 10, 1997
697 * Version: 2.3
698 * Email: Daniel.Stenberg@sth.frontec.se
699 *
700 *
701 * Read 'thoughts' for theories and details of this implementation.
702 *
703 * v2.1
704 * - I once again managed to gain some memory. BLOCK allocations now only use
705 * a 4 bytes header (instead of previos 8) just as FRAGMENTS.
706 *
707 * v2.2
708 * - Re-adjusted the fragment sizes to better fit into the somewhat larger
709 * block.
710 *
711 * v2.3
712 * - Made realloc(NULL, size) work as it should. Which is like a malloc(size)
713 *
714 *****************************************************************************/
715
716#include <stdio.h>
717#include <string.h>
718
719#ifdef DEBUG
720#include <stdarg.h>
721#endif
722
723#ifdef PSOS
724#include <psos.h>
725#define SEMAPHORE /* the PSOS routines use semaphore protection */
726#else
727#include <stdlib.h> /* makes the PSOS complain on the 'size_t' typedef */
728#endif
729
730#ifdef BMALLOC
731#include "bmalloc.h"
732#endif
733
734/* Each TOP takes care of a chain of BLOCKS */
735struct MemTop {
736 struct MemBlock *chain; /* pointer to the BLOCK chain */
737 long nfree; /* total number of free FRAGMENTS in the chain */
738 short nmax; /* total number of FRAGMENTS in this kind of BLOCK */
739 size_t fragsize; /* the size of each FRAGMENT */
740
741#ifdef SEMAPHORE /* if we're protecting the list with SEMAPHORES */
742 long semaphore_id; /* semaphore used to lock this particular list */
743#endif
744
745};
746
747/* Each BLOCK takes care of an amount of FRAGMENTS */
748struct MemBlock {
749 struct MemTop *top; /* our TOP struct */
750 struct MemBlock *next; /* next BLOCK */
751 struct MemBlock *prev; /* prev BLOCK */
752
753 struct MemFrag *first; /* the first free FRAGMENT in this block */
754
755 short nfree; /* number of free FRAGMENTS in this BLOCK */
756};
757
758/* This is the data kept in all _free_ FRAGMENTS */
759struct MemFrag {
760 struct MemFrag *next; /* next free FRAGMENT */
761 struct MemFrag *prev; /* prev free FRAGMENT */
762};
763
764/* This is the data kept in all _allocated_ FRAGMENTS and BLOCKS. We add this
765 to the allocation size first thing in the ALLOC function to make room for
766 this smoothly. */
767
768struct MemInfo {
769 void *block;
770 /* which BLOCK is our father, if BLOCK_BIT is set it means this is a
771 stand-alone, large allocation and then the rest of the bits should be
772 treated as the size of the block */
773#define BLOCK_BIT 1
774};
775
776/* ---------------------------------------------------------------------- */
777/* Defines */
778/* ---------------------------------------------------------------------- */
779
780#ifdef DEBUG
781#define MEMINCR(addr,x) memchange(addr, x)
782#define MEMDECR(addr,x) memchange(addr,-(x))
783#else
784#define MEMINCR(a,x)
785#define MEMDECR(a,x)
786#endif
787
788/* The low level functions used to get memory from the OS and to return memory
789 to the OS, we may also define a stub that does the actual allocation and
790 free, these are the defined function names used in the dmalloc system
791 anyway: */
792#ifdef PSOS
793
794#ifdef DEBUG
795#define DMEM_OSALLOCMEM(size,pointer,type) pointer=(type)dbgmalloc(size)
796#define DMEM_OSFREEMEM(x) dbgfree(x)
797#else
798#define DMEM_OSALLOCMEM(size,pointer,type) rn_getseg(0,size,RN_NOWAIT,0,(void **)&pointer)
799/* Similar, but this returns the memory */
800#define DMEM_OSFREEMEM(x) rn_retseg(0, x)
801#endif
802
803/* Argument: <id> */
804#define SEMAPHOREOBTAIN(x) sm_p(x, SM_WAIT, 0)
805/* Argument: <id> */
806#define SEMAPHORERETURN(x) sm_v(x)
807/* Argument: <name> <id-variable name> */
808#define SEMAPHORECREATE(x,y) sm_create(x, 1, SM_FIFO, (ULONG *)&(y))
809
810#else
811#ifdef BMALLOC /* use our own big-memory-allocation system */
812#define DMEM_OSALLOCMEM(size,pointer,type) pointer=(type)bmalloc(size)
813#define DMEM_OSFREEMEM(x) bfree(x)
814#elif DEBUG
815#define DMEM_OSALLOCMEM(size,pointer,type) pointer=(type)dbgmalloc(size)
816#define DMEM_OSFREEMEM(x) dbgfree(x)
817#else
818#define DMEM_OSALLOCMEM(size,pointer,type) pointer=(type)malloc(size)
819#define DMEM_OSFREEMEM(x) free(x)
820#endif
821#endif
822
823
824/* the largest memory allocation that is made a FRAGMENT: (grab the highest
825 number from the list below) */
826#define DMEM_LARGESTSIZE 2032
827
828/* The total size of a BLOCK used for FRAGMENTS
829 In order to make this use only *1* even alignment from the big-block-
830 allocation-system (possible the bmalloc() system also written by me)
831 we need to subtract the [maximum] struct sizes that could get added all
832 the way through to the grab from the memory. */
833#define DMEM_BLOCKSIZE 4064 /* (4096 - sizeof(struct MemBlock) - 12) */
834
835/* Since the blocksize isn't an even 2^X story anymore, we make a table with
836 the FRAGMENT sizes and amounts that fills up a BLOCK nicely */
837
838/* a little 'bc' script that helps us maximize the usage:
839 - for 32-bit aligned addresses (SPARC crashes otherwise):
840 for(i=20; i<2040; i++) { a=4064/i; if(a*i >= 4060) { if(i%4==0) {i;} } }
841
842
843 I try to approximate a double of each size, starting with ~20. We don't do
844 ODD sizes since several CPU flavours dump core when accessing such
845 addresses. We try to do 32-bit aligned to make ALL kinds of CPUs to remain
846 happy with us.
847 */
848
849#if BIGBLOCKS==4060 /* previously */
850short qinfo[]= { 20, 28, 52, 116, 312, 580, 812, 2028 };
851#else
852short qinfo[]= { 20, 28, 52, 116, 312, 580, 1016, 2032};
853/* 52 and 312 only make use of 4056 bytes, but without them there are too
854 wide gaps */
855#endif
856
857#define MIN(x,y) ((x)<(y)?(x):(y))
858
859/* ---------------------------------------------------------------------- */
860/* Globals */
861/* ---------------------------------------------------------------------- */
862
863/* keeper of the chain of BLOCKS */
864static struct MemTop top[ sizeof(qinfo)/sizeof(qinfo[0]) ];
865
866/* are we experienced? */
867static char initialized = 0;
868
869/* ---------------------------------------------------------------------- */
870/* Start of the real code */
871/* ---------------------------------------------------------------------- */
872
873#ifdef DEBUG
874/************
875 * A few functions that are verbose and tells us about the current status
876 * of the dmalloc system
877 ***********/
878
879static void dmalloc_status()
880{
881 int i;
882 int used;
883 int num;
884 int totalfree=0;
885 struct MemBlock *block;
886 for(i=0; i<sizeof(qinfo)/sizeof(qinfo[0]);i++) {
887 block = top[i].chain;
888 used = 0;
889 num = 0;
890 while(block) {
891 used += top[i].nmax-block->nfree;
892 num++;
893 block = block->next;
894 }
895 printf("Q %d (FRAG %4d), USED %4d FREE %4ld (SIZE %4ld) BLOCKS %d\n",
896 i, top[i].fragsize, used, top[i].nfree,
897 top[i].nfree*top[i].fragsize, num);
898 totalfree += top[i].nfree*top[i].fragsize;
899 }
900 printf("Total unused memory stolen by dmalloc: %d\n", totalfree);
901}
902
903static void dmalloc_failed(size_t size)
904{
905 printf("*** " __FILE__ " Couldn't allocate %d bytes\n", size);
906 dmalloc_status();
907}
908#else
909#define dmalloc_failed(x)
910#endif
911
912#ifdef DEBUG
913
914#define BORDER 1200
915
916void *dbgmalloc(int size)
917{
918 char *mem;
919 size += BORDER;
920#ifdef PSOS
921 rn_getseg(0,size,RN_NOWAIT,0,(void **)&mem);
922#else
923 mem = malloc(size);
924#endif
925 if(mem) {
926 memset(mem, 0xaa, BORDER/2);
927 memset(mem+BORDER/2, 0xbb, size -BORDER);
928 memset(mem-BORDER/2+size, 0xcc, BORDER/2);
929 *(long *)mem = size;
930 mem += (BORDER/2);
931 }
932 printf("OSmalloc(%p)\n", mem);
933 return (void *)mem;
934}
935
936void checkmem(char *ptr)
937{
938 int i;
939 long size;
940 ptr -= BORDER/2;
941
942 for(i=4; i<(BORDER/2); i++)
943 if((unsigned char)ptr[i] != 0xaa) {
944 printf("########### ALERT ALERT\n");
945 break;
946 }
947 size = *(long *)ptr;
948 for(i=size-1; i>=(size - BORDER/2); i--)
949 if((unsigned char)ptr[i] != 0xcc) {
950 printf("********* POST ALERT\n");
951 break;
952 }
953}
954
955void dbgfree(char *ptr)
956{
957 long size;
958 checkmem(ptr);
959 ptr -= BORDER/2;
960 size = *(long *)ptr;
961
962 printf("OSfree(%ld)\n", size);
963#ifdef PSOS
964 rn_retseg(0, ptr);
965#else
966 free(ptr);
967#endif
968}
969
970
971#define DBG(x) syslog x
972
973void syslog(char *fmt, ...)
974{
975 va_list ap;
976 va_start(ap, fmt);
977 vfprintf(stdout, fmt, ap);
978 va_end(ap);
979}
980
981void memchange(void *a, int x)
982{
983 static int memory=0;
984 static int count=0;
985 static int max=0;
986 if(memory > max)
987 max = memory;
988 memory += x;
989 DBG(("%d. PTR %p / %d TOTAL %d MAX %d\n", ++count, a, x, memory, max));
990}
991#else
992#define DBG(x)
993#endif
994
995/****************************************************************************
996 *
997 * FragBlock()
998 *
999 * This function makes FRAGMENTS of the BLOCK sent as argument.
1000 *
1001 ***************************************************************************/
1002
1003static void FragBlock(char *memp, int size)
1004{
1005 struct MemFrag *frag=(struct MemFrag *)memp;
1006 struct MemFrag *prev=NULL; /* no previous in the first round */
1007 int count=0;
1008 while((count+size) <= DMEM_BLOCKSIZE) {
1009 memp += size;
1010 frag->next = (struct MemFrag *)memp;
1011 frag->prev = prev;
1012 prev = frag;
1013 frag = frag->next;
1014 count += size;
1015 }
1016 prev->next = NULL; /* the last one has no next struct */
1017}
1018
1019/***************************************************************************
1020 *
1021 * initialize();
1022 *
1023 * Called in the first dmalloc(). Inits a few memory things.
1024 *
1025 **************************************************************************/
1026static void initialize(void)
1027{
1028 int i;
1029 /* Setup the nmax and fragsize fields of the top structs */
1030 for(i=0; i< sizeof(qinfo)/sizeof(qinfo[0]); i++) {
1031 top[i].fragsize = qinfo[i];
1032 top[i].nmax = DMEM_BLOCKSIZE/qinfo[i];
1033
1034#ifdef PSOS
1035 /* for some reason, these aren't nulled from start: */
1036 top[i].chain = NULL; /* no BLOCKS */
1037 top[i].nfree = 0; /* no FRAGMENTS */
1038#endif
1039#ifdef SEMAPHORE
1040 {
1041 char name[7];
1042 sprintf(name, "MEM%d", i);
1043 SEMAPHORECREATE(name, top[i].semaphore_id);
1044 /* doesn't matter if it failed, we continue anyway ;-( */
1045 }
1046#endif
1047 }
1048 initialized = 1;
1049}
1050
1051/****************************************************************************
1052 *
1053 * FragFromBlock()
1054 *
1055 * This should return a fragment from the block and mark it as used
1056 * accordingly.
1057 *
1058 ***************************************************************************/
1059
1060static void *FragFromBlock(struct MemBlock *block)
1061{
1062 /* make frag point to the first free FRAGMENT */
1063 struct MemFrag *frag = block->first;
1064 struct MemInfo *mem = (struct MemInfo *)frag;
1065
1066 /*
1067 * Remove the FRAGMENT from the list and decrease the free counters.
1068 */
1069 block->first = frag->next; /* new first free FRAGMENT */
1070
1071 block->nfree--; /* BLOCK counter */
1072 block->top->nfree--; /* TOP counter */
1073
1074 /* heal the FRAGMENT list */
1075 if(frag->prev) {
1076 frag->prev->next = frag->next;
1077 }
1078 if(frag->next) {
1079 frag->next->prev = frag->prev;
1080 }
1081 mem->block = block; /* no block bit set here */
1082
1083 return ((char *)mem)+sizeof(struct MemInfo);
1084}
1085
1086/***************************************************************************
1087 *
1088 * dmalloc()
1089 *
1090 * This needs no explanation. A malloc() look-alike.
1091 *
1092 **************************************************************************/
1093
1094void *dmalloc(size_t size)
1095{
1096 void *mem;
1097
1098 DBG(("dmalloc(%d)\n", size));
1099
1100 if(!initialized)
1101 initialize();
1102
1103 /* First, we make room for the space needed in every allocation */
1104 size += sizeof(struct MemInfo);
1105
1106 if(size < DMEM_LARGESTSIZE) {
1107 /* get a FRAGMENT */
1108
1109 struct MemBlock *block=NULL; /* SAFE */
1110 struct MemBlock *newblock=NULL; /* SAFE */
1111 struct MemTop *memtop=NULL; /* SAFE */
1112
1113 /* Determine which queue to use */
1114 int queue;
1115 for(queue=0; size > qinfo[queue]; queue++)
1116 ;
1117 do {
1118 /* This is the head master of our chain: */
1119 memtop = &top[queue];
1120
1121 DBG(("Top info: %p %d %d %d\n",
1122 memtop->chain,
1123 memtop->nfree,
1124 memtop->nmax,
1125 memtop->fragsize));
1126
1127#ifdef SEMAPHORE
1128 if(SEMAPHOREOBTAIN(memtop->semaphore_id))
1129 return NULL; /* failed somehow */
1130#endif
1131
1132 /* get the first BLOCK in the chain */
1133 block = memtop->chain;
1134
1135 /* check if we have a free FRAGMENT */
1136 if(memtop->nfree) {
1137 /* there exists a free FRAGMENT in this chain */
1138
1139 /* I WANT THIS LOOP OUT OF HERE! */
1140
1141 /* search for the free FRAGMENT */
1142 while(!block->nfree)
1143 block = block->next; /* check next BLOCK */
1144
1145 /*
1146 * Now 'block' is the first BLOCK with a free FRAGMENT
1147 */
1148
1149 mem = FragFromBlock(block);
1150
1151 }
1152 else {
1153 /* we do *not* have a free FRAGMENT but need to get us a new BLOCK */
1154
1155 DMEM_OSALLOCMEM(DMEM_BLOCKSIZE + sizeof(struct MemBlock),
1156 newblock,
1157 struct MemBlock *);
1158 if(!newblock) {
1159 if(++queue < sizeof(qinfo)/sizeof(qinfo[0])) {
1160 /* There are queues for bigger FRAGMENTS that we should check
1161 before we fail this for real */
1162#ifdef DEBUG
1163 printf("*** " __FILE__ " Trying a bigger Q: %d\n", queue);
1164#endif
1165 mem = NULL;
1166 }
1167 else {
1168 dmalloc_failed(size- sizeof(struct MemInfo));
1169 return NULL; /* not enough memory */
1170 }
1171 }
1172 else {
1173 /* allocation of big BLOCK was successful */
1174
1175 MEMINCR(newblock, DMEM_BLOCKSIZE + sizeof(struct MemBlock));
1176
1177 memtop->chain = newblock; /* attach this BLOCK to the chain */
1178 newblock->next = block; /* point to the previous first BLOCK */
1179 if(block)
1180 block->prev = newblock; /* point back on this new BLOCK */
1181 newblock->prev = NULL; /* no previous */
1182 newblock->top = memtop; /* our head master */
1183
1184 /* point to the new first FRAGMENT */
1185 newblock->first = (struct MemFrag *)
1186 ((char *)newblock+sizeof(struct MemBlock));
1187
1188 /* create FRAGMENTS of the BLOCK: */
1189 FragBlock((char *)newblock->first, memtop->fragsize);
1190
1191#if defined(DEBUG) && !defined(BMALLOC)
1192 checkmem((char *)newblock);
1193#endif
1194
1195 /* fix the nfree counters */
1196 newblock->nfree = memtop->nmax;
1197 memtop->nfree += memtop->nmax;
1198
1199 /* get a FRAGMENT from the BLOCK */
1200 mem = FragFromBlock(newblock);
1201 }
1202 }
1203#ifdef SEMAPHORE
1204 SEMAPHORERETURN(memtop->semaphore_id); /* let it go */
1205#endif
1206 } while(NULL == mem); /* if we should retry a larger FRAGMENT */
1207 }
1208 else {
1209 /* get a stand-alone BLOCK */
1210 struct MemInfo *meminfo;
1211
1212 if(size&1)
1213 /* don't leave this with an odd size since we'll use that bit for
1214 information */
1215 size++;
1216
1217 DMEM_OSALLOCMEM(size, meminfo, struct MemInfo *);
1218
1219 if(meminfo) {
1220 MEMINCR(meminfo, size);
1221 meminfo->block = (void *)(size|BLOCK_BIT);
1222 mem = (char *)meminfo + sizeof(struct MemInfo);
1223 }
1224 else {
1225 dmalloc_failed(size);
1226 mem = NULL;
1227 }
1228 }
1229 return (void *)mem;
1230}
1231
1232/***************************************************************************
1233 *
1234 * dfree()
1235 *
1236 * This needs no explanation. A free() look-alike.
1237 *
1238 **************************************************************************/
1239
1240void dfree(void *memp)
1241{
1242 struct MemInfo *meminfo = (struct MemInfo *)
1243 ((char *)memp- sizeof(struct MemInfo));
1244
1245 DBG(("dfree(%p)\n", memp));
1246
1247 if(!((size_t)meminfo->block&BLOCK_BIT)) {
1248 /* this is a FRAGMENT we have to deal with */
1249
1250 struct MemBlock *block=meminfo->block;
1251 struct MemTop *memtop = block->top;
1252
1253#ifdef SEMAPHORE
1254 SEMAPHOREOBTAIN(memtop->semaphore_id);
1255#endif
1256
1257 /* increase counters */
1258 block->nfree++;
1259 memtop->nfree++;
1260
1261 /* is this BLOCK completely empty now? */
1262 if(block->nfree == memtop->nmax) {
1263 /* yes, return the BLOCK to the system */
1264 if(block->prev)
1265 block->prev->next = block->next;
1266 else
1267 memtop->chain = block->next;
1268 if(block->next)
1269 block->next->prev = block->prev;
1270
1271 memtop->nfree -= memtop->nmax; /* total counter subtraction */
1272 MEMDECR(block, DMEM_BLOCKSIZE + sizeof(struct MemBlock));
1273 DMEM_OSFREEMEM((void *)block); /* return the whole block */
1274 }
1275 else {
1276 /* there are still used FRAGMENTS in the BLOCK, link this one
1277 into the chain of free ones */
1278 struct MemFrag *frag = (struct MemFrag *)meminfo;
1279 frag->prev = NULL;
1280 frag->next = block->first;
1281 if(block->first)
1282 block->first->prev = frag;
1283 block->first = frag;
1284 }
1285#ifdef SEMAPHORE
1286 SEMAPHORERETURN(memtop->semaphore_id);
1287#endif
1288 }
1289 else {
1290 /* big stand-alone block, just give it back to the OS: */
1291 MEMDECR(&meminfo->block, (size_t)meminfo->block&~BLOCK_BIT); /* clean BLOCK_BIT */
1292 DMEM_OSFREEMEM((void *)meminfo);
1293 }
1294}
1295
1296/***************************************************************************
1297 *
1298 * drealloc()
1299 *
1300 * This needs no explanation. A realloc() look-alike.
1301 *
1302 **************************************************************************/
1303
1304void *drealloc(char *ptr, size_t size)
1305{
1306 struct MemInfo *meminfo = (struct MemInfo *)
1307 ((char *)ptr- sizeof(struct MemInfo));
1308 /*
1309 * ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
1310 * NOTE: the ->size field of the meminfo will now contain the MemInfo
1311 * struct size too!
1312 * ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
1313 */
1314 void *mem=NULL; /* SAFE */
1315 size_t prevsize;
1316
1317 /* NOTE that this is only valid if BLOCK_BIT isn't set: */
1318 struct MemBlock *block;
1319
1320 DBG(("drealloc(%p, %d)\n", ptr, size));
1321
1322 if(NULL == ptr)
1323 return dmalloc( size );
1324
1325 block = meminfo->block;
1326
1327 if(!((size_t)meminfo->block&BLOCK_BIT) &&
1328 (size + sizeof(struct MemInfo) <
1329 (prevsize = block->top->fragsize) )) {
1330 /* This is a FRAGMENT and new size is possible to retain within the same
1331 FRAGMENT */
1332 if((prevsize > qinfo[0]) &&
1333 /* this is not the smallest memory Q */
1334 (size < (block->top-1)->fragsize))
1335 /* this fits in a smaller Q */
1336 ;
1337 else
1338 mem = ptr; /* Just return the same pointer as we got in. */
1339 }
1340 if(!mem) {
1341 /* This is a stand-alone BLOCK or a realloc that no longer fits within
1342 the same FRAGMENT */
1343
1344 if((size_t)meminfo->block&BLOCK_BIT) {
1345 prevsize = ((size_t)meminfo->block&~BLOCK_BIT) -
1346 sizeof(struct MemInfo);
1347 }
1348 else
1349 prevsize -= sizeof(struct MemInfo);
1350
1351 /* No tricks involved here, just grab a new bite of memory, copy the data
1352 * from the old place and free the old memory again. */
1353 mem = dmalloc(size);
1354 if(mem) {
1355 memcpy(mem, ptr, MIN(size, prevsize) );
1356 dfree(ptr);
1357 }
1358 }
1359 return mem;
1360}
1361
1362/***************************************************************************
1363 *
1364 * dcalloc()
1365 *
1366 * This needs no explanation. A calloc() look-alike.
1367 *
1368 **************************************************************************/
1369/* Allocate an array of NMEMB elements each SIZE bytes long.
1370 The entire array is initialized to zeros. */
1371void *
1372dcalloc (size_t nmemb, size_t size)
1373{
1374 void *result = dmalloc (nmemb * size);
1375
1376 if (result != NULL)
1377 memset (result, 0, nmemb * size);
1378
1379 return result;
1380}
generated by cgit v1.2.3 (git 2.39.1) at 2024-09-12 17:45:49 +0000