stream, vconn: Fix comments.
[sliver-openvswitch.git] / datapath / table.c
1 /*
2  * Copyright (c) 2009, 2010 Nicira Networks.
3  * Distributed under the terms of the GNU GPL version 2.
4  *
5  * Significant portions of this file may be copied from parts of the Linux
6  * kernel, by Linus Torvalds and others.
7  */
8
9 #include "flow.h"
10 #include "datapath.h"
11 #include "table.h"
12
13 #include <linux/gfp.h>
14 #include <linux/slab.h>
15 #include <linux/mm.h>
16 #include <asm/pgtable.h>
17
18 /**
19  * struct tbl - hash table
20  * @n_buckets: number of buckets (a power of 2 between %TBL_L1_SIZE and
21  * %TBL_MAX_BUCKETS)
22  * @buckets: pointer to @n_buckets/%TBL_L1_SIZE pointers to %TBL_L1_SIZE pointers
23  * to buckets
24  * @rcu: RCU callback structure
25  * @obj_destructor: Called on each element when the table is destroyed.
26  *
27  * The @buckets array is logically an array of pointers to buckets.  It is
28  * broken into two levels to avoid the need to kmalloc() any object larger than
29  * a single page or to use vmalloc().  @buckets is always nonnull, as is each
30  * @buckets[i], but each @buckets[i][j] is nonnull only if the specified hash
31  * bucket is nonempty (for 0 <= i < @n_buckets/%TBL_L1_SIZE, 0 <= j <
32  * %TBL_L1_SIZE).
33  */
34 struct tbl {
35         struct rcu_head rcu;
36         unsigned int n_buckets;
37         struct tbl_bucket ***buckets;
38         unsigned int count;
39         void (*obj_destructor)(struct tbl_node *);
40 };
41
42 /**
43  * struct tbl_bucket - single bucket within a hash table
44  * @rcu: RCU callback structure
45  * @n_objs: number of objects in @objs[] array
46  * @objs: array of @n_objs pointers to table nodes contained inside objects
47  *
48  * The expected number of objects per bucket is 1, but this allows for an
49  * arbitrary number of collisions.
50  */
51 struct tbl_bucket {
52         struct rcu_head rcu;
53         unsigned int n_objs;
54         struct tbl_node *objs[];
55 };
56
57 static inline int bucket_size(int n_objs)
58 {
59         return sizeof(struct tbl_bucket) + sizeof(struct tbl_node *) * n_objs;
60 }
61
62 static struct tbl_bucket *bucket_alloc(int n_objs)
63 {
64         return kmalloc(bucket_size(n_objs), GFP_KERNEL);
65 }
66
67 static void free_buckets(struct tbl_bucket ***l1, unsigned int n_buckets,
68                          void (*free_obj)(struct tbl_node *))
69 {
70         unsigned int i;
71
72         for (i = 0; i < n_buckets >> TBL_L1_BITS; i++) {
73                 struct tbl_bucket **l2 = l1[i];
74                 unsigned int j;
75
76                 for (j = 0; j < TBL_L1_SIZE; j++) {
77                         struct tbl_bucket *bucket = l2[j];
78                         if (!bucket)
79                                 continue;
80
81                         if (free_obj) {
82                                 unsigned int k;
83                                 for (k = 0; k < bucket->n_objs; k++)
84                                         free_obj(bucket->objs[k]);
85                         }
86                         kfree(bucket);
87                 }
88                 free_page((unsigned long)l2);
89         }
90         kfree(l1);
91 }
92
93 static struct tbl_bucket ***alloc_buckets(unsigned int n_buckets)
94 {
95         struct tbl_bucket ***l1;
96         unsigned int i;
97
98         l1 = kmalloc((n_buckets >> TBL_L1_BITS) * sizeof(struct tbl_bucket **),
99                      GFP_KERNEL);
100         if (!l1)
101                 return NULL;
102         for (i = 0; i < n_buckets >> TBL_L1_BITS; i++) {
103                 l1[i] = (struct tbl_bucket **)get_zeroed_page(GFP_KERNEL);
104                 if (!l1[i]) {
105                         free_buckets(l1, i << TBL_L1_BITS, 0);
106                         return NULL;
107                 }
108         }
109         return l1;
110 }
111
112 /**
113  * tbl_create - create and return a new hash table
114  * @n_buckets: number of buckets in the new table
115  *
116  * Creates and returns a new hash table, or %NULL if memory cannot be
117  * allocated.  @n_buckets must be a power of 2 in the range %TBL_L1_SIZE to
118  * %TBL_MAX_BUCKETS.
119  */
120 struct tbl *tbl_create(unsigned int n_buckets)
121 {
122         struct tbl *table;
123
124         if (!n_buckets)
125                 n_buckets = TBL_L1_SIZE;
126
127         table = kzalloc(sizeof *table, GFP_KERNEL);
128         if (!table)
129                 goto err;
130
131         table->n_buckets = n_buckets;
132         table->buckets = alloc_buckets(n_buckets);
133         if (!table->buckets)
134                 goto err_free_table;
135
136         return table;
137
138 err_free_table:
139         kfree(table);
140 err:
141         return NULL;
142 }
143
144 /**
145  * tbl_destroy - destroy hash table and optionally the objects it contains
146  * @table: table to destroy
147  * @destructor: function to be called on objects at destruction time
148  *
149  * If a destructor is null, then the buckets in @table are destroyed
150  * but not the objects within those buckets.  This behavior is useful when a
151  * table is being replaced by a larger or smaller one without destroying the
152  * objects.
153  *
154  * If a destructor is not null, then it is called on the objects in @table
155  * before destroying the buckets.
156  */
157 void tbl_destroy(struct tbl *table, void (*destructor)(struct tbl_node *))
158 {
159         if (!table)
160                 return;
161
162         free_buckets(table->buckets, table->n_buckets, destructor);
163         kfree(table);
164 }
165
166 static void destroy_table_rcu(struct rcu_head *rcu)
167 {
168         struct tbl *table = container_of(rcu, struct tbl, rcu);
169         tbl_destroy(table, table->obj_destructor);
170 }
171
172 /**
173  * tbl_deferred_destroy - destroy table after a RCU grace period
174  * @table: table to destroy
175  * @destructor: function to be called on objects at destruction time
176  *
177  * Calls tbl_destroy() on @table after an RCU grace period. If @destructor is
178  * not null it is called on every element before the table is destroyed. */
179 void tbl_deferred_destroy(struct tbl *table, void (*destructor)(struct tbl_node *))
180 {
181         if (!table)
182                 return;
183
184         table->obj_destructor = destructor;
185         call_rcu(&table->rcu, destroy_table_rcu);
186 }
187
188 static struct tbl_bucket **find_bucket(struct tbl *table, u32 hash)
189 {
190         unsigned int l1 = (hash & (table->n_buckets - 1)) >> TBL_L1_SHIFT;
191         unsigned int l2 = hash & ((1 << TBL_L2_BITS) - 1);
192         return &table->buckets[l1][l2];
193 }
194
195 static int search_bucket(const struct tbl_bucket *bucket, void *target, u32 hash,
196                          int (*cmp)(const struct tbl_node *, void *))
197 {
198         int i;
199
200         for (i = 0; i < bucket->n_objs; i++) {
201                 struct tbl_node *obj = rcu_dereference(bucket->objs[i]);
202                 if (obj->hash == hash && likely(cmp(obj, target)))
203                         return i;
204         }
205
206         return -1;
207 }
208
209 /**
210  * tbl_lookup - searches hash table for a matching object
211  * @table: hash table to search
212  * @target: identifier for the object that is being searched for, will be
213  * provided as an argument to @cmp when making comparisions
214  * @hash: hash of @target
215  * @cmp: comparision function to match objects with the given hash, returns
216  * nonzero if the objects match, zero otherwise
217  *
218  * Searches @table for an object identified by @target.  Returns the tbl_node
219  * contained in the object if successful, otherwise %NULL.
220  */
221 struct tbl_node *tbl_lookup(struct tbl *table, void *target, u32 hash,
222                             int (*cmp)(const struct tbl_node *, void *))
223 {
224         struct tbl_bucket **bucketp = find_bucket(table, hash);
225         struct tbl_bucket *bucket = rcu_dereference(*bucketp);
226         int index;
227
228         if (!bucket)
229                 return NULL;
230
231         index = search_bucket(bucket, target, hash, cmp);
232         if (index < 0)
233                 return NULL;
234
235         return bucket->objs[index];
236 }
237
238 /**
239  * tbl_foreach - iterate through hash table
240  * @table: table to iterate
241  * @callback: function to call for each entry
242  * @aux: Extra data to pass to @callback
243  *
244  * Iterates through all of the objects in @table in hash order, passing each of
245  * them in turn to @callback.  If @callback returns nonzero, this terminates
246  * the iteration and tbl_foreach() returns the same value.  Returns 0 if
247  * @callback never returns nonzero.
248  *
249  * This function does not try to intelligently handle the case where @callback
250  * adds or removes flows in @table.
251  */
252 int tbl_foreach(struct tbl *table,
253                 int (*callback)(struct tbl_node *, void *aux), void *aux)
254 {
255         unsigned int i, j, k;
256         for (i = 0; i < table->n_buckets >> TBL_L1_BITS; i++) {
257                 struct tbl_bucket **l2 = table->buckets[i];
258                 for (j = 0; j < TBL_L1_SIZE; j++) {
259                         struct tbl_bucket *bucket = rcu_dereference(l2[j]);
260                         if (!bucket)
261                                 continue;
262
263                         for (k = 0; k < bucket->n_objs; k++) {
264                                 int error = (*callback)(bucket->objs[k], aux);
265                                 if (error)
266                                         return error;
267                         }
268                 }
269         }
270         return 0;
271 }
272
273 static int insert_table_flow(struct tbl_node *node, void *new_table_)
274 {
275         struct tbl *new_table = new_table_;
276         return tbl_insert(new_table, node, node->hash);
277 }
278
279 /**
280  * tbl_expand - create a hash table with more buckets
281  * @table: table to expand
282  *
283  * Creates a new table containing the same objects as @table but with twice
284  * as many buckets.  Returns 0 if successful, otherwise a negative error.  The
285  * caller should free @table upon success (probably using
286  * tbl_deferred_destroy()).
287  */
288 struct tbl *tbl_expand(struct tbl *table)
289 {
290         int err;
291         int n_buckets = table->n_buckets * 2;
292         struct tbl *new_table;
293
294         if (n_buckets >= TBL_MAX_BUCKETS) {
295                 err = -ENOSPC;
296                 goto error;
297         }
298
299         err = -ENOMEM;
300         new_table = tbl_create(n_buckets);
301         if (!new_table)
302                 goto error;
303
304         if (tbl_foreach(table, insert_table_flow, new_table))
305                 goto error_free_new_table;
306
307         return new_table;
308
309 error_free_new_table:
310         tbl_destroy(new_table, NULL);
311 error:
312         return ERR_PTR(err);
313 }
314
315 /**
316  * tbl_n_buckets - returns the number of buckets
317  * @table: table to examine
318  *
319  * Returns the number of buckets currently allocated in @table, useful when
320  * deciding whether to expand.
321  */
322 int tbl_n_buckets(struct tbl *table)
323 {
324         return table->n_buckets;
325 }
326
327 static void free_bucket_rcu(struct rcu_head *rcu)
328 {
329         struct tbl_bucket *bucket = container_of(rcu, struct tbl_bucket, rcu);
330         kfree(bucket);
331 }
332
333 /**
334  * tbl_insert - insert object into table
335  * @table: table in which to insert object
336  * @target: tbl_node contained in object to insert
337  * @hash: hash of object to insert
338  *
339  * The caller must ensure that no object considered to be identical to @target
340  * already exists in @table.  Returns 0 or a negative error (currently just
341  * -ENOMEM).
342  */
343 int tbl_insert(struct tbl *table, struct tbl_node *target, u32 hash)
344 {
345         struct tbl_bucket **oldp = find_bucket(table, hash);
346         struct tbl_bucket *old = *rcu_dereference(oldp);
347         unsigned int n = old ? old->n_objs : 0;
348         struct tbl_bucket *new = bucket_alloc(n + 1);
349
350         if (!new)
351                 return -ENOMEM;
352
353         target->hash = hash;
354
355         new->n_objs = n + 1;
356         if (old)
357                 memcpy(new->objs, old->objs, n * sizeof(struct tbl_node *));
358         new->objs[n] = target;
359
360         rcu_assign_pointer(*oldp, new);
361         if (old)
362                 call_rcu(&old->rcu, free_bucket_rcu);
363
364         table->count++;
365
366         return 0;
367 }
368
369 /**
370  * tbl_remove - remove object from table
371  * @table: table from which to remove object
372  * @target: tbl_node inside of object to remove
373  *
374  * The caller must ensure that @target itself is in @table.  (It is not
375  * good enough for @table to contain a different object considered identical
376  * @target.)
377  *
378  * Returns 0 or a negative error (currently just -ENOMEM).  Yes, it *is*
379  * possible for object deletion to fail due to lack of memory.
380  */
381 int tbl_remove(struct tbl *table, struct tbl_node *target)
382 {
383         struct tbl_bucket **oldp = find_bucket(table, target->hash);
384         struct tbl_bucket *old = *rcu_dereference(oldp);
385         unsigned int n = old->n_objs;
386         struct tbl_bucket *new;
387
388         if (n > 1) {
389                 unsigned int i;
390
391                 new = bucket_alloc(n - 1);
392                 if (!new)
393                         return -ENOMEM;
394
395                 new->n_objs = 0;
396                 for (i = 0; i < n; i++) {
397                         struct tbl_node *obj = old->objs[i];
398                         if (obj != target)
399                                 new->objs[new->n_objs++] = obj;
400                 }
401                 WARN_ON_ONCE(new->n_objs != n - 1);
402         } else {
403                 new = NULL;
404         }
405
406         rcu_assign_pointer(*oldp, new);
407         call_rcu(&old->rcu, free_bucket_rcu);
408
409         table->count--;
410
411         return 0;
412 }
413
414 /**
415  * tbl_count - retrieves the number of stored objects
416  * @table: table to count
417  *
418  * Returns the number of objects that have been inserted into the hash table.
419  */
420 unsigned int tbl_count(struct tbl *table)
421 {
422         return table->count;
423 }