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