55 				struct bpf_htab *htab;  member
70 static bool htab_is_lru(const struct bpf_htab *htab)  in htab_is_lru()  argument
72 	return htab->map.map_type == BPF_MAP_TYPE_LRU_HASH ||  in htab_is_lru()
73 		htab->map.map_type == BPF_MAP_TYPE_LRU_PERCPU_HASH;  in htab_is_lru()
76 static bool htab_is_percpu(const struct bpf_htab *htab)  in htab_is_percpu()  argument
78 	return htab->map.map_type == BPF_MAP_TYPE_PERCPU_HASH ||  in htab_is_percpu()
79 		htab->map.map_type == BPF_MAP_TYPE_LRU_PERCPU_HASH;  in htab_is_percpu()
82 static bool htab_is_prealloc(const struct bpf_htab *htab)  in htab_is_prealloc()  argument
84 	return !(htab->map.map_flags & BPF_F_NO_PREALLOC);  in htab_is_prealloc()
103 static struct htab_elem *get_htab_elem(struct bpf_htab *htab, int i)  in get_htab_elem()  argument
105 	return (struct htab_elem *) (htab->elems + i * htab->elem_size);  in get_htab_elem()
108 static void htab_free_elems(struct bpf_htab *htab)  in htab_free_elems()  argument
112 	if (!htab_is_percpu(htab))  in htab_free_elems()
115 	for (i = 0; i < htab->map.max_entries; i++) {  in htab_free_elems()
118 		pptr = htab_elem_get_ptr(get_htab_elem(htab, i),  in htab_free_elems()
119 					 htab->map.key_size);  in htab_free_elems()
124 	bpf_map_area_free(htab->elems);  in htab_free_elems()
127 static struct htab_elem *prealloc_lru_pop(struct bpf_htab *htab, void *key,  in prealloc_lru_pop()  argument
130 	struct bpf_lru_node *node = bpf_lru_pop_free(&htab->lru, hash);  in prealloc_lru_pop()
135 		memcpy(l->key, key, htab->map.key_size);  in prealloc_lru_pop()
142 static int prealloc_init(struct bpf_htab *htab)  in prealloc_init()  argument
144 	u32 num_entries = htab->map.max_entries;  in prealloc_init()
147 	if (!htab_is_percpu(htab) && !htab_is_lru(htab))  in prealloc_init()
150 	htab->elems = bpf_map_area_alloc(htab->elem_size * num_entries,  in prealloc_init()
151 					 htab->map.numa_node);  in prealloc_init()
152 	if (!htab->elems)  in prealloc_init()
155 	if (!htab_is_percpu(htab))  in prealloc_init()
159 		u32 size = round_up(htab->map.value_size, 8);  in prealloc_init()
165 		htab_elem_set_ptr(get_htab_elem(htab, i), htab->map.key_size,  in prealloc_init()
171 	if (htab_is_lru(htab))  in prealloc_init()
172 		err = bpf_lru_init(&htab->lru,  in prealloc_init()
173 				   htab->map.map_flags & BPF_F_NO_COMMON_LRU,  in prealloc_init()
177 				   htab);  in prealloc_init()
179 		err = pcpu_freelist_init(&htab->freelist);  in prealloc_init()
184 	if (htab_is_lru(htab))  in prealloc_init()
185 		bpf_lru_populate(&htab->lru, htab->elems,  in prealloc_init()
187 				 htab->elem_size, num_entries);  in prealloc_init()
189 		pcpu_freelist_populate(&htab->freelist,  in prealloc_init()
190 				       htab->elems + offsetof(struct htab_elem, fnode),  in prealloc_init()
191 				       htab->elem_size, num_entries);  in prealloc_init()
196 	htab_free_elems(htab);  in prealloc_init()
200 static void prealloc_destroy(struct bpf_htab *htab)  in prealloc_destroy()  argument
202 	htab_free_elems(htab);  in prealloc_destroy()
204 	if (htab_is_lru(htab))  in prealloc_destroy()
205 		bpf_lru_destroy(&htab->lru);  in prealloc_destroy()
207 		pcpu_freelist_destroy(&htab->freelist);  in prealloc_destroy()
210 static int alloc_extra_elems(struct bpf_htab *htab)  in alloc_extra_elems()  argument
222 		l = pcpu_freelist_pop(&htab->freelist);  in alloc_extra_elems()
229 	htab->extra_elems = pptr;  in alloc_extra_elems()
249 	BUILD_BUG_ON(offsetof(struct htab_elem, htab) !=  in htab_map_alloc_check()
311 	struct bpf_htab *htab;  in htab_map_alloc()  local
315 	htab = kzalloc(sizeof(*htab), GFP_USER);  in htab_map_alloc()
316 	if (!htab)  in htab_map_alloc()
319 	bpf_map_init_from_attr(&htab->map, attr);  in htab_map_alloc()
326 		htab->map.max_entries = roundup(attr->max_entries,  in htab_map_alloc()
328 		if (htab->map.max_entries < attr->max_entries)  in htab_map_alloc()
329 			htab->map.max_entries = rounddown(attr->max_entries,  in htab_map_alloc()
334 	htab->n_buckets = roundup_pow_of_two(htab->map.max_entries);  in htab_map_alloc()
336 	htab->elem_size = sizeof(struct htab_elem) +  in htab_map_alloc()
337 			  round_up(htab->map.key_size, 8);  in htab_map_alloc()
339 		htab->elem_size += sizeof(void *);  in htab_map_alloc()
341 		htab->elem_size += round_up(htab->map.value_size, 8);  in htab_map_alloc()
345 	if (htab->n_buckets == 0 ||  in htab_map_alloc()
346 	    htab->n_buckets > U32_MAX / sizeof(struct bucket))  in htab_map_alloc()
349 	cost = (u64) htab->n_buckets * sizeof(struct bucket) +  in htab_map_alloc()
350 	       (u64) htab->elem_size * htab->map.max_entries;  in htab_map_alloc()
353 		cost += (u64) round_up(htab->map.value_size, 8) *  in htab_map_alloc()
354 			num_possible_cpus() * htab->map.max_entries;  in htab_map_alloc()
356 	       cost += (u64) htab->elem_size * num_possible_cpus();  in htab_map_alloc()
362 	htab->map.pages = round_up(cost, PAGE_SIZE) >> PAGE_SHIFT;  in htab_map_alloc()
365 	err = bpf_map_precharge_memlock(htab->map.pages);  in htab_map_alloc()
370 	htab->buckets = bpf_map_area_alloc(htab->n_buckets *  in htab_map_alloc()
372 					   htab->map.numa_node);  in htab_map_alloc()
373 	if (!htab->buckets)  in htab_map_alloc()
376 	htab->hashrnd = get_random_int();  in htab_map_alloc()
377 	for (i = 0; i < htab->n_buckets; i++) {  in htab_map_alloc()
378 		INIT_HLIST_NULLS_HEAD(&htab->buckets[i].head, i);  in htab_map_alloc()
379 		raw_spin_lock_init(&htab->buckets[i].lock);  in htab_map_alloc()
383 		err = prealloc_init(htab);  in htab_map_alloc()
391 			err = alloc_extra_elems(htab);  in htab_map_alloc()
397 	return &htab->map;  in htab_map_alloc()
400 	prealloc_destroy(htab);  in htab_map_alloc()
402 	bpf_map_area_free(htab->buckets);  in htab_map_alloc()
404 	kfree(htab);  in htab_map_alloc()
413 static inline struct bucket *__select_bucket(struct bpf_htab *htab, u32 hash)  in __select_bucket()  argument
415 	return &htab->buckets[hash & (htab->n_buckets - 1)];  in __select_bucket()
418 static inline struct hlist_nulls_head *select_bucket(struct bpf_htab *htab, u32 hash)  in select_bucket()  argument
420 	return &__select_bucket(htab, hash)->head;  in select_bucket()
466 	struct bpf_htab *htab = container_of(map, struct bpf_htab, map);  in __htab_map_lookup_elem()  local
476 	hash = htab_map_hash(key, key_size, htab->hashrnd);  in __htab_map_lookup_elem()
478 	head = select_bucket(htab, hash);  in __htab_map_lookup_elem()
480 	l = lookup_nulls_elem_raw(head, hash, key, key_size, htab->n_buckets);  in __htab_map_lookup_elem()
563 	struct bpf_htab *htab = (struct bpf_htab *)arg;  in htab_lru_map_delete_node()  local
571 	b = __select_bucket(htab, tgt_l->hash);  in htab_lru_map_delete_node()
590 	struct bpf_htab *htab = container_of(map, struct bpf_htab, map);  in htab_map_get_next_key()  local
603 	hash = htab_map_hash(key, key_size, htab->hashrnd);  in htab_map_get_next_key()
605 	head = select_bucket(htab, hash);  in htab_map_get_next_key()
608 	l = lookup_nulls_elem_raw(head, hash, key, key_size, htab->n_buckets);  in htab_map_get_next_key()
624 	i = hash & (htab->n_buckets - 1);  in htab_map_get_next_key()
629 	for (; i < htab->n_buckets; i++) {  in htab_map_get_next_key()
630 		head = select_bucket(htab, i);  in htab_map_get_next_key()
646 static void htab_elem_free(struct bpf_htab *htab, struct htab_elem *l)  in htab_elem_free()  argument
648 	if (htab->map.map_type == BPF_MAP_TYPE_PERCPU_HASH)  in htab_elem_free()
649 		free_percpu(htab_elem_get_ptr(l, htab->map.key_size));  in htab_elem_free()
656 	struct bpf_htab *htab = l->htab;  in htab_elem_free_rcu()  local
664 	htab_elem_free(htab, l);  in htab_elem_free_rcu()
669 static void free_htab_elem(struct bpf_htab *htab, struct htab_elem *l)  in free_htab_elem()  argument
671 	struct bpf_map *map = &htab->map;  in free_htab_elem()
679 	if (htab_is_prealloc(htab)) {  in free_htab_elem()
680 		pcpu_freelist_push(&htab->freelist, &l->fnode);  in free_htab_elem()
682 		atomic_dec(&htab->count);  in free_htab_elem()
683 		l->htab = htab;  in free_htab_elem()
688 static void pcpu_copy_value(struct bpf_htab *htab, void __percpu *pptr,  in pcpu_copy_value()  argument
693 		memcpy(this_cpu_ptr(pptr), value, htab->map.value_size);  in pcpu_copy_value()
695 		u32 size = round_up(htab->map.value_size, 8);  in pcpu_copy_value()
706 static bool fd_htab_map_needs_adjust(const struct bpf_htab *htab)  in fd_htab_map_needs_adjust()  argument
708 	return htab->map.map_type == BPF_MAP_TYPE_HASH_OF_MAPS &&  in fd_htab_map_needs_adjust()
712 static u32 htab_size_value(const struct bpf_htab *htab, bool percpu)  in htab_size_value()  argument
714 	u32 size = htab->map.value_size;  in htab_size_value()
716 	if (percpu || fd_htab_map_needs_adjust(htab))  in htab_size_value()
721 static struct htab_elem *alloc_htab_elem(struct bpf_htab *htab, void *key,  in alloc_htab_elem()  argument
726 	u32 size = htab_size_value(htab, percpu);  in alloc_htab_elem()
727 	bool prealloc = htab_is_prealloc(htab);  in alloc_htab_elem()
736 			pl_new = this_cpu_ptr(htab->extra_elems);  in alloc_htab_elem()
742 			l = pcpu_freelist_pop(&htab->freelist);  in alloc_htab_elem()
748 		if (atomic_inc_return(&htab->count) > htab->map.max_entries)  in alloc_htab_elem()
758 		l_new = kmalloc_node(htab->elem_size, GFP_ATOMIC | __GFP_NOWARN,  in alloc_htab_elem()
759 				     htab->map.numa_node);  in alloc_htab_elem()
781 		pcpu_copy_value(htab, pptr, value, onallcpus);  in alloc_htab_elem()
792 	atomic_dec(&htab->count);  in alloc_htab_elem()
796 static int check_flags(struct bpf_htab *htab, struct htab_elem *l_old,  in check_flags()  argument
814 	struct bpf_htab *htab = container_of(map, struct bpf_htab, map);  in htab_map_update_elem()  local
830 	hash = htab_map_hash(key, key_size, htab->hashrnd);  in htab_map_update_elem()
832 	b = __select_bucket(htab, hash);  in htab_map_update_elem()
840 	ret = check_flags(htab, l_old, map_flags);  in htab_map_update_elem()
844 	l_new = alloc_htab_elem(htab, key, value, key_size, hash, false, false,  in htab_map_update_elem()
858 		if (!htab_is_prealloc(htab))  in htab_map_update_elem()
859 			free_htab_elem(htab, l_old);  in htab_map_update_elem()
870 	struct bpf_htab *htab = container_of(map, struct bpf_htab, map);  in htab_lru_map_update_elem()  local
886 	hash = htab_map_hash(key, key_size, htab->hashrnd);  in htab_lru_map_update_elem()
888 	b = __select_bucket(htab, hash);  in htab_lru_map_update_elem()
896 	l_new = prealloc_lru_pop(htab, key, hash);  in htab_lru_map_update_elem()
906 	ret = check_flags(htab, l_old, map_flags);  in htab_lru_map_update_elem()
924 		bpf_lru_push_free(&htab->lru, &l_new->lru_node);  in htab_lru_map_update_elem()
926 		bpf_lru_push_free(&htab->lru, &l_old->lru_node);  in htab_lru_map_update_elem()
935 	struct bpf_htab *htab = container_of(map, struct bpf_htab, map);  in __htab_percpu_map_update_elem()  local
951 	hash = htab_map_hash(key, key_size, htab->hashrnd);  in __htab_percpu_map_update_elem()
953 	b = __select_bucket(htab, hash);  in __htab_percpu_map_update_elem()
961 	ret = check_flags(htab, l_old, map_flags);  in __htab_percpu_map_update_elem()
967 		pcpu_copy_value(htab, htab_elem_get_ptr(l_old, key_size),  in __htab_percpu_map_update_elem()
970 		l_new = alloc_htab_elem(htab, key, value, key_size,  in __htab_percpu_map_update_elem()
988 	struct bpf_htab *htab = container_of(map, struct bpf_htab, map);  in __htab_lru_percpu_map_update_elem()  local
1004 	hash = htab_map_hash(key, key_size, htab->hashrnd);  in __htab_lru_percpu_map_update_elem()
1006 	b = __select_bucket(htab, hash);  in __htab_lru_percpu_map_update_elem()
1015 		l_new = prealloc_lru_pop(htab, key, hash);  in __htab_lru_percpu_map_update_elem()
1025 	ret = check_flags(htab, l_old, map_flags);  in __htab_lru_percpu_map_update_elem()
1033 		pcpu_copy_value(htab, htab_elem_get_ptr(l_old, key_size),  in __htab_lru_percpu_map_update_elem()
1036 		pcpu_copy_value(htab, htab_elem_get_ptr(l_new, key_size),  in __htab_lru_percpu_map_update_elem()
1045 		bpf_lru_push_free(&htab->lru, &l_new->lru_node);  in __htab_lru_percpu_map_update_elem()
1065 	struct bpf_htab *htab = container_of(map, struct bpf_htab, map);  in htab_map_delete_elem()  local
1077 	hash = htab_map_hash(key, key_size, htab->hashrnd);  in htab_map_delete_elem()
1078 	b = __select_bucket(htab, hash);  in htab_map_delete_elem()
1087 		free_htab_elem(htab, l);  in htab_map_delete_elem()
1097 	struct bpf_htab *htab = container_of(map, struct bpf_htab, map);  in htab_lru_map_delete_elem()  local
1109 	hash = htab_map_hash(key, key_size, htab->hashrnd);  in htab_lru_map_delete_elem()
1110 	b = __select_bucket(htab, hash);  in htab_lru_map_delete_elem()
1124 		bpf_lru_push_free(&htab->lru, &l->lru_node);  in htab_lru_map_delete_elem()
1128 static void delete_all_elements(struct bpf_htab *htab)  in delete_all_elements()  argument
1132 	for (i = 0; i < htab->n_buckets; i++) {  in delete_all_elements()
1133 		struct hlist_nulls_head *head = select_bucket(htab, i);  in delete_all_elements()
1139 			htab_elem_free(htab, l);  in delete_all_elements()
1147 	struct bpf_htab *htab = container_of(map, struct bpf_htab, map);  in htab_map_free()  local
1160 	if (!htab_is_prealloc(htab))  in htab_map_free()
1161 		delete_all_elements(htab);  in htab_map_free()
1163 		prealloc_destroy(htab);  in htab_map_free()
1165 	free_percpu(htab->extra_elems);  in htab_map_free()
1166 	bpf_map_area_free(htab->buckets);  in htab_map_free()
1167 	kfree(htab);  in htab_map_free()
1240 	struct bpf_htab *htab = container_of(map, struct bpf_htab, map);  in bpf_percpu_hash_copy()  local
1256 	if (htab_is_lru(htab))  in bpf_percpu_hash_copy()
1273 	struct bpf_htab *htab = container_of(map, struct bpf_htab, map);  in bpf_percpu_hash_update()  local
1277 	if (htab_is_lru(htab))  in bpf_percpu_hash_update()
1317 	struct bpf_htab *htab = container_of(map, struct bpf_htab, map);  in fd_htab_map_free()  local
1323 	for (i = 0; i < htab->n_buckets; i++) {  in fd_htab_map_free()
1324 		head = select_bucket(htab, i);  in fd_htab_map_free()