| Message ID | AT5PR84MB0210CD64E8568736C99822F2DC210@AT5PR84MB0210.NAMPRD84.PROD.OUTLOOK.COM |
|---|---|
| State | Changes Requested |
| Headers | show |
On Mon, Jun 27, 2016 at 08:07:02PM +0000, Rodriguez Betancourt, Esteban wrote: > Prevents the cloning of rows with outgoing or > incoming weak references when those rows aren't > being modified. > > It improves the OVSDB Server performance when > many rows with weak references are involved > in a transaction. > > Signed-off-by: Esteban Rodriguez Betancourt <estebarb@hpe.com> Great idea. Thanks for working on this! The new ovs_list_transplant() function takes two "const" pointers to lists but it modifies both lists. I don't think it makes sense for them to be const. The new ovs_list_transplant() function has a name that doesn't give much of a idea of what it does. I think that really it appends everything in 'src' to 'dst', although those are not great names since both lists are modified. Maybe ovs_list_push_back_all() would be a better name. I think that the new ovs_list_transplant() function can be implemented in terms of ovs_list_splice(), as: ovs_list_splice(dst, &src->next, src); I see a couple of existing uses of ovs_list_splice() to do that, so it's probably best to convert them to use the new function for consistency. Since add_weak_ref() doesn't use its first argument now, please delete the parameter entirely instead of marking it OVS_UNUSED. In add_weak_ref(), instead of using memcpy() to copy a struct uuid, please use an ordinary assignment with =. I don't think that this loop in ovsdb_txn_update_weak_refs() needs to be the _SAFE variant: it appears to me that it iterates on ->src_refs and ->src_node but only modifies ->dst_refs and ->dst_node: > + LIST_FOR_EACH_SAFE (weak, next, src_node, &txn_row->new->src_refs) { > + /* dst_row MUST exist */ > + dst_row = CONST_CAST(struct ovsdb_row *, > + ovsdb_table_get_row(weak->dst_table, &weak->dst)); > + ovs_list_insert(&dst_row->dst_refs, &weak->dst_node); > + } It's taking me some thought to convince myself that this new version is as correct as the previous version. Do you have any arguments or explanations to help me out? Thanks, Ben.
Thanks for the comments, I'm going to send soon a new patch with the suggestions
applied.
About how the patch works:
The first attempt to stop the cascade changes was something like:
@@ -471,7 +512,7 @@ assess_weak_refs(struct ovsdb_txn *txn, struct ovsdb_txn_row *txn_row)
struct ovsdb_table *table;
struct shash_node *node;
- if (txn_row->old) {
+ if (txn_row->old && !txn_row->new) {
The rationale was: the weak references are linked by UUID, and the UUID never changes, unless
if the current row is being deleted. So, we in fact didn't need to change the rows that weak-referenced
the current row if the row wasn't deleted.
It didn't works: we discover that the modified rows were lacking incoming weak references in
the dst_refs list, so that gives us the idea of "moving" the references in old->dst_refs to new->dst_refs.
In the original code (dst_refs is created from scratch):
old->dst_refs = all the rows that weak referenced old
new->dst_refs = all the rows that weak referenced old and are still weak referencing new + rows in the transaction that weak referenced new
In the patch (dst_refs incrementally built):
Old->dst_refs = all the rows that weak referenced old
(Ideally, but expansive to calculate:)
New->dst_refs = old->dst_refs - "weak references removed within this TXN" + "weak references created within this TXN"
(What was implemented:)
New->dst_refs = old->dst_refs - "weak references in old rows in TXN" + "weak references in new rows in TXN"
The resulting sets should be equal in both cases.
There we do some more optimizations:
- If we know that the transactions must be successful at some point then,
instead of cloning dst_refs we could just move the elements between
the lists.
- At that point we lost the rollback feature, but we aren't going to need
it anyway (note that we didn't really touch the src_refs part).
- The references in dst_refs must point to new instead than old.
Previously we iterated over all the weak references in dst_refs
to change that pointer, but using an UUID is easier, and prevents
that iteration completely.
Regards,
Esteban
> -----Original Message-----
> From: Ben Pfaff [mailto:blp@ovn.org]
> Sent: sábado, 2 de julio de 2016 14:06
> To: Rodriguez Betancourt, Esteban <estebarb@hpe.com>
> Cc: dev@openvswitch.org
> Subject: Re: [ovs-dev] [PATCH] ovsdb: Weak references performance fix
>
> On Mon, Jun 27, 2016 at 08:07:02PM +0000, Rodriguez Betancourt, Esteban
> wrote:
> > Prevents the cloning of rows with outgoing or incoming weak references
> > when those rows aren't being modified.
> >
> > It improves the OVSDB Server performance when many rows with weak
> > references are involved in a transaction.
> >
> > Signed-off-by: Esteban Rodriguez Betancourt <estebarb@hpe.com>
>
> Great idea. Thanks for working on this!
>
> The new ovs_list_transplant() function takes two "const" pointers to lists but
> it modifies both lists. I don't think it makes sense for them to be const.
>
> The new ovs_list_transplant() function has a name that doesn't give much of
> a idea of what it does. I think that really it appends everything in 'src' to 'dst',
> although those are not great names since both lists are modified. Maybe
> ovs_list_push_back_all() would be a better name.
>
> I think that the new ovs_list_transplant() function can be implemented in
> terms of ovs_list_splice(), as:
> ovs_list_splice(dst, &src->next, src); I see a couple of existing uses of
> ovs_list_splice() to do that, so it's probably best to convert them to use the
> new function for consistency.
>
> Since add_weak_ref() doesn't use its first argument now, please delete the
> parameter entirely instead of marking it OVS_UNUSED.
>
> In add_weak_ref(), instead of using memcpy() to copy a struct uuid, please
> use an ordinary assignment with =.
>
> I don't think that this loop in ovsdb_txn_update_weak_refs() needs to be
> the _SAFE variant: it appears to me that it iterates on ->src_refs and
> ->src_node but only modifies ->dst_refs and ->dst_node:
> > + LIST_FOR_EACH_SAFE (weak, next, src_node, &txn_row->new-
> >src_refs) {
> > + /* dst_row MUST exist */
> > + dst_row = CONST_CAST(struct ovsdb_row *,
> > + ovsdb_table_get_row(weak->dst_table, &weak->dst));
> > + ovs_list_insert(&dst_row->dst_refs, &weak->dst_node);
> > + }
>
> It's taking me some thought to convince myself that this new version is as
> correct as the previous version. Do you have any arguments or explanations
> to help me out?
>
> Thanks,
>
> Ben.
That's a great explanation. I understand better now. Thank you. On Fri, Jul 08, 2016 at 08:34:46PM +0000, Rodriguez Betancourt, Esteban wrote: > Thanks for the comments, I'm going to send soon a new patch with the suggestions > applied. > > About how the patch works: > The first attempt to stop the cascade changes was something like: > > @@ -471,7 +512,7 @@ assess_weak_refs(struct ovsdb_txn *txn, struct ovsdb_txn_row *txn_row) > struct ovsdb_table *table; > struct shash_node *node; > > - if (txn_row->old) { > + if (txn_row->old && !txn_row->new) { > > The rationale was: the weak references are linked by UUID, and the UUID never changes, unless > if the current row is being deleted. So, we in fact didn't need to change the rows that weak-referenced > the current row if the row wasn't deleted. > It didn't works: we discover that the modified rows were lacking incoming weak references in > the dst_refs list, so that gives us the idea of "moving" the references in old->dst_refs to new->dst_refs. > > In the original code (dst_refs is created from scratch): > > old->dst_refs = all the rows that weak referenced old > > new->dst_refs = all the rows that weak referenced old and are still weak referencing new + rows in the transaction that weak referenced new > > > > In the patch (dst_refs incrementally built): > Old->dst_refs = all the rows that weak referenced old > > (Ideally, but expansive to calculate:) > New->dst_refs = old->dst_refs - "weak references removed within this TXN" + "weak references created within this TXN" > > (What was implemented:) > New->dst_refs = old->dst_refs - "weak references in old rows in TXN" + "weak references in new rows in TXN" > > The resulting sets should be equal in both cases. > > > There we do some more optimizations: > - If we know that the transactions must be successful at some point then, > instead of cloning dst_refs we could just move the elements between > the lists. > > - At that point we lost the rollback feature, but we aren't going to need > it anyway (note that we didn't really touch the src_refs part). > > - The references in dst_refs must point to new instead than old. > Previously we iterated over all the weak references in dst_refs > to change that pointer, but using an UUID is easier, and prevents > that iteration completely. > > Regards, > Esteban > > > -----Original Message----- > > From: Ben Pfaff [mailto:blp@ovn.org] > > Sent: sábado, 2 de julio de 2016 14:06 > > To: Rodriguez Betancourt, Esteban <estebarb@hpe.com> > > Cc: dev@openvswitch.org > > Subject: Re: [ovs-dev] [PATCH] ovsdb: Weak references performance fix > > > > On Mon, Jun 27, 2016 at 08:07:02PM +0000, Rodriguez Betancourt, Esteban > > wrote: > > > Prevents the cloning of rows with outgoing or incoming weak references > > > when those rows aren't being modified. > > > > > > It improves the OVSDB Server performance when many rows with weak > > > references are involved in a transaction. > > > > > > Signed-off-by: Esteban Rodriguez Betancourt <estebarb@hpe.com> > > > > Great idea. Thanks for working on this! > > > > The new ovs_list_transplant() function takes two "const" pointers to lists but > > it modifies both lists. I don't think it makes sense for them to be const. > > > > The new ovs_list_transplant() function has a name that doesn't give much of > > a idea of what it does. I think that really it appends everything in 'src' to 'dst', > > although those are not great names since both lists are modified. Maybe > > ovs_list_push_back_all() would be a better name. > > > > I think that the new ovs_list_transplant() function can be implemented in > > terms of ovs_list_splice(), as: > > ovs_list_splice(dst, &src->next, src); I see a couple of existing uses of > > ovs_list_splice() to do that, so it's probably best to convert them to use the > > new function for consistency. > > > > Since add_weak_ref() doesn't use its first argument now, please delete the > > parameter entirely instead of marking it OVS_UNUSED. > > > > In add_weak_ref(), instead of using memcpy() to copy a struct uuid, please > > use an ordinary assignment with =. > > > > I don't think that this loop in ovsdb_txn_update_weak_refs() needs to be > > the _SAFE variant: it appears to me that it iterates on ->src_refs and > > ->src_node but only modifies ->dst_refs and ->dst_node: > > > + LIST_FOR_EACH_SAFE (weak, next, src_node, &txn_row->new- > > >src_refs) { > > > + /* dst_row MUST exist */ > > > + dst_row = CONST_CAST(struct ovsdb_row *, > > > + ovsdb_table_get_row(weak->dst_table, &weak->dst)); > > > + ovs_list_insert(&dst_row->dst_refs, &weak->dst_node); > > > + } > > > > It's taking me some thought to convince myself that this new version is as > > correct as the previous version. Do you have any arguments or explanations > > to help me out? > > > > Thanks, > > > > Ben.
diff --git a/include/openvswitch/list.h b/include/openvswitch/list.h index 5c2cca4..a762ef7 100644 --- a/include/openvswitch/list.h +++ b/include/openvswitch/list.h @@ -288,4 +288,23 @@ ovs_list_is_short(const struct ovs_list *list) return list->next == list->prev; } +/* Transplant a list into another, and resets the origin list */ +static inline void +ovs_list_transplant(const struct ovs_list *dst_, const struct ovs_list *src_) +{ + struct ovs_list *src, *dst; + src = CONST_CAST(struct ovs_list *, src_); + dst = CONST_CAST(struct ovs_list *, dst_); + + /* Chain last element of dst with first of src */ + src->next->prev = dst->prev; + dst->prev->next = src->next; + + /* Chain last element of src with head of dst */ + src->prev->next = dst; + dst->prev = src->prev; + + ovs_list_init(src); +} + #endif /* list.h */ diff --git a/ovsdb/row.h b/ovsdb/row.h index b1d1edd..b38c7dd 100644 --- a/ovsdb/row.h +++ b/ovsdb/row.h @@ -36,9 +36,11 @@ struct ovsdb_column_set; * ovsdb_weak_ref" structures are created for them. */ struct ovsdb_weak_ref { - struct ovs_list src_node; /* In src->src_refs list. */ - struct ovs_list dst_node; /* In destination row's dst_refs list. */ - struct ovsdb_row *src; /* Source row. */ + struct ovs_list src_node; /* In src->src_refs list. */ + struct ovs_list dst_node; /* In destination row's dst_refs list. */ + struct ovsdb_row *src; /* Source row. */ + struct ovsdb_table *dst_table; /* Destination table. */ + struct uuid dst; /* Destination row uuid. */ }; /* A row in a database table. */ diff --git a/ovsdb/transaction.c b/ovsdb/transaction.c index 9e12a62..5ad3de0 100644 --- a/ovsdb/transaction.c +++ b/ovsdb/transaction.c @@ -436,8 +436,48 @@ ovsdb_txn_row_commit(struct ovsdb_txn *txn OVS_UNUSED, return NULL; } +static struct ovsdb_error * +ovsdb_txn_update_weak_refs(struct ovsdb_txn *txn OVS_UNUSED, + struct ovsdb_txn_row *txn_row) +{ + struct ovsdb_weak_ref *weak, *next; + + /* Remove the weak references originating in the old version of the row */ + if (txn_row->old) { + LIST_FOR_EACH_SAFE (weak, next, src_node, &txn_row->old->src_refs) { + ovs_list_remove(&weak->src_node); + ovs_list_remove(&weak->dst_node); + free(weak); + } + } + + /* Although the originating rows have the responsability of updating the + * weak references in the dst, is possible that some source rows aren't + * part of the transaction. + * In that situation this row needs to move the list of incoming weak + * references from the old row into the new one. + */ + if (txn_row->old && txn_row->new) { + /* Move the incoming weak references from old to new */ + ovs_list_transplant(&txn_row->new->dst_refs, &txn_row->old->dst_refs); + } + + /* Insert the weak references originating in the new version of the row */ + struct ovsdb_row *dst_row; + if (txn_row->new) { + LIST_FOR_EACH_SAFE (weak, next, src_node, &txn_row->new->src_refs) { + /* dst_row MUST exist */ + dst_row = CONST_CAST(struct ovsdb_row *, + ovsdb_table_get_row(weak->dst_table, &weak->dst)); + ovs_list_insert(&dst_row->dst_refs, &weak->dst_node); + } + } + + return NULL; +} + static void -add_weak_ref(struct ovsdb_txn *txn, +add_weak_ref(struct ovsdb_txn *txn OVS_UNUSED, const struct ovsdb_row *src_, const struct ovsdb_row *dst_) { struct ovsdb_row *src = CONST_CAST(struct ovsdb_row *, src_); @@ -448,8 +488,6 @@ add_weak_ref(struct ovsdb_txn *txn, return; } - dst = ovsdb_txn_row_modify(txn, dst); - if (!ovs_list_is_empty(&dst->dst_refs)) { /* Omit duplicates. */ weak = CONTAINER_OF(ovs_list_back(&dst->dst_refs), @@ -461,7 +499,10 @@ add_weak_ref(struct ovsdb_txn *txn, weak = xmalloc(sizeof *weak); weak->src = src; - ovs_list_push_back(&dst->dst_refs, &weak->dst_node); + weak->dst_table = dst->table; + memcpy(&weak->dst, ovsdb_row_get_uuid(dst), sizeof(struct uuid)); + /* The dst_refs list is updated at commit time */ + ovs_list_init(&weak->dst_node); ovs_list_push_back(&src->src_refs, &weak->src_node); } @@ -471,7 +512,7 @@ assess_weak_refs(struct ovsdb_txn *txn, struct ovsdb_txn_row *txn_row) struct ovsdb_table *table; struct shash_node *node; - if (txn_row->old) { + if (txn_row->old && !txn_row->new) { /* Mark rows that have weak references to 'txn_row' as modified, so * that their weak references will get reassessed. */ struct ovsdb_weak_ref *weak, *next; @@ -838,6 +879,7 @@ ovsdb_txn_commit_(struct ovsdb_txn *txn, bool durable) /* Finalize commit. */ txn->db->run_triggers = true; + ovsdb_error_assert(for_each_txn_row(txn, ovsdb_txn_update_weak_refs)); ovsdb_error_assert(for_each_txn_row(txn, ovsdb_txn_row_commit)); ovsdb_txn_free(txn); diff --git a/tests/library.at b/tests/library.at index e5095a0..69a14e9 100644 --- a/tests/library.at +++ b/tests/library.at @@ -44,7 +44,7 @@ AT_CHECK([ovstest test-atomic]) AT_CLEANUP AT_SETUP([linked lists]) -AT_CHECK([ovstest test-list], [0], [... +AT_CHECK([ovstest test-list], [0], [.... ]) AT_CLEANUP diff --git a/tests/test-list.c b/tests/test-list.c index d413f30..d85b9ad 100644 --- a/tests/test-list.c +++ b/tests/test-list.c @@ -185,6 +185,46 @@ test_list_for_each_pop(void) } } +/* Tests the transplant of one list into another */ +static void +test_list_transplant(void) +{ + struct ovs_list list_a, list_b; + struct element a, b, c, d; + + a.value = 0; + b.value = 1; + c.value = 2; + d.value = 3; + + ovs_list_init(&list_a); + ovs_list_init(&list_b); + + ovs_list_insert(&list_a, &a.node); + ovs_list_insert(&list_a, &b.node); + ovs_list_insert(&list_b, &c.node); + ovs_list_insert(&list_b, &d.node); + + /* Check test preconditions */ + assert(2 == ovs_list_size(&list_a)); + assert(2 == ovs_list_size(&list_b)); + + /* Perform transplant */ + ovs_list_transplant(&list_a, &list_b); + + /* Check expected result */ + assert(4 == ovs_list_size(&list_a)); + assert(0 == ovs_list_size(&list_b)); + + struct element *node; + int n = 0; + LIST_FOR_EACH(node, node, &list_a) { + assert(n == node->value); + n++; + } + assert(n == 4); +} + static void run_test(void (*function)(void)) { @@ -198,6 +238,7 @@ test_list_main(int argc OVS_UNUSED, char *argv[] OVS_UNUSED) run_test(test_list_construction); run_test(test_list_for_each_safe); run_test(test_list_for_each_pop); + run_test(test_list_transplant); printf("\n"); }
Prevents the cloning of rows with outgoing or incoming weak references when those rows aren't being modified. It improves the OVSDB Server performance when many rows with weak references are involved in a transaction. Signed-off-by: Esteban Rodriguez Betancourt <estebarb@hpe.com> --- include/openvswitch/list.h | 19 +++++++++++++++++ ovsdb/row.h | 8 ++++--- ovsdb/transaction.c | 52 +++++++++++++++++++++++++++++++++++++++++----- tests/library.at | 2 +- tests/test-list.c | 41 ++++++++++++++++++++++++++++++++++++ 5 files changed, 113 insertions(+), 9 deletions(-)