41 static u32 head_hashfn(struct rhashtable *ht,  in head_hashfn()  argument
45 	return rht_head_hashfn(ht, tbl, he, ht->p);  in head_hashfn()
51 int lockdep_rht_mutex_is_held(struct rhashtable *ht)  in lockdep_rht_mutex_is_held()  argument
53 	return (debug_locks) ? lockdep_is_held(&ht->mutex) : 1;  in lockdep_rht_mutex_is_held()
116 static union nested_table *nested_table_alloc(struct rhashtable *ht,  in nested_table_alloc()  argument
139 static struct bucket_table *nested_bucket_table_alloc(struct rhashtable *ht,  in nested_bucket_table_alloc()  argument
156 	if (!nested_table_alloc(ht, (union nested_table __rcu **)tbl->buckets,  in nested_bucket_table_alloc()
167 static struct bucket_table *bucket_table_alloc(struct rhashtable *ht,  in bucket_table_alloc()  argument
181 		tbl = nested_bucket_table_alloc(ht, nbuckets, gfp);  in bucket_table_alloc()
195 				   ht->p.locks_mul, gfp) < 0) {  in bucket_table_alloc()
210 static struct bucket_table *rhashtable_last_table(struct rhashtable *ht,  in rhashtable_last_table()  argument
217 		tbl = rht_dereference_rcu(tbl->future_tbl, ht);  in rhashtable_last_table()
223 static int rhashtable_rehash_one(struct rhashtable *ht, unsigned int old_hash)  in rhashtable_rehash_one()  argument
225 	struct bucket_table *old_tbl = rht_dereference(ht->tbl, ht);  in rhashtable_rehash_one()
226 	struct bucket_table *new_tbl = rhashtable_last_table(ht, old_tbl);  in rhashtable_rehash_one()
251 	new_hash = head_hashfn(ht, new_tbl, entry);  in rhashtable_rehash_one()
270 static int rhashtable_rehash_chain(struct rhashtable *ht,  in rhashtable_rehash_chain()  argument
273 	struct bucket_table *old_tbl = rht_dereference(ht->tbl, ht);  in rhashtable_rehash_chain()
280 	while (!(err = rhashtable_rehash_one(ht, old_hash)))  in rhashtable_rehash_chain()
292 static int rhashtable_rehash_attach(struct rhashtable *ht,  in rhashtable_rehash_attach()  argument
308 static int rhashtable_rehash_table(struct rhashtable *ht)  in rhashtable_rehash_table()  argument
310 	struct bucket_table *old_tbl = rht_dereference(ht->tbl, ht);  in rhashtable_rehash_table()
316 	new_tbl = rht_dereference(old_tbl->future_tbl, ht);  in rhashtable_rehash_table()
321 		err = rhashtable_rehash_chain(ht, old_hash);  in rhashtable_rehash_table()
328 	rcu_assign_pointer(ht->tbl, new_tbl);  in rhashtable_rehash_table()
330 	spin_lock(&ht->lock);  in rhashtable_rehash_table()
333 	spin_unlock(&ht->lock);  in rhashtable_rehash_table()
341 	return rht_dereference(new_tbl->future_tbl, ht) ? -EAGAIN : 0;  in rhashtable_rehash_table()
344 static int rhashtable_rehash_alloc(struct rhashtable *ht,  in rhashtable_rehash_alloc()  argument
351 	ASSERT_RHT_MUTEX(ht);  in rhashtable_rehash_alloc()
353 	new_tbl = bucket_table_alloc(ht, size, GFP_KERNEL);  in rhashtable_rehash_alloc()
357 	err = rhashtable_rehash_attach(ht, old_tbl, new_tbl);  in rhashtable_rehash_alloc()
380 static int rhashtable_shrink(struct rhashtable *ht)  in rhashtable_shrink()  argument
382 	struct bucket_table *old_tbl = rht_dereference(ht->tbl, ht);  in rhashtable_shrink()
383 	unsigned int nelems = atomic_read(&ht->nelems);  in rhashtable_shrink()
388 	if (size < ht->p.min_size)  in rhashtable_shrink()
389 		size = ht->p.min_size;  in rhashtable_shrink()
394 	if (rht_dereference(old_tbl->future_tbl, ht))  in rhashtable_shrink()
397 	return rhashtable_rehash_alloc(ht, old_tbl, size);  in rhashtable_shrink()
402 	struct rhashtable *ht;  in rht_deferred_worker()  local
406 	ht = container_of(work, struct rhashtable, run_work);  in rht_deferred_worker()
407 	mutex_lock(&ht->mutex);  in rht_deferred_worker()
409 	tbl = rht_dereference(ht->tbl, ht);  in rht_deferred_worker()
410 	tbl = rhashtable_last_table(ht, tbl);  in rht_deferred_worker()
412 	if (rht_grow_above_75(ht, tbl))  in rht_deferred_worker()
413 		err = rhashtable_rehash_alloc(ht, tbl, tbl->size * 2);  in rht_deferred_worker()
414 	else if (ht->p.automatic_shrinking && rht_shrink_below_30(ht, tbl))  in rht_deferred_worker()
415 		err = rhashtable_shrink(ht);  in rht_deferred_worker()
417 		err = rhashtable_rehash_alloc(ht, tbl, tbl->size);  in rht_deferred_worker()
420 		err = rhashtable_rehash_table(ht);  in rht_deferred_worker()
422 	mutex_unlock(&ht->mutex);  in rht_deferred_worker()
425 		schedule_work(&ht->run_work);  in rht_deferred_worker()
428 static int rhashtable_insert_rehash(struct rhashtable *ht,  in rhashtable_insert_rehash()  argument
436 	old_tbl = rht_dereference_rcu(ht->tbl, ht);  in rhashtable_insert_rehash()
442 	if (rht_grow_above_75(ht, tbl))  in rhashtable_insert_rehash()
450 	new_tbl = bucket_table_alloc(ht, size, GFP_ATOMIC | __GFP_NOWARN);  in rhashtable_insert_rehash()
454 	err = rhashtable_rehash_attach(ht, tbl, new_tbl);  in rhashtable_insert_rehash()
460 		schedule_work(&ht->run_work);  in rhashtable_insert_rehash()
471 		schedule_work(&ht->run_work);  in rhashtable_insert_rehash()
476 static void *rhashtable_lookup_one(struct rhashtable *ht,  in rhashtable_lookup_one()  argument
481 		.ht = ht,  in rhashtable_lookup_one()
496 		    (ht->p.obj_cmpfn ?  in rhashtable_lookup_one()
497 		     ht->p.obj_cmpfn(&arg, rht_obj(ht, head)) :  in rhashtable_lookup_one()
498 		     rhashtable_compare(&arg, rht_obj(ht, head)))) {  in rhashtable_lookup_one()
503 		if (!ht->rhlist)  in rhashtable_lookup_one()
504 			return rht_obj(ht, head);  in rhashtable_lookup_one()
523 static struct bucket_table *rhashtable_insert_one(struct rhashtable *ht,  in rhashtable_insert_one()  argument
539 	new_tbl = rht_dereference_rcu(tbl->future_tbl, ht);  in rhashtable_insert_one()
546 	if (unlikely(rht_grow_above_max(ht, tbl)))  in rhashtable_insert_one()
549 	if (unlikely(rht_grow_above_100(ht, tbl)))  in rhashtable_insert_one()
552 	pprev = rht_bucket_insert(ht, tbl, hash);  in rhashtable_insert_one()
559 	if (ht->rhlist) {  in rhashtable_insert_one()
568 	atomic_inc(&ht->nelems);  in rhashtable_insert_one()
569 	if (rht_grow_above_75(ht, tbl))  in rhashtable_insert_one()
570 		schedule_work(&ht->run_work);  in rhashtable_insert_one()
575 static void *rhashtable_try_insert(struct rhashtable *ht, const void *key,  in rhashtable_try_insert()  argument
584 	tbl = rcu_dereference(ht->tbl);  in rhashtable_try_insert()
590 		hash = rht_head_hashfn(ht, tbl, obj, ht->p);  in rhashtable_try_insert()
598 		tbl = rht_dereference_rcu(tbl->future_tbl, ht);  in rhashtable_try_insert()
601 	data = rhashtable_lookup_one(ht, tbl, hash, key, obj);  in rhashtable_try_insert()
602 	new_tbl = rhashtable_insert_one(ht, tbl, hash, obj, data);  in rhashtable_try_insert()
608 		hash = rht_head_hashfn(ht, tbl, obj, ht->p);  in rhashtable_try_insert()
612 		data = rhashtable_lookup_one(ht, tbl, hash, key, obj);  in rhashtable_try_insert()
613 		new_tbl = rhashtable_insert_one(ht, tbl, hash, obj, data);  in rhashtable_try_insert()
623 		data = ERR_PTR(rhashtable_insert_rehash(ht, tbl) ?:  in rhashtable_try_insert()
629 void *rhashtable_insert_slow(struct rhashtable *ht, const void *key,  in rhashtable_insert_slow()  argument
636 		data = rhashtable_try_insert(ht, key, obj);  in rhashtable_insert_slow()
665 void rhashtable_walk_enter(struct rhashtable *ht, struct rhashtable_iter *iter)  in rhashtable_walk_enter()  argument
667 	iter->ht = ht;  in rhashtable_walk_enter()
673 	spin_lock(&ht->lock);  in rhashtable_walk_enter()
675 		rcu_dereference_protected(ht->tbl, lockdep_is_held(&ht->lock));  in rhashtable_walk_enter()
677 	spin_unlock(&ht->lock);  in rhashtable_walk_enter()
689 	spin_lock(&iter->ht->lock);  in rhashtable_walk_exit()
692 	spin_unlock(&iter->ht->lock);  in rhashtable_walk_exit()
717 	struct rhashtable *ht = iter->ht;  in rhashtable_walk_start_check()  local
718 	bool rhlist = ht->rhlist;  in rhashtable_walk_start_check()
722 	spin_lock(&ht->lock);  in rhashtable_walk_start_check()
725 	spin_unlock(&ht->lock);  in rhashtable_walk_start_check()
730 		iter->walker.tbl = rht_dereference_rcu(ht->tbl, ht);  in rhashtable_walk_start_check()
791 	struct rhashtable *ht = iter->ht;  in __rhashtable_walk_find_next()  local
793 	bool rhlist = ht->rhlist;  in __rhashtable_walk_find_next()
824 			return rht_obj(ht, rhlist ? &list->rhead : p);  in __rhashtable_walk_find_next()
835 	iter->walker.tbl = rht_dereference_rcu(tbl->future_tbl, ht);  in __rhashtable_walk_find_next()
862 	struct rhashtable *ht = iter->ht;  in rhashtable_walk_next()  local
864 	bool rhlist = ht->rhlist;  in rhashtable_walk_next()
875 			return rht_obj(ht, rhlist ? &list->rhead : p);  in rhashtable_walk_next()
901 	struct rhashtable *ht = iter->ht;  in rhashtable_walk_peek()  local
905 		return rht_obj(ht, ht->rhlist ? &list->rhead : p);  in rhashtable_walk_peek()
933 	struct rhashtable *ht;  in rhashtable_walk_stop()  local
939 	ht = iter->ht;  in rhashtable_walk_stop()
941 	spin_lock(&ht->lock);  in rhashtable_walk_stop()
946 	spin_unlock(&ht->lock);  in rhashtable_walk_stop()
1014 int rhashtable_init(struct rhashtable *ht,  in rhashtable_init()  argument
1024 	memset(ht, 0, sizeof(*ht));  in rhashtable_init()
1025 	mutex_init(&ht->mutex);  in rhashtable_init()
1026 	spin_lock_init(&ht->lock);  in rhashtable_init()
1027 	memcpy(&ht->p, params, sizeof(*params));  in rhashtable_init()
1030 		ht->p.min_size = roundup_pow_of_two(params->min_size);  in rhashtable_init()
1033 	ht->max_elems = 1u << 31;  in rhashtable_init()
1036 		ht->p.max_size = rounddown_pow_of_two(params->max_size);  in rhashtable_init()
1037 		if (ht->p.max_size < ht->max_elems / 2)  in rhashtable_init()
1038 			ht->max_elems = ht->p.max_size * 2;  in rhashtable_init()
1041 	ht->p.min_size = max_t(u16, ht->p.min_size, HASH_MIN_SIZE);  in rhashtable_init()
1043 	size = rounded_hashtable_size(&ht->p);  in rhashtable_init()
1046 		ht->p.locks_mul = roundup_pow_of_two(params->locks_mul);  in rhashtable_init()
1048 		ht->p.locks_mul = BUCKET_LOCKS_PER_CPU;  in rhashtable_init()
1050 	ht->key_len = ht->p.key_len;  in rhashtable_init()
1052 		ht->p.hashfn = jhash;  in rhashtable_init()
1054 		if (!(ht->key_len & (sizeof(u32) - 1))) {  in rhashtable_init()
1055 			ht->key_len /= sizeof(u32);  in rhashtable_init()
1056 			ht->p.hashfn = rhashtable_jhash2;  in rhashtable_init()
1065 	tbl = bucket_table_alloc(ht, size, GFP_KERNEL);  in rhashtable_init()
1067 		size = max_t(u16, ht->p.min_size, HASH_MIN_SIZE);  in rhashtable_init()
1068 		tbl = bucket_table_alloc(ht, size, GFP_KERNEL | __GFP_NOFAIL);  in rhashtable_init()
1071 	atomic_set(&ht->nelems, 0);  in rhashtable_init()
1073 	RCU_INIT_POINTER(ht->tbl, tbl);  in rhashtable_init()
1075 	INIT_WORK(&ht->run_work, rht_deferred_worker);  in rhashtable_init()
1094 	err = rhashtable_init(&hlt->ht, params);  in rhltable_init()
1095 	hlt->ht.rhlist = true;  in rhltable_init()
1100 static void rhashtable_free_one(struct rhashtable *ht, struct rhash_head *obj,  in rhashtable_free_one()  argument
1106 	if (!ht->rhlist) {  in rhashtable_free_one()
1107 		free_fn(rht_obj(ht, obj), arg);  in rhashtable_free_one()
1114 		list = rht_dereference(list->next, ht);  in rhashtable_free_one()
1115 		free_fn(rht_obj(ht, obj), arg);  in rhashtable_free_one()
1134 void rhashtable_free_and_destroy(struct rhashtable *ht,  in rhashtable_free_and_destroy()  argument
1141 	cancel_work_sync(&ht->run_work);  in rhashtable_free_and_destroy()
1143 	mutex_lock(&ht->mutex);  in rhashtable_free_and_destroy()
1144 	tbl = rht_dereference(ht->tbl, ht);  in rhashtable_free_and_destroy()
1151 			for (pos = rht_dereference(*rht_bucket(tbl, i), ht),  in rhashtable_free_and_destroy()
1153 					rht_dereference(pos->next, ht) : NULL;  in rhashtable_free_and_destroy()
1157 					rht_dereference(pos->next, ht) : NULL)  in rhashtable_free_and_destroy()
1158 				rhashtable_free_one(ht, pos, free_fn, arg);  in rhashtable_free_and_destroy()
1162 	next_tbl = rht_dereference(tbl->future_tbl, ht);  in rhashtable_free_and_destroy()
1168 	mutex_unlock(&ht->mutex);  in rhashtable_free_and_destroy()
1172 void rhashtable_destroy(struct rhashtable *ht)  in rhashtable_destroy()  argument
1174 	return rhashtable_free_and_destroy(ht, NULL, NULL);  in rhashtable_destroy()
1209 struct rhash_head __rcu **rht_bucket_nested_insert(struct rhashtable *ht,  in rht_bucket_nested_insert()  argument
1220 	ntbl = nested_table_alloc(ht, &ntbl[index].table,  in rht_bucket_nested_insert()
1227 		ntbl = nested_table_alloc(ht, &ntbl[index].table,  in rht_bucket_nested_insert()