![[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] / 40BSD / cmd / px|
Return to malloc.c CVS log | Up to [CSRG BSD Unix] / 40BSD / cmd / px |
1.1 root 1: /* Copyright (c) 1979 Regents of the University of California */
2:
3: static char sccsid[] = "@(#)malloc.c 4.1 10/10/80";
4:
5: /*
6: * Patched up version of malloc to do an integrity check
7: * on each allocation or free.
8: */
9:
10: #ifdef debug
11: #define ASSERT(p,t) if(!(p))return(t(TRASHED));else
12: #else
13: #define ASSERT(p,t)
14: #endif
15:
16: /* avoid break bug */
17: #ifdef pdp11
18: #define GRANULE 64
19: #else
20: #define GRANULE 0
21: #endif
22: /* C storage allocator
23: * circular first-fit strategy
24: * works with noncontiguous, but monotonically linked, arena
25: * each block is preceded by a ptr to the (pointer of)
26: * the next following block
27: * blocks are exact number of words long
28: * aligned to the data type requirements of ALIGN
29: * pointers to blocks must have BUSY bit 0
30: * bit in ptr is 1 for busy, 0 for idle
31: * gaps in arena are merely noted as busy blocks
32: * last block of arena (pointed to by alloct) is empty and
33: * has a pointer to first
34: * idle blocks are coalesced during space search
35: *
36: * a different implementation may need to redefine
37: * ALIGN, NALIGN, BLOCK, BUSY, INT
38: * where INT is integer type to which a pointer can be cast
39: */
40: #define INT int
41: #define ALIGN int
42: #define NALIGN 1
43: #define WORD sizeof(union store)
44: #define BLOCK 1024 /* a multiple of WORD*/
45: #define BUSY 1
46: #define NULL 0
47: #define TRASHED -1
48: #define testbusy(p) ((INT)(p)&BUSY)
49: #define setbusy(p) (union store *)((INT)(p)|BUSY)
50: #define clearbusy(p) (union store *)((INT)(p)&~BUSY)
51:
52: union store { union store *ptr;
53: ALIGN dummy[NALIGN];
54: int calloc; /*calloc clears an array of integers*/
55: };
56:
57: static union store allocs[2]; /*initial arena*/
58: static union store *allocp; /*search ptr*/
59: static union store *alloct; /*arena top*/
60: char *sbrk();
61:
62: char *
63: malloc(nbytes)
64:
65: unsigned nbytes;
66: {
67: register union store *p, *q;
68: register nw;
69: static temp; /*coroutines assume no auto*/
70:
71: if(allocs[0].ptr==0) { /*first time*/
72: allocs[0].ptr = setbusy(&allocs[1]);
73: allocs[1].ptr = setbusy(&allocs[0]);
74: alloct = &allocs[1];
75: allocp = &allocs[0];
76: }
77: nw = (nbytes+WORD+WORD-1)/WORD;
78: ASSERT(allocp>=allocs && allocp<=alloct,(char *));
79: ASSERT(allock(),(char *));
80: for(p=allocp; ; ) {
81: for(temp=0; ; ) {
82: if(!testbusy(p->ptr)) {
83: while(!testbusy((q=p->ptr)->ptr)) {
84: ASSERT(q>p&&q<alloct,(char *));
85: p->ptr = q->ptr;
86: }
87: if(q>=p+nw && p+nw>=p)
88: goto found;
89: }
90: q = p;
91: p = clearbusy(p->ptr);
92: if(p>q)
93: ASSERT(p<=alloct,(char *));
94: else if(q!=alloct || p!=allocs) {
95: ASSERT(q==alloct&&p==allocs,(char *));
96: return(NULL);
97: } else if(++temp>1)
98: break;
99: }
100: temp = ((nw+BLOCK/WORD)/(BLOCK/WORD))*(BLOCK/WORD);
101: q = (union store *)sbrk(0);
102: if(q+temp+GRANULE < q) {
103: return(NULL);
104: }
105: q = (union store *)sbrk(temp*WORD);
106: if((INT)q == -1) {
107: return(NULL);
108: }
109: ASSERT(q>alloct,(char *));
110: alloct->ptr = q;
111: if(q!=alloct+1)
112: alloct->ptr = setbusy(alloct->ptr);
113: alloct = q->ptr = q+temp-1;
114: alloct->ptr = setbusy(allocs);
115: }
116: found:
117: allocp = p + nw;
118: ASSERT(allocp<=alloct,(char *));
119: if(q>allocp) {
120: allocp->ptr = p->ptr;
121: }
122: p->ptr = setbusy(allocp);
123: return((char *)(p+1));
124: }
125:
126: /*
127: * freeing strategy tuned for LIFO allocation
128: */
129:
130: free(ap)
131:
132: register char *ap;
133: {
134: register union store *p = (union store *)ap;
135:
136: ASSERT(p != 0,(long));
137: ASSERT(p>clearbusy(allocs[1].ptr)&&p<=alloct,(long));
138: ASSERT(allock(),(long));
139: allocp = --p;
140: ASSERT(testbusy(p->ptr),(long));
141: p->ptr = clearbusy(p->ptr);
142: ASSERT(p->ptr > allocp && p->ptr <= alloct,(long));
143: return(NULL);
144: }
145:
146: #ifdef debug
147: allock()
148: {
149: #ifdef longdebug
150: register union store *p;
151: int x;
152: x = 0;
153: for(p= &allocs[0]; clearbusy(p->ptr) > p; p=clearbusy(p->ptr)) {
154: if(p==allocp)
155: x++;
156: }
157: ASSERT(p==alloct,(long));
158: return(x==1|p==allocp);
159: #else
160: return(1);
161: #endif
162: }
163: #endif
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.