Update primary code license to Apache 2.0.
[openvswitch] / datapath / table.c
1 /*
2  * Copyright (c) 2009 Nicira Networks.
3  * Distributed under the terms of the GNU GPL version 2.
4  *
5  * Significant portions of this file may be copied from parts of the Linux
6  * kernel, by Linus Torvalds and others.
7  */
8
9 #include "flow.h"
10 #include "datapath.h"
11
12 #include <linux/gfp.h>
13 #include <linux/jhash.h>
14 #include <linux/slab.h>
15 #include <linux/vmalloc.h>
16 #include <linux/mm.h>
17 #include <linux/highmem.h>
18 #include <asm/pgtable.h>
19
20 static void free_table(struct sw_flow ***flows, unsigned int n_buckets,
21                        int free_flows)
22 {
23         unsigned int i;
24
25         for (i = 0; i < n_buckets >> DP_L1_BITS; i++) {
26                 struct sw_flow **l2 = flows[i];
27                 if (free_flows) {
28                         unsigned int j;
29                         for (j = 0; j < DP_L1_SIZE; j++) {
30                                 if (l2[j])
31                                         flow_free(l2[j]);
32                         }
33                 }
34                 free_page((unsigned long)l2);
35         }
36         kfree(flows);
37 }
38
39 static struct sw_flow ***alloc_table(unsigned int n_buckets)
40 {
41         struct sw_flow ***flows;
42         unsigned int i;
43
44         flows = kmalloc((n_buckets >> DP_L1_BITS) * sizeof(struct sw_flow**),
45                         GFP_KERNEL);
46         if (!flows)
47                 return NULL;
48         for (i = 0; i < n_buckets >> DP_L1_BITS; i++) {
49                 flows[i] = (struct sw_flow **)get_zeroed_page(GFP_KERNEL);
50                 if (!flows[i]) {
51                         free_table(flows, i << DP_L1_BITS, 0);
52                         return NULL;
53                 }
54         }
55         return flows;
56 }
57
58 struct dp_table *dp_table_create(unsigned int n_buckets)
59 {
60         struct dp_table *table;
61
62         table = kzalloc(sizeof *table, GFP_KERNEL);
63         if (!table)
64                 goto err;
65
66         table->n_buckets = n_buckets;
67         table->flows[0] = alloc_table(n_buckets);
68         if (!table[0].flows)
69                 goto err_free_tables;
70
71         table->flows[1] = alloc_table(n_buckets);
72         if (!table->flows[1])
73                 goto err_free_flows0;
74
75         return table;
76
77 err_free_flows0:
78         free_table(table->flows[0], table->n_buckets, 0);
79 err_free_tables:
80         kfree(table);
81 err:
82         return NULL;
83 }
84
85 void dp_table_destroy(struct dp_table *table, int free_flows)
86 {
87         int i;
88         for (i = 0; i < 2; i++)
89                 free_table(table->flows[i], table->n_buckets, free_flows);
90         kfree(table);
91 }
92
93 static struct sw_flow **find_bucket(struct dp_table *table,
94                                     struct sw_flow ***flows, u32 hash)
95 {
96         unsigned int l1 = (hash & (table->n_buckets - 1)) >> DP_L1_SHIFT;
97         unsigned int l2 = hash & ((1 << DP_L2_BITS) - 1);
98         return &flows[l1][l2];
99 }
100
101 static struct sw_flow *lookup_table(struct dp_table *table,
102                                     struct sw_flow ***flows, u32 hash,
103                                     const struct odp_flow_key *key)
104 {
105         struct sw_flow **bucket = find_bucket(table, flows, hash);
106         struct sw_flow *flow = rcu_dereference(*bucket);
107         if (flow && !memcmp(&flow->key, key, sizeof(struct odp_flow_key)))
108                 return flow;
109         return NULL;
110 }
111
112 static u32 flow_hash0(const struct odp_flow_key *key)
113 {
114         return jhash2((u32*)key, sizeof *key / sizeof(u32), 0xaaaaaaaa);
115 }
116
117 static u32 flow_hash1(const struct odp_flow_key *key)
118 {
119         return jhash2((u32*)key, sizeof *key / sizeof(u32), 0x55555555);
120 }
121
122 static void find_buckets(struct dp_table *table,
123                          const struct odp_flow_key *key,
124                          struct sw_flow **buckets[2])
125 {
126         buckets[0] = find_bucket(table, table->flows[0], flow_hash0(key));
127         buckets[1] = find_bucket(table, table->flows[1], flow_hash1(key));
128 }
129
130 struct sw_flow *dp_table_lookup(struct dp_table *table,
131                                 const struct odp_flow_key *key)
132 {
133         struct sw_flow *flow;
134         flow = lookup_table(table, table->flows[0], flow_hash0(key), key);
135         if (!flow)
136                 flow = lookup_table(table, table->flows[1],
137                                     flow_hash1(key), key);
138         return flow;
139 }
140
141 int dp_table_foreach(struct dp_table *table,
142                      int (*callback)(struct sw_flow *flow, void *aux),
143                      void *aux)
144 {
145         unsigned int i, j, k;
146         for (i = 0; i < 2; i++) {
147                 for (j = 0; j < table->n_buckets >> DP_L1_BITS; j++) {
148                         struct sw_flow **l2 = table->flows[i][j];
149                         for (k = 0; k < DP_L1_SIZE; k++) {
150                                 struct sw_flow *flow = rcu_dereference(l2[k]);
151                                 if (flow) {
152                                         int error = callback(flow, aux);
153                                         if (error)
154                                                 return error;
155                                 }
156                         }
157                 }
158         }
159         return 0;
160 }
161
162 static int insert_flow(struct sw_flow *flow, void *new_table_)
163 {
164         struct dp_table *new_table = new_table_;
165         struct sw_flow **buckets[2];
166         int i;
167
168         find_buckets(new_table, &flow->key, buckets);
169         for (i = 0; i < 2; i++) {
170                 if (!*buckets[i]) {
171                         rcu_assign_pointer(*buckets[i], flow);
172                         return 0;
173                 }
174         }
175         WARN_ON_ONCE(1);
176         return 0;
177 }
178
179 static void dp_free_table_rcu(struct rcu_head *rcu)
180 {
181         struct dp_table *table = container_of(rcu, struct dp_table, rcu);
182         dp_table_destroy(table, 0);
183 }
184
185 int dp_table_expand(struct datapath *dp)
186 {
187         struct dp_table *old_table = rcu_dereference(dp->table);
188         struct dp_table *new_table = dp_table_create(old_table->n_buckets * 2);
189         if (!new_table)
190                 return -ENOMEM;
191         dp_table_foreach(old_table, insert_flow, new_table);
192         rcu_assign_pointer(dp->table, new_table);
193         call_rcu(&old_table->rcu, dp_free_table_rcu);
194         return 0;
195 }
196
197 static void dp_free_table_and_flows_rcu(struct rcu_head *rcu)
198 {
199         struct dp_table *table = container_of(rcu, struct dp_table, rcu);
200         dp_table_destroy(table, 1);
201 }
202
203 int dp_table_flush(struct datapath *dp)
204 {
205         struct dp_table *old_table = rcu_dereference(dp->table);
206         struct dp_table *new_table = dp_table_create(DP_L1_SIZE);
207         if (!new_table)
208                 return -ENOMEM;
209         rcu_assign_pointer(dp->table, new_table);
210         call_rcu(&old_table->rcu, dp_free_table_and_flows_rcu);
211         return 0;
212 }
213
214 struct sw_flow **
215 dp_table_lookup_for_insert(struct dp_table *table,
216                            const struct odp_flow_key *target)
217 {
218         struct sw_flow **buckets[2];
219         struct sw_flow **empty_bucket = NULL;
220         int i;
221
222         find_buckets(table, target, buckets);
223         for (i = 0; i < 2; i++) {
224                 struct sw_flow *f = rcu_dereference(*buckets[i]);
225                 if (f) {
226                         if (!memcmp(&f->key, target, sizeof(struct odp_flow_key)))
227                                 return buckets[i];
228                 } else if (!empty_bucket)
229                         empty_bucket = buckets[i];
230         }
231         return empty_bucket;
232 }
233
234 int dp_table_delete(struct dp_table *table, struct sw_flow *target)
235 {
236         struct sw_flow **buckets[2];
237         int i;
238
239         find_buckets(table, &target->key, buckets);
240         for (i = 0; i < 2; i++) {
241                 struct sw_flow *flow = rcu_dereference(*buckets[i]);
242                 if (flow == target) {
243                         rcu_assign_pointer(*buckets[i], NULL);
244                         return 0;
245                 }
246         }
247         return -ENOENT;
248 }