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