lpm_trie_bench.c

  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
 17char _license[] SEC("license") = "GPL";
 18
 19/* Filled by userspace. See fill_map() in bench_lpm_trie_map.c */
 20struct {
 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
 28long hits;
 29long duration_ns;
 30
 31/* Configured from userspace */
 32__u32 nr_entries;
 33__u32 prefixlen;
 34bool random;
 35__u8 op;
 36
 37static __u64 latency_free_start;
 38
 39SEC("fentry/bpf_map_free_deferred")
 40int 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
 63SEC("fexit/bpf_map_free_deferred")
 64int 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
 80static __u32 cur_key;
 81
 82static __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
 92static int noop(__u32 index, __u32 *unused)
 93{
 94	return 0;
 95}
 96
 97static 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
110static 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
123static 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
146static 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
162static 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
191SEC("xdp")
192int 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}