include/linux/rhashtable.h

113 static inline void *rht_obj(const struct rhashtable *ht,
116 	return (char *)he - ht->p.head_offset;
125 static inline unsigned int rht_key_get_hash(struct rhashtable *ht,
131 	/* params must be equal to ht->p if it isn't constant. */
133 		hash = ht->p.hashfn(key, ht->key_len, hash_rnd);
144 		unsigned int key_len = ht->p.key_len;
156 	struct rhashtable *ht, const struct bucket_table *tbl,
159 	unsigned int hash = rht_key_get_hash(ht, key, params, tbl->hash_rnd);
165 	struct rhashtable *ht, const struct bucket_table *tbl,
168 	const char *ptr = rht_obj(ht, he);
172 							    ht->p.key_len,
174 	       rht_key_hashfn(ht, tbl, ptr + params.key_offset, params);
179  * @ht:		hash table
182 static inline bool rht_grow_above_75(const struct rhashtable *ht,
186 	return atomic_read(&ht->nelems) > (tbl->size / 4 * 3) &&
187 	       (!ht->p.max_size || tbl->size < ht->p.max_size);
192  * @ht:		hash table
195 static inline bool rht_shrink_below_30(const struct rhashtable *ht,
199 	return atomic_read(&ht->nelems) < (tbl->size * 3 / 10) &&
200 	       tbl->size > ht->p.min_size;
205  * @ht:		hash table
208 static inline bool rht_grow_above_100(const struct rhashtable *ht,
211 	return atomic_read(&ht->nelems) > tbl->size &&
212 		(!ht->p.max_size || tbl->size < ht->p.max_size);
217  * @ht:		hash table
220 static inline bool rht_grow_above_max(const struct rhashtable *ht,
223 	return atomic_read(&ht->nelems) >= ht->max_elems;
227 int lockdep_rht_mutex_is_held(struct rhashtable *ht);
230 static inline int lockdep_rht_mutex_is_held(struct rhashtable *ht)
242 void *rhashtable_insert_slow(struct rhashtable *ht, const void *key,
245 void rhashtable_walk_enter(struct rhashtable *ht,
259 void rhashtable_free_and_destroy(struct rhashtable *ht,
262 void rhashtable_destroy(struct rhashtable *ht);
269 	struct rhashtable *ht, struct bucket_table *tbl, unsigned int hash);
271 #define rht_dereference(p, ht) \
272 	rcu_dereference_protected(p, lockdep_rht_mutex_is_held(ht))
274 #define rht_dereference_rcu(p, ht) \
275 	rcu_dereference_check(p, lockdep_rht_mutex_is_held(ht))
301 	struct rhashtable *ht, struct bucket_table *tbl, unsigned int hash)
303 	return unlikely(tbl->nest) ? rht_bucket_nested_insert(ht, tbl, hash) :
582 	struct rhashtable *ht = arg->ht;
585 	return memcmp(ptr + ht->p.key_offset, arg->key, ht->p.key_len);
590 	struct rhashtable *ht, const void *key,
594 		.ht = ht,
602 	tbl = rht_dereference_rcu(ht->tbl, ht);
604 	hash = rht_key_hashfn(ht, tbl, key, params);
609 			    params.obj_cmpfn(&arg, rht_obj(ht, he)) :
610 			    rhashtable_compare(&arg, rht_obj(ht, he)))
622 	tbl = rht_dereference_rcu(tbl->future_tbl, ht);
631  * @ht:		hash table
643 	struct rhashtable *ht, const void *key,
646 	struct rhash_head *he = __rhashtable_lookup(ht, key, params);
648 	return he ? rht_obj(ht, he) : NULL;
653  * @ht:		hash table
666 	struct rhashtable *ht, const void *key,
672 	obj = rhashtable_lookup(ht, key, params);
696 	struct rhash_head *he = __rhashtable_lookup(&hlt->ht, key, params);
706 	struct rhashtable *ht, const void *key, struct rhash_head *obj,
710 		.ht = ht,
724 	tbl = rht_dereference_rcu(ht->tbl, ht);
725 	hash = rht_head_hashfn(ht, tbl, obj, params);
727 	bkt = rht_bucket_insert(ht, tbl, hash);
738 		return rhashtable_insert_slow(ht, key, obj);
748 		     params.obj_cmpfn(&arg, rht_obj(ht, head)) :
749 		     rhashtable_compare(&arg, rht_obj(ht, head)))) {
754 		data = rht_obj(ht, head);
779 	if (unlikely(rht_grow_above_max(ht, tbl)))
782 	if (unlikely(rht_grow_above_100(ht, tbl)))
796 	atomic_inc(&ht->nelems);
799 	if (rht_grow_above_75(ht, tbl))
800 		schedule_work(&ht->run_work);
815  * @ht:		hash table
829 	struct rhashtable *ht, struct rhash_head *obj,
834 	ret = __rhashtable_insert_fast(ht, NULL, obj, params, false);
861 	return PTR_ERR(__rhashtable_insert_fast(&hlt->ht, key, &list->rhead,
884 	const char *key = rht_obj(&hlt->ht, &list->rhead);
893  * @ht:		hash table
906 	struct rhashtable *ht, struct rhash_head *obj,
909 	const char *key = rht_obj(ht, obj);
912 	BUG_ON(ht->p.obj_hashfn);
914 	ret = __rhashtable_insert_fast(ht, key + ht->p.key_offset, obj, params,
924  * @ht:		hash table
933 	struct rhashtable *ht, struct rhash_head *obj,
936 	const char *key = rht_obj(ht, obj);
938 	BUG_ON(ht->p.obj_hashfn);
940 	return __rhashtable_insert_fast(ht, key + ht->p.key_offset, obj, params,
947  * @ht:		hash table
960 	struct rhashtable *ht, const void *key, struct rhash_head *obj,
965 	BUG_ON(!ht->p.obj_hashfn || !key);
967 	ret = __rhashtable_insert_fast(ht, key, obj, params, false);
976  * @ht:		hash table
986 	struct rhashtable *ht, const void *key, struct rhash_head *obj,
989 	BUG_ON(!ht->p.obj_hashfn || !key);
991 	return __rhashtable_insert_fast(ht, key, obj, params, false);
996 	struct rhashtable *ht, struct bucket_table *tbl,
1007 	hash = rht_head_hashfn(ht, tbl, obj, params);
1066 		atomic_dec(&ht->nelems);
1067 		if (unlikely(ht->p.automatic_shrinking &&
1068 			     rht_shrink_below_30(ht, tbl)))
1069 			schedule_work(&ht->run_work);
1078 	struct rhashtable *ht, struct rhash_head *obj,
1086 	tbl = rht_dereference_rcu(ht->tbl, ht);
1093 	while ((err = __rhashtable_remove_fast_one(ht, tbl, obj, params,
1095 	       (tbl = rht_dereference_rcu(tbl->future_tbl, ht)))
1105  * @ht:		hash table
1119 	struct rhashtable *ht, struct rhash_head *obj,
1122 	return __rhashtable_remove_fast(ht, obj, params, false);
1144 	return __rhashtable_remove_fast(&hlt->ht, &list->rhead, params, true);
1149 	struct rhashtable *ht, struct bucket_table *tbl,
1163 	hash = rht_head_hashfn(ht, tbl, obj_old, params);
1164 	if (hash != rht_head_hashfn(ht, tbl, obj_new, params))
1199  * @ht:		hash table
1212 	struct rhashtable *ht, struct rhash_head *obj_old,
1221 	tbl = rht_dereference_rcu(ht->tbl, ht);
1228 	while ((err = __rhashtable_replace_fast(ht, tbl, obj_old,
1230 	       (tbl = rht_dereference_rcu(tbl->future_tbl, ht)))
1262 	return rhashtable_walk_enter(&hlt->ht, iter);
1278 	return rhashtable_free_and_destroy(&hlt->ht, free_fn, arg);