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=-0.8 required=3.0 tests=DKIM_SIGNED,DKIM_VALID, HEADER_FROM_DIFFERENT_DOMAINS,MAILING_LIST_MULTI,SPF_HELO_NONE,SPF_PASS autolearn=ham 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 D8C7DC31E5B for ; Mon, 17 Jun 2019 20:40:31 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.kernel.org (Postfix) with ESMTP id 9876020644 for ; Mon, 17 Jun 2019 20:40:31 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=netronome-com.20150623.gappssmtp.com header.i=@netronome-com.20150623.gappssmtp.com header.b="i8dDfSO2" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726808AbfFQUkb (ORCPT ); Mon, 17 Jun 2019 16:40:31 -0400 Received: from mail-wr1-f66.google.com ([209.85.221.66]:46450 "EHLO mail-wr1-f66.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726614AbfFQUkb (ORCPT ); Mon, 17 Jun 2019 16:40:31 -0400 Received: by mail-wr1-f66.google.com with SMTP id n4so11429558wrw.13 for ; Mon, 17 Jun 2019 13:40:28 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=netronome-com.20150623.gappssmtp.com; s=20150623; h=references:user-agent:from:to:cc:subject:in-reply-to:date :message-id:mime-version:content-transfer-encoding; bh=qJNOR205RRS/cpQqB2DVQekqXUcpwR647q7Hv5JeF88=; b=i8dDfSO2Hnnu+gqFq0hXcLDe18Y5Nubwhadkdf1GaxExf/C2tJ3FxbakJxKML/0PAa DKTpEKblqal3HJS7ctu3jyet5OJOPAzhAcVfvrCEW9uRPHZacQeZG4AbAes9WyKYGrG7 wD+Arw4TrcCWV4D8YTy+qE7xBHen0FeuB6pCsJyTDF2IZFkuwnx7WOHRzalbxFsLjtwW uUNZgPA06adawv33GMIkUYmRZw2RpO4unUzy8GuhllUH5+36nRqy3pfZc1ukqKVwtLmY IuntzFidOGy7bCJ2N0QoMMALFJ8Odt+B+c34PVHJpbBRJgrc2xI6tW0OT/X9OCSljoOW IISQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:references:user-agent:from:to:cc:subject :in-reply-to:date:message-id:mime-version:content-transfer-encoding; bh=qJNOR205RRS/cpQqB2DVQekqXUcpwR647q7Hv5JeF88=; b=dOeULSu7wK8c5e5oNk6Oud/lRJ+dweotGHhmAP8oc3qV/TGiPgQPLIH4pkxLFliwhf m+X1o+8rfQAM4U85P258GMM1DLOal61FBz6uin/00dkGaCREnTcwOgmLIEm3WdZ9PujP 43hkyG2jF0kfy0pAFNPa7HiOJ7IehPzrPqkskWi0OPD1G5abrrAFI2D1+Gqzw014v9xP mf7OsY+x9h8eqqxMP4xMPsKN43Vzoh0A3plgcfLIA8dwN6ss9z+yxB3nwgoC0wfnBC59 npoBSt1zT0GA6Nlf7fFi2F7+pXwz7VSGpAcX5B03Kvujc/lvcKh8J8s0ZmxbZ/8pc+Gs p3/Q== X-Gm-Message-State: APjAAAUGTwmQnN61yKPIU1MDvV0G1GXP/nLMmAk8o8sJ36/ePmLu1PtT FhINjTtaH8ldKU64cuFcJat87nP9y2M= X-Google-Smtp-Source: APXvYqxdUeO14TqWL8bysVaLeeQM9hs9Dikoq2vDyhK9XBADrMx55LbEtXUzyRCMip9Dp1UuASK2xg== X-Received: by 2002:adf:fb81:: with SMTP id a1mr5748605wrr.329.1560804028234; Mon, 17 Jun 2019 13:40:28 -0700 (PDT) Received: from LAPTOP-V3S7NLPL (cpc1-cmbg19-2-0-cust104.5-4.cable.virginm.net. [82.27.180.105]) by smtp.gmail.com with ESMTPSA id f1sm244407wml.28.2019.06.17.13.40.27 (version=TLS1_2 cipher=ECDHE-RSA-CHACHA20-POLY1305 bits=256/256); Mon, 17 Jun 2019 13:40:27 -0700 (PDT) References: <20190612113208.21865-1-naveen.n.rao@linux.vnet.ibm.com> <87sgse26av.fsf@netronome.com> <87r27y25c3.fsf@netronome.com> <87ef3w5hew.fsf@netronome.com> <41dfe080-be03-3344-d279-e638a5a6168d@solarflare.com> <878su0geyt.fsf@netronome.com> <58d86352-4989-38d6-666b-5e932df9ed46@solarflare.com> User-agent: mu4e 0.9.18; emacs 25.2.2 From: Jiong Wang To: Edward Cree , Alexei Starovoitov , Andrii Nakryiko Cc: Jiong Wang , Alexei Starovoitov , "Naveen N. Rao" , Daniel Borkmann , bpf , Network Development , Michael Ellerman , Jakub Kicinski Subject: Re: [PATCH] bpf: optimize constant blinding In-reply-to: <58d86352-4989-38d6-666b-5e932df9ed46@solarflare.com> Date: Mon, 17 Jun 2019 21:40:26 +0100 Message-ID: <877e9kgd39.fsf@netronome.com> MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit Sender: bpf-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: bpf@vger.kernel.org Edward Cree writes: > On 17/06/2019 20:59, Jiong Wang wrote: >> Edward Cree writes: >> >>> On 14/06/2019 16:13, Jiong Wang wrote: >>>> Just an update and keep people posted. >>>> >>>> Working on linked list based approach, the implementation looks like the >>>> following, mostly a combine of discussions happened and Naveen's patch, >>>> please feel free to comment. >>>> >>>> - Use the reserved opcode 0xf0 with BPF_ALU as new pseudo insn code >>>> BPF_LIST_INSN. (0xf0 is also used with BPF_JMP class for tail call). >>>> >>>> - Introduce patch pool into bpf_prog->aux to keep all patched insns. >>> It's not clear to me what the point of the patch pool is, rather than just >>>  doing the patch straight away.  >> I used pool because I was thinking insn to be patched could be high >> percentage, so doing lots of alloc call is going to be less efficient? so >> allocate a big pool, and each time when creating new patch node, allocate >> it from the pool directly. Node is addressed using pool_base + offset, each >> node only need to keep offset. > Good idea; but in that case it doesn't need to be a pool of patches (storing >  their prev and next), just a pool of insns.  I.e. struct bpf_insn pool[many]; >  then in orig prog when patching an insn replace it with BPF_LIST_INSN.  If >  we later decide to patch an insn within a patch, we can replace it (i.e. the >  entry in bpf_insn_pool) with another BPF_LIST_INSN pointing to some later bit >  of the pool, then we just have a little bit of recursion at linearise time. > Does that work? I feel it is not going to work well. What I have proposed initially is something similar, except when we are patching an insn within a patch (do exist, for example zext insertion will apply to some patched alu insn inserted in ctx convert pass), then we split the patch, this then makes the data structures used in two shapes, 1. original prog->insnsi is still maintained as array. 2. if one insn is BPF_LIST_INSN, then it is a list, and could traverse it using pool_base + insn.imm = list head. But then there is data structure inconsistent, so now when doing insn traversal we need something like: for (idx = 0; idx < insn_cnt; idx++) { if (insns[idx] is not BPF_LIST_INSN) { do_insn(...) } else if (insns[idx] is BPF_LIST_INSN) { list = pool_base + insn.imm; while (list) { insn = list_head->insn; do_insn(...) list = pool_base + list->next; } } } Code logic inside convert_ctx_accesses/fixup_bpf_call etc needs to be re-factored out into a separate function do_NNN so it could be called in above logic. Now if we don't split patch when patch an insn inside patch, instead, if we replace the patched insn using what you suggested, then the logic looks to me becomes even more complex, something like for (idx = 0; idx < insn_cnt; idx++) { if (insns[idx] is not BPF_LIST_INSN) { do_insn(...) } else if (insns[idx] is BPF_LIST_INSN) { list = pool_base + insn.imm; while (list) { insn = list_head->insn; if (insn is BF_LIST_INSN) { sub_list = ... while () do_insn() continue; } do_insn(...) list = pool_base + list->next; } } } So, I am thinking what Alexei and Andrii suggested make sense, just use single data structure (singly linked list) to represent everything, so the insn traversal etc could be simple, but I am considering it is better to still base the list on top of the pool infrastructure mentioned? I have somethingn like the following: +struct bpf_list_insn { + struct bpf_insn insn; + u32 next; +}; struct bpf_prog_aux {: + struct { + struct bpf_list_insn *pool; + u32 size; + u32 used; + }; Whenever you want to do intensive patching work you could call bpf_patch_init to setup the pool, the setup including: 1. convert the original prog->insnsi into a list of bpf_list_insn. next is index into the pool, so for those initial insnsi, they are 1, 2, 3, 4, 5, ... Then when doing patching, just allocate new slot from the pool, and link them into the list. When patching finished call bpf_patch_fini to do lineraize, could use the same algo in Navee's patch. After digest Alexei and Andrii's reply, I still don't see the need to turn branch target into list, and I am not sure whether pool based list sound good? it saves size, resize pool doesn't invalid allocated node (the offset doesn't change) but requires one extra addition to calculate the pointer. > > -Ed