Thomas Gleixner | c942299 | 2019-05-29 07:12:43 -0700 | [diff] [blame] | 1 | // SPDX-License-Identifier: GPL-2.0-only |
Pravin B Shelar | e644571 | 2013-10-03 18:16:47 -0700 | [diff] [blame] | 2 | /* |
Pravin B Shelar | 9b996e5 | 2014-05-06 18:41:20 -0700 | [diff] [blame] | 3 | * Copyright (c) 2007-2014 Nicira, Inc. |
Pravin B Shelar | e644571 | 2013-10-03 18:16:47 -0700 | [diff] [blame] | 4 | */ |
| 5 | |
| 6 | #include "flow.h" |
| 7 | #include "datapath.h" |
Thomas Graf | 34ae932 | 2015-07-21 10:44:03 +0200 | [diff] [blame] | 8 | #include "flow_netlink.h" |
Pravin B Shelar | e644571 | 2013-10-03 18:16:47 -0700 | [diff] [blame] | 9 | #include <linux/uaccess.h> |
| 10 | #include <linux/netdevice.h> |
| 11 | #include <linux/etherdevice.h> |
| 12 | #include <linux/if_ether.h> |
| 13 | #include <linux/if_vlan.h> |
| 14 | #include <net/llc_pdu.h> |
| 15 | #include <linux/kernel.h> |
Daniel Borkmann | 8754589 | 2014-12-10 16:33:11 +0100 | [diff] [blame] | 16 | #include <linux/jhash.h> |
Pravin B Shelar | e644571 | 2013-10-03 18:16:47 -0700 | [diff] [blame] | 17 | #include <linux/jiffies.h> |
| 18 | #include <linux/llc.h> |
| 19 | #include <linux/module.h> |
| 20 | #include <linux/in.h> |
| 21 | #include <linux/rcupdate.h> |
Thadeu Lima de Souza Cascardo | db74a33 | 2016-09-15 19:11:53 -0300 | [diff] [blame] | 22 | #include <linux/cpumask.h> |
Pravin B Shelar | e644571 | 2013-10-03 18:16:47 -0700 | [diff] [blame] | 23 | #include <linux/if_arp.h> |
| 24 | #include <linux/ip.h> |
| 25 | #include <linux/ipv6.h> |
| 26 | #include <linux/sctp.h> |
| 27 | #include <linux/tcp.h> |
| 28 | #include <linux/udp.h> |
| 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 | |
Pravin B Shelar | b637e49 | 2013-10-04 00:14:23 -0700 | [diff] [blame] | 36 | #define TBL_MIN_BUCKETS 1024 |
| 37 | #define REHASH_INTERVAL (10 * 60 * HZ) |
| 38 | |
Pravin B Shelar | e644571 | 2013-10-03 18:16:47 -0700 | [diff] [blame] | 39 | static struct kmem_cache *flow_cache; |
Jarno Rajahalme | 63e7959 | 2014-03-27 12:42:54 -0700 | [diff] [blame] | 40 | struct kmem_cache *flow_stats_cache __read_mostly; |
Pravin B Shelar | e644571 | 2013-10-03 18:16:47 -0700 | [diff] [blame] | 41 | |
| 42 | static u16 range_n_bytes(const struct sw_flow_key_range *range) |
| 43 | { |
| 44 | return range->end - range->start; |
| 45 | } |
| 46 | |
| 47 | void ovs_flow_mask_key(struct sw_flow_key *dst, const struct sw_flow_key *src, |
Jesse Gross | ae5f2fb | 2015-09-21 20:21:20 -0700 | [diff] [blame] | 48 | bool full, const struct sw_flow_mask *mask) |
Pravin B Shelar | e644571 | 2013-10-03 18:16:47 -0700 | [diff] [blame] | 49 | { |
Jesse Gross | ae5f2fb | 2015-09-21 20:21:20 -0700 | [diff] [blame] | 50 | int start = full ? 0 : mask->range.start; |
| 51 | int len = full ? sizeof *dst : range_n_bytes(&mask->range); |
| 52 | const long *m = (const long *)((const u8 *)&mask->key + start); |
| 53 | const long *s = (const long *)((const u8 *)src + start); |
| 54 | long *d = (long *)((u8 *)dst + start); |
Pravin B Shelar | e644571 | 2013-10-03 18:16:47 -0700 | [diff] [blame] | 55 | int i; |
| 56 | |
Jesse Gross | ae5f2fb | 2015-09-21 20:21:20 -0700 | [diff] [blame] | 57 | /* If 'full' is true then all of 'dst' is fully initialized. Otherwise, |
| 58 | * if 'full' is false the memory outside of the 'mask->range' is left |
| 59 | * uninitialized. This can be used as an optimization when further |
| 60 | * operations on 'dst' only use contents within 'mask->range'. |
Pravin B Shelar | e644571 | 2013-10-03 18:16:47 -0700 | [diff] [blame] | 61 | */ |
Jesse Gross | ae5f2fb | 2015-09-21 20:21:20 -0700 | [diff] [blame] | 62 | for (i = 0; i < len; i += sizeof(long)) |
Pravin B Shelar | e644571 | 2013-10-03 18:16:47 -0700 | [diff] [blame] | 63 | *d++ = *s++ & *m++; |
| 64 | } |
| 65 | |
Jarno Rajahalme | 23dabf8 | 2014-03-27 12:35:23 -0700 | [diff] [blame] | 66 | struct sw_flow *ovs_flow_alloc(void) |
Pravin B Shelar | e644571 | 2013-10-03 18:16:47 -0700 | [diff] [blame] | 67 | { |
| 68 | struct sw_flow *flow; |
Pablo Neira Ayuso | aef833c | 2019-07-19 18:20:13 +0200 | [diff] [blame] | 69 | struct sw_flow_stats *stats; |
Pravin B Shelar | e644571 | 2013-10-03 18:16:47 -0700 | [diff] [blame] | 70 | |
Thadeu Lima de Souza Cascardo | db74a33 | 2016-09-15 19:11:53 -0300 | [diff] [blame] | 71 | flow = kmem_cache_zalloc(flow_cache, GFP_KERNEL); |
Pravin B Shelar | e644571 | 2013-10-03 18:16:47 -0700 | [diff] [blame] | 72 | if (!flow) |
| 73 | return ERR_PTR(-ENOMEM); |
| 74 | |
Thadeu Lima de Souza Cascardo | db74a33 | 2016-09-15 19:11:53 -0300 | [diff] [blame] | 75 | flow->stats_last_writer = -1; |
Pravin B Shelar | e644571 | 2013-10-03 18:16:47 -0700 | [diff] [blame] | 76 | |
Jarno Rajahalme | 63e7959 | 2014-03-27 12:42:54 -0700 | [diff] [blame] | 77 | /* Initialize the default stat node. */ |
| 78 | stats = kmem_cache_alloc_node(flow_stats_cache, |
Konstantin Khlebnikov | 598c12d | 2015-10-02 13:18:22 +0300 | [diff] [blame] | 79 | GFP_KERNEL | __GFP_ZERO, |
| 80 | node_online(0) ? 0 : NUMA_NO_NODE); |
Jarno Rajahalme | 63e7959 | 2014-03-27 12:42:54 -0700 | [diff] [blame] | 81 | if (!stats) |
Jarno Rajahalme | 23dabf8 | 2014-03-27 12:35:23 -0700 | [diff] [blame] | 82 | goto err; |
Pravin B Shelar | e298e50 | 2013-10-29 17:22:21 -0700 | [diff] [blame] | 83 | |
Jarno Rajahalme | 63e7959 | 2014-03-27 12:42:54 -0700 | [diff] [blame] | 84 | spin_lock_init(&stats->lock); |
Pravin B Shelar | e298e50 | 2013-10-29 17:22:21 -0700 | [diff] [blame] | 85 | |
Jarno Rajahalme | 63e7959 | 2014-03-27 12:42:54 -0700 | [diff] [blame] | 86 | RCU_INIT_POINTER(flow->stats[0], stats); |
| 87 | |
Tonghao Zhang | c4b2bf6 | 2017-07-17 23:28:06 -0700 | [diff] [blame] | 88 | cpumask_set_cpu(0, &flow->cpu_used_mask); |
| 89 | |
Pravin B Shelar | e644571 | 2013-10-03 18:16:47 -0700 | [diff] [blame] | 90 | return flow; |
Pravin B Shelar | e298e50 | 2013-10-29 17:22:21 -0700 | [diff] [blame] | 91 | err: |
Wei Yongjun | ece37c8 | 2014-01-08 18:13:14 +0800 | [diff] [blame] | 92 | kmem_cache_free(flow_cache, flow); |
Pravin B Shelar | e298e50 | 2013-10-29 17:22:21 -0700 | [diff] [blame] | 93 | return ERR_PTR(-ENOMEM); |
Pravin B Shelar | e644571 | 2013-10-03 18:16:47 -0700 | [diff] [blame] | 94 | } |
| 95 | |
Thomas Graf | 12eb18f | 2014-11-06 06:58:52 -0800 | [diff] [blame] | 96 | int ovs_flow_tbl_count(const struct flow_table *table) |
Pravin B Shelar | b637e49 | 2013-10-04 00:14:23 -0700 | [diff] [blame] | 97 | { |
| 98 | return table->count; |
| 99 | } |
| 100 | |
Pravin B Shelar | e644571 | 2013-10-03 18:16:47 -0700 | [diff] [blame] | 101 | static void flow_free(struct sw_flow *flow) |
| 102 | { |
Thadeu Lima de Souza Cascardo | db74a33 | 2016-09-15 19:11:53 -0300 | [diff] [blame] | 103 | int cpu; |
Jarno Rajahalme | 63e7959 | 2014-03-27 12:42:54 -0700 | [diff] [blame] | 104 | |
Joe Stringer | 74ed7ab | 2015-01-21 16:42:52 -0800 | [diff] [blame] | 105 | if (ovs_identifier_is_key(&flow->id)) |
| 106 | kfree(flow->id.unmasked_key); |
Thomas Graf | 34ae932 | 2015-07-21 10:44:03 +0200 | [diff] [blame] | 107 | if (flow->sf_acts) |
| 108 | ovs_nla_free_flow_actions((struct sw_flow_actions __force *)flow->sf_acts); |
Thadeu Lima de Souza Cascardo | db74a33 | 2016-09-15 19:11:53 -0300 | [diff] [blame] | 109 | /* We open code this to make sure cpu 0 is always considered */ |
Tonghao Zhang | c4b2bf6 | 2017-07-17 23:28:06 -0700 | [diff] [blame] | 110 | for (cpu = 0; cpu < nr_cpu_ids; cpu = cpumask_next(cpu, &flow->cpu_used_mask)) |
Thadeu Lima de Souza Cascardo | db74a33 | 2016-09-15 19:11:53 -0300 | [diff] [blame] | 111 | if (flow->stats[cpu]) |
Jarno Rajahalme | 63e7959 | 2014-03-27 12:42:54 -0700 | [diff] [blame] | 112 | kmem_cache_free(flow_stats_cache, |
Pablo Neira Ayuso | aef833c | 2019-07-19 18:20:13 +0200 | [diff] [blame] | 113 | (struct sw_flow_stats __force *)flow->stats[cpu]); |
Pravin B Shelar | e644571 | 2013-10-03 18:16:47 -0700 | [diff] [blame] | 114 | kmem_cache_free(flow_cache, flow); |
| 115 | } |
| 116 | |
| 117 | static void rcu_free_flow_callback(struct rcu_head *rcu) |
| 118 | { |
| 119 | struct sw_flow *flow = container_of(rcu, struct sw_flow, rcu); |
| 120 | |
| 121 | flow_free(flow); |
| 122 | } |
| 123 | |
| 124 | void ovs_flow_free(struct sw_flow *flow, bool deferred) |
| 125 | { |
| 126 | if (!flow) |
| 127 | return; |
| 128 | |
Pravin B Shelar | e644571 | 2013-10-03 18:16:47 -0700 | [diff] [blame] | 129 | if (deferred) |
| 130 | call_rcu(&flow->rcu, rcu_free_flow_callback); |
| 131 | else |
| 132 | flow_free(flow); |
| 133 | } |
| 134 | |
Pravin B Shelar | b637e49 | 2013-10-04 00:14:23 -0700 | [diff] [blame] | 135 | static void __table_instance_destroy(struct table_instance *ti) |
Pravin B Shelar | e644571 | 2013-10-03 18:16:47 -0700 | [diff] [blame] | 136 | { |
Kent Overstreet | ee9c5e6 | 2019-03-11 23:31:02 -0700 | [diff] [blame] | 137 | kvfree(ti->buckets); |
Pravin B Shelar | b637e49 | 2013-10-04 00:14:23 -0700 | [diff] [blame] | 138 | kfree(ti); |
Pravin B Shelar | e644571 | 2013-10-03 18:16:47 -0700 | [diff] [blame] | 139 | } |
| 140 | |
Pravin B Shelar | b637e49 | 2013-10-04 00:14:23 -0700 | [diff] [blame] | 141 | static struct table_instance *table_instance_alloc(int new_size) |
Pravin B Shelar | e644571 | 2013-10-03 18:16:47 -0700 | [diff] [blame] | 142 | { |
Pravin B Shelar | b637e49 | 2013-10-04 00:14:23 -0700 | [diff] [blame] | 143 | struct table_instance *ti = kmalloc(sizeof(*ti), GFP_KERNEL); |
Kent Overstreet | ee9c5e6 | 2019-03-11 23:31:02 -0700 | [diff] [blame] | 144 | int i; |
Pravin B Shelar | e644571 | 2013-10-03 18:16:47 -0700 | [diff] [blame] | 145 | |
Pravin B Shelar | b637e49 | 2013-10-04 00:14:23 -0700 | [diff] [blame] | 146 | if (!ti) |
Pravin B Shelar | e644571 | 2013-10-03 18:16:47 -0700 | [diff] [blame] | 147 | return NULL; |
| 148 | |
Kent Overstreet | ee9c5e6 | 2019-03-11 23:31:02 -0700 | [diff] [blame] | 149 | ti->buckets = kvmalloc_array(new_size, sizeof(struct hlist_head), |
| 150 | GFP_KERNEL); |
Pravin B Shelar | b637e49 | 2013-10-04 00:14:23 -0700 | [diff] [blame] | 151 | if (!ti->buckets) { |
| 152 | kfree(ti); |
Pravin B Shelar | e644571 | 2013-10-03 18:16:47 -0700 | [diff] [blame] | 153 | return NULL; |
| 154 | } |
Kent Overstreet | ee9c5e6 | 2019-03-11 23:31:02 -0700 | [diff] [blame] | 155 | |
| 156 | for (i = 0; i < new_size; i++) |
| 157 | INIT_HLIST_HEAD(&ti->buckets[i]); |
| 158 | |
Pravin B Shelar | b637e49 | 2013-10-04 00:14:23 -0700 | [diff] [blame] | 159 | ti->n_buckets = new_size; |
| 160 | ti->node_ver = 0; |
| 161 | ti->keep_flows = false; |
| 162 | get_random_bytes(&ti->hash_seed, sizeof(u32)); |
| 163 | |
| 164 | return ti; |
| 165 | } |
| 166 | |
| 167 | int ovs_flow_tbl_init(struct flow_table *table) |
| 168 | { |
Joe Stringer | 74ed7ab | 2015-01-21 16:42:52 -0800 | [diff] [blame] | 169 | struct table_instance *ti, *ufid_ti; |
Pravin B Shelar | b637e49 | 2013-10-04 00:14:23 -0700 | [diff] [blame] | 170 | |
| 171 | ti = table_instance_alloc(TBL_MIN_BUCKETS); |
| 172 | |
| 173 | if (!ti) |
| 174 | return -ENOMEM; |
| 175 | |
Joe Stringer | 74ed7ab | 2015-01-21 16:42:52 -0800 | [diff] [blame] | 176 | ufid_ti = table_instance_alloc(TBL_MIN_BUCKETS); |
| 177 | if (!ufid_ti) |
| 178 | goto free_ti; |
| 179 | |
Pravin B Shelar | b637e49 | 2013-10-04 00:14:23 -0700 | [diff] [blame] | 180 | rcu_assign_pointer(table->ti, ti); |
Joe Stringer | 74ed7ab | 2015-01-21 16:42:52 -0800 | [diff] [blame] | 181 | rcu_assign_pointer(table->ufid_ti, ufid_ti); |
Pravin B Shelar | b637e49 | 2013-10-04 00:14:23 -0700 | [diff] [blame] | 182 | INIT_LIST_HEAD(&table->mask_list); |
| 183 | table->last_rehash = jiffies; |
Pravin B Shelar | e644571 | 2013-10-03 18:16:47 -0700 | [diff] [blame] | 184 | table->count = 0; |
Joe Stringer | 74ed7ab | 2015-01-21 16:42:52 -0800 | [diff] [blame] | 185 | table->ufid_count = 0; |
Pravin B Shelar | b637e49 | 2013-10-04 00:14:23 -0700 | [diff] [blame] | 186 | return 0; |
Joe Stringer | 74ed7ab | 2015-01-21 16:42:52 -0800 | [diff] [blame] | 187 | |
| 188 | free_ti: |
| 189 | __table_instance_destroy(ti); |
| 190 | return -ENOMEM; |
Pravin B Shelar | e644571 | 2013-10-03 18:16:47 -0700 | [diff] [blame] | 191 | } |
| 192 | |
| 193 | static void flow_tbl_destroy_rcu_cb(struct rcu_head *rcu) |
| 194 | { |
Pravin B Shelar | b637e49 | 2013-10-04 00:14:23 -0700 | [diff] [blame] | 195 | struct table_instance *ti = container_of(rcu, struct table_instance, rcu); |
Pravin B Shelar | e644571 | 2013-10-03 18:16:47 -0700 | [diff] [blame] | 196 | |
Pravin B Shelar | b637e49 | 2013-10-04 00:14:23 -0700 | [diff] [blame] | 197 | __table_instance_destroy(ti); |
| 198 | } |
| 199 | |
Joe Stringer | 74ed7ab | 2015-01-21 16:42:52 -0800 | [diff] [blame] | 200 | static void table_instance_destroy(struct table_instance *ti, |
| 201 | struct table_instance *ufid_ti, |
| 202 | bool deferred) |
Pravin B Shelar | b637e49 | 2013-10-04 00:14:23 -0700 | [diff] [blame] | 203 | { |
Andy Zhou | e80857c | 2014-01-21 09:31:04 -0800 | [diff] [blame] | 204 | int i; |
| 205 | |
Pravin B Shelar | b637e49 | 2013-10-04 00:14:23 -0700 | [diff] [blame] | 206 | if (!ti) |
| 207 | return; |
| 208 | |
Joe Stringer | 74ed7ab | 2015-01-21 16:42:52 -0800 | [diff] [blame] | 209 | BUG_ON(!ufid_ti); |
Andy Zhou | e80857c | 2014-01-21 09:31:04 -0800 | [diff] [blame] | 210 | if (ti->keep_flows) |
| 211 | goto skip_flows; |
| 212 | |
| 213 | for (i = 0; i < ti->n_buckets; i++) { |
| 214 | struct sw_flow *flow; |
Kent Overstreet | ee9c5e6 | 2019-03-11 23:31:02 -0700 | [diff] [blame] | 215 | struct hlist_head *head = &ti->buckets[i]; |
Andy Zhou | e80857c | 2014-01-21 09:31:04 -0800 | [diff] [blame] | 216 | struct hlist_node *n; |
| 217 | int ver = ti->node_ver; |
Joe Stringer | 74ed7ab | 2015-01-21 16:42:52 -0800 | [diff] [blame] | 218 | int ufid_ver = ufid_ti->node_ver; |
Andy Zhou | e80857c | 2014-01-21 09:31:04 -0800 | [diff] [blame] | 219 | |
Joe Stringer | 74ed7ab | 2015-01-21 16:42:52 -0800 | [diff] [blame] | 220 | hlist_for_each_entry_safe(flow, n, head, flow_table.node[ver]) { |
| 221 | hlist_del_rcu(&flow->flow_table.node[ver]); |
| 222 | if (ovs_identifier_is_ufid(&flow->id)) |
| 223 | hlist_del_rcu(&flow->ufid_table.node[ufid_ver]); |
Andy Zhou | e80857c | 2014-01-21 09:31:04 -0800 | [diff] [blame] | 224 | ovs_flow_free(flow, deferred); |
| 225 | } |
| 226 | } |
| 227 | |
| 228 | skip_flows: |
Joe Stringer | 74ed7ab | 2015-01-21 16:42:52 -0800 | [diff] [blame] | 229 | if (deferred) { |
Pravin B Shelar | b637e49 | 2013-10-04 00:14:23 -0700 | [diff] [blame] | 230 | call_rcu(&ti->rcu, flow_tbl_destroy_rcu_cb); |
Joe Stringer | 74ed7ab | 2015-01-21 16:42:52 -0800 | [diff] [blame] | 231 | call_rcu(&ufid_ti->rcu, flow_tbl_destroy_rcu_cb); |
| 232 | } else { |
Pravin B Shelar | b637e49 | 2013-10-04 00:14:23 -0700 | [diff] [blame] | 233 | __table_instance_destroy(ti); |
Joe Stringer | 74ed7ab | 2015-01-21 16:42:52 -0800 | [diff] [blame] | 234 | __table_instance_destroy(ufid_ti); |
| 235 | } |
Pravin B Shelar | e644571 | 2013-10-03 18:16:47 -0700 | [diff] [blame] | 236 | } |
| 237 | |
Pravin B Shelar | 9b996e5 | 2014-05-06 18:41:20 -0700 | [diff] [blame] | 238 | /* No need for locking this function is called from RCU callback or |
| 239 | * error path. |
| 240 | */ |
| 241 | void ovs_flow_tbl_destroy(struct flow_table *table) |
Pravin B Shelar | e644571 | 2013-10-03 18:16:47 -0700 | [diff] [blame] | 242 | { |
Pravin B Shelar | 9b996e5 | 2014-05-06 18:41:20 -0700 | [diff] [blame] | 243 | struct table_instance *ti = rcu_dereference_raw(table->ti); |
Joe Stringer | 74ed7ab | 2015-01-21 16:42:52 -0800 | [diff] [blame] | 244 | struct table_instance *ufid_ti = rcu_dereference_raw(table->ufid_ti); |
Pravin B Shelar | e644571 | 2013-10-03 18:16:47 -0700 | [diff] [blame] | 245 | |
Joe Stringer | 74ed7ab | 2015-01-21 16:42:52 -0800 | [diff] [blame] | 246 | table_instance_destroy(ti, ufid_ti, false); |
Pravin B Shelar | e644571 | 2013-10-03 18:16:47 -0700 | [diff] [blame] | 247 | } |
| 248 | |
Pravin B Shelar | b637e49 | 2013-10-04 00:14:23 -0700 | [diff] [blame] | 249 | struct sw_flow *ovs_flow_tbl_dump_next(struct table_instance *ti, |
Pravin B Shelar | e644571 | 2013-10-03 18:16:47 -0700 | [diff] [blame] | 250 | u32 *bucket, u32 *last) |
| 251 | { |
| 252 | struct sw_flow *flow; |
| 253 | struct hlist_head *head; |
| 254 | int ver; |
| 255 | int i; |
| 256 | |
Pravin B Shelar | b637e49 | 2013-10-04 00:14:23 -0700 | [diff] [blame] | 257 | ver = ti->node_ver; |
| 258 | while (*bucket < ti->n_buckets) { |
Pravin B Shelar | e644571 | 2013-10-03 18:16:47 -0700 | [diff] [blame] | 259 | i = 0; |
Kent Overstreet | ee9c5e6 | 2019-03-11 23:31:02 -0700 | [diff] [blame] | 260 | head = &ti->buckets[*bucket]; |
Joe Stringer | 74ed7ab | 2015-01-21 16:42:52 -0800 | [diff] [blame] | 261 | hlist_for_each_entry_rcu(flow, head, flow_table.node[ver]) { |
Pravin B Shelar | e644571 | 2013-10-03 18:16:47 -0700 | [diff] [blame] | 262 | if (i < *last) { |
| 263 | i++; |
| 264 | continue; |
| 265 | } |
| 266 | *last = i + 1; |
| 267 | return flow; |
| 268 | } |
| 269 | (*bucket)++; |
| 270 | *last = 0; |
| 271 | } |
| 272 | |
| 273 | return NULL; |
| 274 | } |
| 275 | |
Pravin B Shelar | b637e49 | 2013-10-04 00:14:23 -0700 | [diff] [blame] | 276 | static struct hlist_head *find_bucket(struct table_instance *ti, u32 hash) |
Pravin B Shelar | e644571 | 2013-10-03 18:16:47 -0700 | [diff] [blame] | 277 | { |
Pravin B Shelar | b637e49 | 2013-10-04 00:14:23 -0700 | [diff] [blame] | 278 | hash = jhash_1word(hash, ti->hash_seed); |
Kent Overstreet | ee9c5e6 | 2019-03-11 23:31:02 -0700 | [diff] [blame] | 279 | return &ti->buckets[hash & (ti->n_buckets - 1)]; |
Pravin B Shelar | e644571 | 2013-10-03 18:16:47 -0700 | [diff] [blame] | 280 | } |
| 281 | |
Joe Stringer | 74ed7ab | 2015-01-21 16:42:52 -0800 | [diff] [blame] | 282 | static void table_instance_insert(struct table_instance *ti, |
| 283 | struct sw_flow *flow) |
Pravin B Shelar | e644571 | 2013-10-03 18:16:47 -0700 | [diff] [blame] | 284 | { |
| 285 | struct hlist_head *head; |
| 286 | |
Joe Stringer | 74ed7ab | 2015-01-21 16:42:52 -0800 | [diff] [blame] | 287 | head = find_bucket(ti, flow->flow_table.hash); |
| 288 | hlist_add_head_rcu(&flow->flow_table.node[ti->node_ver], head); |
| 289 | } |
| 290 | |
| 291 | static void ufid_table_instance_insert(struct table_instance *ti, |
| 292 | struct sw_flow *flow) |
| 293 | { |
| 294 | struct hlist_head *head; |
| 295 | |
| 296 | head = find_bucket(ti, flow->ufid_table.hash); |
| 297 | hlist_add_head_rcu(&flow->ufid_table.node[ti->node_ver], head); |
Pravin B Shelar | e644571 | 2013-10-03 18:16:47 -0700 | [diff] [blame] | 298 | } |
| 299 | |
Pravin B Shelar | b637e49 | 2013-10-04 00:14:23 -0700 | [diff] [blame] | 300 | static void flow_table_copy_flows(struct table_instance *old, |
Joe Stringer | 74ed7ab | 2015-01-21 16:42:52 -0800 | [diff] [blame] | 301 | struct table_instance *new, bool ufid) |
Pravin B Shelar | e644571 | 2013-10-03 18:16:47 -0700 | [diff] [blame] | 302 | { |
| 303 | int old_ver; |
| 304 | int i; |
| 305 | |
| 306 | old_ver = old->node_ver; |
| 307 | new->node_ver = !old_ver; |
| 308 | |
| 309 | /* Insert in new table. */ |
| 310 | for (i = 0; i < old->n_buckets; i++) { |
| 311 | struct sw_flow *flow; |
Kent Overstreet | ee9c5e6 | 2019-03-11 23:31:02 -0700 | [diff] [blame] | 312 | struct hlist_head *head = &old->buckets[i]; |
Pravin B Shelar | e644571 | 2013-10-03 18:16:47 -0700 | [diff] [blame] | 313 | |
Joe Stringer | 74ed7ab | 2015-01-21 16:42:52 -0800 | [diff] [blame] | 314 | if (ufid) |
| 315 | hlist_for_each_entry(flow, head, |
| 316 | ufid_table.node[old_ver]) |
| 317 | ufid_table_instance_insert(new, flow); |
| 318 | else |
| 319 | hlist_for_each_entry(flow, head, |
| 320 | flow_table.node[old_ver]) |
| 321 | table_instance_insert(new, flow); |
Pravin B Shelar | e644571 | 2013-10-03 18:16:47 -0700 | [diff] [blame] | 322 | } |
| 323 | |
Pravin B Shelar | e644571 | 2013-10-03 18:16:47 -0700 | [diff] [blame] | 324 | old->keep_flows = true; |
| 325 | } |
| 326 | |
Pravin B Shelar | b637e49 | 2013-10-04 00:14:23 -0700 | [diff] [blame] | 327 | static struct table_instance *table_instance_rehash(struct table_instance *ti, |
Joe Stringer | 74ed7ab | 2015-01-21 16:42:52 -0800 | [diff] [blame] | 328 | int n_buckets, bool ufid) |
Pravin B Shelar | e644571 | 2013-10-03 18:16:47 -0700 | [diff] [blame] | 329 | { |
Pravin B Shelar | b637e49 | 2013-10-04 00:14:23 -0700 | [diff] [blame] | 330 | struct table_instance *new_ti; |
Pravin B Shelar | e644571 | 2013-10-03 18:16:47 -0700 | [diff] [blame] | 331 | |
Pravin B Shelar | b637e49 | 2013-10-04 00:14:23 -0700 | [diff] [blame] | 332 | new_ti = table_instance_alloc(n_buckets); |
| 333 | if (!new_ti) |
Pravin B Shelar | 618ed0c | 2013-10-04 00:17:42 -0700 | [diff] [blame] | 334 | return NULL; |
Pravin B Shelar | e644571 | 2013-10-03 18:16:47 -0700 | [diff] [blame] | 335 | |
Joe Stringer | 74ed7ab | 2015-01-21 16:42:52 -0800 | [diff] [blame] | 336 | flow_table_copy_flows(ti, new_ti, ufid); |
Pravin B Shelar | e644571 | 2013-10-03 18:16:47 -0700 | [diff] [blame] | 337 | |
Pravin B Shelar | b637e49 | 2013-10-04 00:14:23 -0700 | [diff] [blame] | 338 | return new_ti; |
Pravin B Shelar | e644571 | 2013-10-03 18:16:47 -0700 | [diff] [blame] | 339 | } |
| 340 | |
Pravin B Shelar | b637e49 | 2013-10-04 00:14:23 -0700 | [diff] [blame] | 341 | int ovs_flow_tbl_flush(struct flow_table *flow_table) |
Pravin B Shelar | e644571 | 2013-10-03 18:16:47 -0700 | [diff] [blame] | 342 | { |
Joe Stringer | 74ed7ab | 2015-01-21 16:42:52 -0800 | [diff] [blame] | 343 | struct table_instance *old_ti, *new_ti; |
| 344 | struct table_instance *old_ufid_ti, *new_ufid_ti; |
Pravin B Shelar | e644571 | 2013-10-03 18:16:47 -0700 | [diff] [blame] | 345 | |
Pravin B Shelar | b637e49 | 2013-10-04 00:14:23 -0700 | [diff] [blame] | 346 | new_ti = table_instance_alloc(TBL_MIN_BUCKETS); |
| 347 | if (!new_ti) |
| 348 | return -ENOMEM; |
Joe Stringer | 74ed7ab | 2015-01-21 16:42:52 -0800 | [diff] [blame] | 349 | new_ufid_ti = table_instance_alloc(TBL_MIN_BUCKETS); |
| 350 | if (!new_ufid_ti) |
| 351 | goto err_free_ti; |
| 352 | |
| 353 | old_ti = ovsl_dereference(flow_table->ti); |
| 354 | old_ufid_ti = ovsl_dereference(flow_table->ufid_ti); |
Pravin B Shelar | b637e49 | 2013-10-04 00:14:23 -0700 | [diff] [blame] | 355 | |
| 356 | rcu_assign_pointer(flow_table->ti, new_ti); |
Joe Stringer | 74ed7ab | 2015-01-21 16:42:52 -0800 | [diff] [blame] | 357 | rcu_assign_pointer(flow_table->ufid_ti, new_ufid_ti); |
Pravin B Shelar | b637e49 | 2013-10-04 00:14:23 -0700 | [diff] [blame] | 358 | flow_table->last_rehash = jiffies; |
| 359 | flow_table->count = 0; |
Joe Stringer | 74ed7ab | 2015-01-21 16:42:52 -0800 | [diff] [blame] | 360 | flow_table->ufid_count = 0; |
Pravin B Shelar | b637e49 | 2013-10-04 00:14:23 -0700 | [diff] [blame] | 361 | |
Joe Stringer | 74ed7ab | 2015-01-21 16:42:52 -0800 | [diff] [blame] | 362 | table_instance_destroy(old_ti, old_ufid_ti, true); |
Pravin B Shelar | b637e49 | 2013-10-04 00:14:23 -0700 | [diff] [blame] | 363 | return 0; |
Joe Stringer | 74ed7ab | 2015-01-21 16:42:52 -0800 | [diff] [blame] | 364 | |
| 365 | err_free_ti: |
| 366 | __table_instance_destroy(new_ti); |
| 367 | return -ENOMEM; |
Pravin B Shelar | e644571 | 2013-10-03 18:16:47 -0700 | [diff] [blame] | 368 | } |
| 369 | |
Joe Stringer | 272c2cf | 2015-01-21 16:42:50 -0800 | [diff] [blame] | 370 | static u32 flow_hash(const struct sw_flow_key *key, |
| 371 | const struct sw_flow_key_range *range) |
Pravin B Shelar | e644571 | 2013-10-03 18:16:47 -0700 | [diff] [blame] | 372 | { |
Joe Stringer | 272c2cf | 2015-01-21 16:42:50 -0800 | [diff] [blame] | 373 | int key_start = range->start; |
| 374 | int key_end = range->end; |
Daniele Di Proietto | 7085130 | 2014-01-23 10:56:49 -0800 | [diff] [blame] | 375 | const u32 *hash_key = (const u32 *)((const u8 *)key + key_start); |
Pravin B Shelar | e644571 | 2013-10-03 18:16:47 -0700 | [diff] [blame] | 376 | int hash_u32s = (key_end - key_start) >> 2; |
| 377 | |
| 378 | /* Make sure number of hash bytes are multiple of u32. */ |
| 379 | BUILD_BUG_ON(sizeof(long) % sizeof(u32)); |
| 380 | |
Daniel Borkmann | 8754589 | 2014-12-10 16:33:11 +0100 | [diff] [blame] | 381 | return jhash2(hash_key, hash_u32s, 0); |
Pravin B Shelar | e644571 | 2013-10-03 18:16:47 -0700 | [diff] [blame] | 382 | } |
| 383 | |
| 384 | static int flow_key_start(const struct sw_flow_key *key) |
| 385 | { |
Jiri Benc | 00a93ba | 2015-10-05 13:09:46 +0200 | [diff] [blame] | 386 | if (key->tun_proto) |
Pravin B Shelar | e644571 | 2013-10-03 18:16:47 -0700 | [diff] [blame] | 387 | return 0; |
| 388 | else |
| 389 | return rounddown(offsetof(struct sw_flow_key, phy), |
| 390 | sizeof(long)); |
| 391 | } |
| 392 | |
| 393 | static bool cmp_key(const struct sw_flow_key *key1, |
| 394 | const struct sw_flow_key *key2, |
| 395 | int key_start, int key_end) |
| 396 | { |
Daniele Di Proietto | 7085130 | 2014-01-23 10:56:49 -0800 | [diff] [blame] | 397 | const long *cp1 = (const long *)((const u8 *)key1 + key_start); |
| 398 | const long *cp2 = (const long *)((const u8 *)key2 + key_start); |
Pravin B Shelar | e644571 | 2013-10-03 18:16:47 -0700 | [diff] [blame] | 399 | long diffs = 0; |
| 400 | int i; |
| 401 | |
| 402 | for (i = key_start; i < key_end; i += sizeof(long)) |
| 403 | diffs |= *cp1++ ^ *cp2++; |
| 404 | |
| 405 | return diffs == 0; |
| 406 | } |
| 407 | |
| 408 | static bool flow_cmp_masked_key(const struct sw_flow *flow, |
| 409 | const struct sw_flow_key *key, |
Joe Stringer | 272c2cf | 2015-01-21 16:42:50 -0800 | [diff] [blame] | 410 | const struct sw_flow_key_range *range) |
Pravin B Shelar | e644571 | 2013-10-03 18:16:47 -0700 | [diff] [blame] | 411 | { |
Joe Stringer | 272c2cf | 2015-01-21 16:42:50 -0800 | [diff] [blame] | 412 | return cmp_key(&flow->key, key, range->start, range->end); |
Pravin B Shelar | e644571 | 2013-10-03 18:16:47 -0700 | [diff] [blame] | 413 | } |
| 414 | |
Joe Stringer | 74ed7ab | 2015-01-21 16:42:52 -0800 | [diff] [blame] | 415 | static bool ovs_flow_cmp_unmasked_key(const struct sw_flow *flow, |
| 416 | const struct sw_flow_match *match) |
Pravin B Shelar | e644571 | 2013-10-03 18:16:47 -0700 | [diff] [blame] | 417 | { |
| 418 | struct sw_flow_key *key = match->key; |
| 419 | int key_start = flow_key_start(key); |
| 420 | int key_end = match->range.end; |
| 421 | |
Joe Stringer | 74ed7ab | 2015-01-21 16:42:52 -0800 | [diff] [blame] | 422 | BUG_ON(ovs_identifier_is_ufid(&flow->id)); |
| 423 | return cmp_key(flow->id.unmasked_key, key, key_start, key_end); |
Pravin B Shelar | e644571 | 2013-10-03 18:16:47 -0700 | [diff] [blame] | 424 | } |
| 425 | |
Pravin B Shelar | b637e49 | 2013-10-04 00:14:23 -0700 | [diff] [blame] | 426 | static struct sw_flow *masked_flow_lookup(struct table_instance *ti, |
Pravin B Shelar | e644571 | 2013-10-03 18:16:47 -0700 | [diff] [blame] | 427 | const struct sw_flow_key *unmasked, |
Thomas Graf | 12eb18f | 2014-11-06 06:58:52 -0800 | [diff] [blame] | 428 | const struct sw_flow_mask *mask) |
Pravin B Shelar | e644571 | 2013-10-03 18:16:47 -0700 | [diff] [blame] | 429 | { |
| 430 | struct sw_flow *flow; |
| 431 | struct hlist_head *head; |
Pravin B Shelar | e644571 | 2013-10-03 18:16:47 -0700 | [diff] [blame] | 432 | u32 hash; |
| 433 | struct sw_flow_key masked_key; |
| 434 | |
Jesse Gross | ae5f2fb | 2015-09-21 20:21:20 -0700 | [diff] [blame] | 435 | ovs_flow_mask_key(&masked_key, unmasked, false, mask); |
Joe Stringer | 272c2cf | 2015-01-21 16:42:50 -0800 | [diff] [blame] | 436 | hash = flow_hash(&masked_key, &mask->range); |
Pravin B Shelar | b637e49 | 2013-10-04 00:14:23 -0700 | [diff] [blame] | 437 | head = find_bucket(ti, hash); |
Joe Stringer | 74ed7ab | 2015-01-21 16:42:52 -0800 | [diff] [blame] | 438 | hlist_for_each_entry_rcu(flow, head, flow_table.node[ti->node_ver]) { |
| 439 | if (flow->mask == mask && flow->flow_table.hash == hash && |
Joe Stringer | 272c2cf | 2015-01-21 16:42:50 -0800 | [diff] [blame] | 440 | flow_cmp_masked_key(flow, &masked_key, &mask->range)) |
Pravin B Shelar | e644571 | 2013-10-03 18:16:47 -0700 | [diff] [blame] | 441 | return flow; |
| 442 | } |
| 443 | return NULL; |
| 444 | } |
| 445 | |
Andy Zhou | 5bb5063 | 2013-11-25 10:42:46 -0800 | [diff] [blame] | 446 | struct sw_flow *ovs_flow_tbl_lookup_stats(struct flow_table *tbl, |
Andy Zhou | 1bd7116 | 2013-10-22 10:42:46 -0700 | [diff] [blame] | 447 | const struct sw_flow_key *key, |
| 448 | u32 *n_mask_hit) |
Pravin B Shelar | e644571 | 2013-10-03 18:16:47 -0700 | [diff] [blame] | 449 | { |
Jesse Gross | 663efa3 | 2013-12-03 10:58:53 -0800 | [diff] [blame] | 450 | struct table_instance *ti = rcu_dereference_ovsl(tbl->ti); |
Pravin B Shelar | e644571 | 2013-10-03 18:16:47 -0700 | [diff] [blame] | 451 | struct sw_flow_mask *mask; |
Pravin B Shelar | b637e49 | 2013-10-04 00:14:23 -0700 | [diff] [blame] | 452 | struct sw_flow *flow; |
Pravin B Shelar | e644571 | 2013-10-03 18:16:47 -0700 | [diff] [blame] | 453 | |
Andy Zhou | 1bd7116 | 2013-10-22 10:42:46 -0700 | [diff] [blame] | 454 | *n_mask_hit = 0; |
Pravin B Shelar | b637e49 | 2013-10-04 00:14:23 -0700 | [diff] [blame] | 455 | list_for_each_entry_rcu(mask, &tbl->mask_list, list) { |
Andy Zhou | 1bd7116 | 2013-10-22 10:42:46 -0700 | [diff] [blame] | 456 | (*n_mask_hit)++; |
Pravin B Shelar | b637e49 | 2013-10-04 00:14:23 -0700 | [diff] [blame] | 457 | flow = masked_flow_lookup(ti, key, mask); |
Pravin B Shelar | e644571 | 2013-10-03 18:16:47 -0700 | [diff] [blame] | 458 | if (flow) /* Found */ |
Pravin B Shelar | b637e49 | 2013-10-04 00:14:23 -0700 | [diff] [blame] | 459 | return flow; |
Pravin B Shelar | e644571 | 2013-10-03 18:16:47 -0700 | [diff] [blame] | 460 | } |
Pravin B Shelar | b637e49 | 2013-10-04 00:14:23 -0700 | [diff] [blame] | 461 | return NULL; |
| 462 | } |
Pravin B Shelar | e644571 | 2013-10-03 18:16:47 -0700 | [diff] [blame] | 463 | |
Andy Zhou | 5bb5063 | 2013-11-25 10:42:46 -0800 | [diff] [blame] | 464 | struct sw_flow *ovs_flow_tbl_lookup(struct flow_table *tbl, |
| 465 | const struct sw_flow_key *key) |
| 466 | { |
| 467 | u32 __always_unused n_mask_hit; |
| 468 | |
| 469 | return ovs_flow_tbl_lookup_stats(tbl, key, &n_mask_hit); |
| 470 | } |
| 471 | |
Alex Wang | 4a46b24 | 2014-06-30 20:30:29 -0700 | [diff] [blame] | 472 | struct sw_flow *ovs_flow_tbl_lookup_exact(struct flow_table *tbl, |
Thomas Graf | 12eb18f | 2014-11-06 06:58:52 -0800 | [diff] [blame] | 473 | const struct sw_flow_match *match) |
Alex Wang | 4a46b24 | 2014-06-30 20:30:29 -0700 | [diff] [blame] | 474 | { |
| 475 | struct table_instance *ti = rcu_dereference_ovsl(tbl->ti); |
| 476 | struct sw_flow_mask *mask; |
| 477 | struct sw_flow *flow; |
| 478 | |
| 479 | /* Always called under ovs-mutex. */ |
| 480 | list_for_each_entry(mask, &tbl->mask_list, list) { |
| 481 | flow = masked_flow_lookup(ti, match->key, mask); |
Joe Stringer | 74ed7ab | 2015-01-21 16:42:52 -0800 | [diff] [blame] | 482 | if (flow && ovs_identifier_is_key(&flow->id) && |
| 483 | ovs_flow_cmp_unmasked_key(flow, match)) |
| 484 | return flow; |
| 485 | } |
| 486 | return NULL; |
| 487 | } |
| 488 | |
| 489 | static u32 ufid_hash(const struct sw_flow_id *sfid) |
| 490 | { |
| 491 | return jhash(sfid->ufid, sfid->ufid_len, 0); |
| 492 | } |
| 493 | |
| 494 | static bool ovs_flow_cmp_ufid(const struct sw_flow *flow, |
| 495 | const struct sw_flow_id *sfid) |
| 496 | { |
| 497 | if (flow->id.ufid_len != sfid->ufid_len) |
| 498 | return false; |
| 499 | |
| 500 | return !memcmp(flow->id.ufid, sfid->ufid, sfid->ufid_len); |
| 501 | } |
| 502 | |
| 503 | bool ovs_flow_cmp(const struct sw_flow *flow, const struct sw_flow_match *match) |
| 504 | { |
| 505 | if (ovs_identifier_is_ufid(&flow->id)) |
| 506 | return flow_cmp_masked_key(flow, match->key, &match->range); |
| 507 | |
| 508 | return ovs_flow_cmp_unmasked_key(flow, match); |
| 509 | } |
| 510 | |
| 511 | struct sw_flow *ovs_flow_tbl_lookup_ufid(struct flow_table *tbl, |
| 512 | const struct sw_flow_id *ufid) |
| 513 | { |
| 514 | struct table_instance *ti = rcu_dereference_ovsl(tbl->ufid_ti); |
| 515 | struct sw_flow *flow; |
| 516 | struct hlist_head *head; |
| 517 | u32 hash; |
| 518 | |
| 519 | hash = ufid_hash(ufid); |
| 520 | head = find_bucket(ti, hash); |
| 521 | hlist_for_each_entry_rcu(flow, head, ufid_table.node[ti->node_ver]) { |
| 522 | if (flow->ufid_table.hash == hash && |
| 523 | ovs_flow_cmp_ufid(flow, ufid)) |
Alex Wang | 4a46b24 | 2014-06-30 20:30:29 -0700 | [diff] [blame] | 524 | return flow; |
| 525 | } |
| 526 | return NULL; |
| 527 | } |
| 528 | |
Andy Zhou | 1bd7116 | 2013-10-22 10:42:46 -0700 | [diff] [blame] | 529 | int ovs_flow_tbl_num_masks(const struct flow_table *table) |
| 530 | { |
| 531 | struct sw_flow_mask *mask; |
| 532 | int num = 0; |
| 533 | |
| 534 | list_for_each_entry(mask, &table->mask_list, list) |
| 535 | num++; |
| 536 | |
| 537 | return num; |
| 538 | } |
| 539 | |
Joe Stringer | 74ed7ab | 2015-01-21 16:42:52 -0800 | [diff] [blame] | 540 | static struct table_instance *table_instance_expand(struct table_instance *ti, |
| 541 | bool ufid) |
Pravin B Shelar | b637e49 | 2013-10-04 00:14:23 -0700 | [diff] [blame] | 542 | { |
Joe Stringer | 74ed7ab | 2015-01-21 16:42:52 -0800 | [diff] [blame] | 543 | return table_instance_rehash(ti, ti->n_buckets * 2, ufid); |
Pravin B Shelar | e644571 | 2013-10-03 18:16:47 -0700 | [diff] [blame] | 544 | } |
| 545 | |
Jarno Rajahalme | 56c1986 | 2014-05-05 13:24:53 -0700 | [diff] [blame] | 546 | /* Remove 'mask' from the mask list, if it is not needed any more. */ |
| 547 | static void flow_mask_remove(struct flow_table *tbl, struct sw_flow_mask *mask) |
| 548 | { |
| 549 | if (mask) { |
| 550 | /* ovs-lock is required to protect mask-refcount and |
| 551 | * mask list. |
| 552 | */ |
| 553 | ASSERT_OVSL(); |
| 554 | BUG_ON(!mask->ref_count); |
| 555 | mask->ref_count--; |
| 556 | |
| 557 | if (!mask->ref_count) { |
| 558 | list_del_rcu(&mask->list); |
| 559 | kfree_rcu(mask, rcu); |
| 560 | } |
| 561 | } |
| 562 | } |
| 563 | |
| 564 | /* Must be called with OVS mutex held. */ |
Pravin B Shelar | e644571 | 2013-10-03 18:16:47 -0700 | [diff] [blame] | 565 | void ovs_flow_tbl_remove(struct flow_table *table, struct sw_flow *flow) |
| 566 | { |
Pravin B Shelar | b637e49 | 2013-10-04 00:14:23 -0700 | [diff] [blame] | 567 | struct table_instance *ti = ovsl_dereference(table->ti); |
Joe Stringer | 74ed7ab | 2015-01-21 16:42:52 -0800 | [diff] [blame] | 568 | struct table_instance *ufid_ti = ovsl_dereference(table->ufid_ti); |
Pravin B Shelar | b637e49 | 2013-10-04 00:14:23 -0700 | [diff] [blame] | 569 | |
Pravin B Shelar | e644571 | 2013-10-03 18:16:47 -0700 | [diff] [blame] | 570 | BUG_ON(table->count == 0); |
Joe Stringer | 74ed7ab | 2015-01-21 16:42:52 -0800 | [diff] [blame] | 571 | hlist_del_rcu(&flow->flow_table.node[ti->node_ver]); |
Pravin B Shelar | e644571 | 2013-10-03 18:16:47 -0700 | [diff] [blame] | 572 | table->count--; |
Joe Stringer | 74ed7ab | 2015-01-21 16:42:52 -0800 | [diff] [blame] | 573 | if (ovs_identifier_is_ufid(&flow->id)) { |
| 574 | hlist_del_rcu(&flow->ufid_table.node[ufid_ti->node_ver]); |
| 575 | table->ufid_count--; |
| 576 | } |
Jarno Rajahalme | 56c1986 | 2014-05-05 13:24:53 -0700 | [diff] [blame] | 577 | |
| 578 | /* RCU delete the mask. 'flow->mask' is not NULLed, as it should be |
| 579 | * accessible as long as the RCU read lock is held. |
| 580 | */ |
| 581 | flow_mask_remove(table, flow->mask); |
Pravin B Shelar | e644571 | 2013-10-03 18:16:47 -0700 | [diff] [blame] | 582 | } |
| 583 | |
Pravin B Shelar | 618ed0c | 2013-10-04 00:17:42 -0700 | [diff] [blame] | 584 | static struct sw_flow_mask *mask_alloc(void) |
Pravin B Shelar | e644571 | 2013-10-03 18:16:47 -0700 | [diff] [blame] | 585 | { |
| 586 | struct sw_flow_mask *mask; |
| 587 | |
| 588 | mask = kmalloc(sizeof(*mask), GFP_KERNEL); |
| 589 | if (mask) |
Andy Zhou | e80857c | 2014-01-21 09:31:04 -0800 | [diff] [blame] | 590 | mask->ref_count = 1; |
Pravin B Shelar | e644571 | 2013-10-03 18:16:47 -0700 | [diff] [blame] | 591 | |
| 592 | return mask; |
| 593 | } |
| 594 | |
Pravin B Shelar | e644571 | 2013-10-03 18:16:47 -0700 | [diff] [blame] | 595 | static bool mask_equal(const struct sw_flow_mask *a, |
| 596 | const struct sw_flow_mask *b) |
| 597 | { |
Daniele Di Proietto | 7085130 | 2014-01-23 10:56:49 -0800 | [diff] [blame] | 598 | const u8 *a_ = (const u8 *)&a->key + a->range.start; |
| 599 | const u8 *b_ = (const u8 *)&b->key + b->range.start; |
Pravin B Shelar | e644571 | 2013-10-03 18:16:47 -0700 | [diff] [blame] | 600 | |
| 601 | return (a->range.end == b->range.end) |
| 602 | && (a->range.start == b->range.start) |
| 603 | && (memcmp(a_, b_, range_n_bytes(&a->range)) == 0); |
| 604 | } |
| 605 | |
Pravin B Shelar | 618ed0c | 2013-10-04 00:17:42 -0700 | [diff] [blame] | 606 | static struct sw_flow_mask *flow_mask_find(const struct flow_table *tbl, |
Pravin B Shelar | e644571 | 2013-10-03 18:16:47 -0700 | [diff] [blame] | 607 | const struct sw_flow_mask *mask) |
| 608 | { |
| 609 | struct list_head *ml; |
| 610 | |
Pravin B Shelar | b637e49 | 2013-10-04 00:14:23 -0700 | [diff] [blame] | 611 | list_for_each(ml, &tbl->mask_list) { |
Pravin B Shelar | e644571 | 2013-10-03 18:16:47 -0700 | [diff] [blame] | 612 | struct sw_flow_mask *m; |
| 613 | m = container_of(ml, struct sw_flow_mask, list); |
| 614 | if (mask_equal(mask, m)) |
| 615 | return m; |
| 616 | } |
| 617 | |
| 618 | return NULL; |
| 619 | } |
| 620 | |
Ben Pfaff | d121190 | 2013-11-25 10:40:51 -0800 | [diff] [blame] | 621 | /* Add 'mask' into the mask list, if it is not already there. */ |
Pravin B Shelar | 618ed0c | 2013-10-04 00:17:42 -0700 | [diff] [blame] | 622 | static int flow_mask_insert(struct flow_table *tbl, struct sw_flow *flow, |
Thomas Graf | 12eb18f | 2014-11-06 06:58:52 -0800 | [diff] [blame] | 623 | const struct sw_flow_mask *new) |
Pravin B Shelar | e644571 | 2013-10-03 18:16:47 -0700 | [diff] [blame] | 624 | { |
Pravin B Shelar | 618ed0c | 2013-10-04 00:17:42 -0700 | [diff] [blame] | 625 | struct sw_flow_mask *mask; |
| 626 | mask = flow_mask_find(tbl, new); |
| 627 | if (!mask) { |
| 628 | /* Allocate a new mask if none exsits. */ |
| 629 | mask = mask_alloc(); |
| 630 | if (!mask) |
| 631 | return -ENOMEM; |
| 632 | mask->key = new->key; |
| 633 | mask->range = new->range; |
| 634 | list_add_rcu(&mask->list, &tbl->mask_list); |
Andy Zhou | e80857c | 2014-01-21 09:31:04 -0800 | [diff] [blame] | 635 | } else { |
| 636 | BUG_ON(!mask->ref_count); |
| 637 | mask->ref_count++; |
Pravin B Shelar | 618ed0c | 2013-10-04 00:17:42 -0700 | [diff] [blame] | 638 | } |
| 639 | |
Pravin B Shelar | 618ed0c | 2013-10-04 00:17:42 -0700 | [diff] [blame] | 640 | flow->mask = mask; |
| 641 | return 0; |
| 642 | } |
| 643 | |
Jarno Rajahalme | 56c1986 | 2014-05-05 13:24:53 -0700 | [diff] [blame] | 644 | /* Must be called with OVS mutex held. */ |
Joe Stringer | d29ab6f | 2015-01-21 16:42:49 -0800 | [diff] [blame] | 645 | static void flow_key_insert(struct flow_table *table, struct sw_flow *flow) |
Pravin B Shelar | 618ed0c | 2013-10-04 00:17:42 -0700 | [diff] [blame] | 646 | { |
| 647 | struct table_instance *new_ti = NULL; |
| 648 | struct table_instance *ti; |
Pravin B Shelar | 618ed0c | 2013-10-04 00:17:42 -0700 | [diff] [blame] | 649 | |
Joe Stringer | 74ed7ab | 2015-01-21 16:42:52 -0800 | [diff] [blame] | 650 | flow->flow_table.hash = flow_hash(&flow->key, &flow->mask->range); |
Pravin B Shelar | 618ed0c | 2013-10-04 00:17:42 -0700 | [diff] [blame] | 651 | ti = ovsl_dereference(table->ti); |
| 652 | table_instance_insert(ti, flow); |
| 653 | table->count++; |
| 654 | |
| 655 | /* Expand table, if necessary, to make room. */ |
| 656 | if (table->count > ti->n_buckets) |
Joe Stringer | 74ed7ab | 2015-01-21 16:42:52 -0800 | [diff] [blame] | 657 | new_ti = table_instance_expand(ti, false); |
Pravin B Shelar | 618ed0c | 2013-10-04 00:17:42 -0700 | [diff] [blame] | 658 | else if (time_after(jiffies, table->last_rehash + REHASH_INTERVAL)) |
Joe Stringer | 74ed7ab | 2015-01-21 16:42:52 -0800 | [diff] [blame] | 659 | new_ti = table_instance_rehash(ti, ti->n_buckets, false); |
Pravin B Shelar | 618ed0c | 2013-10-04 00:17:42 -0700 | [diff] [blame] | 660 | |
| 661 | if (new_ti) { |
| 662 | rcu_assign_pointer(table->ti, new_ti); |
Joe Stringer | 74ed7ab | 2015-01-21 16:42:52 -0800 | [diff] [blame] | 663 | call_rcu(&ti->rcu, flow_tbl_destroy_rcu_cb); |
Pravin B Shelar | 618ed0c | 2013-10-04 00:17:42 -0700 | [diff] [blame] | 664 | table->last_rehash = jiffies; |
| 665 | } |
Joe Stringer | d29ab6f | 2015-01-21 16:42:49 -0800 | [diff] [blame] | 666 | } |
| 667 | |
| 668 | /* Must be called with OVS mutex held. */ |
Joe Stringer | 74ed7ab | 2015-01-21 16:42:52 -0800 | [diff] [blame] | 669 | static void flow_ufid_insert(struct flow_table *table, struct sw_flow *flow) |
| 670 | { |
| 671 | struct table_instance *ti; |
| 672 | |
| 673 | flow->ufid_table.hash = ufid_hash(&flow->id); |
| 674 | ti = ovsl_dereference(table->ufid_ti); |
| 675 | ufid_table_instance_insert(ti, flow); |
| 676 | table->ufid_count++; |
| 677 | |
| 678 | /* Expand table, if necessary, to make room. */ |
| 679 | if (table->ufid_count > ti->n_buckets) { |
| 680 | struct table_instance *new_ti; |
| 681 | |
| 682 | new_ti = table_instance_expand(ti, true); |
| 683 | if (new_ti) { |
| 684 | rcu_assign_pointer(table->ufid_ti, new_ti); |
| 685 | call_rcu(&ti->rcu, flow_tbl_destroy_rcu_cb); |
| 686 | } |
| 687 | } |
| 688 | } |
| 689 | |
| 690 | /* Must be called with OVS mutex held. */ |
Joe Stringer | d29ab6f | 2015-01-21 16:42:49 -0800 | [diff] [blame] | 691 | int ovs_flow_tbl_insert(struct flow_table *table, struct sw_flow *flow, |
| 692 | const struct sw_flow_mask *mask) |
| 693 | { |
| 694 | int err; |
| 695 | |
| 696 | err = flow_mask_insert(table, flow, mask); |
| 697 | if (err) |
| 698 | return err; |
| 699 | flow_key_insert(table, flow); |
Joe Stringer | 74ed7ab | 2015-01-21 16:42:52 -0800 | [diff] [blame] | 700 | if (ovs_identifier_is_ufid(&flow->id)) |
| 701 | flow_ufid_insert(table, flow); |
Joe Stringer | d29ab6f | 2015-01-21 16:42:49 -0800 | [diff] [blame] | 702 | |
Pravin B Shelar | 618ed0c | 2013-10-04 00:17:42 -0700 | [diff] [blame] | 703 | return 0; |
Pravin B Shelar | e644571 | 2013-10-03 18:16:47 -0700 | [diff] [blame] | 704 | } |
| 705 | |
| 706 | /* Initializes the flow module. |
| 707 | * Returns zero if successful or a negative error code. */ |
| 708 | int ovs_flow_init(void) |
| 709 | { |
| 710 | BUILD_BUG_ON(__alignof__(struct sw_flow_key) % __alignof__(long)); |
| 711 | BUILD_BUG_ON(sizeof(struct sw_flow_key) % sizeof(long)); |
| 712 | |
Jarno Rajahalme | 63e7959 | 2014-03-27 12:42:54 -0700 | [diff] [blame] | 713 | flow_cache = kmem_cache_create("sw_flow", sizeof(struct sw_flow) |
Thadeu Lima de Souza Cascardo | db74a33 | 2016-09-15 19:11:53 -0300 | [diff] [blame] | 714 | + (nr_cpu_ids |
Pablo Neira Ayuso | aef833c | 2019-07-19 18:20:13 +0200 | [diff] [blame] | 715 | * sizeof(struct sw_flow_stats *)), |
Jarno Rajahalme | 63e7959 | 2014-03-27 12:42:54 -0700 | [diff] [blame] | 716 | 0, 0, NULL); |
Pravin B Shelar | e644571 | 2013-10-03 18:16:47 -0700 | [diff] [blame] | 717 | if (flow_cache == NULL) |
| 718 | return -ENOMEM; |
| 719 | |
Jarno Rajahalme | 63e7959 | 2014-03-27 12:42:54 -0700 | [diff] [blame] | 720 | flow_stats_cache |
Pablo Neira Ayuso | aef833c | 2019-07-19 18:20:13 +0200 | [diff] [blame] | 721 | = kmem_cache_create("sw_flow_stats", sizeof(struct sw_flow_stats), |
Jarno Rajahalme | 63e7959 | 2014-03-27 12:42:54 -0700 | [diff] [blame] | 722 | 0, SLAB_HWCACHE_ALIGN, NULL); |
| 723 | if (flow_stats_cache == NULL) { |
| 724 | kmem_cache_destroy(flow_cache); |
| 725 | flow_cache = NULL; |
| 726 | return -ENOMEM; |
| 727 | } |
| 728 | |
Pravin B Shelar | e644571 | 2013-10-03 18:16:47 -0700 | [diff] [blame] | 729 | return 0; |
| 730 | } |
| 731 | |
| 732 | /* Uninitializes the flow module. */ |
| 733 | void ovs_flow_exit(void) |
| 734 | { |
Jarno Rajahalme | 63e7959 | 2014-03-27 12:42:54 -0700 | [diff] [blame] | 735 | kmem_cache_destroy(flow_stats_cache); |
Pravin B Shelar | e644571 | 2013-10-03 18:16:47 -0700 | [diff] [blame] | 736 | kmem_cache_destroy(flow_cache); |
| 737 | } |