/*
* Distributed under the terms of the GNU GPL version 2.
- * Copyright (c) 2007 The Board of Trustees of The Leland Stanford Junior Univer
-sity
+ * Copyright (c) 2007, 2008 The Board of Trustees of The Leland
+ * Stanford Junior University
*/
#include "table.h"
struct sw_table_hash {
struct sw_table swt;
- spinlock_t lock;
struct crc32 crc32;
- atomic_t n_flows;
+ unsigned int n_flows;
unsigned int bucket_mask; /* Number of buckets minus 1. */
struct sw_flow **buckets;
};
const struct sw_flow_key *key)
{
struct sw_table_hash *th = (struct sw_table_hash *) swt;
- unsigned int crc = crc32_calculate(&th->crc32, key, sizeof *key);
+ unsigned int crc = crc32_calculate(&th->crc32, key,
+ offsetof(struct sw_flow_key, wildcards));
return &th->buckets[crc & th->bucket_mask];
}
const struct sw_flow_key *key)
{
struct sw_flow *flow = *find_bucket(swt, key);
- return flow && !memcmp(&flow->key, key, sizeof *key) ? flow : NULL;
+ return flow && flow_keys_equal(&flow->key, key) ? flow : NULL;
}
static int table_hash_insert(struct sw_table *swt, struct sw_flow *flow)
{
struct sw_table_hash *th = (struct sw_table_hash *) swt;
struct sw_flow **bucket;
- unsigned long int flags;
int retval;
if (flow->key.wildcards != 0)
return 0;
- spin_lock_irqsave(&th->lock, flags);
bucket = find_bucket(swt, &flow->key);
if (*bucket == NULL) {
- atomic_inc(&th->n_flows);
+ th->n_flows++;
rcu_assign_pointer(*bucket, flow);
retval = 1;
} else {
struct sw_flow *old_flow = *bucket;
- if (!memcmp(&old_flow->key, &flow->key, sizeof flow->key)
- && flow_del(old_flow)) {
+ if (flow_keys_equal(&old_flow->key, &flow->key)) {
rcu_assign_pointer(*bucket, flow);
flow_deferred_free(old_flow);
retval = 1;
retval = 0;
}
}
- spin_unlock_irqrestore(&th->lock, flags);
return retval;
}
-/* Caller must update n_flows. */
-static int do_delete(struct sw_flow **bucket, struct sw_flow *flow)
+static int table_hash_modify(struct sw_table *swt,
+ const struct sw_flow_key *key, uint16_t priority, int strict,
+ const struct ofp_action_header *actions, size_t actions_len)
{
- if (flow_del(flow)) {
- rcu_assign_pointer(*bucket, NULL);
- flow_deferred_free(flow);
- return 1;
+ struct sw_table_hash *th = (struct sw_table_hash *) swt;
+ unsigned int count = 0;
+
+ if (key->wildcards == 0) {
+ struct sw_flow **bucket = find_bucket(swt, key);
+ struct sw_flow *flow = *bucket;
+ if (flow && flow_matches_desc(&flow->key, key, strict)
+ && (!strict || (flow->priority == priority))) {
+ flow_replace_acts(flow, actions, actions_len);
+ count = 1;
+ }
+ } else {
+ unsigned int i;
+
+ for (i = 0; i <= th->bucket_mask; i++) {
+ struct sw_flow **bucket = &th->buckets[i];
+ struct sw_flow *flow = *bucket;
+ if (flow && flow_matches_desc(&flow->key, key, strict)
+ && (!strict || (flow->priority == priority))) {
+ flow_replace_acts(flow, actions, actions_len);
+ count++;
+ }
+ }
}
- return 0;
+ return count;
+}
+
+/* Caller must update n_flows. */
+static int do_delete(struct datapath *dp, struct sw_flow **bucket,
+ struct sw_flow *flow, enum nx_flow_end_reason reason)
+{
+ dp_send_flow_end(dp, flow, reason);
+ rcu_assign_pointer(*bucket, NULL);
+ flow_deferred_free(flow);
+ return 1;
}
-/* Returns number of deleted flows. */
-static int table_hash_delete(struct sw_table *swt,
- const struct sw_flow_key *key, int strict)
+/* Returns number of deleted flows. We can ignore the priority
+ * argument, since all exact-match entries are the same (highest)
+ * priority. */
+static int table_hash_delete(struct datapath *dp, struct sw_table *swt,
+ const struct sw_flow_key *key, uint16_t out_port,
+ uint16_t priority, int strict)
{
struct sw_table_hash *th = (struct sw_table_hash *) swt;
unsigned int count = 0;
if (key->wildcards == 0) {
struct sw_flow **bucket = find_bucket(swt, key);
struct sw_flow *flow = *bucket;
- if (flow && !memcmp(&flow->key, key, sizeof *key))
- count = do_delete(bucket, flow);
+ if (flow && flow_keys_equal(&flow->key, key)
+ && flow_has_out_port(flow, out_port))
+ count = do_delete(dp, bucket, flow, NXFER_DELETE);
} else {
unsigned int i;
for (i = 0; i <= th->bucket_mask; i++) {
struct sw_flow **bucket = &th->buckets[i];
struct sw_flow *flow = *bucket;
- if (flow && flow_del_matches(&flow->key, key, strict))
- count += do_delete(bucket, flow);
+ if (flow && flow_matches_desc(&flow->key, key, strict)
+ && flow_has_out_port(flow, out_port))
+ count += do_delete(dp, bucket, flow, NXFER_DELETE);
}
}
- if (count)
- atomic_sub(count, &th->n_flows);
+ th->n_flows -= count;
return count;
}
unsigned int i;
int count = 0;
+ mutex_lock(&dp_mutex);
for (i = 0; i <= th->bucket_mask; i++) {
struct sw_flow **bucket = &th->buckets[i];
struct sw_flow *flow = *bucket;
- if (flow && flow_timeout(flow)) {
- count += do_delete(bucket, flow);
- if (dp->hello_flags & OFP_CHELLO_SEND_FLOW_EXP)
- dp_send_flow_expired(dp, flow);
+ if (flow) {
+ int reason = flow_timeout(flow);
+ if (reason >= 0) {
+ count += do_delete(dp, bucket, flow, reason);
+ }
}
}
+ th->n_flows -= count;
+ mutex_unlock(&dp_mutex);
- if (count)
- atomic_sub(count, &th->n_flows);
return count;
}
kfree(th);
}
-struct swt_iterator_hash {
- struct sw_table_hash *th;
- unsigned int bucket_i;
-};
-
-static struct sw_flow *next_flow(struct swt_iterator_hash *ih)
-{
- for (;ih->bucket_i <= ih->th->bucket_mask; ih->bucket_i++) {
- struct sw_flow *f = ih->th->buckets[ih->bucket_i];
- if (f != NULL)
- return f;
- }
-
- return NULL;
-}
-
-static int table_hash_iterator(struct sw_table *swt,
- struct swt_iterator *swt_iter)
+static int table_hash_iterate(struct sw_table *swt,
+ const struct sw_flow_key *key, uint16_t out_port,
+ struct sw_table_position *position,
+ int (*callback)(struct sw_flow *, void *private),
+ void *private)
{
- struct swt_iterator_hash *ih;
-
- swt_iter->private = ih = kmalloc(sizeof *ih, GFP_KERNEL);
+ struct sw_table_hash *th = (struct sw_table_hash *) swt;
- if (ih == NULL)
+ if (position->private[0] > th->bucket_mask)
return 0;
- ih->th = (struct sw_table_hash *) swt;
-
- ih->bucket_i = 0;
- swt_iter->flow = next_flow(ih);
-
- return 1;
-}
-
-static void table_hash_next(struct swt_iterator *swt_iter)
-{
- struct swt_iterator_hash *ih;
-
- if (swt_iter->flow == NULL)
- return;
-
- ih = (struct swt_iterator_hash *) swt_iter->private;
+ if (key->wildcards == 0) {
+ struct sw_flow *flow;
+ int error;
- ih->bucket_i++;
- swt_iter->flow = next_flow(ih);
-}
+ flow = table_hash_lookup(swt, key);
+ if (!flow || !flow_has_out_port(flow, out_port))
+ return 0;
-static void table_hash_iterator_destroy(struct swt_iterator *swt_iter)
-{
- kfree(swt_iter->private);
+ error = callback(flow, private);
+ if (!error)
+ position->private[0] = -1;
+ return error;
+ } else {
+ int i;
+
+ for (i = position->private[0]; i <= th->bucket_mask; i++) {
+ struct sw_flow *flow = th->buckets[i];
+ if (flow && flow_matches_1wild(&flow->key, key)
+ && flow_has_out_port(flow, out_port)) {
+ int error = callback(flow, private);
+ if (error) {
+ position->private[0] = i;
+ return error;
+ }
+ }
+ }
+ return 0;
+ }
}
-
static void table_hash_stats(struct sw_table *swt,
struct sw_table_stats *stats)
{
struct sw_table_hash *th = (struct sw_table_hash *) swt;
stats->name = "hash";
- stats->n_flows = atomic_read(&th->n_flows);
+ stats->wildcards = 0; /* No wildcards are supported. */
+ stats->n_flows = th->n_flows;
stats->max_flows = th->bucket_mask + 1;
+ stats->n_lookup = swt->n_lookup;
+ stats->n_matched = swt->n_matched;
}
struct sw_table *table_hash_create(unsigned int polynomial,
struct sw_table_hash *th;
struct sw_table *swt;
- th = kmalloc(sizeof *th, GFP_KERNEL);
+ th = kzalloc(sizeof *th, GFP_KERNEL);
if (th == NULL)
return NULL;
swt->delete = table_hash_delete;
swt->timeout = table_hash_timeout;
swt->destroy = table_hash_destroy;
- swt->iterator = table_hash_iterator;
- swt->iterator_next = table_hash_next;
- swt->iterator_destroy = table_hash_iterator_destroy;
+ swt->iterate = table_hash_iterate;
swt->stats = table_hash_stats;
- spin_lock_init(&th->lock);
crc32_init(&th->crc32, polynomial);
- atomic_set(&th->n_flows, 0);
+ th->n_flows = 0;
return swt;
}
for (i = 0; i < 2; i++) {
struct sw_flow *flow = *find_bucket(t2->subtable[i], key);
- if (flow && !memcmp(&flow->key, key, sizeof *key))
+ if (flow && flow_keys_equal(&flow->key, key))
return flow;
}
return NULL;
return table_hash_insert(t2->subtable[1], flow);
}
-static int table_hash2_delete(struct sw_table *swt,
- const struct sw_flow_key *key, int strict)
+static int table_hash2_modify(struct sw_table *swt,
+ const struct sw_flow_key *key, uint16_t priority, int strict,
+ const struct ofp_action_header *actions, size_t actions_len)
+{
+ struct sw_table_hash2 *t2 = (struct sw_table_hash2 *) swt;
+ return (table_hash_modify(t2->subtable[0], key, priority, strict,
+ actions, actions_len)
+ + table_hash_modify(t2->subtable[1], key, priority, strict,
+ actions, actions_len));
+}
+
+static int table_hash2_delete(struct datapath *dp, struct sw_table *swt,
+ const struct sw_flow_key *key,
+ uint16_t out_port,
+ uint16_t priority, int strict)
{
struct sw_table_hash2 *t2 = (struct sw_table_hash2 *) swt;
- return (table_hash_delete(t2->subtable[0], key, strict)
- + table_hash_delete(t2->subtable[1], key, strict));
+ return (table_hash_delete(dp, t2->subtable[0], key, out_port,
+ priority, strict)
+ + table_hash_delete(dp, t2->subtable[1], key, out_port,
+ priority, strict));
}
static int table_hash2_timeout(struct datapath *dp, struct sw_table *swt)
kfree(t2);
}
-struct swt_iterator_hash2 {
- struct sw_table_hash2 *th2;
- struct swt_iterator ih;
- uint8_t table_i;
-};
-
-static int table_hash2_iterator(struct sw_table *swt,
- struct swt_iterator *swt_iter)
-{
- struct swt_iterator_hash2 *ih2;
-
- swt_iter->private = ih2 = kmalloc(sizeof *ih2, GFP_KERNEL);
- if (ih2 == NULL)
- return 0;
-
- ih2->th2 = (struct sw_table_hash2 *) swt;
- if (!table_hash_iterator(ih2->th2->subtable[0], &ih2->ih)) {
- kfree(ih2);
- return 0;
- }
-
- if (ih2->ih.flow != NULL) {
- swt_iter->flow = ih2->ih.flow;
- ih2->table_i = 0;
- } else {
- table_hash_iterator_destroy(&ih2->ih);
- ih2->table_i = 1;
- if (!table_hash_iterator(ih2->th2->subtable[1], &ih2->ih)) {
- kfree(ih2);
- return 0;
- }
- swt_iter->flow = ih2->ih.flow;
- }
-
- return 1;
-}
-
-static void table_hash2_next(struct swt_iterator *swt_iter)
+static int table_hash2_iterate(struct sw_table *swt,
+ const struct sw_flow_key *key, uint16_t out_port,
+ struct sw_table_position *position,
+ int (*callback)(struct sw_flow *, void *),
+ void *private)
{
- struct swt_iterator_hash2 *ih2;
-
- if (swt_iter->flow == NULL)
- return;
-
- ih2 = (struct swt_iterator_hash2 *) swt_iter->private;
- table_hash_next(&ih2->ih);
+ struct sw_table_hash2 *t2 = (struct sw_table_hash2 *) swt;
+ int i;
- if (ih2->ih.flow != NULL) {
- swt_iter->flow = ih2->ih.flow;
- } else {
- if (ih2->table_i == 0) {
- table_hash_iterator_destroy(&ih2->ih);
- ih2->table_i = 1;
- if (!table_hash_iterator(ih2->th2->subtable[1], &ih2->ih)) {
- ih2->ih.private = NULL;
- swt_iter->flow = NULL;
- } else {
- swt_iter->flow = ih2->ih.flow;
- }
- } else {
- swt_iter->flow = NULL;
+ for (i = position->private[1]; i < 2; i++) {
+ int error = table_hash_iterate(t2->subtable[i], key, out_port,
+ position, callback, private);
+ if (error) {
+ return error;
}
+ position->private[0] = 0;
+ position->private[1]++;
}
-}
-
-static void table_hash2_iterator_destroy(struct swt_iterator *swt_iter)
-{
- struct swt_iterator_hash2 *ih2;
-
- ih2 = (struct swt_iterator_hash2 *) swt_iter->private;
- if (ih2->ih.private != NULL)
- table_hash_iterator_destroy(&ih2->ih);
- kfree(ih2);
+ return 0;
}
static void table_hash2_stats(struct sw_table *swt,
for (i = 0; i < 2; i++)
table_hash_stats(t2->subtable[i], &substats[i]);
stats->name = "hash2";
- stats->n_flows = substats[0].n_flows + substats[1].n_flows;
+ stats->wildcards = 0; /* No wildcards are supported. */
+ stats->n_flows = substats[0].n_flows + substats[1].n_flows;
stats->max_flows = substats[0].max_flows + substats[1].max_flows;
+ stats->n_lookup = swt->n_lookup;
+ stats->n_matched = swt->n_matched;
}
struct sw_table *table_hash2_create(unsigned int poly0, unsigned int buckets0,
struct sw_table_hash2 *t2;
struct sw_table *swt;
- t2 = kmalloc(sizeof *t2, GFP_KERNEL);
+ t2 = kzalloc(sizeof *t2, GFP_KERNEL);
if (t2 == NULL)
return NULL;
swt = &t2->swt;
swt->lookup = table_hash2_lookup;
swt->insert = table_hash2_insert;
+ swt->modify = table_hash2_modify;
swt->delete = table_hash2_delete;
swt->timeout = table_hash2_timeout;
swt->destroy = table_hash2_destroy;
+ swt->iterate = table_hash2_iterate;
swt->stats = table_hash2_stats;
- swt->iterator = table_hash2_iterator;
- swt->iterator_next = table_hash2_next;
- swt->iterator_destroy = table_hash2_iterator_destroy;
-
return swt;
out_free_subtable0:
ptr = vmalloc(size);
if (ptr)
printk("openflow: used vmalloc for %lu bytes\n",
- (unsigned long)size);
+ (unsigned long)size);
}
return ptr;
}