1 /*
2 * Copyright (c) 2017, 2020, 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 #include "precompiled.hpp"
25 #include "gc/z/zArray.inline.hpp"
26 #include "gc/z/zPage.inline.hpp"
27 #include "gc/z/zRelocationSet.hpp"
28 #include "gc/z/zRelocationSetSelector.inline.hpp"
29 #include "jfr/jfrEvents.hpp"
30 #include "logging/log.hpp"
31 #include "runtime/globals.hpp"
32 #include "utilities/debug.hpp"
33 #include "utilities/powerOfTwo.hpp"
34
35 ZRelocationSetSelectorGroupStats::ZRelocationSetSelectorGroupStats() :
36 _npages(0),
37 _total(0),
38 _live(0),
39 _garbage(0),
40 _empty(0),
41 _compacting_from(0),
42 _compacting_to(0) {}
43
44 ZRelocationSetSelectorGroup::ZRelocationSetSelectorGroup(const char* name,
45 uint8_t page_type,
46 size_t page_size,
47 size_t object_size_limit) :
48 _name(name),
49 _page_type(page_type),
50 _page_size(page_size),
51 _object_size_limit(object_size_limit),
52 _fragmentation_limit(page_size * (ZFragmentationLimit / 100)),
53 _registered_pages(),
54 _sorted_pages(NULL),
55 _nselected(0),
56 _stats() {}
57
58 ZRelocationSetSelectorGroup::~ZRelocationSetSelectorGroup() {
59 FREE_C_HEAP_ARRAY(ZPage*, _sorted_pages);
60 }
61
62 void ZRelocationSetSelectorGroup::register_live_page(ZPage* page) {
63 const uint8_t type = page->type();
64 const size_t size = page->size();
65 const size_t live = page->live_bytes();
66 const size_t garbage = size - live;
67
68 if (garbage > _fragmentation_limit) {
69 _registered_pages.append(page);
70 }
71
72 _stats._npages++;
73 _stats._total += size;
74 _stats._live += live;
75 _stats._garbage += garbage;
76 }
77
78 void ZRelocationSetSelectorGroup::register_garbage_page(ZPage* page) {
79 const size_t size = page->size();
80
81 _stats._npages++;
82 _stats._total += size;
83 _stats._garbage += size;
84 _stats._empty += size;
85 }
86
87 bool ZRelocationSetSelectorGroup::is_disabled() {
88 // Medium pages are disabled when their page size is zero
89 return _page_type == ZPageTypeMedium && _page_size == 0;
90 }
91
92 bool ZRelocationSetSelectorGroup::is_selectable() {
93 // Large pages are not selectable
94 return _page_type != ZPageTypeLarge;
95 }
96
97 void ZRelocationSetSelectorGroup::semi_sort() {
98 // Semi-sort registered pages by live bytes in ascending order
99 const size_t npartitions_shift = 11;
100 const size_t npartitions = (size_t)1 << npartitions_shift;
101 const size_t partition_size = _page_size >> npartitions_shift;
102 const size_t partition_size_shift = exact_log2(partition_size);
103 const size_t npages = _registered_pages.length();
104
105 // Partition slots/fingers
106 size_t partitions[npartitions];
107
108 // Allocate destination array
109 assert(_sorted_pages == NULL, "Already initialized");
110 _sorted_pages = NEW_C_HEAP_ARRAY(ZPage*, npages, mtGC);
111 debug_only(memset(_sorted_pages, 0, npages * sizeof(ZPage*)));
112
113 // Calculate partition slots
114 memset(partitions, 0, sizeof(partitions));
115 ZArrayIterator<ZPage*> iter1(&_registered_pages);
116 for (ZPage* page; iter1.next(&page);) {
117 const size_t index = page->live_bytes() >> partition_size_shift;
118 partitions[index]++;
119 }
120
121 // Calculate partition fingers
122 size_t finger = 0;
123 for (size_t i = 0; i < npartitions; i++) {
124 const size_t slots = partitions[i];
125 partitions[i] = finger;
126 finger += slots;
127 }
128
129 // Sort pages into partitions
130 ZArrayIterator<ZPage*> iter2(&_registered_pages);
131 for (ZPage* page; iter2.next(&page);) {
132 const size_t index = page->live_bytes() >> partition_size_shift;
133 const size_t finger = partitions[index]++;
134 assert(_sorted_pages[finger] == NULL, "Invalid finger");
135 _sorted_pages[finger] = page;
136 }
137 }
138
139 void ZRelocationSetSelectorGroup::select_inner() {
140 // Calculate the number of pages to relocate by successively including pages in
141 // a candidate relocation set and calculate the maximum space requirement for
142 // their live objects.
143 const size_t npages = _registered_pages.length();
144 size_t selected_from = 0;
145 size_t selected_to = 0;
146 size_t from_size = 0;
147
148 semi_sort();
149
150 for (size_t from = 1; from <= npages; from++) {
151 // Add page to the candidate relocation set
152 from_size += _sorted_pages[from - 1]->live_bytes();
153
154 // Calculate the maximum number of pages needed by the candidate relocation set.
155 // By subtracting the object size limit from the pages size we get the maximum
156 // number of pages that the relocation set is guaranteed to fit in, regardless
157 // of in which order the objects are relocated.
158 const size_t to = ceil((double)(from_size) / (double)(_page_size - _object_size_limit));
159
160 // Calculate the relative difference in reclaimable space compared to our
161 // currently selected final relocation set. If this number is larger than the
162 // acceptable fragmentation limit, then the current candidate relocation set
163 // becomes our new final relocation set.
164 const size_t diff_from = from - selected_from;
165 const size_t diff_to = to - selected_to;
166 const double diff_reclaimable = 100 - percent_of(diff_to, diff_from);
167 if (diff_reclaimable > ZFragmentationLimit) {
168 selected_from = from;
169 selected_to = to;
170 }
171
172 log_trace(gc, reloc)("Candidate Relocation Set (%s Pages): "
173 SIZE_FORMAT "->" SIZE_FORMAT ", %.1f%% relative defragmentation, %s",
174 _name, from, to, diff_reclaimable, (selected_from == from) ? "Selected" : "Rejected");
175 }
176
177 // Finalize selection
178 _nselected = selected_from;
179
180 // Update statistics
181 _stats._compacting_from = selected_from * _page_size;
182 _stats._compacting_to = selected_to * _page_size;
183
184 log_trace(gc, reloc)("Relocation Set (%s Pages): " SIZE_FORMAT "->" SIZE_FORMAT ", " SIZE_FORMAT " skipped",
185 _name, selected_from, selected_to, npages - _nselected);
186 }
187
188 void ZRelocationSetSelectorGroup::select() {
189 if (is_disabled()) {
190 return;
191 }
192
193 EventZRelocationSetGroup event;
194
195 if (is_selectable()) {
196 select_inner();
197 }
198
199 // Send event
200 event.commit(_page_type, _stats.npages(), _stats.total(), _stats.empty(),
201 _stats.compacting_from(), _stats.compacting_to());
202 }
203
204 ZRelocationSetSelector::ZRelocationSetSelector() :
205 _small("Small", ZPageTypeSmall, ZPageSizeSmall, ZObjectSizeLimitSmall),
206 _medium("Medium", ZPageTypeMedium, ZPageSizeMedium, ZObjectSizeLimitMedium),
207 _large("Large", ZPageTypeLarge, 0 /* page_size */, 0 /* object_size_limit */) {}
208
209 void ZRelocationSetSelector::register_live_page(ZPage* page) {
210 const uint8_t type = page->type();
211
212 if (type == ZPageTypeSmall) {
213 _small.register_live_page(page);
214 } else if (type == ZPageTypeMedium) {
215 _medium.register_live_page(page);
216 } else {
217 _large.register_live_page(page);
218 }
219 }
220
221 void ZRelocationSetSelector::register_garbage_page(ZPage* page) {
222 const uint8_t type = page->type();
223
224 if (type == ZPageTypeSmall) {
225 _small.register_garbage_page(page);
226 } else if (type == ZPageTypeMedium) {
227 _medium.register_garbage_page(page);
228 } else {
229 _large.register_garbage_page(page);
230 }
231 }
232
233 void ZRelocationSetSelector::select(ZRelocationSet* relocation_set) {
234 // Select pages to relocate. The resulting relocation set will be
235 // sorted such that medium pages comes first, followed by small
236 // pages. Pages within each page group will be semi-sorted by live
237 // bytes in ascending order. Relocating pages in this order allows
238 // us to start reclaiming memory more quickly.
239
240 EventZRelocationSet event;
241
242 // Select pages from each group
243 _large.select();
244 _medium.select();
245 _small.select();
246
247 // Populate relocation set
248 relocation_set->populate(_medium.selected(), _medium.nselected(),
249 _small.selected(), _small.nselected());
250
251 // Send event
252 event.commit(total(), empty(), compacting_from(), compacting_to());
253 }
254
255 ZRelocationSetSelectorStats ZRelocationSetSelector::stats() const {
256 ZRelocationSetSelectorStats stats;
257 stats._small = _small.stats();
258 stats._medium = _medium.stats();
259 stats._large = _large.stats();
260 return stats;
261 }