Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 23.128.96.18 as permitted sender) client-ip=23.128.96.18;
Subject: Re: [RFC PATCH 12/17] gcc-plugins: objtool: Add plugin to detect
 switch table on arm64
To:     Nick Desaulniers <ndesaulniers@google.com>,
        Josh Poimboeuf <jpoimboe@redhat.com>
Cc:     Ard Biesheuvel <ardb@kernel.org>, Mark Brown <broonie@kernel.org>,
        Catalin Marinas <catalin.marinas@arm.com>,
        Kees Cook <keescook@chromium.org>,
        Linux ARM <linux-arm-kernel@lists.infradead.org>,
        linux-efi <linux-efi@vger.kernel.org>,
        linux-hardening@vger.kernel.org,
        LKML <linux-kernel@vger.kernel.org>,
        Mark Rutland <mark.rutland@arm.com>,
        Masahiro Yamada <masahiroy@kernel.org>,
        Michal Marek <michal.lkml@markovi.net>,
        Peter Zijlstra <peterz@infradead.org>, raphael.gault@arm.com,
        Will Deacon <will@kernel.org>,
        clang-built-linux <clang-built-linux@googlegroups.com>,
        Bill Wendling <morbo@google.com>
References: <20210120173800.1660730-13-jthierry@redhat.com>
 <20210127221557.1119744-1-ndesaulniers@google.com>
 <20210127232651.rj3mo7c2oqh4ytsr@treble>
 <CAKwvOdkOeENcM5X7X926sv2Xmtko=_nOPeKZ2+51s13CW1QAjw@mail.gmail.com>
 <20210201214423.dhsma73k7ccscovm@treble>
 <CAKwvOdmgNPSpY2oPHFr8EKGXYJbm7K9gySKFgyn4FERa9nTXmw@mail.gmail.com>
From:   Julien Thierry <jthierry@redhat.com>
Message-ID: <671f1aa9-975e-1bda-6768-259adbdc24c8@redhat.com>
Date:   Tue, 2 Feb 2021 09:57:19 +0100
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:68.0) Gecko/20100101
 Thunderbird/68.11.0
MIME-Version: 1.0
In-Reply-To: <CAKwvOdmgNPSpY2oPHFr8EKGXYJbm7K9gySKFgyn4FERa9nTXmw@mail.gmail.com>
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Language: en-US
Content-Transfer-Encoding: 7bit
Precedence: bulk


On 2/2/21 12:17 AM, Nick Desaulniers wrote:
> On Mon, Feb 1, 2021 at 1:44 PM Josh Poimboeuf <jpoimboe@redhat.com> wrote:
>>
>> On Fri, Jan 29, 2021 at 10:10:01AM -0800, Nick Desaulniers wrote:
>>> On Wed, Jan 27, 2021 at 3:27 PM Josh Poimboeuf <jpoimboe@redhat.com> wrote:
>>>>
>>>> On Wed, Jan 27, 2021 at 02:15:57PM -0800, Nick Desaulniers wrote:
>>>>>> From: Raphael Gault <raphael.gault@arm.com>
>>>>>>
>>>>>> This plugins comes into play before the final 2 RTL passes of GCC and
>>>>>> detects switch-tables that are to be outputed in the ELF and writes
>>>>>> information in an ".discard.switch_table_info" section which will be
>>>>>> used by objtool.
>>>>>>
>>>>>> Signed-off-by: Raphael Gault <raphael.gault@arm.com>
>>>>>> [J.T.: Change section name to store switch table information,
>>>>>>         Make plugin Kconfig be selected rather than opt-in by user,
>>>>>>         Add a relocation in the switch_table_info that points to
>>>>>>         the jump operation itself]
>>>>>> Signed-off-by: Julien Thierry <jthierry@redhat.com>
>>>>>
>>>>> Rather than tightly couple this feature to a particular toolchain via
>>>>> plugin, it might be nice to consider what features could be spec'ed out
>>>>> for toolchains to implement (perhaps via a -f flag).
>>>>
>>>> The problem is being able to detect switch statement jump table vectors.
>>>>
>>>> For a given indirect branch (due to a switch statement), what are all
>>>> the corresponding jump targets?
>>>>
>>>> We would need the compiler to annotate that information somehow.
>>>
>>> Makes sense, the compiler should have this information.  How is this
>>> problem solved on x86?
>>
>> 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.

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, <addr>          // 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.


> 
> 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 
tables (one per jump table) of references to the jump targets, similar 
to what x86 has, except that in this case this table isn't actually used 
by runtime code and is discarded at link time. I only chose this to 
minimize what needed to be changed in objtool and because the format 
seemed simple enough.

But I'm open on some alternative, whether it's a -fjump-table-info 
option added to compilers with a different format to do the links. The 
important requirement is to be able to know all the candidate targets 
for a "br <reg>" instruction.

[1] https://lkml.org/lkml/2021/1/20/910

Thanks,

-- 
Julien Thierry