1
2
3
4
5#include <linux/bpf.h>
6#include <linux/btf.h>
7#include <linux/jhash.h>
8#include <linux/filter.h>
9#include <linux/rculist_nulls.h>
10#include <linux/random.h>
11#include <uapi/linux/btf.h>
12#include <linux/rcupdate_trace.h>
13#include "percpu_freelist.h"
14#include "bpf_lru_list.h"
15#include "map_in_map.h"
16
17#define HTAB_CREATE_FLAG_MASK \
18 (BPF_F_NO_PREALLOC | BPF_F_NO_COMMON_LRU | BPF_F_NUMA_NODE | \
19 BPF_F_ACCESS_MASK | BPF_F_ZERO_SEED)
20
21#define BATCH_OPS(_name) \
22 .map_lookup_batch = \
23 _name##_map_lookup_batch, \
24 .map_lookup_and_delete_batch = \
25 _name##_map_lookup_and_delete_batch, \
26 .map_update_batch = \
27 generic_map_update_batch, \
28 .map_delete_batch = \
29 generic_map_delete_batch
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81struct bucket {
82 struct hlist_nulls_head head;
83 union {
84 raw_spinlock_t raw_lock;
85 spinlock_t lock;
86 };
87};
88
89#define HASHTAB_MAP_LOCK_COUNT 8
90#define HASHTAB_MAP_LOCK_MASK (HASHTAB_MAP_LOCK_COUNT - 1)
91
92struct bpf_htab {
93 struct bpf_map map;
94 struct bucket *buckets;
95 void *elems;
96 union {
97 struct pcpu_freelist freelist;
98 struct bpf_lru lru;
99 };
100 struct htab_elem *__percpu *extra_elems;
101 atomic_t count;
102 u32 n_buckets;
103 u32 elem_size;
104 u32 hashrnd;
105 struct lock_class_key lockdep_key;
106 int __percpu *map_locked[HASHTAB_MAP_LOCK_COUNT];
107};
108
109
110struct htab_elem {
111 union {
112 struct hlist_nulls_node hash_node;
113 struct {
114 void *padding;
115 union {
116 struct bpf_htab *htab;
117 struct pcpu_freelist_node fnode;
118 struct htab_elem *batch_flink;
119 };
120 };
121 };
122 union {
123 struct rcu_head rcu;
124 struct bpf_lru_node lru_node;
125 };
126 u32 hash;
127 char key[] __aligned(8);
128};
129
130static inline bool htab_is_prealloc(const struct bpf_htab *htab)
131{
132 return !(htab->map.map_flags & BPF_F_NO_PREALLOC);
133}
134
135static inline bool htab_use_raw_lock(const struct bpf_htab *htab)
136{
137 return (!IS_ENABLED(CONFIG_PREEMPT_RT) || htab_is_prealloc(htab));
138}
139
140static void htab_init_buckets(struct bpf_htab *htab)
141{
142 unsigned i;
143
144 for (i = 0; i < htab->n_buckets; i++) {
145 INIT_HLIST_NULLS_HEAD(&htab->buckets[i].head, i);
146 if (htab_use_raw_lock(htab)) {
147 raw_spin_lock_init(&htab->buckets[i].raw_lock);
148 lockdep_set_class(&htab->buckets[i].raw_lock,
149 &htab->lockdep_key);
150 } else {
151 spin_lock_init(&htab->buckets[i].lock);
152 lockdep_set_class(&htab->buckets[i].lock,
153 &htab->lockdep_key);
154 }
155 cond_resched();
156 }
157}
158
159static inline int htab_lock_bucket(const struct bpf_htab *htab,
160 struct bucket *b, u32 hash,
161 unsigned long *pflags)
162{
163 unsigned long flags;
164
165 hash = hash & HASHTAB_MAP_LOCK_MASK;
166
167 migrate_disable();
168 if (unlikely(__this_cpu_inc_return(*(htab->map_locked[hash])) != 1)) {
169 __this_cpu_dec(*(htab->map_locked[hash]));
170 migrate_enable();
171 return -EBUSY;
172 }
173
174 if (htab_use_raw_lock(htab))
175 raw_spin_lock_irqsave(&b->raw_lock, flags);
176 else
177 spin_lock_irqsave(&b->lock, flags);
178 *pflags = flags;
179
180 return 0;
181}
182
183static inline void htab_unlock_bucket(const struct bpf_htab *htab,
184 struct bucket *b, u32 hash,
185 unsigned long flags)
186{
187 hash = hash & HASHTAB_MAP_LOCK_MASK;
188 if (htab_use_raw_lock(htab))
189 raw_spin_unlock_irqrestore(&b->raw_lock, flags);
190 else
191 spin_unlock_irqrestore(&b->lock, flags);
192 __this_cpu_dec(*(htab->map_locked[hash]));
193 migrate_enable();
194}
195
196static bool htab_lru_map_delete_node(void *arg, struct bpf_lru_node *node);
197
198static bool htab_is_lru(const struct bpf_htab *htab)
199{
200 return htab->map.map_type == BPF_MAP_TYPE_LRU_HASH ||
201 htab->map.map_type == BPF_MAP_TYPE_LRU_PERCPU_HASH;
202}
203
204static bool htab_is_percpu(const struct bpf_htab *htab)
205{
206 return htab->map.map_type == BPF_MAP_TYPE_PERCPU_HASH ||
207 htab->map.map_type == BPF_MAP_TYPE_LRU_PERCPU_HASH;
208}
209
210static inline void htab_elem_set_ptr(struct htab_elem *l, u32 key_size,
211 void __percpu *pptr)
212{
213 *(void __percpu **)(l->key + key_size) = pptr;
214}
215
216static inline void __percpu *htab_elem_get_ptr(struct htab_elem *l, u32 key_size)
217{
218 return *(void __percpu **)(l->key + key_size);
219}
220
221static void *fd_htab_map_get_ptr(const struct bpf_map *map, struct htab_elem *l)
222{
223 return *(void **)(l->key + roundup(map->key_size, 8));
224}
225
226static struct htab_elem *get_htab_elem(struct bpf_htab *htab, int i)
227{
228 return (struct htab_elem *) (htab->elems + i * (u64)htab->elem_size);
229}
230
231static void htab_free_elems(struct bpf_htab *htab)
232{
233 int i;
234
235 if (!htab_is_percpu(htab))
236 goto free_elems;
237
238 for (i = 0; i < htab->map.max_entries; i++) {
239 void __percpu *pptr;
240
241 pptr = htab_elem_get_ptr(get_htab_elem(htab, i),
242 htab->map.key_size);
243 free_percpu(pptr);
244 cond_resched();
245 }
246free_elems:
247 bpf_map_area_free(htab->elems);
248}
249
250
251
252
253
254
255
256
257
258
259
260
261static struct htab_elem *prealloc_lru_pop(struct bpf_htab *htab, void *key,
262 u32 hash)
263{
264 struct bpf_lru_node *node = bpf_lru_pop_free(&htab->lru, hash);
265 struct htab_elem *l;
266
267 if (node) {
268 l = container_of(node, struct htab_elem, lru_node);
269 memcpy(l->key, key, htab->map.key_size);
270 return l;
271 }
272
273 return NULL;
274}
275
276static int prealloc_init(struct bpf_htab *htab)
277{
278 u32 num_entries = htab->map.max_entries;
279 int err = -ENOMEM, i;
280
281 if (!htab_is_percpu(htab) && !htab_is_lru(htab))
282 num_entries += num_possible_cpus();
283
284 htab->elems = bpf_map_area_alloc((u64)htab->elem_size * num_entries,
285 htab->map.numa_node);
286 if (!htab->elems)
287 return -ENOMEM;
288
289 if (!htab_is_percpu(htab))
290 goto skip_percpu_elems;
291
292 for (i = 0; i < num_entries; i++) {
293 u32 size = round_up(htab->map.value_size, 8);
294 void __percpu *pptr;
295
296 pptr = bpf_map_alloc_percpu(&htab->map, size, 8,
297 GFP_USER | __GFP_NOWARN);
298 if (!pptr)
299 goto free_elems;
300 htab_elem_set_ptr(get_htab_elem(htab, i), htab->map.key_size,
301 pptr);
302 cond_resched();
303 }
304
305skip_percpu_elems:
306 if (htab_is_lru(htab))
307 err = bpf_lru_init(&htab->lru,
308 htab->map.map_flags & BPF_F_NO_COMMON_LRU,
309 offsetof(struct htab_elem, hash) -
310 offsetof(struct htab_elem, lru_node),
311 htab_lru_map_delete_node,
312 htab);
313 else
314 err = pcpu_freelist_init(&htab->freelist);
315
316 if (err)
317 goto free_elems;
318
319 if (htab_is_lru(htab))
320 bpf_lru_populate(&htab->lru, htab->elems,
321 offsetof(struct htab_elem, lru_node),
322 htab->elem_size, num_entries);
323 else
324 pcpu_freelist_populate(&htab->freelist,
325 htab->elems + offsetof(struct htab_elem, fnode),
326 htab->elem_size, num_entries);
327
328 return 0;
329
330free_elems:
331 htab_free_elems(htab);
332 return err;
333}
334
335static void prealloc_destroy(struct bpf_htab *htab)
336{
337 htab_free_elems(htab);
338
339 if (htab_is_lru(htab))
340 bpf_lru_destroy(&htab->lru);
341 else
342 pcpu_freelist_destroy(&htab->freelist);
343}
344
345static int alloc_extra_elems(struct bpf_htab *htab)
346{
347 struct htab_elem *__percpu *pptr, *l_new;
348 struct pcpu_freelist_node *l;
349 int cpu;
350
351 pptr = bpf_map_alloc_percpu(&htab->map, sizeof(struct htab_elem *), 8,
352 GFP_USER | __GFP_NOWARN);
353 if (!pptr)
354 return -ENOMEM;
355
356 for_each_possible_cpu(cpu) {
357 l = pcpu_freelist_pop(&htab->freelist);
358
359
360
361 l_new = container_of(l, struct htab_elem, fnode);
362 *per_cpu_ptr(pptr, cpu) = l_new;
363 }
364 htab->extra_elems = pptr;
365 return 0;
366}
367
368
369static int htab_map_alloc_check(union bpf_attr *attr)
370{
371 bool percpu = (attr->map_type == BPF_MAP_TYPE_PERCPU_HASH ||
372 attr->map_type == BPF_MAP_TYPE_LRU_PERCPU_HASH);
373 bool lru = (attr->map_type == BPF_MAP_TYPE_LRU_HASH ||
374 attr->map_type == BPF_MAP_TYPE_LRU_PERCPU_HASH);
375
376
377
378
379
380 bool percpu_lru = (attr->map_flags & BPF_F_NO_COMMON_LRU);
381 bool prealloc = !(attr->map_flags & BPF_F_NO_PREALLOC);
382 bool zero_seed = (attr->map_flags & BPF_F_ZERO_SEED);
383 int numa_node = bpf_map_attr_numa_node(attr);
384
385 BUILD_BUG_ON(offsetof(struct htab_elem, htab) !=
386 offsetof(struct htab_elem, hash_node.pprev));
387 BUILD_BUG_ON(offsetof(struct htab_elem, fnode.next) !=
388 offsetof(struct htab_elem, hash_node.pprev));
389
390 if (lru && !bpf_capable())
391
392
393
394 return -EPERM;
395
396 if (zero_seed && !capable(CAP_SYS_ADMIN))
397
398 return -EPERM;
399
400 if (attr->map_flags & ~HTAB_CREATE_FLAG_MASK ||
401 !bpf_map_flags_access_ok(attr->map_flags))
402 return -EINVAL;
403
404 if (!lru && percpu_lru)
405 return -EINVAL;
406
407 if (lru && !prealloc)
408 return -ENOTSUPP;
409
410 if (numa_node != NUMA_NO_NODE && (percpu || percpu_lru))
411 return -EINVAL;
412
413
414
415
416 if (attr->max_entries == 0 || attr->key_size == 0 ||
417 attr->value_size == 0)
418 return -EINVAL;
419
420 if ((u64)attr->key_size + attr->value_size >= KMALLOC_MAX_SIZE -
421 sizeof(struct htab_elem))
422
423
424
425
426
427 return -E2BIG;
428
429 return 0;
430}
431
432static struct bpf_map *htab_map_alloc(union bpf_attr *attr)
433{
434 bool percpu = (attr->map_type == BPF_MAP_TYPE_PERCPU_HASH ||
435 attr->map_type == BPF_MAP_TYPE_LRU_PERCPU_HASH);
436 bool lru = (attr->map_type == BPF_MAP_TYPE_LRU_HASH ||
437 attr->map_type == BPF_MAP_TYPE_LRU_PERCPU_HASH);
438
439
440
441
442
443 bool percpu_lru = (attr->map_flags & BPF_F_NO_COMMON_LRU);
444 bool prealloc = !(attr->map_flags & BPF_F_NO_PREALLOC);
445 struct bpf_htab *htab;
446 int err, i;
447
448 htab = kzalloc(sizeof(*htab), GFP_USER | __GFP_ACCOUNT);
449 if (!htab)
450 return ERR_PTR(-ENOMEM);
451
452 lockdep_register_key(&htab->lockdep_key);
453
454 bpf_map_init_from_attr(&htab->map, attr);
455
456 if (percpu_lru) {
457
458
459
460
461 htab->map.max_entries = roundup(attr->max_entries,
462 num_possible_cpus());
463 if (htab->map.max_entries < attr->max_entries)
464 htab->map.max_entries = rounddown(attr->max_entries,
465 num_possible_cpus());
466 }
467
468
469 htab->n_buckets = roundup_pow_of_two(htab->map.max_entries);
470
471 htab->elem_size = sizeof(struct htab_elem) +
472 round_up(htab->map.key_size, 8);
473 if (percpu)
474 htab->elem_size += sizeof(void *);
475 else
476 htab->elem_size += round_up(htab->map.value_size, 8);
477
478 err = -E2BIG;
479
480 if (htab->n_buckets == 0 ||
481 htab->n_buckets > U32_MAX / sizeof(struct bucket))
482 goto free_htab;
483
484 err = -ENOMEM;
485 htab->buckets = bpf_map_area_alloc(htab->n_buckets *
486 sizeof(struct bucket),
487 htab->map.numa_node);
488 if (!htab->buckets)
489 goto free_htab;
490
491 for (i = 0; i < HASHTAB_MAP_LOCK_COUNT; i++) {
492 htab->map_locked[i] = bpf_map_alloc_percpu(&htab->map,
493 sizeof(int),
494 sizeof(int),
495 GFP_USER);
496 if (!htab->map_locked[i])
497 goto free_map_locked;
498 }
499
500 if (htab->map.map_flags & BPF_F_ZERO_SEED)
501 htab->hashrnd = 0;
502 else
503 htab->hashrnd = get_random_int();
504
505 htab_init_buckets(htab);
506
507 if (prealloc) {
508 err = prealloc_init(htab);
509 if (err)
510 goto free_map_locked;
511
512 if (!percpu && !lru) {
513
514
515
516 err = alloc_extra_elems(htab);
517 if (err)
518 goto free_prealloc;
519 }
520 }
521
522 return &htab->map;
523
524free_prealloc:
525 prealloc_destroy(htab);
526free_map_locked:
527 for (i = 0; i < HASHTAB_MAP_LOCK_COUNT; i++)
528 free_percpu(htab->map_locked[i]);
529 bpf_map_area_free(htab->buckets);
530free_htab:
531 lockdep_unregister_key(&htab->lockdep_key);
532 kfree(htab);
533 return ERR_PTR(err);
534}
535
536static inline u32 htab_map_hash(const void *key, u32 key_len, u32 hashrnd)
537{
538 return jhash(key, key_len, hashrnd);
539}
540
541static inline struct bucket *__select_bucket(struct bpf_htab *htab, u32 hash)
542{
543 return &htab->buckets[hash & (htab->n_buckets - 1)];
544}
545
546static inline struct hlist_nulls_head *select_bucket(struct bpf_htab *htab, u32 hash)
547{
548 return &__select_bucket(htab, hash)->head;
549}
550
551
552static struct htab_elem *lookup_elem_raw(struct hlist_nulls_head *head, u32 hash,
553 void *key, u32 key_size)
554{
555 struct hlist_nulls_node *n;
556 struct htab_elem *l;
557
558 hlist_nulls_for_each_entry_rcu(l, n, head, hash_node)
559 if (l->hash == hash && !memcmp(&l->key, key, key_size))
560 return l;
561
562 return NULL;
563}
564
565
566
567
568
569static struct htab_elem *lookup_nulls_elem_raw(struct hlist_nulls_head *head,
570 u32 hash, void *key,
571 u32 key_size, u32 n_buckets)
572{
573 struct hlist_nulls_node *n;
574 struct htab_elem *l;
575
576again:
577 hlist_nulls_for_each_entry_rcu(l, n, head, hash_node)
578 if (l->hash == hash && !memcmp(&l->key, key, key_size))
579 return l;
580
581 if (unlikely(get_nulls_value(n) != (hash & (n_buckets - 1))))
582 goto again;
583
584 return NULL;
585}
586
587
588
589
590
591
592static void *__htab_map_lookup_elem(struct bpf_map *map, void *key)
593{
594 struct bpf_htab *htab = container_of(map, struct bpf_htab, map);
595 struct hlist_nulls_head *head;
596 struct htab_elem *l;
597 u32 hash, key_size;
598
599 WARN_ON_ONCE(!rcu_read_lock_held() && !rcu_read_lock_trace_held() &&
600 !rcu_read_lock_bh_held());
601
602 key_size = map->key_size;
603
604 hash = htab_map_hash(key, key_size, htab->hashrnd);
605
606 head = select_bucket(htab, hash);
607
608 l = lookup_nulls_elem_raw(head, hash, key, key_size, htab->n_buckets);
609
610 return l;
611}
612
613static void *htab_map_lookup_elem(struct bpf_map *map, void *key)
614{
615 struct htab_elem *l = __htab_map_lookup_elem(map, key);
616
617 if (l)
618 return l->key + round_up(map->key_size, 8);
619
620 return NULL;
621}
622
623
624
625
626
627
628
629
630
631
632
633
634static int htab_map_gen_lookup(struct bpf_map *map, struct bpf_insn *insn_buf)
635{
636 struct bpf_insn *insn = insn_buf;
637 const int ret = BPF_REG_0;
638
639 BUILD_BUG_ON(!__same_type(&__htab_map_lookup_elem,
640 (void *(*)(struct bpf_map *map, void *key))NULL));
641 *insn++ = BPF_EMIT_CALL(BPF_CAST_CALL(__htab_map_lookup_elem));
642 *insn++ = BPF_JMP_IMM(BPF_JEQ, ret, 0, 1);
643 *insn++ = BPF_ALU64_IMM(BPF_ADD, ret,
644 offsetof(struct htab_elem, key) +
645 round_up(map->key_size, 8));
646 return insn - insn_buf;
647}
648
649static __always_inline void *__htab_lru_map_lookup_elem(struct bpf_map *map,
650 void *key, const bool mark)
651{
652 struct htab_elem *l = __htab_map_lookup_elem(map, key);
653
654 if (l) {
655 if (mark)
656 bpf_lru_node_set_ref(&l->lru_node);
657 return l->key + round_up(map->key_size, 8);
658 }
659
660 return NULL;
661}
662
663static void *htab_lru_map_lookup_elem(struct bpf_map *map, void *key)
664{
665 return __htab_lru_map_lookup_elem(map, key, true);
666}
667
668static void *htab_lru_map_lookup_elem_sys(struct bpf_map *map, void *key)
669{
670 return __htab_lru_map_lookup_elem(map, key, false);
671}
672
673static int htab_lru_map_gen_lookup(struct bpf_map *map,
674 struct bpf_insn *insn_buf)
675{
676 struct bpf_insn *insn = insn_buf;
677 const int ret = BPF_REG_0;
678 const int ref_reg = BPF_REG_1;
679
680 BUILD_BUG_ON(!__same_type(&__htab_map_lookup_elem,
681 (void *(*)(struct bpf_map *map, void *key))NULL));
682 *insn++ = BPF_EMIT_CALL(BPF_CAST_CALL(__htab_map_lookup_elem));
683 *insn++ = BPF_JMP_IMM(BPF_JEQ, ret, 0, 4);
684 *insn++ = BPF_LDX_MEM(BPF_B, ref_reg, ret,
685 offsetof(struct htab_elem, lru_node) +
686 offsetof(struct bpf_lru_node, ref));
687 *insn++ = BPF_JMP_IMM(BPF_JNE, ref_reg, 0, 1);
688 *insn++ = BPF_ST_MEM(BPF_B, ret,
689 offsetof(struct htab_elem, lru_node) +
690 offsetof(struct bpf_lru_node, ref),
691 1);
692 *insn++ = BPF_ALU64_IMM(BPF_ADD, ret,
693 offsetof(struct htab_elem, key) +
694 round_up(map->key_size, 8));
695 return insn - insn_buf;
696}
697
698
699
700
701static bool htab_lru_map_delete_node(void *arg, struct bpf_lru_node *node)
702{
703 struct bpf_htab *htab = (struct bpf_htab *)arg;
704 struct htab_elem *l = NULL, *tgt_l;
705 struct hlist_nulls_head *head;
706 struct hlist_nulls_node *n;
707 unsigned long flags;
708 struct bucket *b;
709 int ret;
710
711 tgt_l = container_of(node, struct htab_elem, lru_node);
712 b = __select_bucket(htab, tgt_l->hash);
713 head = &b->head;
714
715 ret = htab_lock_bucket(htab, b, tgt_l->hash, &flags);
716 if (ret)
717 return false;
718
719 hlist_nulls_for_each_entry_rcu(l, n, head, hash_node)
720 if (l == tgt_l) {
721 hlist_nulls_del_rcu(&l->hash_node);
722 break;
723 }
724
725 htab_unlock_bucket(htab, b, tgt_l->hash, flags);
726
727 return l == tgt_l;
728}
729
730
731static int htab_map_get_next_key(struct bpf_map *map, void *key, void *next_key)
732{
733 struct bpf_htab *htab = container_of(map, struct bpf_htab, map);
734 struct hlist_nulls_head *head;
735 struct htab_elem *l, *next_l;
736 u32 hash, key_size;
737 int i = 0;
738
739 WARN_ON_ONCE(!rcu_read_lock_held());
740
741 key_size = map->key_size;
742
743 if (!key)
744 goto find_first_elem;
745
746 hash = htab_map_hash(key, key_size, htab->hashrnd);
747
748 head = select_bucket(htab, hash);
749
750
751 l = lookup_nulls_elem_raw(head, hash, key, key_size, htab->n_buckets);
752
753 if (!l)
754 goto find_first_elem;
755
756
757 next_l = hlist_nulls_entry_safe(rcu_dereference_raw(hlist_nulls_next_rcu(&l->hash_node)),
758 struct htab_elem, hash_node);
759
760 if (next_l) {
761
762 memcpy(next_key, next_l->key, key_size);
763 return 0;
764 }
765
766
767 i = hash & (htab->n_buckets - 1);
768 i++;
769
770find_first_elem:
771
772 for (; i < htab->n_buckets; i++) {
773 head = select_bucket(htab, i);
774
775
776 next_l = hlist_nulls_entry_safe(rcu_dereference_raw(hlist_nulls_first_rcu(head)),
777 struct htab_elem, hash_node);
778 if (next_l) {
779
780 memcpy(next_key, next_l->key, key_size);
781 return 0;
782 }
783 }
784
785
786 return -ENOENT;
787}
788
789static void htab_elem_free(struct bpf_htab *htab, struct htab_elem *l)
790{
791 if (htab->map.map_type == BPF_MAP_TYPE_PERCPU_HASH)
792 free_percpu(htab_elem_get_ptr(l, htab->map.key_size));
793 kfree(l);
794}
795
796static void htab_elem_free_rcu(struct rcu_head *head)
797{
798 struct htab_elem *l = container_of(head, struct htab_elem, rcu);
799 struct bpf_htab *htab = l->htab;
800
801 htab_elem_free(htab, l);
802}
803
804static void htab_put_fd_value(struct bpf_htab *htab, struct htab_elem *l)
805{
806 struct bpf_map *map = &htab->map;
807 void *ptr;
808
809 if (map->ops->map_fd_put_ptr) {
810 ptr = fd_htab_map_get_ptr(map, l);
811 map->ops->map_fd_put_ptr(ptr);
812 }
813}
814
815static void free_htab_elem(struct bpf_htab *htab, struct htab_elem *l)
816{
817 htab_put_fd_value(htab, l);
818
819 if (htab_is_prealloc(htab)) {
820 __pcpu_freelist_push(&htab->freelist, &l->fnode);
821 } else {
822 atomic_dec(&htab->count);
823 l->htab = htab;
824 call_rcu(&l->rcu, htab_elem_free_rcu);
825 }
826}
827
828static void pcpu_copy_value(struct bpf_htab *htab, void __percpu *pptr,
829 void *value, bool onallcpus)
830{
831 if (!onallcpus) {
832
833 memcpy(this_cpu_ptr(pptr), value, htab->map.value_size);
834 } else {
835 u32 size = round_up(htab->map.value_size, 8);
836 int off = 0, cpu;
837
838 for_each_possible_cpu(cpu) {
839 bpf_long_memcpy(per_cpu_ptr(pptr, cpu),
840 value + off, size);
841 off += size;
842 }
843 }
844}
845
846static void pcpu_init_value(struct bpf_htab *htab, void __percpu *pptr,
847 void *value, bool onallcpus)
848{
849
850
851
852
853
854
855 if (htab_is_prealloc(htab) && !onallcpus) {
856 u32 size = round_up(htab->map.value_size, 8);
857 int current_cpu = raw_smp_processor_id();
858 int cpu;
859
860 for_each_possible_cpu(cpu) {
861 if (cpu == current_cpu)
862 bpf_long_memcpy(per_cpu_ptr(pptr, cpu), value,
863 size);
864 else
865 memset(per_cpu_ptr(pptr, cpu), 0, size);
866 }
867 } else {
868 pcpu_copy_value(htab, pptr, value, onallcpus);
869 }
870}
871
872static bool fd_htab_map_needs_adjust(const struct bpf_htab *htab)
873{
874 return htab->map.map_type == BPF_MAP_TYPE_HASH_OF_MAPS &&
875 BITS_PER_LONG == 64;
876}
877
878static struct htab_elem *alloc_htab_elem(struct bpf_htab *htab, void *key,
879 void *value, u32 key_size, u32 hash,
880 bool percpu, bool onallcpus,
881 struct htab_elem *old_elem)
882{
883 u32 size = htab->map.value_size;
884 bool prealloc = htab_is_prealloc(htab);
885 struct htab_elem *l_new, **pl_new;
886 void __percpu *pptr;
887
888 if (prealloc) {
889 if (old_elem) {
890
891
892
893 pl_new = this_cpu_ptr(htab->extra_elems);
894 l_new = *pl_new;
895 htab_put_fd_value(htab, old_elem);
896 *pl_new = old_elem;
897 } else {
898 struct pcpu_freelist_node *l;
899
900 l = __pcpu_freelist_pop(&htab->freelist);
901 if (!l)
902 return ERR_PTR(-E2BIG);
903 l_new = container_of(l, struct htab_elem, fnode);
904 }
905 } else {
906 if (atomic_inc_return(&htab->count) > htab->map.max_entries)
907 if (!old_elem) {
908
909
910
911
912
913 l_new = ERR_PTR(-E2BIG);
914 goto dec_count;
915 }
916 l_new = bpf_map_kmalloc_node(&htab->map, htab->elem_size,
917 GFP_ATOMIC | __GFP_NOWARN,
918 htab->map.numa_node);
919 if (!l_new) {
920 l_new = ERR_PTR(-ENOMEM);
921 goto dec_count;
922 }
923 check_and_init_map_lock(&htab->map,
924 l_new->key + round_up(key_size, 8));
925 }
926
927 memcpy(l_new->key, key, key_size);
928 if (percpu) {
929 size = round_up(size, 8);
930 if (prealloc) {
931 pptr = htab_elem_get_ptr(l_new, key_size);
932 } else {
933
934 pptr = bpf_map_alloc_percpu(&htab->map, size, 8,
935 GFP_ATOMIC | __GFP_NOWARN);
936 if (!pptr) {
937 kfree(l_new);
938 l_new = ERR_PTR(-ENOMEM);
939 goto dec_count;
940 }
941 }
942
943 pcpu_init_value(htab, pptr, value, onallcpus);
944
945 if (!prealloc)
946 htab_elem_set_ptr(l_new, key_size, pptr);
947 } else if (fd_htab_map_needs_adjust(htab)) {
948 size = round_up(size, 8);
949 memcpy(l_new->key + round_up(key_size, 8), value, size);
950 } else {
951 copy_map_value(&htab->map,
952 l_new->key + round_up(key_size, 8),
953 value);
954 }
955
956 l_new->hash = hash;
957 return l_new;
958dec_count:
959 atomic_dec(&htab->count);
960 return l_new;
961}
962
963static int check_flags(struct bpf_htab *htab, struct htab_elem *l_old,
964 u64 map_flags)
965{
966 if (l_old && (map_flags & ~BPF_F_LOCK) == BPF_NOEXIST)
967
968 return -EEXIST;
969
970 if (!l_old && (map_flags & ~BPF_F_LOCK) == BPF_EXIST)
971
972 return -ENOENT;
973
974 return 0;
975}
976
977
978static int htab_map_update_elem(struct bpf_map *map, void *key, void *value,
979 u64 map_flags)
980{
981 struct bpf_htab *htab = container_of(map, struct bpf_htab, map);
982 struct htab_elem *l_new = NULL, *l_old;
983 struct hlist_nulls_head *head;
984 unsigned long flags;
985 struct bucket *b;
986 u32 key_size, hash;
987 int ret;
988
989 if (unlikely((map_flags & ~BPF_F_LOCK) > BPF_EXIST))
990
991 return -EINVAL;
992
993 WARN_ON_ONCE(!rcu_read_lock_held() && !rcu_read_lock_trace_held() &&
994 !rcu_read_lock_bh_held());
995
996 key_size = map->key_size;
997
998 hash = htab_map_hash(key, key_size, htab->hashrnd);
999
1000 b = __select_bucket(htab, hash);
1001 head = &b->head;
1002
1003 if (unlikely(map_flags & BPF_F_LOCK)) {
1004 if (unlikely(!map_value_has_spin_lock(map)))
1005 return -EINVAL;
1006
1007 l_old = lookup_nulls_elem_raw(head, hash, key, key_size,
1008 htab->n_buckets);
1009 ret = check_flags(htab, l_old, map_flags);
1010 if (ret)
1011 return ret;
1012 if (l_old) {
1013
1014 copy_map_value_locked(map,
1015 l_old->key + round_up(key_size, 8),
1016 value, false);
1017 return 0;
1018 }
1019
1020
1021
1022
1023 }
1024
1025 ret = htab_lock_bucket(htab, b, hash, &flags);
1026 if (ret)
1027 return ret;
1028
1029 l_old = lookup_elem_raw(head, hash, key, key_size);
1030
1031 ret = check_flags(htab, l_old, map_flags);
1032 if (ret)
1033 goto err;
1034
1035 if (unlikely(l_old && (map_flags & BPF_F_LOCK))) {
1036
1037
1038
1039
1040
1041
1042 copy_map_value_locked(map,
1043 l_old->key + round_up(key_size, 8),
1044 value, false);
1045 ret = 0;
1046 goto err;
1047 }
1048
1049 l_new = alloc_htab_elem(htab, key, value, key_size, hash, false, false,
1050 l_old);
1051 if (IS_ERR(l_new)) {
1052
1053 ret = PTR_ERR(l_new);
1054 goto err;
1055 }
1056
1057
1058
1059
1060 hlist_nulls_add_head_rcu(&l_new->hash_node, head);
1061 if (l_old) {
1062 hlist_nulls_del_rcu(&l_old->hash_node);
1063 if (!htab_is_prealloc(htab))
1064 free_htab_elem(htab, l_old);
1065 }
1066 ret = 0;
1067err:
1068 htab_unlock_bucket(htab, b, hash, flags);
1069 return ret;
1070}
1071
1072static int htab_lru_map_update_elem(struct bpf_map *map, void *key, void *value,
1073 u64 map_flags)
1074{
1075 struct bpf_htab *htab = container_of(map, struct bpf_htab, map);
1076 struct htab_elem *l_new, *l_old = NULL;
1077 struct hlist_nulls_head *head;
1078 unsigned long flags;
1079 struct bucket *b;
1080 u32 key_size, hash;
1081 int ret;
1082
1083 if (unlikely(map_flags > BPF_EXIST))
1084
1085 return -EINVAL;
1086
1087 WARN_ON_ONCE(!rcu_read_lock_held() && !rcu_read_lock_trace_held() &&
1088 !rcu_read_lock_bh_held());
1089
1090 key_size = map->key_size;
1091
1092 hash = htab_map_hash(key, key_size, htab->hashrnd);
1093
1094 b = __select_bucket(htab, hash);
1095 head = &b->head;
1096
1097
1098
1099
1100
1101
1102 l_new = prealloc_lru_pop(htab, key, hash);
1103 if (!l_new)
1104 return -ENOMEM;
1105 memcpy(l_new->key + round_up(map->key_size, 8), value, map->value_size);
1106
1107 ret = htab_lock_bucket(htab, b, hash, &flags);
1108 if (ret)
1109 return ret;
1110
1111 l_old = lookup_elem_raw(head, hash, key, key_size);
1112
1113 ret = check_flags(htab, l_old, map_flags);
1114 if (ret)
1115 goto err;
1116
1117
1118
1119
1120 hlist_nulls_add_head_rcu(&l_new->hash_node, head);
1121 if (l_old) {
1122 bpf_lru_node_set_ref(&l_new->lru_node);
1123 hlist_nulls_del_rcu(&l_old->hash_node);
1124 }
1125 ret = 0;
1126
1127err:
1128 htab_unlock_bucket(htab, b, hash, flags);
1129
1130 if (ret)
1131 bpf_lru_push_free(&htab->lru, &l_new->lru_node);
1132 else if (l_old)
1133 bpf_lru_push_free(&htab->lru, &l_old->lru_node);
1134
1135 return ret;
1136}
1137
1138static int __htab_percpu_map_update_elem(struct bpf_map *map, void *key,
1139 void *value, u64 map_flags,
1140 bool onallcpus)
1141{
1142 struct bpf_htab *htab = container_of(map, struct bpf_htab, map);
1143 struct htab_elem *l_new = NULL, *l_old;
1144 struct hlist_nulls_head *head;
1145 unsigned long flags;
1146 struct bucket *b;
1147 u32 key_size, hash;
1148 int ret;
1149
1150 if (unlikely(map_flags > BPF_EXIST))
1151
1152 return -EINVAL;
1153
1154 WARN_ON_ONCE(!rcu_read_lock_held() && !rcu_read_lock_trace_held() &&
1155 !rcu_read_lock_bh_held());
1156
1157 key_size = map->key_size;
1158
1159 hash = htab_map_hash(key, key_size, htab->hashrnd);
1160
1161 b = __select_bucket(htab, hash);
1162 head = &b->head;
1163
1164 ret = htab_lock_bucket(htab, b, hash, &flags);
1165 if (ret)
1166 return ret;
1167
1168 l_old = lookup_elem_raw(head, hash, key, key_size);
1169
1170 ret = check_flags(htab, l_old, map_flags);
1171 if (ret)
1172 goto err;
1173
1174 if (l_old) {
1175
1176 pcpu_copy_value(htab, htab_elem_get_ptr(l_old, key_size),
1177 value, onallcpus);
1178 } else {
1179 l_new = alloc_htab_elem(htab, key, value, key_size,
1180 hash, true, onallcpus, NULL);
1181 if (IS_ERR(l_new)) {
1182 ret = PTR_ERR(l_new);
1183 goto err;
1184 }
1185 hlist_nulls_add_head_rcu(&l_new->hash_node, head);
1186 }
1187 ret = 0;
1188err:
1189 htab_unlock_bucket(htab, b, hash, flags);
1190 return ret;
1191}
1192
1193static int __htab_lru_percpu_map_update_elem(struct bpf_map *map, void *key,
1194 void *value, u64 map_flags,
1195 bool onallcpus)
1196{
1197 struct bpf_htab *htab = container_of(map, struct bpf_htab, map);
1198 struct htab_elem *l_new = NULL, *l_old;
1199 struct hlist_nulls_head *head;
1200 unsigned long flags;
1201 struct bucket *b;
1202 u32 key_size, hash;
1203 int ret;
1204
1205 if (unlikely(map_flags > BPF_EXIST))
1206
1207 return -EINVAL;
1208
1209 WARN_ON_ONCE(!rcu_read_lock_held() && !rcu_read_lock_trace_held() &&
1210 !rcu_read_lock_bh_held());
1211
1212 key_size = map->key_size;
1213
1214 hash = htab_map_hash(key, key_size, htab->hashrnd);
1215
1216 b = __select_bucket(htab, hash);
1217 head = &b->head;
1218
1219
1220
1221
1222
1223
1224 if (map_flags != BPF_EXIST) {
1225 l_new = prealloc_lru_pop(htab, key, hash);
1226 if (!l_new)
1227 return -ENOMEM;
1228 }
1229
1230 ret = htab_lock_bucket(htab, b, hash, &flags);
1231 if (ret)
1232 return ret;
1233
1234 l_old = lookup_elem_raw(head, hash, key, key_size);
1235
1236 ret = check_flags(htab, l_old, map_flags);
1237 if (ret)
1238 goto err;
1239
1240 if (l_old) {
1241 bpf_lru_node_set_ref(&l_old->lru_node);
1242
1243
1244 pcpu_copy_value(htab, htab_elem_get_ptr(l_old, key_size),
1245 value, onallcpus);
1246 } else {
1247 pcpu_init_value(htab, htab_elem_get_ptr(l_new, key_size),
1248 value, onallcpus);
1249 hlist_nulls_add_head_rcu(&l_new->hash_node, head);
1250 l_new = NULL;
1251 }
1252 ret = 0;
1253err:
1254 htab_unlock_bucket(htab, b, hash, flags);
1255 if (l_new)
1256 bpf_lru_push_free(&htab->lru, &l_new->lru_node);
1257 return ret;
1258}
1259
1260static int htab_percpu_map_update_elem(struct bpf_map *map, void *key,
1261 void *value, u64 map_flags)
1262{
1263 return __htab_percpu_map_update_elem(map, key, value, map_flags, false);
1264}
1265
1266static int htab_lru_percpu_map_update_elem(struct bpf_map *map, void *key,
1267 void *value, u64 map_flags)
1268{
1269 return __htab_lru_percpu_map_update_elem(map, key, value, map_flags,
1270 false);
1271}
1272
1273
1274static int htab_map_delete_elem(struct bpf_map *map, void *key)
1275{
1276 struct bpf_htab *htab = container_of(map, struct bpf_htab, map);
1277 struct hlist_nulls_head *head;
1278 struct bucket *b;
1279 struct htab_elem *l;
1280 unsigned long flags;
1281 u32 hash, key_size;
1282 int ret;
1283
1284 WARN_ON_ONCE(!rcu_read_lock_held() && !rcu_read_lock_trace_held() &&
1285 !rcu_read_lock_bh_held());
1286
1287 key_size = map->key_size;
1288
1289 hash = htab_map_hash(key, key_size, htab->hashrnd);
1290 b = __select_bucket(htab, hash);
1291 head = &b->head;
1292
1293 ret = htab_lock_bucket(htab, b, hash, &flags);
1294 if (ret)
1295 return ret;
1296
1297 l = lookup_elem_raw(head, hash, key, key_size);
1298
1299 if (l) {
1300 hlist_nulls_del_rcu(&l->hash_node);
1301 free_htab_elem(htab, l);
1302 } else {
1303 ret = -ENOENT;
1304 }
1305
1306 htab_unlock_bucket(htab, b, hash, flags);
1307 return ret;
1308}
1309
1310static int htab_lru_map_delete_elem(struct bpf_map *map, void *key)
1311{
1312 struct bpf_htab *htab = container_of(map, struct bpf_htab, map);
1313 struct hlist_nulls_head *head;
1314 struct bucket *b;
1315 struct htab_elem *l;
1316 unsigned long flags;
1317 u32 hash, key_size;
1318 int ret;
1319
1320 WARN_ON_ONCE(!rcu_read_lock_held() && !rcu_read_lock_trace_held() &&
1321 !rcu_read_lock_bh_held());
1322
1323 key_size = map->key_size;
1324
1325 hash = htab_map_hash(key, key_size, htab->hashrnd);
1326 b = __select_bucket(htab, hash);
1327 head = &b->head;
1328
1329 ret = htab_lock_bucket(htab, b, hash, &flags);
1330 if (ret)
1331 return ret;
1332
1333 l = lookup_elem_raw(head, hash, key, key_size);
1334
1335 if (l)
1336 hlist_nulls_del_rcu(&l->hash_node);
1337 else
1338 ret = -ENOENT;
1339
1340 htab_unlock_bucket(htab, b, hash, flags);
1341 if (l)
1342 bpf_lru_push_free(&htab->lru, &l->lru_node);
1343 return ret;
1344}
1345
1346static void delete_all_elements(struct bpf_htab *htab)
1347{
1348 int i;
1349
1350 for (i = 0; i < htab->n_buckets; i++) {
1351 struct hlist_nulls_head *head = select_bucket(htab, i);
1352 struct hlist_nulls_node *n;
1353 struct htab_elem *l;
1354
1355 hlist_nulls_for_each_entry_safe(l, n, head, hash_node) {
1356 hlist_nulls_del_rcu(&l->hash_node);
1357 htab_elem_free(htab, l);
1358 }
1359 }
1360}
1361
1362
1363static void htab_map_free(struct bpf_map *map)
1364{
1365 struct bpf_htab *htab = container_of(map, struct bpf_htab, map);
1366 int i;
1367
1368
1369
1370
1371
1372
1373
1374
1375
1376 rcu_barrier();
1377 if (!htab_is_prealloc(htab))
1378 delete_all_elements(htab);
1379 else
1380 prealloc_destroy(htab);
1381
1382 free_percpu(htab->extra_elems);
1383 bpf_map_area_free(htab->buckets);
1384 for (i = 0; i < HASHTAB_MAP_LOCK_COUNT; i++)
1385 free_percpu(htab->map_locked[i]);
1386 lockdep_unregister_key(&htab->lockdep_key);
1387 kfree(htab);
1388}
1389
1390static void htab_map_seq_show_elem(struct bpf_map *map, void *key,
1391 struct seq_file *m)
1392{
1393 void *value;
1394
1395 rcu_read_lock();
1396
1397 value = htab_map_lookup_elem(map, key);
1398 if (!value) {
1399 rcu_read_unlock();
1400 return;
1401 }
1402
1403 btf_type_seq_show(map->btf, map->btf_key_type_id, key, m);
1404 seq_puts(m, ": ");
1405 btf_type_seq_show(map->btf, map->btf_value_type_id, value, m);
1406 seq_puts(m, "\n");
1407
1408 rcu_read_unlock();
1409}
1410
1411static int __htab_map_lookup_and_delete_elem(struct bpf_map *map, void *key,
1412 void *value, bool is_lru_map,
1413 bool is_percpu, u64 flags)
1414{
1415 struct bpf_htab *htab = container_of(map, struct bpf_htab, map);
1416 struct hlist_nulls_head *head;
1417 unsigned long bflags;
1418 struct htab_elem *l;
1419 u32 hash, key_size;
1420 struct bucket *b;
1421 int ret;
1422
1423 key_size = map->key_size;
1424
1425 hash = htab_map_hash(key, key_size, htab->hashrnd);
1426 b = __select_bucket(htab, hash);
1427 head = &b->head;
1428
1429 ret = htab_lock_bucket(htab, b, hash, &bflags);
1430 if (ret)
1431 return ret;
1432
1433 l = lookup_elem_raw(head, hash, key, key_size);
1434 if (!l) {
1435 ret = -ENOENT;
1436 } else {
1437 if (is_percpu) {
1438 u32 roundup_value_size = round_up(map->value_size, 8);
1439 void __percpu *pptr;
1440 int off = 0, cpu;
1441
1442 pptr = htab_elem_get_ptr(l, key_size);
1443 for_each_possible_cpu(cpu) {
1444 bpf_long_memcpy(value + off,
1445 per_cpu_ptr(pptr, cpu),
1446 roundup_value_size);
1447 off += roundup_value_size;
1448 }
1449 } else {
1450 u32 roundup_key_size = round_up(map->key_size, 8);
1451
1452 if (flags & BPF_F_LOCK)
1453 copy_map_value_locked(map, value, l->key +
1454 roundup_key_size,
1455 true);
1456 else
1457 copy_map_value(map, value, l->key +
1458 roundup_key_size);
1459 check_and_init_map_lock(map, value);
1460 }
1461
1462 hlist_nulls_del_rcu(&l->hash_node);
1463 if (!is_lru_map)
1464 free_htab_elem(htab, l);
1465 }
1466
1467 htab_unlock_bucket(htab, b, hash, bflags);
1468
1469 if (is_lru_map && l)
1470 bpf_lru_push_free(&htab->lru, &l->lru_node);
1471
1472 return ret;
1473}
1474
1475static int htab_map_lookup_and_delete_elem(struct bpf_map *map, void *key,
1476 void *value, u64 flags)
1477{
1478 return __htab_map_lookup_and_delete_elem(map, key, value, false, false,
1479 flags);
1480}
1481
1482static int htab_percpu_map_lookup_and_delete_elem(struct bpf_map *map,
1483 void *key, void *value,
1484 u64 flags)
1485{
1486 return __htab_map_lookup_and_delete_elem(map, key, value, false, true,
1487 flags);
1488}
1489
1490static int htab_lru_map_lookup_and_delete_elem(struct bpf_map *map, void *key,
1491 void *value, u64 flags)
1492{
1493 return __htab_map_lookup_and_delete_elem(map, key, value, true, false,
1494 flags);
1495}
1496
1497static int htab_lru_percpu_map_lookup_and_delete_elem(struct bpf_map *map,
1498 void *key, void *value,
1499 u64 flags)
1500{
1501 return __htab_map_lookup_and_delete_elem(map, key, value, true, true,
1502 flags);
1503}
1504
1505static int
1506__htab_map_lookup_and_delete_batch(struct bpf_map *map,
1507 const union bpf_attr *attr,
1508 union bpf_attr __user *uattr,
1509 bool do_delete, bool is_lru_map,
1510 bool is_percpu)
1511{
1512 struct bpf_htab *htab = container_of(map, struct bpf_htab, map);
1513 u32 bucket_cnt, total, key_size, value_size, roundup_key_size;
1514 void *keys = NULL, *values = NULL, *value, *dst_key, *dst_val;
1515 void __user *uvalues = u64_to_user_ptr(attr->batch.values);
1516 void __user *ukeys = u64_to_user_ptr(attr->batch.keys);
1517 void __user *ubatch = u64_to_user_ptr(attr->batch.in_batch);
1518 u32 batch, max_count, size, bucket_size;
1519 struct htab_elem *node_to_free = NULL;
1520 u64 elem_map_flags, map_flags;
1521 struct hlist_nulls_head *head;
1522 struct hlist_nulls_node *n;
1523 unsigned long flags = 0;
1524 bool locked = false;
1525 struct htab_elem *l;
1526 struct bucket *b;
1527 int ret = 0;
1528
1529 elem_map_flags = attr->batch.elem_flags;
1530 if ((elem_map_flags & ~BPF_F_LOCK) ||
1531 ((elem_map_flags & BPF_F_LOCK) && !map_value_has_spin_lock(map)))
1532 return -EINVAL;
1533
1534 map_flags = attr->batch.flags;
1535 if (map_flags)
1536 return -EINVAL;
1537
1538 max_count = attr->batch.count;
1539 if (!max_count)
1540 return 0;
1541
1542 if (put_user(0, &uattr->batch.count))
1543 return -EFAULT;
1544
1545 batch = 0;
1546 if (ubatch && copy_from_user(&batch, ubatch, sizeof(batch)))
1547 return -EFAULT;
1548
1549 if (batch >= htab->n_buckets)
1550 return -ENOENT;
1551
1552 key_size = htab->map.key_size;
1553 roundup_key_size = round_up(htab->map.key_size, 8);
1554 value_size = htab->map.value_size;
1555 size = round_up(value_size, 8);
1556 if (is_percpu)
1557 value_size = size * num_possible_cpus();
1558 total = 0;
1559
1560
1561
1562 bucket_size = 5;
1563
1564alloc:
1565
1566
1567
1568 keys = kvmalloc_array(key_size, bucket_size, GFP_USER | __GFP_NOWARN);
1569 values = kvmalloc_array(value_size, bucket_size, GFP_USER | __GFP_NOWARN);
1570 if (!keys || !values) {
1571 ret = -ENOMEM;
1572 goto after_loop;
1573 }
1574
1575again:
1576 bpf_disable_instrumentation();
1577 rcu_read_lock();
1578again_nocopy:
1579 dst_key = keys;
1580 dst_val = values;
1581 b = &htab->buckets[batch];
1582 head = &b->head;
1583
1584 if (locked) {
1585 ret = htab_lock_bucket(htab, b, batch, &flags);
1586 if (ret)
1587 goto next_batch;
1588 }
1589
1590 bucket_cnt = 0;
1591 hlist_nulls_for_each_entry_rcu(l, n, head, hash_node)
1592 bucket_cnt++;
1593
1594 if (bucket_cnt && !locked) {
1595 locked = true;
1596 goto again_nocopy;
1597 }
1598
1599 if (bucket_cnt > (max_count - total)) {
1600 if (total == 0)
1601 ret = -ENOSPC;
1602
1603
1604
1605 htab_unlock_bucket(htab, b, batch, flags);
1606 rcu_read_unlock();
1607 bpf_enable_instrumentation();
1608 goto after_loop;
1609 }
1610
1611 if (bucket_cnt > bucket_size) {
1612 bucket_size = bucket_cnt;
1613
1614
1615
1616 htab_unlock_bucket(htab, b, batch, flags);
1617 rcu_read_unlock();
1618 bpf_enable_instrumentation();
1619 kvfree(keys);
1620 kvfree(values);
1621 goto alloc;
1622 }
1623
1624
1625 if (!locked)
1626 goto next_batch;
1627
1628 hlist_nulls_for_each_entry_safe(l, n, head, hash_node) {
1629 memcpy(dst_key, l->key, key_size);
1630
1631 if (is_percpu) {
1632 int off = 0, cpu;
1633 void __percpu *pptr;
1634
1635 pptr = htab_elem_get_ptr(l, map->key_size);
1636 for_each_possible_cpu(cpu) {
1637 bpf_long_memcpy(dst_val + off,
1638 per_cpu_ptr(pptr, cpu), size);
1639 off += size;
1640 }
1641 } else {
1642 value = l->key + roundup_key_size;
1643 if (elem_map_flags & BPF_F_LOCK)
1644 copy_map_value_locked(map, dst_val, value,
1645 true);
1646 else
1647 copy_map_value(map, dst_val, value);
1648 check_and_init_map_lock(map, dst_val);
1649 }
1650 if (do_delete) {
1651 hlist_nulls_del_rcu(&l->hash_node);
1652
1653
1654
1655
1656
1657
1658 if (is_lru_map) {
1659 l->batch_flink = node_to_free;
1660 node_to_free = l;
1661 } else {
1662 free_htab_elem(htab, l);
1663 }
1664 }
1665 dst_key += key_size;
1666 dst_val += value_size;
1667 }
1668
1669 htab_unlock_bucket(htab, b, batch, flags);
1670 locked = false;
1671
1672 while (node_to_free) {
1673 l = node_to_free;
1674 node_to_free = node_to_free->batch_flink;
1675 bpf_lru_push_free(&htab->lru, &l->lru_node);
1676 }
1677
1678next_batch:
1679
1680
1681
1682 if (!bucket_cnt && (batch + 1 < htab->n_buckets)) {
1683 batch++;
1684 goto again_nocopy;
1685 }
1686
1687 rcu_read_unlock();
1688 bpf_enable_instrumentation();
1689 if (bucket_cnt && (copy_to_user(ukeys + total * key_size, keys,
1690 key_size * bucket_cnt) ||
1691 copy_to_user(uvalues + total * value_size, values,
1692 value_size * bucket_cnt))) {
1693 ret = -EFAULT;
1694 goto after_loop;
1695 }
1696
1697 total += bucket_cnt;
1698 batch++;
1699 if (batch >= htab->n_buckets) {
1700 ret = -ENOENT;
1701 goto after_loop;
1702 }
1703 goto again;
1704
1705after_loop:
1706 if (ret == -EFAULT)
1707 goto out;
1708
1709
1710 ubatch = u64_to_user_ptr(attr->batch.out_batch);
1711 if (copy_to_user(ubatch, &batch, sizeof(batch)) ||
1712 put_user(total, &uattr->batch.count))
1713 ret = -EFAULT;
1714
1715out:
1716 kvfree(keys);
1717 kvfree(values);
1718 return ret;
1719}
1720
1721static int
1722htab_percpu_map_lookup_batch(struct bpf_map *map, const union bpf_attr *attr,
1723 union bpf_attr __user *uattr)
1724{
1725 return __htab_map_lookup_and_delete_batch(map, attr, uattr, false,
1726 false, true);
1727}
1728
1729static int
1730htab_percpu_map_lookup_and_delete_batch(struct bpf_map *map,
1731 const union bpf_attr *attr,
1732 union bpf_attr __user *uattr)
1733{
1734 return __htab_map_lookup_and_delete_batch(map, attr, uattr, true,
1735 false, true);
1736}
1737
1738static int
1739htab_map_lookup_batch(struct bpf_map *map, const union bpf_attr *attr,
1740 union bpf_attr __user *uattr)
1741{
1742 return __htab_map_lookup_and_delete_batch(map, attr, uattr, false,
1743 false, false);
1744}
1745
1746static int
1747htab_map_lookup_and_delete_batch(struct bpf_map *map,
1748 const union bpf_attr *attr,
1749 union bpf_attr __user *uattr)
1750{
1751 return __htab_map_lookup_and_delete_batch(map, attr, uattr, true,
1752 false, false);
1753}
1754
1755static int
1756htab_lru_percpu_map_lookup_batch(struct bpf_map *map,
1757 const union bpf_attr *attr,
1758 union bpf_attr __user *uattr)
1759{
1760 return __htab_map_lookup_and_delete_batch(map, attr, uattr, false,
1761 true, true);
1762}
1763
1764static int
1765htab_lru_percpu_map_lookup_and_delete_batch(struct bpf_map *map,
1766 const union bpf_attr *attr,
1767 union bpf_attr __user *uattr)
1768{
1769 return __htab_map_lookup_and_delete_batch(map, attr, uattr, true,
1770 true, true);
1771}
1772
1773static int
1774htab_lru_map_lookup_batch(struct bpf_map *map, const union bpf_attr *attr,
1775 union bpf_attr __user *uattr)
1776{
1777 return __htab_map_lookup_and_delete_batch(map, attr, uattr, false,
1778 true, false);
1779}
1780
1781static int
1782htab_lru_map_lookup_and_delete_batch(struct bpf_map *map,
1783 const union bpf_attr *attr,
1784 union bpf_attr __user *uattr)
1785{
1786 return __htab_map_lookup_and_delete_batch(map, attr, uattr, true,
1787 true, false);
1788}
1789
1790struct bpf_iter_seq_hash_map_info {
1791 struct bpf_map *map;
1792 struct bpf_htab *htab;
1793 void *percpu_value_buf;
1794 u32 bucket_id;
1795 u32 skip_elems;
1796};
1797
1798static struct htab_elem *
1799bpf_hash_map_seq_find_next(struct bpf_iter_seq_hash_map_info *info,
1800 struct htab_elem *prev_elem)
1801{
1802 const struct bpf_htab *htab = info->htab;
1803 u32 skip_elems = info->skip_elems;
1804 u32 bucket_id = info->bucket_id;
1805 struct hlist_nulls_head *head;
1806 struct hlist_nulls_node *n;
1807 struct htab_elem *elem;
1808 struct bucket *b;
1809 u32 i, count;
1810
1811 if (bucket_id >= htab->n_buckets)
1812 return NULL;
1813
1814
1815 if (prev_elem) {
1816
1817
1818
1819 n = rcu_dereference_raw(hlist_nulls_next_rcu(&prev_elem->hash_node));
1820 elem = hlist_nulls_entry_safe(n, struct htab_elem, hash_node);
1821 if (elem)
1822 return elem;
1823
1824
1825 b = &htab->buckets[bucket_id++];
1826 rcu_read_unlock();
1827 skip_elems = 0;
1828 }
1829
1830 for (i = bucket_id; i < htab->n_buckets; i++) {
1831 b = &htab->buckets[i];
1832 rcu_read_lock();
1833
1834 count = 0;
1835 head = &b->head;
1836 hlist_nulls_for_each_entry_rcu(elem, n, head, hash_node) {
1837 if (count >= skip_elems) {
1838 info->bucket_id = i;
1839 info->skip_elems = count;
1840 return elem;
1841 }
1842 count++;
1843 }
1844
1845 rcu_read_unlock();
1846 skip_elems = 0;
1847 }
1848
1849 info->bucket_id = i;
1850 info->skip_elems = 0;
1851 return NULL;
1852}
1853
1854static void *bpf_hash_map_seq_start(struct seq_file *seq, loff_t *pos)
1855{
1856 struct bpf_iter_seq_hash_map_info *info = seq->private;
1857 struct htab_elem *elem;
1858
1859 elem = bpf_hash_map_seq_find_next(info, NULL);
1860 if (!elem)
1861 return NULL;
1862
1863 if (*pos == 0)
1864 ++*pos;
1865 return elem;
1866}
1867
1868static void *bpf_hash_map_seq_next(struct seq_file *seq, void *v, loff_t *pos)
1869{
1870 struct bpf_iter_seq_hash_map_info *info = seq->private;
1871
1872 ++*pos;
1873 ++info->skip_elems;
1874 return bpf_hash_map_seq_find_next(info, v);
1875}
1876
1877static int __bpf_hash_map_seq_show(struct seq_file *seq, struct htab_elem *elem)
1878{
1879 struct bpf_iter_seq_hash_map_info *info = seq->private;
1880 u32 roundup_key_size, roundup_value_size;
1881 struct bpf_iter__bpf_map_elem ctx = {};
1882 struct bpf_map *map = info->map;
1883 struct bpf_iter_meta meta;
1884 int ret = 0, off = 0, cpu;
1885 struct bpf_prog *prog;
1886 void __percpu *pptr;
1887
1888 meta.seq = seq;
1889 prog = bpf_iter_get_info(&meta, elem == NULL);
1890 if (prog) {
1891 ctx.meta = &meta;
1892 ctx.map = info->map;
1893 if (elem) {
1894 roundup_key_size = round_up(map->key_size, 8);
1895 ctx.key = elem->key;
1896 if (!info->percpu_value_buf) {
1897 ctx.value = elem->key + roundup_key_size;
1898 } else {
1899 roundup_value_size = round_up(map->value_size, 8);
1900 pptr = htab_elem_get_ptr(elem, map->key_size);
1901 for_each_possible_cpu(cpu) {
1902 bpf_long_memcpy(info->percpu_value_buf + off,
1903 per_cpu_ptr(pptr, cpu),
1904 roundup_value_size);
1905 off += roundup_value_size;
1906 }
1907 ctx.value = info->percpu_value_buf;
1908 }
1909 }
1910 ret = bpf_iter_run_prog(prog, &ctx);
1911 }
1912
1913 return ret;
1914}
1915
1916static int bpf_hash_map_seq_show(struct seq_file *seq, void *v)
1917{
1918 return __bpf_hash_map_seq_show(seq, v);
1919}
1920
1921static void bpf_hash_map_seq_stop(struct seq_file *seq, void *v)
1922{
1923 if (!v)
1924 (void)__bpf_hash_map_seq_show(seq, NULL);
1925 else
1926 rcu_read_unlock();
1927}
1928
1929static int bpf_iter_init_hash_map(void *priv_data,
1930 struct bpf_iter_aux_info *aux)
1931{
1932 struct bpf_iter_seq_hash_map_info *seq_info = priv_data;
1933 struct bpf_map *map = aux->map;
1934 void *value_buf;
1935 u32 buf_size;
1936
1937 if (map->map_type == BPF_MAP_TYPE_PERCPU_HASH ||
1938 map->map_type == BPF_MAP_TYPE_LRU_PERCPU_HASH) {
1939 buf_size = round_up(map->value_size, 8) * num_possible_cpus();
1940 value_buf = kmalloc(buf_size, GFP_USER | __GFP_NOWARN);
1941 if (!value_buf)
1942 return -ENOMEM;
1943
1944 seq_info->percpu_value_buf = value_buf;
1945 }
1946
1947 seq_info->map = map;
1948 seq_info->htab = container_of(map, struct bpf_htab, map);
1949 return 0;
1950}
1951
1952static void bpf_iter_fini_hash_map(void *priv_data)
1953{
1954 struct bpf_iter_seq_hash_map_info *seq_info = priv_data;
1955
1956 kfree(seq_info->percpu_value_buf);
1957}
1958
1959static const struct seq_operations bpf_hash_map_seq_ops = {
1960 .start = bpf_hash_map_seq_start,
1961 .next = bpf_hash_map_seq_next,
1962 .stop = bpf_hash_map_seq_stop,
1963 .show = bpf_hash_map_seq_show,
1964};
1965
1966static const struct bpf_iter_seq_info iter_seq_info = {
1967 .seq_ops = &bpf_hash_map_seq_ops,
1968 .init_seq_private = bpf_iter_init_hash_map,
1969 .fini_seq_private = bpf_iter_fini_hash_map,
1970 .seq_priv_size = sizeof(struct bpf_iter_seq_hash_map_info),
1971};
1972
1973static int bpf_for_each_hash_elem(struct bpf_map *map, void *callback_fn,
1974 void *callback_ctx, u64 flags)
1975{
1976 struct bpf_htab *htab = container_of(map, struct bpf_htab, map);
1977 struct hlist_nulls_head *head;
1978 struct hlist_nulls_node *n;
1979 struct htab_elem *elem;
1980 u32 roundup_key_size;
1981 int i, num_elems = 0;
1982 void __percpu *pptr;
1983 struct bucket *b;
1984 void *key, *val;
1985 bool is_percpu;
1986 u64 ret = 0;
1987
1988 if (flags != 0)
1989 return -EINVAL;
1990
1991 is_percpu = htab_is_percpu(htab);
1992
1993 roundup_key_size = round_up(map->key_size, 8);
1994
1995
1996
1997 if (is_percpu)
1998 migrate_disable();
1999 for (i = 0; i < htab->n_buckets; i++) {
2000 b = &htab->buckets[i];
2001 rcu_read_lock();
2002 head = &b->head;
2003 hlist_nulls_for_each_entry_rcu(elem, n, head, hash_node) {
2004 key = elem->key;
2005 if (is_percpu) {
2006
2007 pptr = htab_elem_get_ptr(elem, map->key_size);
2008 val = this_cpu_ptr(pptr);
2009 } else {
2010 val = elem->key + roundup_key_size;
2011 }
2012 num_elems++;
2013 ret = BPF_CAST_CALL(callback_fn)((u64)(long)map,
2014 (u64)(long)key, (u64)(long)val,
2015 (u64)(long)callback_ctx, 0);
2016
2017 if (ret) {
2018 rcu_read_unlock();
2019 goto out;
2020 }
2021 }
2022 rcu_read_unlock();
2023 }
2024out:
2025 if (is_percpu)
2026 migrate_enable();
2027 return num_elems;
2028}
2029
2030static int htab_map_btf_id;
2031const struct bpf_map_ops htab_map_ops = {
2032 .map_meta_equal = bpf_map_meta_equal,
2033 .map_alloc_check = htab_map_alloc_check,
2034 .map_alloc = htab_map_alloc,
2035 .map_free = htab_map_free,
2036 .map_get_next_key = htab_map_get_next_key,
2037 .map_lookup_elem = htab_map_lookup_elem,
2038 .map_lookup_and_delete_elem = htab_map_lookup_and_delete_elem,
2039 .map_update_elem = htab_map_update_elem,
2040 .map_delete_elem = htab_map_delete_elem,
2041 .map_gen_lookup = htab_map_gen_lookup,
2042 .map_seq_show_elem = htab_map_seq_show_elem,
2043 .map_set_for_each_callback_args = map_set_for_each_callback_args,
2044 .map_for_each_callback = bpf_for_each_hash_elem,
2045 BATCH_OPS(htab),
2046 .map_btf_name = "bpf_htab",
2047 .map_btf_id = &htab_map_btf_id,
2048 .iter_seq_info = &iter_seq_info,
2049};
2050
2051static int htab_lru_map_btf_id;
2052const struct bpf_map_ops htab_lru_map_ops = {
2053 .map_meta_equal = bpf_map_meta_equal,
2054 .map_alloc_check = htab_map_alloc_check,
2055 .map_alloc = htab_map_alloc,
2056 .map_free = htab_map_free,
2057 .map_get_next_key = htab_map_get_next_key,
2058 .map_lookup_elem = htab_lru_map_lookup_elem,
2059 .map_lookup_and_delete_elem = htab_lru_map_lookup_and_delete_elem,
2060 .map_lookup_elem_sys_only = htab_lru_map_lookup_elem_sys,
2061 .map_update_elem = htab_lru_map_update_elem,
2062 .map_delete_elem = htab_lru_map_delete_elem,
2063 .map_gen_lookup = htab_lru_map_gen_lookup,
2064 .map_seq_show_elem = htab_map_seq_show_elem,
2065 .map_set_for_each_callback_args = map_set_for_each_callback_args,
2066 .map_for_each_callback = bpf_for_each_hash_elem,
2067 BATCH_OPS(htab_lru),
2068 .map_btf_name = "bpf_htab",
2069 .map_btf_id = &htab_lru_map_btf_id,
2070 .iter_seq_info = &iter_seq_info,
2071};
2072
2073
2074static void *htab_percpu_map_lookup_elem(struct bpf_map *map, void *key)
2075{
2076 struct htab_elem *l = __htab_map_lookup_elem(map, key);
2077
2078 if (l)
2079 return this_cpu_ptr(htab_elem_get_ptr(l, map->key_size));
2080 else
2081 return NULL;
2082}
2083
2084static void *htab_lru_percpu_map_lookup_elem(struct bpf_map *map, void *key)
2085{
2086 struct htab_elem *l = __htab_map_lookup_elem(map, key);
2087
2088 if (l) {
2089 bpf_lru_node_set_ref(&l->lru_node);
2090 return this_cpu_ptr(htab_elem_get_ptr(l, map->key_size));
2091 }
2092
2093 return NULL;
2094}
2095
2096int bpf_percpu_hash_copy(struct bpf_map *map, void *key, void *value)
2097{
2098 struct htab_elem *l;
2099 void __percpu *pptr;
2100 int ret = -ENOENT;
2101 int cpu, off = 0;
2102 u32 size;
2103
2104
2105
2106
2107
2108 size = round_up(map->value_size, 8);
2109 rcu_read_lock();
2110 l = __htab_map_lookup_elem(map, key);
2111 if (!l)
2112 goto out;
2113
2114
2115
2116 pptr = htab_elem_get_ptr(l, map->key_size);
2117 for_each_possible_cpu(cpu) {
2118 bpf_long_memcpy(value + off,
2119 per_cpu_ptr(pptr, cpu), size);
2120 off += size;
2121 }
2122 ret = 0;
2123out:
2124 rcu_read_unlock();
2125 return ret;
2126}
2127
2128int bpf_percpu_hash_update(struct bpf_map *map, void *key, void *value,
2129 u64 map_flags)
2130{
2131 struct bpf_htab *htab = container_of(map, struct bpf_htab, map);
2132 int ret;
2133
2134 rcu_read_lock();
2135 if (htab_is_lru(htab))
2136 ret = __htab_lru_percpu_map_update_elem(map, key, value,
2137 map_flags, true);
2138 else
2139 ret = __htab_percpu_map_update_elem(map, key, value, map_flags,
2140 true);
2141 rcu_read_unlock();
2142
2143 return ret;
2144}
2145
2146static void htab_percpu_map_seq_show_elem(struct bpf_map *map, void *key,
2147 struct seq_file *m)
2148{
2149 struct htab_elem *l;
2150 void __percpu *pptr;
2151 int cpu;
2152
2153 rcu_read_lock();
2154
2155 l = __htab_map_lookup_elem(map, key);
2156 if (!l) {
2157 rcu_read_unlock();
2158 return;
2159 }
2160
2161 btf_type_seq_show(map->btf, map->btf_key_type_id, key, m);
2162 seq_puts(m, ": {\n");
2163 pptr = htab_elem_get_ptr(l, map->key_size);
2164 for_each_possible_cpu(cpu) {
2165 seq_printf(m, "\tcpu%d: ", cpu);
2166 btf_type_seq_show(map->btf, map->btf_value_type_id,
2167 per_cpu_ptr(pptr, cpu), m);
2168 seq_puts(m, "\n");
2169 }
2170 seq_puts(m, "}\n");
2171
2172 rcu_read_unlock();
2173}
2174
2175static int htab_percpu_map_btf_id;
2176const struct bpf_map_ops htab_percpu_map_ops = {
2177 .map_meta_equal = bpf_map_meta_equal,
2178 .map_alloc_check = htab_map_alloc_check,
2179 .map_alloc = htab_map_alloc,
2180 .map_free = htab_map_free,
2181 .map_get_next_key = htab_map_get_next_key,
2182 .map_lookup_elem = htab_percpu_map_lookup_elem,
2183 .map_lookup_and_delete_elem = htab_percpu_map_lookup_and_delete_elem,
2184 .map_update_elem = htab_percpu_map_update_elem,
2185 .map_delete_elem = htab_map_delete_elem,
2186 .map_seq_show_elem = htab_percpu_map_seq_show_elem,
2187 .map_set_for_each_callback_args = map_set_for_each_callback_args,
2188 .map_for_each_callback = bpf_for_each_hash_elem,
2189 BATCH_OPS(htab_percpu),
2190 .map_btf_name = "bpf_htab",
2191 .map_btf_id = &htab_percpu_map_btf_id,
2192 .iter_seq_info = &iter_seq_info,
2193};
2194
2195static int htab_lru_percpu_map_btf_id;
2196const struct bpf_map_ops htab_lru_percpu_map_ops = {
2197 .map_meta_equal = bpf_map_meta_equal,
2198 .map_alloc_check = htab_map_alloc_check,
2199 .map_alloc = htab_map_alloc,
2200 .map_free = htab_map_free,
2201 .map_get_next_key = htab_map_get_next_key,
2202 .map_lookup_elem = htab_lru_percpu_map_lookup_elem,
2203 .map_lookup_and_delete_elem = htab_lru_percpu_map_lookup_and_delete_elem,
2204 .map_update_elem = htab_lru_percpu_map_update_elem,
2205 .map_delete_elem = htab_lru_map_delete_elem,
2206 .map_seq_show_elem = htab_percpu_map_seq_show_elem,
2207 .map_set_for_each_callback_args = map_set_for_each_callback_args,
2208 .map_for_each_callback = bpf_for_each_hash_elem,
2209 BATCH_OPS(htab_lru_percpu),
2210 .map_btf_name = "bpf_htab",
2211 .map_btf_id = &htab_lru_percpu_map_btf_id,
2212 .iter_seq_info = &iter_seq_info,
2213};
2214
2215static int fd_htab_map_alloc_check(union bpf_attr *attr)
2216{
2217 if (attr->value_size != sizeof(u32))
2218 return -EINVAL;
2219 return htab_map_alloc_check(attr);
2220}
2221
2222static void fd_htab_map_free(struct bpf_map *map)
2223{
2224 struct bpf_htab *htab = container_of(map, struct bpf_htab, map);
2225 struct hlist_nulls_node *n;
2226 struct hlist_nulls_head *head;
2227 struct htab_elem *l;
2228 int i;
2229
2230 for (i = 0; i < htab->n_buckets; i++) {
2231 head = select_bucket(htab, i);
2232
2233 hlist_nulls_for_each_entry_safe(l, n, head, hash_node) {
2234 void *ptr = fd_htab_map_get_ptr(map, l);
2235
2236 map->ops->map_fd_put_ptr(ptr);
2237 }
2238 }
2239
2240 htab_map_free(map);
2241}
2242
2243
2244int bpf_fd_htab_map_lookup_elem(struct bpf_map *map, void *key, u32 *value)
2245{
2246 void **ptr;
2247 int ret = 0;
2248
2249 if (!map->ops->map_fd_sys_lookup_elem)
2250 return -ENOTSUPP;
2251
2252 rcu_read_lock();
2253 ptr = htab_map_lookup_elem(map, key);
2254 if (ptr)
2255 *value = map->ops->map_fd_sys_lookup_elem(READ_ONCE(*ptr));
2256 else
2257 ret = -ENOENT;
2258 rcu_read_unlock();
2259
2260 return ret;
2261}
2262
2263
2264int bpf_fd_htab_map_update_elem(struct bpf_map *map, struct file *map_file,
2265 void *key, void *value, u64 map_flags)
2266{
2267 void *ptr;
2268 int ret;
2269 u32 ufd = *(u32 *)value;
2270
2271 ptr = map->ops->map_fd_get_ptr(map, map_file, ufd);
2272 if (IS_ERR(ptr))
2273 return PTR_ERR(ptr);
2274
2275 ret = htab_map_update_elem(map, key, &ptr, map_flags);
2276 if (ret)
2277 map->ops->map_fd_put_ptr(ptr);
2278
2279 return ret;
2280}
2281
2282static struct bpf_map *htab_of_map_alloc(union bpf_attr *attr)
2283{
2284 struct bpf_map *map, *inner_map_meta;
2285
2286 inner_map_meta = bpf_map_meta_alloc(attr->inner_map_fd);
2287 if (IS_ERR(inner_map_meta))
2288 return inner_map_meta;
2289
2290 map = htab_map_alloc(attr);
2291 if (IS_ERR(map)) {
2292 bpf_map_meta_free(inner_map_meta);
2293 return map;
2294 }
2295
2296 map->inner_map_meta = inner_map_meta;
2297
2298 return map;
2299}
2300
2301static void *htab_of_map_lookup_elem(struct bpf_map *map, void *key)
2302{
2303 struct bpf_map **inner_map = htab_map_lookup_elem(map, key);
2304
2305 if (!inner_map)
2306 return NULL;
2307
2308 return READ_ONCE(*inner_map);
2309}
2310
2311static int htab_of_map_gen_lookup(struct bpf_map *map,
2312 struct bpf_insn *insn_buf)
2313{
2314 struct bpf_insn *insn = insn_buf;
2315 const int ret = BPF_REG_0;
2316
2317 BUILD_BUG_ON(!__same_type(&__htab_map_lookup_elem,
2318 (void *(*)(struct bpf_map *map, void *key))NULL));
2319 *insn++ = BPF_EMIT_CALL(BPF_CAST_CALL(__htab_map_lookup_elem));
2320 *insn++ = BPF_JMP_IMM(BPF_JEQ, ret, 0, 2);
2321 *insn++ = BPF_ALU64_IMM(BPF_ADD, ret,
2322 offsetof(struct htab_elem, key) +
2323 round_up(map->key_size, 8));
2324 *insn++ = BPF_LDX_MEM(BPF_DW, ret, ret, 0);
2325
2326 return insn - insn_buf;
2327}
2328
2329static void htab_of_map_free(struct bpf_map *map)
2330{
2331 bpf_map_meta_free(map->inner_map_meta);
2332 fd_htab_map_free(map);
2333}
2334
2335static int htab_of_maps_map_btf_id;
2336const struct bpf_map_ops htab_of_maps_map_ops = {
2337 .map_alloc_check = fd_htab_map_alloc_check,
2338 .map_alloc = htab_of_map_alloc,
2339 .map_free = htab_of_map_free,
2340 .map_get_next_key = htab_map_get_next_key,
2341 .map_lookup_elem = htab_of_map_lookup_elem,
2342 .map_delete_elem = htab_map_delete_elem,
2343 .map_fd_get_ptr = bpf_map_fd_get_ptr,
2344 .map_fd_put_ptr = bpf_map_fd_put_ptr,
2345 .map_fd_sys_lookup_elem = bpf_map_fd_sys_lookup_elem,
2346 .map_gen_lookup = htab_of_map_gen_lookup,
2347 .map_check_btf = map_check_no_btf,
2348 .map_btf_name = "bpf_htab",
2349 .map_btf_id = &htab_of_maps_map_btf_id,
2350};
2351