home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / sa104os2.zip / SATHR104.ZIP / SATHER / SYSTEM / GC / ALLCHBLK.C next >
C/C++ Source or Header  |  1994-05-19  |  11KB  |  360 lines
  1. /* 
  2.  * Copyright 1988, 1989 Hans-J. Boehm, Alan J. Demers
  3.  * Copyright (c) 1991-1994 by Xerox Corporation.  All rights reserved.
  4.  *
  5.  * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED
  6.  * OR IMPLIED.  ANY USE IS AT YOUR OWN RISK.
  7.  *
  8.  * Permission is hereby granted to use or copy this program
  9.  * for any purpose,  provided the above notices are retained on all copies.
  10.  * Permission to modify the code and to distribute modified code is granted,
  11.  * provided the above notices are retained, and a notice that the code was
  12.  * modified is included with the above copyright notice.
  13.  */
  14. /* Boehm, May 19, 1994 1:55 pm PDT */
  15.  
  16. #define DEBUG
  17. #undef DEBUG
  18. #include <stdio.h>
  19. #include "gc_priv.h"
  20.  
  21.  
  22. /**/
  23. /* allocate/free routines for heap blocks
  24. /* Note that everything called from outside the garbage collector
  25. /* should be prepared to abort at any point as the result of a signal.
  26. /**/
  27.  
  28. /*
  29.  * Free heap blocks are kept on a list sorted by address.
  30.  * The hb_hdr.hbh_sz field of a free heap block contains the length
  31.  * (in bytes) of the entire block.
  32.  * Neighbors are coalesced.
  33.  */
  34.  
  35. # define MAX_BLACK_LIST_ALLOC (2*HBLKSIZE)
  36.         /* largest block we will allocate starting on a black   */
  37.         /* listed block.  Must be >= HBLKSIZE.            */
  38.  
  39. struct hblk * GC_hblkfreelist = 0;
  40.  
  41. struct hblk *GC_savhbp = (struct hblk *)0;  /* heap block preceding next */
  42.                      /* block to be examined by   */
  43.                      /* GC_allochblk.                */
  44.  
  45. void GC_print_hblkfreelist()
  46. {
  47.     struct hblk * h = GC_hblkfreelist;
  48.     word total_free = 0;
  49.     hdr * hhdr = HDR(h);
  50.     word sz;
  51.     
  52.     while (h != 0) {
  53.         sz = hhdr -> hb_sz;
  54.         GC_printf2("0x%lx size %lu ", (unsigned long)h, (unsigned long)sz);
  55.         total_free += sz;
  56.         if (GC_is_black_listed(h, HBLKSIZE) != 0) {
  57.              GC_printf0("start black listed\n");
  58.         } else if (GC_is_black_listed(h, hhdr -> hb_sz) != 0) {
  59.              GC_printf0("partially black listed\n");
  60.         } else {
  61.              GC_printf0("not black listed\n");
  62.         }
  63.         h = hhdr -> hb_next;
  64.         hhdr = HDR(h);
  65.     }
  66.     GC_printf1("Total of %lu bytes on free list\n", (unsigned long)total_free);
  67. }
  68.  
  69. /* Initialize hdr for a block containing the indicated size and     */
  70. /* kind of objects.                            */
  71. /* Return FALSE on failure.                        */
  72. static bool setup_header(hhdr, sz, kind, flags)
  73. register hdr * hhdr;
  74. word sz;    /* object size in words */
  75. int kind;
  76. unsigned char flags;
  77. {
  78.     register word descr;
  79.     
  80.     /* Add description of valid object pointers */
  81.       if (!GC_add_map_entry(sz)) return(FALSE);
  82.       hhdr -> hb_map = GC_obj_map[sz > MAXOBJSZ? 0 : sz];
  83.       
  84.     /* Set size, kind and mark proc fields */
  85.       hhdr -> hb_sz = sz;
  86.       hhdr -> hb_obj_kind = kind;
  87.       hhdr -> hb_flags = flags;
  88.       descr = GC_obj_kinds[kind].ok_descriptor;
  89.       if (GC_obj_kinds[kind].ok_relocate_descr) descr += WORDS_TO_BYTES(sz);
  90.       hhdr -> hb_descr = descr;
  91.       
  92.     /* Clear mark bits */
  93.       GC_clear_hdr_marks(hhdr);
  94.       
  95.     hhdr -> hb_last_reclaimed = (unsigned short)GC_gc_no;
  96.     return(TRUE);
  97. }
  98.  
  99. /*
  100.  * Allocate (and return pointer to) a heap block
  101.  *   for objects of size sz words.
  102.  *
  103.  * NOTE: We set obj_map field in header correctly.
  104.  *       Caller is resposnsible for building an object freelist in block.
  105.  *
  106.  * We clear the block if it is destined for large objects, and if
  107.  * kind requires that newly allocated objects be cleared.
  108.  */
  109. struct hblk *
  110. GC_allochblk(sz, kind, flags)
  111. word sz;
  112. int kind;
  113. unsigned char flags;
  114. {
  115.     register struct hblk *thishbp;
  116.     register hdr * thishdr;        /* Header corr. to thishbp */
  117.     register struct hblk *hbp;
  118.     register hdr * hhdr;        /* Header corr. to hbp */
  119.     struct hblk *prevhbp;
  120.     register hdr * phdr;        /* Header corr. to prevhbp */
  121.     signed_word size_needed;    /* number of bytes in requested objects */
  122.     signed_word size_avail;    /* bytes available in this block    */
  123.     bool first_time = TRUE;
  124.  
  125.     size_needed = HBLKSIZE * OBJ_SZ_TO_BLOCKS(sz);
  126.  
  127.     /* search for a big enough block in free list */
  128.     hbp = GC_savhbp;
  129.     hhdr = HDR(hbp);
  130.     for(;;) {
  131.  
  132.         prevhbp = hbp;
  133.         phdr = hhdr;
  134.         hbp = (prevhbp == 0? GC_hblkfreelist : phdr->hb_next);
  135.         hhdr = HDR(hbp);
  136.  
  137.         if( prevhbp == GC_savhbp && !first_time) {
  138.             return(0);
  139.         }
  140.  
  141.         first_time = FALSE;
  142.  
  143.         if( hbp == 0 ) continue;
  144.  
  145.         size_avail = hhdr->hb_sz;
  146.         if (size_avail < size_needed) continue;
  147.         /* If the next heap block is obviously better, go on.    */
  148.         /* This prevents us from disassembling a single large block */
  149.         /* to get tiny blocks.                    */
  150.         {
  151.           signed_word next_size;
  152.           
  153.           thishbp = hhdr -> hb_next;
  154.           if (thishbp == 0) thishbp = GC_hblkfreelist; 
  155.           thishdr = HDR(thishbp);
  156.           next_size = (signed_word)(thishdr -> hb_sz);
  157.           if (next_size < size_avail
  158.               && next_size >= size_needed
  159.               && !GC_is_black_listed(thishbp, (word)size_needed)) {
  160.               continue;
  161.           }
  162.         }
  163.         if ( kind != UNCOLLECTABLE &&
  164.              (kind != PTRFREE || size_needed > MAX_BLACK_LIST_ALLOC)) {
  165.           struct hblk * lasthbp = hbp;
  166.           ptr_t search_end = (ptr_t)hbp + size_avail - size_needed;
  167.           signed_word eff_size_needed = ((flags & IGNORE_OFF_PAGE)?
  168.                               HBLKSIZE
  169.                               : size_needed);
  170.           
  171.           
  172.           while ((ptr_t)lasthbp <= search_end
  173.                  && (thishbp = GC_is_black_listed(lasthbp,
  174.                                        (word)eff_size_needed))) {
  175.             lasthbp = thishbp;
  176.           }
  177.           size_avail -= (ptr_t)lasthbp - (ptr_t)hbp;
  178.           thishbp = lasthbp;
  179.           if (size_avail >= size_needed && thishbp != hbp
  180.               && GC_install_header(thishbp)) {
  181.               /* Split the block at thishbp */
  182.                   thishdr = HDR(thishbp);
  183.                   /* GC_invalidate_map not needed, since we will    */
  184.                   /* allocate this block.                */
  185.               thishdr -> hb_next = hhdr -> hb_next;
  186.               thishdr -> hb_sz = size_avail;
  187.               hhdr -> hb_sz = (ptr_t)thishbp - (ptr_t)hbp;
  188.               hhdr -> hb_next = thishbp;
  189.           /* Advance to thishbp */
  190.               prevhbp = hbp;
  191.               phdr = hhdr;
  192.               hbp = thishbp;
  193.               hhdr = thishdr;
  194.           } else if (size_avail == 0
  195.                    && size_needed == HBLKSIZE
  196.                    && prevhbp != 0) {
  197. #        ifndef FIND_LEAK
  198.                 static unsigned count = 0;
  199.                 
  200.                 /* The block is completely blacklisted.  We need     */
  201.                 /* to drop some such blocks, since otherwise we spend */
  202.                 /* all our time traversing them if pointerfree    */
  203.                 /* blocks are unpopular.                */
  204.               /* A dropped block will be reconsidered at next GC.    */
  205.               if ((++count & 3) == 0) {
  206.                 /* Allocate and drop the block */
  207.                   if (GC_install_counts(hbp, hhdr->hb_sz)) {
  208.                     phdr -> hb_next = hhdr -> hb_next;
  209.                     (void) setup_header(
  210.                           hhdr,
  211.                             BYTES_TO_WORDS(hhdr->hb_sz - HDR_BYTES),
  212.                             PTRFREE, 0); /* Cant fail */
  213.                       if (GC_debugging_started) {
  214.                           BZERO(hbp + HDR_BYTES, hhdr->hb_sz - HDR_BYTES);
  215.                       }
  216.                     if (GC_savhbp == hbp) GC_savhbp = prevhbp;
  217.                   }
  218.                 /* Restore hbp to point at free block */
  219.                   hbp = prevhbp;
  220.                   hhdr = phdr;
  221.                   if (hbp == GC_savhbp) first_time = TRUE;
  222.               }
  223. #        endif
  224.           }
  225.         }
  226.         if( size_avail >= size_needed ) {
  227.         /* found a big enough block       */
  228.         /* let thishbp --> the block      */
  229.         /* set prevhbp, hbp to bracket it */
  230.             thishbp = hbp;
  231.             thishdr = hhdr;
  232.             if( size_avail == size_needed ) {
  233.             hbp = hhdr->hb_next;
  234.             hhdr = HDR(hbp);
  235.             } else {
  236.             hbp = (struct hblk *)
  237.                 (((word)thishbp) + size_needed);
  238.             if (!GC_install_header(hbp)) continue;
  239.             hhdr = HDR(hbp);
  240.             GC_invalidate_map(hhdr);
  241.             hhdr->hb_next = thishdr->hb_next;
  242.             hhdr->hb_sz = size_avail - size_needed;
  243.             }
  244.         /* remove *thishbp from hblk freelist */
  245.             if( prevhbp == 0 ) {
  246.             GC_hblkfreelist = hbp;
  247.             } else {
  248.             phdr->hb_next = hbp;
  249.             }
  250.         /* save current list search position */
  251.             GC_savhbp = hbp;
  252.         break;
  253.         }
  254.     }
  255.     
  256.     /* Notify virtual dirty bit implementation that we are about to write. */
  257.         GC_write_hint(thishbp);
  258.     
  259.     /* Add it to map of valid blocks */
  260.         if (!GC_install_counts(thishbp, (word)size_needed)) return(0);
  261.         /* This leaks memory under very rare conditions. */
  262.             
  263.     /* Set up header */
  264.         if (!setup_header(thishdr, sz, kind, flags)) {
  265.             GC_remove_counts(thishbp, (word)size_needed);
  266.             return(0); /* ditto */
  267.         }
  268.         
  269.     /* Clear block if necessary */
  270.     if (GC_debugging_started
  271.         || sz > MAXOBJSZ && GC_obj_kinds[kind].ok_init) {
  272.         BZERO(thishbp + HDR_BYTES,  size_needed - HDR_BYTES);
  273.     }
  274.     
  275.     return( thishbp );
  276. }
  277.  
  278. struct hblk * GC_freehblk_ptr = 0;  /* Search position hint for GC_freehblk */
  279.  
  280. /*
  281.  * Free a heap block.
  282.  *
  283.  * Coalesce the block with its neighbors if possible.
  284.  *
  285.  * All mark words are assumed to be cleared.
  286.  */
  287. void
  288. GC_freehblk(p)
  289. register struct hblk *p;
  290. {
  291. register hdr *phdr;    /* Header corresponding to p */
  292. register struct hblk *hbp, *prevhbp;
  293. register hdr *hhdr, *prevhdr;
  294. register signed_word size;
  295.  
  296.     /* GC_savhbp may become invalid due to coalescing.  Clear it. */
  297.     GC_savhbp = (struct hblk *)0;
  298.  
  299.     phdr = HDR(p);
  300.     size = phdr->hb_sz;
  301.     size = HBLKSIZE * OBJ_SZ_TO_BLOCKS(size);
  302.     GC_remove_counts(p, (word)size);
  303.     phdr->hb_sz = size;
  304.     GC_invalidate_map(phdr);
  305.     prevhbp = 0;
  306.     
  307.     /* The following optimization was suggested by David Detlefs.    */
  308.     /* Note that the header cannot be NIL, since there cannot be an    */
  309.     /* intervening  call to GC_freehblk without resetting        */
  310.     /* GC_freehblk_ptr.                            */
  311.     if (GC_freehblk_ptr != 0 &&
  312.         HDR(GC_freehblk_ptr)->hb_map == GC_invalid_map &&
  313.         (ptr_t)GC_freehblk_ptr < (ptr_t)p) {
  314.       hbp = GC_freehblk_ptr;
  315.     } else {
  316.       hbp = GC_hblkfreelist;
  317.     };
  318.     hhdr = HDR(hbp);
  319.  
  320.     while( (hbp != 0) && (hbp < p) ) {
  321.     prevhbp = hbp;
  322.     prevhdr = hhdr;
  323.     hbp = hhdr->hb_next;
  324.     hhdr = HDR(hbp);
  325.     }
  326.     GC_freehblk_ptr = prevhbp;
  327.     
  328.     /* Check for duplicate deallocation in the easy case */
  329.       if (hbp != 0 && (ptr_t)p + size > (ptr_t)hbp
  330.         || prevhbp != 0 && (ptr_t)prevhbp + prevhdr->hb_sz > (ptr_t)p) {
  331.         GC_printf1("Duplicate large block deallocation of 0x%lx\n",
  332.                (unsigned long) p);
  333.         GC_printf2("Surrounding free blocks are 0x%lx and 0x%lx\n",
  334.                   (unsigned long) prevhbp, (unsigned long) hbp);
  335.       }
  336.  
  337.     /* Coalesce with successor, if possible */
  338.       if( (((word)p)+size) == ((word)hbp) ) {
  339.     phdr->hb_next = hhdr->hb_next;
  340.     phdr->hb_sz += hhdr->hb_sz;
  341.     GC_remove_header(hbp);
  342.       } else {
  343.     phdr->hb_next = hbp;
  344.       }
  345.  
  346.     
  347.     if( prevhbp == 0 ) {
  348.     GC_hblkfreelist = p;
  349.     } else if( (((word)prevhbp) + prevhdr->hb_sz)
  350.                  == ((word)p) ) {
  351.       /* Coalesce with predecessor */
  352.     prevhdr->hb_next = phdr->hb_next;
  353.     prevhdr->hb_sz += phdr->hb_sz;
  354.     GC_remove_header(p);
  355.     } else {
  356.     prevhdr->hb_next = p;
  357.     }
  358. }
  359.  
  360.