2 * Copyright (c) 2007-2013 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 <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>
28 #include <linux/hash.h>
29 #include <linux/jiffies.h>
30 #include <linux/llc.h>
31 #include <linux/module.h>
33 #include <linux/rcupdate.h>
34 #include <linux/if_arp.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>
45 #include <net/ndisc.h>
49 #define TBL_MIN_BUCKETS 1024
50 #define REHASH_INTERVAL (10 * 60 * HZ)
52 #define MC_HASH_SHIFT 8
53 #define MC_HASH_ENTRIES (1u << MC_HASH_SHIFT)
54 #define MC_HASH_SEGS ((sizeof(uint32_t) * 8) / MC_HASH_SHIFT)
56 static struct kmem_cache
*flow_cache
;
57 struct kmem_cache
*flow_stats_cache __read_mostly
;
59 static u16
range_n_bytes(const struct sw_flow_key_range
*range
)
61 return range
->end
- range
->start
;
64 void ovs_flow_mask_key(struct sw_flow_key
*dst
, const struct sw_flow_key
*src
,
65 const struct sw_flow_mask
*mask
)
67 const long *m
= (const long *)((const u8
*)&mask
->key
+
69 const long *s
= (const long *)((const u8
*)src
+
71 long *d
= (long *)((u8
*)dst
+ mask
->range
.start
);
74 /* The memory outside of the 'mask->range' are not set since
75 * further operations on 'dst' only uses contents within
78 for (i
= 0; i
< range_n_bytes(&mask
->range
); i
+= sizeof(long))
82 struct sw_flow
*ovs_flow_alloc(void)
85 struct flow_stats
*stats
;
88 flow
= kmem_cache_alloc(flow_cache
, GFP_KERNEL
);
90 return ERR_PTR(-ENOMEM
);
94 flow
->stats_last_writer
= NUMA_NO_NODE
;
96 /* Initialize the default stat node. */
97 stats
= kmem_cache_alloc_node(flow_stats_cache
,
98 GFP_KERNEL
| __GFP_ZERO
, 0);
102 spin_lock_init(&stats
->lock
);
104 RCU_INIT_POINTER(flow
->stats
[0], stats
);
108 RCU_INIT_POINTER(flow
->stats
[node
], NULL
);
112 kmem_cache_free(flow_cache
, flow
);
113 return ERR_PTR(-ENOMEM
);
116 int ovs_flow_tbl_count(struct flow_table
*table
)
121 static struct flex_array
*alloc_buckets(unsigned int n_buckets
)
123 struct flex_array
*buckets
;
126 buckets
= flex_array_alloc(sizeof(struct hlist_head
),
127 n_buckets
, GFP_KERNEL
);
131 err
= flex_array_prealloc(buckets
, 0, n_buckets
, GFP_KERNEL
);
133 flex_array_free(buckets
);
137 for (i
= 0; i
< n_buckets
; i
++)
138 INIT_HLIST_HEAD((struct hlist_head
*)
139 flex_array_get(buckets
, i
));
144 static void flow_free(struct sw_flow
*flow
)
148 kfree((struct sw_flow_actions __force
*)flow
->sf_acts
);
150 if (flow
->stats
[node
])
151 kmem_cache_free(flow_stats_cache
,
152 (struct flow_stats __force
*)flow
->stats
[node
]);
153 kmem_cache_free(flow_cache
, flow
);
156 static void rcu_free_flow_callback(struct rcu_head
*rcu
)
158 struct sw_flow
*flow
= container_of(rcu
, struct sw_flow
, rcu
);
163 static void rcu_free_sw_flow_mask_cb(struct rcu_head
*rcu
)
165 struct sw_flow_mask
*mask
= container_of(rcu
, struct sw_flow_mask
, rcu
);
170 void ovs_flow_free(struct sw_flow
*flow
, bool deferred
)
176 call_rcu(&flow
->rcu
, rcu_free_flow_callback
);
181 static void free_buckets(struct flex_array
*buckets
)
183 flex_array_free(buckets
);
187 static void __table_instance_destroy(struct table_instance
*ti
)
189 free_buckets(ti
->buckets
);
193 static struct table_instance
*table_instance_alloc(int new_size
)
195 struct table_instance
*ti
= kmalloc(sizeof(*ti
), GFP_KERNEL
);
200 ti
->buckets
= alloc_buckets(new_size
);
206 ti
->n_buckets
= new_size
;
208 ti
->keep_flows
= false;
209 get_random_bytes(&ti
->hash_seed
, sizeof(u32
));
214 int ovs_flow_tbl_init(struct flow_table
*table
)
216 struct table_instance
*ti
;
218 table
->mask_cache
= __alloc_percpu(sizeof(struct mask_cache_entry
) *
219 MC_HASH_ENTRIES
, __alignof__(struct mask_cache_entry
));
220 if (!table
->mask_cache
)
223 ti
= table_instance_alloc(TBL_MIN_BUCKETS
);
225 free_percpu(table
->mask_cache
);
229 rcu_assign_pointer(table
->ti
, ti
);
230 INIT_LIST_HEAD(&table
->mask_list
);
231 table
->last_rehash
= jiffies
;
236 static void flow_tbl_destroy_rcu_cb(struct rcu_head
*rcu
)
238 struct table_instance
*ti
= container_of(rcu
, struct table_instance
, rcu
);
240 __table_instance_destroy(ti
);
243 static void table_instance_destroy(struct table_instance
*ti
, bool deferred
)
253 for (i
= 0; i
< ti
->n_buckets
; i
++) {
254 struct sw_flow
*flow
;
255 struct hlist_head
*head
= flex_array_get(ti
->buckets
, i
);
256 struct hlist_node
*n
;
257 int ver
= ti
->node_ver
;
259 hlist_for_each_entry_safe(flow
, n
, head
, hash_node
[ver
]) {
260 hlist_del_rcu(&flow
->hash_node
[ver
]);
261 ovs_flow_free(flow
, deferred
);
267 call_rcu(&ti
->rcu
, flow_tbl_destroy_rcu_cb
);
269 __table_instance_destroy(ti
);
272 /* No need for locking this function is called from RCU callback or
274 void ovs_flow_tbl_destroy(struct flow_table
*table
)
276 struct table_instance
*ti
= (struct table_instance __force
*)table
->ti
;
278 free_percpu(table
->mask_cache
);
279 table_instance_destroy(ti
, false);
282 struct sw_flow
*ovs_flow_tbl_dump_next(struct table_instance
*ti
,
283 u32
*bucket
, u32
*last
)
285 struct sw_flow
*flow
;
286 struct hlist_head
*head
;
291 while (*bucket
< ti
->n_buckets
) {
293 head
= flex_array_get(ti
->buckets
, *bucket
);
294 hlist_for_each_entry_rcu(flow
, head
, hash_node
[ver
]) {
309 static struct hlist_head
*find_bucket(struct table_instance
*ti
, u32 hash
)
311 hash
= jhash_1word(hash
, ti
->hash_seed
);
312 return flex_array_get(ti
->buckets
,
313 (hash
& (ti
->n_buckets
- 1)));
316 static void table_instance_insert(struct table_instance
*ti
, struct sw_flow
*flow
)
318 struct hlist_head
*head
;
320 head
= find_bucket(ti
, flow
->hash
);
321 hlist_add_head_rcu(&flow
->hash_node
[ti
->node_ver
], head
);
324 static void flow_table_copy_flows(struct table_instance
*old
,
325 struct table_instance
*new)
330 old_ver
= old
->node_ver
;
331 new->node_ver
= !old_ver
;
333 /* Insert in new table. */
334 for (i
= 0; i
< old
->n_buckets
; i
++) {
335 struct sw_flow
*flow
;
336 struct hlist_head
*head
;
338 head
= flex_array_get(old
->buckets
, i
);
340 hlist_for_each_entry(flow
, head
, hash_node
[old_ver
])
341 table_instance_insert(new, flow
);
344 old
->keep_flows
= true;
347 static struct table_instance
*table_instance_rehash(struct table_instance
*ti
,
350 struct table_instance
*new_ti
;
352 new_ti
= table_instance_alloc(n_buckets
);
356 flow_table_copy_flows(ti
, new_ti
);
361 int ovs_flow_tbl_flush(struct flow_table
*flow_table
)
363 struct table_instance
*old_ti
;
364 struct table_instance
*new_ti
;
366 old_ti
= ovsl_dereference(flow_table
->ti
);
367 new_ti
= table_instance_alloc(TBL_MIN_BUCKETS
);
371 rcu_assign_pointer(flow_table
->ti
, new_ti
);
372 flow_table
->last_rehash
= jiffies
;
373 flow_table
->count
= 0;
375 table_instance_destroy(old_ti
, true);
379 static u32
flow_hash(const struct sw_flow_key
*key
, int key_start
,
382 const u32
*hash_key
= (const u32
*)((const u8
*)key
+ key_start
);
383 int hash_u32s
= (key_end
- key_start
) >> 2;
385 /* Make sure number of hash bytes are multiple of u32. */
386 BUILD_BUG_ON(sizeof(long) % sizeof(u32
));
388 return arch_fast_hash2(hash_key
, hash_u32s
, 0);
391 static int flow_key_start(const struct sw_flow_key
*key
)
393 if (key
->tun_key
.ipv4_dst
)
396 return rounddown(offsetof(struct sw_flow_key
, phy
),
400 static bool cmp_key(const struct sw_flow_key
*key1
,
401 const struct sw_flow_key
*key2
,
402 int key_start
, int key_end
)
404 const long *cp1
= (const long *)((const u8
*)key1
+ key_start
);
405 const long *cp2
= (const long *)((const u8
*)key2
+ key_start
);
409 for (i
= key_start
; i
< key_end
; i
+= sizeof(long))
410 diffs
|= *cp1
++ ^ *cp2
++;
415 static bool flow_cmp_masked_key(const struct sw_flow
*flow
,
416 const struct sw_flow_key
*key
,
417 int key_start
, int key_end
)
419 return cmp_key(&flow
->key
, key
, key_start
, key_end
);
422 bool ovs_flow_cmp_unmasked_key(const struct sw_flow
*flow
,
423 struct sw_flow_match
*match
)
425 struct sw_flow_key
*key
= match
->key
;
426 int key_start
= flow_key_start(key
);
427 int key_end
= match
->range
.end
;
429 return cmp_key(&flow
->unmasked_key
, key
, key_start
, key_end
);
432 static struct sw_flow
*masked_flow_lookup(struct table_instance
*ti
,
433 const struct sw_flow_key
*unmasked
,
434 struct sw_flow_mask
*mask
,
437 struct sw_flow
*flow
;
438 struct hlist_head
*head
;
439 int key_start
= mask
->range
.start
;
440 int key_end
= mask
->range
.end
;
442 struct sw_flow_key masked_key
;
444 ovs_flow_mask_key(&masked_key
, unmasked
, mask
);
445 hash
= flow_hash(&masked_key
, key_start
, key_end
);
446 head
= find_bucket(ti
, hash
);
448 hlist_for_each_entry_rcu(flow
, head
, hash_node
[ti
->node_ver
]) {
449 if (flow
->mask
== mask
&& flow
->hash
== hash
&&
450 flow_cmp_masked_key(flow
, &masked_key
,
458 static struct sw_flow
*flow_lookup(struct flow_table
*tbl
,
459 struct table_instance
*ti
,
460 const struct sw_flow_key
*key
,
463 struct sw_flow_mask
*mask
;
464 struct sw_flow
*flow
;
466 list_for_each_entry_rcu(mask
, &tbl
->mask_list
, list
) {
467 flow
= masked_flow_lookup(ti
, key
, mask
, n_mask_hit
);
468 if (flow
) /* Found */
475 * mask_cache maps flow to probable mask. This cache is not tightly
476 * coupled cache, It means updates to mask list can result in inconsistent
477 * cache entry in mask cache.
478 * This is per cpu cache and is divided in MC_HASH_SEGS segments.
479 * In case of a hash collision the entry is hashed in next segment.
481 struct sw_flow
*ovs_flow_tbl_lookup_stats(struct flow_table
*tbl
,
482 const struct sw_flow_key
*key
,
486 struct table_instance
*ti
= rcu_dereference_ovsl(tbl
->ti
);
487 struct mask_cache_entry
*entries
, *ce
, *del
;
488 struct sw_flow
*flow
;
493 if (unlikely(!skb_hash
))
494 return flow_lookup(tbl
, ti
, key
, n_mask_hit
);
497 entries
= this_cpu_ptr(tbl
->mask_cache
);
499 for (seg
= 0; seg
< MC_HASH_SEGS
; seg
++) {
502 index
= hash
& (MC_HASH_ENTRIES
- 1);
503 ce
= &entries
[index
];
505 if (ce
->skb_hash
== skb_hash
) {
506 struct sw_flow_mask
*mask
;
510 list_for_each_entry_rcu(mask
, &tbl
->mask_list
, list
) {
511 if (ce
->mask_index
== i
++) {
512 flow
= masked_flow_lookup(ti
, key
, mask
,
514 if (flow
) /* Found */
524 if (!del
|| (del
->skb_hash
&& !ce
->skb_hash
)) {
528 hash
>>= MC_HASH_SHIFT
;
531 flow
= flow_lookup(tbl
, ti
, key
, n_mask_hit
);
534 del
->skb_hash
= skb_hash
;
535 del
->mask_index
= (*n_mask_hit
- 1);
540 struct sw_flow
*ovs_flow_tbl_lookup(struct flow_table
*tbl
,
541 const struct sw_flow_key
*key
)
543 struct table_instance
*ti
= rcu_dereference_ovsl(tbl
->ti
);
544 u32 __always_unused n_mask_hit
;
547 return flow_lookup(tbl
, ti
, key
, &n_mask_hit
);
550 int ovs_flow_tbl_num_masks(const struct flow_table
*table
)
552 struct sw_flow_mask
*mask
;
555 list_for_each_entry(mask
, &table
->mask_list
, list
)
561 static struct table_instance
*table_instance_expand(struct table_instance
*ti
)
563 return table_instance_rehash(ti
, ti
->n_buckets
* 2);
566 /* Remove 'mask' from the mask list, if it is not needed any more. */
567 static void flow_mask_remove(struct flow_table
*tbl
, struct sw_flow_mask
*mask
)
570 /* ovs-lock is required to protect mask-refcount and
574 BUG_ON(!mask
->ref_count
);
577 if (!mask
->ref_count
) {
578 list_del_rcu(&mask
->list
);
579 call_rcu(&mask
->rcu
, rcu_free_sw_flow_mask_cb
);
584 /* Must be called with OVS mutex held. */
585 void ovs_flow_tbl_remove(struct flow_table
*table
, struct sw_flow
*flow
)
587 struct table_instance
*ti
= ovsl_dereference(table
->ti
);
589 BUG_ON(table
->count
== 0);
590 hlist_del_rcu(&flow
->hash_node
[ti
->node_ver
]);
593 /* RCU delete the mask. 'flow->mask' is not NULLed, as it should be
594 * accessible as long as the RCU read lock is held. */
595 flow_mask_remove(table
, flow
->mask
);
598 static struct sw_flow_mask
*mask_alloc(void)
600 struct sw_flow_mask
*mask
;
602 mask
= kmalloc(sizeof(*mask
), GFP_KERNEL
);
609 static bool mask_equal(const struct sw_flow_mask
*a
,
610 const struct sw_flow_mask
*b
)
612 const u8
*a_
= (const u8
*)&a
->key
+ a
->range
.start
;
613 const u8
*b_
= (const u8
*)&b
->key
+ b
->range
.start
;
615 return (a
->range
.end
== b
->range
.end
)
616 && (a
->range
.start
== b
->range
.start
)
617 && (memcmp(a_
, b_
, range_n_bytes(&a
->range
)) == 0);
620 static struct sw_flow_mask
*flow_mask_find(const struct flow_table
*tbl
,
621 const struct sw_flow_mask
*mask
)
623 struct list_head
*ml
;
625 list_for_each(ml
, &tbl
->mask_list
) {
626 struct sw_flow_mask
*m
;
627 m
= container_of(ml
, struct sw_flow_mask
, list
);
628 if (mask_equal(mask
, m
))
635 /* Add 'mask' into the mask list, if it is not already there. */
636 static int flow_mask_insert(struct flow_table
*tbl
, struct sw_flow
*flow
,
637 struct sw_flow_mask
*new)
639 struct sw_flow_mask
*mask
;
640 mask
= flow_mask_find(tbl
, new);
642 /* Allocate a new mask if none exsits. */
646 mask
->key
= new->key
;
647 mask
->range
= new->range
;
648 list_add_tail_rcu(&mask
->list
, &tbl
->mask_list
);
650 BUG_ON(!mask
->ref_count
);
658 /* Must be called with OVS mutex held. */
659 int ovs_flow_tbl_insert(struct flow_table
*table
, struct sw_flow
*flow
,
660 struct sw_flow_mask
*mask
)
662 struct table_instance
*new_ti
= NULL
;
663 struct table_instance
*ti
;
666 err
= flow_mask_insert(table
, flow
, mask
);
670 flow
->hash
= flow_hash(&flow
->key
, flow
->mask
->range
.start
,
671 flow
->mask
->range
.end
);
672 ti
= ovsl_dereference(table
->ti
);
673 table_instance_insert(ti
, flow
);
676 /* Expand table, if necessary, to make room. */
677 if (table
->count
> ti
->n_buckets
)
678 new_ti
= table_instance_expand(ti
);
679 else if (time_after(jiffies
, table
->last_rehash
+ REHASH_INTERVAL
))
680 new_ti
= table_instance_rehash(ti
, ti
->n_buckets
);
683 rcu_assign_pointer(table
->ti
, new_ti
);
684 table_instance_destroy(ti
, true);
685 table
->last_rehash
= jiffies
;
690 /* Initializes the flow module.
691 * Returns zero if successful or a negative error code. */
692 int ovs_flow_init(void)
694 BUILD_BUG_ON(__alignof__(struct sw_flow_key
) % __alignof__(long));
695 BUILD_BUG_ON(sizeof(struct sw_flow_key
) % sizeof(long));
697 flow_cache
= kmem_cache_create("sw_flow", sizeof(struct sw_flow
)
698 + (num_possible_nodes()
699 * sizeof(struct flow_stats
*)),
701 if (flow_cache
== NULL
)
705 = kmem_cache_create("sw_flow_stats", sizeof(struct flow_stats
),
706 0, SLAB_HWCACHE_ALIGN
, NULL
);
707 if (flow_stats_cache
== NULL
) {
708 kmem_cache_destroy(flow_cache
);
716 /* Uninitializes the flow module. */
717 void ovs_flow_exit(void)
719 kmem_cache_destroy(flow_stats_cache
);
720 kmem_cache_destroy(flow_cache
);