1 // SPDX-License-Identifier: GPL-2.0 2 /* Copyright (c) 2025 Cloudflare */ 3 4 #include <vmlinux.h> 5 #include <errno.h> 6 #include <bpf/bpf_tracing.h> 7 #include <bpf/bpf_helpers.h> 8 #include <bpf/bpf_core_read.h> 9 #include "bpf_misc.h" 10 #include "bpf_atomic.h" 11 #include "progs/lpm_trie.h" 12 13 #define BPF_OBJ_NAME_LEN 16U 14 #define MAX_ENTRIES 100000000 15 #define NR_LOOPS 10000 16 17 char _license[] SEC("license") = "GPL"; 18 19 /* Filled by userspace. See fill_map() in bench_lpm_trie_map.c */ 20 struct { 21 __uint(type, BPF_MAP_TYPE_LPM_TRIE); 22 __type(key, struct trie_key); 23 __type(value, __u32); 24 __uint(map_flags, BPF_F_NO_PREALLOC); 25 __uint(max_entries, MAX_ENTRIES); 26 } trie_map SEC(".maps"); 27 28 long hits; 29 long duration_ns; 30 31 /* Configured from userspace */ 32 __u32 nr_entries; 33 __u32 prefixlen; 34 bool random; 35 __u8 op; 36 37 static __u64 latency_free_start; 38 39 SEC("fentry/bpf_map_free_deferred") 40 int BPF_PROG(trie_free_entry, struct work_struct *work) 41 { 42 struct bpf_map *map = container_of(work, struct bpf_map, work); 43 char name[BPF_OBJ_NAME_LEN]; 44 u32 map_type; 45 46 map_type = BPF_CORE_READ(map, map_type); 47 if (map_type != BPF_MAP_TYPE_LPM_TRIE) 48 return 0; 49 50 /* 51 * Ideally we'd have access to the map ID but that's already 52 * freed before we enter trie_free(). 53 */ 54 BPF_CORE_READ_STR_INTO(&name, map, name); 55 if (bpf_strncmp(name, BPF_OBJ_NAME_LEN, "trie_free_map")) 56 return 0; 57 58 latency_free_start = bpf_ktime_get_ns(); 59 60 return 0; 61 } 62 63 SEC("fexit/bpf_map_free_deferred") 64 int BPF_PROG(trie_free_exit, struct work_struct *work) 65 { 66 __u64 val; 67 68 if (!latency_free_start) 69 return 0; 70 71 val = bpf_ktime_get_ns() - latency_free_start; 72 latency_free_start = 0; 73 74 __sync_add_and_fetch(&duration_ns, val); 75 __sync_add_and_fetch(&hits, 1); 76 77 return 0; 78 } 79 80 static __u32 cur_key; 81 82 static __always_inline void generate_key(struct trie_key *key) 83 { 84 key->prefixlen = prefixlen; 85 86 if (random) 87 key->data = bpf_get_prandom_u32() % nr_entries; 88 else 89 key->data = cur_key++ % nr_entries; 90 } 91 92 static int noop(__u32 index, __u32 *unused) 93 { 94 return 0; 95 } 96 97 static int baseline(__u32 index, __u32 *unused) 98 { 99 struct trie_key key; 100 __u32 blackbox = 0; 101 102 generate_key(&key); 103 /* Avoid compiler optimizing out the modulo */ 104 barrier_var(blackbox); 105 blackbox = READ_ONCE(key.data); 106 107 return 0; 108 } 109 110 static int lookup(__u32 index, int *retval) 111 { 112 struct trie_key key; 113 114 generate_key(&key); 115 if (!bpf_map_lookup_elem(&trie_map, &key)) { 116 *retval = -ENOENT; 117 return 1; 118 } 119 120 return 0; 121 } 122 123 static int insert(__u32 index, int *retval) 124 { 125 struct trie_key key; 126 u32 val = 1; 127 int err; 128 129 generate_key(&key); 130 err = bpf_map_update_elem(&trie_map, &key, &val, BPF_NOEXIST); 131 if (err) { 132 *retval = err; 133 return 1; 134 } 135 136 /* Is this the last entry? */ 137 if (key.data == nr_entries - 1) { 138 /* For atomicity concerns, see the comment in delete() */ 139 *retval = LPM_BENCH_REINIT_MAP; 140 return 1; 141 } 142 143 return 0; 144 } 145 146 static int update(__u32 index, int *retval) 147 { 148 struct trie_key key; 149 u32 val = 1; 150 int err; 151 152 generate_key(&key); 153 err = bpf_map_update_elem(&trie_map, &key, &val, BPF_EXIST); 154 if (err) { 155 *retval = err; 156 return 1; 157 } 158 159 return 0; 160 } 161 162 static int delete(__u32 index, int *retval) 163 { 164 struct trie_key key; 165 int err; 166 167 generate_key(&key); 168 err = bpf_map_delete_elem(&trie_map, &key); 169 if (err) { 170 *retval = err; 171 return 1; 172 } 173 174 /* Do we need to refill the map? */ 175 if (key.data == nr_entries - 1) { 176 /* 177 * Atomicity isn't required because DELETE only supports 178 * one producer running concurrently. What we need is a 179 * way to track how many entries have been deleted from 180 * the trie between consecutive invocations of the BPF 181 * prog because a single bpf_loop() call might not 182 * delete all entries, e.g. when NR_LOOPS < nr_entries. 183 */ 184 *retval = LPM_BENCH_REINIT_MAP; 185 return 1; 186 } 187 188 return 0; 189 } 190 191 SEC("xdp") 192 int BPF_PROG(run_bench) 193 { 194 int err = LPM_BENCH_SUCCESS; 195 u64 start, delta; 196 int loops; 197 198 start = bpf_ktime_get_ns(); 199 200 switch (op) { 201 case LPM_OP_NOOP: 202 loops = bpf_loop(NR_LOOPS, noop, NULL, 0); 203 break; 204 case LPM_OP_BASELINE: 205 loops = bpf_loop(NR_LOOPS, baseline, NULL, 0); 206 break; 207 case LPM_OP_LOOKUP: 208 loops = bpf_loop(NR_LOOPS, lookup, &err, 0); 209 break; 210 case LPM_OP_INSERT: 211 loops = bpf_loop(NR_LOOPS, insert, &err, 0); 212 break; 213 case LPM_OP_UPDATE: 214 loops = bpf_loop(NR_LOOPS, update, &err, 0); 215 break; 216 case LPM_OP_DELETE: 217 loops = bpf_loop(NR_LOOPS, delete, &err, 0); 218 break; 219 default: 220 bpf_printk("invalid benchmark operation\n"); 221 return -1; 222 } 223 224 delta = bpf_ktime_get_ns() - start; 225 226 __sync_add_and_fetch(&duration_ns, delta); 227 __sync_add_and_fetch(&hits, loops); 228 229 return err; 230 } 231