flow_table.c (04b7d136d015f220b1003e6c573834658d507a31) flow_table.c (4bc63b1b531df518576a97d17bf5939fdbc33ccb)
1// SPDX-License-Identifier: GPL-2.0-only
2/*
3 * Copyright (c) 2007-2014 Nicira, Inc.
4 */
5
6#include "flow.h"
7#include "datapath.h"
8#include "flow_netlink.h"

--- 20 unchanged lines hidden (view full) ---

29#include <linux/icmp.h>
30#include <linux/icmpv6.h>
31#include <linux/rculist.h>
32#include <net/ip.h>
33#include <net/ipv6.h>
34#include <net/ndisc.h>
35
36#define TBL_MIN_BUCKETS 1024
1// SPDX-License-Identifier: GPL-2.0-only
2/*
3 * Copyright (c) 2007-2014 Nicira, Inc.
4 */
5
6#include "flow.h"
7#include "datapath.h"
8#include "flow_netlink.h"

--- 20 unchanged lines hidden (view full) ---

29#include <linux/icmp.h>
30#include <linux/icmpv6.h>
31#include <linux/rculist.h>
32#include <net/ip.h>
33#include <net/ipv6.h>
34#include <net/ndisc.h>
35
36#define TBL_MIN_BUCKETS 1024
37#define MASK_ARRAY_SIZE_MIN 16
37#define REHASH_INTERVAL (10 * 60 * HZ)
38
39#define MC_HASH_SHIFT 8
40#define MC_HASH_ENTRIES (1u << MC_HASH_SHIFT)
41#define MC_HASH_SEGS ((sizeof(uint32_t) * 8) / MC_HASH_SHIFT)
42
43static struct kmem_cache *flow_cache;
44struct kmem_cache *flow_stats_cache __read_mostly;

--- 118 unchanged lines hidden (view full) ---

163 ti->n_buckets = new_size;
164 ti->node_ver = 0;
165 ti->keep_flows = false;
166 get_random_bytes(&ti->hash_seed, sizeof(u32));
167
168 return ti;
169}
170
38#define REHASH_INTERVAL (10 * 60 * HZ)
39
40#define MC_HASH_SHIFT 8
41#define MC_HASH_ENTRIES (1u << MC_HASH_SHIFT)
42#define MC_HASH_SEGS ((sizeof(uint32_t) * 8) / MC_HASH_SHIFT)
43
44static struct kmem_cache *flow_cache;
45struct kmem_cache *flow_stats_cache __read_mostly;

--- 118 unchanged lines hidden (view full) ---

164 ti->n_buckets = new_size;
165 ti->node_ver = 0;
166 ti->keep_flows = false;
167 get_random_bytes(&ti->hash_seed, sizeof(u32));
168
169 return ti;
170}
171
172static struct mask_array *tbl_mask_array_alloc(int size)
173{
174 struct mask_array *new;
175
176 size = max(MASK_ARRAY_SIZE_MIN, size);
177 new = kzalloc(sizeof(struct mask_array) +
178 sizeof(struct sw_flow_mask *) * size, GFP_KERNEL);
179 if (!new)
180 return NULL;
181
182 new->count = 0;
183 new->max = size;
184
185 return new;
186}
187
188static int tbl_mask_array_realloc(struct flow_table *tbl, int size)
189{
190 struct mask_array *old;
191 struct mask_array *new;
192
193 new = tbl_mask_array_alloc(size);
194 if (!new)
195 return -ENOMEM;
196
197 old = ovsl_dereference(tbl->mask_array);
198 if (old) {
199 int i;
200
201 for (i = 0; i < old->max; i++) {
202 if (ovsl_dereference(old->masks[i]))
203 new->masks[new->count++] = old->masks[i];
204 }
205 }
206
207 rcu_assign_pointer(tbl->mask_array, new);
208 kfree_rcu(old, rcu);
209
210 return 0;
211}
212
171int ovs_flow_tbl_init(struct flow_table *table)
172{
173 struct table_instance *ti, *ufid_ti;
213int ovs_flow_tbl_init(struct flow_table *table)
214{
215 struct table_instance *ti, *ufid_ti;
216 struct mask_array *ma;
174
175 table->mask_cache = __alloc_percpu(sizeof(struct mask_cache_entry) *
176 MC_HASH_ENTRIES,
177 __alignof__(struct mask_cache_entry));
178 if (!table->mask_cache)
179 return -ENOMEM;
180
217
218 table->mask_cache = __alloc_percpu(sizeof(struct mask_cache_entry) *
219 MC_HASH_ENTRIES,
220 __alignof__(struct mask_cache_entry));
221 if (!table->mask_cache)
222 return -ENOMEM;
223
224 ma = tbl_mask_array_alloc(MASK_ARRAY_SIZE_MIN);
225 if (!ma)
226 goto free_mask_cache;
227
181 ti = table_instance_alloc(TBL_MIN_BUCKETS);
182 if (!ti)
228 ti = table_instance_alloc(TBL_MIN_BUCKETS);
229 if (!ti)
183 goto free_mask_cache;
230 goto free_mask_array;
184
185 ufid_ti = table_instance_alloc(TBL_MIN_BUCKETS);
186 if (!ufid_ti)
187 goto free_ti;
188
189 rcu_assign_pointer(table->ti, ti);
190 rcu_assign_pointer(table->ufid_ti, ufid_ti);
231
232 ufid_ti = table_instance_alloc(TBL_MIN_BUCKETS);
233 if (!ufid_ti)
234 goto free_ti;
235
236 rcu_assign_pointer(table->ti, ti);
237 rcu_assign_pointer(table->ufid_ti, ufid_ti);
191 INIT_LIST_HEAD(&table->mask_list);
238 rcu_assign_pointer(table->mask_array, ma);
192 table->last_rehash = jiffies;
193 table->count = 0;
194 table->ufid_count = 0;
195 return 0;
196
197free_ti:
198 __table_instance_destroy(ti);
239 table->last_rehash = jiffies;
240 table->count = 0;
241 table->ufid_count = 0;
242 return 0;
243
244free_ti:
245 __table_instance_destroy(ti);
246free_mask_array:
247 kfree(ma);
199free_mask_cache:
200 free_percpu(table->mask_cache);
201 return -ENOMEM;
202}
203
204static void flow_tbl_destroy_rcu_cb(struct rcu_head *rcu)
205{
206 struct table_instance *ti = container_of(rcu, struct table_instance, rcu);

--- 43 unchanged lines hidden (view full) ---

250 * error path.
251 */
252void ovs_flow_tbl_destroy(struct flow_table *table)
253{
254 struct table_instance *ti = rcu_dereference_raw(table->ti);
255 struct table_instance *ufid_ti = rcu_dereference_raw(table->ufid_ti);
256
257 free_percpu(table->mask_cache);
248free_mask_cache:
249 free_percpu(table->mask_cache);
250 return -ENOMEM;
251}
252
253static void flow_tbl_destroy_rcu_cb(struct rcu_head *rcu)
254{
255 struct table_instance *ti = container_of(rcu, struct table_instance, rcu);

--- 43 unchanged lines hidden (view full) ---

299 * error path.
300 */
301void ovs_flow_tbl_destroy(struct flow_table *table)
302{
303 struct table_instance *ti = rcu_dereference_raw(table->ti);
304 struct table_instance *ufid_ti = rcu_dereference_raw(table->ufid_ti);
305
306 free_percpu(table->mask_cache);
307 kfree_rcu(rcu_dereference_raw(table->mask_array), rcu);
258 table_instance_destroy(ti, ufid_ti, false);
259}
260
261struct sw_flow *ovs_flow_tbl_dump_next(struct table_instance *ti,
262 u32 *bucket, u32 *last)
263{
264 struct sw_flow *flow;
265 struct hlist_head *head;

--- 189 unchanged lines hidden (view full) ---

455 flow_cmp_masked_key(flow, &masked_key, &mask->range))
456 return flow;
457 }
458 return NULL;
459}
460
461static struct sw_flow *flow_lookup(struct flow_table *tbl,
462 struct table_instance *ti,
308 table_instance_destroy(ti, ufid_ti, false);
309}
310
311struct sw_flow *ovs_flow_tbl_dump_next(struct table_instance *ti,
312 u32 *bucket, u32 *last)
313{
314 struct sw_flow *flow;
315 struct hlist_head *head;

--- 189 unchanged lines hidden (view full) ---

505 flow_cmp_masked_key(flow, &masked_key, &mask->range))
506 return flow;
507 }
508 return NULL;
509}
510
511static struct sw_flow *flow_lookup(struct flow_table *tbl,
512 struct table_instance *ti,
513 struct mask_array *ma,
463 const struct sw_flow_key *key,
514 const struct sw_flow_key *key,
464 u32 *n_mask_hit)
515 u32 *n_mask_hit,
516 u32 *index)
465{
517{
466 struct sw_flow_mask *mask;
467 struct sw_flow *flow;
518 struct sw_flow *flow;
519 int i;
468
520
469 list_for_each_entry_rcu(mask, &tbl->mask_list, list) {
470 flow = masked_flow_lookup(ti, key, mask, n_mask_hit);
471 if (flow) /* Found */
472 return flow;
521 for (i = 0; i < ma->max; i++) {
522 struct sw_flow_mask *mask;
523
524 mask = rcu_dereference_ovsl(ma->masks[i]);
525 if (mask) {
526 flow = masked_flow_lookup(ti, key, mask, n_mask_hit);
527 if (flow) { /* Found */
528 *index = i;
529 return flow;
530 }
531 }
473 }
532 }
533
474 return NULL;
475}
476
477/*
478 * mask_cache maps flow to probable mask. This cache is not tightly
479 * coupled cache, It means updates to mask list can result in inconsistent
480 * cache entry in mask cache.
481 * This is per cpu cache and is divided in MC_HASH_SEGS segments.
482 * In case of a hash collision the entry is hashed in next segment.
483 * */
484struct sw_flow *ovs_flow_tbl_lookup_stats(struct flow_table *tbl,
485 const struct sw_flow_key *key,
486 u32 skb_hash,
487 u32 *n_mask_hit)
488{
534 return NULL;
535}
536
537/*
538 * mask_cache maps flow to probable mask. This cache is not tightly
539 * coupled cache, It means updates to mask list can result in inconsistent
540 * cache entry in mask cache.
541 * This is per cpu cache and is divided in MC_HASH_SEGS segments.
542 * In case of a hash collision the entry is hashed in next segment.
543 * */
544struct sw_flow *ovs_flow_tbl_lookup_stats(struct flow_table *tbl,
545 const struct sw_flow_key *key,
546 u32 skb_hash,
547 u32 *n_mask_hit)
548{
549 struct mask_array *ma = rcu_dereference_ovsl(tbl->mask_array);
489 struct table_instance *ti = rcu_dereference_ovsl(tbl->ti);
490 struct mask_cache_entry *entries, *ce, *del;
491 struct sw_flow *flow;
492 u32 hash = skb_hash;
493 int seg;
494
495 *n_mask_hit = 0;
550 struct table_instance *ti = rcu_dereference_ovsl(tbl->ti);
551 struct mask_cache_entry *entries, *ce, *del;
552 struct sw_flow *flow;
553 u32 hash = skb_hash;
554 int seg;
555
556 *n_mask_hit = 0;
496 if (unlikely(!skb_hash))
497 return flow_lookup(tbl, ti, key, n_mask_hit);
557 if (unlikely(!skb_hash)) {
558 u32 __always_unused mask_index;
498
559
560 return flow_lookup(tbl, ti, ma, key, n_mask_hit, &mask_index);
561 }
562
499 del = NULL;
500 entries = this_cpu_ptr(tbl->mask_cache);
501
502 for (seg = 0; seg < MC_HASH_SEGS; seg++) {
503 int index;
504
505 index = hash & (MC_HASH_ENTRIES - 1);
506 ce = &entries[index];
507
508 if (ce->skb_hash == skb_hash) {
509 struct sw_flow_mask *mask;
563 del = NULL;
564 entries = this_cpu_ptr(tbl->mask_cache);
565
566 for (seg = 0; seg < MC_HASH_SEGS; seg++) {
567 int index;
568
569 index = hash & (MC_HASH_ENTRIES - 1);
570 ce = &entries[index];
571
572 if (ce->skb_hash == skb_hash) {
573 struct sw_flow_mask *mask;
510 int i;
574 struct sw_flow *flow;
511
575
512 i = 0;
513 list_for_each_entry_rcu(mask, &tbl->mask_list, list) {
514 if (ce->mask_index == i++) {
515 flow = masked_flow_lookup(ti, key, mask,
516 n_mask_hit);
517 if (flow) /* Found */
518 return flow;
519
520 break;
521 }
576 mask = rcu_dereference_ovsl(ma->masks[ce->mask_index]);
577 if (mask) {
578 flow = masked_flow_lookup(ti, key, mask,
579 n_mask_hit);
580 if (flow) /* Found */
581 return flow;
522 }
523
524 del = ce;
525 break;
526 }
527
582 }
583
584 del = ce;
585 break;
586 }
587
528 if (!del || (del->skb_hash && !ce->skb_hash)) {
588 if (!del || (del->skb_hash && !ce->skb_hash) ||
589 (rcu_dereference_ovsl(ma->masks[del->mask_index]) &&
590 !rcu_dereference_ovsl(ma->masks[ce->mask_index]))) {
529 del = ce;
530 }
531
532 hash >>= MC_HASH_SHIFT;
533 }
534
591 del = ce;
592 }
593
594 hash >>= MC_HASH_SHIFT;
595 }
596
535 flow = flow_lookup(tbl, ti, key, n_mask_hit);
597 flow = flow_lookup(tbl, ti, ma, key, n_mask_hit, &del->mask_index);
536
598
537 if (flow) {
599 if (flow)
538 del->skb_hash = skb_hash;
600 del->skb_hash = skb_hash;
539 del->mask_index = (*n_mask_hit - 1);
540 }
541
542 return flow;
543}
544
545struct sw_flow *ovs_flow_tbl_lookup(struct flow_table *tbl,
546 const struct sw_flow_key *key)
547{
548 struct table_instance *ti = rcu_dereference_ovsl(tbl->ti);
601
602 return flow;
603}
604
605struct sw_flow *ovs_flow_tbl_lookup(struct flow_table *tbl,
606 const struct sw_flow_key *key)
607{
608 struct table_instance *ti = rcu_dereference_ovsl(tbl->ti);
609 struct mask_array *ma = rcu_dereference_ovsl(tbl->mask_array);
610
549 u32 __always_unused n_mask_hit;
611 u32 __always_unused n_mask_hit;
612 u32 __always_unused index;
550
613
551 return flow_lookup(tbl, ti, key, &n_mask_hit);
614 return flow_lookup(tbl, ti, ma, key, &n_mask_hit, &index);
552}
553
554struct sw_flow *ovs_flow_tbl_lookup_exact(struct flow_table *tbl,
555 const struct sw_flow_match *match)
556{
615}
616
617struct sw_flow *ovs_flow_tbl_lookup_exact(struct flow_table *tbl,
618 const struct sw_flow_match *match)
619{
557 struct table_instance *ti = rcu_dereference_ovsl(tbl->ti);
558 struct sw_flow_mask *mask;
559 struct sw_flow *flow;
560 u32 __always_unused n_mask_hit;
620 struct mask_array *ma = ovsl_dereference(tbl->mask_array);
621 int i;
561
562 /* Always called under ovs-mutex. */
622
623 /* Always called under ovs-mutex. */
563 list_for_each_entry(mask, &tbl->mask_list, list) {
624 for (i = 0; i < ma->max; i++) {
625 struct table_instance *ti = rcu_dereference_ovsl(tbl->ti);
626 u32 __always_unused n_mask_hit;
627 struct sw_flow_mask *mask;
628 struct sw_flow *flow;
629
630 mask = ovsl_dereference(ma->masks[i]);
631 if (!mask)
632 continue;
633
564 flow = masked_flow_lookup(ti, match->key, mask, &n_mask_hit);
565 if (flow && ovs_identifier_is_key(&flow->id) &&
634 flow = masked_flow_lookup(ti, match->key, mask, &n_mask_hit);
635 if (flow && ovs_identifier_is_key(&flow->id) &&
566 ovs_flow_cmp_unmasked_key(flow, match))
636 ovs_flow_cmp_unmasked_key(flow, match)) {
567 return flow;
637 return flow;
638 }
568 }
639 }
640
569 return NULL;
570}
571
572static u32 ufid_hash(const struct sw_flow_id *sfid)
573{
574 return jhash(sfid->ufid, sfid->ufid_len, 0);
575}
576

--- 29 unchanged lines hidden (view full) ---

606 ovs_flow_cmp_ufid(flow, ufid))
607 return flow;
608 }
609 return NULL;
610}
611
612int ovs_flow_tbl_num_masks(const struct flow_table *table)
613{
641 return NULL;
642}
643
644static u32 ufid_hash(const struct sw_flow_id *sfid)
645{
646 return jhash(sfid->ufid, sfid->ufid_len, 0);
647}
648

--- 29 unchanged lines hidden (view full) ---

678 ovs_flow_cmp_ufid(flow, ufid))
679 return flow;
680 }
681 return NULL;
682}
683
684int ovs_flow_tbl_num_masks(const struct flow_table *table)
685{
614 struct sw_flow_mask *mask;
615 int num = 0;
686 struct mask_array *ma = rcu_dereference_ovsl(table->mask_array);
616
687
617 list_for_each_entry(mask, &table->mask_list, list)
618 num++;
619
620 return num;
688 return ma->count;
621}
622
623static struct table_instance *table_instance_expand(struct table_instance *ti,
624 bool ufid)
625{
626 return table_instance_rehash(ti, ti->n_buckets * 2, ufid);
627}
628

--- 4 unchanged lines hidden (view full) ---

633 /* ovs-lock is required to protect mask-refcount and
634 * mask list.
635 */
636 ASSERT_OVSL();
637 BUG_ON(!mask->ref_count);
638 mask->ref_count--;
639
640 if (!mask->ref_count) {
689}
690
691static struct table_instance *table_instance_expand(struct table_instance *ti,
692 bool ufid)
693{
694 return table_instance_rehash(ti, ti->n_buckets * 2, ufid);
695}
696

--- 4 unchanged lines hidden (view full) ---

701 /* ovs-lock is required to protect mask-refcount and
702 * mask list.
703 */
704 ASSERT_OVSL();
705 BUG_ON(!mask->ref_count);
706 mask->ref_count--;
707
708 if (!mask->ref_count) {
641 list_del_rcu(&mask->list);
642 kfree_rcu(mask, rcu);
709 struct mask_array *ma;
710 int i;
711
712 ma = ovsl_dereference(tbl->mask_array);
713 for (i = 0; i < ma->max; i++) {
714 if (mask == ovsl_dereference(ma->masks[i])) {
715 RCU_INIT_POINTER(ma->masks[i], NULL);
716 ma->count--;
717 kfree_rcu(mask, rcu);
718 return;
719 }
720 }
721 BUG();
643 }
644 }
645}
646
647/* Must be called with OVS mutex held. */
648void ovs_flow_tbl_remove(struct flow_table *table, struct sw_flow *flow)
649{
650 struct table_instance *ti = ovsl_dereference(table->ti);

--- 33 unchanged lines hidden (view full) ---

684 return (a->range.end == b->range.end)
685 && (a->range.start == b->range.start)
686 && (memcmp(a_, b_, range_n_bytes(&a->range)) == 0);
687}
688
689static struct sw_flow_mask *flow_mask_find(const struct flow_table *tbl,
690 const struct sw_flow_mask *mask)
691{
722 }
723 }
724}
725
726/* Must be called with OVS mutex held. */
727void ovs_flow_tbl_remove(struct flow_table *table, struct sw_flow *flow)
728{
729 struct table_instance *ti = ovsl_dereference(table->ti);

--- 33 unchanged lines hidden (view full) ---

763 return (a->range.end == b->range.end)
764 && (a->range.start == b->range.start)
765 && (memcmp(a_, b_, range_n_bytes(&a->range)) == 0);
766}
767
768static struct sw_flow_mask *flow_mask_find(const struct flow_table *tbl,
769 const struct sw_flow_mask *mask)
770{
692 struct list_head *ml;
771 struct mask_array *ma;
772 int i;
693
773
694 list_for_each(ml, &tbl->mask_list) {
695 struct sw_flow_mask *m;
696 m = container_of(ml, struct sw_flow_mask, list);
697 if (mask_equal(mask, m))
698 return m;
774 ma = ovsl_dereference(tbl->mask_array);
775 for (i = 0; i < ma->max; i++) {
776 struct sw_flow_mask *t;
777 t = ovsl_dereference(ma->masks[i]);
778
779 if (t && mask_equal(mask, t))
780 return t;
699 }
700
701 return NULL;
702}
703
704/* Add 'mask' into the mask list, if it is not already there. */
705static int flow_mask_insert(struct flow_table *tbl, struct sw_flow *flow,
706 const struct sw_flow_mask *new)
707{
708 struct sw_flow_mask *mask;
781 }
782
783 return NULL;
784}
785
786/* Add 'mask' into the mask list, if it is not already there. */
787static int flow_mask_insert(struct flow_table *tbl, struct sw_flow *flow,
788 const struct sw_flow_mask *new)
789{
790 struct sw_flow_mask *mask;
791
709 mask = flow_mask_find(tbl, new);
710 if (!mask) {
792 mask = flow_mask_find(tbl, new);
793 if (!mask) {
794 struct mask_array *ma;
795 int i;
796
711 /* Allocate a new mask if none exsits. */
712 mask = mask_alloc();
713 if (!mask)
714 return -ENOMEM;
715 mask->key = new->key;
716 mask->range = new->range;
797 /* Allocate a new mask if none exsits. */
798 mask = mask_alloc();
799 if (!mask)
800 return -ENOMEM;
801 mask->key = new->key;
802 mask->range = new->range;
717 list_add_tail_rcu(&mask->list, &tbl->mask_list);
803
804 /* Add mask to mask-list. */
805 ma = ovsl_dereference(tbl->mask_array);
806 if (ma->count >= ma->max) {
807 int err;
808
809 err = tbl_mask_array_realloc(tbl, ma->max +
810 MASK_ARRAY_SIZE_MIN);
811 if (err) {
812 kfree(mask);
813 return err;
814 }
815
816 ma = ovsl_dereference(tbl->mask_array);
817 }
818
819 for (i = 0; i < ma->max; i++) {
820 const struct sw_flow_mask *t;
821
822 t = ovsl_dereference(ma->masks[i]);
823 if (!t) {
824 rcu_assign_pointer(ma->masks[i], mask);
825 ma->count++;
826 break;
827 }
828 }
718 } else {
719 BUG_ON(!mask->ref_count);
720 mask->ref_count++;
721 }
722
723 flow->mask = mask;
724 return 0;
725}

--- 95 unchanged lines hidden --- 		829 } else {
830 BUG_ON(!mask->ref_count);
831 mask->ref_count++;
832 }
833
834 flow->mask = mask;
835 return 0;
836}

--- 95 unchanged lines hidden ---