/*
* Resizable, Scalable, Concurrent Hash Table
*
* Copyright (c) 2014-2015 Thomas Graf <tgraf@suug.ch>
* Copyright (c) 2008-2014 Patrick McHardy <kaber@trash.net>
*
* Based on the following paper:
* https://www.usenix.org/legacy/event/atc11/tech/final_files/Triplett.pdf
*
* Code partially derived from nft_hash
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License version 2 as
* published by the Free Software Foundation.
*/
#include <linux/kernel.h>
#include <linux/init.h>
#include <linux/log2.h>
#include <linux/sched.h>
#include <linux/slab.h>
#include <linux/vmalloc.h>
#include <linux/mm.h>
#include <linux/jhash.h>
#include <linux/random.h>
#include <linux/rhashtable.h>
#include <linux/err.h>
#define HASH_DEFAULT_SIZE 64UL
#define HASH_MIN_SIZE 4U
#define BUCKET_LOCKS_PER_CPU 128UL
/* Base bits plus 1 bit for nulls marker */
#define HASH_RESERVED_SPACE (RHT_BASE_BITS + 1)
/* The bucket lock is selected based on the hash and protects mutations
* on a group of hash buckets.
*
* A maximum of tbl->size/2 bucket locks is allocated. This ensures that
* a single lock always covers both buckets which may both contains
* entries which link to the same bucket of the old table during resizing.
* This allows to simplify the locking as locking the bucket in both
* tables during resize always guarantee protection.
*
* IMPORTANT: When holding the bucket lock of both the old and new table
* during expansions and shrinking, the old bucket lock must always be
* acquired first.
*/
static spinlock_t *bucket_lock(const struct bucket_table *tbl, u32 hash)
{
return &tbl->locks[hash & tbl->locks_mask];
}
static void *rht_obj(const struct rhashtable *ht, const struct rhash_head *he)
{
return (void *) he - ht->p.head_offset;
}
static u32 rht_bucket_index(const struct bucket_table *tbl, u32 hash)
{
return (hash >> HASH_RESERVED_SPACE) & (tbl->size - 1);
}
static u32 key_hashfn(struct rhashtable *ht, const struct bucket_table *tbl,
const void *key)
{
return rht_bucket_index(tbl, ht->p.hashfn(key, ht->p.key_len,
tbl->hash_rnd));
}
static u32 head_hashfn(struct rhashtable *ht,
const struct bucket_table *tbl,
const struct rhash_head *he)
{
const char *ptr = rht_obj(ht, he);
return likely(ht->p.key_len) ?
key_hashfn(ht, tbl, ptr + ht->p.key_offset) :
rht_bucket_index(tbl, ht->p.obj_hashfn(ptr, tbl->hash_rnd));
}
#ifdef CONFIG_PROVE_LOCKING
#define ASSERT_RHT_MUTEX(HT) BUG_ON(!lockdep_rht_mutex_is_held(HT))
int lockdep_rht_mutex_is_held(struct rhashtable *ht)
{
return (debug_locks) ? lockdep_is_held(&ht->mutex) : 1;
}
EXPORT_SYMBOL_GPL(lockdep_rht_mutex_is_held);
int lockdep_rht_bucket_is_held(const struct bucket_table *tbl, u32 hash)
{
spinlock_t *lock = bucket_lock(tbl, hash);
return (debug_locks) ? lockdep_is_held(lock) : 1;
}
EXPORT_SYMBOL_GPL(lockdep_rht_bucket_is_held);
#else
#define ASSERT_RHT_MUTEX(HT)
#endif
static int alloc_bucket_locks(struct rhashtable *ht, struct bucket_table *tbl)
{
unsigned int i, size;
#if defined(CONFIG_PROVE_LOCKING)
unsigned int nr_pcpus = 2;
#else
unsigned int nr_pcpus = num_possible_cpus();
#endif
nr_pcpus = min_t(unsigned int, nr_pcpus, 32UL);
size = roundup_pow_of_two(nr_pcpus * ht->p.locks_mul);
/* Never allocate more than 0.5 locks per bucket */
size = min_t(unsigned int, size, tbl->size >> 1);
if (sizeof(spinlock_t) != 0) {
#ifdef CONFIG_NUMA
if (size * sizeof(spinlock_t) > PAGE_SIZE)
tbl->locks = vmalloc(size * sizeof(spinlock_t));
else
#endif
tbl->locks = kmalloc_array(size, sizeof(spinlock_t),
GFP_KERNEL);
if (!tbl->locks)
return -ENOMEM;
for (i = 0; i < size; i++)
spin_lock_init(&tbl->locks[i]);
}
tbl->locks_mask = size - 1;
return 0;
}
static void bucket_table_free(const struct bucket_table *tbl)
{
if (tbl)
kvfree(tbl->locks);
kvfree(tbl);
}
static void bucket_table_free_rcu(struct rcu_head *head)
{
bucket_table_free(container_of(head, struct bucket_table, rcu));
}
static struct bucket_table *bucket_table_alloc(struct rhashtable *ht,
size_t nbuckets)
{
struct bucket_table *tbl = NULL;
size_t size;
int i;
size =<