blob: bd14052ed3420d2f7c3f3c636000e9822476f253 [file] [log] [blame]
Pravin B Shelare6445712013-10-03 18:16:47 -07001/*
2 * Copyright (c) 2007-2013 Nicira, Inc.
3 *
4 * This program is free software; you can redistribute it and/or
5 * modify it under the terms of version 2 of the GNU General Public
6 * License as published by the Free Software Foundation.
7 *
8 * This program is distributed in the hope that it will be useful, but
9 * WITHOUT ANY WARRANTY; without even the implied warranty of
10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
11 * General Public License for more details.
12 *
13 * You should have received a copy of the GNU General Public License
14 * along with this program; if not, write to the Free Software
15 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
16 * 02110-1301, USA
17 */
18
19#include "flow.h"
20#include "datapath.h"
21#include <linux/uaccess.h>
22#include <linux/netdevice.h>
23#include <linux/etherdevice.h>
24#include <linux/if_ether.h>
25#include <linux/if_vlan.h>
26#include <net/llc_pdu.h>
27#include <linux/kernel.h>
Francesco Fusco500f8082013-12-12 16:09:06 +010028#include <linux/hash.h>
Pravin B Shelare6445712013-10-03 18:16:47 -070029#include <linux/jiffies.h>
30#include <linux/llc.h>
31#include <linux/module.h>
32#include <linux/in.h>
33#include <linux/rcupdate.h>
34#include <linux/if_arp.h>
35#include <linux/ip.h>
36#include <linux/ipv6.h>
37#include <linux/sctp.h>
38#include <linux/tcp.h>
39#include <linux/udp.h>
40#include <linux/icmp.h>
41#include <linux/icmpv6.h>
42#include <linux/rculist.h>
43#include <net/ip.h>
44#include <net/ipv6.h>
45#include <net/ndisc.h>
46
Pravin B Shelarb637e492013-10-04 00:14:23 -070047#define TBL_MIN_BUCKETS 1024
48#define REHASH_INTERVAL (10 * 60 * HZ)
49
Pravin B Shelare6445712013-10-03 18:16:47 -070050static struct kmem_cache *flow_cache;
51
52static u16 range_n_bytes(const struct sw_flow_key_range *range)
53{
54 return range->end - range->start;
55}
56
57void ovs_flow_mask_key(struct sw_flow_key *dst, const struct sw_flow_key *src,
58 const struct sw_flow_mask *mask)
59{
60 const long *m = (long *)((u8 *)&mask->key + mask->range.start);
61 const long *s = (long *)((u8 *)src + mask->range.start);
62 long *d = (long *)((u8 *)dst + mask->range.start);
63 int i;
64
65 /* The memory outside of the 'mask->range' are not set since
66 * further operations on 'dst' only uses contents within
67 * 'mask->range'.
68 */
69 for (i = 0; i < range_n_bytes(&mask->range); i += sizeof(long))
70 *d++ = *s++ & *m++;
71}
72
Pravin B Shelare298e502013-10-29 17:22:21 -070073struct sw_flow *ovs_flow_alloc(bool percpu_stats)
Pravin B Shelare6445712013-10-03 18:16:47 -070074{
75 struct sw_flow *flow;
Pravin B Shelare298e502013-10-29 17:22:21 -070076 int cpu;
Pravin B Shelare6445712013-10-03 18:16:47 -070077
78 flow = kmem_cache_alloc(flow_cache, GFP_KERNEL);
79 if (!flow)
80 return ERR_PTR(-ENOMEM);
81
Pravin B Shelare6445712013-10-03 18:16:47 -070082 flow->sf_acts = NULL;
83 flow->mask = NULL;
84
Pravin B Shelare298e502013-10-29 17:22:21 -070085 flow->stats.is_percpu = percpu_stats;
86
87 if (!percpu_stats) {
88 flow->stats.stat = kzalloc(sizeof(*flow->stats.stat), GFP_KERNEL);
89 if (!flow->stats.stat)
90 goto err;
91
92 spin_lock_init(&flow->stats.stat->lock);
93 } else {
94 flow->stats.cpu_stats = alloc_percpu(struct flow_stats);
95 if (!flow->stats.cpu_stats)
96 goto err;
97
98 for_each_possible_cpu(cpu) {
99 struct flow_stats *cpu_stats;
100
101 cpu_stats = per_cpu_ptr(flow->stats.cpu_stats, cpu);
102 spin_lock_init(&cpu_stats->lock);
103 }
104 }
Pravin B Shelare6445712013-10-03 18:16:47 -0700105 return flow;
Pravin B Shelare298e502013-10-29 17:22:21 -0700106err:
Wei Yongjunece37c82014-01-08 18:13:14 +0800107 kmem_cache_free(flow_cache, flow);
Pravin B Shelare298e502013-10-29 17:22:21 -0700108 return ERR_PTR(-ENOMEM);
Pravin B Shelare6445712013-10-03 18:16:47 -0700109}
110
Pravin B Shelarb637e492013-10-04 00:14:23 -0700111int ovs_flow_tbl_count(struct flow_table *table)
112{
113 return table->count;
114}
115
Pravin B Shelare6445712013-10-03 18:16:47 -0700116static struct flex_array *alloc_buckets(unsigned int n_buckets)
117{
118 struct flex_array *buckets;
119 int i, err;
120
121 buckets = flex_array_alloc(sizeof(struct hlist_head),
122 n_buckets, GFP_KERNEL);
123 if (!buckets)
124 return NULL;
125
126 err = flex_array_prealloc(buckets, 0, n_buckets, GFP_KERNEL);
127 if (err) {
128 flex_array_free(buckets);
129 return NULL;
130 }
131
132 for (i = 0; i < n_buckets; i++)
133 INIT_HLIST_HEAD((struct hlist_head *)
134 flex_array_get(buckets, i));
135
136 return buckets;
137}
138
139static void flow_free(struct sw_flow *flow)
140{
141 kfree((struct sf_flow_acts __force *)flow->sf_acts);
Pravin B Shelare298e502013-10-29 17:22:21 -0700142 if (flow->stats.is_percpu)
143 free_percpu(flow->stats.cpu_stats);
144 else
145 kfree(flow->stats.stat);
Pravin B Shelare6445712013-10-03 18:16:47 -0700146 kmem_cache_free(flow_cache, flow);
147}
148
149static void rcu_free_flow_callback(struct rcu_head *rcu)
150{
151 struct sw_flow *flow = container_of(rcu, struct sw_flow, rcu);
152
153 flow_free(flow);
154}
155
156void ovs_flow_free(struct sw_flow *flow, bool deferred)
157{
158 if (!flow)
159 return;
160
Andy Zhoue80857c2014-01-21 09:31:04 -0800161 ASSERT_OVSL();
162
163 if (flow->mask) {
164 struct sw_flow_mask *mask = flow->mask;
165
166 BUG_ON(!mask->ref_count);
167 mask->ref_count--;
168
169 if (!mask->ref_count) {
170 list_del_rcu(&mask->list);
171 if (deferred)
172 kfree_rcu(mask, rcu);
173 else
174 kfree(mask);
175 }
176 }
Pravin B Shelare6445712013-10-03 18:16:47 -0700177
178 if (deferred)
179 call_rcu(&flow->rcu, rcu_free_flow_callback);
180 else
181 flow_free(flow);
182}
183
184static void free_buckets(struct flex_array *buckets)
185{
186 flex_array_free(buckets);
187}
188
Andy Zhoue80857c2014-01-21 09:31:04 -0800189
Pravin B Shelarb637e492013-10-04 00:14:23 -0700190static void __table_instance_destroy(struct table_instance *ti)
Pravin B Shelare6445712013-10-03 18:16:47 -0700191{
Pravin B Shelarb637e492013-10-04 00:14:23 -0700192 free_buckets(ti->buckets);
193 kfree(ti);
Pravin B Shelare6445712013-10-03 18:16:47 -0700194}
195
Pravin B Shelarb637e492013-10-04 00:14:23 -0700196static struct table_instance *table_instance_alloc(int new_size)
Pravin B Shelare6445712013-10-03 18:16:47 -0700197{
Pravin B Shelarb637e492013-10-04 00:14:23 -0700198 struct table_instance *ti = kmalloc(sizeof(*ti), GFP_KERNEL);
Pravin B Shelare6445712013-10-03 18:16:47 -0700199
Pravin B Shelarb637e492013-10-04 00:14:23 -0700200 if (!ti)
Pravin B Shelare6445712013-10-03 18:16:47 -0700201 return NULL;
202
Pravin B Shelarb637e492013-10-04 00:14:23 -0700203 ti->buckets = alloc_buckets(new_size);
Pravin B Shelare6445712013-10-03 18:16:47 -0700204
Pravin B Shelarb637e492013-10-04 00:14:23 -0700205 if (!ti->buckets) {
206 kfree(ti);
Pravin B Shelare6445712013-10-03 18:16:47 -0700207 return NULL;
208 }
Pravin B Shelarb637e492013-10-04 00:14:23 -0700209 ti->n_buckets = new_size;
210 ti->node_ver = 0;
211 ti->keep_flows = false;
212 get_random_bytes(&ti->hash_seed, sizeof(u32));
213
214 return ti;
215}
216
217int ovs_flow_tbl_init(struct flow_table *table)
218{
219 struct table_instance *ti;
220
221 ti = table_instance_alloc(TBL_MIN_BUCKETS);
222
223 if (!ti)
224 return -ENOMEM;
225
226 rcu_assign_pointer(table->ti, ti);
227 INIT_LIST_HEAD(&table->mask_list);
228 table->last_rehash = jiffies;
Pravin B Shelare6445712013-10-03 18:16:47 -0700229 table->count = 0;
Pravin B Shelarb637e492013-10-04 00:14:23 -0700230 return 0;
Pravin B Shelare6445712013-10-03 18:16:47 -0700231}
232
233static void flow_tbl_destroy_rcu_cb(struct rcu_head *rcu)
234{
Pravin B Shelarb637e492013-10-04 00:14:23 -0700235 struct table_instance *ti = container_of(rcu, struct table_instance, rcu);
Pravin B Shelare6445712013-10-03 18:16:47 -0700236
Pravin B Shelarb637e492013-10-04 00:14:23 -0700237 __table_instance_destroy(ti);
238}
239
240static void table_instance_destroy(struct table_instance *ti, bool deferred)
241{
Andy Zhoue80857c2014-01-21 09:31:04 -0800242 int i;
243
Pravin B Shelarb637e492013-10-04 00:14:23 -0700244 if (!ti)
245 return;
246
Andy Zhoue80857c2014-01-21 09:31:04 -0800247 if (ti->keep_flows)
248 goto skip_flows;
249
250 for (i = 0; i < ti->n_buckets; i++) {
251 struct sw_flow *flow;
252 struct hlist_head *head = flex_array_get(ti->buckets, i);
253 struct hlist_node *n;
254 int ver = ti->node_ver;
255
256 hlist_for_each_entry_safe(flow, n, head, hash_node[ver]) {
257 hlist_del_rcu(&flow->hash_node[ver]);
258 ovs_flow_free(flow, deferred);
259 }
260 }
261
262skip_flows:
Pravin B Shelarb637e492013-10-04 00:14:23 -0700263 if (deferred)
264 call_rcu(&ti->rcu, flow_tbl_destroy_rcu_cb);
265 else
266 __table_instance_destroy(ti);
Pravin B Shelare6445712013-10-03 18:16:47 -0700267}
268
Andy Zhoue80857c2014-01-21 09:31:04 -0800269void ovs_flow_tbl_destroy(struct flow_table *table, bool deferred)
Pravin B Shelare6445712013-10-03 18:16:47 -0700270{
Pravin B Shelarb637e492013-10-04 00:14:23 -0700271 struct table_instance *ti = ovsl_dereference(table->ti);
Pravin B Shelare6445712013-10-03 18:16:47 -0700272
Andy Zhoue80857c2014-01-21 09:31:04 -0800273 table_instance_destroy(ti, deferred);
Pravin B Shelare6445712013-10-03 18:16:47 -0700274}
275
Pravin B Shelarb637e492013-10-04 00:14:23 -0700276struct sw_flow *ovs_flow_tbl_dump_next(struct table_instance *ti,
Pravin B Shelare6445712013-10-03 18:16:47 -0700277 u32 *bucket, u32 *last)
278{
279 struct sw_flow *flow;
280 struct hlist_head *head;
281 int ver;
282 int i;
283
Pravin B Shelarb637e492013-10-04 00:14:23 -0700284 ver = ti->node_ver;
285 while (*bucket < ti->n_buckets) {
Pravin B Shelare6445712013-10-03 18:16:47 -0700286 i = 0;
Pravin B Shelarb637e492013-10-04 00:14:23 -0700287 head = flex_array_get(ti->buckets, *bucket);
Pravin B Shelare6445712013-10-03 18:16:47 -0700288 hlist_for_each_entry_rcu(flow, head, hash_node[ver]) {
289 if (i < *last) {
290 i++;
291 continue;
292 }
293 *last = i + 1;
294 return flow;
295 }
296 (*bucket)++;
297 *last = 0;
298 }
299
300 return NULL;
301}
302
Pravin B Shelarb637e492013-10-04 00:14:23 -0700303static struct hlist_head *find_bucket(struct table_instance *ti, u32 hash)
Pravin B Shelare6445712013-10-03 18:16:47 -0700304{
Pravin B Shelarb637e492013-10-04 00:14:23 -0700305 hash = jhash_1word(hash, ti->hash_seed);
306 return flex_array_get(ti->buckets,
307 (hash & (ti->n_buckets - 1)));
Pravin B Shelare6445712013-10-03 18:16:47 -0700308}
309
Pravin B Shelarb637e492013-10-04 00:14:23 -0700310static void table_instance_insert(struct table_instance *ti, struct sw_flow *flow)
Pravin B Shelare6445712013-10-03 18:16:47 -0700311{
312 struct hlist_head *head;
313
Pravin B Shelarb637e492013-10-04 00:14:23 -0700314 head = find_bucket(ti, flow->hash);
315 hlist_add_head_rcu(&flow->hash_node[ti->node_ver], head);
Pravin B Shelare6445712013-10-03 18:16:47 -0700316}
317
Pravin B Shelarb637e492013-10-04 00:14:23 -0700318static void flow_table_copy_flows(struct table_instance *old,
319 struct table_instance *new)
Pravin B Shelare6445712013-10-03 18:16:47 -0700320{
321 int old_ver;
322 int i;
323
324 old_ver = old->node_ver;
325 new->node_ver = !old_ver;
326
327 /* Insert in new table. */
328 for (i = 0; i < old->n_buckets; i++) {
329 struct sw_flow *flow;
330 struct hlist_head *head;
331
332 head = flex_array_get(old->buckets, i);
333
334 hlist_for_each_entry(flow, head, hash_node[old_ver])
Pravin B Shelarb637e492013-10-04 00:14:23 -0700335 table_instance_insert(new, flow);
Pravin B Shelare6445712013-10-03 18:16:47 -0700336 }
337
Pravin B Shelare6445712013-10-03 18:16:47 -0700338 old->keep_flows = true;
339}
340
Pravin B Shelarb637e492013-10-04 00:14:23 -0700341static struct table_instance *table_instance_rehash(struct table_instance *ti,
Pravin B Shelare6445712013-10-03 18:16:47 -0700342 int n_buckets)
343{
Pravin B Shelarb637e492013-10-04 00:14:23 -0700344 struct table_instance *new_ti;
Pravin B Shelare6445712013-10-03 18:16:47 -0700345
Pravin B Shelarb637e492013-10-04 00:14:23 -0700346 new_ti = table_instance_alloc(n_buckets);
347 if (!new_ti)
Pravin B Shelar618ed0c2013-10-04 00:17:42 -0700348 return NULL;
Pravin B Shelare6445712013-10-03 18:16:47 -0700349
Pravin B Shelarb637e492013-10-04 00:14:23 -0700350 flow_table_copy_flows(ti, new_ti);
Pravin B Shelare6445712013-10-03 18:16:47 -0700351
Pravin B Shelarb637e492013-10-04 00:14:23 -0700352 return new_ti;
Pravin B Shelare6445712013-10-03 18:16:47 -0700353}
354
Pravin B Shelarb637e492013-10-04 00:14:23 -0700355int ovs_flow_tbl_flush(struct flow_table *flow_table)
Pravin B Shelare6445712013-10-03 18:16:47 -0700356{
Pravin B Shelarb637e492013-10-04 00:14:23 -0700357 struct table_instance *old_ti;
358 struct table_instance *new_ti;
Pravin B Shelare6445712013-10-03 18:16:47 -0700359
Pravin B Shelarb637e492013-10-04 00:14:23 -0700360 old_ti = ovsl_dereference(flow_table->ti);
361 new_ti = table_instance_alloc(TBL_MIN_BUCKETS);
362 if (!new_ti)
363 return -ENOMEM;
364
365 rcu_assign_pointer(flow_table->ti, new_ti);
366 flow_table->last_rehash = jiffies;
367 flow_table->count = 0;
368
369 table_instance_destroy(old_ti, true);
370 return 0;
Pravin B Shelare6445712013-10-03 18:16:47 -0700371}
372
373static u32 flow_hash(const struct sw_flow_key *key, int key_start,
374 int key_end)
375{
376 u32 *hash_key = (u32 *)((u8 *)key + key_start);
377 int hash_u32s = (key_end - key_start) >> 2;
378
379 /* Make sure number of hash bytes are multiple of u32. */
380 BUILD_BUG_ON(sizeof(long) % sizeof(u32));
381
Francesco Fusco500f8082013-12-12 16:09:06 +0100382 return arch_fast_hash2(hash_key, hash_u32s, 0);
Pravin B Shelare6445712013-10-03 18:16:47 -0700383}
384
385static int flow_key_start(const struct sw_flow_key *key)
386{
387 if (key->tun_key.ipv4_dst)
388 return 0;
389 else
390 return rounddown(offsetof(struct sw_flow_key, phy),
391 sizeof(long));
392}
393
394static bool cmp_key(const struct sw_flow_key *key1,
395 const struct sw_flow_key *key2,
396 int key_start, int key_end)
397{
398 const long *cp1 = (long *)((u8 *)key1 + key_start);
399 const long *cp2 = (long *)((u8 *)key2 + key_start);
400 long diffs = 0;
401 int i;
402
403 for (i = key_start; i < key_end; i += sizeof(long))
404 diffs |= *cp1++ ^ *cp2++;
405
406 return diffs == 0;
407}
408
409static bool flow_cmp_masked_key(const struct sw_flow *flow,
410 const struct sw_flow_key *key,
411 int key_start, int key_end)
412{
413 return cmp_key(&flow->key, key, key_start, key_end);
414}
415
416bool ovs_flow_cmp_unmasked_key(const struct sw_flow *flow,
417 struct sw_flow_match *match)
418{
419 struct sw_flow_key *key = match->key;
420 int key_start = flow_key_start(key);
421 int key_end = match->range.end;
422
423 return cmp_key(&flow->unmasked_key, key, key_start, key_end);
424}
425
Pravin B Shelarb637e492013-10-04 00:14:23 -0700426static struct sw_flow *masked_flow_lookup(struct table_instance *ti,
Pravin B Shelare6445712013-10-03 18:16:47 -0700427 const struct sw_flow_key *unmasked,
428 struct sw_flow_mask *mask)
429{
430 struct sw_flow *flow;
431 struct hlist_head *head;
432 int key_start = mask->range.start;
433 int key_end = mask->range.end;
434 u32 hash;
435 struct sw_flow_key masked_key;
436
437 ovs_flow_mask_key(&masked_key, unmasked, mask);
438 hash = flow_hash(&masked_key, key_start, key_end);
Pravin B Shelarb637e492013-10-04 00:14:23 -0700439 head = find_bucket(ti, hash);
440 hlist_for_each_entry_rcu(flow, head, hash_node[ti->node_ver]) {
Pravin B Shelar8ddd0942013-10-29 23:10:58 -0700441 if (flow->mask == mask && flow->hash == hash &&
Pravin B Shelare6445712013-10-03 18:16:47 -0700442 flow_cmp_masked_key(flow, &masked_key,
443 key_start, key_end))
444 return flow;
445 }
446 return NULL;
447}
448
Andy Zhou5bb50632013-11-25 10:42:46 -0800449struct sw_flow *ovs_flow_tbl_lookup_stats(struct flow_table *tbl,
Andy Zhou1bd71162013-10-22 10:42:46 -0700450 const struct sw_flow_key *key,
451 u32 *n_mask_hit)
Pravin B Shelare6445712013-10-03 18:16:47 -0700452{
Jesse Gross663efa32013-12-03 10:58:53 -0800453 struct table_instance *ti = rcu_dereference_ovsl(tbl->ti);
Pravin B Shelare6445712013-10-03 18:16:47 -0700454 struct sw_flow_mask *mask;
Pravin B Shelarb637e492013-10-04 00:14:23 -0700455 struct sw_flow *flow;
Pravin B Shelare6445712013-10-03 18:16:47 -0700456
Andy Zhou1bd71162013-10-22 10:42:46 -0700457 *n_mask_hit = 0;
Pravin B Shelarb637e492013-10-04 00:14:23 -0700458 list_for_each_entry_rcu(mask, &tbl->mask_list, list) {
Andy Zhou1bd71162013-10-22 10:42:46 -0700459 (*n_mask_hit)++;
Pravin B Shelarb637e492013-10-04 00:14:23 -0700460 flow = masked_flow_lookup(ti, key, mask);
Pravin B Shelare6445712013-10-03 18:16:47 -0700461 if (flow) /* Found */
Pravin B Shelarb637e492013-10-04 00:14:23 -0700462 return flow;
Pravin B Shelare6445712013-10-03 18:16:47 -0700463 }
Pravin B Shelarb637e492013-10-04 00:14:23 -0700464 return NULL;
465}
Pravin B Shelare6445712013-10-03 18:16:47 -0700466
Andy Zhou5bb50632013-11-25 10:42:46 -0800467struct sw_flow *ovs_flow_tbl_lookup(struct flow_table *tbl,
468 const struct sw_flow_key *key)
469{
470 u32 __always_unused n_mask_hit;
471
472 return ovs_flow_tbl_lookup_stats(tbl, key, &n_mask_hit);
473}
474
Andy Zhou1bd71162013-10-22 10:42:46 -0700475int ovs_flow_tbl_num_masks(const struct flow_table *table)
476{
477 struct sw_flow_mask *mask;
478 int num = 0;
479
480 list_for_each_entry(mask, &table->mask_list, list)
481 num++;
482
483 return num;
484}
485
Pravin B Shelarb637e492013-10-04 00:14:23 -0700486static struct table_instance *table_instance_expand(struct table_instance *ti)
487{
488 return table_instance_rehash(ti, ti->n_buckets * 2);
Pravin B Shelare6445712013-10-03 18:16:47 -0700489}
490
Pravin B Shelare6445712013-10-03 18:16:47 -0700491void ovs_flow_tbl_remove(struct flow_table *table, struct sw_flow *flow)
492{
Pravin B Shelarb637e492013-10-04 00:14:23 -0700493 struct table_instance *ti = ovsl_dereference(table->ti);
494
Pravin B Shelare6445712013-10-03 18:16:47 -0700495 BUG_ON(table->count == 0);
Pravin B Shelarb637e492013-10-04 00:14:23 -0700496 hlist_del_rcu(&flow->hash_node[ti->node_ver]);
Pravin B Shelare6445712013-10-03 18:16:47 -0700497 table->count--;
498}
499
Pravin B Shelar618ed0c2013-10-04 00:17:42 -0700500static struct sw_flow_mask *mask_alloc(void)
Pravin B Shelare6445712013-10-03 18:16:47 -0700501{
502 struct sw_flow_mask *mask;
503
504 mask = kmalloc(sizeof(*mask), GFP_KERNEL);
505 if (mask)
Andy Zhoue80857c2014-01-21 09:31:04 -0800506 mask->ref_count = 1;
Pravin B Shelare6445712013-10-03 18:16:47 -0700507
508 return mask;
509}
510
Pravin B Shelare6445712013-10-03 18:16:47 -0700511static bool mask_equal(const struct sw_flow_mask *a,
512 const struct sw_flow_mask *b)
513{
514 u8 *a_ = (u8 *)&a->key + a->range.start;
515 u8 *b_ = (u8 *)&b->key + b->range.start;
516
517 return (a->range.end == b->range.end)
518 && (a->range.start == b->range.start)
519 && (memcmp(a_, b_, range_n_bytes(&a->range)) == 0);
520}
521
Pravin B Shelar618ed0c2013-10-04 00:17:42 -0700522static struct sw_flow_mask *flow_mask_find(const struct flow_table *tbl,
Pravin B Shelare6445712013-10-03 18:16:47 -0700523 const struct sw_flow_mask *mask)
524{
525 struct list_head *ml;
526
Pravin B Shelarb637e492013-10-04 00:14:23 -0700527 list_for_each(ml, &tbl->mask_list) {
Pravin B Shelare6445712013-10-03 18:16:47 -0700528 struct sw_flow_mask *m;
529 m = container_of(ml, struct sw_flow_mask, list);
530 if (mask_equal(mask, m))
531 return m;
532 }
533
534 return NULL;
535}
536
Ben Pfaffd1211902013-11-25 10:40:51 -0800537/* Add 'mask' into the mask list, if it is not already there. */
Pravin B Shelar618ed0c2013-10-04 00:17:42 -0700538static int flow_mask_insert(struct flow_table *tbl, struct sw_flow *flow,
539 struct sw_flow_mask *new)
Pravin B Shelare6445712013-10-03 18:16:47 -0700540{
Pravin B Shelar618ed0c2013-10-04 00:17:42 -0700541 struct sw_flow_mask *mask;
542 mask = flow_mask_find(tbl, new);
543 if (!mask) {
544 /* Allocate a new mask if none exsits. */
545 mask = mask_alloc();
546 if (!mask)
547 return -ENOMEM;
548 mask->key = new->key;
549 mask->range = new->range;
550 list_add_rcu(&mask->list, &tbl->mask_list);
Andy Zhoue80857c2014-01-21 09:31:04 -0800551 } else {
552 BUG_ON(!mask->ref_count);
553 mask->ref_count++;
Pravin B Shelar618ed0c2013-10-04 00:17:42 -0700554 }
555
Pravin B Shelar618ed0c2013-10-04 00:17:42 -0700556 flow->mask = mask;
557 return 0;
558}
559
560int ovs_flow_tbl_insert(struct flow_table *table, struct sw_flow *flow,
561 struct sw_flow_mask *mask)
562{
563 struct table_instance *new_ti = NULL;
564 struct table_instance *ti;
565 int err;
566
567 err = flow_mask_insert(table, flow, mask);
568 if (err)
569 return err;
570
571 flow->hash = flow_hash(&flow->key, flow->mask->range.start,
572 flow->mask->range.end);
573 ti = ovsl_dereference(table->ti);
574 table_instance_insert(ti, flow);
575 table->count++;
576
577 /* Expand table, if necessary, to make room. */
578 if (table->count > ti->n_buckets)
579 new_ti = table_instance_expand(ti);
580 else if (time_after(jiffies, table->last_rehash + REHASH_INTERVAL))
581 new_ti = table_instance_rehash(ti, ti->n_buckets);
582
583 if (new_ti) {
584 rcu_assign_pointer(table->ti, new_ti);
585 table_instance_destroy(ti, true);
586 table->last_rehash = jiffies;
587 }
588 return 0;
Pravin B Shelare6445712013-10-03 18:16:47 -0700589}
590
591/* Initializes the flow module.
592 * Returns zero if successful or a negative error code. */
593int ovs_flow_init(void)
594{
595 BUILD_BUG_ON(__alignof__(struct sw_flow_key) % __alignof__(long));
596 BUILD_BUG_ON(sizeof(struct sw_flow_key) % sizeof(long));
597
598 flow_cache = kmem_cache_create("sw_flow", sizeof(struct sw_flow), 0,
599 0, NULL);
600 if (flow_cache == NULL)
601 return -ENOMEM;
602
603 return 0;
604}
605
606/* Uninitializes the flow module. */
607void ovs_flow_exit(void)
608{
609 kmem_cache_destroy(flow_cache);
610}