Received: from mail-pj1-f48.google.com (mail-pj1-f48.google.com [209.85.216.48]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id AAF2F3AC0DD for ; Tue, 26 May 2026 19:37:36 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.216.48 ARC-Seal:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1779824258; cv=none; b=q6zfo/eAYIX6O7hVJMzX2ZD/ElFR4j9pSStJXItpoq1fSajT0mKNgaiim1MhhiP6tq2oSU9TMw3a6ZIn5Ev4VBFP2rJacG/c0CLBPIdIu3o4PKALovNMkV/8bNHe6wdULHNldkECu/mL17lSuy8YTE2dFUSMGRMBvxMDj2eNlPA= ARC-Message-Signature:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1779824258; c=relaxed/simple; bh=CIx/wbIY+h0O3qhg794H9N5puKyMZqIXFqmREPW3X38=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version:Content-Type; b=WxSm7pSaIZQ6FINeb/mvU9LOKCNil4wo4sIvdDReKiN33rRCnbAUw5NzD+ln/S2NBa2Tw7zKvseAERvOpBVTTMcCxp7XWcg94zjcuo+0xwz9HEN6rCOSsPq2ngyUeR8+zWCJvLQuI48Ns9XIgNWnqyvbCXA8JyGXxb1t2FGBOlA= ARC-Authentication-Results:i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=stL2yUJU; arc=none smtp.client-ip=209.85.216.48 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="stL2yUJU" Received: by mail-pj1-f48.google.com with SMTP id 98e67ed59e1d1-3699cdeec05so4734706a91.3 for ; Tue, 26 May 2026 12:37:36 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20251104; t=1779824256; x=1780429056; darn=vger.kernel.org; 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=QMywEO/xTDK++kG9pCAaD0ZUp3EUmpHCYjtqjv7Eqo4=; b=stL2yUJUZ7sNWB1yHabX6b4trrC//YNAoWZKQfK/zj0PO0DjPvcj5TRFN6aRARhngm KP8kX2X/2zbreLc3kLzdDF5KbcrbXVuUinQW3jygnM4ITOIF34qYDaIZFih56Focc2fZ GhaYmpbYVsdxQn8n8cO05tNQESzG7ecIKdJS4+zSGwFhiaFJYddxXbi/bmvjWKo9C83R Zt5N++U/tdHfWNTMKzVIZzaUHIMTZmDyHMU/IKu1ZCMMcGjlc+FfBXHCzlKgErjPXv+Y nsvTN2ZjfHBzFzzopRDHm3y2wwNcTySBS+2FxonV4vbjZsW+beJrTlsCXahCLJmTpf7J J9Vw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20251104; t=1779824256; x=1780429056; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-gg:x-gm-message-state:from :to:cc:subject:date:message-id:reply-to; bh=QMywEO/xTDK++kG9pCAaD0ZUp3EUmpHCYjtqjv7Eqo4=; b=VWsRPQQt6b5lhuytrRDqgf20YEM6rUN/w1gm2/fZ+atXkzPE+RmG/yvMnLFsWj0X8j 99W/V7GyB4St6PbJYJCrppPC+fNUoeUcDyGCjVo5sH23le8a3/wrib1OKKmp1tfN826x byenZ23K8BC30e5IX4Ikoy8oku2WX/tdATNDkQUhrSwPp0JshHxlOaFUcnWpwz/py+pU FGTKR8UNl0uavQbm5mGLI31hvXZRBfkDZaQDgGgwOaNol20LBaVCrus0xRbLFt/dXlv5 57UnO7Uuw3zIlRr+C6bQbTWUCJJejlJqq5bDG7YKWPUZ9CfqqJTTFli+zG8s009ZNeYj vPqw== X-Gm-Message-State: AOJu0Yw4DV1gK/Oo8dvuLJF15VGzcurT/RclQYewizmZ3NLjcbm4XxjH cHkoOwUAdX/4hnUs/69VoJ0+TG7xEiCKL7ZZuA+w9TeW8HRpRESpdVD1B3X2YlRxQeM= X-Gm-Gg: Acq92OF9Aqu7kFdAdyFcf/dGIfZDEgsmb9eCNIgs/3LkK81efBAFP4l/yWqqbJq/U1q k/ehGAM9+mV7i/lHuFSN1fDQNROF8XIosSXcrqzbGVIcFP45D7t1YaDw4aJrenQRuF7L0jTvD0P YMUwk7WYCjnbx33+t1QUw90qwiUky8EZ0+cgYZhx+RaSAPWu/E370I3y/KcfPAcMziAT2xI7orw 2ytQRPSfDqQdNE+mztqiCidMytHQlr4xTEVQqtBokYUYUn32qP8bcSEczDwBtb2FGdO7kiJFba7 C6tr9hpLYG7npTj+/i0pW5FXB8HVtJjtkYt2JN+/Ye6ij7E5Tz1xrMgeK9iqWZYBj0Byq+kCoPJ LYvqHzMcTecE4tRIgFmONPy/kzKVBXIFsBFYC+Ikf3hsJP5gQWR+iA2cBQUiNwhCKx/zgLLaUCE 1aEktxlZdZzczxcgffpKUg7rdqpGBgXLbHf1p99dkCFvarZVQyO0VL3YK4BAgLhXy2Ky3wgZUAH sxc2g== X-Received: by 2002:a17:90b:350a:b0:36a:fcf5:64d2 with SMTP id 98e67ed59e1d1-36afcf566b1mr5169264a91.16.1779824256031; Tue, 26 May 2026 12:37:36 -0700 (PDT) Received: from ezingerman-fedora-PF4V722J ([38.34.87.7]) by smtp.gmail.com with ESMTPSA id 98e67ed59e1d1-36a72c913a1sm12617283a91.15.2026.05.26.12.37.35 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 26 May 2026 12:37:35 -0700 (PDT) From: Eduard Zingerman To: bpf@vger.kernel.org, ast@kernel.org, andrii@kernel.org Cc: daniel@iogearbox.net, martin.lau@linux.dev, kernel-team@fb.com, yonghong.song@linux.dev, eddyz87@gmail.com, memxor@gmail.com Subject: [PATCH RFC bpf-next v2 3/6] selftests/bpf: test cases for loop hierarchy computation Date: Tue, 26 May 2026 12:37:17 -0700 Message-ID: <20260526-better-1m-reporting-v2-3-e7ec61c45d41@gmail.com> X-Mailer: git-send-email 2.54.0 In-Reply-To: <20260526-better-1m-reporting-v2-0-e7ec61c45d41@gmail.com> References: <20260526-better-1m-reporting-v2-0-e7ec61c45d41@gmail.com> Precedence: bulk X-Mailing-List: bpf@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: 8bit Test cases covering the following branches in bpf_compute_loops(): - Case B: simple backedge creating a loop (loop_single) - Case B: two independent loops (loop_two_independent) - Case B + D: nested loops where inner header's loop_header points to outer (loop_nested) - Case C: diamond CFG with no loops (fwd_edges_no_loop) - Case D: sibling inner loops within one outer loop (loop_nested_siblings) - Three levels of loop nesting (loop_three_levels) - Loop with if-else body containing forward branches (loop_with_if_else) Signed-off-by: Eduard Zingerman --- tools/testing/selftests/bpf/prog_tests/verifier.c | 2 + .../selftests/bpf/progs/verifier_loop_hierarchy.c | 233 +++++++++++++++++++++ 2 files changed, 235 insertions(+) diff --git a/tools/testing/selftests/bpf/prog_tests/verifier.c b/tools/testing/selftests/bpf/prog_tests/verifier.c index 219ff2969868..35d92d176c1f 100644 --- a/tools/testing/selftests/bpf/prog_tests/verifier.c +++ b/tools/testing/selftests/bpf/prog_tests/verifier.c @@ -57,6 +57,7 @@ #include "verifier_live_stack.skel.h" #include "verifier_liveness_exp.skel.h" #include "verifier_load_acquire.skel.h" +#include "verifier_loop_hierarchy.skel.h" #include "verifier_loops1.skel.h" #include "verifier_lwt.skel.h" #include "verifier_map_in_map.skel.h" @@ -208,6 +209,7 @@ void test_verifier_leak_ptr(void) { RUN(verifier_leak_ptr); } void test_verifier_linked_scalars(void) { RUN(verifier_linked_scalars); } void test_verifier_live_stack(void) { RUN(verifier_live_stack); } void test_verifier_liveness_exp(void) { RUN(verifier_liveness_exp); } +void test_verifier_loop_hierarchy(void) { RUN(verifier_loop_hierarchy); } void test_verifier_loops1(void) { RUN(verifier_loops1); } void test_verifier_lwt(void) { RUN(verifier_lwt); } void test_verifier_map_in_map(void) { RUN(verifier_map_in_map); } diff --git a/tools/testing/selftests/bpf/progs/verifier_loop_hierarchy.c b/tools/testing/selftests/bpf/progs/verifier_loop_hierarchy.c new file mode 100644 index 000000000000..84cabfa42485 --- /dev/null +++ b/tools/testing/selftests/bpf/progs/verifier_loop_hierarchy.c @@ -0,0 +1,233 @@ +// SPDX-License-Identifier: GPL-2.0 +/* Copyright (c) 2026 Meta Platforms, Inc. and affiliates. */ + +#include +#include +#include "bpf_misc.h" + +/* + * kernel/bpf/loops.c:compute_loops() distinguish between + * the following cases: + * - B: backedge -> simple loop + * - C: cross edge to non-loop node -> no-op + * - D: edge to node whose header is in DFS path -> nested loop + * - E: edge to node whose header is NOT in DFS path -> irreducible + * + * Below test cases cover the above branches in various combinations. + */ + +/* Case B: single bounded loop. */ +SEC("socket") +__success +__log_level(2) +__msg("Program dump") +__msg(" 0: {{.*}} (b7) r0 = 0") +__msg(" 1 1: {{.*}} (07) r0 += 1") +__msg(" 1 1 2: {{.*}} (a5) if r0 < 0xa goto pc-2") +__msg(" 3: {{.*}} (95) exit") +__naked void loop_single(void) +{ + asm volatile (" \ + r0 = 0; \ +1: r0 += 1; \ + if r0 < 10 goto 1b; \ + exit; \ +" ::: __clobber_all); +} + +/* Case B: two independent loops at the same nesting level. */ +SEC("socket") +__success +__log_level(2) +__msg("Program dump") +__msg(" 0: {{.*}} (b7) r0 = 0") +__msg(" 2 1: {{.*}} (07) r0 += 1") +__msg(" 2 1 2: {{.*}} (a5) if r0 < 0xa goto pc-2") +__msg(" 3: {{.*}} (b7) r1 = 0") +__msg(" 1 4: {{.*}} (07) r1 += 1") +__msg(" 1 4 5: {{.*}} (a5) if r1 < 0xa goto pc-2") +__msg(" 6: {{.*}} (95) exit") +__naked void loop_two_independent(void) +{ + asm volatile (" \ + r0 = 0; \ +1: r0 += 1; \ + if r0 < 10 goto 1b; \ + r1 = 0; \ +2: r1 += 1; \ + if r1 < 10 goto 2b; \ + exit; \ +" ::: __clobber_all); +} + +/* Case B + D: nested loops. */ +SEC("socket") +__success +__log_level(2) +__msg("Program dump") +__msg(" 0: {{.*}} (b7) r0 = 0") +__msg(" 1 1: {{.*}} (07) r0 += 1") /* outer loop header */ +__msg(" 1 1 2: {{.*}} (b7) r1 = 0") /* outer loop insn */ +__msg(" 1 1 3: {{.*}} (07) r1 += 1") /* inner loop header */ +__msg(" 1 3 4: {{.*}} (a5) if r1 < 0x5 goto pc-2") /* inner loop insn */ +__msg(" 1 1 5: {{.*}} (a5) if r0 < 0xa goto pc-5") /* outer loop insn */ +__msg(" 6: {{.*}} (95) exit") +__naked void loop_nested(void) +{ + asm volatile (" \ + r0 = 0; \ +1: r0 += 1; \ + r1 = 0; \ +2: r1 += 1; \ + if r1 < 5 goto 2b; \ + if r0 < 10 goto 1b; \ + exit; \ +" ::: __clobber_all); +} + +/* Case C: forward edges, no loops. */ +SEC("socket") +__success +__log_level(2) +__msg("Program dump") +__msg(" 0: {{.*}} (85) call bpf_get_prandom_u32") +__msg(" 1: {{.*}} (25) if r0 > 0x0 goto pc+2") +__msg(" 2: {{.*}} (b7) r0 = 2") +__msg(" 3: {{.*}} (05) goto pc+1") +__msg(" 4: {{.*}} (b7) r0 = 3") +__msg(" 5: {{.*}} (95) exit") +__naked void fwd_edges_no_loop(void) +{ + asm volatile (" \ + call %[bpf_get_prandom_u32]; \ + if r0 > 0 goto 1f; \ + r0 = 2; \ + goto 2f; \ +1: r0 = 3; \ +2: exit; \ +" : + : __imm(bpf_get_prandom_u32) + : __clobber_all); +} + +/* Case B + D: two sibling inner loops within one outer loop. */ +SEC("socket") +__success +__log_level(2) +__msg("Program dump") +__msg(" 0: {{.*}} (b7) r0 = 0") +__msg(" 1 1: {{.*}} (07) r0 += 1") +__msg(" 1 1 2: {{.*}} (b7) r1 = 0") +__msg(" 1 1 3: {{.*}} (07) r1 += 1") +__msg(" 1 3 4: {{.*}} (a5) if r1 < 0x5 goto pc-2") +__msg(" 1 1 5: {{.*}} (b7) r2 = 0") +__msg(" 1 1 6: {{.*}} (07) r2 += 1") +__msg(" 1 6 7: {{.*}} (a5) if r2 < 0x5 goto pc-2") +__msg(" 1 1 8: {{.*}} (a5) if r0 < 0xa goto pc-8") +__msg(" 9: {{.*}} (95) exit") +__naked void loop_nested_siblings(void) +{ + asm volatile (" \ + r0 = 0; \ +1: r0 += 1; \ + r1 = 0; \ +2: r1 += 1; \ + if r1 < 5 goto 2b; \ + r2 = 0; \ +3: r2 += 1; \ + if r2 < 5 goto 3b; \ + if r0 < 10 goto 1b; \ + exit; \ +" ::: __clobber_all); +} + +/* Three levels of nesting. */ +SEC("socket") +__success +__log_level(2) +__msg("Program dump") +__msg(" 0: {{.*}} (b7) r0 = 0") +__msg(" 1 1: {{.*}} (07) r0 += 1") +__msg(" 1 1 2: {{.*}} (b7) r1 = 0") +__msg(" 1 1 3: {{.*}} (07) r1 += 1") +__msg(" 1 3 4: {{.*}} (b7) r2 = 0") +__msg(" 1 3 5: {{.*}} (07) r2 += 1") +__msg(" 1 5 6: {{.*}} (a5) if r2 < 0x3 goto pc-2") +__msg(" 1 3 7: {{.*}} (a5) if r1 < 0x5 goto pc-5") +__msg(" 1 1 8: {{.*}} (a5) if r0 < 0xa goto pc-8") +__msg(" 9: {{.*}} (95) exit") +__naked void loop_three_levels(void) +{ + asm volatile (" \ + r0 = 0; \ +1: r0 += 1; \ + r1 = 0; \ +2: r1 += 1; \ + r2 = 0; \ +3: r2 += 1; \ + if r2 < 3 goto 3b; \ + if r1 < 5 goto 2b; \ + if r0 < 10 goto 1b; \ + exit; \ +" ::: __clobber_all); +} + +/* Loop with an if-else body (forward branch inside loop, Case C). */ +SEC("socket") +__success +__log_level(2) +__msg("Program dump") +__msg(" 0: {{.*}} (b7) r0 = 0") +__msg(" 1 1: {{.*}} (07) r0 += 1") +__msg(" 1 1 2: {{.*}} (bf) r1 = r0") +__msg(" 1 1 3: {{.*}} (25) if r1 > 0x5 goto pc+1") +__msg(" 1 1 4: {{.*}} (b7) r1 = 1") +__msg(" 1 1 5: {{.*}} (0f) r0 += r1") +__msg(" 1 1 6: {{.*}} (a5) if r0 < 0x64 goto pc-6") +__msg(" 7: {{.*}} (95) exit") +__naked void loop_with_if_else(void) +{ + asm volatile (" \ + r0 = 0; \ +1: r0 += 1; \ + r1 = r0; \ + if r1 > 5 goto 2f; \ + r1 = 1; \ +2: r0 += r1; \ + if r0 < 100 goto 1b; \ + exit; \ +" ::: __clobber_all); +} + +/* Case E: irreducible loop. */ +SEC("socket") +__success +__log_level(2) +__msg("Program dump") +__msg(" 0: {{.*}} (85) call bpf_get_prandom_u32") +__msg(" 1: {{.*}} (b7) r1 = 0") +__msg(" 2: {{.*}} (25) if r0 > 0x5 goto pc+2") +__msg(" 1 3: {{.*}} (b7) r1 = 1") +__msg(" 1 3 4: {{.*}} (05) goto pc+1") +__msg(" 5: {{.*}} (b7) r1 = 2") +__msg(" 1 3 6: {{.*}} (0f) r0 += r1") +__msg(" 1 3 7: {{.*}} (a5) if r0 < 0x10 goto pc-5") +__msg(" 8: {{.*}} (95) exit") +__naked void loop_irreducible(void) +{ + asm volatile (" \ + call %[bpf_get_prandom_u32]; \ + r1 = 0; \ + if r0 > 5 goto 2f; \ +1: r1 = 1; \ + goto 3f; \ +2: r1 = 2; \ +3: r0 += r1; \ + if r0 < 16 goto 1b; \ + exit; \ +" : + : __imm(bpf_get_prandom_u32) + : __clobber_all); +} + +char _license[] SEC("license") = "GPL"; -- 2.54.0