rhashtable.h 6.78 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
/*
 * Resizable, Scalable, Concurrent Hash Table
 *
 * Copyright (c) 2014 Thomas Graf <tgraf@suug.ch>
 * Copyright (c) 2008-2014 Patrick McHardy <kaber@trash.net>
 *
 * Based on the following paper by Josh Triplett, Paul E. McKenney
 * and Jonathan Walpole:
 * 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.
 */

#ifndef _LINUX_RHASHTABLE_H
#define _LINUX_RHASHTABLE_H

#include <linux/rculist.h>

struct rhash_head {
24
	struct rhash_head __rcu		*next;
25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46
};

#define INIT_HASH_HEAD(ptr) ((ptr)->next = NULL)

struct bucket_table {
	size_t				size;
	struct rhash_head __rcu		*buckets[];
};

typedef u32 (*rht_hashfn_t)(const void *data, u32 len, u32 seed);
typedef u32 (*rht_obj_hashfn_t)(const void *data, u32 seed);

struct rhashtable;

/**
 * struct rhashtable_params - Hash table construction parameters
 * @nelem_hint: Hint on number of elements, should be 75% of desired size
 * @key_len: Length of key
 * @key_offset: Offset of key in struct to be hashed
 * @head_offset: Offset of rhash_head in struct to be hashed
 * @hash_rnd: Seed to use while hashing
 * @max_shift: Maximum number of shifts while expanding
47
 * @min_shift: Minimum number of shifts while shrinking
48 49 50 51 52 53 54 55 56 57 58 59 60
 * @hashfn: Function to hash key
 * @obj_hashfn: Function to hash object
 * @grow_decision: If defined, may return true if table should expand
 * @shrink_decision: If defined, may return true if table should shrink
 * @mutex_is_held: Must return true if protecting mutex is held
 */
struct rhashtable_params {
	size_t			nelem_hint;
	size_t			key_len;
	size_t			key_offset;
	size_t			head_offset;
	u32			hash_rnd;
	size_t			max_shift;
61
	size_t			min_shift;
62 63 64 65 66 67
	rht_hashfn_t		hashfn;
	rht_obj_hashfn_t	obj_hashfn;
	bool			(*grow_decision)(const struct rhashtable *ht,
						 size_t new_size);
	bool			(*shrink_decision)(const struct rhashtable *ht,
						   size_t new_size);
68
#ifdef CONFIG_PROVE_LOCKING
69 70
	int			(*mutex_is_held)(void *parent);
	void			*parent;
71
#endif
72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98
};

/**
 * struct rhashtable - Hash table handle
 * @tbl: Bucket table
 * @nelems: Number of elements in table
 * @shift: Current size (1 << shift)
 * @p: Configuration parameters
 */
struct rhashtable {
	struct bucket_table __rcu	*tbl;
	size_t				nelems;
	size_t				shift;
	struct rhashtable_params	p;
};

#ifdef CONFIG_PROVE_LOCKING
int lockdep_rht_mutex_is_held(const struct rhashtable *ht);
#else
static inline int lockdep_rht_mutex_is_held(const struct rhashtable *ht)
{
	return 1;
}
#endif /* CONFIG_PROVE_LOCKING */

int rhashtable_init(struct rhashtable *ht, struct rhashtable_params *params);

99 100
void rhashtable_insert(struct rhashtable *ht, struct rhash_head *node);
bool rhashtable_remove(struct rhashtable *ht, struct rhash_head *node);
101
void rhashtable_remove_pprev(struct rhashtable *ht, struct rhash_head *obj,
102
			     struct rhash_head __rcu **pprev);
103 104 105 106

bool rht_grow_above_75(const struct rhashtable *ht, size_t new_size);
bool rht_shrink_below_30(const struct rhashtable *ht, size_t new_size);

107 108
int rhashtable_expand(struct rhashtable *ht);
int rhashtable_shrink(struct rhashtable *ht);
109 110

void *rhashtable_lookup(const struct rhashtable *ht, const void *key);
111
void *rhashtable_lookup_compare(const struct rhashtable *ht, const void *key,
112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203
				bool (*compare)(void *, void *), void *arg);

void rhashtable_destroy(const struct rhashtable *ht);

#define rht_dereference(p, ht) \
	rcu_dereference_protected(p, lockdep_rht_mutex_is_held(ht))

#define rht_dereference_rcu(p, ht) \
	rcu_dereference_check(p, lockdep_rht_mutex_is_held(ht))

#define rht_entry(ptr, type, member) container_of(ptr, type, member)
#define rht_entry_safe(ptr, type, member) \
({ \
	typeof(ptr) __ptr = (ptr); \
	   __ptr ? rht_entry(__ptr, type, member) : NULL; \
})

#define rht_next_entry_safe(pos, ht, member) \
({ \
	pos ? rht_entry_safe(rht_dereference((pos)->member.next, ht), \
			     typeof(*(pos)), member) : NULL; \
})

/**
 * rht_for_each - iterate over hash chain
 * @pos:	&struct rhash_head to use as a loop cursor.
 * @head:	head of the hash chain (struct rhash_head *)
 * @ht:		pointer to your struct rhashtable
 */
#define rht_for_each(pos, head, ht) \
	for (pos = rht_dereference(head, ht); \
	     pos; \
	     pos = rht_dereference((pos)->next, ht))

/**
 * rht_for_each_entry - iterate over hash chain of given type
 * @pos:	type * to use as a loop cursor.
 * @head:	head of the hash chain (struct rhash_head *)
 * @ht:		pointer to your struct rhashtable
 * @member:	name of the rhash_head within the hashable struct.
 */
#define rht_for_each_entry(pos, head, ht, member) \
	for (pos = rht_entry_safe(rht_dereference(head, ht), \
				   typeof(*(pos)), member); \
	     pos; \
	     pos = rht_next_entry_safe(pos, ht, member))

/**
 * rht_for_each_entry_safe - safely iterate over hash chain of given type
 * @pos:	type * to use as a loop cursor.
 * @n:		type * to use for temporary next object storage
 * @head:	head of the hash chain (struct rhash_head *)
 * @ht:		pointer to your struct rhashtable
 * @member:	name of the rhash_head within the hashable struct.
 *
 * This hash chain list-traversal primitive allows for the looped code to
 * remove the loop cursor from the list.
 */
#define rht_for_each_entry_safe(pos, n, head, ht, member)		\
	for (pos = rht_entry_safe(rht_dereference(head, ht), \
				  typeof(*(pos)), member), \
	     n = rht_next_entry_safe(pos, ht, member); \
	     pos; \
	     pos = n, \
	     n = rht_next_entry_safe(pos, ht, member))

/**
 * rht_for_each_rcu - iterate over rcu hash chain
 * @pos:	&struct rhash_head to use as a loop cursor.
 * @head:	head of the hash chain (struct rhash_head *)
 * @ht:		pointer to your struct rhashtable
 *
 * This hash chain list-traversal primitive may safely run concurrently with
 * the _rcu fkht mutation primitives such as rht_insert() as long as the
 * traversal is guarded by rcu_read_lock().
 */
#define rht_for_each_rcu(pos, head, ht) \
	for (pos = rht_dereference_rcu(head, ht); \
	     pos; \
	     pos = rht_dereference_rcu((pos)->next, ht))

/**
 * rht_for_each_entry_rcu - iterate over rcu hash chain of given type
 * @pos:	type * to use as a loop cursor.
 * @head:	head of the hash chain (struct rhash_head *)
 * @member:	name of the rhash_head within the hashable struct.
 *
 * This hash chain list-traversal primitive may safely run concurrently with
 * the _rcu fkht mutation primitives such as rht_insert() as long as the
 * traversal is guarded by rcu_read_lock().
 */
#define rht_for_each_entry_rcu(pos, head, member) \
204 205
	for (pos = rht_entry_safe(rcu_dereference_raw(head), \
				  typeof(*(pos)), member); \
206
	     pos; \
207 208
	     pos = rht_entry_safe(rcu_dereference_raw((pos)->member.next), \
				  typeof(*(pos)), member))
209 210

#endif /* _LINUX_RHASHTABLE_H */