switch/table-mac.c

   1 /* Copyright (c) 2008 The Board of Trustees of The Leland Stanford
   2  * Junior University
   3  *
   4  * We are making the OpenFlow specification and associated documentation
   5  * (Software) available for public use and benefit with the expectation
   6  * that others will use, modify and enhance the Software and contribute
   7  * those enhancements back to the community. However, since we would
   8  * like to make the Software available for broadest use, with as few
   9  * restrictions as possible permission is hereby granted, free of
  10  * charge, to any person obtaining a copy of this Software to deal in
  11  * the Software under the copyrights without restriction, including
  12  * without limitation the rights to use, copy, modify, merge, publish,
  13  * distribute, sublicense, and/or sell copies of the Software, and to
  14  * permit persons to whom the Software is furnished to do so, subject to
  15  * the following conditions:
  16  *
  17  * The above copyright notice and this permission notice shall be
  18  * included in all copies or substantial portions of the Software.
  19  *
  20  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  21  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  22  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  23  * NONINFRINGEMENT.  IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
  24  * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
  25  * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
  26  * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  27  * SOFTWARE.
  28  *
  29  * The name and trademarks of copyright holder(s) may NOT be used in
  30  * advertising or publicity pertaining to the Software or any
  31  * derivatives without specific, written prior permission.
  32  */
  33
  34 #include "table.h"
  35 #include <assert.h>
  36 #include <stdlib.h>
  37 #include <string.h>
  38 #include "crc32.h"
  39 #include "switch-flow.h"
  40 #include "openflow.h"
  41 #include "datapath.h"
  42
  43 struct sw_table_mac {
  44     struct sw_table swt;
  45     struct crc32 crc32;
  46     unsigned int n_flows;
  47     unsigned int max_flows;
  48     unsigned int bucket_mask; /* Number of buckets minus 1. */
  49     struct list *buckets;
  50 };
  51
  52 static struct list *find_bucket(struct sw_table *swt,
  53                                 const struct sw_flow_key *key)
  54 {
  55     struct sw_table_mac *tm = (struct sw_table_mac *) swt;
  56     unsigned int crc = crc32_calculate(&tm->crc32, key, sizeof *key);
  57     return &tm->buckets[crc & tm->bucket_mask];
  58 }
  59
  60 static struct sw_flow *table_mac_lookup(struct sw_table *swt,
  61                                         const struct sw_flow_key *key)
  62 {
  63     struct list *bucket = find_bucket(swt, key);
  64     struct sw_flow *flow;
  65     LIST_FOR_EACH (flow, struct sw_flow, node, bucket) {
  66         if (!memcmp(key->flow.dl_src, flow->key.flow.dl_src, 6)) {
  67             return flow;
  68         }
  69     }
  70     return NULL;
  71 }
  72
  73 static int table_mac_insert(struct sw_table *swt, struct sw_flow *flow)
  74 {
  75     struct sw_table_mac *tm = (struct sw_table_mac *) swt;
  76     struct list *bucket;
  77     struct sw_flow *f;
  78
  79     /* MAC table only handles flows that match on Ethernet
  80        source address and wildcard everything else. */
  81     if (flow->key.wildcards != (OFPFW_ALL & ~OFPFW_DL_SRC))
  82         return 0;
  83     bucket = find_bucket(swt, &flow->key);
  84
  85     LIST_FOR_EACH (f, struct sw_flow, node, bucket) {
  86         if (!memcmp(f->key.flow.dl_src, flow->key.flow.dl_src, 6)) {
  87             list_replace(&flow->node, &f->node);
  88             flow_free(f);
  89             return 1;
  90         }
  91     }
  92
  93     /* Table overflow? */
  94     if (tm->n_flows >= tm->max_flows) {
  95         return 0;
  96     }
  97     tm->n_flows++;
  98
  99     list_push_front(bucket, &flow->node);
 100     return 1;
 101 }
 102
 103 static void
 104 do_delete(struct sw_flow *flow)
 105 {
 106     list_remove(&flow->node);
 107     flow_free(flow);
 108 }
 109
 110 /* Returns number of deleted flows. */
 111 static int table_mac_delete(struct sw_table *swt,
 112                             const struct sw_flow_key *key, int strict)
 113 {
 114     struct sw_table_mac *tm = (struct sw_table_mac *) swt;
 115
 116     if (key->wildcards == (OFPFW_ALL & ~OFPFW_DL_SRC)) {
 117         struct sw_flow *flow = table_mac_lookup(swt, key);
 118         if (flow) {
 119             do_delete(flow);
 120             tm->n_flows--;
 121             return 1;
 122         }
 123         return 0;
 124     } else {
 125         unsigned int i;
 126         int count = 0;
 127         for (i = 0; i <= tm->bucket_mask; i++) {
 128             struct list *bucket = &tm->buckets[i];
 129             struct sw_flow *flow, *next;
 130             LIST_FOR_EACH_SAFE (flow, next, struct sw_flow, node, bucket) {
 131                 if (flow_del_matches(&flow->key, key, strict)) {
 132                     do_delete(flow);
 133                     count++;
 134                 }
 135             }
 136         }
 137         tm->n_flows -= count;
 138         return count;
 139     }
 140 }
 141
 142 static void table_mac_timeout(struct sw_table *swt, struct list *deleted)
 143 {
 144     struct sw_table_mac *tm = (struct sw_table_mac *) swt;
 145     unsigned int i;
 146
 147     for (i = 0; i <= tm->bucket_mask; i++) {
 148         struct list *bucket = &tm->buckets[i];
 149         struct sw_flow *flow, *next;
 150         LIST_FOR_EACH_SAFE (flow, next, struct sw_flow, node, bucket) {
 151             if (flow_timeout(flow)) {
 152                 list_remove(&flow->node);
 153                 list_push_back(deleted, &flow->node);
 154                 tm->n_flows--;
 155             }
 156         }
 157     }
 158 }
 159
 160 static void table_mac_destroy(struct sw_table *swt)
 161 {
 162     struct sw_table_mac *tm = (struct sw_table_mac *) swt;
 163     unsigned int i;
 164     for (i = 0; i <= tm->bucket_mask; i++) {
 165         struct list *list = &tm->buckets[i];
 166         while (!list_is_empty(list)) {
 167             struct sw_flow *flow = CONTAINER_OF(list_front(list),
 168                                                 struct sw_flow, node);
 169             list_remove(&flow->node);
 170             flow_free(flow);
 171         }
 172     }
 173     free(tm->buckets);
 174     free(tm);
 175 }
 176
 177 struct swt_iterator_mac {
 178     struct sw_table_mac *tm;
 179     unsigned int bucket_i;
 180 };
 181
 182 static struct sw_flow *next_head_flow(struct swt_iterator_mac *im)
 183 {
 184     for (; im->bucket_i <= im->tm->bucket_mask; im->bucket_i++) {
 185         struct list *bucket = &im->tm->buckets[im->bucket_i];
 186         if (!list_is_empty(bucket)) {
 187             return CONTAINER_OF(bucket, struct sw_flow, node);
 188         }
 189     }
 190     return NULL;
 191 }
 192
 193 static int table_mac_iterator(struct sw_table *swt,
 194                               struct swt_iterator *swt_iter)
 195 {
 196     struct swt_iterator_mac *im;
 197
 198     swt_iter->private = im = malloc(sizeof *im);
 199     if (im == NULL)
 200         return 0;
 201
 202     im->tm = (struct sw_table_mac *) swt;
 203
 204     if (!im->tm->n_flows)
 205         swt_iter->flow = NULL;
 206     else {
 207         im->bucket_i = 0;
 208         swt_iter->flow = next_head_flow(im);
 209     }
 210
 211     return 1;
 212 }
 213
 214 static void table_mac_next(struct swt_iterator *swt_iter)
 215 {
 216     struct swt_iterator_mac *im;
 217     struct list *next;
 218
 219     if (swt_iter->flow == NULL)
 220         return;
 221
 222     im = (struct swt_iterator_mac *) swt_iter->private;
 223
 224     next = swt_iter->flow->node.next;
 225     if (next != NULL) {
 226         swt_iter->flow = CONTAINER_OF(next, struct sw_flow, node);
 227     } else {
 228         im->bucket_i++;
 229         swt_iter->flow = next_head_flow(im);
 230     }
 231 }
 232
 233 static void table_mac_iterator_destroy(struct swt_iterator *swt_iter)
 234 {
 235     free(swt_iter->private);
 236 }
 237
 238 static void table_mac_stats(struct sw_table *swt, struct sw_table_stats *stats)
 239 {
 240     struct sw_table_mac *tm = (struct sw_table_mac *) swt;
 241     stats->name = "mac";
 242     stats->n_flows = tm->n_flows;
 243     stats->max_flows = tm->max_flows;
 244 }
 245
 246 struct sw_table *table_mac_create(unsigned int n_buckets,
 247                                   unsigned int max_flows)
 248 {
 249     struct sw_table_mac *tm;
 250     struct sw_table *swt;
 251     unsigned int i;
 252
 253     tm = calloc(1, sizeof *tm);
 254     if (tm == NULL)
 255         return NULL;
 256
 257     assert(!(n_buckets & (n_buckets - 1)));
 258
 259     tm->buckets = malloc(n_buckets * sizeof *tm->buckets);
 260     if (tm->buckets == NULL) {
 261         printf("failed to allocate %u buckets\n", n_buckets);
 262         free(tm);
 263         return NULL;
 264     }
 265     for (i = 0; i < n_buckets; i++) {
 266         list_init(&tm->buckets[i]);
 267     }
 268     tm->bucket_mask = n_buckets - 1;
 269
 270     swt = &tm->swt;
 271     swt->lookup = table_mac_lookup;
 272     swt->insert = table_mac_insert;
 273     swt->delete = table_mac_delete;
 274     swt->timeout = table_mac_timeout;
 275     swt->destroy = table_mac_destroy;
 276     swt->stats = table_mac_stats;
 277
 278     swt->iterator = table_mac_iterator;
 279     swt->iterator_next = table_mac_next;
 280     swt->iterator_destroy = table_mac_iterator_destroy;
 281
 282     crc32_init(&tm->crc32, 0x04C11DB7); /* Ethernet CRC. */
 283     tm->n_flows = 0;
 284     tm->max_flows = max_flows;
 285
 286     return swt;
 287 }