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