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 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 46 ZRelocationSetSelectorGroup::~ZRelocationSetSelectorGroup() { 47 FREE_C_HEAP_ARRAY(ZPage*, _sorted_pages); 48 } 49 50 void 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 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 // 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 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 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 153 ZPage* const* ZRelocationSetSelectorGroup::selected() const { 154 return _sorted_pages; 155 } 156 157 size_t ZRelocationSetSelectorGroup::nselected() const { 158 return _nselected; 159 } 160 161 size_t ZRelocationSetSelectorGroup::relocating() const { 162 return _relocating; 163 } 164 165 size_t ZRelocationSetSelectorGroup::fragmentation() const { 166 return _fragmentation; 167 } 168 169 ZRelocationSetSelector::ZRelocationSetSelector() : 170 _small("Small", ZPageSizeSmall, ZObjectSizeLimitSmall), 171 _medium("Medium", ZPageSizeMedium, ZObjectSizeLimitMedium), 172 _live(0), 173 _garbage(0), 174 _fragmentation(0) {} 175 176 void 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 193 void ZRelocationSetSelector::register_garbage_page(ZPage* page) { 194 _garbage += page->size(); 195 } 196 197 void 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 213 size_t ZRelocationSetSelector::live() const { 214 return _live; 215 } 216 217 size_t ZRelocationSetSelector::garbage() const { 218 return _garbage; 219 } 220 221 size_t ZRelocationSetSelector::relocating() const { 222 return _small.relocating() + _medium.relocating(); 223 } 224 225 size_t ZRelocationSetSelector::fragmentation() const { 226 return _fragmentation + _small.fragmentation() + _medium.fragmentation(); 227 }