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