10ed02bdaSArd Biesheuvel // SPDX-License-Identifier: GPL-2.0 20ed02bdaSArd Biesheuvel /* 30ed02bdaSArd Biesheuvel * Copyright (C) 2016 Linaro Ltd; <ard.biesheuvel@linaro.org> 40ed02bdaSArd Biesheuvel */ 50ed02bdaSArd Biesheuvel 60ed02bdaSArd Biesheuvel #include <linux/efi.h> 70ed02bdaSArd Biesheuvel #include <linux/log2.h> 80ed02bdaSArd Biesheuvel #include <asm/efi.h> 90ed02bdaSArd Biesheuvel 100ed02bdaSArd Biesheuvel #include "efistub.h" 110ed02bdaSArd Biesheuvel 120ed02bdaSArd Biesheuvel /* 130ed02bdaSArd Biesheuvel * Return the number of slots covered by this entry, i.e., the number of 140ed02bdaSArd Biesheuvel * addresses it covers that are suitably aligned and supply enough room 150ed02bdaSArd Biesheuvel * for the allocation. 160ed02bdaSArd Biesheuvel */ 170ed02bdaSArd Biesheuvel static unsigned long get_entry_num_slots(efi_memory_desc_t *md, 180ed02bdaSArd Biesheuvel unsigned long size, 19*bc5ddcefSArd Biesheuvel unsigned long align_shift, 20*bc5ddcefSArd Biesheuvel u64 alloc_limit) 210ed02bdaSArd Biesheuvel { 220ed02bdaSArd Biesheuvel unsigned long align = 1UL << align_shift; 230ed02bdaSArd Biesheuvel u64 first_slot, last_slot, region_end; 240ed02bdaSArd Biesheuvel 250ed02bdaSArd Biesheuvel if (md->type != EFI_CONVENTIONAL_MEMORY) 260ed02bdaSArd Biesheuvel return 0; 270ed02bdaSArd Biesheuvel 280ed02bdaSArd Biesheuvel if (efi_soft_reserve_enabled() && 290ed02bdaSArd Biesheuvel (md->attribute & EFI_MEMORY_SP)) 300ed02bdaSArd Biesheuvel return 0; 310ed02bdaSArd Biesheuvel 320ed02bdaSArd Biesheuvel region_end = min(md->phys_addr + md->num_pages * EFI_PAGE_SIZE - 1, 33*bc5ddcefSArd Biesheuvel alloc_limit); 344152433cSBenjamin Herrenschmidt if (region_end < size) 354152433cSBenjamin Herrenschmidt return 0; 360ed02bdaSArd Biesheuvel 370ed02bdaSArd Biesheuvel first_slot = round_up(md->phys_addr, align); 380ed02bdaSArd Biesheuvel last_slot = round_down(region_end - size + 1, align); 390ed02bdaSArd Biesheuvel 400ed02bdaSArd Biesheuvel if (first_slot > last_slot) 410ed02bdaSArd Biesheuvel return 0; 420ed02bdaSArd Biesheuvel 430ed02bdaSArd Biesheuvel return ((unsigned long)(last_slot - first_slot) >> align_shift) + 1; 440ed02bdaSArd Biesheuvel } 450ed02bdaSArd Biesheuvel 460ed02bdaSArd Biesheuvel /* 470ed02bdaSArd Biesheuvel * The UEFI memory descriptors have a virtual address field that is only used 480ed02bdaSArd Biesheuvel * when installing the virtual mapping using SetVirtualAddressMap(). Since it 490ed02bdaSArd Biesheuvel * is unused here, we can reuse it to keep track of each descriptor's slot 500ed02bdaSArd Biesheuvel * count. 510ed02bdaSArd Biesheuvel */ 520ed02bdaSArd Biesheuvel #define MD_NUM_SLOTS(md) ((md)->virt_addr) 530ed02bdaSArd Biesheuvel 540ed02bdaSArd Biesheuvel efi_status_t efi_random_alloc(unsigned long size, 550ed02bdaSArd Biesheuvel unsigned long align, 560ed02bdaSArd Biesheuvel unsigned long *addr, 579cf42bcaSArd Biesheuvel unsigned long random_seed, 58*bc5ddcefSArd Biesheuvel int memory_type, 59*bc5ddcefSArd Biesheuvel unsigned long alloc_limit) 600ed02bdaSArd Biesheuvel { 61eab31265SArd Biesheuvel unsigned long total_slots = 0, target_slot; 62a6cfe03cSArd Biesheuvel unsigned long total_mirrored_slots = 0; 63eab31265SArd Biesheuvel struct efi_boot_memmap *map; 640ed02bdaSArd Biesheuvel efi_status_t status; 650ed02bdaSArd Biesheuvel int map_offset; 660ed02bdaSArd Biesheuvel 67171539f5SArd Biesheuvel status = efi_get_memory_map(&map, false); 680ed02bdaSArd Biesheuvel if (status != EFI_SUCCESS) 690ed02bdaSArd Biesheuvel return status; 700ed02bdaSArd Biesheuvel 710ed02bdaSArd Biesheuvel if (align < EFI_ALLOC_ALIGN) 720ed02bdaSArd Biesheuvel align = EFI_ALLOC_ALIGN; 730ed02bdaSArd Biesheuvel 74e1df73e2SArd Biesheuvel size = round_up(size, EFI_ALLOC_ALIGN); 75e1df73e2SArd Biesheuvel 760ed02bdaSArd Biesheuvel /* count the suitable slots in each memory map entry */ 77eab31265SArd Biesheuvel for (map_offset = 0; map_offset < map->map_size; map_offset += map->desc_size) { 78eab31265SArd Biesheuvel efi_memory_desc_t *md = (void *)map->map + map_offset; 790ed02bdaSArd Biesheuvel unsigned long slots; 800ed02bdaSArd Biesheuvel 81*bc5ddcefSArd Biesheuvel slots = get_entry_num_slots(md, size, ilog2(align), alloc_limit); 820ed02bdaSArd Biesheuvel MD_NUM_SLOTS(md) = slots; 830ed02bdaSArd Biesheuvel total_slots += slots; 84a6cfe03cSArd Biesheuvel if (md->attribute & EFI_MEMORY_MORE_RELIABLE) 85a6cfe03cSArd Biesheuvel total_mirrored_slots += slots; 860ed02bdaSArd Biesheuvel } 870ed02bdaSArd Biesheuvel 88a6cfe03cSArd Biesheuvel /* consider only mirrored slots for randomization if any exist */ 89a6cfe03cSArd Biesheuvel if (total_mirrored_slots > 0) 90a6cfe03cSArd Biesheuvel total_slots = total_mirrored_slots; 91a6cfe03cSArd Biesheuvel 920ed02bdaSArd Biesheuvel /* find a random number between 0 and total_slots */ 93c37c9162SArd Biesheuvel target_slot = (total_slots * (u64)(random_seed & U32_MAX)) >> 32; 940ed02bdaSArd Biesheuvel 950ed02bdaSArd Biesheuvel /* 960ed02bdaSArd Biesheuvel * target_slot is now a value in the range [0, total_slots), and so 970ed02bdaSArd Biesheuvel * it corresponds with exactly one of the suitable slots we recorded 980ed02bdaSArd Biesheuvel * when iterating over the memory map the first time around. 990ed02bdaSArd Biesheuvel * 1000ed02bdaSArd Biesheuvel * So iterate over the memory map again, subtracting the number of 1010ed02bdaSArd Biesheuvel * slots of each entry at each iteration, until we have found the entry 1020ed02bdaSArd Biesheuvel * that covers our chosen slot. Use the residual value of target_slot 1030ed02bdaSArd Biesheuvel * to calculate the randomly chosen address, and allocate it directly 1040ed02bdaSArd Biesheuvel * using EFI_ALLOCATE_ADDRESS. 1050ed02bdaSArd Biesheuvel */ 1060b1d9debSArd Biesheuvel status = EFI_OUT_OF_RESOURCES; 107eab31265SArd Biesheuvel for (map_offset = 0; map_offset < map->map_size; map_offset += map->desc_size) { 108eab31265SArd Biesheuvel efi_memory_desc_t *md = (void *)map->map + map_offset; 1090ed02bdaSArd Biesheuvel efi_physical_addr_t target; 1100ed02bdaSArd Biesheuvel unsigned long pages; 1110ed02bdaSArd Biesheuvel 112a6cfe03cSArd Biesheuvel if (total_mirrored_slots > 0 && 113a6cfe03cSArd Biesheuvel !(md->attribute & EFI_MEMORY_MORE_RELIABLE)) 114a6cfe03cSArd Biesheuvel continue; 115a6cfe03cSArd Biesheuvel 1160ed02bdaSArd Biesheuvel if (target_slot >= MD_NUM_SLOTS(md)) { 1170ed02bdaSArd Biesheuvel target_slot -= MD_NUM_SLOTS(md); 1180ed02bdaSArd Biesheuvel continue; 1190ed02bdaSArd Biesheuvel } 1200ed02bdaSArd Biesheuvel 1210ed02bdaSArd Biesheuvel target = round_up(md->phys_addr, align) + target_slot * align; 122e1df73e2SArd Biesheuvel pages = size / EFI_PAGE_SIZE; 1230ed02bdaSArd Biesheuvel 1240ed02bdaSArd Biesheuvel status = efi_bs_call(allocate_pages, EFI_ALLOCATE_ADDRESS, 1259cf42bcaSArd Biesheuvel memory_type, pages, &target); 1260ed02bdaSArd Biesheuvel if (status == EFI_SUCCESS) 1270ed02bdaSArd Biesheuvel *addr = target; 1280ed02bdaSArd Biesheuvel break; 1290ed02bdaSArd Biesheuvel } 1300ed02bdaSArd Biesheuvel 131eab31265SArd Biesheuvel efi_bs_call(free_pool, map); 1320ed02bdaSArd Biesheuvel 1330ed02bdaSArd Biesheuvel return status; 1340ed02bdaSArd Biesheuvel } 135