![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to malloc.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [CSRG BSD Unix] / 43BSDReno / contrib / isode-beta / quipu|
Return to malloc.c CVS log | Up to [CSRG BSD Unix] / 43BSDReno / contrib / isode-beta / quipu |
1.1 root 1: /* malloc.c - Quipu DSA specific memory management */
2:
3: #ifndef lint
4: static char *rcsid = "$Header: /f/osi/quipu/RCS/malloc.c,v 7.1 90/07/09 14:46:17 mrose Exp $";
5: #endif
6:
7: /*
8: * $Header: /f/osi/quipu/RCS/malloc.c,v 7.1 90/07/09 14:46:17 mrose Exp $
9: *
10: *
11: * $Log: malloc.c,v $
12: * Revision 7.1 90/07/09 14:46:17 mrose
13: * sync
14: *
15: * Revision 7.0 89/11/23 22:20:55 mrose
16: * Release 6.0
17: *
18: */
19:
20: /*
21: * NOTICE
22: *
23: * Acquisition, use, and distribution of this module and related
24: * materials are subject to the restrictions of a license agreement.
25: * Consult the Preface in the User's Manual for the full terms of
26: * this agreement.
27: *
28: */
29:
30: #include <stdio.h>
31: #include "manifest.h"
32: #include "quipu/malloc.h"
33: #include "quipu/util.h"
34:
35: static int malloc_file = 0;
36:
37: #ifdef QUIPU_MALLOC
38:
39: extern LLog * log_dsap;
40: extern SFD attempt_restart();
41:
42: #if defined(DEBUG) && defined(sun3)
43: #define MALLOCSTACK
44: #endif
45:
46: #ifdef MALLOCSTACK
47: #include <sys/file.h>
48: off_t lseek();
49: #ifndef MALLOCTRACE
50: #define MALLOCTRACE
51: #endif
52: #else
53: #define write_stack(x)
54: #endif
55:
56:
57: #define MAXHEAP 100 /* Number of heaps */
58: #ifndef BSD42
59: #define PAGESIZE 0x2000 /* The systems memory page size */
60: #else
61: #define PAGESIZE pagesize
62: #endif
63:
64: #define ALIGN(x) (((x) + (sizeof(char *) - 1)) & ~(sizeof(char *) - 1))
65: #define PAGEALIGN(x) (((x) + (PAGESIZE-1)) & ~(PAGESIZE-1))
66: #define SMALLMAX 65536 /* largest block a short can reference */
67:
68:
69: struct header {
70: union {
71: struct {
72: unsigned short control;
73: unsigned short size;
74: } small;
75: unsigned int big;
76: } un;
77: };
78:
79: #define bigsize un.big
80: #define smallsize un.small.size
81: #define use un.small.control
82:
83: #define INUSE 0x1000
84: #define USED(x) (x->use & INUSE)
85:
86: /* sizes chosen for anticipated QUIPU behaviour */
87: #define BUCKETS 11
88: static unsigned sizes [BUCKETS] = { 0, 12, 16, 24, 48, 64, 128, 256, 512, 8191, 0 };
89:
90: struct freelist {
91: struct header * block;
92: unsigned int size;
93: struct freelist * next;
94: struct freelist * prev;
95: };
96:
97: struct freehead {
98: struct header head;
99: struct freelist * flist;
100: };
101:
102: static struct freelist heaps[MAXHEAP][BUCKETS];
103: static struct freelist *heapptr[MAXHEAP];
104: static struct freelist bigmem = { 0,0,&bigmem, &bigmem};
105: static struct freelist *bigfree = &bigmem;
106: static struct freelist freemem = { 0,0,&freemem, &freemem};
107: static struct freelist *listfree = &freemem;
108:
109: static int first_malloc = 1;
110: static char * top_mem;
111:
112: #ifdef BSD42
113: static int pagesize = 0x2000;
114: #endif
115:
116: extern caddr_t sbrk();
117:
118: #ifdef MALLOCTRACE
119: static int malloc_started = 0;
120: static char * malloc_fname = (char *)0;
121: #endif
122:
123: #ifndef MALLOCTRACE
124: /* ARGSUSED */
125: #endif
126:
127: #endif
128:
129: start_malloc_trace(f)
130: char * f;
131: {
132: #ifdef MALLOCTRACE
133: char * env, *getenv ();
134:
135: if (((env = getenv ("TRACE_MEMORY")) == (char *)0) || (*env == 0))
136: return;
137:
138: if (! malloc_started) {
139: if (f == (char *)0)
140: malloc_fname = "memory.out";
141: else
142: malloc_fname = f;
143: malloc_file = creat (malloc_fname,0644);
144: malloc_started = 1;
145: } else {
146: malloc_file = open (malloc_fname,1);
147: (void) lseek (malloc_file,0l,2);
148: }
149: #else
150: malloc_file = 0;
151: #endif
152: }
153:
154: stop_malloc_trace ()
155: {
156: #ifdef MALLOCTRACE
157: if (malloc_file)
158: (void) close (malloc_file);
159: #endif
160: malloc_file = 0;
161: }
162:
163: #ifdef QUIPU_MALLOC
164: #ifdef MALLOCTRACE
165:
166: static write_string (p)
167: char *p;
168: {
169: register char *q;
170:
171: if (!malloc_file)
172: return;
173:
174: q = p;
175: while (*q++)
176: ;
177: (void) write(malloc_file, p, q-p-1);
178: }
179:
180: static write_addr(addr)
181: char *addr;
182: {
183: char buf[20];
184: static char hex[] = "0123456789abcdef";
185: char *ptr;
186: int x;
187:
188: if (!malloc_file)
189: return;
190:
191: x = (int) addr;
192:
193: if (x == 0) {
194: (void) write(malloc_file, "0 ",2);
195: return;
196: }
197:
198: ptr = buf;
199: while (x > 0)
200: *ptr++ = hex[x % 16], x /= 16;
201: *ptr = 0;
202:
203: while (ptr != buf)
204: (void) write(malloc_file, --ptr,1);
205:
206: (void) write (malloc_file," ",1);
207: }
208:
209: static write_int(x)
210: unsigned x;
211: {
212: char buf[20];
213: static char dec[] = "0123456789";
214: char *ptr;
215:
216: if (!malloc_file)
217: return;
218:
219: if (x == 0) {
220: (void) write(malloc_file, "0 ",2);
221: return;
222: }
223:
224: ptr = buf;
225: while (x > 0)
226: *ptr++ = dec[x % 10], x /= 10;
227:
228: while (ptr != buf)
229: (void) write(malloc_file, --ptr,1);
230:
231: (void) write (malloc_file," ",1);
232: }
233:
234: static char * log_realloc (oldlen,newlen,bsize,addr)
235: unsigned oldlen,newlen,bsize;
236: char * addr;
237: {
238: write_string ("realloc of "); write_int (oldlen);
239: write_string ("at "); write_addr (addr);
240: write_string ("\n");
241: write_stack("x");
242:
243: write_string ("realloc-to of "); write_int (newlen);
244: write_string ("gets "); write_int (bsize);
245: write_string ("at "); write_addr (addr);
246: write_string ("\n");
247: write_stack("x");
248: }
249:
250: static print_free_list (heap)
251: unsigned heap;
252: {
253: int i;
254: struct freelist * top;
255: struct freelist * ptr;
256:
257: write_string ("free list for heap ");write_int(heap);write_string(":\n");
258: for (i=0; i<BUCKETS; i++) {
259: top = &heaps[heap][i];
260: write_int (sizes[i]); write_string (": ");
261: for (ptr = top->next ; ptr != top; ptr=ptr->next)
262: write_int (ptr->size);
263: write_string ("\n");
264: }
265: }
266:
267: #ifdef MALLOCSTACK
268:
269: /* ever so slightly machine dependant !!! */
270:
271: static write_stack (x)
272: char * x;
273: {
274:
275: struct stackframe {
276: struct stackframe *next;
277: char *addr;
278: } * frame;
279:
280: for (frame = ((struct stackframe *)(&x-2))->next ; frame; frame = frame->next) {
281: write_string ("C ");
282: write_addr ((char *)frame->addr);
283: write_string ("\n");
284: }
285: write_string ("\n");
286:
287: }
288: #endif
289: #endif
290:
291:
292: static return_freelist (next)
293: struct freelist *next;
294: {
295: next->next = listfree->next;
296: next->prev = listfree;
297: listfree->next->prev = next;
298: listfree->next = next;
299: }
300:
301: static struct freelist * new_freelist ()
302: {
303: struct freelist * flist;
304:
305: flist = listfree->next;
306:
307: if (flist == listfree) {
308: int i;
309: struct freelist * next;
310: /* go and get some more */
311: if ((flist = (struct freelist *) sbrk (PAGESIZE)) == (struct freelist *)0) {
312: /* there are 100s of places where Quipu would choke on a naff malloc */
313: attempt_restart (-2);
314: return ((struct freelist *)0);
315: }
316: top_mem = (char *)flist + PAGESIZE;
317: next = (struct freelist *)flist;
318: next++;
319: for (i=sizeof (struct freelist); i< PAGESIZE ; i+=sizeof (struct freelist))
320: return_freelist (next++);
321: } else {
322: flist->prev->next = flist->next;
323: flist->next->prev = flist->prev;
324: }
325:
326: return (flist);
327: }
328:
329:
330: static char * big_malloc (realsize)
331: /* used for mallocs of > MAXSMALL */
332: unsigned realsize;
333: {
334: unsigned blocksize;
335: struct freelist * flist;
336: struct header * head = (struct header *)0;
337: char * mem;
338:
339: for (flist = bigfree->next; flist != bigfree; flist=flist->next) {
340: if (flist->size >= realsize) {
341: head = flist->block;
342: flist->prev->next = flist->next;
343: flist->next->prev = flist->prev;
344: return_freelist (flist);
345: break;
346: }
347: }
348:
349: if (head == (struct header *)0) {
350: /* go and get on then !!! */
351: blocksize = PAGEALIGN(realsize);
352: if ((head = (struct header *) sbrk ((int)blocksize)) == (struct header *)0) {
353: /* there are 100s of places where Quipu would choke on a naff malloc */
354: attempt_restart (-2);
355: return ((char *)0);
356: }
357: top_mem = (char *)head + blocksize;
358: head->bigsize = blocksize | 0x01;
359: } else
360: head->bigsize |= 0x01;
361:
362: mem = (char *) head + ALIGN(sizeof (struct header));
363:
364: #ifdef MALLOCTRACE
365: write_string ("gets "); write_int (head->bigsize);
366: write_string ("at "); write_addr (mem);
367: write_string ("\n");
368: write_stack("x");
369: #endif
370:
371: return (mem);
372:
373: }
374:
375: static big_free (ptr)
376: struct header *ptr;
377: {
378: struct freelist *next;
379: struct freehead *x;
380:
381: if ((next = new_freelist ()) == (struct freelist *)0)
382: return;
383: next->size=ptr->bigsize;
384: next->block = ptr;
385: ptr->bigsize &= ~1;
386: next->next = bigfree->next;
387: next->prev = bigfree;
388: bigfree->next->prev = next;
389: bigfree->next = next;
390:
391: x = (struct freehead *) ptr;
392: x->flist = next;
393: }
394:
395: static which_list (size)
396: register unsigned size;
397: {
398: register unsigned * p;
399:
400: p = sizes;
401: p [BUCKETS -1] = size; /* force stop to while loop */
402:
403: while ( size > *p++ )
404: ;
405:
406: return ( (p-1) - sizes);
407: }
408:
409: static add_free (x)
410: struct header * x;
411: {
412: struct freelist *next, *c;
413: struct freehead *ptr;
414:
415: x->use &= ~INUSE;
416:
417: if ((c = heapptr[x->use]) == (struct freelist *) 0)
418: c = heapptr[x->use] = heaps[x->use];
419:
420: c = &c[which_list(x->smallsize)];
421:
422: if ((next = new_freelist ()) == (struct freelist *)0)
423: return;
424: next->size=x->smallsize;
425: next->block = x;
426: next->next = c->next;
427: next->prev = c;
428: c->next->prev = next;
429: c->next = next;
430:
431: ptr = (struct freehead *) x;
432: ptr->flist = next;
433: }
434:
435: static remove_free (a)
436: register struct freelist * a;
437: {
438: a->block->use |= INUSE;
439: a->prev->next = a->next;
440: a->next->prev = a->prev;
441: return_freelist(a);
442: }
443:
444: static struct header * next_free_block (ptr)
445: register struct header * ptr;
446: {
447: register struct header * next;
448:
449: next = (struct header *)((char *)ptr + ptr->smallsize);
450: if (PAGEALIGN((int)ptr) != PAGEALIGN((int)next + 1))
451: return (struct header *)0;
452: if (((char *)next < top_mem) && (next->use == (ptr->use & ~INUSE)))
453: return (next);
454:
455: return (struct header *)0;
456:
457: }
458:
459: static struct header * find_block (size)
460: unsigned size;
461: {
462: register struct freelist * top;
463: register struct freelist * ptr;
464: register int i;
465: #ifdef BESTFIT
466: struct freelist * best = (struct freelist *)0;
467: #endif
468:
469: if ((top = heapptr[mem_heap]) == (struct freelist *)0)
470: return ((struct header *) 0);
471:
472: top = &top[i = which_list (size)];
473:
474: for (; i < BUCKETS ; i++,top++ ) {
475: for (ptr = top->next ; ptr != top; ptr=ptr->next) {
476: if (ptr->size >= size) {
477: #ifdef BESTFIT
478: if (ptr->size == size) {
479: remove_free (ptr);
480: return (&(ptr->block));
481: }
482: if ( (best == (struct freelist *)0)
483: || (ptr->size < best->size))
484: best = ptr;
485:
486: #else
487: remove_free (ptr);
488: return (ptr->block);
489: #endif
490: }
491: }
492:
493: #ifdef BESTFIT
494: if (best != (struct freelist *)0) {
495: remove_free (best);
496: return (&(best->block));
497: }
498: #endif
499: }
500: return (struct header *)0;
501: }
502:
503: static use_block (ptr,size)
504: register struct header *ptr;
505: register unsigned size;
506: {
507: register struct header *next;
508:
509: if ((ptr->smallsize == size) || (ptr->smallsize < size + sizeof (struct freehead)))
510: return; /* don't split it -> left with block too small for use */
511:
512: next = (struct header *)((char *)ptr + size);
513: next->smallsize = ptr->smallsize - size;
514: next->use = ptr->use & ~INUSE;
515:
516: ptr->smallsize = size;
517: ptr->use |= INUSE;
518:
519: add_free (next);
520: }
521:
522: char * malloc (size)
523: register unsigned size;
524: {
525: char * mem;
526: struct header *head;
527: register unsigned realsize, blocksize;
528:
529: #ifdef BSD42
530: if (first_malloc)
531: pagesize = getpagesize ();
532: #endif
533:
534: if (mem_heap >= MAXHEAP)
535: mem_heap = MAXHEAP - 1;
536:
537: if (size < sizeof (struct freelist *)) /* memory will be used when freed for freelist !!! */
538: realsize = ALIGN (sizeof (struct freehead));
539: else
540: realsize = ALIGN (size) + ALIGN (sizeof (struct header));
541:
542: if (realsize >= SMALLMAX) {
543: #ifdef MALLOCTRACE
544: write_string ("malloc of "); write_int (size);
545: #endif
546: return (big_malloc (realsize));
547: }
548:
549: if (first_malloc) {
550: /* set up freelist */
551: unsigned x;
552: int i,j;
553:
554: for (i = 0; i < MAXHEAP; i++) {
555: heapptr[i] = (struct freelist *) 0;
556: for (j = 0 ; j<BUCKETS; j++) {
557: heaps[i][j].prev = &heaps[i][j];
558: heaps[i][j].next = &heaps[i][j];
559: heaps[i][j].size = 0;
560: }
561: }
562:
563: /* align first sbrk to page boundary */
564: x = (unsigned)sbrk(0);
565: x = PAGEALIGN (x) - x;
566: blocksize = PAGEALIGN(realsize) + x;
567: if ((head = (struct header *) sbrk ((int)blocksize)) == (struct header *)0) {
568: /* there are 100s of places where Quipu would choke on a naff malloc */
569: attempt_restart (-2);
570: return ((char *)0);
571: }
572: head->smallsize = blocksize;
573: top_mem = (char *)head + blocksize;
574: first_malloc = 0;
575: head->use = INUSE | mem_heap;
576: use_block (head,realsize);
577:
578: } else if ((head = find_block (realsize)) == (struct header *)0) {
579: blocksize = PAGEALIGN(realsize);
580: if ((head = (struct header *) sbrk ((int)blocksize)) == (struct header *)0) {
581: /* there are 100s of places where Quipu would choke on a naff malloc */
582: attempt_restart (-2);
583: return ((char *)0);
584: }
585: head->smallsize = blocksize;
586: top_mem = (char *)head + blocksize;
587: head->use = INUSE | mem_heap;
588: use_block (head,realsize);
589: } else
590: use_block (head,realsize);
591:
592: mem = (char *) head + ALIGN(sizeof (struct header));
593:
594: #ifdef MALLOCTRACE
595: write_string ("malloc of "); write_int (size);
596: write_string ("gets "); write_int (head->smallsize);
597: write_string ("at "); write_addr (mem);
598: write_string ("heap ");write_int (mem_heap);
599: write_string ("\n");
600: write_stack("x");
601: #endif
602:
603: return (mem);
604: }
605:
606: free(s)
607: char *s;
608: {
609: struct header * ptr;
610: struct header * next;
611:
612: ptr = (struct header *) (s - ALIGN (sizeof (struct header)));
613:
614: if (ptr->smallsize & 1) {
615: #ifdef MALLOCTRACE
616: write_string ("free of "); write_int (ptr->bigsize);
617: write_string ("at "); write_addr (s);
618: write_string ("heap (big)\n");
619: write_stack("x");
620: #endif
621: big_free (ptr);
622: return;
623: }
624:
625: #ifdef MALLOCTRACE
626: write_string ("free of "); write_int (ptr->smallsize);
627: write_string ("at "); write_addr (s);
628: write_string ("heap "); write_int (ptr->use & ~INUSE);
629: write_string ("\n");
630: write_stack("x");
631: #endif
632:
633: if (! USED(ptr)) {
634: LLOG (log_dsap,LLOG_EXCEPTIONS,("freeing problem"));
635: return; /* already freed !!! */
636: }
637:
638: /* join forward free block in loop to catch previous back blocks ! */
639: while ((next = next_free_block(ptr)) != (struct header *) 0) {
640: ptr->smallsize += next->smallsize;
641: remove_free (((struct freehead *)next)->flist);
642: }
643: add_free (ptr);
644:
645: return;
646:
647: }
648:
649:
650: char *realloc(s, n)
651: char *s;
652: register unsigned n;
653: {
654: char * mem;
655: register unsigned realsize;
656: struct header * ptr;
657: struct header * next;
658:
659: ptr = (struct header *) (s - ALIGN (sizeof (struct header)));
660:
661: if (ptr->smallsize & 1) {
662: DLOG (log_dsap,LLOG_DEBUG,("re-alloc of big block"));
663: #ifdef MALLOCTRACE
664: write_stack ("x");
665: #endif
666: goto out;
667: }
668:
669: if (! USED(ptr)) {
670: LLOG (log_dsap,LLOG_EXCEPTIONS,("re-alloc problem"));
671: #ifdef MALLOCTRACE
672: write_stack ("x");
673: #endif
674: goto out;
675: }
676:
677: realsize = ALIGN (n) + ALIGN (sizeof (struct header));
678: if (ptr->smallsize >= realsize) {
679: #ifdef MALLOCTRACE
680: log_realloc (ptr->smallsize,realsize,ptr->smallsize,s);
681: #endif
682: return (s);
683: }
684:
685: /* see if next block is free */
686: if ((next = next_free_block(ptr)) != (struct header *) 0) {
687: struct header * top;
688:
689: top = next;
690: /* join with other free blocks */
691: while ((next = next_free_block(top)) != (struct header *) 0) {
692: top->smallsize += next->smallsize;
693: remove_free (((struct freehead *)next)->flist);
694: }
695: remove_free (((struct freehead *)top)->flist);
696:
697: /* is it big enough ? */
698: if (ptr->smallsize + top->smallsize >= realsize) {
699: #ifdef MALLOCTRACE
700: unsigned savesize;
701: savesize = ptr->smallsize;
702: #endif
703:
704: ptr->smallsize += top->smallsize;
705: use_block (ptr,realsize);
706: #ifdef MALLOCTRACE
707: log_realloc (savesize,realsize,ptr->smallsize,s);
708: #endif
709: return (s);
710: } else
711: /* return to free list */
712: add_free (top);
713: }
714:
715: out:;
716: if ((mem = malloc (n)) == (char *)0)
717: return ((char *)0);
718: bcopy (s,mem,(int)n);
719: free (s);
720:
721: return (mem);
722: }
723:
724: char *calloc(n, size)
725: unsigned n, size;
726: {
727: char * mem;
728: unsigned x;
729:
730: x= n*size;
731: if ((mem = malloc (x)) == (char *)0)
732: return ((char *)0);
733: bzero (mem,(int)x);
734: return (mem);
735: }
736:
737: void
738: cfree(mem)
739: char * mem;
740: {
741: free(mem);
742: }
743:
744: #endif
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.