From mboxrd@z Thu Jan 1 00:00:00 1970 From: Jiong Wang Subject: Re: [RFC PATCH v2 bpf-next 0/2] verifier liveness simplification Date: Wed, 26 Sep 2018 23:16:10 +0100 Message-ID: <0252cca7-82e4-24d3-8682-e1a613d6cd78@netronome.com> References: Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 7bit Cc: netdev@vger.kernel.org To: Edward Cree , ast@kernel.org, daniel@iogearbox.net Return-path: Received: from mail-wr1-f66.google.com ([209.85.221.66]:40591 "EHLO mail-wr1-f66.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1725722AbeI0EbV (ORCPT ); Thu, 27 Sep 2018 00:31:21 -0400 Received: by mail-wr1-f66.google.com with SMTP id y8-v6so470327wrh.7 for ; Wed, 26 Sep 2018 15:16:15 -0700 (PDT) In-Reply-To: Content-Language: en-GB Sender: netdev-owner@vger.kernel.org List-ID: On 22/08/2018 20:00, Edward Cree wrote: > The first patch is a simplification of register liveness tracking by using > a separate parentage chain for each register and stack slot, thus avoiding > the need for logic to handle callee-saved registers when applying read > marks. In the future this idea may be extended to form use-def chains. Interesting. This could potentially help efficient code-gen for 32-bit architectures and I had been thinking some implementations along this line and would like to have a discussion. Program description === It will be good if we could know one instruction is safe to operate on low 32-bit sub-register only. If this is true: - 32-bit arches could save some code-gen. - 64-bit arches could utilize 32-bit sub-register instructions. Algorithm === Based on the current verifier code-path-walker, it looks to me we could get 32-bit safety information using the following algorithm: 1. assume all instructions operate on 32-bit sub-register initially. 2. link each insn to insns which define its use. 3. for a register use, if it is a 64-bit write back to memory, or if it is a comparison-then-jump based on 64-bit value, or if it is a right shift, then consider the use is a 64-bit use, then all its define insns and their parents define insns should be marked as need full 64-bit operation. 4. currently, register read (REG_LIVE_READ) will be propagated to parent state when path prune happened, and REG_LIVE_WRITTEN would screen off such propagation. We need to propagate 64-bit mark in similar way, but REG_LIVE_WRITTEN shouldn't screen off backward 64-bit mark propagation if the written reg also used as source reg (this has raised REG_LIVE_READ propagation but it is not necessarily indicating 64-bit read) in the same instruction. Implementation === And it seems there could be an implementation based on current liveness tracking infrastructure without dramatic change. 1. instruction level use->def chain - new active_defs array for each call frame to record which insn the active define of one register comes from. callee copies active_defs from caller for argument registers only, and copies active_def of R0 to caller when exit. struct bpf_func_state { ... s16 active_defs[__MAX_BPF_REG]; - new use->def chains for each instruction. one eBPF insn could have two uses at maximum. also one new boolean "full_ref_def" added to keep the final 32-bit safety information. it will be true if this instruction needs to operate on full 64-bit. bpf_insn_aux_data { ... struct { s16 def[2]; bool full_ref_def; }; 2. Inside mark_reg_read, split SRC_OP to SRC0_OP/SRC1_OP/SRC_OP_64/SRC1_OP_64 to indicate one register read if from the first or second use slot of this instruction, and to indicate whether the read is on full 64-bit which will only be true if the read is for 64-bit write back to memory, or 64-bit comparison-then-jump, or bit right shift means 64-bit. Build use->def chain for any read, but do 64-bit backward propagation for 64-bit read only. The propagation is to set full_ref_def to true for def and parent defs of the 64-bit read. 3. Need new bpf_reg_liveness enum, REG_LIVE_READ64 to indicate there is 64-bit access to one register in the pruned path, and need REG_LIVE_WRITTEN64 to indicate a write that is REG_LIVE_WRITTEN but should not screen backward propagate 64-bit read info. #define REG_LIVE_NONE 0 #define REG_LIVE_READ BIT(0) #define REG_LIVE_READ64 BIT(1) #define REG_LIVE_WRITTEN BIT(2) #define REG_LIVE_WRITTEN64 BIT(3) I might have missed something in above thoughts, would appreciate reviews and suggestions. I will also send out some concrete patches later. Regards, Jiong