1 /* Copyright (c) 2008 The Board of Trustees of The Leland Stanford
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:
17 * The above copyright notice and this permission notice shall be
18 * included in all copies or substantial portions of the Software.
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
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.
39 #include "switch-flow.h"
47 unsigned int max_flows;
48 unsigned int bucket_mask; /* Number of buckets minus 1. */
52 static struct list *find_bucket(struct sw_table *swt,
53 const struct sw_flow_key *key)
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];
60 static struct sw_flow *table_mac_lookup(struct sw_table *swt,
61 const struct sw_flow_key *key)
63 struct list *bucket = find_bucket(swt, key);
65 LIST_FOR_EACH (flow, struct sw_flow, node, bucket) {
66 if (!memcmp(key->flow.dl_src, flow->key.flow.dl_src, 6)) {
73 static int table_mac_insert(struct sw_table *swt, struct sw_flow *flow)
75 struct sw_table_mac *tm = (struct sw_table_mac *) swt;
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))
83 bucket = find_bucket(swt, &flow->key);
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);
94 if (tm->n_flows >= tm->max_flows) {
99 list_push_front(bucket, &flow->node);
104 do_delete(struct sw_flow *flow)
106 list_remove(&flow->node);
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)
114 struct sw_table_mac *tm = (struct sw_table_mac *) swt;
116 if (key->wildcards == (OFPFW_ALL & ~OFPFW_DL_SRC)) {
117 struct sw_flow *flow = table_mac_lookup(swt, key);
127 for (i = 0; i <= tm->bucket_mask; i++) {
128 struct list *bucket = &tm->buckets[i];
129 struct sw_flow *flow;
130 LIST_FOR_EACH (flow, struct sw_flow, node, bucket) {
131 if (flow_del_matches(&flow->key, key, strict)) {
137 tm->n_flows -= count;
142 static int table_mac_timeout(struct datapath *dp, struct sw_table *swt)
144 struct sw_table_mac *tm = (struct sw_table_mac *) swt;
148 for (i = 0; i <= tm->bucket_mask; i++) {
149 struct list *bucket = &tm->buckets[i];
150 struct sw_flow *flow;
151 LIST_FOR_EACH (flow, struct sw_flow, node, bucket) {
152 if (flow_timeout(flow)) {
153 dp_send_flow_expired(dp, flow);
159 tm->n_flows -= count;
163 static void table_mac_destroy(struct sw_table *swt)
165 struct sw_table_mac *tm = (struct sw_table_mac *) swt;
167 for (i = 0; i <= tm->bucket_mask; i++) {
168 struct list *list = &tm->buckets[i];
169 while (!list_is_empty(list)) {
170 struct sw_flow *flow = CONTAINER_OF(list_front(list),
171 struct sw_flow, node);
172 list_remove(&flow->node);
180 struct swt_iterator_mac {
181 struct sw_table_mac *tm;
182 unsigned int bucket_i;
185 static struct sw_flow *next_head_flow(struct swt_iterator_mac *im)
187 for (; im->bucket_i <= im->tm->bucket_mask; im->bucket_i++) {
188 struct list *bucket = &im->tm->buckets[im->bucket_i];
189 if (!list_is_empty(bucket)) {
190 return CONTAINER_OF(bucket, struct sw_flow, node);
196 static int table_mac_iterator(struct sw_table *swt,
197 struct swt_iterator *swt_iter)
199 struct swt_iterator_mac *im;
201 swt_iter->private = im = malloc(sizeof *im);
205 im->tm = (struct sw_table_mac *) swt;
207 if (!im->tm->n_flows)
208 swt_iter->flow = NULL;
211 swt_iter->flow = next_head_flow(im);
217 static void table_mac_next(struct swt_iterator *swt_iter)
219 struct swt_iterator_mac *im;
222 if (swt_iter->flow == NULL)
225 im = (struct swt_iterator_mac *) swt_iter->private;
227 next = swt_iter->flow->node.next;
229 swt_iter->flow = CONTAINER_OF(next, struct sw_flow, node);
232 swt_iter->flow = next_head_flow(im);
236 static void table_mac_iterator_destroy(struct swt_iterator *swt_iter)
238 free(swt_iter->private);
241 static void table_mac_stats(struct sw_table *swt, struct sw_table_stats *stats)
243 struct sw_table_mac *tm = (struct sw_table_mac *) swt;
245 stats->n_flows = tm->n_flows;
246 stats->max_flows = tm->max_flows;
249 struct sw_table *table_mac_create(unsigned int n_buckets,
250 unsigned int max_flows)
252 struct sw_table_mac *tm;
253 struct sw_table *swt;
256 tm = calloc(1, sizeof *tm);
260 assert(!(n_buckets & (n_buckets - 1)));
262 tm->buckets = malloc(n_buckets * sizeof *tm->buckets);
263 if (tm->buckets == NULL) {
264 printf("failed to allocate %u buckets\n", n_buckets);
268 for (i = 0; i < n_buckets; i++) {
269 list_init(&tm->buckets[i]);
271 tm->bucket_mask = n_buckets - 1;
274 swt->lookup = table_mac_lookup;
275 swt->insert = table_mac_insert;
276 swt->delete = table_mac_delete;
277 swt->timeout = table_mac_timeout;
278 swt->destroy = table_mac_destroy;
279 swt->stats = table_mac_stats;
281 swt->iterator = table_mac_iterator;
282 swt->iterator_next = table_mac_next;
283 swt->iterator_destroy = table_mac_iterator_destroy;
285 crc32_init(&tm->crc32, 0x04C11DB7); /* Ethernet CRC. */
287 tm->max_flows = max_flows;