kernel/bpf/hashtab.c

   1 // SPDX-License-Identifier: GPL-2.0-only
   2 /* Copyright (c) 2011-2014 PLUMgrid, http://plumgrid.com
   3  * Copyright (c) 2016 Facebook
   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  * The bucket lock has two protection scopes:
  33  *
  34  * 1) Serializing concurrent operations from BPF programs on different
  35  *    CPUs
  36  *
  37  * 2) Serializing concurrent operations from BPF programs and sys_bpf()
  38  *
  39  * BPF programs can execute in any context including perf, kprobes and
  40  * tracing. As there are almost no limits where perf, kprobes and tracing
  41  * can be invoked from the lock operations need to be protected against
  42  * deadlocks. Deadlocks can be caused by recursion and by an invocation in
  43  * the lock held section when functions which acquire this lock are invoked
  44  * from sys_bpf(). BPF recursion is prevented by incrementing the per CPU
  45  * variable bpf_prog_active, which prevents BPF programs attached to perf
  46  * events, kprobes and tracing to be invoked before the prior invocation
  47  * from one of these contexts completed. sys_bpf() uses the same mechanism
  48  * by pinning the task to the current CPU and incrementing the recursion
  49  * protection across the map operation.
  50  *
  51  * This has subtle implications on PREEMPT_RT. PREEMPT_RT forbids certain
  52  * operations like memory allocations (even with GFP_ATOMIC) from atomic
  53  * contexts. This is required because even with GFP_ATOMIC the memory
  54  * allocator calls into code paths which acquire locks with long held lock
  55  * sections. To ensure the deterministic behaviour these locks are regular
  56  * spinlocks, which are converted to 'sleepable' spinlocks on RT. The only
  57  * true atomic contexts on an RT kernel are the low level hardware
  58  * handling, scheduling, low level interrupt handling, NMIs etc. None of
  59  * these contexts should ever do memory allocations.
  60  *
  61  * As regular device interrupt handlers and soft interrupts are forced into
  62  * thread context, the existing code which does
  63  *   spin_lock*(); alloc(GPF_ATOMIC); spin_unlock*();
  64  * just works.
  65  *
  66  * In theory the BPF locks could be converted to regular spinlocks as well,
  67  * but the bucket locks and percpu_freelist locks can be taken from
  68  * arbitrary contexts (perf, kprobes, tracepoints) which are required to be
  69  * atomic contexts even on RT. These mechanisms require preallocated maps,
  70  * so there is no need to invoke memory allocations within the lock held
  71  * sections.
  72  *
  73  * BPF maps which need dynamic allocation are only used from (forced)
  74  * thread context on RT and can therefore use regular spinlocks which in
  75  * turn allows to invoke memory allocations from the lock held section.
  76  *
  77  * On a non RT kernel this distinction is neither possible nor required.
  78  * spinlock maps to raw_spinlock and the extra code is optimized out by the
  79  * compiler.
  80  */
  81 struct 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
  92 struct 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; /* number of elements in this hashtable */
 102         u32 n_buckets;  /* number of hash buckets */
 103         u32 elem_size;  /* size of each element in bytes */
 104         u32 hashrnd;
 105         struct lock_class_key lockdep_key;
 106         int __percpu *map_locked[HASHTAB_MAP_LOCK_COUNT];
 107 };
 108
 109 /* each htab element is struct htab_elem + key + value */
 110 struct 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
 130 static inline bool htab_is_prealloc(const struct bpf_htab *htab)
 131 {
 132         return !(htab->map.map_flags & BPF_F_NO_PREALLOC);
 133 }
 134
 135 static 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
 140 static 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
 159 static 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
 183 static 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
 196 static bool htab_lru_map_delete_node(void *arg, struct bpf_lru_node *node);
 197
 198 static 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
 204 static 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
 210 static 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
 216 static 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
 221 static 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
 226 static 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
 231 static 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         }
 246 free_elems:
 247         bpf_map_area_free(htab->elems);
 248 }
 249
 250 /* The LRU list has a lock (lru_lock). Each htab bucket has a lock
 251  * (bucket_lock). If both locks need to be acquired together, the lock
 252  * order is always lru_lock -> bucket_lock and this only happens in
 253  * bpf_lru_list.c logic. For example, certain code path of
 254  * bpf_lru_pop_free(), which is called by function prealloc_lru_pop(),
 255  * will acquire lru_lock first followed by acquiring bucket_lock.
 256  *
 257  * In hashtab.c, to avoid deadlock, lock acquisition of
 258  * bucket_lock followed by lru_lock is not allowed. In such cases,
 259  * bucket_lock needs to be released first before acquiring lru_lock.
 260  */
 261 static 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
 276 static 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
 305 skip_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
 330 free_elems:
 331         htab_free_elems(htab);
 332         return err;
 333 }
 334
 335 static 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
 345 static 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                 /* pop will succeed, since prealloc_init()
 359                  * preallocated extra num_possible_cpus elements
 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 /* Called from syscall */
 369 static 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         /* percpu_lru means each cpu has its own LRU list.
 376          * it is different from BPF_MAP_TYPE_PERCPU_HASH where
 377          * the map's value itself is percpu.  percpu_lru has
 378          * nothing to do with the map's value.
 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                 /* LRU implementation is much complicated than other
 392                  * maps.  Hence, limit to CAP_BPF.
 393                  */
 394                 return -EPERM;
 395
 396         if (zero_seed && !capable(CAP_SYS_ADMIN))
 397                 /* Guard against local DoS, and discourage production use. */
 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         /* check sanity of attributes.
 414          * value_size == 0 may be allowed in the future to use map as a set
 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                 /* if key_size + value_size is bigger, the user space won't be
 423                  * able to access the elements via bpf syscall. This check
 424                  * also makes sure that the elem_size doesn't overflow and it's
 425                  * kmalloc-able later in htab_map_update_elem()
 426                  */
 427                 return -E2BIG;
 428
 429         return 0;
 430 }
 431
 432 static 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         /* percpu_lru means each cpu has its own LRU list.
 439          * it is different from BPF_MAP_TYPE_PERCPU_HASH where
 440          * the map's value itself is percpu.  percpu_lru has
 441          * nothing to do with the map's value.
 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                 /* ensure each CPU's lru list has >=1 elements.
 458                  * since we are at it, make each lru list has the same
 459                  * number of elements.
 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         /* hash table size must be power of 2 */
 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         /* prevent zero size kmalloc and check for u32 overflow */
 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                         /* lru itself can remove the least used element, so
 514                          * there is no need for an extra elem during map_update.
 515                          */
 516                         err = alloc_extra_elems(htab);
 517                         if (err)
 518                                 goto free_prealloc;
 519                 }
 520         }
 521
 522         return &htab->map;
 523
 524 free_prealloc:
 525         prealloc_destroy(htab);
 526 free_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);
 530 free_htab:
 531         lockdep_unregister_key(&htab->lockdep_key);
 532         kfree(htab);
 533         return ERR_PTR(err);
 534 }
 535
 536 static inline u32 htab_map_hash(const void *key, u32 key_len, u32 hashrnd)
 537 {
 538         return jhash(key, key_len, hashrnd);
 539 }
 540
 541 static inline struct bucket *__select_bucket(struct bpf_htab *htab, u32 hash)
 542 {
 543         return &htab->buckets[hash & (htab->n_buckets - 1)];
 544 }
 545
 546 static inline struct hlist_nulls_head *select_bucket(struct bpf_htab *htab, u32 hash)
 547 {
 548         return &__select_bucket(htab, hash)->head;
 549 }
 550
 551 /* this lookup function can only be called with bucket lock taken */
 552 static 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 /* can be called without bucket lock. it will repeat the loop in
 566  * the unlikely event when elements moved from one bucket into another
 567  * while link list is being walked
 568  */
 569 static 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
 576 again:
 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 /* Called from syscall or from eBPF program directly, so
 588  * arguments have to match bpf_map_lookup_elem() exactly.
 589  * The return value is adjusted by BPF instructions
 590  * in htab_map_gen_lookup().
 591  */
 592 static 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
 613 static 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 /* inline bpf_map_lookup_elem() call.
 624  * Instead of:
 625  * bpf_prog
 626  *   bpf_map_lookup_elem
 627  *     map->ops->map_lookup_elem
 628  *       htab_map_lookup_elem
 629  *         __htab_map_lookup_elem
 630  * do:
 631  * bpf_prog
 632  *   __htab_map_lookup_elem
 633  */
 634 static 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
 649 static __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
 663 static 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
 668 static 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
 673 static 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 /* It is called from the bpf_lru_list when the LRU needs to delete
 699  * older elements from the htab.
 700  */
 701 static 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 /* Called from syscall */
 731 static 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         /* lookup the key */
 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         /* key was found, get next key in the same bucket */
 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                 /* if next elem in this hash list is non-zero, just return it */
 762                 memcpy(next_key, next_l->key, key_size);
 763                 return 0;
 764         }
 765
 766         /* no more elements in this hash list, go to the next bucket */
 767         i = hash & (htab->n_buckets - 1);
 768         i++;
 769
 770 find_first_elem:
 771         /* iterate over buckets */
 772         for (; i < htab->n_buckets; i++) {
 773                 head = select_bucket(htab, i);
 774
 775                 /* pick first element in the bucket */
 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                         /* if it's not empty, just return it */
 780                         memcpy(next_key, next_l->key, key_size);
 781                         return 0;
 782                 }
 783         }
 784
 785         /* iterated over all buckets and all elements */
 786         return -ENOENT;
 787 }
 788
 789 static 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
 796 static 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
 804 static 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
 815 static 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
 828 static void pcpu_copy_value(struct bpf_htab *htab, void __percpu *pptr,
 829                             void *value, bool onallcpus)
 830 {
 831         if (!onallcpus) {
 832                 /* copy true value_size bytes */
 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
 846 static void pcpu_init_value(struct bpf_htab *htab, void __percpu *pptr,
 847                             void *value, bool onallcpus)
 848 {
 849         /* When using prealloc and not setting the initial value on all cpus,
 850          * zero-fill element values for other cpus (just as what happens when
 851          * not using prealloc). Otherwise, bpf program has no way to ensure
 852          * known initial values for cpus other than current one
 853          * (onallcpus=false always when coming from bpf prog).
 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
 872 static 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
 878 static 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                         /* if we're updating the existing element,
 891                          * use per-cpu extra elems to avoid freelist_pop/push
 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                                 /* when map is full and update() is replacing
 909                                  * old element, it's ok to allocate, since
 910                                  * old element will be freed immediately.
 911                                  * Otherwise return an error
 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                         /* alloc_percpu zero-fills */
 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;
 958 dec_count:
 959         atomic_dec(&htab->count);
 960         return l_new;
 961 }
 962
 963 static 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                 /* elem already exists */
 968                 return -EEXIST;
 969
 970         if (!l_old && (map_flags & ~BPF_F_LOCK) == BPF_EXIST)
 971                 /* elem doesn't exist, cannot update it */
 972                 return -ENOENT;
 973
 974         return 0;
 975 }
 976
 977 /* Called from syscall or from eBPF program */
 978 static 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                 /* unknown flags */
 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                 /* find an element without taking the bucket lock */
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                         /* grab the element lock and update value in place */
1014                         copy_map_value_locked(map,
1015                                               l_old->key + round_up(key_size, 8),
1016                                               value, false);
1017                         return 0;
1018                 }
1019                 /* fall through, grab the bucket lock and lookup again.
1020                  * 99.9% chance that the element won't be found,
1021                  * but second lookup under lock has to be done.
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                 /* first lookup without the bucket lock didn't find the element,
1037                  * but second lookup with the bucket lock found it.
1038                  * This case is highly unlikely, but has to be dealt with:
1039                  * grab the element lock in addition to the bucket lock
1040                  * and update element in place
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                 /* all pre-allocated elements are in use or memory exhausted */
1053                 ret = PTR_ERR(l_new);
1054                 goto err;
1055         }
1056
1057         /* add new element to the head of the list, so that
1058          * concurrent search will find it before old elem
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;
1067 err:
1068         htab_unlock_bucket(htab, b, hash, flags);
1069         return ret;
1070 }
1071
1072 static 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                 /* unknown flags */
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         /* For LRU, we need to alloc before taking bucket's
1098          * spinlock because getting free nodes from LRU may need
1099          * to remove older elements from htab and this removal
1100          * operation will need a bucket lock.
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         /* add new element to the head of the list, so that
1118          * concurrent search will find it before old elem
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
1127 err:
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
1138 static 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                 /* unknown flags */
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                 /* per-cpu hash map can update value in-place */
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;
1188 err:
1189         htab_unlock_bucket(htab, b, hash, flags);
1190         return ret;
1191 }
1192
1193 static 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                 /* unknown flags */
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         /* For LRU, we need to alloc before taking bucket's
1220          * spinlock because LRU's elem alloc may need
1221          * to remove older elem from htab and this removal
1222          * operation will need a bucket lock.
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                 /* per-cpu hash map can update value in-place */
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;
1253 err:
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
1260 static 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
1266 static 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 /* Called from syscall or from eBPF program */
1274 static 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
1310 static 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
1346 static 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 /* Called when map->refcnt goes to zero, either from workqueue or from syscall */
1363 static 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         /* bpf_free_used_maps() or close(map_fd) will trigger this map_free callback.
1369          * bpf_free_used_maps() is called after bpf prog is no longer executing.
1370          * There is no need to synchronize_rcu() here to protect map elements.
1371          */
1372
1373         /* some of free_htab_elem() callbacks for elements of this map may
1374          * not have executed. Wait for them.
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
1390 static 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
1411 static 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
1475 static 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
1482 static 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
1490 static 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
1497 static 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
1505 static 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         /* while experimenting with hash tables with sizes ranging from 10 to
1560          * 1000, it was observed that a bucket can have upto 5 entries.
1561          */
1562         bucket_size = 5;
1563
1564 alloc:
1565         /* We cannot do copy_from_user or copy_to_user inside
1566          * the rcu_read_lock. Allocate enough space here.
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
1575 again:
1576         bpf_disable_instrumentation();
1577         rcu_read_lock();
1578 again_nocopy:
1579         dst_key = keys;
1580         dst_val = values;
1581         b = &htab->buckets[batch];
1582         head = &b->head;
1583         /* do not grab the lock unless need it (bucket_cnt > 0). */
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                 /* Note that since bucket_cnt > 0 here, it is implicit
1603                  * that the locked was grabbed, so release it.
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                 /* Note that since bucket_cnt > 0 here, it is implicit
1614                  * that the locked was grabbed, so release it.
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         /* Next block is only safe to run if you have grabbed the lock */
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                         /* bpf_lru_push_free() will acquire lru_lock, which
1654                          * may cause deadlock. See comments in function
1655                          * prealloc_lru_pop(). Let us do bpf_lru_push_free()
1656                          * after releasing the bucket lock.
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
1678 next_batch:
1679         /* If we are not copying data, we can go to next bucket and avoid
1680          * unlocking the rcu.
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
1705 after_loop:
1706         if (ret == -EFAULT)
1707                 goto out;
1708
1709         /* copy # of entries and next batch */
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
1715 out:
1716         kvfree(keys);
1717         kvfree(values);
1718         return ret;
1719 }
1720
1721 static int
1722 htab_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
1729 static int
1730 htab_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
1738 static int
1739 htab_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
1746 static int
1747 htab_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
1755 static int
1756 htab_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
1764 static int
1765 htab_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
1773 static int
1774 htab_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
1781 static int
1782 htab_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
1790 struct bpf_iter_seq_hash_map_info {
1791         struct bpf_map *map;
1792         struct bpf_htab *htab;
1793         void *percpu_value_buf; // non-zero means percpu hash
1794         u32 bucket_id;
1795         u32 skip_elems;
1796 };
1797
1798 static struct htab_elem *
1799 bpf_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         /* try to find next elem in the same bucket */
1815         if (prev_elem) {
1816                 /* no update/deletion on this bucket, prev_elem should be still valid
1817                  * and we won't skip elements.
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                 /* not found, unlock and go to the next bucket */
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
1854 static 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
1868 static 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
1877 static 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
1916 static int bpf_hash_map_seq_show(struct seq_file *seq, void *v)
1917 {
1918         return __bpf_hash_map_seq_show(seq, v);
1919 }
1920
1921 static 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
1929 static 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
1952 static 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
1959 static 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
1966 static 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
1973 static 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         /* disable migration so percpu value prepared here will be the
1995          * same as the one seen by the bpf program with bpf_map_lookup_elem().
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                                 /* current cpu value for percpu map */
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                         /* return value: 0 - continue, 1 - stop and return */
2017                         if (ret) {
2018                                 rcu_read_unlock();
2019                                 goto out;
2020                         }
2021                 }
2022                 rcu_read_unlock();
2023         }
2024 out:
2025         if (is_percpu)
2026                 migrate_enable();
2027         return num_elems;
2028 }
2029
2030 static int htab_map_btf_id;
2031 const 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
2051 static int htab_lru_map_btf_id;
2052 const 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 /* Called from eBPF program */
2074 static 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
2084 static 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
2096 int 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         /* per_cpu areas are zero-filled and bpf programs can only
2105          * access 'value_size' of them, so copying rounded areas
2106          * will not leak any kernel data
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         /* We do not mark LRU map element here in order to not mess up
2114          * eviction heuristics when user space does a map walk.
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;
2123 out:
2124         rcu_read_unlock();
2125         return ret;
2126 }
2127
2128 int 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
2146 static 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
2175 static int htab_percpu_map_btf_id;
2176 const 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
2195 static int htab_lru_percpu_map_btf_id;
2196 const 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
2215 static 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
2222 static 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 /* only called from syscall */
2244 int 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 /* only called from syscall */
2264 int 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
2282 static 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
2301 static 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
2311 static 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
2329 static 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
2335 static int htab_of_maps_map_btf_id;
2336 const 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 };