home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / cpp_libs / intrvews / xgrab.lha / xgrab / ui / GC / alloc.c next >
Encoding:
C/C++ Source or Header  |  1990-04-25  |  21.8 KB  |  793 lines
  1. /*
  2.  * This file contains the functions:
  3.  *    void new_hblk(n)
  4.  *    static void clear_marks()
  5.  *      mark(alignment)
  6.  *      mark_all(b,t,alignment)
  7.  *    void gcollect()
  8.  *    expand_hp: func[val Short] val Void
  9.  *    struct obj * _allocobj(sz)
  10.  *    struct obj * _allocaobj(sz)
  11.  *
  12.  */
  13.  
  14.  
  15. # include <stdio.h>
  16. # include <signal.h>
  17. # include <sys/types.h>
  18. # include <sys/times.h>
  19. # include "gc.h"
  20.  
  21. /* Leaving these defined enables output to stderr.  In order of */
  22. /* increasing verbosity:                                        */
  23. #define REPORT_FAILURE   /* Print values that looked "almost" like pointers */
  24. #undef REPORT_FAILURE
  25. #define DEBUG            /* Verbose debugging output */
  26. #undef DEBUG
  27. #define DEBUG2           /* EXTREMELY verbose debugging output */
  28. #undef DEBUG2
  29. #define USE_STACK       /* Put mark stack onto process stack.  This assumes */
  30.             /* that it's safe to put data below the stack ptr,  */
  31.             /* and that the system will expand the stack as     */
  32.             /* necessary.  This is known to be true under Sun   */
  33.             /* UNIX (tm) and Vax Berkeley UNIX.  It is also     */
  34.             /* known to be false under some other UNIX          */
  35.             /* implementations.                                 */
  36. #undef USE_HEAP
  37. #ifdef RT
  38. #   define USE_HEAP
  39. #   undef USE_STACK
  40. #endif
  41. #ifdef MIPS
  42. #   define USE_HEAP
  43. #   undef USE_STACK
  44. #endif
  45.  
  46. /*
  47.  * This is an attempt at a garbage collecting storage allocator
  48.  * that should run on most UNIX systems.  The garbage
  49.  * collector is overly conservative in that it may fail to reclaim
  50.  * inaccessible storage.  On the other hand, it does not assume
  51.  * any runtime tag information.
  52.  * We make the following assumptions:
  53.  *  1.  We are running under something that looks like Berkeley UNIX,
  54.  *      on one of the supported architectures.
  55.  *  2.  For every accessible object, a pointer to it is stored in
  56.  *          a) the stack segment, or
  57.  *          b) the data or bss segment, or
  58.  *          c) the registers, or
  59.  *          d) an accessible block.
  60.  *
  61.  */
  62.  
  63. /*
  64.  * Separate free lists are maintained for different sized objects
  65.  * up to MAXOBJSZ or MAXAOBJSZ.
  66.  * The lists objfreelist[i] contain free objects of size i which may
  67.  * contain nested pointers.  The lists aobjfreelist[i] contain free
  68.  * atomic objects, which may not contain nested pointers.
  69.  * The call allocobj(i) insures that objfreelist[i] points to a non-empty
  70.  * free list it returns a pointer to the first entry on the free list.
  71.  * Allocobj may be called to allocate an object of (small) size i
  72.  * as follows:
  73.  *
  74.  *            opp = &(objfreelist[i]);
  75.  *            if (*opp == (struct obj *)0) allocobj(i);
  76.  *            ptr = *opp;
  77.  *            *opp = ptr->next;
  78.  *
  79.  * The call to allocobj may be replaced by a call to _allocobj if it
  80.  * is made from C, or if C register save conventions are sufficient.
  81.  * Note that this is very fast if the free list is non-empty; it should
  82.  * only involve the execution of 4 or 5 simple instructions.
  83.  * All composite objects on freelists are cleared, except for
  84.  * their first longword.
  85.  */
  86.  
  87. /*
  88.  *  The allocator uses allochblk to allocate large chunks of objects.
  89.  * These chunks all start on addresses which are multiples of
  90.  * HBLKSZ.  All starting addresses are maintained on a contiguous
  91.  * list so that they can be traversed in the sweep phase of garbage collection.
  92.  * This makes it possible to check quickly whether an
  93.  * arbitrary address corresponds to an object administered by the
  94.  * allocator.
  95.  *  We make the (probably false) claim that this can be interrupted
  96.  * by a signal with at most the loss of some chunk of memory.
  97.  */
  98.  
  99. /* Declarations for fundamental data structures.  These are grouped */
  100. /* together, so that the collector can skip over them.              */
  101. /* This relies on some assumptions about the compiler that are not  */
  102. /* guaranteed valid, but ...                                        */
  103.  
  104. long heapsize = 0;      /* Heap size in bytes */
  105.  
  106. long non_gc_bytes = 0;  /* Number of bytes not intended to be collected */
  107.  
  108. char copyright[] = "Copyright 1988,1989 Hans-J. Boehm and Alan J. Demers";
  109.  
  110. /* Return a rough approximation to the stack pointer.  A hack,  */
  111. /* but it's semi-portable.                                      */
  112. word * get_current_sp()
  113. {
  114.     word x;
  115.     return(&x);
  116. }
  117.  
  118. /*
  119.  * Allocate a new heapblock for objects of size n.
  120.  * Add all of the heapblock's objects to the free list for objects
  121.  * of that size.  A negative n requests atomic objects.
  122.  */
  123. void new_hblk(n)
  124. long n;
  125. {
  126.     register word *p,
  127.           *r;
  128.     word *last_object;        /* points to last object in new hblk    */
  129.     register struct hblk *h;    /* the new heap block            */
  130.     register long abs_sz;    /* |n|    */
  131.     register int i;
  132.  
  133. #   ifdef PRINTSTATS
  134.     if ((sizeof (struct hblk)) > HBLKSIZE) {
  135.         abort("HBLK SZ inconsistency");
  136.         }
  137. #   endif
  138.  
  139.   /* Allocate a new heap block */
  140.     h = allochblk(n);
  141.  
  142.   /* Add it to hblklist */
  143.     add_hblklist(h);
  144.  
  145.   /* Add objects to free list */
  146.     abs_sz = abs(n);
  147.     p = &(h -> hb_body[abs_sz]);    /* second object in *h    */
  148.     r = &(h -> hb_body[0]);           /* One object behind p    */
  149.     last_object = ((word *)((char *)h + HBLKSIZE)) - abs_sz;
  150.                 /* Last place for last object to start */
  151.  
  152.   /* make a list of all objects in *h with head as last object */
  153.     while (p <= last_object) {
  154.       /* current object's link points to last object */
  155.     ((struct obj *)p) -> obj_link = (struct obj *)r;
  156.     r = p;
  157.     p += abs_sz;
  158.     }
  159.     p -= abs_sz;            /* p now points to last object */
  160.  
  161.   /*
  162.    * put p (which is now head of list of objects in *h) as first
  163.    * pointer in the appropriate free list for this size.
  164.    */
  165.     if (n < 0) {
  166.     ((struct obj *)(h -> hb_body)) -> obj_link = aobjfreelist[abs_sz];
  167.     aobjfreelist[abs_sz] = ((struct obj *)p);
  168.     } else {
  169.     ((struct obj *)(h -> hb_body)) -> obj_link = objfreelist[abs_sz];
  170.     objfreelist[abs_sz] = ((struct obj *)p);
  171.     }
  172.  
  173.   /*
  174.    * Set up mask in header to facilitate alignment checks
  175.    * See "gc.h" for a description of how this works.
  176.    */
  177. #   ifndef RT
  178.     switch (abs_sz) {
  179.         case 1:
  180.         h -> hb_mask = 0x3;
  181.         break;
  182.         case 2:
  183.         h -> hb_mask = 0x7;
  184.         break;
  185.         case 4:
  186.         h -> hb_mask = 0xf;
  187.         break;
  188.         case 8:
  189.         h -> hb_mask = 0x1f;
  190.         break;
  191.         case 16:
  192.         h -> hb_mask = 0x3f;
  193.         break;
  194.         /* By default it remains set to a negative value */
  195.     }
  196. #   else
  197.       /* the 4.2 pcc C compiler did not produce correct code for the switch */
  198.     if (abs_sz == 1)    { h -> hb_mask = 0x3; }
  199.     else if (abs_sz == 2)    { h -> hb_mask = 0x7; }
  200.     else if (abs_sz == 4)    { h -> hb_mask = 0xf; }
  201.     else if (abs_sz == 8)    { h -> hb_mask = 0x1f; }
  202.     else if (abs_sz == 16)    { h -> hb_mask = 0x3f; }
  203.     /* else skip; */
  204. #   endif
  205.  
  206. #   ifdef DEBUG
  207.     printf("Allocated new heap block at address 0x%X\n",
  208.         h);
  209. #   endif
  210. }
  211.  
  212.  
  213. /* some more variables */
  214.  
  215. extern long mem_found;  /* Number of reclaimed longwords */
  216.             /* after garbage collection      */
  217.  
  218. extern long atomic_in_use, composite_in_use;
  219. extern errno;
  220.  
  221. /*
  222.  * Clear mark bits in all allocated heap blocks
  223.  */
  224. static void clear_marks()
  225. {
  226.     register int j;
  227.     register struct hblk **p;
  228.     register struct hblk *q;
  229.  
  230. # ifdef HBLK_MAP
  231.     for (q = (struct hblk *) heapstart; ((char*)q) < heaplim; q++)
  232.       if (is_hblk(q)) {
  233. # else
  234.     for (p = hblklist; p < last_hblk; p++) {
  235.     q = *p;
  236. # endif
  237.         for (j = 0; j < MARK_BITS_SZ; j++) {
  238.         q -> hb_marks[j] = 0;
  239.         }
  240.     }
  241. }
  242.  
  243. /* Limits of stack for mark routine.  Set by caller to mark.           */
  244. /* All items between mark_stack_top and mark_stack_bottom-1 still need */
  245. /* to be marked.  All items on the stack satisfy quicktest.  They do   */
  246. /* not necessarily reference real objects.                             */
  247. word * mark_stack_bottom;
  248. word * mark_stack_top;
  249.  
  250. #ifdef USE_STACK
  251. # define STACKGAP 1024 /* Gap in longwords between hardware stack and    */
  252.                /* the mark stack.                */
  253.                /* Must suffice for printf calls and signal      */
  254.                /* handling.                    */
  255. #endif
  256.  
  257.  
  258. #ifdef USE_STACK
  259. #   define PUSH_MS(ptr) *(--mark_stack_top) = (word) ptr
  260. #   define NOT_DONE(a,b) (a < b)
  261. #else
  262. # ifdef USE_HEAP
  263.     char *cur_break = 0;
  264.  
  265. #   define STACKINCR 0x4000
  266. #   define PUSH_MS(ptr)                         \
  267.     mark_stack_top++;                                               \
  268.     if ((char*)mark_stack_top >= cur_break) {             \
  269.         if (sbrk(STACKINCR) == -1) {                \
  270.         fprintf(stderr, "sbrk failed, code = %d\n",errno);      \
  271.         exit(1);                        \
  272.         } else {                            \
  273.         cur_break += STACKINCR;                                \
  274.         }                                \
  275.     }                                \
  276.     *mark_stack_top = (word) ptr
  277. #   define NOT_DONE(a,b) (a > b)
  278. # else
  279.     --> where does the mark stack go? <--
  280. # endif
  281. #endif
  282.  
  283.  
  284. /* Mark all objects corresponding to pointers between mark_stack_bottom */
  285. /* and mark_stack_bottom.  Assume that nested pointers are aligned      */
  286. /* on alignment-byte boundaries.                    */
  287. mark(alignment)
  288. int alignment;
  289. {
  290.   register long sz;
  291.   extern char end, etext;
  292.   register struct obj *p; /* pointer to current object to be marked */
  293.  
  294.   while (NOT_DONE(mark_stack_top,mark_stack_bottom)) {
  295.       register long word_no;
  296.       register long mask;
  297.       register struct hblk * h;
  298.  
  299. #    ifdef USE_STACK
  300.       p = (struct obj *)(*mark_stack_top++);
  301. #    else
  302. #     ifdef USE_HEAP
  303.     p = (struct obj *)(*mark_stack_top--);
  304. #     else
  305.     --> fixit <--
  306. #     endif
  307. #    endif
  308.  
  309.   /* if not a pointer to obj on heap, skip it */
  310.     if (((char *) p) >= heaplim) {
  311.     continue;
  312.     }
  313.  
  314.     h = HBLKPTR(p);
  315.  
  316. # ifndef INTERIOR_POINTERS
  317.     /* Check mark bit first, since this test is much more likely to */
  318.     /* fail than later ones.                                        */
  319.       word_no = ((word *)p) - ((word *)h);
  320.       if (mark_bit(h, word_no)) {
  321.     continue;
  322.       }
  323. # endif
  324.  
  325. # ifdef INTERIOR_POINTERS
  326.     if (!is_hblk(h)) {
  327.     char m = get_map(h);
  328.     while (m > 0 && m < 0x7f) {
  329.         h -= m;
  330.         m = get_map(h);
  331.     }
  332.     if (m == HBLK_INVALID) {
  333. #         ifdef REPORT_FAILURE
  334.         printf("-> Pointer to non-heap loc: %X\n", p);
  335. #         endif
  336.       continue;
  337.     }
  338.     }
  339.     if (((long)p) - ((long)h) < sizeof (struct hblkhdr)) {
  340.     continue;
  341.     }
  342. # else
  343.     if (!is_hblk(h)) {
  344. #    ifdef REPORT_FAILURE
  345.       printf("-> Pointer to non-heap loc: %X\n", p);
  346. #       endif
  347.     continue;
  348.     }
  349. # endif
  350.     sz = HB_SIZE(h);
  351.     mask = h -> hb_mask;
  352.  
  353. # ifdef INTERIOR_POINTERS
  354.     word_no = get_word_no(p,h,sz,mask);
  355. # else
  356.     if (!is_proper_obj(p,h,sz,mask)) {
  357. #       ifdef REPORT_FAILURE
  358.         printf("-> Bad pointer to heap block: %X,sz = %d\n",p,sz);
  359. #    endif
  360.     continue;
  361.     }
  362. # endif
  363.  
  364.     if (word_no + sz > BYTES_TO_WORDS(HBLKSIZE)
  365.     && word_no != BYTES_TO_WORDS(sizeof(struct hblkhdr))
  366.        /* Not first object */) {
  367.       /* 
  368.        * Note that we dont necessarily check for pointers to the block header.
  369.        * This doesn't cause any problems, since we have mark
  370.        * bits allocated for such bogus objects.
  371.        * We have to check for references past the last object, since
  372.        * marking from uch an "object" could cause an exception.
  373.        */
  374. #       ifdef REPORT_FAILURE
  375.         printf("-> Bad pointer to heap block: %X,sz = %d\n",p,sz);
  376. #    endif
  377.     continue;
  378.     }
  379.  
  380. #   ifdef INTERIOR_POINTERS
  381.       if (mark_bit(h, word_no)) {
  382.     continue;
  383.       }
  384. #   endif
  385.  
  386. #   ifdef DEBUG2
  387.     printf("*** set bit for heap %x, word %x\n",h,word_no);
  388. #   endif
  389.     set_mark_bit(h, word_no);
  390.     if (h -> hb_sz < 0) {
  391.     /* Atomic object */
  392.       continue;
  393.     }
  394.     {
  395.       /* Mark from fields inside the object */
  396.     register struct obj ** q;
  397.     register struct obj * r;
  398.     register long lim;   /* Should be struct obj **, but we're out of */
  399.                  /* A registers on a 68000.                   */
  400.  
  401. #       ifdef INTERIOR_POINTERS
  402.       /* Adjust p, so that it's properly aligned */
  403. #           ifdef DEBUG
  404.           if (p != ((struct obj *)(((word *)h) + word_no))) {
  405.         printf("Adjusting from %X to ", p);
  406.         p = ((struct obj *)(((word *)h) + word_no));
  407.         printf("%X\n", p);
  408.           } else {
  409.         p = ((struct obj *)(((word *)h) + word_no));
  410.           }
  411. #           else
  412.           p = ((struct obj *)(((word *)h) + word_no));
  413. #           endif
  414. #       endif
  415. #       ifdef UNALIGNED
  416.       lim = ((long)(&(p -> obj_component[sz]))) - 3;
  417. #       else
  418.       lim = (long)(&(p -> obj_component[sz]));
  419. #       endif
  420.     for (q = (struct obj **)(&(p -> obj_component[0]));
  421.                     q < (struct obj **)lim;) {
  422.         r = *q;
  423.         if (quicktest(r)) {
  424. #               ifdef DEBUG2
  425.             printf("Found plausible nested pointer");
  426.             printf(": 0x%X inside 0x%X at 0x%X\n", r, p, q);
  427. #               endif
  428.         PUSH_MS(((word)r));
  429.         }
  430. #           ifdef UNALIGNED
  431.         q = ((struct obj **)(((long)q)+alignment));
  432. #           else
  433.         q++;
  434. #           endif 
  435.     }
  436.     }
  437.   }
  438. }
  439.  
  440.  
  441. /*********************************************************************/
  442. /* Mark all locations reachable via pointers located between b and t */
  443. /* b is the first location to be checked. t is one past the last     */
  444. /* location to be checked.                                           */
  445. /* Assume that pointers are aligned on alignment-byte                */
  446. /* boundaries.                                 */
  447. /*********************************************************************/
  448. void mark_all(b, t, alignment)
  449. word * b;
  450. word * t;
  451. int alignment;
  452. {
  453.     register word *p;
  454.     register word r;
  455.     register word *lim;
  456.  
  457. #   ifdef DEBUG
  458.     printf("Checking for pointers between 0x%X and 0x%X\n",
  459.         b, t);
  460. #   endif
  461.  
  462.     /* Allocate mark stack, leaving a hole below the real stack. */
  463. #     ifdef USE_STACK
  464.     mark_stack_bottom = get_current_sp() - STACKGAP;
  465.     mark_stack_top = mark_stack_bottom;
  466. #     else
  467. #       ifdef USE_HEAP
  468.       mark_stack_bottom = (word *) sbrk(0); /* current break */
  469.       cur_break = (char *) mark_stack_bottom;
  470.       mark_stack_top = mark_stack_bottom;
  471. #       else
  472.       -> then where should the mark stack go ? <-
  473. #       endif
  474. #     endif
  475.  
  476.   /* Round b down so it is properly aligned */
  477. #   ifdef UNALIGNED
  478.       if (alignment == 2) {
  479.         b = (word *)(((long) b) & ~1);
  480.       } else if (alignment == 4) {
  481.     b = (word *)(((long) b) & ~3);
  482.       } else if (alignment != 1) {
  483.     fprintf(stderr, "Bad alignment parameter to mark_all\n");
  484.     abort(alignment);
  485.       }
  486. #   else
  487.       b = (word *)(((long) b) & ~3);
  488. #   endif
  489.  
  490.   /* check all pointers in range and put on mark_stack if quicktest true */
  491.     lim = t - 1 /* longword */;
  492.     for (p = b; ((unsigned) p) <= ((unsigned) lim);) {
  493.         /* Coercion to unsigned in the preceding appears to be necessary */
  494.         /* due to a bug in the 4.2BSD C compiler.                        */
  495.     r = *p;
  496.     if (quicktest(r)) {
  497. #           ifdef DEBUG2
  498.         printf("Found plausible pointer: %X\n", r);
  499. #           endif
  500.         PUSH_MS(r);         /* push r onto the mark stack */
  501.     }
  502. #       ifdef UNALIGNED
  503.       p = (word *)(((char *)p) + alignment);
  504. #       else
  505.       p++;
  506. #       endif
  507.     }
  508.     if (mark_stack_top != mark_stack_bottom) mark(alignment);
  509.  
  510. #   ifdef USE_HEAP
  511.       brk(mark_stack_bottom);     /* reset break to where it was before */
  512.       cur_break = (char *) mark_stack_bottom;
  513. #   endif
  514. }
  515.  
  516. /*
  517.  * Restore inaccessible objects to the free list 
  518.  * update mem_found (number of reclaimed longwords after garbage collection)
  519.  */
  520. void gcollect()
  521. {
  522.     extern void mark_regs();
  523.  
  524.     extern int holdsigs();  /* disables non-urgent signals - see the    */
  525.                 /* file "callcc.c"                */
  526.  
  527.     long Omask = 0;     /* mask to restore signal mask to after
  528.              * critical section.
  529.              */
  530.  
  531. #   ifdef PRINTTIMES
  532.       /* some debugging values */
  533.     double start_time = 0;
  534.     double mark_time = 0;
  535.     double done_time = 0;
  536.     static struct tms time_buf;
  537. #       define FTIME \
  538.          (((double)(time_buf.tms_utime + time_buf.tms_stime))/FLOAT_HZ)
  539.  
  540.       /* Get starting time */
  541.         times(&time_buf);
  542.         start_time = FTIME;
  543. #   endif
  544.  
  545. #   ifdef DEBUG2
  546.     printf("Here we are in gcollect\n"); 
  547. #   endif
  548.  
  549.     /* Don't want to deal with signals in the middle so mask 'em out */
  550.     Omask = holdsigs();
  551.  
  552.     /* Mark from all roots.  */
  553.     mark_roots();
  554.  
  555.     /* Clear free list mark bits, in case they got accidentally marked   */
  556.     /* Note: HBLKPTR(p) == pointer to head of block containing *p        */
  557.     /* Also subtract memory remaining from mem_found count.              */
  558.     /* Note that composite objects on free list are cleared.             */
  559.     /* Thus accidentally marking a free list is not a problem;  only     */
  560.     /* objects on the list itself will be marked, and that's fixed here. */
  561.       {
  562.     register int size;        /* current object size        */
  563.     register struct obj * p;    /* pointer to current object    */
  564.     register struct hblk * q;    /* pointer to block containing *p */
  565.     register int word_no;           /* "index" of *p in *q          */
  566. #       ifdef REPORT_FAILURE
  567.         int prev_failure = 0;
  568. #       endif
  569.  
  570.     for (size = 1; size < MAXOBJSZ; size++) {
  571.         for (p= objfreelist[size]; p != ((struct obj *)0); p=p->obj_link){
  572.         q = HBLKPTR(p);
  573.         word_no = (((word *)p) - ((word *)q));
  574. #               ifdef REPORT_FAILURE
  575.           if (!prev_failure && mark_bit(q, word_no)) {
  576.             printf("-> Pointer to composite free list: %X,sz = %d\n",
  577.                 p, size);
  578.             prev_failure = 1;
  579.           }
  580. #               endif
  581.         clear_mark_bit(q, word_no);
  582.         mem_found -= size;
  583.         }
  584. #           ifdef REPORT_FAILURE
  585.         prev_failure = 0;
  586. #           endif
  587.     }
  588.     for (size = 1; size < MAXAOBJSZ; size++) {
  589.         for(p= aobjfreelist[size]; p != ((struct obj *)0); p=p->obj_link){
  590.         q = HBLKPTR(p);
  591.         word_no = (((long *)p) - ((long *)q));
  592. #               ifdef REPORT_FAILURE
  593.           if (!prev_failure && mark_bit(q, word_no)) {
  594.             printf("-> Pointer to atomic free list: %X,sz = %d\n",
  595.                 p, size);
  596.             prev_failure = 1;
  597.           }
  598. #               endif
  599.         clear_mark_bit(q, word_no);
  600.         mem_found -= size;
  601.         }
  602. #           ifdef REPORT_FAILURE
  603.         prev_failure = 0;
  604. #           endif
  605.     }
  606.       }
  607.  
  608. #   ifdef PRINTTIMES
  609.       /* Get intermediate time */
  610.     times(&time_buf);
  611.     mark_time = FTIME;
  612. #   endif
  613.  
  614. #   ifdef PRINTSTATS
  615.     printf("Bytes recovered before reclaim - f.l. count = %d\n",
  616.            WORDS_TO_BYTES(mem_found));
  617. #   endif
  618.  
  619.   /* Reconstruct free lists to contain everything not marked */
  620.     reclaim();
  621.  
  622.   /* clear mark bits in all allocated heap blocks */
  623.     clear_marks();
  624.  
  625. #   ifdef PRINTSTATS
  626.     printf("Reclaimed %d bytes in heap of size %d bytes\n",
  627.            WORDS_TO_BYTES(mem_found), heapsize);
  628.     printf("%d (atomic) + %d (composite) bytes in use\n",
  629.            WORDS_TO_BYTES(atomic_in_use),
  630.            WORDS_TO_BYTES(composite_in_use));
  631. #   endif
  632.  
  633.   /*
  634.    * What follows is somewhat heuristic.  Constant may benefit
  635.    * from tuning ...
  636.    */
  637.     if (WORDS_TO_BYTES(mem_found) * 4 < heapsize) {
  638.       /* Less than about 1/4 of available memory was reclaimed - get more */
  639.     {
  640.         long size_to_get = HBLKSIZE + hincr * HBLKSIZE;
  641.         struct hblk * thishbp;
  642.         char * nheaplim;
  643.  
  644.         thishbp = HBLKPTR(((unsigned)sbrk(0))+HBLKSIZE-1 );
  645.         nheaplim = (char *) (((unsigned)thishbp) + size_to_get);
  646.         if( ((char *) brk(nheaplim)) == ((char *)-1) ) {
  647.         write(2,"Out of memory, trying to continue ...\n",38);
  648.         } else {
  649.         heaplim = nheaplim;
  650.         thishbp->hb_sz = 
  651.             BYTES_TO_WORDS(size_to_get - sizeof(struct hblkhdr));
  652.         freehblk(thishbp);
  653.         heapsize += size_to_get;
  654.         update_hincr;
  655.         }
  656. #           ifdef PRINTSTATS
  657.         printf("Gcollect: needed to increase heap size by %d\n",
  658.                size_to_get);
  659. #           endif
  660.     }
  661.     }
  662.  
  663.    /* Reset mem_found for next collection */
  664.      mem_found = 0;
  665.  
  666.   /* Reenable signals */
  667.     sigsetmask(Omask);
  668.  
  669.   /* Get final time */
  670. #   ifdef PRINTTIMES
  671.     times(&time_buf);
  672.     done_time = FTIME;
  673.     printf("Garbage collection took %7.2f + %7.2f secs\n",
  674.            mark_time - start_time, done_time - mark_time);
  675. #   endif
  676. }
  677.  
  678. /*
  679.  * this explicitly increases the size of the heap.  It is used
  680.  * internally, but my also be invoked directly by the user.
  681.  * The argument is in units of HBLKSIZE.
  682.  */
  683. void expand_hp(n)
  684. int n;
  685. {
  686.     struct hblk * thishbp = HBLKPTR(((unsigned)sbrk(0))+HBLKSIZE-1 );
  687.     extern int holdsigs();
  688.     int Omask;
  689.  
  690.     /* Don't want to deal with signals in the middle of this */
  691.     Omask = holdsigs();
  692.  
  693.     heaplim = (char *) (((unsigned)thishbp) + n * HBLKSIZE);
  694.     if (n > 2*hincr) {
  695.     hincr = n/2;
  696.     }
  697.     if( ((char *) brk(heaplim)) == ((char *)-1) ) {
  698.     write(2,"Out of Memory!\n",15);
  699.     exit(-1);
  700.     }
  701. #   ifdef PRINTSTATS
  702.     printf("Voluntarily increasing heap size by %d\n",
  703.            n*HBLKSIZE);
  704. #   endif
  705.     thishbp->hb_sz = BYTES_TO_WORDS(n * HBLKSIZE - sizeof(struct hblkhdr));
  706.     freehblk(thishbp);
  707.     heapsize += ((char *)heaplim) - ((char *)thishbp);
  708.     /* Reenable signals */
  709.     sigsetmask(Omask);
  710. }
  711.  
  712.  
  713. extern int dont_gc;  /* Unsafe to start garbage collection */
  714.  
  715. /*
  716.  * Make sure the composite object free list for sz is not empty.
  717.  * Return a pointer to the first object on the free list.
  718.  * The object MUST BE REMOVED FROM THE FREE LIST BY THE CALLER.
  719.  *
  720.  * note: _allocobj
  721.  */
  722. struct obj * _allocobj(sz)
  723. long sz;
  724. {
  725.     if (sz == 0) return((struct obj *)0);
  726.  
  727. #   ifdef DEBUG2
  728.     printf("here we are in _allocobj\n");
  729. #   endif
  730.  
  731.     if (objfreelist[sz] == ((struct obj *)0)) {
  732.       if (hblkfreelist == ((struct hblk *)0) && !dont_gc) {
  733.     if (GC_DIV * non_gc_bytes < GC_MULT * heapsize) {
  734. #         ifdef DEBUG
  735.         printf("Calling gcollect\n");
  736. #         endif
  737.       gcollect();
  738.     } else {
  739.       expand_hp(NON_GC_HINCR);
  740.     }
  741.       }
  742.       if (objfreelist[sz] == ((struct obj *)0)) {
  743. #       ifdef DEBUG
  744.         printf("Calling new_hblk\n");
  745. #    endif
  746.       new_hblk(sz);
  747.       }
  748.     }
  749. #   ifdef DEBUG2
  750.     printf("Returning %x from _allocobj\n",objfreelist[sz]);
  751.     printf("Objfreelist[%d] = %x\n",sz,objfreelist[sz]);
  752. #   endif
  753.     return(objfreelist[sz]);
  754. }
  755.  
  756. /*
  757.  * Make sure the atomic object free list for sz is not empty.
  758.  * Return a pointer to the first object on the free list.
  759.  * The object MUST BE REMOVED FROM THE FREE LIST BY THE CALLER.
  760.  *
  761.  * note: this is called by allocaobj (see the file mach_dep.c)
  762.  */
  763. struct obj * _allocaobj(sz)
  764. long sz;
  765. {
  766.     if (sz == 0) return((struct obj *)0);
  767.  
  768.     if (aobjfreelist[sz] == ((struct obj *) 0)) {
  769.       if (hblkfreelist == ((struct hblk *)0) && !dont_gc) {
  770.     if (GC_DIV * non_gc_bytes < GC_MULT * heapsize) {
  771. #         ifdef DEBUG
  772.         printf("Calling gcollect\n");
  773. #         endif
  774.       gcollect();
  775.     } else {
  776.       expand_hp(NON_GC_HINCR);
  777.     }
  778.       }
  779.       if (aobjfreelist[sz] == ((struct obj *) 0)) {
  780.       new_hblk(-sz);
  781.       }
  782.     }
  783.     return(aobjfreelist[sz]);
  784. }
  785.  
  786. # ifdef SPARC
  787.   put_mark_stack_bottom(val)
  788.   long val;
  789.   {
  790.     mark_stack_bottom = (word *)val;
  791.   }
  792. # endif
  793.