| Message ID | 1572618234-6904-6-git-send-email-xiangxia.m.yue@gmail.com |
|---|---|
| State | Awaiting Upstream |
| Headers | show |
| Series | optimize openvswitch flow looking up | expand |
On Fri, Nov 1, 2019 at 7:24 AM <xiangxia.m.yue@gmail.com> wrote: > > From: Tonghao Zhang <xiangxia.m.yue@gmail.com> > > The full looking up on flow table traverses all mask array. > If mask-array is too large, the number of invalid flow-mask > increase, performance will be drop. > > One bad case, for example: M means flow-mask is valid and NULL > of flow-mask means deleted. > > +-------------------------------------------+ > | M | NULL | ... | NULL | M| > +-------------------------------------------+ > > In that case, without this patch, openvswitch will traverses all > mask array, because there will be one flow-mask in the tail. This > patch changes the way of flow-mask inserting and deleting, and the > mask array will be keep as below: there is not a NULL hole. In the > fast path, we can "break" "for" (not "continue") in flow_lookup > when we get a NULL flow-mask. > > "break" > v > +-------------------------------------------+ > | M | M | NULL |... | NULL | NULL| > +-------------------------------------------+ > > This patch don't optimize slow or control path, still using ma->max > to traverse. Slow path: > * tbl_mask_array_realloc > * ovs_flow_tbl_lookup_exact > * flow_mask_find > > Signed-off-by: Tonghao Zhang <xiangxia.m.yue@gmail.com> > Tested-by: Greg Rose <gvrose8192@gmail.com> > --- Acked-by: Pravin B Shelar <pshelar@ovn.org>
On Sat, Nov 2, 2019 at 11:50 PM Pravin Shelar <pshelar@ovn.org> wrote: > > On Fri, Nov 1, 2019 at 7:24 AM <xiangxia.m.yue@gmail.com> wrote: > > > > From: Tonghao Zhang <xiangxia.m.yue@gmail.com> > > > > The full looking up on flow table traverses all mask array. > > If mask-array is too large, the number of invalid flow-mask > > increase, performance will be drop. > > > > One bad case, for example: M means flow-mask is valid and NULL > > of flow-mask means deleted. > > > > +-------------------------------------------+ > > | M | NULL | ... | NULL | M| > > +-------------------------------------------+ > > > > In that case, without this patch, openvswitch will traverses all > > mask array, because there will be one flow-mask in the tail. This > > patch changes the way of flow-mask inserting and deleting, and the > > mask array will be keep as below: there is not a NULL hole. In the > > fast path, we can "break" "for" (not "continue") in flow_lookup > > when we get a NULL flow-mask. > > > > "break" > > v > > +-------------------------------------------+ > > | M | M | NULL |... | NULL | NULL| > > +-------------------------------------------+ > > > > This patch don't optimize slow or control path, still using ma->max > > to traverse. Slow path: > > * tbl_mask_array_realloc > > * ovs_flow_tbl_lookup_exact > > * flow_mask_find > > > > Signed-off-by: Tonghao Zhang <xiangxia.m.yue@gmail.com> > > Tested-by: Greg Rose <gvrose8192@gmail.com> > > --- > Acked-by: Pravin B Shelar <pshelar@ovn.org> Nack to this patch. It makes the mask cache invalid when moving the flow mask to fill another hole. And the penalty for miss the mask cache is larger than the benefit of this patch (avoiding the NULL flow-mask). William
From: William Tu <u9012063@gmail.com> Date: Mon, 4 Nov 2019 05:59:27 -0800 > Nack to this patch. These changes are already in net-next. If you already pointed out these problems in previous discussions, I'm sorry about that.
On Mon, Nov 4, 2019 at 6:00 AM William Tu <u9012063@gmail.com> wrote: > > On Sat, Nov 2, 2019 at 11:50 PM Pravin Shelar <pshelar@ovn.org> wrote: > > > > On Fri, Nov 1, 2019 at 7:24 AM <xiangxia.m.yue@gmail.com> wrote: > > > > > > From: Tonghao Zhang <xiangxia.m.yue@gmail.com> > > > > > > The full looking up on flow table traverses all mask array. > > > If mask-array is too large, the number of invalid flow-mask > > > increase, performance will be drop. > > > > > > One bad case, for example: M means flow-mask is valid and NULL > > > of flow-mask means deleted. > > > > > > +-------------------------------------------+ > > > | M | NULL | ... | NULL | M| > > > +-------------------------------------------+ > > > > > > In that case, without this patch, openvswitch will traverses all > > > mask array, because there will be one flow-mask in the tail. This > > > patch changes the way of flow-mask inserting and deleting, and the > > > mask array will be keep as below: there is not a NULL hole. In the > > > fast path, we can "break" "for" (not "continue") in flow_lookup > > > when we get a NULL flow-mask. > > > > > > "break" > > > v > > > +-------------------------------------------+ > > > | M | M | NULL |... | NULL | NULL| > > > +-------------------------------------------+ > > > > > > This patch don't optimize slow or control path, still using ma->max > > > to traverse. Slow path: > > > * tbl_mask_array_realloc > > > * ovs_flow_tbl_lookup_exact > > > * flow_mask_find > > > > > > Signed-off-by: Tonghao Zhang <xiangxia.m.yue@gmail.com> > > > Tested-by: Greg Rose <gvrose8192@gmail.com> > > > --- > > Acked-by: Pravin B Shelar <pshelar@ovn.org> > > Nack to this patch. > > It makes the mask cache invalid when moving the flow mask > to fill another hole. > And the penalty for miss the mask cache is larger than the > benefit of this patch (avoiding the NULL flow-mask). > Hi William, The cache invalidation would occur in case of changes to flow mask list. I think in general datapath processing there should not be too many changes to mask list since a mask is typically shared between multiple mega flows. Flow-table changes does not always result in mask list updates. In last round Tonghao has posted number to to support this patch. If you are worried about some other use case can you provide performance numbers, that way we can take this discussion forward. Thanks, Pravin.
On Mon, Nov 4, 2019 at 2:10 PM Pravin Shelar <pshelar@ovn.org> wrote: > > On Mon, Nov 4, 2019 at 6:00 AM William Tu <u9012063@gmail.com> wrote: > > > > On Sat, Nov 2, 2019 at 11:50 PM Pravin Shelar <pshelar@ovn.org> wrote: > > > > > > On Fri, Nov 1, 2019 at 7:24 AM <xiangxia.m.yue@gmail.com> wrote: > > > > > > > > From: Tonghao Zhang <xiangxia.m.yue@gmail.com> > > > > > > > > The full looking up on flow table traverses all mask array. > > > > If mask-array is too large, the number of invalid flow-mask > > > > increase, performance will be drop. > > > > > > > > One bad case, for example: M means flow-mask is valid and NULL > > > > of flow-mask means deleted. > > > > > > > > +-------------------------------------------+ > > > > | M | NULL | ... | NULL | M| > > > > +-------------------------------------------+ > > > > > > > > In that case, without this patch, openvswitch will traverses all > > > > mask array, because there will be one flow-mask in the tail. This > > > > patch changes the way of flow-mask inserting and deleting, and the > > > > mask array will be keep as below: there is not a NULL hole. In the > > > > fast path, we can "break" "for" (not "continue") in flow_lookup > > > > when we get a NULL flow-mask. > > > > > > > > "break" > > > > v > > > > +-------------------------------------------+ > > > > | M | M | NULL |... | NULL | NULL| > > > > +-------------------------------------------+ > > > > > > > > This patch don't optimize slow or control path, still using ma->max > > > > to traverse. Slow path: > > > > * tbl_mask_array_realloc > > > > * ovs_flow_tbl_lookup_exact > > > > * flow_mask_find > > > > > > > > Signed-off-by: Tonghao Zhang <xiangxia.m.yue@gmail.com> > > > > Tested-by: Greg Rose <gvrose8192@gmail.com> > > > > --- > > > Acked-by: Pravin B Shelar <pshelar@ovn.org> > > > > Nack to this patch. > > > > It makes the mask cache invalid when moving the flow mask > > to fill another hole. > > And the penalty for miss the mask cache is larger than the > > benefit of this patch (avoiding the NULL flow-mask). > > > Hi William, > > The cache invalidation would occur in case of changes to flow mask > list. I think in general datapath processing there should not be too > many changes to mask list since a mask is typically shared between > multiple mega flows. Flow-table changes does not always result in mask > list updates. In last round Tonghao has posted number to to support > this patch. > If you are worried about some other use case can you provide > performance numbers, that way we can take this discussion forward. > I see, I don't have any use case to provide. Thanks, William
diff --git a/net/openvswitch/flow_table.c b/net/openvswitch/flow_table.c index c7ba435..a10d421 100644 --- a/net/openvswitch/flow_table.c +++ b/net/openvswitch/flow_table.c @@ -518,8 +518,8 @@ static struct sw_flow *flow_lookup(struct flow_table *tbl, u32 *n_mask_hit, u32 *index) { - struct sw_flow_mask *mask; struct sw_flow *flow; + struct sw_flow_mask *mask; int i; if (*index < ma->max) { @@ -538,7 +538,7 @@ static struct sw_flow *flow_lookup(struct flow_table *tbl, mask = rcu_dereference_ovsl(ma->masks[i]); if (!mask) - continue; + break; flow = masked_flow_lookup(ti, key, mask, n_mask_hit); if (flow) { /* Found */ @@ -695,8 +695,7 @@ struct sw_flow *ovs_flow_tbl_lookup_ufid(struct flow_table *tbl, int ovs_flow_tbl_num_masks(const struct flow_table *table) { struct mask_array *ma = rcu_dereference_ovsl(table->mask_array); - - return ma->count; + return READ_ONCE(ma->count); } static struct table_instance *table_instance_expand(struct table_instance *ti, @@ -705,21 +704,33 @@ static struct table_instance *table_instance_expand(struct table_instance *ti, return table_instance_rehash(ti, ti->n_buckets * 2, ufid); } -static void tbl_mask_array_delete_mask(struct mask_array *ma, - struct sw_flow_mask *mask) +static void tbl_mask_array_del_mask(struct flow_table *tbl, + struct sw_flow_mask *mask) { - int i; + struct mask_array *ma = ovsl_dereference(tbl->mask_array); + int i, ma_count = READ_ONCE(ma->count); /* Remove the deleted mask pointers from the array */ - for (i = 0; i < ma->max; i++) { - if (mask == ovsl_dereference(ma->masks[i])) { - RCU_INIT_POINTER(ma->masks[i], NULL); - ma->count--; - kfree_rcu(mask, rcu); - return; - } + for (i = 0; i < ma_count; i++) { + if (mask == ovsl_dereference(ma->masks[i])) + goto found; } + BUG(); + return; + +found: + WRITE_ONCE(ma->count, ma_count -1); + + rcu_assign_pointer(ma->masks[i], ma->masks[ma_count -1]); + RCU_INIT_POINTER(ma->masks[ma_count -1], NULL); + + kfree_rcu(mask, rcu); + + /* Shrink the mask array if necessary. */ + if (ma->max >= (MASK_ARRAY_SIZE_MIN * 2) && + ma_count <= (ma->max / 3)) + tbl_mask_array_realloc(tbl, ma->max / 2); } /* Remove 'mask' from the mask list, if it is not needed any more. */ @@ -733,17 +744,8 @@ static void flow_mask_remove(struct flow_table *tbl, struct sw_flow_mask *mask) BUG_ON(!mask->ref_count); mask->ref_count--; - if (!mask->ref_count) { - struct mask_array *ma; - - ma = ovsl_dereference(tbl->mask_array); - tbl_mask_array_delete_mask(ma, mask); - - /* Shrink the mask array if necessary. */ - if (ma->max >= (MASK_ARRAY_SIZE_MIN * 2) && - ma->count <= (ma->max / 3)) - tbl_mask_array_realloc(tbl, ma->max / 2); - } + if (!mask->ref_count) + tbl_mask_array_del_mask(tbl, mask); } } @@ -807,6 +809,29 @@ static struct sw_flow_mask *flow_mask_find(const struct flow_table *tbl, return NULL; } +static int tbl_mask_array_add_mask(struct flow_table *tbl, + struct sw_flow_mask *new) +{ + struct mask_array *ma = ovsl_dereference(tbl->mask_array); + int err, ma_count = READ_ONCE(ma->count); + + if (ma_count >= ma->max) { + err = tbl_mask_array_realloc(tbl, ma->max + + MASK_ARRAY_SIZE_MIN); + if (err) + return err; + + ma = ovsl_dereference(tbl->mask_array); + } + + BUG_ON(ovsl_dereference(ma->masks[ma_count])); + + rcu_assign_pointer(ma->masks[ma_count], new); + WRITE_ONCE(ma->count, ma_count +1); + + return 0; +} + /* Add 'mask' into the mask list, if it is not already there. */ static int flow_mask_insert(struct flow_table *tbl, struct sw_flow *flow, const struct sw_flow_mask *new) @@ -815,9 +840,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(); if (!mask) @@ -826,29 +848,9 @@ static int flow_mask_insert(struct flow_table *tbl, struct sw_flow *flow, mask->range = new->range; /* Add mask to mask-list. */ - ma = ovsl_dereference(tbl->mask_array); - if (ma->count >= ma->max) { - int err; - - err = tbl_mask_array_realloc(tbl, ma->max + - MASK_ARRAY_SIZE_MIN); - if (err) { - kfree(mask); - return err; - } - - 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; - } + if (tbl_mask_array_add_mask(tbl, mask)) { + kfree(mask); + return -ENOMEM; } } else { BUG_ON(!mask->ref_count);