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/jhash.h>
29 #include <linux/jiffies.h>
30 #include <linux/llc.h>
31 #include <linux/module.h>
33 #include <linux/rcupdate.h>
34 #include <linux/cpumask.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 #include "flow_netlink.h"
50 #define TBL_MIN_BUCKETS 1024
51 #define MASK_ARRAY_SIZE_MIN 16
52 #define REHASH_INTERVAL (10 * 60 * HZ)
54 #define MC_HASH_SHIFT 8
55 #define MC_HASH_ENTRIES (1u << MC_HASH_SHIFT)
56 #define MC_HASH_SEGS ((sizeof(uint32_t) * 8) / MC_HASH_SHIFT)
58 static struct kmem_cache
*flow_cache
;
59 struct kmem_cache
*flow_stats_cache __read_mostly
;
61 static u16
range_n_bytes(const struct sw_flow_key_range
*range
)
63 return range
->end
- range
->start
;
66 void ovs_flow_mask_key(struct sw_flow_key
*dst
, const struct sw_flow_key
*src
,
67 bool full
, const struct sw_flow_mask
*mask
)
69 int start
= full
? 0 : mask
->range
.start
;
70 int len
= full
? sizeof *dst
: range_n_bytes(&mask
->range
);
71 const long *m
= (const long *)((const u8
*)&mask
->key
+ start
);
72 const long *s
= (const long *)((const u8
*)src
+ start
);
73 long *d
= (long *)((u8
*)dst
+ start
);
76 /* If 'full' is true then all of 'dst' is fully initialized. Otherwise,
77 * if 'full' is false the memory outside of the 'mask->range' is left
78 * uninitialized. This can be used as an optimization when further
79 * operations on 'dst' only use contents within 'mask->range'.
81 for (i
= 0; i
< len
; i
+= sizeof(long))
85 struct sw_flow
*ovs_flow_alloc(void)
88 struct sw_flow_stats
*stats
;
90 flow
= kmem_cache_zalloc(flow_cache
, GFP_KERNEL
);
92 return ERR_PTR(-ENOMEM
);
94 flow
->stats_last_writer
= -1;
96 /* Initialize the default stat node. */
97 stats
= kmem_cache_alloc_node(flow_stats_cache
,
98 GFP_KERNEL
| __GFP_ZERO
,
99 node_online(0) ? 0 : NUMA_NO_NODE
);
103 spin_lock_init(&stats
->lock
);
105 RCU_INIT_POINTER(flow
->stats
[0], stats
);
107 cpumask_set_cpu(0, &flow
->cpu_used_mask
);
111 kmem_cache_free(flow_cache
, flow
);
112 return ERR_PTR(-ENOMEM
);
115 int ovs_flow_tbl_count(const struct flow_table
*table
)
120 static void flow_free(struct sw_flow
*flow
)
124 if (ovs_identifier_is_key(&flow
->id
))
125 kfree(flow
->id
.unmasked_key
);
127 ovs_nla_free_flow_actions((struct sw_flow_actions __force
*)flow
->sf_acts
);
128 /* We open code this to make sure cpu 0 is always considered */
129 for (cpu
= 0; cpu
< nr_cpu_ids
; cpu
= cpumask_next(cpu
, &flow
->cpu_used_mask
))
130 if (flow
->stats
[cpu
])
131 kmem_cache_free(flow_stats_cache
,
132 rcu_dereference_raw(flow
->stats
[cpu
]));
133 kmem_cache_free(flow_cache
, flow
);
136 static void rcu_free_flow_callback(struct rcu_head
*rcu
)
138 struct sw_flow
*flow
= container_of(rcu
, struct sw_flow
, rcu
);
143 void ovs_flow_free(struct sw_flow
*flow
, bool deferred
)
149 call_rcu(&flow
->rcu
, rcu_free_flow_callback
);
154 static void __table_instance_destroy(struct table_instance
*ti
)
160 static struct table_instance
*table_instance_alloc(int new_size
)
162 struct table_instance
*ti
= kmalloc(sizeof(*ti
), GFP_KERNEL
);
168 ti
->buckets
= kvmalloc_array(new_size
, sizeof(struct hlist_head
),
175 for (i
= 0; i
< new_size
; i
++)
176 INIT_HLIST_HEAD(&ti
->buckets
[i
]);
178 ti
->n_buckets
= new_size
;
180 ti
->keep_flows
= false;
181 get_random_bytes(&ti
->hash_seed
, sizeof(u32
));
186 static void mask_array_rcu_cb(struct rcu_head
*rcu
)
188 struct mask_array
*ma
= container_of(rcu
, struct mask_array
, rcu
);
193 static struct mask_array
*tbl_mask_array_alloc(int size
)
195 struct mask_array
*new;
197 size
= max(MASK_ARRAY_SIZE_MIN
, size
);
198 new = kzalloc(sizeof(struct mask_array
) +
199 sizeof(struct sw_flow_mask
*) * size
, GFP_KERNEL
);
209 static int tbl_mask_array_realloc(struct flow_table
*tbl
, int size
)
211 struct mask_array
*old
;
212 struct mask_array
*new;
214 new = tbl_mask_array_alloc(size
);
218 old
= ovsl_dereference(tbl
->mask_array
);
222 for (i
= 0; i
< old
->max
; i
++) {
223 if (ovsl_dereference(old
->masks
[i
]))
224 new->masks
[count
++] = old
->masks
[i
];
229 rcu_assign_pointer(tbl
->mask_array
, new);
232 call_rcu(&old
->rcu
, mask_array_rcu_cb
);
237 static int tbl_mask_array_add_mask(struct flow_table
*tbl
,
238 struct sw_flow_mask
*new)
240 struct mask_array
*ma
= ovsl_dereference(tbl
->mask_array
);
241 int err
, ma_count
= READ_ONCE(ma
->count
);
243 if (ma_count
>= ma
->max
) {
244 err
= tbl_mask_array_realloc(tbl
, ma
->max
+
245 MASK_ARRAY_SIZE_MIN
);
249 ma
= ovsl_dereference(tbl
->mask_array
);
252 BUG_ON(ovsl_dereference(ma
->masks
[ma_count
]));
254 rcu_assign_pointer(ma
->masks
[ma_count
], new);
255 WRITE_ONCE(ma
->count
, ma_count
+1);
260 static void tbl_mask_array_del_mask(struct flow_table
*tbl
,
261 struct sw_flow_mask
*mask
)
263 struct mask_array
*ma
= ovsl_dereference(tbl
->mask_array
);
264 int i
, ma_count
= READ_ONCE(ma
->count
);
266 /* Remove the deleted mask pointers from the array */
267 for (i
= 0; i
< ma_count
; i
++) {
268 if (mask
== ovsl_dereference(ma
->masks
[i
]))
276 WRITE_ONCE(ma
->count
, ma_count
-1);
278 rcu_assign_pointer(ma
->masks
[i
], ma
->masks
[ma_count
-1]);
279 RCU_INIT_POINTER(ma
->masks
[ma_count
-1], NULL
);
281 kfree_rcu(mask
, rcu
);
283 /* Shrink the mask array if necessary. */
284 if (ma
->max
>= (MASK_ARRAY_SIZE_MIN
* 2) &&
285 ma_count
<= (ma
->max
/ 3))
286 tbl_mask_array_realloc(tbl
, ma
->max
/ 2);
289 /* Remove 'mask' from the mask list, if it is not needed any more. */
290 static void flow_mask_remove(struct flow_table
*tbl
, struct sw_flow_mask
*mask
)
293 /* ovs-lock is required to protect mask-refcount and
297 BUG_ON(!mask
->ref_count
);
300 if (!mask
->ref_count
)
301 tbl_mask_array_del_mask(tbl
, mask
);
305 int ovs_flow_tbl_init(struct flow_table
*table
)
307 struct table_instance
*ti
, *ufid_ti
;
308 struct mask_array
*ma
;
310 table
->mask_cache
= __alloc_percpu(sizeof(struct mask_cache_entry
) *
311 MC_HASH_ENTRIES
, __alignof__(struct mask_cache_entry
));
312 if (!table
->mask_cache
)
315 ma
= tbl_mask_array_alloc(MASK_ARRAY_SIZE_MIN
);
317 goto free_mask_cache
;
319 ti
= table_instance_alloc(TBL_MIN_BUCKETS
);
321 goto free_mask_array
;
323 ufid_ti
= table_instance_alloc(TBL_MIN_BUCKETS
);
327 rcu_assign_pointer(table
->ti
, ti
);
328 rcu_assign_pointer(table
->ufid_ti
, ufid_ti
);
329 rcu_assign_pointer(table
->mask_array
, ma
);
330 table
->last_rehash
= jiffies
;
332 table
->ufid_count
= 0;
336 __table_instance_destroy(ti
);
340 free_percpu(table
->mask_cache
);
344 static void flow_tbl_destroy_rcu_cb(struct rcu_head
*rcu
)
346 struct table_instance
*ti
= container_of(rcu
, struct table_instance
, rcu
);
348 __table_instance_destroy(ti
);
351 static void table_instance_flow_free(struct flow_table
*table
,
352 struct table_instance
*ti
,
353 struct table_instance
*ufid_ti
,
354 struct sw_flow
*flow
,
357 hlist_del_rcu(&flow
->flow_table
.node
[ti
->node_ver
]);
361 if (ovs_identifier_is_ufid(&flow
->id
)) {
362 hlist_del_rcu(&flow
->ufid_table
.node
[ufid_ti
->node_ver
]);
368 flow_mask_remove(table
, flow
->mask
);
371 static void table_instance_destroy(struct flow_table
*table
,
372 struct table_instance
*ti
,
373 struct table_instance
*ufid_ti
,
385 for (i
= 0; i
< ti
->n_buckets
; i
++) {
386 struct sw_flow
*flow
;
387 struct hlist_head
*head
= &ti
->buckets
[i
];
388 struct hlist_node
*n
;
390 hlist_for_each_entry_safe(flow
, n
, head
,
391 flow_table
.node
[ti
->node_ver
]) {
393 table_instance_flow_free(table
, ti
, ufid_ti
,
395 ovs_flow_free(flow
, deferred
);
401 call_rcu(&ti
->rcu
, flow_tbl_destroy_rcu_cb
);
402 call_rcu(&ufid_ti
->rcu
, flow_tbl_destroy_rcu_cb
);
404 __table_instance_destroy(ti
);
405 __table_instance_destroy(ufid_ti
);
409 /* No need for locking this function is called from RCU callback or
412 void ovs_flow_tbl_destroy(struct flow_table
*table
)
414 struct table_instance
*ti
= rcu_dereference_raw(table
->ti
);
415 struct table_instance
*ufid_ti
= rcu_dereference_raw(table
->ufid_ti
);
417 free_percpu(table
->mask_cache
);
418 kfree(rcu_dereference_raw(table
->mask_array
));
419 table_instance_destroy(table
, ti
, ufid_ti
, false);
422 struct sw_flow
*ovs_flow_tbl_dump_next(struct table_instance
*ti
,
423 u32
*bucket
, u32
*last
)
425 struct sw_flow
*flow
;
426 struct hlist_head
*head
;
431 while (*bucket
< ti
->n_buckets
) {
433 head
= &ti
->buckets
[*bucket
];
434 hlist_for_each_entry_rcu(flow
, head
, flow_table
.node
[ver
]) {
449 static struct hlist_head
*find_bucket(struct table_instance
*ti
, u32 hash
)
451 hash
= jhash_1word(hash
, ti
->hash_seed
);
452 return &ti
->buckets
[hash
& (ti
->n_buckets
- 1)];
455 static void table_instance_insert(struct table_instance
*ti
,
456 struct sw_flow
*flow
)
458 struct hlist_head
*head
;
460 head
= find_bucket(ti
, flow
->flow_table
.hash
);
461 hlist_add_head_rcu(&flow
->flow_table
.node
[ti
->node_ver
], head
);
464 static void ufid_table_instance_insert(struct table_instance
*ti
,
465 struct sw_flow
*flow
)
467 struct hlist_head
*head
;
469 head
= find_bucket(ti
, flow
->ufid_table
.hash
);
470 hlist_add_head_rcu(&flow
->ufid_table
.node
[ti
->node_ver
], head
);
473 static void flow_table_copy_flows(struct table_instance
*old
,
474 struct table_instance
*new, bool ufid
)
479 old_ver
= old
->node_ver
;
480 new->node_ver
= !old_ver
;
482 /* Insert in new table. */
483 for (i
= 0; i
< old
->n_buckets
; i
++) {
484 struct sw_flow
*flow
;
485 struct hlist_head
*head
= &old
->buckets
[i
];
488 hlist_for_each_entry_rcu(flow
, head
,
489 ufid_table
.node
[old_ver
])
490 ufid_table_instance_insert(new, flow
);
492 hlist_for_each_entry_rcu(flow
, head
,
493 flow_table
.node
[old_ver
])
494 table_instance_insert(new, flow
);
497 old
->keep_flows
= true;
500 static struct table_instance
*table_instance_rehash(struct table_instance
*ti
,
501 int n_buckets
, bool ufid
)
503 struct table_instance
*new_ti
;
505 new_ti
= table_instance_alloc(n_buckets
);
509 flow_table_copy_flows(ti
, new_ti
, ufid
);
514 int ovs_flow_tbl_flush(struct flow_table
*flow_table
)
516 struct table_instance
*old_ti
, *new_ti
;
517 struct table_instance
*old_ufid_ti
, *new_ufid_ti
;
519 new_ti
= table_instance_alloc(TBL_MIN_BUCKETS
);
522 new_ufid_ti
= table_instance_alloc(TBL_MIN_BUCKETS
);
526 old_ti
= ovsl_dereference(flow_table
->ti
);
527 old_ufid_ti
= ovsl_dereference(flow_table
->ufid_ti
);
529 rcu_assign_pointer(flow_table
->ti
, new_ti
);
530 rcu_assign_pointer(flow_table
->ufid_ti
, new_ufid_ti
);
531 flow_table
->last_rehash
= jiffies
;
532 flow_table
->count
= 0;
533 flow_table
->ufid_count
= 0;
535 table_instance_destroy(flow_table
, old_ti
, old_ufid_ti
, true);
539 __table_instance_destroy(new_ti
);
543 static u32
flow_hash(const struct sw_flow_key
*key
,
544 const struct sw_flow_key_range
*range
)
546 const u32
*hash_key
= (const u32
*)((const u8
*)key
+ range
->start
);
548 /* Make sure number of hash bytes are multiple of u32. */
549 int hash_u32s
= range_n_bytes(range
) >> 2;
551 return jhash2(hash_key
, hash_u32s
, 0);
554 static int flow_key_start(const struct sw_flow_key
*key
)
559 return rounddown(offsetof(struct sw_flow_key
, phy
),
563 static bool cmp_key(const struct sw_flow_key
*key1
,
564 const struct sw_flow_key
*key2
,
565 int key_start
, int key_end
)
567 const long *cp1
= (const long *)((const u8
*)key1
+ key_start
);
568 const long *cp2
= (const long *)((const u8
*)key2
+ key_start
);
572 for (i
= key_start
; i
< key_end
; i
+= sizeof(long))
573 diffs
|= *cp1
++ ^ *cp2
++;
578 static bool flow_cmp_masked_key(const struct sw_flow
*flow
,
579 const struct sw_flow_key
*key
,
580 const struct sw_flow_key_range
*range
)
582 return cmp_key(&flow
->key
, key
, range
->start
, range
->end
);
585 static bool ovs_flow_cmp_unmasked_key(const struct sw_flow
*flow
,
586 const struct sw_flow_match
*match
)
588 struct sw_flow_key
*key
= match
->key
;
589 int key_start
= flow_key_start(key
);
590 int key_end
= match
->range
.end
;
592 BUG_ON(ovs_identifier_is_ufid(&flow
->id
));
593 return cmp_key(flow
->id
.unmasked_key
, key
, key_start
, key_end
);
596 static struct sw_flow
*masked_flow_lookup(struct table_instance
*ti
,
597 const struct sw_flow_key
*unmasked
,
598 const struct sw_flow_mask
*mask
,
601 struct sw_flow
*flow
;
602 struct hlist_head
*head
;
604 struct sw_flow_key masked_key
;
606 ovs_flow_mask_key(&masked_key
, unmasked
, false, mask
);
607 hash
= flow_hash(&masked_key
, &mask
->range
);
608 head
= find_bucket(ti
, hash
);
610 hlist_for_each_entry_rcu(flow
, head
, flow_table
.node
[ti
->node_ver
]) {
611 if (flow
->mask
== mask
&& flow
->flow_table
.hash
== hash
&&
612 flow_cmp_masked_key(flow
, &masked_key
, &mask
->range
))
618 /* Flow lookup does full lookup on flow table. It starts with
619 * mask from index passed in *index.
621 static struct sw_flow
*flow_lookup(struct flow_table
*tbl
,
622 struct table_instance
*ti
,
623 const struct mask_array
*ma
,
624 const struct sw_flow_key
*key
,
628 struct sw_flow
*flow
;
629 struct sw_flow_mask
*mask
;
632 if (likely(*index
< ma
->max
)) {
633 mask
= rcu_dereference_ovsl(ma
->masks
[*index
]);
635 flow
= masked_flow_lookup(ti
, key
, mask
, n_mask_hit
);
641 for (i
= 0; i
< ma
->max
; i
++) {
646 mask
= rcu_dereference_ovsl(ma
->masks
[i
]);
650 flow
= masked_flow_lookup(ti
, key
, mask
, n_mask_hit
);
651 if (flow
) { /* Found */
661 * mask_cache maps flow to probable mask. This cache is not tightly
662 * coupled cache, It means updates to mask list can result in inconsistent
663 * cache entry in mask cache.
664 * This is per cpu cache and is divided in MC_HASH_SEGS segments.
665 * In case of a hash collision the entry is hashed in next segment.
667 struct sw_flow
*ovs_flow_tbl_lookup_stats(struct flow_table
*tbl
,
668 const struct sw_flow_key
*key
,
672 struct mask_array
*ma
= rcu_dereference(tbl
->mask_array
);
673 struct table_instance
*ti
= rcu_dereference(tbl
->ti
);
674 struct mask_cache_entry
*entries
, *ce
;
675 struct sw_flow
*flow
;
680 if (unlikely(!skb_hash
)) {
683 return flow_lookup(tbl
, ti
, ma
, key
, n_mask_hit
, &mask_index
);
686 /* Pre and post recirulation flows usually have the same skb_hash
687 * value. To avoid hash collisions, rehash the 'skb_hash' with
690 skb_hash
= jhash_1word(skb_hash
, key
->recirc_id
);
694 entries
= this_cpu_ptr(tbl
->mask_cache
);
696 /* Find the cache entry 'ce' to operate on. */
697 for (seg
= 0; seg
< MC_HASH_SEGS
; seg
++) {
698 int index
= hash
& (MC_HASH_ENTRIES
- 1);
699 struct mask_cache_entry
*e
;
702 if (e
->skb_hash
== skb_hash
) {
703 flow
= flow_lookup(tbl
, ti
, ma
, key
, n_mask_hit
,
710 if (!ce
|| e
->skb_hash
< ce
->skb_hash
)
711 ce
= e
; /* A better replacement cache candidate. */
713 hash
>>= MC_HASH_SHIFT
;
716 /* Cache miss, do full lookup. */
717 flow
= flow_lookup(tbl
, ti
, ma
, key
, n_mask_hit
, &ce
->mask_index
);
719 ce
->skb_hash
= skb_hash
;
724 struct sw_flow
*ovs_flow_tbl_lookup(struct flow_table
*tbl
,
725 const struct sw_flow_key
*key
)
727 struct table_instance
*ti
= rcu_dereference_ovsl(tbl
->ti
);
728 struct mask_array
*ma
= rcu_dereference_ovsl(tbl
->mask_array
);
729 u32 __always_unused n_mask_hit
;
732 return flow_lookup(tbl
, ti
, ma
, key
, &n_mask_hit
, &index
);
735 struct sw_flow
*ovs_flow_tbl_lookup_exact(struct flow_table
*tbl
,
736 const struct sw_flow_match
*match
)
738 struct mask_array
*ma
= ovsl_dereference(tbl
->mask_array
);
741 /* Always called under ovs-mutex. */
742 for (i
= 0; i
< ma
->max
; i
++) {
743 struct table_instance
*ti
= ovsl_dereference(tbl
->ti
);
744 u32 __always_unused n_mask_hit
;
745 struct sw_flow_mask
*mask
;
746 struct sw_flow
*flow
;
748 mask
= ovsl_dereference(ma
->masks
[i
]);
751 flow
= masked_flow_lookup(ti
, match
->key
, mask
, &n_mask_hit
);
752 if (flow
&& ovs_identifier_is_key(&flow
->id
) &&
753 ovs_flow_cmp_unmasked_key(flow
, match
))
759 static u32
ufid_hash(const struct sw_flow_id
*sfid
)
761 return jhash(sfid
->ufid
, sfid
->ufid_len
, 0);
764 static bool ovs_flow_cmp_ufid(const struct sw_flow
*flow
,
765 const struct sw_flow_id
*sfid
)
767 if (flow
->id
.ufid_len
!= sfid
->ufid_len
)
770 return !memcmp(flow
->id
.ufid
, sfid
->ufid
, sfid
->ufid_len
);
773 bool ovs_flow_cmp(const struct sw_flow
*flow
, const struct sw_flow_match
*match
)
775 if (ovs_identifier_is_ufid(&flow
->id
))
776 return flow_cmp_masked_key(flow
, match
->key
, &match
->range
);
778 return ovs_flow_cmp_unmasked_key(flow
, match
);
781 struct sw_flow
*ovs_flow_tbl_lookup_ufid(struct flow_table
*tbl
,
782 const struct sw_flow_id
*ufid
)
784 struct table_instance
*ti
= rcu_dereference_ovsl(tbl
->ufid_ti
);
785 struct sw_flow
*flow
;
786 struct hlist_head
*head
;
789 hash
= ufid_hash(ufid
);
790 head
= find_bucket(ti
, hash
);
791 hlist_for_each_entry_rcu(flow
, head
, ufid_table
.node
[ti
->node_ver
]) {
792 if (flow
->ufid_table
.hash
== hash
&&
793 ovs_flow_cmp_ufid(flow
, ufid
))
799 int ovs_flow_tbl_num_masks(const struct flow_table
*table
)
801 struct mask_array
*ma
;
803 ma
= rcu_dereference_ovsl(table
->mask_array
);
804 return READ_ONCE(ma
->count
);
807 static struct table_instance
*table_instance_expand(struct table_instance
*ti
,
810 return table_instance_rehash(ti
, ti
->n_buckets
* 2, ufid
);
813 /* Must be called with OVS mutex held. */
814 void ovs_flow_tbl_remove(struct flow_table
*table
, struct sw_flow
*flow
)
816 struct table_instance
*ti
= ovsl_dereference(table
->ti
);
817 struct table_instance
*ufid_ti
= ovsl_dereference(table
->ufid_ti
);
819 BUG_ON(table
->count
== 0);
820 table_instance_flow_free(table
, ti
, ufid_ti
, flow
, true);
823 static struct sw_flow_mask
*mask_alloc(void)
825 struct sw_flow_mask
*mask
;
827 mask
= kmalloc(sizeof(*mask
), GFP_KERNEL
);
834 static bool mask_equal(const struct sw_flow_mask
*a
,
835 const struct sw_flow_mask
*b
)
837 const u8
*a_
= (const u8
*)&a
->key
+ a
->range
.start
;
838 const u8
*b_
= (const u8
*)&b
->key
+ b
->range
.start
;
840 return (a
->range
.end
== b
->range
.end
)
841 && (a
->range
.start
== b
->range
.start
)
842 && (memcmp(a_
, b_
, range_n_bytes(&a
->range
)) == 0);
845 static struct sw_flow_mask
*flow_mask_find(const struct flow_table
*tbl
,
846 const struct sw_flow_mask
*mask
)
848 struct mask_array
*ma
;
851 ma
= ovsl_dereference(tbl
->mask_array
);
852 for (i
= 0; i
< ma
->max
; i
++) {
853 struct sw_flow_mask
*t
;
855 t
= ovsl_dereference(ma
->masks
[i
]);
856 if (t
&& mask_equal(mask
, t
))
863 /* Add 'mask' into the mask list, if it is not already there. */
864 static int flow_mask_insert(struct flow_table
*tbl
, struct sw_flow
*flow
,
865 const struct sw_flow_mask
*new)
867 struct sw_flow_mask
*mask
;
869 mask
= flow_mask_find(tbl
, new);
871 /* Allocate a new mask if none exsits. */
876 mask
->key
= new->key
;
877 mask
->range
= new->range
;
879 /* Add mask to mask-list. */
880 if (tbl_mask_array_add_mask(tbl
, mask
)) {
886 BUG_ON(!mask
->ref_count
);
894 /* Must be called with OVS mutex held. */
895 static void flow_key_insert(struct flow_table
*table
, struct sw_flow
*flow
)
897 struct table_instance
*new_ti
= NULL
;
898 struct table_instance
*ti
;
900 flow
->flow_table
.hash
= flow_hash(&flow
->key
, &flow
->mask
->range
);
901 ti
= ovsl_dereference(table
->ti
);
902 table_instance_insert(ti
, flow
);
905 /* Expand table, if necessary, to make room. */
906 if (table
->count
> ti
->n_buckets
)
907 new_ti
= table_instance_expand(ti
, false);
908 else if (time_after(jiffies
, table
->last_rehash
+ REHASH_INTERVAL
))
909 new_ti
= table_instance_rehash(ti
, ti
->n_buckets
, false);
912 rcu_assign_pointer(table
->ti
, new_ti
);
913 call_rcu(&ti
->rcu
, flow_tbl_destroy_rcu_cb
);
914 table
->last_rehash
= jiffies
;
918 /* Must be called with OVS mutex held. */
919 static void flow_ufid_insert(struct flow_table
*table
, struct sw_flow
*flow
)
921 struct table_instance
*ti
;
923 flow
->ufid_table
.hash
= ufid_hash(&flow
->id
);
924 ti
= ovsl_dereference(table
->ufid_ti
);
925 ufid_table_instance_insert(ti
, flow
);
928 /* Expand table, if necessary, to make room. */
929 if (table
->ufid_count
> ti
->n_buckets
) {
930 struct table_instance
*new_ti
;
932 new_ti
= table_instance_expand(ti
, true);
934 rcu_assign_pointer(table
->ufid_ti
, new_ti
);
935 call_rcu(&ti
->rcu
, flow_tbl_destroy_rcu_cb
);
940 /* Must be called with OVS mutex held. */
941 int ovs_flow_tbl_insert(struct flow_table
*table
, struct sw_flow
*flow
,
942 const struct sw_flow_mask
*mask
)
946 err
= flow_mask_insert(table
, flow
, mask
);
949 flow_key_insert(table
, flow
);
950 if (ovs_identifier_is_ufid(&flow
->id
))
951 flow_ufid_insert(table
, flow
);
956 /* Initializes the flow module.
957 * Returns zero if successful or a negative error code.
959 int ovs_flow_init(void)
961 BUILD_BUG_ON(__alignof__(struct sw_flow_key
) % __alignof__(long));
962 BUILD_BUG_ON(sizeof(struct sw_flow_key
) % sizeof(long));
964 flow_cache
= kmem_cache_create("sw_flow", sizeof(struct sw_flow
)
966 * sizeof(struct sw_flow_stats
*)),
968 if (flow_cache
== NULL
)
972 = kmem_cache_create("sw_flow_stats", sizeof(struct sw_flow_stats
),
973 0, SLAB_HWCACHE_ALIGN
, NULL
);
974 if (flow_stats_cache
== NULL
) {
975 kmem_cache_destroy(flow_cache
);
983 /* Uninitializes the flow module. */
984 void ovs_flow_exit(void)
986 kmem_cache_destroy(flow_stats_cache
);
987 kmem_cache_destroy(flow_cache
);