X-Git-Url: http://git.onelab.eu/?a=blobdiff_plain;f=datapath%2Ftable-hash.c;h=86e19201e555c2d808c876df6a43b180580a0c3b;hb=686cd5c3d8dd7f23c320b4e3a3c25c59c355f78c;hp=57a9f1c008b39a3f6b280966cef78d3eb4e57216;hpb=468e00132f76a6d057da1520873e7a468ccae422;p=sliver-openvswitch.git

diff --git a/datapath/table-hash.c b/datapath/table-hash.c
index 57a9f1c00..86e19201e 100644
--- a/datapath/table-hash.c
+++ b/datapath/table-hash.c
@@ -1,7 +1,7 @@
 /*
  * 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"
@@ -21,9 +21,8 @@ static void kmem_free(void *, size_t);
 
 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;
 };
@@ -32,7 +31,8 @@ static struct sw_flow **find_bucket(struct sw_table *swt,
 									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];
 }
 
@@ -40,29 +40,26 @@ static struct sw_flow *table_hash_lookup(struct sw_table *swt,
 										 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;
@@ -70,24 +67,54 @@ static int table_hash_insert(struct sw_table *swt, struct sw_flow *flow)
 			retval = 0;
 		}
 	}
-	spin_unlock_irqrestore(&th->lock, flags);
 	return retval;
 }
 
+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) 
+{
+	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 count;
+}
+
 /* Caller must update n_flows. */
 static int do_delete(struct sw_flow **bucket, struct sw_flow *flow)
 {
-	if (flow_del(flow)) {
-		rcu_assign_pointer(*bucket, NULL);
-		flow_deferred_free(flow);
-		return 1;
-	}
-	return 0;
+	rcu_assign_pointer(*bucket, NULL);
+	flow_deferred_free(flow);
+	return 1;
 }
 
-/* Returns number of deleted flows. */
+/* 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 sw_table *swt,
-							 const struct sw_flow_key *key, int strict)
+							 const struct sw_flow_key *key, 
+							 uint16_t priority, int strict)
 {
 	struct sw_table_hash *th = (struct sw_table_hash *) swt;
 	unsigned int count = 0;
@@ -95,7 +122,7 @@ static int table_hash_delete(struct sw_table *swt,
 	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))
+		if (flow && flow_keys_equal(&flow->key, key))
 			count = do_delete(bucket, flow);
 	} else {
 		unsigned int i;
@@ -103,12 +130,11 @@ static int table_hash_delete(struct sw_table *swt,
 		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))
+			if (flow && flow_matches_desc(&flow->key, key, strict))
 				count += do_delete(bucket, flow);
 		}
 	}
-	if (count)
-		atomic_sub(count, &th->n_flows);
+	th->n_flows -= count;
 	return count;
 }
 
@@ -118,18 +144,21 @@ static int table_hash_timeout(struct datapath *dp, struct sw_table *swt)
 	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(bucket, flow); 
+				dp_send_flow_expired(dp, flow, reason);
+			}
 		}
 	}
+	th->n_flows -= count;
+	mutex_unlock(&dp_mutex);
 
-	if (count)
-		atomic_sub(count, &th->n_flows);
 	return count;
 }
 
@@ -144,65 +173,55 @@ static void table_hash_destroy(struct sw_table *swt)
 	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,
+			      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)
+			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)) {
+				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,
@@ -211,7 +230,7 @@ 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;
 
@@ -230,14 +249,11 @@ struct sw_table *table_hash_create(unsigned int polynomial,
 	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;
 }
@@ -257,7 +273,7 @@ static struct sw_flow *table_hash2_lookup(struct sw_table *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;
@@ -272,12 +288,24 @@ static int table_hash2_insert(struct sw_table *swt, struct sw_flow *flow)
 	return table_hash_insert(t2->subtable[1], flow);
 }
 
+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 sw_table *swt,
-							  const struct sw_flow_key *key, int strict)
+							  const struct sw_flow_key *key, 
+							  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(t2->subtable[0], key, priority, strict)
+			+ table_hash_delete(t2->subtable[1], key, priority, strict));
 }
 
 static int table_hash2_timeout(struct datapath *dp, struct sw_table *swt)
@@ -295,79 +323,25 @@ static void table_hash2_destroy(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,
+			       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, 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,
@@ -380,8 +354,11 @@ 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,
@@ -391,7 +368,7 @@ 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;
 
@@ -406,15 +383,13 @@ struct sw_table *table_hash2_create(unsigned int poly0, unsigned int buckets0,
 	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:
@@ -440,7 +415,7 @@ kmem_alloc(size_t size)
 		ptr = vmalloc(size);
 		if (ptr)
 			printk("openflow: used vmalloc for %lu bytes\n", 
-                    (unsigned long)size);
+					(unsigned long)size);
 	}
 	return ptr;
 }