| /* |
| * Copyright (c) 2017, 2019, Oracle and/or its affiliates. All rights reserved. |
| * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. |
| * |
| * This code is free software; you can redistribute it and/or modify it |
| * under the terms of the GNU General Public License version 2 only, as |
| * published by the Free Software Foundation. |
| * |
| * This code is distributed in the hope that it will be useful, but WITHOUT |
| * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or |
| * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
| * version 2 for more details (a copy is included in the LICENSE file that |
| * accompanied this code). |
| * |
| * You should have received a copy of the GNU General Public License version |
| * 2 along with this work; if not, write to the Free Software Foundation, |
| * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. |
| * |
| * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA |
| * or visit www.oracle.com if you need additional information or have any |
| * questions. |
| */ |
| |
| #include "precompiled.hpp" |
| #include "gc/z/zArray.inline.hpp" |
| #include "gc/z/zPage.inline.hpp" |
| #include "gc/z/zRelocationSet.hpp" |
| #include "gc/z/zRelocationSetSelector.hpp" |
| #include "logging/log.hpp" |
| #include "runtime/globals.hpp" |
| #include "utilities/debug.hpp" |
| |
| ZRelocationSetSelectorGroup::ZRelocationSetSelectorGroup(const char* name, |
| size_t page_size, |
| size_t object_size_limit) : |
| _name(name), |
| _page_size(page_size), |
| _object_size_limit(object_size_limit), |
| _fragmentation_limit(page_size * (ZFragmentationLimit / 100)), |
| _registered_pages(), |
| _sorted_pages(NULL), |
| _nselected(0), |
| _relocating(0), |
| _fragmentation(0) {} |
| |
| ZRelocationSetSelectorGroup::~ZRelocationSetSelectorGroup() { |
| FREE_C_HEAP_ARRAY(ZPage*, _sorted_pages); |
| } |
| |
| void ZRelocationSetSelectorGroup::register_live_page(ZPage* page, size_t garbage) { |
| if (garbage > _fragmentation_limit) { |
| _registered_pages.add(page); |
| } else { |
| _fragmentation += garbage; |
| } |
| } |
| |
| void ZRelocationSetSelectorGroup::semi_sort() { |
| // Semi-sort registered pages by live bytes in ascending order |
| const size_t npartitions_shift = 11; |
| const size_t npartitions = (size_t)1 << npartitions_shift; |
| const size_t partition_size = _page_size >> npartitions_shift; |
| const size_t partition_size_shift = exact_log2(partition_size); |
| const size_t npages = _registered_pages.size(); |
| |
| // Partition slots/fingers |
| size_t partitions[npartitions]; |
| |
| // Allocate destination array |
| _sorted_pages = REALLOC_C_HEAP_ARRAY(ZPage*, _sorted_pages, npages, mtGC); |
| debug_only(memset(_sorted_pages, 0, npages * sizeof(ZPage*))); |
| |
| // Calculate partition slots |
| memset(partitions, 0, sizeof(partitions)); |
| ZArrayIterator<ZPage*> iter1(&_registered_pages); |
| for (ZPage* page; iter1.next(&page);) { |
| const size_t index = page->live_bytes() >> partition_size_shift; |
| partitions[index]++; |
| } |
| |
| // Calculate partition fingers |
| size_t finger = 0; |
| for (size_t i = 0; i < npartitions; i++) { |
| const size_t slots = partitions[i]; |
| partitions[i] = finger; |
| finger += slots; |
| } |
| |
| // Sort pages into partitions |
| ZArrayIterator<ZPage*> iter2(&_registered_pages); |
| for (ZPage* page; iter2.next(&page);) { |
| const size_t index = page->live_bytes() >> partition_size_shift; |
| const size_t finger = partitions[index]++; |
| assert(_sorted_pages[finger] == NULL, "Invalid finger"); |
| _sorted_pages[finger] = page; |
| } |
| } |
| |
| void ZRelocationSetSelectorGroup::select() { |
| // Calculate the number of pages to relocate by successively including pages in |
| // a candidate relocation set and calculate the maximum space requirement for |
| // their live objects. |
| const size_t npages = _registered_pages.size(); |
| size_t selected_from = 0; |
| size_t selected_to = 0; |
| size_t selected_from_size = 0; |
| size_t from_size = 0; |
| |
| semi_sort(); |
| |
| for (size_t from = 1; from <= npages; from++) { |
| // Add page to the candidate relocation set |
| from_size += _sorted_pages[from - 1]->live_bytes(); |
| |
| // Calculate the maximum number of pages needed by the candidate relocation set. |
| // By subtracting the object size limit from the pages size we get the maximum |
| // number of pages that the relocation set is guaranteed to fit in, regardless |
| // of in which order the objects are relocated. |
| const size_t to = ceil((double)(from_size) / (double)(_page_size - _object_size_limit)); |
| |
| // Calculate the relative difference in reclaimable space compared to our |
| // currently selected final relocation set. If this number is larger than the |
| // acceptable fragmentation limit, then the current candidate relocation set |
| // becomes our new final relocation set. |
| const size_t diff_from = from - selected_from; |
| const size_t diff_to = to - selected_to; |
| const double diff_reclaimable = 100 - percent_of(diff_to, diff_from); |
| if (diff_reclaimable > ZFragmentationLimit) { |
| selected_from = from; |
| selected_to = to; |
| selected_from_size = from_size; |
| } |
| |
| log_trace(gc, reloc)("Candidate Relocation Set (%s Pages): " |
| SIZE_FORMAT "->" SIZE_FORMAT ", %.1f%% relative defragmentation, %s", |
| _name, from, to, diff_reclaimable, (selected_from == from) ? "Selected" : "Rejected"); |
| } |
| |
| // Finalize selection |
| _nselected = selected_from; |
| |
| // Update statistics |
| _relocating = selected_from_size; |
| for (size_t i = _nselected; i < npages; i++) { |
| ZPage* const page = _sorted_pages[i]; |
| _fragmentation += page->size() - page->live_bytes(); |
| } |
| |
| log_debug(gc, reloc)("Relocation Set (%s Pages): " SIZE_FORMAT "->" SIZE_FORMAT ", " SIZE_FORMAT " skipped", |
| _name, selected_from, selected_to, npages - _nselected); |
| } |
| |
| ZPage* const* ZRelocationSetSelectorGroup::selected() const { |
| return _sorted_pages; |
| } |
| |
| size_t ZRelocationSetSelectorGroup::nselected() const { |
| return _nselected; |
| } |
| |
| size_t ZRelocationSetSelectorGroup::relocating() const { |
| return _relocating; |
| } |
| |
| size_t ZRelocationSetSelectorGroup::fragmentation() const { |
| return _fragmentation; |
| } |
| |
| ZRelocationSetSelector::ZRelocationSetSelector() : |
| _small("Small", ZPageSizeSmall, ZObjectSizeLimitSmall), |
| _medium("Medium", ZPageSizeMedium, ZObjectSizeLimitMedium), |
| _live(0), |
| _garbage(0), |
| _fragmentation(0) {} |
| |
| void ZRelocationSetSelector::register_live_page(ZPage* page) { |
| const uint8_t type = page->type(); |
| const size_t live = page->live_bytes(); |
| const size_t garbage = page->size() - live; |
| |
| if (type == ZPageTypeSmall) { |
| _small.register_live_page(page, garbage); |
| } else if (type == ZPageTypeMedium) { |
| _medium.register_live_page(page, garbage); |
| } else { |
| _fragmentation += garbage; |
| } |
| |
| _live += live; |
| _garbage += garbage; |
| } |
| |
| void ZRelocationSetSelector::register_garbage_page(ZPage* page) { |
| _garbage += page->size(); |
| } |
| |
| void ZRelocationSetSelector::select(ZRelocationSet* relocation_set) { |
| // Select pages to relocate. The resulting relocation set will be |
| // sorted such that medium pages comes first, followed by small |
| // pages. Pages within each page group will be semi-sorted by live |
| // bytes in ascending order. Relocating pages in this order allows |
| // us to start reclaiming memory more quickly. |
| |
| // Select pages from each group |
| _medium.select(); |
| _small.select(); |
| |
| // Populate relocation set |
| relocation_set->populate(_medium.selected(), _medium.nselected(), |
| _small.selected(), _small.nselected()); |
| } |
| |
| size_t ZRelocationSetSelector::live() const { |
| return _live; |
| } |
| |
| size_t ZRelocationSetSelector::garbage() const { |
| return _garbage; |
| } |
| |
| size_t ZRelocationSetSelector::relocating() const { |
| return _small.relocating() + _medium.relocating(); |
| } |
| |
| size_t ZRelocationSetSelector::fragmentation() const { |
| return _fragmentation + _small.fragmentation() + _medium.fragmentation(); |
| } |