pintos-os.org Git - openvswitch/blob - switch/table-mac.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 "switch-flow.h"
  28 #include "openflow.h"
  29 #include "datapath.h"
  30
  31 struct sw_table_mac {
  32     struct sw_table swt;
  33     struct crc32 crc32;
  34     unsigned int n_flows;
  35     unsigned int max_flows;
  36     unsigned int bucket_mask; /* Number of buckets minus 1. */
  37     struct list *buckets;
  38 };
  39
  40 static struct list *find_bucket(struct sw_table *swt,
  41                                 const struct sw_flow_key *key)
  42 {
  43     struct sw_table_mac *tm = (struct sw_table_mac *) swt;
  44     unsigned int crc = crc32_calculate(&tm->crc32, key, sizeof *key);
  45     return &tm->buckets[crc & tm->bucket_mask];
  46 }
  47
  48 static struct sw_flow *table_mac_lookup(struct sw_table *swt,
  49                                         const struct sw_flow_key *key)
  50 {
  51     struct list *bucket = find_bucket(swt, key);
  52     struct sw_flow *flow;
  53     LIST_FOR_EACH (flow, struct sw_flow, node, bucket) {
  54         if (!memcmp(key->flow.dl_src, flow->key.flow.dl_src, 6)) {
  55             return flow;
  56         }
  57     }
  58     return NULL;
  59 }
  60
  61 static int table_mac_insert(struct sw_table *swt, struct sw_flow *flow)
  62 {
  63     struct sw_table_mac *tm = (struct sw_table_mac *) swt;
  64     struct list *bucket;
  65     struct sw_flow *f;
  66
  67     /* MAC table only handles flows that match on Ethernet
  68        source address and wildcard everything else. */
  69     if (flow->key.wildcards != (OFPFW_ALL & ~OFPFW_DL_SRC))
  70         return 0;
  71     bucket = find_bucket(swt, &flow->key);
  72
  73     LIST_FOR_EACH (f, struct sw_flow, node, bucket) {
  74         if (!memcmp(f->key.flow.dl_src, flow->key.flow.dl_src, 6)) {
  75             list_replace(&flow->node, &f->node);
  76             flow_free(f);
  77             return 1;
  78         }
  79     }
  80
  81     /* Table overflow? */
  82     if (tm->n_flows >= tm->max_flows) {
  83         return 0;
  84     }
  85     tm->n_flows++;
  86
  87     list_push_front(bucket, &flow->node);
  88     return 1;
  89 }
  90
  91 static void
  92 do_delete(struct sw_flow *flow)
  93 {
  94     list_remove(&flow->node);
  95     flow_free(flow);
  96 }
  97
  98 /* Returns number of deleted flows. */
  99 static int table_mac_delete(struct sw_table *swt,
 100                             const struct sw_flow_key *key, int strict)
 101 {
 102     struct sw_table_mac *tm = (struct sw_table_mac *) swt;
 103
 104     if (key->wildcards == (OFPFW_ALL & ~OFPFW_DL_SRC)) {
 105         struct sw_flow *flow = table_mac_lookup(swt, key);
 106         if (flow) {
 107             do_delete(flow);
 108             tm->n_flows--;
 109             return 1;
 110         }
 111         return 0;
 112     } else {
 113         unsigned int i;
 114         int count = 0;
 115         for (i = 0; i <= tm->bucket_mask; i++) {
 116             struct list *bucket = &tm->buckets[i];
 117             struct sw_flow *flow;
 118             LIST_FOR_EACH (flow, struct sw_flow, node, bucket) {
 119                 if (flow_del_matches(&flow->key, key, strict)) {
 120                     do_delete(flow);
 121                     count++;
 122                 }
 123             }
 124         }
 125         tm->n_flows -= count;
 126         return count;
 127     }
 128 }
 129
 130 static int table_mac_timeout(struct datapath *dp, struct sw_table *swt)
 131 {
 132     struct sw_table_mac *tm = (struct sw_table_mac *) swt;
 133     unsigned int i;
 134     int count = 0;
 135
 136     for (i = 0; i <= tm->bucket_mask; i++) {
 137         struct list *bucket = &tm->buckets[i];
 138         struct sw_flow *flow;
 139         LIST_FOR_EACH (flow, struct sw_flow, node, bucket) {
 140             if (flow_timeout(flow)) {
 141                 dp_send_flow_expired(dp, flow);
 142                 do_delete(flow);
 143                 count++;
 144             }
 145         }
 146     }
 147     tm->n_flows -= count;
 148     return count;
 149 }
 150
 151 static void table_mac_destroy(struct sw_table *swt)
 152 {
 153     struct sw_table_mac *tm = (struct sw_table_mac *) swt;
 154     unsigned int i;
 155     for (i = 0; i <= tm->bucket_mask; i++) {
 156         struct list *list = &tm->buckets[i];
 157         while (!list_is_empty(list)) {
 158             struct sw_flow *flow = CONTAINER_OF(list_front(list),
 159                                                 struct sw_flow, node);
 160             list_remove(&flow->node);
 161             flow_free(flow);
 162         }
 163     }
 164     free(tm->buckets);
 165     free(tm);
 166 }
 167
 168 struct swt_iterator_mac {
 169     struct sw_table_mac *tm;
 170     unsigned int bucket_i;
 171 };
 172
 173 static struct sw_flow *next_head_flow(struct swt_iterator_mac *im)
 174 {
 175     for (; im->bucket_i <= im->tm->bucket_mask; im->bucket_i++) {
 176         struct list *bucket = &im->tm->buckets[im->bucket_i];
 177         if (!list_is_empty(bucket)) {
 178             return CONTAINER_OF(bucket, struct sw_flow, node);
 179         }
 180     }
 181     return NULL;
 182 }
 183
 184 static int table_mac_iterator(struct sw_table *swt,
 185                               struct swt_iterator *swt_iter)
 186 {
 187     struct swt_iterator_mac *im;
 188
 189     swt_iter->private = im = malloc(sizeof *im);
 190     if (im == NULL)
 191         return 0;
 192
 193     im->tm = (struct sw_table_mac *) swt;
 194
 195     if (!im->tm->n_flows)
 196         swt_iter->flow = NULL;
 197     else {
 198         im->bucket_i = 0;
 199         swt_iter->flow = next_head_flow(im);
 200     }
 201
 202     return 1;
 203 }
 204
 205 static void table_mac_next(struct swt_iterator *swt_iter)
 206 {
 207     struct swt_iterator_mac *im;
 208     struct list *next;
 209
 210     if (swt_iter->flow == NULL)
 211         return;
 212
 213     im = (struct swt_iterator_mac *) swt_iter->private;
 214
 215     next = swt_iter->flow->node.next;
 216     if (next != NULL) {
 217         swt_iter->flow = CONTAINER_OF(next, struct sw_flow, node);
 218     } else {
 219         im->bucket_i++;
 220         swt_iter->flow = next_head_flow(im);
 221     }
 222 }
 223
 224 static void table_mac_iterator_destroy(struct swt_iterator *swt_iter)
 225 {
 226     free(swt_iter->private);
 227 }
 228
 229 static void table_mac_stats(struct sw_table *swt, struct sw_table_stats *stats)
 230 {
 231     struct sw_table_mac *tm = (struct sw_table_mac *) swt;
 232     stats->name = "mac";
 233     stats->n_flows = tm->n_flows;
 234     stats->max_flows = tm->max_flows;
 235 }
 236
 237 struct sw_table *table_mac_create(unsigned int n_buckets,
 238                                   unsigned int max_flows)
 239 {
 240     struct sw_table_mac *tm;
 241     struct sw_table *swt;
 242     unsigned int i;
 243
 244     tm = calloc(1, sizeof *tm);
 245     if (tm == NULL)
 246         return NULL;
 247
 248     assert(!(n_buckets & (n_buckets - 1)));
 249
 250     tm->buckets = malloc(n_buckets * sizeof *tm->buckets);
 251     if (tm->buckets == NULL) {
 252         printf("failed to allocate %u buckets\n", n_buckets);
 253         free(tm);
 254         return NULL;
 255     }
 256     for (i = 0; i < n_buckets; i++) {
 257         list_init(&tm->buckets[i]);
 258     }
 259     tm->bucket_mask = n_buckets - 1;
 260
 261     swt = &tm->swt;
 262     swt->lookup = table_mac_lookup;
 263     swt->insert = table_mac_insert;
 264     swt->delete = table_mac_delete;
 265     swt->timeout = table_mac_timeout;
 266     swt->destroy = table_mac_destroy;
 267     swt->stats = table_mac_stats;
 268
 269     swt->iterator = table_mac_iterator;
 270     swt->iterator_next = table_mac_next;
 271     swt->iterator_destroy = table_mac_iterator_destroy;
 272
 273     crc32_init(&tm->crc32, 0x04C11DB7); /* Ethernet CRC. */
 274     tm->n_flows = 0;
 275     tm->max_flows = max_flows;
 276
 277     return swt;
 278 }