2 * Copyright (c) 2009, 2010 Nicira Networks.
3 * Distributed under the terms of the GNU GPL version 2.
5 * Significant portions of this file may be copied from parts of the Linux
6 * kernel, by Linus Torvalds and others.
13 #include <linux/gfp.h>
14 #include <linux/slab.h>
16 #include <asm/pgtable.h>
19 * struct tbl_bucket - single bucket within a hash table
20 * @rcu: RCU callback structure
21 * @n_objs: number of objects in @objs[] array
22 * @objs: array of @n_objs pointers to table nodes contained inside objects
24 * The expected number of objects per bucket is 1, but this allows for an
25 * arbitrary number of collisions.
30 struct tbl_node *objs[];
33 static inline int bucket_size(int n_objs)
35 return sizeof(struct tbl_bucket) + sizeof(struct tbl_node *) * n_objs;
38 static struct tbl_bucket *bucket_alloc(int n_objs)
40 return kmalloc(bucket_size(n_objs), GFP_KERNEL);
43 static void free_buckets(struct tbl_bucket ***l1, unsigned int n_buckets,
44 void (*free_obj)(struct tbl_node *))
48 for (i = 0; i < n_buckets >> TBL_L1_BITS; i++) {
49 struct tbl_bucket **l2 = l1[i];
52 for (j = 0; j < TBL_L1_SIZE; j++) {
53 struct tbl_bucket *bucket = l2[j];
59 for (k = 0; k < bucket->n_objs; k++)
60 free_obj(bucket->objs[k]);
64 free_page((unsigned long)l2);
69 static struct tbl_bucket ***alloc_buckets(unsigned int n_buckets)
71 struct tbl_bucket ***l1;
74 l1 = kmalloc((n_buckets >> TBL_L1_BITS) * sizeof(struct tbl_bucket **),
78 for (i = 0; i < n_buckets >> TBL_L1_BITS; i++) {
79 l1[i] = (struct tbl_bucket **)get_zeroed_page(GFP_KERNEL);
81 free_buckets(l1, i << TBL_L1_BITS, 0);
89 * tbl_create - create and return a new hash table
90 * @n_buckets: number of buckets in the new table
92 * Creates and returns a new hash table, or %NULL if memory cannot be
93 * allocated. @n_buckets must be a power of 2 in the range %TBL_L1_SIZE to
96 struct tbl *tbl_create(unsigned int n_buckets)
101 n_buckets = TBL_L1_SIZE;
103 table = kzalloc(sizeof *table, GFP_KERNEL);
107 table->n_buckets = n_buckets;
108 table->buckets = alloc_buckets(n_buckets);
121 * tbl_destroy - destroy hash table and optionally the objects it contains
122 * @table: table to destroy
123 * @destructor: function to be called on objects at destruction time
125 * If a destructor is null, then the buckets in @table are destroyed
126 * but not the objects within those buckets. This behavior is useful when a
127 * table is being replaced by a larger or smaller one without destroying the
130 * If a destructor is not null, then it is called on the objects in @table
131 * before destroying the buckets.
133 void tbl_destroy(struct tbl *table, void (*destructor)(struct tbl_node *))
138 free_buckets(table->buckets, table->n_buckets, destructor);
142 static void destroy_table_rcu(struct rcu_head *rcu)
144 struct tbl *table = container_of(rcu, struct tbl, rcu);
145 tbl_destroy(table, table->obj_destructor);
149 * tbl_deferred_destroy - destroy table after a RCU grace period
150 * @table: table to destroy
151 * @destructor: function to be called on objects at destruction time
153 * Calls tbl_destroy() on @table after an RCU grace period. If @destructor is
154 * not null it is called on every element before the table is destroyed. */
155 void tbl_deferred_destroy(struct tbl *table, void (*destructor)(struct tbl_node *))
160 table->obj_destructor = destructor;
161 call_rcu(&table->rcu, destroy_table_rcu);
164 static struct tbl_bucket **find_bucket(struct tbl *table, u32 hash)
166 unsigned int l1 = (hash & (table->n_buckets - 1)) >> TBL_L1_SHIFT;
167 unsigned int l2 = hash & ((1 << TBL_L2_BITS) - 1);
168 return &table->buckets[l1][l2];
171 static int search_bucket(const struct tbl_bucket *bucket, void *target, u32 hash,
172 int (*cmp)(const struct tbl_node *, void *))
176 for (i = 0; i < bucket->n_objs; i++) {
177 struct tbl_node *obj = rcu_dereference(bucket->objs[i]);
178 if (obj->hash == hash && likely(cmp(obj, target)))
186 * tbl_lookup - searches hash table for a matching object
187 * @table: hash table to search
188 * @target: identifier for the object that is being searched for, will be
189 * provided as an argument to @cmp when making comparisions
190 * @hash: hash of @target
191 * @cmp: comparision function to match objects with the given hash, returns
192 * nonzero if the objects match, zero otherwise
194 * Searches @table for an object identified by @target. Returns the tbl_node
195 * contained in the object if successful, otherwise %NULL.
197 struct tbl_node *tbl_lookup(struct tbl *table, void *target, u32 hash,
198 int (*cmp)(const struct tbl_node *, void *))
200 struct tbl_bucket **bucketp = find_bucket(table, hash);
201 struct tbl_bucket *bucket = rcu_dereference(*bucketp);
207 index = search_bucket(bucket, target, hash, cmp);
211 return bucket->objs[index];
215 * tbl_foreach - iterate through hash table
216 * @table: table to iterate
217 * @callback: function to call for each entry
218 * @aux: Extra data to pass to @callback
220 * Iterates through all of the objects in @table in hash order, passing each of
221 * them in turn to @callback. If @callback returns nonzero, this terminates
222 * the iteration and tbl_foreach() returns the same value. Returns 0 if
223 * @callback never returns nonzero.
225 * This function does not try to intelligently handle the case where @callback
226 * adds or removes flows in @table.
228 int tbl_foreach(struct tbl *table,
229 int (*callback)(struct tbl_node *, void *aux), void *aux)
231 unsigned int i, j, k;
232 for (i = 0; i < table->n_buckets >> TBL_L1_BITS; i++) {
233 struct tbl_bucket **l2 = table->buckets[i];
234 for (j = 0; j < TBL_L1_SIZE; j++) {
235 struct tbl_bucket *bucket = rcu_dereference(l2[j]);
239 for (k = 0; k < bucket->n_objs; k++) {
240 int error = (*callback)(bucket->objs[k], aux);
249 static int insert_table_flow(struct tbl_node *node, void *new_table_)
251 struct tbl *new_table = new_table_;
252 return tbl_insert(new_table, node, node->hash);
256 * tbl_expand - create a hash table with more buckets
257 * @table: table to expand
259 * Creates a new table containing the same objects as @table but with twice
260 * as many buckets. Returns 0 if successful, otherwise a negative error. The
261 * caller should free @table upon success (probably using
262 * tbl_deferred_destroy()).
264 struct tbl *tbl_expand(struct tbl *table)
267 int n_buckets = table->n_buckets * 2;
268 struct tbl *new_table;
270 if (n_buckets >= TBL_MAX_BUCKETS) {
276 new_table = tbl_create(n_buckets);
280 if (tbl_foreach(table, insert_table_flow, new_table))
281 goto error_free_new_table;
285 error_free_new_table:
286 tbl_destroy(new_table, NULL);
292 * tbl_n_buckets - returns the number of buckets
293 * @table: table to examine
295 * Returns the number of buckets currently allocated in @table, useful when
296 * deciding whether to expand.
298 int tbl_n_buckets(struct tbl *table)
300 return table->n_buckets;
303 static void free_bucket_rcu(struct rcu_head *rcu)
305 struct tbl_bucket *bucket = container_of(rcu, struct tbl_bucket, rcu);
310 * tbl_insert - insert object into table
311 * @table: table in which to insert object
312 * @target: tbl_node contained in object to insert
313 * @hash: hash of object to insert
315 * The caller must ensure that no object considered to be identical to @target
316 * already exists in @table. Returns 0 or a negative error (currently just
319 int tbl_insert(struct tbl *table, struct tbl_node *target, u32 hash)
321 struct tbl_bucket **oldp = find_bucket(table, hash);
322 struct tbl_bucket *old = *rcu_dereference(oldp);
323 unsigned int n = old ? old->n_objs : 0;
324 struct tbl_bucket *new = bucket_alloc(n + 1);
333 memcpy(new->objs, old->objs, n * sizeof(struct tbl_node *));
334 new->objs[n] = target;
336 rcu_assign_pointer(*oldp, new);
338 call_rcu(&old->rcu, free_bucket_rcu);
346 * tbl_remove - remove object from table
347 * @table: table from which to remove object
348 * @target: tbl_node inside of object to remove
350 * The caller must ensure that @target itself is in @table. (It is not
351 * good enough for @table to contain a different object considered identical
354 * Returns 0 or a negative error (currently just -ENOMEM). Yes, it *is*
355 * possible for object deletion to fail due to lack of memory.
357 int tbl_remove(struct tbl *table, struct tbl_node *target)
359 struct tbl_bucket **oldp = find_bucket(table, target->hash);
360 struct tbl_bucket *old = *rcu_dereference(oldp);
361 unsigned int n = old->n_objs;
362 struct tbl_bucket *new;
367 new = bucket_alloc(n - 1);
372 for (i = 0; i < n; i++) {
373 struct tbl_node *obj = old->objs[i];
375 new->objs[new->n_objs++] = obj;
377 WARN_ON_ONCE(new->n_objs != n - 1);
382 rcu_assign_pointer(*oldp, new);
383 call_rcu(&old->rcu, free_bucket_rcu);
391 * tbl_count - retrieves the number of stored objects
392 * @table: table to count
394 * Returns the number of objects that have been inserted into the hash table.
396 unsigned int tbl_count(struct tbl *table)