47 				struct bpf_htab *htab;  member
62 static bool htab_is_lru(const struct bpf_htab *htab)  in htab_is_lru()  argument
64 	return htab->map.map_type == BPF_MAP_TYPE_LRU_HASH ||  in htab_is_lru()
65 		htab->map.map_type == BPF_MAP_TYPE_LRU_PERCPU_HASH;  in htab_is_lru()
68 static bool htab_is_percpu(const struct bpf_htab *htab)  in htab_is_percpu()  argument
70 	return htab->map.map_type == BPF_MAP_TYPE_PERCPU_HASH ||  in htab_is_percpu()
71 		htab->map.map_type == BPF_MAP_TYPE_LRU_PERCPU_HASH;  in htab_is_percpu()
74 static bool htab_is_prealloc(const struct bpf_htab *htab)  in htab_is_prealloc()  argument
76 	return !(htab->map.map_flags & BPF_F_NO_PREALLOC);  in htab_is_prealloc()
95 static struct htab_elem *get_htab_elem(struct bpf_htab *htab, int i)  in get_htab_elem()  argument
97 	return (struct htab_elem *) (htab->elems + i * htab->elem_size);  in get_htab_elem()
100 static void htab_free_elems(struct bpf_htab *htab)  in htab_free_elems()  argument
104 	if (!htab_is_percpu(htab))  in htab_free_elems()
107 	for (i = 0; i < htab->map.max_entries; i++) {  in htab_free_elems()
110 		pptr = htab_elem_get_ptr(get_htab_elem(htab, i),  in htab_free_elems()
111 					 htab->map.key_size);  in htab_free_elems()
116 	bpf_map_area_free(htab->elems);  in htab_free_elems()
119 static struct htab_elem *prealloc_lru_pop(struct bpf_htab *htab, void *key,  in prealloc_lru_pop()  argument
122 	struct bpf_lru_node *node = bpf_lru_pop_free(&htab->lru, hash);  in prealloc_lru_pop()
127 		memcpy(l->key, key, htab->map.key_size);  in prealloc_lru_pop()
134 static int prealloc_init(struct bpf_htab *htab)  in prealloc_init()  argument
136 	u32 num_entries = htab->map.max_entries;  in prealloc_init()
139 	if (!htab_is_percpu(htab) && !htab_is_lru(htab))  in prealloc_init()
142 	htab->elems = bpf_map_area_alloc(htab->elem_size * num_entries,  in prealloc_init()
143 					 htab->map.numa_node);  in prealloc_init()
144 	if (!htab->elems)  in prealloc_init()
147 	if (!htab_is_percpu(htab))  in prealloc_init()
151 		u32 size = round_up(htab->map.value_size, 8);  in prealloc_init()
157 		htab_elem_set_ptr(get_htab_elem(htab, i), htab->map.key_size,  in prealloc_init()
163 	if (htab_is_lru(htab))  in prealloc_init()
164 		err = bpf_lru_init(&htab->lru,  in prealloc_init()
165 				   htab->map.map_flags & BPF_F_NO_COMMON_LRU,  in prealloc_init()
169 				   htab);  in prealloc_init()
171 		err = pcpu_freelist_init(&htab->freelist);  in prealloc_init()
176 	if (htab_is_lru(htab))  in prealloc_init()
177 		bpf_lru_populate(&htab->lru, htab->elems,  in prealloc_init()
179 				 htab->elem_size, num_entries);  in prealloc_init()
181 		pcpu_freelist_populate(&htab->freelist,  in prealloc_init()
182 				       htab->elems + offsetof(struct htab_elem, fnode),  in prealloc_init()
183 				       htab->elem_size, num_entries);  in prealloc_init()
188 	htab_free_elems(htab);  in prealloc_init()
192 static void prealloc_destroy(struct bpf_htab *htab)  in prealloc_destroy()  argument
194 	htab_free_elems(htab);  in prealloc_destroy()
196 	if (htab_is_lru(htab))  in prealloc_destroy()
197 		bpf_lru_destroy(&htab->lru);  in prealloc_destroy()
199 		pcpu_freelist_destroy(&htab->freelist);  in prealloc_destroy()
202 static int alloc_extra_elems(struct bpf_htab *htab)  in alloc_extra_elems()  argument
214 		l = pcpu_freelist_pop(&htab->freelist);  in alloc_extra_elems()
221 	htab->extra_elems = pptr;  in alloc_extra_elems()
242 	BUILD_BUG_ON(offsetof(struct htab_elem, htab) !=  in htab_map_alloc_check()
308 	struct bpf_htab *htab;  in htab_map_alloc()  local
312 	htab = kzalloc(sizeof(*htab), GFP_USER);  in htab_map_alloc()
313 	if (!htab)  in htab_map_alloc()
316 	bpf_map_init_from_attr(&htab->map, attr);  in htab_map_alloc()
323 		htab->map.max_entries = roundup(attr->max_entries,  in htab_map_alloc()
325 		if (htab->map.max_entries < attr->max_entries)  in htab_map_alloc()
326 			htab->map.max_entries = rounddown(attr->max_entries,  in htab_map_alloc()
331 	htab->n_buckets = roundup_pow_of_two(htab->map.max_entries);  in htab_map_alloc()
333 	htab->elem_size = sizeof(struct htab_elem) +  in htab_map_alloc()
334 			  round_up(htab->map.key_size, 8);  in htab_map_alloc()
336 		htab->elem_size += sizeof(void *);  in htab_map_alloc()
338 		htab->elem_size += round_up(htab->map.value_size, 8);  in htab_map_alloc()
342 	if (htab->n_buckets == 0 ||  in htab_map_alloc()
343 	    htab->n_buckets > U32_MAX / sizeof(struct bucket))  in htab_map_alloc()
346 	cost = (u64) htab->n_buckets * sizeof(struct bucket) +  in htab_map_alloc()
347 	       (u64) htab->elem_size * htab->map.max_entries;  in htab_map_alloc()
350 		cost += (u64) round_up(htab->map.value_size, 8) *  in htab_map_alloc()
351 			num_possible_cpus() * htab->map.max_entries;  in htab_map_alloc()
353 	       cost += (u64) htab->elem_size * num_possible_cpus();  in htab_map_alloc()
356 	err = bpf_map_charge_init(&htab->map.memory, cost);  in htab_map_alloc()
361 	htab->buckets = bpf_map_area_alloc(htab->n_buckets *  in htab_map_alloc()
363 					   htab->map.numa_node);  in htab_map_alloc()
364 	if (!htab->buckets)  in htab_map_alloc()
367 	if (htab->map.map_flags & BPF_F_ZERO_SEED)  in htab_map_alloc()
368 		htab->hashrnd = 0;  in htab_map_alloc()
370 		htab->hashrnd = get_random_int();  in htab_map_alloc()
372 	for (i = 0; i < htab->n_buckets; i++) {  in htab_map_alloc()
373 		INIT_HLIST_NULLS_HEAD(&htab->buckets[i].head, i);  in htab_map_alloc()
374 		raw_spin_lock_init(&htab->buckets[i].lock);  in htab_map_alloc()
378 		err = prealloc_init(htab);  in htab_map_alloc()
386 			err = alloc_extra_elems(htab);  in htab_map_alloc()
392 	return &htab->map;  in htab_map_alloc()
395 	prealloc_destroy(htab);  in htab_map_alloc()
397 	bpf_map_area_free(htab->buckets);  in htab_map_alloc()
399 	bpf_map_charge_finish(&htab->map.memory);  in htab_map_alloc()
401 	kfree(htab);  in htab_map_alloc()
410 static inline struct bucket *__select_bucket(struct bpf_htab *htab, u32 hash)  in __select_bucket()  argument
412 	return &htab->buckets[hash & (htab->n_buckets - 1)];  in __select_bucket()
415 static inline struct hlist_nulls_head *select_bucket(struct bpf_htab *htab, u32 hash)  in select_bucket()  argument
417 	return &__select_bucket(htab, hash)->head;  in select_bucket()
463 	struct bpf_htab *htab = container_of(map, struct bpf_htab, map);  in __htab_map_lookup_elem()  local
473 	hash = htab_map_hash(key, key_size, htab->hashrnd);  in __htab_map_lookup_elem()
475 	head = select_bucket(htab, hash);  in __htab_map_lookup_elem()
477 	l = lookup_nulls_elem_raw(head, hash, key, key_size, htab->n_buckets);  in __htab_map_lookup_elem()
572 	struct bpf_htab *htab = (struct bpf_htab *)arg;  in htab_lru_map_delete_node()  local
580 	b = __select_bucket(htab, tgt_l->hash);  in htab_lru_map_delete_node()
599 	struct bpf_htab *htab = container_of(map, struct bpf_htab, map);  in htab_map_get_next_key()  local
612 	hash = htab_map_hash(key, key_size, htab->hashrnd);  in htab_map_get_next_key()
614 	head = select_bucket(htab, hash);  in htab_map_get_next_key()
617 	l = lookup_nulls_elem_raw(head, hash, key, key_size, htab->n_buckets);  in htab_map_get_next_key()
633 	i = hash & (htab->n_buckets - 1);  in htab_map_get_next_key()
638 	for (; i < htab->n_buckets; i++) {  in htab_map_get_next_key()
639 		head = select_bucket(htab, i);  in htab_map_get_next_key()
655 static void htab_elem_free(struct bpf_htab *htab, struct htab_elem *l)  in htab_elem_free()  argument
657 	if (htab->map.map_type == BPF_MAP_TYPE_PERCPU_HASH)  in htab_elem_free()
658 		free_percpu(htab_elem_get_ptr(l, htab->map.key_size));  in htab_elem_free()
665 	struct bpf_htab *htab = l->htab;  in htab_elem_free_rcu()  local
673 	htab_elem_free(htab, l);  in htab_elem_free_rcu()
678 static void free_htab_elem(struct bpf_htab *htab, struct htab_elem *l)  in free_htab_elem()  argument
680 	struct bpf_map *map = &htab->map;  in free_htab_elem()
688 	if (htab_is_prealloc(htab)) {  in free_htab_elem()
689 		__pcpu_freelist_push(&htab->freelist, &l->fnode);  in free_htab_elem()
691 		atomic_dec(&htab->count);  in free_htab_elem()
692 		l->htab = htab;  in free_htab_elem()
697 static void pcpu_copy_value(struct bpf_htab *htab, void __percpu *pptr,  in pcpu_copy_value()  argument
702 		memcpy(this_cpu_ptr(pptr), value, htab->map.value_size);  in pcpu_copy_value()
704 		u32 size = round_up(htab->map.value_size, 8);  in pcpu_copy_value()
715 static bool fd_htab_map_needs_adjust(const struct bpf_htab *htab)  in fd_htab_map_needs_adjust()  argument
717 	return htab->map.map_type == BPF_MAP_TYPE_HASH_OF_MAPS &&  in fd_htab_map_needs_adjust()
721 static struct htab_elem *alloc_htab_elem(struct bpf_htab *htab, void *key,  in alloc_htab_elem()  argument
726 	u32 size = htab->map.value_size;  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()
764 		check_and_init_map_lock(&htab->map,  in alloc_htab_elem()
784 		pcpu_copy_value(htab, pptr, value, onallcpus);  in alloc_htab_elem()
788 	} else if (fd_htab_map_needs_adjust(htab)) {  in alloc_htab_elem()
792 		copy_map_value(&htab->map,  in alloc_htab_elem()
800 	atomic_dec(&htab->count);  in alloc_htab_elem()
804 static int check_flags(struct bpf_htab *htab, struct htab_elem *l_old,  in check_flags()  argument
822 	struct bpf_htab *htab = container_of(map, struct bpf_htab, map);  in htab_map_update_elem()  local
838 	hash = htab_map_hash(key, key_size, htab->hashrnd);  in htab_map_update_elem()
840 	b = __select_bucket(htab, hash);  in htab_map_update_elem()
848 					      htab->n_buckets);  in htab_map_update_elem()
849 		ret = check_flags(htab, l_old, map_flags);  in htab_map_update_elem()
870 	ret = check_flags(htab, l_old, map_flags);  in htab_map_update_elem()
888 	l_new = alloc_htab_elem(htab, key, value, key_size, hash, false, false,  in htab_map_update_elem()
902 		if (!htab_is_prealloc(htab))  in htab_map_update_elem()
903 			free_htab_elem(htab, l_old);  in htab_map_update_elem()
914 	struct bpf_htab *htab = container_of(map, struct bpf_htab, map);  in htab_lru_map_update_elem()  local
930 	hash = htab_map_hash(key, key_size, htab->hashrnd);  in htab_lru_map_update_elem()
932 	b = __select_bucket(htab, hash);  in htab_lru_map_update_elem()
940 	l_new = prealloc_lru_pop(htab, key, hash);  in htab_lru_map_update_elem()
950 	ret = check_flags(htab, l_old, map_flags);  in htab_lru_map_update_elem()
968 		bpf_lru_push_free(&htab->lru, &l_new->lru_node);  in htab_lru_map_update_elem()
970 		bpf_lru_push_free(&htab->lru, &l_old->lru_node);  in htab_lru_map_update_elem()
979 	struct bpf_htab *htab = container_of(map, struct bpf_htab, map);  in __htab_percpu_map_update_elem()  local
995 	hash = htab_map_hash(key, key_size, htab->hashrnd);  in __htab_percpu_map_update_elem()
997 	b = __select_bucket(htab, hash);  in __htab_percpu_map_update_elem()
1005 	ret = check_flags(htab, l_old, map_flags);  in __htab_percpu_map_update_elem()
1011 		pcpu_copy_value(htab, htab_elem_get_ptr(l_old, key_size),  in __htab_percpu_map_update_elem()
1014 		l_new = alloc_htab_elem(htab, key, value, key_size,  in __htab_percpu_map_update_elem()
1032 	struct bpf_htab *htab = container_of(map, struct bpf_htab, map);  in __htab_lru_percpu_map_update_elem()  local
1048 	hash = htab_map_hash(key, key_size, htab->hashrnd);  in __htab_lru_percpu_map_update_elem()
1050 	b = __select_bucket(htab, hash);  in __htab_lru_percpu_map_update_elem()
1059 		l_new = prealloc_lru_pop(htab, key, hash);  in __htab_lru_percpu_map_update_elem()
1069 	ret = check_flags(htab, l_old, map_flags);  in __htab_lru_percpu_map_update_elem()
1077 		pcpu_copy_value(htab, htab_elem_get_ptr(l_old, key_size),  in __htab_lru_percpu_map_update_elem()
1080 		pcpu_copy_value(htab, htab_elem_get_ptr(l_new, key_size),  in __htab_lru_percpu_map_update_elem()
1089 		bpf_lru_push_free(&htab->lru, &l_new->lru_node);  in __htab_lru_percpu_map_update_elem()
1109 	struct bpf_htab *htab = container_of(map, struct bpf_htab, map);  in htab_map_delete_elem()  local
1121 	hash = htab_map_hash(key, key_size, htab->hashrnd);  in htab_map_delete_elem()
1122 	b = __select_bucket(htab, hash);  in htab_map_delete_elem()
1131 		free_htab_elem(htab, l);  in htab_map_delete_elem()
1141 	struct bpf_htab *htab = container_of(map, struct bpf_htab, map);  in htab_lru_map_delete_elem()  local
1153 	hash = htab_map_hash(key, key_size, htab->hashrnd);  in htab_lru_map_delete_elem()
1154 	b = __select_bucket(htab, hash);  in htab_lru_map_delete_elem()
1168 		bpf_lru_push_free(&htab->lru, &l->lru_node);  in htab_lru_map_delete_elem()
1172 static void delete_all_elements(struct bpf_htab *htab)  in delete_all_elements()  argument
1176 	for (i = 0; i < htab->n_buckets; i++) {  in delete_all_elements()
1177 		struct hlist_nulls_head *head = select_bucket(htab, i);  in delete_all_elements()
1183 			htab_elem_free(htab, l);  in delete_all_elements()
1191 	struct bpf_htab *htab = container_of(map, struct bpf_htab, map);  in htab_map_free()  local
1204 	if (!htab_is_prealloc(htab))  in htab_map_free()
1205 		delete_all_elements(htab);  in htab_map_free()
1207 		prealloc_destroy(htab);  in htab_map_free()
1209 	free_percpu(htab->extra_elems);  in htab_map_free()
1210 	bpf_map_area_free(htab->buckets);  in htab_map_free()
1211 	kfree(htab);  in htab_map_free()
1318 	struct bpf_htab *htab = container_of(map, struct bpf_htab, map);  in bpf_percpu_hash_update()  local
1322 	if (htab_is_lru(htab))  in bpf_percpu_hash_update()
1393 	struct bpf_htab *htab = container_of(map, struct bpf_htab, map);  in fd_htab_map_free()  local
1399 	for (i = 0; i < htab->n_buckets; i++) {  in fd_htab_map_free()
1400 		head = select_bucket(htab, i);  in fd_htab_map_free()