1 // SPDX-License-Identifier: GPL-2.0 2 /* Copyright (c) 2026 Meta Platforms, Inc. and affiliates. */ 3 4 #include <linux/bpf.h> 5 #include <bpf/bpf_helpers.h> 6 #include "bpf_misc.h" 7 8 /* 9 * Exponential complexity in analyze_subprog() liveness analysis. 10 * 11 * analyze_subprog() recurses into each call site that passes FP-derived 12 * arguments, creating a unique func_instance per (callsite, depth). 13 * There is no memoization for callees reached with equivalent entry args. 14 * Even if memoization were added, it can be defeated by passing a distinct 15 * FP offset at each call site. arg_track keys on (frame, off[]), so 16 * r1=fp-8, r1=fp-16, ... r1=fp-400 produce 50 unique cache keys per level. 17 * 18 * This test chains 8 subprograms (the MAX_CALL_FRAMES limit). Each 19 * intermediate function calls the next one 50 times, each time with a 20 * different FP-relative offset in r1. 21 * 22 * Without complexity limits in analyze_subprog() the resulting 50^7 ~ 7.8 * 10^11 23 * recursive analyze_subprog() calls will cause a CPU soft lockup or OOM. 24 * 25 * The BPF program itself is ~1200 instructions and perfectly valid. 26 */ 27 28 char _license[] SEC("license") = "GPL"; 29 30 /* Call fn with r1 = r10 + off (a unique FP-derived arg per call site) */ 31 #define C(fn, off) "r1 = r10;" \ 32 "r1 += -" #off ";" \ 33 "call " #fn ";" 34 35 /* 50 calls, each with a distinct FP offset: -8, -16, ... -400 */ 36 #define CALLS_50(fn) \ 37 C(fn, 8) C(fn, 16) C(fn, 24) C(fn, 32) C(fn, 40) \ 38 C(fn, 48) C(fn, 56) C(fn, 64) C(fn, 72) C(fn, 80) \ 39 C(fn, 88) C(fn, 96) C(fn, 104) C(fn, 112) C(fn, 120) \ 40 C(fn, 128) C(fn, 136) C(fn, 144) C(fn, 152) C(fn, 160) \ 41 C(fn, 168) C(fn, 176) C(fn, 184) C(fn, 192) C(fn, 200) \ 42 C(fn, 208) C(fn, 216) C(fn, 224) C(fn, 232) C(fn, 240) \ 43 C(fn, 248) C(fn, 256) C(fn, 264) C(fn, 272) C(fn, 280) \ 44 C(fn, 288) C(fn, 296) C(fn, 304) C(fn, 312) C(fn, 320) \ 45 C(fn, 328) C(fn, 336) C(fn, 344) C(fn, 352) C(fn, 360) \ 46 C(fn, 368) C(fn, 376) C(fn, 384) C(fn, 392) C(fn, 400) 47 48 /* Leaf: depth 7, no further calls */ 49 __naked __noinline __used 50 static unsigned long exp_sub7(void) 51 { 52 asm volatile ( 53 "r0 = 0;" 54 "exit;" 55 ::: __clobber_all); 56 } 57 58 /* depth 6 -> calls exp_sub7 x50 with distinct offsets */ 59 __naked __noinline __used 60 static unsigned long exp_sub6(void) 61 { 62 asm volatile ( 63 CALLS_50(exp_sub7) 64 "r0 = 0;" 65 "exit;" 66 ::: __clobber_all); 67 } 68 69 /* depth 5 -> calls exp_sub6 x50 */ 70 __naked __noinline __used 71 static unsigned long exp_sub5(void) 72 { 73 asm volatile ( 74 CALLS_50(exp_sub6) 75 "r0 = 0;" 76 "exit;" 77 ::: __clobber_all); 78 } 79 80 /* depth 4 -> calls exp_sub5 x50 */ 81 __naked __noinline __used 82 static unsigned long exp_sub4(void) 83 { 84 asm volatile ( 85 CALLS_50(exp_sub5) 86 "r0 = 0;" 87 "exit;" 88 ::: __clobber_all); 89 } 90 91 /* depth 3 -> calls exp_sub4 x50 */ 92 __naked __noinline __used 93 static unsigned long exp_sub3(void) 94 { 95 asm volatile ( 96 CALLS_50(exp_sub4) 97 "r0 = 0;" 98 "exit;" 99 ::: __clobber_all); 100 } 101 102 /* depth 2 -> calls exp_sub3 x50 */ 103 __naked __noinline __used 104 static unsigned long exp_sub2(void) 105 { 106 asm volatile ( 107 CALLS_50(exp_sub3) 108 "r0 = 0;" 109 "exit;" 110 ::: __clobber_all); 111 } 112 113 /* depth 1 -> calls exp_sub2 x50 */ 114 __naked __noinline __used 115 static unsigned long exp_sub1(void) 116 { 117 asm volatile ( 118 CALLS_50(exp_sub2) 119 "r0 = 0;" 120 "exit;" 121 ::: __clobber_all); 122 } 123 124 /* 125 * Entry: depth 0. Calls exp_sub1 50 times, each with a distinct 126 * FP offset in r1. Every call site produces a unique arg_track, 127 * defeating any memoization keyed on entry args. 128 */ 129 SEC("?raw_tp") 130 __failure __log_level(2) 131 __msg("liveness analysis exceeded complexity limit") 132 __naked int liveness_exponential_complexity(void) 133 { 134 asm volatile ( 135 CALLS_50(exp_sub1) 136 "r0 = 0;" 137 "exit;" 138 ::: __clobber_all); 139 } 140