util/led/memory.c

   1 /*
   2  * (c) copyright 1987 by the Vrije Universiteit, Amsterdam, The Netherlands.
   3  * See the copyright notice in the ACK home directory, in the file "Copyright".
   4  */
   5 #ifndef lint
   6 static char rcsid[] = "$Id: memory.c,v 3.20 1994/06/24 10:34:53 ceriel Exp $";
   7 #endif
   8
   9 /*
  10  * Memory manager. Memory is divided into NMEMS pieces. There is a struct
  11  * for each piece telling where it is, how many bytes are used, and how may
  12  * are left. If a request for core doesn't fit in the left bytes, an sbrk()
  13  * is done and pieces after the one that requested the growth are moved up.
  14  *
  15  * Unfortunately, we cannot use sbrk to request more memory, because its
  16  * result cannot be trusted. More specifically, it does not work properly
  17  * on 2.9 BSD, and probably does not work properly on 2.8 BSD and V7 either.
  18  * The problem is that "sbrk" adds the increment to the current "break"
  19  * WITHOUT testing the carry bit. So, if your break is at 40000, and
  20  * you "sbrk(30000)", it will succeed, but your break will be at 4464
  21  * (70000 - 65536).
  22  */
  23
  24 #include <stdio.h>
  25 #include <out.h>
  26 #include "const.h"
  27 #include "assert.h"
  28 #include "debug.h"
  29 #include "memory.h"
  30
  31 static          copy_down();
  32 static          copy_up();
  33 static          free_saved_moduls();
  34
  35 struct memory   mems[NMEMS];
  36
  37 bool    incore = TRUE;  /* TRUE while everything can be kept in core. */
  38 ind_t   core_position = (ind_t)0;       /* Index of current module. */
  39
  40 #define GRANULE         64      /* power of 2 */
  41
  42 static char *BASE;
  43 static ind_t refused;
  44
  45 sbreak(incr)
  46         ind_t incr;
  47 {
  48         unsigned int    inc;
  49
  50         incr = (incr + (GRANULE - 1)) & ~(GRANULE - 1);
  51
  52         inc = incr;
  53         if ((refused && refused < incr) ||
  54             (sizeof(char *) < sizeof(long) &&
  55              (inc != incr || BASE + inc < BASE)) ||
  56             brk(BASE + incr) == -1) {
  57                 if (!refused || refused > incr)
  58                         refused = incr;
  59                 return -1;
  60         }
  61         BASE += incr;
  62         return 0;
  63 }
  64
  65 /*
  66  * Initialize some pieces of core. We hope that this will be our last
  67  * real allocation, meaning we've made the right choices.
  68  */
  69 init_core()
  70 {
  71         register char           *base;
  72         register ind_t          total_size;
  73         register struct memory  *mem;
  74         extern char             *sbrk();
  75
  76 #include "mach.c"
  77 #define ALIGN 8                 /* minimum alignment for pieces */
  78 #define AT_LEAST        (ind_t)2*ALIGN  /* See comment about string areas. */
  79
  80         total_size = (ind_t)0;  /* Will accumulate the sizes. */
  81         BASE = base = sbrk(0);          /* First free. */
  82         if ((int)base % ALIGN) {
  83                 base  = sbrk(ALIGN - (int)base % ALIGN);
  84                 BASE = base = sbrk(0);
  85         }
  86         /*
  87          * String areas are special-cased. The first byte is unused as a way to
  88          * distinguish a name without string from a name which has the first
  89          * string in the string area.
  90          */
  91         for (mem = mems; mem < &mems[NMEMS]; mem++) {
  92                 mem->mem_base = base;
  93                 mem->mem_full = (ind_t)0;
  94                 if (mem == &mems[ALLOLCHR] || mem == &mems[ALLOGCHR]) {
  95                         if (mem->mem_left == 0) {
  96                                 mem->mem_left = ALIGN;
  97                                 total_size += ALIGN;
  98                                 base += ALIGN;
  99                         }
 100                         base += mem->mem_left;
 101                         total_size += mem->mem_left;
 102                         mem->mem_left--;
 103                         mem->mem_full++;
 104                 }
 105                 else {
 106                         base += mem->mem_left;  /* Each piece will start after prev. */
 107                         total_size += mem->mem_left;
 108                 }
 109         }
 110
 111         if (sbreak(total_size) == -1) {
 112                 incore = FALSE; /* In core strategy failed. */
 113                 if (sbreak(AT_LEAST) == -1)
 114                         fatal("no core at all");
 115
 116                 base = BASE;
 117                 for (mem = mems; mem < &mems[NMEMS]; mem++) {
 118                         mem->mem_base = base;
 119                         if (mem == &mems[ALLOLCHR] || mem == &mems[ALLOGCHR]) {
 120                                 base += ALIGN;
 121                                 mem->mem_left = ALIGN - 1;
 122                                 mem->mem_full = 1;
 123                         }
 124                         else {
 125                                 mem->mem_full = (ind_t)0;
 126                                 mem->mem_left = 0;
 127                         }
 128                 }
 129         }
 130 }
 131
 132 /*
 133  * Allocate an extra block of `incr' bytes and move all pieces with index
 134  * higher than `piece' up with the size of the block.
 135  * Move up as much as possible, if "incr" fails.
 136  */
 137 static ind_t
 138 move_up(piece, incr)
 139         register int            piece;
 140         register ind_t          incr;
 141 {
 142         register struct memory  *mem;
 143 #ifndef NOSTATISTICS
 144         extern int statistics;
 145 #endif
 146
 147         debug("move_up(%d, %d)\n", piece, (int)incr, 0, 0);
 148         while (incr > 0 && sbreak(incr) == -1)
 149                 incr -= INCRSIZE;
 150
 151         if (incr <= 0) {
 152                 incr = 0;
 153                 return (ind_t) 0;
 154         }
 155 #ifndef NOSTATISTICS
 156         if (statistics) fprintf(stderr,"moving up %lx\n", (long) incr);
 157 #endif
 158         for (mem = &mems[NMEMS - 1]; mem > &mems[piece]; mem--)
 159                 copy_up(mem, incr);
 160
 161         mems[piece].mem_left += incr;
 162         return incr;
 163 }
 164
 165 extern int      passnumber;
 166
 167 /*
 168  * This routine is called if `piece' needs `incr' bytes and the system won't
 169  * give them. We first steal the free bytes of all lower pieces and move them
 170  * and `piece' down. If that doesn't give us enough bytes, we steal the free
 171  * bytes of all higher pieces and move them up. We return whether we have
 172  * enough bytes, the first or the second time.
 173  */
 174 static bool
 175 compact(piece, incr, flag)
 176         register int            piece;
 177         register ind_t          incr;
 178 #define NORMAL 0
 179 #define FREEZE 1
 180 #define FORCED 2
 181 {
 182         register ind_t          gain, size;
 183         register struct memory  *mem;
 184         int min = piece, max = piece;
 185 #define SHIFT_COUNT 2           /* let pieces only contribute if their free
 186                                    memory is more than 1/2**SHIFT_COUNT * 100 %
 187                                    of its occupied memory
 188                                 */
 189
 190         debug("compact(%d, %d, %d)\n", piece, (int)incr, flag, 0);
 191         for (mem = &mems[0]; mem < &mems[NMEMS - 1]; mem++) {
 192                 assert(mem->mem_base + mem->mem_full + mem->mem_left == (mem+1)->mem_base);
 193         }
 194
 195         mem = &mems[piece];
 196         if (flag == NORMAL) {
 197                 /* try and gain a bit more than needed */
 198                 gain = (mem->mem_full + incr) >> SHIFT_COUNT;
 199                 if (incr < gain) incr = gain;
 200         }
 201
 202         /*
 203          * First, check that moving will result in enough space
 204          */
 205         if (flag != FREEZE) {
 206                 gain = mem->mem_left;
 207                 for (mem = &mems[piece-1]; mem >= &mems[0]; mem--) {
 208                         /*
 209                          * Don't give it all away!
 210                          * If this does not give us enough, bad luck
 211                          */
 212                         if (flag == FORCED)
 213                                 size = 0;
 214                         else {
 215                                 size = mem->mem_full >> SHIFT_COUNT;
 216                                 if (size == 0) size = mem->mem_left >> 1;
 217                         }
 218                         if (mem->mem_left >= size)
 219                                 gain += (mem->mem_left - size) & ~(ALIGN - 1);
 220                         if (gain >= incr) {
 221                                 min = mem - &mems[0];
 222                                 break;
 223                         }
 224                 }
 225                 if (min == piece)
 226                     for (mem = &mems[piece+1]; mem <= &mems[NMEMS - 1]; mem++) {
 227                         /*
 228                          * Don't give it all away!
 229                          * If this does not give us enough, bad luck
 230                          */
 231                         if (flag == FORCED)
 232                                 size = 0;
 233                         else {
 234                                 size = mem->mem_full >> SHIFT_COUNT;
 235                                 if (size == 0) size = mem->mem_left >> 1;
 236                         }
 237                         if (mem->mem_left >= size)
 238                                 gain += (mem->mem_left - size) & ~(ALIGN - 1);
 239                         if (gain >= incr) {
 240                                 max = mem - &mems[0];
 241                                 break;
 242                         }
 243                 }
 244                 if (min == piece) {
 245                         min = 0;
 246                         if (max == piece) max = 0;
 247                 }
 248                 if (gain < incr) return 0;
 249         }
 250         else {
 251                 min = 0;
 252                 max = NMEMS - 1;
 253         }
 254
 255         gain = 0;
 256         for (mem = &mems[min]; mem != &mems[piece]; mem++) {
 257                 /* Here memory is inserted before a piece. */
 258                 assert(passnumber == FIRST || gain == (ind_t)0);
 259                 if (gain) copy_down(mem, gain);
 260                 if (flag == FREEZE || gain < incr) {
 261                         if (flag != NORMAL) size = 0;
 262                         else {
 263                                 size = mem->mem_full >> SHIFT_COUNT;
 264                                 if (size == 0) size = mem->mem_left >> 1;
 265                         }
 266                         if (mem->mem_left >= size) {
 267                                 size = (mem->mem_left - size) & ~(ALIGN - 1);
 268                                 gain += size;
 269                                 mem->mem_left -= size;
 270                         }
 271                 }
 272         }
 273         /*
 274          * Now mems[piece]:
 275          */
 276         if (gain) copy_down(mem, gain);
 277         gain += mem->mem_left;
 278         mem->mem_left = 0;
 279
 280         if (gain < incr) {
 281                 register ind_t  up = (ind_t)0;
 282
 283                 for (mem = &mems[max]; mem > &mems[piece]; mem--) {
 284                         /* Here memory is appended after a piece. */
 285                         if (flag == FREEZE || gain + up < incr) {
 286                                 if (flag != NORMAL) size = 0;
 287                                 else {
 288                                         size = mem->mem_full >> SHIFT_COUNT;
 289                                         if (size == 0) size = mem->mem_left >> 1;
 290                                 }
 291                                 if (mem->mem_left >= size) {
 292                                         size = (mem->mem_left - size) & ~(ALIGN - 1);
 293                                         up += size;
 294                                         mem->mem_left -= size;
 295                                 }
 296                         }
 297                         if (up) copy_up(mem, up);
 298                 }
 299                 gain += up;
 300         }
 301         mems[piece].mem_left += gain;
 302         assert(flag == FREEZE || gain >= incr);
 303         for (mem = &mems[0]; mem < &mems[NMEMS - 1]; mem++) {
 304                 assert(mem->mem_base + mem->mem_full + mem->mem_left == (mem+1)->mem_base);
 305         }
 306         return gain >= incr;
 307 }
 308
 309 /*
 310  * The bytes of `mem' must be moved `dist' down in the address space.
 311  * We copy the bytes from low to high, because the tail of the new area may
 312  * overlap with the old area, but we do not want to overwrite them before they
 313  * are copied.
 314  */
 315 static
 316 copy_down(mem, dist)
 317         register struct memory  *mem;
 318         ind_t                   dist;
 319 {
 320         register char           *old;
 321         register char           *new;
 322         register ind_t          size;
 323
 324         size = mem->mem_full;
 325         old = mem->mem_base;
 326         new = old - dist;
 327         mem->mem_base = new;
 328         while (size--)
 329                 *new++ = *old++;
 330 }
 331
 332 /*
 333  * The bytes of `mem' must be moved `dist' up in the address space.
 334  * We copy the bytes from high to low, because the tail of the new area may
 335  * overlap with the old area, but we do not want to overwrite them before they
 336  * are copied.
 337  */
 338 static
 339 copy_up(mem, dist)
 340         register struct memory  *mem;
 341         ind_t                   dist;
 342 {
 343         register char           *old;
 344         register char           *new;
 345         register ind_t          size;
 346
 347         size = mem->mem_full;
 348         old = mem->mem_base + size;
 349         new = old + dist;
 350         while (size--)
 351                 *--new = *--old;
 352         mem->mem_base = new;
 353 }
 354
 355 static int alloctype = NORMAL;
 356
 357 /*
 358  * Add `size' bytes to the bytes already allocated for `piece'. If it has no
 359  * free bytes left, ask them from memory or, if that fails, from the free
 360  * bytes of other pieces. The offset of the new area is returned. No matter
 361  * how many times the area is moved, because of another allocate, this offset
 362  * remains valid.
 363  */
 364 ind_t
 365 alloc(piece, size)
 366         int                     piece;
 367         register long           size;
 368 {
 369         register ind_t          incr = 0;
 370         ind_t                   left = mems[piece].mem_left;
 371         register ind_t          full = mems[piece].mem_full;
 372
 373         assert(passnumber == FIRST || (!incore && piece == ALLOMODL));
 374         if (size == (long)0)
 375                 return full;
 376         if (size != (ind_t)size)
 377                 return BADOFF;
 378         switch(piece) {
 379         case ALLOMODL:
 380         case ALLORANL:
 381                 size = int_align(size);
 382         }
 383
 384         if (size - left > 0)
 385                 incr = ((size - left + (INCRSIZE - 1)) / INCRSIZE) * INCRSIZE;
 386
 387         if (incr == 0 ||
 388             (incr < left + full && (incr -= move_up(piece, left + full)) <= 0) ||
 389             move_up(piece, incr) == incr ||
 390             compact(piece, size, alloctype)) {
 391                 mems[piece].mem_full += size;
 392                 mems[piece].mem_left -= size;
 393                 return full;
 394         } else {
 395                 incore = FALSE;
 396                 return BADOFF;
 397         }
 398 }
 399
 400 /*
 401  * Same as alloc() but for a piece which really needs it. If the first
 402  * attempt fails, release the space occupied by other pieces and try again.
 403  */
 404 ind_t
 405 hard_alloc(piece, size)
 406         register int    piece;
 407         register long   size;
 408 {
 409         register ind_t  ret;
 410         register int    i;
 411
 412         if (size != (ind_t)size)
 413                 return BADOFF;
 414         if ((ret = alloc(piece, size)) != BADOFF) {
 415                 return ret;
 416         }
 417
 418         /*
 419          * Deallocate what we don't need.
 420          */
 421         for (i = 0; i < NMEMS; i++) {
 422                 switch (i) {
 423                 case ALLOGLOB:
 424                 case ALLOGCHR:
 425                 case ALLOSYMB:
 426                 case ALLOARCH:
 427                 case ALLOMODL:
 428                 case ALLORANL:
 429                         break;  /* Do not try to deallocate this. */
 430                 default:
 431                         dealloc(i);
 432                         break;
 433                 }
 434         }
 435         free_saved_moduls();
 436
 437         if ((ret = alloc(piece, size)) != BADOFF) {
 438                 return ret;
 439         }
 440
 441         alloctype = FORCED;
 442         ret = alloc(piece, size);
 443         alloctype = NORMAL;
 444         return ret;
 445 }
 446
 447 /*
 448  * We don't need the previous modules, so we put the current module
 449  * at the start of the piece allocated for module contents, thereby
 450  * overwriting the saved modules, and release its space.
 451  */
 452 static
 453 free_saved_moduls()
 454 {
 455         register ind_t          size;
 456         register char           *old, *new;
 457         register struct memory  *mem = &mems[ALLOMODL];
 458
 459         size = mem->mem_full - core_position;
 460         new = mem->mem_base;
 461         old = new + core_position;
 462         while (size--)
 463                 *new++ = *old++;
 464         mem->mem_full -= core_position;
 465         mem->mem_left += core_position;
 466         core_position = (ind_t)0;
 467 }
 468
 469 /*
 470  * The piece of memory with index `piece' is no longer needed.
 471  * We take care that it can be used by compact() later, if needed.
 472  */
 473 dealloc(piece)
 474         register int            piece;
 475 {
 476         /*
 477          * Some pieces need their memory throughout the program.
 478          */
 479         assert(piece != ALLOGLOB);
 480         assert(piece != ALLOGCHR);
 481         assert(piece != ALLOSYMB);
 482         assert(piece != ALLOARCH);
 483         mems[piece].mem_left += mems[piece].mem_full;
 484         mems[piece].mem_full = (ind_t)0;
 485 }
 486
 487 char *
 488 core_alloc(piece, size)
 489         register int    piece;
 490         register long   size;
 491 {
 492         register ind_t  off;
 493
 494         if ((off = alloc(piece, size)) == BADOFF)
 495                 return (char *)0;
 496         return address(piece, off);
 497 }
 498
 499 core_free(piece, p)
 500         int     piece;
 501         char    *p;
 502 {
 503         char    *q = address(piece, mems[piece].mem_full);
 504
 505         assert(p < q);
 506         switch(sizeof(unsigned) == sizeof(char *)) {
 507         case 1:
 508                 mems[piece].mem_full -= (unsigned) (q - p);
 509                 mems[piece].mem_left += (unsigned) (q - p);
 510                 break;
 511         default:
 512                 mems[piece].mem_full -= (ind_t) q - (ind_t) p;
 513                 mems[piece].mem_left += (ind_t) q - (ind_t) p;
 514                 break;
 515         }
 516 }
 517
 518 /*
 519  * Reset index into piece of memory for modules and
 520  * take care that the allocated pieces will not be moved.
 521  */
 522 freeze_core()
 523 {
 524         register int    i;
 525
 526         core_position = (ind_t)0;
 527
 528         if (incore)
 529                 return;
 530
 531         for (i = 0; i < NMEMS; i++) {
 532                 switch (i) {
 533                 case ALLOGLOB:
 534                 case ALLOGCHR:
 535                 case ALLOSYMB:
 536                 case ALLOARCH:
 537                         break;  /* Do not try to deallocate this. */
 538                 default:
 539                         dealloc(i);
 540                         break;
 541                 }
 542         }
 543         compact(NMEMS - 1, (ind_t)0, FREEZE);
 544 }
 545
 546 /* ------------------------------------------------------------------------- */
 547
 548 /*
 549  * To transform the various pieces of the output in core to the file format,
 550  * we must order the bytes in the unsigned shorts and longs as ACK prescribes.
 551  */
 552 write_bytes()
 553 {
 554         unsigned short          nsect;
 555         long                    offchar;
 556         register struct memory  *mem;
 557         extern unsigned short   NLocals, NGlobals;
 558         extern long             NLChars, NGChars;
 559         extern int              flagword;
 560         extern struct outhead   outhead;
 561         extern struct outsect   outsect[];
 562         extern char             *outputname;
 563         int                     sectionno = 0;
 564
 565         nsect = outhead.oh_nsect;
 566         offchar = OFF_CHAR(outhead);
 567
 568         /*
 569          * We allocated two areas: one for local and one for global names.
 570          * Also, we used another kind of on_foff than on file.
 571          * At the end of the global area we have put the section names.
 572          */
 573         if (!(flagword & SFLAG)) {
 574                 do_crs((struct outname *)mems[ALLOLOCL].mem_base, NLocals);
 575                 namecpy((struct outname *)mems[ALLOLOCL].mem_base,
 576                         NLocals,
 577                         offchar
 578                 );
 579                 namecpy((struct outname *)mems[ALLOGLOB].mem_base,
 580                         NGlobals + nsect,
 581                         offchar + NLChars
 582                 );
 583         }
 584         /*
 585          * These pieces must always be written.
 586          */
 587         wr_ohead(&outhead);
 588         wr_sect(outsect, nsect);
 589         for (mem = &mems[ALLOEMIT]; mem < &mems[ALLORELO]; mem++)
 590                 wrt_emit(mem->mem_base, sectionno++, mem->mem_full);
 591         /*
 592          * The rest depends on the flags.
 593          */
 594         if (flagword & (RFLAG|CFLAG))
 595                 wr_relo((struct outrelo *) mems[ALLORELO].mem_base,
 596                         outhead.oh_nrelo);
 597         if (!(flagword & SFLAG)) {
 598                 wr_name((struct outname *) mems[ALLOLOCL].mem_base,
 599                         NLocals);
 600                 wr_name((struct outname *) mems[ALLOGLOB].mem_base,
 601                         NGlobals+nsect);
 602                 wr_string(mems[ALLOLCHR].mem_base + 1, (long)NLChars);
 603                 wr_string(mems[ALLOGCHR].mem_base + 1, (long)NGChars);
 604 #ifdef SYMDBUG
 605                 wr_dbug(mems[ALLODBUG].mem_base, mems[ALLODBUG].mem_full);
 606 #endif /* SYMDBUG */
 607         }
 608 }
 609
 610 namecpy(name, nname, offchar)
 611         register struct outname *name;
 612         register unsigned       nname;
 613         register long           offchar;
 614 {
 615         while (nname--) {
 616                 if (name->on_foff)
 617                         name->on_foff += offchar - 1;
 618                 name++;
 619         }
 620 }