Spell verb form of "set up" correctly throughout the tree.
[openvswitch] / datapath / table.c
1 /*
2  * Copyright (c) 2009 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
12 #include <linux/gfp.h>
13 #include <linux/jhash.h>
14 #include <linux/random.h>
15 #include <linux/slab.h>
16 #include <linux/vmalloc.h>
17 #include <linux/mm.h>
18 #include <linux/highmem.h>
19 #include <asm/pgtable.h>
20
21 static inline int bucket_size(int n_flows)
22 {
23         return sizeof(struct dp_bucket) + sizeof(struct sw_flow*) * n_flows;
24 }
25
26 static struct dp_bucket *dp_bucket_alloc(int n_flows)
27 {
28         return kmalloc(bucket_size(n_flows), GFP_KERNEL);
29 }
30
31 static void free_buckets(struct dp_bucket ***l1, unsigned int n_buckets,
32                          int free_flows)
33 {
34         unsigned int i;
35
36         for (i = 0; i < n_buckets >> DP_L1_BITS; i++) {
37                 struct dp_bucket **l2 = l1[i];
38                 unsigned int j;
39
40                 for (j = 0; j < DP_L1_SIZE; j++) {
41                         struct dp_bucket *bucket = l2[j];
42                         if (!bucket)
43                                 continue;
44
45                         if (free_flows) {
46                                 unsigned int k;
47                                 for (k = 0; k < bucket->n_flows; k++)
48                                         flow_free(bucket->flows[k]);
49                         }
50                         kfree(bucket);
51                 }
52                 free_page((unsigned long)l2);
53         }
54         kfree(l1);
55 }
56
57 static struct dp_bucket ***alloc_buckets(unsigned int n_buckets)
58 {
59         struct dp_bucket ***l1;
60         unsigned int i;
61
62         l1 = kmalloc((n_buckets >> DP_L1_BITS) * sizeof(struct dp_bucket**),
63                      GFP_KERNEL);
64         if (!l1)
65                 return NULL;
66         for (i = 0; i < n_buckets >> DP_L1_BITS; i++) {
67                 l1[i] = (struct dp_bucket **)get_zeroed_page(GFP_KERNEL);
68                 if (!l1[i]) {
69                         free_buckets(l1, i << DP_L1_BITS, 0);
70                         return NULL;
71                 }
72         }
73         return l1;
74 }
75
76 /**
77  * dp_table_create - create and return a new flow table
78  * @n_buckets: number of buckets in the new table
79  *
80  * Creates and returns a new flow table, or %NULL if memory cannot be
81  * allocated.  @n_buckets must be a power of 2 in the range %DP_L1_SIZE to
82  * %DP_MAX_BUCKETS.
83  */
84 struct dp_table *dp_table_create(unsigned int n_buckets)
85 {
86         struct dp_table *table;
87
88         table = kzalloc(sizeof *table, GFP_KERNEL);
89         if (!table)
90                 goto err;
91
92         table->n_buckets = n_buckets;
93         table->buckets = alloc_buckets(n_buckets);
94         if (!table->buckets)
95                 goto err_free_table;
96         get_random_bytes(&table->hash_seed, sizeof table->hash_seed);
97
98         return table;
99
100 err_free_table:
101         kfree(table);
102 err:
103         return NULL;
104 }
105
106 /**
107  * dp_table_destroy - destroy flow table and optionally the flows it contains
108  * @table: table to destroy (must not be %NULL)
109  * @free_flows: whether to destroy the flows
110  *
111  * If @free_flows is zero, then the buckets in @table are destroyed but not the
112  * flows within those buckets.  This behavior is useful when a table is being
113  * replaced by a larger or smaller one without destroying the flows.
114  *
115  * If @free_flows is nonzero, then the flows in @table are destroyed as well as
116  * the buckets.
117  */
118 void dp_table_destroy(struct dp_table *table, int free_flows)
119 {
120         free_buckets(table->buckets, table->n_buckets, free_flows);
121         kfree(table);
122 }
123
124 static struct dp_bucket **find_bucket(struct dp_table *table, u32 hash)
125 {
126         unsigned int l1 = (hash & (table->n_buckets - 1)) >> DP_L1_SHIFT;
127         unsigned int l2 = hash & ((1 << DP_L2_BITS) - 1);
128         return &table->buckets[l1][l2];
129 }
130
131 static int search_bucket(const struct dp_bucket *bucket, const struct odp_flow_key *key)
132 {
133         int i;
134
135         for (i = 0; i < bucket->n_flows; i++) {
136                 struct sw_flow *flow = rcu_dereference(bucket->flows[i]);
137                 if (!memcmp(&flow->key, key, sizeof(struct odp_flow_key)))
138                         return i;
139         }
140
141         return -1;
142 }
143
144 static struct sw_flow *lookup_flow(struct dp_table *table, u32 hash,
145                                    const struct odp_flow_key *key)
146 {
147         struct dp_bucket **bucketp = find_bucket(table, hash);
148         struct dp_bucket *bucket = rcu_dereference(*bucketp);
149         int index;
150
151         if (!bucket)
152                 return NULL;
153
154         index = search_bucket(bucket, key);
155         if (index < 0)
156                 return NULL;
157
158         return bucket->flows[index];
159 }
160
161 static u32 flow_hash(const struct dp_table *table,
162                      const struct odp_flow_key *key)
163 {
164         return jhash2((u32*)key, sizeof *key / sizeof(u32), table->hash_seed);
165 }
166
167 /**
168  * dp_table_lookup - searches flow table for a matching flow
169  * @table: flow table to search
170  * @key: flow key for which to search
171  *
172  * Searches @table for a flow whose key is equal to @key.  Returns the flow if
173  * successful, otherwise %NULL.
174  */
175 struct sw_flow *dp_table_lookup(struct dp_table *table,
176                                 const struct odp_flow_key *key)
177 {
178         return lookup_flow(table, flow_hash(table, key), key);
179 }
180
181 /**
182  * dp_table_foreach - iterate through flow table
183  * @table: table to iterate
184  * @callback: function to call for each flow entry
185  * @aux: Extra data to pass to @callback
186  *
187  * Iterates through all of the flows in @table in hash order, passing each of
188  * them in turn to @callback.  If @callback returns nonzero, this terminates
189  * the iteration and dp_table_foreach() returns the same value.  Returns 0 if
190  * @callback never returns nonzero.
191  *
192  * This function does not try to intelligently handle the case where @callback
193  * adds or removes flows in @table.
194  */
195 int dp_table_foreach(struct dp_table *table,
196                      int (*callback)(struct sw_flow *flow, void *aux),
197                      void *aux)
198 {
199         unsigned int i, j, k;
200         for (i = 0; i < table->n_buckets >> DP_L1_BITS; i++) {
201                 struct dp_bucket **l2 = table->buckets[i];
202                 for (j = 0; j < DP_L1_SIZE; j++) {
203                         struct dp_bucket *bucket = rcu_dereference(l2[j]);
204                         if (!bucket)
205                                 continue;
206
207                         for (k = 0; k < bucket->n_flows; k++) {
208                                 int error = (*callback)(bucket->flows[k], aux);
209                                 if (error)
210                                         return error;
211                         }
212                 }
213         }
214         return 0;
215 }
216
217 static int insert_flow(struct sw_flow *flow, void *new_table_)
218 {
219         struct dp_table *new_table = new_table_;
220         return dp_table_insert(new_table, flow);
221 }
222
223 static void dp_free_table_rcu(struct rcu_head *rcu)
224 {
225         struct dp_table *table = container_of(rcu, struct dp_table, rcu);
226         dp_table_destroy(table, 0);
227 }
228
229 /**
230  * dp_table_expand - replace datapath's flow table by one with more buckets
231  * @dp: datapath to expand
232  *
233  * Replaces @dp's flow table by one that has twice as many buckets.  All of the
234  * flows in @dp's flow table are moved to the new flow table.  Returns 0 if
235  * successful, otherwise a negative error.
236  */
237 int dp_table_expand(struct datapath *dp)
238 {
239         struct dp_table *old_table = rcu_dereference(dp->table);
240         struct dp_table *new_table;
241
242         new_table = dp_table_create(old_table->n_buckets * 2);
243         if (!new_table)
244                 goto error;
245
246         if (dp_table_foreach(old_table, insert_flow, new_table))
247                 goto error_free_new_table;
248
249         rcu_assign_pointer(dp->table, new_table);
250         call_rcu(&old_table->rcu, dp_free_table_rcu);
251         return 0;
252
253 error_free_new_table:
254         dp_table_destroy(new_table, 0);
255 error:
256         return -ENOMEM;
257 }
258
259 static void dp_free_table_and_flows_rcu(struct rcu_head *rcu)
260 {
261         struct dp_table *table = container_of(rcu, struct dp_table, rcu);
262         dp_table_destroy(table, 1);
263 }
264
265 /**
266  * dp_table_flush - clear datapath's flow table
267  * @dp: datapath to clear
268  *
269  * Replaces @dp's flow table by an empty flow table, destroying all the flows
270  * in the old table (after a suitable RCU grace period).
271  */
272 int dp_table_flush(struct datapath *dp)
273 {
274         struct dp_table *old_table = rcu_dereference(dp->table);
275         struct dp_table *new_table = dp_table_create(DP_L1_SIZE);
276         if (!new_table)
277                 return -ENOMEM;
278         rcu_assign_pointer(dp->table, new_table);
279         call_rcu(&old_table->rcu, dp_free_table_and_flows_rcu);
280         return 0;
281 }
282
283 static void dp_free_bucket_rcu(struct rcu_head *rcu)
284 {
285         struct dp_bucket *bucket = container_of(rcu, struct dp_bucket, rcu);
286         kfree(bucket);
287 }
288
289 /**
290  * dp_table_insert - insert flow into table
291  * @table: table in which to insert flow
292  * @target: flow to insert
293  *
294  * The caller must ensure that no flow with key identical to @target->key
295  * already exists in @table.  Returns 0 or a negative error (currently just
296  * -ENOMEM).
297  *
298  * The caller is responsible for updating &struct datapath's n_flows member.
299  */
300 int dp_table_insert(struct dp_table *table, struct sw_flow *target)
301 {
302         u32 hash = flow_hash(table, &target->key);
303         struct dp_bucket **oldp = find_bucket(table, hash);
304         struct dp_bucket *old = *rcu_dereference(oldp);
305         unsigned int n = old ? old->n_flows : 0;
306         struct dp_bucket *new = dp_bucket_alloc(n + 1);
307
308         if (!new)
309                 return -ENOMEM;
310
311         new->n_flows = n + 1;
312         if (old)
313                 memcpy(new->flows, old->flows, n * sizeof(struct sw_flow*));
314         new->flows[n] = target;
315
316         rcu_assign_pointer(*oldp, new);
317         if (old)
318                 call_rcu(&old->rcu, dp_free_bucket_rcu);
319
320         return 0;
321 }
322
323 /**
324  * dp_table_delete - remove flow from table
325  * @table: table from which to remove flow
326  * @target: flow to remove
327  *
328  * The caller must ensure that @target itself is in @table.  (It is not
329  * good enough for @table to contain a different flow with a key equal to
330  * @target's key.)
331  *
332  * Returns 0 or a negative error (currently just -ENOMEM).  Yes, it *is*
333  * possible for a flow deletion to fail due to lack of memory.
334  *
335  * The caller is responsible for updating &struct datapath's n_flows member.
336  */
337 int dp_table_delete(struct dp_table *table, struct sw_flow *target)
338 {
339         u32 hash = flow_hash(table, &target->key);
340         struct dp_bucket **oldp = find_bucket(table, hash);
341         struct dp_bucket *old = *rcu_dereference(oldp);
342         unsigned int n = old->n_flows;
343         struct dp_bucket *new;
344
345         if (n > 1) {
346                 unsigned int i;
347
348                 new = dp_bucket_alloc(n - 1);
349                 if (!new)
350                         return -ENOMEM;
351
352                 new->n_flows = 0;
353                 for (i = 0; i < n; i++) {
354                         struct sw_flow *flow = old->flows[i];
355                         if (flow != target)
356                                 new->flows[new->n_flows++] = flow;
357                 }
358                 WARN_ON_ONCE(new->n_flows != n - 1);
359         } else {
360                 new = NULL;
361         }
362
363         rcu_assign_pointer(*oldp, new);
364         call_rcu(&old->rcu, dp_free_bucket_rcu);
365
366         return 0;
367 }