1 /* Copyright (C) 2008 Board of Trustees, Leland Stanford Jr. University.
3 * Permission is hereby granted, free of charge, to any person obtaining a copy
4 * of this software and associated documentation files (the "Software"), to
5 * deal in the Software without restriction, including without limitation the
6 * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
7 * sell copies of the Software, and to permit persons to whom the Software is
8 * furnished to do so, subject to the following conditions:
10 * The above copyright notice and this permission notice shall be included in
11 * all copies or substantial portions of the Software.
13 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
14 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
15 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
16 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
17 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
18 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
30 struct sw_table_hash {
34 unsigned int bucket_mask; /* Number of buckets minus 1. */
35 struct sw_flow **buckets;
38 static struct sw_flow **find_bucket(struct sw_table *swt,
39 const struct sw_flow_key *key)
41 struct sw_table_hash *th = (struct sw_table_hash *) swt;
42 unsigned int crc = crc32_calculate(&th->crc32, key, sizeof *key);
43 return &th->buckets[crc & th->bucket_mask];
46 static struct sw_flow *table_hash_lookup(struct sw_table *swt,
47 const struct sw_flow_key *key)
49 struct sw_flow *flow = *find_bucket(swt, key);
50 return flow && !memcmp(&flow->key, key, sizeof *key) ? flow : NULL;
53 static int table_hash_insert(struct sw_table *swt, struct sw_flow *flow)
55 struct sw_table_hash *th = (struct sw_table_hash *) swt;
56 struct sw_flow **bucket;
59 if (flow->key.wildcards != 0)
62 bucket = find_bucket(swt, &flow->key);
63 if (*bucket == NULL) {
68 struct sw_flow *old_flow = *bucket;
69 if (!memcmp(&old_flow->key, &flow->key, sizeof flow->key)) {
80 /* Caller must update n_flows. */
82 do_delete(struct sw_flow **bucket)
88 /* Returns number of deleted flows. */
89 static int table_hash_delete(struct sw_table *swt,
90 const struct sw_flow_key *key, int strict)
92 struct sw_table_hash *th = (struct sw_table_hash *) swt;
93 unsigned int count = 0;
95 if (key->wildcards == 0) {
96 struct sw_flow **bucket = find_bucket(swt, key);
97 struct sw_flow *flow = *bucket;
98 if (flow && !memcmp(&flow->key, key, sizeof *key)) {
105 for (i = 0; i <= th->bucket_mask; i++) {
106 struct sw_flow **bucket = &th->buckets[i];
107 struct sw_flow *flow = *bucket;
108 if (flow && flow_del_matches(&flow->key, key, strict)) {
114 th->n_flows -= count;
118 static int table_hash_timeout(struct datapath *dp, struct sw_table *swt)
120 struct sw_table_hash *th = (struct sw_table_hash *) swt;
124 for (i = 0; i <= th->bucket_mask; i++) {
125 struct sw_flow **bucket = &th->buckets[i];
126 struct sw_flow *flow = *bucket;
127 if (flow && flow_timeout(flow)) {
128 dp_send_flow_expired(dp, flow);
133 th->n_flows -= count;
137 static void table_hash_destroy(struct sw_table *swt)
139 struct sw_table_hash *th = (struct sw_table_hash *) swt;
141 for (i = 0; i <= th->bucket_mask; i++) {
142 if (th->buckets[i]) {
143 flow_free(th->buckets[i]);
150 struct swt_iterator_hash {
151 struct sw_table_hash *th;
152 unsigned int bucket_i;
155 static struct sw_flow *next_flow(struct swt_iterator_hash *ih)
157 for (;ih->bucket_i <= ih->th->bucket_mask; ih->bucket_i++) {
158 struct sw_flow *f = ih->th->buckets[ih->bucket_i];
166 static int table_hash_iterator(struct sw_table *swt,
167 struct swt_iterator *swt_iter)
169 struct swt_iterator_hash *ih;
171 swt_iter->private = ih = malloc(sizeof *ih);
176 ih->th = (struct sw_table_hash *) swt;
179 swt_iter->flow = next_flow(ih);
184 static void table_hash_next(struct swt_iterator *swt_iter)
186 struct swt_iterator_hash *ih;
188 if (swt_iter->flow == NULL)
191 ih = (struct swt_iterator_hash *) swt_iter->private;
194 swt_iter->flow = next_flow(ih);
197 static void table_hash_iterator_destroy(struct swt_iterator *swt_iter)
199 free(swt_iter->private);
202 static void table_hash_stats(struct sw_table *swt,
203 struct sw_table_stats *stats)
205 struct sw_table_hash *th = (struct sw_table_hash *) swt;
206 stats->name = "hash";
207 stats->n_flows = th->n_flows;
208 stats->max_flows = th->bucket_mask + 1;
211 struct sw_table *table_hash_create(unsigned int polynomial,
212 unsigned int n_buckets)
214 struct sw_table_hash *th;
215 struct sw_table *swt;
217 th = malloc(sizeof *th);
221 assert(!(n_buckets & (n_buckets - 1)));
222 th->buckets = calloc(n_buckets, sizeof *th->buckets);
223 if (th->buckets == NULL) {
224 printf("failed to allocate %u buckets\n", n_buckets);
228 th->bucket_mask = n_buckets - 1;
231 swt->lookup = table_hash_lookup;
232 swt->insert = table_hash_insert;
233 swt->delete = table_hash_delete;
234 swt->timeout = table_hash_timeout;
235 swt->destroy = table_hash_destroy;
236 swt->iterator = table_hash_iterator;
237 swt->iterator_next = table_hash_next;
238 swt->iterator_destroy = table_hash_iterator_destroy;
239 swt->stats = table_hash_stats;
241 crc32_init(&th->crc32, polynomial);
246 /* Double-hashing table. */
248 struct sw_table_hash2 {
250 struct sw_table *subtable[2];
253 static struct sw_flow *table_hash2_lookup(struct sw_table *swt,
254 const struct sw_flow_key *key)
256 struct sw_table_hash2 *t2 = (struct sw_table_hash2 *) swt;
259 for (i = 0; i < 2; i++) {
260 struct sw_flow *flow = *find_bucket(t2->subtable[i], key);
261 if (flow && !memcmp(&flow->key, key, sizeof *key))
267 static int table_hash2_insert(struct sw_table *swt, struct sw_flow *flow)
269 struct sw_table_hash2 *t2 = (struct sw_table_hash2 *) swt;
271 if (table_hash_insert(t2->subtable[0], flow))
273 return table_hash_insert(t2->subtable[1], flow);
276 static int table_hash2_delete(struct sw_table *swt,
277 const struct sw_flow_key *key, int strict)
279 struct sw_table_hash2 *t2 = (struct sw_table_hash2 *) swt;
280 return (table_hash_delete(t2->subtable[0], key, strict)
281 + table_hash_delete(t2->subtable[1], key, strict));
284 static int table_hash2_timeout(struct datapath *dp, struct sw_table *swt)
286 struct sw_table_hash2 *t2 = (struct sw_table_hash2 *) swt;
287 return (table_hash_timeout(dp, t2->subtable[0])
288 + table_hash_timeout(dp, t2->subtable[1]));
291 static void table_hash2_destroy(struct sw_table *swt)
293 struct sw_table_hash2 *t2 = (struct sw_table_hash2 *) swt;
294 table_hash_destroy(t2->subtable[0]);
295 table_hash_destroy(t2->subtable[1]);
299 struct swt_iterator_hash2 {
300 struct sw_table_hash2 *th2;
301 struct swt_iterator ih;
305 static int table_hash2_iterator(struct sw_table *swt,
306 struct swt_iterator *swt_iter)
308 struct swt_iterator_hash2 *ih2;
310 swt_iter->private = ih2 = malloc(sizeof *ih2);
314 ih2->th2 = (struct sw_table_hash2 *) swt;
315 if (!table_hash_iterator(ih2->th2->subtable[0], &ih2->ih)) {
320 if (ih2->ih.flow != NULL) {
321 swt_iter->flow = ih2->ih.flow;
324 table_hash_iterator_destroy(&ih2->ih);
326 if (!table_hash_iterator(ih2->th2->subtable[1], &ih2->ih)) {
330 swt_iter->flow = ih2->ih.flow;
336 static void table_hash2_next(struct swt_iterator *swt_iter)
338 struct swt_iterator_hash2 *ih2;
340 if (swt_iter->flow == NULL)
343 ih2 = (struct swt_iterator_hash2 *) swt_iter->private;
344 table_hash_next(&ih2->ih);
346 if (ih2->ih.flow != NULL) {
347 swt_iter->flow = ih2->ih.flow;
349 if (ih2->table_i == 0) {
350 table_hash_iterator_destroy(&ih2->ih);
352 if (!table_hash_iterator(ih2->th2->subtable[1], &ih2->ih)) {
353 ih2->ih.private = NULL;
354 swt_iter->flow = NULL;
356 swt_iter->flow = ih2->ih.flow;
359 swt_iter->flow = NULL;
364 static void table_hash2_iterator_destroy(struct swt_iterator *swt_iter)
366 struct swt_iterator_hash2 *ih2;
368 ih2 = (struct swt_iterator_hash2 *) swt_iter->private;
369 if (ih2->ih.private != NULL)
370 table_hash_iterator_destroy(&ih2->ih);
374 static void table_hash2_stats(struct sw_table *swt,
375 struct sw_table_stats *stats)
377 struct sw_table_hash2 *t2 = (struct sw_table_hash2 *) swt;
378 struct sw_table_stats substats[2];
381 for (i = 0; i < 2; i++)
382 table_hash_stats(t2->subtable[i], &substats[i]);
383 stats->name = "hash2";
384 stats->n_flows = substats[0].n_flows + substats[1].n_flows;
385 stats->max_flows = substats[0].max_flows + substats[1].max_flows;
388 struct sw_table *table_hash2_create(unsigned int poly0, unsigned int buckets0,
389 unsigned int poly1, unsigned int buckets1)
392 struct sw_table_hash2 *t2;
393 struct sw_table *swt;
395 t2 = malloc(sizeof *t2);
399 t2->subtable[0] = table_hash_create(poly0, buckets0);
400 if (t2->subtable[0] == NULL)
403 t2->subtable[1] = table_hash_create(poly1, buckets1);
404 if (t2->subtable[1] == NULL)
405 goto out_free_subtable0;
408 swt->lookup = table_hash2_lookup;
409 swt->insert = table_hash2_insert;
410 swt->delete = table_hash2_delete;
411 swt->timeout = table_hash2_timeout;
412 swt->destroy = table_hash2_destroy;
413 swt->stats = table_hash2_stats;
415 swt->iterator = table_hash2_iterator;
416 swt->iterator_next = table_hash2_next;
417 swt->iterator_destroy = table_hash2_iterator_destroy;
422 table_hash_destroy(t2->subtable[0]);