memory.c 14 KB

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