util/opt/alloc.c

   1 #ifndef NORCSID
   2 static char rcsid[] = "$Id: alloc.c,v 2.11 1994/06/24 10:39:37 ceriel Exp $";
   3 #endif
   4
   5 #include <stdio.h>
   6 #include "param.h"
   7 #include "types.h"
   8 #include "tes.h"
   9 #include "assert.h"
  10 #include "alloc.h"
  11 #include "line.h"
  12 #include "lookup.h"
  13 #include "proinf.h"
  14
  15 /*
  16  * (c) copyright 1987 by the Vrije Universiteit, Amsterdam, The Netherlands.
  17  * See the copyright notice in the ACK home directory, in the file "Copyright".
  18  *
  19  * Author: Hans van Staveren
  20  */
  21
  22 #ifdef USEMALLOC
  23
  24 short * myalloc();
  25
  26 #define newcore(size) myalloc(size)
  27 #define oldcore(p,size) free(p)
  28
  29 #else
  30
  31 #undef CORECHECK        /* if defined tests are made to insure
  32                            each block occurs at most once */
  33
  34 #define CCHUNK  1024    /* number of shorts asked from system */
  35
  36 short *newcore(),*freshcore();
  37 extern char *sbrk();
  38
  39 #ifdef COREDEBUG
  40 int shortsasked=0;
  41 #endif
  42
  43 #endif
  44
  45 /*
  46  * The following two sizetables contain the sizes of the various kinds
  47  * of line and argument structures.
  48  * Care has been taken to make this table implementation independent,
  49  * but if you think very hard you might find a compiler failing the
  50  * assumptions made.
  51  * A wasteful but safe approach is to replace every line of them by
  52  *  sizeof(line_t)
  53  * and
  54  *  sizeof(arg_t)
  55  * respectively.
  56  */
  57
  58 #define LBASE (sizeof(line_t)-sizeof(un_l_a))
  59
  60 int lsizetab[] = {
  61         LBASE,
  62         LBASE+sizeof(short),
  63         LBASE+sizeof(offset),
  64         LBASE+sizeof(num_p),
  65         LBASE+sizeof(sym_p),
  66         LBASE+sizeof(s_la_sval),
  67         LBASE+sizeof(s_la_lval),
  68         LBASE+sizeof(arg_p),
  69         LBASE
  70 };
  71
  72 #define ABASE (sizeof(arg_t)-sizeof(un_a_a))
  73
  74 int asizetab[] = {
  75         ABASE+sizeof(offset),
  76         ABASE+sizeof(num_p),
  77         ABASE+sizeof(sym_p),
  78         ABASE+sizeof(s_a_val),
  79         ABASE+sizeof(argb_t),
  80         ABASE+sizeof(s_a_con),
  81         ABASE+sizeof(s_a_con),
  82         ABASE+sizeof(s_a_con),
  83 };
  84
  85 /*
  86  * alloc routines:
  87  * Two parts:
  88  *   1) typed alloc and free routines
  89  *   2) untyped raw core allocation
  90  */
  91
  92 /*
  93  * PART 1
  94  */
  95
  96 line_p  newline(optyp) int optyp; {
  97         register line_p lnp;
  98         register kind=optyp;
  99
 100         if (kind>OPMINI)
 101                 kind = OPMINI;
 102         lnp = (line_p) newcore(lsizetab[kind]);
 103         lnp->l_optyp = optyp;
 104         return(lnp);
 105 }
 106
 107 oldline(lnp) register line_p lnp; {
 108         register kind=lnp->l_optyp&BMASK;
 109
 110         if (kind>OPMINI)
 111                 kind = OPMINI;
 112         if (kind == OPLIST)
 113                 oldargs(lnp->l_a.la_arg);
 114         oldcore((short *) lnp,lsizetab[kind]);
 115 }
 116
 117 arg_p newarg(kind) int kind; {
 118         register arg_p ap;
 119
 120         ap = (arg_p) newcore(asizetab[kind]);
 121         ap->a_typ = kind;
 122         return(ap);
 123 }
 124
 125 oldargs(ap) register arg_p ap; {
 126         register arg_p  next;
 127
 128         while (ap != (arg_p) 0) {
 129                 next = ap->a_next;
 130                 switch(ap->a_typ) {
 131                 case ARGSTR:
 132                         oldargb(ap->a_a.a_string.ab_next);
 133                         break;
 134                 case ARGICN:
 135                 case ARGUCN:
 136                 case ARGFCN:
 137                         oldargb(ap->a_a.a_con.ac_con.ab_next);
 138                         break;
 139                 }
 140                 oldcore((short *) ap,asizetab[ap->a_typ]);
 141                 ap = next;
 142         }
 143 }
 144
 145 oldargb(abp) register argb_p abp; {
 146         register argb_p next;
 147
 148         while (abp != (argb_p) 0) {
 149                 next = abp->ab_next;
 150                 oldcore((short *) abp,sizeof (argb_t));
 151                 abp = next;
 152         }
 153 }
 154
 155 reg_p newreg() {
 156
 157         return((reg_p) newcore(sizeof(reg_t)));
 158 }
 159
 160 oldreg(rp) reg_p rp; {
 161
 162         oldcore((short *) rp,sizeof(reg_t));
 163 }
 164
 165 num_p newnum() {
 166
 167         return((num_p) newcore(sizeof(num_t)));
 168 }
 169
 170 oldnum(lp) num_p lp; {
 171
 172         oldcore((short *) lp,sizeof(num_t));
 173 }
 174
 175 offset *newrom() {
 176
 177         return((offset *) newcore(MAXROM*sizeof(offset)));
 178 }
 179
 180 sym_p newsym(len) int len; {
 181         /*
 182          * sym_t includes a 2 character s_name at the end
 183          * extend this structure with len-2 characters
 184          */
 185         return((sym_p) newcore(sizeof(sym_t) - 2 + len));
 186 }
 187
 188 argb_p newargb() {
 189
 190         return((argb_p) newcore(sizeof(argb_t)));
 191 }
 192
 193 #ifndef USEMALLOC
 194
 195 /******************************************************************/
 196 /******   Start of raw core management package    *****************/
 197 /******************************************************************/
 198
 199 #define MAXSHORT 30     /* Maximum number of shorts one can ask for */
 200
 201 short *freelist[MAXSHORT];
 202
 203 typedef struct coreblock {
 204         struct coreblock *co_next;
 205         short co_size;
 206 } core_t,*core_p;
 207
 208 #define SINC    (sizeof(core_t)/sizeof(short))
 209 #ifdef COREDEBUG
 210 coreverbose() {
 211         register size;
 212         register short *p;
 213         register sum;
 214
 215         sum = 0;
 216         for(size=1;size<MAXSHORT;size++)
 217                 for (p=freelist[size];p!=0;p = *(short **) p)
 218                         sum += size;
 219         fprintf(stderr,"Used core %u\n",(shortsasked-sum)*sizeof(short));
 220 }
 221 #endif
 222
 223 #ifdef SEPID
 224
 225 compactcore() {
 226         register core_p corelist=0,tp,cl;
 227         int size;
 228
 229 #ifdef COREDEBUG
 230         fprintf(stderr,"Almost out of core\n");
 231 #endif
 232         for(size=SINC;size<MAXSHORT;size++) {
 233                 while ((tp = (core_p) freelist[size]) != (core_p) 0) {
 234                         freelist[size] = (short *) tp->co_next;
 235                         tp->co_size = size;
 236                         if (corelist==0 || tp<corelist) {
 237                                 tp->co_next = corelist;
 238                                 corelist = tp;
 239                         } else {
 240                                 for(cl=corelist;cl->co_next != 0 && tp>cl->co_next;
 241                                                         cl = cl->co_next)
 242                                         ;
 243                                 tp->co_next = cl->co_next;
 244                                 cl->co_next = tp;
 245                         }
 246                 }
 247         }
 248         while (corelist != 0) {
 249                 while ((short *) corelist->co_next ==
 250                     (short *) corelist + corelist->co_size) {
 251                         corelist->co_size += corelist->co_next->co_size;
 252                         corelist->co_next =  corelist->co_next->co_next;
 253                 }
 254                 assert(corelist->co_next==0 ||
 255                         (short *) corelist->co_next >
 256                             (short *) corelist + corelist->co_size);
 257                 while (corelist->co_size >= MAXSHORT+SINC) {
 258                         oldcore((short *) corelist + corelist->co_size-(MAXSHORT-1),
 259                                 sizeof(short)*(MAXSHORT-1));
 260                         corelist->co_size -= MAXSHORT;
 261                 }
 262                 if (corelist->co_size >= MAXSHORT) {
 263                         oldcore((short *) corelist + corelist->co_size-SINC,
 264                                 sizeof(short)*SINC);
 265                         corelist->co_size -= SINC;
 266                 }
 267                 cl = corelist->co_next;
 268                 oldcore((short *) corelist, sizeof(short)*corelist->co_size);
 269                 corelist = cl;
 270         }
 271 }
 272
 273 short *grabcore(size) int size; {
 274         register short *p;
 275         register trysize;
 276
 277         /*
 278          * Desperate situation, can't get more core from system.
 279          * Postpone giving up just a little bit by splitting up
 280          * larger free blocks if possible.
 281          * Algorithm is worst fit.
 282          */
 283
 284         assert(size<2*MAXSHORT);
 285         for(trysize=2*MAXSHORT-2; trysize>size; trysize -= 2) {
 286                 p = freelist[trysize/sizeof(short)];
 287                 if ( p != (short *) 0) {
 288                         freelist[trysize/sizeof(short)] = *(short **) p;
 289                         oldcore(p+size/sizeof(short),trysize-size);
 290                         return(p);
 291                 }
 292         }
 293
 294         /*
 295          * Can't get more core from the biggies, try to combine the
 296          * little ones. This is expensive but probably better than
 297          * giving up.
 298          */
 299
 300         compactcore();
 301         if ((p=freelist[size/sizeof(short)]) != 0) {
 302                 freelist[size/sizeof(short)] = * (short **) p;
 303                 return(p);
 304         }
 305         for(trysize=2*MAXSHORT-2; trysize>size; trysize -= 2) {
 306                 p = freelist[trysize/sizeof(short)];
 307                 if ( p != (short *) 0) {
 308                         freelist[trysize/sizeof(short)] = *(short **) p;
 309                         oldcore(p+size/sizeof(short),trysize-size);
 310                         return(p);
 311                 }
 312         }
 313
 314         /*
 315          * That's it then. Finished.
 316          */
 317
 318         return(0);
 319 }
 320 #endif  /* SEPID */
 321
 322 short *newcore(size) int size; {
 323         register short *p,*q;
 324
 325         size = (size + sizeof(int) - 1) & ~(sizeof(int) - 1);
 326         if( size < 2*MAXSHORT ) {
 327                 if ((p=freelist[size/sizeof(short)]) != (short *) 0)
 328                         freelist[size/sizeof(short)] = *(short **) p;
 329                 else {
 330                         p = freshcore(size);
 331 #ifdef SEPID
 332                         if (p == (short *) 0)
 333                                 p = grabcore(size);
 334 #endif
 335                 }
 336         } else
 337                 p = freshcore(size);
 338         if (p == 0)
 339                 error("out of memory");
 340         for (q=p; size > 0 ; size -= sizeof(short))
 341                 *q++ = 0;
 342         return(p);
 343 }
 344
 345 #ifndef USEMALLOC
 346
 347 /*
 348  * stdio uses malloc and free.
 349  * you can use these as substitutes
 350  */
 351
 352 char *malloc(size) int size; {
 353
 354         /*
 355          * malloc(III) is called by stdio,
 356          * this routine is a substitute.
 357          */
 358
 359         return( (char *) newcore(size));
 360 }
 361
 362 free() {
 363
 364 }
 365 #endif
 366
 367 oldcore(p,size) short *p; int size; {
 368 #ifdef CORECHECK
 369         register short *cp;
 370 #endif
 371
 372         assert(size<2*MAXSHORT);
 373 #ifdef CORECHECK
 374         for (cp=freelist[size/sizeof(short)]; cp != (short *) 0;
 375             cp = *(short **) cp)
 376                 assert(cp != p);
 377 #endif
 378         *(short **) p = freelist[size/sizeof(short)];
 379         freelist[size/sizeof(short)] = p;
 380 }
 381
 382 short *ccur,*cend;
 383
 384 coreinit(p1,p2) short *p1,*p2; {
 385
 386         /*
 387          * coreinit is called with the boundaries of a piece of
 388          * memory that can be used for starters.
 389          */
 390
 391         ccur = p1;
 392         cend = p2;
 393 }
 394
 395 short *freshcore(size) int size; {
 396         register short *temp;
 397         static int cchunk=CCHUNK;
 398
 399         while(&ccur[size/sizeof(short)] >= cend && cchunk>0) {
 400                 do {
 401                         temp = (short *) sbrk(cchunk*sizeof(short));
 402                         if (temp == (short *) -1)
 403                                 cchunk >>= 1;
 404                         else if (temp != cend)
 405                                 ccur = cend = temp;
 406                 } while (temp == (short *) -1 && cchunk>0);
 407                 cend += cchunk;
 408 #ifdef COREDEBUG
 409                 shortsasked += cchunk;
 410 #endif
 411         }
 412         if (cchunk==0)
 413                 return(0);
 414         temp = ccur;
 415         ccur = &ccur[size/sizeof(short)];
 416         return(temp);
 417 }
 418
 419 #else   /* USEMALLOC */
 420
 421 coreinit() {
 422
 423         /*
 424          * Empty function, no initialization needed
 425          */
 426 }
 427
 428 short *myalloc(size) register size; {
 429         register short *p,*q;
 430         extern char *malloc();
 431
 432         p = (short *)malloc(size);
 433         if (p == 0)
 434                 error("out of memory");
 435         for(q=p;size>0;size -= sizeof(short))
 436                 *q++ = 0;
 437         return(p);
 438 }
 439 #endif