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: 8003781 Return-Path: X-Original-To: patchwork-linux-arm@patchwork.kernel.org Delivered-To: patchwork-parsemail@patchwork2.web.kernel.org Received: from mail.kernel.org (mail.kernel.org [198.145.29.136]) by patchwork2.web.kernel.org (Postfix) with ESMTP id 5712CBEEE5 for ; Mon, 11 Jan 2016 13:32:27 +0000 (UTC) Received: from mail.kernel.org (localhost [127.0.0.1]) by mail.kernel.org (Postfix) with ESMTP id 6876120220 for ; Mon, 11 Jan 2016 13:32:26 +0000 (UTC) Received: from bombadil.infradead.org (bombadil.infradead.org [198.137.202.9]) (using TLSv1.2 with cipher AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by mail.kernel.org (Postfix) with ESMTPS id 8F3E7201FE for ; Mon, 11 Jan 2016 13:32:24 +0000 (UTC) Received: from localhost ([127.0.0.1] helo=bombadil.infradead.org) by bombadil.infradead.org with esmtp (Exim 4.80.1 #2 (Red Hat Linux)) id 1aIcYe-0007fV-9w; Mon, 11 Jan 2016 13:30:52 +0000 Received: from mail-wm0-x22a.google.com ([2a00:1450:400c:c09::22a]) by bombadil.infradead.org with esmtps (Exim 4.80.1 #2 (Red Hat Linux)) id 1aIcOj-0003Wf-42 for linux-arm-kernel@lists.infradead.org; Mon, 11 Jan 2016 13:20:42 +0000 Received: by mail-wm0-x22a.google.com with SMTP id f206so211203039wmf.0 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=bIVwSWipxdI0NpnF5/S3AZWS7ROj0JLmcQGpxODw8+c3udVixGR04KcFbWVSUKdAol irJ8NG5lc8u8TukXrp88azWzBbxwaVpVluXjbcUI9u6Dxis7L4KVQ/YVM5lq9AKKfulk V3WOcXjZa0PlP3sdIoYqPUgp+m+MQoeElAKCWtVxZkSc9ODG5plJ6GQgaQcUb/niN0yP xdyiXNvcnVxml1ASWMGZIjxwfN1s4/C9gN3SYMWwYvQlY4OzK8g97RGSkVhFmV/EVUuM zUqkNJb5Vqg2LSC3urqXPtBzgHwOLpicSplma4Juo1uVR72BOGBBpifFMdF+BT21o2RI 2VuQ== X-Gm-Message-State: ALoCoQnGDVZLp1kIFeqjdVDXD/u/V6O4yPWa7qszVEycex0dft30SK+M3ISSzGmZkHoWnDEKIJY2AsFm33mU2GHzzOSsrctWOg== 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 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> X-CRM114-Version: 20100106-BlameMichelson ( TRE 0.8.0 (BSD) ) MR-646709E3 X-CRM114-CacheID: sfid-20160111_052037_708253_411F5BCD X-CRM114-Status: GOOD ( 17.27 ) X-Spam-Score: -2.7 (--) X-BeenThere: linux-arm-kernel@lists.infradead.org X-Mailman-Version: 2.1.20 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Cc: Matt Fleming , arnd@arndb.de, Ard Biesheuvel , bhupesh.sharma@freescale.com, stuart.yoder@freescale.com, marc.zyngier@arm.com, christoffer.dall@linaro.org MIME-Version: 1.0 Sender: "linux-arm-kernel" Errors-To: linux-arm-kernel-bounces+patchwork-linux-arm=patchwork.kernel.org@lists.infradead.org X-Spam-Status: No, score=-4.1 required=5.0 tests=BAYES_00,DKIM_SIGNED, RCVD_IN_DNSWL_MED,RP_MATCHES_RCVD,T_DKIM_INVALID,UNPARSEABLE_RELAY autolearn=unavailable version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on mail.kernel.org X-Virus-Scanned: ClamAV using ClamSMTP 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(+) 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; +}