memory.c 15 KB

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