summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--include/linux/rhashtable.h6
-rw-r--r--lib/rhashtable.c55
2 files changed, 28 insertions, 33 deletions
diff --git a/include/linux/rhashtable.h b/include/linux/rhashtable.h
index 5ef8ea551556..c93ff8ac474a 100644
--- a/include/linux/rhashtable.h
+++ b/include/linux/rhashtable.h
@@ -50,6 +50,7 @@ struct rhash_head {
* struct bucket_table - Table of hash buckets
* @size: Number of hash buckets
* @hash_rnd: Random seed to fold into hash
+ * @shift: Current size (1 << shift)
* @locks_mask: Mask to apply before accessing locks[]
* @locks: Array of spinlocks protecting individual buckets
* @buckets: size * hash buckets
@@ -57,6 +58,7 @@ struct rhash_head {
struct bucket_table {
size_t size;
u32 hash_rnd;
+ u32 shift;
unsigned int locks_mask;
spinlock_t *locks;
@@ -99,7 +101,6 @@ struct rhashtable_params {
* @tbl: Bucket table
* @future_tbl: Table under construction during expansion/shrinking
* @nelems: Number of elements in table
- * @shift: Current size (1 << shift)
* @p: Configuration parameters
* @run_work: Deferred worker to expand/shrink asynchronously
* @mutex: Mutex to protect current/future table swapping
@@ -110,12 +111,11 @@ struct rhashtable {
struct bucket_table __rcu *tbl;
struct bucket_table __rcu *future_tbl;
atomic_t nelems;
- atomic_t shift;
+ bool being_destroyed;
struct rhashtable_params p;
struct work_struct run_work;
struct mutex mutex;
struct list_head walkers;
- bool being_destroyed;
};
/**
diff --git a/lib/rhashtable.c b/lib/rhashtable.c
index 68210cc2bab8..adea791ea3ab 100644
--- a/lib/rhashtable.c
+++ b/lib/rhashtable.c
@@ -147,7 +147,7 @@ static void bucket_table_free(const struct bucket_table *tbl)
}
static struct bucket_table *bucket_table_alloc(struct rhashtable *ht,
- size_t nbuckets)
+ size_t nbuckets, u32 hash_rnd)
{
struct bucket_table *tbl = NULL;
size_t size;
@@ -162,6 +162,8 @@ static struct bucket_table *bucket_table_alloc(struct rhashtable *ht,
return NULL;
tbl->size = nbuckets;
+ tbl->shift = ilog2(nbuckets);
+ tbl->hash_rnd = hash_rnd;
if (alloc_bucket_locks(ht, tbl) < 0) {
bucket_table_free(tbl);
@@ -177,25 +179,27 @@ static struct bucket_table *bucket_table_alloc(struct rhashtable *ht,
/**
* rht_grow_above_75 - returns true if nelems > 0.75 * table-size
* @ht: hash table
- * @new_size: new table size
+ * @tbl: current table
*/
-static bool rht_grow_above_75(const struct rhashtable *ht, size_t new_size)
+static bool rht_grow_above_75(const struct rhashtable *ht,
+ const struct bucket_table *tbl)
{
/* Expand table when exceeding 75% load */
- return atomic_read(&ht->nelems) > (new_size / 4 * 3) &&
- (!ht->p.max_shift || atomic_read(&ht->shift) < ht->p.max_shift);
+ return atomic_read(&ht->nelems) > (tbl->size / 4 * 3) &&
+ (!ht->p.max_shift || tbl->shift < ht->p.max_shift);
}
/**
* rht_shrink_below_30 - returns true if nelems < 0.3 * table-size
* @ht: hash table
- * @new_size: new table size
+ * @tbl: current table
*/
-static bool rht_shrink_below_30(const struct rhashtable *ht, size_t new_size)
+static bool rht_shrink_below_30(const struct rhashtable *ht,
+ const struct bucket_table *tbl)
{
/* Shrink table beneath 30% load */
- return atomic_read(&ht->nelems) < (new_size * 3 / 10) &&
- (atomic_read(&ht->shift) > ht->p.min_shift);
+ return atomic_read(&ht->nelems) < (tbl->size * 3 / 10) &&
+ tbl->shift > ht->p.min_shift;
}
static int rhashtable_rehash_one(struct rhashtable *ht, unsigned old_hash)
@@ -310,16 +314,11 @@ int rhashtable_expand(struct rhashtable *ht)
ASSERT_RHT_MUTEX(ht);
- new_tbl = bucket_table_alloc(ht, old_tbl->size * 2);
+ new_tbl = bucket_table_alloc(ht, old_tbl->size * 2, old_tbl->hash_rnd);
if (new_tbl == NULL)
return -ENOMEM;
- new_tbl->hash_rnd = old_tbl->hash_rnd;
-
- atomic_inc(&ht->shift);
-
rhashtable_rehash(ht, new_tbl);
-
return 0;
}
EXPORT_SYMBOL_GPL(rhashtable_expand);
@@ -342,20 +341,15 @@ EXPORT_SYMBOL_GPL(rhashtable_expand);
*/
int rhashtable_shrink(struct rhashtable *ht)
{
- struct bucket_table *new_tbl, *tbl = rht_dereference(ht->tbl, ht);
+ struct bucket_table *new_tbl, *old_tbl = rht_dereference(ht->tbl, ht);
ASSERT_RHT_MUTEX(ht);
- new_tbl = bucket_table_alloc(ht, tbl->size / 2);
+ new_tbl = bucket_table_alloc(ht, old_tbl->size / 2, old_tbl->hash_rnd);
if (new_tbl == NULL)
return -ENOMEM;
- new_tbl->hash_rnd = tbl->hash_rnd;
-
- atomic_dec(&ht->shift);
-
rhashtable_rehash(ht, new_tbl);
-
return 0;
}
EXPORT_SYMBOL_GPL(rhashtable_shrink);
@@ -376,9 +370,9 @@ static void rht_deferred_worker(struct work_struct *work)
list_for_each_entry(walker, &ht->walkers, list)
walker->resize = true;
- if (rht_grow_above_75(ht, tbl->size))
+ if (rht_grow_above_75(ht, tbl))
rhashtable_expand(ht);
- else if (rht_shrink_below_30(ht, tbl->size))
+ else if (rht_shrink_below_30(ht, tbl))
rhashtable_shrink(ht);
unlock:
mutex_unlock(&ht->mutex);
@@ -431,7 +425,7 @@ static bool __rhashtable_insert(struct rhashtable *ht, struct rhash_head *obj,
rcu_assign_pointer(tbl->buckets[hash], obj);
atomic_inc(&ht->nelems);
- if (no_resize_running && rht_grow_above_75(ht, tbl->size))
+ if (no_resize_running && rht_grow_above_75(ht, tbl))
schedule_work(&ht->run_work);
exit:
@@ -539,7 +533,7 @@ bool rhashtable_remove(struct rhashtable *ht, struct rhash_head *obj)
bool no_resize_running = tbl == old_tbl;
atomic_dec(&ht->nelems);
- if (no_resize_running && rht_shrink_below_30(ht, tbl->size))
+ if (no_resize_running && rht_shrink_below_30(ht, tbl))
schedule_work(&ht->run_work);
}
@@ -913,6 +907,7 @@ int rhashtable_init(struct rhashtable *ht, struct rhashtable_params *params)
{
struct bucket_table *tbl;
size_t size;
+ u32 hash_rnd;
size = HASH_DEFAULT_SIZE;
@@ -939,14 +934,14 @@ int rhashtable_init(struct rhashtable *ht, struct rhashtable_params *params)
else
ht->p.locks_mul = BUCKET_LOCKS_PER_CPU;
- tbl = bucket_table_alloc(ht, size);
+ get_random_bytes(&hash_rnd, sizeof(hash_rnd));
+
+ tbl = bucket_table_alloc(ht, size, hash_rnd);
if (tbl == NULL)
return -ENOMEM;
- get_random_bytes(&tbl->hash_rnd, sizeof(tbl->hash_rnd));
-
atomic_set(&ht->nelems, 0);
- atomic_set(&ht->shift, ilog2(tbl->size));
+
RCU_INIT_POINTER(ht->tbl, tbl);
RCU_INIT_POINTER(ht->future_tbl, tbl);