| // Copyright 2016 The Fuchsia Authors |
| // |
| // Use of this source code is governed by a MIT-style |
| // license that can be found in the LICENSE file or at |
| // https://opensource.org/licenses/MIT |
| #include "pmm_arena.h" |
| |
| #include <align.h> |
| #include <inttypes.h> |
| #include <lib/counters.h> |
| #include <lib/zx/status.h> |
| #include <string.h> |
| #include <trace.h> |
| #include <zircon/errors.h> |
| #include <zircon/types.h> |
| |
| #include <kernel/range_check.h> |
| #include <ktl/limits.h> |
| #include <pretty/cpp/sizes.h> |
| #include <vm/bootalloc.h> |
| #include <vm/bootreserve.h> |
| #include <vm/physmap.h> |
| |
| #include "pmm_node.h" |
| #include "vm_priv.h" |
| |
| #define LOCAL_TRACE VM_GLOBAL_TRACE(0) |
| |
| // The maximum number of page runs examined while performing a contiguous allocation. |
| KCOUNTER_DECLARE(counter_max_runs_examined, "vm.pmm.max_runs_examined", Max) |
| |
| zx_status_t PmmArena::Init(const pmm_arena_info_t* info, PmmNode* node) { |
| // TODO: validate that info is sane (page aligned, etc) |
| info_ = *info; |
| |
| // allocate an array of pages to back this one |
| size_t page_count = size() / PAGE_SIZE; |
| size_t page_array_size = ROUNDUP_PAGE_SIZE(page_count * sizeof(vm_page)); |
| |
| // if the arena is too small to be useful, bail |
| if (page_array_size >= size()) { |
| printf("PMM: arena too small to be useful (size %zu)\n", size()); |
| return ZX_ERR_BUFFER_TOO_SMALL; |
| } |
| |
| // allocate a chunk to back the page array out of the arena itself, near the top of memory |
| reserve_range_t range; |
| auto status = boot_reserve_range_search(base(), size(), page_array_size, &range); |
| if (status != ZX_OK) { |
| printf("PMM: arena intersects with reserved memory in unresovable way\n"); |
| return ZX_ERR_NO_MEMORY; |
| } |
| |
| DEBUG_ASSERT(range.pa >= base() && range.len <= page_array_size); |
| |
| // get the kernel pointer |
| void* raw_page_array = paddr_to_physmap(range.pa); |
| LTRACEF("arena for base 0%#" PRIxPTR " size %#zx page array at %p size %#zx\n", base(), size(), |
| raw_page_array, page_array_size); |
| |
| memset(raw_page_array, 0, page_array_size); |
| |
| page_array_ = (vm_page_t*)raw_page_array; |
| |
| // we've just constructed |page_count| pages in the state vm_page_state::FREE |
| vm_page::add_to_initial_count(vm_page_state::FREE, page_count); |
| |
| // compute the range of the array that backs the array itself |
| size_t array_start_index = (PAGE_ALIGN(range.pa) - info_.base) / PAGE_SIZE; |
| size_t array_end_index = array_start_index + page_array_size / PAGE_SIZE; |
| LTRACEF("array_start_index %zu, array_end_index %zu, page_count %zu\n", array_start_index, |
| array_end_index, page_count); |
| |
| DEBUG_ASSERT(array_start_index < page_count && array_end_index <= page_count); |
| |
| // add all pages that aren't part of the page array to the free list |
| // pages part of the free array go to the WIRED state |
| list_node list; |
| list_initialize(&list); |
| for (size_t i = 0; i < page_count; i++) { |
| auto& p = page_array_[i]; |
| |
| p.paddr_priv = base() + i * PAGE_SIZE; |
| if (i >= array_start_index && i < array_end_index) { |
| p.set_state(vm_page_state::WIRED); |
| } else { |
| list_add_tail(&list, &p.queue_node); |
| } |
| } |
| |
| node->AddFreePages(&list); |
| |
| return ZX_OK; |
| } |
| |
| zx_status_t PmmArena::InitForTest(const pmm_arena_info_t& info, vm_page_t* page_array) { |
| info_ = info; |
| page_array_ = page_array; |
| return ZX_OK; |
| } |
| |
| vm_page_t* PmmArena::FindSpecific(paddr_t pa) { |
| if (!address_in_arena(pa)) { |
| return nullptr; |
| } |
| |
| size_t index = (pa - base()) / PAGE_SIZE; |
| |
| DEBUG_ASSERT(index < size() / PAGE_SIZE); |
| |
| return get_page(index); |
| } |
| |
| // Computes and returns the offset from |page_array_| of the first element at or |
| // after |offset| whose physical address alignment satisfies |alignment_log2|. |
| // |
| // Note, the returned value may exceed the bounds of |page_array_|. |
| static uint64_t Align(uint64_t offset, uint8_t alignment_log2, uint64_t first_aligned_offset) { |
| if (offset < first_aligned_offset) { |
| return first_aligned_offset; |
| } |
| DEBUG_ASSERT(alignment_log2 >= PAGE_SIZE_SHIFT); |
| // The "extra" alignment required above and beyond PAGE_SIZE alignment. |
| const uint64_t offset_alignment = alignment_log2 - PAGE_SIZE_SHIFT; |
| return ROUNDUP(offset - first_aligned_offset, 1UL << (offset_alignment)) + first_aligned_offset; |
| } |
| |
| zx::status<uint64_t> PmmArena::FindLastNonFree(uint64_t offset, size_t count) const { |
| uint64_t i = offset + count - 1; |
| do { |
| if (!page_array_[i].is_free()) { |
| return zx::ok(i); |
| } |
| } while (i-- > offset); |
| |
| return zx::error(ZX_ERR_NOT_FOUND); |
| } |
| |
| vm_page_t* PmmArena::FindFreeContiguous(size_t count, uint8_t alignment_log2) { |
| DEBUG_ASSERT(count > 0); |
| |
| if (alignment_log2 < PAGE_SIZE_SHIFT) { |
| alignment_log2 = PAGE_SIZE_SHIFT; |
| } |
| |
| // Number of pages in this arena. |
| const uint64_t arena_count = size() / PAGE_SIZE; |
| // Offset of the first page that satisfies the required alignment. |
| const uint64_t first_aligned_offset = |
| (ROUNDUP(base(), 1UL << alignment_log2) - base()) / PAGE_SIZE; |
| // Start our search at the hint so that we can skip over regions previously |
| // known to be in use. |
| const uint64_t initial = search_hint_; |
| DEBUG_ASSERT_MSG(initial < arena_count, "initial %lu\n", initial); |
| uint64_t candidate = Align(initial, alignment_log2, first_aligned_offset); |
| // Keep track of how many runs of pages we examine before finding a |
| // sufficiently long contiguous run. |
| int64_t num_runs_examined = 0; |
| // Indicates whether we have wrapped around back to the start of the arena. |
| bool wrapped = false; |
| vm_page_t* result = nullptr; |
| |
| // Keep searching until we've wrapped and "lapped" our initial starting point. |
| while (!wrapped || candidate < initial) { |
| LTRACEF( |
| "num_runs_examined=%ld candidate=%lu count=%zu alignment_log2=%d arena_count=%lu " |
| "initial=%lu\n", |
| num_runs_examined, candidate, count, alignment_log2, arena_count, initial); |
| num_runs_examined++; |
| if (!InRange(candidate, count, arena_count)) { |
| if (wrapped) { |
| break; |
| } |
| wrapped = true; |
| candidate = first_aligned_offset; |
| } else { |
| // Is the candidate region free? Walk the pages of the region back to |
| // front, stopping at the first non-free page. |
| |
| zx::status<uint64_t> last_non_free = FindLastNonFree(candidate, count); |
| if (last_non_free.is_error()) { |
| // Candidate region is free. We're done. |
| search_hint_ = (candidate + count) % arena_count; |
| result = &page_array_[candidate]; |
| DEBUG_ASSERT_MSG(candidate < arena_count, "candidate=%lu arena_count=%lu\n", candidate, |
| arena_count); |
| break; |
| } |
| |
| // Candidate region is not completely free. Skip over the "broken" run, |
| // maintaining alignment. |
| candidate = Align(last_non_free.value() + 1, alignment_log2, first_aligned_offset); |
| } |
| } |
| |
| int64_t max = counter_max_runs_examined.Value(); |
| if (num_runs_examined > max) { |
| counter_max_runs_examined.Set(num_runs_examined); |
| } |
| |
| return result; |
| } |
| |
| void PmmArena::CountStates(size_t state_count[VmPageStateIndex(vm_page_state::COUNT_)]) const { |
| for (size_t i = 0; i < size() / PAGE_SIZE; i++) { |
| state_count[VmPageStateIndex(page_array_[i].state())]++; |
| } |
| } |
| |
| void PmmArena::Dump(bool dump_pages, bool dump_free_ranges) const { |
| printf(" arena %p: name '%s' base %#" PRIxPTR " size %s (0x%zx) flags 0x%x\n", this, name(), |
| base(), pretty::FormattedBytes(size()).str(), size(), flags()); |
| printf("\tpage_array %p search_hint %lu\n", page_array_, search_hint_); |
| |
| // dump all of the pages |
| if (dump_pages) { |
| for (size_t i = 0; i < size() / PAGE_SIZE; i++) { |
| page_array_[i].dump(); |
| } |
| } |
| |
| // count the number of pages in every state |
| size_t state_count[VmPageStateIndex(vm_page_state::COUNT_)] = {}; |
| CountStates(state_count); |
| |
| printf("\tpage states:\n"); |
| for (unsigned int i = 0; i < VmPageStateIndex(vm_page_state::COUNT_); i++) { |
| printf("\t\t%-12s %-16zu (%zu bytes)\n", page_state_to_string(vm_page_state(i)), state_count[i], |
| state_count[i] * PAGE_SIZE); |
| } |
| |
| // dump the free pages |
| if (dump_free_ranges) { |
| printf("\tfree ranges:\n"); |
| ssize_t last = -1; |
| for (size_t i = 0; i < size() / PAGE_SIZE; i++) { |
| if (page_array_[i].is_free()) { |
| if (last == -1) { |
| last = i; |
| } |
| } else { |
| if (last != -1) { |
| printf("\t\t%#" PRIxPTR " - %#" PRIxPTR "\n", base() + last * PAGE_SIZE, |
| base() + i * PAGE_SIZE); |
| } |
| last = -1; |
| } |
| } |
| |
| if (last != -1) { |
| printf("\t\t%#" PRIxPTR " - %#" PRIxPTR "\n", base() + last * PAGE_SIZE, base() + size()); |
| } |
| } |
| } |