include/AD/gc/gcheaps.h

   1 //////////////////////////////////////////////////////////////////////////////
   2 // NOTICE:
   3 //
   4 // ADLib, Prop and their related set of tools and documentation are in the
   5 // public domain.   The author(s) of this software reserve no copyrights on
   6 // the source code and any code generated using the tools.  You are encouraged
   7 // to use ADLib and Prop to develop software, in both academic and commercial
   8 // settings, and are welcomed to incorporate any part of ADLib and Prop into
   9 // your programs.
  10 //
  11 // Although you are under no obligation to do so, we strongly recommend that
  12 // you give away all software developed using our tools.
  13 //
  14 // We also ask that credit be given to us when ADLib and/or Prop are used in
  15 // your programs, and that this notice be preserved intact in all the source
  16 // code.
  17 //
  18 // This software is still under development and we welcome(read crave for)
  19 // any suggestions and help from the users.
  20 //
  21 // Allen Leung (leunga@cs.nyu.edu)
  22 // 1994-1995
  23 //////////////////////////////////////////////////////////////////////////////
  24
  25 #ifndef garbage_collection_spaces_h
  26 #define garbage_collection_spaces_h
  27
  28 #include <new>
  29 #include <AD/generic/generic.h>  // generic definitions
  30 #include <AD/gc/gcconfig.h>      // system configurations
  31 #include <AD/gc/gcintern.h>      // internal data structures
  32 #include <AD/gc/gc.h>            // garbage collector base class
  33 #include <AD/gc/gcbitmap.h>      // bitmaps
  34 #include <AD/gc/gcmacros.h>      // useful macros
  35
  36 class ostream;
  37
  38 //////////////////////////////////////////////////////////////////////////////
  39 //  Garbage collection space manager.
  40 //  The space manager provides the following services:
  41 //     (1)  Partition the collectable heaps into pages
  42 //     (2)  Maintain bitmaps on these pages so that starting addresses
  43 //          of objects can be found (for interior pointers.)
  44 //////////////////////////////////////////////////////////////////////////////
  45 class GCHeapManager {
  46
  47    GCHeapManager (const GCHeapManager&);   // no copy constructor
  48    void operator = (const GCHeapManager&); // no assignment
  49
  50 public:
  51
  52    ///////////////////////////////////////////////////////////////////////////
  53    //  Type definitions
  54    ///////////////////////////////////////////////////////////////////////////
  55    typedef size_t        GCPageId;  // a page id
  56    typedef GC::GC_ID     GC_ID;     // collector id.
  57
  58 protected:
  59
  60    ///////////////////////////////////////////////////////////////////////////
  61    //  Statistics
  62    ///////////////////////////////////////////////////////////////////////////
  63    static size_t number_of_pages_allocated;
  64    static size_t number_of_pages_used;
  65    static size_t number_of_pages_free;
  66    static size_t number_of_pages_blacklisted;
  67
  68    ///////////////////////////////////////////////////////////////////////////
  69    //  Message verbosity
  70    ///////////////////////////////////////////////////////////////////////////
  71    static int verbosity_level;
  72
  73 public:
  74    ///////////////////////////////////////////////////////////////////////////
  75    // Status of a page in the alloc table.  The page status is one byte long
  76    // and stored in an array in the heap.  To prevent them from mistaken
  77    // for real heap addresses, we choose some high numbers.  On Unix
  78    // most platforms these resemble stack addresses.
  79    ///////////////////////////////////////////////////////////////////////////
  80    enum PageStatus {
  81       not_allocated   = 0x00, // we don't have this page; the OS has it
  82       blacklisted     = 0xfc, // this page will never be used by the application
  83       from_space      = 0xfd, // this is the from space of a heap
  84       to_space        = 0xfe, // this is the to space of a heap
  85       newly_allocated = 0xff  // this is the space used during the copying phase
  86    };
  87
  88    ///////////////////////////////////////////////////////////////////////////
  89    //  An address range
  90    ///////////////////////////////////////////////////////////////////////////
  91    struct AddrRange { void * start, * stop; };
  92
  93 private:
  94    ///////////////////////////////////////////////////////////////////////////
  95    //  Make it possible for certain classes to use the page table info
  96    //  directly without going thru the inline functions since inlining
  97    //  may not be as efficient as macros.
  98    ///////////////////////////////////////////////////////////////////////////
  99    friend class BGC;
 100    friend class MarkSweepGC;
 101    friend class BGC_F;
 102    friend class CGC;
 103    friend class GCVerifier;
 104
 105    ///////////////////////////////////////////////////////////////////////////
 106    //  Page tables.
 107    //    We store them in page_table and bitmap_table respectively.  These
 108    //  tables are stored in an offseted manner.
 109    //  Empty pages are stored as null pointers.
 110    //  Tracked addresses are addresses that have corresponding page table
 111    //  entries while mapped addresses are addresses that have bitmap entries.
 112    ///////////////////////////////////////////////////////////////////////////
 113    static void *   lowest_mapped_addr;  // lowest of the mapped addresses
 114    static void *   highest_mapped_addr; // highest of the mapped addresses
 115    static void *   lowest_tracked_addr; // lowest of the tracked addresses
 116    static void *   highest_tracked_addr;// highest of the tracked addresses
 117
 118    static Byte *   gc_table;            // mapping from page id to collector id
 119    static Byte *   gc_table_mem;        // the tables memory
 120    static Byte *   page_table;          // mark all pages that we own
 121    static Byte *   page_table_mem;      // the tables memory
 122    static size_t   page_table_size;     // number of pages in the table.
 123    static GCBitMap object_map;          // map of starting addresses of objects
 124    static GCBitMap live_map;            // map of live objects
 125    static GCBitMap traversed_map;       // map of cross heap objects
 126
 127    ///////////////////////////////////////////////////////////////////////////
 128    //  Free list.
 129    //     Deallocated pages are chained together into the free list
 130    //  so that it can be reused quickly.
 131    ///////////////////////////////////////////////////////////////////////////
 132
 133 public:
 134
 135    ///////////////////////////////////////////////////////////////////////////
 136    //  Constructor and destructor
 137    ///////////////////////////////////////////////////////////////////////////
 138    GCHeapManager();
 139   ~GCHeapManager();
 140
 141    ///////////////////////////////////////////////////////////////////////////
 142    //  Address boundaries
 143    ///////////////////////////////////////////////////////////////////////////
 144    inline static void * lo_mapped()  { return lowest_mapped_addr; }
 145    inline static void * hi_mapped()  { return highest_mapped_addr; }
 146    inline static void * lo_tracked() { return lowest_tracked_addr; }
 147    inline static void * hi_tracked() { return highest_tracked_addr; }
 148    inline static Bool is_mapped(void * addr)
 149       { return addr >= lowest_mapped_addr && addr < highest_mapped_addr; }
 150    inline static Bool is_tracked(void * addr)
 151       { return addr >= lowest_tracked_addr && addr < highest_tracked_addr; }
 152
 153    ///////////////////////////////////////////////////////////////////////////
 154    //  Page table
 155    ///////////////////////////////////////////////////////////////////////////
 156    inline static PageStatus page_status(GCPageId id)
 157       { return (PageStatus)page_table[id]; }
 158    inline static PageStatus page_status(void * addr)
 159       { return (PageStatus)page_table[GC_PAGE_ID(addr)]; }
 160    inline static GC_ID page_gc(GCPageId id) { return gc_table[id]; }
 161    inline static GC_ID page_gc(void * addr)
 162       { return gc_table[GC_PAGE_ID(addr)]; }
 163    inline static void set_page_status(GCPageId id, PageStatus s)
 164       { page_table[id] = s; }
 165    inline static void set_page_gc(GCPageId id, GC_ID gc)
 166       { gc_table[id] = gc; }
 167    inline static void promote_page(GCPageId id) { page_table[id] = to_space; }
 168    inline static void promote_page(void * addr)
 169       { page_table[GC_PAGE_ID(addr)] = to_space; }
 170
 171    ///////////////////////////////////////////////////////////////////////////
 172    // Bitmaps
 173    ///////////////////////////////////////////////////////////////////////////
 174    inline static GCBitMap& get_object_map() { return object_map; }
 175    inline static GCBitMap& get_live_map()   { return live_map; }
 176
 177    ///////////////////////////////////////////////////////////////////////////
 178    //  Free space
 179    ///////////////////////////////////////////////////////////////////////////
 180    inline static size_t pages_allocated()   { return number_of_pages_allocated; }
 181    inline static size_t pages_used()        { return number_of_pages_used; }
 182    inline static size_t pages_free()        { return number_of_pages_free; }
 183    inline static size_t pages_blacklisted() { return number_of_pages_blacklisted; }
 184    inline static size_t bytes_allocated()   { return number_of_pages_allocated * GC_PAGE_SIZE; }
 185    inline static size_t bytes_used()        { return number_of_pages_used * GC_PAGE_SIZE; }
 186    inline static size_t bytes_free()        { return number_of_pages_free * GC_PAGE_SIZE; }
 187    inline static size_t bytes_blacklisted() { return number_of_pages_blacklisted * GC_PAGE_SIZE; }
 188
 189    ///////////////////////////////////////////////////////////////////////////
 190    //  Verbosity level
 191    ///////////////////////////////////////////////////////////////////////////
 192    inline static int  verbosity()          { return verbosity_level; }
 193    inline static void set_verbosity(int v) { verbosity_level = v; }
 194    inline static Bool is_verbose()         { return verbosity_level > 0; }
 195
 196    ///////////////////////////////////////////////////////////////////////////
 197    //  Methods for allocating/deallocating memory and manipulating
 198    //  the page tables.
 199    //    blacklisted_data()  -- return a table of blacklisted static addresses
 200    //    clear_page_table()  -- empty the entire page table
 201    //    release_all_pages() -- release all pages owned by a collector
 202    //    allocate_pages()    -- allocate a bunch of pages
 203    ///////////////////////////////////////////////////////////////////////////
 204
 205    ///////////////////////////////////////////////////////////////////////////
 206    //  Method to return a table of blacklisted static data addresses.
 207    ///////////////////////////////////////////////////////////////////////////
 208    static const AddrRange * blacklisted_data (size_t& n);
 209
 210    ///////////////////////////////////////////////////////////////////////////
 211    //  Method to expand the ranges of the page tables.
 212    ///////////////////////////////////////////////////////////////////////////
 213    static void  grow_page_table (void * start, void * stop);
 214
 215    ///////////////////////////////////////////////////////////////////////////
 216    //  Method to release all the pages owned by a collector.
 217    ///////////////////////////////////////////////////////////////////////////
 218    static void   release_all_pages(GC *);
 219
 220    ///////////////////////////////////////////////////////////////////////////
 221    //  Method to allocate a set of consecutive pages from the heap manager.
 222    //  The client tells the heap manager how much space is needed, and
 223    //  how much is preferred.   The actual number of bytes is returned
 224    //  the parameter ``bytes_gotten'' and the address of the new pages
 225    //  is returned.
 226    ///////////////////////////////////////////////////////////////////////////
 227    static void * allocate_pages
 228       ( GC *       gc,                 // the collector to allocate for
 229         size_t     bytes_need,         // number of bytes we need
 230         size_t     bytes_wanted,       // number of bytes we prefer to have
 231         size_t&    bytes_gotten,       // number of bytes actually got
 232         PageStatus status = from_space // the default status of the pages
 233       );
 234
 235    ///////////////////////////////////////////////////////////////////////////
 236    //  Method to deallocate pages owned by a collector
 237    ///////////////////////////////////////////////////////////////////////////
 238    static void deallocate_pages
 239       ( GC *     gc,          // the collector
 240         GCPageId page_id,     // starting page to deallocate
 241         size_t   pages        // number of pages
 242       );
 243
 244    ///////////////////////////////////////////////////////////////////////////
 245    //  Method to discard all pages in the from space of the collector.
 246    //  As a side effect, the total number of bytes now owned by the collector
 247    //  and the total number of bytes freed are returned as the 2nd and 3rd
 248    //  parameter.
 249    ///////////////////////////////////////////////////////////////////////////
 250    static void   discard_from_space(GC *, size_t& total, size_t& removed);
 251
 252    ///////////////////////////////////////////////////////////////////////////
 253    //  Mark all pages within start and stop to have certain page status.
 254    ///////////////////////////////////////////////////////////////////////////
 255    static void   mark_space(void * start, void * stop, PageStatus status);
 256
 257    ///////////////////////////////////////////////////////////////////////////
 258    //  Method to (un)blacklist a range of addresses.
 259    //  Use blacklist_system_heap(start,stop,true) to blacklist
 260    //  and blacklist_system_heap(start,stop,false) to unblacklist
 261    ///////////////////////////////////////////////////////////////////////////
 262    static void   blacklist_system_heap(void * start, void * stop, Bool mark);
 263    static void   blacklist   (const void * addr, size_t size_in_bytes);
 264    static void   unblacklist (const void * addr, size_t size_in_bytes);
 265
 266    ///////////////////////////////////////////////////////////////////////////
 267    //  Method to allocate some initialized memory on page boundaries.
 268    //  The storage is outside of the collectable heap and is meant to
 269    //  be used as auxiliary data.
 270    ///////////////////////////////////////////////////////////////////////////
 271    static void * allocate_pages_on_boundaries   (size_t size, void *& real);
 272    static void   deallocate_pages_on_boundaries (void *, size_t);
 273
 274    ///////////////////////////////////////////////////////////////////////////
 275    //  Error reporting
 276    ///////////////////////////////////////////////////////////////////////////
 277    static ostream& error (const char *);
 278    static ostream& print_report(ostream&);
 279
 280 private:
 281    ///////////////////////////////////////////////////////////////////////////
 282    //  The following methods are not meant to be used by the clients directly.
 283    ///////////////////////////////////////////////////////////////////////////
 284
 285    ///////////////////////////////////////////////////////////////////////////
 286    //  Method to clear the entire page table.  DO NOT USE!
 287    ///////////////////////////////////////////////////////////////////////////
 288    static void   clear_page_table ();
 289
 290    ///////////////////////////////////////////////////////////////////////////
 291    //  Method to expand the page tables.  Used only internally
 292    ///////////////////////////////////////////////////////////////////////////
 293    static void * allocate_new_pages (GC *, size_t bytes); // allocate new pages
 294
 295    ///////////////////////////////////////////////////////////////////////////
 296    //  Method to blacklist a set of newly allocated pages.  This method
 297    //  is only used internally by the heap manager.
 298    ///////////////////////////////////////////////////////////////////////////
 299    static void   blacklist_new_pages(void * start, void * stop);
 300 };
 301
 302 //////////////////////////////////////////////////////////////////////////////
 303 //  A synonym for class GCHeapManager to save keystrokes.
 304 //////////////////////////////////////////////////////////////////////////////
 305 typedef class GCHeapManager HM;
 306
 307 #endif