Lines Matching refs: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()
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()
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()
254 new_hash = head_hashfn(ht, new_tbl, entry); in rhashtable_rehash_one()
274 static int rhashtable_rehash_chain(struct rhashtable *ht, in rhashtable_rehash_chain() argument
277 struct bucket_table *old_tbl = rht_dereference(ht->tbl, ht); in rhashtable_rehash_chain()
285 while (!(err = rhashtable_rehash_one(ht, bkt, old_hash))) in rhashtable_rehash_chain()
295 static int rhashtable_rehash_attach(struct rhashtable *ht, in rhashtable_rehash_attach() argument
312 static int rhashtable_rehash_table(struct rhashtable *ht) in rhashtable_rehash_table() argument
314 struct bucket_table *old_tbl = rht_dereference(ht->tbl, ht); in rhashtable_rehash_table()
320 new_tbl = rht_dereference(old_tbl->future_tbl, ht); in rhashtable_rehash_table()
325 err = rhashtable_rehash_chain(ht, old_hash); in rhashtable_rehash_table()
332 rcu_assign_pointer(ht->tbl, new_tbl); in rhashtable_rehash_table()
334 spin_lock(&ht->lock); in rhashtable_rehash_table()
346 spin_unlock(&ht->lock); in rhashtable_rehash_table()
348 return rht_dereference(new_tbl->future_tbl, ht) ? -EAGAIN : 0; in rhashtable_rehash_table()
351 static int rhashtable_rehash_alloc(struct rhashtable *ht, in rhashtable_rehash_alloc() argument
358 ASSERT_RHT_MUTEX(ht); in rhashtable_rehash_alloc()
360 new_tbl = bucket_table_alloc(ht, size, GFP_KERNEL); in rhashtable_rehash_alloc()
364 err = rhashtable_rehash_attach(ht, old_tbl, new_tbl); in rhashtable_rehash_alloc()
387 static int rhashtable_shrink(struct rhashtable *ht) in rhashtable_shrink() argument
389 struct bucket_table *old_tbl = rht_dereference(ht->tbl, ht); in rhashtable_shrink()
390 unsigned int nelems = atomic_read(&ht->nelems); in rhashtable_shrink()
395 if (size < ht->p.min_size) in rhashtable_shrink()
396 size = ht->p.min_size; in rhashtable_shrink()
401 if (rht_dereference(old_tbl->future_tbl, ht)) in rhashtable_shrink()
404 return rhashtable_rehash_alloc(ht, old_tbl, size); in rhashtable_shrink()
409 struct rhashtable *ht; in rht_deferred_worker() local
413 ht = container_of(work, struct rhashtable, run_work); in rht_deferred_worker()
414 mutex_lock(&ht->mutex); in rht_deferred_worker()
416 tbl = rht_dereference(ht->tbl, ht); in rht_deferred_worker()
417 tbl = rhashtable_last_table(ht, tbl); in rht_deferred_worker()
419 if (rht_grow_above_75(ht, tbl)) in rht_deferred_worker()
420 err = rhashtable_rehash_alloc(ht, tbl, tbl->size * 2); in rht_deferred_worker()
421 else if (ht->p.automatic_shrinking && rht_shrink_below_30(ht, tbl)) in rht_deferred_worker()
422 err = rhashtable_shrink(ht); in rht_deferred_worker()
424 err = rhashtable_rehash_alloc(ht, tbl, tbl->size); in rht_deferred_worker()
429 nerr = rhashtable_rehash_table(ht); in rht_deferred_worker()
433 mutex_unlock(&ht->mutex); in rht_deferred_worker()
436 schedule_work(&ht->run_work); in rht_deferred_worker()
439 static int rhashtable_insert_rehash(struct rhashtable *ht, in rhashtable_insert_rehash() argument
447 old_tbl = rht_dereference_rcu(ht->tbl, ht); in rhashtable_insert_rehash()
453 if (rht_grow_above_75(ht, tbl)) in rhashtable_insert_rehash()
461 new_tbl = bucket_table_alloc(ht, size, GFP_ATOMIC | __GFP_NOWARN); in rhashtable_insert_rehash()
465 err = rhashtable_rehash_attach(ht, tbl, new_tbl); in rhashtable_insert_rehash()
471 schedule_work(&ht->run_work); in rhashtable_insert_rehash()
482 schedule_work(&ht->run_work); in rhashtable_insert_rehash()
487 static void *rhashtable_lookup_one(struct rhashtable *ht, in rhashtable_lookup_one() argument
493 .ht = ht, in rhashtable_lookup_one()
507 (ht->p.obj_cmpfn ? in rhashtable_lookup_one()
508 ht->p.obj_cmpfn(&arg, rht_obj(ht, head)) : in rhashtable_lookup_one()
509 rhashtable_compare(&arg, rht_obj(ht, head)))) { in rhashtable_lookup_one()
514 if (!ht->rhlist) in rhashtable_lookup_one()
515 return rht_obj(ht, head); in rhashtable_lookup_one()
539 struct rhashtable *ht, struct rhash_lock_head __rcu **bkt, in rhashtable_insert_one() argument
552 new_tbl = rht_dereference_rcu(tbl->future_tbl, ht); in rhashtable_insert_one()
559 if (unlikely(rht_grow_above_max(ht, tbl))) in rhashtable_insert_one()
562 if (unlikely(rht_grow_above_100(ht, tbl))) in rhashtable_insert_one()
568 if (ht->rhlist) { in rhashtable_insert_one()
580 atomic_inc(&ht->nelems); in rhashtable_insert_one()
581 if (rht_grow_above_75(ht, tbl)) in rhashtable_insert_one()
582 schedule_work(&ht->run_work); in rhashtable_insert_one()
587 static void *rhashtable_try_insert(struct rhashtable *ht, const void *key, in rhashtable_try_insert() argument
596 new_tbl = rcu_dereference(ht->tbl); in rhashtable_try_insert()
600 hash = rht_head_hashfn(ht, tbl, obj, ht->p); in rhashtable_try_insert()
605 bkt = rht_bucket_insert(ht, tbl, hash); in rhashtable_try_insert()
607 new_tbl = rht_dereference_rcu(tbl->future_tbl, ht); in rhashtable_try_insert()
611 data = rhashtable_lookup_one(ht, bkt, tbl, in rhashtable_try_insert()
613 new_tbl = rhashtable_insert_one(ht, bkt, tbl, in rhashtable_try_insert()
623 data = ERR_PTR(rhashtable_insert_rehash(ht, tbl) ?: in rhashtable_try_insert()
629 void *rhashtable_insert_slow(struct rhashtable *ht, const void *key, in rhashtable_insert_slow() argument
636 data = rhashtable_try_insert(ht, key, obj); in rhashtable_insert_slow()
665 void rhashtable_walk_enter(struct rhashtable *ht, struct rhashtable_iter *iter) in rhashtable_walk_enter() argument
667 iter->ht = ht; in rhashtable_walk_enter()
673 spin_lock(&ht->lock); in rhashtable_walk_enter()
675 rcu_dereference_protected(ht->tbl, lockdep_is_held(&ht->lock)); in rhashtable_walk_enter()
677 spin_unlock(&ht->lock); in rhashtable_walk_enter()
689 spin_lock(&iter->ht->lock); in rhashtable_walk_exit()
692 spin_unlock(&iter->ht->lock); in rhashtable_walk_exit()
717 struct rhashtable *ht = iter->ht; in rhashtable_walk_start_check() local
718 bool rhlist = ht->rhlist; in rhashtable_walk_start_check()
722 spin_lock(&ht->lock); in rhashtable_walk_start_check()
725 spin_unlock(&ht->lock); in rhashtable_walk_start_check()
730 iter->walker.tbl = rht_dereference_rcu(ht->tbl, ht); in rhashtable_walk_start_check()
791 struct rhashtable *ht = iter->ht; in __rhashtable_walk_find_next() local
793 bool rhlist = ht->rhlist; in __rhashtable_walk_find_next()
824 return rht_obj(ht, rhlist ? &list->rhead : p); in __rhashtable_walk_find_next()
835 iter->walker.tbl = rht_dereference_rcu(tbl->future_tbl, ht); in __rhashtable_walk_find_next()
862 struct rhashtable *ht = iter->ht; in rhashtable_walk_next() local
864 bool rhlist = ht->rhlist; in rhashtable_walk_next()
875 return rht_obj(ht, rhlist ? &list->rhead : p); in rhashtable_walk_next()
901 struct rhashtable *ht = iter->ht; in rhashtable_walk_peek() local
905 return rht_obj(ht, ht->rhlist ? &list->rhead : p); in rhashtable_walk_peek()
933 struct rhashtable *ht; in rhashtable_walk_stop() local
939 ht = iter->ht; in rhashtable_walk_stop()
941 spin_lock(&ht->lock); in rhashtable_walk_stop()
947 spin_unlock(&ht->lock); in rhashtable_walk_stop()
1015 int rhashtable_init(struct rhashtable *ht, in rhashtable_init() argument
1025 memset(ht, 0, sizeof(*ht)); in rhashtable_init()
1026 mutex_init(&ht->mutex); in rhashtable_init()
1027 spin_lock_init(&ht->lock); in rhashtable_init()
1028 memcpy(&ht->p, params, sizeof(*params)); in rhashtable_init()
1031 ht->p.min_size = roundup_pow_of_two(params->min_size); in rhashtable_init()
1034 ht->max_elems = 1u << 31; in rhashtable_init()
1037 ht->p.max_size = rounddown_pow_of_two(params->max_size); in rhashtable_init()
1038 if (ht->p.max_size < ht->max_elems / 2) in rhashtable_init()
1039 ht->max_elems = ht->p.max_size * 2; in rhashtable_init()
1042 ht->p.min_size = max_t(u16, ht->p.min_size, HASH_MIN_SIZE); in rhashtable_init()
1044 size = rounded_hashtable_size(&ht->p); in rhashtable_init()
1046 ht->key_len = ht->p.key_len; in rhashtable_init()
1048 ht->p.hashfn = jhash; in rhashtable_init()
1050 if (!(ht->key_len & (sizeof(u32) - 1))) { in rhashtable_init()
1051 ht->key_len /= sizeof(u32); in rhashtable_init()
1052 ht->p.hashfn = rhashtable_jhash2; in rhashtable_init()
1061 tbl = bucket_table_alloc(ht, size, GFP_KERNEL); in rhashtable_init()
1063 size = max_t(u16, ht->p.min_size, HASH_MIN_SIZE); in rhashtable_init()
1064 tbl = bucket_table_alloc(ht, size, GFP_KERNEL | __GFP_NOFAIL); in rhashtable_init()
1067 atomic_set(&ht->nelems, 0); in rhashtable_init()
1069 RCU_INIT_POINTER(ht->tbl, tbl); in rhashtable_init()
1071 INIT_WORK(&ht->run_work, rht_deferred_worker); in rhashtable_init()
1090 err = rhashtable_init(&hlt->ht, params); in rhltable_init()
1091 hlt->ht.rhlist = true; in rhltable_init()
1096 static void rhashtable_free_one(struct rhashtable *ht, struct rhash_head *obj, in rhashtable_free_one() argument
1102 if (!ht->rhlist) { in rhashtable_free_one()
1103 free_fn(rht_obj(ht, obj), arg); in rhashtable_free_one()
1110 list = rht_dereference(list->next, ht); in rhashtable_free_one()
1111 free_fn(rht_obj(ht, obj), arg); in rhashtable_free_one()
1130 void rhashtable_free_and_destroy(struct rhashtable *ht, in rhashtable_free_and_destroy() argument
1137 cancel_work_sync(&ht->run_work); in rhashtable_free_and_destroy()
1139 mutex_lock(&ht->mutex); in rhashtable_free_and_destroy()
1140 tbl = rht_dereference(ht->tbl, ht); in rhashtable_free_and_destroy()
1149 rht_dereference(pos->next, ht) : NULL; in rhashtable_free_and_destroy()
1153 rht_dereference(pos->next, ht) : NULL) in rhashtable_free_and_destroy()
1154 rhashtable_free_one(ht, pos, free_fn, arg); in rhashtable_free_and_destroy()
1158 next_tbl = rht_dereference(tbl->future_tbl, ht); in rhashtable_free_and_destroy()
1164 mutex_unlock(&ht->mutex); in rhashtable_free_and_destroy()
1168 void rhashtable_destroy(struct rhashtable *ht) in rhashtable_destroy() argument
1170 return rhashtable_free_and_destroy(ht, NULL, NULL); in rhashtable_destroy()
1215 struct rhashtable *ht, struct bucket_table *tbl, unsigned int hash) in rht_bucket_nested_insert() argument
1224 ntbl = nested_table_alloc(ht, &ntbl[index].table, in rht_bucket_nested_insert()
1231 ntbl = nested_table_alloc(ht, &ntbl[index].table, in rht_bucket_nested_insert()