alloc.c 8.5 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439
  1. #ifndef NORCSID
  2. static char rcsid[] = "$Id$";
  3. #endif
  4. #include <stdlib.h>
  5. #include <stdio.h>
  6. #include "param.h"
  7. #include "types.h"
  8. #include "tes.h"
  9. #include "assert.h"
  10. #include "alloc.h"
  11. #include "line.h"
  12. #include "lookup.h"
  13. #include "proinf.h"
  14. /*
  15. * (c) copyright 1987 by the Vrije Universiteit, Amsterdam, The Netherlands.
  16. * See the copyright notice in the ACK home directory, in the file "Copyright".
  17. *
  18. * Author: Hans van Staveren
  19. */
  20. #ifdef USEMALLOC
  21. short * myalloc();
  22. #define newcore(size) myalloc(size)
  23. #define oldcore(p,size) free(p)
  24. #else
  25. #undef CORECHECK /* if defined tests are made to insure
  26. each block occurs at most once */
  27. #define CCHUNK 1024 /* number of shorts asked from system */
  28. short *newcore(),*freshcore();
  29. extern char *sbrk();
  30. #ifdef COREDEBUG
  31. int shortsasked=0;
  32. #endif
  33. #endif
  34. /*
  35. * The following two sizetables contain the sizes of the various kinds
  36. * of line and argument structures.
  37. * Care has been taken to make this table implementation independent,
  38. * but if you think very hard you might find a compiler failing the
  39. * assumptions made.
  40. * A wasteful but safe approach is to replace every line of them by
  41. * sizeof(line_t)
  42. * and
  43. * sizeof(arg_t)
  44. * respectively.
  45. */
  46. #define LBASE (sizeof(line_t)-sizeof(un_l_a))
  47. int lsizetab[] = {
  48. LBASE,
  49. LBASE+sizeof(short),
  50. LBASE+sizeof(offset),
  51. LBASE+sizeof(num_p),
  52. LBASE+sizeof(sym_p),
  53. LBASE+sizeof(s_la_sval),
  54. LBASE+sizeof(s_la_lval),
  55. LBASE+sizeof(arg_p),
  56. LBASE
  57. };
  58. #define ABASE (sizeof(arg_t)-sizeof(un_a_a))
  59. int asizetab[] = {
  60. ABASE+sizeof(offset),
  61. ABASE+sizeof(num_p),
  62. ABASE+sizeof(sym_p),
  63. ABASE+sizeof(s_a_val),
  64. ABASE+sizeof(argb_t),
  65. ABASE+sizeof(s_a_con),
  66. ABASE+sizeof(s_a_con),
  67. ABASE+sizeof(s_a_con),
  68. };
  69. /*
  70. * alloc routines:
  71. * Two parts:
  72. * 1) typed alloc and free routines
  73. * 2) untyped raw core allocation
  74. */
  75. /*
  76. * PART 1
  77. */
  78. line_p newline(optyp) int optyp; {
  79. register line_p lnp;
  80. register kind=optyp;
  81. if (kind>OPMINI)
  82. kind = OPMINI;
  83. lnp = (line_p) newcore(lsizetab[kind]);
  84. lnp->l_optyp = optyp;
  85. return(lnp);
  86. }
  87. oldline(lnp) register line_p lnp; {
  88. register kind=lnp->l_optyp&BMASK;
  89. if (kind>OPMINI)
  90. kind = OPMINI;
  91. if (kind == OPLIST)
  92. oldargs(lnp->l_a.la_arg);
  93. oldcore((short *) lnp,lsizetab[kind]);
  94. }
  95. arg_p newarg(kind) int kind; {
  96. register arg_p ap;
  97. ap = (arg_p) newcore(asizetab[kind]);
  98. ap->a_typ = kind;
  99. return(ap);
  100. }
  101. oldargs(ap) register arg_p ap; {
  102. register arg_p next;
  103. while (ap != (arg_p) 0) {
  104. next = ap->a_next;
  105. switch(ap->a_typ) {
  106. case ARGSTR:
  107. oldargb(ap->a_a.a_string.ab_next);
  108. break;
  109. case ARGICN:
  110. case ARGUCN:
  111. case ARGFCN:
  112. oldargb(ap->a_a.a_con.ac_con.ab_next);
  113. break;
  114. }
  115. oldcore((short *) ap,asizetab[ap->a_typ]);
  116. ap = next;
  117. }
  118. }
  119. oldargb(abp) register argb_p abp; {
  120. register argb_p next;
  121. while (abp != (argb_p) 0) {
  122. next = abp->ab_next;
  123. oldcore((short *) abp,sizeof (argb_t));
  124. abp = next;
  125. }
  126. }
  127. reg_p newreg() {
  128. return((reg_p) newcore(sizeof(reg_t)));
  129. }
  130. oldreg(rp) reg_p rp; {
  131. oldcore((short *) rp,sizeof(reg_t));
  132. }
  133. num_p newnum() {
  134. return((num_p) newcore(sizeof(num_t)));
  135. }
  136. oldnum(lp) num_p lp; {
  137. oldcore((short *) lp,sizeof(num_t));
  138. }
  139. offset *newrom() {
  140. return((offset *) newcore(MAXROM*sizeof(offset)));
  141. }
  142. sym_p newsym(len) int len; {
  143. /*
  144. * sym_t includes a 2 character s_name at the end
  145. * extend this structure with len-2 characters
  146. */
  147. return((sym_p) newcore(sizeof(sym_t) - 2 + len));
  148. }
  149. argb_p newargb() {
  150. return((argb_p) newcore(sizeof(argb_t)));
  151. }
  152. #ifndef USEMALLOC
  153. /******************************************************************/
  154. /****** Start of raw core management package *****************/
  155. /******************************************************************/
  156. #define MAXSHORT 30 /* Maximum number of shorts one can ask for */
  157. short *freelist[MAXSHORT];
  158. typedef struct coreblock {
  159. struct coreblock *co_next;
  160. short co_size;
  161. } core_t,*core_p;
  162. #define SINC (sizeof(core_t)/sizeof(short))
  163. #ifdef COREDEBUG
  164. coreverbose() {
  165. register size;
  166. register short *p;
  167. register sum;
  168. sum = 0;
  169. for(size=1;size<MAXSHORT;size++)
  170. for (p=freelist[size];p!=0;p = *(short **) p)
  171. sum += size;
  172. fprintf(stderr,"Used core %u\n",(shortsasked-sum)*sizeof(short));
  173. }
  174. #endif
  175. #ifdef SEPID
  176. compactcore() {
  177. register core_p corelist=0,tp,cl;
  178. int size;
  179. #ifdef COREDEBUG
  180. fprintf(stderr,"Almost out of core\n");
  181. #endif
  182. for(size=SINC;size<MAXSHORT;size++) {
  183. while ((tp = (core_p) freelist[size]) != (core_p) 0) {
  184. freelist[size] = (short *) tp->co_next;
  185. tp->co_size = size;
  186. if (corelist==0 || tp<corelist) {
  187. tp->co_next = corelist;
  188. corelist = tp;
  189. } else {
  190. for(cl=corelist;cl->co_next != 0 && tp>cl->co_next;
  191. cl = cl->co_next)
  192. ;
  193. tp->co_next = cl->co_next;
  194. cl->co_next = tp;
  195. }
  196. }
  197. }
  198. while (corelist != 0) {
  199. while ((short *) corelist->co_next ==
  200. (short *) corelist + corelist->co_size) {
  201. corelist->co_size += corelist->co_next->co_size;
  202. corelist->co_next = corelist->co_next->co_next;
  203. }
  204. assert(corelist->co_next==0 ||
  205. (short *) corelist->co_next >
  206. (short *) corelist + corelist->co_size);
  207. while (corelist->co_size >= MAXSHORT+SINC) {
  208. oldcore((short *) corelist + corelist->co_size-(MAXSHORT-1),
  209. sizeof(short)*(MAXSHORT-1));
  210. corelist->co_size -= MAXSHORT;
  211. }
  212. if (corelist->co_size >= MAXSHORT) {
  213. oldcore((short *) corelist + corelist->co_size-SINC,
  214. sizeof(short)*SINC);
  215. corelist->co_size -= SINC;
  216. }
  217. cl = corelist->co_next;
  218. oldcore((short *) corelist, sizeof(short)*corelist->co_size);
  219. corelist = cl;
  220. }
  221. }
  222. short *grabcore(size) int size; {
  223. register short *p;
  224. register trysize;
  225. /*
  226. * Desperate situation, can't get more core from system.
  227. * Postpone giving up just a little bit by splitting up
  228. * larger free blocks if possible.
  229. * Algorithm is worst fit.
  230. */
  231. assert(size<2*MAXSHORT);
  232. for(trysize=2*MAXSHORT-2; trysize>size; trysize -= 2) {
  233. p = freelist[trysize/sizeof(short)];
  234. if ( p != (short *) 0) {
  235. freelist[trysize/sizeof(short)] = *(short **) p;
  236. oldcore(p+size/sizeof(short),trysize-size);
  237. return(p);
  238. }
  239. }
  240. /*
  241. * Can't get more core from the biggies, try to combine the
  242. * little ones. This is expensive but probably better than
  243. * giving up.
  244. */
  245. compactcore();
  246. if ((p=freelist[size/sizeof(short)]) != 0) {
  247. freelist[size/sizeof(short)] = * (short **) p;
  248. return(p);
  249. }
  250. for(trysize=2*MAXSHORT-2; trysize>size; trysize -= 2) {
  251. p = freelist[trysize/sizeof(short)];
  252. if ( p != (short *) 0) {
  253. freelist[trysize/sizeof(short)] = *(short **) p;
  254. oldcore(p+size/sizeof(short),trysize-size);
  255. return(p);
  256. }
  257. }
  258. /*
  259. * That's it then. Finished.
  260. */
  261. return(0);
  262. }
  263. #endif /* SEPID */
  264. short *newcore(size) int size; {
  265. register short *p,*q;
  266. size = (size + sizeof(int) - 1) & ~(sizeof(int) - 1);
  267. if( size < 2*MAXSHORT ) {
  268. if ((p=freelist[size/sizeof(short)]) != (short *) 0)
  269. freelist[size/sizeof(short)] = *(short **) p;
  270. else {
  271. p = freshcore(size);
  272. #ifdef SEPID
  273. if (p == (short *) 0)
  274. p = grabcore(size);
  275. #endif
  276. }
  277. } else
  278. p = freshcore(size);
  279. if (p == 0)
  280. error("out of memory");
  281. for (q=p; size > 0 ; size -= sizeof(short))
  282. *q++ = 0;
  283. return(p);
  284. }
  285. #ifndef USEMALLOC
  286. /*
  287. * stdio uses malloc and free.
  288. * you can use these as substitutes
  289. */
  290. char *malloc(size) int size; {
  291. /*
  292. * malloc(III) is called by stdio,
  293. * this routine is a substitute.
  294. */
  295. return( (char *) newcore(size));
  296. }
  297. free() {
  298. }
  299. #endif
  300. oldcore(p,size) short *p; int size; {
  301. #ifdef CORECHECK
  302. register short *cp;
  303. #endif
  304. assert(size<2*MAXSHORT);
  305. #ifdef CORECHECK
  306. for (cp=freelist[size/sizeof(short)]; cp != (short *) 0;
  307. cp = *(short **) cp)
  308. assert(cp != p);
  309. #endif
  310. *(short **) p = freelist[size/sizeof(short)];
  311. freelist[size/sizeof(short)] = p;
  312. }
  313. short *ccur,*cend;
  314. coreinit(p1,p2) short *p1,*p2; {
  315. /*
  316. * coreinit is called with the boundaries of a piece of
  317. * memory that can be used for starters.
  318. */
  319. ccur = p1;
  320. cend = p2;
  321. }
  322. short *freshcore(size) int size; {
  323. register short *temp;
  324. static int cchunk=CCHUNK;
  325. while(&ccur[size/sizeof(short)] >= cend && cchunk>0) {
  326. do {
  327. temp = (short *) sbrk(cchunk*sizeof(short));
  328. if (temp == (short *) -1)
  329. cchunk >>= 1;
  330. else if (temp != cend)
  331. ccur = cend = temp;
  332. } while (temp == (short *) -1 && cchunk>0);
  333. cend += cchunk;
  334. #ifdef COREDEBUG
  335. shortsasked += cchunk;
  336. #endif
  337. }
  338. if (cchunk==0)
  339. return(0);
  340. temp = ccur;
  341. ccur = &ccur[size/sizeof(short)];
  342. return(temp);
  343. }
  344. #else /* USEMALLOC */
  345. coreinit() {
  346. /*
  347. * Empty function, no initialization needed
  348. */
  349. }
  350. short *myalloc(size) register size; {
  351. register short *p,*q;
  352. p = (short *)malloc(size);
  353. if (p == 0)
  354. error("out of memory");
  355. for(q=p;size>0;size -= sizeof(short))
  356. *q++ = 0;
  357. return(p);
  358. }
  359. #endif