5 #include <linux/jhash.h>
6 #include <linux/slab.h>
7 #include <linux/vmalloc.h>
9 #include <linux/highmem.h>
10 #include <asm/pgtable.h>
12 static void free_table(struct sw_flow ***flows, unsigned int n_buckets,
17 for (i = 0; i < n_buckets >> DP_L1_BITS; i++) {
18 struct sw_flow **l2 = flows[i];
21 for (j = 0; j < DP_L1_SIZE; j++) {
26 free_page((unsigned long)l2);
31 static struct sw_flow ***alloc_table(unsigned int n_buckets)
33 struct sw_flow ***flows;
36 flows = kmalloc((n_buckets >> DP_L1_BITS) * sizeof(struct sw_flow**),
40 for (i = 0; i < n_buckets >> DP_L1_BITS; i++) {
41 flows[i] = (struct sw_flow **)get_zeroed_page(GFP_KERNEL);
43 free_table(flows, i << DP_L1_BITS, 0);
50 struct dp_table *dp_table_create(unsigned int n_buckets)
52 struct dp_table *table;
54 table = kzalloc(sizeof *table, GFP_KERNEL);
58 table->n_buckets = n_buckets;
59 table->flows[0] = alloc_table(n_buckets);
63 table->flows[1] = alloc_table(n_buckets);
70 free_table(table->flows[0], table->n_buckets, 0);
77 void dp_table_destroy(struct dp_table *table, int free_flows)
80 for (i = 0; i < 2; i++)
81 free_table(table->flows[i], table->n_buckets, free_flows);
85 static struct sw_flow **find_bucket(struct dp_table *table,
86 struct sw_flow ***flows, u32 hash)
88 unsigned int l1 = (hash & (table->n_buckets - 1)) >> DP_L1_SHIFT;
89 unsigned int l2 = hash & ((1 << DP_L2_BITS) - 1);
90 return &flows[l1][l2];
93 static struct sw_flow *lookup_table(struct dp_table *table,
94 struct sw_flow ***flows, u32 hash,
95 const struct odp_flow_key *key)
97 struct sw_flow **bucket = find_bucket(table, flows, hash);
98 struct sw_flow *flow = rcu_dereference(*bucket);
99 if (flow && !memcmp(&flow->key, key, sizeof(struct odp_flow_key)))
104 static u32 flow_hash0(const struct odp_flow_key *key)
106 return jhash2((u32*)key, sizeof *key / sizeof(u32), 0xaaaaaaaa);
109 static u32 flow_hash1(const struct odp_flow_key *key)
111 return jhash2((u32*)key, sizeof *key / sizeof(u32), 0x55555555);
114 static void find_buckets(struct dp_table *table,
115 const struct odp_flow_key *key,
116 struct sw_flow **buckets[2])
118 buckets[0] = find_bucket(table, table->flows[0], flow_hash0(key));
119 buckets[1] = find_bucket(table, table->flows[1], flow_hash1(key));
122 struct sw_flow *dp_table_lookup(struct dp_table *table,
123 const struct odp_flow_key *key)
125 struct sw_flow *flow;
126 flow = lookup_table(table, table->flows[0], flow_hash0(key), key);
128 flow = lookup_table(table, table->flows[1],
129 flow_hash1(key), key);
133 int dp_table_foreach(struct dp_table *table,
134 int (*callback)(struct sw_flow *flow, void *aux),
137 unsigned int i, j, k;
138 for (i = 0; i < 2; i++) {
139 for (j = 0; j < table->n_buckets >> DP_L1_BITS; j++) {
140 struct sw_flow **l2 = table->flows[i][j];
141 for (k = 0; k < DP_L1_SIZE; k++) {
142 struct sw_flow *flow = rcu_dereference(l2[k]);
144 int error = callback(flow, aux);
154 static int insert_flow(struct sw_flow *flow, void *new_table_)
156 struct dp_table *new_table = new_table_;
157 struct sw_flow **buckets[2];
160 find_buckets(new_table, &flow->key, buckets);
161 for (i = 0; i < 2; i++) {
163 rcu_assign_pointer(*buckets[i], flow);
171 static void dp_free_table_rcu(struct rcu_head *rcu)
173 struct dp_table *table = container_of(rcu, struct dp_table, rcu);
174 dp_table_destroy(table, 0);
177 int dp_table_expand(struct datapath *dp)
179 struct dp_table *old_table = rcu_dereference(dp->table);
180 struct dp_table *new_table = dp_table_create(old_table->n_buckets * 2);
183 dp_table_foreach(old_table, insert_flow, new_table);
184 rcu_assign_pointer(dp->table, new_table);
185 call_rcu(&old_table->rcu, dp_free_table_rcu);
189 static void dp_free_table_and_flows_rcu(struct rcu_head *rcu)
191 struct dp_table *table = container_of(rcu, struct dp_table, rcu);
192 dp_table_destroy(table, 1);
195 int dp_table_flush(struct datapath *dp)
197 struct dp_table *old_table = rcu_dereference(dp->table);
198 struct dp_table *new_table = dp_table_create(DP_L1_SIZE);
201 rcu_assign_pointer(dp->table, new_table);
202 call_rcu(&old_table->rcu, dp_free_table_and_flows_rcu);
207 dp_table_lookup_for_insert(struct dp_table *table,
208 const struct odp_flow_key *target)
210 struct sw_flow **buckets[2];
211 struct sw_flow **empty_bucket = NULL;
214 find_buckets(table, target, buckets);
215 for (i = 0; i < 2; i++) {
216 struct sw_flow *f = rcu_dereference(*buckets[i]);
218 if (!memcmp(&f->key, target, sizeof(struct odp_flow_key)))
220 } else if (!empty_bucket)
221 empty_bucket = buckets[i];
226 int dp_table_delete(struct dp_table *table, struct sw_flow *target)
228 struct sw_flow **buckets[2];
231 find_buckets(table, &target->key, buckets);
232 for (i = 0; i < 2; i++) {
233 struct sw_flow *flow = rcu_dereference(*buckets[i]);
234 if (flow == target) {
235 rcu_assign_pointer(*buckets[i], NULL);