123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594 |
- /*
- * (c) copyright 1987 by the Vrije Universiteit, Amsterdam, The Netherlands.
- * See the copyright notice in the ACK home directory, in the file "Copyright".
- */
- /*
- * Memory manager. Memory is divided into NMEMS pieces. There is a struct
- * for each piece telling where it is, how many bytes are used, and how may
- * are left. If a request for core doesn't fit in the left bytes, an sbrk()
- * is done and pieces after the one that requested the growth are moved up.
- *
- * Unfortunately, we cannot use sbrk to request more memory, because its
- * result cannot be trusted. More specifically, it does not work properly
- * on 2.9 BSD, and probably does not work properly on 2.8 BSD and V7 either.
- * The problem is that "sbrk" adds the increment to the current "break"
- * WITHOUT testing the carry bit. So, if your break is at 40000, and
- * you "sbrk(30000)", it will succeed, but your break will be at 4464
- * (70000 - 65536).
- */
- #include <stdio.h>
- #include <unistd.h>
- #include <out.h>
- #include "const.h"
- #include "assert.h"
- #include "debug.h"
- #include "arch.h"
- #include "memory.h"
- #include "defs.h"
- #include "object.h"
- #include <missing_proto.h>
- static ind_t move_up(int piece, ind_t incr);
- static bool compact(int piece, ind_t incr, int flag);
- static void copy_down(struct memory *mem, ind_t dist);
- static void copy_up(struct memory *mem, ind_t dist);
- static void free_saved_moduls();
- struct memory mems[NMEMS];
- bool incore = TRUE; /* TRUE while everything can be kept in core. */
- ind_t core_position = (ind_t)0; /* Index of current module. */
- #define GRANULE 64 /* power of 2 */
- static char *BASE;
- static ind_t refused;
- int sbreak(ind_t incr)
- {
- unsigned int inc;
- incr = (incr + (GRANULE - 1)) & ~(GRANULE - 1);
- inc = incr;
- if ((refused && refused < incr) ||
- (sizeof(char *) < sizeof(long) &&
- (inc != incr || BASE + inc < BASE)) ||
- (void *)brk(BASE + incr) == (void *)-1) {
- if (!refused || refused > incr)
- refused = incr;
- return -1;
- }
- BASE += incr;
- return 0;
- }
- /*
- * Initialize some pieces of core. We hope that this will be our last
- * real allocation, meaning we've made the right choices.
- */
- void init_core()
- {
- char *base;
- ind_t total_size;
- struct memory *mem;
- #include "mach.c"
- #define ALIGN 8 /* minimum alignment for pieces */
- #define AT_LEAST (ind_t)2*ALIGN /* See comment about string areas. */
- total_size = (ind_t)0; /* Will accumulate the sizes. */
- BASE = base = (char *)sbrk(0); /* First free. */
- if ((int)base % ALIGN) {
- base = (char *)sbrk(ALIGN - (int)base % ALIGN);
- BASE = base = (char *)sbrk(0);
- }
- /*
- * String areas are special-cased. The first byte is unused as a way to
- * distinguish a name without string from a name which has the first
- * string in the string area.
- */
- for (mem = mems; mem < &mems[NMEMS]; mem++) {
- mem->mem_base = base;
- mem->mem_full = (ind_t)0;
- if (mem == &mems[ALLOLCHR] || mem == &mems[ALLOGCHR]) {
- if (mem->mem_left == 0) {
- mem->mem_left = ALIGN;
- total_size += ALIGN;
- base += ALIGN;
- }
- base += mem->mem_left;
- total_size += mem->mem_left;
- mem->mem_left--;
- mem->mem_full++;
- }
- else {
- base += mem->mem_left; /* Each piece will start after prev. */
- total_size += mem->mem_left;
- }
- }
- if (sbreak(total_size) == -1) {
- incore = FALSE; /* In core strategy failed. */
- if (sbreak(AT_LEAST) == -1)
- fatal("no core at all");
-
- base = BASE;
- for (mem = mems; mem < &mems[NMEMS]; mem++) {
- mem->mem_base = base;
- if (mem == &mems[ALLOLCHR] || mem == &mems[ALLOGCHR]) {
- base += ALIGN;
- mem->mem_left = ALIGN - 1;
- mem->mem_full = 1;
- }
- else {
- mem->mem_full = (ind_t)0;
- mem->mem_left = 0;
- }
- }
- }
- }
- /*
- * Allocate an extra block of `incr' bytes and move all pieces with index
- * higher than `piece' up with the size of the block.
- * Move up as much as possible, if "incr" fails.
- */
- static ind_t move_up(int piece, ind_t incr)
- {
- register struct memory *mem;
- #ifndef NOSTATISTICS
- extern int statistics;
- #endif
- debug("move_up(%d, %d)\n", piece, (int)incr);
- while (incr > 0 && sbreak(incr) == -1)
- incr -= INCRSIZE;
- if (incr <= 0) {
- incr = 0;
- return (ind_t) 0;
- }
- #ifndef NOSTATISTICS
- if (statistics) fprintf(stderr,"moving up %lx\n", (long) incr);
- #endif
- for (mem = &mems[NMEMS - 1]; mem > &mems[piece]; mem--)
- copy_up(mem, incr);
- mems[piece].mem_left += incr;
- return incr;
- }
- extern int passnumber;
- /*
- * This routine is called if `piece' needs `incr' bytes and the system won't
- * give them. We first steal the free bytes of all lower pieces and move them
- * and `piece' down. If that doesn't give us enough bytes, we steal the free
- * bytes of all higher pieces and move them up. We return whether we have
- * enough bytes, the first or the second time.
- */
- #define NORMAL 0
- #define FREEZE 1
- #define FORCED 2
- static bool compact(int piece, ind_t incr, int flag)
- {
- ind_t gain, size;
- struct memory *mem;
- int min = piece, max = piece;
- #define SHIFT_COUNT 2 /* let pieces only contribute if their free
- memory is more than 1/2**SHIFT_COUNT * 100 %
- of its occupied memory
- */
- debug("compact(%d, %d, %d)\n", piece, (int)incr, flag);
- for (mem = &mems[0]; mem < &mems[NMEMS - 1]; mem++) {
- assert(mem->mem_base + mem->mem_full + mem->mem_left == (mem+1)->mem_base);
- }
- mem = &mems[piece];
- if (flag == NORMAL) {
- /* try and gain a bit more than needed */
- gain = (mem->mem_full + incr) >> SHIFT_COUNT;
- if (incr < gain) incr = gain;
- }
-
- /*
- * First, check that moving will result in enough space
- */
- if (flag != FREEZE) {
- gain = mem->mem_left;
- for (mem = &mems[piece-1]; mem >= &mems[0]; mem--) {
- /*
- * Don't give it all away!
- * If this does not give us enough, bad luck
- */
- if (flag == FORCED)
- size = 0;
- else {
- size = mem->mem_full >> SHIFT_COUNT;
- if (size == 0) size = mem->mem_left >> 1;
- }
- if (mem->mem_left >= size)
- gain += (mem->mem_left - size) & ~(ALIGN - 1);
- if (gain >= incr) {
- min = mem - &mems[0];
- break;
- }
- }
- if (min == piece)
- for (mem = &mems[piece+1]; mem <= &mems[NMEMS - 1]; mem++) {
- /*
- * Don't give it all away!
- * If this does not give us enough, bad luck
- */
- if (flag == FORCED)
- size = 0;
- else {
- size = mem->mem_full >> SHIFT_COUNT;
- if (size == 0) size = mem->mem_left >> 1;
- }
- if (mem->mem_left >= size)
- gain += (mem->mem_left - size) & ~(ALIGN - 1);
- if (gain >= incr) {
- max = mem - &mems[0];
- break;
- }
- }
- if (min == piece) {
- min = 0;
- if (max == piece) max = 0;
- }
- if (gain < incr) return 0;
- }
- else {
- min = 0;
- max = NMEMS - 1;
- }
- gain = 0;
- for (mem = &mems[min]; mem != &mems[piece]; mem++) {
- /* Here memory is inserted before a piece. */
- assert(passnumber == FIRST || gain == (ind_t)0);
- if (gain) copy_down(mem, gain);
- if (flag == FREEZE || gain < incr) {
- if (flag != NORMAL) size = 0;
- else {
- size = mem->mem_full >> SHIFT_COUNT;
- if (size == 0) size = mem->mem_left >> 1;
- }
- if (mem->mem_left >= size) {
- size = (mem->mem_left - size) & ~(ALIGN - 1);
- gain += size;
- mem->mem_left -= size;
- }
- }
- }
- /*
- * Now mems[piece]:
- */
- if (gain) copy_down(mem, gain);
- gain += mem->mem_left;
- mem->mem_left = 0;
- if (gain < incr) {
- ind_t up = (ind_t)0;
- for (mem = &mems[max]; mem > &mems[piece]; mem--) {
- /* Here memory is appended after a piece. */
- if (flag == FREEZE || gain + up < incr) {
- if (flag != NORMAL) size = 0;
- else {
- size = mem->mem_full >> SHIFT_COUNT;
- if (size == 0) size = mem->mem_left >> 1;
- }
- if (mem->mem_left >= size) {
- size = (mem->mem_left - size) & ~(ALIGN - 1);
- up += size;
- mem->mem_left -= size;
- }
- }
- if (up) copy_up(mem, up);
- }
- gain += up;
- }
- mems[piece].mem_left += gain;
- assert(flag == FREEZE || gain >= incr);
- for (mem = &mems[0]; mem < &mems[NMEMS - 1]; mem++) {
- assert(mem->mem_base + mem->mem_full + mem->mem_left == (mem+1)->mem_base);
- }
- return gain >= incr;
- }
- /*
- * The bytes of `mem' must be moved `dist' down in the address space.
- * We copy the bytes from low to high, because the tail of the new area may
- * overlap with the old area, but we do not want to overwrite them before they
- * are copied.
- */
- static void copy_down(struct memory *mem, ind_t dist)
- {
- char *old;
- char *new;
- ind_t size;
- size = mem->mem_full;
- old = mem->mem_base;
- new = old - dist;
- mem->mem_base = new;
- while (size--)
- *new++ = *old++;
- }
- /*
- * The bytes of `mem' must be moved `dist' up in the address space.
- * We copy the bytes from high to low, because the tail of the new area may
- * overlap with the old area, but we do not want to overwrite them before they
- * are copied.
- */
- static void copy_up(struct memory *mem, ind_t dist)
- {
- char *old;
- char *new;
- ind_t size;
- size = mem->mem_full;
- old = mem->mem_base + size;
- new = old + dist;
- while (size--)
- *--new = *--old;
- mem->mem_base = new;
- }
- static int alloctype = NORMAL;
- /*
- * Add `size' bytes to the bytes already allocated for `piece'. If it has no
- * free bytes left, ask them from memory or, if that fails, from the free
- * bytes of other pieces. The offset of the new area is returned. No matter
- * how many times the area is moved, because of another allocate, this offset
- * remains valid.
- */
- ind_t alloc(int piece, long size)
- {
- ind_t incr = 0;
- ind_t left = mems[piece].mem_left;
- ind_t full = mems[piece].mem_full;
- assert(passnumber == FIRST || (!incore && piece == ALLOMODL));
- if (size == (long)0)
- return full;
- if (size != (ind_t)size)
- return BADOFF;
- switch(piece) {
- case ALLOMODL:
- case ALLORANL:
- size = int_align(size);
- }
- if (size - left > 0)
- incr = ((size - left + (INCRSIZE - 1)) / INCRSIZE) * INCRSIZE;
- if (incr == 0 ||
- (incr < left + full && (incr -= move_up(piece, left + full)) <= 0) ||
- move_up(piece, incr) == incr ||
- compact(piece, size, alloctype)) {
- mems[piece].mem_full += size;
- mems[piece].mem_left -= size;
- return full;
- } else {
- incore = FALSE;
- return BADOFF;
- }
- }
- /*
- * Same as alloc() but for a piece which really needs it. If the first
- * attempt fails, release the space occupied by other pieces and try again.
- */
- ind_t hard_alloc(int piece, long size)
- {
- ind_t ret;
- int i;
- if (size != (ind_t)size)
- return BADOFF;
- if ((ret = alloc(piece, size)) != BADOFF) {
- return ret;
- }
- /*
- * Deallocate what we don't need.
- */
- for (i = 0; i < NMEMS; i++) {
- switch (i) {
- case ALLOGLOB:
- case ALLOGCHR:
- case ALLOSYMB:
- case ALLOARCH:
- case ALLOMODL:
- case ALLORANL:
- break; /* Do not try to deallocate this. */
- default:
- dealloc(i);
- break;
- }
- }
- free_saved_moduls();
- if ((ret = alloc(piece, size)) != BADOFF) {
- return ret;
- }
- alloctype = FORCED;
- ret = alloc(piece, size);
- alloctype = NORMAL;
- return ret;
- }
- /*
- * We don't need the previous modules, so we put the current module
- * at the start of the piece allocated for module contents, thereby
- * overwriting the saved modules, and release its space.
- */
- static void free_saved_moduls()
- {
- ind_t size;
- char *old, *new;
- struct memory *mem = &mems[ALLOMODL];
- size = mem->mem_full - core_position;
- new = mem->mem_base;
- old = new + core_position;
- while (size--)
- *new++ = *old++;
- mem->mem_full -= core_position;
- mem->mem_left += core_position;
- core_position = (ind_t)0;
- }
- /*
- * The piece of memory with index `piece' is no longer needed.
- * We take care that it can be used by compact() later, if needed.
- */
- void dealloc(int piece)
- {
- /*
- * Some pieces need their memory throughout the program.
- */
- assert(piece != ALLOGLOB);
- assert(piece != ALLOGCHR);
- assert(piece != ALLOSYMB);
- assert(piece != ALLOARCH);
- mems[piece].mem_left += mems[piece].mem_full;
- mems[piece].mem_full = (ind_t)0;
- }
- char *core_alloc(int piece, long size)
- {
- register ind_t off;
- if ((off = alloc(piece, size)) == BADOFF)
- return (char *)0;
- return address(piece, off);
- }
- void core_free(int piece, char *p)
- {
- char *q = address(piece, mems[piece].mem_full);
- assert(p < q);
- if (sizeof(unsigned) == sizeof(char *))
- {
- mems[piece].mem_full -= (unsigned) (q - p);
- mems[piece].mem_left += (unsigned) (q - p);
- }
- else
- {
- mems[piece].mem_full -= (ind_t) q - (ind_t) p;
- mems[piece].mem_left += (ind_t) q - (ind_t) p;
- }
- }
- /*
- * Reset index into piece of memory for modules and
- * take care that the allocated pieces will not be moved.
- */
- void freeze_core()
- {
- int i;
- core_position = (ind_t)0;
- if (incore)
- return;
- for (i = 0; i < NMEMS; i++) {
- switch (i) {
- case ALLOGLOB:
- case ALLOGCHR:
- case ALLOSYMB:
- case ALLOARCH:
- break; /* Do not try to deallocate this. */
- default:
- dealloc(i);
- break;
- }
- }
- compact(NMEMS - 1, (ind_t)0, FREEZE);
- }
- /* ------------------------------------------------------------------------- */
- /*
- * To transform the various pieces of the output in core to the file format,
- * we must order the bytes in the unsigned shorts and longs as ACK prescribes.
- */
- void write_bytes()
- {
- unsigned short nsect;
- long offchar;
- struct memory *mem;
- extern unsigned short NLocals, NGlobals;
- extern long NLChars, NGChars;
- extern int flagword;
- extern struct outhead outhead;
- extern struct outsect outsect[];
- /* extern char *outputname; */
- int sectionno = 0;
- nsect = outhead.oh_nsect;
- offchar = OFF_CHAR(outhead);
- /*
- * We allocated two areas: one for local and one for global names.
- * Also, we used another kind of on_foff than on file.
- * At the end of the global area we have put the section names.
- */
- if (!(flagword & SFLAG)) {
- do_crs((struct outname *)mems[ALLOLOCL].mem_base, NLocals);
- namecpy((struct outname *)mems[ALLOLOCL].mem_base,
- NLocals,
- offchar
- );
- namecpy((struct outname *)mems[ALLOGLOB].mem_base,
- NGlobals + nsect,
- offchar + NLChars
- );
- }
- /*
- * These pieces must always be written.
- */
- wr_ohead(&outhead);
- wr_sect(outsect, nsect);
- for (mem = &mems[ALLOEMIT]; mem < &mems[ALLORELO]; mem++)
- wrt_emit(mem->mem_base, sectionno++, mem->mem_full);
- /*
- * The rest depends on the flags.
- */
- if (flagword & (RFLAG|CFLAG))
- wr_relo((struct outrelo *) mems[ALLORELO].mem_base,
- outhead.oh_nrelo);
- if (!(flagword & SFLAG)) {
- wr_name((struct outname *) mems[ALLOLOCL].mem_base,
- NLocals);
- wr_name((struct outname *) mems[ALLOGLOB].mem_base,
- NGlobals+nsect);
- wr_string(mems[ALLOLCHR].mem_base + 1, (long)NLChars);
- wr_string(mems[ALLOGCHR].mem_base + 1, (long)NGChars);
- #ifdef SYMDBUG
- wr_dbug(mems[ALLODBUG].mem_base, mems[ALLODBUG].mem_full);
- #endif /* SYMDBUG */
- }
- }
- void namecpy(struct outname *name, unsigned int nname, long offchar)
- {
- while (nname--) {
- if (name->on_foff)
- name->on_foff += offchar - 1;
- name++;
- }
- }
|