# HG changeset patch
# User tschatzl
# Date 1380108324 -7200
# Node ID a19bea467577149e3f6a2cac3025bce49a9c1b2b
# Parent  10cc3b624f8f42b9c2bc6549cb6308c0a0fcb0e2
7163191: G1: introduce a "heap spanning table" abstraction
Summary: Add G1BiasedArray<T> that is an array where each element represents a fixed-sized subdivision of the heap. Use this abstraction to refactor the HeapRegionSeq class.
Reviewed-by: brutisso

diff -r 10cc3b624f8f -r a19bea467577 make/excludeSrc.make
--- a/make/excludeSrc.make	Tue Sep 24 10:14:02 2013 +0200
+++ b/make/excludeSrc.make	Wed Sep 25 13:25:24 2013 +0200
@@ -88,7 +88,7 @@
 	g1ErgoVerbose.cpp g1GCPhaseTimes.cpp g1HRPrinter.cpp g1HotCardCache.cpp g1Log.cpp \
 	g1MMUTracker.cpp g1MarkSweep.cpp g1MemoryPool.cpp g1MonitoringSupport.cpp \
 	g1RemSet.cpp g1RemSetSummary.cpp g1SATBCardTableModRefBS.cpp g1_globals.cpp heapRegion.cpp \
-	heapRegionRemSet.cpp heapRegionSeq.cpp heapRegionSet.cpp heapRegionSets.cpp \
+	g1BiasedArray.cpp heapRegionRemSet.cpp heapRegionSeq.cpp heapRegionSet.cpp heapRegionSets.cpp \
 	ptrQueue.cpp satbQueue.cpp sparsePRT.cpp survRateGroup.cpp vm_operations_g1.cpp \
 	adjoiningGenerations.cpp adjoiningVirtualSpaces.cpp asPSOldGen.cpp asPSYoungGen.cpp \
 	cardTableExtension.cpp gcTaskManager.cpp gcTaskThread.cpp objectStartArray.cpp \
diff -r 10cc3b624f8f -r a19bea467577 src/share/vm/gc_implementation/g1/g1BiasedArray.cpp
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/share/vm/gc_implementation/g1/g1BiasedArray.cpp	Wed Sep 25 13:25:24 2013 +0200
@@ -0,0 +1,141 @@
+/*
+ * Copyright (c) 2013, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ *
+ */
+
+#include "precompiled.hpp"
+#include "gc_implementation/g1/g1BiasedArray.hpp"
+
+#ifndef PRODUCT
+void G1BiasedMappedArrayBase::verify_index(idx_t index) const {
+  guarantee(_base != NULL, "Array not initialized");
+  guarantee(index < length(), err_msg("Index out of bounds index: "SIZE_FORMAT" length: "SIZE_FORMAT, index, length()));
+}
+
+void G1BiasedMappedArrayBase::verify_biased_index(idx_t biased_index) const {
+  guarantee(_biased_base != NULL, "Array not initialized");
+  guarantee(biased_index >= bias() && biased_index < (bias() + length()),
+    err_msg("Biased index out of bounds, index: "SIZE_FORMAT" bias: "SIZE_FORMAT" length: "SIZE_FORMAT, biased_index, bias(), length()));
+}
+
+void G1BiasedMappedArrayBase::verify_biased_index_inclusive_end(idx_t biased_index) const {
+  guarantee(_biased_base != NULL, "Array not initialized");
+  guarantee(biased_index >= bias() && biased_index <= (bias() + length()),
+    err_msg("Biased index out of inclusive bounds, index: "SIZE_FORMAT" bias: "SIZE_FORMAT" length: "SIZE_FORMAT, biased_index, bias(), length()));
+}
+
+class TestMappedArray : public G1BiasedMappedArray<int> {
+protected:
+  virtual int default_value() const { return 0xBAADBABE; }
+public:
+  static void test_biasedarray() {
+    const size_t REGION_SIZE_IN_WORDS = 512;
+    const size_t NUM_REGIONS = 20;
+    HeapWord* fake_heap = (HeapWord*)LP64_ONLY(0xBAAA00000) NOT_LP64(0xBA000000); // Any value that is non-zero
+
+    TestMappedArray array;
+    array.initialize(fake_heap, fake_heap + REGION_SIZE_IN_WORDS * NUM_REGIONS,
+            REGION_SIZE_IN_WORDS * HeapWordSize);
+    // Check address calculation (bounds)
+    assert(array.bottom_address_mapped() == fake_heap,
+      err_msg("bottom mapped address should be "PTR_FORMAT", but is "PTR_FORMAT, fake_heap, array.bottom_address_mapped()));
+    assert(array.end_address_mapped() == (fake_heap + REGION_SIZE_IN_WORDS * NUM_REGIONS), "must be");
+
+    int* bottom = array.address_mapped_to(fake_heap);
+    assert((void*)bottom == (void*) array.base(), "must be");
+    int* end = array.address_mapped_to(fake_heap + REGION_SIZE_IN_WORDS * NUM_REGIONS);
+    assert((void*)end == (void*)(array.base() + array.length()), "must be");
+    // The entire array should contain default value elements
+    for (int* current = bottom; current < end; current++) {
+      assert(*current == array.default_value(), "must be");
+    }
+
+    // Test setting values in the table
+
+    HeapWord* region_start_address = fake_heap + REGION_SIZE_IN_WORDS * (NUM_REGIONS / 2);
+    HeapWord* region_end_address = fake_heap + (REGION_SIZE_IN_WORDS * (NUM_REGIONS / 2) + REGION_SIZE_IN_WORDS - 1);
+
+    // Set/get by address tests: invert some value; first retrieve one
+    int actual_value = array.get_by_index(NUM_REGIONS / 2);
+    array.set_by_index(NUM_REGIONS / 2, ~actual_value);
+    // Get the same value by address, should correspond to the start of the "region"
+    int value = array.get_by_address(region_start_address);
+    assert(value == ~actual_value, "must be");
+    // Get the same value by address, at one HeapWord before the start
+    value = array.get_by_address(region_start_address - 1);
+    assert(value == array.default_value(), "must be");
+    // Get the same value by address, at the end of the "region"
+    value = array.get_by_address(region_end_address);
+    assert(value == ~actual_value, "must be");
+    // Make sure the next value maps to another index
+    value = array.get_by_address(region_end_address + 1);
+    assert(value == array.default_value(), "must be");
+
+    // Reset the value in the array
+    array.set_by_address(region_start_address + (region_end_address - region_start_address) / 2, actual_value);
+
+    // The entire array should have the default value again
+    for (int* current = bottom; current < end; current++) {
+      assert(*current == array.default_value(), "must be");
+    }
+
+    // Set/get by index tests: invert some value
+    idx_t index = NUM_REGIONS / 2;
+    actual_value = array.get_by_index(index);
+    array.set_by_index(index, ~actual_value);
+
+    value = array.get_by_index(index);
+    assert(value == ~actual_value, "must be");
+
+    value = array.get_by_index(index - 1);
+    assert(value == array.default_value(), "must be");
+
+    value = array.get_by_index(index + 1);
+    assert(value == array.default_value(), "must be");
+
+    array.set_by_index(0, 0);
+    value = array.get_by_index(0);
+    assert(value == 0, "must be");
+
+    array.set_by_index(array.length() - 1, 0);
+    value = array.get_by_index(array.length() - 1);
+    assert(value == 0, "must be");
+
+    array.set_by_index(index, 0);
+
+    // The array should have three zeros, and default values otherwise
+    size_t num_zeros = 0;
+    for (int* current = bottom; current < end; current++) {
+      assert(*current == array.default_value() || *current == 0, "must be");
+      if (*current == 0) {
+        num_zeros++;
+      }
+    }
+    assert(num_zeros == 3, "must be");
+  }
+};
+
+void TestG1BiasedArray_test() {
+  TestMappedArray::test_biasedarray();
+}
+
+#endif
diff -r 10cc3b624f8f -r a19bea467577 src/share/vm/gc_implementation/g1/g1BiasedArray.hpp
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/share/vm/gc_implementation/g1/g1BiasedArray.hpp	Wed Sep 25 13:25:24 2013 +0200
@@ -0,0 +1,181 @@
+/*
+ * Copyright (c) 2013, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ *
+ */
+
+#ifndef SHARE_VM_GC_IMPLEMENTATION_G1_G1BIASEDARRAY_HPP
+#define SHARE_VM_GC_IMPLEMENTATION_G1_G1BIASEDARRAY_HPP
+
+#include "utilities/debug.hpp"
+#include "memory/allocation.inline.hpp"
+
+// Implements the common base functionality for arrays that contain provisions
+// for accessing its elements using a biased index.
+// The element type is defined by the instantiating the template.
+class G1BiasedMappedArrayBase VALUE_OBJ_CLASS_SPEC {
+  friend class VMStructs;
+public:
+  typedef size_t idx_t;
+protected:
+  address _base;          // the real base address
+  size_t _length;         // the length of the array
+  address _biased_base;   // base address biased by "bias" elements
+  size_t _bias;           // the bias, i.e. the offset biased_base is located to the right in elements
+  uint _shift_by;         // the amount of bits to shift right when mapping to an index of the array.
+
+protected:
+
+  G1BiasedMappedArrayBase() : _base(NULL), _length(0), _biased_base(NULL),
+    _bias(0), _shift_by(0) { }
+
+  // Allocate a new array, generic version.
+  static address create_new_base_array(size_t length, size_t elem_size) {
+    assert(length > 0, "just checking");
+    assert(elem_size > 0, "just checking");
+    return NEW_C_HEAP_ARRAY(u_char, length * elem_size, mtGC);
+  }
+
+  // Initialize the members of this class. The biased start address of this array
+  // is the bias (in elements) multiplied by the element size.
+  void initialize_base(address base, size_t length, size_t bias, size_t elem_size, uint shift_by) {
+    assert(base != NULL, "just checking");
+    assert(length > 0, "just checking");
+    assert(shift_by < sizeof(uintptr_t) * 8, err_msg("Shifting by %zd, larger than word size?", shift_by));
+    _base = base;
+    _length = length;
+    _biased_base = base - (bias * elem_size);
+    _bias = bias;
+    _shift_by = shift_by;
+  }
+
+  // Allocate and initialize this array to cover the heap addresses in the range
+  // of [bottom, end).
+  void initialize(HeapWord* bottom, HeapWord* end, size_t target_elem_size_in_bytes, size_t mapping_granularity_in_bytes) {
+    assert(mapping_granularity_in_bytes > 0, "just checking");
+    assert(is_power_of_2(mapping_granularity_in_bytes),
+      err_msg("mapping granularity must be power of 2, is %zd", mapping_granularity_in_bytes));
+    assert((uintptr_t)bottom % mapping_granularity_in_bytes == 0,
+      err_msg("bottom mapping area address must be a multiple of mapping granularity %zd, is "PTR_FORMAT,
+        mapping_granularity_in_bytes, bottom));
+    assert((uintptr_t)end % mapping_granularity_in_bytes == 0,
+      err_msg("end mapping area address must be a multiple of mapping granularity %zd, is "PTR_FORMAT,
+        mapping_granularity_in_bytes, end));
+    size_t num_target_elems = (end - bottom) / (mapping_granularity_in_bytes / HeapWordSize);
+    idx_t bias = (uintptr_t)bottom / mapping_granularity_in_bytes;
+    address base = create_new_base_array(num_target_elems, target_elem_size_in_bytes);
+    initialize_base(base, num_target_elems, bias, target_elem_size_in_bytes, log2_intptr(mapping_granularity_in_bytes));
+  }
+
+  size_t bias() const { return _bias; }
+  uint shift_by() const { return _shift_by; }
+
+  void verify_index(idx_t index) const PRODUCT_RETURN;
+  void verify_biased_index(idx_t biased_index) const PRODUCT_RETURN;
+  void verify_biased_index_inclusive_end(idx_t biased_index) const PRODUCT_RETURN;
+
+public:
+   // Return the length of the array in elements.
+   size_t length() const { return _length; }
+};
+
+// Array that provides biased access and mapping from (valid) addresses in the
+// heap into this array.
+template<class T>
+class G1BiasedMappedArray : public G1BiasedMappedArrayBase {
+public:
+  typedef G1BiasedMappedArrayBase::idx_t idx_t;
+
+  T* base() const { return (T*)G1BiasedMappedArrayBase::_base; }
+  // Return the element of the given array at the given index. Assume
+  // the index is valid. This is a convenience method that does sanity
+  // checking on the index.
+  T get_by_index(idx_t index) const {
+    verify_index(index);
+    return this->base()[index];
+  }
+
+  // Set the element of the given array at the given index to the
+  // given value. Assume the index is valid. This is a convenience
+  // method that does sanity checking on the index.
+  void set_by_index(idx_t index, T value) {
+    verify_index(index);
+    this->base()[index] = value;
+  }
+
+  // The raw biased base pointer.
+  T* biased_base() const { return (T*)G1BiasedMappedArrayBase::_biased_base; }
+
+  // Return the element of the given array that covers the given word in the
+  // heap. Assumes the index is valid.
+  T get_by_address(HeapWord* value) const {
+    idx_t biased_index = ((uintptr_t)value) >> this->shift_by();
+    this->verify_biased_index(biased_index);
+    return biased_base()[biased_index];
+  }
+
+  // Set the value of the array entry that corresponds to the given array.
+  void set_by_address(HeapWord * address, T value) {
+    idx_t biased_index = ((uintptr_t)address) >> this->shift_by();
+    this->verify_biased_index(biased_index);
+    biased_base()[biased_index] = value;
+  }
+
+protected:
+  // Returns the address of the element the given address maps to
+  T* address_mapped_to(HeapWord* address) {
+    idx_t biased_index = ((uintptr_t)address) >> this->shift_by();
+    this->verify_biased_index_inclusive_end(biased_index);
+    return biased_base() + biased_index;
+  }
+
+public:
+  // Return the smallest address (inclusive) in the heap that this array covers.
+  HeapWord* bottom_address_mapped() const {
+    return (HeapWord*) ((uintptr_t)this->bias() << this->shift_by());
+  }
+
+  // Return the highest address (exclusive) in the heap that this array covers.
+  HeapWord* end_address_mapped() const {
+    return (HeapWord*) ((uintptr_t)(this->bias() + this->length()) << this->shift_by());
+  }
+
+protected:
+  virtual T default_value() const = 0;
+  // Set all elements of the given array to the given value.
+  void clear() {
+    T value = default_value();
+    for (idx_t i = 0; i < length(); i++) {
+      set_by_index(i, value);
+    }
+  }
+public:
+  G1BiasedMappedArray() {}
+
+  // Allocate and initialize this array to cover the heap addresses in the range
+  // of [bottom, end).
+  void initialize(HeapWord* bottom, HeapWord* end, size_t mapping_granularity) {
+    G1BiasedMappedArrayBase::initialize(bottom, end, sizeof(T), mapping_granularity);
+    this->clear();
+  }
+};
+
+#endif // SHARE_VM_GC_IMPLEMENTATION_G1_G1BIASEDARRAY_HPP
diff -r 10cc3b624f8f -r a19bea467577 src/share/vm/gc_implementation/g1/g1CollectedHeap.cpp
--- a/src/share/vm/gc_implementation/g1/g1CollectedHeap.cpp	Tue Sep 24 10:14:02 2013 +0200
+++ b/src/share/vm/gc_implementation/g1/g1CollectedHeap.cpp	Wed Sep 25 13:25:24 2013 +0200
@@ -2069,8 +2069,10 @@
   _g1_storage.initialize(g1_rs, 0);
   _g1_committed = MemRegion((HeapWord*)_g1_storage.low(), (size_t) 0);
   _hrs.initialize((HeapWord*) _g1_reserved.start(),
-                  (HeapWord*) _g1_reserved.end(),
-                  _expansion_regions);
+                  (HeapWord*) _g1_reserved.end());
+  assert(_hrs.max_length() == _expansion_regions,
+         err_msg("max length: %u expansion regions: %u",
+                 _hrs.max_length(), _expansion_regions));
 
   // Do later initialization work for concurrent refinement.
   _cg1r->init();
diff -r 10cc3b624f8f -r a19bea467577 src/share/vm/gc_implementation/g1/heapRegionSeq.cpp
--- a/src/share/vm/gc_implementation/g1/heapRegionSeq.cpp	Tue Sep 24 10:14:02 2013 +0200
+++ b/src/share/vm/gc_implementation/g1/heapRegionSeq.cpp	Wed Sep 25 13:25:24 2013 +0200
@@ -71,27 +71,16 @@
 
 // Public
 
-void HeapRegionSeq::initialize(HeapWord* bottom, HeapWord* end,
-                               uint max_length) {
+void HeapRegionSeq::initialize(HeapWord* bottom, HeapWord* end) {
   assert((uintptr_t) bottom % HeapRegion::GrainBytes == 0,
          "bottom should be heap region aligned");
   assert((uintptr_t) end % HeapRegion::GrainBytes == 0,
          "end should be heap region aligned");
 
-  _length = 0;
-  _heap_bottom = bottom;
-  _heap_end = end;
-  _region_shift = HeapRegion::LogOfHRGrainBytes;
   _next_search_index = 0;
   _allocated_length = 0;
-  _max_length = max_length;
 
-  _regions = NEW_C_HEAP_ARRAY(HeapRegion*, max_length, mtGC);
-  memset(_regions, 0, (size_t) max_length * sizeof(HeapRegion*));
-  _regions_biased = _regions - ((uintx) bottom >> _region_shift);
-
-  assert(&_regions[0] == &_regions_biased[addr_to_index_biased(bottom)],
-         "bottom should be included in the region with index 0");
+  _regions.initialize(bottom, end, HeapRegion::GrainBytes);
 }
 
 MemRegion HeapRegionSeq::expand_by(HeapWord* old_end,
@@ -101,15 +90,15 @@
   G1CollectedHeap* g1h = G1CollectedHeap::heap();
 
   HeapWord* next_bottom = old_end;
-  assert(_heap_bottom <= next_bottom, "invariant");
+  assert(heap_bottom() <= next_bottom, "invariant");
   while (next_bottom < new_end) {
-    assert(next_bottom < _heap_end, "invariant");
+    assert(next_bottom < heap_end(), "invariant");
     uint index = length();
 
-    assert(index < _max_length, "otherwise we cannot expand further");
+    assert(index < max_length(), "otherwise we cannot expand further");
     if (index == 0) {
       // We have not allocated any regions so far
-      assert(next_bottom == _heap_bottom, "invariant");
+      assert(next_bottom == heap_bottom(), "invariant");
     } else {
       // next_bottom should match the end of the last/previous region
       assert(next_bottom == at(index - 1)->end(), "invariant");
@@ -122,8 +111,8 @@
         // allocation failed, we bail out and return what we have done so far
         return MemRegion(old_end, next_bottom);
       }
-      assert(_regions[index] == NULL, "invariant");
-      _regions[index] = new_hr;
+      assert(_regions.get_by_index(index) == NULL, "invariant");
+      _regions.set_by_index(index, new_hr);
       increment_allocated_length();
     }
     // Have to increment the length first, otherwise we will get an
@@ -228,26 +217,26 @@
 
 #ifndef PRODUCT
 void HeapRegionSeq::verify_optional() {
-  guarantee(_length <= _allocated_length,
+  guarantee(length() <= _allocated_length,
             err_msg("invariant: _length: %u _allocated_length: %u",
-                    _length, _allocated_length));
-  guarantee(_allocated_length <= _max_length,
+                    length(), _allocated_length));
+  guarantee(_allocated_length <= max_length(),
             err_msg("invariant: _allocated_length: %u _max_length: %u",
-                    _allocated_length, _max_length));
-  guarantee(_next_search_index <= _length,
+                    _allocated_length, max_length()));
+  guarantee(_next_search_index <= length(),
             err_msg("invariant: _next_search_index: %u _length: %u",
-                    _next_search_index, _length));
+                    _next_search_index, length()));
 
-  HeapWord* prev_end = _heap_bottom;
+  HeapWord* prev_end = heap_bottom();
   for (uint i = 0; i < _allocated_length; i += 1) {
-    HeapRegion* hr = _regions[i];
+    HeapRegion* hr = _regions.get_by_index(i);
     guarantee(hr != NULL, err_msg("invariant: i: %u", i));
     guarantee(hr->bottom() == prev_end,
               err_msg("invariant i: %u "HR_FORMAT" prev_end: "PTR_FORMAT,
                       i, HR_FORMAT_PARAMS(hr), prev_end));
     guarantee(hr->hrs_index() == i,
               err_msg("invariant: i: %u hrs_index(): %u", i, hr->hrs_index()));
-    if (i < _length) {
+    if (i < length()) {
       // Asserts will fire if i is >= _length
       HeapWord* addr = hr->bottom();
       guarantee(addr_to_region(addr) == hr, "sanity");
@@ -265,8 +254,8 @@
       prev_end = hr->end();
     }
   }
-  for (uint i = _allocated_length; i < _max_length; i += 1) {
-    guarantee(_regions[i] == NULL, err_msg("invariant i: %u", i));
+  for (uint i = _allocated_length; i < max_length(); i += 1) {
+    guarantee(_regions.get_by_index(i) == NULL, err_msg("invariant i: %u", i));
   }
 }
 #endif // PRODUCT
diff -r 10cc3b624f8f -r a19bea467577 src/share/vm/gc_implementation/g1/heapRegionSeq.hpp
--- a/src/share/vm/gc_implementation/g1/heapRegionSeq.hpp	Tue Sep 24 10:14:02 2013 +0200
+++ b/src/share/vm/gc_implementation/g1/heapRegionSeq.hpp	Wed Sep 25 13:25:24 2013 +0200
@@ -25,10 +25,17 @@
 #ifndef SHARE_VM_GC_IMPLEMENTATION_G1_HEAPREGIONSEQ_HPP
 #define SHARE_VM_GC_IMPLEMENTATION_G1_HEAPREGIONSEQ_HPP
 
+#include "gc_implementation/g1/g1BiasedArray.hpp"
+
 class HeapRegion;
 class HeapRegionClosure;
 class FreeRegionList;
 
+class G1HeapRegionTable : public G1BiasedMappedArray<HeapRegion*> {
+ protected:
+   virtual HeapRegion* default_value() const { return NULL; }
+};
+
 // This class keeps track of the region metadata (i.e., HeapRegion
 // instances). They are kept in the _regions array in address
 // order. A region's index in the array corresponds to its index in
@@ -44,35 +51,21 @@
 //
 // We keep track of three lengths:
 //
-// * _length (returned by length()) is the number of currently
+// * _committed_length (returned by length()) is the number of currently
 //   committed regions.
 // * _allocated_length (not exposed outside this class) is the
 //   number of regions for which we have HeapRegions.
-// * _max_length (returned by max_length()) is the maximum number of
-//   regions the heap can have.
+// * max_length() returns the maximum number of regions the heap can have.
 //
-// and maintain that: _length <= _allocated_length <= _max_length
+// and maintain that: _committed_length <= _allocated_length <= max_length()
 
 class HeapRegionSeq: public CHeapObj<mtGC> {
   friend class VMStructs;
 
-  // The array that holds the HeapRegions.
-  HeapRegion** _regions;
-
-  // Version of _regions biased to address 0
-  HeapRegion** _regions_biased;
+  G1HeapRegionTable _regions;
 
   // The number of regions committed in the heap.
-  uint _length;
-
-  // The address of the first reserved word in the heap.
-  HeapWord* _heap_bottom;
-
-  // The address of the last reserved word in the heap - 1.
-  HeapWord* _heap_end;
-
-  // The log of the region byte size.
-  uint _region_shift;
+  uint _committed_length;
 
   // A hint for which index to start searching from for humongous
   // allocations.
@@ -81,37 +74,33 @@
   // The number of regions for which we have allocated HeapRegions for.
   uint _allocated_length;
 
-  // The maximum number of regions in the heap.
-  uint _max_length;
-
   // Find a contiguous set of empty regions of length num, starting
   // from the given index.
   uint find_contiguous_from(uint from, uint num);
 
-  // Map a heap address to a biased region index. Assume that the
-  // address is valid.
-  inline uintx addr_to_index_biased(HeapWord* addr) const;
-
   void increment_allocated_length() {
-    assert(_allocated_length < _max_length, "pre-condition");
+    assert(_allocated_length < max_length(), "pre-condition");
     _allocated_length++;
   }
 
   void increment_length() {
-    assert(_length < _max_length, "pre-condition");
-    _length++;
+    assert(length() < max_length(), "pre-condition");
+    _committed_length++;
   }
 
   void decrement_length() {
-    assert(_length > 0, "pre-condition");
-    _length--;
+    assert(length() > 0, "pre-condition");
+    _committed_length--;
   }
 
+  HeapWord* heap_bottom() const { return _regions.bottom_address_mapped(); }
+  HeapWord* heap_end() const {return _regions.end_address_mapped(); }
+
  public:
   // Empty contructor, we'll initialize it with the initialize() method.
-  HeapRegionSeq() { }
+  HeapRegionSeq() : _regions(), _committed_length(0), _next_search_index(0), _allocated_length(0) { }
 
-  void initialize(HeapWord* bottom, HeapWord* end, uint max_length);
+  void initialize(HeapWord* bottom, HeapWord* end);
 
   // Return the HeapRegion at the given index. Assume that the index
   // is valid.
@@ -126,10 +115,10 @@
   inline HeapRegion* addr_to_region_unsafe(HeapWord* addr) const;
 
   // Return the number of regions that have been committed in the heap.
-  uint length() const { return _length; }
+  uint length() const { return _committed_length; }
 
   // Return the maximum number of regions in the heap.
-  uint max_length() const { return _max_length; }
+  uint max_length() const { return (uint)_regions.length(); }
 
   // Expand the sequence to reflect that the heap has grown from
   // old_end to new_end. Either create new HeapRegions, or re-use
diff -r 10cc3b624f8f -r a19bea467577 src/share/vm/gc_implementation/g1/heapRegionSeq.inline.hpp
--- a/src/share/vm/gc_implementation/g1/heapRegionSeq.inline.hpp	Tue Sep 24 10:14:02 2013 +0200
+++ b/src/share/vm/gc_implementation/g1/heapRegionSeq.inline.hpp	Wed Sep 25 13:25:24 2013 +0200
@@ -28,28 +28,16 @@
 #include "gc_implementation/g1/heapRegion.hpp"
 #include "gc_implementation/g1/heapRegionSeq.hpp"
 
-inline uintx HeapRegionSeq::addr_to_index_biased(HeapWord* addr) const {
-  assert(_heap_bottom <= addr && addr < _heap_end,
-         err_msg("addr: "PTR_FORMAT" bottom: "PTR_FORMAT" end: "PTR_FORMAT,
-                 addr, _heap_bottom, _heap_end));
-  uintx index = (uintx) addr >> _region_shift;
-  return index;
-}
-
 inline HeapRegion* HeapRegionSeq::addr_to_region_unsafe(HeapWord* addr) const {
-  assert(_heap_bottom <= addr && addr < _heap_end,
-         err_msg("addr: "PTR_FORMAT" bottom: "PTR_FORMAT" end: "PTR_FORMAT,
-                 addr, _heap_bottom, _heap_end));
-  uintx index_biased = addr_to_index_biased(addr);
-  HeapRegion* hr = _regions_biased[index_biased];
+  HeapRegion* hr = _regions.get_by_address(addr);
   assert(hr != NULL, "invariant");
   return hr;
 }
 
 inline HeapRegion* HeapRegionSeq::addr_to_region(HeapWord* addr) const {
-  if (addr != NULL && addr < _heap_end) {
-    assert(addr >= _heap_bottom,
-          err_msg("addr: "PTR_FORMAT" bottom: "PTR_FORMAT, addr, _heap_bottom));
+  if (addr != NULL && addr < heap_end()) {
+    assert(addr >= heap_bottom(),
+          err_msg("addr: "PTR_FORMAT" bottom: "PTR_FORMAT, addr, heap_bottom()));
     return addr_to_region_unsafe(addr);
   }
   return NULL;
@@ -57,7 +45,7 @@
 
 inline HeapRegion* HeapRegionSeq::at(uint index) const {
   assert(index < length(), "pre-condition");
-  HeapRegion* hr = _regions[index];
+  HeapRegion* hr = _regions.get_by_index(index);
   assert(hr != NULL, "sanity");
   assert(hr->hrs_index() == index, "sanity");
   return hr;
diff -r 10cc3b624f8f -r a19bea467577 src/share/vm/gc_implementation/g1/vmStructs_g1.hpp
--- a/src/share/vm/gc_implementation/g1/vmStructs_g1.hpp	Tue Sep 24 10:14:02 2013 +0200
+++ b/src/share/vm/gc_implementation/g1/vmStructs_g1.hpp	Wed Sep 25 13:25:24 2013 +0200
@@ -34,8 +34,14 @@
   static_field(HeapRegion, GrainBytes,        size_t)                         \
   static_field(HeapRegion, LogOfHRGrainBytes, int)                            \
                                                                               \
-  nonstatic_field(HeapRegionSeq,   _regions, HeapRegion**)                    \
-  nonstatic_field(HeapRegionSeq,   _length,  uint)                            \
+  nonstatic_field(G1HeapRegionTable, _base,             address)              \
+  nonstatic_field(G1HeapRegionTable, _length,           size_t)               \
+  nonstatic_field(G1HeapRegionTable, _biased_base,      address)              \
+  nonstatic_field(G1HeapRegionTable, _bias,             size_t)               \
+  nonstatic_field(G1HeapRegionTable, _shift_by,         uint)                 \
+                                                                              \
+  nonstatic_field(HeapRegionSeq,   _regions,            G1HeapRegionTable)    \
+  nonstatic_field(HeapRegionSeq,   _committed_length,   uint)                 \
                                                                               \
   nonstatic_field(G1CollectedHeap, _hrs,                HeapRegionSeq)        \
   nonstatic_field(G1CollectedHeap, _g1_committed,       MemRegion)            \
@@ -58,6 +64,8 @@
 
 #define VM_TYPES_G1(declare_type, declare_toplevel_type)                      \
                                                                               \
+  declare_toplevel_type(G1HeapRegionTable)                                    \
+                                                                              \
   declare_type(G1CollectedHeap, SharedHeap)                                   \
                                                                               \
   declare_type(HeapRegion, ContiguousSpace)                                   \
diff -r 10cc3b624f8f -r a19bea467577 src/share/vm/prims/jni.cpp
--- a/src/share/vm/prims/jni.cpp	Tue Sep 24 10:14:02 2013 +0200
+++ b/src/share/vm/prims/jni.cpp	Wed Sep 25 13:25:24 2013 +0200
@@ -5047,6 +5047,9 @@
 void TestReserveMemorySpecial_test();
 void TestVirtualSpace_test();
 void MetaspaceAux_test();
+#if INCLUDE_ALL_GCS
+void TestG1BiasedArray_test();
+#endif
 
 void execute_internal_vm_tests() {
   if (ExecuteInternalVMTests) {
@@ -5066,6 +5069,7 @@
     run_unit_test(VMStructs::test());
 #endif
 #if INCLUDE_ALL_GCS
+    run_unit_test(TestG1BiasedArray_test());
     run_unit_test(HeapRegionRemSet::test_prt());
 #endif
     tty->print_cr("All internal VM tests passed");