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/btf.h> 15 #include <linux/jhash.h> 16 #include <linux/filter.h> 17 #include <linux/rculist_nulls.h> 18 #include <linux/random.h> 19 #include <uapi/linux/btf.h> 20 #include "percpu_freelist.h" 21 #include "bpf_lru_list.h" 22 #include "map_in_map.h" 23 24 #define HTAB_CREATE_FLAG_MASK \ 25 (BPF_F_NO_PREALLOC | BPF_F_NO_COMMON_LRU | BPF_F_NUMA_NODE | \ 26 BPF_F_RDONLY | BPF_F_WRONLY | BPF_F_ZERO_SEED) 27 28 struct bucket { 29 struct hlist_nulls_head head; 30 raw_spinlock_t lock; 31 }; 32 33 struct bpf_htab { 34 struct bpf_map map; 35 struct bucket *buckets; 36 void *elems; 37 union { 38 struct pcpu_freelist freelist; 39 struct bpf_lru lru; 40 }; 41 struct htab_elem *__percpu *extra_elems; 42 atomic_t count; /* number of elements in this hashtable */ 43 u32 n_buckets; /* number of hash buckets */ 44 u32 elem_size; /* size of each element in bytes */ 45 u32 hashrnd; 46 }; 47 48 /* each htab element is struct htab_elem + key + value */ 49 struct htab_elem { 50 union { 51 struct hlist_nulls_node hash_node; 52 struct { 53 void *padding; 54 union { 55 struct bpf_htab *htab; 56 struct pcpu_freelist_node fnode; 57 }; 58 }; 59 }; 60 union { 61 struct rcu_head rcu; 62 struct bpf_lru_node lru_node; 63 }; 64 u32 hash; 65 char key[0] __aligned(8); 66 }; 67 68 static bool htab_lru_map_delete_node(void *arg, struct bpf_lru_node *node); 69 70 static bool htab_is_lru(const struct bpf_htab *htab) 71 { 72 return htab->map.map_type == BPF_MAP_TYPE_LRU_HASH || 73 htab->map.map_type == BPF_MAP_TYPE_LRU_PERCPU_HASH; 74 } 75 76 static bool htab_is_percpu(const struct bpf_htab *htab) 77 { 78 return htab->map.map_type == BPF_MAP_TYPE_PERCPU_HASH || 79 htab->map.map_type == BPF_MAP_TYPE_LRU_PERCPU_HASH; 80 } 81 82 static bool htab_is_prealloc(const struct bpf_htab *htab) 83 { 84 return !(htab->map.map_flags & BPF_F_NO_PREALLOC); 85 } 86 87 static inline void htab_elem_set_ptr(struct htab_elem *l, u32 key_size, 88 void __percpu *pptr) 89 { 90 *(void __percpu **)(l->key + key_size) = pptr; 91 } 92 93 static inline void __percpu *htab_elem_get_ptr(struct htab_elem *l, u32 key_size) 94 { 95 return *(void __percpu **)(l->key + key_size); 96 } 97 98 static void *fd_htab_map_get_ptr(const struct bpf_map *map, struct htab_elem *l) 99 { 100 return *(void **)(l->key + roundup(map->key_size, 8)); 101 } 102 103 static struct htab_elem *get_htab_elem(struct bpf_htab *htab, int i) 104 { 105 return (struct htab_elem *) (htab->elems + i * htab->elem_size); 106 } 107 108 static void htab_free_elems(struct bpf_htab *htab) 109 { 110 int i; 111 112 if (!htab_is_percpu(htab)) 113 goto free_elems; 114 115 for (i = 0; i < htab->map.max_entries; i++) { 116 void __percpu *pptr; 117 118 pptr = htab_elem_get_ptr(get_htab_elem(htab, i), 119 htab->map.key_size); 120 free_percpu(pptr); 121 cond_resched(); 122 } 123 free_elems: 124 bpf_map_area_free(htab->elems); 125 } 126 127 static struct htab_elem *prealloc_lru_pop(struct bpf_htab *htab, void *key, 128 u32 hash) 129 { 130 struct bpf_lru_node *node = bpf_lru_pop_free(&htab->lru, hash); 131 struct htab_elem *l; 132 133 if (node) { 134 l = container_of(node, struct htab_elem, lru_node); 135 memcpy(l->key, key, htab->map.key_size); 136 return l; 137 } 138 139 return NULL; 140 } 141 142 static int prealloc_init(struct bpf_htab *htab) 143 { 144 u32 num_entries = htab->map.max_entries; 145 int err = -ENOMEM, i; 146 147 if (!htab_is_percpu(htab) && !htab_is_lru(htab)) 148 num_entries += num_possible_cpus(); 149 150 htab->elems = bpf_map_area_alloc(htab->elem_size * num_entries, 151 htab->map.numa_node); 152 if (!htab->elems) 153 return -ENOMEM; 154 155 if (!htab_is_percpu(htab)) 156 goto skip_percpu_elems; 157 158 for (i = 0; i < num_entries; i++) { 159 u32 size = round_up(htab->map.value_size, 8); 160 void __percpu *pptr; 161 162 pptr = __alloc_percpu_gfp(size, 8, GFP_USER | __GFP_NOWARN); 163 if (!pptr) 164 goto free_elems; 165 htab_elem_set_ptr(get_htab_elem(htab, i), htab->map.key_size, 166 pptr); 167 cond_resched(); 168 } 169 170 skip_percpu_elems: 171 if (htab_is_lru(htab)) 172 err = bpf_lru_init(&htab->lru, 173 htab->map.map_flags & BPF_F_NO_COMMON_LRU, 174 offsetof(struct htab_elem, hash) - 175 offsetof(struct htab_elem, lru_node), 176 htab_lru_map_delete_node, 177 htab); 178 else 179 err = pcpu_freelist_init(&htab->freelist); 180 181 if (err) 182 goto free_elems; 183 184 if (htab_is_lru(htab)) 185 bpf_lru_populate(&htab->lru, htab->elems, 186 offsetof(struct htab_elem, lru_node), 187 htab->elem_size, num_entries); 188 else 189 pcpu_freelist_populate(&htab->freelist, 190 htab->elems + offsetof(struct htab_elem, fnode), 191 htab->elem_size, num_entries); 192 193 return 0; 194 195 free_elems: 196 htab_free_elems(htab); 197 return err; 198 } 199 200 static void prealloc_destroy(struct bpf_htab *htab) 201 { 202 htab_free_elems(htab); 203 204 if (htab_is_lru(htab)) 205 bpf_lru_destroy(&htab->lru); 206 else 207 pcpu_freelist_destroy(&htab->freelist); 208 } 209 210 static int alloc_extra_elems(struct bpf_htab *htab) 211 { 212 struct htab_elem *__percpu *pptr, *l_new; 213 struct pcpu_freelist_node *l; 214 int cpu; 215 216 pptr = __alloc_percpu_gfp(sizeof(struct htab_elem *), 8, 217 GFP_USER | __GFP_NOWARN); 218 if (!pptr) 219 return -ENOMEM; 220 221 for_each_possible_cpu(cpu) { 222 l = pcpu_freelist_pop(&htab->freelist); 223 /* pop will succeed, since prealloc_init() 224 * preallocated extra num_possible_cpus elements 225 */ 226 l_new = container_of(l, struct htab_elem, fnode); 227 *per_cpu_ptr(pptr, cpu) = l_new; 228 } 229 htab->extra_elems = pptr; 230 return 0; 231 } 232 233 /* Called from syscall */ 234 static int htab_map_alloc_check(union bpf_attr *attr) 235 { 236 bool percpu = (attr->map_type == BPF_MAP_TYPE_PERCPU_HASH || 237 attr->map_type == BPF_MAP_TYPE_LRU_PERCPU_HASH); 238 bool lru = (attr->map_type == BPF_MAP_TYPE_LRU_HASH || 239 attr->map_type == BPF_MAP_TYPE_LRU_PERCPU_HASH); 240 /* percpu_lru means each cpu has its own LRU list. 241 * it is different from BPF_MAP_TYPE_PERCPU_HASH where 242 * the map's value itself is percpu. percpu_lru has 243 * nothing to do with the map's value. 244 */ 245 bool percpu_lru = (attr->map_flags & BPF_F_NO_COMMON_LRU); 246 bool prealloc = !(attr->map_flags & BPF_F_NO_PREALLOC); 247 bool zero_seed = (attr->map_flags & BPF_F_ZERO_SEED); 248 int numa_node = bpf_map_attr_numa_node(attr); 249 250 BUILD_BUG_ON(offsetof(struct htab_elem, htab) != 251 offsetof(struct htab_elem, hash_node.pprev)); 252 BUILD_BUG_ON(offsetof(struct htab_elem, fnode.next) != 253 offsetof(struct htab_elem, hash_node.pprev)); 254 255 if (lru && !capable(CAP_SYS_ADMIN)) 256 /* LRU implementation is much complicated than other 257 * maps. Hence, limit to CAP_SYS_ADMIN for now. 258 */ 259 return -EPERM; 260 261 if (zero_seed && !capable(CAP_SYS_ADMIN)) 262 /* Guard against local DoS, and discourage production use. */ 263 return -EPERM; 264 265 if (attr->map_flags & ~HTAB_CREATE_FLAG_MASK) 266 /* reserved bits should not be used */ 267 return -EINVAL; 268 269 if (!lru && percpu_lru) 270 return -EINVAL; 271 272 if (lru && !prealloc) 273 return -ENOTSUPP; 274 275 if (numa_node != NUMA_NO_NODE && (percpu || percpu_lru)) 276 return -EINVAL; 277 278 /* check sanity of attributes. 279 * value_size == 0 may be allowed in the future to use map as a set 280 */ 281 if (attr->max_entries == 0 || attr->key_size == 0 || 282 attr->value_size == 0) 283 return -EINVAL; 284 285 if (attr->key_size > MAX_BPF_STACK) 286 /* eBPF programs initialize keys on stack, so they cannot be 287 * larger than max stack size 288 */ 289 return -E2BIG; 290 291 if (attr->value_size >= KMALLOC_MAX_SIZE - 292 MAX_BPF_STACK - sizeof(struct htab_elem)) 293 /* if value_size is bigger, the user space won't be able to 294 * access the elements via bpf syscall. This check also makes 295 * sure that the elem_size doesn't overflow and it's 296 * kmalloc-able later in htab_map_update_elem() 297 */ 298 return -E2BIG; 299 300 return 0; 301 } 302 303 static struct bpf_map *htab_map_alloc(union bpf_attr *attr) 304 { 305 bool percpu = (attr->map_type == BPF_MAP_TYPE_PERCPU_HASH || 306 attr->map_type == BPF_MAP_TYPE_LRU_PERCPU_HASH); 307 bool lru = (attr->map_type == BPF_MAP_TYPE_LRU_HASH || 308 attr->map_type == BPF_MAP_TYPE_LRU_PERCPU_HASH); 309 /* percpu_lru means each cpu has its own LRU list. 310 * it is different from BPF_MAP_TYPE_PERCPU_HASH where 311 * the map's value itself is percpu. percpu_lru has 312 * nothing to do with the map's value. 313 */ 314 bool percpu_lru = (attr->map_flags & BPF_F_NO_COMMON_LRU); 315 bool prealloc = !(attr->map_flags & BPF_F_NO_PREALLOC); 316 struct bpf_htab *htab; 317 int err, i; 318 u64 cost; 319 320 htab = kzalloc(sizeof(*htab), GFP_USER); 321 if (!htab) 322 return ERR_PTR(-ENOMEM); 323 324 bpf_map_init_from_attr(&htab->map, attr); 325 326 if (percpu_lru) { 327 /* ensure each CPU's lru list has >=1 elements. 328 * since we are at it, make each lru list has the same 329 * number of elements. 330 */ 331 htab->map.max_entries = roundup(attr->max_entries, 332 num_possible_cpus()); 333 if (htab->map.max_entries < attr->max_entries) 334 htab->map.max_entries = rounddown(attr->max_entries, 335 num_possible_cpus()); 336 } 337 338 /* hash table size must be power of 2 */ 339 htab->n_buckets = roundup_pow_of_two(htab->map.max_entries); 340 341 htab->elem_size = sizeof(struct htab_elem) + 342 round_up(htab->map.key_size, 8); 343 if (percpu) 344 htab->elem_size += sizeof(void *); 345 else 346 htab->elem_size += round_up(htab->map.value_size, 8); 347 348 err = -E2BIG; 349 /* prevent zero size kmalloc and check for u32 overflow */ 350 if (htab->n_buckets == 0 || 351 htab->n_buckets > U32_MAX / sizeof(struct bucket)) 352 goto free_htab; 353 354 cost = (u64) htab->n_buckets * sizeof(struct bucket) + 355 (u64) htab->elem_size * htab->map.max_entries; 356 357 if (percpu) 358 cost += (u64) round_up(htab->map.value_size, 8) * 359 num_possible_cpus() * htab->map.max_entries; 360 else 361 cost += (u64) htab->elem_size * num_possible_cpus(); 362 363 if (cost >= U32_MAX - PAGE_SIZE) 364 /* make sure page count doesn't overflow */ 365 goto free_htab; 366 367 htab->map.pages = round_up(cost, PAGE_SIZE) >> PAGE_SHIFT; 368 369 /* if map size is larger than memlock limit, reject it early */ 370 err = bpf_map_precharge_memlock(htab->map.pages); 371 if (err) 372 goto free_htab; 373 374 err = -ENOMEM; 375 htab->buckets = bpf_map_area_alloc(htab->n_buckets * 376 sizeof(struct bucket), 377 htab->map.numa_node); 378 if (!htab->buckets) 379 goto free_htab; 380 381 if (htab->map.map_flags & BPF_F_ZERO_SEED) 382 htab->hashrnd = 0; 383 else 384 htab->hashrnd = get_random_int(); 385 386 for (i = 0; i < htab->n_buckets; i++) { 387 INIT_HLIST_NULLS_HEAD(&htab->buckets[i].head, i); 388 raw_spin_lock_init(&htab->buckets[i].lock); 389 } 390 391 if (prealloc) { 392 err = prealloc_init(htab); 393 if (err) 394 goto free_buckets; 395 396 if (!percpu && !lru) { 397 /* lru itself can remove the least used element, so 398 * there is no need for an extra elem during map_update. 399 */ 400 err = alloc_extra_elems(htab); 401 if (err) 402 goto free_prealloc; 403 } 404 } 405 406 return &htab->map; 407 408 free_prealloc: 409 prealloc_destroy(htab); 410 free_buckets: 411 bpf_map_area_free(htab->buckets); 412 free_htab: 413 kfree(htab); 414 return ERR_PTR(err); 415 } 416 417 static inline u32 htab_map_hash(const void *key, u32 key_len, u32 hashrnd) 418 { 419 return jhash(key, key_len, hashrnd); 420 } 421 422 static inline struct bucket *__select_bucket(struct bpf_htab *htab, u32 hash) 423 { 424 return &htab->buckets[hash & (htab->n_buckets - 1)]; 425 } 426 427 static inline struct hlist_nulls_head *select_bucket(struct bpf_htab *htab, u32 hash) 428 { 429 return &__select_bucket(htab, hash)->head; 430 } 431 432 /* this lookup function can only be called with bucket lock taken */ 433 static struct htab_elem *lookup_elem_raw(struct hlist_nulls_head *head, u32 hash, 434 void *key, u32 key_size) 435 { 436 struct hlist_nulls_node *n; 437 struct htab_elem *l; 438 439 hlist_nulls_for_each_entry_rcu(l, n, head, hash_node) 440 if (l->hash == hash && !memcmp(&l->key, key, key_size)) 441 return l; 442 443 return NULL; 444 } 445 446 /* can be called without bucket lock. it will repeat the loop in 447 * the unlikely event when elements moved from one bucket into another 448 * while link list is being walked 449 */ 450 static struct htab_elem *lookup_nulls_elem_raw(struct hlist_nulls_head *head, 451 u32 hash, void *key, 452 u32 key_size, u32 n_buckets) 453 { 454 struct hlist_nulls_node *n; 455 struct htab_elem *l; 456 457 again: 458 hlist_nulls_for_each_entry_rcu(l, n, head, hash_node) 459 if (l->hash == hash && !memcmp(&l->key, key, key_size)) 460 return l; 461 462 if (unlikely(get_nulls_value(n) != (hash & (n_buckets - 1)))) 463 goto again; 464 465 return NULL; 466 } 467 468 /* Called from syscall or from eBPF program directly, so 469 * arguments have to match bpf_map_lookup_elem() exactly. 470 * The return value is adjusted by BPF instructions 471 * in htab_map_gen_lookup(). 472 */ 473 static void *__htab_map_lookup_elem(struct bpf_map *map, void *key) 474 { 475 struct bpf_htab *htab = container_of(map, struct bpf_htab, map); 476 struct hlist_nulls_head *head; 477 struct htab_elem *l; 478 u32 hash, key_size; 479 480 /* Must be called with rcu_read_lock. */ 481 WARN_ON_ONCE(!rcu_read_lock_held()); 482 483 key_size = map->key_size; 484 485 hash = htab_map_hash(key, key_size, htab->hashrnd); 486 487 head = select_bucket(htab, hash); 488 489 l = lookup_nulls_elem_raw(head, hash, key, key_size, htab->n_buckets); 490 491 return l; 492 } 493 494 static void *htab_map_lookup_elem(struct bpf_map *map, void *key) 495 { 496 struct htab_elem *l = __htab_map_lookup_elem(map, key); 497 498 if (l) 499 return l->key + round_up(map->key_size, 8); 500 501 return NULL; 502 } 503 504 /* inline bpf_map_lookup_elem() call. 505 * Instead of: 506 * bpf_prog 507 * bpf_map_lookup_elem 508 * map->ops->map_lookup_elem 509 * htab_map_lookup_elem 510 * __htab_map_lookup_elem 511 * do: 512 * bpf_prog 513 * __htab_map_lookup_elem 514 */ 515 static u32 htab_map_gen_lookup(struct bpf_map *map, struct bpf_insn *insn_buf) 516 { 517 struct bpf_insn *insn = insn_buf; 518 const int ret = BPF_REG_0; 519 520 BUILD_BUG_ON(!__same_type(&__htab_map_lookup_elem, 521 (void *(*)(struct bpf_map *map, void *key))NULL)); 522 *insn++ = BPF_EMIT_CALL(BPF_CAST_CALL(__htab_map_lookup_elem)); 523 *insn++ = BPF_JMP_IMM(BPF_JEQ, ret, 0, 1); 524 *insn++ = BPF_ALU64_IMM(BPF_ADD, ret, 525 offsetof(struct htab_elem, key) + 526 round_up(map->key_size, 8)); 527 return insn - insn_buf; 528 } 529 530 static void *htab_lru_map_lookup_elem(struct bpf_map *map, void *key) 531 { 532 struct htab_elem *l = __htab_map_lookup_elem(map, key); 533 534 if (l) { 535 bpf_lru_node_set_ref(&l->lru_node); 536 return l->key + round_up(map->key_size, 8); 537 } 538 539 return NULL; 540 } 541 542 static u32 htab_lru_map_gen_lookup(struct bpf_map *map, 543 struct bpf_insn *insn_buf) 544 { 545 struct bpf_insn *insn = insn_buf; 546 const int ret = BPF_REG_0; 547 const int ref_reg = BPF_REG_1; 548 549 BUILD_BUG_ON(!__same_type(&__htab_map_lookup_elem, 550 (void *(*)(struct bpf_map *map, void *key))NULL)); 551 *insn++ = BPF_EMIT_CALL(BPF_CAST_CALL(__htab_map_lookup_elem)); 552 *insn++ = BPF_JMP_IMM(BPF_JEQ, ret, 0, 4); 553 *insn++ = BPF_LDX_MEM(BPF_B, ref_reg, ret, 554 offsetof(struct htab_elem, lru_node) + 555 offsetof(struct bpf_lru_node, ref)); 556 *insn++ = BPF_JMP_IMM(BPF_JNE, ref_reg, 0, 1); 557 *insn++ = BPF_ST_MEM(BPF_B, ret, 558 offsetof(struct htab_elem, lru_node) + 559 offsetof(struct bpf_lru_node, ref), 560 1); 561 *insn++ = BPF_ALU64_IMM(BPF_ADD, ret, 562 offsetof(struct htab_elem, key) + 563 round_up(map->key_size, 8)); 564 return insn - insn_buf; 565 } 566 567 /* It is called from the bpf_lru_list when the LRU needs to delete 568 * older elements from the htab. 569 */ 570 static bool htab_lru_map_delete_node(void *arg, struct bpf_lru_node *node) 571 { 572 struct bpf_htab *htab = (struct bpf_htab *)arg; 573 struct htab_elem *l = NULL, *tgt_l; 574 struct hlist_nulls_head *head; 575 struct hlist_nulls_node *n; 576 unsigned long flags; 577 struct bucket *b; 578 579 tgt_l = container_of(node, struct htab_elem, lru_node); 580 b = __select_bucket(htab, tgt_l->hash); 581 head = &b->head; 582 583 raw_spin_lock_irqsave(&b->lock, flags); 584 585 hlist_nulls_for_each_entry_rcu(l, n, head, hash_node) 586 if (l == tgt_l) { 587 hlist_nulls_del_rcu(&l->hash_node); 588 break; 589 } 590 591 raw_spin_unlock_irqrestore(&b->lock, flags); 592 593 return l == tgt_l; 594 } 595 596 /* Called from syscall */ 597 static int htab_map_get_next_key(struct bpf_map *map, void *key, void *next_key) 598 { 599 struct bpf_htab *htab = container_of(map, struct bpf_htab, map); 600 struct hlist_nulls_head *head; 601 struct htab_elem *l, *next_l; 602 u32 hash, key_size; 603 int i = 0; 604 605 WARN_ON_ONCE(!rcu_read_lock_held()); 606 607 key_size = map->key_size; 608 609 if (!key) 610 goto find_first_elem; 611 612 hash = htab_map_hash(key, key_size, htab->hashrnd); 613 614 head = select_bucket(htab, hash); 615 616 /* lookup the key */ 617 l = lookup_nulls_elem_raw(head, hash, key, key_size, htab->n_buckets); 618 619 if (!l) 620 goto find_first_elem; 621 622 /* key was found, get next key in the same bucket */ 623 next_l = hlist_nulls_entry_safe(rcu_dereference_raw(hlist_nulls_next_rcu(&l->hash_node)), 624 struct htab_elem, hash_node); 625 626 if (next_l) { 627 /* if next elem in this hash list is non-zero, just return it */ 628 memcpy(next_key, next_l->key, key_size); 629 return 0; 630 } 631 632 /* no more elements in this hash list, go to the next bucket */ 633 i = hash & (htab->n_buckets - 1); 634 i++; 635 636 find_first_elem: 637 /* iterate over buckets */ 638 for (; i < htab->n_buckets; i++) { 639 head = select_bucket(htab, i); 640 641 /* pick first element in the bucket */ 642 next_l = hlist_nulls_entry_safe(rcu_dereference_raw(hlist_nulls_first_rcu(head)), 643 struct htab_elem, hash_node); 644 if (next_l) { 645 /* if it's not empty, just return it */ 646 memcpy(next_key, next_l->key, key_size); 647 return 0; 648 } 649 } 650 651 /* iterated over all buckets and all elements */ 652 return -ENOENT; 653 } 654 655 static void htab_elem_free(struct bpf_htab *htab, struct htab_elem *l) 656 { 657 if (htab->map.map_type == BPF_MAP_TYPE_PERCPU_HASH) 658 free_percpu(htab_elem_get_ptr(l, htab->map.key_size)); 659 kfree(l); 660 } 661 662 static void htab_elem_free_rcu(struct rcu_head *head) 663 { 664 struct htab_elem *l = container_of(head, struct htab_elem, rcu); 665 struct bpf_htab *htab = l->htab; 666 667 /* must increment bpf_prog_active to avoid kprobe+bpf triggering while 668 * we're calling kfree, otherwise deadlock is possible if kprobes 669 * are placed somewhere inside of slub 670 */ 671 preempt_disable(); 672 __this_cpu_inc(bpf_prog_active); 673 htab_elem_free(htab, l); 674 __this_cpu_dec(bpf_prog_active); 675 preempt_enable(); 676 } 677 678 static void free_htab_elem(struct bpf_htab *htab, struct htab_elem *l) 679 { 680 struct bpf_map *map = &htab->map; 681 682 if (map->ops->map_fd_put_ptr) { 683 void *ptr = fd_htab_map_get_ptr(map, l); 684 685 map->ops->map_fd_put_ptr(ptr); 686 } 687 688 if (htab_is_prealloc(htab)) { 689 __pcpu_freelist_push(&htab->freelist, &l->fnode); 690 } else { 691 atomic_dec(&htab->count); 692 l->htab = htab; 693 call_rcu(&l->rcu, htab_elem_free_rcu); 694 } 695 } 696 697 static void pcpu_copy_value(struct bpf_htab *htab, void __percpu *pptr, 698 void *value, bool onallcpus) 699 { 700 if (!onallcpus) { 701 /* copy true value_size bytes */ 702 memcpy(this_cpu_ptr(pptr), value, htab->map.value_size); 703 } else { 704 u32 size = round_up(htab->map.value_size, 8); 705 int off = 0, cpu; 706 707 for_each_possible_cpu(cpu) { 708 bpf_long_memcpy(per_cpu_ptr(pptr, cpu), 709 value + off, size); 710 off += size; 711 } 712 } 713 } 714 715 static bool fd_htab_map_needs_adjust(const struct bpf_htab *htab) 716 { 717 return htab->map.map_type == BPF_MAP_TYPE_HASH_OF_MAPS && 718 BITS_PER_LONG == 64; 719 } 720 721 static struct htab_elem *alloc_htab_elem(struct bpf_htab *htab, void *key, 722 void *value, u32 key_size, u32 hash, 723 bool percpu, bool onallcpus, 724 struct htab_elem *old_elem) 725 { 726 u32 size = htab->map.value_size; 727 bool prealloc = htab_is_prealloc(htab); 728 struct htab_elem *l_new, **pl_new; 729 void __percpu *pptr; 730 731 if (prealloc) { 732 if (old_elem) { 733 /* if we're updating the existing element, 734 * use per-cpu extra elems to avoid freelist_pop/push 735 */ 736 pl_new = this_cpu_ptr(htab->extra_elems); 737 l_new = *pl_new; 738 *pl_new = old_elem; 739 } else { 740 struct pcpu_freelist_node *l; 741 742 l = __pcpu_freelist_pop(&htab->freelist); 743 if (!l) 744 return ERR_PTR(-E2BIG); 745 l_new = container_of(l, struct htab_elem, fnode); 746 } 747 } else { 748 if (atomic_inc_return(&htab->count) > htab->map.max_entries) 749 if (!old_elem) { 750 /* when map is full and update() is replacing 751 * old element, it's ok to allocate, since 752 * old element will be freed immediately. 753 * Otherwise return an error 754 */ 755 l_new = ERR_PTR(-E2BIG); 756 goto dec_count; 757 } 758 l_new = kmalloc_node(htab->elem_size, GFP_ATOMIC | __GFP_NOWARN, 759 htab->map.numa_node); 760 if (!l_new) { 761 l_new = ERR_PTR(-ENOMEM); 762 goto dec_count; 763 } 764 check_and_init_map_lock(&htab->map, 765 l_new->key + round_up(key_size, 8)); 766 } 767 768 memcpy(l_new->key, key, key_size); 769 if (percpu) { 770 size = round_up(size, 8); 771 if (prealloc) { 772 pptr = htab_elem_get_ptr(l_new, key_size); 773 } else { 774 /* alloc_percpu zero-fills */ 775 pptr = __alloc_percpu_gfp(size, 8, 776 GFP_ATOMIC | __GFP_NOWARN); 777 if (!pptr) { 778 kfree(l_new); 779 l_new = ERR_PTR(-ENOMEM); 780 goto dec_count; 781 } 782 } 783 784 pcpu_copy_value(htab, pptr, value, onallcpus); 785 786 if (!prealloc) 787 htab_elem_set_ptr(l_new, key_size, pptr); 788 } else if (fd_htab_map_needs_adjust(htab)) { 789 size = round_up(size, 8); 790 memcpy(l_new->key + round_up(key_size, 8), value, size); 791 } else { 792 copy_map_value(&htab->map, 793 l_new->key + round_up(key_size, 8), 794 value); 795 } 796 797 l_new->hash = hash; 798 return l_new; 799 dec_count: 800 atomic_dec(&htab->count); 801 return l_new; 802 } 803 804 static int check_flags(struct bpf_htab *htab, struct htab_elem *l_old, 805 u64 map_flags) 806 { 807 if (l_old && (map_flags & ~BPF_F_LOCK) == BPF_NOEXIST) 808 /* elem already exists */ 809 return -EEXIST; 810 811 if (!l_old && (map_flags & ~BPF_F_LOCK) == BPF_EXIST) 812 /* elem doesn't exist, cannot update it */ 813 return -ENOENT; 814 815 return 0; 816 } 817 818 /* Called from syscall or from eBPF program */ 819 static int htab_map_update_elem(struct bpf_map *map, void *key, void *value, 820 u64 map_flags) 821 { 822 struct bpf_htab *htab = container_of(map, struct bpf_htab, map); 823 struct htab_elem *l_new = NULL, *l_old; 824 struct hlist_nulls_head *head; 825 unsigned long flags; 826 struct bucket *b; 827 u32 key_size, hash; 828 int ret; 829 830 if (unlikely((map_flags & ~BPF_F_LOCK) > BPF_EXIST)) 831 /* unknown flags */ 832 return -EINVAL; 833 834 WARN_ON_ONCE(!rcu_read_lock_held()); 835 836 key_size = map->key_size; 837 838 hash = htab_map_hash(key, key_size, htab->hashrnd); 839 840 b = __select_bucket(htab, hash); 841 head = &b->head; 842 843 if (unlikely(map_flags & BPF_F_LOCK)) { 844 if (unlikely(!map_value_has_spin_lock(map))) 845 return -EINVAL; 846 /* find an element without taking the bucket lock */ 847 l_old = lookup_nulls_elem_raw(head, hash, key, key_size, 848 htab->n_buckets); 849 ret = check_flags(htab, l_old, map_flags); 850 if (ret) 851 return ret; 852 if (l_old) { 853 /* grab the element lock and update value in place */ 854 copy_map_value_locked(map, 855 l_old->key + round_up(key_size, 8), 856 value, false); 857 return 0; 858 } 859 /* fall through, grab the bucket lock and lookup again. 860 * 99.9% chance that the element won't be found, 861 * but second lookup under lock has to be done. 862 */ 863 } 864 865 /* bpf_map_update_elem() can be called in_irq() */ 866 raw_spin_lock_irqsave(&b->lock, flags); 867 868 l_old = lookup_elem_raw(head, hash, key, key_size); 869 870 ret = check_flags(htab, l_old, map_flags); 871 if (ret) 872 goto err; 873 874 if (unlikely(l_old && (map_flags & BPF_F_LOCK))) { 875 /* first lookup without the bucket lock didn't find the element, 876 * but second lookup with the bucket lock found it. 877 * This case is highly unlikely, but has to be dealt with: 878 * grab the element lock in addition to the bucket lock 879 * and update element in place 880 */ 881 copy_map_value_locked(map, 882 l_old->key + round_up(key_size, 8), 883 value, false); 884 ret = 0; 885 goto err; 886 } 887 888 l_new = alloc_htab_elem(htab, key, value, key_size, hash, false, false, 889 l_old); 890 if (IS_ERR(l_new)) { 891 /* all pre-allocated elements are in use or memory exhausted */ 892 ret = PTR_ERR(l_new); 893 goto err; 894 } 895 896 /* add new element to the head of the list, so that 897 * concurrent search will find it before old elem 898 */ 899 hlist_nulls_add_head_rcu(&l_new->hash_node, head); 900 if (l_old) { 901 hlist_nulls_del_rcu(&l_old->hash_node); 902 if (!htab_is_prealloc(htab)) 903 free_htab_elem(htab, l_old); 904 } 905 ret = 0; 906 err: 907 raw_spin_unlock_irqrestore(&b->lock, flags); 908 return ret; 909 } 910 911 static int htab_lru_map_update_elem(struct bpf_map *map, void *key, void *value, 912 u64 map_flags) 913 { 914 struct bpf_htab *htab = container_of(map, struct bpf_htab, map); 915 struct htab_elem *l_new, *l_old = NULL; 916 struct hlist_nulls_head *head; 917 unsigned long flags; 918 struct bucket *b; 919 u32 key_size, hash; 920 int ret; 921 922 if (unlikely(map_flags > BPF_EXIST)) 923 /* unknown flags */ 924 return -EINVAL; 925 926 WARN_ON_ONCE(!rcu_read_lock_held()); 927 928 key_size = map->key_size; 929 930 hash = htab_map_hash(key, key_size, htab->hashrnd); 931 932 b = __select_bucket(htab, hash); 933 head = &b->head; 934 935 /* For LRU, we need to alloc before taking bucket's 936 * spinlock because getting free nodes from LRU may need 937 * to remove older elements from htab and this removal 938 * operation will need a bucket lock. 939 */ 940 l_new = prealloc_lru_pop(htab, key, hash); 941 if (!l_new) 942 return -ENOMEM; 943 memcpy(l_new->key + round_up(map->key_size, 8), value, map->value_size); 944 945 /* bpf_map_update_elem() can be called in_irq() */ 946 raw_spin_lock_irqsave(&b->lock, flags); 947 948 l_old = lookup_elem_raw(head, hash, key, key_size); 949 950 ret = check_flags(htab, l_old, map_flags); 951 if (ret) 952 goto err; 953 954 /* add new element to the head of the list, so that 955 * concurrent search will find it before old elem 956 */ 957 hlist_nulls_add_head_rcu(&l_new->hash_node, head); 958 if (l_old) { 959 bpf_lru_node_set_ref(&l_new->lru_node); 960 hlist_nulls_del_rcu(&l_old->hash_node); 961 } 962 ret = 0; 963 964 err: 965 raw_spin_unlock_irqrestore(&b->lock, flags); 966 967 if (ret) 968 bpf_lru_push_free(&htab->lru, &l_new->lru_node); 969 else if (l_old) 970 bpf_lru_push_free(&htab->lru, &l_old->lru_node); 971 972 return ret; 973 } 974 975 static int __htab_percpu_map_update_elem(struct bpf_map *map, void *key, 976 void *value, u64 map_flags, 977 bool onallcpus) 978 { 979 struct bpf_htab *htab = container_of(map, struct bpf_htab, map); 980 struct htab_elem *l_new = NULL, *l_old; 981 struct hlist_nulls_head *head; 982 unsigned long flags; 983 struct bucket *b; 984 u32 key_size, hash; 985 int ret; 986 987 if (unlikely(map_flags > BPF_EXIST)) 988 /* unknown flags */ 989 return -EINVAL; 990 991 WARN_ON_ONCE(!rcu_read_lock_held()); 992 993 key_size = map->key_size; 994 995 hash = htab_map_hash(key, key_size, htab->hashrnd); 996 997 b = __select_bucket(htab, hash); 998 head = &b->head; 999 1000 /* bpf_map_update_elem() can be called in_irq() */ 1001 raw_spin_lock_irqsave(&b->lock, flags); 1002 1003 l_old = lookup_elem_raw(head, hash, key, key_size); 1004 1005 ret = check_flags(htab, l_old, map_flags); 1006 if (ret) 1007 goto err; 1008 1009 if (l_old) { 1010 /* per-cpu hash map can update value in-place */ 1011 pcpu_copy_value(htab, htab_elem_get_ptr(l_old, key_size), 1012 value, onallcpus); 1013 } else { 1014 l_new = alloc_htab_elem(htab, key, value, key_size, 1015 hash, true, onallcpus, NULL); 1016 if (IS_ERR(l_new)) { 1017 ret = PTR_ERR(l_new); 1018 goto err; 1019 } 1020 hlist_nulls_add_head_rcu(&l_new->hash_node, head); 1021 } 1022 ret = 0; 1023 err: 1024 raw_spin_unlock_irqrestore(&b->lock, flags); 1025 return ret; 1026 } 1027 1028 static int __htab_lru_percpu_map_update_elem(struct bpf_map *map, void *key, 1029 void *value, u64 map_flags, 1030 bool onallcpus) 1031 { 1032 struct bpf_htab *htab = container_of(map, struct bpf_htab, map); 1033 struct htab_elem *l_new = NULL, *l_old; 1034 struct hlist_nulls_head *head; 1035 unsigned long flags; 1036 struct bucket *b; 1037 u32 key_size, hash; 1038 int ret; 1039 1040 if (unlikely(map_flags > BPF_EXIST)) 1041 /* unknown flags */ 1042 return -EINVAL; 1043 1044 WARN_ON_ONCE(!rcu_read_lock_held()); 1045 1046 key_size = map->key_size; 1047 1048 hash = htab_map_hash(key, key_size, htab->hashrnd); 1049 1050 b = __select_bucket(htab, hash); 1051 head = &b->head; 1052 1053 /* For LRU, we need to alloc before taking bucket's 1054 * spinlock because LRU's elem alloc may need 1055 * to remove older elem from htab and this removal 1056 * operation will need a bucket lock. 1057 */ 1058 if (map_flags != BPF_EXIST) { 1059 l_new = prealloc_lru_pop(htab, key, hash); 1060 if (!l_new) 1061 return -ENOMEM; 1062 } 1063 1064 /* bpf_map_update_elem() can be called in_irq() */ 1065 raw_spin_lock_irqsave(&b->lock, flags); 1066 1067 l_old = lookup_elem_raw(head, hash, key, key_size); 1068 1069 ret = check_flags(htab, l_old, map_flags); 1070 if (ret) 1071 goto err; 1072 1073 if (l_old) { 1074 bpf_lru_node_set_ref(&l_old->lru_node); 1075 1076 /* per-cpu hash map can update value in-place */ 1077 pcpu_copy_value(htab, htab_elem_get_ptr(l_old, key_size), 1078 value, onallcpus); 1079 } else { 1080 pcpu_copy_value(htab, htab_elem_get_ptr(l_new, key_size), 1081 value, onallcpus); 1082 hlist_nulls_add_head_rcu(&l_new->hash_node, head); 1083 l_new = NULL; 1084 } 1085 ret = 0; 1086 err: 1087 raw_spin_unlock_irqrestore(&b->lock, flags); 1088 if (l_new) 1089 bpf_lru_push_free(&htab->lru, &l_new->lru_node); 1090 return ret; 1091 } 1092 1093 static int htab_percpu_map_update_elem(struct bpf_map *map, void *key, 1094 void *value, u64 map_flags) 1095 { 1096 return __htab_percpu_map_update_elem(map, key, value, map_flags, false); 1097 } 1098 1099 static int htab_lru_percpu_map_update_elem(struct bpf_map *map, void *key, 1100 void *value, u64 map_flags) 1101 { 1102 return __htab_lru_percpu_map_update_elem(map, key, value, map_flags, 1103 false); 1104 } 1105 1106 /* Called from syscall or from eBPF program */ 1107 static int htab_map_delete_elem(struct bpf_map *map, void *key) 1108 { 1109 struct bpf_htab *htab = container_of(map, struct bpf_htab, map); 1110 struct hlist_nulls_head *head; 1111 struct bucket *b; 1112 struct htab_elem *l; 1113 unsigned long flags; 1114 u32 hash, key_size; 1115 int ret = -ENOENT; 1116 1117 WARN_ON_ONCE(!rcu_read_lock_held()); 1118 1119 key_size = map->key_size; 1120 1121 hash = htab_map_hash(key, key_size, htab->hashrnd); 1122 b = __select_bucket(htab, hash); 1123 head = &b->head; 1124 1125 raw_spin_lock_irqsave(&b->lock, flags); 1126 1127 l = lookup_elem_raw(head, hash, key, key_size); 1128 1129 if (l) { 1130 hlist_nulls_del_rcu(&l->hash_node); 1131 free_htab_elem(htab, l); 1132 ret = 0; 1133 } 1134 1135 raw_spin_unlock_irqrestore(&b->lock, flags); 1136 return ret; 1137 } 1138 1139 static int htab_lru_map_delete_elem(struct bpf_map *map, void *key) 1140 { 1141 struct bpf_htab *htab = container_of(map, struct bpf_htab, map); 1142 struct hlist_nulls_head *head; 1143 struct bucket *b; 1144 struct htab_elem *l; 1145 unsigned long flags; 1146 u32 hash, key_size; 1147 int ret = -ENOENT; 1148 1149 WARN_ON_ONCE(!rcu_read_lock_held()); 1150 1151 key_size = map->key_size; 1152 1153 hash = htab_map_hash(key, key_size, htab->hashrnd); 1154 b = __select_bucket(htab, hash); 1155 head = &b->head; 1156 1157 raw_spin_lock_irqsave(&b->lock, flags); 1158 1159 l = lookup_elem_raw(head, hash, key, key_size); 1160 1161 if (l) { 1162 hlist_nulls_del_rcu(&l->hash_node); 1163 ret = 0; 1164 } 1165 1166 raw_spin_unlock_irqrestore(&b->lock, flags); 1167 if (l) 1168 bpf_lru_push_free(&htab->lru, &l->lru_node); 1169 return ret; 1170 } 1171 1172 static void delete_all_elements(struct bpf_htab *htab) 1173 { 1174 int i; 1175 1176 for (i = 0; i < htab->n_buckets; i++) { 1177 struct hlist_nulls_head *head = select_bucket(htab, i); 1178 struct hlist_nulls_node *n; 1179 struct htab_elem *l; 1180 1181 hlist_nulls_for_each_entry_safe(l, n, head, hash_node) { 1182 hlist_nulls_del_rcu(&l->hash_node); 1183 htab_elem_free(htab, l); 1184 } 1185 } 1186 } 1187 1188 /* Called when map->refcnt goes to zero, either from workqueue or from syscall */ 1189 static void htab_map_free(struct bpf_map *map) 1190 { 1191 struct bpf_htab *htab = container_of(map, struct bpf_htab, map); 1192 1193 /* at this point bpf_prog->aux->refcnt == 0 and this map->refcnt == 0, 1194 * so the programs (can be more than one that used this map) were 1195 * disconnected from events. Wait for outstanding critical sections in 1196 * these programs to complete 1197 */ 1198 synchronize_rcu(); 1199 1200 /* some of free_htab_elem() callbacks for elements of this map may 1201 * not have executed. Wait for them. 1202 */ 1203 rcu_barrier(); 1204 if (!htab_is_prealloc(htab)) 1205 delete_all_elements(htab); 1206 else 1207 prealloc_destroy(htab); 1208 1209 free_percpu(htab->extra_elems); 1210 bpf_map_area_free(htab->buckets); 1211 kfree(htab); 1212 } 1213 1214 static void htab_map_seq_show_elem(struct bpf_map *map, void *key, 1215 struct seq_file *m) 1216 { 1217 void *value; 1218 1219 rcu_read_lock(); 1220 1221 value = htab_map_lookup_elem(map, key); 1222 if (!value) { 1223 rcu_read_unlock(); 1224 return; 1225 } 1226 1227 btf_type_seq_show(map->btf, map->btf_key_type_id, key, m); 1228 seq_puts(m, ": "); 1229 btf_type_seq_show(map->btf, map->btf_value_type_id, value, m); 1230 seq_puts(m, "\n"); 1231 1232 rcu_read_unlock(); 1233 } 1234 1235 const struct bpf_map_ops htab_map_ops = { 1236 .map_alloc_check = htab_map_alloc_check, 1237 .map_alloc = htab_map_alloc, 1238 .map_free = htab_map_free, 1239 .map_get_next_key = htab_map_get_next_key, 1240 .map_lookup_elem = htab_map_lookup_elem, 1241 .map_update_elem = htab_map_update_elem, 1242 .map_delete_elem = htab_map_delete_elem, 1243 .map_gen_lookup = htab_map_gen_lookup, 1244 .map_seq_show_elem = htab_map_seq_show_elem, 1245 }; 1246 1247 const struct bpf_map_ops htab_lru_map_ops = { 1248 .map_alloc_check = htab_map_alloc_check, 1249 .map_alloc = htab_map_alloc, 1250 .map_free = htab_map_free, 1251 .map_get_next_key = htab_map_get_next_key, 1252 .map_lookup_elem = htab_lru_map_lookup_elem, 1253 .map_update_elem = htab_lru_map_update_elem, 1254 .map_delete_elem = htab_lru_map_delete_elem, 1255 .map_gen_lookup = htab_lru_map_gen_lookup, 1256 .map_seq_show_elem = htab_map_seq_show_elem, 1257 }; 1258 1259 /* Called from eBPF program */ 1260 static void *htab_percpu_map_lookup_elem(struct bpf_map *map, void *key) 1261 { 1262 struct htab_elem *l = __htab_map_lookup_elem(map, key); 1263 1264 if (l) 1265 return this_cpu_ptr(htab_elem_get_ptr(l, map->key_size)); 1266 else 1267 return NULL; 1268 } 1269 1270 static void *htab_lru_percpu_map_lookup_elem(struct bpf_map *map, void *key) 1271 { 1272 struct htab_elem *l = __htab_map_lookup_elem(map, key); 1273 1274 if (l) { 1275 bpf_lru_node_set_ref(&l->lru_node); 1276 return this_cpu_ptr(htab_elem_get_ptr(l, map->key_size)); 1277 } 1278 1279 return NULL; 1280 } 1281 1282 int bpf_percpu_hash_copy(struct bpf_map *map, void *key, void *value) 1283 { 1284 struct bpf_htab *htab = container_of(map, struct bpf_htab, map); 1285 struct htab_elem *l; 1286 void __percpu *pptr; 1287 int ret = -ENOENT; 1288 int cpu, off = 0; 1289 u32 size; 1290 1291 /* per_cpu areas are zero-filled and bpf programs can only 1292 * access 'value_size' of them, so copying rounded areas 1293 * will not leak any kernel data 1294 */ 1295 size = round_up(map->value_size, 8); 1296 rcu_read_lock(); 1297 l = __htab_map_lookup_elem(map, key); 1298 if (!l) 1299 goto out; 1300 if (htab_is_lru(htab)) 1301 bpf_lru_node_set_ref(&l->lru_node); 1302 pptr = htab_elem_get_ptr(l, map->key_size); 1303 for_each_possible_cpu(cpu) { 1304 bpf_long_memcpy(value + off, 1305 per_cpu_ptr(pptr, cpu), size); 1306 off += size; 1307 } 1308 ret = 0; 1309 out: 1310 rcu_read_unlock(); 1311 return ret; 1312 } 1313 1314 int bpf_percpu_hash_update(struct bpf_map *map, void *key, void *value, 1315 u64 map_flags) 1316 { 1317 struct bpf_htab *htab = container_of(map, struct bpf_htab, map); 1318 int ret; 1319 1320 rcu_read_lock(); 1321 if (htab_is_lru(htab)) 1322 ret = __htab_lru_percpu_map_update_elem(map, key, value, 1323 map_flags, true); 1324 else 1325 ret = __htab_percpu_map_update_elem(map, key, value, map_flags, 1326 true); 1327 rcu_read_unlock(); 1328 1329 return ret; 1330 } 1331 1332 static void htab_percpu_map_seq_show_elem(struct bpf_map *map, void *key, 1333 struct seq_file *m) 1334 { 1335 struct htab_elem *l; 1336 void __percpu *pptr; 1337 int cpu; 1338 1339 rcu_read_lock(); 1340 1341 l = __htab_map_lookup_elem(map, key); 1342 if (!l) { 1343 rcu_read_unlock(); 1344 return; 1345 } 1346 1347 btf_type_seq_show(map->btf, map->btf_key_type_id, key, m); 1348 seq_puts(m, ": {\n"); 1349 pptr = htab_elem_get_ptr(l, map->key_size); 1350 for_each_possible_cpu(cpu) { 1351 seq_printf(m, "\tcpu%d: ", cpu); 1352 btf_type_seq_show(map->btf, map->btf_value_type_id, 1353 per_cpu_ptr(pptr, cpu), m); 1354 seq_puts(m, "\n"); 1355 } 1356 seq_puts(m, "}\n"); 1357 1358 rcu_read_unlock(); 1359 } 1360 1361 const struct bpf_map_ops htab_percpu_map_ops = { 1362 .map_alloc_check = htab_map_alloc_check, 1363 .map_alloc = htab_map_alloc, 1364 .map_free = htab_map_free, 1365 .map_get_next_key = htab_map_get_next_key, 1366 .map_lookup_elem = htab_percpu_map_lookup_elem, 1367 .map_update_elem = htab_percpu_map_update_elem, 1368 .map_delete_elem = htab_map_delete_elem, 1369 .map_seq_show_elem = htab_percpu_map_seq_show_elem, 1370 }; 1371 1372 const struct bpf_map_ops htab_lru_percpu_map_ops = { 1373 .map_alloc_check = htab_map_alloc_check, 1374 .map_alloc = htab_map_alloc, 1375 .map_free = htab_map_free, 1376 .map_get_next_key = htab_map_get_next_key, 1377 .map_lookup_elem = htab_lru_percpu_map_lookup_elem, 1378 .map_update_elem = htab_lru_percpu_map_update_elem, 1379 .map_delete_elem = htab_lru_map_delete_elem, 1380 .map_seq_show_elem = htab_percpu_map_seq_show_elem, 1381 }; 1382 1383 static int fd_htab_map_alloc_check(union bpf_attr *attr) 1384 { 1385 if (attr->value_size != sizeof(u32)) 1386 return -EINVAL; 1387 return htab_map_alloc_check(attr); 1388 } 1389 1390 static void fd_htab_map_free(struct bpf_map *map) 1391 { 1392 struct bpf_htab *htab = container_of(map, struct bpf_htab, map); 1393 struct hlist_nulls_node *n; 1394 struct hlist_nulls_head *head; 1395 struct htab_elem *l; 1396 int i; 1397 1398 for (i = 0; i < htab->n_buckets; i++) { 1399 head = select_bucket(htab, i); 1400 1401 hlist_nulls_for_each_entry_safe(l, n, head, hash_node) { 1402 void *ptr = fd_htab_map_get_ptr(map, l); 1403 1404 map->ops->map_fd_put_ptr(ptr); 1405 } 1406 } 1407 1408 htab_map_free(map); 1409 } 1410 1411 /* only called from syscall */ 1412 int bpf_fd_htab_map_lookup_elem(struct bpf_map *map, void *key, u32 *value) 1413 { 1414 void **ptr; 1415 int ret = 0; 1416 1417 if (!map->ops->map_fd_sys_lookup_elem) 1418 return -ENOTSUPP; 1419 1420 rcu_read_lock(); 1421 ptr = htab_map_lookup_elem(map, key); 1422 if (ptr) 1423 *value = map->ops->map_fd_sys_lookup_elem(READ_ONCE(*ptr)); 1424 else 1425 ret = -ENOENT; 1426 rcu_read_unlock(); 1427 1428 return ret; 1429 } 1430 1431 /* only called from syscall */ 1432 int bpf_fd_htab_map_update_elem(struct bpf_map *map, struct file *map_file, 1433 void *key, void *value, u64 map_flags) 1434 { 1435 void *ptr; 1436 int ret; 1437 u32 ufd = *(u32 *)value; 1438 1439 ptr = map->ops->map_fd_get_ptr(map, map_file, ufd); 1440 if (IS_ERR(ptr)) 1441 return PTR_ERR(ptr); 1442 1443 ret = htab_map_update_elem(map, key, &ptr, map_flags); 1444 if (ret) 1445 map->ops->map_fd_put_ptr(ptr); 1446 1447 return ret; 1448 } 1449 1450 static struct bpf_map *htab_of_map_alloc(union bpf_attr *attr) 1451 { 1452 struct bpf_map *map, *inner_map_meta; 1453 1454 inner_map_meta = bpf_map_meta_alloc(attr->inner_map_fd); 1455 if (IS_ERR(inner_map_meta)) 1456 return inner_map_meta; 1457 1458 map = htab_map_alloc(attr); 1459 if (IS_ERR(map)) { 1460 bpf_map_meta_free(inner_map_meta); 1461 return map; 1462 } 1463 1464 map->inner_map_meta = inner_map_meta; 1465 1466 return map; 1467 } 1468 1469 static void *htab_of_map_lookup_elem(struct bpf_map *map, void *key) 1470 { 1471 struct bpf_map **inner_map = htab_map_lookup_elem(map, key); 1472 1473 if (!inner_map) 1474 return NULL; 1475 1476 return READ_ONCE(*inner_map); 1477 } 1478 1479 static u32 htab_of_map_gen_lookup(struct bpf_map *map, 1480 struct bpf_insn *insn_buf) 1481 { 1482 struct bpf_insn *insn = insn_buf; 1483 const int ret = BPF_REG_0; 1484 1485 BUILD_BUG_ON(!__same_type(&__htab_map_lookup_elem, 1486 (void *(*)(struct bpf_map *map, void *key))NULL)); 1487 *insn++ = BPF_EMIT_CALL(BPF_CAST_CALL(__htab_map_lookup_elem)); 1488 *insn++ = BPF_JMP_IMM(BPF_JEQ, ret, 0, 2); 1489 *insn++ = BPF_ALU64_IMM(BPF_ADD, ret, 1490 offsetof(struct htab_elem, key) + 1491 round_up(map->key_size, 8)); 1492 *insn++ = BPF_LDX_MEM(BPF_DW, ret, ret, 0); 1493 1494 return insn - insn_buf; 1495 } 1496 1497 static void htab_of_map_free(struct bpf_map *map) 1498 { 1499 bpf_map_meta_free(map->inner_map_meta); 1500 fd_htab_map_free(map); 1501 } 1502 1503 const struct bpf_map_ops htab_of_maps_map_ops = { 1504 .map_alloc_check = fd_htab_map_alloc_check, 1505 .map_alloc = htab_of_map_alloc, 1506 .map_free = htab_of_map_free, 1507 .map_get_next_key = htab_map_get_next_key, 1508 .map_lookup_elem = htab_of_map_lookup_elem, 1509 .map_delete_elem = htab_map_delete_elem, 1510 .map_fd_get_ptr = bpf_map_fd_get_ptr, 1511 .map_fd_put_ptr = bpf_map_fd_put_ptr, 1512 .map_fd_sys_lookup_elem = bpf_map_fd_sys_lookup_elem, 1513 .map_gen_lookup = htab_of_map_gen_lookup, 1514 .map_check_btf = map_check_no_btf, 1515 }; 1516