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