1 /* 2 * CDDL HEADER START 3 * 4 * The contents of this file are subject to the terms of the 5 * Common Development and Distribution License, Version 1.0 only 6 * (the "License"). You may not use this file except in compliance 7 * with the License. 8 * 9 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE 10 * or http://www.opensolaris.org/os/licensing. 11 * See the License for the specific language governing permissions 12 * and limitations under the License. 13 * 14 * When distributing Covered Code, include this CDDL HEADER in each 15 * file and include the License file at usr/src/OPENSOLARIS.LICENSE. 16 * If applicable, add the following below this CDDL HEADER, with the 17 * fields enclosed by brackets "[]" replaced with your own identifying 18 * information: Portions Copyright [yyyy] [name of copyright owner] 19 * 20 * CDDL HEADER END 21 */ 22 /* Copyright (c) 1984, 1986, 1987, 1988, 1989 AT&T */ 23 /* All Rights Reserved */ 24 25 26 #ident "%Z%%M% %I% %E% SMI" /* SVr4.0 1.3 */ 27 #ifdef debug 28 #define ASSERT(p) if(!(p))botch("p");else 29 botch(s) 30 char *s; 31 { 32 printf("assertion botched: %s\n",s); 33 abort(); 34 } 35 #else 36 #define ASSERT(p) 37 #endif 38 39 /* C storage allocator 40 * circular first-fit strategy 41 * works with noncontiguous, but monotonically linked, arena 42 * each block is preceded by a ptr to the (pointer of) 43 * the next following block 44 * blocks are exact number of words long 45 * aligned to the data type requirements of ALIGN 46 * pointers to blocks must have BUSY bit 0 47 * bit in ptr is 1 for busy, 0 for idle 48 * gaps in arena are merely noted as busy blocks 49 * last block of arena is empty and 50 * has a pointer to first 51 * idle blocks are coalesced during space search 52 * 53 * a different implementation may need to redefine 54 * ALIGN, NALIGN, BLOCK, BUSY, INT 55 * where INT is integer type to which a pointer can be cast 56 */ 57 #define INT int 58 #define ALIGN int 59 #define NALIGN 1 60 #define WORD sizeof(union store) 61 #define BLOCK 1024 62 #define BUSY 1 63 #define NULL 0 64 #define testbusy(p) ((INT)(p)&BUSY) 65 #define setbusy(p) (union store *)((INT)(p)|BUSY) 66 #define clearbusy(p) (union store *)((INT)(p)&~BUSY) 67 68 union store { 69 union store *ptr; 70 ALIGN dummy[NALIGN]; 71 int calloc; /*calloc clears an array of integers*/ 72 }; 73 74 static union store alloca; /* initial arena */ 75 static union store *allocb = &alloca; /*arena base*/ 76 static union store *allocp = &alloca; /*search ptr*/ 77 static union store *allocx; /*for benefit of realloc*/ 78 extern char *sbrk(); 79 80 char * 81 malloc(nbytes) 82 unsigned nbytes; 83 { 84 register union store *p, *q; 85 register nw; 86 register temp; 87 register union store *r = 0; 88 89 nw = (nbytes+WORD+WORD-1)/WORD + 1; /*need one more than asked for*/ 90 ASSERT(allock(allocp)); 91 for(; ; ) { /* done at most twice */ 92 p = allocp; 93 if(alloca.ptr!=0) /*C can't initialize union*/ 94 for(temp=0; ; ) { 95 if(!testbusy(p->ptr)) { 96 while(!testbusy((q=p->ptr)->ptr)) { 97 ASSERT(q>p); 98 p->ptr = q->ptr; 99 allocp = p; 100 } 101 if(q>=p+nw && p+nw>=p) 102 goto found; 103 r = p; 104 } 105 q = p; 106 p = clearbusy(p->ptr); 107 if(p <= q) { 108 ASSERT(p==allocb); 109 if(p != allocb) 110 return(NULL); 111 if(++temp>1) 112 break; 113 } 114 } 115 temp = nw; 116 p = (union store *)sbrk(0); 117 if (r && !testbusy(r->ptr) && r->ptr + 1 == p) 118 temp -= p - r - 1; 119 temp = ((temp+BLOCK/WORD)/(BLOCK/WORD))*(BLOCK/WORD); 120 if(p+temp <= p) 121 return(NULL); 122 for(; ; ) { 123 q = (union store *)sbrk(temp*WORD); 124 if((INT)q != -1) 125 break; 126 temp -= (temp-nw+1)/2; 127 if(temp <= nw) 128 return(NULL); 129 } 130 ialloc((char *)q, (unsigned)temp*WORD); 131 } 132 found: 133 allocp = p + nw; 134 if(q>allocp) { 135 allocx = allocp->ptr; 136 allocp->ptr = p->ptr; 137 } 138 p->ptr = setbusy(allocp); 139 return((char *)(p+1)); 140 } 141 142 /* freeing strategy tuned for LIFO allocation 143 */ 144 free(ap) 145 char *ap; 146 { 147 register union store *p = (union store *)ap; 148 149 allocp = --p; 150 ASSERT(allock(allocp)); 151 ASSERT(testbusy(p->ptr)); 152 p->ptr = clearbusy(p->ptr); 153 ASSERT(p->ptr > allocp); 154 } 155 156 /* ialloc(q, nbytes) inserts a block that did not come 157 * from malloc into the arena 158 * 159 * q points to new block 160 * r points to last of new block 161 * p points to last cell of arena before new block 162 * s points to first cell of arena after new block 163 */ 164 ialloc(qq, nbytes) 165 char *qq; 166 unsigned nbytes; 167 { 168 register union store *p, *q, *s; 169 union store *r; 170 171 q = (union store *)qq; 172 r = q + (nbytes/WORD) - 1; 173 q->ptr = r; 174 if(alloca.ptr==0) /*C can't initialize union*/ 175 alloca.ptr = &alloca; 176 for(p=allocb; ; p=s) { 177 s = clearbusy(p->ptr); 178 if(s==allocb) 179 break; 180 ASSERT(s>p); 181 if(s>r) { 182 if(p<q) 183 break; 184 else 185 ASSERT(p>r); 186 } 187 } 188 p->ptr = q==p+1? q: setbusy(q); 189 r->ptr = s==r+1? s: setbusy(s); 190 if(allocb > q) 191 allocb = q; 192 allocp = allocb; 193 } 194 195 /* realloc(p, nbytes) reallocates a block obtained from malloc() 196 * and freed since last call of malloc() 197 * to have new size nbytes, and old content 198 * returns new location, or 0 on failure 199 */ 200 201 char * 202 realloc(pp, nbytes) 203 char *pp; 204 unsigned nbytes; 205 { 206 register union store *q; 207 register union store *p = (union store *)pp; 208 union store *s, *t; 209 register unsigned nw; 210 unsigned onw; 211 212 ASSERT(allock(p-1)); 213 if(testbusy(p[-1].ptr)) 214 free((char *)p); 215 onw = p[-1].ptr - p; 216 q = (union store *)malloc(nbytes); 217 if(q==NULL || q==p) 218 return((char *)q); 219 ASSERT(q<p||q>p[-1].ptr); 220 s = p; 221 t = q; 222 nw = (nbytes+WORD-1)/WORD; 223 if(nw<onw) 224 onw = nw; 225 while(onw--!=0) 226 *t++ = *s++; 227 ASSERT(clearbusy(q[-1].ptr)-q==nw); 228 if(q<p && q+nw>=p) 229 (q+(q+nw-p))->ptr = allocx; 230 ASSERT(allock(q-1)); 231 return((char *)q); 232 } 233 234 #ifdef debug 235 allock(q) 236 union store *q; 237 { 238 #ifdef longdebug 239 register union store *p, *r; 240 int x; 241 x = 0; 242 p = allocb; 243 if(alloca.ptr==0) 244 return(1); 245 for( ; (r=clearbusy(p->ptr)) > p; p=r) { 246 if(p==q) 247 x++; 248 } 249 return(r==allocb&(x==1|p==q)); 250 #else 251 return(q>=allocb); 252 #endif 253 } 254 #endif 255 256