1*8e17c662SQuentin Perret // SPDX-License-Identifier: GPL-2.0-only 2*8e17c662SQuentin Perret /* 3*8e17c662SQuentin Perret * Copyright (C) 2020 Google LLC 4*8e17c662SQuentin Perret * Author: Quentin Perret <qperret@google.com> 5*8e17c662SQuentin Perret */ 6*8e17c662SQuentin Perret 7*8e17c662SQuentin Perret #include <asm/kvm_hyp.h> 8*8e17c662SQuentin Perret #include <nvhe/gfp.h> 9*8e17c662SQuentin Perret 10*8e17c662SQuentin Perret u64 __hyp_vmemmap; 11*8e17c662SQuentin Perret 12*8e17c662SQuentin Perret /* 13*8e17c662SQuentin Perret * Index the hyp_vmemmap to find a potential buddy page, but make no assumption 14*8e17c662SQuentin Perret * about its current state. 15*8e17c662SQuentin Perret * 16*8e17c662SQuentin Perret * Example buddy-tree for a 4-pages physically contiguous pool: 17*8e17c662SQuentin Perret * 18*8e17c662SQuentin Perret * o : Page 3 19*8e17c662SQuentin Perret * / 20*8e17c662SQuentin Perret * o-o : Page 2 21*8e17c662SQuentin Perret * / 22*8e17c662SQuentin Perret * / o : Page 1 23*8e17c662SQuentin Perret * / / 24*8e17c662SQuentin Perret * o---o-o : Page 0 25*8e17c662SQuentin Perret * Order 2 1 0 26*8e17c662SQuentin Perret * 27*8e17c662SQuentin Perret * Example of requests on this pool: 28*8e17c662SQuentin Perret * __find_buddy_nocheck(pool, page 0, order 0) => page 1 29*8e17c662SQuentin Perret * __find_buddy_nocheck(pool, page 0, order 1) => page 2 30*8e17c662SQuentin Perret * __find_buddy_nocheck(pool, page 1, order 0) => page 0 31*8e17c662SQuentin Perret * __find_buddy_nocheck(pool, page 2, order 0) => page 3 32*8e17c662SQuentin Perret */ 33*8e17c662SQuentin Perret static struct hyp_page *__find_buddy_nocheck(struct hyp_pool *pool, 34*8e17c662SQuentin Perret struct hyp_page *p, 35*8e17c662SQuentin Perret unsigned int order) 36*8e17c662SQuentin Perret { 37*8e17c662SQuentin Perret phys_addr_t addr = hyp_page_to_phys(p); 38*8e17c662SQuentin Perret 39*8e17c662SQuentin Perret addr ^= (PAGE_SIZE << order); 40*8e17c662SQuentin Perret 41*8e17c662SQuentin Perret /* 42*8e17c662SQuentin Perret * Don't return a page outside the pool range -- it belongs to 43*8e17c662SQuentin Perret * something else and may not be mapped in hyp_vmemmap. 44*8e17c662SQuentin Perret */ 45*8e17c662SQuentin Perret if (addr < pool->range_start || addr >= pool->range_end) 46*8e17c662SQuentin Perret return NULL; 47*8e17c662SQuentin Perret 48*8e17c662SQuentin Perret return hyp_phys_to_page(addr); 49*8e17c662SQuentin Perret } 50*8e17c662SQuentin Perret 51*8e17c662SQuentin Perret /* Find a buddy page currently available for allocation */ 52*8e17c662SQuentin Perret static struct hyp_page *__find_buddy_avail(struct hyp_pool *pool, 53*8e17c662SQuentin Perret struct hyp_page *p, 54*8e17c662SQuentin Perret unsigned int order) 55*8e17c662SQuentin Perret { 56*8e17c662SQuentin Perret struct hyp_page *buddy = __find_buddy_nocheck(pool, p, order); 57*8e17c662SQuentin Perret 58*8e17c662SQuentin Perret if (!buddy || buddy->order != order || list_empty(&buddy->node)) 59*8e17c662SQuentin Perret return NULL; 60*8e17c662SQuentin Perret 61*8e17c662SQuentin Perret return buddy; 62*8e17c662SQuentin Perret 63*8e17c662SQuentin Perret } 64*8e17c662SQuentin Perret 65*8e17c662SQuentin Perret static void __hyp_attach_page(struct hyp_pool *pool, 66*8e17c662SQuentin Perret struct hyp_page *p) 67*8e17c662SQuentin Perret { 68*8e17c662SQuentin Perret unsigned int order = p->order; 69*8e17c662SQuentin Perret struct hyp_page *buddy; 70*8e17c662SQuentin Perret 71*8e17c662SQuentin Perret memset(hyp_page_to_virt(p), 0, PAGE_SIZE << p->order); 72*8e17c662SQuentin Perret 73*8e17c662SQuentin Perret /* 74*8e17c662SQuentin Perret * Only the first struct hyp_page of a high-order page (otherwise known 75*8e17c662SQuentin Perret * as the 'head') should have p->order set. The non-head pages should 76*8e17c662SQuentin Perret * have p->order = HYP_NO_ORDER. Here @p may no longer be the head 77*8e17c662SQuentin Perret * after coallescing, so make sure to mark it HYP_NO_ORDER proactively. 78*8e17c662SQuentin Perret */ 79*8e17c662SQuentin Perret p->order = HYP_NO_ORDER; 80*8e17c662SQuentin Perret for (; (order + 1) < pool->max_order; order++) { 81*8e17c662SQuentin Perret buddy = __find_buddy_avail(pool, p, order); 82*8e17c662SQuentin Perret if (!buddy) 83*8e17c662SQuentin Perret break; 84*8e17c662SQuentin Perret 85*8e17c662SQuentin Perret /* Take the buddy out of its list, and coallesce with @p */ 86*8e17c662SQuentin Perret list_del_init(&buddy->node); 87*8e17c662SQuentin Perret buddy->order = HYP_NO_ORDER; 88*8e17c662SQuentin Perret p = min(p, buddy); 89*8e17c662SQuentin Perret } 90*8e17c662SQuentin Perret 91*8e17c662SQuentin Perret /* Mark the new head, and insert it */ 92*8e17c662SQuentin Perret p->order = order; 93*8e17c662SQuentin Perret list_add_tail(&p->node, &pool->free_area[order]); 94*8e17c662SQuentin Perret } 95*8e17c662SQuentin Perret 96*8e17c662SQuentin Perret static void hyp_attach_page(struct hyp_page *p) 97*8e17c662SQuentin Perret { 98*8e17c662SQuentin Perret struct hyp_pool *pool = hyp_page_to_pool(p); 99*8e17c662SQuentin Perret 100*8e17c662SQuentin Perret hyp_spin_lock(&pool->lock); 101*8e17c662SQuentin Perret __hyp_attach_page(pool, p); 102*8e17c662SQuentin Perret hyp_spin_unlock(&pool->lock); 103*8e17c662SQuentin Perret } 104*8e17c662SQuentin Perret 105*8e17c662SQuentin Perret static struct hyp_page *__hyp_extract_page(struct hyp_pool *pool, 106*8e17c662SQuentin Perret struct hyp_page *p, 107*8e17c662SQuentin Perret unsigned int order) 108*8e17c662SQuentin Perret { 109*8e17c662SQuentin Perret struct hyp_page *buddy; 110*8e17c662SQuentin Perret 111*8e17c662SQuentin Perret list_del_init(&p->node); 112*8e17c662SQuentin Perret while (p->order > order) { 113*8e17c662SQuentin Perret /* 114*8e17c662SQuentin Perret * The buddy of order n - 1 currently has HYP_NO_ORDER as it 115*8e17c662SQuentin Perret * is covered by a higher-level page (whose head is @p). Use 116*8e17c662SQuentin Perret * __find_buddy_nocheck() to find it and inject it in the 117*8e17c662SQuentin Perret * free_list[n - 1], effectively splitting @p in half. 118*8e17c662SQuentin Perret */ 119*8e17c662SQuentin Perret p->order--; 120*8e17c662SQuentin Perret buddy = __find_buddy_nocheck(pool, p, p->order); 121*8e17c662SQuentin Perret buddy->order = p->order; 122*8e17c662SQuentin Perret list_add_tail(&buddy->node, &pool->free_area[buddy->order]); 123*8e17c662SQuentin Perret } 124*8e17c662SQuentin Perret 125*8e17c662SQuentin Perret return p; 126*8e17c662SQuentin Perret } 127*8e17c662SQuentin Perret 128*8e17c662SQuentin Perret void hyp_put_page(void *addr) 129*8e17c662SQuentin Perret { 130*8e17c662SQuentin Perret struct hyp_page *p = hyp_virt_to_page(addr); 131*8e17c662SQuentin Perret 132*8e17c662SQuentin Perret if (hyp_page_ref_dec_and_test(p)) 133*8e17c662SQuentin Perret hyp_attach_page(p); 134*8e17c662SQuentin Perret } 135*8e17c662SQuentin Perret 136*8e17c662SQuentin Perret void hyp_get_page(void *addr) 137*8e17c662SQuentin Perret { 138*8e17c662SQuentin Perret struct hyp_page *p = hyp_virt_to_page(addr); 139*8e17c662SQuentin Perret 140*8e17c662SQuentin Perret hyp_page_ref_inc(p); 141*8e17c662SQuentin Perret } 142*8e17c662SQuentin Perret 143*8e17c662SQuentin Perret void *hyp_alloc_pages(struct hyp_pool *pool, unsigned int order) 144*8e17c662SQuentin Perret { 145*8e17c662SQuentin Perret unsigned int i = order; 146*8e17c662SQuentin Perret struct hyp_page *p; 147*8e17c662SQuentin Perret 148*8e17c662SQuentin Perret hyp_spin_lock(&pool->lock); 149*8e17c662SQuentin Perret 150*8e17c662SQuentin Perret /* Look for a high-enough-order page */ 151*8e17c662SQuentin Perret while (i < pool->max_order && list_empty(&pool->free_area[i])) 152*8e17c662SQuentin Perret i++; 153*8e17c662SQuentin Perret if (i >= pool->max_order) { 154*8e17c662SQuentin Perret hyp_spin_unlock(&pool->lock); 155*8e17c662SQuentin Perret return NULL; 156*8e17c662SQuentin Perret } 157*8e17c662SQuentin Perret 158*8e17c662SQuentin Perret /* Extract it from the tree at the right order */ 159*8e17c662SQuentin Perret p = list_first_entry(&pool->free_area[i], struct hyp_page, node); 160*8e17c662SQuentin Perret p = __hyp_extract_page(pool, p, order); 161*8e17c662SQuentin Perret 162*8e17c662SQuentin Perret hyp_spin_unlock(&pool->lock); 163*8e17c662SQuentin Perret hyp_set_page_refcounted(p); 164*8e17c662SQuentin Perret 165*8e17c662SQuentin Perret return hyp_page_to_virt(p); 166*8e17c662SQuentin Perret } 167*8e17c662SQuentin Perret 168*8e17c662SQuentin Perret int hyp_pool_init(struct hyp_pool *pool, u64 pfn, unsigned int nr_pages, 169*8e17c662SQuentin Perret unsigned int reserved_pages) 170*8e17c662SQuentin Perret { 171*8e17c662SQuentin Perret phys_addr_t phys = hyp_pfn_to_phys(pfn); 172*8e17c662SQuentin Perret struct hyp_page *p; 173*8e17c662SQuentin Perret int i; 174*8e17c662SQuentin Perret 175*8e17c662SQuentin Perret hyp_spin_lock_init(&pool->lock); 176*8e17c662SQuentin Perret pool->max_order = min(MAX_ORDER, get_order(nr_pages << PAGE_SHIFT)); 177*8e17c662SQuentin Perret for (i = 0; i < pool->max_order; i++) 178*8e17c662SQuentin Perret INIT_LIST_HEAD(&pool->free_area[i]); 179*8e17c662SQuentin Perret pool->range_start = phys; 180*8e17c662SQuentin Perret pool->range_end = phys + (nr_pages << PAGE_SHIFT); 181*8e17c662SQuentin Perret 182*8e17c662SQuentin Perret /* Init the vmemmap portion */ 183*8e17c662SQuentin Perret p = hyp_phys_to_page(phys); 184*8e17c662SQuentin Perret memset(p, 0, sizeof(*p) * nr_pages); 185*8e17c662SQuentin Perret for (i = 0; i < nr_pages; i++) { 186*8e17c662SQuentin Perret p[i].pool = pool; 187*8e17c662SQuentin Perret INIT_LIST_HEAD(&p[i].node); 188*8e17c662SQuentin Perret } 189*8e17c662SQuentin Perret 190*8e17c662SQuentin Perret /* Attach the unused pages to the buddy tree */ 191*8e17c662SQuentin Perret for (i = reserved_pages; i < nr_pages; i++) 192*8e17c662SQuentin Perret __hyp_attach_page(pool, &p[i]); 193*8e17c662SQuentin Perret 194*8e17c662SQuentin Perret return 0; 195*8e17c662SQuentin Perret } 196