From patchwork Mon Nov 29 22:37:21 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Joanne Koong X-Patchwork-Id: 12645979 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 32C0BC433EF for ; Mon, 29 Nov 2021 22:40:03 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S234804AbhK2WnT (ORCPT ); Mon, 29 Nov 2021 17:43:19 -0500 Received: from mx0b-00082601.pphosted.com ([67.231.153.30]:39558 "EHLO mx0a-00082601.pphosted.com" rhost-flags-OK-OK-OK-FAIL) by vger.kernel.org with ESMTP id S234484AbhK2Wmm (ORCPT ); Mon, 29 Nov 2021 17:42:42 -0500 Received: from pps.filterd (m0089730.ppops.net [127.0.0.1]) by m0089730.ppops.net (8.16.1.2/8.16.1.2) with SMTP id 1ATIlB4x032204 for ; Mon, 29 Nov 2021 14:39: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-type : content-transfer-encoding; s=facebook; bh=pr0VB0oy4MQhVPuDiKPO7NJLtAuY/ihjJS5dz6mCwXc=; b=oRitHy8gAaXWIm6HmjMrAWog2RyGE9eiYnqo4mu9TqzZz72R9tdlZAtmRd4LtiU9WjWx bt5hYo1WbyOuEy3ULp6a+kNj/YJ42uc03HhHt5qOWnbOKdI9jmbcbgTHNvUxb/ufFVYb KVIY1jOvuk3dUy0vLRaKn29qbyiTl9uTni0= Received: from maileast.thefacebook.com ([163.114.130.16]) by m0089730.ppops.net with ESMTP id 3cmna6778n-3 (version=TLSv1.2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128 verify=NOT) for ; Mon, 29 Nov 2021 14:39:20 -0800 Received: from intmgw001.25.frc3.facebook.com (2620:10d:c0a8:1b::d) by mail.thefacebook.com (2620:10d:c0a8:83::6) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256) id 15.1.2308.20; Mon, 29 Nov 2021 14:39:07 -0800 Received: by devbig612.frc2.facebook.com (Postfix, from userid 115148) id 236B9570A522; Mon, 29 Nov 2021 14:39:00 -0800 (PST) From: Joanne Koong To: CC: , , , , Joanne Koong Subject: [PATCH v3 bpf-next 0/4] Add bpf_loop helper Date: Mon, 29 Nov 2021 14:37:21 -0800 Message-ID: <20211129223725.2770730-1-joannekoong@fb.com> X-Mailer: git-send-email 2.30.2 MIME-Version: 1.0 X-FB-Internal: Safe X-FB-Source: Intern X-Proofpoint-GUID: GxmJIiu1Ma5Zuz7e2cUdVVxF8ynmfTzc X-Proofpoint-ORIG-GUID: GxmJIiu1Ma5Zuz7e2cUdVVxF8ynmfTzc X-Proofpoint-Virus-Version: vendor=baseguard engine=ICAP:2.0.205,Aquarius:18.0.790,Hydra:6.0.425,FMLib:17.0.607.475 definitions=2021-11-29_11,2021-11-28_01,2020-04-07_01 X-Proofpoint-Spam-Details: rule=fb_default_notspam policy=fb_default score=0 adultscore=0 impostorscore=0 suspectscore=0 lowpriorityscore=0 mlxlogscore=645 spamscore=0 bulkscore=0 malwarescore=0 clxscore=1015 phishscore=0 mlxscore=0 priorityscore=1501 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2110150000 definitions=main-2111290107 X-FB-Internal: deliver Precedence: bulk List-ID: X-Mailing-List: bpf@vger.kernel.org X-Patchwork-Delegate: bpf@iogearbox.net This patchset add a new helper, bpf_loop. One of the complexities of using for loops in bpf programs is that the verifier needs to ensure that in every possibility of the loop logic, the loop will always terminate. As such, there is a limit on how many iterations the loop can do. The bpf_loop helper moves the loop logic into the kernel and can thereby guarantee that the loop will always terminate. The bpf_loop helper simplifies a lot of the complexity the verifier needs to check, as well as removes the constraint on the number of loops able to be run. From the test results, we see that using bpf_loop in place of the traditional for loop led to a decrease in verification time and number of bpf instructions by ~99%. The benchmark results show that as the number of iterations increases, the overhead per iteration decreases. The high-level overview of the patches - Patch 1 - kernel-side + API changes for adding bpf_loop Patch 2 - tests Patch 3 - use bpf_loop in strobemeta + pyperf600 and measure verifier performance Patch 4 - benchmark for throughput + latency of bpf_loop call v2 -> v3: ~ Rerun benchmarks on physical machine, update results ~ Propagate original error codes in the verifier v1 -> v2: ~ Change helper name to bpf_loop (instead of bpf_for_each) ~ Set max nr_loops (~8 million loops) for bpf_loop call ~ Split tests + strobemeta/pyperf600 changes into two patches ~ Add new ops_report_final helper for outputting throughput and latency Joanne Koong (4): bpf: Add bpf_loop helper selftests/bpf: Add bpf_loop test selftests/bpf: measure bpf_loop verifier performance selftest/bpf/benchs: add bpf_loop benchmark include/linux/bpf.h | 1 + include/uapi/linux/bpf.h | 25 ++++ kernel/bpf/bpf_iter.c | 35 +++++ kernel/bpf/helpers.c | 2 + kernel/bpf/verifier.c | 88 ++++++----- tools/include/uapi/linux/bpf.h | 25 ++++ tools/testing/selftests/bpf/Makefile | 4 +- tools/testing/selftests/bpf/bench.c | 37 +++++ tools/testing/selftests/bpf/bench.h | 2 + .../selftests/bpf/benchs/bench_bpf_loop.c | 105 +++++++++++++ .../bpf/benchs/run_bench_bpf_loop.sh | 15 ++ .../selftests/bpf/benchs/run_common.sh | 15 ++ .../selftests/bpf/prog_tests/bpf_loop.c | 138 ++++++++++++++++++ .../bpf/prog_tests/bpf_verif_scale.c | 12 ++ tools/testing/selftests/bpf/progs/bpf_loop.c | 99 +++++++++++++ .../selftests/bpf/progs/bpf_loop_bench.c | 26 ++++ tools/testing/selftests/bpf/progs/pyperf.h | 71 ++++++++- .../selftests/bpf/progs/pyperf600_bpf_loop.c | 6 + .../testing/selftests/bpf/progs/strobemeta.h | 75 +++++++++- .../selftests/bpf/progs/strobemeta_bpf_loop.c | 9 ++ 20 files changed, 751 insertions(+), 39 deletions(-) create mode 100644 tools/testing/selftests/bpf/benchs/bench_bpf_loop.c create mode 100755 tools/testing/selftests/bpf/benchs/run_bench_bpf_loop.sh create mode 100644 tools/testing/selftests/bpf/prog_tests/bpf_loop.c create mode 100644 tools/testing/selftests/bpf/progs/bpf_loop.c create mode 100644 tools/testing/selftests/bpf/progs/bpf_loop_bench.c create mode 100644 tools/testing/selftests/bpf/progs/pyperf600_bpf_loop.c create mode 100644 tools/testing/selftests/bpf/progs/strobemeta_bpf_loop.c