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