1 | // SPDX-License-Identifier: GPL-2.0 |
2 | /* Copyright (c) 2019 Facebook */ |
3 | #include <linux/rculist.h> |
4 | #include <linux/list.h> |
5 | #include <linux/hash.h> |
6 | #include <linux/types.h> |
7 | #include <linux/spinlock.h> |
8 | #include <linux/bpf.h> |
9 | #include <linux/btf_ids.h> |
10 | #include <linux/bpf_local_storage.h> |
11 | #include <net/sock.h> |
12 | #include <uapi/linux/sock_diag.h> |
13 | #include <uapi/linux/btf.h> |
14 | #include <linux/rcupdate.h> |
15 | #include <linux/rcupdate_trace.h> |
16 | #include <linux/rcupdate_wait.h> |
17 | |
18 | #define BPF_LOCAL_STORAGE_CREATE_FLAG_MASK (BPF_F_NO_PREALLOC | BPF_F_CLONE) |
19 | |
20 | static struct bpf_local_storage_map_bucket * |
21 | select_bucket(struct bpf_local_storage_map *smap, |
22 | struct bpf_local_storage_elem *selem) |
23 | { |
24 | return &smap->buckets[hash_ptr(ptr: selem, bits: smap->bucket_log)]; |
25 | } |
26 | |
27 | static int mem_charge(struct bpf_local_storage_map *smap, void *owner, u32 size) |
28 | { |
29 | struct bpf_map *map = &smap->map; |
30 | |
31 | if (!map->ops->map_local_storage_charge) |
32 | return 0; |
33 | |
34 | return map->ops->map_local_storage_charge(smap, owner, size); |
35 | } |
36 | |
37 | static void mem_uncharge(struct bpf_local_storage_map *smap, void *owner, |
38 | u32 size) |
39 | { |
40 | struct bpf_map *map = &smap->map; |
41 | |
42 | if (map->ops->map_local_storage_uncharge) |
43 | map->ops->map_local_storage_uncharge(smap, owner, size); |
44 | } |
45 | |
46 | static struct bpf_local_storage __rcu ** |
47 | owner_storage(struct bpf_local_storage_map *smap, void *owner) |
48 | { |
49 | struct bpf_map *map = &smap->map; |
50 | |
51 | return map->ops->map_owner_storage_ptr(owner); |
52 | } |
53 | |
54 | static bool selem_linked_to_storage_lockless(const struct bpf_local_storage_elem *selem) |
55 | { |
56 | return !hlist_unhashed_lockless(h: &selem->snode); |
57 | } |
58 | |
59 | static bool selem_linked_to_storage(const struct bpf_local_storage_elem *selem) |
60 | { |
61 | return !hlist_unhashed(h: &selem->snode); |
62 | } |
63 | |
64 | static bool selem_linked_to_map_lockless(const struct bpf_local_storage_elem *selem) |
65 | { |
66 | return !hlist_unhashed_lockless(h: &selem->map_node); |
67 | } |
68 | |
69 | static bool selem_linked_to_map(const struct bpf_local_storage_elem *selem) |
70 | { |
71 | return !hlist_unhashed(h: &selem->map_node); |
72 | } |
73 | |
74 | struct bpf_local_storage_elem * |
75 | bpf_selem_alloc(struct bpf_local_storage_map *smap, void *owner, |
76 | void *value, bool charge_mem, gfp_t gfp_flags) |
77 | { |
78 | struct bpf_local_storage_elem *selem; |
79 | |
80 | if (charge_mem && mem_charge(smap, owner, size: smap->elem_size)) |
81 | return NULL; |
82 | |
83 | if (smap->bpf_ma) { |
84 | migrate_disable(); |
85 | selem = bpf_mem_cache_alloc_flags(ma: &smap->selem_ma, flags: gfp_flags); |
86 | migrate_enable(); |
87 | if (selem) |
88 | /* Keep the original bpf_map_kzalloc behavior |
89 | * before started using the bpf_mem_cache_alloc. |
90 | * |
91 | * No need to use zero_map_value. The bpf_selem_free() |
92 | * only does bpf_mem_cache_free when there is |
93 | * no other bpf prog is using the selem. |
94 | */ |
95 | memset(SDATA(selem)->data, 0, smap->map.value_size); |
96 | } else { |
97 | selem = bpf_map_kzalloc(map: &smap->map, size: smap->elem_size, |
98 | flags: gfp_flags | __GFP_NOWARN); |
99 | } |
100 | |
101 | if (selem) { |
102 | if (value) |
103 | copy_map_value(map: &smap->map, SDATA(selem)->data, src: value); |
104 | /* No need to call check_and_init_map_value as memory is zero init */ |
105 | return selem; |
106 | } |
107 | |
108 | if (charge_mem) |
109 | mem_uncharge(smap, owner, size: smap->elem_size); |
110 | |
111 | return NULL; |
112 | } |
113 | |
114 | /* rcu tasks trace callback for bpf_ma == false */ |
115 | static void __bpf_local_storage_free_trace_rcu(struct rcu_head *rcu) |
116 | { |
117 | struct bpf_local_storage *local_storage; |
118 | |
119 | /* If RCU Tasks Trace grace period implies RCU grace period, do |
120 | * kfree(), else do kfree_rcu(). |
121 | */ |
122 | local_storage = container_of(rcu, struct bpf_local_storage, rcu); |
123 | if (rcu_trace_implies_rcu_gp()) |
124 | kfree(objp: local_storage); |
125 | else |
126 | kfree_rcu(local_storage, rcu); |
127 | } |
128 | |
129 | static void bpf_local_storage_free_rcu(struct rcu_head *rcu) |
130 | { |
131 | struct bpf_local_storage *local_storage; |
132 | |
133 | local_storage = container_of(rcu, struct bpf_local_storage, rcu); |
134 | bpf_mem_cache_raw_free(ptr: local_storage); |
135 | } |
136 | |
137 | static void bpf_local_storage_free_trace_rcu(struct rcu_head *rcu) |
138 | { |
139 | if (rcu_trace_implies_rcu_gp()) |
140 | bpf_local_storage_free_rcu(rcu); |
141 | else |
142 | call_rcu(head: rcu, func: bpf_local_storage_free_rcu); |
143 | } |
144 | |
145 | /* Handle bpf_ma == false */ |
146 | static void __bpf_local_storage_free(struct bpf_local_storage *local_storage, |
147 | bool vanilla_rcu) |
148 | { |
149 | if (vanilla_rcu) |
150 | kfree_rcu(local_storage, rcu); |
151 | else |
152 | call_rcu_tasks_trace(rhp: &local_storage->rcu, |
153 | func: __bpf_local_storage_free_trace_rcu); |
154 | } |
155 | |
156 | static void bpf_local_storage_free(struct bpf_local_storage *local_storage, |
157 | struct bpf_local_storage_map *smap, |
158 | bool bpf_ma, bool reuse_now) |
159 | { |
160 | if (!local_storage) |
161 | return; |
162 | |
163 | if (!bpf_ma) { |
164 | __bpf_local_storage_free(local_storage, vanilla_rcu: reuse_now); |
165 | return; |
166 | } |
167 | |
168 | if (!reuse_now) { |
169 | call_rcu_tasks_trace(rhp: &local_storage->rcu, |
170 | func: bpf_local_storage_free_trace_rcu); |
171 | return; |
172 | } |
173 | |
174 | if (smap) { |
175 | migrate_disable(); |
176 | bpf_mem_cache_free(ma: &smap->storage_ma, ptr: local_storage); |
177 | migrate_enable(); |
178 | } else { |
179 | /* smap could be NULL if the selem that triggered |
180 | * this 'local_storage' creation had been long gone. |
181 | * In this case, directly do call_rcu(). |
182 | */ |
183 | call_rcu(head: &local_storage->rcu, func: bpf_local_storage_free_rcu); |
184 | } |
185 | } |
186 | |
187 | /* rcu tasks trace callback for bpf_ma == false */ |
188 | static void __bpf_selem_free_trace_rcu(struct rcu_head *rcu) |
189 | { |
190 | struct bpf_local_storage_elem *selem; |
191 | |
192 | selem = container_of(rcu, struct bpf_local_storage_elem, rcu); |
193 | if (rcu_trace_implies_rcu_gp()) |
194 | kfree(objp: selem); |
195 | else |
196 | kfree_rcu(selem, rcu); |
197 | } |
198 | |
199 | /* Handle bpf_ma == false */ |
200 | static void __bpf_selem_free(struct bpf_local_storage_elem *selem, |
201 | bool vanilla_rcu) |
202 | { |
203 | if (vanilla_rcu) |
204 | kfree_rcu(selem, rcu); |
205 | else |
206 | call_rcu_tasks_trace(rhp: &selem->rcu, func: __bpf_selem_free_trace_rcu); |
207 | } |
208 | |
209 | static void bpf_selem_free_rcu(struct rcu_head *rcu) |
210 | { |
211 | struct bpf_local_storage_elem *selem; |
212 | |
213 | selem = container_of(rcu, struct bpf_local_storage_elem, rcu); |
214 | bpf_mem_cache_raw_free(ptr: selem); |
215 | } |
216 | |
217 | static void bpf_selem_free_trace_rcu(struct rcu_head *rcu) |
218 | { |
219 | if (rcu_trace_implies_rcu_gp()) |
220 | bpf_selem_free_rcu(rcu); |
221 | else |
222 | call_rcu(head: rcu, func: bpf_selem_free_rcu); |
223 | } |
224 | |
225 | void bpf_selem_free(struct bpf_local_storage_elem *selem, |
226 | struct bpf_local_storage_map *smap, |
227 | bool reuse_now) |
228 | { |
229 | bpf_obj_free_fields(rec: smap->map.record, SDATA(selem)->data); |
230 | |
231 | if (!smap->bpf_ma) { |
232 | __bpf_selem_free(selem, vanilla_rcu: reuse_now); |
233 | return; |
234 | } |
235 | |
236 | if (!reuse_now) { |
237 | call_rcu_tasks_trace(rhp: &selem->rcu, func: bpf_selem_free_trace_rcu); |
238 | } else { |
239 | /* Instead of using the vanilla call_rcu(), |
240 | * bpf_mem_cache_free will be able to reuse selem |
241 | * immediately. |
242 | */ |
243 | migrate_disable(); |
244 | bpf_mem_cache_free(ma: &smap->selem_ma, ptr: selem); |
245 | migrate_enable(); |
246 | } |
247 | } |
248 | |
249 | /* local_storage->lock must be held and selem->local_storage == local_storage. |
250 | * The caller must ensure selem->smap is still valid to be |
251 | * dereferenced for its smap->elem_size and smap->cache_idx. |
252 | */ |
253 | static bool bpf_selem_unlink_storage_nolock(struct bpf_local_storage *local_storage, |
254 | struct bpf_local_storage_elem *selem, |
255 | bool uncharge_mem, bool reuse_now) |
256 | { |
257 | struct bpf_local_storage_map *smap; |
258 | bool free_local_storage; |
259 | void *owner; |
260 | |
261 | smap = rcu_dereference_check(SDATA(selem)->smap, bpf_rcu_lock_held()); |
262 | owner = local_storage->owner; |
263 | |
264 | /* All uncharging on the owner must be done first. |
265 | * The owner may be freed once the last selem is unlinked |
266 | * from local_storage. |
267 | */ |
268 | if (uncharge_mem) |
269 | mem_uncharge(smap, owner, size: smap->elem_size); |
270 | |
271 | free_local_storage = hlist_is_singular_node(n: &selem->snode, |
272 | h: &local_storage->list); |
273 | if (free_local_storage) { |
274 | mem_uncharge(smap, owner, size: sizeof(struct bpf_local_storage)); |
275 | local_storage->owner = NULL; |
276 | |
277 | /* After this RCU_INIT, owner may be freed and cannot be used */ |
278 | RCU_INIT_POINTER(*owner_storage(smap, owner), NULL); |
279 | |
280 | /* local_storage is not freed now. local_storage->lock is |
281 | * still held and raw_spin_unlock_bh(&local_storage->lock) |
282 | * will be done by the caller. |
283 | * |
284 | * Although the unlock will be done under |
285 | * rcu_read_lock(), it is more intuitive to |
286 | * read if the freeing of the storage is done |
287 | * after the raw_spin_unlock_bh(&local_storage->lock). |
288 | * |
289 | * Hence, a "bool free_local_storage" is returned |
290 | * to the caller which then calls then frees the storage after |
291 | * all the RCU grace periods have expired. |
292 | */ |
293 | } |
294 | hlist_del_init_rcu(n: &selem->snode); |
295 | if (rcu_access_pointer(local_storage->cache[smap->cache_idx]) == |
296 | SDATA(selem)) |
297 | RCU_INIT_POINTER(local_storage->cache[smap->cache_idx], NULL); |
298 | |
299 | bpf_selem_free(selem, smap, reuse_now); |
300 | |
301 | if (rcu_access_pointer(local_storage->smap) == smap) |
302 | RCU_INIT_POINTER(local_storage->smap, NULL); |
303 | |
304 | return free_local_storage; |
305 | } |
306 | |
307 | static bool check_storage_bpf_ma(struct bpf_local_storage *local_storage, |
308 | struct bpf_local_storage_map *storage_smap, |
309 | struct bpf_local_storage_elem *selem) |
310 | { |
311 | |
312 | struct bpf_local_storage_map *selem_smap; |
313 | |
314 | /* local_storage->smap may be NULL. If it is, get the bpf_ma |
315 | * from any selem in the local_storage->list. The bpf_ma of all |
316 | * local_storage and selem should have the same value |
317 | * for the same map type. |
318 | * |
319 | * If the local_storage->list is already empty, the caller will not |
320 | * care about the bpf_ma value also because the caller is not |
321 | * responsibile to free the local_storage. |
322 | */ |
323 | |
324 | if (storage_smap) |
325 | return storage_smap->bpf_ma; |
326 | |
327 | if (!selem) { |
328 | struct hlist_node *n; |
329 | |
330 | n = rcu_dereference_check(hlist_first_rcu(&local_storage->list), |
331 | bpf_rcu_lock_held()); |
332 | if (!n) |
333 | return false; |
334 | |
335 | selem = hlist_entry(n, struct bpf_local_storage_elem, snode); |
336 | } |
337 | selem_smap = rcu_dereference_check(SDATA(selem)->smap, bpf_rcu_lock_held()); |
338 | |
339 | return selem_smap->bpf_ma; |
340 | } |
341 | |
342 | static void bpf_selem_unlink_storage(struct bpf_local_storage_elem *selem, |
343 | bool reuse_now) |
344 | { |
345 | struct bpf_local_storage_map *storage_smap; |
346 | struct bpf_local_storage *local_storage; |
347 | bool bpf_ma, free_local_storage = false; |
348 | unsigned long flags; |
349 | |
350 | if (unlikely(!selem_linked_to_storage_lockless(selem))) |
351 | /* selem has already been unlinked from sk */ |
352 | return; |
353 | |
354 | local_storage = rcu_dereference_check(selem->local_storage, |
355 | bpf_rcu_lock_held()); |
356 | storage_smap = rcu_dereference_check(local_storage->smap, |
357 | bpf_rcu_lock_held()); |
358 | bpf_ma = check_storage_bpf_ma(local_storage, storage_smap, selem); |
359 | |
360 | raw_spin_lock_irqsave(&local_storage->lock, flags); |
361 | if (likely(selem_linked_to_storage(selem))) |
362 | free_local_storage = bpf_selem_unlink_storage_nolock( |
363 | local_storage, selem, uncharge_mem: true, reuse_now); |
364 | raw_spin_unlock_irqrestore(&local_storage->lock, flags); |
365 | |
366 | if (free_local_storage) |
367 | bpf_local_storage_free(local_storage, smap: storage_smap, bpf_ma, reuse_now); |
368 | } |
369 | |
370 | void bpf_selem_link_storage_nolock(struct bpf_local_storage *local_storage, |
371 | struct bpf_local_storage_elem *selem) |
372 | { |
373 | RCU_INIT_POINTER(selem->local_storage, local_storage); |
374 | hlist_add_head_rcu(n: &selem->snode, h: &local_storage->list); |
375 | } |
376 | |
377 | static void bpf_selem_unlink_map(struct bpf_local_storage_elem *selem) |
378 | { |
379 | struct bpf_local_storage_map *smap; |
380 | struct bpf_local_storage_map_bucket *b; |
381 | unsigned long flags; |
382 | |
383 | if (unlikely(!selem_linked_to_map_lockless(selem))) |
384 | /* selem has already be unlinked from smap */ |
385 | return; |
386 | |
387 | smap = rcu_dereference_check(SDATA(selem)->smap, bpf_rcu_lock_held()); |
388 | b = select_bucket(smap, selem); |
389 | raw_spin_lock_irqsave(&b->lock, flags); |
390 | if (likely(selem_linked_to_map(selem))) |
391 | hlist_del_init_rcu(n: &selem->map_node); |
392 | raw_spin_unlock_irqrestore(&b->lock, flags); |
393 | } |
394 | |
395 | void bpf_selem_link_map(struct bpf_local_storage_map *smap, |
396 | struct bpf_local_storage_elem *selem) |
397 | { |
398 | struct bpf_local_storage_map_bucket *b = select_bucket(smap, selem); |
399 | unsigned long flags; |
400 | |
401 | raw_spin_lock_irqsave(&b->lock, flags); |
402 | RCU_INIT_POINTER(SDATA(selem)->smap, smap); |
403 | hlist_add_head_rcu(n: &selem->map_node, h: &b->list); |
404 | raw_spin_unlock_irqrestore(&b->lock, flags); |
405 | } |
406 | |
407 | void bpf_selem_unlink(struct bpf_local_storage_elem *selem, bool reuse_now) |
408 | { |
409 | /* Always unlink from map before unlinking from local_storage |
410 | * because selem will be freed after successfully unlinked from |
411 | * the local_storage. |
412 | */ |
413 | bpf_selem_unlink_map(selem); |
414 | bpf_selem_unlink_storage(selem, reuse_now); |
415 | } |
416 | |
417 | void __bpf_local_storage_insert_cache(struct bpf_local_storage *local_storage, |
418 | struct bpf_local_storage_map *smap, |
419 | struct bpf_local_storage_elem *selem) |
420 | { |
421 | unsigned long flags; |
422 | |
423 | /* spinlock is needed to avoid racing with the |
424 | * parallel delete. Otherwise, publishing an already |
425 | * deleted sdata to the cache will become a use-after-free |
426 | * problem in the next bpf_local_storage_lookup(). |
427 | */ |
428 | raw_spin_lock_irqsave(&local_storage->lock, flags); |
429 | if (selem_linked_to_storage(selem)) |
430 | rcu_assign_pointer(local_storage->cache[smap->cache_idx], SDATA(selem)); |
431 | raw_spin_unlock_irqrestore(&local_storage->lock, flags); |
432 | } |
433 | |
434 | static int check_flags(const struct bpf_local_storage_data *old_sdata, |
435 | u64 map_flags) |
436 | { |
437 | if (old_sdata && (map_flags & ~BPF_F_LOCK) == BPF_NOEXIST) |
438 | /* elem already exists */ |
439 | return -EEXIST; |
440 | |
441 | if (!old_sdata && (map_flags & ~BPF_F_LOCK) == BPF_EXIST) |
442 | /* elem doesn't exist, cannot update it */ |
443 | return -ENOENT; |
444 | |
445 | return 0; |
446 | } |
447 | |
448 | int bpf_local_storage_alloc(void *owner, |
449 | struct bpf_local_storage_map *smap, |
450 | struct bpf_local_storage_elem *first_selem, |
451 | gfp_t gfp_flags) |
452 | { |
453 | struct bpf_local_storage *prev_storage, *storage; |
454 | struct bpf_local_storage **owner_storage_ptr; |
455 | int err; |
456 | |
457 | err = mem_charge(smap, owner, size: sizeof(*storage)); |
458 | if (err) |
459 | return err; |
460 | |
461 | if (smap->bpf_ma) { |
462 | migrate_disable(); |
463 | storage = bpf_mem_cache_alloc_flags(ma: &smap->storage_ma, flags: gfp_flags); |
464 | migrate_enable(); |
465 | } else { |
466 | storage = bpf_map_kzalloc(map: &smap->map, size: sizeof(*storage), |
467 | flags: gfp_flags | __GFP_NOWARN); |
468 | } |
469 | |
470 | if (!storage) { |
471 | err = -ENOMEM; |
472 | goto uncharge; |
473 | } |
474 | |
475 | RCU_INIT_POINTER(storage->smap, smap); |
476 | INIT_HLIST_HEAD(&storage->list); |
477 | raw_spin_lock_init(&storage->lock); |
478 | storage->owner = owner; |
479 | |
480 | bpf_selem_link_storage_nolock(local_storage: storage, selem: first_selem); |
481 | bpf_selem_link_map(smap, selem: first_selem); |
482 | |
483 | owner_storage_ptr = |
484 | (struct bpf_local_storage **)owner_storage(smap, owner); |
485 | /* Publish storage to the owner. |
486 | * Instead of using any lock of the kernel object (i.e. owner), |
487 | * cmpxchg will work with any kernel object regardless what |
488 | * the running context is, bh, irq...etc. |
489 | * |
490 | * From now on, the owner->storage pointer (e.g. sk->sk_bpf_storage) |
491 | * is protected by the storage->lock. Hence, when freeing |
492 | * the owner->storage, the storage->lock must be held before |
493 | * setting owner->storage ptr to NULL. |
494 | */ |
495 | prev_storage = cmpxchg(owner_storage_ptr, NULL, storage); |
496 | if (unlikely(prev_storage)) { |
497 | bpf_selem_unlink_map(selem: first_selem); |
498 | err = -EAGAIN; |
499 | goto uncharge; |
500 | |
501 | /* Note that even first_selem was linked to smap's |
502 | * bucket->list, first_selem can be freed immediately |
503 | * (instead of kfree_rcu) because |
504 | * bpf_local_storage_map_free() does a |
505 | * synchronize_rcu_mult (waiting for both sleepable and |
506 | * normal programs) before walking the bucket->list. |
507 | * Hence, no one is accessing selem from the |
508 | * bucket->list under rcu_read_lock(). |
509 | */ |
510 | } |
511 | |
512 | return 0; |
513 | |
514 | uncharge: |
515 | bpf_local_storage_free(local_storage: storage, smap, bpf_ma: smap->bpf_ma, reuse_now: true); |
516 | mem_uncharge(smap, owner, size: sizeof(*storage)); |
517 | return err; |
518 | } |
519 | |
520 | /* sk cannot be going away because it is linking new elem |
521 | * to sk->sk_bpf_storage. (i.e. sk->sk_refcnt cannot be 0). |
522 | * Otherwise, it will become a leak (and other memory issues |
523 | * during map destruction). |
524 | */ |
525 | struct bpf_local_storage_data * |
526 | bpf_local_storage_update(void *owner, struct bpf_local_storage_map *smap, |
527 | void *value, u64 map_flags, gfp_t gfp_flags) |
528 | { |
529 | struct bpf_local_storage_data *old_sdata = NULL; |
530 | struct bpf_local_storage_elem *alloc_selem, *selem = NULL; |
531 | struct bpf_local_storage *local_storage; |
532 | unsigned long flags; |
533 | int err; |
534 | |
535 | /* BPF_EXIST and BPF_NOEXIST cannot be both set */ |
536 | if (unlikely((map_flags & ~BPF_F_LOCK) > BPF_EXIST) || |
537 | /* BPF_F_LOCK can only be used in a value with spin_lock */ |
538 | unlikely((map_flags & BPF_F_LOCK) && |
539 | !btf_record_has_field(smap->map.record, BPF_SPIN_LOCK))) |
540 | return ERR_PTR(error: -EINVAL); |
541 | |
542 | if (gfp_flags == GFP_KERNEL && (map_flags & ~BPF_F_LOCK) != BPF_NOEXIST) |
543 | return ERR_PTR(error: -EINVAL); |
544 | |
545 | local_storage = rcu_dereference_check(*owner_storage(smap, owner), |
546 | bpf_rcu_lock_held()); |
547 | if (!local_storage || hlist_empty(h: &local_storage->list)) { |
548 | /* Very first elem for the owner */ |
549 | err = check_flags(NULL, map_flags); |
550 | if (err) |
551 | return ERR_PTR(error: err); |
552 | |
553 | selem = bpf_selem_alloc(smap, owner, value, charge_mem: true, gfp_flags); |
554 | if (!selem) |
555 | return ERR_PTR(error: -ENOMEM); |
556 | |
557 | err = bpf_local_storage_alloc(owner, smap, first_selem: selem, gfp_flags); |
558 | if (err) { |
559 | bpf_selem_free(selem, smap, reuse_now: true); |
560 | mem_uncharge(smap, owner, size: smap->elem_size); |
561 | return ERR_PTR(error: err); |
562 | } |
563 | |
564 | return SDATA(selem); |
565 | } |
566 | |
567 | if ((map_flags & BPF_F_LOCK) && !(map_flags & BPF_NOEXIST)) { |
568 | /* Hoping to find an old_sdata to do inline update |
569 | * such that it can avoid taking the local_storage->lock |
570 | * and changing the lists. |
571 | */ |
572 | old_sdata = |
573 | bpf_local_storage_lookup(local_storage, smap, cacheit_lockit: false); |
574 | err = check_flags(old_sdata, map_flags); |
575 | if (err) |
576 | return ERR_PTR(error: err); |
577 | if (old_sdata && selem_linked_to_storage_lockless(SELEM(old_sdata))) { |
578 | copy_map_value_locked(map: &smap->map, dst: old_sdata->data, |
579 | src: value, lock_src: false); |
580 | return old_sdata; |
581 | } |
582 | } |
583 | |
584 | /* A lookup has just been done before and concluded a new selem is |
585 | * needed. The chance of an unnecessary alloc is unlikely. |
586 | */ |
587 | alloc_selem = selem = bpf_selem_alloc(smap, owner, value, charge_mem: true, gfp_flags); |
588 | if (!alloc_selem) |
589 | return ERR_PTR(error: -ENOMEM); |
590 | |
591 | raw_spin_lock_irqsave(&local_storage->lock, flags); |
592 | |
593 | /* Recheck local_storage->list under local_storage->lock */ |
594 | if (unlikely(hlist_empty(&local_storage->list))) { |
595 | /* A parallel del is happening and local_storage is going |
596 | * away. It has just been checked before, so very |
597 | * unlikely. Return instead of retry to keep things |
598 | * simple. |
599 | */ |
600 | err = -EAGAIN; |
601 | goto unlock; |
602 | } |
603 | |
604 | old_sdata = bpf_local_storage_lookup(local_storage, smap, cacheit_lockit: false); |
605 | err = check_flags(old_sdata, map_flags); |
606 | if (err) |
607 | goto unlock; |
608 | |
609 | if (old_sdata && (map_flags & BPF_F_LOCK)) { |
610 | copy_map_value_locked(map: &smap->map, dst: old_sdata->data, src: value, |
611 | lock_src: false); |
612 | selem = SELEM(old_sdata); |
613 | goto unlock; |
614 | } |
615 | |
616 | alloc_selem = NULL; |
617 | /* First, link the new selem to the map */ |
618 | bpf_selem_link_map(smap, selem); |
619 | |
620 | /* Second, link (and publish) the new selem to local_storage */ |
621 | bpf_selem_link_storage_nolock(local_storage, selem); |
622 | |
623 | /* Third, remove old selem, SELEM(old_sdata) */ |
624 | if (old_sdata) { |
625 | bpf_selem_unlink_map(SELEM(old_sdata)); |
626 | bpf_selem_unlink_storage_nolock(local_storage, SELEM(old_sdata), |
627 | uncharge_mem: true, reuse_now: false); |
628 | } |
629 | |
630 | unlock: |
631 | raw_spin_unlock_irqrestore(&local_storage->lock, flags); |
632 | if (alloc_selem) { |
633 | mem_uncharge(smap, owner, size: smap->elem_size); |
634 | bpf_selem_free(selem: alloc_selem, smap, reuse_now: true); |
635 | } |
636 | return err ? ERR_PTR(error: err) : SDATA(selem); |
637 | } |
638 | |
639 | static u16 bpf_local_storage_cache_idx_get(struct bpf_local_storage_cache *cache) |
640 | { |
641 | u64 min_usage = U64_MAX; |
642 | u16 i, res = 0; |
643 | |
644 | spin_lock(lock: &cache->idx_lock); |
645 | |
646 | for (i = 0; i < BPF_LOCAL_STORAGE_CACHE_SIZE; i++) { |
647 | if (cache->idx_usage_counts[i] < min_usage) { |
648 | min_usage = cache->idx_usage_counts[i]; |
649 | res = i; |
650 | |
651 | /* Found a free cache_idx */ |
652 | if (!min_usage) |
653 | break; |
654 | } |
655 | } |
656 | cache->idx_usage_counts[res]++; |
657 | |
658 | spin_unlock(lock: &cache->idx_lock); |
659 | |
660 | return res; |
661 | } |
662 | |
663 | static void bpf_local_storage_cache_idx_free(struct bpf_local_storage_cache *cache, |
664 | u16 idx) |
665 | { |
666 | spin_lock(lock: &cache->idx_lock); |
667 | cache->idx_usage_counts[idx]--; |
668 | spin_unlock(lock: &cache->idx_lock); |
669 | } |
670 | |
671 | int bpf_local_storage_map_alloc_check(union bpf_attr *attr) |
672 | { |
673 | if (attr->map_flags & ~BPF_LOCAL_STORAGE_CREATE_FLAG_MASK || |
674 | !(attr->map_flags & BPF_F_NO_PREALLOC) || |
675 | attr->max_entries || |
676 | attr->key_size != sizeof(int) || !attr->value_size || |
677 | /* Enforce BTF for userspace sk dumping */ |
678 | !attr->btf_key_type_id || !attr->btf_value_type_id) |
679 | return -EINVAL; |
680 | |
681 | if (attr->value_size > BPF_LOCAL_STORAGE_MAX_VALUE_SIZE) |
682 | return -E2BIG; |
683 | |
684 | return 0; |
685 | } |
686 | |
687 | int bpf_local_storage_map_check_btf(const struct bpf_map *map, |
688 | const struct btf *btf, |
689 | const struct btf_type *key_type, |
690 | const struct btf_type *value_type) |
691 | { |
692 | u32 int_data; |
693 | |
694 | if (BTF_INFO_KIND(key_type->info) != BTF_KIND_INT) |
695 | return -EINVAL; |
696 | |
697 | int_data = *(u32 *)(key_type + 1); |
698 | if (BTF_INT_BITS(int_data) != 32 || BTF_INT_OFFSET(int_data)) |
699 | return -EINVAL; |
700 | |
701 | return 0; |
702 | } |
703 | |
704 | void bpf_local_storage_destroy(struct bpf_local_storage *local_storage) |
705 | { |
706 | struct bpf_local_storage_map *storage_smap; |
707 | struct bpf_local_storage_elem *selem; |
708 | bool bpf_ma, free_storage = false; |
709 | struct hlist_node *n; |
710 | unsigned long flags; |
711 | |
712 | storage_smap = rcu_dereference_check(local_storage->smap, bpf_rcu_lock_held()); |
713 | bpf_ma = check_storage_bpf_ma(local_storage, storage_smap, NULL); |
714 | |
715 | /* Neither the bpf_prog nor the bpf_map's syscall |
716 | * could be modifying the local_storage->list now. |
717 | * Thus, no elem can be added to or deleted from the |
718 | * local_storage->list by the bpf_prog or by the bpf_map's syscall. |
719 | * |
720 | * It is racing with bpf_local_storage_map_free() alone |
721 | * when unlinking elem from the local_storage->list and |
722 | * the map's bucket->list. |
723 | */ |
724 | raw_spin_lock_irqsave(&local_storage->lock, flags); |
725 | hlist_for_each_entry_safe(selem, n, &local_storage->list, snode) { |
726 | /* Always unlink from map before unlinking from |
727 | * local_storage. |
728 | */ |
729 | bpf_selem_unlink_map(selem); |
730 | /* If local_storage list has only one element, the |
731 | * bpf_selem_unlink_storage_nolock() will return true. |
732 | * Otherwise, it will return false. The current loop iteration |
733 | * intends to remove all local storage. So the last iteration |
734 | * of the loop will set the free_cgroup_storage to true. |
735 | */ |
736 | free_storage = bpf_selem_unlink_storage_nolock( |
737 | local_storage, selem, uncharge_mem: true, reuse_now: true); |
738 | } |
739 | raw_spin_unlock_irqrestore(&local_storage->lock, flags); |
740 | |
741 | if (free_storage) |
742 | bpf_local_storage_free(local_storage, smap: storage_smap, bpf_ma, reuse_now: true); |
743 | } |
744 | |
745 | u64 bpf_local_storage_map_mem_usage(const struct bpf_map *map) |
746 | { |
747 | struct bpf_local_storage_map *smap = (struct bpf_local_storage_map *)map; |
748 | u64 usage = sizeof(*smap); |
749 | |
750 | /* The dynamically callocated selems are not counted currently. */ |
751 | usage += sizeof(*smap->buckets) * (1ULL << smap->bucket_log); |
752 | return usage; |
753 | } |
754 | |
755 | /* When bpf_ma == true, the bpf_mem_alloc is used to allocate and free memory. |
756 | * A deadlock free allocator is useful for storage that the bpf prog can easily |
757 | * get a hold of the owner PTR_TO_BTF_ID in any context. eg. bpf_get_current_task_btf. |
758 | * The task and cgroup storage fall into this case. The bpf_mem_alloc reuses |
759 | * memory immediately. To be reuse-immediate safe, the owner destruction |
760 | * code path needs to go through a rcu grace period before calling |
761 | * bpf_local_storage_destroy(). |
762 | * |
763 | * When bpf_ma == false, the kmalloc and kfree are used. |
764 | */ |
765 | struct bpf_map * |
766 | bpf_local_storage_map_alloc(union bpf_attr *attr, |
767 | struct bpf_local_storage_cache *cache, |
768 | bool bpf_ma) |
769 | { |
770 | struct bpf_local_storage_map *smap; |
771 | unsigned int i; |
772 | u32 nbuckets; |
773 | int err; |
774 | |
775 | smap = bpf_map_area_alloc(size: sizeof(*smap), NUMA_NO_NODE); |
776 | if (!smap) |
777 | return ERR_PTR(error: -ENOMEM); |
778 | bpf_map_init_from_attr(map: &smap->map, attr); |
779 | |
780 | nbuckets = roundup_pow_of_two(num_possible_cpus()); |
781 | /* Use at least 2 buckets, select_bucket() is undefined behavior with 1 bucket */ |
782 | nbuckets = max_t(u32, 2, nbuckets); |
783 | smap->bucket_log = ilog2(nbuckets); |
784 | |
785 | smap->buckets = bpf_map_kvcalloc(map: &smap->map, n: sizeof(*smap->buckets), |
786 | size: nbuckets, GFP_USER | __GFP_NOWARN); |
787 | if (!smap->buckets) { |
788 | err = -ENOMEM; |
789 | goto free_smap; |
790 | } |
791 | |
792 | for (i = 0; i < nbuckets; i++) { |
793 | INIT_HLIST_HEAD(&smap->buckets[i].list); |
794 | raw_spin_lock_init(&smap->buckets[i].lock); |
795 | } |
796 | |
797 | smap->elem_size = offsetof(struct bpf_local_storage_elem, |
798 | sdata.data[attr->value_size]); |
799 | |
800 | smap->bpf_ma = bpf_ma; |
801 | if (bpf_ma) { |
802 | err = bpf_mem_alloc_init(ma: &smap->selem_ma, size: smap->elem_size, percpu: false); |
803 | if (err) |
804 | goto free_smap; |
805 | |
806 | err = bpf_mem_alloc_init(ma: &smap->storage_ma, size: sizeof(struct bpf_local_storage), percpu: false); |
807 | if (err) { |
808 | bpf_mem_alloc_destroy(ma: &smap->selem_ma); |
809 | goto free_smap; |
810 | } |
811 | } |
812 | |
813 | smap->cache_idx = bpf_local_storage_cache_idx_get(cache); |
814 | return &smap->map; |
815 | |
816 | free_smap: |
817 | kvfree(addr: smap->buckets); |
818 | bpf_map_area_free(base: smap); |
819 | return ERR_PTR(error: err); |
820 | } |
821 | |
822 | void bpf_local_storage_map_free(struct bpf_map *map, |
823 | struct bpf_local_storage_cache *cache, |
824 | int __percpu *busy_counter) |
825 | { |
826 | struct bpf_local_storage_map_bucket *b; |
827 | struct bpf_local_storage_elem *selem; |
828 | struct bpf_local_storage_map *smap; |
829 | unsigned int i; |
830 | |
831 | smap = (struct bpf_local_storage_map *)map; |
832 | bpf_local_storage_cache_idx_free(cache, idx: smap->cache_idx); |
833 | |
834 | /* Note that this map might be concurrently cloned from |
835 | * bpf_sk_storage_clone. Wait for any existing bpf_sk_storage_clone |
836 | * RCU read section to finish before proceeding. New RCU |
837 | * read sections should be prevented via bpf_map_inc_not_zero. |
838 | */ |
839 | synchronize_rcu(); |
840 | |
841 | /* bpf prog and the userspace can no longer access this map |
842 | * now. No new selem (of this map) can be added |
843 | * to the owner->storage or to the map bucket's list. |
844 | * |
845 | * The elem of this map can be cleaned up here |
846 | * or when the storage is freed e.g. |
847 | * by bpf_sk_storage_free() during __sk_destruct(). |
848 | */ |
849 | for (i = 0; i < (1U << smap->bucket_log); i++) { |
850 | b = &smap->buckets[i]; |
851 | |
852 | rcu_read_lock(); |
853 | /* No one is adding to b->list now */ |
854 | while ((selem = hlist_entry_safe( |
855 | rcu_dereference_raw(hlist_first_rcu(&b->list)), |
856 | struct bpf_local_storage_elem, map_node))) { |
857 | if (busy_counter) { |
858 | migrate_disable(); |
859 | this_cpu_inc(*busy_counter); |
860 | } |
861 | bpf_selem_unlink(selem, reuse_now: true); |
862 | if (busy_counter) { |
863 | this_cpu_dec(*busy_counter); |
864 | migrate_enable(); |
865 | } |
866 | cond_resched_rcu(); |
867 | } |
868 | rcu_read_unlock(); |
869 | } |
870 | |
871 | /* While freeing the storage we may still need to access the map. |
872 | * |
873 | * e.g. when bpf_sk_storage_free() has unlinked selem from the map |
874 | * which then made the above while((selem = ...)) loop |
875 | * exit immediately. |
876 | * |
877 | * However, while freeing the storage one still needs to access the |
878 | * smap->elem_size to do the uncharging in |
879 | * bpf_selem_unlink_storage_nolock(). |
880 | * |
881 | * Hence, wait another rcu grace period for the storage to be freed. |
882 | */ |
883 | synchronize_rcu(); |
884 | |
885 | if (smap->bpf_ma) { |
886 | bpf_mem_alloc_destroy(ma: &smap->selem_ma); |
887 | bpf_mem_alloc_destroy(ma: &smap->storage_ma); |
888 | } |
889 | kvfree(addr: smap->buckets); |
890 | bpf_map_area_free(base: smap); |
891 | } |
892 | |