From patchwork Thu Oct 22 04:45:26 2015 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Andy Zhou X-Patchwork-Id: 534201 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from archives.nicira.com (unknown [IPv6:2600:3c00::f03c:91ff:fe6e:bdf7]) by ozlabs.org (Postfix) with ESMTP id 1879A140157 for ; Thu, 22 Oct 2015 15:46:08 +1100 (AEDT) Authentication-Results: ozlabs.org; dkim=fail reason="signature verification failed" (2048-bit key; unprotected) header.d=nicira_com.20150623.gappssmtp.com header.i=@nicira_com.20150623.gappssmtp.com header.b=sRtIojRH; dkim-atps=neutral Received: from archives.nicira.com (localhost [127.0.0.1]) by archives.nicira.com (Postfix) with ESMTP id D3C631076C; Wed, 21 Oct 2015 21:45:49 -0700 (PDT) X-Original-To: dev@openvswitch.org Delivered-To: dev@openvswitch.org Received: from mx3v1.cudamail.com (mx3.cudamail.com [64.34.241.5]) by archives.nicira.com (Postfix) with ESMTPS id 86EC810763 for ; Wed, 21 Oct 2015 21:45:48 -0700 (PDT) Received: from bar3.cudamail.com (bar1 [192.168.15.1]) by mx3v1.cudamail.com (Postfix) with ESMTP id 11386618217 for ; Wed, 21 Oct 2015 22:45:48 -0600 (MDT) X-ASG-Debug-ID: 1445489147-03dd7b106c1aca20001-byXFYA Received: from mx3-pf3.cudamail.com ([192.168.14.3]) by bar3.cudamail.com with ESMTP id GH1aBL60GJkV2mho (version=TLSv1 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO) for ; Wed, 21 Oct 2015 22:45:47 -0600 (MDT) X-Barracuda-Envelope-From: azhou@nicira.com X-Barracuda-RBL-Trusted-Forwarder: 192.168.14.3 Received: from unknown (HELO mail-wi0-f170.google.com) (209.85.212.170) by mx3-pf3.cudamail.com with ESMTPS (RC4-SHA encrypted); 22 Oct 2015 04:45:46 -0000 Received-SPF: unknown (mx3-pf3.cudamail.com: Multiple SPF records returned) X-Barracuda-Apparent-Source-IP: 209.85.212.170 X-Barracuda-RBL-IP: 209.85.212.170 Received: by wicfv8 with SMTP id fv8so102719982wic.0 for ; Wed, 21 Oct 2015 21:45:45 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=nicira_com.20150623.gappssmtp.com; s=20150623; h=from:to:cc:subject:date:message-id:in-reply-to:references; bh=MNzeFBGpNSG7nqA43Y4LF2mjuxWRu78H0xkucd6cR/0=; b=sRtIojRHFqAHylGtuG+JfZvMVVx9hdpnnl9vexBX4ciLDiRBvutvxQH/yIxfhSfhgf Rz3uj2haI7mq4DkCj7t3y+P6nNX8Fa30Sprijn0733YIabNHY+jJZKnDUKV4IeVlMYB2 BO0Q9bvLyg7ppXWJWfTFu0ynqB2gsO1uQb0ZTHOr4in215EIWmInObaHRa3ixqSj6zgn ipwLjUYj7asgA+jT8AIciAMLPmwEnyOlrKr7YFJIBOSRaQ1luqqyqZTzgsPQUdbw09gX UY04DhIC1srp0M1JkBLy0QObiozPL5jzJhME4FpbdTGjT4MoxGIRpnopC3BBFRJgi0VI SwVg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references; bh=MNzeFBGpNSG7nqA43Y4LF2mjuxWRu78H0xkucd6cR/0=; b=HYekcERThW+kmmPw3dPqjziS7fPF1njkiDaZ76oyiU8PsSrcVwQYgh1LIq2J4jPgCx 0u2JO1rosH1obam/SyQm0E9syRMPaYTHITdP13F3fElnYF3ryi1v0Wk/piHDMFBcOlpR lQjsGEBBl7ABOmTnW2xUUjsR2Bwhylcix3QURgryNbGNtynjdRk+JBUG5IO9HZoucwwZ +6AcT1NfPrgURdsA4kwWB4HVhwJ7PwpqZp5mLVJaYpY28mUbv83TF2omYD2hl1W8cZDW JmnaIBBOcFlFvR7dXADXYGRDZxaTwLbyHGY4KJD05N4Zd8hNp6uLTmk6pVHtB1VNzc5B hL/Q== X-Gm-Message-State: ALoCoQkPa4q9ojZYl3D3KMahGH1fycdv2hxrqyj7atvpLPZn+xgpMbiBJQhqAGwwIGuuOL64+ovw X-Received: by 10.180.240.169 with SMTP id wb9mr39470655wic.88.1445489145335; Wed, 21 Oct 2015 21:45:45 -0700 (PDT) Received: from ubuntu.localdomain ([208.91.1.34]) by smtp.gmail.com with ESMTPSA id s16sm26389112wik.16.2015.10.21.21.45.43 (version=TLSv1.2 cipher=ECDHE-RSA-AES128-SHA bits=128/128); Wed, 21 Oct 2015 21:45:44 -0700 (PDT) X-CudaMail-Envelope-Sender: azhou@nicira.com From: Andy Zhou To: dev@openvswitch.org X-CudaMail-Whitelist-To: dev@openvswitch.org X-CudaMail-MID: CM-V3-1020077423 X-CudaMail-DTE: 102115 X-CudaMail-Originating-IP: 209.85.212.170 Date: Wed, 21 Oct 2015 21:45:26 -0700 X-ASG-Orig-Subj: [##CM-V3-1020077423##][mointor2 4/9] lib: add diff and apply diff APIs for ovsdb_datum Message-Id: <1445489131-21483-4-git-send-email-azhou@nicira.com> X-Mailer: git-send-email 1.9.1 In-Reply-To: <1445489131-21483-1-git-send-email-azhou@nicira.com> References: <1445489131-21483-1-git-send-email-azhou@nicira.com> X-Barracuda-Connect: UNKNOWN[192.168.14.3] X-Barracuda-Start-Time: 1445489147 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] [mointor2 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" 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 --- 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(-) 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 },