From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-6.1 required=3.0 tests=BAYES_00,DKIMWL_WL_HIGH, DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,HEADER_FROM_DIFFERENT_DOMAINS, MAILING_LIST_MULTI,SPF_HELO_NONE,SPF_PASS autolearn=no autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 8C004C433E9 for ; Wed, 3 Feb 2021 00:16:19 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 3EAD764F72 for ; Wed, 3 Feb 2021 00:16:19 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S231641AbhBCAQE (ORCPT ); Tue, 2 Feb 2021 19:16:04 -0500 Received: from us-smtp-delivery-124.mimecast.com ([63.128.21.124]:31665 "EHLO us-smtp-delivery-124.mimecast.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S229513AbhBCAQB (ORCPT ); Tue, 2 Feb 2021 19:16:01 -0500 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1612311270; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version:content-type:content-type: in-reply-to:in-reply-to:references:references; bh=SiaraPMcWlUGQ15HgWRnEvPFg5Cm3xwMPN0LwTOYT8c=; b=fZkmIIkn4Q8dL2+P2DOsZoiwofi6IgGwQp9iYDycPwjdY4gLuiFvDTrYA5jW2MNVLxwIdQ SYjuCK7z59m47Z/r4c5YlHhNz26B7LgwGZ7uDtWKjORB/bE6Aes99i8Gxl1xgMptkr/BDU UH2twDscAoO0un2NvkE5m68vPGd+qm0= Received: from mimecast-mx01.redhat.com (mimecast-mx01.redhat.com [209.132.183.4]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-566-6TM_tgRuO0-KZsWk2A-z2Q-1; Tue, 02 Feb 2021 19:14:28 -0500 X-MC-Unique: 6TM_tgRuO0-KZsWk2A-z2Q-1 Received: from smtp.corp.redhat.com (int-mx01.intmail.prod.int.phx2.redhat.com [10.5.11.11]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mimecast-mx01.redhat.com (Postfix) with ESMTPS id 59E9E801817; Wed, 3 Feb 2021 00:14:26 +0000 (UTC) Received: from treble (ovpn-120-118.rdu2.redhat.com [10.10.120.118]) by smtp.corp.redhat.com (Postfix) with ESMTPS id 0CD7118993; Wed, 3 Feb 2021 00:14:21 +0000 (UTC) Date: Tue, 2 Feb 2021 18:14:14 -0600 From: Josh Poimboeuf To: Nick Desaulniers Cc: Julien Thierry , Ard Biesheuvel , Mark Brown , Catalin Marinas , Kees Cook , Linux ARM , linux-efi , linux-hardening@vger.kernel.org, LKML , Mark Rutland , Masahiro Yamada , Michal Marek , Peter Zijlstra , raphael.gault@arm.com, Will Deacon , clang-built-linux , Bill Wendling , swine@google.com, yonghyun@google.com Subject: Re: [RFC PATCH 12/17] gcc-plugins: objtool: Add plugin to detect switch table on arm64 Message-ID: <20210203001414.idjrcrki7wmhndre@treble> References: <20210120173800.1660730-13-jthierry@redhat.com> <20210127221557.1119744-1-ndesaulniers@google.com> <20210127232651.rj3mo7c2oqh4ytsr@treble> <20210201214423.dhsma73k7ccscovm@treble> <671f1aa9-975e-1bda-6768-259adbdc24c8@redhat.com> MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Disposition: inline In-Reply-To: X-Scanned-By: MIMEDefang 2.79 on 10.5.11.11 Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On Tue, Feb 02, 2021 at 03:01:22PM -0800, Nick Desaulniers wrote: > > >> Thus far we've been able to successfully reverse engineer it on x86, > > >> though it hasn't been easy. > > >> > > >> There were some particulars for arm64 which made doing so impossible. > > >> (I don't remember the details.) > > > > The main issue is that the tables for arm64 have more indirection than x86. > > I wonder if PAC or BTI also make this slightly more complex? PAC at > least has implications for unwinders, IIUC. What is PAC/BTI? > > On x86, the dispatching jump instruction fetches the target address from > > a contiguous array of addresses based on a given offset. So the list of > > potential targets of the jump is neatly organized in a table (and sure, > > before link time these are just relocation, but still processable). > > > > On arm64 (with GCC at least), what is stored in a table is an array of > > candidate offsets from the jump instruction. And because arm64 is > > limited to 32bit instructions, the encoding often requires multiple > > instructions to compute the target address: > > > > ldr<*> x_offset, [x_offsets_table, x_index, ...] // load offset > > adr x_dest_base, // load target branch for offset 0 > > add x_dest, x_target_base, x_offset, ... // compute final address > > br x_dest // jump > > > > Where this gets trickier is that (with GCC) the offsets stored in the > > table might or might not be signed constants (and this can be seen in > > GCC intermediate representations, but I do not believe this information > > is output in the final object file). And on top of that, GCC might > > decide to use offsets that are seen as unsigned during intermediate > > representation as signed offset by sign extending them in the add > > instruction. > > > > So, to handle this we'd have to track the different operation done with > > the offset, from the load to the final jump, decoding the instructions > > and deducing the potential target instructions from the table of offsets. > > > > But that is error prone as we don't really know how many instructions > > can be between the ones doing the address computation, and I remember > > some messy case of a jump table inside a jump table where tracking the > > instruction touching one or the other offset would need a lot of corner > > case handling. > > > > And this of course is just for GCC, I haven't looked at what it all > > looks like on Clang's end. > > Sure, but this is what production unwinders do, and they don't require > compiler plugins, right? What do you mean by "production unwinders"? Generally unwinders rely on either frame pointers or DWARF, but (without validation) those aren't robust enough for live patching in the kernel, so I'm not sure how this is relevant. > > > I think the details are pertinent to finding a portable solution. The > > > commit message of this commit in particular doesn't document such > > > details, such as why such an approach is necessary or how the data is > > > laid out for objtool to consume it. > > > > > > > Sorry, I will need to make that clearer. The next patch explains it a > > bit [1] > > > > Basically, for simplicity, the plugin creates a new section containing > > Right, this takes a focus on simplicity, at the cost of alienating a toolchain. > > Ard's point about 3193c0836f20 relating to -fgcse is that when > presented with tricky cases to unwind, the simplest approach is taken. > There it was disabling a compiler specific compiler optimization, here > it's either a compiler specific compiler plugin (or disabling another > compiler optimization). The pattern seems to be "Objtool isn't smart > enough" ... "compiler optimization disabled" or "compiler plugin > dependency." You're taking the two absolute worst case scenarios (one of which is just a patch which doesn't look like it's going to get merged anyway) and drawing a false narrative. In this case the simplest approach would have been to just give up and disable jump tables. We try as hard as possible (beyond turning objtool into a full emulator) to avoid doing that kind of thing because objtool isn't supposed to dictate kernel optimizations. Otherwise we would have disabled jump tables (even for non-retpolines) a long time ago, because that's been a serious PITA. You might not like the plugin -- I don't like it either -- but the goal was to avoid penalizing the kernel with "objtool-friendly" optimizations. That said, jump tables are such a pain for objtool (and currently impossible to deal with for arm64) that I'm completely open to just disabling them if they're shown to have negligible benefit for the kernel. -- Josh From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-4.1 required=3.0 tests=BAYES_00,DKIMWL_WL_HIGH, DKIM_SIGNED,DKIM_VALID,HEADER_FROM_DIFFERENT_DOMAINS,MAILING_LIST_MULTI, SPF_HELO_NONE,SPF_PASS,URIBL_BLOCKED autolearn=no autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 8D465C433DB for ; Wed, 3 Feb 2021 00:16:17 +0000 (UTC) Received: from merlin.infradead.org (merlin.infradead.org [205.233.59.134]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by mail.kernel.org (Postfix) with ESMTPS id 2B39364F65 for ; Wed, 3 Feb 2021 00:16:17 +0000 (UTC) DMARC-Filter: OpenDMARC Filter v1.3.2 mail.kernel.org 2B39364F65 Authentication-Results: mail.kernel.org; dmarc=fail (p=none dis=none) header.from=redhat.com Authentication-Results: mail.kernel.org; spf=none smtp.mailfrom=linux-arm-kernel-bounces+linux-arm-kernel=archiver.kernel.org@lists.infradead.org DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=lists.infradead.org; s=merlin.20170209; h=Sender:Content-Transfer-Encoding: Content-Type:Cc:List-Subscribe:List-Help:List-Post:List-Archive: List-Unsubscribe:List-Id:In-Reply-To:MIME-Version:References:Message-ID: Subject:To:From:Date:Reply-To:Content-ID:Content-Description:Resent-Date: Resent-From:Resent-Sender:Resent-To:Resent-Cc:Resent-Message-ID:List-Owner; bh=mpTMO6gZjcXAyiGBKWUD9FNot67rOkOUiW9Vq2RFPU0=; b=Or6noyxY+lUvKMz6DTxbA1QER orzOrnM9Z+/+trQZskF5b4ki+c11oT28ZJAxaUZRAuHoBnzw0nmTZYDaNR0stBCb2pRrN0inRqXWA IXwvfXbtPaTgsFEYHtLmL9tq1+H+685ITCFrt3yhmZaV5jFA+xEucU1PN7eYBca7H3xux4Q5nKQvS 5wuCTBOCs8sDjNUjL1u54FBUsOQl7JQDu9WHAJrTwuaHtSf4g0FjpshkLiUagidEf2SjZvD3QFTsE 3vrg/YJXKsWnR0ntjf0IutBEUqJck5yBu7zT6cBJj0J+y6WpaSLP17x9bs4d5hi4KO2l3EzM0Difj HB2sZBuIw==; Received: from localhost ([::1] helo=merlin.infradead.org) by merlin.infradead.org with esmtp (Exim 4.92.3 #3 (Red Hat Linux)) id 1l75oe-0006PK-FU; Wed, 03 Feb 2021 00:14:40 +0000 Received: from us-smtp-delivery-124.mimecast.com ([63.128.21.124]) by merlin.infradead.org with esmtps (Exim 4.92.3 #3 (Red Hat Linux)) id 1l75oZ-0006OQ-8u for linux-arm-kernel@lists.infradead.org; Wed, 03 Feb 2021 00:14:37 +0000 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1612311272; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version:content-type:content-type: in-reply-to:in-reply-to:references:references; bh=SiaraPMcWlUGQ15HgWRnEvPFg5Cm3xwMPN0LwTOYT8c=; b=agnhJAtKz8i+bQHm7wdMz5h/NXs6tovDFJwpKl0z+dpqphbDlfLTuZhVcPnrfZnyxCjKOT Cf3Iza4Do3Ow9KDabPg5tQ+0Lb0XYkiYVwPLdqKtpz3NiH/F9GvAk28P6QSHTPC2yhxrbJ Z8x1S8sGffXtNjUT6doz1c2tJaERPVw= Received: from mimecast-mx01.redhat.com (mimecast-mx01.redhat.com [209.132.183.4]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-566-6TM_tgRuO0-KZsWk2A-z2Q-1; Tue, 02 Feb 2021 19:14:28 -0500 X-MC-Unique: 6TM_tgRuO0-KZsWk2A-z2Q-1 Received: from smtp.corp.redhat.com (int-mx01.intmail.prod.int.phx2.redhat.com [10.5.11.11]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mimecast-mx01.redhat.com (Postfix) with ESMTPS id 59E9E801817; Wed, 3 Feb 2021 00:14:26 +0000 (UTC) Received: from treble (ovpn-120-118.rdu2.redhat.com [10.10.120.118]) by smtp.corp.redhat.com (Postfix) with ESMTPS id 0CD7118993; Wed, 3 Feb 2021 00:14:21 +0000 (UTC) Date: Tue, 2 Feb 2021 18:14:14 -0600 From: Josh Poimboeuf To: Nick Desaulniers Subject: Re: [RFC PATCH 12/17] gcc-plugins: objtool: Add plugin to detect switch table on arm64 Message-ID: <20210203001414.idjrcrki7wmhndre@treble> References: <20210120173800.1660730-13-jthierry@redhat.com> <20210127221557.1119744-1-ndesaulniers@google.com> <20210127232651.rj3mo7c2oqh4ytsr@treble> <20210201214423.dhsma73k7ccscovm@treble> <671f1aa9-975e-1bda-6768-259adbdc24c8@redhat.com> MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: X-Scanned-By: MIMEDefang 2.79 on 10.5.11.11 X-CRM114-Version: 20100106-BlameMichelson ( TRE 0.8.0 (BSD) ) MR-646709E3 X-CRM114-CacheID: sfid-20210202_191435_387050_4DF1B92D X-CRM114-Status: GOOD ( 39.85 ) X-BeenThere: linux-arm-kernel@lists.infradead.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Cc: Mark Rutland , Bill Wendling , linux-efi , Julien Thierry , clang-built-linux , Peter Zijlstra , Catalin Marinas , Masahiro Yamada , yonghyun@google.com, LKML , Michal Marek , raphael.gault@arm.com, Mark Brown , linux-hardening@vger.kernel.org, swine@google.com, Will Deacon , Ard Biesheuvel , Linux ARM , Kees Cook Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit Sender: "linux-arm-kernel" Errors-To: linux-arm-kernel-bounces+linux-arm-kernel=archiver.kernel.org@lists.infradead.org On Tue, Feb 02, 2021 at 03:01:22PM -0800, Nick Desaulniers wrote: > > >> Thus far we've been able to successfully reverse engineer it on x86, > > >> though it hasn't been easy. > > >> > > >> There were some particulars for arm64 which made doing so impossible. > > >> (I don't remember the details.) > > > > The main issue is that the tables for arm64 have more indirection than x86. > > I wonder if PAC or BTI also make this slightly more complex? PAC at > least has implications for unwinders, IIUC. What is PAC/BTI? > > On x86, the dispatching jump instruction fetches the target address from > > a contiguous array of addresses based on a given offset. So the list of > > potential targets of the jump is neatly organized in a table (and sure, > > before link time these are just relocation, but still processable). > > > > On arm64 (with GCC at least), what is stored in a table is an array of > > candidate offsets from the jump instruction. And because arm64 is > > limited to 32bit instructions, the encoding often requires multiple > > instructions to compute the target address: > > > > ldr<*> x_offset, [x_offsets_table, x_index, ...] // load offset > > adr x_dest_base, // load target branch for offset 0 > > add x_dest, x_target_base, x_offset, ... // compute final address > > br x_dest // jump > > > > Where this gets trickier is that (with GCC) the offsets stored in the > > table might or might not be signed constants (and this can be seen in > > GCC intermediate representations, but I do not believe this information > > is output in the final object file). And on top of that, GCC might > > decide to use offsets that are seen as unsigned during intermediate > > representation as signed offset by sign extending them in the add > > instruction. > > > > So, to handle this we'd have to track the different operation done with > > the offset, from the load to the final jump, decoding the instructions > > and deducing the potential target instructions from the table of offsets. > > > > But that is error prone as we don't really know how many instructions > > can be between the ones doing the address computation, and I remember > > some messy case of a jump table inside a jump table where tracking the > > instruction touching one or the other offset would need a lot of corner > > case handling. > > > > And this of course is just for GCC, I haven't looked at what it all > > looks like on Clang's end. > > Sure, but this is what production unwinders do, and they don't require > compiler plugins, right? What do you mean by "production unwinders"? Generally unwinders rely on either frame pointers or DWARF, but (without validation) those aren't robust enough for live patching in the kernel, so I'm not sure how this is relevant. > > > I think the details are pertinent to finding a portable solution. The > > > commit message of this commit in particular doesn't document such > > > details, such as why such an approach is necessary or how the data is > > > laid out for objtool to consume it. > > > > > > > Sorry, I will need to make that clearer. The next patch explains it a > > bit [1] > > > > Basically, for simplicity, the plugin creates a new section containing > > Right, this takes a focus on simplicity, at the cost of alienating a toolchain. > > Ard's point about 3193c0836f20 relating to -fgcse is that when > presented with tricky cases to unwind, the simplest approach is taken. > There it was disabling a compiler specific compiler optimization, here > it's either a compiler specific compiler plugin (or disabling another > compiler optimization). The pattern seems to be "Objtool isn't smart > enough" ... "compiler optimization disabled" or "compiler plugin > dependency." You're taking the two absolute worst case scenarios (one of which is just a patch which doesn't look like it's going to get merged anyway) and drawing a false narrative. In this case the simplest approach would have been to just give up and disable jump tables. We try as hard as possible (beyond turning objtool into a full emulator) to avoid doing that kind of thing because objtool isn't supposed to dictate kernel optimizations. Otherwise we would have disabled jump tables (even for non-retpolines) a long time ago, because that's been a serious PITA. You might not like the plugin -- I don't like it either -- but the goal was to avoid penalizing the kernel with "objtool-friendly" optimizations. That said, jump tables are such a pain for objtool (and currently impossible to deal with for arm64) that I'm completely open to just disabling them if they're shown to have negligible benefit for the kernel. -- Josh _______________________________________________ linux-arm-kernel mailing list linux-arm-kernel@lists.infradead.org http://lists.infradead.org/mailman/listinfo/linux-arm-kernel