From patchwork Mon Jan 11 13:19:13 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Ard Biesheuvel X-Patchwork-Id: 59477 Delivered-To: patch@linaro.org Received: by 10.112.130.2 with SMTP id oa2csp2105177lbb; Mon, 11 Jan 2016 05:21:24 -0800 (PST) X-Received: by 10.98.87.204 with SMTP id i73mr25973364pfj.63.1452518484290; Mon, 11 Jan 2016 05:21:24 -0800 (PST) Return-Path: Received: from vger.kernel.org (vger.kernel.org. [209.132.180.67]) by mx.google.com with ESMTP id rm12si2448249pab.225.2016.01.11.05.21.23; Mon, 11 Jan 2016 05:21:24 -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 S1759995AbcAKNVU (ORCPT + 29 others); Mon, 11 Jan 2016 08:21:20 -0500 Received: from mail-wm0-f54.google.com ([74.125.82.54]:38438 "EHLO mail-wm0-f54.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S932882AbcAKNUR (ORCPT ); Mon, 11 Jan 2016 08:20:17 -0500 Received: by mail-wm0-f54.google.com with SMTP id b14so267962757wmb.1 for ; Mon, 11 Jan 2016 05:20:16 -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=7NyC6fyXXNRXpFR5mdyNs5iEajHoG/aZ3a+dDg6T6Rs=; b=efq6abMXHORyuEhOx+6ZtjyhHNsPdrK6SkzEqD5ngMseLihiMwvA8VC/h4wyiBiYNs e7vnRXbvmb7wLNyOW3G1PwUPk4neRr+k+lhwadxUBurEW73gYxcoJ5yutK78QnsZ3biP P0nSuTVaZ1NqNYZiIkxwAVU9ckcMWQSexoTJ0= 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=7NyC6fyXXNRXpFR5mdyNs5iEajHoG/aZ3a+dDg6T6Rs=; b=DTqD/SrpsZnRCEHw1D09U2W6pH4v1UaqT3vuoa6dBIF2FK6GObJ1Pj92wP66bkeTti IWdIk2Jh9EaimCL3PcXzbTyPq6tyNpSjuvc7rhlmeiEoCtRLRU3/tMw/80jso/Lgc08B YZNj0s1AP8JhRAKUeEHGuBSWy6SL0BYavNk1yg58zelMFS2MHLSogOj7upFGJ+YXrzML mfAd0o55Y68rTETAXgbHdUBa3GfGoqFXxxLOyOsGpd7/kqi6lEfkYa8B2E9Borxix4RX qxyUGlJcs8AtuZOx21O2Y8Xu4FQPvSU687iZO1+ksf1nWwB2RsCMRTNOTvJtkKN0w2uS LEpw== X-Gm-Message-State: ALoCoQkQ7bT5mACA+jHmS2UHhd3hJ6TdO6q6QiPVe/aryHpmbbm9gG1fL0BGrfdj1rmJtPR7uQh+W8j3DdIVGj7nBFWUS9Aoww== X-Received: by 10.194.172.2 with SMTP id ay2mr133674475wjc.137.1452518415775; Mon, 11 Jan 2016 05:20:15 -0800 (PST) Received: from localhost.localdomain (cag06-7-83-153-85-71.fbx.proxad.net. [83.153.85.71]) by smtp.gmail.com with ESMTPSA id c15sm12766055wmd.19.2016.01.11.05.20.13 (version=TLS1_2 cipher=ECDHE-RSA-AES128-SHA bits=128/128); Mon, 11 Jan 2016 05:20:15 -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, Ard Biesheuvel , Matt Fleming Subject: [PATCH v3 19/21] efi: stub: add implementation of efi_random_alloc() Date: Mon, 11 Jan 2016 14:19:13 +0100 Message-Id: <1452518355-4606-21-git-send-email-ard.biesheuvel@linaro.org> X-Mailer: git-send-email 2.5.0 In-Reply-To: <1452518355-4606-1-git-send-email-ard.biesheuvel@linaro.org> References: <1452518355-4606-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 offset 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 | 85 ++++++++++++++++++++ 2 files changed, 89 insertions(+) -- 2.5.0 diff --git a/drivers/firmware/efi/libstub/efistub.h b/drivers/firmware/efi/libstub/efistub.h index 206b7252b9d1..7a38e29da53d 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_bits, + 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 f539b1e31459..d4829824508c 100644 --- a/drivers/firmware/efi/libstub/random.c +++ b/drivers/firmware/efi/libstub/random.c @@ -33,3 +33,88 @@ efi_status_t efi_get_random_bytes(efi_system_table_t *sys_table, return rng->get_rng(rng, NULL, size, out); } + +/* + * Return a weight for a memory entry depending on how many offsets it covers + * that are suitably aligned and supply enough room for the allocation. + */ +static unsigned long get_entry_weight(efi_memory_desc_t *md, unsigned long size, + unsigned long align_bits) +{ + u64 start, end; + + if (md->type != EFI_CONVENTIONAL_MEMORY) + return 0; + + if (!(md->attribute & EFI_MEMORY_WB)) + return 0; + + start = round_up(md->phys_addr, 1 << align_bits); + end = round_down(md->phys_addr + md->num_pages * EFI_PAGE_SIZE - size, + 1 << align_bits); + + if (start >= end) + return 0; + + return (end - start) >> align_bits; +} + +/* + * 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 weight. + */ +#define MD_WEIGHT(md) ((md)->virt_addr) + +efi_status_t efi_random_alloc(efi_system_table_t *sys_table_arg, + unsigned long size, unsigned long align_bits, + unsigned long *addr, unsigned long random_seed) +{ + unsigned long map_size, desc_size, max_weight = 0, target; + efi_memory_desc_t *memory_map; + efi_status_t status = EFI_NOT_FOUND; + int l; + + status = efi_get_memory_map(sys_table_arg, &memory_map, &map_size, + &desc_size, NULL, NULL); + if (status != EFI_SUCCESS) + return status; + + /* assign each entry in the memory map a weight */ + for (l = 0; l < map_size; l += desc_size) { + efi_memory_desc_t *md = (void *)memory_map + l; + unsigned long weight; + + weight = get_entry_weight(md, size, align_bits); + MD_WEIGHT(md) = weight; + max_weight += weight; + } + + /* find a random number between 0 and max_weight */ + target = (max_weight * (u16)random_seed) >> 16; + + /* find the entry whose accumulated weight covers the target */ + for (l = 0; l < map_size; l += desc_size) { + efi_memory_desc_t *md = (void *)memory_map + l; + + if (target < MD_WEIGHT(md)) { + unsigned long pages; + + *addr = round_up(md->phys_addr, 1 << align_bits) + + (target << align_bits); + pages = round_up(size, EFI_PAGE_SIZE) / EFI_PAGE_SIZE; + + status = efi_call_early(allocate_pages, + EFI_ALLOCATE_ADDRESS, + EFI_LOADER_DATA, + pages, + (efi_physical_addr_t *)addr); + break; + } + target -= MD_WEIGHT(md); + } + + efi_call_early(free_pool, memory_map); + + return status; +}