|
|
1.1 root 1: /* Copyright 1989 by AT&T Bell Laboratories */
2: #include <signal.h>
3: #include <sys/types.h>
4: #ifdef BSD
5: #include <sys/time.h>
6: #include <sys/resource.h>
7: #endif
8:
9: #ifdef MIPS
10: #include <sys/syscall.h>
11: #include <mips/cachectl.h>
12: #include <errno.h>
13: #endif
14:
15: #include "tags.h"
16: #include "descriptor.h"
17:
18: #define refcell(z) int z[2] = {mak_desc(1,tag_array), ML_INT(0)};
19:
20: #ifdef NeXT
21:
22: #include <c.h> /* TRUE and FALSE */
23: #include <sys/kern_return.h> /* KERN_whatever */
24: #include <mach.h> /* type definitions */
25:
26: #endif NeXT
27:
28: refcell(collected0)
29: refcell(collectedfrom0)
30: refcell(current0)
31: refcell(gcmessages0)
32: refcell(majorcollections0)
33: refcell(minorcollections0)
34: refcell(pstruct0)
35: refcell(ratio0)
36: refcell(softmax0)
37:
38: #define collected (collected0[1])
39: #define collectedfrom (collectedfrom0[1])
40: #define current (current0[1])
41: #define gcmessages (gcmessages0[1])
42: #define majorcollections (majorcollections0[1])
43: #define minorcollections (minorcollections0[1])
44: #define pstruct (pstruct0[1])
45: #define ratio (ratio0[1])
46: #define softmax (softmax0[1])
47:
48: int arenabase; /* bottom of the heap */
49: int arenasize = 0; /* heap starts empty */
50: int new_size = 1024 * 1024; /* default heap size of 1 megabyte */
51: int arstart; /* beginning of main arena */
52: int arend; /* end of main arena, and the heap */
53: int old_high; /* marks end of persistent heap */
54: int new_high;
55: int new_new_high;
56: int lastbreak;
57:
58: int cause, fault_code;
59: int bottom; /* saved stack-pointer */
60: int fpsave; /* saved frame pointer */
61: int saved_pc_relative;
62: int saved_pc, saved_dataptr, saved_exnptr, saved_storeptr=1, saved_limit;
63: #ifdef SPARC
64: extern int saved_ptrs[], saved_nonptrs[]; /* allocated in SPARC.prim.s */
65: #else
66: int saved_ptrs[32], saved_nonptrs[32];
67: #endif
68:
69: int store_preserve=1, preserving=0;
70:
71: extern int handle_c[], return_c[];
72:
73: apply(func,arg) int func, arg;
74: {int i;
75: saved_exnptr = (int) handle_c;
76: saved_ptrs[0] = arg;
77: saved_ptrs[1] = (int) return_c;
78: saved_ptrs[2] = func;
79: saved_pc = *(int*)func;
80: for(i=3;i<32;i++) saved_ptrs[i]=0;
81: runML();
82: return saved_ptrs[0];
83: }
84:
85: int exportFilid;
86:
87: runML()
88: {int i;
89: for(;;)
90: {cause=0;
91: #ifdef MIPS
92: cacheflush((char *) arenabase, arenasize, ICACHE);
93: #endif
94: restoreregs();
95: switch(cause)
96: {case CAUSE_EXN: return uncaught(saved_ptrs[0]);
97: case CAUSE_GC: callgc0(); break;
98: case CAUSE_RET: return;
99: case CAUSE_EXPORT: saved_pc=0;
100: for(i=2;i<32;i++) saved_ptrs[i]=0;
101: callgc0(); callgc0();
102: saved_pc = *(int*)saved_ptrs[1];
103: export(exportFilid);
104: saved_ptrs[0]=1;
105: break;
106: case CAUSE_BLAST: saved_pc=0;
107: callgc0();
108: saved_pc = *(int*)saved_ptrs[1];
109: break;
110: case CAUSE_STOR: saved_pc=0;
111: callgc0();
112: preserving = (saved_ptrs[0]!=1);
113: saved_ptrs[0]= uniq(store_preserve);
114: store_preserve=1;
115: saved_pc = *(int*)saved_ptrs[1];
116: break;
117: case CAUSE_FAULT:
118: for(i=0;i<32;i++) saved_ptrs[i]=0;
119: saved_ptrs[0]=fault_code;
120: saved_ptrs[1]=saved_exnptr;
121: saved_pc = *(int*)saved_ptrs[1];
122: break;
123: }
124: }
125: }
126:
127:
128: #define pagesize 8192
129:
130: #ifdef NeXT
131:
132: /**
133: ** This implements sbrk/brk using vm_allocate/vm_deallocate.
134: ** Arguments are assumed to be page multiples, and the argument
135: ** to brk is assumed to be just after the desired breakpoint.
136: **
137: ** No relationship between the mapped region and the rest of the
138: ** process image is guaranteed, but it is expected that the region
139: ** will follow the end of data/bss.
140: **
141: ** Works with NeXT Mach (software release 0.9). 5/15/89
142: **
143: ** James William O'Toole Jr.
144: **
145: **/
146:
147: extern vm_task_t task_self_;
148:
149: int mach_sbrk_needsinit = TRUE;
150: int mach_maplimit = 0;
151: int mach_brkpt = 0;
152: int mach_quant = 0x800000;
153: int big_heap = 0x2000000;
154:
155: static int sbrk(incr)
156: int incr;
157: {
158: if (incr) die("sbrk called with nonzero value");
159: if (mach_sbrk_needsinit != FALSE) {
160: if (vm_allocate(task_self_, &mach_brkpt, big_heap,TRUE)
161: != KERN_SUCCESS)
162: die("vm_allocate failed");
163: mach_maplimit = mach_brkpt + big_heap;
164: mach_sbrk_needsinit = FALSE;
165: }
166: return(mach_brkpt);
167: }
168:
169: static int brk(pos)
170: int pos;
171: {
172: if (pos>mach_maplimit) return KERN_FAILURE;
173: return KERN_SUCCESS;
174: }
175:
176: #endif NeXT
177:
178: init_gc()
179: {
180: arenabase=sbrk(0);
181: lastbreak=arenabase;
182: increase_heapsize();
183: old_high = arenabase;
184: arstart = arenabase+arenasize/2;
185: saved_dataptr = (int)arstart;
186: saved_limit = arenabase+arenasize-4096;
187: }
188:
189: #ifdef ADVICE
190: struct timeval zero, ogtime, ostime, otime;
191: int getting_advice;
192: int old_size;
193: int old_minorcount;
194: #endif
195:
196: restarter()
197: {extern int edata;
198: resettimers();
199: lastbreak = (int)&edata;
200: getmore_restart();
201: #ifdef ADVICE
202: ostime=zero; otime=zero; ogtime=zero;
203: getting_advice=1;
204: initadvice();
205: #endif
206: saved_dataptr = (int)arstart;
207: saved_limit = lastbreak-4096;
208: setupsignals();
209: saved_ptrs[0]=3;
210: runML();
211: #ifdef ADVICE
212: call_endadvice();
213: #endif
214: _exit(0);
215: }
216:
217: callgc0()
218: {int i; int *roots[40]; int **rootsptr = roots;
219: #ifdef V9
220: int (*inthandle)();
221: inthandle = signal(SIGINT,SIG_IGN);
222: #endif
223: suspendtimers();
224: *rootsptr++ = &pstruct;
225: *rootsptr++ = &saved_exnptr;
226: for(i=0;i<32;i++) *rootsptr++ = saved_ptrs+i;
227: {extern int gcprof[];
228: int *currentsave = (int *) current;
229: current = (int) (gcprof+1);
230: *rootsptr++ = (int *) ¤tsave;
231: *rootsptr++ = (int *) &store_preserve;
232: *rootsptr++ = (int *) &saved_pc;
233: *rootsptr=0;
234: i=0;
235: callgc(roots,&saved_dataptr,saved_storeptr);
236: saved_storeptr=1;
237: current = (int) currentsave;
238: }
239: restarttimers();
240: #ifdef V9
241: signal(SIGINT,inthandle);
242: #endif
243: }
244:
245: int getmore_die(){die("bug: insufficient to_space\n");}
246:
247: int amount_desired;
248:
249: int decrease_heapsize()
250: {int p = arenabase+new_size;
251: p = (p + pagesize-1 ) & ~(pagesize-1);
252: if (p<lastbreak)
253: {brk(p);
254: arenasize = p-arenabase;
255: if (gcmessages >= ML_INT(2))
256: chatting("\n[Decreasing heap to %dk]\n",arenasize/1024);
257: lastbreak=p;}
258: return lastbreak;}
259:
260: int increase_heapsize() /* new_size > arenasize */
261: {int p = arenabase+new_size;
262: RESTART:
263: p = (p + pagesize-1 ) & ~(pagesize-1);
264: if (p==lastbreak)
265: {if (gcmessages >= ML_INT(2)) chatting("\nWarning: can't increase heap\n");
266: return p;}
267: else if (brk(p))
268: {if (gcmessages >= ML_INT(3))
269: chatting("\nWarning: must reduce heap request\n");
270: p=(lastbreak+(p-pagesize))/2; goto RESTART;}
271: else {lastbreak=p;
272: arenasize = p-arenabase;
273: if (gcmessages >= ML_INT(2))
274: chatting("\n[Increasing heap to %dk]\n",arenasize/1024);
275: return p;}
276: }
277:
278: int compute_new_size(live_size)
279: int live_size;
280: {int new_size, gamma = (ratio<7?7:ratio)>>1, max = softmax>>1;
281: if (2000000000 / gamma < live_size)
282: new_size = 2000000000;
283: else new_size=live_size*gamma;
284: if (max < new_size)
285: {int new = 3*live_size;
286: new_size = (new>max?new:max);}
287: return new_size;
288: }
289:
290: int getmore_must()
291: {int oldsize=arenasize;
292: int live_size = amount_desired+arenasize+arenabase-old_high;
293: new_size=compute_new_size(live_size);
294: {int r=increase_heapsize();
295: #ifdef ADVICE
296: while (oldsize==arenasize)
297: {chatting("\nCan't get more memory; waiting\n");
298: sleep(10);
299: chatting("Trying again\n");
300: r=increase_heapsize();
301: }
302: #else
303: if (oldsize==arenasize) die("\nRan out of memory");
304: #endif
305: return r;
306: }
307: }
308:
309: getmore_restart()
310: {int live_size = old_high - arenabase;
311: int a = 0;
312: int x = gcmessages;
313: gcmessages=ML_INT(0);
314: new_size=compute_new_size(live_size);
315: do {increase_heapsize();
316: if (arenasize==a) die("Can't get enough memory to start ML\n");
317: a=arenasize;
318: } while (arenasize < 3*live_size);
319: gcmessages=x;
320: }
321:
322: callgc(misc_roots, /* vector of ptrs to extra root words */
323: arptr, /* place to put new freespace pointer */
324: store_list /* list of refs stored into */
325: )
326: int ***misc_roots; int *arptr; int **store_list;
327: {int amount_desired;
328: arend = arenabase+arenasize;
329: if (cause==CAUSE_EXPORT || cause==CAUSE_STOR) amount_desired = 0;
330: else amount_desired = 4+arend-(*arptr);
331: if (arstart== *arptr) new_high = old_high; /* no minor needed */
332: else
333: {if (gcmessages >= ML_INT(3)) chatting("\n[Minor collection...");
334: starttime();
335: gc(arstart,arend,
336: old_high,arstart,
337: old_high,
338: &new_high,
339: misc_roots,store_list,
340: getmore_die, 0);
341: {int a = new_high-old_high, b =(*arptr)-arstart, msec=endtime();
342: if (gcmessages >= ML_INT(3))
343: chatting(" %d%% used (%d/%d), %d msec]\n", (100*a)/b, a, b, msec);
344: collected += 2*((a+512)/1024); /* round to nearest k */
345: collectedfrom += 2*((b+512)/1024);
346: minorcollections+=2;
347: }
348: #ifdef GCDEBUG
349: checkup(arstart,new_high);
350: clear(new_high,arenabase+arenasize);
351: #endif
352: }
353: {int need_major = 0; int was_preserving; int gamma = (ratio<7?7:ratio)>>1;
354: if (cause==CAUSE_EXPORT || cause==CAUSE_BLAST) need_major = 1;
355: else {int cut = arenasize-arenasize/gamma;
356: int max = softmax>>1;
357: int halfmax = max/2;
358: int halfsize = arenasize/2;
359: cut = (cut<halfmax?cut:halfmax);
360: cut = (cut>halfsize?cut:halfsize);
361: if (new_high+amount_desired > arenabase+cut) need_major = 1;
362: else {int live_size = amount_desired+new_high-old_high;
363: #ifdef ADVICE
364: if ((arenabase+arenasize-new_high)/2 <= amount_desired*3+100) need_major=1;
365: if (minorcollections > old_minorcount+200) need_major=1;
366: #else
367: new_size=compute_new_size(live_size);
368: if (new_size > arenasize
369: && (increase_heapsize()-new_high)/2 <= amount_desired)
370: need_major = 1;
371: #endif ADVICE
372: }}
373: if (cause==CAUSE_BLAST) old_high=new_high;
374: if (need_major)
375: {if (gcmessages >= ML_INT(1)) chatting("\n[Major collection...");
376: starttime();
377: was_preserving=preserving; preserving=0;
378: if (gc(arenabase,old_high,
379: old_high,arenabase+arenasize,
380: new_high,
381: &new_new_high,
382: misc_roots,1,
383: getmore_must, cause==CAUSE_BLAST? &saved_ptrs[0]: 0))
384: {moveback(old_high,new_new_high,
385: arenabase,
386: misc_roots);
387: {int a = new_new_high-new_high,
388: b = new_high-arenabase, msec=endtime();
389: if (gcmessages >= ML_INT(1))
390: chatting(" %d%% used (%d/%d), %d msec]\n",(100*a)/b, a, b, msec);
391: collected += 2*((a+512)/1024);
392: collectedfrom += 2*((b+512)/1024);
393: majorcollections+=2;}
394: {int live_size = amount_desired+new_new_high-old_high;
395: old_high=arenabase+new_new_high-old_high;
396: #ifdef ADVICE
397: new_size = ask_new_size(live_size);
398: #else
399: new_size = compute_new_size(live_size);
400: #endif
401: if (new_size > arenasize)
402: {int end = increase_heapsize();
403: if ((end-old_high)/2 <= amount_desired)
404: die("\nRan out of memory\n");}
405: #ifdef ADVICE
406: else if (new_size < arenasize) decrease_heapsize();
407: old_size = arenasize;
408: old_minorcount = minorcollections;
409: #else
410: else if (new_size < (arenasize/4)*3) decrease_heapsize();
411: #endif
412: }}
413: else {endtime(); if (gcmessages >= ML_INT(1)) chatting("abandoned]\n");}
414: preserving=was_preserving;
415: }
416: else old_high=new_high;
417: }
418: arend = arenabase+arenasize;
419: arstart = (((arend+old_high)/2)+3)&(~3);
420: (*arptr) = arstart;
421: saved_limit = arend-4096;
422: #ifdef V9
423: { extern int ghandle();
424: signal(SIGFPE, ghandle);
425: }
426: #endif /* V9 */
427: }
428:
429: #ifdef GCDEBUG
430: clear(low,high) int *low, *high;
431: {int *i;
432: chatting("clearing new space... ");
433: for(i=low; i<high; i++) *i=0;
434: chatting("done\n");
435: }
436:
437: int *descriptor;
438: checkup(low,high)
439: int *low,*high;
440: {int *i,*j;
441: chatting("checking to_space... ");
442: i = low;
443: while (i < high) {
444: descriptor = i;
445: switch(get_tag(i)) {
446: case tag_backptr:
447: chatting("Uncool backpointer at %x in to_space\n",i);
448: exit(0);
449: break;
450: case tag_embedded:
451: chatting("Uncool embedded tag at %x in to_space\n",i);
452: exit(0);
453: break;
454: case tag_string:
455: case tag_bytearray:
456: i += (get_len(i)+7)>>2;
457: break;
458: case tag_record:
459: case tag_array:
460: j = i + get_len(i) + 1;
461: while(++i < j) {
462: if (*i & 1) continue;
463: else if ((int*)*i > high) {
464: chatting("Uncool pointer %x at %x\n", *i,i);
465: chatting("Descriptor is at %x\n",descriptor);
466: }
467: else if ((int*)*i < low) {
468: chatting("Uncool pointer %#x at %#x\n", *i,i);
469: chatting("Descriptor is at %#x\n",descriptor);
470: }
471: }
472: break;
473: case tag_forwarded:
474: chatting("Uncool forwarding tag at %x in to_space\n",i);
475: exit(0);
476: break;
477: default: /* function pointers */
478: chatting("Unexpected even tag %d at %x in to_space\n",
479: get_tag(i),i);
480: exit(0);
481: break;
482: }
483: }
484: chatting("done\n");
485: }
486: #endif /* GCDEBUG */
487:
488: int g_sec,g_usec,t_sec,t_usec;
489: #ifdef BSD
490: struct rusage r1, r2;
491:
492: starttime()
493: {getrusage(0,&r1);}
494:
495: endtime()
496: {
497: int sec,usec;
498: getrusage(0,&r2);
499: sec = r2.ru_utime.tv_sec-r1.ru_utime.tv_sec;
500: usec = r2.ru_utime.tv_usec-r1.ru_utime.tv_usec;
501: if (usec < 0) {sec--; usec += 1000000;}
502: return (usec/1000 + sec*1000);
503: }
504:
505: struct rusage garbagetime,timestamp,s1,s2;
506:
507: suspendtimers()
508: {
509: getrusage(0,&s1);
510: }
511:
512: restarttimers()
513: {
514: int sec,usec;
515: getrusage(0,&s2);
516: sec = s2.ru_utime.tv_sec-s1.ru_utime.tv_sec+garbagetime.ru_utime.tv_sec;
517: usec = s2.ru_utime.tv_usec-s1.ru_utime.tv_usec+garbagetime.ru_utime.tv_usec;
518: if (usec < 0) {sec--; usec += 1000000;}
519: else if (usec > 1000000) {sec++; usec -= 1000000;}
520: garbagetime.ru_utime.tv_sec = sec;
521: garbagetime.ru_utime.tv_usec = usec;
522: }
523:
524: resettimers()
525: {
526: garbagetime.ru_utime.tv_sec = 0;
527: garbagetime.ru_utime.tv_usec = 0;
528: s2.ru_utime.tv_sec = s1.ru_utime.tv_sec = 0;
529: s2.ru_utime.tv_usec = s1.ru_utime.tv_usec = 0;
530: r2.ru_utime.tv_sec = r1.ru_utime.tv_sec = 0;
531: r2.ru_utime.tv_usec = r1.ru_utime.tv_usec = 0;
532: collected = collectedfrom = minorcollections = majorcollections = ML_INT(0);
533: }
534:
535: timer()
536: {
537: getrusage(0,×tamp);
538: g_usec = garbagetime.ru_utime.tv_usec * 2 + 1;
539: g_sec = garbagetime.ru_utime.tv_sec * 2 + 1;
540: t_usec = timestamp.ru_utime.tv_usec * 2 + 1;
541: t_sec = timestamp.ru_utime.tv_sec * 2 + 1;
542: }
543:
544: #ifdef ADVICE
545: struct timeval subt(a,b) struct timeval a,b;
546: {struct timeval x;
547: x.tv_sec = a.tv_sec - b.tv_sec;
548: x.tv_usec = a.tv_usec - b.tv_usec;
549: if (x.tv_usec<0) {x.tv_sec--; x.tv_usec+=1000000;}
550: else if (x.tv_usec > 1000000) {x.tv_sec--; x.tv_usec+=1000000;}
551: return x;
552: }
553:
554: struct timezone zone;
555:
556: int milli(t) struct timeval t;
557: {
558: return t.tv_sec*1000 + t.tv_usec/1000;
559: }
560:
561: int ask_new_size(live_size) int live_size;
562: {int answer;
563: int s0 = arenabase+2*live_size;
564: int sf = /* (old_size?old_size:arenasize) */ arenasize - 2*live_size;
565: int delta; struct rusage adv; struct timeval newgtime, newttime, systime;
566: getrusage(0,&adv);
567: newgtime = subt(subt(adv.ru_utime,s1.ru_utime),
568: subt(ogtime,garbagetime.ru_utime));
569: newttime = subt(subt(adv.ru_utime,otime),newgtime);
570: systime = subt(adv.ru_stime,ostime);
571: ostime=adv.ru_stime;
572: otime=adv.ru_utime;
573: ogtime = subt(garbagetime.ru_utime,subt(s1.ru_utime,adv.ru_utime));
574: if ((!getting_advice) ||
575: memadvice(s0,sf,milli(newttime),milli(newgtime),0,
576: live_size,milli(systime),&answer))
577: return compute_new_size(live_size);
578: else if (answer < live_size/2) return 5*live_size/2;
579: else return answer+2*live_size;
580: }
581:
582: call_endadvice()
583: {
584: int delta; struct rusage adv; struct timeval newgtime, newttime, systime;
585: getrusage(0,&adv);
586: newgtime = subt(garbagetime.ru_utime,ogtime);
587: newttime = subt(subt(adv.ru_utime,otime),newgtime);
588: systime = subt(adv.ru_stime,ostime);
589: if (getting_advice)
590: endadvice(milli(newttime),milli(newgtime),milli(systime));
591: }
592:
593:
594:
595: #endif
596: #endif /* BSD */
597:
598: #ifdef V9
599: #include <sys/times.h>
600: struct tms t1,t2;
601:
602: starttime()
603: {times(&t1);}
604:
605: endtime()
606: {
607: int hzsec;
608: times(&t2);
609: hzsec = t2.tms_utime-t1.tms_utime;
610: return(hzsec*1000/60);
611: }
612:
613: struct tms timestamp,s1,s2;
614: int garbagetime;
615:
616: suspendtimers()
617: {
618: times(&s1);
619: }
620:
621: restarttimers()
622: {
623: times(&s2);
624: garbagetime += s2.tms_utime-s1.tms_utime;
625: }
626:
627: resettimers()
628: {
629: garbagetime = 0;
630: s2.tms_utime = s1.tms_utime = 0;
631: t2.tms_utime = t1.tms_utime = 0;
632: collected = collectedfrom = minorcollections = majorcollections = ML_INT(0);
633: }
634:
635:
636: timer()
637: {
638: times(×tamp);
639: g_usec = garbagetime % 60 * 1000000 / 60 * 2 + 1;
640: g_sec = garbagetime / 60 * 2 + 1;
641: t_usec = timestamp.tms_utime % 60 * 1000000 / 60 * 2 + 1;
642: t_sec = timestamp.tms_utime / 60 * 2 + 1;
643: }
644:
645: #endif /* V9 */
646:
647: int uniq(arg) int arg;
648: {int q, *p;
649: #define BASE(ptr) (((int**)(ptr))[0])
650: #define INDEX(ptr) ((((int*)(ptr))[1]-1)>>1)
651: #define NEXTP(ptr) (((int*)(ptr))[2])
652: for(q=arg;q!=1;q=NEXTP(q))
653: if ( INDEX(q) == -1)
654: {((int*)q)[-1]= BASE(q)[-1];
655: ((int**)q)[0][-1] = 0;
656: }
657: for(q=arg;q!=1;q=NEXTP(q))
658: if ( BASE(q)[-1] && INDEX(q)>=0 && BASE(q)[INDEX(q)])
659: {((int*)q)[-1]= BASE(q)[INDEX(q)];
660: BASE(q)[INDEX(q)] = 0;
661: }
662: p= &arg;
663: while (*p!=1)
664: if (((int**)*p)[0][(((int*)*p)[1]-1)/2])
665: *p = NEXTP(*p);
666: else {BASE(*p)[INDEX(*p)] = ((int*)*p)[-1];
667: ((int*)*p)[-1] = 3*16+1;
668: p = &NEXTP(*p);
669: }
670:
671: return arg;
672: }
673:
674: #ifdef ADVICE
675:
676: static char mallocbuf[0x10000], *mallocptr=mallocbuf;
677:
678: char *malloc(n) int n;
679: {char *p;
680: n = (n+3) & ~3;
681: if (mallocptr+n > mallocbuf+0x10000) die ("Too much malloc.");
682: p=mallocptr;
683: mallocptr+=n;
684: return p;
685: }
686:
687: char *free(){}
688:
689: char *realloc(){
690: die ("Didn't expect realloc.");
691: }
692:
693: char *calloc(n,m) int n,m;
694: {char *p = malloc(n*m); int i;
695: for(i=0;i<n;i++) p[i]=0;
696: return p;
697: }
698:
699: char *cfree() {}
700: #endif
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.