Lines Matching full:ht
37 static u32 head_hashfn(struct rhashtable *ht, in head_hashfn() argument
41 return rht_head_hashfn(ht, tbl, he, ht->p); in head_hashfn()
45 #define ASSERT_RHT_MUTEX(HT) BUG_ON(!lockdep_rht_mutex_is_held(HT)) argument
47 int lockdep_rht_mutex_is_held(struct rhashtable *ht) in lockdep_rht_mutex_is_held() argument
49 return (debug_locks) ? lockdep_is_held(&ht->mutex) : 1; in lockdep_rht_mutex_is_held()
63 #define ASSERT_RHT_MUTEX(HT) argument
122 static union nested_table *nested_table_alloc(struct rhashtable *ht, in nested_table_alloc() argument
147 static struct bucket_table *nested_bucket_table_alloc(struct rhashtable *ht, in nested_bucket_table_alloc() argument
164 if (!nested_table_alloc(ht, (union nested_table __rcu **)tbl->buckets, in nested_bucket_table_alloc()
175 static struct bucket_table *bucket_table_alloc(struct rhashtable *ht, in bucket_table_alloc() argument
189 tbl = nested_bucket_table_alloc(ht, nbuckets, gfp); in bucket_table_alloc()
211 static struct bucket_table *rhashtable_last_table(struct rhashtable *ht, in rhashtable_last_table() argument
218 tbl = rht_dereference_rcu(tbl->future_tbl, ht); in rhashtable_last_table()
224 static int rhashtable_rehash_one(struct rhashtable *ht, in rhashtable_rehash_one() argument
228 struct bucket_table *old_tbl = rht_dereference(ht->tbl, ht); in rhashtable_rehash_one()
229 struct bucket_table *new_tbl = rhashtable_last_table(ht, old_tbl); in rhashtable_rehash_one()
255 new_hash = head_hashfn(ht, new_tbl, entry); in rhashtable_rehash_one()
276 static int rhashtable_rehash_chain(struct rhashtable *ht, in rhashtable_rehash_chain() argument
279 struct bucket_table *old_tbl = rht_dereference(ht->tbl, ht); in rhashtable_rehash_chain()
288 while (!(err = rhashtable_rehash_one(ht, bkt, old_hash))) in rhashtable_rehash_chain()
298 static int rhashtable_rehash_attach(struct rhashtable *ht, in rhashtable_rehash_attach() argument
315 static int rhashtable_rehash_table(struct rhashtable *ht) in rhashtable_rehash_table() argument
317 struct bucket_table *old_tbl = rht_dereference(ht->tbl, ht); in rhashtable_rehash_table()
323 new_tbl = rht_dereference(old_tbl->future_tbl, ht); in rhashtable_rehash_table()
328 err = rhashtable_rehash_chain(ht, old_hash); in rhashtable_rehash_table()
335 rcu_assign_pointer(ht->tbl, new_tbl); in rhashtable_rehash_table()
337 spin_lock(&ht->lock); in rhashtable_rehash_table()
349 spin_unlock(&ht->lock); in rhashtable_rehash_table()
351 return rht_dereference(new_tbl->future_tbl, ht) ? -EAGAIN : 0; in rhashtable_rehash_table()
354 static int rhashtable_rehash_alloc(struct rhashtable *ht, in rhashtable_rehash_alloc() argument
361 ASSERT_RHT_MUTEX(ht); in rhashtable_rehash_alloc()
363 new_tbl = bucket_table_alloc(ht, size, GFP_KERNEL); in rhashtable_rehash_alloc()
367 err = rhashtable_rehash_attach(ht, old_tbl, new_tbl); in rhashtable_rehash_alloc()
376 * @ht: the hash table to shrink
382 * ht->mutex.
390 static int rhashtable_shrink(struct rhashtable *ht) in rhashtable_shrink() argument
392 struct bucket_table *old_tbl = rht_dereference(ht->tbl, ht); in rhashtable_shrink()
393 unsigned int nelems = atomic_read(&ht->nelems); in rhashtable_shrink()
398 if (size < ht->p.min_size) in rhashtable_shrink()
399 size = ht->p.min_size; in rhashtable_shrink()
404 if (rht_dereference(old_tbl->future_tbl, ht)) in rhashtable_shrink()
407 return rhashtable_rehash_alloc(ht, old_tbl, size); in rhashtable_shrink()
412 struct rhashtable *ht; in rht_deferred_worker() local
416 ht = container_of(work, struct rhashtable, run_work); in rht_deferred_worker()
417 mutex_lock(&ht->mutex); in rht_deferred_worker()
419 tbl = rht_dereference(ht->tbl, ht); in rht_deferred_worker()
420 tbl = rhashtable_last_table(ht, tbl); in rht_deferred_worker()
422 if (rht_grow_above_75(ht, tbl)) in rht_deferred_worker()
423 err = rhashtable_rehash_alloc(ht, tbl, tbl->size * 2); in rht_deferred_worker()
424 else if (ht->p.automatic_shrinking && rht_shrink_below_30(ht, tbl)) in rht_deferred_worker()
425 err = rhashtable_shrink(ht); in rht_deferred_worker()
427 err = rhashtable_rehash_alloc(ht, tbl, tbl->size); in rht_deferred_worker()
432 nerr = rhashtable_rehash_table(ht); in rht_deferred_worker()
436 mutex_unlock(&ht->mutex); in rht_deferred_worker()
439 schedule_work(&ht->run_work); in rht_deferred_worker()
442 static int rhashtable_insert_rehash(struct rhashtable *ht, in rhashtable_insert_rehash() argument
450 old_tbl = rht_dereference_rcu(ht->tbl, ht); in rhashtable_insert_rehash()
456 if (rht_grow_above_75(ht, tbl)) in rhashtable_insert_rehash()
464 new_tbl = bucket_table_alloc(ht, size, GFP_ATOMIC | __GFP_NOWARN); in rhashtable_insert_rehash()
468 err = rhashtable_rehash_attach(ht, tbl, new_tbl); in rhashtable_insert_rehash()
474 schedule_work(&ht->run_work); in rhashtable_insert_rehash()
485 schedule_work(&ht->run_work); in rhashtable_insert_rehash()
490 static void *rhashtable_lookup_one(struct rhashtable *ht, in rhashtable_lookup_one() argument
496 .ht = ht, in rhashtable_lookup_one()
510 (ht->p.obj_cmpfn ? in rhashtable_lookup_one()
511 ht->p.obj_cmpfn(&arg, rht_obj(ht, head)) : in rhashtable_lookup_one()
512 rhashtable_compare(&arg, rht_obj(ht, head)))) { in rhashtable_lookup_one()
517 if (!ht->rhlist) in rhashtable_lookup_one()
518 return rht_obj(ht, head); in rhashtable_lookup_one()
542 struct rhashtable *ht, struct rhash_lock_head __rcu **bkt, in rhashtable_insert_one() argument
555 new_tbl = rht_dereference_rcu(tbl->future_tbl, ht); in rhashtable_insert_one()
562 if (unlikely(rht_grow_above_max(ht, tbl))) in rhashtable_insert_one()
565 if (unlikely(rht_grow_above_100(ht, tbl))) in rhashtable_insert_one()
571 if (ht->rhlist) { in rhashtable_insert_one()
583 atomic_inc(&ht->nelems); in rhashtable_insert_one()
584 if (rht_grow_above_75(ht, tbl)) in rhashtable_insert_one()
585 schedule_work(&ht->run_work); in rhashtable_insert_one()
590 static void *rhashtable_try_insert(struct rhashtable *ht, const void *key, in rhashtable_try_insert() argument
600 new_tbl = rcu_dereference(ht->tbl); in rhashtable_try_insert()
604 hash = rht_head_hashfn(ht, tbl, obj, ht->p); in rhashtable_try_insert()
609 bkt = rht_bucket_insert(ht, tbl, hash); in rhashtable_try_insert()
611 new_tbl = rht_dereference_rcu(tbl->future_tbl, ht); in rhashtable_try_insert()
615 data = rhashtable_lookup_one(ht, bkt, tbl, in rhashtable_try_insert()
617 new_tbl = rhashtable_insert_one(ht, bkt, tbl, in rhashtable_try_insert()
627 data = ERR_PTR(rhashtable_insert_rehash(ht, tbl) ?: in rhashtable_try_insert()
633 void *rhashtable_insert_slow(struct rhashtable *ht, const void *key, in rhashtable_insert_slow() argument
640 data = rhashtable_try_insert(ht, key, obj); in rhashtable_insert_slow()
650 * @ht: Table to walk over
669 void rhashtable_walk_enter(struct rhashtable *ht, struct rhashtable_iter *iter) in rhashtable_walk_enter() argument
671 iter->ht = ht; in rhashtable_walk_enter()
677 spin_lock(&ht->lock); in rhashtable_walk_enter()
679 rcu_dereference_protected(ht->tbl, lockdep_is_held(&ht->lock)); in rhashtable_walk_enter()
681 spin_unlock(&ht->lock); in rhashtable_walk_enter()
693 spin_lock(&iter->ht->lock); in rhashtable_walk_exit()
696 spin_unlock(&iter->ht->lock); in rhashtable_walk_exit()
721 struct rhashtable *ht = iter->ht; in rhashtable_walk_start_check() local
722 bool rhlist = ht->rhlist; in rhashtable_walk_start_check()
726 spin_lock(&ht->lock); in rhashtable_walk_start_check()
729 spin_unlock(&ht->lock); in rhashtable_walk_start_check()
734 iter->walker.tbl = rht_dereference_rcu(ht->tbl, ht); in rhashtable_walk_start_check()
795 struct rhashtable *ht = iter->ht; in __rhashtable_walk_find_next() local
797 bool rhlist = ht->rhlist; in __rhashtable_walk_find_next()
828 return rht_obj(ht, rhlist ? &list->rhead : p); in __rhashtable_walk_find_next()
839 iter->walker.tbl = rht_dereference_rcu(tbl->future_tbl, ht); in __rhashtable_walk_find_next()
866 struct rhashtable *ht = iter->ht; in rhashtable_walk_next() local
868 bool rhlist = ht->rhlist; in rhashtable_walk_next()
879 return rht_obj(ht, rhlist ? &list->rhead : p); in rhashtable_walk_next()
905 struct rhashtable *ht = iter->ht; in rhashtable_walk_peek() local
909 return rht_obj(ht, ht->rhlist ? &list->rhead : p); in rhashtable_walk_peek()
937 struct rhashtable *ht; in rhashtable_walk_stop() local
943 ht = iter->ht; in rhashtable_walk_stop()
945 spin_lock(&ht->lock); in rhashtable_walk_stop()
951 spin_unlock(&ht->lock); in rhashtable_walk_stop()
979 * @ht: hash table to be initialized
1019 int rhashtable_init(struct rhashtable *ht, in rhashtable_init() argument
1029 memset(ht, 0, sizeof(*ht)); in rhashtable_init()
1030 mutex_init(&ht->mutex); in rhashtable_init()
1031 spin_lock_init(&ht->lock); in rhashtable_init()
1032 memcpy(&ht->p, params, sizeof(*params)); in rhashtable_init()
1035 ht->p.min_size = roundup_pow_of_two(params->min_size); in rhashtable_init()
1038 ht->max_elems = 1u << 31; in rhashtable_init()
1041 ht->p.max_size = rounddown_pow_of_two(params->max_size); in rhashtable_init()
1042 if (ht->p.max_size < ht->max_elems / 2) in rhashtable_init()
1043 ht->max_elems = ht->p.max_size * 2; in rhashtable_init()
1046 ht->p.min_size = max_t(u16, ht->p.min_size, HASH_MIN_SIZE); in rhashtable_init()
1048 size = rounded_hashtable_size(&ht->p); 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()
1121 * @ht: the hash table to destroy
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()
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()
1219 struct rhashtable *ht, struct bucket_table *tbl, unsigned int hash) in rht_bucket_nested_insert() argument
1228 ntbl = nested_table_alloc(ht, &ntbl[index].table, in rht_bucket_nested_insert()
1235 ntbl = nested_table_alloc(ht, &ntbl[index].table, in rht_bucket_nested_insert()