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 #include "gc_implementation/g1/heapRegionSet.hpp"
30
31 class HeapRegion;
32 class HeapRegionClosure;
33 class FreeRegionList;
34
35 class G1HeapRegionTable : public G1BiasedMappedArray<HeapRegion*> {
36 protected:
37 virtual HeapRegion* default_value() const { return NULL; }
38 };
39
40 // This class keeps track of the region metadata (i.e., HeapRegion
41 // instances). They are kept in the _regions array in address
42 // order. A region's index in the array corresponds to its index in
43 // the heap (i.e., 0 is the region at the bottom of the heap, 1 is
44 // the one after it, etc.). Two regions that are consecutive in the
45 // array should also be adjacent in the address space (i.e.,
46 // region(i).end() == region(i+1).bottom().
47 //
48 // We create a HeapRegion when we commit the region's address space
49 // for the first time. When we uncommit the address space of a
50 // region we retain the HeapRegion to be able to re-use it in the
51 // future (in case we recommit it).
52 //
53 // We keep track of three lengths:
54 //
55 // * _committed_length (returned by length()) is the number of currently
56 // committed regions.
57 // * _allocated_length (not exposed outside this class) is the
58 // number of regions for which we have HeapRegions.
59 // * max_length() returns the maximum number of regions the heap can have.
60 //
61 // and maintain that: _committed_length <= _allocated_length <= max_length()
62
63 class HeapRegionSeq: public CHeapObj<mtGC> {
64 friend class VMStructs;
65
66 G1HeapRegionTable _regions;
67
68 ReservedSpace _reserved;
69 VirtualSpace _storage;
70
71 FreeRegionList _free_list;
72
73 // The number of regions committed in the heap.
74 uint _num_committed;
75
76 // Internal only. The highest heap region +1 we allocated a HeapRegion instance for.
77 uint _allocated_heapregions_length;
78
79 HeapWord* heap_bottom() const { return _regions.bottom_address_mapped(); }
80 HeapWord* heap_top() const { return heap_bottom() + _num_committed * HeapRegion::GrainWords; }
81 HeapWord* heap_end() const {return _regions.end_address_mapped(); }
82
83 void make_regions_available(uint index, uint num_regions = 1);
84
85 // Pass down commit calls to the VirtualSpace.
86 void commit_regions(uint index, size_t num_regions = 1);
87 void uncommit_regions(uint index, size_t num_regions = 1);
88
89 // Notify other data structures about change in the heap layout.
90 void update_committed_space(HeapWord* old_end, HeapWord* new_end);
91 // Calculate the starting region for each worker during parallel iteration so
92 // that they do not all start from the same region.
93 uint start_region_for_worker(uint worker_i, uint num_workers, uint num_regions) const;
94
95 // Finds the next sequence of unavailable regions starting from start_idx. Returns the
96 // length of the sequence found. If this result is zero, no such sequence could be found,
97 // otherwise res_idx indicates the start index of these regions.
98 uint find_unavailable_from_idx(uint start_idx, uint* res_idx) const;
99 // Finds the next sequence of empty regions starting from start_idx, going backwards in
100 // the heap. Returns the length of the sequence found. If this value is zero, no
101 // sequence could be found, otherwise res_idx contains the start index of this range.
102 uint find_empty_from_idx_reverse(uint start_idx, uint* res_idx) const;
103 #ifdef ASSERT
104 public:
105 bool is_free(HeapRegion* hr) const;
106 #endif
107 // Returns whether the given region is available for allocation.
108 bool is_available(uint region) const;
109
110 // Allocate a new HeapRegion for the given index.
111 HeapRegion* new_heap_region(uint hrs_index);
112 public:
113 // Empty constructor, we'll initialize it with the initialize() method.
114 HeapRegionSeq() : _regions(), _reserved(), _storage(), _num_committed(0),
115 _free_list("Master Free List", new MasterFreeRegionListMtSafeChecker()),
116 _allocated_heapregions_length(0)
117 { }
118
119 void initialize(ReservedSpace reserved);
120
121 // Return the "dummy" region used for G1AllocRegion. This is currently a hardwired
122 // new HeapRegion that owns HeapRegion at index 0. Since at the moment we commit
123 // the heap from the lowest address, this region (and its associated data
124 // structures) are available and we do not need to check further.
125 HeapRegion* get_dummy_region() { return new_heap_region(0); }
126
127 // Return the HeapRegion at the given index. Assume that the index
128 // is valid.
129 inline HeapRegion* at(uint index) const;
130
131 // If addr is within the committed space return its corresponding
132 // HeapRegion, otherwise return NULL.
133 inline HeapRegion* addr_to_region(HeapWord* addr) const;
134
135 // Insert the given region into the free region list.
136 inline void insert_into_free_list(HeapRegion* hr);
137
138 // Insert the given region list into the global free region list.
139 void insert_list_into_free_list(FreeRegionList* list) {
158 }
159
160 // Return the number of committed free regions in the heap.
161 uint num_free_regions() const {
162 return _free_list.length();
163 }
164
165 size_t total_capacity_bytes() const {
166 return num_free_regions() * HeapRegion::GrainBytes;
167 }
168
169 // Return the number of available (uncommitted) regions.
170 uint available() const { return max_length() - length(); }
171
172 // Return the number of regions that have been committed in the heap.
173 uint length() const { return _num_committed; }
174
175 // Return the maximum number of regions in the heap.
176 uint max_length() const { return (uint)_regions.length(); }
177
178 MemRegion committed() const { MemRegion temp(heap_bottom(), heap_top()); return temp; }
179
180 MemRegion reserved() const { MemRegion temp(heap_bottom(), heap_end()); return temp; }
181
182 // Expand the sequence to reflect that the heap has grown. Either create new
183 // HeapRegions, or re-use existing ones. Returns the number of regions the
184 // sequence was expanded by. If a HeapRegion allocation fails, the resulting
185 // number of regions might be smaller than what's desired.
186 uint expand_by(uint num_regions);
187
188 // Makes sure that the regions from start to start+num_regions-1 are available
189 // for allocation. Returns the number of regions that were committed to achieve
190 // this.
191 uint expand_at(uint start, uint num_regions);
192
193 // Find a contiguous set of empty or uncommitted regions of length num and return
194 // the index of the first region or G1_NO_HRS_INDEX if the search was unsuccessful.
195 // If only_empty is true, only empty regions are considered.
196 // Searches from bottom to top of the heap, doing a first-fit.
197 uint find_contiguous(size_t num, bool only_empty);
198
199 HeapRegion* next_region_in_heap(const HeapRegion* r) const;
200
201 // Apply blk->doHeapRegion() on all committed regions in address order,
202 // terminating the iteration early if doHeapRegion() returns true.
203 void iterate(HeapRegionClosure* blk) const;
204
205 void par_iterate(HeapRegionClosure* blk, uint worker_id, uint no_of_par_workers, jint claim_value) const;
206
207 // Uncommit up to num_regions_to_remove regions that are completely free.
208 // Return the actual number of uncommitted regions.
209 uint shrink_by(uint num_regions_to_remove);
210
211 void verify();
212
213 // Do some sanity checking.
214 void verify_optional() PRODUCT_RETURN;
215 };
216
217 #endif // SHARE_VM_GC_IMPLEMENTATION_G1_HEAPREGIONSEQ_HPP
|
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 #include "gc_implementation/g1/g1RegionToSpaceMapper.hpp"
30 #include "gc_implementation/g1/heapRegionSet.hpp"
31
32 class HeapRegion;
33 class HeapRegionClosure;
34 class FreeRegionList;
35
36 class G1HeapRegionTable : public G1BiasedMappedArray<HeapRegion*> {
37 protected:
38 virtual HeapRegion* default_value() const { return NULL; }
39 };
40
41 // This class keeps track of the actual heap memory, auxiliary data
42 // and its metadata (i.e., HeapRegion instances) and the list of free regions.
43 //
44 // This allows maximum flexibility for deciding what to commit or uncommit given
45 // a request from outside.
46 //
47 // HeapRegions are kept in the _regions array in address order. A region's
48 // index in the array corresponds to its index in the heap (i.e., 0 is the
49 // region at the bottom of the heap, 1 is the one after it, etc.). Two
50 // regions that are consecutive in the array should also be adjacent in the
51 // address space (i.e., region(i).end() == region(i+1).bottom().
52 //
53 // We create a HeapRegion when we commit the region's address space
54 // for the first time. When we uncommit the address space of a
55 // region we retain the HeapRegion to be able to re-use it in the
56 // future (in case we recommit it).
57 //
58 // We keep track of three lengths:
59 //
60 // * _num_committed (returned by length()) is the number of currently
61 // committed regions. These may not be contiguous.
62 // * _allocated_heapregions_length (not exposed outside this class) is the
63 // number of regions+1 for which we have HeapRegions.
64 // * max_length() returns the maximum number of regions the heap can have.
65 //
66
67 class HeapRegionSeq: public CHeapObj<mtGC> {
68 friend class VMStructs;
69
70 G1HeapRegionTable _regions;
71
72 G1RegionToSpaceMapper* _heap_mapper;
73 G1RegionToSpaceMapper* _prev_bitmap_mapper;
74 G1RegionToSpaceMapper* _next_bitmap_mapper;
75 G1RegionToSpaceMapper* _bot_mapper;
76 G1RegionToSpaceMapper* _cardtable_mapper;
77 G1RegionToSpaceMapper* _card_counts_mapper;
78
79 FreeRegionList _free_list;
80
81 // Each bit in this bitmap indicates that the corresponding region is available
82 // for allocation.
83 BitMap _available_map;
84
85 // The number of regions committed in the heap.
86 uint _num_committed;
87
88 // Internal only. The highest heap region +1 we allocated a HeapRegion instance for.
89 uint _allocated_heapregions_length;
90
91 HeapWord* heap_bottom() const { return _regions.bottom_address_mapped(); }
92 HeapWord* heap_end() const {return _regions.end_address_mapped(); }
93
94 void make_regions_available(uint index, uint num_regions = 1);
95
96 // Pass down commit calls to the VirtualSpace.
97 void commit_regions(uint index, size_t num_regions = 1);
98 void uncommit_regions(uint index, size_t num_regions = 1);
99
100 // Notify other data structures about change in the heap layout.
101 void update_committed_space(HeapWord* old_end, HeapWord* new_end);
102 // Calculate the starting region for each worker during parallel iteration so
103 // that they do not all start from the same region.
104 uint start_region_for_worker(uint worker_i, uint num_workers, uint num_regions) const;
105
106 // Find a contiguous set of empty or uncommitted regions of length num and return
107 // the index of the first region or G1_NO_HRS_INDEX if the search was unsuccessful.
108 // If only_empty is true, only empty regions are considered.
109 // Searches from bottom to top of the heap, doing a first-fit.
110 uint find_contiguous(size_t num, bool only_empty);
111 // Finds the next sequence of unavailable regions starting from start_idx. Returns the
112 // length of the sequence found. If this result is zero, no such sequence could be found,
113 // otherwise res_idx indicates the start index of these regions.
114 uint find_unavailable_from_idx(uint start_idx, uint* res_idx) const;
115 // Finds the next sequence of empty regions starting from start_idx, going backwards in
116 // the heap. Returns the length of the sequence found. If this value is zero, no
117 // sequence could be found, otherwise res_idx contains the start index of this range.
118 uint find_empty_from_idx_reverse(uint start_idx, uint* res_idx) const;
119 // Allocate a new HeapRegion for the given index.
120 HeapRegion* new_heap_region(uint hrs_index);
121 #ifdef ASSERT
122 public:
123 bool is_free(HeapRegion* hr) const;
124 #endif
125 // Returns whether the given region is available for allocation.
126 bool is_available(uint region) const;
127
128 public:
129 // Empty constructor, we'll initialize it with the initialize() method.
130 HeapRegionSeq() : _regions(), _heap_mapper(NULL), _num_committed(0),
131 _next_bitmap_mapper(NULL), _prev_bitmap_mapper(NULL), _bot_mapper(NULL),
132 _allocated_heapregions_length(0), _available_map(),
133 _free_list("Free list", new MasterFreeRegionListMtSafeChecker())
134 { }
135
136 void initialize(G1RegionToSpaceMapper* heap_storage,
137 G1RegionToSpaceMapper* prev_bitmap,
138 G1RegionToSpaceMapper* next_bitmap,
139 G1RegionToSpaceMapper* bot,
140 G1RegionToSpaceMapper* cardtable,
141 G1RegionToSpaceMapper* card_counts);
142
143 // Return the "dummy" region used for G1AllocRegion. This is currently a hardwired
144 // new HeapRegion that owns HeapRegion at index 0. Since at the moment we commit
145 // the heap from the lowest address, this region (and its associated data
146 // structures) are available and we do not need to check further.
147 HeapRegion* get_dummy_region() { return new_heap_region(0); }
148
149 // Return the HeapRegion at the given index. Assume that the index
150 // is valid.
151 inline HeapRegion* at(uint index) const;
152
153 // If addr is within the committed space return its corresponding
154 // HeapRegion, otherwise return NULL.
155 inline HeapRegion* addr_to_region(HeapWord* addr) const;
156
157 // Insert the given region into the free region list.
158 inline void insert_into_free_list(HeapRegion* hr);
159
160 // Insert the given region list into the global free region list.
161 void insert_list_into_free_list(FreeRegionList* list) {
180 }
181
182 // Return the number of committed free regions in the heap.
183 uint num_free_regions() const {
184 return _free_list.length();
185 }
186
187 size_t total_capacity_bytes() const {
188 return num_free_regions() * HeapRegion::GrainBytes;
189 }
190
191 // Return the number of available (uncommitted) regions.
192 uint available() const { return max_length() - length(); }
193
194 // Return the number of regions that have been committed in the heap.
195 uint length() const { return _num_committed; }
196
197 // Return the maximum number of regions in the heap.
198 uint max_length() const { return (uint)_regions.length(); }
199
200 MemRegion reserved() const { MemRegion temp(heap_bottom(), heap_end()); return temp; }
201
202 // Expand the sequence to reflect that the heap has grown. Either create new
203 // HeapRegions, or re-use existing ones. Returns the number of regions the
204 // sequence was expanded by. If a HeapRegion allocation fails, the resulting
205 // number of regions might be smaller than what's desired.
206 uint expand_by(uint num_regions);
207
208 // Makes sure that the regions from start to start+num_regions-1 are available
209 // for allocation. Returns the number of regions that were committed to achieve
210 // this.
211 uint expand_at(uint start, uint num_regions);
212
213 // Find a contiguous set of empty regions of length num. Returns the start index of
214 // that set, or G1_NO_HRS_INDEX.
215 uint find_contiguous_only_empty(size_t num) { return find_contiguous(num, true); }
216 // Find a contiguous set of empty or unavailable regions of length num. Returns the
217 // start index of that set, or G1_NO_HRS_INDEX.
218 uint find_contiguous_empty_or_unavailable(size_t num) { return find_contiguous(num, false); }
219
220 HeapRegion* next_region_in_heap(const HeapRegion* r) const;
221
222 // Apply blk->doHeapRegion() on all committed regions in address order,
223 // terminating the iteration early if doHeapRegion() returns true.
224 void iterate(HeapRegionClosure* blk) const;
225
226 void par_iterate(HeapRegionClosure* blk, uint worker_id, uint no_of_par_workers, jint claim_value) const;
227
228 // Uncommit up to num_regions_to_remove regions that are completely free.
229 // Return the actual number of uncommitted regions.
230 uint shrink_by(uint num_regions_to_remove);
231
232 void verify();
233
234 // Do some sanity checking.
235 void verify_optional() PRODUCT_RETURN;
236 };
237
238 #endif // SHARE_VM_GC_IMPLEMENTATION_G1_HEAPREGIONSEQ_HPP
|