From patchwork Wed Jul 5 14:47:29 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Kumar Kartikeya Dwivedi X-Patchwork-Id: 13302284 X-Patchwork-Delegate: bpf@iogearbox.net Received: from lindbergh.monkeyblade.net (lindbergh.monkeyblade.net [23.128.96.19]) (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 856173233 for ; Wed, 5 Jul 2023 14:47:45 +0000 (UTC) Received: from mail-pl1-x644.google.com (mail-pl1-x644.google.com [IPv6:2607:f8b0:4864:20::644]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 3F0AD131 for ; Wed, 5 Jul 2023 07:47:44 -0700 (PDT) Received: by mail-pl1-x644.google.com with SMTP id d9443c01a7336-1b8a462e0b0so10273605ad.3 for ; Wed, 05 Jul 2023 07:47:44 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20221208; t=1688568463; x=1691160463; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=DLgXET5GN50Vn8yz0ucBvMMOL5Vw+DEQS5xWCgueJ3o=; b=O6D+34fCUUEpbd5WTwJTRH5y5N1MeiWOZcziAh0K118RL8RZeYWyLkn714yx6z2p4R QXchQdh1btJxCeCqTmKPiim+DbQc0KW85vBCvyrXjbLu0orAyd3gonYQ5V2lDLETgm5q icGSbf03cIixjtfMU+KbvVW49CZ05DFAzt80EuV9jIQ4eoVzqAh9F59OF7pArytBm5VR OLL4kmf5GizplQaYx7QMu/cBOsEWHgU3axwg+d3746jjlsMpTDLHCNxVQFEO2vyvyVxL OkfbzLxUJZ0Pfn9weouiAzFsXZ3RMkj2q1IUZKsj7H1IOCXvtXljTLeZ96BclOc8UIwC 1yTQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1688568463; x=1691160463; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=DLgXET5GN50Vn8yz0ucBvMMOL5Vw+DEQS5xWCgueJ3o=; b=kKcMhVsI7lfl5p8nniHc+VJ2k0fUmwZGWZKstmP1mhIqUK1QrND4PNpOR5K+QhQSb7 q64u8Tu3pKGDiSds7RrXkG39YU9igyJLSBYKX2g9rcisfBoHkJyn/U5a7arYm7E01elb bQ+rO3d0Ed64v2Ry+UA28hWR+KDHqVi42qsy57kM1yAFuvExX1Q4itTLaFKlpMp7EeVA c8m15dVM2b9LEwuEZSJJICIjEftYRfm0uD+k8roAJ9FAGh1PgmzVTJXTIu8OoZeHaVOf Ix/0gzN/tnaNIo2/7lCyn+NL/P1lpCb0WTxFoM7VCMZS1hNnvCSZJI1xh+Fn41Zl3zOe FmWA== X-Gm-Message-State: ABy/qLYscdoZy2QBmS++DfiL+nXlscMLjUH+sGqaxy36tv3mGfbjq7PH aHSgr/laeRPb/fHl+JwZQPDIRjRdRyRPt6o+ X-Google-Smtp-Source: APBJJlHB/IpmTMAvQIEnUlL9KXxlrOns5qWNkSsWJ9mSxOGwz2HUQ+6POwXSJDE3xArM+881RtbU1A== X-Received: by 2002:a17:902:e845:b0:1b0:6c10:6836 with SMTP id t5-20020a170902e84500b001b06c106836mr14974051plg.33.1688568463141; Wed, 05 Jul 2023 07:47:43 -0700 (PDT) Received: from localhost ([49.36.209.255]) by smtp.gmail.com with ESMTPSA id t4-20020a170902b20400b001b85a56597bsm10917157plr.185.2023.07.05.07.47.42 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 05 Jul 2023 07:47:42 -0700 (PDT) From: Kumar Kartikeya Dwivedi To: bpf@vger.kernel.org Cc: Alexei Starovoitov , Daniel Borkmann , Andrii Nakryiko , Martin KaFai Lau Subject: [PATCH bpf v1 1/2] bpf: Fix max stack depth check for async callbacks Date: Wed, 5 Jul 2023 20:17:29 +0530 Message-Id: <20230705144730.235802-2-memxor@gmail.com> X-Mailer: git-send-email 2.40.1 In-Reply-To: <20230705144730.235802-1-memxor@gmail.com> References: <20230705144730.235802-1-memxor@gmail.com> Precedence: bulk X-Mailing-List: bpf@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 X-Developer-Signature: v=1; a=openpgp-sha256; l=2030; i=memxor@gmail.com; h=from:subject; bh=Ee8gRv5X/5pH0jZN2VrHE0zNKVstwLXYEYOysRbKFeQ=; b=owEBbQKS/ZANAwAKAUzgyIZIvxHKAcsmYgBkpYFoSuD39iaY8V4MoFBptFmwR0ePYb3yLmyE4 cQHjJlRaxaJAjMEAAEKAB0WIQRLvip+Buz51YI8YRFM4MiGSL8RygUCZKWBaAAKCRBM4MiGSL8R yoXsEACUvOML7cGLEMdjLqUtAvHEqkrfzcW9nF8VOO8apjI6n/fXss9910ApsA5FIpXhIhu1P2g afZ84jt6rb3SQ/EnWPuhe5zqwn+cfwzNrXaHqJ/nRdpkQEQEhqxCByJLQ5fOu6v3ttlVCBhcrSn 2G4ZrgNJdY/HCxp9cIFy1aG098OlTZ9a0tipENIcI6FSAPf8HbtXDmEkWyOwd/6FhaxYyy9Y10O 3X0q0W+HQv5tgccJFKd7qERuJfHfsMA8hSRvcyJWcxBbt4n6/PVubvmQBwiRJriQ2hcA++nrr3X b2etSU4NAl77Vv25qI1yC6GUInmXTerYcmEnbym1aoCP1hZZpAUeJrdH7Pl8z4kU8f9qM4fmn+n Ci4S68vUZyQIjB0lsxdO0WfTPI6qvTFeADfqMSRmRKMgAPO0uHgaws/zMkv8f9XhGusfADw3dYr v8ghgDqqAK6pfNd3HOUy1j96zVTgvuAT9Fy/+Z3XkFOpK5mALGWMxlffoPlY+adoPNpp0U2g7fF UvnNmV90T/PZHsnmWUbKiCUNF/P6qsYaSRduX29fNaJMNoVNdVEuQq1NgYrLhyMWuT2jWOTlwPk ++Bkw2EJ5V71qkiR7uVlKlu1XyFFq6RnzM8sQWepBCV0ChJAqAJ81rFGzEtbVyVxykGefO5v8Ua Qn8rdfqNA5XSWXg== X-Developer-Key: i=memxor@gmail.com; a=openpgp; fpr=4BBE2A7E06ECF9D5823C61114CE0C88648BF11CA X-Spam-Status: No, score=-2.1 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,FREEMAIL_FROM, RCVD_IN_DNSWL_NONE,SPF_HELO_NONE,SPF_PASS,T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on lindbergh.monkeyblade.net X-Patchwork-Delegate: bpf@iogearbox.net The check_max_stack_depth pass happens after the verifier's symbolic execution, and attempts to walk the call graph of the BPF program, ensuring that the stack usage stays within bounds for all possible call chains. There are two cases to consider: bpf_pseudo_func and bpf_pseudo_call. In the former case, the callback pointer is loaded into a register, and is assumed that it is passed to some helper later which calls it (however there is no way to be sure), but the check remains conservative and accounts the stack usage anyway. For this particular case, asynchronous callbacks are skipped as they execute asynchronously when their corresponding event fires. The case of bpf_pseudo_call is simpler and we know that the call is definitely made, hence the stack depth of the subprog is accounted for. However, the current check still skips an asynchronous callback even if a bpf_pseudo_call was made for it. This is erroneous, as it will miss accounting for the stack usage of the asynchronous callback, which can be used to breach the maximum stack depth limit. Fix this by only skipping asynchronous callbacks when the instruction is not a pseudo call to the subprog. Fixes: 7ddc80a476c2 ("bpf: Teach stack depth check about async callbacks.") Signed-off-by: Kumar Kartikeya Dwivedi --- kernel/bpf/verifier.c | 5 +++-- 1 file changed, 3 insertions(+), 2 deletions(-) diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index 11e54dd8b6dd..930b5555cfd3 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -5642,8 +5642,9 @@ static int check_max_stack_depth(struct bpf_verifier_env *env) verbose(env, "verifier bug. subprog has tail_call and async cb\n"); return -EFAULT; } - /* async callbacks don't increase bpf prog stack size */ - continue; + /* async callbacks don't increase bpf prog stack size unless called directly */ + if (!bpf_pseudo_call(insn + i)) + continue; } i = next_insn; From patchwork Wed Jul 5 14:47:30 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Kumar Kartikeya Dwivedi X-Patchwork-Id: 13302285 X-Patchwork-Delegate: bpf@iogearbox.net Received: from lindbergh.monkeyblade.net (lindbergh.monkeyblade.net [23.128.96.19]) (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 1F44A3233 for ; Wed, 5 Jul 2023 14:47:50 +0000 (UTC) Received: from mail-pl1-x643.google.com (mail-pl1-x643.google.com [IPv6:2607:f8b0:4864:20::643]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 4755F1B6 for ; Wed, 5 Jul 2023 07:47:48 -0700 (PDT) Received: by mail-pl1-x643.google.com with SMTP id d9443c01a7336-1b88e5b3834so16813495ad.3 for ; Wed, 05 Jul 2023 07:47:48 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20221208; t=1688568467; x=1691160467; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=M83gZd8Zadb83q5TrdCvxbKyZ8+U22NCP8QItkiTLnA=; b=dw25QlX4SUMfRhjwooWjo+V+XwVI529xo5Wg7eEdi2NkyFiB45sxIXa2HMbEDRvUIM iRD27WeUKLUTcz7rGNL9aMMfTWbqm/T73Rx3MhPg94nSESzxC9QsZZ1vnBHAr3OylWSo bfSJgURhxv9RA1Z+iYUQ6s1+A60mCX+mvofGmQG1nKtQDPzBtFTC+o7EZk/4TVQ6YoM2 NED7ZpEKP911BwfTNdcW3no3ywKu7Aok3B4GO3NPkPZXWAaJPzEEjTM+A2bmMOSxVOJV oni7Ie8jhd0OAlFgQANUetW0PO4jqOtBKIDNQk7HFKHPZ2XyTCxz2LGypCgvDEuFqc8E 6wBA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1688568467; x=1691160467; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=M83gZd8Zadb83q5TrdCvxbKyZ8+U22NCP8QItkiTLnA=; b=eW6FADJJT4OtUUSBvaXgSJwL6DiAaSj9VpUdYxDjbfrOd1bTWZ04sTHFLRj6cnRRpC arvlObn4HXi7BzUJ+XBiVJ9/SZHpiF9Iu6CrKv9ScmQlr/IriG4sw4hVfE1akqWD9TdM YsTGQWioghf0W2UHppEfo3ce0DgZlljuTzSY4HAyzYVa7nSQ81HTH7YUybnco6m4Q/OR 3PDeDUybxqj16z8iqaGWEoAX2CjFeAcj/BTtd76Et5RGmRbpY/XHvc5NSIkbXvRdy6dH HbgwanNT3K67aKJtuWAUqL3jJQD95JaIO8We4YDU4ak+Vtpr9ZMtlehX4iVTkV0yc6eO 0vZA== X-Gm-Message-State: ABy/qLbYkLtCQIggzTu5nuTXQDrffFCYSDiLXwH8yJMwH6uMu4q3Tl5d i3zjmUZ2UNvsgGuNZW6gkKqnLfriDCezJgG4 X-Google-Smtp-Source: APBJJlF/GwvbLkkHdi/e2vcpX56wVBIY0TsKCSfFfOweHpLLp08L7Y6mYftFbYT+k9Vu0AiDvNYiQA== X-Received: by 2002:a17:902:ea08:b0:1ad:f407:37d1 with SMTP id s8-20020a170902ea0800b001adf40737d1mr12627949plg.52.1688568467119; Wed, 05 Jul 2023 07:47:47 -0700 (PDT) Received: from localhost ([49.36.209.255]) by smtp.gmail.com with ESMTPSA id x3-20020a1709027c0300b001ab1b7bae5asm19062284pll.184.2023.07.05.07.47.46 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 05 Jul 2023 07:47:46 -0700 (PDT) From: Kumar Kartikeya Dwivedi To: bpf@vger.kernel.org Cc: Alexei Starovoitov , Daniel Borkmann , Andrii Nakryiko , Martin KaFai Lau Subject: [PATCH bpf v1 2/2] selftests/bpf: Add selftest for check_stack_max_depth bug Date: Wed, 5 Jul 2023 20:17:30 +0530 Message-Id: <20230705144730.235802-3-memxor@gmail.com> X-Mailer: git-send-email 2.40.1 In-Reply-To: <20230705144730.235802-1-memxor@gmail.com> References: <20230705144730.235802-1-memxor@gmail.com> Precedence: bulk X-Mailing-List: bpf@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 X-Developer-Signature: v=1; a=openpgp-sha256; l=2319; i=memxor@gmail.com; h=from:subject; bh=3WfVBEfjwSndKJo7xtesDDpuAoXw5+no5uSSdV3Ph4M=; b=owEBbQKS/ZANAwAKAUzgyIZIvxHKAcsmYgBkpYFovLvhXYyITzdrqe/GKMU4nQJ9IR9ie9VtW w7SK8odg3SJAjMEAAEKAB0WIQRLvip+Buz51YI8YRFM4MiGSL8RygUCZKWBaAAKCRBM4MiGSL8R ypWWD/wKj6MLLjEjUqgXrKakCS8YdtmE8doN60ESA8/1tlgYOLV/d65fP7ZrSA1ekZI6EeSr+1R NCT7k/kXwBBue28kFTTIWJUTH7D9gltd52megDbpwyZLP0OoInYZg5NlmC19WlCdQtyvz6LPLYb Fh7CFuVY45ouqVlQzc308cAendI8nbqNL5xSwzORFNvYlVj04wYx8aFg6laG/T3bqSiNrUzv33I h7AE30+UrTW5xzMhmkPbE4czm9CgL23KjnXlKLfI4DTOCXPRxH8CH8Q70MbAyTgohN5r32tNFw+ SXmLo7q4ebMr3JRL+KYJsGeKpUvs4FepbWqMAtcIHoz8iWML8w28bAHvWVcR+YfUSndVoCI0V9+ 1GzLJBmcu5tkrJRIPEgXIqVF52v/jqQ/b5nFncgkgY3FAE6iYhsoU1DAJtTu3J5gp1lewsiqbQK OMidW+sujPy5Hon5LILnEH9zPKGUpZAiHkyGk5l6yICQwnldoFp9Eqk1OsTGnTweGgCgck+5UHP xFD+HpTw3XhrWkjF/TtILCkMWe1qKsBcGZ/usyZyr8lisLxHv/UZlugS1qnmvm5/01XdUiagMEb Kj6xRW6oMqP6YofnTV35DZu056DzsiQigyfGJx0nfsUBPu0TOICPHW4RB9NWEPP29Lm7akCdBj9 kuwnaD0qZmWBbhQ== X-Developer-Key: i=memxor@gmail.com; a=openpgp; fpr=4BBE2A7E06ECF9D5823C61114CE0C88648BF11CA X-Spam-Status: No, score=-2.1 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,FREEMAIL_FROM, RCVD_IN_DNSWL_NONE,SPF_HELO_NONE,SPF_PASS,T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on lindbergh.monkeyblade.net X-Patchwork-Delegate: bpf@iogearbox.net Use the bpf_timer_set_callback helper to mark timer_cb as an async callback, and put a direct call to timer_cb in the main subprog. As the check_stack_max_depth happens after the do_check pass, the order does not matter. Without the previous fix, the test passes successfully. Signed-off-by: Kumar Kartikeya Dwivedi --- .../bpf/prog_tests/async_stack_depth.c | 9 +++++ .../selftests/bpf/progs/async_stack_depth.c | 40 +++++++++++++++++++ 2 files changed, 49 insertions(+) create mode 100644 tools/testing/selftests/bpf/prog_tests/async_stack_depth.c create mode 100644 tools/testing/selftests/bpf/progs/async_stack_depth.c diff --git a/tools/testing/selftests/bpf/prog_tests/async_stack_depth.c b/tools/testing/selftests/bpf/prog_tests/async_stack_depth.c new file mode 100644 index 000000000000..118abc29b236 --- /dev/null +++ b/tools/testing/selftests/bpf/prog_tests/async_stack_depth.c @@ -0,0 +1,9 @@ +// SPDX-License-Identifier: GPL-2.0 +#include + +#include "async_stack_depth.skel.h" + +void test_async_stack_depth(void) +{ + RUN_TESTS(async_stack_depth); +} diff --git a/tools/testing/selftests/bpf/progs/async_stack_depth.c b/tools/testing/selftests/bpf/progs/async_stack_depth.c new file mode 100644 index 000000000000..477ba950bb43 --- /dev/null +++ b/tools/testing/selftests/bpf/progs/async_stack_depth.c @@ -0,0 +1,40 @@ +// SPDX-License-Identifier: GPL-2.0 +#include +#include + +#include "bpf_misc.h" + +struct hmap_elem { + struct bpf_timer timer; +}; + +struct { + __uint(type, BPF_MAP_TYPE_HASH); + __uint(max_entries, 64); + __type(key, int); + __type(value, struct hmap_elem); +} hmap SEC(".maps"); + +__attribute__((noinline)) +static int timer_cb(void *map, int *key, struct bpf_timer *timer) +{ + volatile char buf[256] = {}; + return buf[69]; +} + +SEC("tc") +__failure __msg("combined stack size of 2 calls") +int prog(struct __sk_buff *ctx) +{ + struct hmap_elem *elem; + volatile char buf[256] = {}; + + elem = bpf_map_lookup_elem(&hmap, &(int){0}); + if (!elem) + return 0; + + timer_cb(NULL, NULL, NULL); + return bpf_timer_set_callback(&elem->timer, timer_cb) + buf[0]; +} + +char _license[] SEC("license") = "GPL";