/[cmucl]/src/lisp/gencgc.c
ViewVC logotype

Diff of /src/lisp/gencgc.c

Parent Directory Parent Directory | Revision Log Revision Log | View Patch Patch

revision 1.95.2.1 by rtoy, Wed May 14 16:12:06 2008 UTC revision 1.95.2.1.2.8 by rtoy, Tue May 5 17:31:18 2009 UTC
# Line 247  unsigned counters_verbose = 0; Line 247  unsigned counters_verbose = 0;
247   * To enable the use of page protection to help avoid the scavenging   * To enable the use of page protection to help avoid the scavenging
248   * of pages that don't have pointers to younger generations.   * of pages that don't have pointers to younger generations.
249   */   */
 #if defined(DARWIN) && defined(__i386__)  
 boolean enable_page_protection = FALSE;  
 #else  
250  boolean enable_page_protection = TRUE;  boolean enable_page_protection = TRUE;
 #endif  
251    
252  /*  /*
253   * Hunt for pointers to old-space, when GCing generations >= verify_gen.   * Hunt for pointers to old-space, when GCing generations >= verify_gen.
# Line 389  static char *heap_base = NULL; Line 385  static char *heap_base = NULL;
385  /*  /*
386   * Calculate the start address for the given page number.   * Calculate the start address for the given page number.
387   */   */
388  inline char *  static char *
389  page_address(int page_num)  page_address(int page_num)
390  {  {
391      return heap_base + PAGE_SIZE * page_num;      return heap_base + PAGE_SIZE * page_num;
# Line 399  page_address(int page_num) Line 395  page_address(int page_num)
395   * Find the page index within the page_table for the given address.   * Find the page index within the page_table for the given address.
396   * Returns -1 on failure.   * Returns -1 on failure.
397   */   */
398  inline int  int
399  find_page_index(void *addr)  find_page_index(void *addr)
400  {  {
401      int index = (char *) addr - heap_base;      int index = (char *) addr - heap_base;
# Line 413  find_page_index(void *addr) Line 409  find_page_index(void *addr)
409      return -1;      return -1;
410  }  }
411    
412    /*
413     * This routine implements a write barrier used to record stores into
414     * to boxed regions outside of generation 0.  When such a store occurs
415     * this routine will be automatically invoked by the page fault
416     * handler.  If passed an address outside of the dynamic space, this
417     * routine will return immediately with a value of 0.  Otherwise, the
418     * page belonging to the address is made writable, the protection
419     * change is recorded in the garbage collector page table, and a value
420     * of 1 is returned.
421     */
422    int
423    gc_write_barrier(void *addr)
424    {
425        int page_index = find_page_index(addr);
426    
427        /* Check if the fault is within the dynamic space. */
428        if (page_index == -1) {
429             return 0;
430        }
431    
432        /* The page should have been marked write protected */
433        if (!PAGE_WRITE_PROTECTED(page_index))
434             fprintf(stderr,
435                     "*** Page fault in page not marked as write protected\n");
436    
437        /* Un-protect the page */
438        os_protect(page_address(page_index), PAGE_SIZE, OS_VM_PROT_ALL);
439        page_table[page_index].flags &= ~PAGE_WRITE_PROTECTED_MASK;
440        page_table[page_index].flags |= PAGE_WRITE_PROTECT_CLEARED_MASK;
441    
442        return 1;
443    }
444    
445  /*  /*
446   * A structure to hold the state of a generation.   * A structure to hold the state of a generation.
# Line 1561  gc_alloc_large(int nbytes, int unboxed, Line 1589  gc_alloc_large(int nbytes, int unboxed,
1589  }  }
1590    
1591  /*  /*
1592   * Allocate bytes from the boxed_region. It first checks if there is   * If the current region has more than this much space left, we don't
1593   * room, if not then it calls gc_alloc_new_region to find a new region   * want to abandon the region (wasting space), but do a "large" alloc
1594   * with enough space. A pointer to the start of the region is returned.   * to a new region.
1595     */
1596    
1597    int region_empty_threshold = 32;
1598    
1599    
1600    /*
1601     * How many consecutive large alloc we can do before we abandon the
1602     * current region
1603     */
1604    int consecutive_large_alloc_limit = 10;
1605    
1606    
1607    /*
1608     * This is for debugging.  It gets incremented every time we have to
1609     * abandon the current region, because we done too many gc_alloc's in
1610     * the current region without changing the region.
1611     */
1612    struct alloc_stats
1613    {
1614        int consecutive_alloc;
1615        int abandon_region_count;
1616        int regions_differ_count;
1617        struct alloc_region saved_region;
1618    };
1619    
1620    struct alloc_stats boxed_stats =
1621    {0, 0, 0,
1622     {NULL, NULL, -1, -1, NULL}};
1623    
1624    struct alloc_stats unboxed_stats =
1625    {0, 0, 0,
1626     {NULL, NULL, -1, -1, NULL}};
1627    
1628    /*
1629     * Allocate bytes from a boxed or unboxed region. It first checks if
1630     * there is room, if not then it calls gc_alloc_new_region to find a
1631     * new region with enough space. A pointer to the start of the region
1632     * is returned.  The parameter "unboxed" should be 0 (boxed) or 1
1633     * (unboxed).
1634   */   */
1635  static void *  static void *
1636  gc_alloc(int nbytes)  gc_alloc_region(int nbytes, struct alloc_region *region, int unboxed, struct alloc_stats *stats)
1637  {  {
1638      char *new_free_pointer;      char *new_free_pointer;
   
1639  #if 0  #if 0
1640      fprintf(stderr, "gc_alloc %d\n", nbytes);      fprintf(stderr, "gc_alloc %d\n", nbytes);
1641  #endif  #endif
1642    
1643      /* Check if there is room in the current alloc region. */      /* Check if there is room in the current alloc region. */
1644      new_free_pointer = boxed_region.free_pointer + nbytes;      new_free_pointer = region->free_pointer + nbytes;
1645    
1646      if (new_free_pointer <= boxed_region.end_addr) {      if (new_free_pointer <= region->end_addr) {
1647          /* If so then allocate from the current alloc region. */          /* If so then allocate from the current alloc region. */
1648          char *new_obj = boxed_region.free_pointer;          char *new_obj = region->free_pointer;
1649    
1650          boxed_region.free_pointer = new_free_pointer;          region->free_pointer = new_free_pointer;
1651    
1652          /* Check if the alloc region is almost empty. */          /* Check if the alloc region is almost empty. */
1653          if (boxed_region.end_addr - boxed_region.free_pointer <= 32) {          if (region->end_addr - region->free_pointer <= 32) {
1654              /* If so finished with the current region. */              /* If so finished with the current region. */
1655              gc_alloc_update_page_tables(0, &boxed_region);              gc_alloc_update_page_tables(unboxed, region);
1656              /* Setup a new region. */              /* Setup a new region. */
1657              gc_alloc_new_region(32, 0, &boxed_region);              gc_alloc_new_region(32, unboxed, region);
1658          }          }
1659    
1660            stats->consecutive_alloc = 0;
1661            memcpy(&stats->saved_region, region, sizeof(stats->saved_region));
1662    
1663          return (void *) new_obj;          return (void *) new_obj;
1664      }      }
1665    
1666      /* Else not enough free space in the current region. */      /* Else not enough free space in the current region. */
1667    
1668      /*      /*
1669         * If the allocation is large enough, always do a large alloc This
1670         * helps GC so we don't have to copy this object again.
1671         */
1672    
1673        if (nbytes >= large_object_size) {
1674            return gc_alloc_large(nbytes, unboxed, region);
1675        }
1676    
1677        /*
1678       * If there is a bit of room left in the current region then       * If there is a bit of room left in the current region then
1679       * allocate a large object.       * allocate a large object.
1680       */       */
1681      if (boxed_region.end_addr - boxed_region.free_pointer > 32)  
1682          return gc_alloc_large(nbytes, 0, &boxed_region);      /*
1683         * This has potentially very bad behavior on sparc if the current
1684         * boxed region is too small for the allocation, but the free
1685         * space is greater than 32 (region_empty_threshold).  The
1686         * scenario is where we're always allocating something that won't
1687         * fit in the boxed region, and we keep calling gc_alloc_large.
1688         * Since gc_alloc_large doesn't change the region, the next
1689         * allocation will again be out-of-line and we hit a kernel trap
1690         * again.  And so on, so we waste all of our time doing kernel
1691         * traps to allocate small things.  This also affects ppc.
1692         *
1693         * X86 has the same issue, but the affect is less because the
1694         * out-of-line allocation is a just a function call, not a kernel
1695         * trap.
1696         *
1697         * Heuristic: If we do too many consecutive large allocations
1698         * because the current region has some space left, we give up and
1699         * abandon the region. This will prevent the bad scenario above
1700         * from killing allocation performance.
1701         *
1702         */
1703    
1704        if ((region->end_addr - region->free_pointer > region_empty_threshold)
1705            && (stats->consecutive_alloc < consecutive_large_alloc_limit)) {
1706            /*
1707             * Is the saved region the same as the current region?  If so,
1708             * update the counter.  If not, that means we did some other
1709             * (inline) allocation, so reset the counter and region
1710             */
1711            if (memcmp(&stats->saved_region, region, sizeof(stats->saved_region)) == 0) {
1712                ++stats->consecutive_alloc;
1713            } else {
1714                stats->consecutive_alloc = 0;
1715                ++stats->regions_differ_count;
1716                memcpy(&stats->saved_region, region, sizeof(stats->saved_region));
1717            }
1718    
1719            return gc_alloc_large(nbytes, unboxed, region);
1720        }
1721    
1722        stats->consecutive_alloc = 0;
1723        ++stats->abandon_region_count;
1724    
1725      /* Else find a new region. */      /* Else find a new region. */
1726    
1727      /* Finished with the current region. */      /* Finished with the current region. */
1728      gc_alloc_update_page_tables(0, &boxed_region);      gc_alloc_update_page_tables(unboxed, region);
1729    
1730      /* Setup a new region. */      /* Setup a new region. */
1731      gc_alloc_new_region(nbytes, 0, &boxed_region);      gc_alloc_new_region(nbytes, unboxed, region);
1732    
1733      /* Should now be enough room. */      /* Should now be enough room. */
1734    
1735      /* Check if there is room in the current region. */      /* Check if there is room in the current region. */
1736      new_free_pointer = boxed_region.free_pointer + nbytes;      new_free_pointer = region->free_pointer + nbytes;
1737    
1738      if (new_free_pointer <= boxed_region.end_addr) {      if (new_free_pointer <= region->end_addr) {
1739          /* If so then allocate from the current region. */          /* If so then allocate from the current region. */
1740          void *new_obj = boxed_region.free_pointer;          void *new_obj = region->free_pointer;
1741    
1742          boxed_region.free_pointer = new_free_pointer;          region->free_pointer = new_free_pointer;
1743    
1744          /* Check if the current region is almost empty. */          /* Check if the current region is almost empty. */
1745          if (boxed_region.end_addr - boxed_region.free_pointer <= 32) {          if (region->end_addr - region->free_pointer <= 32) {
1746              /* If so find, finished with the current region. */              /* If so find, finished with the current region. */
1747              gc_alloc_update_page_tables(0, &boxed_region);              gc_alloc_update_page_tables(unboxed, region);
1748    
1749              /* Setup a new region. */              /* Setup a new region. */
1750              gc_alloc_new_region(32, 0, &boxed_region);              gc_alloc_new_region(32, unboxed, region);
1751          }          }
1752    
1753            memcpy(&stats->saved_region, region, sizeof(stats->saved_region));
1754    
1755          return (void *) new_obj;          return (void *) new_obj;
1756      }      }
1757    
# Line 1639  gc_alloc(int nbytes) Line 1761  gc_alloc(int nbytes)
1761  }  }
1762    
1763  /*  /*
1764     * Allocate bytes from the boxed_region. It first checks if there is
1765     * room, if not then it calls gc_alloc_new_region to find a new region
1766     * with enough space. A pointer to the start of the region is returned.
1767     */
1768    static inline void *
1769    gc_alloc(int nbytes)
1770    {
1771        void* obj;
1772    
1773        obj = gc_alloc_region(nbytes, &boxed_region, 0, &boxed_stats);
1774    
1775        return obj;
1776    }
1777    
1778    /*
1779   * Allocate space from the boxed_region. If there is not enough free   * Allocate space from the boxed_region. If there is not enough free
1780   * space then call gc_alloc to do the job. A pointer to the start of   * space then call gc_alloc to do the job. A pointer to the start of
1781   * the region is returned.   * the region is returned.
# Line 1692  gc_quick_alloc_large(int nbytes) Line 1829  gc_quick_alloc_large(int nbytes)
1829      return gc_alloc(nbytes);      return gc_alloc(nbytes);
1830  }  }
1831    
1832    static inline void *
   
   
 static void *  
1833  gc_alloc_unboxed(int nbytes)  gc_alloc_unboxed(int nbytes)
1834  {  {
1835      char *new_free_pointer;      void *obj;
   
 #if 0  
     fprintf(stderr, "gc_alloc_unboxed %d\n", nbytes);  
 #endif  
   
     /* Check if there is room in the current region. */  
     new_free_pointer = unboxed_region.free_pointer + nbytes;  
   
     if (new_free_pointer <= unboxed_region.end_addr) {  
         /* If so then allocate from the current region. */  
         void *new_obj = unboxed_region.free_pointer;  
   
         unboxed_region.free_pointer = new_free_pointer;  
   
         /* Check if the current region is almost empty. */  
         if ((unboxed_region.end_addr - unboxed_region.free_pointer) <= 32) {  
             /* If so finished with the current region. */  
             gc_alloc_update_page_tables(1, &unboxed_region);  
   
             /* Setup a new region. */  
             gc_alloc_new_region(32, 1, &unboxed_region);  
         }  
   
         return (void *) new_obj;  
     }  
   
     /* Else not enough free space in the current region. */  
   
     /*  
      * If there is a bit of room left in the current region then  
      * allocate a large object.  
      */  
     if (unboxed_region.end_addr - unboxed_region.free_pointer > 32)  
         return gc_alloc_large(nbytes, 1, &unboxed_region);  
   
     /* Else find a new region. */  
   
     /* Finished with the current region. */  
     gc_alloc_update_page_tables(1, &unboxed_region);  
1836    
1837      /* Setup a new region. */      obj = gc_alloc_region(nbytes, &unboxed_region, 1, &unboxed_stats);
     gc_alloc_new_region(nbytes, 1, &unboxed_region);  
   
     /* Should now be enough room. */  
   
     /* Check if there is room in the current region. */  
     new_free_pointer = unboxed_region.free_pointer + nbytes;  
   
     if (new_free_pointer <= unboxed_region.end_addr) {  
         /* If so then allocate from the current region. */  
         void *new_obj = unboxed_region.free_pointer;  
1838    
1839          unboxed_region.free_pointer = new_free_pointer;      return obj;
   
         /* Check if the current region is almost empty. */  
         if ((unboxed_region.end_addr - unboxed_region.free_pointer) <= 32) {  
             /* If so find, finished with the current region. */  
             gc_alloc_update_page_tables(1, &unboxed_region);  
   
             /* Setup a new region. */  
             gc_alloc_new_region(32, 1, &unboxed_region);  
         }  
   
         return (void *) new_obj;  
     }  
   
     /* Shouldn't happen? */  
     gc_assert(0);  
     return 0;  
1840  }  }
1841    
1842  static inline void *  static inline void *

Legend:
Removed from v.1.95.2.1  
changed lines
  Added in v.1.95.2.1.2.8

  ViewVC Help
Powered by ViewVC 1.1.5