From patchwork Thu Dec 1 18:34: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: 13061730 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 79408C47088 for ; Thu, 1 Dec 2022 18:35:31 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S231136AbiLASf3 (ORCPT ); Thu, 1 Dec 2022 13:35:29 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:60850 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S230462AbiLASf1 (ORCPT ); Thu, 1 Dec 2022 13:35:27 -0500 Received: from mx0a-00082601.pphosted.com (mx0a-00082601.pphosted.com [67.231.145.42]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id D67D0B90C9 for ; Thu, 1 Dec 2022 10:35:20 -0800 (PST) Received: from pps.filterd (m0109334.ppops.net [127.0.0.1]) by mx0a-00082601.pphosted.com (8.17.1.19/8.17.1.19) with ESMTP id 2B1IZCxJ017474 for ; Thu, 1 Dec 2022 10:35: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=FyxDG0tELAO3dBVdkMyGpq01rNquhcb1h6PzCWb1nlg=; b=ZbGLXO38J8H7IBdvNp/3ty8yqb2uR3ctgohrG7dfXbJVn6jpTXqVDzWFXSo1JPsbjUWo osChEoKYYVBuarZJvToDPlW8oODLQKffxDjNHGKw5HHZ7AeRp73m3EkHJg5OB0BEmYWP I3MEaW/nPaXaO9a/Ccu0E8BlRuRU2sieKeQ= Received: from maileast.thefacebook.com ([163.114.130.16]) by mx0a-00082601.pphosted.com (PPS) with ESMTPS id 3m65bcxvhj-5 (version=TLSv1.2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128 verify=NOT) for ; Thu, 01 Dec 2022 10:35:20 -0800 Received: from twshared24004.14.frc2.facebook.com (2620:10d:c0a8:1b::d) by mail.thefacebook.com (2620:10d:c0a8:83::4) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256) id 15.1.2375.31; Thu, 1 Dec 2022 10:34:16 -0800 Received: by devbig077.ldc1.facebook.com (Postfix, from userid 158236) id 6AEE411BCBE15; Thu, 1 Dec 2022 10:34:08 -0800 (PST) From: Dave Marchevsky To: CC: Alexei Starovoitov , Daniel Borkmann , Andrii Nakryiko , Kernel Team , Yonghong Song , Dave Marchevsky , Yonghong Song , Kumar Kartikeya Dwivedi Subject: [PATCH v2 bpf-next 1/2] bpf: Fix release_on_unlock release logic for multiple refs Date: Thu, 1 Dec 2022 10:34:05 -0800 Message-ID: <20221201183406.1203621-1-davemarchevsky@fb.com> X-Mailer: git-send-email 2.30.2 MIME-Version: 1.0 X-FB-Internal: Safe X-Proofpoint-GUID: 07DMRD22qE8BonQiAMRyauXNlB3vEiQM X-Proofpoint-ORIG-GUID: 07DMRD22qE8BonQiAMRyauXNlB3vEiQM X-Proofpoint-Virus-Version: vendor=baseguard engine=ICAP:2.0.219,Aquarius:18.0.923,Hydra:6.0.545,FMLib:17.11.122.1 definitions=2022-12-01_12,2022-12-01_01,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 replaced with ref 7, which is _not_ release_on_unlock, and loop from the back, we'd see: state->refs = [2 4 7] (start of idx=2) state->refs = [2 4 7] (start of idx=1) state->refs = [2 7] (start of idx=0, refs 7 and 4 swapped) state->refs = [7] (after idx=0, 7 and 2 swapped, loop terminates) Signed-off-by: Dave Marchevsky Acked-by: Yonghong Song cc: Kumar Kartikeya Dwivedi Fixes: 534e86bc6c66 ("bpf: Add 'release on unlock' logic for bpf_list_push_{front,back}") --- v1 -> v2 lore.kernel.org/bpf/b5d46fd5-2693-cd46-9515-700fef1a110b@meta.com: * Update second example in patch summary to use a new ref_id for the non-release_on_unlock ref. (Yonghong) * Add Yonghong's ack 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 d0ecc0b18b20..b0db9c10567b 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -5738,7 +5738,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