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