1: #ifdef debug
2: #define ASSERT(p) if(!(p))botch("p");else
3: botch(s)
4: char *s;
5: {
6: printf("assertion botched: %s\n",s);
7: abort();
8: }
9: #else
10: #define ASSERT(p)
11: #endif
12:
13: /* avoid break bug */
14: #ifdef pdp11
15: #define GRANULE 64
16: #else
17: #define GRANULE 0
18: #endif
19: /* C storage allocator
20: * circular first-fit strategy
21: * works with noncontiguous, but monotonically linked, arena
22: * each block is preceded by a ptr to the (pointer of)
23: * the next following block
24: * blocks are exact number of words long
25: * aligned to the data type requirements of ALIGN
26: * pointers to blocks must have BUSY bit 0
27: * bit in ptr is 1 for busy, 0 for idle
28: * gaps in arena are merely noted as busy blocks
29: * last block of arena (pointed to by alloct) is empty and
30: * has a pointer to first
31: * idle blocks are coalesced during space search
32: *
33: * a different implementation may need to redefine
34: * ALIGN, NALIGN, BLOCK, BUSY, INT
35: * where INT is integer type to which a pointer can be cast
36: */
37: #define INT int
38: #define ALIGN int
39: #define NALIGN 1
40: #define WORD sizeof(union store)
41: #define BLOCK 1024 /* a multiple of WORD*/
42: #define BUSY 1
43: #define NULL 0
44: #define testbusy(p) ((INT)(p)&BUSY)
45: #define setbusy(p) (union store *)((INT)(p)|BUSY)
46: #define clearbusy(p) (union store *)((INT)(p)&~BUSY)
47:
48: union store { union store *ptr;
49: ALIGN dummy[NALIGN];
50: int calloc; /*calloc clears an array of integers*/
51: };
52:
53: static union store allocs[2]; /*initial arena*/
54: static union store *allocp; /*search ptr*/
55: static union store *alloct; /*arena top*/
56: static union store *allocx; /*for benefit of realloc*/
57: char *sbrk();
58:
59: char *
60: malloc(nbytes)
61: unsigned nbytes;
62: {
63: register union store *p, *q;
64: register nw;
65: static temp; /*coroutines assume no auto*/
66:
67: if(allocs[0].ptr==0) { /*first time*/
68: allocs[0].ptr = setbusy(&allocs[1]);
69: allocs[1].ptr = setbusy(&allocs[0]);
70: alloct = &allocs[1];
71: allocp = &allocs[0];
72: }
73: nw = (nbytes+WORD+WORD-1)/WORD;
74: ASSERT(allocp>=allocs && allocp<=alloct);
75: ASSERT(allock());
76: for(p=allocp; ; ) {
77: for(temp=0; ; ) {
78: if(!testbusy(p->ptr)) {
79: while(!testbusy((q=p->ptr)->ptr)) {
80: ASSERT(q>p&&q<alloct);
81: p->ptr = q->ptr;
82: }
83: if(q>=p+nw && p+nw>=p)
84: goto found;
85: }
86: q = p;
87: p = clearbusy(p->ptr);
88: if(p>q)
89: ASSERT(p<=alloct);
90: else if(q!=alloct || p!=allocs) {
91: ASSERT(q==alloct&&p==allocs);
92: return(NULL);
93: } else if(++temp>1)
94: break;
95: }
96: temp = ((nw+BLOCK/WORD)/(BLOCK/WORD))*(BLOCK/WORD);
97: q = (union store *)sbrk(0);
98: if(q+temp+GRANULE < q) {
99: return(NULL);
100: }
101: q = (union store *)sbrk(temp*WORD);
102: if((INT)q == -1) {
103: return(NULL);
104: }
105: ASSERT(q>alloct);
106: alloct->ptr = q;
107: if(q!=alloct+1)
108: alloct->ptr = setbusy(alloct->ptr);
109: alloct = q->ptr = q+temp-1;
110: alloct->ptr = setbusy(allocs);
111: }
112: found:
113: allocp = p + nw;
114: ASSERT(allocp<=alloct);
115: if(q>allocp) {
116: allocx = allocp->ptr;
117: allocp->ptr = p->ptr;
118: }
119: p->ptr = setbusy(allocp);
120: return((char *)(p+1));
121: }
122:
123: /* freeing strategy tuned for LIFO allocation
124: */
125: free(ap)
126: register char *ap;
127: {
128: register union store *p = (union store *)ap;
129:
130: ASSERT(p>clearbusy(allocs[1].ptr)&&p<=alloct);
131: ASSERT(allock());
132: allocp = --p;
133: ASSERT(testbusy(p->ptr));
134: p->ptr = clearbusy(p->ptr);
135: ASSERT(p->ptr > allocp && p->ptr <= alloct);
136: }
137:
138: /* realloc(p, nbytes) reallocates a block obtained from malloc()
139: * and freed since last call of malloc()
140: * to have new size nbytes, and old content
141: * returns new location, or 0 on failure
142: */
143:
144: char *
145: realloc(p, nbytes)
146: register union store *p;
147: unsigned nbytes;
148: {
149: register union store *q;
150: union store *s, *t;
151: register unsigned nw;
152: unsigned onw;
153:
154: if(testbusy(p[-1].ptr))
155: free((char *)p);
156: onw = p[-1].ptr - p;
157: q = (union store *)malloc(nbytes);
158: if(q==NULL || q==p)
159: return((char *)q);
160: s = p;
161: t = q;
162: nw = (nbytes+WORD-1)/WORD;
163: if(nw<onw)
164: onw = nw;
165: while(onw--!=0)
166: *t++ = *s++;
167: if(q<p && q+nw>=p)
168: (q+(q+nw-p))->ptr = allocx;
169: return((char *)q);
170: }
171:
172: #ifdef debug
173: allock()
174: {
175: #ifdef longdebug
176: register union store *p;
177: int x;
178: x = 0;
179: for(p= &allocs[0]; clearbusy(p->ptr) > p; p=clearbusy(p->ptr)) {
180: if(p==allocp)
181: x++;
182: }
183: ASSERT(p==alloct);
184: return(x==1|p==allocp);
185: #else
186: return(1);
187: #endif
188: }
189: #endif
Defined functions
botch
defined in line
3; used 1 times
free
defined in line
125; used 74 times
- in line 155
- in /usr/include/mp.h line
6-11(3)
- in /usr/src/cmd/awk/tran.c line
63,
230
- in /usr/src/cmd/col.c line
214,
302
- in /usr/src/cmd/cron.c line
146,
158
- in /usr/src/cmd/dc/dc.c line
1759,
1792,
1871-1872(2),
1891
- in /usr/src/cmd/dcheck.c line
117
- in /usr/src/cmd/diff.c line
130-131(2),
188,
342-348(4)
- in /usr/src/cmd/ed.c line
747
- in /usr/src/cmd/icheck.c line
172,
185
- in /usr/src/cmd/m4/m4.c line
497,
517-519(3)
- in /usr/src/cmd/nm.c line
190
- in /usr/src/cmd/ratfor/r1.c line
260
- in /usr/src/cmd/ratfor/rlook.c line
54
- in /usr/src/cmd/refer/glue1.c line
121-124(2)
- in /usr/src/cmd/refer/hunt2.c line
232-233(2)
- in /usr/src/cmd/struct/0.alloc.c line
31,
82
- in /usr/src/cmd/struct/0.parts.c line
108
- in /usr/src/cmd/struct/beauty.y line
77-90(5),
98,
168,
175-185(3),
195,
202-208(3),
227-228(2),
408-410(2)
- in /usr/src/cmd/struct/tree.c line
35-36(2),
74,
88
- in /usr/src/cmd/uucp/anlwrk.c line
69
- in /usr/src/cmd/uucp/gnsys.c line
67
- in /usr/src/cmd/uucp/ulockf.c line
108
- in /usr/src/libI77/close.c line
16,
25
- in /usr/src/libI77/lread.c line
321
- in /usr/src/libI77/util.c line
110-114(2)
- in /usr/src/libc/gen/calloc.c line
30
- in /usr/src/libc/stdio/flsbuf.c line
103
- in /usr/src/libc/stdio/setbuf.c line
8
- in /usr/src/libmp/mout.c line
74
malloc
defined in line
59; used 108 times
- in line 157
- in /usr/src/cmd/awk/awk.def line
48
- in /usr/src/cmd/awk/b.c line
275,
473
- in /usr/src/cmd/awk/main.c line
116,
134
- in /usr/src/cmd/awk/parse.c line
6
- in /usr/src/cmd/awk/run.c line
319,
515
- in /usr/src/cmd/awk/tran.c line
42,
85,
220,
233-237(3)
- in /usr/src/cmd/cc.c line
424,
432
- in /usr/src/cmd/col.c line
210-215(2)
- in /usr/src/cmd/cron.c line
19,
149
- in /usr/src/cmd/dc/dc.c line
886,
1675-1678(2),
1692-1695(2),
1873,
1933-1935(2)
- in /usr/src/cmd/dc/dc.h line
114
- in /usr/src/cmd/dcheck.c line
31,
86
- in /usr/src/cmd/diff.c line
117-119(2),
132,
201,
321
- in /usr/src/cmd/diffh.c line
24,
41
- in /usr/src/cmd/ed.c line
97,
145
- in /usr/src/cmd/eqn/lex.c line
189-192(2)
- in /usr/src/cmd/eqn/lookup.c line
184,
199
- in /usr/src/cmd/expr.y line
60,
128,
184,
196,
206-208(2)
- in /usr/src/cmd/graph.c line
58,
74-75(2)
- in /usr/src/cmd/icheck.c line
44,
141
- in /usr/src/cmd/learn/learn.c line
11-16(2)
- in /usr/src/cmd/ls.c line
331,
338
- in /usr/src/cmd/m4/m4.c line
103,
486,
527
- in /usr/src/cmd/neqn/lex.c line
189-192(2)
- in /usr/src/cmd/neqn/lookup.c line
184,
199
- in /usr/src/cmd/nm.c line
30,
159
- in /usr/src/cmd/quot.c line
43,
231
- in /usr/src/cmd/ratfor/r.h line
61
- in /usr/src/cmd/ratfor/r1.c line
184,
237
- in /usr/src/cmd/ratfor/rlook.c line
14,
46,
64
- in /usr/src/cmd/spline.c line
272,
314-315(2)
- in /usr/src/cmd/struct/0.alloc.c line
17,
93
- in /usr/src/cmd/struct/beauty.y line
304
- in /usr/src/cmd/struct/tree.c line
12-16(2),
75,
89,
95
- in /usr/src/cmd/tar/tar.c line
53,
403
- in /usr/src/cmd/tsort.c line
32,
61,
120-121(2)
- in /usr/src/cmd/uucp/pk1.c line
37
- in /usr/src/cmd/xsend/xsend.c line
27
- in /usr/src/games/quiz.c line
26,
294
- in /usr/src/libI77/lread.c line
323
- in /usr/src/libc/gen/calloc.c line
11-16(2)
- in /usr/src/libc/stdio/filbuf.c line
3,
24
- in /usr/src/libc/stdio/flsbuf.c line
3,
37
- in /usr/src/libmp/mout.c line
62
- in /usr/src/libmp/util.c line
1,
21
Defined variables
allocp
defined in line
54; used 14 times
allocs
defined in line
53; used 13 times
alloct
defined in line
55; used 17 times
Defined union's
store
defined in line
48; used 30 times
Defined macros
ALIGN
defined in line
38; used 1 times
ASSERT
defined in line
10; used 12 times
BLOCK
defined in line
41; used 3 times
BUSY
defined in line
42; used 3 times
INT
defined in line
37; used 4 times
NULL
defined in line
43; used 4 times
WORD
defined in line
40; used 9 times