From patchwork Wed Nov 30 19:25:04 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Dave Marchevsky X-Patchwork-Id: 13060310 X-Patchwork-Delegate: bpf@iogearbox.net Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id CDC6BC4321E for ; Wed, 30 Nov 2022 19:26:03 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S229520AbiK3TZ3 (ORCPT ); Wed, 30 Nov 2022 14:25:29 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:40198 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S229497AbiK3TZW (ORCPT ); Wed, 30 Nov 2022 14:25:22 -0500 Received: from mx0a-00082601.pphosted.com (mx0b-00082601.pphosted.com [67.231.153.30]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 3EC5D862C3 for ; Wed, 30 Nov 2022 11:25:21 -0800 (PST) Received: from pps.filterd (m0089730.ppops.net [127.0.0.1]) by m0089730.ppops.net (8.17.1.19/8.17.1.19) with ESMTP id 2AUG0s3h004606 for ; Wed, 30 Nov 2022 11:25:20 -0800 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=fb.com; h=from : to : cc : subject : date : message-id : mime-version : content-transfer-encoding : content-type; s=facebook; bh=fGHjDTwCXQs5a505HsJR5Kmp5sLU5IYj8Jwwjl960sE=; b=p77dHYUcQhET9FcvUqgEBBJcH4g0+3lCfeeGzc0RtDgJVYv/cO8onTivNYc1Lqpr+ufC 7ZCZycTDyW5TYCRKEWyATwS4snz9Bq9J8w/V8qd5dhnaCczL7Hdd4c6mrV/mSLri/fPu AL8sXda11tLq7U2fyvgalkZQ5zUmH1NpP34= Received: from mail.thefacebook.com ([163.114.132.120]) by m0089730.ppops.net (PPS) with ESMTPS id 3m5v7595wu-2 (version=TLSv1.2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128 verify=NOT) for ; Wed, 30 Nov 2022 11:25:20 -0800 Received: from twshared8047.05.ash9.facebook.com (2620:10d:c085:108::8) by mail.thefacebook.com (2620:10d:c085:11d::6) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256) id 15.1.2375.31; Wed, 30 Nov 2022 11:25:18 -0800 Received: by devbig077.ldc1.facebook.com (Postfix, from userid 158236) id A5DD211AE2CD1; Wed, 30 Nov 2022 11:25:08 -0800 (PST) From: Dave Marchevsky To: CC: Alexei Starovoitov , Daniel Borkmann , Andrii Nakryiko , Kernel Team , Dave Marchevsky , Kumar Kartikeya Dwivedi Subject: [PATCH bpf-next 1/2] bpf: Fix release_on_unlock release logic for multiple refs Date: Wed, 30 Nov 2022 11:25:04 -0800 Message-ID: <20221130192505.914566-1-davemarchevsky@fb.com> X-Mailer: git-send-email 2.30.2 MIME-Version: 1.0 X-FB-Internal: Safe X-Proofpoint-ORIG-GUID: 8Iyh87MekAo4IkqKBEStDqufhhDwNtHJ X-Proofpoint-GUID: 8Iyh87MekAo4IkqKBEStDqufhhDwNtHJ X-Proofpoint-Virus-Version: vendor=baseguard engine=ICAP:2.0.219,Aquarius:18.0.895,Hydra:6.0.545,FMLib:17.11.122.1 definitions=2022-11-30_04,2022-11-30_02,2022-06-22_01 Precedence: bulk List-ID: X-Mailing-List: bpf@vger.kernel.org X-Patchwork-Delegate: bpf@iogearbox.net Consider a verifier state with three acquired references, all with release_on_unlock = true: idx 0 1 2 state->refs = [2 4 6] (with 2, 4, and 6 being the ref ids). When bpf_spin_unlock is called, process_spin_lock will loop through all acquired_refs and, for each ref, if it's release_on_unlock, calls release_reference on it. That function in turn calls release_reference_state, which removes the reference from state->refs by swapping the reference state with the last reference state in refs array and decrements acquired_refs count. process_spin_lock's loop logic, which is essentially: for (i = 0; i < state->acquired_refs; i++) { if (!state->refs[i].release_on_unlock) continue; release_reference(state->refs[i].id); } will fail to release release_on_unlock references which are swapped from the end. Running this logic on our example demonstrates: state->refs = [2 4 6] (start of idx=0 iter) release state->refs[0] by swapping w/ state->refs[2] state->refs = [6 4] (start of idx=1) release state->refs[1], no need to swap as it's the last idx state->refs = [6] (start of idx=2, loop terminates) ref_id 6 should have been removed but was skipped. Fix this by looping from back-to-front, which results in refs that are candidates for removal being swapped with refs which have already been examined and kept. If we modify our initial example such that ref 6 is not release_on_unlock and loop from the back, we'd see: state->refs = [2 4 6] (start of idx=2) state->refs = [2 4 6] (start of idx=1) state->refs = [2 6] (start of idx=0) state->refs = [6] (after idx=0, loop terminates) Signed-off-by: Dave Marchevsky cc: Kumar Kartikeya Dwivedi Fixes: 534e86bc6c66 ("bpf: Add 'release on unlock' logic for bpf_list_push_{front,back}") Acked-by: Yonghong Song --- I noticed this while testing ng_ds version of rbtree. Submitting separately so that this fix can be applied before the rest of rbtree work, as the latter will likely need a few respins. An alternative to this fix would be to modify or add new helper functions which enable safe release_reference in a loop. The additional complexity of this alternative seems unnecessary to me for now as this is currently the only place in verifier where release_reference in a loop is used. kernel/bpf/verifier.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index 4e7f1d085e53..ac3e1219a7a5 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -5726,7 +5726,7 @@ static int process_spin_lock(struct bpf_verifier_env *env, int regno, cur->active_lock.ptr = NULL; cur->active_lock.id = 0; - for (i = 0; i < fstate->acquired_refs; i++) { + for (i = fstate->acquired_refs - 1; i >= 0; i--) { int err; /* Complain on error because this reference state cannot From patchwork Wed Nov 30 19:25:05 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Dave Marchevsky X-Patchwork-Id: 13060309 X-Patchwork-Delegate: bpf@iogearbox.net Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id DFB1DC47089 for ; Wed, 30 Nov 2022 19:26:03 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S229507AbiK3TZ2 (ORCPT ); Wed, 30 Nov 2022 14:25:28 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:40184 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S229630AbiK3TZS (ORCPT ); Wed, 30 Nov 2022 14:25:18 -0500 Received: from mx0a-00082601.pphosted.com (mx0a-00082601.pphosted.com [67.231.145.42]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 55151862C4 for ; Wed, 30 Nov 2022 11:25:17 -0800 (PST) Received: from pps.filterd (m0148461.ppops.net [127.0.0.1]) by mx0a-00082601.pphosted.com (8.17.1.19/8.17.1.19) with ESMTP id 2AUD0HKr002620 for ; Wed, 30 Nov 2022 11:25:16 -0800 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=fb.com; h=from : to : cc : subject : date : message-id : in-reply-to : references : mime-version : content-transfer-encoding : content-type; s=facebook; bh=c21/RxjJ+X/zCJbYrlHYzEi17+2XCtf38q7aL5Vgz00=; b=k34LSJcUZk0M0fcxjXabVyKNw0LvXCsR9gzUbs8MIWKgBPqPMAbBehpiB2HnmbhX9mEf zjk8t3KxRaF+PDiyY1iXQUrk2J4hkvyNW0bqFKq7m0liHnnlzI29dOIRcwtbpqNmT/z3 y0eDUEL4h39lisgHAOzFhfHgeYDpQ7PhUD0= Received: from mail.thefacebook.com ([163.114.132.120]) by mx0a-00082601.pphosted.com (PPS) with ESMTPS id 3m67nvkfxt-2 (version=TLSv1.2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128 verify=NOT) for ; Wed, 30 Nov 2022 11:25:16 -0800 Received: from twshared13940.35.frc1.facebook.com (2620:10d:c085:108::4) by mail.thefacebook.com (2620:10d:c085:11d::4) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256) id 15.1.2375.31; Wed, 30 Nov 2022 11:25:15 -0800 Received: by devbig077.ldc1.facebook.com (Postfix, from userid 158236) id F3D4411AE2D56; Wed, 30 Nov 2022 11:25:12 -0800 (PST) From: Dave Marchevsky To: CC: Alexei Starovoitov , Daniel Borkmann , Andrii Nakryiko , Kernel Team , Dave Marchevsky , Kumar Kartikeya Dwivedi Subject: [PATCH bpf-next 2/2] selftests/bpf: Validate multiple ref release_on_unlock logic Date: Wed, 30 Nov 2022 11:25:05 -0800 Message-ID: <20221130192505.914566-2-davemarchevsky@fb.com> X-Mailer: git-send-email 2.30.2 In-Reply-To: <20221130192505.914566-1-davemarchevsky@fb.com> References: <20221130192505.914566-1-davemarchevsky@fb.com> MIME-Version: 1.0 X-FB-Internal: Safe X-Proofpoint-ORIG-GUID: W5MQFiYN1Pf9692Z88VZ26c6GcSKrRHW X-Proofpoint-GUID: W5MQFiYN1Pf9692Z88VZ26c6GcSKrRHW X-Proofpoint-Virus-Version: vendor=baseguard engine=ICAP:2.0.219,Aquarius:18.0.895,Hydra:6.0.545,FMLib:17.11.122.1 definitions=2022-11-30_04,2022-11-30_02,2022-06-22_01 Precedence: bulk List-ID: X-Mailing-List: bpf@vger.kernel.org X-Patchwork-Delegate: bpf@iogearbox.net Modify list_push_pop_multiple to alloc and insert nodes 2-at-a-time. Without the previous patch's fix, this block of code: bpf_spin_lock(lock); bpf_list_push_front(head, &f[i]->node); bpf_list_push_front(head, &f[i + 1]->node); bpf_spin_unlock(lock); would fail check_reference_leak check as release_on_unlock logic would miss a ref that should've been released. Signed-off-by: Dave Marchevsky cc: Kumar Kartikeya Dwivedi --- tools/testing/selftests/bpf/progs/linked_list.c | 17 ++++++++++++++++- 1 file changed, 16 insertions(+), 1 deletion(-) diff --git a/tools/testing/selftests/bpf/progs/linked_list.c b/tools/testing/selftests/bpf/progs/linked_list.c index 2c7b615c6d41..4ad88da5cda2 100644 --- a/tools/testing/selftests/bpf/progs/linked_list.c +++ b/tools/testing/selftests/bpf/progs/linked_list.c @@ -99,13 +99,28 @@ int list_push_pop_multiple(struct bpf_spin_lock *lock, struct bpf_list_head *hea struct foo *f[8], *pf; int i; - for (i = 0; i < ARRAY_SIZE(f); i++) { + /* Loop following this check adds nodes 2-at-a-time in order to + * validate multiple release_on_unlock release logic + */ + if (ARRAY_SIZE(f) % 2) + return 10; + + for (i = 0; i < ARRAY_SIZE(f); i += 2) { f[i] = bpf_obj_new(typeof(**f)); if (!f[i]) return 2; f[i]->data = i; + + f[i + 1] = bpf_obj_new(typeof(**f)); + if (!f[i + 1]) { + bpf_obj_drop(f[i]); + return 9; + } + f[i + 1]->data = i + 1; + bpf_spin_lock(lock); bpf_list_push_front(head, &f[i]->node); + bpf_list_push_front(head, &f[i + 1]->node); bpf_spin_unlock(lock); }