memory.c 14 KB

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