2 * Copyright (c) 2007-2014 Nicira, Inc.
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.
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.
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
21 #include "flow_netlink.h"
22 #include <linux/uaccess.h>
23 #include <linux/netdevice.h>
24 #include <linux/etherdevice.h>
25 #include <linux/if_ether.h>
26 #include <linux/if_vlan.h>
27 #include <net/llc_pdu.h>
28 #include <linux/kernel.h>
29 #include <linux/jhash.h>
30 #include <linux/jiffies.h>
31 #include <linux/llc.h>
32 #include <linux/module.h>
34 #include <linux/rcupdate.h>
35 #include <linux/if_arp.h>
37 #include <linux/ipv6.h>
38 #include <linux/sctp.h>
39 #include <linux/tcp.h>
40 #include <linux/udp.h>
41 #include <linux/icmp.h>
42 #include <linux/icmpv6.h>
43 #include <linux/rculist.h>
46 #include <net/ndisc.h>
48 #define TBL_MIN_BUCKETS 1024
49 #define REHASH_INTERVAL (10 * 60 * HZ)
51 static struct kmem_cache
*flow_cache
;
52 struct kmem_cache
*flow_stats_cache __read_mostly
;
54 static u16
range_n_bytes(const struct sw_flow_key_range
*range
)
56 return range
->end
- range
->start
;
59 void ovs_flow_mask_key(struct sw_flow_key
*dst
, const struct sw_flow_key
*src
,
60 bool full
, const struct sw_flow_mask
*mask
)
62 int start
= full
? 0 : mask
->range
.start
;
63 int len
= full
? sizeof *dst
: range_n_bytes(&mask
->range
);
64 const long *m
= (const long *)((const u8
*)&mask
->key
+ start
);
65 const long *s
= (const long *)((const u8
*)src
+ start
);
66 long *d
= (long *)((u8
*)dst
+ start
);
69 /* If 'full' is true then all of 'dst' is fully initialized. Otherwise,
70 * if 'full' is false the memory outside of the 'mask->range' is left
71 * uninitialized. This can be used as an optimization when further
72 * operations on 'dst' only use contents within 'mask->range'.
74 for (i
= 0; i
< len
; i
+= sizeof(long))
78 struct sw_flow
*ovs_flow_alloc(void)
81 struct flow_stats
*stats
;
84 flow
= kmem_cache_alloc(flow_cache
, GFP_KERNEL
);
86 return ERR_PTR(-ENOMEM
);
90 flow
->id
.unmasked_key
= NULL
;
91 flow
->id
.ufid_len
= 0;
92 flow
->stats_last_writer
= NUMA_NO_NODE
;
94 /* Initialize the default stat node. */
95 stats
= kmem_cache_alloc_node(flow_stats_cache
,
96 GFP_KERNEL
| __GFP_ZERO
, 0);
100 spin_lock_init(&stats
->lock
);
102 RCU_INIT_POINTER(flow
->stats
[0], stats
);
106 RCU_INIT_POINTER(flow
->stats
[node
], NULL
);
110 kmem_cache_free(flow_cache
, flow
);
111 return ERR_PTR(-ENOMEM
);
114 int ovs_flow_tbl_count(const struct flow_table
*table
)
119 static struct flex_array
*alloc_buckets(unsigned int n_buckets
)
121 struct flex_array
*buckets
;
124 buckets
= flex_array_alloc(sizeof(struct hlist_head
),
125 n_buckets
, GFP_KERNEL
);
129 err
= flex_array_prealloc(buckets
, 0, n_buckets
, GFP_KERNEL
);
131 flex_array_free(buckets
);
135 for (i
= 0; i
< n_buckets
; i
++)
136 INIT_HLIST_HEAD((struct hlist_head
*)
137 flex_array_get(buckets
, i
));
142 static void flow_free(struct sw_flow
*flow
)
146 if (ovs_identifier_is_key(&flow
->id
))
147 kfree(flow
->id
.unmasked_key
);
149 ovs_nla_free_flow_actions((struct sw_flow_actions __force
*)flow
->sf_acts
);
151 if (flow
->stats
[node
])
152 kmem_cache_free(flow_stats_cache
,
153 (struct flow_stats __force
*)flow
->stats
[node
]);
154 kmem_cache_free(flow_cache
, flow
);
157 static void rcu_free_flow_callback(struct rcu_head
*rcu
)
159 struct sw_flow
*flow
= container_of(rcu
, struct sw_flow
, rcu
);
164 void ovs_flow_free(struct sw_flow
*flow
, bool deferred
)
170 call_rcu(&flow
->rcu
, rcu_free_flow_callback
);
175 static void free_buckets(struct flex_array
*buckets
)
177 flex_array_free(buckets
);
181 static void __table_instance_destroy(struct table_instance
*ti
)
183 free_buckets(ti
->buckets
);
187 static struct table_instance
*table_instance_alloc(int new_size
)
189 struct table_instance
*ti
= kmalloc(sizeof(*ti
), GFP_KERNEL
);
194 ti
->buckets
= alloc_buckets(new_size
);
200 ti
->n_buckets
= new_size
;
202 ti
->keep_flows
= false;
203 get_random_bytes(&ti
->hash_seed
, sizeof(u32
));
208 int ovs_flow_tbl_init(struct flow_table
*table
)
210 struct table_instance
*ti
, *ufid_ti
;
212 ti
= table_instance_alloc(TBL_MIN_BUCKETS
);
217 ufid_ti
= table_instance_alloc(TBL_MIN_BUCKETS
);
221 rcu_assign_pointer(table
->ti
, ti
);
222 rcu_assign_pointer(table
->ufid_ti
, ufid_ti
);
223 INIT_LIST_HEAD(&table
->mask_list
);
224 table
->last_rehash
= jiffies
;
226 table
->ufid_count
= 0;
230 __table_instance_destroy(ti
);
234 static void flow_tbl_destroy_rcu_cb(struct rcu_head
*rcu
)
236 struct table_instance
*ti
= container_of(rcu
, struct table_instance
, rcu
);
238 __table_instance_destroy(ti
);
241 static void table_instance_destroy(struct table_instance
*ti
,
242 struct table_instance
*ufid_ti
,
254 for (i
= 0; i
< ti
->n_buckets
; i
++) {
255 struct sw_flow
*flow
;
256 struct hlist_head
*head
= flex_array_get(ti
->buckets
, i
);
257 struct hlist_node
*n
;
258 int ver
= ti
->node_ver
;
259 int ufid_ver
= ufid_ti
->node_ver
;
261 hlist_for_each_entry_safe(flow
, n
, head
, flow_table
.node
[ver
]) {
262 hlist_del_rcu(&flow
->flow_table
.node
[ver
]);
263 if (ovs_identifier_is_ufid(&flow
->id
))
264 hlist_del_rcu(&flow
->ufid_table
.node
[ufid_ver
]);
265 ovs_flow_free(flow
, deferred
);
271 call_rcu(&ti
->rcu
, flow_tbl_destroy_rcu_cb
);
272 call_rcu(&ufid_ti
->rcu
, flow_tbl_destroy_rcu_cb
);
274 __table_instance_destroy(ti
);
275 __table_instance_destroy(ufid_ti
);
279 /* No need for locking this function is called from RCU callback or
282 void ovs_flow_tbl_destroy(struct flow_table
*table
)
284 struct table_instance
*ti
= rcu_dereference_raw(table
->ti
);
285 struct table_instance
*ufid_ti
= rcu_dereference_raw(table
->ufid_ti
);
287 table_instance_destroy(ti
, ufid_ti
, false);
290 struct sw_flow
*ovs_flow_tbl_dump_next(struct table_instance
*ti
,
291 u32
*bucket
, u32
*last
)
293 struct sw_flow
*flow
;
294 struct hlist_head
*head
;
299 while (*bucket
< ti
->n_buckets
) {
301 head
= flex_array_get(ti
->buckets
, *bucket
);
302 hlist_for_each_entry_rcu(flow
, head
, flow_table
.node
[ver
]) {
317 static struct hlist_head
*find_bucket(struct table_instance
*ti
, u32 hash
)
319 hash
= jhash_1word(hash
, ti
->hash_seed
);
320 return flex_array_get(ti
->buckets
,
321 (hash
& (ti
->n_buckets
- 1)));
324 static void table_instance_insert(struct table_instance
*ti
,
325 struct sw_flow
*flow
)
327 struct hlist_head
*head
;
329 head
= find_bucket(ti
, flow
->flow_table
.hash
);
330 hlist_add_head_rcu(&flow
->flow_table
.node
[ti
->node_ver
], head
);
333 static void ufid_table_instance_insert(struct table_instance
*ti
,
334 struct sw_flow
*flow
)
336 struct hlist_head
*head
;
338 head
= find_bucket(ti
, flow
->ufid_table
.hash
);
339 hlist_add_head_rcu(&flow
->ufid_table
.node
[ti
->node_ver
], head
);
342 static void flow_table_copy_flows(struct table_instance
*old
,
343 struct table_instance
*new, bool ufid
)
348 old_ver
= old
->node_ver
;
349 new->node_ver
= !old_ver
;
351 /* Insert in new table. */
352 for (i
= 0; i
< old
->n_buckets
; i
++) {
353 struct sw_flow
*flow
;
354 struct hlist_head
*head
;
356 head
= flex_array_get(old
->buckets
, i
);
359 hlist_for_each_entry(flow
, head
,
360 ufid_table
.node
[old_ver
])
361 ufid_table_instance_insert(new, flow
);
363 hlist_for_each_entry(flow
, head
,
364 flow_table
.node
[old_ver
])
365 table_instance_insert(new, flow
);
368 old
->keep_flows
= true;
371 static struct table_instance
*table_instance_rehash(struct table_instance
*ti
,
372 int n_buckets
, bool ufid
)
374 struct table_instance
*new_ti
;
376 new_ti
= table_instance_alloc(n_buckets
);
380 flow_table_copy_flows(ti
, new_ti
, ufid
);
385 int ovs_flow_tbl_flush(struct flow_table
*flow_table
)
387 struct table_instance
*old_ti
, *new_ti
;
388 struct table_instance
*old_ufid_ti
, *new_ufid_ti
;
390 new_ti
= table_instance_alloc(TBL_MIN_BUCKETS
);
393 new_ufid_ti
= table_instance_alloc(TBL_MIN_BUCKETS
);
397 old_ti
= ovsl_dereference(flow_table
->ti
);
398 old_ufid_ti
= ovsl_dereference(flow_table
->ufid_ti
);
400 rcu_assign_pointer(flow_table
->ti
, new_ti
);
401 rcu_assign_pointer(flow_table
->ufid_ti
, new_ufid_ti
);
402 flow_table
->last_rehash
= jiffies
;
403 flow_table
->count
= 0;
404 flow_table
->ufid_count
= 0;
406 table_instance_destroy(old_ti
, old_ufid_ti
, true);
410 __table_instance_destroy(new_ti
);
414 static u32
flow_hash(const struct sw_flow_key
*key
,
415 const struct sw_flow_key_range
*range
)
417 int key_start
= range
->start
;
418 int key_end
= range
->end
;
419 const u32
*hash_key
= (const u32
*)((const u8
*)key
+ key_start
);
420 int hash_u32s
= (key_end
- key_start
) >> 2;
422 /* Make sure number of hash bytes are multiple of u32. */
423 BUILD_BUG_ON(sizeof(long) % sizeof(u32
));
425 return jhash2(hash_key
, hash_u32s
, 0);
428 static int flow_key_start(const struct sw_flow_key
*key
)
430 if (key
->tun_key
.u
.ipv4
.dst
)
433 return rounddown(offsetof(struct sw_flow_key
, phy
),
437 static bool cmp_key(const struct sw_flow_key
*key1
,
438 const struct sw_flow_key
*key2
,
439 int key_start
, int key_end
)
441 const long *cp1
= (const long *)((const u8
*)key1
+ key_start
);
442 const long *cp2
= (const long *)((const u8
*)key2
+ key_start
);
446 for (i
= key_start
; i
< key_end
; i
+= sizeof(long))
447 diffs
|= *cp1
++ ^ *cp2
++;
452 static bool flow_cmp_masked_key(const struct sw_flow
*flow
,
453 const struct sw_flow_key
*key
,
454 const struct sw_flow_key_range
*range
)
456 return cmp_key(&flow
->key
, key
, range
->start
, range
->end
);
459 static bool ovs_flow_cmp_unmasked_key(const struct sw_flow
*flow
,
460 const struct sw_flow_match
*match
)
462 struct sw_flow_key
*key
= match
->key
;
463 int key_start
= flow_key_start(key
);
464 int key_end
= match
->range
.end
;
466 BUG_ON(ovs_identifier_is_ufid(&flow
->id
));
467 return cmp_key(flow
->id
.unmasked_key
, key
, key_start
, key_end
);
470 static struct sw_flow
*masked_flow_lookup(struct table_instance
*ti
,
471 const struct sw_flow_key
*unmasked
,
472 const struct sw_flow_mask
*mask
)
474 struct sw_flow
*flow
;
475 struct hlist_head
*head
;
477 struct sw_flow_key masked_key
;
479 ovs_flow_mask_key(&masked_key
, unmasked
, false, mask
);
480 hash
= flow_hash(&masked_key
, &mask
->range
);
481 head
= find_bucket(ti
, hash
);
482 hlist_for_each_entry_rcu(flow
, head
, flow_table
.node
[ti
->node_ver
]) {
483 if (flow
->mask
== mask
&& flow
->flow_table
.hash
== hash
&&
484 flow_cmp_masked_key(flow
, &masked_key
, &mask
->range
))
490 struct sw_flow
*ovs_flow_tbl_lookup_stats(struct flow_table
*tbl
,
491 const struct sw_flow_key
*key
,
494 struct table_instance
*ti
= rcu_dereference_ovsl(tbl
->ti
);
495 struct sw_flow_mask
*mask
;
496 struct sw_flow
*flow
;
499 list_for_each_entry_rcu(mask
, &tbl
->mask_list
, list
) {
501 flow
= masked_flow_lookup(ti
, key
, mask
);
502 if (flow
) /* Found */
508 struct sw_flow
*ovs_flow_tbl_lookup(struct flow_table
*tbl
,
509 const struct sw_flow_key
*key
)
511 u32 __always_unused n_mask_hit
;
513 return ovs_flow_tbl_lookup_stats(tbl
, key
, &n_mask_hit
);
516 struct sw_flow
*ovs_flow_tbl_lookup_exact(struct flow_table
*tbl
,
517 const struct sw_flow_match
*match
)
519 struct table_instance
*ti
= rcu_dereference_ovsl(tbl
->ti
);
520 struct sw_flow_mask
*mask
;
521 struct sw_flow
*flow
;
523 /* Always called under ovs-mutex. */
524 list_for_each_entry(mask
, &tbl
->mask_list
, list
) {
525 flow
= masked_flow_lookup(ti
, match
->key
, mask
);
526 if (flow
&& ovs_identifier_is_key(&flow
->id
) &&
527 ovs_flow_cmp_unmasked_key(flow
, match
))
533 static u32
ufid_hash(const struct sw_flow_id
*sfid
)
535 return jhash(sfid
->ufid
, sfid
->ufid_len
, 0);
538 static bool ovs_flow_cmp_ufid(const struct sw_flow
*flow
,
539 const struct sw_flow_id
*sfid
)
541 if (flow
->id
.ufid_len
!= sfid
->ufid_len
)
544 return !memcmp(flow
->id
.ufid
, sfid
->ufid
, sfid
->ufid_len
);
547 bool ovs_flow_cmp(const struct sw_flow
*flow
, const struct sw_flow_match
*match
)
549 if (ovs_identifier_is_ufid(&flow
->id
))
550 return flow_cmp_masked_key(flow
, match
->key
, &match
->range
);
552 return ovs_flow_cmp_unmasked_key(flow
, match
);
555 struct sw_flow
*ovs_flow_tbl_lookup_ufid(struct flow_table
*tbl
,
556 const struct sw_flow_id
*ufid
)
558 struct table_instance
*ti
= rcu_dereference_ovsl(tbl
->ufid_ti
);
559 struct sw_flow
*flow
;
560 struct hlist_head
*head
;
563 hash
= ufid_hash(ufid
);
564 head
= find_bucket(ti
, hash
);
565 hlist_for_each_entry_rcu(flow
, head
, ufid_table
.node
[ti
->node_ver
]) {
566 if (flow
->ufid_table
.hash
== hash
&&
567 ovs_flow_cmp_ufid(flow
, ufid
))
573 int ovs_flow_tbl_num_masks(const struct flow_table
*table
)
575 struct sw_flow_mask
*mask
;
578 list_for_each_entry(mask
, &table
->mask_list
, list
)
584 static struct table_instance
*table_instance_expand(struct table_instance
*ti
,
587 return table_instance_rehash(ti
, ti
->n_buckets
* 2, ufid
);
590 /* Remove 'mask' from the mask list, if it is not needed any more. */
591 static void flow_mask_remove(struct flow_table
*tbl
, struct sw_flow_mask
*mask
)
594 /* ovs-lock is required to protect mask-refcount and
598 BUG_ON(!mask
->ref_count
);
601 if (!mask
->ref_count
) {
602 list_del_rcu(&mask
->list
);
603 kfree_rcu(mask
, rcu
);
608 /* Must be called with OVS mutex held. */
609 void ovs_flow_tbl_remove(struct flow_table
*table
, struct sw_flow
*flow
)
611 struct table_instance
*ti
= ovsl_dereference(table
->ti
);
612 struct table_instance
*ufid_ti
= ovsl_dereference(table
->ufid_ti
);
614 BUG_ON(table
->count
== 0);
615 hlist_del_rcu(&flow
->flow_table
.node
[ti
->node_ver
]);
617 if (ovs_identifier_is_ufid(&flow
->id
)) {
618 hlist_del_rcu(&flow
->ufid_table
.node
[ufid_ti
->node_ver
]);
622 /* RCU delete the mask. 'flow->mask' is not NULLed, as it should be
623 * accessible as long as the RCU read lock is held.
625 flow_mask_remove(table
, flow
->mask
);
628 static struct sw_flow_mask
*mask_alloc(void)
630 struct sw_flow_mask
*mask
;
632 mask
= kmalloc(sizeof(*mask
), GFP_KERNEL
);
639 static bool mask_equal(const struct sw_flow_mask
*a
,
640 const struct sw_flow_mask
*b
)
642 const u8
*a_
= (const u8
*)&a
->key
+ a
->range
.start
;
643 const u8
*b_
= (const u8
*)&b
->key
+ b
->range
.start
;
645 return (a
->range
.end
== b
->range
.end
)
646 && (a
->range
.start
== b
->range
.start
)
647 && (memcmp(a_
, b_
, range_n_bytes(&a
->range
)) == 0);
650 static struct sw_flow_mask
*flow_mask_find(const struct flow_table
*tbl
,
651 const struct sw_flow_mask
*mask
)
653 struct list_head
*ml
;
655 list_for_each(ml
, &tbl
->mask_list
) {
656 struct sw_flow_mask
*m
;
657 m
= container_of(ml
, struct sw_flow_mask
, list
);
658 if (mask_equal(mask
, m
))
665 /* Add 'mask' into the mask list, if it is not already there. */
666 static int flow_mask_insert(struct flow_table
*tbl
, struct sw_flow
*flow
,
667 const struct sw_flow_mask
*new)
669 struct sw_flow_mask
*mask
;
670 mask
= flow_mask_find(tbl
, new);
672 /* Allocate a new mask if none exsits. */
676 mask
->key
= new->key
;
677 mask
->range
= new->range
;
678 list_add_rcu(&mask
->list
, &tbl
->mask_list
);
680 BUG_ON(!mask
->ref_count
);
688 /* Must be called with OVS mutex held. */
689 static void flow_key_insert(struct flow_table
*table
, struct sw_flow
*flow
)
691 struct table_instance
*new_ti
= NULL
;
692 struct table_instance
*ti
;
694 flow
->flow_table
.hash
= flow_hash(&flow
->key
, &flow
->mask
->range
);
695 ti
= ovsl_dereference(table
->ti
);
696 table_instance_insert(ti
, flow
);
699 /* Expand table, if necessary, to make room. */
700 if (table
->count
> ti
->n_buckets
)
701 new_ti
= table_instance_expand(ti
, false);
702 else if (time_after(jiffies
, table
->last_rehash
+ REHASH_INTERVAL
))
703 new_ti
= table_instance_rehash(ti
, ti
->n_buckets
, false);
706 rcu_assign_pointer(table
->ti
, new_ti
);
707 call_rcu(&ti
->rcu
, flow_tbl_destroy_rcu_cb
);
708 table
->last_rehash
= jiffies
;
712 /* Must be called with OVS mutex held. */
713 static void flow_ufid_insert(struct flow_table
*table
, struct sw_flow
*flow
)
715 struct table_instance
*ti
;
717 flow
->ufid_table
.hash
= ufid_hash(&flow
->id
);
718 ti
= ovsl_dereference(table
->ufid_ti
);
719 ufid_table_instance_insert(ti
, flow
);
722 /* Expand table, if necessary, to make room. */
723 if (table
->ufid_count
> ti
->n_buckets
) {
724 struct table_instance
*new_ti
;
726 new_ti
= table_instance_expand(ti
, true);
728 rcu_assign_pointer(table
->ufid_ti
, new_ti
);
729 call_rcu(&ti
->rcu
, flow_tbl_destroy_rcu_cb
);
734 /* Must be called with OVS mutex held. */
735 int ovs_flow_tbl_insert(struct flow_table
*table
, struct sw_flow
*flow
,
736 const struct sw_flow_mask
*mask
)
740 err
= flow_mask_insert(table
, flow
, mask
);
743 flow_key_insert(table
, flow
);
744 if (ovs_identifier_is_ufid(&flow
->id
))
745 flow_ufid_insert(table
, flow
);
750 /* Initializes the flow module.
751 * Returns zero if successful or a negative error code. */
752 int ovs_flow_init(void)
754 BUILD_BUG_ON(__alignof__(struct sw_flow_key
) % __alignof__(long));
755 BUILD_BUG_ON(sizeof(struct sw_flow_key
) % sizeof(long));
757 flow_cache
= kmem_cache_create("sw_flow", sizeof(struct sw_flow
)
759 * sizeof(struct flow_stats
*)),
761 if (flow_cache
== NULL
)
765 = kmem_cache_create("sw_flow_stats", sizeof(struct flow_stats
),
766 0, SLAB_HWCACHE_ALIGN
, NULL
);
767 if (flow_stats_cache
== NULL
) {
768 kmem_cache_destroy(flow_cache
);
776 /* Uninitializes the flow module. */
777 void ovs_flow_exit(void)
779 kmem_cache_destroy(flow_stats_cache
);
780 kmem_cache_destroy(flow_cache
);