35 static u32 head_hashfn(struct rhashtable *ht,  in head_hashfn()  argument
39 	return rht_head_hashfn(ht, tbl, he, ht->p);  in head_hashfn()
45 int lockdep_rht_mutex_is_held(struct rhashtable *ht)  in lockdep_rht_mutex_is_held()  argument
47 	return (debug_locks) ? lockdep_is_held(&ht->mutex) : 1;  in lockdep_rht_mutex_is_held()
63 static int alloc_bucket_locks(struct rhashtable *ht, struct bucket_table *tbl,  in alloc_bucket_locks()  argument
74 	size = roundup_pow_of_two(nr_pcpus * ht->p.locks_mul);  in alloc_bucket_locks()
111 static struct bucket_table *bucket_table_alloc(struct rhashtable *ht,  in bucket_table_alloc()  argument
130 	if (alloc_bucket_locks(ht, tbl, gfp) < 0) {  in bucket_table_alloc()
140 		INIT_RHT_NULLS_HEAD(tbl->buckets[i], ht, i);  in bucket_table_alloc()
145 static struct bucket_table *rhashtable_last_table(struct rhashtable *ht,  in rhashtable_last_table()  argument
152 		tbl = rht_dereference_rcu(tbl->future_tbl, ht);  in rhashtable_last_table()
158 static int rhashtable_rehash_one(struct rhashtable *ht, unsigned int old_hash)  in rhashtable_rehash_one()  argument
160 	struct bucket_table *old_tbl = rht_dereference(ht->tbl, ht);  in rhashtable_rehash_one()
161 	struct bucket_table *new_tbl = rhashtable_last_table(ht,  in rhashtable_rehash_one()
162 		rht_dereference_rcu(old_tbl->future_tbl, ht));  in rhashtable_rehash_one()
182 	new_hash = head_hashfn(ht, new_tbl, entry);  in rhashtable_rehash_one()
201 static void rhashtable_rehash_chain(struct rhashtable *ht,  in rhashtable_rehash_chain()  argument
204 	struct bucket_table *old_tbl = rht_dereference(ht->tbl, ht);  in rhashtable_rehash_chain()
210 	while (!rhashtable_rehash_one(ht, old_hash))  in rhashtable_rehash_chain()
216 static int rhashtable_rehash_attach(struct rhashtable *ht,  in rhashtable_rehash_attach()  argument
242 static int rhashtable_rehash_table(struct rhashtable *ht)  in rhashtable_rehash_table()  argument
244 	struct bucket_table *old_tbl = rht_dereference(ht->tbl, ht);  in rhashtable_rehash_table()
249 	new_tbl = rht_dereference(old_tbl->future_tbl, ht);  in rhashtable_rehash_table()
254 		rhashtable_rehash_chain(ht, old_hash);  in rhashtable_rehash_table()
257 	rcu_assign_pointer(ht->tbl, new_tbl);  in rhashtable_rehash_table()
259 	spin_lock(&ht->lock);  in rhashtable_rehash_table()
262 	spin_unlock(&ht->lock);  in rhashtable_rehash_table()
270 	return rht_dereference(new_tbl->future_tbl, ht) ? -EAGAIN : 0;  in rhashtable_rehash_table()
288 static int rhashtable_expand(struct rhashtable *ht)  in rhashtable_expand()  argument
290 	struct bucket_table *new_tbl, *old_tbl = rht_dereference(ht->tbl, ht);  in rhashtable_expand()
293 	ASSERT_RHT_MUTEX(ht);  in rhashtable_expand()
295 	old_tbl = rhashtable_last_table(ht, old_tbl);  in rhashtable_expand()
297 	new_tbl = bucket_table_alloc(ht, old_tbl->size * 2, GFP_KERNEL);  in rhashtable_expand()
301 	err = rhashtable_rehash_attach(ht, old_tbl, new_tbl);  in rhashtable_expand()
324 static int rhashtable_shrink(struct rhashtable *ht)  in rhashtable_shrink()  argument
326 	struct bucket_table *new_tbl, *old_tbl = rht_dereference(ht->tbl, ht);  in rhashtable_shrink()
330 	ASSERT_RHT_MUTEX(ht);  in rhashtable_shrink()
332 	size = roundup_pow_of_two(atomic_read(&ht->nelems) * 3 / 2);  in rhashtable_shrink()
333 	if (size < ht->p.min_size)  in rhashtable_shrink()
334 		size = ht->p.min_size;  in rhashtable_shrink()
339 	if (rht_dereference(old_tbl->future_tbl, ht))  in rhashtable_shrink()
342 	new_tbl = bucket_table_alloc(ht, size, GFP_KERNEL);  in rhashtable_shrink()
346 	err = rhashtable_rehash_attach(ht, old_tbl, new_tbl);  in rhashtable_shrink()
355 	struct rhashtable *ht;  in rht_deferred_worker()  local
359 	ht = container_of(work, struct rhashtable, run_work);  in rht_deferred_worker()
360 	mutex_lock(&ht->mutex);  in rht_deferred_worker()
362 	tbl = rht_dereference(ht->tbl, ht);  in rht_deferred_worker()
363 	tbl = rhashtable_last_table(ht, tbl);  in rht_deferred_worker()
365 	if (rht_grow_above_75(ht, tbl))  in rht_deferred_worker()
366 		rhashtable_expand(ht);  in rht_deferred_worker()
367 	else if (ht->p.automatic_shrinking && rht_shrink_below_30(ht, tbl))  in rht_deferred_worker()
368 		rhashtable_shrink(ht);  in rht_deferred_worker()
370 	err = rhashtable_rehash_table(ht);  in rht_deferred_worker()
372 	mutex_unlock(&ht->mutex);  in rht_deferred_worker()
375 		schedule_work(&ht->run_work);  in rht_deferred_worker()
378 static bool rhashtable_check_elasticity(struct rhashtable *ht,  in rhashtable_check_elasticity()  argument
382 	unsigned int elasticity = ht->elasticity;  in rhashtable_check_elasticity()
392 int rhashtable_insert_rehash(struct rhashtable *ht,  in rhashtable_insert_rehash()  argument
400 	old_tbl = rht_dereference_rcu(ht->tbl, ht);  in rhashtable_insert_rehash()
406 	if (rht_grow_above_75(ht, tbl))  in rhashtable_insert_rehash()
414 	new_tbl = bucket_table_alloc(ht, size, GFP_ATOMIC);  in rhashtable_insert_rehash()
418 	err = rhashtable_rehash_attach(ht, tbl, new_tbl);  in rhashtable_insert_rehash()
424 		schedule_work(&ht->run_work);  in rhashtable_insert_rehash()
435 		schedule_work(&ht->run_work);  in rhashtable_insert_rehash()
441 struct bucket_table *rhashtable_insert_slow(struct rhashtable *ht,  in rhashtable_insert_slow()  argument
450 	tbl = rhashtable_last_table(ht, tbl);  in rhashtable_insert_slow()
451 	hash = head_hashfn(ht, tbl, obj);  in rhashtable_insert_slow()
455 	if (key && rhashtable_lookup_fast(ht, key, ht->p))  in rhashtable_insert_slow()
459 	if (unlikely(rht_grow_above_max(ht, tbl)))  in rhashtable_insert_slow()
463 	if (rhashtable_check_elasticity(ht, tbl, hash) ||  in rhashtable_insert_slow()
464 	    rht_grow_above_100(ht, tbl))  in rhashtable_insert_slow()
475 	atomic_inc(&ht->nelems);  in rhashtable_insert_slow()
510 int rhashtable_walk_init(struct rhashtable *ht, struct rhashtable_iter *iter)  in rhashtable_walk_init()  argument
512 	iter->ht = ht;  in rhashtable_walk_init()
521 	spin_lock(&ht->lock);  in rhashtable_walk_init()
523 		rcu_dereference_protected(ht->tbl, lockdep_is_held(&ht->lock));  in rhashtable_walk_init()
525 	spin_unlock(&ht->lock);  in rhashtable_walk_init()
539 	spin_lock(&iter->ht->lock);  in rhashtable_walk_exit()
542 	spin_unlock(&iter->ht->lock);  in rhashtable_walk_exit()
564 	struct rhashtable *ht = iter->ht;  in rhashtable_walk_start()  local
568 	spin_lock(&ht->lock);  in rhashtable_walk_start()
571 	spin_unlock(&ht->lock);  in rhashtable_walk_start()
574 		iter->walker->tbl = rht_dereference_rcu(ht->tbl, ht);  in rhashtable_walk_start()
597 	struct rhashtable *ht = iter->ht;  in rhashtable_walk_next()  local
618 			return rht_obj(ht, p);  in rhashtable_walk_next()
629 	iter->walker->tbl = rht_dereference_rcu(tbl->future_tbl, ht);  in rhashtable_walk_next()
649 	struct rhashtable *ht;  in rhashtable_walk_stop()  local
655 	ht = iter->ht;  in rhashtable_walk_stop()
657 	spin_lock(&ht->lock);  in rhashtable_walk_stop()
662 	spin_unlock(&ht->lock);  in rhashtable_walk_stop()
725 int rhashtable_init(struct rhashtable *ht,  in rhashtable_init()  argument
740 	memset(ht, 0, sizeof(*ht));  in rhashtable_init()
741 	mutex_init(&ht->mutex);  in rhashtable_init()
742 	spin_lock_init(&ht->lock);  in rhashtable_init()
743 	memcpy(&ht->p, params, sizeof(*params));  in rhashtable_init()
746 		ht->p.min_size = roundup_pow_of_two(params->min_size);  in rhashtable_init()
749 		ht->p.max_size = rounddown_pow_of_two(params->max_size);  in rhashtable_init()
752 		ht->p.insecure_max_entries =  in rhashtable_init()
755 		ht->p.insecure_max_entries = ht->p.max_size * 2;  in rhashtable_init()
757 	ht->p.min_size = max(ht->p.min_size, HASH_MIN_SIZE);  in rhashtable_init()
760 		size = rounded_hashtable_size(&ht->p);  in rhashtable_init()
775 		ht->elasticity = 16;  in rhashtable_init()
778 		ht->p.locks_mul = roundup_pow_of_two(params->locks_mul);  in rhashtable_init()
780 		ht->p.locks_mul = BUCKET_LOCKS_PER_CPU;  in rhashtable_init()
782 	ht->key_len = ht->p.key_len;  in rhashtable_init()
784 		ht->p.hashfn = jhash;  in rhashtable_init()
786 		if (!(ht->key_len & (sizeof(u32) - 1))) {  in rhashtable_init()
787 			ht->key_len /= sizeof(u32);  in rhashtable_init()
788 			ht->p.hashfn = rhashtable_jhash2;  in rhashtable_init()
792 	tbl = bucket_table_alloc(ht, size, GFP_KERNEL);  in rhashtable_init()
796 	atomic_set(&ht->nelems, 0);  in rhashtable_init()
798 	RCU_INIT_POINTER(ht->tbl, tbl);  in rhashtable_init()
800 	INIT_WORK(&ht->run_work, rht_deferred_worker);  in rhashtable_init()
821 void rhashtable_free_and_destroy(struct rhashtable *ht,  in rhashtable_free_and_destroy()  argument
828 	cancel_work_sync(&ht->run_work);  in rhashtable_free_and_destroy()
830 	mutex_lock(&ht->mutex);  in rhashtable_free_and_destroy()
831 	tbl = rht_dereference(ht->tbl, ht);  in rhashtable_free_and_destroy()
836 			for (pos = rht_dereference(tbl->buckets[i], ht),  in rhashtable_free_and_destroy()
838 					rht_dereference(pos->next, ht) : NULL;  in rhashtable_free_and_destroy()
842 					rht_dereference(pos->next, ht) : NULL)  in rhashtable_free_and_destroy()
843 				free_fn(rht_obj(ht, pos), arg);  in rhashtable_free_and_destroy()
848 	mutex_unlock(&ht->mutex);  in rhashtable_free_and_destroy()
852 void rhashtable_destroy(struct rhashtable *ht)  in rhashtable_destroy()  argument
854 	return rhashtable_free_and_destroy(ht, NULL, NULL);  in rhashtable_destroy()