1 /*
2 * Copyright (c) 2013, 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_G1HEAPSPANNINGTABLE_HPP
26 #define SHARE_VM_GC_IMPLEMENTATION_G1_G1HEAPSPANNINGTABLE_HPP
27
28 #include "memory/allocation.inline.hpp"
29
30 // The G1HeapSpanningTable class is a utility class that provides
31 // facilities to subclasses that divide the G1 heap into fixed size
32 // chunks (e.g. heap regions) and use an array or arrays that have one
33 // entry per such chunk. It provides methods that can retrieve an
34 // array element given either an index or a heap address. For the case
35 // where the given heap address is known to be valid (i.e., within the
36 // G1 heap) a fast look-up is also provided (using a version of the
37 // array pointer that is biased to address 0). The G1HeapSpanningTable
38 // class keeps track of both the max length of the array as well as
39 // which part of it is actively used.
40
41 template <class T>
42 class G1HeapSpanningTable : public CHeapObj<mtGC> {
43 protected:
44 // Sub classes should override this.
45 virtual T default_value() const = 0;
46
47 // The address of the first reserved word in the heap.
48 HeapWord* _heap_bottom;
49
50 // The active bound of the heap, i.e., the address of the last
51 // committed word in the heap + 1.
52 HeapWord* _heap_end;
53
54 // The maximum bound of the heap, i.e., the address of the last
55 // reserved word in the heap + 1.
56 HeapWord* _max_heap_end;
57
58 // The active number of array elements.
59 uint _length;
60
61 // The maximum value _length has ever grown to.
62 uint _length_high_watermark;
63
64 // The max number of array elements.
65 uint _max_length;
66
67 // The log of the heap subdivision size in bytes.
68 uint _shift_by;
69
70 // Return the number of array elements for the given heap bound.
71 uint length_for(HeapWord* end) {
72 assert(_heap_bottom <= end && end <= _max_heap_end,
73 err_msg("end: "PTR_FORMAT" bottom: "PTR_FORMAT" max end: "PTR_FORMAT, \
74 end, _heap_bottom, _max_heap_end));
75 size_t diff_bytes = pointer_delta(end, _heap_bottom, sizeof(char));
76 uint length = (uint) (diff_bytes >> _shift_by);
77 assert(((size_t)(length << _shift_by)) == diff_bytes, "sanity");
78 assert(length <= _max_length,
79 err_msg("length: %u max length: %u", length, _max_length));
80 return length;
81 }
82
83 // getters and setters with index
84
85 // Return the element of the given array at the given index. Assume
86 // the index is valid. This is a convenience method that does sanity
87 // checking on the index.
88 T get(T* array, uint index) const {
89 assert(index < _length, err_msg("index: %u length: %u", index, _length));
90 return array[index];
91 }
92
93 // Set the element of the given array at the given index to the
94 // given value. Assume the index is valid. This is a convenience
95 // method that does sanity checking on the index.
96 void set(T* array, uint index, T value) {
97 assert(index < _length, err_msg("index: %u length: %u", index, _length));
98 array[index] = value;
99 }
100
101 // getters with address (normal and fast versions)
102
103 // Map a heap address to a biased index. Assume that the address is valid.
104 uintx addr_to_index_biased(HeapWord* addr) const {
105 assert(_heap_bottom <= addr && addr < _max_heap_end,
106 err_msg("addr: "PTR_FORMAT" bottom: "PTR_FORMAT" end: "PTR_FORMAT,
107 addr, _heap_bottom, _max_heap_end));
108 return (uintx) addr >> _shift_by;
109 }
110
111 // Return the element of the given array that corresponds to the
112 // given address. The array should be the biased version. Assume
113 // that the address is valid.
114 T get_unsafe(T* array_biased, HeapWord* addr) const {
115 // No need to check the validity of addr as addr_to_index_biased()
116 // will do so.
117 uintx index_biased = addr_to_index_biased(addr);
118 return array_biased[index_biased];
119 }
120
121 // Allocate, clear, and return a new array.
122 T* create_new_array() { return (T*) create_new_array_base(); }
123
124 // Return the biased (to address 0) address of the given array.
125 T* get_biased_array(T* array) {
126 T* array_biased = array - (uintx) ((uintptr_t) _heap_bottom >> _shift_by);
127 assert(&array[0] == &array_biased[addr_to_index_biased(_heap_bottom)],
128 "array slot 0 should be the same as as the biased slot for bottom");
129 return array_biased;
130 }
131
132 // Set all elements of the given array to the default value.
133 void clear(T* array) {
134 for (uint i=0; i < max_length(); i += 1) {
135 array[i] = default_value();
136 }
137 }
138
139 // Allocate, clear, and return a new array.
140 T* create_new_array_base() {
141 T* array = (T*) NEW_C_HEAP_ARRAY(char, array_size_bytes(), mtGC);
142 clear(array);
143 return array;
144 }
145
146 // Size of the array in bytes.
147 size_t array_size_bytes() {
148 return (size_t) _max_length * sizeof(T);
149 }
150
151 // Update all fields to reflect that the heap end has been moved.
152 // Return the previous heap end.
153 HeapWord* update_heap_end(HeapWord* new_end) {
154 HeapWord* old_heap_end = _heap_end;
155
156 // length_for() will verify new_end so we don't have to do it here too.
157 uint new_length = length_for(new_end);
158 _length = new_length;
159 if (new_length > _length_high_watermark) {
160 _length_high_watermark = new_length;
161 }
162 _heap_end = new_end;
163
164 return old_heap_end;
165 }
166
167 // Determine whether the address falls into the G1 heap or not.
168 bool in_g1_heap(HeapWord* addr) const {
169 assert(addr == NULL || addr >= _heap_bottom,
170 err_msg("addr: "PTR_FORMAT" bottom: "PTR_FORMAT, addr, _heap_bottom));
171 // We always check against _max_heap_end instead of_heap_end.
172 // Sometimes we expand the heap during a GC concurrently
173 // with other threads and this avoids any potential races.
174 return addr != NULL && addr < _max_heap_end;
175 }
176
177 // Empty constructor, we'll do all initialization in the initialize() method.
178 G1HeapSpanningTable() { }
179
180 void initialize_base(HeapWord* bottom, HeapWord* max_end, uint shift_by) {
181 _shift_by = shift_by;
182
183 _heap_bottom = bottom;
184 _heap_end = bottom;
185 _max_heap_end = max_end;
186
187 _length = 0;
188 _length_high_watermark = 0;
189 _max_length = length_for(max_end);
190 }
191
192 #ifndef PRODUCT
193 // Do sanity checking.
194 void verify_optional() {
195 uint length_for_heap_end = length_for(_heap_end);
196 guarantee(length_for_heap_end == _length,
197 err_msg("invariant: _length: %u _heap_end: "PTR_FORMAT" %u",
198 _length, _heap_end, length_for_heap_end));
199 guarantee(_length <= _length_high_watermark,
200 err_msg("invariant: _length: %u _length_high_watermark: %u",
201 _length, _length_high_watermark));
202 guarantee(_length_high_watermark <= _max_length,
203 err_msg("invariant: _length_high_watermark: %u _max_length: %u",
204 _length_high_watermark, _max_length));
205 }
206 #endif // !PRODUCT
207
208 public:
209 // Return the active number of array elements.
210 uint length() const { return _length; }
211
212 // Return the maximum number of array elements.
213 uint max_length() const { return _max_length; }
214 };
215
216 #endif // SHARE_VM_GC_IMPLEMENTATION_G1_G1HEAPSPANNINGTABLE_HPP