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