1// Copyright 2018 The Fuchsia Authors
2//
3// Use of this source code is governed by a MIT-style
4// license that can be found in the LICENSE file or at
5// https://opensource.org/licenses/MIT
6#include "pmm_node.h"
7
8#include <inttypes.h>
9#include <kernel/mp.h>
10#include <trace.h>
11#include <vm/bootalloc.h>
12#include <vm/physmap.h>
13#include <zxcpp/new.h>
14
15#include "vm_priv.h"
16
17#define LOCAL_TRACE MAX(VM_GLOBAL_TRACE, 0)
18
19namespace {
20
21void set_state_alloc(vm_page* page) {
22    LTRACEF("page %p: prev state %s\n", page, page_state_to_string(page->state));
23
24    DEBUG_ASSERT(page->state == VM_PAGE_STATE_FREE);
25
26    page->state = VM_PAGE_STATE_ALLOC;
27}
28
29} // namespace
30
31PmmNode::PmmNode() {
32}
33
34PmmNode::~PmmNode() {
35}
36
37// We disable thread safety analysis here, since this function is only called
38// during early boot before threading exists.
39zx_status_t PmmNode::AddArena(const pmm_arena_info_t* info) TA_NO_THREAD_SAFETY_ANALYSIS {
40    LTRACEF("arena %p name '%s' base %#" PRIxPTR " size %#zx\n", info, info->name, info->base, info->size);
41
42    // Make sure we're in early boot (ints disabled and no active CPUs according
43    // to the scheduler).
44    DEBUG_ASSERT(mp_get_active_mask() == 0);
45    DEBUG_ASSERT(arch_ints_disabled());
46
47    DEBUG_ASSERT(IS_PAGE_ALIGNED(info->base));
48    DEBUG_ASSERT(IS_PAGE_ALIGNED(info->size));
49    DEBUG_ASSERT(info->size > 0);
50
51    // allocate a c++ arena object
52    PmmArena* arena = new (boot_alloc_mem(sizeof(PmmArena))) PmmArena();
53
54    // initialize the object
55    auto status = arena->Init(info, this);
56    if (status != ZX_OK) {
57        // leaks boot allocator memory
58        arena->~PmmArena();
59        printf("PMM: pmm_add_arena failed to initialize arena\n");
60        return status;
61    }
62
63    // walk the arena list and add arena based on priority order
64    for (auto& a : arena_list_) {
65        if (a.priority() > arena->priority()) {
66            arena_list_.insert(a, arena);
67            goto done_add;
68        }
69    }
70
71    // walked off the end, add it to the end of the list
72    arena_list_.push_back(arena);
73
74done_add:
75    arena_cumulative_size_ += info->size;
76
77    return ZX_OK;
78}
79
80// called at boot time as arenas are brought online, no locks are acquired
81void PmmNode::AddFreePages(list_node* list) TA_NO_THREAD_SAFETY_ANALYSIS {
82    LTRACEF("list %p\n", list);
83
84    vm_page *temp, *page;
85    list_for_every_entry_safe (list, page, temp, vm_page, queue_node) {
86        list_delete(&page->queue_node);
87        list_add_tail(&free_list_, &page->queue_node);
88        free_count_++;
89    }
90
91    LTRACEF("free count now %" PRIu64 "\n", free_count_);
92}
93
94zx_status_t PmmNode::AllocPage(uint alloc_flags, vm_page_t** page_out, paddr_t* pa_out) {
95    Guard<fbl::Mutex> guard{&lock_};
96
97    vm_page* page = list_remove_head_type(&free_list_, vm_page, queue_node);
98    if (!page) {
99        return ZX_ERR_NO_MEMORY;
100    }
101
102    DEBUG_ASSERT(free_count_ > 0);
103    free_count_--;
104
105    DEBUG_ASSERT(page->is_free());
106
107    set_state_alloc(page);
108
109#if PMM_ENABLE_FREE_FILL
110    CheckFreeFill(page);
111#endif
112
113    if (pa_out) {
114        *pa_out = page->paddr();
115    }
116
117    if (page_out) {
118        *page_out = page;
119    }
120
121    LTRACEF("allocating page %p, pa %#" PRIxPTR "\n", page, page->paddr());
122
123    return ZX_OK;
124}
125
126zx_status_t PmmNode::AllocPages(size_t count, uint alloc_flags, list_node* list) {
127    LTRACEF("count %zu\n", count);
128
129    // list must be initialized prior to calling this
130    DEBUG_ASSERT(list);
131
132    if (unlikely(count == 0)) {
133        return ZX_OK;
134    }
135
136    Guard<fbl::Mutex> guard{&lock_};
137
138    while (count > 0) {
139        vm_page* page = list_remove_head_type(&free_list_, vm_page, queue_node);
140        if (unlikely(!page)) {
141            // free pages that have already been allocated
142            FreeListLocked(list);
143            return ZX_ERR_NO_MEMORY;
144        }
145
146        LTRACEF("allocating page %p, pa %#" PRIxPTR "\n", page, page->paddr());
147
148        DEBUG_ASSERT(free_count_ > 0);
149
150        free_count_--;
151
152        DEBUG_ASSERT(page->is_free());
153#if PMM_ENABLE_FREE_FILL
154        CheckFreeFill(page);
155#endif
156
157        page->state = VM_PAGE_STATE_ALLOC;
158        list_add_tail(list, &page->queue_node);
159
160        count--;
161    }
162
163    return ZX_OK;
164}
165
166zx_status_t PmmNode::AllocRange(paddr_t address, size_t count, list_node* list) {
167    LTRACEF("address %#" PRIxPTR ", count %zu\n", address, count);
168
169    // list must be initialized prior to calling this
170    DEBUG_ASSERT(list);
171
172    size_t allocated = 0;
173    if (count == 0) {
174        return ZX_OK;
175    }
176
177    address = ROUNDDOWN(address, PAGE_SIZE);
178
179    Guard<fbl::Mutex> guard{&lock_};
180
181    // walk through the arenas, looking to see if the physical page belongs to it
182    for (auto& a : arena_list_) {
183        while (allocated < count && a.address_in_arena(address)) {
184            vm_page_t* page = a.FindSpecific(address);
185            if (!page) {
186                break;
187            }
188
189            if (!page->is_free()) {
190                break;
191            }
192
193            list_delete(&page->queue_node);
194
195            page->state = VM_PAGE_STATE_ALLOC;
196
197            list_add_tail(list, &page->queue_node);
198
199            allocated++;
200            address += PAGE_SIZE;
201            free_count_--;
202        }
203
204        if (allocated == count) {
205            break;
206        }
207    }
208
209    if (allocated != count) {
210        // we were not able to allocate the entire run, free these pages
211        FreeListLocked(list);
212        return ZX_ERR_NOT_FOUND;
213    }
214
215    return ZX_OK;
216}
217
218zx_status_t PmmNode::AllocContiguous(const size_t count, uint alloc_flags, uint8_t alignment_log2,
219                                     paddr_t* pa, list_node* list) {
220    LTRACEF("count %zu, align %u\n", count, alignment_log2);
221
222    if (count == 0) {
223        return ZX_OK;
224    }
225    if (alignment_log2 < PAGE_SIZE_SHIFT) {
226        alignment_log2 = PAGE_SIZE_SHIFT;
227    }
228
229    // pa and list must be valid pointers
230    DEBUG_ASSERT(pa);
231    DEBUG_ASSERT(list);
232
233    Guard<fbl::Mutex> guard{&lock_};
234
235    for (auto& a : arena_list_) {
236        vm_page_t* p = a.FindFreeContiguous(count, alignment_log2);
237        if (!p) {
238            continue;
239        }
240
241        *pa = p->paddr();
242
243        // remove the pages from the run out of the free list
244        for (size_t i = 0; i < count; i++, p++) {
245            DEBUG_ASSERT_MSG(p->is_free(), "p %p state %u\n", p, p->state);
246            DEBUG_ASSERT(list_in_list(&p->queue_node));
247
248            list_delete(&p->queue_node);
249            p->state = VM_PAGE_STATE_ALLOC;
250
251            DEBUG_ASSERT(free_count_ > 0);
252
253            free_count_--;
254
255#if PMM_ENABLE_FREE_FILL
256            CheckFreeFill(p);
257#endif
258
259            list_add_tail(list, &p->queue_node);
260        }
261
262        return ZX_OK;
263    }
264
265    LTRACEF("couldn't find run\n");
266    return ZX_ERR_NOT_FOUND;
267}
268
269void PmmNode::FreePageLocked(vm_page* page) {
270    LTRACEF("page %p state %u paddr %#" PRIxPTR "\n", page, page->state, page->paddr());
271
272    DEBUG_ASSERT(page->state != VM_PAGE_STATE_OBJECT || page->object.pin_count == 0);
273    DEBUG_ASSERT(!page->is_free());
274
275#if PMM_ENABLE_FREE_FILL
276    FreeFill(page);
277#endif
278
279    // remove it from its old queue
280    if (list_in_list(&page->queue_node)) {
281        list_delete(&page->queue_node);
282    }
283
284    // mark it free
285    page->state = VM_PAGE_STATE_FREE;
286
287    // add it to the free queue
288    list_add_head(&free_list_, &page->queue_node);
289
290    free_count_++;
291}
292
293void PmmNode::FreePage(vm_page* page) {
294    Guard<fbl::Mutex> guard{&lock_};
295
296    FreePageLocked(page);
297}
298
299void PmmNode::FreeListLocked(list_node* list) {
300    DEBUG_ASSERT(list);
301
302    while (!list_is_empty(list)) {
303        vm_page* page = list_remove_head_type(list, vm_page, queue_node);
304
305        FreePageLocked(page);
306    }
307}
308
309void PmmNode::FreeList(list_node* list) {
310    Guard<fbl::Mutex> guard{&lock_};
311
312    FreeListLocked(list);
313}
314
315// okay if accessed outside of a lock
316uint64_t PmmNode::CountFreePages() const TA_NO_THREAD_SAFETY_ANALYSIS {
317    return free_count_;
318}
319
320uint64_t PmmNode::CountTotalBytes() const TA_NO_THREAD_SAFETY_ANALYSIS {
321    return arena_cumulative_size_;
322}
323
324void PmmNode::CountTotalStates(uint64_t state_count[VM_PAGE_STATE_COUNT_]) const {
325    // TODO(MG-833): This is extremely expensive, holding a global lock
326    // and touching every page/arena. We should keep a running count instead.
327    Guard<fbl::Mutex> guard{&lock_};
328    for (auto& a : arena_list_) {
329        a.CountStates(state_count);
330    }
331}
332
333void PmmNode::DumpFree() const TA_NO_THREAD_SAFETY_ANALYSIS {
334    auto megabytes_free = CountFreePages() / 256u;
335    printf(" %zu free MBs\n", megabytes_free);
336}
337
338void PmmNode::Dump(bool is_panic) const {
339    // No lock analysis here, as we want to just go for it in the panic case without the lock.
340    auto dump = [this]() TA_NO_THREAD_SAFETY_ANALYSIS {
341        printf("pmm node %p: free_count %zu (%zu bytes), total size %zu\n",
342               this, free_count_, free_count_ * PAGE_SIZE, arena_cumulative_size_);
343        for (auto& a : arena_list_) {
344            a.Dump(false, false);
345        }
346    };
347
348    if (is_panic) {
349        dump();
350    } else {
351        Guard<fbl::Mutex> guard{&lock_};
352        dump();
353    }
354}
355
356#if PMM_ENABLE_FREE_FILL
357void PmmNode::EnforceFill() {
358    DEBUG_ASSERT(!enforce_fill_);
359
360    vm_page* page;
361    list_for_every_entry (&free_list_, page, vm_page, queue_node) {
362        FreeFill(page);
363    }
364
365    enforce_fill_ = true;
366}
367
368void PmmNode::FreeFill(vm_page_t* page) {
369    void* kvaddr = paddr_to_physmap(page->paddr());
370    DEBUG_ASSERT(is_kernel_address((vaddr_t)kvaddr));
371    memset(kvaddr, PMM_FREE_FILL_BYTE, PAGE_SIZE);
372}
373
374void PmmNode::CheckFreeFill(vm_page_t* page) {
375    uint8_t* kvaddr = static_cast<uint8_t*>(paddr_to_physmap(page->paddr()));
376    for (size_t j = 0; j < PAGE_SIZE; ++j) {
377        ASSERT(!enforce_fill_ || *(kvaddr + j) == PMM_FREE_FILL_BYTE);
378    }
379}
380#endif // PMM_ENABLE_FREE_FILL
381