diff mbox

[ovs-dev,monitor2,v2,4/9] lib: add diff and apply diff APIs for ovsdb_datum

Message ID 1448403366-21460-4-git-send-email-azhou@ovn.org
State Deferred
Headers show

Commit Message

Andy Zhou Nov. 24, 2015, 10:16 p.m. UTC 
From: Andy Zhou <azhou@nicira.com>

When an OVSDB column change its value, it is more efficient to only
send what has changed, rather than sending the entire new copy.
This is analogous to software programmer send patches rather than
the entire source file.

For columns store a single element, the "diff" datum is the same
as the "new" datum.

For columns that store set or map, it is only necessary to send the
information about the elements changed (including addition or removal).
The "diff" for those types are all elements that are changed.

Those APIs are mainly used for implementing a new OVSDB server
"update2" JSON-RPC notification, which encodes modifications
of a column with the contents of those "diff"s. Later patch implements
the "update2" notification.

Signed-off-by: Andy Zhou <azhou@nicira.com>

---
v1->v2:  Change ovsdb_datum_diff() and ovsdb_datum_apply_diff() API
         to accept the 'diff' rather than create the object within
	 the function.

	 Change test to print the diff object and resulting object
	 after applying diff
---
 lib/ovsdb-data.c    | 83 +++++++++++++++++++++++++++++++++++++++++++++++++++++
 lib/ovsdb-data.h    | 14 ++++++++-
 tests/ovsdb-data.at | 80 +++++++++++++++++++++++++++++++++++++++++++++++++++
 tests/test-ovsdb.c  | 61 ++++++++++++++++++++++++++++++++++++++-
 4 files changed, 236 insertions(+), 2 deletions(-)

Comments

Ben Pfaff Nov. 30, 2015, 3:12 a.m. UTC | #1 
On Tue, Nov 24, 2015 at 02:16:01PM -0800, Andy Zhou wrote:
> From: Andy Zhou <azhou@nicira.com>
> 
> When an OVSDB column change its value, it is more efficient to only
> send what has changed, rather than sending the entire new copy.
> This is analogous to software programmer send patches rather than
> the entire source file.
> 
> For columns store a single element, the "diff" datum is the same
> as the "new" datum.
> 
> For columns that store set or map, it is only necessary to send the
> information about the elements changed (including addition or removal).
> The "diff" for those types are all elements that are changed.
> 
> Those APIs are mainly used for implementing a new OVSDB server
> "update2" JSON-RPC notification, which encodes modifications
> of a column with the contents of those "diff"s. Later patch implements
> the "update2" notification.
> 
> Signed-off-by: Andy Zhou <azhou@nicira.com>
> 
> ---
> v1->v2:  Change ovsdb_datum_diff() and ovsdb_datum_apply_diff() API
>          to accept the 'diff' rather than create the object within
> 	 the function.
> 
> 	 Change test to print the diff object and resulting object
> 	 after applying diff

Thanks Andy.

Acked-by: Ben Pfaff <blp@ovn.org>
Liran Schour Dec. 1, 2015, 2:20 p.m. UTC | #2 
"dev" <dev-bounces@openvswitch.org> wrote on 25/11/2015 12:16:01 AM:

> From: Andy Zhou <azhou@nicira.com>
> @@ -617,6 +621,101 @@ monitor_print(struct json *table_updates,
> }
> 
> static void
> +monitor2_print_row(struct json *row, const char *type, const char 
*uuid,
> +                   const struct ovsdb_column_set *columns, struct table 
*t)
> +{
> +    if (!strcmp(type, "delete")) {
> +        if (row->type != JSON_NULL) {
> +            ovs_error(0, "delete method does not expect <row>");
> +            return;
> +        }
> +
> +        table_add_row(t);
> +        table_add_cell(t)->text = xstrdup(uuid);
> +        table_add_cell(t)->text = xstrdup(type);
> +    } else {
> +        if (!row || row->type != JSON_OBJECT) {
> +            ovs_error(0, "<row> is not object");
> +            return;
> +        }
> +        monitor_print_row(row, type, uuid, columns, t);
> +    }
> +}

Update2 does not send default values, therefore we will miss these values 
on ovsdb-client.
I can fix it on monitor_cond or you can send an updated patch.
Andy Zhou Dec. 11, 2015, 10:37 p.m. UTC | #3 
On Tue, Dec 1, 2015 at 6:20 AM, Liran Schour <LIRANS@il.ibm.com> wrote:

> "dev" <dev-bounces@openvswitch.org> wrote on 25/11/2015 12:16:01 AM:
>
> > From: Andy Zhou <azhou@nicira.com>
> > @@ -617,6 +621,101 @@ monitor_print(struct json *table_updates,
> > }
> >
> > static void
> > +monitor2_print_row(struct json *row, const char *type, const char
> *uuid,
> > +                   const struct ovsdb_column_set *columns, struct table
> *t)
> > +{
> > +    if (!strcmp(type, "delete")) {
> > +        if (row->type != JSON_NULL) {
> > +            ovs_error(0, "delete method does not expect <row>");
> > +            return;
> > +        }
> > +
> > +        table_add_row(t);
> > +        table_add_cell(t)->text = xstrdup(uuid);
> > +        table_add_cell(t)->text = xstrdup(type);
> > +    } else {
> > +        if (!row || row->type != JSON_OBJECT) {
> > +            ovs_error(0, "<row> is not object");
> > +            return;
> > +        }
> > +        monitor_print_row(row, type, uuid, columns, t);
> > +    }
> > +}
>
> Update2 does not send default values, therefore we will miss these values
> on ovsdb-client.
> I can fix it on monitor_cond or you can send an updated patch.
>

What changes do you have in mind?

The goal of "monitor" command is to show what's being transmitted per ovsdb
remote protocol. Since
the default values are not being transmitted, I'd think it is O.K. not to
show them. No?

>
> _______________________________________________
> dev mailing list
> dev@openvswitch.org
> http://openvswitch.org/mailman/listinfo/dev
>
Liran Schour Dec. 14, 2015, 6:55 a.m. UTC | #4 
Andy Zhou <azhou@ovn.org> wrote on 12/12/2015 12:37:32 AM:

> On Tue, Dec 1, 2015 at 6:20 AM, Liran Schour <LIRANS@il.ibm.com> wrote:
> "dev" <dev-bounces@openvswitch.org> wrote on 25/11/2015 12:16:01 AM:
> 
> > From: Andy Zhou <azhou@nicira.com>
> > @@ -617,6 +621,101 @@ monitor_print(struct json *table_updates,
> > }
> >
> > static void
> > +monitor2_print_row(struct json *row, const char *type, const char
> *uuid,
> > +                   const struct ovsdb_column_set *columns, struct 
table
> *t)
> > +{
> > +    if (!strcmp(type, "delete")) {
> > +        if (row->type != JSON_NULL) {
> > +            ovs_error(0, "delete method does not expect <row>");
> > +            return;
> > +        }
> > +
> > +        table_add_row(t);
> > +        table_add_cell(t)->text = xstrdup(uuid);
> > +        table_add_cell(t)->text = xstrdup(type);
> > +    } else {
> > +        if (!row || row->type != JSON_OBJECT) {
> > +            ovs_error(0, "<row> is not object");
> > +            return;
> > +        }
> > +        monitor_print_row(row, type, uuid, columns, t);
> > +    }
> > +}
> 
> Update2 does not send default values, therefore we will miss these 
values
> on ovsdb-client.
> I can fix it on monitor_cond or you can send an updated patch.
> 
> What changes do you have in mind? 

> The goal of "monitor" command is to show what's being transmitted 
> per ovsdb remote protocol. Since
> the default values are not being transmitted, I'd think it is O.K. 
> not to show them. No?
> 

OK. I thought the user expects to see the real outcome of the updates. If 
not and "monitor" command should show only what is being transmitted it is 
OK like it is now.

Thanks
Ben Pfaff Dec. 14, 2015, 12:22 p.m. UTC | #5 
On Mon, Dec 14, 2015 at 08:55:01AM +0200, Liran Schour wrote:
> Andy Zhou <azhou@ovn.org> wrote on 12/12/2015 12:37:32 AM:
> 
> > On Tue, Dec 1, 2015 at 6:20 AM, Liran Schour <LIRANS@il.ibm.com> wrote:
> > "dev" <dev-bounces@openvswitch.org> wrote on 25/11/2015 12:16:01 AM:
> > 
> > > From: Andy Zhou <azhou@nicira.com>
> > > @@ -617,6 +621,101 @@ monitor_print(struct json *table_updates,
> > > }
> > >
> > > static void
> > > +monitor2_print_row(struct json *row, const char *type, const char
> > *uuid,
> > > +                   const struct ovsdb_column_set *columns, struct 
> table
> > *t)
> > > +{
> > > +    if (!strcmp(type, "delete")) {
> > > +        if (row->type != JSON_NULL) {
> > > +            ovs_error(0, "delete method does not expect <row>");
> > > +            return;
> > > +        }
> > > +
> > > +        table_add_row(t);
> > > +        table_add_cell(t)->text = xstrdup(uuid);
> > > +        table_add_cell(t)->text = xstrdup(type);
> > > +    } else {
> > > +        if (!row || row->type != JSON_OBJECT) {
> > > +            ovs_error(0, "<row> is not object");
> > > +            return;
> > > +        }
> > > +        monitor_print_row(row, type, uuid, columns, t);
> > > +    }
> > > +}
> > 
> > Update2 does not send default values, therefore we will miss these 
> values
> > on ovsdb-client.
> > I can fix it on monitor_cond or you can send an updated patch.
> > 
> > What changes do you have in mind? 
> 
> > The goal of "monitor" command is to show what's being transmitted 
> > per ovsdb remote protocol. Since
> > the default values are not being transmitted, I'd think it is O.K. 
> > not to show them. No?
> > 
> 
> OK. I thought the user expects to see the real outcome of the updates. If 
> not and "monitor" command should show only what is being transmitted it is 
> OK like it is now.

I guess that the purpose could be argued either way, but I think it's
reasonable to have it work the way Andy did it.
diff mbox

Patch

diff --git a/lib/ovsdb-data.c b/lib/ovsdb-data.c
index f7d0b06..75febad 100644
--- a/lib/ovsdb-data.c
+++ b/lib/ovsdb-data.c
@@ -1905,6 +1905,89 @@  ovsdb_symbol_table_insert(struct ovsdb_symbol_table *symtab,
     return symbol;
 }
 
+/* APIs for Generating and apply diffs.  */
+
+/* Generate a difference ovsdb_dataum between 'old' and 'new'.
+ * 'new' can be regenerated by applying the difference to the 'old'.
+ *
+ * The diff operation is reversible. Given 'old',
+ * 'new' can be recreated by applying diff to 'old'.
+ *
+ * Thus
+ *     Let  d = 'old' diff 'new'
+ *     then 'new' = 'old' diff d
+ *
+ * The 'diff' datum is always safe; the orders of keys are maintained
+ * since they are added in order.   */
+void
+ovsdb_datum_diff(struct ovsdb_datum *diff,
+                 const struct ovsdb_datum *old,
+                 const struct ovsdb_datum *new,
+                 const struct ovsdb_type *type)
+{
+    size_t oi, ni;
+
+    ovsdb_datum_init_empty(diff);
+    if (!ovsdb_type_is_composite(type)) {
+        ovsdb_datum_clone(diff, new, type);
+        return;
+    }
+
+    /* Generate the diff in O(n) time. */
+    for (oi = ni = 0; oi < old->n && ni < new->n; ) {
+        int c = ovsdb_atom_compare_3way(&old->keys[oi], &new->keys[ni],
+                                        type->key.type);
+        if (c < 0) {
+            ovsdb_datum_add_unsafe(diff, &old->keys[oi], &old->values[oi],
+                                   type);
+            oi++;
+        } else if (c > 0) {
+            ovsdb_datum_add_unsafe(diff, &new->keys[ni], &new->values[ni],
+                                   type);
+            ni++;
+        } else {
+            if (type->value.type != OVSDB_TYPE_VOID &&
+                ovsdb_atom_compare_3way(&old->values[oi], &new->values[ni],
+                                        type->value.type)) {
+                ovsdb_datum_add_unsafe(diff, &new->keys[ni], &new->values[ni],
+                                       type);
+            }
+            oi++; ni++;
+        }
+    }
+
+    for (; oi < old->n; oi++) {
+        ovsdb_datum_add_unsafe(diff, &old->keys[oi], &old->values[oi], type);
+    }
+
+    for (; ni < new->n; ni++) {
+        ovsdb_datum_add_unsafe(diff, &new->keys[ni], &new->values[ni], type);
+    }
+}
+
+/* Apply 'diff' to 'old' to regenerate 'new'.
+ *
+ * Return NULL if the 'new' is successfully generated, otherwise, return
+ * ovsdb_error and the stat of 'new' is indeterministic. */
+struct ovsdb_error *
+ovsdb_datum_apply_diff(struct ovsdb_datum *new,
+                       const struct ovsdb_datum *old,
+                       const struct ovsdb_datum *diff,
+                       const struct ovsdb_type *type)
+{
+    ovsdb_datum_init_empty(new);
+    ovsdb_datum_diff(new, old, diff, type);
+
+    /* Make sure member size of 'new' conforms to type. */
+    if (new->n < type->n_min || new->n > type->n_max) {
+        ovsdb_datum_destroy(new, type);
+        return ovsdb_error(NULL, "Datum crated by diff has size error");
+    }
+
+    return NULL;
+}
+
+
 /* Extracts a token from the beginning of 's' and returns a pointer just after
  * the token.  Stores the token itself into '*outp', which the caller is
  * responsible for freeing (with free()).
diff --git a/lib/ovsdb-data.h b/lib/ovsdb-data.h
index 802f718..2789540 100644
--- a/lib/ovsdb-data.h
+++ b/lib/ovsdb-data.h
@@ -1,4 +1,4 @@ 
-/* Copyright (c) 2009, 2010, 2011, 2012 Nicira, Inc.
+/* Copyright (c) 2009, 2010, 2011, 2012, 2015 Nicira, Inc.
  *
  * Licensed under the Apache License, Version 2.0 (the "License");
  * you may not use this file except in compliance with the License.
@@ -216,6 +216,18 @@  void ovsdb_datum_subtract(struct ovsdb_datum *a,
                           const struct ovsdb_datum *b,
                           const struct ovsdb_type *b_type);
 
+/* Generate and apply diffs */
+void ovsdb_datum_diff(struct ovsdb_datum *diff,
+                      const struct ovsdb_datum *old,
+                      const struct ovsdb_datum *new,
+                      const struct ovsdb_type *type);
+
+struct ovsdb_error *ovsdb_datum_apply_diff(struct ovsdb_datum *new,
+                                           const struct ovsdb_datum *old,
+                                           const struct ovsdb_datum *diff,
+                                           const struct ovsdb_type *type)
+OVS_WARN_UNUSED_RESULT;
+
 /* Raw operations that may not maintain the invariants. */
 void ovsdb_datum_remove_unsafe(struct ovsdb_datum *, size_t idx,
                                const struct ovsdb_type *);
diff --git a/tests/ovsdb-data.at b/tests/ovsdb-data.at
index ed8cb0e..468e3b0 100644
--- a/tests/ovsdb-data.at
+++ b/tests/ovsdb-data.at
@@ -783,3 +783,83 @@  OVSDB_CHECK_NEGATIVE([duplicate integer key not allowed in string map],
   [[parse-data-strings '{"key": "integer", "value": "boolean", "max": 5}' \
     '1=true 2=false 1=false']],
   [map contains duplicate key])
+
+OVSDB_CHECK_POSITIVE([generate and apply diff -- integer],
+  [[diff-data '["integer"]' '[0]' '[2]']],
+  [[diff: 2
+apply diff: 2
+OK]])
+
+OVSDB_CHECK_POSITIVE([generate and apply diff -- boolean],
+  [[diff-data '["boolean"]' '[true]' '[false]']],
+  [[diff: false
+apply diff: false
+OK]])
+
+OVSDB_CHECK_POSITIVE([generate and apply diff -- string],
+  [[diff-data '["string"]' '["AAA"]' '["BBB"]']],
+  [[diff: "BBB"
+apply diff: "BBB"
+OK]])
+
+dnl Test set modifications.
+OVSDB_CHECK_POSITIVE([generate and apply diff -- set],
+  [[diff-data '{"key": "integer", "min":0, "max": 3}' \
+  '["set", [0, 1]]'  '["set", [1,2]]' \
+  '["set", [0, 1]]'  '["set", [1]]' \
+  '["set", []]'  '["set", [0, 1]]' \
+  '["set", [0, 1]]'  '["set", []]'
+  ]],
+  [[diff: ["set",[0,2]]
+apply diff: ["set",[1,2]]
+OK
+diff: 0
+apply diff: 1
+OK
+diff: ["set",[0,1]]
+apply diff: ["set",[0,1]]
+OK
+diff: ["set",[0,1]]
+apply diff: ["set",[]]
+OK]])
+
+dnl Test set modifications causes data to violate set size constrain.
+OVSDB_CHECK_NEGATIVE([generate and apply diff -- set -- size error],
+  [[diff-data '{"key": "integer", "min":0, "max": 3}' \
+  '["set", [0, 1]]'  '["set", [1, 2, 3, 4]]']],
+  [[ovsdb error: Datum crated by diff has size error]])
+
+dnl Test set modifications.
+OVSDB_CHECK_POSITIVE([generate and apply diff -- map],
+  [[diff-data '{"key": "string", "value": "string", "min":0, "max": 3}' \
+  '["map", [["2 gills", "1 chopin"]]]'  '["map", [["2 pints", "1 quart"]]]' \
+  '["map", [["2 gills", "1 chopin"]]]'  '["map", [["2 gills", "1 chopin"]]]' \
+  '["map", [["2 gills", "1 chopin"]]]'  '["map", []]' \
+  '["map", []]'  '["map", [["2 pints", "1 quart"]]]' \
+  '["map", [["2 gills", "1 chopin"]]]'  '["map", [["2 gills", "1 gallon"]]]' \
+  ]],
+  [[diff: ["map",[["2 gills","1 chopin"],["2 pints","1 quart"]]]
+apply diff: ["map",[["2 pints","1 quart"]]]
+OK
+diff: ["map",[]]
+apply diff: ["map",[["2 gills","1 chopin"]]]
+OK
+diff: ["map",[["2 gills","1 chopin"]]]
+apply diff: ["map",[]]
+OK
+diff: ["map",[["2 pints","1 quart"]]]
+apply diff: ["map",[["2 pints","1 quart"]]]
+OK
+diff: ["map",[["2 gills","1 gallon"]]]
+apply diff: ["map",[["2 gills","1 gallon"]]]
+OK]])
+
+OVSDB_CHECK_NEGATIVE([generate and apply diff with map -- size error],
+  [[diff-data '{"key": "string", "value": "string", "min":0, "max": 3}' \
+  '["map", [["2 gills", "1 chopin"]]]' \
+  '["map", [["2 gills", "1 gallon"],
+            ["2 pints", "1 quart"],
+            ["2 quarts", "1 pottle"],
+            ["2 gallons", "1 peck"]]]' \
+  ]],
+  [[ovsdb error: Datum crated by diff has size error]])
diff --git a/tests/test-ovsdb.c b/tests/test-ovsdb.c
index 76c9ad9..0ce8f9d 100644
--- a/tests/test-ovsdb.c
+++ b/tests/test-ovsdb.c
@@ -1,5 +1,5 @@ 
 /*
- * Copyright (c) 2009, 2010, 2011, 2012, 2013 Nicira, Inc.
+ * Copyright (c) 2009, 2010, 2011, 2012, 2013, 2015 Nicira, Inc.
  *
  * Licensed under the Apache License, Version 2.0 (the "License");
  * you may not use this file except in compliance with the License.
@@ -398,6 +398,64 @@  do_default_data(struct ovs_cmdl_context *ctx OVS_UNUSED)
 }
 
 static void
+do_diff_data(struct ovs_cmdl_context *ctx)
+{
+    struct ovsdb_type type;
+    struct json *json;
+    struct ovsdb_datum new, old, diff, reincarnation;
+
+    json = unbox_json(parse_json(ctx->argv[1]));
+    check_ovsdb_error(ovsdb_type_from_json(&type, json));
+    json_destroy(json);
+
+    /* Arguments in pairs of 'old' and 'new'. */
+    for (int i = 2; i < ctx->argc - 1; i+=2) {
+        struct ovsdb_error *error;
+
+        json = unbox_json(parse_json(ctx->argv[i]));
+        check_ovsdb_error(ovsdb_datum_from_json(&old, &type, json, NULL));
+        json_destroy(json);
+
+        json = unbox_json(parse_json(ctx->argv[i+1]));
+        check_ovsdb_error(ovsdb_transient_datum_from_json(&new, &type, json));
+        json_destroy(json);
+
+        /* Generate the diff.  */
+        ovsdb_datum_diff(&diff, &old, &new, &type);
+
+        /* Apply diff to 'old' to create'reincarnation'. */
+        error = ovsdb_datum_apply_diff(&reincarnation, &old, &diff, &type);
+        if (error) {
+            ovs_fatal(0, "%s", ovsdb_error_to_string(error));
+        }
+
+        /* Test to make sure 'new' equals 'reincarnation'.  */
+        if (!ovsdb_datum_equals(&new, &reincarnation, &type)) {
+            ovs_fatal(0, "failed to apply diff");
+        }
+
+        /* Print diff */
+        json = ovsdb_datum_to_json(&diff, &type);
+        printf ("diff: ");
+        print_and_free_json(json);
+
+        /* Print reincarnation */
+        json = ovsdb_datum_to_json(&reincarnation, &type);
+        printf ("apply diff: ");
+        print_and_free_json(json);
+
+        ovsdb_datum_destroy(&new, &type);
+        ovsdb_datum_destroy(&old, &type);
+        ovsdb_datum_destroy(&diff, &type);
+        ovsdb_datum_destroy(&reincarnation, &type);
+
+        printf("OK\n");
+    }
+
+    ovsdb_type_destroy(&type);
+}
+
+static void
 do_parse_atomic_type(struct ovs_cmdl_context *ctx)
 {
     enum ovsdb_atomic_type type;
@@ -2053,6 +2111,7 @@  static struct ovs_cmdl_command all_commands[] = {
     { "log-io", NULL, 2, INT_MAX, do_log_io },
     { "default-atoms", NULL, 0, 0, do_default_atoms },
     { "default-data", NULL, 0, 0, do_default_data },
+    { "diff-data", NULL, 3, INT_MAX, do_diff_data},
     { "parse-atomic-type", NULL, 1, 1, do_parse_atomic_type },
     { "parse-base-type", NULL, 1, 1, do_parse_base_type },
     { "parse-type", NULL, 1, 1, do_parse_type },