1 // SPDX-License-Identifier: GPL-2.0
2 /*
3 * queue_stack_maps.c: BPF queue and stack maps
4 *
5 * Copyright (c) 2018 Politecnico di Torino
6 */
7 #include <linux/bpf.h>
8 #include <linux/list.h>
9 #include <linux/slab.h>
10 #include <linux/capability.h>
11 #include "percpu_freelist.h"
12
13 #define QUEUE_STACK_CREATE_FLAG_MASK \
14 (BPF_F_NUMA_NODE | BPF_F_ACCESS_MASK)
15
16 struct bpf_queue_stack {
17 struct bpf_map map;
18 raw_spinlock_t lock;
19 u32 head, tail;
20 u32 size; /* max_entries + 1 */
21
22 char elements[] __aligned(8);
23 };
24
bpf_queue_stack(struct bpf_map * map)25 static struct bpf_queue_stack *bpf_queue_stack(struct bpf_map *map)
26 {
27 return container_of(map, struct bpf_queue_stack, map);
28 }
29
queue_stack_map_is_empty(struct bpf_queue_stack * qs)30 static bool queue_stack_map_is_empty(struct bpf_queue_stack *qs)
31 {
32 return qs->head == qs->tail;
33 }
34
queue_stack_map_is_full(struct bpf_queue_stack * qs)35 static bool queue_stack_map_is_full(struct bpf_queue_stack *qs)
36 {
37 u32 head = qs->head + 1;
38
39 if (unlikely(head >= qs->size))
40 head = 0;
41
42 return head == qs->tail;
43 }
44
45 /* Called from syscall */
queue_stack_map_alloc_check(union bpf_attr * attr)46 static int queue_stack_map_alloc_check(union bpf_attr *attr)
47 {
48 if (!bpf_capable())
49 return -EPERM;
50
51 /* check sanity of attributes */
52 if (attr->max_entries == 0 || attr->key_size != 0 ||
53 attr->value_size == 0 ||
54 attr->map_flags & ~QUEUE_STACK_CREATE_FLAG_MASK ||
55 !bpf_map_flags_access_ok(attr->map_flags))
56 return -EINVAL;
57
58 if (attr->value_size > KMALLOC_MAX_SIZE)
59 /* if value_size is bigger, the user space won't be able to
60 * access the elements.
61 */
62 return -E2BIG;
63
64 return 0;
65 }
66
queue_stack_map_alloc(union bpf_attr * attr)67 static struct bpf_map *queue_stack_map_alloc(union bpf_attr *attr)
68 {
69 int numa_node = bpf_map_attr_numa_node(attr);
70 struct bpf_queue_stack *qs;
71 u64 size, queue_size;
72
73 size = (u64) attr->max_entries + 1;
74 queue_size = sizeof(*qs) + size * attr->value_size;
75
76 qs = bpf_map_area_alloc(queue_size, numa_node);
77 if (!qs)
78 return ERR_PTR(-ENOMEM);
79
80 memset(qs, 0, sizeof(*qs));
81
82 bpf_map_init_from_attr(&qs->map, attr);
83
84 qs->size = size;
85
86 raw_spin_lock_init(&qs->lock);
87
88 return &qs->map;
89 }
90
91 /* Called when map->refcnt goes to zero, either from workqueue or from syscall */
queue_stack_map_free(struct bpf_map * map)92 static void queue_stack_map_free(struct bpf_map *map)
93 {
94 struct bpf_queue_stack *qs = bpf_queue_stack(map);
95
96 bpf_map_area_free(qs);
97 }
98
__queue_map_get(struct bpf_map * map,void * value,bool delete)99 static int __queue_map_get(struct bpf_map *map, void *value, bool delete)
100 {
101 struct bpf_queue_stack *qs = bpf_queue_stack(map);
102 unsigned long flags;
103 int err = 0;
104 void *ptr;
105
106 if (in_nmi()) {
107 if (!raw_spin_trylock_irqsave(&qs->lock, flags))
108 return -EBUSY;
109 } else {
110 raw_spin_lock_irqsave(&qs->lock, flags);
111 }
112
113 if (queue_stack_map_is_empty(qs)) {
114 memset(value, 0, qs->map.value_size);
115 err = -ENOENT;
116 goto out;
117 }
118
119 ptr = &qs->elements[qs->tail * qs->map.value_size];
120 memcpy(value, ptr, qs->map.value_size);
121
122 if (delete) {
123 if (unlikely(++qs->tail >= qs->size))
124 qs->tail = 0;
125 }
126
127 out:
128 raw_spin_unlock_irqrestore(&qs->lock, flags);
129 return err;
130 }
131
132
__stack_map_get(struct bpf_map * map,void * value,bool delete)133 static int __stack_map_get(struct bpf_map *map, void *value, bool delete)
134 {
135 struct bpf_queue_stack *qs = bpf_queue_stack(map);
136 unsigned long flags;
137 int err = 0;
138 void *ptr;
139 u32 index;
140
141 if (in_nmi()) {
142 if (!raw_spin_trylock_irqsave(&qs->lock, flags))
143 return -EBUSY;
144 } else {
145 raw_spin_lock_irqsave(&qs->lock, flags);
146 }
147
148 if (queue_stack_map_is_empty(qs)) {
149 memset(value, 0, qs->map.value_size);
150 err = -ENOENT;
151 goto out;
152 }
153
154 index = qs->head - 1;
155 if (unlikely(index >= qs->size))
156 index = qs->size - 1;
157
158 ptr = &qs->elements[index * qs->map.value_size];
159 memcpy(value, ptr, qs->map.value_size);
160
161 if (delete)
162 qs->head = index;
163
164 out:
165 raw_spin_unlock_irqrestore(&qs->lock, flags);
166 return err;
167 }
168
169 /* Called from syscall or from eBPF program */
queue_map_peek_elem(struct bpf_map * map,void * value)170 static int queue_map_peek_elem(struct bpf_map *map, void *value)
171 {
172 return __queue_map_get(map, value, false);
173 }
174
175 /* Called from syscall or from eBPF program */
stack_map_peek_elem(struct bpf_map * map,void * value)176 static int stack_map_peek_elem(struct bpf_map *map, void *value)
177 {
178 return __stack_map_get(map, value, false);
179 }
180
181 /* Called from syscall or from eBPF program */
queue_map_pop_elem(struct bpf_map * map,void * value)182 static int queue_map_pop_elem(struct bpf_map *map, void *value)
183 {
184 return __queue_map_get(map, value, true);
185 }
186
187 /* Called from syscall or from eBPF program */
stack_map_pop_elem(struct bpf_map * map,void * value)188 static int stack_map_pop_elem(struct bpf_map *map, void *value)
189 {
190 return __stack_map_get(map, value, true);
191 }
192
193 /* Called from syscall or from eBPF program */
queue_stack_map_push_elem(struct bpf_map * map,void * value,u64 flags)194 static int queue_stack_map_push_elem(struct bpf_map *map, void *value,
195 u64 flags)
196 {
197 struct bpf_queue_stack *qs = bpf_queue_stack(map);
198 unsigned long irq_flags;
199 int err = 0;
200 void *dst;
201
202 /* BPF_EXIST is used to force making room for a new element in case the
203 * map is full
204 */
205 bool replace = (flags & BPF_EXIST);
206
207 /* Check supported flags for queue and stack maps */
208 if (flags & BPF_NOEXIST || flags > BPF_EXIST)
209 return -EINVAL;
210
211 if (in_nmi()) {
212 if (!raw_spin_trylock_irqsave(&qs->lock, irq_flags))
213 return -EBUSY;
214 } else {
215 raw_spin_lock_irqsave(&qs->lock, irq_flags);
216 }
217
218 if (queue_stack_map_is_full(qs)) {
219 if (!replace) {
220 err = -E2BIG;
221 goto out;
222 }
223 /* advance tail pointer to overwrite oldest element */
224 if (unlikely(++qs->tail >= qs->size))
225 qs->tail = 0;
226 }
227
228 dst = &qs->elements[qs->head * qs->map.value_size];
229 memcpy(dst, value, qs->map.value_size);
230
231 if (unlikely(++qs->head >= qs->size))
232 qs->head = 0;
233
234 out:
235 raw_spin_unlock_irqrestore(&qs->lock, irq_flags);
236 return err;
237 }
238
239 /* Called from syscall or from eBPF program */
queue_stack_map_lookup_elem(struct bpf_map * map,void * key)240 static void *queue_stack_map_lookup_elem(struct bpf_map *map, void *key)
241 {
242 return NULL;
243 }
244
245 /* Called from syscall or from eBPF program */
queue_stack_map_update_elem(struct bpf_map * map,void * key,void * value,u64 flags)246 static int queue_stack_map_update_elem(struct bpf_map *map, void *key,
247 void *value, u64 flags)
248 {
249 return -EINVAL;
250 }
251
252 /* Called from syscall or from eBPF program */
queue_stack_map_delete_elem(struct bpf_map * map,void * key)253 static int queue_stack_map_delete_elem(struct bpf_map *map, void *key)
254 {
255 return -EINVAL;
256 }
257
258 /* Called from syscall */
queue_stack_map_get_next_key(struct bpf_map * map,void * key,void * next_key)259 static int queue_stack_map_get_next_key(struct bpf_map *map, void *key,
260 void *next_key)
261 {
262 return -EINVAL;
263 }
264
265 static int queue_map_btf_id;
266 const struct bpf_map_ops queue_map_ops = {
267 .map_meta_equal = bpf_map_meta_equal,
268 .map_alloc_check = queue_stack_map_alloc_check,
269 .map_alloc = queue_stack_map_alloc,
270 .map_free = queue_stack_map_free,
271 .map_lookup_elem = queue_stack_map_lookup_elem,
272 .map_update_elem = queue_stack_map_update_elem,
273 .map_delete_elem = queue_stack_map_delete_elem,
274 .map_push_elem = queue_stack_map_push_elem,
275 .map_pop_elem = queue_map_pop_elem,
276 .map_peek_elem = queue_map_peek_elem,
277 .map_get_next_key = queue_stack_map_get_next_key,
278 .map_btf_name = "bpf_queue_stack",
279 .map_btf_id = &queue_map_btf_id,
280 };
281
282 static int stack_map_btf_id;
283 const struct bpf_map_ops stack_map_ops = {
284 .map_meta_equal = bpf_map_meta_equal,
285 .map_alloc_check = queue_stack_map_alloc_check,
286 .map_alloc = queue_stack_map_alloc,
287 .map_free = queue_stack_map_free,
288 .map_lookup_elem = queue_stack_map_lookup_elem,
289 .map_update_elem = queue_stack_map_update_elem,
290 .map_delete_elem = queue_stack_map_delete_elem,
291 .map_push_elem = queue_stack_map_push_elem,
292 .map_pop_elem = stack_map_pop_elem,
293 .map_peek_elem = stack_map_peek_elem,
294 .map_get_next_key = queue_stack_map_get_next_key,
295 .map_btf_name = "bpf_queue_stack",
296 .map_btf_id = &stack_map_btf_id,
297 };
298