kernel/bpf/hashtab.c

   1 /* Copyright (c) 2011-2014 PLUMgrid, http://plumgrid.com
   2  * Copyright (c) 2016 Facebook
   3  *
   4  * This program is free software; you can redistribute it and/or
   5  * modify it under the terms of version 2 of the GNU General Public
   6  * License as published by the Free Software Foundation.
   7  *
   8  * This program is distributed in the hope that it will be useful, but
   9  * WITHOUT ANY WARRANTY; without even the implied warranty of
  10  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  11  * General Public License for more details.
  12  */
  13 #include <linux/bpf.h>
  14 #include <linux/jhash.h>
  15 #include <linux/filter.h>
  16 #include <linux/rculist_nulls.h>
  17 #include "percpu_freelist.h"
  18
  19 struct bucket {
  20         struct hlist_nulls_head head;
  21         raw_spinlock_t lock;
  22 };
  23
  24 struct bpf_htab {
  25         struct bpf_map map;
  26         struct bucket *buckets;
  27         void *elems;
  28         struct pcpu_freelist freelist;
  29         void __percpu *extra_elems;
  30         atomic_t count; /* number of elements in this hashtable */
  31         u32 n_buckets;  /* number of hash buckets */
  32         u32 elem_size;  /* size of each element in bytes */
  33 };
  34
  35 enum extra_elem_state {
  36         HTAB_NOT_AN_EXTRA_ELEM = 0,
  37         HTAB_EXTRA_ELEM_FREE,
  38         HTAB_EXTRA_ELEM_USED
  39 };
  40
  41 /* each htab element is struct htab_elem + key + value */
  42 struct htab_elem {
  43         union {
  44                 struct hlist_nulls_node hash_node;
  45                 struct {
  46                         void *padding;
  47                         union {
  48                                 struct bpf_htab *htab;
  49                                 struct pcpu_freelist_node fnode;
  50                         };
  51                 };
  52         };
  53         union {
  54                 struct rcu_head rcu;
  55                 enum extra_elem_state state;
  56         };
  57         u32 hash;
  58         char key[0] __aligned(8);
  59 };
  60
  61 static inline void htab_elem_set_ptr(struct htab_elem *l, u32 key_size,
  62                                      void __percpu *pptr)
  63 {
  64         *(void __percpu **)(l->key + key_size) = pptr;
  65 }
  66
  67 static inline void __percpu *htab_elem_get_ptr(struct htab_elem *l, u32 key_size)
  68 {
  69         return *(void __percpu **)(l->key + key_size);
  70 }
  71
  72 static struct htab_elem *get_htab_elem(struct bpf_htab *htab, int i)
  73 {
  74         return (struct htab_elem *) (htab->elems + i * htab->elem_size);
  75 }
  76
  77 static void htab_free_elems(struct bpf_htab *htab)
  78 {
  79         int i;
  80
  81         if (htab->map.map_type != BPF_MAP_TYPE_PERCPU_HASH)
  82                 goto free_elems;
  83
  84         for (i = 0; i < htab->map.max_entries; i++) {
  85                 void __percpu *pptr;
  86
  87                 pptr = htab_elem_get_ptr(get_htab_elem(htab, i),
  88                                          htab->map.key_size);
  89                 free_percpu(pptr);
  90         }
  91 free_elems:
  92         bpf_map_area_free(htab->elems);
  93 }
  94
  95 static int prealloc_elems_and_freelist(struct bpf_htab *htab)
  96 {
  97         int err = -ENOMEM, i;
  98
  99         htab->elems = bpf_map_area_alloc(htab->elem_size *
 100                                          htab->map.max_entries);
 101         if (!htab->elems)
 102                 return -ENOMEM;
 103
 104         if (htab->map.map_type != BPF_MAP_TYPE_PERCPU_HASH)
 105                 goto skip_percpu_elems;
 106
 107         for (i = 0; i < htab->map.max_entries; i++) {
 108                 u32 size = round_up(htab->map.value_size, 8);
 109                 void __percpu *pptr;
 110
 111                 pptr = __alloc_percpu_gfp(size, 8, GFP_USER | __GFP_NOWARN);
 112                 if (!pptr)
 113                         goto free_elems;
 114                 htab_elem_set_ptr(get_htab_elem(htab, i), htab->map.key_size,
 115                                   pptr);
 116         }
 117
 118 skip_percpu_elems:
 119         err = pcpu_freelist_init(&htab->freelist);
 120         if (err)
 121                 goto free_elems;
 122
 123         pcpu_freelist_populate(&htab->freelist,
 124                                htab->elems + offsetof(struct htab_elem, fnode),
 125                                htab->elem_size, htab->map.max_entries);
 126
 127         return 0;
 128
 129 free_elems:
 130         htab_free_elems(htab);
 131         return err;
 132 }
 133
 134 static int alloc_extra_elems(struct bpf_htab *htab)
 135 {
 136         void __percpu *pptr;
 137         int cpu;
 138
 139         pptr = __alloc_percpu_gfp(htab->elem_size, 8, GFP_USER | __GFP_NOWARN);
 140         if (!pptr)
 141                 return -ENOMEM;
 142
 143         for_each_possible_cpu(cpu) {
 144                 ((struct htab_elem *)per_cpu_ptr(pptr, cpu))->state =
 145                         HTAB_EXTRA_ELEM_FREE;
 146         }
 147         htab->extra_elems = pptr;
 148         return 0;
 149 }
 150
 151 /* Called from syscall */
 152 static struct bpf_map *htab_map_alloc(union bpf_attr *attr)
 153 {
 154         bool percpu = attr->map_type == BPF_MAP_TYPE_PERCPU_HASH;
 155         struct bpf_htab *htab;
 156         int err, i;
 157         u64 cost;
 158
 159         BUILD_BUG_ON(offsetof(struct htab_elem, htab) !=
 160                      offsetof(struct htab_elem, hash_node.pprev));
 161         BUILD_BUG_ON(offsetof(struct htab_elem, fnode.next) !=
 162                      offsetof(struct htab_elem, hash_node.pprev));
 163
 164         if (attr->map_flags & ~BPF_F_NO_PREALLOC)
 165                 /* reserved bits should not be used */
 166                 return ERR_PTR(-EINVAL);
 167
 168         htab = kzalloc(sizeof(*htab), GFP_USER);
 169         if (!htab)
 170                 return ERR_PTR(-ENOMEM);
 171
 172         /* mandatory map attributes */
 173         htab->map.map_type = attr->map_type;
 174         htab->map.key_size = attr->key_size;
 175         htab->map.value_size = attr->value_size;
 176         htab->map.max_entries = attr->max_entries;
 177         htab->map.map_flags = attr->map_flags;
 178
 179         /* check sanity of attributes.
 180          * value_size == 0 may be allowed in the future to use map as a set
 181          */
 182         err = -EINVAL;
 183         if (htab->map.max_entries == 0 || htab->map.key_size == 0 ||
 184             htab->map.value_size == 0)
 185                 goto free_htab;
 186
 187         /* hash table size must be power of 2 */
 188         htab->n_buckets = roundup_pow_of_two(htab->map.max_entries);
 189
 190         err = -E2BIG;
 191         if (htab->map.key_size > MAX_BPF_STACK)
 192                 /* eBPF programs initialize keys on stack, so they cannot be
 193                  * larger than max stack size
 194                  */
 195                 goto free_htab;
 196
 197         if (htab->map.value_size >= (1 << (KMALLOC_SHIFT_MAX - 1)) -
 198             MAX_BPF_STACK - sizeof(struct htab_elem))
 199                 /* if value_size is bigger, the user space won't be able to
 200                  * access the elements via bpf syscall. This check also makes
 201                  * sure that the elem_size doesn't overflow and it's
 202                  * kmalloc-able later in htab_map_update_elem()
 203                  */
 204                 goto free_htab;
 205
 206         if (percpu && round_up(htab->map.value_size, 8) > PCPU_MIN_UNIT_SIZE)
 207                 /* make sure the size for pcpu_alloc() is reasonable */
 208                 goto free_htab;
 209
 210         htab->elem_size = sizeof(struct htab_elem) +
 211                           round_up(htab->map.key_size, 8);
 212         if (percpu)
 213                 htab->elem_size += sizeof(void *);
 214         else
 215                 htab->elem_size += round_up(htab->map.value_size, 8);
 216
 217         /* prevent zero size kmalloc and check for u32 overflow */
 218         if (htab->n_buckets == 0 ||
 219             htab->n_buckets > U32_MAX / sizeof(struct bucket))
 220                 goto free_htab;
 221
 222         cost = (u64) htab->n_buckets * sizeof(struct bucket) +
 223                (u64) htab->elem_size * htab->map.max_entries;
 224
 225         if (percpu)
 226                 cost += (u64) round_up(htab->map.value_size, 8) *
 227                         num_possible_cpus() * htab->map.max_entries;
 228         else
 229                cost += (u64) htab->elem_size * num_possible_cpus();
 230
 231         if (cost >= U32_MAX - PAGE_SIZE)
 232                 /* make sure page count doesn't overflow */
 233                 goto free_htab;
 234
 235         htab->map.pages = round_up(cost, PAGE_SIZE) >> PAGE_SHIFT;
 236
 237         /* if map size is larger than memlock limit, reject it early */
 238         err = bpf_map_precharge_memlock(htab->map.pages);
 239         if (err)
 240                 goto free_htab;
 241
 242         err = -ENOMEM;
 243         htab->buckets = bpf_map_area_alloc(htab->n_buckets *
 244                                            sizeof(struct bucket));
 245         if (!htab->buckets)
 246                 goto free_htab;
 247
 248         for (i = 0; i < htab->n_buckets; i++) {
 249                 INIT_HLIST_NULLS_HEAD(&htab->buckets[i].head, i);
 250                 raw_spin_lock_init(&htab->buckets[i].lock);
 251         }
 252
 253         if (!percpu) {
 254                 err = alloc_extra_elems(htab);
 255                 if (err)
 256                         goto free_buckets;
 257         }
 258
 259         if (!(attr->map_flags & BPF_F_NO_PREALLOC)) {
 260                 err = prealloc_elems_and_freelist(htab);
 261                 if (err)
 262                         goto free_extra_elems;
 263         }
 264
 265         return &htab->map;
 266
 267 free_extra_elems:
 268         free_percpu(htab->extra_elems);
 269 free_buckets:
 270         bpf_map_area_free(htab->buckets);
 271 free_htab:
 272         kfree(htab);
 273         return ERR_PTR(err);
 274 }
 275
 276 static inline u32 htab_map_hash(const void *key, u32 key_len)
 277 {
 278         return jhash(key, key_len, 0);
 279 }
 280
 281 static inline struct bucket *__select_bucket(struct bpf_htab *htab, u32 hash)
 282 {
 283         return &htab->buckets[hash & (htab->n_buckets - 1)];
 284 }
 285
 286 static inline struct hlist_nulls_head *select_bucket(struct bpf_htab *htab, u32 hash)
 287 {
 288         return &__select_bucket(htab, hash)->head;
 289 }
 290
 291 /* this lookup function can only be called with bucket lock taken */
 292 static struct htab_elem *lookup_elem_raw(struct hlist_nulls_head *head, u32 hash,
 293                                          void *key, u32 key_size)
 294 {
 295         struct hlist_nulls_node *n;
 296         struct htab_elem *l;
 297
 298         hlist_nulls_for_each_entry_rcu(l, n, head, hash_node)
 299                 if (l->hash == hash && !memcmp(&l->key, key, key_size))
 300                         return l;
 301
 302         return NULL;
 303 }
 304
 305 /* can be called without bucket lock. it will repeat the loop in
 306  * the unlikely event when elements moved from one bucket into another
 307  * while link list is being walked
 308  */
 309 static struct htab_elem *lookup_nulls_elem_raw(struct hlist_nulls_head *head,
 310                                                u32 hash, void *key,
 311                                                u32 key_size, u32 n_buckets)
 312 {
 313         struct hlist_nulls_node *n;
 314         struct htab_elem *l;
 315
 316 again:
 317         hlist_nulls_for_each_entry_rcu(l, n, head, hash_node)
 318                 if (l->hash == hash && !memcmp(&l->key, key, key_size))
 319                         return l;
 320
 321         if (unlikely(get_nulls_value(n) != (hash & (n_buckets - 1))))
 322                 goto again;
 323
 324         return NULL;
 325 }
 326
 327 /* Called from syscall or from eBPF program */
 328 static void *__htab_map_lookup_elem(struct bpf_map *map, void *key)
 329 {
 330         struct bpf_htab *htab = container_of(map, struct bpf_htab, map);
 331         struct hlist_nulls_head *head;
 332         struct htab_elem *l;
 333         u32 hash, key_size;
 334
 335         /* Must be called with rcu_read_lock. */
 336         WARN_ON_ONCE(!rcu_read_lock_held());
 337
 338         key_size = map->key_size;
 339
 340         hash = htab_map_hash(key, key_size);
 341
 342         head = select_bucket(htab, hash);
 343
 344         l = lookup_nulls_elem_raw(head, hash, key, key_size, htab->n_buckets);
 345
 346         return l;
 347 }
 348
 349 static void *htab_map_lookup_elem(struct bpf_map *map, void *key)
 350 {
 351         struct htab_elem *l = __htab_map_lookup_elem(map, key);
 352
 353         if (l)
 354                 return l->key + round_up(map->key_size, 8);
 355
 356         return NULL;
 357 }
 358
 359 /* Called from syscall */
 360 static int htab_map_get_next_key(struct bpf_map *map, void *key, void *next_key)
 361 {
 362         struct bpf_htab *htab = container_of(map, struct bpf_htab, map);
 363         struct hlist_nulls_head *head;
 364         struct htab_elem *l, *next_l;
 365         u32 hash, key_size;
 366         int i = 0;
 367
 368         WARN_ON_ONCE(!rcu_read_lock_held());
 369
 370         key_size = map->key_size;
 371
 372         if (!key)
 373                 goto find_first_elem;
 374
 375         hash = htab_map_hash(key, key_size);
 376
 377         head = select_bucket(htab, hash);
 378
 379         /* lookup the key */
 380         l = lookup_nulls_elem_raw(head, hash, key, key_size, htab->n_buckets);
 381
 382         if (!l)
 383                 goto find_first_elem;
 384
 385         /* key was found, get next key in the same bucket */
 386         next_l = hlist_nulls_entry_safe(rcu_dereference_raw(hlist_nulls_next_rcu(&l->hash_node)),
 387                                   struct htab_elem, hash_node);
 388
 389         if (next_l) {
 390                 /* if next elem in this hash list is non-zero, just return it */
 391                 memcpy(next_key, next_l->key, key_size);
 392                 return 0;
 393         }
 394
 395         /* no more elements in this hash list, go to the next bucket */
 396         i = hash & (htab->n_buckets - 1);
 397         i++;
 398
 399 find_first_elem:
 400         /* iterate over buckets */
 401         for (; i < htab->n_buckets; i++) {
 402                 head = select_bucket(htab, i);
 403
 404                 /* pick first element in the bucket */
 405                 next_l = hlist_nulls_entry_safe(rcu_dereference_raw(hlist_nulls_first_rcu(head)),
 406                                           struct htab_elem, hash_node);
 407                 if (next_l) {
 408                         /* if it's not empty, just return it */
 409                         memcpy(next_key, next_l->key, key_size);
 410                         return 0;
 411                 }
 412         }
 413
 414         /* iterated over all buckets and all elements */
 415         return -ENOENT;
 416 }
 417
 418 static void htab_elem_free(struct bpf_htab *htab, struct htab_elem *l)
 419 {
 420         if (htab->map.map_type == BPF_MAP_TYPE_PERCPU_HASH)
 421                 free_percpu(htab_elem_get_ptr(l, htab->map.key_size));
 422         kfree(l);
 423 }
 424
 425 static void htab_elem_free_rcu(struct rcu_head *head)
 426 {
 427         struct htab_elem *l = container_of(head, struct htab_elem, rcu);
 428         struct bpf_htab *htab = l->htab;
 429
 430         /* must increment bpf_prog_active to avoid kprobe+bpf triggering while
 431          * we're calling kfree, otherwise deadlock is possible if kprobes
 432          * are placed somewhere inside of slub
 433          */
 434         preempt_disable();
 435         __this_cpu_inc(bpf_prog_active);
 436         htab_elem_free(htab, l);
 437         __this_cpu_dec(bpf_prog_active);
 438         preempt_enable();
 439 }
 440
 441 static void free_htab_elem(struct bpf_htab *htab, struct htab_elem *l)
 442 {
 443         if (l->state == HTAB_EXTRA_ELEM_USED) {
 444                 l->state = HTAB_EXTRA_ELEM_FREE;
 445                 return;
 446         }
 447
 448         if (!(htab->map.map_flags & BPF_F_NO_PREALLOC)) {
 449                 pcpu_freelist_push(&htab->freelist, &l->fnode);
 450         } else {
 451                 atomic_dec(&htab->count);
 452                 l->htab = htab;
 453                 call_rcu(&l->rcu, htab_elem_free_rcu);
 454         }
 455 }
 456
 457 static struct htab_elem *alloc_htab_elem(struct bpf_htab *htab, void *key,
 458                                          void *value, u32 key_size, u32 hash,
 459                                          bool percpu, bool onallcpus,
 460                                          bool old_elem_exists)
 461 {
 462         u32 size = htab->map.value_size;
 463         bool prealloc = !(htab->map.map_flags & BPF_F_NO_PREALLOC);
 464         struct htab_elem *l_new;
 465         void __percpu *pptr;
 466         int err = 0;
 467
 468         if (prealloc) {
 469                 struct pcpu_freelist_node *l;
 470
 471                 l = pcpu_freelist_pop(&htab->freelist);
 472                 if (!l)
 473                         err = -E2BIG;
 474                 else
 475                         l_new = container_of(l, struct htab_elem, fnode);
 476         } else {
 477                 if (atomic_inc_return(&htab->count) > htab->map.max_entries) {
 478                         atomic_dec(&htab->count);
 479                         err = -E2BIG;
 480                 } else {
 481                         l_new = kmalloc(htab->elem_size,
 482                                         GFP_ATOMIC | __GFP_NOWARN);
 483                         if (!l_new)
 484                                 return ERR_PTR(-ENOMEM);
 485                 }
 486         }
 487
 488         if (err) {
 489                 if (!old_elem_exists)
 490                         return ERR_PTR(err);
 491
 492                 /* if we're updating the existing element and the hash table
 493                  * is full, use per-cpu extra elems
 494                  */
 495                 l_new = this_cpu_ptr(htab->extra_elems);
 496                 if (l_new->state != HTAB_EXTRA_ELEM_FREE)
 497                         return ERR_PTR(-E2BIG);
 498                 l_new->state = HTAB_EXTRA_ELEM_USED;
 499         } else {
 500                 l_new->state = HTAB_NOT_AN_EXTRA_ELEM;
 501         }
 502
 503         memcpy(l_new->key, key, key_size);
 504         if (percpu) {
 505                 /* round up value_size to 8 bytes */
 506                 size = round_up(size, 8);
 507
 508                 if (prealloc) {
 509                         pptr = htab_elem_get_ptr(l_new, key_size);
 510                 } else {
 511                         /* alloc_percpu zero-fills */
 512                         pptr = __alloc_percpu_gfp(size, 8,
 513                                                   GFP_ATOMIC | __GFP_NOWARN);
 514                         if (!pptr) {
 515                                 kfree(l_new);
 516                                 return ERR_PTR(-ENOMEM);
 517                         }
 518                 }
 519
 520                 if (!onallcpus) {
 521                         /* copy true value_size bytes */
 522                         memcpy(this_cpu_ptr(pptr), value, htab->map.value_size);
 523                 } else {
 524                         int off = 0, cpu;
 525
 526                         for_each_possible_cpu(cpu) {
 527                                 bpf_long_memcpy(per_cpu_ptr(pptr, cpu),
 528                                                 value + off, size);
 529                                 off += size;
 530                         }
 531                 }
 532                 if (!prealloc)
 533                         htab_elem_set_ptr(l_new, key_size, pptr);
 534         } else {
 535                 memcpy(l_new->key + round_up(key_size, 8), value, size);
 536         }
 537
 538         l_new->hash = hash;
 539         return l_new;
 540 }
 541
 542 static int check_flags(struct bpf_htab *htab, struct htab_elem *l_old,
 543                        u64 map_flags)
 544 {
 545         if (l_old && map_flags == BPF_NOEXIST)
 546                 /* elem already exists */
 547                 return -EEXIST;
 548
 549         if (!l_old && map_flags == BPF_EXIST)
 550                 /* elem doesn't exist, cannot update it */
 551                 return -ENOENT;
 552
 553         return 0;
 554 }
 555
 556 /* Called from syscall or from eBPF program */
 557 static int htab_map_update_elem(struct bpf_map *map, void *key, void *value,
 558                                 u64 map_flags)
 559 {
 560         struct bpf_htab *htab = container_of(map, struct bpf_htab, map);
 561         struct htab_elem *l_new = NULL, *l_old;
 562         struct hlist_nulls_head *head;
 563         unsigned long flags;
 564         struct bucket *b;
 565         u32 key_size, hash;
 566         int ret;
 567
 568         if (unlikely(map_flags > BPF_EXIST))
 569                 /* unknown flags */
 570                 return -EINVAL;
 571
 572         WARN_ON_ONCE(!rcu_read_lock_held());
 573
 574         key_size = map->key_size;
 575
 576         hash = htab_map_hash(key, key_size);
 577
 578         b = __select_bucket(htab, hash);
 579         head = &b->head;
 580
 581         /* bpf_map_update_elem() can be called in_irq() */
 582         raw_spin_lock_irqsave(&b->lock, flags);
 583
 584         l_old = lookup_elem_raw(head, hash, key, key_size);
 585
 586         ret = check_flags(htab, l_old, map_flags);
 587         if (ret)
 588                 goto err;
 589
 590         l_new = alloc_htab_elem(htab, key, value, key_size, hash, false, false,
 591                                 !!l_old);
 592         if (IS_ERR(l_new)) {
 593                 /* all pre-allocated elements are in use or memory exhausted */
 594                 ret = PTR_ERR(l_new);
 595                 goto err;
 596         }
 597
 598         /* add new element to the head of the list, so that
 599          * concurrent search will find it before old elem
 600          */
 601         hlist_nulls_add_head_rcu(&l_new->hash_node, head);
 602         if (l_old) {
 603                 hlist_nulls_del_rcu(&l_old->hash_node);
 604                 free_htab_elem(htab, l_old);
 605         }
 606         ret = 0;
 607 err:
 608         raw_spin_unlock_irqrestore(&b->lock, flags);
 609         return ret;
 610 }
 611
 612 static int __htab_percpu_map_update_elem(struct bpf_map *map, void *key,
 613                                          void *value, u64 map_flags,
 614                                          bool onallcpus)
 615 {
 616         struct bpf_htab *htab = container_of(map, struct bpf_htab, map);
 617         struct htab_elem *l_new = NULL, *l_old;
 618         struct hlist_nulls_head *head;
 619         unsigned long flags;
 620         struct bucket *b;
 621         u32 key_size, hash;
 622         int ret;
 623
 624         if (unlikely(map_flags > BPF_EXIST))
 625                 /* unknown flags */
 626                 return -EINVAL;
 627
 628         WARN_ON_ONCE(!rcu_read_lock_held());
 629
 630         key_size = map->key_size;
 631
 632         hash = htab_map_hash(key, key_size);
 633
 634         b = __select_bucket(htab, hash);
 635         head = &b->head;
 636
 637         /* bpf_map_update_elem() can be called in_irq() */
 638         raw_spin_lock_irqsave(&b->lock, flags);
 639
 640         l_old = lookup_elem_raw(head, hash, key, key_size);
 641
 642         ret = check_flags(htab, l_old, map_flags);
 643         if (ret)
 644                 goto err;
 645
 646         if (l_old) {
 647                 void __percpu *pptr = htab_elem_get_ptr(l_old, key_size);
 648                 u32 size = htab->map.value_size;
 649
 650                 /* per-cpu hash map can update value in-place */
 651                 if (!onallcpus) {
 652                         memcpy(this_cpu_ptr(pptr), value, size);
 653                 } else {
 654                         int off = 0, cpu;
 655
 656                         size = round_up(size, 8);
 657                         for_each_possible_cpu(cpu) {
 658                                 bpf_long_memcpy(per_cpu_ptr(pptr, cpu),
 659                                                 value + off, size);
 660                                 off += size;
 661                         }
 662                 }
 663         } else {
 664                 l_new = alloc_htab_elem(htab, key, value, key_size,
 665                                         hash, true, onallcpus, false);
 666                 if (IS_ERR(l_new)) {
 667                         ret = PTR_ERR(l_new);
 668                         goto err;
 669                 }
 670                 hlist_nulls_add_head_rcu(&l_new->hash_node, head);
 671         }
 672         ret = 0;
 673 err:
 674         raw_spin_unlock_irqrestore(&b->lock, flags);
 675         return ret;
 676 }
 677
 678 static int htab_percpu_map_update_elem(struct bpf_map *map, void *key,
 679                                        void *value, u64 map_flags)
 680 {
 681         return __htab_percpu_map_update_elem(map, key, value, map_flags, false);
 682 }
 683
 684 /* Called from syscall or from eBPF program */
 685 static int htab_map_delete_elem(struct bpf_map *map, void *key)
 686 {
 687         struct bpf_htab *htab = container_of(map, struct bpf_htab, map);
 688         struct hlist_nulls_head *head;
 689         struct bucket *b;
 690         struct htab_elem *l;
 691         unsigned long flags;
 692         u32 hash, key_size;
 693         int ret = -ENOENT;
 694
 695         WARN_ON_ONCE(!rcu_read_lock_held());
 696
 697         key_size = map->key_size;
 698
 699         hash = htab_map_hash(key, key_size);
 700         b = __select_bucket(htab, hash);
 701         head = &b->head;
 702
 703         raw_spin_lock_irqsave(&b->lock, flags);
 704
 705         l = lookup_elem_raw(head, hash, key, key_size);
 706
 707         if (l) {
 708                 hlist_nulls_del_rcu(&l->hash_node);
 709                 free_htab_elem(htab, l);
 710                 ret = 0;
 711         }
 712
 713         raw_spin_unlock_irqrestore(&b->lock, flags);
 714         return ret;
 715 }
 716
 717 static void delete_all_elements(struct bpf_htab *htab)
 718 {
 719         int i;
 720
 721         for (i = 0; i < htab->n_buckets; i++) {
 722                 struct hlist_nulls_head *head = select_bucket(htab, i);
 723                 struct hlist_nulls_node *n;
 724                 struct htab_elem *l;
 725
 726                 hlist_nulls_for_each_entry_safe(l, n, head, hash_node) {
 727                         hlist_nulls_del_rcu(&l->hash_node);
 728                         if (l->state != HTAB_EXTRA_ELEM_USED)
 729                                 htab_elem_free(htab, l);
 730                 }
 731         }
 732 }
 733 /* Called when map->refcnt goes to zero, either from workqueue or from syscall */
 734 static void htab_map_free(struct bpf_map *map)
 735 {
 736         struct bpf_htab *htab = container_of(map, struct bpf_htab, map);
 737
 738         /* at this point bpf_prog->aux->refcnt == 0 and this map->refcnt == 0,
 739          * so the programs (can be more than one that used this map) were
 740          * disconnected from events. Wait for outstanding critical sections in
 741          * these programs to complete
 742          */
 743         synchronize_rcu();
 744
 745         /* some of free_htab_elem() callbacks for elements of this map may
 746          * not have executed. Wait for them.
 747          */
 748         rcu_barrier();
 749         if (htab->map.map_flags & BPF_F_NO_PREALLOC) {
 750                 delete_all_elements(htab);
 751         } else {
 752                 htab_free_elems(htab);
 753                 pcpu_freelist_destroy(&htab->freelist);
 754         }
 755         free_percpu(htab->extra_elems);
 756         bpf_map_area_free(htab->buckets);
 757         kfree(htab);
 758 }
 759
 760 static const struct bpf_map_ops htab_ops = {
 761         .map_alloc = htab_map_alloc,
 762         .map_free = htab_map_free,
 763         .map_get_next_key = htab_map_get_next_key,
 764         .map_lookup_elem = htab_map_lookup_elem,
 765         .map_update_elem = htab_map_update_elem,
 766         .map_delete_elem = htab_map_delete_elem,
 767 };
 768
 769 static struct bpf_map_type_list htab_type __read_mostly = {
 770         .ops = &htab_ops,
 771         .type = BPF_MAP_TYPE_HASH,
 772 };
 773
 774 /* Called from eBPF program */
 775 static void *htab_percpu_map_lookup_elem(struct bpf_map *map, void *key)
 776 {
 777         struct htab_elem *l = __htab_map_lookup_elem(map, key);
 778
 779         if (l)
 780                 return this_cpu_ptr(htab_elem_get_ptr(l, map->key_size));
 781         else
 782                 return NULL;
 783 }
 784
 785 int bpf_percpu_hash_copy(struct bpf_map *map, void *key, void *value)
 786 {
 787         struct htab_elem *l;
 788         void __percpu *pptr;
 789         int ret = -ENOENT;
 790         int cpu, off = 0;
 791         u32 size;
 792
 793         /* per_cpu areas are zero-filled and bpf programs can only
 794          * access 'value_size' of them, so copying rounded areas
 795          * will not leak any kernel data
 796          */
 797         size = round_up(map->value_size, 8);
 798         rcu_read_lock();
 799         l = __htab_map_lookup_elem(map, key);
 800         if (!l)
 801                 goto out;
 802         pptr = htab_elem_get_ptr(l, map->key_size);
 803         for_each_possible_cpu(cpu) {
 804                 bpf_long_memcpy(value + off,
 805                                 per_cpu_ptr(pptr, cpu), size);
 806                 off += size;
 807         }
 808         ret = 0;
 809 out:
 810         rcu_read_unlock();
 811         return ret;
 812 }
 813
 814 int bpf_percpu_hash_update(struct bpf_map *map, void *key, void *value,
 815                            u64 map_flags)
 816 {
 817         int ret;
 818
 819         rcu_read_lock();
 820         ret = __htab_percpu_map_update_elem(map, key, value, map_flags, true);
 821         rcu_read_unlock();
 822
 823         return ret;
 824 }
 825
 826 static const struct bpf_map_ops htab_percpu_ops = {
 827         .map_alloc = htab_map_alloc,
 828         .map_free = htab_map_free,
 829         .map_get_next_key = htab_map_get_next_key,
 830         .map_lookup_elem = htab_percpu_map_lookup_elem,
 831         .map_update_elem = htab_percpu_map_update_elem,
 832         .map_delete_elem = htab_map_delete_elem,
 833 };
 834
 835 static struct bpf_map_type_list htab_percpu_type __read_mostly = {
 836         .ops = &htab_percpu_ops,
 837         .type = BPF_MAP_TYPE_PERCPU_HASH,
 838 };
 839
 840 static int __init register_htab_map(void)
 841 {
 842         bpf_register_map_type(&htab_type);
 843         bpf_register_map_type(&htab_percpu_type);
 844         return 0;
 845 }
 846 late_initcall(register_htab_map);