Branch data Line data Source code
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[0] __aligned(8);
23 : : };
24 : :
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 : :
30 : : static bool queue_stack_map_is_empty(struct bpf_queue_stack *qs)
31 : : {
32 : 0 : return qs->head == qs->tail;
33 : : }
34 : :
35 : : static bool queue_stack_map_is_full(struct bpf_queue_stack *qs)
36 : : {
37 : 0 : u32 head = qs->head + 1;
38 : :
39 [ # # ]: 0 : if (unlikely(head >= qs->size))
40 : : head = 0;
41 : :
42 : 0 : return head == qs->tail;
43 : : }
44 : :
45 : : /* Called from syscall */
46 : 0 : static int queue_stack_map_alloc_check(union bpf_attr *attr)
47 : : {
48 [ # # ]: 0 : if (!capable(CAP_SYS_ADMIN))
49 : : return -EPERM;
50 : :
51 : : /* check sanity of attributes */
52 [ # # # # : 0 : if (attr->max_entries == 0 || attr->key_size != 0 ||
# # ]
53 [ # # ]: 0 : attr->value_size == 0 ||
54 [ # # ]: 0 : attr->map_flags & ~QUEUE_STACK_CREATE_FLAG_MASK ||
55 : : !bpf_map_flags_access_ok(attr->map_flags))
56 : : return -EINVAL;
57 : :
58 [ # # ]: 0 : 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 : 0 : return 0;
65 : : }
66 : :
67 : 0 : static struct bpf_map *queue_stack_map_alloc(union bpf_attr *attr)
68 : : {
69 : : int ret, numa_node = bpf_map_attr_numa_node(attr);
70 : 0 : struct bpf_map_memory mem = {0};
71 : : struct bpf_queue_stack *qs;
72 : : u64 size, queue_size, cost;
73 : :
74 : 0 : size = (u64) attr->max_entries + 1;
75 : 0 : cost = queue_size = sizeof(*qs) + size * attr->value_size;
76 : :
77 : 0 : ret = bpf_map_charge_init(&mem, cost);
78 [ # # ]: 0 : if (ret < 0)
79 : 0 : return ERR_PTR(ret);
80 : :
81 : 0 : qs = bpf_map_area_alloc(queue_size, numa_node);
82 [ # # ]: 0 : if (!qs) {
83 : 0 : bpf_map_charge_finish(&mem);
84 : 0 : return ERR_PTR(-ENOMEM);
85 : : }
86 : :
87 : 0 : memset(qs, 0, sizeof(*qs));
88 : :
89 : 0 : bpf_map_init_from_attr(&qs->map, attr);
90 : :
91 : 0 : bpf_map_charge_move(&qs->map.memory, &mem);
92 : 0 : qs->size = size;
93 : :
94 : 0 : raw_spin_lock_init(&qs->lock);
95 : :
96 : 0 : return &qs->map;
97 : : }
98 : :
99 : : /* Called when map->refcnt goes to zero, either from workqueue or from syscall */
100 : 0 : static void queue_stack_map_free(struct bpf_map *map)
101 : : {
102 : : struct bpf_queue_stack *qs = bpf_queue_stack(map);
103 : :
104 : : /* at this point bpf_prog->aux->refcnt == 0 and this map->refcnt == 0,
105 : : * so the programs (can be more than one that used this map) were
106 : : * disconnected from events. Wait for outstanding critical sections in
107 : : * these programs to complete
108 : : */
109 : 0 : synchronize_rcu();
110 : :
111 : 0 : bpf_map_area_free(qs);
112 : 0 : }
113 : :
114 : 0 : static int __queue_map_get(struct bpf_map *map, void *value, bool delete)
115 : : {
116 : : struct bpf_queue_stack *qs = bpf_queue_stack(map);
117 : : unsigned long flags;
118 : : int err = 0;
119 : : void *ptr;
120 : :
121 : 0 : raw_spin_lock_irqsave(&qs->lock, flags);
122 : :
123 [ # # ]: 0 : if (queue_stack_map_is_empty(qs)) {
124 : 0 : memset(value, 0, qs->map.value_size);
125 : : err = -ENOENT;
126 : 0 : goto out;
127 : : }
128 : :
129 : 0 : ptr = &qs->elements[qs->tail * qs->map.value_size];
130 : 0 : memcpy(value, ptr, qs->map.value_size);
131 : :
132 [ # # ]: 0 : if (delete) {
133 [ # # ]: 0 : if (unlikely(++qs->tail >= qs->size))
134 : 0 : qs->tail = 0;
135 : : }
136 : :
137 : : out:
138 : 0 : raw_spin_unlock_irqrestore(&qs->lock, flags);
139 : 0 : return err;
140 : : }
141 : :
142 : :
143 : 0 : static int __stack_map_get(struct bpf_map *map, void *value, bool delete)
144 : : {
145 : : struct bpf_queue_stack *qs = bpf_queue_stack(map);
146 : : unsigned long flags;
147 : : int err = 0;
148 : : void *ptr;
149 : : u32 index;
150 : :
151 : 0 : raw_spin_lock_irqsave(&qs->lock, flags);
152 : :
153 [ # # ]: 0 : if (queue_stack_map_is_empty(qs)) {
154 : 0 : memset(value, 0, qs->map.value_size);
155 : : err = -ENOENT;
156 : 0 : goto out;
157 : : }
158 : :
159 : 0 : index = qs->head - 1;
160 [ # # ]: 0 : if (unlikely(index >= qs->size))
161 : 0 : index = qs->size - 1;
162 : :
163 : 0 : ptr = &qs->elements[index * qs->map.value_size];
164 : 0 : memcpy(value, ptr, qs->map.value_size);
165 : :
166 [ # # ]: 0 : if (delete)
167 : 0 : qs->head = index;
168 : :
169 : : out:
170 : 0 : raw_spin_unlock_irqrestore(&qs->lock, flags);
171 : 0 : return err;
172 : : }
173 : :
174 : : /* Called from syscall or from eBPF program */
175 : 0 : static int queue_map_peek_elem(struct bpf_map *map, void *value)
176 : : {
177 : 0 : return __queue_map_get(map, value, false);
178 : : }
179 : :
180 : : /* Called from syscall or from eBPF program */
181 : 0 : static int stack_map_peek_elem(struct bpf_map *map, void *value)
182 : : {
183 : 0 : return __stack_map_get(map, value, false);
184 : : }
185 : :
186 : : /* Called from syscall or from eBPF program */
187 : 0 : static int queue_map_pop_elem(struct bpf_map *map, void *value)
188 : : {
189 : 0 : return __queue_map_get(map, value, true);
190 : : }
191 : :
192 : : /* Called from syscall or from eBPF program */
193 : 0 : static int stack_map_pop_elem(struct bpf_map *map, void *value)
194 : : {
195 : 0 : return __stack_map_get(map, value, true);
196 : : }
197 : :
198 : : /* Called from syscall or from eBPF program */
199 : 0 : static int queue_stack_map_push_elem(struct bpf_map *map, void *value,
200 : : u64 flags)
201 : : {
202 : : struct bpf_queue_stack *qs = bpf_queue_stack(map);
203 : : unsigned long irq_flags;
204 : : int err = 0;
205 : : void *dst;
206 : :
207 : : /* BPF_EXIST is used to force making room for a new element in case the
208 : : * map is full
209 : : */
210 : 0 : bool replace = (flags & BPF_EXIST);
211 : :
212 : : /* Check supported flags for queue and stack maps */
213 [ # # # # ]: 0 : if (flags & BPF_NOEXIST || flags > BPF_EXIST)
214 : : return -EINVAL;
215 : :
216 : 0 : raw_spin_lock_irqsave(&qs->lock, irq_flags);
217 : :
218 [ # # ]: 0 : if (queue_stack_map_is_full(qs)) {
219 [ # # ]: 0 : if (!replace) {
220 : : err = -E2BIG;
221 : : goto out;
222 : : }
223 : : /* advance tail pointer to overwrite oldest element */
224 [ # # ]: 0 : if (unlikely(++qs->tail >= qs->size))
225 : 0 : qs->tail = 0;
226 : : }
227 : :
228 : 0 : dst = &qs->elements[qs->head * qs->map.value_size];
229 : 0 : memcpy(dst, value, qs->map.value_size);
230 : :
231 [ # # ]: 0 : if (unlikely(++qs->head >= qs->size))
232 : 0 : qs->head = 0;
233 : :
234 : : out:
235 : 0 : raw_spin_unlock_irqrestore(&qs->lock, irq_flags);
236 : 0 : return err;
237 : : }
238 : :
239 : : /* Called from syscall or from eBPF program */
240 : 0 : static void *queue_stack_map_lookup_elem(struct bpf_map *map, void *key)
241 : : {
242 : 0 : return NULL;
243 : : }
244 : :
245 : : /* Called from syscall or from eBPF program */
246 : 0 : static int queue_stack_map_update_elem(struct bpf_map *map, void *key,
247 : : void *value, u64 flags)
248 : : {
249 : 0 : return -EINVAL;
250 : : }
251 : :
252 : : /* Called from syscall or from eBPF program */
253 : 0 : static int queue_stack_map_delete_elem(struct bpf_map *map, void *key)
254 : : {
255 : 0 : return -EINVAL;
256 : : }
257 : :
258 : : /* Called from syscall */
259 : 0 : static int queue_stack_map_get_next_key(struct bpf_map *map, void *key,
260 : : void *next_key)
261 : : {
262 : 0 : return -EINVAL;
263 : : }
264 : :
265 : : const struct bpf_map_ops queue_map_ops = {
266 : : .map_alloc_check = queue_stack_map_alloc_check,
267 : : .map_alloc = queue_stack_map_alloc,
268 : : .map_free = queue_stack_map_free,
269 : : .map_lookup_elem = queue_stack_map_lookup_elem,
270 : : .map_update_elem = queue_stack_map_update_elem,
271 : : .map_delete_elem = queue_stack_map_delete_elem,
272 : : .map_push_elem = queue_stack_map_push_elem,
273 : : .map_pop_elem = queue_map_pop_elem,
274 : : .map_peek_elem = queue_map_peek_elem,
275 : : .map_get_next_key = queue_stack_map_get_next_key,
276 : : };
277 : :
278 : : const struct bpf_map_ops stack_map_ops = {
279 : : .map_alloc_check = queue_stack_map_alloc_check,
280 : : .map_alloc = queue_stack_map_alloc,
281 : : .map_free = queue_stack_map_free,
282 : : .map_lookup_elem = queue_stack_map_lookup_elem,
283 : : .map_update_elem = queue_stack_map_update_elem,
284 : : .map_delete_elem = queue_stack_map_delete_elem,
285 : : .map_push_elem = queue_stack_map_push_elem,
286 : : .map_pop_elem = stack_map_pop_elem,
287 : : .map_peek_elem = stack_map_peek_elem,
288 : : .map_get_next_key = queue_stack_map_get_next_key,
289 : : };
|
