X-Git-Url: http://git.onelab.eu/?a=blobdiff_plain;f=datapath%2Ftable.c;h=47fa01690dbc574581f844e494a4976eae1ba228;hb=280c6e99fd5fcdaff5af6990f0c346d113d90cde;hp=d2432e89da2ceacf34eaf7dd390196ab8f40d8c7;hpb=406e37ecf554529e9380ef06863d85ccc94009d1;p=sliver-openvswitch.git

diff --git a/datapath/table.c b/datapath/table.c
index d2432e89d..47fa01690 100644
--- a/datapath/table.c
+++ b/datapath/table.c
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 2009, 2010 Nicira Networks.
+ * Copyright (c) 2009, 2010, 2011 Nicira Networks.
  * Distributed under the terms of the GNU GPL version 2.
  *
  * Significant portions of this file may be copied from parts of the Linux
@@ -10,6 +10,7 @@
 #include "datapath.h"
 #include "table.h"
 
+#include <linux/genetlink.h>
 #include <linux/gfp.h>
 #include <linux/slab.h>
 #include <linux/mm.h>
@@ -30,6 +31,17 @@ struct tbl_bucket {
 	struct tbl_node *objs[];
 };
 
+static struct tbl_bucket *get_bucket(struct tbl_bucket __rcu *bucket)
+{
+	return rcu_dereference_check(bucket, rcu_read_lock_held() ||
+				     lockdep_genl_is_held());
+}
+
+static struct tbl_bucket *get_bucket_protected(struct tbl_bucket __rcu *bucket)
+{
+	return rcu_dereference_protected(bucket, lockdep_genl_is_held());
+}
+
 static inline int bucket_size(int n_objs)
 {
 	return sizeof(struct tbl_bucket) + sizeof(struct tbl_node *) * n_objs;
@@ -40,17 +52,18 @@ static struct tbl_bucket *bucket_alloc(int n_objs)
 	return kmalloc(bucket_size(n_objs), GFP_KERNEL);
 }
 
-static void free_buckets(struct tbl_bucket ***l1, unsigned int n_buckets,
+static void free_buckets(struct tbl_bucket __rcu ***l1,
+			 unsigned int n_buckets,
 			 void (*free_obj)(struct tbl_node *))
 {
 	unsigned int i;
 
 	for (i = 0; i < n_buckets >> TBL_L1_SHIFT; i++) {
-		struct tbl_bucket **l2 = l1[i];
+		struct tbl_bucket __rcu **l2 = l1[i];
 		unsigned int j;
 
 		for (j = 0; j < TBL_L2_SIZE; j++) {
-			struct tbl_bucket *bucket = l2[j];
+			struct tbl_bucket *bucket = (struct tbl_bucket __force *)l2[j];
 			if (!bucket)
 				continue;
 
@@ -66,9 +79,9 @@ static void free_buckets(struct tbl_bucket ***l1, unsigned int n_buckets,
 	kfree(l1);
 }
 
-static struct tbl_bucket ***alloc_buckets(unsigned int n_buckets)
+static struct tbl_bucket __rcu ***alloc_buckets(unsigned int n_buckets)
 {
-	struct tbl_bucket ***l1;
+	struct tbl_bucket __rcu ***l1;
 	unsigned int i;
 
 	l1 = kmalloc((n_buckets >> TBL_L1_SHIFT) * sizeof(struct tbl_bucket **),
@@ -76,7 +89,7 @@ static struct tbl_bucket ***alloc_buckets(unsigned int n_buckets)
 	if (!l1)
 		return NULL;
 	for (i = 0; i < n_buckets >> TBL_L1_SHIFT; i++) {
-		l1[i] = (struct tbl_bucket **)get_zeroed_page(GFP_KERNEL);
+		l1[i] = (struct tbl_bucket __rcu **)get_zeroed_page(GFP_KERNEL);
 		if (!l1[i]) {
 			free_buckets(l1, i << TBL_L1_SHIFT, NULL);
 			return NULL;
@@ -97,7 +110,7 @@ struct tbl *tbl_create(unsigned int n_buckets)
 {
 	struct tbl *table;
 
-	table = kzalloc(sizeof *table, GFP_KERNEL);
+	table = kzalloc(sizeof(*table), GFP_KERNEL);
 	if (!table)
 		goto err;
 
@@ -195,7 +208,7 @@ struct tbl_node *tbl_lookup(struct tbl *table, void *target, u32 hash,
 			    int (*cmp)(const struct tbl_node *, void *))
 {
 	struct tbl_bucket __rcu **bucketp = find_bucket(table, hash);
-	struct tbl_bucket *bucket = rcu_dereference(*bucketp);
+	struct tbl_bucket *bucket = get_bucket(*bucketp);
 	int index;
 
 	if (!bucket)
@@ -236,7 +249,7 @@ int tbl_foreach(struct tbl *table,
 			struct tbl_bucket *bucket;
 			unsigned int i;
 
-			bucket = rcu_dereference(l2[l2_idx]);
+			bucket = get_bucket(l2[l2_idx]);
 			if (!bucket)
 				continue;
 
@@ -250,6 +263,53 @@ int tbl_foreach(struct tbl *table,
 	return 0;
 }
 
+/**
+ * tbl_next - find next node in hash table
+ * @table: table to iterate
+ * @bucketp: On entry, hash value of bucket to start from.  On exit, updated
+ * to bucket to start from on next call.
+ * @objp: On entry, index to start from within first bucket.  On exit, updated
+ * to index to start from on next call.
+ *
+ * Returns the next node in @table in hash order, or %NULL when no nodes remain
+ * in the hash table.
+ *
+ * On entry, uses the values that @bucketp and @objp reference to determine
+ * where to begin iteration.  Use 0 for both values to begin a new iteration.
+ * On exit, stores the values to pass on the next iteration into @bucketp and
+ * @objp's referents.
+ */
+struct tbl_node *tbl_next(struct tbl *table, u32 *bucketp, u32 *objp)
+{
+	unsigned int n_l1 = table->n_buckets >> TBL_L1_SHIFT;
+	u32 s_l1_idx = *bucketp >> TBL_L1_SHIFT;
+	u32 s_l2_idx = *bucketp & (TBL_L2_SIZE - 1);
+	u32 s_obj = *objp;
+	unsigned int l1_idx;
+
+	for (l1_idx = s_l1_idx; l1_idx < n_l1; l1_idx++) {
+		struct tbl_bucket __rcu **l2 = table->buckets[l1_idx];
+		unsigned int l2_idx;
+
+		for (l2_idx = s_l2_idx; l2_idx < TBL_L2_SIZE; l2_idx++) {
+			struct tbl_bucket *bucket;
+
+			bucket = get_bucket_protected(l2[l2_idx]);
+			if (bucket && s_obj < bucket->n_objs) {
+				*bucketp = (l1_idx << TBL_L1_SHIFT) + l2_idx;
+				*objp = s_obj + 1;
+				return bucket->objs[s_obj];
+			}
+
+			s_obj = 0;
+		}
+		s_l2_idx = 0;
+	}
+	*bucketp = 0;
+	*objp = 0;
+	return NULL;
+}
+
 static int insert_table_flow(struct tbl_node *node, void *new_table_)
 {
 	struct tbl *new_table = new_table_;
@@ -323,7 +383,7 @@ static void free_bucket_rcu(struct rcu_head *rcu)
 int tbl_insert(struct tbl *table, struct tbl_node *target, u32 hash)
 {
 	struct tbl_bucket __rcu **oldp = find_bucket(table, hash);
-	struct tbl_bucket *old = rcu_dereference(*oldp);
+	struct tbl_bucket *old = get_bucket_protected(*oldp);
 	unsigned int n = old ? old->n_objs : 0;
 	struct tbl_bucket *new = bucket_alloc(n + 1);
 
@@ -361,7 +421,7 @@ int tbl_insert(struct tbl *table, struct tbl_node *target, u32 hash)
 int tbl_remove(struct tbl *table, struct tbl_node *target)
 {
 	struct tbl_bucket __rcu **oldp = find_bucket(table, target->hash);
-	struct tbl_bucket *old = rcu_dereference(*oldp);
+	struct tbl_bucket *old = get_bucket_protected(*oldp);
 	unsigned int n = old->n_objs;
 	struct tbl_bucket *new;