36 		       const struct bucket_table *tbl,  in head_hashfn()  argument
39 	return rht_head_hashfn(ht, tbl, he, ht->p);  in head_hashfn()
51 int lockdep_rht_bucket_is_held(const struct bucket_table *tbl, u32 hash)  in lockdep_rht_bucket_is_held()  argument
53 	spinlock_t *lock = rht_bucket_lock(tbl, hash);  in lockdep_rht_bucket_is_held()
63 static int alloc_bucket_locks(struct rhashtable *ht, struct bucket_table *tbl,  in alloc_bucket_locks()  argument
77 	size = min_t(unsigned int, size, tbl->size >> 1);  in alloc_bucket_locks()
83 			tbl->locks = vmalloc(size * sizeof(spinlock_t));  in alloc_bucket_locks()
86 		tbl->locks = kmalloc_array(size, sizeof(spinlock_t),  in alloc_bucket_locks()
88 		if (!tbl->locks)  in alloc_bucket_locks()
91 			spin_lock_init(&tbl->locks[i]);  in alloc_bucket_locks()
93 	tbl->locks_mask = size - 1;  in alloc_bucket_locks()
98 static void bucket_table_free(const struct bucket_table *tbl)  in bucket_table_free()  argument
100 	if (tbl)  in bucket_table_free()
101 		kvfree(tbl->locks);  in bucket_table_free()
103 	kvfree(tbl);  in bucket_table_free()
115 	struct bucket_table *tbl = NULL;  in bucket_table_alloc()  local
119 	size = sizeof(*tbl) + nbuckets * sizeof(tbl->buckets[0]);  in bucket_table_alloc()
122 		tbl = kzalloc(size, gfp | __GFP_NOWARN | __GFP_NORETRY);  in bucket_table_alloc()
123 	if (tbl == NULL && gfp == GFP_KERNEL)  in bucket_table_alloc()
124 		tbl = vzalloc(size);  in bucket_table_alloc()
125 	if (tbl == NULL)  in bucket_table_alloc()
128 	tbl->size = nbuckets;  in bucket_table_alloc()
130 	if (alloc_bucket_locks(ht, tbl, gfp) < 0) {  in bucket_table_alloc()
131 		bucket_table_free(tbl);  in bucket_table_alloc()
135 	INIT_LIST_HEAD(&tbl->walkers);  in bucket_table_alloc()
137 	get_random_bytes(&tbl->hash_rnd, sizeof(tbl->hash_rnd));  in bucket_table_alloc()
140 		INIT_RHT_NULLS_HEAD(tbl->buckets[i], ht, i);  in bucket_table_alloc()
142 	return tbl;  in bucket_table_alloc()
146 						  struct bucket_table *tbl)  in rhashtable_last_table()  argument
151 		new_tbl = tbl;  in rhashtable_last_table()
152 		tbl = rht_dereference_rcu(tbl->future_tbl, ht);  in rhashtable_last_table()
153 	} while (tbl);  in rhashtable_last_table()
160 	struct bucket_table *old_tbl = rht_dereference(ht->tbl, ht);  in rhashtable_rehash_one()
204 	struct bucket_table *old_tbl = rht_dereference(ht->tbl, ht);  in rhashtable_rehash_chain()
244 	struct bucket_table *old_tbl = rht_dereference(ht->tbl, ht);  in rhashtable_rehash_table()
257 	rcu_assign_pointer(ht->tbl, new_tbl);  in rhashtable_rehash_table()
261 		walker->tbl = NULL;  in rhashtable_rehash_table()
290 	struct bucket_table *new_tbl, *old_tbl = rht_dereference(ht->tbl, ht);  in rhashtable_expand()
326 	struct bucket_table *new_tbl, *old_tbl = rht_dereference(ht->tbl, ht);  in rhashtable_shrink()
356 	struct bucket_table *tbl;  in rht_deferred_worker()  local
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()
367 	else if (ht->p.automatic_shrinking && rht_shrink_below_30(ht, tbl))  in rht_deferred_worker()
379 					struct bucket_table *tbl,  in rhashtable_check_elasticity()  argument
385 	rht_for_each(head, tbl, hash)  in rhashtable_check_elasticity()
393 			     struct bucket_table *tbl)  in rhashtable_insert_rehash()  argument
400 	old_tbl = rht_dereference_rcu(ht->tbl, ht);  in rhashtable_insert_rehash()
402 	size = tbl->size;  in rhashtable_insert_rehash()
406 	if (rht_grow_above_75(ht, tbl))  in rhashtable_insert_rehash()
409 	else if (old_tbl != tbl)  in rhashtable_insert_rehash()
418 	err = rhashtable_rehash_attach(ht, tbl, new_tbl);  in rhashtable_insert_rehash()
430 	if (likely(rcu_dereference_raw(tbl->future_tbl)))  in rhashtable_insert_rehash()
444 					    struct bucket_table *tbl)  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()
452 	spin_lock_nested(rht_bucket_lock(tbl, hash), SINGLE_DEPTH_NESTING);  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()
469 	head = rht_dereference_bucket(tbl->buckets[hash], tbl, hash);  in rhashtable_insert_slow()
473 	rcu_assign_pointer(tbl->buckets[hash], obj);  in rhashtable_insert_slow()
478 	spin_unlock(rht_bucket_lock(tbl, hash));  in rhashtable_insert_slow()
483 		return tbl;  in rhashtable_insert_slow()
522 	iter->walker->tbl =  in rhashtable_walk_init()
523 		rcu_dereference_protected(ht->tbl, lockdep_is_held(&ht->lock));  in rhashtable_walk_init()
524 	list_add(&iter->walker->list, &iter->walker->tbl->walkers);  in rhashtable_walk_init()
540 	if (iter->walker->tbl)  in rhashtable_walk_exit()
569 	if (iter->walker->tbl)  in rhashtable_walk_start()
573 	if (!iter->walker->tbl) {  in rhashtable_walk_start()
574 		iter->walker->tbl = rht_dereference_rcu(ht->tbl, ht);  in rhashtable_walk_start()
596 	struct bucket_table *tbl = iter->walker->tbl;  in rhashtable_walk_next()  local
601 		p = rht_dereference_bucket_rcu(p->next, tbl, iter->slot);  in rhashtable_walk_next()
605 	for (; iter->slot < tbl->size; iter->slot++) {  in rhashtable_walk_next()
608 		rht_for_each_rcu(p, tbl, iter->slot) {  in rhashtable_walk_next()
629 	iter->walker->tbl = rht_dereference_rcu(tbl->future_tbl, ht);  in rhashtable_walk_next()
630 	if (iter->walker->tbl) {  in rhashtable_walk_next()
650 	struct bucket_table *tbl = iter->walker->tbl;  in rhashtable_walk_stop()  local
652 	if (!tbl)  in rhashtable_walk_stop()
658 	if (tbl->rehash < tbl->size)  in rhashtable_walk_stop()
659 		list_add(&iter->walker->list, &tbl->walkers);  in rhashtable_walk_stop()
661 		iter->walker->tbl = NULL;  in rhashtable_walk_stop()
728 	struct bucket_table *tbl;  in rhashtable_init()  local
792 	tbl = bucket_table_alloc(ht, size, GFP_KERNEL);  in rhashtable_init()
793 	if (tbl == NULL)  in rhashtable_init()
798 	RCU_INIT_POINTER(ht->tbl, tbl);  in rhashtable_init()
825 	const struct bucket_table *tbl;  in rhashtable_free_and_destroy()  local
831 	tbl = rht_dereference(ht->tbl, ht);  in rhashtable_free_and_destroy()
833 		for (i = 0; i < tbl->size; i++) {  in rhashtable_free_and_destroy()
836 			for (pos = rht_dereference(tbl->buckets[i], ht),  in rhashtable_free_and_destroy()
847 	bucket_table_free(tbl);  in rhashtable_free_and_destroy()