Commit | Line | Data |
---|---|---|
eb5ad1d2 F |
1 | #define ASSERT(p) if(!(p))botch("p");else |
2 | botch(s) | |
3 | char *s; | |
4 | { | |
5 | printf("assertion botched: %s\n",s); | |
6 | abort(); | |
7 | } | |
8 | /* C storage allocator | |
9 | * circular first-fit strategy | |
10 | * works with noncontiguous, but monotonically linked, arena | |
11 | * each block is preceded by a ptr to the (pointer of) | |
12 | * the next following block | |
13 | * blocks are exact number of words long; BUSY | |
14 | * bit in ptr is 1 for busy, 0 for idle | |
15 | * gaps in arena are merely noted as busy blocks | |
16 | * last block of arena (pointed to by alloct) is empty and | |
17 | * has a pointer to first | |
18 | * idle blocks are coalesced during space search | |
19 | */ | |
20 | /* all these defines must be powers of 2 */ | |
21 | #define WORD sizeof(struct store) | |
22 | #define BLOCK 1024 | |
23 | #define BUSY 1 | |
24 | #define NULL 0 | |
25 | #define testbusy(p) ((int)(p)&BUSY) | |
26 | #define setbusy(p) ((int)(p)+BUSY) | |
27 | #define clearbusy(p) ((int)(p)&~BUSY) | |
28 | ||
29 | struct store { struct store *ptr; }; | |
30 | ||
31 | struct store allocs[] = { /*initial arena*/ | |
32 | setbusy(&allocs[1].ptr), | |
33 | setbusy(&allocs[0].ptr) | |
34 | }; | |
35 | struct store *allocp = &allocs[1]; /*search ptr*/ | |
36 | struct store *alloct = &allocs[1]; /*arena top*/ | |
37 | struct store *allocx; /*for benefit of realloc*/ | |
38 | struct store *sbrk(); | |
39 | ||
40 | struct store * | |
41 | malloc(nbytes) | |
42 | unsigned nbytes; | |
43 | { | |
44 | register struct store *p, *q; | |
45 | register nw; | |
46 | static temp; /*coroutines assume no auto*/ | |
47 | ||
48 | nw = (nbytes+2*WORD-1)/WORD; | |
49 | ASSERT(allocp>allocs && allocp<=alloct); | |
50 | for(p=allocp; ; ) { | |
51 | for(temp=0; ; ) { | |
52 | if(!testbusy(p->ptr)) { | |
53 | while(!testbusy((q=p->ptr)->ptr)) { | |
54 | ASSERT(q>p&&q<alloct); | |
55 | p->ptr = q->ptr; | |
56 | } | |
57 | if(q>=p+nw && p+nw>=p) | |
58 | goto found; | |
59 | } | |
60 | q = p; | |
61 | p = clearbusy(p->ptr); | |
62 | if(p>q) | |
63 | ASSERT(p<=alloct); | |
64 | else if(q!=alloct || p!=allocs) { | |
65 | write(2,"corrupt arena\n",14); | |
66 | exit(0175); | |
67 | } else if(++temp>1) | |
68 | break; | |
69 | } | |
70 | temp = (nw+BLOCK/WORD)&~(BLOCK/WORD-1); | |
71 | q = sbrk(0); | |
72 | if(q+temp < q) | |
73 | return(NULL); | |
74 | q = sbrk(temp*WORD); | |
75 | if((int)q == -1) | |
76 | return(NULL); | |
77 | ASSERT(q>alloct); | |
78 | alloct->ptr = q; | |
79 | if(q!=alloct+1) | |
80 | alloct->ptr = setbusy(alloct->ptr); | |
81 | alloct = q->ptr = q+temp-1; | |
82 | alloct->ptr = setbusy(allocs); | |
83 | } | |
84 | found: | |
85 | allocp = p + nw; | |
86 | ASSERT(allocp<=alloct); | |
87 | if(q>allocp) { | |
88 | allocx = allocp->ptr; | |
89 | allocp->ptr = p->ptr; | |
90 | } | |
91 | p->ptr = setbusy(allocp); | |
92 | return(p+1); | |
93 | } | |
94 | /* freeing strategy tuned for LIFO allocation | |
95 | */ | |
96 | free(p) | |
97 | register struct store *p; | |
98 | { | |
99 | ASSERT(p>clearbusy(allocs[1].ptr)&&p<=alloct); | |
100 | allocp = --p; | |
101 | ASSERT(testbusy(p->ptr)); | |
102 | p->ptr = clearbusy(p->ptr); | |
103 | ASSERT(p->ptr > allocp && p->ptr <= alloct); | |
104 | } | |
105 | \f | |
106 | struct { unsigned tag:4, vtype:4;}; | |
107 | ||
108 | prbusy() | |
109 | { | |
110 | register struct store *p, *q; | |
111 | ||
112 | ASSERT(allocp>allocs && allocp<=alloct); | |
113 | for(p=allocs; ; ) { | |
114 | if(testbusy(p->ptr)) | |
115 | { | |
116 | printf("busy 0%o, tag %d, type %d, length %d\n", | |
117 | p, p[1].tag, p[1].vtype, | |
118 | clearbusy(p->ptr) - (int) p - 2 ); | |
119 | } | |
120 | q = p; | |
121 | p = clearbusy(p->ptr); | |
122 | if(p>q) | |
123 | ASSERT(p<=alloct); | |
124 | else if(q!=alloct || p!=allocs) | |
125 | { | |
126 | write(2,"corrupt arena\n",14); | |
127 | exit(0175); | |
128 | } | |
129 | else return; | |
130 | } | |
131 | } |