When deleting a mask from the mask array, we always move the last entry
into its current location. Another approach can be NULL in its current
place, and periodically compact it.
The approach taken by this patch is more efficient during run time.
During look up, fast path packet don't have to skip over NULL pointers.
A more important advantage of this approach is that it tries to
keep the mask array index stable by avoiding periodic index reshuffle.
This patch implements an optimization to further promote index
stability. By leaving the last entry value intact when moving it to
a new location, the old cache index can 'fix' themselves, by noticing
the index in the cache is outside the valid mask array region. The new
index can be found by scanning the mask pointer within the valid region.
Signed-off-by: Andy Zhou <az...@nicira.com>
---
datapath/flow_table.c | 114 ++++++++++++++++++++++++++++++++++++--------------
1 file changed, 82 insertions(+), 32 deletions(-)
diff --git a/datapath/flow_table.c b/datapath/flow_table.c
index 58a25c7..0bc114c 100644
--- a/datapath/flow_table.c
+++ b/datapath/flow_table.c
@@ -247,10 +247,10 @@ static int tbl_mask_array_realloc(struct flow_table *tbl,
int size)
if (old) {
int i;
- for (i = 0; i < old->max; i++) {
- if (old->masks[i])
- new->masks[new->count++] = old->masks[i];
- }
+ for (i = 0; i < old->max; i++)
+ new->masks[i] = old->masks[i];
+
+ new->count = old->count;
}
rcu_assign_pointer(tbl->mask_array, new);
@@ -260,6 +260,54 @@ static int tbl_mask_array_realloc(struct flow_table *tbl,
int size)
return 0;
}
+static void tbl_mask_array_delete_mask(struct mask_array *ma,
+ const struct sw_flow_mask *mask)
+{
+ int i = 0;
+
+ /* Delete a mask pointer from the valid section.
+ *
+ * Also move the last entry in its place, so there is no
+ * whole in the valid section.
+ *
+ * Notice the last entry still pints the original mask.
+ */
+ while (i < ma->count - 1) {
+ if (!mask || mask == ma->masks[i]) {
+ struct sw_flow_mask *last;
+
+ last = ma->masks[ma->count-1];
+ rcu_assign_pointer(ma->masks[i], last);
+ ma->count--;
+ } else
+ i++;
+ }
+
+ /* Delete mask pointers from the invalid section.
+ *
+ * Set them NULL to prevent future references.
+ */
+ for (; i < ma->max; i++) {
+ if (mask == ma->masks[i])
+ RCU_INIT_POINTER(ma->masks[i], NULL);
+
+ if (i == ma->count)
+ ma->count--;
+ }
+}
+
+static int tbl_mask_array_find_idx(struct mask_array *ma,
+ const struct sw_flow_mask *mask)
+{
+ int i;
+
+ for (i = 0; i < ma->count; i++)
+ if (mask == ovsl_dereference(ma->masks[i]))
+ return i;
+
+ return -1;
+}
+
int ovs_flow_tbl_init(struct flow_table *table)
{
struct table_instance *ti;
@@ -524,7 +572,7 @@ static struct sw_flow *flow_lookup(struct flow_table *tbl,
struct sw_flow *flow;
int i;
- for (i = 0; i < ma->max; i++) {
+ for (i = 0; i < ma->count; i++) {
struct sw_flow_mask *mask;
mask = rcu_dereference_ovsl(ma->masks[i]);
@@ -578,15 +626,34 @@ struct sw_flow *ovs_flow_tbl_lookup_stats(struct
flow_table *tbl,
if (ce->skb_hash == skb_hash) {
struct sw_flow_mask *mask;
+ del = ce;
mask = rcu_dereference_ovsl(ma->masks[ce->mask_index]);
- if (mask) {
- flow = masked_flow_lookup(ti, key, mask,
- n_mask_hit);
- if (flow) /* Found */
- return flow;
+ if (!mask) {
+ /* Cache invalid */
+ ce->skb_hash = 0;
+ break;
}
- del = ce;
+
+ if (ce->mask_index >= ma->count) {
+ int new_idx;
+
+ new_idx = tbl_mask_array_find_idx(ma, mask);
+ if (new_idx >= 0)
+ ce->mask_index = new_idx;
+ else {
+ /* Cache invalid */
+ ce->skb_hash = 0;
+ break;
+ }
+ }
+
+ flow = masked_flow_lookup(ti, key, mask, n_mask_hit);
+ if (flow)
+ /* Cache hit */
+ return flow;
+
+ /* Cache miss, do full look up */
break;
}
@@ -644,18 +711,9 @@ static void flow_mask_remove(struct flow_table *tbl,
struct sw_flow_mask *mask)
if (!mask->ref_count) {
struct mask_array *ma;
- int i;
ma = ovsl_dereference(tbl->mask_array);
- for (i = 0; i < ma->max; i++) {
- if (mask == ovsl_dereference(ma->masks[i])) {
- RCU_INIT_POINTER(ma->masks[i], NULL);
- ma->count--;
- goto free;
- }
- }
- BUG();
-free:
+ tbl_mask_array_delete_mask(ma, mask);
call_rcu(&mask->rcu, rcu_free_sw_flow_mask_cb);
}
}
@@ -704,7 +762,7 @@ static struct sw_flow_mask *flow_mask_find(const struct
flow_table *tbl,
int i;
ma = ovsl_dereference(tbl->mask_array);
- for (i = 0; i < ma->max; i++) {
+ for (i = 0; i < ma->count; i++) {
struct sw_flow_mask *t;
t = ovsl_dereference(ma->masks[i]);
@@ -724,7 +782,6 @@ static int flow_mask_insert(struct flow_table *tbl, struct
sw_flow *flow,
mask = flow_mask_find(tbl, new);
if (!mask) {
struct mask_array *ma;
- int i;
/* Allocate a new mask if none exsits. */
mask = mask_alloc();
@@ -747,16 +804,9 @@ static int flow_mask_insert(struct flow_table *tbl, struct
sw_flow *flow,
}
ma = ovsl_dereference(tbl->mask_array);
}
- for (i = 0; i < ma->max; i++) {
- const struct sw_flow_mask *t;
- t = ovsl_dereference(ma->masks[i]);
- if (!t) {
- rcu_assign_pointer(ma->masks[i], mask);
- ma->count++;
- break;
- }
- }
+ rcu_assign_pointer(ma->masks[ma->count], mask);
+ ma->count++;
} else {
BUG_ON(!mask->ref_count);
mask->ref_count++;
--
1.9.1
_______________________________________________
dev mailing list
dev@openvswitch.org
http://openvswitch.org/mailman/listinfo/dev
