From patchwork Tue Jan 26 17:10:47 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Ard Biesheuvel X-Patchwork-Id: 60491 Delivered-To: patch@linaro.org Received: by 10.112.130.2 with SMTP id oa2csp2089861lbb; Tue, 26 Jan 2016 09:13:08 -0800 (PST) X-Received: by 10.66.141.11 with SMTP id rk11mr34144196pab.156.1453828388105; Tue, 26 Jan 2016 09:13:08 -0800 (PST) Return-Path: Received: from vger.kernel.org (vger.kernel.org. [209.132.180.67]) by mx.google.com with ESMTP id wz15si3099194pac.76.2016.01.26.09.13.07; Tue, 26 Jan 2016 09:13:08 -0800 (PST) Received-SPF: pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) client-ip=209.132.180.67; Authentication-Results: mx.google.com; spf=pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dkim=pass header.i=@linaro.org Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S967174AbcAZRNF (ORCPT + 30 others); Tue, 26 Jan 2016 12:13:05 -0500 Received: from mail-wm0-f42.google.com ([74.125.82.42]:36352 "EHLO mail-wm0-f42.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S934100AbcAZRLx (ORCPT ); Tue, 26 Jan 2016 12:11:53 -0500 Received: by mail-wm0-f42.google.com with SMTP id l65so113137554wmf.1 for ; Tue, 26 Jan 2016 09:11:53 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=linaro.org; s=google; h=from:to:cc:subject:date:message-id:in-reply-to:references; bh=/KgAGRRVS7KHLTHwOU5WkWPdvxdaAKr7MkkWUCrtzFw=; b=cIhhGRClv1HaxI3yTNXKy/BC6D5NOW4kq/GJU/lyxjUdGd7glQFE/gyRlwMKozTddo QfeKMX6uXhg12uxVp3T/HVhP7Etrw5cAQjSVrCnz1vr1Bv+TCoFKy584g7PZnk+7k1QL fl3x+8eGxGCDxIAJkDCkX5VWeipG6yy0qyDyU= X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references; bh=/KgAGRRVS7KHLTHwOU5WkWPdvxdaAKr7MkkWUCrtzFw=; b=kMlO+nZood651WNLVRcOq/oTjPbT3kVK2Lp4xdu1nXjvAkquUT1yHY4H+YDbOtRBbC D2q5pYvE+LT5Xyrp4U7WWIqRD4OpHHC0rbUJPQddE5kBbcvk08iMnd/YRxwwspHNHxbz dT3Y9hSQTg761weYUtmNX54K4k6W8fMmzZop23MyMXQWrNMXcbP6IH6SybxNbuzf6WU5 V5O31WPniL8el8CU22xb6bx7LATJTjnMMkQvF4r9ejY2TyUVZAZJm1N/q6LmvCN7B9G8 mlFNMOQ6982VqEP7/+vcnGOvcNrtRlSUoJGIF9Vj8bBkhAU4MUyT2imlMRv5WdiNwlb5 SXnw== X-Gm-Message-State: AG10YOSGzAuxf8YRKnKg/EkE8coJ6EKUeXZ/CW3Ow8iWyvBbquFfNn/h8EJD1Eejy4JDAl2G X-Received: by 10.28.222.86 with SMTP id v83mr24119945wmg.17.1453828311944; Tue, 26 Jan 2016 09:11:51 -0800 (PST) Received: from localhost.localdomain ([195.55.142.58]) by smtp.gmail.com with ESMTPSA id ko2sm2328617wjc.9.2016.01.26.09.11.49 (version=TLS1_2 cipher=ECDHE-RSA-AES128-SHA bits=128/128); Tue, 26 Jan 2016 09:11:51 -0800 (PST) From: Ard Biesheuvel To: linux-arm-kernel@lists.infradead.org, kernel-hardening@lists.openwall.com, will.deacon@arm.com, catalin.marinas@arm.com, mark.rutland@arm.com, leif.lindholm@linaro.org, keescook@chromium.org, linux-kernel@vger.kernel.org Cc: stuart.yoder@freescale.com, bhupesh.sharma@freescale.com, arnd@arndb.de, marc.zyngier@arm.com, christoffer.dall@linaro.org, labbott@fedoraproject.org, matt@codeblueprint.co.uk, Ard Biesheuvel Subject: [PATCH v4 20/22] efi: stub: add implementation of efi_random_alloc() Date: Tue, 26 Jan 2016 18:10:47 +0100 Message-Id: <1453828249-14467-21-git-send-email-ard.biesheuvel@linaro.org> X-Mailer: git-send-email 2.5.0 In-Reply-To: <1453828249-14467-1-git-send-email-ard.biesheuvel@linaro.org> References: <1453828249-14467-1-git-send-email-ard.biesheuvel@linaro.org> Sender: linux-kernel-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org This implements efi_random_alloc(), which allocates a chunk of memory of a certain size at a certain alignment, and uses the random_seed argument it receives to randomize the address of the allocation. This is implemented by iterating over the UEFI memory map, counting the number of suitable slots (aligned offsets) within each region, and picking a random number between 0 and 'number of slots - 1' to select the slot, This should guarantee that each possible offset is chosen equally likely. Suggested-by: Kees Cook Cc: Matt Fleming Signed-off-by: Ard Biesheuvel --- drivers/firmware/efi/libstub/efistub.h | 4 + drivers/firmware/efi/libstub/random.c | 100 ++++++++++++++++++++ 2 files changed, 104 insertions(+) -- 2.5.0 diff --git a/drivers/firmware/efi/libstub/efistub.h b/drivers/firmware/efi/libstub/efistub.h index 206b7252b9d1..5ed3d3f38166 100644 --- a/drivers/firmware/efi/libstub/efistub.h +++ b/drivers/firmware/efi/libstub/efistub.h @@ -46,4 +46,8 @@ void efi_get_virtmap(efi_memory_desc_t *memory_map, unsigned long map_size, efi_status_t efi_get_random_bytes(efi_system_table_t *sys_table, unsigned long size, u8 *out); +efi_status_t efi_random_alloc(efi_system_table_t *sys_table_arg, + unsigned long size, unsigned long align, + unsigned long *addr, unsigned long random_seed); + #endif diff --git a/drivers/firmware/efi/libstub/random.c b/drivers/firmware/efi/libstub/random.c index 97941ee5954f..b98346350230 100644 --- a/drivers/firmware/efi/libstub/random.c +++ b/drivers/firmware/efi/libstub/random.c @@ -33,3 +33,103 @@ efi_status_t efi_get_random_bytes(efi_system_table_t *sys_table_arg, return rng->get_rng(rng, NULL, size, out); } + +/* + * Return the number of slots covered by this entry, i.e., the number of + * addresses it covers that are suitably aligned and supply enough room + * for the allocation. + */ +static unsigned long get_entry_num_slots(efi_memory_desc_t *md, + unsigned long size, + unsigned long align) +{ + u64 start, end; + + if (md->type != EFI_CONVENTIONAL_MEMORY) + return 0; + + start = round_up(md->phys_addr, align); + end = round_down(md->phys_addr + md->num_pages * EFI_PAGE_SIZE - size, + align); + + if (start > end) + return 0; + + return (end - start + 1) / align; +} + +/* + * The UEFI memory descriptors have a virtual address field that is only used + * when installing the virtual mapping using SetVirtualAddressMap(). Since it + * is unused here, we can reuse it to keep track of each descriptor's slot + * count. + */ +#define MD_NUM_SLOTS(md) ((md)->virt_addr) + +efi_status_t efi_random_alloc(efi_system_table_t *sys_table_arg, + unsigned long size, + unsigned long align, + unsigned long *addr, + unsigned long random_seed) +{ + unsigned long map_size, desc_size, total_slots = 0, target_slot; + efi_status_t status = EFI_NOT_FOUND; + efi_memory_desc_t *memory_map; + int map_offset; + + status = efi_get_memory_map(sys_table_arg, &memory_map, &map_size, + &desc_size, NULL, NULL); + if (status != EFI_SUCCESS) + return status; + + if (align < EFI_ALLOC_ALIGN) + align = EFI_ALLOC_ALIGN; + + /* count the suitable slots in each memory map entry */ + for (map_offset = 0; map_offset < map_size; map_offset += desc_size) { + efi_memory_desc_t *md = (void *)memory_map + map_offset; + unsigned long slots; + + slots = get_entry_num_slots(md, size, align); + MD_NUM_SLOTS(md) = slots; + total_slots += slots; + } + + /* find a random number between 0 and total_slots */ + target_slot = (total_slots * (u16)random_seed) >> 16; + + /* + * target_slot is now a value in the range [0, total_slots), and so + * it corresponds with exactly one of the suitable slots we recorded + * when iterating over the memory map the first time around. + * + * So iterate over the memory map again, subtracting the number of + * slots of each entry at each iteration, until we have found the entry + * that covers our chosen slot. Use the residual value of target_slot + * to calculate the randomly chosen address, and allocate it directly + * using EFI_ALLOCATE_ADDRESS. + */ + for (map_offset = 0; map_offset < map_size; map_offset += desc_size) { + efi_memory_desc_t *md = (void *)memory_map + map_offset; + efi_physical_addr_t target; + unsigned long pages; + + if (target_slot >= MD_NUM_SLOTS(md)) { + target_slot -= MD_NUM_SLOTS(md); + continue; + } + + target = round_up(md->phys_addr, align) + target_slot * align; + pages = round_up(size, EFI_PAGE_SIZE) / EFI_PAGE_SIZE; + + status = efi_call_early(allocate_pages, EFI_ALLOCATE_ADDRESS, + EFI_LOADER_DATA, pages, &target); + if (status == EFI_SUCCESS) + *addr = target; + break; + } + + efi_call_early(free_pool, memory_map); + + return status; +}