From patchwork Tue Nov 24 22:16:01 2015 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Andy Zhou X-Patchwork-Id: 548315 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from archives.nicira.com (li376-54.members.linode.com [96.126.127.54]) by ozlabs.org (Postfix) with ESMTP id 3C10F1402BB for ; Wed, 25 Nov 2015 09:16:41 +1100 (AEDT) Received: from archives.nicira.com (localhost [127.0.0.1]) by archives.nicira.com (Postfix) with ESMTP id E3D2710A24; Tue, 24 Nov 2015 14:16:30 -0800 (PST) X-Original-To: dev@openvswitch.org Delivered-To: dev@openvswitch.org Received: from mx3v3.cudamail.com (mx3.cudamail.com [64.34.241.5]) by archives.nicira.com (Postfix) with ESMTPS id 3B1F610A11 for ; Tue, 24 Nov 2015 14:16:28 -0800 (PST) Received: from bar3.cudamail.com (localhost [127.0.0.1]) by mx3v3.cudamail.com (Postfix) with ESMTPS id C653016108E for ; Tue, 24 Nov 2015 15:16:27 -0700 (MST) X-ASG-Debug-ID: 1448403387-03dd7b4644350d70001-byXFYA Received: from mx3-pf1.cudamail.com ([192.168.14.2]) by bar3.cudamail.com with ESMTP id lrpocbezaSaWZSHN (version=TLSv1 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO) for ; Tue, 24 Nov 2015 15:16:27 -0700 (MST) X-Barracuda-Envelope-From: azhou.ovn@gmail.com X-Barracuda-RBL-Trusted-Forwarder: 192.168.14.2 Received: from unknown (HELO mail-pa0-f54.google.com) (209.85.220.54) by mx3-pf1.cudamail.com with ESMTPS (RC4-SHA encrypted); 24 Nov 2015 22:16:27 -0000 Received-SPF: pass (mx3-pf1.cudamail.com: SPF record at _netblocks.google.com designates 209.85.220.54 as permitted sender) X-Barracuda-RBL-Trusted-Forwarder: 209.85.220.54 Received: by pacdm15 with SMTP id dm15so34868449pac.3 for ; Tue, 24 Nov 2015 14:16:25 -0800 (PST) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=from:to:cc:subject:date:message-id:in-reply-to:references; bh=r55vgS9BdkuUIQ0SUA9udQ89ck+UIyVSYKnoLAfDmrA=; b=gKy4+iK4AiBbOQN853AcTg9ghuPBGZyU47bgiPRTRmmlZVfh1BM7juUv0jOIsteR3C TXU2UhzC7A5QnEvE/fr21aXhIMg/Iq94vf5Q6IJAlQNvLpGOiGrkvoTKEDwwp+YNYm3k J38eefqC6MA/l3Mpvg6TNac+d1Eq7uLn9bMYmhUQH86IMm8KhPvvCYLddFXf4j5YABjb 5dMHgJCzCH9X3d3lVhixSCngH/NQpGSxjw5Y6iqXkN6ISM8MujFtscgDllPsbi3lTbR8 kv2WE8Y3byUcV3y3CB9STXsCdmba6ODRUKQ7mh+7r32n623ttxblGMzTnQm/UvH3BWdU 4UTg== X-Received: by 10.98.71.138 with SMTP id p10mr26469531pfi.61.1448403385597; Tue, 24 Nov 2015 14:16:25 -0800 (PST) Received: from ubuntu.localdomain ([208.91.1.34]) by smtp.gmail.com with ESMTPSA id b15sm16374570pfj.7.2015.11.24.14.16.24 (version=TLS1_2 cipher=ECDHE-RSA-AES128-SHA bits=128/128); Tue, 24 Nov 2015 14:16:24 -0800 (PST) X-CudaMail-Envelope-Sender: azhou.ovn@gmail.com X-Barracuda-Apparent-Source-IP: 208.91.1.34 From: Andy Zhou To: dev@openvswitch.org X-CudaMail-Whitelist-To: dev@openvswitch.org X-CudaMail-MID: CM-V1-1123060751 X-CudaMail-DTE: 112415 X-CudaMail-Originating-IP: 209.85.220.54 Date: Tue, 24 Nov 2015 14:16:01 -0800 X-ASG-Orig-Subj: [##CM-V1-1123060751##][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> X-Mailer: git-send-email 1.9.1 In-Reply-To: <1448403366-21460-1-git-send-email-azhou@ovn.org> References: <1448403366-21460-1-git-send-email-azhou@ovn.org> X-Barracuda-Connect: UNKNOWN[192.168.14.2] X-Barracuda-Start-Time: 1448403387 X-Barracuda-Encrypted: DHE-RSA-AES256-SHA X-Barracuda-URL: https://web.cudamail.com:443/cgi-mod/mark.cgi X-ASG-Whitelist: Header =?UTF-8?B?eFwtY3VkYW1haWxcLXdoaXRlbGlzdFwtdG8=?= X-Virus-Scanned: by bsmtpd at cudamail.com X-Barracuda-BRTS-Status: 1 Subject: [ovs-dev] [monitor2 v2 4/9] lib: add diff and apply diff APIs for ovsdb_datum X-BeenThere: dev@openvswitch.org X-Mailman-Version: 2.1.16 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , MIME-Version: 1.0 Errors-To: dev-bounces@openvswitch.org Sender: "dev" From: Andy Zhou 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 Acked-by: Ben Pfaff --- 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(-) 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 },