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 (the "License"). 6 * You may not use this file except in compliance with the License. 7 * 8 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE 9 * or http://www.opensolaris.org/os/licensing. 10 * See the License for the specific language governing permissions 11 * and limitations under the License. 12 * 13 * When distributing Covered Code, include this CDDL HEADER in each 14 * file and include the License file at usr/src/OPENSOLARIS.LICENSE. 15 * If applicable, add the following below this CDDL HEADER, with the 16 * fields enclosed by brackets "[]" replaced with your own identifying 17 * information: Portions Copyright [yyyy] [name of copyright owner] 18 * 19 * CDDL HEADER END 20 */ 21 22 /* 23 * Copyright 2009 Sun Microsystems, Inc. All rights reserved. 24 * Use is subject to license terms. 25 */ 26 27 /* Copyright (c) 1984, 1986, 1987, 1988, 1989 AT&T */ 28 /* All Rights Reserved */ 29 30 /* 31 * UNIX shell 32 */ 33 34 #include "defs.h" 35 36 37 /* 38 * storage allocator 39 * (circular first fit strategy) 40 */ 41 42 #define BUSY 01 43 #define busy(x) (Rcheat((x)->word) & BUSY) 44 45 unsigned brkincr = BRKINCR; 46 struct blk *blokp; /* current search pointer */ 47 struct blk *bloktop; /* top of arena (last blok) */ 48 49 unsigned char *brkbegin; 50 extern unsigned char *setbrk(); 51 52 #ifdef DEBUG 53 /* 54 * If DEBUG is defined, the following testing will be performed: 55 * - chkbptr() checks the linkage of blocks by following links. 56 * Note that this makes shell really slow. 57 * - fill_pat() fills the memory block with pattern like umem does. 58 * The pattern used to fill the memory area is defined below. 59 */ 60 #define PAT_MAGIC 0xfeedface 61 #define PAT_INIT 0xbaddcafe 62 #define PAT_FREE 0xdeadbeef 63 64 static void fill_pat(struct blk *, uint32_t); 65 static void chkbptr(struct blk *); 66 #endif 67 68 void * 69 alloc(size_t nbytes) 70 { 71 size_t rbytes = round(nbytes + ALIGNSIZ, ALIGNSIZ); 72 73 if (stakbot == 0) { 74 addblok((unsigned int)0); 75 } 76 77 for (;;) { 78 int c = 0; 79 struct blk *p = blokp; 80 struct blk *q; 81 82 do 83 { 84 if (!busy(p)) { 85 while (!busy(q = p->word)) 86 p->word = q->word; 87 if ((char *)q - (char *)p >= rbytes) { 88 blokp = (struct blk *) 89 ((char *)p + rbytes); 90 if (q > blokp) 91 blokp->word = p->word; 92 p->word = (struct blk *) 93 (Rcheat(blokp) | BUSY); 94 #ifdef DEBUG 95 fill_pat(p, PAT_INIT); 96 #endif 97 return ((char *)(p + 1)); 98 } 99 } 100 q = p; 101 p = (struct blk *)(Rcheat(p->word) & ~BUSY); 102 } while (p > q || (c++) == 0); 103 addblok(rbytes); 104 } 105 } 106 107 void 108 addblok(unsigned int reqd) 109 { 110 if (stakbot == 0) { 111 brkbegin = setbrk(3 * BRKINCR); 112 /* 113 * setbrk() returns 8 byte aligned address 114 * but we could need larger align in future 115 */ 116 brkbegin = (unsigned char *)round(brkbegin, ALIGNSIZ); 117 bloktop = (struct blk *)brkbegin; 118 } 119 120 if (stakbas != staktop) { 121 unsigned char *rndstak; 122 struct blk *blokstak; 123 124 if (staktop >= brkend) 125 growstak(staktop); 126 pushstak(0); 127 rndstak = (unsigned char *)round(staktop, ALIGNSIZ); 128 blokstak = (struct blk *)(stakbas) - 1; 129 blokstak->word = stakbsy; 130 stakbsy = blokstak; 131 bloktop->word = (struct blk *)(Rcheat(rndstak) | BUSY); 132 bloktop = (struct blk *)(rndstak); 133 } 134 reqd += brkincr; 135 reqd &= ~(brkincr - 1); 136 blokp = bloktop; 137 /* 138 * brkend points to the first invalid address. 139 * make sure bloktop is valid. 140 */ 141 if ((unsigned char *)&bloktop->word >= brkend) { 142 if (setbrk((unsigned)((unsigned char *) 143 (&bloktop->word) - brkend + sizeof (struct blk))) == 144 (unsigned char *)-1) 145 error(nospace); 146 } 147 bloktop = bloktop->word = (struct blk *)(Rcheat(bloktop) + reqd); 148 if ((unsigned char *)&bloktop->word >= brkend) { 149 if (setbrk((unsigned)((unsigned char *) 150 (&bloktop->word) - brkend + sizeof (struct blk))) == 151 (unsigned char *)-1) 152 error(nospace); 153 } 154 bloktop->word = (struct blk *)(brkbegin + 1); 155 { 156 unsigned char *stakadr = (unsigned char *) 157 (bloktop + 2); 158 unsigned char *sp = stakadr; 159 if (reqd = (staktop-stakbot)) { 160 if (stakadr + reqd >= brkend) 161 growstak(stakadr + reqd); 162 while (reqd-- > 0) 163 *sp++ = *stakbot++; 164 sp--; 165 } 166 staktop = sp; 167 if (staktop >= brkend) 168 growstak(staktop); 169 stakbas = stakbot = stakadr; 170 } 171 } 172 173 void 174 free(ap) 175 void *ap; 176 { 177 struct blk *p; 178 179 if ((p = (struct blk *)ap) && p < bloktop && p > (struct blk *)brkbegin) 180 { 181 #ifdef DEBUG 182 chkbptr(p); 183 #endif 184 --p; 185 p->word = (struct blk *)(Rcheat(p->word) & ~BUSY); 186 #ifdef DEBUG 187 fill_pat(p, PAT_FREE); 188 #endif 189 } 190 191 192 } 193 194 195 #ifdef DEBUG 196 197 static void 198 fill_pat(struct blk *ptr, uint32_t pat) 199 { 200 uint32_t *ui, *eui; 201 202 *(uint32_t *)ptr->pad = PAT_MAGIC; 203 eui = (uint32_t *)(Rcheat(ptr->word) & ~BUSY); 204 for (ui = (uint32_t *)(ptr + 1); ui < eui; ui++) 205 *ui = pat; 206 } 207 208 static void 209 chkbptr(struct blk *ptr) 210 { 211 int exf = 0; 212 struct blk *p = (struct blk *)brkbegin; 213 struct blk *q; 214 int us = 0, un = 0; 215 216 for (;;) { 217 q = (struct blk *)(Rcheat(p->word) & ~BUSY); 218 219 if (p+1 == ptr) 220 exf++; 221 222 if (q < (struct blk *)brkbegin || q > bloktop) 223 abort(); 224 225 if (p == bloktop) 226 break; 227 228 if (busy(p)) 229 us += q - p; 230 else 231 un += q - p; 232 233 if (p >= q) 234 abort(); 235 236 p = q; 237 } 238 if (exf == 0) 239 abort(); 240 } 241 242 static void 243 chkmem() 244 { 245 struct blk *p = (struct blk *)brkbegin; 246 struct blk *q; 247 int us = 0, un = 0; 248 249 for (;;) { 250 q = (struct blk *)(Rcheat(p->word) & ~BUSY); 251 252 if (q < (struct blk *)brkbegin || q > bloktop) 253 abort(); 254 255 if (p == bloktop) 256 break; 257 258 if (busy(p)) 259 us += q - p; 260 else 261 un += q - p; 262 263 if (p >= q) 264 abort(); 265 266 p = q; 267 } 268 269 prs("un/used/avail "); 270 prn(un); 271 blank(); 272 prn(us); 273 blank(); 274 prn((uintptr_t)bloktop - (uintptr_t)brkbegin - (un + us)); 275 newline(); 276 277 } 278 279 #endif 280 281 size_t 282 blklen(q) 283 char *q; 284 { 285 struct blk *pp = (struct blk *)q; 286 struct blk *p; 287 288 --pp; 289 p = (struct blk *)(Rcheat(pp->word) & ~BUSY); 290 291 return ((size_t)((long)p - (long)q)); 292 } 293 294 /* 295 * This is a really hasty hack at putting realloc() in the shell, along 296 * with alloc() and free(). I really hate having to do things like this, 297 * hacking in something before I understand _why_ libcollate does any 298 * memory (re)allocation, let alone feel comfortable with this particular 299 * implementation of realloc, assuming it actually gets used by anything. 300 * 301 * I plan to revist this, for now this is just to get sh to compile so 302 * that xcu4 builds may be done and we get xcu4 on our desktops. 303 * 304 * Eric Brunner, 10/21/94 305 * 306 * Implemented a variation on the suggested fix in Trusted Solaris 2.5, 307 * then forward ported the fix into the mainline shell. 308 * 309 * 3/3/99 310 */ 311 #ifdef __STDC__ 312 void * 313 realloc(pp, nbytes) 314 void *pp; 315 size_t nbytes; 316 #else 317 char * 318 realloc(pp, nbytes) 319 char *pp; 320 size_t nbytes; 321 #endif 322 { 323 char *q; 324 size_t blen; 325 326 if (pp == NULL) 327 return (alloc(nbytes)); 328 if ((nbytes == 0) && (pp != NULL)) 329 free(pp); 330 331 blen = blklen(pp); 332 333 if (blen < nbytes) { /* need to grow */ 334 q = alloc(nbytes); 335 memcpy(q, pp, blen); 336 free(pp); 337 return ((char *)q); 338 } else if (blen == nbytes) { /* do nothing */ 339 return (pp); 340 } else { /* free excess */ 341 q = alloc(nbytes); 342 memcpy(q, pp, nbytes); 343 free(pp); 344 return ((char *)q); 345 } 346 347 #ifdef undef 348 /* 349 * all of what follows is the _idea_ of what is going to be done 350 * getting the size of the block is a problem -- what follows 351 * is _not_ "real", since "sizeof" isn't going to tell me any 352 * thing usefull, probably have to travers the list to the next 353 * blk, then subtract ptr addrs ... and be careful not to leave 354 * holes. 355 */ 356 p = (struct blk *)pp; 357 if (sizeof (p) < nbytes) { /* need to grow */ 358 q = alloc(nbytes); 359 memcpy(q, pp, sizeof (p)); 360 free(pp); 361 return ((char *)q); 362 } else if (sizeof (p) == nbytes) { /* do nothing */ 363 return (pp); 364 } else { /* free excess */ 365 q = alloc(nbytes); 366 memcpy(q, pp, nbytes); 367 free(pp); 368 return ((char *)q); 369 } 370 #endif 371 } 372