3  * Resizable, Scalable, Concurrent Hash Table
32  * which is linked into as hash chain from the hash table - or one
33  * of two or more hash tables when the rhashtable is being resized.
36  * the hash bucket.  This allows us to be sure we've found the end
38  * The value stored in the hash bucket has BIT(0) used as a lock bit.
51  * The maximum (not average) chain length grows with the size of the hash
54  * The value of 16 is selected so that even if the hash table grew to
65  * struct bucket_table - Table of hash buckets
66  * @size: Number of hash buckets
69  * @hash_rnd: Random seed to fold into hash
74  * @buckets: size * hash buckets
91  * NULLS_MARKER() expects a hash value with the low
99  * We never store the NULLS_MARKER in the hash table
120 					    unsigned int hash)  in rht_bucket_index()  argument
122 	return hash & (tbl->size - 1);  in rht_bucket_index()
129 	unsigned int hash;  in rht_key_get_hash()  local
133 		hash = ht->p.hashfn(key, ht->key_len, hash_rnd);  in rht_key_get_hash()
138 			hash = params.hashfn(key, key_len, hash_rnd);  in rht_key_get_hash()
140 			hash = jhash(key, key_len, hash_rnd);  in rht_key_get_hash()
142 			hash = jhash2(key, key_len / sizeof(u32), hash_rnd);  in rht_key_get_hash()
147 			hash = params.hashfn(key, key_len, hash_rnd);  in rht_key_get_hash()
149 			hash = jhash(key, key_len, hash_rnd);  in rht_key_get_hash()
152 	return hash;  in rht_key_get_hash()
159 	unsigned int hash = rht_key_get_hash(ht, key, params, tbl->hash_rnd);  in rht_key_hashfn()  local
161 	return rht_bucket_index(tbl, hash);  in rht_key_hashfn()
179  * @ht:		hash table
192  * @ht:		hash table
205  * @ht:		hash table
217  * @ht:		hash table
228 int lockdep_rht_bucket_is_held(const struct bucket_table *tbl, u32 hash);
236 					     u32 hash)  in lockdep_rht_bucket_is_held()  argument
265 	const struct bucket_table *tbl, unsigned int hash);
267 	const struct bucket_table *tbl, unsigned int hash);
269 	struct rhashtable *ht, struct bucket_table *tbl, unsigned int hash);
277 #define rht_dereference_bucket(p, tbl, hash) \  argument
278 	rcu_dereference_protected(p, lockdep_rht_bucket_is_held(tbl, hash))
280 #define rht_dereference_bucket_rcu(p, tbl, hash) \  argument
281 	rcu_dereference_check(p, lockdep_rht_bucket_is_held(tbl, hash))
287 	const struct bucket_table *tbl, unsigned int hash)  in rht_bucket()  argument
289 	return unlikely(tbl->nest) ? rht_bucket_nested(tbl, hash) :  in rht_bucket()
290 				     &tbl->buckets[hash];  in rht_bucket()
294 	struct bucket_table *tbl, unsigned int hash)  in rht_bucket_var()  argument
296 	return unlikely(tbl->nest) ? __rht_bucket_nested(tbl, hash) :  in rht_bucket_var()
297 				     &tbl->buckets[hash];  in rht_bucket_var()
301 	struct rhashtable *ht, struct bucket_table *tbl, unsigned int hash)  in rht_bucket_insert()  argument
303 	return unlikely(tbl->nest) ? rht_bucket_nested_insert(ht, tbl, hash) :  in rht_bucket_insert()
304 				     &tbl->buckets[hash];  in rht_bucket_insert()
313  * A nested hash table might not have a bucket pointer.  In that case
375 	unsigned int hash)  in rht_ptr()  argument
377 	return __rht_ptr(rht_dereference_bucket(*bkt, tbl, hash), bkt);  in rht_ptr()
408  * rht_for_each_from - iterate over hash chain from given head
412  * @hash:	the hash value / bucket index
414 #define rht_for_each_from(pos, head, tbl, hash) \  argument
417 	     pos = rht_dereference_bucket((pos)->next, tbl, hash))
420  * rht_for_each - iterate over hash chain
423  * @hash:	the hash value / bucket index
425 #define rht_for_each(pos, tbl, hash) \  argument
426 	rht_for_each_from(pos, rht_ptr(rht_bucket(tbl, hash), tbl, hash),  \
427 			  tbl, hash)
430  * rht_for_each_entry_from - iterate over hash chain from given head
435  * @hash:	the hash value / bucket index
438 #define rht_for_each_entry_from(tpos, pos, head, tbl, hash, member)	\  argument
441 	     pos = rht_dereference_bucket((pos)->next, tbl, hash))
444  * rht_for_each_entry - iterate over hash chain of given type
448  * @hash:	the hash value / bucket index
451 #define rht_for_each_entry(tpos, pos, tbl, hash, member)		\  argument
453 				rht_ptr(rht_bucket(tbl, hash), tbl, hash), \
454 				tbl, hash, member)
457  * rht_for_each_entry_safe - safely iterate over hash chain of given type
462  * @hash:	the hash value / bucket index
465  * This hash chain list-traversal primitive allows for the looped code to
468 #define rht_for_each_entry_safe(tpos, pos, next, tbl, hash, member)	      \  argument
469 	for (pos = rht_ptr(rht_bucket(tbl, hash), tbl, hash),		      \
471 		       rht_dereference_bucket(pos->next, tbl, hash) : NULL;   \
475 		       rht_dereference_bucket(pos->next, tbl, hash) : NULL)
478  * rht_for_each_rcu_from - iterate over rcu hash chain from given head
482  * @hash:	the hash value / bucket index
484  * This hash chain list-traversal primitive may safely run concurrently with
488 #define rht_for_each_rcu_from(pos, head, tbl, hash)			\  argument
495  * rht_for_each_rcu - iterate over rcu hash chain
498  * @hash:	the hash value / bucket index
500  * This hash chain list-traversal primitive may safely run concurrently with
504 #define rht_for_each_rcu(pos, tbl, hash)			\  argument
506 	     pos = rht_ptr_rcu(rht_bucket(tbl, hash));		\
511  * rht_for_each_entry_rcu_from - iterated over rcu hash chain from given head
516  * @hash:	the hash value / bucket index
519  * This hash chain list-traversal primitive may safely run concurrently with
523 #define rht_for_each_entry_rcu_from(tpos, pos, head, tbl, hash, member) \  argument
527 	     pos = rht_dereference_bucket_rcu(pos->next, tbl, hash))
530  * rht_for_each_entry_rcu - iterate over rcu hash chain of given type
534  * @hash:	the hash value / bucket index
537  * This hash chain list-traversal primitive may safely run concurrently with
541 #define rht_for_each_entry_rcu(tpos, pos, tbl, hash, member)		   \  argument
543 				    rht_ptr_rcu(rht_bucket(tbl, hash)),	   \
544 				    tbl, hash, member)
547  * rhl_for_each_rcu - iterate over rcu hash table list
551  * This hash chain list-traversal primitive should be used on the
558  * rhl_for_each_entry_rcu - iterate over rcu hash table list of given type
564  * This hash chain list-traversal primitive should be used on the
592 	unsigned int hash;  in __rhashtable_lookup()  local
596 	hash = rht_key_hashfn(ht, tbl, key, params);  in __rhashtable_lookup()
597 	bkt = rht_bucket(tbl, hash);  in __rhashtable_lookup()
599 		rht_for_each_rcu_from(he, rht_ptr_rcu(bkt), tbl, hash) {  in __rhashtable_lookup()
606 		/* An object might have been moved to a different hash chain,  in __rhashtable_lookup()
622  * rhashtable_lookup - search hash table
623  * @ht:		hash table
625  * @params:	hash table parameters
627  * Computes the hash value for the key and traverses the bucket chain looking
644  * rhashtable_lookup_fast - search hash table, without RCU read lock
645  * @ht:		hash table
647  * @params:	hash table parameters
649  * Computes the hash value for the key and traverses the bucket chain looking
671  * rhltable_lookup - search hash list table
672  * @hlt:	hash table
674  * @params:	hash table parameters
676  * Computes the hash value for the key and traverses the bucket chain looking
709 	unsigned int hash;  in __rhashtable_insert_fast()  local
716 	hash = rht_head_hashfn(ht, tbl, obj, params);  in __rhashtable_insert_fast()
718 	bkt = rht_bucket_insert(ht, tbl, hash);  in __rhashtable_insert_fast()
732 	rht_for_each_from(head, rht_ptr(bkt, tbl, hash), tbl, hash) {  in __rhashtable_insert_fast()
755 		head = rht_dereference_bucket(head->next, tbl, hash);  in __rhashtable_insert_fast()
777 	head = rht_ptr(bkt, tbl, hash);  in __rhashtable_insert_fast()
805  * rhashtable_insert_fast - insert object into hash table
806  * @ht:		hash table
807  * @obj:	pointer to hash head inside object
808  * @params:	hash table parameters
833  * rhltable_insert_key - insert object into hash list table
834  * @hlt:	hash list table
836  * @list:	pointer to hash list head inside object
837  * @params:	hash table parameters
857  * rhltable_insert - insert object into hash list table
858  * @hlt:	hash list table
859  * @list:	pointer to hash list head inside object
860  * @params:	hash table parameters
883  * rhashtable_lookup_insert_fast - lookup and insert object into hash table
884  * @ht:		hash table
885  * @obj:	pointer to hash head inside object
886  * @params:	hash table parameters
888  * This lookup function may only be used for fixed key hash table (key_len
914  * rhashtable_lookup_get_insert_fast - lookup and insert object into hash table
915  * @ht:		hash table
916  * @obj:	pointer to hash head inside object
917  * @params:	hash table parameters
936  * rhashtable_lookup_insert_key - search and insert object to hash table
938  * @ht:		hash table
940  * @obj:	pointer to hash head inside object
941  * @params:	hash table parameters
966  * rhashtable_lookup_get_insert_key - lookup and insert object into hash table
967  * @ht:		hash table
969  * @obj:	pointer to hash head inside object
970  * @params:	hash table parameters
994 	unsigned int hash;  in __rhashtable_remove_fast_one()  local
997 	hash = rht_head_hashfn(ht, tbl, obj, params);  in __rhashtable_remove_fast_one()
998 	bkt = rht_bucket_var(tbl, hash);  in __rhashtable_remove_fast_one()
1004 	rht_for_each_from(he, rht_ptr(bkt, tbl, hash), tbl, hash) {  in __rhashtable_remove_fast_one()
1020 							      tbl, hash);  in __rhashtable_remove_fast_one()
1026 			list = rht_dereference_bucket(list->next, tbl, hash);  in __rhashtable_remove_fast_one()
1032 		obj = rht_dereference_bucket(obj->next, tbl, hash);  in __rhashtable_remove_fast_one()
1036 			list = rht_dereference_bucket(list->next, tbl, hash);  in __rhashtable_remove_fast_one()
1094  * rhashtable_remove_fast - remove object from hash table
1095  * @ht:		hash table
1096  * @obj:	pointer to hash head inside object
1097  * @params:	hash table parameters
1099  * Since the hash chain is single linked, the removal operation needs to
1101  * considerable slow if the hash table is not correctly sized.
1116  * rhltable_remove - remove object from hash list table
1117  * @hlt:	hash list table
1118  * @list:	pointer to hash list head inside object
1119  * @params:	hash table parameters
1121  * Since the hash chain is single linked, the removal operation needs to
1123  * considerable slow if the hash table is not correctly sized.
1146 	unsigned int hash;  in __rhashtable_replace_fast()  local
1149 	/* Minimally, the old and new objects must have same hash  in __rhashtable_replace_fast()
1152 	hash = rht_head_hashfn(ht, tbl, obj_old, params);  in __rhashtable_replace_fast()
1153 	if (hash != rht_head_hashfn(ht, tbl, obj_new, params))  in __rhashtable_replace_fast()
1156 	bkt = rht_bucket_var(tbl, hash);  in __rhashtable_replace_fast()
1163 	rht_for_each_from(he, rht_ptr(bkt, tbl, hash), tbl, hash) {  in __rhashtable_replace_fast()
1187  * rhashtable_replace_fast - replace an object in hash table
1188  * @ht:		hash table
1189  * @obj_old:	pointer to hash head inside object being replaced
1190  * @obj_new:	pointer to hash head inside object which is new
1191  * @params:	hash table parameters
1193  * Replacing an object doesn't affect the number of elements in the hash table
1198  * -EINVAL if hash is not the same for the old and new objects.
1230  * @iter:	Hash table Iterator
1232  * This function prepares a hash table walk.
1240  * structure outside the hash table.
1255  * rhltable_free_and_destroy - free elements and destroy hash list table
1256  * @hlt:	the hash list table to destroy