From patchwork Sun Oct 30 09:01:38 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Xim X-Patchwork-Id: 12969 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a5d:6687:0:0:0:0:0 with SMTP id l7csp1714265wru; Sun, 30 Oct 2022 02:22:43 -0700 (PDT) X-Google-Smtp-Source: AMsMyM5r1xPdygeDiaPrM/EeR+xIC1j+nymD8sBBYdSKDY6Ovh9IqL4AIhba6kjh8Ao+0IHeyo4c X-Received: by 2002:a05:6402:42c6:b0:462:1abc:e576 with SMTP id i6-20020a05640242c600b004621abce576mr7960508edc.223.1667121763552; Sun, 30 Oct 2022 02:22:43 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1667121763; cv=none; d=google.com; s=arc-20160816; b=qdP3DUNjk7vTfeuAh6E0ckehclmN3weLGbisAOFEU8NA7h76lowzpGCclGr5kf4H5o uO86tUZBu5cyl+wMoanfSqolQiVIk/v/W8XuuY8YdCOoeDv11BXRTAsHLYbLGWrbqtZ1 wf9lCGGfB0Gar1D3tRZKolYxEnFqLNm3rHMasggoADjcnBWZfvqYmMo2S+/TRbC2EhWD Kq2qneOwmFGU2LxOXSj8kUpd99LE/pAXB1U3wcXJX2NIiFbV83sB8WWm7M7El2/NQ2a2 Pb0qcnuoQ4YXhBexMJKEzi15G3l6P5CpfRiCJqxy/bVqNwZSU+EyF0d8B373OGIslMO7 zuyw== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:content-transfer-encoding:mime-version :references:in-reply-to:message-id:date:subject:cc:to:from; bh=M8o+dKKqjK4yI2SQE52EfBBGj31vv9h1hDO1fl1h0oo=; b=jJiv6ryglBPuqtoUlVQf/wQ8FGBs06rVV5JzWNnJN/zFbBEG6uA1OHI9P2rBygHnQg 2duzg5Xvwr6tf2IBG9roY8IfA7lo+sD0IVbJabAd2D8VFPZdr5IWAVThPsP9w8JaL7Ng QyYK8YKcNyi9Jz6xf8BoMBEMZKWthtMfqSmnFKijRbwT+RKE6KV93Lt0pusLJNKvLvZ8 pnvFrIxG8G8rZc0fSOsB1XldUY6y8Q+/2jC2yS/dGqtnWnUR4HU1EBRpEq4A5AcqRshZ IhIz3jrHS7u4aYe4fuu27CLTDQg+FEBYYSWJVfQHS60n5KH9b0za6/EFTDy9oftqNGUu eMBg== ARC-Authentication-Results: i=1; mx.google.com; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org Received: from out1.vger.email (out1.vger.email. [2620:137:e000::1:20]) by mx.google.com with ESMTP id v21-20020aa7d655000000b0045a11b60c57si3869956edr.121.2022.10.30.02.22.20; Sun, 30 Oct 2022 02:22:43 -0700 (PDT) Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20; Authentication-Results: mx.google.com; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S229730AbiJ3JVo (ORCPT + 99 others); Sun, 30 Oct 2022 05:21:44 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:32916 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S229608AbiJ3JVk (ORCPT ); Sun, 30 Oct 2022 05:21:40 -0400 X-Greylist: delayed 1158 seconds by postgrey-1.37 at lindbergh.monkeyblade.net; Sun, 30 Oct 2022 02:21:37 PDT Received: from cstnet.cn (smtp23.cstnet.cn [159.226.251.23]) by lindbergh.monkeyblade.net (Postfix) with ESMTP id 17DD4B4A8 for ; Sun, 30 Oct 2022 02:21:36 -0700 (PDT) Received: from cgk-Precision-3650-Tower.. (unknown [219.141.235.82]) by APP-03 (Coremail) with SMTP id rQCowABXCVmKPV5jkxYmBw--.33365S9; Sun, 30 Oct 2022 17:02:18 +0800 (CST) From: Chen Guokai To: paul.walmsley@sifive.com, palmer@dabbelt.com, aou@eecs.berkeley.edu, rostedt@goodmis.org, mingo@redhat.com, sfr@canb.auug.org.au Cc: linux-riscv@lists.infradead.org, linux-kernel@vger.kernel.org, liaochang1@huawei.com, Chen Guokai Subject: [PATCH 5/8] riscv/kprobe: Search free register(s) to clobber for 'AUIPC/JALR' Date: Sun, 30 Oct 2022 17:01:38 +0800 Message-Id: <20221030090141.2550837-6-chenguokai17@mails.ucas.ac.cn> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20221030090141.2550837-1-chenguokai17@mails.ucas.ac.cn> References: <20221030090141.2550837-1-chenguokai17@mails.ucas.ac.cn> MIME-Version: 1.0 X-CM-TRANSID: rQCowABXCVmKPV5jkxYmBw--.33365S9 X-Coremail-Antispam: 1UD129KBjvJXoWfJry3uryfWFyDWw43Xw1xAFb_yoWDZryxpF W3Gw4rtF4Utrs5WrW3tF1kJrWSgFs3Grs8Zr15t3yUAw43G3ySqFWvga4avr1DGF13Zr48 Jr4Y9rWI9r4DAFDanT9S1TB71UUUUUUqnTZGkaVYY2UrUUUUjbIjqfuFe4nvWSU5nxnvy2 9KBjDU0xBIdaVrnRJUUUQY14x267AKxVWrJVCq3wAFc2x0x2IEx4CE42xK8VAvwI8IcIk0 rVWrJVCq3wAFIxvE14AKwVWUJVWUGwA2048vs2IY020E87I2jVAFwI0_JF0E3s1l82xGYI kIc2x26xkF7I0E14v26ryj6s0DM28lY4IEw2IIxxk0rwA2F7IY1VAKz4vEj48ve4kI8wA2 z4x0Y4vE2Ix0cI8IcVAFwI0_Xr0_Ar1l84ACjcxK6xIIjxv20xvEc7CjxVAFwI0_Cr0_Gr 1UM28EF7xvwVC2z280aVAFwI0_Cr1j6rxdM28EF7xvwVC2z280aVCY1x0267AKxVW0oVCq 3wAac4AC62xK8xCEY4vEwIxC4wAS0I0E0xvYzxvE52x082IY62kv0487Mc02F40EFcxC0V AKzVAqx4xG6I80ewAv7VC0I7IYx2IY67AKxVWUJVWUGwAv7VC2z280aVAFwI0_Gr0_Cr1l Ox8S6xCaFVCjc4AY6r1j6r4UM4x0Y48IcxkI7VAKI48JM4x0x7Aq67IIx4CEVc8vx2IErc IFxwACI402YVCY1x02628vn2kIc2xKxwCY02Avz4vE14v_GFWl42xK82IYc2Ij64vIr41l 4I8I3I0E4IkC6x0Yz7v_Jr0_Gr1lx2IqxVAqx4xG67AKxVWUJVWUGwC20s026x8GjcxK67 AKxVWUGVWUWwC2zVAF1VAY17CE14v26r1q6r43MIIYrxkI7VAKI48JMIIF0xvE2Ix0cI8I cVAFwI0_JFI_Gr1lIxAIcVC0I7IYx2IY6xkF7I0E14v26F4j6r4UJwCI42IY6xAIw20EY4 v20xvaj40_Jr0_JF4lIxAIcVC2z280aVAFwI0_Jr0_Gr1lIxAIcVC2z280aVCY1x0267AK xVW8JVW8JrUvcSsGvfC2KfnxnUUI43ZEXa7VUUiID3UUUUU== X-Originating-IP: [219.141.235.82] X-CM-SenderInfo: xfkh0w5xrntxyrx6ztxlovh3xfdvhtffof0/1tbiCQAPE2NeHVkoZQABsg X-Spam-Status: No, score=-1.1 required=5.0 tests=BAYES_00,DRUGS_ERECTILE, DRUGS_ERECTILE_OBFU,RCVD_IN_DNSWL_MED,SPF_HELO_PASS,SPF_PASS autolearn=no autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on lindbergh.monkeyblade.net Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1748103870346306500?= X-GMAIL-MSGID: =?utf-8?q?1748103870346306500?= From: Liao Chang This patch implements the algorithm of searching free register(s) for long-jump from a instruction range. AUIPC/JALR instruction pair is introduced with a much wider jump range (4GB), where auipc loads the upper 20 bits to a free register and jalr appends the lower 12 bits to form a 32 bit immediate. Since kprobes can be instrumented at anywhere in kernel space, the free register should be found in a generic way, not depending on the calling convention or any other regulations. The algorithm for finding the free register is inspired by the register renaming in modern processors. From the perspective of register renaming, a register could be represented as two different registers if two neighbour instructions both write to it but no one ever reads. Extending this fact, a register is considered to be free if there is no read before its next write in the execution flow. We are free to change its value without interfering normal execution. In order to do jump optimization, it needs to search two free registers, the first one is used to form AUIPC/JALR jumping to detour buffer, the second one is used to form JR jumping back from detour buffer. If first one has never been updated by instructions that replaced by 'AUIPC/JALR', both register are supposed to be the same one. Let's use the example below to explain how the algorithm work. Given kernel is RVI and RCV hybrid binary, and one kprobe is instrumented at the entry of function idle_dummy. Before Optimized Detour buffer : ... #1 add sp,sp,-16 auipc a0, #? add sp,sp,-16 #2 sd s0,8(sp) sd s0,8(sp) #3 addi s0,sp,16 jalr a0, #?(a0) addi s0,sp,16 #4 ld s0,8(sp) ld s0,8(sp) #5 li a0,0 li a0,0 auipc a0, #? #6 addi sp,sp,16 addi sp,sp,16 jr x0, #?(a0) #7 ret ret For regular kprobe, it is trival to replace the first instruction with C.EREABK, no more instruction and register will be clobbered, in order to optimize kprobe with long-jump, it used to patch the first 8 bytes with AUIPC/JALR, and a0 will be chosen to save the address jumping to, because from #1 to #7, a0 is the only one register that satifies two conditions: (1) First usage is as destination (2) Never been updated in detour buffer. While s0 has been used as the source register at #2, so it is not free to clobber. The searching starts from the kprobe and stop at the last instruction of function or the first branch/jump instruction, it decodes out the 'rs' and 'rd' part of each visited instruction. If the 'rd' has never been read before, record it to bitmask 'write'; if the 'rd' has been written in optimized instruction window, then record it to bitmask 'update'; if the 'rs' never been written before, then record it to another bitmask 'read'. When seaching stops, the remaining bits of 'write' are the free register to used for AUIPC/JALR, the remaining bits of 'write' filtered from 'update' are the free registers to used as 'JR'. Co-developed-by: Chen Guokai Signed-off-by: Chen Guokai Signed-off-by: Liao Chang --- arch/riscv/kernel/probes/opt.c | 225 ++++++++++++++++++++++++++++++++- 1 file changed, 224 insertions(+), 1 deletion(-) diff --git a/arch/riscv/kernel/probes/opt.c b/arch/riscv/kernel/probes/opt.c index e4a619c2077e..6d23c843832e 100644 --- a/arch/riscv/kernel/probes/opt.c +++ b/arch/riscv/kernel/probes/opt.c @@ -12,6 +12,9 @@ #include #include +#include "simulate-insn.h" +#include "decode-insn.h" + static inline int in_auipc_jalr_range(long val) { #ifdef CONFIG_ARCH_RV32I @@ -37,15 +40,235 @@ static void prepare_detour_buffer(kprobe_opcode_t *code, kprobe_opcode_t *slot, { } +/* Registers the first usage of which is the destination of instruction */ +#define WRITE_ON(reg) \ + (*write |= (((*read >> (reg)) ^ 1UL) & 1) << (reg)) +/* Registers the first usage of which is the source of instruction */ +#define READ_ON(reg) \ + (*read |= (((*write >> (reg)) ^ 1UL) & 1) << (reg)) + /* * In RISC-V ISA, AUIPC/JALR clobber one register to form target address, * by inspired by register renaming in OoO processor, this involves search * backwards that is not previously used as a source register and is used * as a destination register before any branch or jump instruction. */ +static void arch_find_register(unsigned long start, unsigned long end, + unsigned long *write, unsigned long *read) +{ + kprobe_opcode_t insn; + unsigned long addr, offset = 0UL; + + for (addr = start; addr < end; addr += offset) { + insn = *(kprobe_opcode_t *)addr; + offset = GET_INSN_LENGTH(insn); + +#ifdef CONFIG_RISCV_ISA_C + if (offset == RVI_INSN_LEN) + goto is_rvi; + + insn &= __COMPRESSED_INSN_MASK; + /* Stop searching until any control transfer instruction */ + if (riscv_insn_is_c_ebreak(insn) || riscv_insn_is_c_j(insn)) + break; + + if (riscv_insn_is_c_jal(insn)) { + /* The rd of C.JAL is x1 by default */ + WRITE_ON(1); + break; + } + + if (riscv_insn_is_c_jr(insn)) { + READ_ON(rvc_r_rs1(insn)); + break; + } + + if (riscv_insn_is_c_jalr(insn)) { + READ_ON(rvc_r_rs1(insn)); + /* The rd of C.JALR is x1 by default */ + WRITE_ON(1); + break; + } + + if (riscv_insn_is_c_beqz(insn) || riscv_insn_is_c_bnez(insn)) { + READ_ON(rvc_b_rs(insn)); + break; + } + + /* + * Decode RVC instructions that encode integer registers, try + * to find out some destination register, the number of which + * are equal with 'least' and never be used as source register. + */ + if (riscv_insn_is_c_sub(insn) || riscv_insn_is_c_subw(insn)) { + READ_ON(rvc_a_rs1(insn)); + READ_ON(rvc_a_rs2(insn)); + continue; + } else if (riscv_insn_is_c_sq(insn) || + riscv_insn_is_c_sw(insn) || + riscv_insn_is_c_sd(insn)) { + READ_ON(rvc_s_rs1(insn)); + READ_ON(rvc_s_rs2(insn)); + continue; + } else if (riscv_insn_is_c_addi16sp(insn) || + riscv_insn_is_c_addi(insn) || + riscv_insn_is_c_addiw(insn) || + riscv_insn_is_c_slli(insn)) { + READ_ON(rvc_i_rs1(insn)); + continue; + } else if (riscv_insn_is_c_sri(insn) || + riscv_insn_is_c_andi(insn)) { + READ_ON(rvc_b_rs(insn)); + continue; + } else if (riscv_insn_is_c_sqsp(insn) || + riscv_insn_is_c_swsp(insn) || + riscv_insn_is_c_sdsp(insn)) { + READ_ON(rvc_ss_rs2(insn)); + /* The rs2 of C.SQSP/SWSP/SDSP are x2 by default */ + READ_ON(2); + continue; + } else if (riscv_insn_is_c_mv(insn)) { + READ_ON(rvc_r_rs2(insn)); + WRITE_ON(rvc_r_rd(insn)); + } else if (riscv_insn_is_c_addi4spn(insn)) { + /* The rs of C.ADDI4SPN is x2 by default */ + READ_ON(2); + WRITE_ON(rvc_l_rd(insn)); + } else if (riscv_insn_is_c_lq(insn) || + riscv_insn_is_c_lw(insn) || + riscv_insn_is_c_ld(insn)) { + /* FIXME: c.lw/c.ld share opcode with c.flw/c.fld */ + READ_ON(rvc_l_rs(insn)); + WRITE_ON(rvc_l_rd(insn)); + } else if (riscv_insn_is_c_lqsp(insn) || + riscv_insn_is_c_lwsp(insn) || + riscv_insn_is_c_ldsp(insn)) { + /* + * FIXME: c.lwsp/c.ldsp share opcode with c.flwsp/c.fldsp + * The rs of C.LQSP/C.LWSP/C.LDSP is x2 by default. + */ + READ_ON(2); + WRITE_ON(rvc_i_rd(insn)); + } else if (riscv_insn_is_c_li(insn) || + riscv_insn_is_c_lui(insn)) { + WRITE_ON(rvc_i_rd(insn)); + } + + if ((*write > 1UL) && __builtin_ctzl(*write & ~1UL)) + return; +is_rvi: +#endif + /* Stop searching until any control transfer instruction */ + if (riscv_insn_is_branch(insn)) { + READ_ON(rvi_rs1(insn)); + READ_ON(rvi_rs2(insn)); + break; + } + + if (riscv_insn_is_jal(insn)) { + WRITE_ON(rvi_rd(insn)); + break; + } + + if (riscv_insn_is_jalr(insn)) { + READ_ON(rvi_rs1(insn)); + WRITE_ON(rvi_rd(insn)); + break; + } + + if (riscv_insn_is_system(insn)) { + /* csrrw, csrrs, csrrc */ + if (rvi_rs1(insn)) + READ_ON(rvi_rs1(insn)); + /* csrrwi, csrrsi, csrrci, csrrw, csrrs, csrrc */ + if (rvi_rd(insn)) + WRITE_ON(rvi_rd(insn)); + break; + } + + /* + * Decode RVC instructions that has rd and rs, try to find out + * some rd, the number of which are equal with 'least' and never + * be used as rs. + */ + if (riscv_insn_is_lui(insn) || riscv_insn_is_auipc(insn)) { + WRITE_ON(rvi_rd(insn)); + } else if (riscv_insn_is_arith_ri(insn) || + riscv_insn_is_load(insn)) { + READ_ON(rvi_rs1(insn)); + WRITE_ON(rvi_rd(insn)); + } else if (riscv_insn_is_arith_rr(insn) || + riscv_insn_is_store(insn) || + riscv_insn_is_amo(insn)) { + READ_ON(rvi_rs1(insn)); + READ_ON(rvi_rs2(insn)); + WRITE_ON(rvi_rd(insn)); + } + + if ((*write > 1UL) && __builtin_ctzl(*write & ~1UL)) + return; + } +} + static void find_free_registers(struct kprobe *kp, struct optimized_kprobe *op, - int *rd1, int *rd2) + int *rd, int *ra) { + unsigned long start, end; + /* + * Searching algorithm explanation: + * + * 1. Define two types of instruction area firstly: + * + * +-----+ + * + + + * + + ---> instrunctions modified by optprobe, named 'O-Area'. + * + + + * +-----+ + * + + + * + + ---> instructions after optprobe, named 'K-Area'. + * + + + * + ~ + + * + * 2. There are two usages for each GPR in given instruction area. + * + * - W: GPR is used as the RD oprand at first emergence. + * - R: GPR is used as the RS oprand at first emergence. + * + * Then there are 4 different usages for each GPR totally: + * + * 1. Used as W in O-Area, Used as W in K-Area. + * 2. Used as W in O-Area, Used as R in K-Area. + * 3. Used as R in O-Area, Used as W in K-Area. + * 4. Used as R in O-Area, Used as R in K-Area. + * + * All registers satisfy #1 or #3 could be chosen to form 'AUIPC/JALR' + * jumping to detour buffer. + * + * All registers satisfy #1 or #2, could be chosen to form 'JR' jumping + * back from detour buffer. + */ + unsigned long kw = 0UL, kr = 0UL, ow = 0UL, or = 0UL; + + /* Search one free register used to form AUIPC/JALR */ + start = (unsigned long)&kp->opcode; + end = start + GET_INSN_LENGTH(kp->opcode); + arch_find_register(start, end, &ow, &or); + + start = (unsigned long)kp->addr + GET_INSN_LENGTH(kp->opcode); + end = (unsigned long)kp->addr + op->optinsn.length; + arch_find_register(start, end, &ow, &or); + + /* Search one free register used to form JR */ + arch_find_register(end, (unsigned long)_end, &kw, &kr); + + if ((kw & ow) > 1UL) { + *rd = __builtin_ctzl((kw & ow) & ~1UL); + *ra = *rd; + return; + } + + *rd = ((kw | ow) == 1UL) ? 0 : __builtin_ctzl((kw | ow) & ~1UL); + *ra = (kw == 1UL) ? 0 : __builtin_ctzl(kw & ~1UL); } /*