From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-wm1-x332.google.com (mail-wm1-x332.google.com [IPv6:2a00:1450:4864:20::332]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by lists.bufferbloat.net (Postfix) with ESMTPS id 6FD7A3B29D for ; Sat, 17 Dec 2022 12:46:49 -0500 (EST) Received: by mail-wm1-x332.google.com with SMTP id v7so3904055wmn.0 for ; Sat, 17 Dec 2022 09:46:49 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=content-transfer-encoding:to:subject:message-id:date:from :in-reply-to:references:mime-version:from:to:cc:subject:date :message-id:reply-to; bh=8mAwTN7MFufHK+Hbn0mHYcilJCHR3yPRrKBdTCwk+Jg=; b=dKnpmxNqKhkehhPxvhhylFype+iCXm3WGywISZLyLQs8gGm5qJINLIwqS+koZMRGGD 5gHrsUpPzc6BjWsSlgjxqSazFbv8c+mHgq5LA4he3XKmZEUHi6Qyu1NHdpyg++vuVrLF iy3oOdutWVlIsM4O5jdmtpoSrX/bKfePBYZJpXyBy415xbtLsXNj5EPcVrtCH8u/dxTS 2svDbcyVk8mtRFa1jE1T8qdMyv5UR8GvNqOVpNjnZrdTwLEU2eczS6dOIuPLCKAaSrXI u4+E7ZxVxJTUvPaR+Im7STEsBddSp1Ooyr80IPg2yqOAyaa8I5tqS3bF2hJzfQC7eU9X LWGQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=content-transfer-encoding:to:subject:message-id:date:from :in-reply-to:references:mime-version:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=8mAwTN7MFufHK+Hbn0mHYcilJCHR3yPRrKBdTCwk+Jg=; b=m6LvoVqMcVPFCCXxOG+ToPlwDUE5MkCAZDVhGPICwHaWxPe/4xF0UnaHdgHdFpOIe3 FpG5UHqcG8CJAZTFJamyuuJzXduMhpEyLhzryzGV1RwmedYyMCBMZ6Z9NdHaDP9hvWQb 1PkbzYcwVO03TbM4SzuYXJzmmpxJbySfykR7q3OjbH2PmNDzhEYAGkWgQ3kmUhOCQdYR Sv1kaiFfuI3BdtWay8WuUIlwykF0Tq18A763qPlXzvariKGucTv9MZs7ho9yI+Qrelbv 3KfE4kjJ2rRCBRfyBOb86aDYI6psetqyWUMuJWV0dv59aPNgMtu28r7xh+FB7QxUkCyc kXgw== X-Gm-Message-State: AFqh2ko4Yn95KVvX3sNa0GCUaiZoucnM9fI8CBg73adoj7vOPSsNhfTR FcWIvBPLFlYt3MMgoOZJEfOk5/u/X8rkaFpy0j5CMqK5 X-Google-Smtp-Source: AMrXdXtxj/iy33y5lCEiZehsOHBjP1ZH1keCPImXIyj/90eGSHIHQjOsNupFJPeA3uU1xMTORCu6/Mnu6Z+Ed6mdrOQ= X-Received: by 2002:a05:600c:1c9b:b0:3c6:c796:1071 with SMTP id k27-20020a05600c1c9b00b003c6c7961071mr520260wms.138.1671299207796; Sat, 17 Dec 2022 09:46:47 -0800 (PST) MIME-Version: 1.0 References: <20221217082506.1570898-1-davemarchevsky@fb.com> <20221217082506.1570898-10-davemarchevsky@fb.com> In-Reply-To: <20221217082506.1570898-10-davemarchevsky@fb.com> From: Dave Taht Date: Sat, 17 Dec 2022 09:46:34 -0800 Message-ID: To: libreqos Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Subject: [LibreQoS] Fwd: [PATCH v2 bpf-next 09/13] bpf: Special verifier handling for bpf_rbtree_{remove, first} X-BeenThere: libreqos@lists.bufferbloat.net X-Mailman-Version: 2.1.20 Precedence: list List-Id: Many ISPs need the kinds of quality shaping cake can do List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sat, 17 Dec 2022 17:46:49 -0000 BPF is becoming an OS all by itself. If we were to rewrite cake to be one instance per cpu across all subscribers, we might schedule packets via the rbtree facility, or perhaps a timerwheel. ---------- Forwarded message --------- From: Dave Marchevsky Date: Sat, Dec 17, 2022 at 12:42 AM Subject: [PATCH v2 bpf-next 09/13] bpf: Special verifier handling for bpf_rbtree_{remove, first} To: Cc: Alexei Starovoitov , Daniel Borkmann , Andrii Nakryiko , Kernel Team , Kumar Kartikeya Dwivedi , Tejun Heo , Dave Marchevsky Newly-added bpf_rbtree_{remove,first} kfuncs have some special properties that require handling in the verifier: * both bpf_rbtree_remove and bpf_rbtree_first return the type containing the bpf_rb_node field, with the offset set to that field's offset, instead of a struct bpf_rb_node * * mark_reg_graph_node helper added in previous patch generalizes this logic, use it * bpf_rbtree_remove's node input is a node that's been inserted in the tree - a non-owning reference. * bpf_rbtree_remove must invalidate non-owning references in order to avoid aliasing issue. Add KF_INVALIDATE_NON_OWN flag, which indicates that the marked kfunc is a non-owning ref invalidation point, and associated verifier logic using previously-added invalidate_non_owning_refs helper. * Unlike other functions, which convert one of their input arg regs to non-owning reference, bpf_rbtree_first takes no arguments and just returns a non-owning reference (possibly null) * For now verifier logic for this is special-cased instead of adding new kfunc flag. This patch, along with the previous one, complete special verifier handling for all rbtree API functions added in this series. Signed-off-by: Dave Marchevsky --- include/linux/btf.h | 1 + kernel/bpf/helpers.c | 2 +- kernel/bpf/verifier.c | 34 ++++++++++++++++++++++++++++------ 3 files changed, 30 insertions(+), 7 deletions(-) diff --git a/include/linux/btf.h b/include/linux/btf.h index 8aee3f7f4248..3663911bb7c0 100644 --- a/include/linux/btf.h +++ b/include/linux/btf.h @@ -72,6 +72,7 @@ #define KF_DESTRUCTIVE (1 << 6) /* kfunc performs destructive actions */ #define KF_RCU (1 << 7) /* kfunc only takes rcu pointer arguments */ #define KF_RELEASE_NON_OWN (1 << 8) /* kfunc converts its referenced arg into non-owning ref */ +#define KF_INVALIDATE_NON_OWN (1 << 9) /* kfunc invalidates non-owning refs after return */ /* * Return the name of the passed struct, if exists, or halt the build if f= or diff --git a/kernel/bpf/helpers.c b/kernel/bpf/helpers.c index de4523c777b7..0e6d010e6423 100644 --- a/kernel/bpf/helpers.c +++ b/kernel/bpf/helpers.c @@ -2121,7 +2121,7 @@ BTF_ID_FLAGS(func, bpf_task_acquire, KF_ACQUIRE | KF_TRUSTED_ARGS) BTF_ID_FLAGS(func, bpf_task_acquire_not_zero, KF_ACQUIRE | KF_RCU | KF_RET_NULL) BTF_ID_FLAGS(func, bpf_task_kptr_get, KF_ACQUIRE | KF_KPTR_GET | KF_RET_NU= LL) BTF_ID_FLAGS(func, bpf_task_release, KF_RELEASE) -BTF_ID_FLAGS(func, bpf_rbtree_remove, KF_ACQUIRE) +BTF_ID_FLAGS(func, bpf_rbtree_remove, KF_ACQUIRE | KF_INVALIDATE_NON_OWN) BTF_ID_FLAGS(func, bpf_rbtree_add, KF_RELEASE | KF_RELEASE_NON_OWN) BTF_ID_FLAGS(func, bpf_rbtree_first, KF_RET_NULL) diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index 75979f78399d..b4bf3701de7f 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -8393,6 +8393,11 @@ static bool is_kfunc_release_non_own(struct bpf_kfunc_call_arg_meta *meta) return meta->kfunc_flags & KF_RELEASE_NON_OWN; } +static bool is_kfunc_invalidate_non_own(struct bpf_kfunc_call_arg_meta *me= ta) +{ + return meta->kfunc_flags & KF_INVALIDATE_NON_OWN; +} + static bool is_kfunc_trusted_args(struct bpf_kfunc_call_arg_meta *meta) { return meta->kfunc_flags & KF_TRUSTED_ARGS; @@ -9425,10 +9430,20 @@ static int check_kfunc_args(struct bpf_verifier_env *env, struct bpf_kfunc_call_ verbose(env, "arg#%d expected pointer to allocated object\n", i); return -EINVAL; } - if (!reg->ref_obj_id) { + if (meta->func_id =3D=3D special_kfunc_list[KF_bpf_rbtree_remove]) { + if (reg->ref_obj_id) { + verbose(env, "rbtree_remove node input must be non-owning ref\n"); + return -EINVAL; + } + if (in_rbtree_lock_required_cb(env)) { + verbose(env, "rbtree_remove not allowed in rbtree cb\n"); + return -EINVAL; + } + } else if (!reg->ref_obj_id) { verbose(env, "allocated object must be referenced\n"); return -EINVAL; } + ret =3D process_kf_arg_ptr_to_rbtree_node(env, reg, regno, meta); if (ret < 0) return ret; @@ -9665,11 +9680,12 @@ static int check_kfunc_call(struct bpf_verifier_env *env, struct bpf_insn *insn, meta.func_id =3D=3D special_kfunc_list[KF_bpf_list_pop_back]) { struct btf_field *field =3D meta.arg_list_head.field; - mark_reg_known_zero(env, regs, BPF_REG_0); - regs[BPF_REG_0].type =3D PTR_TO_BTF_ID | MEM_ALLOC; - regs[BPF_REG_0].btf =3D field->graph_root.b= tf; - regs[BPF_REG_0].btf_id =3D field->graph_root.value_btf_id; - regs[BPF_REG_0].off =3D field->graph_root.node_offset; + mark_reg_graph_node(regs, BPF_REG_0, &field->graph_root); + } else if (meta.func_id =3D=3D special_kfunc_list[KF_bpf_rbtree_remove] || + meta.func_id =3D=3D special_kfunc_list[KF_bpf_rbtree_first]) { + struct btf_field *field =3D meta.arg_rbtree_root.field; + + mark_reg_graph_node(regs, BPF_REG_0, &field->graph_root); } else if (meta.func_id =3D=3D special_kfunc_list[KF_bpf_cast_to_kern_ctx]) { mark_reg_known_zero(env, regs, BPF_REG_0); regs[BPF_REG_0].type =3D PTR_TO_BTF_ID | PTR_TRUSTED; @@ -9735,7 +9751,13 @@ static int check_kfunc_call(struct bpf_verifier_env *env, struct bpf_insn *insn, if (is_kfunc_ret_null(&meta)) regs[BPF_REG_0].id =3D id; regs[BPF_REG_0].ref_obj_id =3D id; + } else if (meta.func_id =3D=3D special_kfunc_list[KF_bpf_rbtree_first]) { + ref_set_non_owning_lock(env, ®s[BPF_REG_0]); } + + if (is_kfunc_invalidate_non_own(&meta)) + invalidate_non_owning_refs(env, &env->cur_state->active_lock); + if (reg_may_point_to_spin_lock(®s[BPF_REG_0]) && !regs[BPF_REG_0].id) regs[BPF_REG_0].id =3D ++env->id_gen; } /* else { add_kfunc_call() ensures it is btf_type_is_void(t) } */ -- 2.30.2 --=20 This song goes out to all the folk that thought Stadia would work: https://www.linkedin.com/posts/dtaht_the-mushroom-song-activity-69813666656= 07352320-FXtz Dave T=C3=A4ht CEO, TekLibre, LLC