switch/table-hash.c

   1 /* Copyright (C) 2008 Board of Trustees, Leland Stanford Jr. University.
   2  *
   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:
   9  *
  10  * The above copyright notice and this permission notice shall be included in
  11  * all copies or substantial portions of the Software.
  12  *
  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
  19  * IN THE SOFTWARE.
  20  */
  21
  22 #include "table.h"
  23 #include <assert.h>
  24 #include <stdlib.h>
  25 #include <string.h>
  26 #include "crc32.h"
  27 #include "flow.h"
  28 #include "datapath.h"
  29
  30 struct sw_table_hash {
  31     struct sw_table swt;
  32     struct crc32 crc32;
  33     unsigned int n_flows;
  34     unsigned int bucket_mask; /* Number of buckets minus 1. */
  35     struct sw_flow **buckets;
  36 };
  37
  38 static struct sw_flow **find_bucket(struct sw_table *swt,
  39                                     const struct sw_flow_key *key)
  40 {
  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];
  44 }
  45
  46 static struct sw_flow *table_hash_lookup(struct sw_table *swt,
  47                                          const struct sw_flow_key *key)
  48 {
  49     struct sw_flow *flow = *find_bucket(swt, key);
  50     return flow && !memcmp(&flow->key, key, sizeof *key) ? flow : NULL;
  51 }
  52
  53 static int table_hash_insert(struct sw_table *swt, struct sw_flow *flow)
  54 {
  55     struct sw_table_hash *th = (struct sw_table_hash *) swt;
  56     struct sw_flow **bucket;
  57     int retval;
  58
  59     if (flow->key.wildcards != 0)
  60         return 0;
  61
  62     bucket = find_bucket(swt, &flow->key);
  63     if (*bucket == NULL) {
  64         th->n_flows++;
  65         *bucket = flow;
  66         retval = 1;
  67     } else {
  68         struct sw_flow *old_flow = *bucket;
  69         if (!memcmp(&old_flow->key, &flow->key, sizeof flow->key)) {
  70             *bucket = flow;
  71             flow_free(old_flow);
  72             retval = 1;
  73         } else {
  74             retval = 0;
  75         }
  76     }
  77     return retval;
  78 }
  79
  80 /* Caller must update n_flows. */
  81 static void
  82 do_delete(struct sw_flow **bucket)
  83 {
  84     flow_free(*bucket);
  85     *bucket = NULL;
  86 }
  87
  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)
  91 {
  92     struct sw_table_hash *th = (struct sw_table_hash *) swt;
  93     unsigned int count = 0;
  94
  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)) {
  99             do_delete(bucket);
 100             count = 1;
 101         }
 102     } else {
 103         unsigned int i;
 104
 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)) {
 109                 do_delete(bucket);
 110                 count++;
 111             }
 112         }
 113     }
 114     th->n_flows -= count;
 115     return count;
 116 }
 117
 118 static int table_hash_timeout(struct datapath *dp, struct sw_table *swt)
 119 {
 120     struct sw_table_hash *th = (struct sw_table_hash *) swt;
 121     unsigned int i;
 122     int count = 0;
 123
 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);
 129             do_delete(bucket);
 130             count++;
 131         }
 132     }
 133     th->n_flows -= count;
 134     return count;
 135 }
 136
 137 static void table_hash_destroy(struct sw_table *swt)
 138 {
 139     struct sw_table_hash *th = (struct sw_table_hash *) swt;
 140     unsigned int i;
 141     for (i = 0; i <= th->bucket_mask; i++) {
 142         if (th->buckets[i]) {
 143             flow_free(th->buckets[i]);
 144         }
 145     }
 146     free(th->buckets);
 147     free(th);
 148 }
 149
 150 struct swt_iterator_hash {
 151     struct sw_table_hash *th;
 152     unsigned int bucket_i;
 153 };
 154
 155 static struct sw_flow *next_flow(struct swt_iterator_hash *ih)
 156 {
 157     for (;ih->bucket_i <= ih->th->bucket_mask; ih->bucket_i++) {
 158         struct sw_flow *f = ih->th->buckets[ih->bucket_i];
 159         if (f != NULL)
 160             return f;
 161     }
 162
 163     return NULL;
 164 }
 165
 166 static int table_hash_iterator(struct sw_table *swt,
 167                                struct swt_iterator *swt_iter)
 168 {
 169     struct swt_iterator_hash *ih;
 170
 171     swt_iter->private = ih = malloc(sizeof *ih);
 172
 173     if (ih == NULL)
 174         return 0;
 175
 176     ih->th = (struct sw_table_hash *) swt;
 177
 178     ih->bucket_i = 0;
 179     swt_iter->flow = next_flow(ih);
 180
 181     return 1;
 182 }
 183
 184 static void table_hash_next(struct swt_iterator *swt_iter)
 185 {
 186     struct swt_iterator_hash *ih;
 187
 188     if (swt_iter->flow == NULL)
 189         return;
 190
 191     ih = (struct swt_iterator_hash *) swt_iter->private;
 192
 193     ih->bucket_i++;
 194     swt_iter->flow = next_flow(ih);
 195 }
 196
 197 static void table_hash_iterator_destroy(struct swt_iterator *swt_iter)
 198 {
 199     free(swt_iter->private);
 200 }
 201
 202 static void table_hash_stats(struct sw_table *swt,
 203                              struct sw_table_stats *stats)
 204 {
 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;
 209 }
 210
 211 struct sw_table *table_hash_create(unsigned int polynomial,
 212                                    unsigned int n_buckets)
 213 {
 214     struct sw_table_hash *th;
 215     struct sw_table *swt;
 216
 217     th = malloc(sizeof *th);
 218     if (th == NULL)
 219         return NULL;
 220
 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);
 225         free(th);
 226         return NULL;
 227     }
 228     th->bucket_mask = n_buckets - 1;
 229
 230     swt = &th->swt;
 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;
 240
 241     crc32_init(&th->crc32, polynomial);
 242
 243     return swt;
 244 }
 245
 246 /* Double-hashing table. */
 247
 248 struct sw_table_hash2 {
 249     struct sw_table swt;
 250     struct sw_table *subtable[2];
 251 };
 252
 253 static struct sw_flow *table_hash2_lookup(struct sw_table *swt,
 254                                           const struct sw_flow_key *key)
 255 {
 256     struct sw_table_hash2 *t2 = (struct sw_table_hash2 *) swt;
 257     int i;
 258
 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))
 262             return flow;
 263     }
 264     return NULL;
 265 }
 266
 267 static int table_hash2_insert(struct sw_table *swt, struct sw_flow *flow)
 268 {
 269     struct sw_table_hash2 *t2 = (struct sw_table_hash2 *) swt;
 270
 271     if (table_hash_insert(t2->subtable[0], flow))
 272         return 1;
 273     return table_hash_insert(t2->subtable[1], flow);
 274 }
 275
 276 static int table_hash2_delete(struct sw_table *swt,
 277                               const struct sw_flow_key *key, int strict)
 278 {
 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));
 282 }
 283
 284 static int table_hash2_timeout(struct datapath *dp, struct sw_table *swt)
 285 {
 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]));
 289 }
 290
 291 static void table_hash2_destroy(struct sw_table *swt)
 292 {
 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]);
 296     free(t2);
 297 }
 298
 299 struct swt_iterator_hash2 {
 300     struct sw_table_hash2 *th2;
 301     struct swt_iterator ih;
 302     uint8_t table_i;
 303 };
 304
 305 static int table_hash2_iterator(struct sw_table *swt,
 306                                 struct swt_iterator *swt_iter)
 307 {
 308     struct swt_iterator_hash2 *ih2;
 309
 310     swt_iter->private = ih2 = malloc(sizeof *ih2);
 311     if (ih2 == NULL)
 312         return 0;
 313
 314     ih2->th2 = (struct sw_table_hash2 *) swt;
 315     if (!table_hash_iterator(ih2->th2->subtable[0], &ih2->ih)) {
 316         free(ih2);
 317         return 0;
 318     }
 319
 320     if (ih2->ih.flow != NULL) {
 321         swt_iter->flow = ih2->ih.flow;
 322         ih2->table_i = 0;
 323     } else {
 324         table_hash_iterator_destroy(&ih2->ih);
 325         ih2->table_i = 1;
 326         if (!table_hash_iterator(ih2->th2->subtable[1], &ih2->ih)) {
 327             free(ih2);
 328             return 0;
 329         }
 330         swt_iter->flow = ih2->ih.flow;
 331     }
 332
 333     return 1;
 334 }
 335
 336 static void table_hash2_next(struct swt_iterator *swt_iter)
 337 {
 338     struct swt_iterator_hash2 *ih2;
 339
 340     if (swt_iter->flow == NULL)
 341         return;
 342
 343     ih2 = (struct swt_iterator_hash2 *) swt_iter->private;
 344     table_hash_next(&ih2->ih);
 345
 346     if (ih2->ih.flow != NULL) {
 347         swt_iter->flow = ih2->ih.flow;
 348     } else {
 349         if (ih2->table_i == 0) {
 350             table_hash_iterator_destroy(&ih2->ih);
 351             ih2->table_i = 1;
 352             if (!table_hash_iterator(ih2->th2->subtable[1], &ih2->ih)) {
 353                 ih2->ih.private = NULL;
 354                 swt_iter->flow = NULL;
 355             } else {
 356                 swt_iter->flow = ih2->ih.flow;
 357             }
 358         } else {
 359             swt_iter->flow = NULL;
 360         }
 361     }
 362 }
 363
 364 static void table_hash2_iterator_destroy(struct swt_iterator *swt_iter)
 365 {
 366     struct swt_iterator_hash2 *ih2;
 367
 368     ih2 = (struct swt_iterator_hash2 *) swt_iter->private;
 369     if (ih2->ih.private != NULL)
 370         table_hash_iterator_destroy(&ih2->ih);
 371     free(ih2);
 372 }
 373
 374 static void table_hash2_stats(struct sw_table *swt,
 375                               struct sw_table_stats *stats)
 376 {
 377     struct sw_table_hash2 *t2 = (struct sw_table_hash2 *) swt;
 378     struct sw_table_stats substats[2];
 379     int i;
 380
 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;
 386 }
 387
 388 struct sw_table *table_hash2_create(unsigned int poly0, unsigned int buckets0,
 389                                     unsigned int poly1, unsigned int buckets1)
 390
 391 {
 392     struct sw_table_hash2 *t2;
 393     struct sw_table *swt;
 394
 395     t2 = malloc(sizeof *t2);
 396     if (t2 == NULL)
 397         return NULL;
 398
 399     t2->subtable[0] = table_hash_create(poly0, buckets0);
 400     if (t2->subtable[0] == NULL)
 401         goto out_free_t2;
 402
 403     t2->subtable[1] = table_hash_create(poly1, buckets1);
 404     if (t2->subtable[1] == NULL)
 405         goto out_free_subtable0;
 406
 407     swt = &t2->swt;
 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;
 414
 415     swt->iterator = table_hash2_iterator;
 416     swt->iterator_next = table_hash2_next;
 417     swt->iterator_destroy = table_hash2_iterator_destroy;
 418
 419     return swt;
 420
 421 out_free_subtable0:
 422     table_hash_destroy(t2->subtable[0]);
 423 out_free_t2:
 424     free(t2);
 425     return NULL;
 426 }