From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from out-179.mta0.migadu.com (out-179.mta0.migadu.com [91.218.175.179]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id BDC0A2F9269 for ; Tue, 6 May 2025 01:59:08 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=91.218.175.179 ARC-Seal:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1746496752; cv=none; b=PYNRCq4touwyxH4qh0J9YMjxy7oDsTDjHuGc8Weyn759zZQjVp/yctAo3M8KwHE+3FGJW1uBtx+QWZBR7mAumTojHCwD1YFEc2smO5BFy5tQBz2Ng4DNUN/ljE4g6z0459LT9O8rXcbic0rnc4Q7EDcTWTvLvo3GQzvTQIZyIwA= ARC-Message-Signature:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1746496752; c=relaxed/simple; bh=eeUTgP0NwfL3qcRcHy5b3DMLeOMNME57EQ6Yo/Tcm70=; h=From:To:Cc:Subject:Date:Message-ID:MIME-Version; b=HVCKgp7bEmiMe9PPP8anCTF3ajYNjeDjyEqIgIihdaCAUkbGFUPunsTS2lP276iVTIP4h9fiRk+2uSH4MtXqZGzhffGkhVNCtTvyqo2mD2/ueXwV8pC5L773308E4D75lfB2Xx/15hlOU9I0Hf+K4qV8aehRcda3w4lKKFT6esE= ARC-Authentication-Results:i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=linux.dev; spf=pass smtp.mailfrom=linux.dev; dkim=pass (1024-bit key) header.d=linux.dev header.i=@linux.dev header.b=L09Y+8zj; arc=none smtp.client-ip=91.218.175.179 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=linux.dev Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=linux.dev Authentication-Results: smtp.subspace.kernel.org; dkim=pass (1024-bit key) header.d=linux.dev header.i=@linux.dev header.b="L09Y+8zj" X-Report-Abuse: Please report any abuse attempt to abuse@migadu.com and include these headers. DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=linux.dev; s=key1; t=1746496745; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version: content-transfer-encoding:content-transfer-encoding; bh=V0AQQ4m6E+YaRU1E5pmNn0Fa+e5mr/bxq64cWLQpUlM=; b=L09Y+8zjpJj/+TvmfFZhzEo+kyq1lqZUuNrEtpAXKtRyWd/jxfRTvu8bzKdpEPrJAvhvqu 8CkEYq0C7jttGgdNHb+Kn6H3Q/R5nXbyPqFt5epqIYCbnTm0O7hjHxq17kA7n6JcEgkqZi Wrvv6u+gL2PyGnV48ITWpWLgpxS9r1I= From: Martin KaFai Lau To: bpf@vger.kernel.org Cc: 'Alexei Starovoitov ' , 'Andrii Nakryiko ' , 'Daniel Borkmann ' , 'Kumar Kartikeya Dwivedi ' , 'Amery Hung ' , netdev@vger.kernel.org, kernel-team@meta.com Subject: [PATCH v2 bpf-next 0/8] bpf: Support bpf rbtree traversal and list peeking Date: Mon, 5 May 2025 18:58:47 -0700 Message-ID: <20250506015857.817950-1-martin.lau@linux.dev> Precedence: bulk X-Mailing-List: netdev@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Migadu-Flow: FLOW_OUT From: Martin KaFai Lau The RFC v1 [1] showed a fq qdisc implementation in bpf that is much closer to the kernel sch_fq.c. The fq example and bpf qdisc changes are separated out from this set. This set is to focus on the kfunc and verifier changes that enable the bpf rbtree traversal and list peeking. v2: - Added tests to check that the return value of the bpf_rbtree_{root,left,right} and bpf_list_{front,back} is marked as a non_own_ref node pointer. (Kumar) - Added tests to ensure that the bpf_rbtree_{root,left,right} and bpf_list_{front,back} must be called after holding the spinlock. - Squashed the selftests adjustment to the corresponding verifier changes to avoid bisect failure. (Kumar) - Separated the bpf qdisc specific changes and fq selftest example from this set. [1]: https://lore.kernel.org/bpf/20250418224652.105998-1-martin.lau@linux.dev/ Martin KaFai Lau (8): bpf: Check KF_bpf_rbtree_add_impl for the "case KF_ARG_PTR_TO_RB_NODE" bpf: Simplify reg0 marking for the rbtree kfuncs that return a bpf_rb_node pointer bpf: Add bpf_rbtree_{root,left,right} kfunc bpf: Allow refcounted bpf_rb_node used in bpf_rbtree_{remove,left,right} selftests/bpf: Add tests for bpf_rbtree_{root,left,right} bpf: Simplify reg0 marking for the list kfuncs that return a bpf_list_node pointer bpf: Add bpf_list_{front,back} kfunc selftests/bpf: Add test for bpf_list_{front,back} kernel/bpf/helpers.c | 52 +++++ kernel/bpf/verifier.c | 64 ++++-- .../selftests/bpf/prog_tests/linked_list.c | 6 + .../testing/selftests/bpf/prog_tests/rbtree.c | 6 + .../selftests/bpf/progs/linked_list_peek.c | 113 ++++++++++ .../testing/selftests/bpf/progs/rbtree_fail.c | 29 +-- .../selftests/bpf/progs/rbtree_search.c | 206 ++++++++++++++++++ 7 files changed, 445 insertions(+), 31 deletions(-) create mode 100644 tools/testing/selftests/bpf/progs/linked_list_peek.c create mode 100644 tools/testing/selftests/bpf/progs/rbtree_search.c -- 2.47.1