1 /* Copyright (c) 2011-2014 PLUMgrid, http://plumgrid.com
2 * Copyright (c) 2016 Facebook
4 * This program is free software; you can redistribute it and/or
5 * modify it under the terms of version 2 of the GNU General Public
6 * License as published by the Free Software Foundation.
8 * This program is distributed in the hope that it will be useful, but
9 * WITHOUT ANY WARRANTY; without even the implied warranty of
10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
11 * General Public License for more details.
13 #include <linux/bpf.h>
14 #include <linux/jhash.h>
15 #include <linux/filter.h>
16 #include <linux/rculist_nulls.h>
17 #include "percpu_freelist.h"
18 #include "bpf_lru_list.h"
19 #include "map_in_map.h"
21 #define HTAB_CREATE_FLAG_MASK \
22 (BPF_F_NO_PREALLOC | BPF_F_NO_COMMON_LRU | BPF_F_NUMA_NODE | \
23 BPF_F_RDONLY | BPF_F_WRONLY)
26 struct hlist_nulls_head head
;
32 struct bucket
*buckets
;
35 struct pcpu_freelist freelist
;
38 struct htab_elem
*__percpu
*extra_elems
;
39 atomic_t count
; /* number of elements in this hashtable */
40 u32 n_buckets
; /* number of hash buckets */
41 u32 elem_size
; /* size of each element in bytes */
44 /* each htab element is struct htab_elem + key + value */
47 struct hlist_nulls_node hash_node
;
51 struct bpf_htab
*htab
;
52 struct pcpu_freelist_node fnode
;
58 struct bpf_lru_node lru_node
;
61 char key
[0] __aligned(8);
64 static bool htab_lru_map_delete_node(void *arg
, struct bpf_lru_node
*node
);
66 static bool htab_is_lru(const struct bpf_htab
*htab
)
68 return htab
->map
.map_type
== BPF_MAP_TYPE_LRU_HASH
||
69 htab
->map
.map_type
== BPF_MAP_TYPE_LRU_PERCPU_HASH
;
72 static bool htab_is_percpu(const struct bpf_htab
*htab
)
74 return htab
->map
.map_type
== BPF_MAP_TYPE_PERCPU_HASH
||
75 htab
->map
.map_type
== BPF_MAP_TYPE_LRU_PERCPU_HASH
;
78 static bool htab_is_prealloc(const struct bpf_htab
*htab
)
80 return !(htab
->map
.map_flags
& BPF_F_NO_PREALLOC
);
83 static inline void htab_elem_set_ptr(struct htab_elem
*l
, u32 key_size
,
86 *(void __percpu
**)(l
->key
+ key_size
) = pptr
;
89 static inline void __percpu
*htab_elem_get_ptr(struct htab_elem
*l
, u32 key_size
)
91 return *(void __percpu
**)(l
->key
+ key_size
);
94 static void *fd_htab_map_get_ptr(const struct bpf_map
*map
, struct htab_elem
*l
)
96 return *(void **)(l
->key
+ roundup(map
->key_size
, 8));
99 static struct htab_elem
*get_htab_elem(struct bpf_htab
*htab
, int i
)
101 return (struct htab_elem
*) (htab
->elems
+ i
* htab
->elem_size
);
104 static void htab_free_elems(struct bpf_htab
*htab
)
108 if (!htab_is_percpu(htab
))
111 for (i
= 0; i
< htab
->map
.max_entries
; i
++) {
114 pptr
= htab_elem_get_ptr(get_htab_elem(htab
, i
),
120 bpf_map_area_free(htab
->elems
);
123 static struct htab_elem
*prealloc_lru_pop(struct bpf_htab
*htab
, void *key
,
126 struct bpf_lru_node
*node
= bpf_lru_pop_free(&htab
->lru
, hash
);
130 l
= container_of(node
, struct htab_elem
, lru_node
);
131 memcpy(l
->key
, key
, htab
->map
.key_size
);
138 static int prealloc_init(struct bpf_htab
*htab
)
140 u32 num_entries
= htab
->map
.max_entries
;
141 int err
= -ENOMEM
, i
;
143 if (!htab_is_percpu(htab
) && !htab_is_lru(htab
))
144 num_entries
+= num_possible_cpus();
146 htab
->elems
= bpf_map_area_alloc(htab
->elem_size
* num_entries
,
147 htab
->map
.numa_node
);
151 if (!htab_is_percpu(htab
))
152 goto skip_percpu_elems
;
154 for (i
= 0; i
< num_entries
; i
++) {
155 u32 size
= round_up(htab
->map
.value_size
, 8);
158 pptr
= __alloc_percpu_gfp(size
, 8, GFP_USER
| __GFP_NOWARN
);
161 htab_elem_set_ptr(get_htab_elem(htab
, i
), htab
->map
.key_size
,
167 if (htab_is_lru(htab
))
168 err
= bpf_lru_init(&htab
->lru
,
169 htab
->map
.map_flags
& BPF_F_NO_COMMON_LRU
,
170 offsetof(struct htab_elem
, hash
) -
171 offsetof(struct htab_elem
, lru_node
),
172 htab_lru_map_delete_node
,
175 err
= pcpu_freelist_init(&htab
->freelist
);
180 if (htab_is_lru(htab
))
181 bpf_lru_populate(&htab
->lru
, htab
->elems
,
182 offsetof(struct htab_elem
, lru_node
),
183 htab
->elem_size
, num_entries
);
185 pcpu_freelist_populate(&htab
->freelist
,
186 htab
->elems
+ offsetof(struct htab_elem
, fnode
),
187 htab
->elem_size
, num_entries
);
192 htab_free_elems(htab
);
196 static void prealloc_destroy(struct bpf_htab
*htab
)
198 htab_free_elems(htab
);
200 if (htab_is_lru(htab
))
201 bpf_lru_destroy(&htab
->lru
);
203 pcpu_freelist_destroy(&htab
->freelist
);
206 static int alloc_extra_elems(struct bpf_htab
*htab
)
208 struct htab_elem
*__percpu
*pptr
, *l_new
;
209 struct pcpu_freelist_node
*l
;
212 pptr
= __alloc_percpu_gfp(sizeof(struct htab_elem
*), 8,
213 GFP_USER
| __GFP_NOWARN
);
217 for_each_possible_cpu(cpu
) {
218 l
= pcpu_freelist_pop(&htab
->freelist
);
219 /* pop will succeed, since prealloc_init()
220 * preallocated extra num_possible_cpus elements
222 l_new
= container_of(l
, struct htab_elem
, fnode
);
223 *per_cpu_ptr(pptr
, cpu
) = l_new
;
225 htab
->extra_elems
= pptr
;
229 /* Called from syscall */
230 static struct bpf_map
*htab_map_alloc(union bpf_attr
*attr
)
232 bool percpu
= (attr
->map_type
== BPF_MAP_TYPE_PERCPU_HASH
||
233 attr
->map_type
== BPF_MAP_TYPE_LRU_PERCPU_HASH
);
234 bool lru
= (attr
->map_type
== BPF_MAP_TYPE_LRU_HASH
||
235 attr
->map_type
== BPF_MAP_TYPE_LRU_PERCPU_HASH
);
236 /* percpu_lru means each cpu has its own LRU list.
237 * it is different from BPF_MAP_TYPE_PERCPU_HASH where
238 * the map's value itself is percpu. percpu_lru has
239 * nothing to do with the map's value.
241 bool percpu_lru
= (attr
->map_flags
& BPF_F_NO_COMMON_LRU
);
242 bool prealloc
= !(attr
->map_flags
& BPF_F_NO_PREALLOC
);
243 int numa_node
= bpf_map_attr_numa_node(attr
);
244 struct bpf_htab
*htab
;
248 BUILD_BUG_ON(offsetof(struct htab_elem
, htab
) !=
249 offsetof(struct htab_elem
, hash_node
.pprev
));
250 BUILD_BUG_ON(offsetof(struct htab_elem
, fnode
.next
) !=
251 offsetof(struct htab_elem
, hash_node
.pprev
));
253 if (lru
&& !capable(CAP_SYS_ADMIN
))
254 /* LRU implementation is much complicated than other
255 * maps. Hence, limit to CAP_SYS_ADMIN for now.
257 return ERR_PTR(-EPERM
);
259 if (attr
->map_flags
& ~HTAB_CREATE_FLAG_MASK
)
260 /* reserved bits should not be used */
261 return ERR_PTR(-EINVAL
);
263 if (!lru
&& percpu_lru
)
264 return ERR_PTR(-EINVAL
);
266 if (lru
&& !prealloc
)
267 return ERR_PTR(-ENOTSUPP
);
269 if (numa_node
!= NUMA_NO_NODE
&& (percpu
|| percpu_lru
))
270 return ERR_PTR(-EINVAL
);
272 htab
= kzalloc(sizeof(*htab
), GFP_USER
);
274 return ERR_PTR(-ENOMEM
);
276 /* mandatory map attributes */
277 htab
->map
.map_type
= attr
->map_type
;
278 htab
->map
.key_size
= attr
->key_size
;
279 htab
->map
.value_size
= attr
->value_size
;
280 htab
->map
.max_entries
= attr
->max_entries
;
281 htab
->map
.map_flags
= attr
->map_flags
;
282 htab
->map
.numa_node
= numa_node
;
284 /* check sanity of attributes.
285 * value_size == 0 may be allowed in the future to use map as a set
288 if (htab
->map
.max_entries
== 0 || htab
->map
.key_size
== 0 ||
289 htab
->map
.value_size
== 0)
293 /* ensure each CPU's lru list has >=1 elements.
294 * since we are at it, make each lru list has the same
295 * number of elements.
297 htab
->map
.max_entries
= roundup(attr
->max_entries
,
298 num_possible_cpus());
299 if (htab
->map
.max_entries
< attr
->max_entries
)
300 htab
->map
.max_entries
= rounddown(attr
->max_entries
,
301 num_possible_cpus());
304 /* hash table size must be power of 2 */
305 htab
->n_buckets
= roundup_pow_of_two(htab
->map
.max_entries
);
308 if (htab
->map
.key_size
> MAX_BPF_STACK
)
309 /* eBPF programs initialize keys on stack, so they cannot be
310 * larger than max stack size
314 if (htab
->map
.value_size
>= KMALLOC_MAX_SIZE
-
315 MAX_BPF_STACK
- sizeof(struct htab_elem
))
316 /* if value_size is bigger, the user space won't be able to
317 * access the elements via bpf syscall. This check also makes
318 * sure that the elem_size doesn't overflow and it's
319 * kmalloc-able later in htab_map_update_elem()
323 htab
->elem_size
= sizeof(struct htab_elem
) +
324 round_up(htab
->map
.key_size
, 8);
326 htab
->elem_size
+= sizeof(void *);
328 htab
->elem_size
+= round_up(htab
->map
.value_size
, 8);
330 /* prevent zero size kmalloc and check for u32 overflow */
331 if (htab
->n_buckets
== 0 ||
332 htab
->n_buckets
> U32_MAX
/ sizeof(struct bucket
))
335 cost
= (u64
) htab
->n_buckets
* sizeof(struct bucket
) +
336 (u64
) htab
->elem_size
* htab
->map
.max_entries
;
339 cost
+= (u64
) round_up(htab
->map
.value_size
, 8) *
340 num_possible_cpus() * htab
->map
.max_entries
;
342 cost
+= (u64
) htab
->elem_size
* num_possible_cpus();
344 if (cost
>= U32_MAX
- PAGE_SIZE
)
345 /* make sure page count doesn't overflow */
348 htab
->map
.pages
= round_up(cost
, PAGE_SIZE
) >> PAGE_SHIFT
;
350 /* if map size is larger than memlock limit, reject it early */
351 err
= bpf_map_precharge_memlock(htab
->map
.pages
);
356 htab
->buckets
= bpf_map_area_alloc(htab
->n_buckets
*
357 sizeof(struct bucket
),
358 htab
->map
.numa_node
);
362 for (i
= 0; i
< htab
->n_buckets
; i
++) {
363 INIT_HLIST_NULLS_HEAD(&htab
->buckets
[i
].head
, i
);
364 raw_spin_lock_init(&htab
->buckets
[i
].lock
);
368 err
= prealloc_init(htab
);
372 if (!percpu
&& !lru
) {
373 /* lru itself can remove the least used element, so
374 * there is no need for an extra elem during map_update.
376 err
= alloc_extra_elems(htab
);
385 prealloc_destroy(htab
);
387 bpf_map_area_free(htab
->buckets
);
393 static inline u32
htab_map_hash(const void *key
, u32 key_len
)
395 return jhash(key
, key_len
, 0);
398 static inline struct bucket
*__select_bucket(struct bpf_htab
*htab
, u32 hash
)
400 return &htab
->buckets
[hash
& (htab
->n_buckets
- 1)];
403 static inline struct hlist_nulls_head
*select_bucket(struct bpf_htab
*htab
, u32 hash
)
405 return &__select_bucket(htab
, hash
)->head
;
408 /* this lookup function can only be called with bucket lock taken */
409 static struct htab_elem
*lookup_elem_raw(struct hlist_nulls_head
*head
, u32 hash
,
410 void *key
, u32 key_size
)
412 struct hlist_nulls_node
*n
;
415 hlist_nulls_for_each_entry_rcu(l
, n
, head
, hash_node
)
416 if (l
->hash
== hash
&& !memcmp(&l
->key
, key
, key_size
))
422 /* can be called without bucket lock. it will repeat the loop in
423 * the unlikely event when elements moved from one bucket into another
424 * while link list is being walked
426 static struct htab_elem
*lookup_nulls_elem_raw(struct hlist_nulls_head
*head
,
428 u32 key_size
, u32 n_buckets
)
430 struct hlist_nulls_node
*n
;
434 hlist_nulls_for_each_entry_rcu(l
, n
, head
, hash_node
)
435 if (l
->hash
== hash
&& !memcmp(&l
->key
, key
, key_size
))
438 if (unlikely(get_nulls_value(n
) != (hash
& (n_buckets
- 1))))
444 /* Called from syscall or from eBPF program directly, so
445 * arguments have to match bpf_map_lookup_elem() exactly.
446 * The return value is adjusted by BPF instructions
447 * in htab_map_gen_lookup().
449 static void *__htab_map_lookup_elem(struct bpf_map
*map
, void *key
)
451 struct bpf_htab
*htab
= container_of(map
, struct bpf_htab
, map
);
452 struct hlist_nulls_head
*head
;
456 /* Must be called with rcu_read_lock. */
457 WARN_ON_ONCE(!rcu_read_lock_held());
459 key_size
= map
->key_size
;
461 hash
= htab_map_hash(key
, key_size
);
463 head
= select_bucket(htab
, hash
);
465 l
= lookup_nulls_elem_raw(head
, hash
, key
, key_size
, htab
->n_buckets
);
470 static void *htab_map_lookup_elem(struct bpf_map
*map
, void *key
)
472 struct htab_elem
*l
= __htab_map_lookup_elem(map
, key
);
475 return l
->key
+ round_up(map
->key_size
, 8);
480 /* inline bpf_map_lookup_elem() call.
483 * bpf_map_lookup_elem
484 * map->ops->map_lookup_elem
485 * htab_map_lookup_elem
486 * __htab_map_lookup_elem
489 * __htab_map_lookup_elem
491 static u32
htab_map_gen_lookup(struct bpf_map
*map
, struct bpf_insn
*insn_buf
)
493 struct bpf_insn
*insn
= insn_buf
;
494 const int ret
= BPF_REG_0
;
496 *insn
++ = BPF_EMIT_CALL((u64 (*)(u64
, u64
, u64
, u64
, u64
))__htab_map_lookup_elem
);
497 *insn
++ = BPF_JMP_IMM(BPF_JEQ
, ret
, 0, 1);
498 *insn
++ = BPF_ALU64_IMM(BPF_ADD
, ret
,
499 offsetof(struct htab_elem
, key
) +
500 round_up(map
->key_size
, 8));
501 return insn
- insn_buf
;
504 static void *htab_lru_map_lookup_elem(struct bpf_map
*map
, void *key
)
506 struct htab_elem
*l
= __htab_map_lookup_elem(map
, key
);
509 bpf_lru_node_set_ref(&l
->lru_node
);
510 return l
->key
+ round_up(map
->key_size
, 8);
516 static u32
htab_lru_map_gen_lookup(struct bpf_map
*map
,
517 struct bpf_insn
*insn_buf
)
519 struct bpf_insn
*insn
= insn_buf
;
520 const int ret
= BPF_REG_0
;
521 const int ref_reg
= BPF_REG_1
;
523 *insn
++ = BPF_EMIT_CALL((u64 (*)(u64
, u64
, u64
, u64
, u64
))__htab_map_lookup_elem
);
524 *insn
++ = BPF_JMP_IMM(BPF_JEQ
, ret
, 0, 4);
525 *insn
++ = BPF_LDX_MEM(BPF_B
, ref_reg
, ret
,
526 offsetof(struct htab_elem
, lru_node
) +
527 offsetof(struct bpf_lru_node
, ref
));
528 *insn
++ = BPF_JMP_IMM(BPF_JNE
, ref_reg
, 0, 1);
529 *insn
++ = BPF_ST_MEM(BPF_B
, ret
,
530 offsetof(struct htab_elem
, lru_node
) +
531 offsetof(struct bpf_lru_node
, ref
),
533 *insn
++ = BPF_ALU64_IMM(BPF_ADD
, ret
,
534 offsetof(struct htab_elem
, key
) +
535 round_up(map
->key_size
, 8));
536 return insn
- insn_buf
;
539 /* It is called from the bpf_lru_list when the LRU needs to delete
540 * older elements from the htab.
542 static bool htab_lru_map_delete_node(void *arg
, struct bpf_lru_node
*node
)
544 struct bpf_htab
*htab
= (struct bpf_htab
*)arg
;
545 struct htab_elem
*l
= NULL
, *tgt_l
;
546 struct hlist_nulls_head
*head
;
547 struct hlist_nulls_node
*n
;
551 tgt_l
= container_of(node
, struct htab_elem
, lru_node
);
552 b
= __select_bucket(htab
, tgt_l
->hash
);
555 raw_spin_lock_irqsave(&b
->lock
, flags
);
557 hlist_nulls_for_each_entry_rcu(l
, n
, head
, hash_node
)
559 hlist_nulls_del_rcu(&l
->hash_node
);
563 raw_spin_unlock_irqrestore(&b
->lock
, flags
);
568 /* Called from syscall */
569 static int htab_map_get_next_key(struct bpf_map
*map
, void *key
, void *next_key
)
571 struct bpf_htab
*htab
= container_of(map
, struct bpf_htab
, map
);
572 struct hlist_nulls_head
*head
;
573 struct htab_elem
*l
, *next_l
;
577 WARN_ON_ONCE(!rcu_read_lock_held());
579 key_size
= map
->key_size
;
582 goto find_first_elem
;
584 hash
= htab_map_hash(key
, key_size
);
586 head
= select_bucket(htab
, hash
);
589 l
= lookup_nulls_elem_raw(head
, hash
, key
, key_size
, htab
->n_buckets
);
592 goto find_first_elem
;
594 /* key was found, get next key in the same bucket */
595 next_l
= hlist_nulls_entry_safe(rcu_dereference_raw(hlist_nulls_next_rcu(&l
->hash_node
)),
596 struct htab_elem
, hash_node
);
599 /* if next elem in this hash list is non-zero, just return it */
600 memcpy(next_key
, next_l
->key
, key_size
);
604 /* no more elements in this hash list, go to the next bucket */
605 i
= hash
& (htab
->n_buckets
- 1);
609 /* iterate over buckets */
610 for (; i
< htab
->n_buckets
; i
++) {
611 head
= select_bucket(htab
, i
);
613 /* pick first element in the bucket */
614 next_l
= hlist_nulls_entry_safe(rcu_dereference_raw(hlist_nulls_first_rcu(head
)),
615 struct htab_elem
, hash_node
);
617 /* if it's not empty, just return it */
618 memcpy(next_key
, next_l
->key
, key_size
);
623 /* iterated over all buckets and all elements */
627 static void htab_elem_free(struct bpf_htab
*htab
, struct htab_elem
*l
)
629 if (htab
->map
.map_type
== BPF_MAP_TYPE_PERCPU_HASH
)
630 free_percpu(htab_elem_get_ptr(l
, htab
->map
.key_size
));
634 static void htab_elem_free_rcu(struct rcu_head
*head
)
636 struct htab_elem
*l
= container_of(head
, struct htab_elem
, rcu
);
637 struct bpf_htab
*htab
= l
->htab
;
639 /* must increment bpf_prog_active to avoid kprobe+bpf triggering while
640 * we're calling kfree, otherwise deadlock is possible if kprobes
641 * are placed somewhere inside of slub
644 __this_cpu_inc(bpf_prog_active
);
645 htab_elem_free(htab
, l
);
646 __this_cpu_dec(bpf_prog_active
);
650 static void free_htab_elem(struct bpf_htab
*htab
, struct htab_elem
*l
)
652 struct bpf_map
*map
= &htab
->map
;
654 if (map
->ops
->map_fd_put_ptr
) {
655 void *ptr
= fd_htab_map_get_ptr(map
, l
);
657 map
->ops
->map_fd_put_ptr(ptr
);
660 if (htab_is_prealloc(htab
)) {
661 pcpu_freelist_push(&htab
->freelist
, &l
->fnode
);
663 atomic_dec(&htab
->count
);
665 call_rcu(&l
->rcu
, htab_elem_free_rcu
);
669 static void pcpu_copy_value(struct bpf_htab
*htab
, void __percpu
*pptr
,
670 void *value
, bool onallcpus
)
673 /* copy true value_size bytes */
674 memcpy(this_cpu_ptr(pptr
), value
, htab
->map
.value_size
);
676 u32 size
= round_up(htab
->map
.value_size
, 8);
679 for_each_possible_cpu(cpu
) {
680 bpf_long_memcpy(per_cpu_ptr(pptr
, cpu
),
687 static bool fd_htab_map_needs_adjust(const struct bpf_htab
*htab
)
689 return htab
->map
.map_type
== BPF_MAP_TYPE_HASH_OF_MAPS
&&
693 static u32
htab_size_value(const struct bpf_htab
*htab
, bool percpu
)
695 u32 size
= htab
->map
.value_size
;
697 if (percpu
|| fd_htab_map_needs_adjust(htab
))
698 size
= round_up(size
, 8);
702 static struct htab_elem
*alloc_htab_elem(struct bpf_htab
*htab
, void *key
,
703 void *value
, u32 key_size
, u32 hash
,
704 bool percpu
, bool onallcpus
,
705 struct htab_elem
*old_elem
)
707 u32 size
= htab_size_value(htab
, percpu
);
708 bool prealloc
= htab_is_prealloc(htab
);
709 struct htab_elem
*l_new
, **pl_new
;
714 /* if we're updating the existing element,
715 * use per-cpu extra elems to avoid freelist_pop/push
717 pl_new
= this_cpu_ptr(htab
->extra_elems
);
721 struct pcpu_freelist_node
*l
;
723 l
= pcpu_freelist_pop(&htab
->freelist
);
725 return ERR_PTR(-E2BIG
);
726 l_new
= container_of(l
, struct htab_elem
, fnode
);
729 if (atomic_inc_return(&htab
->count
) > htab
->map
.max_entries
)
731 /* when map is full and update() is replacing
732 * old element, it's ok to allocate, since
733 * old element will be freed immediately.
734 * Otherwise return an error
736 atomic_dec(&htab
->count
);
737 return ERR_PTR(-E2BIG
);
739 l_new
= kmalloc_node(htab
->elem_size
, GFP_ATOMIC
| __GFP_NOWARN
,
740 htab
->map
.numa_node
);
742 return ERR_PTR(-ENOMEM
);
745 memcpy(l_new
->key
, key
, key_size
);
748 pptr
= htab_elem_get_ptr(l_new
, key_size
);
750 /* alloc_percpu zero-fills */
751 pptr
= __alloc_percpu_gfp(size
, 8,
752 GFP_ATOMIC
| __GFP_NOWARN
);
755 return ERR_PTR(-ENOMEM
);
759 pcpu_copy_value(htab
, pptr
, value
, onallcpus
);
762 htab_elem_set_ptr(l_new
, key_size
, pptr
);
764 memcpy(l_new
->key
+ round_up(key_size
, 8), value
, size
);
771 static int check_flags(struct bpf_htab
*htab
, struct htab_elem
*l_old
,
774 if (l_old
&& map_flags
== BPF_NOEXIST
)
775 /* elem already exists */
778 if (!l_old
&& map_flags
== BPF_EXIST
)
779 /* elem doesn't exist, cannot update it */
785 /* Called from syscall or from eBPF program */
786 static int htab_map_update_elem(struct bpf_map
*map
, void *key
, void *value
,
789 struct bpf_htab
*htab
= container_of(map
, struct bpf_htab
, map
);
790 struct htab_elem
*l_new
= NULL
, *l_old
;
791 struct hlist_nulls_head
*head
;
797 if (unlikely(map_flags
> BPF_EXIST
))
801 WARN_ON_ONCE(!rcu_read_lock_held());
803 key_size
= map
->key_size
;
805 hash
= htab_map_hash(key
, key_size
);
807 b
= __select_bucket(htab
, hash
);
810 /* bpf_map_update_elem() can be called in_irq() */
811 raw_spin_lock_irqsave(&b
->lock
, flags
);
813 l_old
= lookup_elem_raw(head
, hash
, key
, key_size
);
815 ret
= check_flags(htab
, l_old
, map_flags
);
819 l_new
= alloc_htab_elem(htab
, key
, value
, key_size
, hash
, false, false,
822 /* all pre-allocated elements are in use or memory exhausted */
823 ret
= PTR_ERR(l_new
);
827 /* add new element to the head of the list, so that
828 * concurrent search will find it before old elem
830 hlist_nulls_add_head_rcu(&l_new
->hash_node
, head
);
832 hlist_nulls_del_rcu(&l_old
->hash_node
);
833 if (!htab_is_prealloc(htab
))
834 free_htab_elem(htab
, l_old
);
838 raw_spin_unlock_irqrestore(&b
->lock
, flags
);
842 static int htab_lru_map_update_elem(struct bpf_map
*map
, void *key
, void *value
,
845 struct bpf_htab
*htab
= container_of(map
, struct bpf_htab
, map
);
846 struct htab_elem
*l_new
, *l_old
= NULL
;
847 struct hlist_nulls_head
*head
;
853 if (unlikely(map_flags
> BPF_EXIST
))
857 WARN_ON_ONCE(!rcu_read_lock_held());
859 key_size
= map
->key_size
;
861 hash
= htab_map_hash(key
, key_size
);
863 b
= __select_bucket(htab
, hash
);
866 /* For LRU, we need to alloc before taking bucket's
867 * spinlock because getting free nodes from LRU may need
868 * to remove older elements from htab and this removal
869 * operation will need a bucket lock.
871 l_new
= prealloc_lru_pop(htab
, key
, hash
);
874 memcpy(l_new
->key
+ round_up(map
->key_size
, 8), value
, map
->value_size
);
876 /* bpf_map_update_elem() can be called in_irq() */
877 raw_spin_lock_irqsave(&b
->lock
, flags
);
879 l_old
= lookup_elem_raw(head
, hash
, key
, key_size
);
881 ret
= check_flags(htab
, l_old
, map_flags
);
885 /* add new element to the head of the list, so that
886 * concurrent search will find it before old elem
888 hlist_nulls_add_head_rcu(&l_new
->hash_node
, head
);
890 bpf_lru_node_set_ref(&l_new
->lru_node
);
891 hlist_nulls_del_rcu(&l_old
->hash_node
);
896 raw_spin_unlock_irqrestore(&b
->lock
, flags
);
899 bpf_lru_push_free(&htab
->lru
, &l_new
->lru_node
);
901 bpf_lru_push_free(&htab
->lru
, &l_old
->lru_node
);
906 static int __htab_percpu_map_update_elem(struct bpf_map
*map
, void *key
,
907 void *value
, u64 map_flags
,
910 struct bpf_htab
*htab
= container_of(map
, struct bpf_htab
, map
);
911 struct htab_elem
*l_new
= NULL
, *l_old
;
912 struct hlist_nulls_head
*head
;
918 if (unlikely(map_flags
> BPF_EXIST
))
922 WARN_ON_ONCE(!rcu_read_lock_held());
924 key_size
= map
->key_size
;
926 hash
= htab_map_hash(key
, key_size
);
928 b
= __select_bucket(htab
, hash
);
931 /* bpf_map_update_elem() can be called in_irq() */
932 raw_spin_lock_irqsave(&b
->lock
, flags
);
934 l_old
= lookup_elem_raw(head
, hash
, key
, key_size
);
936 ret
= check_flags(htab
, l_old
, map_flags
);
941 /* per-cpu hash map can update value in-place */
942 pcpu_copy_value(htab
, htab_elem_get_ptr(l_old
, key_size
),
945 l_new
= alloc_htab_elem(htab
, key
, value
, key_size
,
946 hash
, true, onallcpus
, NULL
);
948 ret
= PTR_ERR(l_new
);
951 hlist_nulls_add_head_rcu(&l_new
->hash_node
, head
);
955 raw_spin_unlock_irqrestore(&b
->lock
, flags
);
959 static int __htab_lru_percpu_map_update_elem(struct bpf_map
*map
, void *key
,
960 void *value
, u64 map_flags
,
963 struct bpf_htab
*htab
= container_of(map
, struct bpf_htab
, map
);
964 struct htab_elem
*l_new
= NULL
, *l_old
;
965 struct hlist_nulls_head
*head
;
971 if (unlikely(map_flags
> BPF_EXIST
))
975 WARN_ON_ONCE(!rcu_read_lock_held());
977 key_size
= map
->key_size
;
979 hash
= htab_map_hash(key
, key_size
);
981 b
= __select_bucket(htab
, hash
);
984 /* For LRU, we need to alloc before taking bucket's
985 * spinlock because LRU's elem alloc may need
986 * to remove older elem from htab and this removal
987 * operation will need a bucket lock.
989 if (map_flags
!= BPF_EXIST
) {
990 l_new
= prealloc_lru_pop(htab
, key
, hash
);
995 /* bpf_map_update_elem() can be called in_irq() */
996 raw_spin_lock_irqsave(&b
->lock
, flags
);
998 l_old
= lookup_elem_raw(head
, hash
, key
, key_size
);
1000 ret
= check_flags(htab
, l_old
, map_flags
);
1005 bpf_lru_node_set_ref(&l_old
->lru_node
);
1007 /* per-cpu hash map can update value in-place */
1008 pcpu_copy_value(htab
, htab_elem_get_ptr(l_old
, key_size
),
1011 pcpu_copy_value(htab
, htab_elem_get_ptr(l_new
, key_size
),
1013 hlist_nulls_add_head_rcu(&l_new
->hash_node
, head
);
1018 raw_spin_unlock_irqrestore(&b
->lock
, flags
);
1020 bpf_lru_push_free(&htab
->lru
, &l_new
->lru_node
);
1024 static int htab_percpu_map_update_elem(struct bpf_map
*map
, void *key
,
1025 void *value
, u64 map_flags
)
1027 return __htab_percpu_map_update_elem(map
, key
, value
, map_flags
, false);
1030 static int htab_lru_percpu_map_update_elem(struct bpf_map
*map
, void *key
,
1031 void *value
, u64 map_flags
)
1033 return __htab_lru_percpu_map_update_elem(map
, key
, value
, map_flags
,
1037 /* Called from syscall or from eBPF program */
1038 static int htab_map_delete_elem(struct bpf_map
*map
, void *key
)
1040 struct bpf_htab
*htab
= container_of(map
, struct bpf_htab
, map
);
1041 struct hlist_nulls_head
*head
;
1043 struct htab_elem
*l
;
1044 unsigned long flags
;
1048 WARN_ON_ONCE(!rcu_read_lock_held());
1050 key_size
= map
->key_size
;
1052 hash
= htab_map_hash(key
, key_size
);
1053 b
= __select_bucket(htab
, hash
);
1056 raw_spin_lock_irqsave(&b
->lock
, flags
);
1058 l
= lookup_elem_raw(head
, hash
, key
, key_size
);
1061 hlist_nulls_del_rcu(&l
->hash_node
);
1062 free_htab_elem(htab
, l
);
1066 raw_spin_unlock_irqrestore(&b
->lock
, flags
);
1070 static int htab_lru_map_delete_elem(struct bpf_map
*map
, void *key
)
1072 struct bpf_htab
*htab
= container_of(map
, struct bpf_htab
, map
);
1073 struct hlist_nulls_head
*head
;
1075 struct htab_elem
*l
;
1076 unsigned long flags
;
1080 WARN_ON_ONCE(!rcu_read_lock_held());
1082 key_size
= map
->key_size
;
1084 hash
= htab_map_hash(key
, key_size
);
1085 b
= __select_bucket(htab
, hash
);
1088 raw_spin_lock_irqsave(&b
->lock
, flags
);
1090 l
= lookup_elem_raw(head
, hash
, key
, key_size
);
1093 hlist_nulls_del_rcu(&l
->hash_node
);
1097 raw_spin_unlock_irqrestore(&b
->lock
, flags
);
1099 bpf_lru_push_free(&htab
->lru
, &l
->lru_node
);
1103 static void delete_all_elements(struct bpf_htab
*htab
)
1107 for (i
= 0; i
< htab
->n_buckets
; i
++) {
1108 struct hlist_nulls_head
*head
= select_bucket(htab
, i
);
1109 struct hlist_nulls_node
*n
;
1110 struct htab_elem
*l
;
1112 hlist_nulls_for_each_entry_safe(l
, n
, head
, hash_node
) {
1113 hlist_nulls_del_rcu(&l
->hash_node
);
1114 htab_elem_free(htab
, l
);
1119 /* Called when map->refcnt goes to zero, either from workqueue or from syscall */
1120 static void htab_map_free(struct bpf_map
*map
)
1122 struct bpf_htab
*htab
= container_of(map
, struct bpf_htab
, map
);
1124 /* at this point bpf_prog->aux->refcnt == 0 and this map->refcnt == 0,
1125 * so the programs (can be more than one that used this map) were
1126 * disconnected from events. Wait for outstanding critical sections in
1127 * these programs to complete
1131 /* some of free_htab_elem() callbacks for elements of this map may
1132 * not have executed. Wait for them.
1135 if (!htab_is_prealloc(htab
))
1136 delete_all_elements(htab
);
1138 prealloc_destroy(htab
);
1140 free_percpu(htab
->extra_elems
);
1141 bpf_map_area_free(htab
->buckets
);
1145 const struct bpf_map_ops htab_map_ops
= {
1146 .map_alloc
= htab_map_alloc
,
1147 .map_free
= htab_map_free
,
1148 .map_get_next_key
= htab_map_get_next_key
,
1149 .map_lookup_elem
= htab_map_lookup_elem
,
1150 .map_update_elem
= htab_map_update_elem
,
1151 .map_delete_elem
= htab_map_delete_elem
,
1152 .map_gen_lookup
= htab_map_gen_lookup
,
1155 const struct bpf_map_ops htab_lru_map_ops
= {
1156 .map_alloc
= htab_map_alloc
,
1157 .map_free
= htab_map_free
,
1158 .map_get_next_key
= htab_map_get_next_key
,
1159 .map_lookup_elem
= htab_lru_map_lookup_elem
,
1160 .map_update_elem
= htab_lru_map_update_elem
,
1161 .map_delete_elem
= htab_lru_map_delete_elem
,
1162 .map_gen_lookup
= htab_lru_map_gen_lookup
,
1165 /* Called from eBPF program */
1166 static void *htab_percpu_map_lookup_elem(struct bpf_map
*map
, void *key
)
1168 struct htab_elem
*l
= __htab_map_lookup_elem(map
, key
);
1171 return this_cpu_ptr(htab_elem_get_ptr(l
, map
->key_size
));
1176 static void *htab_lru_percpu_map_lookup_elem(struct bpf_map
*map
, void *key
)
1178 struct htab_elem
*l
= __htab_map_lookup_elem(map
, key
);
1181 bpf_lru_node_set_ref(&l
->lru_node
);
1182 return this_cpu_ptr(htab_elem_get_ptr(l
, map
->key_size
));
1188 int bpf_percpu_hash_copy(struct bpf_map
*map
, void *key
, void *value
)
1190 struct bpf_htab
*htab
= container_of(map
, struct bpf_htab
, map
);
1191 struct htab_elem
*l
;
1192 void __percpu
*pptr
;
1197 /* per_cpu areas are zero-filled and bpf programs can only
1198 * access 'value_size' of them, so copying rounded areas
1199 * will not leak any kernel data
1201 size
= round_up(map
->value_size
, 8);
1203 l
= __htab_map_lookup_elem(map
, key
);
1206 if (htab_is_lru(htab
))
1207 bpf_lru_node_set_ref(&l
->lru_node
);
1208 pptr
= htab_elem_get_ptr(l
, map
->key_size
);
1209 for_each_possible_cpu(cpu
) {
1210 bpf_long_memcpy(value
+ off
,
1211 per_cpu_ptr(pptr
, cpu
), size
);
1220 int bpf_percpu_hash_update(struct bpf_map
*map
, void *key
, void *value
,
1223 struct bpf_htab
*htab
= container_of(map
, struct bpf_htab
, map
);
1227 if (htab_is_lru(htab
))
1228 ret
= __htab_lru_percpu_map_update_elem(map
, key
, value
,
1231 ret
= __htab_percpu_map_update_elem(map
, key
, value
, map_flags
,
1238 const struct bpf_map_ops htab_percpu_map_ops
= {
1239 .map_alloc
= htab_map_alloc
,
1240 .map_free
= htab_map_free
,
1241 .map_get_next_key
= htab_map_get_next_key
,
1242 .map_lookup_elem
= htab_percpu_map_lookup_elem
,
1243 .map_update_elem
= htab_percpu_map_update_elem
,
1244 .map_delete_elem
= htab_map_delete_elem
,
1247 const struct bpf_map_ops htab_lru_percpu_map_ops
= {
1248 .map_alloc
= htab_map_alloc
,
1249 .map_free
= htab_map_free
,
1250 .map_get_next_key
= htab_map_get_next_key
,
1251 .map_lookup_elem
= htab_lru_percpu_map_lookup_elem
,
1252 .map_update_elem
= htab_lru_percpu_map_update_elem
,
1253 .map_delete_elem
= htab_lru_map_delete_elem
,
1256 static struct bpf_map
*fd_htab_map_alloc(union bpf_attr
*attr
)
1258 if (attr
->value_size
!= sizeof(u32
))
1259 return ERR_PTR(-EINVAL
);
1260 return htab_map_alloc(attr
);
1263 static void fd_htab_map_free(struct bpf_map
*map
)
1265 struct bpf_htab
*htab
= container_of(map
, struct bpf_htab
, map
);
1266 struct hlist_nulls_node
*n
;
1267 struct hlist_nulls_head
*head
;
1268 struct htab_elem
*l
;
1271 for (i
= 0; i
< htab
->n_buckets
; i
++) {
1272 head
= select_bucket(htab
, i
);
1274 hlist_nulls_for_each_entry_safe(l
, n
, head
, hash_node
) {
1275 void *ptr
= fd_htab_map_get_ptr(map
, l
);
1277 map
->ops
->map_fd_put_ptr(ptr
);
1284 /* only called from syscall */
1285 int bpf_fd_htab_map_lookup_elem(struct bpf_map
*map
, void *key
, u32
*value
)
1290 if (!map
->ops
->map_fd_sys_lookup_elem
)
1294 ptr
= htab_map_lookup_elem(map
, key
);
1296 *value
= map
->ops
->map_fd_sys_lookup_elem(READ_ONCE(*ptr
));
1304 /* only called from syscall */
1305 int bpf_fd_htab_map_update_elem(struct bpf_map
*map
, struct file
*map_file
,
1306 void *key
, void *value
, u64 map_flags
)
1310 u32 ufd
= *(u32
*)value
;
1312 ptr
= map
->ops
->map_fd_get_ptr(map
, map_file
, ufd
);
1314 return PTR_ERR(ptr
);
1316 ret
= htab_map_update_elem(map
, key
, &ptr
, map_flags
);
1318 map
->ops
->map_fd_put_ptr(ptr
);
1323 static struct bpf_map
*htab_of_map_alloc(union bpf_attr
*attr
)
1325 struct bpf_map
*map
, *inner_map_meta
;
1327 inner_map_meta
= bpf_map_meta_alloc(attr
->inner_map_fd
);
1328 if (IS_ERR(inner_map_meta
))
1329 return inner_map_meta
;
1331 map
= fd_htab_map_alloc(attr
);
1333 bpf_map_meta_free(inner_map_meta
);
1337 map
->inner_map_meta
= inner_map_meta
;
1342 static void *htab_of_map_lookup_elem(struct bpf_map
*map
, void *key
)
1344 struct bpf_map
**inner_map
= htab_map_lookup_elem(map
, key
);
1349 return READ_ONCE(*inner_map
);
1352 static u32
htab_of_map_gen_lookup(struct bpf_map
*map
,
1353 struct bpf_insn
*insn_buf
)
1355 struct bpf_insn
*insn
= insn_buf
;
1356 const int ret
= BPF_REG_0
;
1358 *insn
++ = BPF_EMIT_CALL((u64 (*)(u64
, u64
, u64
, u64
, u64
))__htab_map_lookup_elem
);
1359 *insn
++ = BPF_JMP_IMM(BPF_JEQ
, ret
, 0, 2);
1360 *insn
++ = BPF_ALU64_IMM(BPF_ADD
, ret
,
1361 offsetof(struct htab_elem
, key
) +
1362 round_up(map
->key_size
, 8));
1363 *insn
++ = BPF_LDX_MEM(BPF_DW
, ret
, ret
, 0);
1365 return insn
- insn_buf
;
1368 static void htab_of_map_free(struct bpf_map
*map
)
1370 bpf_map_meta_free(map
->inner_map_meta
);
1371 fd_htab_map_free(map
);
1374 const struct bpf_map_ops htab_of_maps_map_ops
= {
1375 .map_alloc
= htab_of_map_alloc
,
1376 .map_free
= htab_of_map_free
,
1377 .map_get_next_key
= htab_map_get_next_key
,
1378 .map_lookup_elem
= htab_of_map_lookup_elem
,
1379 .map_delete_elem
= htab_map_delete_elem
,
1380 .map_fd_get_ptr
= bpf_map_fd_get_ptr
,
1381 .map_fd_put_ptr
= bpf_map_fd_put_ptr
,
1382 .map_fd_sys_lookup_elem
= bpf_map_fd_sys_lookup_elem
,
1383 .map_gen_lookup
= htab_of_map_gen_lookup
,