1 /*
   2  * Copyright (c) 2013, 2014, 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_G1BIASEDARRAY_HPP
  26 #define SHARE_VM_GC_IMPLEMENTATION_G1_G1BIASEDARRAY_HPP
  27 
  28 #include "memory/allocation.hpp"
  29 #include "utilities/debug.hpp"
  30 
  31 // Implements the common base functionality for arrays that contain provisions
  32 // for accessing its elements using a biased index.
  33 // The element type is defined by the instantiating the template.
  34 class G1BiasedMappedArrayBase VALUE_OBJ_CLASS_SPEC {
  35   friend class VMStructs;
  36 public:
  37   typedef size_t idx_t;
  38 protected:
  39   address _base;          // the real base address
  40   size_t _length;         // the length of the array
  41   address _biased_base;   // base address biased by "bias" elements
  42   size_t _bias;           // the bias, i.e. the offset biased_base is located to the right in elements
  43   uint _shift_by;         // the amount of bits to shift right when mapping to an index of the array.
  44 
  45 protected:
  46 
  47   G1BiasedMappedArrayBase() : _base(NULL), _length(0), _biased_base(NULL),
  48     _bias(0), _shift_by(0) { }
  49 
  50   // Allocate a new array, generic version.
  51   static address create_new_base_array(size_t length, size_t elem_size);
  52 
  53   // Initialize the members of this class. The biased start address of this array
  54   // is the bias (in elements) multiplied by the element size.
  55   void initialize_base(address base, size_t length, size_t bias, size_t elem_size, uint shift_by) {
  56     assert(base != NULL, "just checking");
  57     assert(length > 0, "just checking");
  58     assert(shift_by < sizeof(uintptr_t) * 8, err_msg("Shifting by " SSIZE_FORMAT ", larger than word size?", (size_t) shift_by));
  59     _base = base;
  60     _length = length;
  61     _biased_base = base - (bias * elem_size);
  62     _bias = bias;
  63     _shift_by = shift_by;
  64   }
  65 
  66   // Allocate and initialize this array to cover the heap addresses in the range
  67   // of [bottom, end).
  68   void initialize(HeapWord* bottom, HeapWord* end, size_t target_elem_size_in_bytes, size_t mapping_granularity_in_bytes) {
  69     assert(mapping_granularity_in_bytes > 0, "just checking");
  70     assert(is_power_of_2(mapping_granularity_in_bytes),
  71       err_msg("mapping granularity must be power of 2, is %zd", mapping_granularity_in_bytes));
  72     assert((uintptr_t)bottom % mapping_granularity_in_bytes == 0,
  73       err_msg("bottom mapping area address must be a multiple of mapping granularity %zd, is " PTR_FORMAT,
  74         mapping_granularity_in_bytes, p2i(bottom)));
  75     assert((uintptr_t)end % mapping_granularity_in_bytes == 0,
  76       err_msg("end mapping area address must be a multiple of mapping granularity %zd, is " PTR_FORMAT,
  77         mapping_granularity_in_bytes, p2i(end)));
  78     size_t num_target_elems = (end - bottom) / (mapping_granularity_in_bytes / HeapWordSize);
  79     idx_t bias = (uintptr_t)bottom / mapping_granularity_in_bytes;
  80     address base = create_new_base_array(num_target_elems, target_elem_size_in_bytes);
  81     initialize_base(base, num_target_elems, bias, target_elem_size_in_bytes, log2_intptr(mapping_granularity_in_bytes));
  82   }
  83 
  84   size_t bias() const { return _bias; }
  85   uint shift_by() const { return _shift_by; }
  86 
  87   void verify_index(idx_t index) const PRODUCT_RETURN;
  88   void verify_biased_index(idx_t biased_index) const PRODUCT_RETURN;
  89   void verify_biased_index_inclusive_end(idx_t biased_index) const PRODUCT_RETURN;
  90 
  91 public:
  92    // Return the length of the array in elements.
  93    size_t length() const { return _length; }
  94 };
  95 
  96 // Array that provides biased access and mapping from (valid) addresses in the
  97 // heap into this array.
  98 template<class T>
  99 class G1BiasedMappedArray : public G1BiasedMappedArrayBase {
 100 public:
 101   typedef G1BiasedMappedArrayBase::idx_t idx_t;
 102 
 103   T* base() const { return (T*)G1BiasedMappedArrayBase::_base; }
 104   // Return the element of the given array at the given index. Assume
 105   // the index is valid. This is a convenience method that does sanity
 106   // checking on the index.
 107   T get_by_index(idx_t index) const {
 108     verify_index(index);
 109     return this->base()[index];
 110   }
 111 
 112   // Set the element of the given array at the given index to the
 113   // given value. Assume the index is valid. This is a convenience
 114   // method that does sanity checking on the index.
 115   void set_by_index(idx_t index, T value) {
 116     verify_index(index);
 117     this->base()[index] = value;
 118   }
 119 
 120   // The raw biased base pointer.
 121   T* biased_base() const { return (T*)G1BiasedMappedArrayBase::_biased_base; }
 122 
 123   // Return the element of the given array that covers the given word in the
 124   // heap. Assumes the index is valid.
 125   T get_by_address(HeapWord* value) const {
 126     idx_t biased_index = ((uintptr_t)value) >> this->shift_by();
 127     this->verify_biased_index(biased_index);
 128     return biased_base()[biased_index];
 129   }
 130 
 131   // Set the value of the array entry that corresponds to the given array.
 132   void set_by_address(HeapWord * address, T value) {
 133     idx_t biased_index = ((uintptr_t)address) >> this->shift_by();
 134     this->verify_biased_index(biased_index);
 135     biased_base()[biased_index] = value;
 136   }
 137 
 138 protected:
 139   // Returns the address of the element the given address maps to
 140   T* address_mapped_to(HeapWord* address) {
 141     idx_t biased_index = ((uintptr_t)address) >> this->shift_by();
 142     this->verify_biased_index_inclusive_end(biased_index);
 143     return biased_base() + biased_index;
 144   }
 145 
 146 public:
 147   // Return the smallest address (inclusive) in the heap that this array covers.
 148   HeapWord* bottom_address_mapped() const {
 149     return (HeapWord*) ((uintptr_t)this->bias() << this->shift_by());
 150   }
 151 
 152   // Return the highest address (exclusive) in the heap that this array covers.
 153   HeapWord* end_address_mapped() const {
 154     return (HeapWord*) ((uintptr_t)(this->bias() + this->length()) << this->shift_by());
 155   }
 156 
 157 protected:
 158   virtual T default_value() const = 0;
 159   // Set all elements of the given array to the given value.
 160   void clear() {
 161     T value = default_value();
 162     for (idx_t i = 0; i < length(); i++) {
 163       set_by_index(i, value);
 164     }
 165   }
 166 public:
 167   G1BiasedMappedArray() {}
 168 
 169   // Allocate and initialize this array to cover the heap addresses in the range
 170   // of [bottom, end).
 171   void initialize(HeapWord* bottom, HeapWord* end, size_t mapping_granularity) {
 172     G1BiasedMappedArrayBase::initialize(bottom, end, sizeof(T), mapping_granularity);
 173     this->clear();
 174   }
 175 };
 176 
 177 #endif // SHARE_VM_GC_IMPLEMENTATION_G1_G1BIASEDARRAY_HPP