diff mbox

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

Message ID 1445489131-21483-4-git-send-email-azhou@nicira.com
State Changes Requested
Headers show

Commit Message

Andy Zhou Oct. 22, 2015, 4:45 a.m. UTC 
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
"udpate2" JSON-RPC notification, which encodes modifications
of a column with the contents of those "diff"s. Later patch implements
the "udpate2" notification.

Signed-off-by: Andy Zhou <azhou@nicira.com>
---
 lib/ovsdb-data.c    | 83 +++++++++++++++++++++++++++++++++++++++++++++++++++++
 lib/ovsdb-data.h    | 11 ++++++-
 tests/ovsdb-data.at | 56 ++++++++++++++++++++++++++++++++++++
 tests/test-ovsdb.c  | 50 +++++++++++++++++++++++++++++++-
 4 files changed, 198 insertions(+), 2 deletions(-)

Comments

Ben Pfaff Nov. 10, 2015, 4:57 p.m. UTC | #1 
On Wed, Oct 21, 2015 at 09:45:26PM -0700, Andy Zhou wrote:
> 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
> "udpate2" JSON-RPC notification, which encodes modifications
> of a column with the contents of those "diff"s. Later patch implements
> the "udpate2" notification.

s/udpate2/update2/, in two places above.

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

...

> +/* 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

That's a nice property.  Good thinking, I'm sure I would have missed
that at first.

> + * The generated datum is always safe; the orders of keys are maintained
> + * since they are added in order.
> + *
> + * Caller is responsible for freeing the memory returned.   */

It seems that allocating the ovsdb_datum itself is unusual within the
ovsdb-data.c interface.  It seems that it would be more consistent with
the other functions if the caller had to supply it.

Same for ovsdb_datum_apply_diff().

In the test, it would be a little better, I think, if the new diff test
printed out the difference, so that one could visually see that it made
sense and we would know if anything happened to change.

Thanks,

Ben.
diff mbox

Patch

diff --git a/lib/ovsdb-data.c b/lib/ovsdb-data.c
index 592e9ed..9a71195 100644
--- a/lib/ovsdb-data.c
+++ b/lib/ovsdb-data.c
@@ -1912,6 +1912,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 generated datum is always safe; the orders of keys are maintained
+ * since they are added in order.
+ *
+ * Caller is responsible for freeing the memory returned.   */
+struct ovsdb_datum *
+ovsdb_datum_diff(const struct ovsdb_datum *old,
+                 const struct ovsdb_datum *new,
+                 const struct ovsdb_type *type)
+{
+    struct ovsdb_datum *diff = xmalloc(sizeof *diff);
+    size_t oi, ni;
+
+    ovsdb_datum_init_empty(diff);
+    if (!ovsdb_type_is_composite(type)) {
+        ovsdb_datum_clone(diff, new, type);
+        return diff;
+    }
+
+    /* 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);
+    }
+
+    return diff;
+}
+
+struct ovsdb_datum *
+ovsdb_datum_apply_diff(const struct ovsdb_datum *old,
+                       const struct ovsdb_datum *diff,
+                       const struct ovsdb_type *type)
+{
+    struct ovsdb_datum *new;
+
+    new = ovsdb_datum_diff(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);
+        new = NULL;
+    }
+
+    return new;
+}
+
+
 /* 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..760fddf 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,15 @@  void ovsdb_datum_subtract(struct ovsdb_datum *a,
                           const struct ovsdb_datum *b,
                           const struct ovsdb_type *b_type);
 
+/* Generate and apply diffs */
+struct ovsdb_datum *ovsdb_datum_diff(const struct ovsdb_datum *old,
+                                     const struct ovsdb_datum *new,
+                                     const struct ovsdb_type *type);
+
+struct ovsdb_datum *ovsdb_datum_apply_diff(const struct ovsdb_datum *old,
+                                           const struct ovsdb_datum *diff,
+                                           const struct ovsdb_type *type);
+
 /* 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..abf21d1 100644
--- a/tests/ovsdb-data.at
+++ b/tests/ovsdb-data.at
@@ -783,3 +783,59 @@  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]']],
+  [[OK]])
+
+OVSDB_CHECK_POSITIVE([generate and apply diff -- boolean],
+  [[diff-data '["boolean"]' '[true]' '[false]']],
+  [[OK]])
+
+OVSDB_CHECK_POSITIVE([generate and apply diff -- string],
+  [[diff-data '["string"]' '["AAA"]' '["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", []]'
+  ]],
+  [[OK
+OK
+OK
+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]]']],
+  [[test-ovsdb: failed to apply diff]])
+
+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"]]]' \
+  ]],
+  [[OK
+OK
+OK
+OK
+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"]]]' \
+  ]],
+  [[test-ovsdb: failed to apply diff]])
diff --git a/tests/test-ovsdb.c b/tests/test-ovsdb.c
index 7913763..3e22db9 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.
@@ -385,6 +385,53 @@  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) {
+        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.  */
+        diff = ovsdb_datum_diff(&old, &new, &type);
+        if (!diff) {
+            ovs_fatal(0, "failed to generate diff");
+        }
+
+        /* Apply diff and make sure 'reincarnation' == 'new'. */
+        reincarnation = ovsdb_datum_apply_diff(&old, diff, &type);
+        if (!reincarnation
+            || !ovsdb_datum_equals(&new, reincarnation, &type)) {
+            ovs_fatal(0, "failed to apply diff");
+        }
+
+        ovsdb_datum_destroy(&new, &type);
+        ovsdb_datum_destroy(&old, &type);
+        ovsdb_datum_destroy(diff, &type);
+        free(diff);
+        ovsdb_datum_destroy(reincarnation, &type);
+        free(reincarnation);
+
+        printf("OK\n");
+    }
+
+    ovsdb_type_destroy(&type);
+}
+
+static void
 do_parse_atomic_type(struct ovs_cmdl_context *ctx)
 {
     enum ovsdb_atomic_type type;
@@ -1972,6 +2019,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 },