1 /*
   2  * Copyright (c) 2001, 2012, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.
   8  *
   9  * This code is distributed in the hope that it will be useful, but WITHOUT
  10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  11  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  12  * version 2 for more details (a copy is included in the LICENSE file that
  13  * accompanied this code).
  14  *
  15  * You should have received a copy of the GNU General Public License version
  16  * 2 along with this work; if not, write to the Free Software Foundation,
  17  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  18  *
  19  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  20  * or visit www.oracle.com if you need additional information or have any
  21  * questions.
  22  *
  23  */
  24 
  25 #ifndef SHARE_VM_GC_IMPLEMENTATION_G1_HEAPREGIONSEQ_HPP
  26 #define SHARE_VM_GC_IMPLEMENTATION_G1_HEAPREGIONSEQ_HPP
  27 
  28 #include "gc_implementation/g1/g1BiasedArray.hpp"
  29 
  30 class HeapRegion;
  31 class HeapRegionClosure;
  32 class FreeRegionList;
  33 
  34 class G1HeapRegionTable : public G1BiasedMappedArray<HeapRegion*> {
  35  protected:
  36    virtual HeapRegion* default_value() const { return NULL; }
  37 };
  38 
  39 // This class keeps track of the region metadata (i.e., HeapRegion
  40 // instances). They are kept in the _regions array in address
  41 // order. A region's index in the array corresponds to its index in
  42 // the heap (i.e., 0 is the region at the bottom of the heap, 1 is
  43 // the one after it, etc.). Two regions that are consecutive in the
  44 // array should also be adjacent in the address space (i.e.,
  45 // region(i).end() == region(i+1).bottom().
  46 //
  47 // We create a HeapRegion when we commit the region's address space
  48 // for the first time. When we uncommit the address space of a
  49 // region we retain the HeapRegion to be able to re-use it in the
  50 // future (in case we recommit it).
  51 //
  52 // We keep track of three lengths:
  53 //
  54 // * _committed_length (returned by length()) is the number of currently
  55 //   committed regions.
  56 // * _allocated_length (not exposed outside this class) is the
  57 //   number of regions for which we have HeapRegions.
  58 // * max_length() returns the maximum number of regions the heap can have.
  59 //
  60 // and maintain that: _committed_length <= _allocated_length <= max_length()
  61 
  62 class HeapRegionSeq: public CHeapObj<mtGC> {
  63   friend class VMStructs;
  64 
  65   G1HeapRegionTable _regions;
  66 
  67   // The number of regions committed in the heap.
  68   uint _committed_length;
  69 
  70   // A hint for which index to start searching from for humongous
  71   // allocations.
  72   uint _next_search_index;
  73 
  74   // The number of regions for which we have allocated HeapRegions for.
  75   uint _allocated_length;
  76 
  77   // Find a contiguous set of empty regions of length num, starting
  78   // from the given index.
  79   uint find_contiguous_from(uint from, uint num);
  80 
  81   void increment_allocated_length() {
  82     assert(_allocated_length < max_length(), "pre-condition");
  83     _allocated_length++;
  84   }
  85 
  86   void increment_length() {
  87     assert(length() < max_length(), "pre-condition");
  88     _committed_length++;
  89   }
  90 
  91   void decrement_length() {
  92     assert(length() > 0, "pre-condition");
  93     _committed_length--;
  94   }
  95 
  96   HeapWord* heap_bottom() const { return _regions.bottom_address_mapped(); }
  97   HeapWord* heap_end() const {return _regions.end_address_mapped(); }
  98 
  99  public:
 100   // Empty contructor, we'll initialize it with the initialize() method.
 101   HeapRegionSeq() : _regions(), _committed_length(0), _next_search_index(0), _allocated_length(0) { }
 102 
 103   void initialize(HeapWord* bottom, HeapWord* end);
 104 
 105   // Return the HeapRegion at the given index. Assume that the index
 106   // is valid.
 107   inline HeapRegion* at(uint index) const;
 108 
 109   // If addr is within the committed space return its corresponding
 110   // HeapRegion, otherwise return NULL.
 111   inline HeapRegion* addr_to_region(HeapWord* addr) const;
 112 
 113   // Return the HeapRegion that corresponds to the given
 114   // address. Assume the address is valid.
 115   inline HeapRegion* addr_to_region_unsafe(HeapWord* addr) const;
 116 
 117   // Return the number of regions that have been committed in the heap.
 118   uint length() const { return _committed_length; }
 119 
 120   // Return the maximum number of regions in the heap.
 121   uint max_length() const { return (uint)_regions.length(); }
 122 
 123   // Expand the sequence to reflect that the heap has grown from
 124   // old_end to new_end. Either create new HeapRegions, or re-use
 125   // existing ones, and return them in the given list. Returns the
 126   // memory region that covers the newly-created regions. If a
 127   // HeapRegion allocation fails, the result memory region might be
 128   // smaller than the desired one.
 129   MemRegion expand_by(HeapWord* old_end, HeapWord* new_end,
 130                       FreeRegionList* list);
 131 
 132   // Return the number of contiguous regions at the end of the sequence
 133   // that are available for allocation.
 134   uint free_suffix();
 135 
 136   // Find a contiguous set of empty regions of length num and return
 137   // the index of the first region or G1_NULL_HRS_INDEX if the
 138   // search was unsuccessful.
 139   uint find_contiguous(uint num);
 140 
 141   // Apply blk->doHeapRegion() on all committed regions in address order,
 142   // terminating the iteration early if doHeapRegion() returns true.
 143   void iterate(HeapRegionClosure* blk) const;
 144 
 145   // As above, but start the iteration from hr and loop around. If hr
 146   // is NULL, we start from the first region in the heap.
 147   void iterate_from(HeapRegion* hr, HeapRegionClosure* blk) const;
 148 
 149   // Tag as uncommitted as many regions that are completely free as
 150   // possible, up to num_regions_to_remove, from the suffix of the committed
 151   // sequence. Return the actual number of removed regions.
 152   uint shrink_by(uint num_regions_to_remove);
 153 
 154   // Do some sanity checking.
 155   void verify_optional() PRODUCT_RETURN;
 156 };
 157 
 158 #endif // SHARE_VM_GC_IMPLEMENTATION_G1_HEAPREGIONSEQ_HPP