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
27 #include "switch-flow.h"
35 unsigned int max_flows;
36 unsigned int bucket_mask; /* Number of buckets minus 1. */
40 static struct list *find_bucket(struct sw_table *swt,
41 const struct sw_flow_key *key)
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];
48 static struct sw_flow *table_mac_lookup(struct sw_table *swt,
49 const struct sw_flow_key *key)
51 struct list *bucket = find_bucket(swt, key);
53 LIST_FOR_EACH (flow, struct sw_flow, node, bucket) {
54 if (!memcmp(key->flow.dl_src, flow->key.flow.dl_src, 6)) {
61 static int table_mac_insert(struct sw_table *swt, struct sw_flow *flow)
63 struct sw_table_mac *tm = (struct sw_table_mac *) swt;
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))
71 bucket = find_bucket(swt, &flow->key);
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);
82 if (tm->n_flows >= tm->max_flows) {
87 list_push_front(bucket, &flow->node);
92 do_delete(struct sw_flow *flow)
94 list_remove(&flow->node);
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)
102 struct sw_table_mac *tm = (struct sw_table_mac *) swt;
104 if (key->wildcards == (OFPFW_ALL & ~OFPFW_DL_SRC)) {
105 struct sw_flow *flow = table_mac_lookup(swt, key);
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)) {
125 tm->n_flows -= count;
130 static int table_mac_timeout(struct datapath *dp, struct sw_table *swt)
132 struct sw_table_mac *tm = (struct sw_table_mac *) swt;
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);
147 tm->n_flows -= count;
151 static void table_mac_destroy(struct sw_table *swt)
153 struct sw_table_mac *tm = (struct sw_table_mac *) swt;
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);
168 struct swt_iterator_mac {
169 struct sw_table_mac *tm;
170 unsigned int bucket_i;
173 static struct sw_flow *next_head_flow(struct swt_iterator_mac *im)
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);
184 static int table_mac_iterator(struct sw_table *swt,
185 struct swt_iterator *swt_iter)
187 struct swt_iterator_mac *im;
189 swt_iter->private = im = malloc(sizeof *im);
193 im->tm = (struct sw_table_mac *) swt;
195 if (!im->tm->n_flows)
196 swt_iter->flow = NULL;
199 swt_iter->flow = next_head_flow(im);
205 static void table_mac_next(struct swt_iterator *swt_iter)
207 struct swt_iterator_mac *im;
210 if (swt_iter->flow == NULL)
213 im = (struct swt_iterator_mac *) swt_iter->private;
215 next = swt_iter->flow->node.next;
217 swt_iter->flow = CONTAINER_OF(next, struct sw_flow, node);
220 swt_iter->flow = next_head_flow(im);
224 static void table_mac_iterator_destroy(struct swt_iterator *swt_iter)
226 free(swt_iter->private);
229 static void table_mac_stats(struct sw_table *swt, struct sw_table_stats *stats)
231 struct sw_table_mac *tm = (struct sw_table_mac *) swt;
233 stats->n_flows = tm->n_flows;
234 stats->max_flows = tm->max_flows;
237 struct sw_table *table_mac_create(unsigned int n_buckets,
238 unsigned int max_flows)
240 struct sw_table_mac *tm;
241 struct sw_table *swt;
244 tm = calloc(1, sizeof *tm);
248 assert(!(n_buckets & (n_buckets - 1)));
250 tm->buckets = malloc(n_buckets * sizeof *tm->buckets);
251 if (tm->buckets == NULL) {
252 printf("failed to allocate %u buckets\n", n_buckets);
256 for (i = 0; i < n_buckets; i++) {
257 list_init(&tm->buckets[i]);
259 tm->bucket_mask = n_buckets - 1;
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;
269 swt->iterator = table_mac_iterator;
270 swt->iterator_next = table_mac_next;
271 swt->iterator_destroy = table_mac_iterator_destroy;
273 crc32_init(&tm->crc32, 0x04C11DB7); /* Ethernet CRC. */
275 tm->max_flows = max_flows;