From patchwork Thu Jan 18 05:05:08 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Sam Mendoza-Jonas X-Patchwork-Id: 862759 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from lists.ozlabs.org (lists.ozlabs.org [IPv6:2401:3900:2:1::3]) (using TLSv1.2 with cipher ADH-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 3zMXFC5lGgz9t1t for ; Thu, 18 Jan 2018 16:14:23 +1100 (AEDT) Authentication-Results: ozlabs.org; dkim=fail reason="signature verification failed" (2048-bit key; unprotected) header.d=mendozajonas.com header.i=@mendozajonas.com header.b="PE5yVQAh"; dkim=fail reason="signature verification failed" (2048-bit key; unprotected) header.d=messagingengine.com header.i=@messagingengine.com header.b="TZbnEFYl"; dkim-atps=neutral Received: from lists.ozlabs.org (lists.ozlabs.org [IPv6:2401:3900:2:1::3]) by lists.ozlabs.org (Postfix) with ESMTP id 3zMXFC4DNKzF0VQ for ; Thu, 18 Jan 2018 16:14:23 +1100 (AEDT) Authentication-Results: lists.ozlabs.org; dkim=fail reason="signature verification failed" (2048-bit key; unprotected) header.d=mendozajonas.com header.i=@mendozajonas.com header.b="PE5yVQAh"; dkim=fail reason="signature verification failed" (2048-bit key; unprotected) header.d=messagingengine.com header.i=@messagingengine.com header.b="TZbnEFYl"; dkim-atps=neutral X-Original-To: petitboot@lists.ozlabs.org Delivered-To: petitboot@lists.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (mailfrom) smtp.mailfrom=mendozajonas.com (client-ip=66.111.4.25; helo=out1-smtp.messagingengine.com; envelope-from=sam@mendozajonas.com; receiver=) Authentication-Results: lists.ozlabs.org; dkim=pass (2048-bit key; unprotected) header.d=mendozajonas.com header.i=@mendozajonas.com header.b="PE5yVQAh"; dkim=pass (2048-bit key; unprotected) header.d=messagingengine.com header.i=@messagingengine.com header.b="TZbnEFYl"; dkim-atps=neutral Received: from out1-smtp.messagingengine.com (out1-smtp.messagingengine.com [66.111.4.25]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by lists.ozlabs.org (Postfix) with ESMTPS id 3zMXCg0Bk7zF0hV for ; Thu, 18 Jan 2018 16:13:02 +1100 (AEDT) Received: from compute2.internal (compute2.nyi.internal [10.202.2.42]) by mailout.nyi.internal (Postfix) with ESMTP id A95D420F62; Thu, 18 Jan 2018 00:05:35 -0500 (EST) Received: from frontend2 ([10.202.2.161]) by compute2.internal (MEProxy); Thu, 18 Jan 2018 00:05:35 -0500 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= mendozajonas.com; h=cc:date:from:in-reply-to:message-id :references:subject:to:x-me-sender:x-me-sender:x-sasl-enc; s= fm1; bh=YOEyNuAQy/hx6pIjHY5+e8QGSvBtgwuuUKRql6hqgO4=; b=PE5yVQAh rMtPo9aUUv2JhbF10TaWd00eJIX0rshYTevkg8PFZmcrS99Vt4veeG3OgMspP84F Avn4gynD/Ej3Sa4cfd0s9YmNpHUtYozmtB5MxvjqagioFTdYYmcWERFIogeKBrjm IPVG9KLTVVycWbdbkdQwLvWIhuttyHq3g7epajdQ3sxvZ56hkciv6akUHYD+Oz5F FNCAAJi6V4++4YAzTS4oxaChdo0t3+4pQIxUEDAjmSP8dBu90GbKExGO/Wif17RM jY1eL4H/B4v1mVZoQxQO9BUukH9UMxWBxvjuG2UxyOAATRiFJ4RS/u7n/aLxef0f OL6NzXq8RRN3OQ== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=cc:date:from:in-reply-to:message-id :references:subject:to:x-me-sender:x-me-sender:x-sasl-enc; s= fm1; bh=YOEyNuAQy/hx6pIjHY5+e8QGSvBtgwuuUKRql6hqgO4=; b=TZbnEFYl LKol/1v63QQSsrgU8ApIzmjV9OoNodH5sZhuHFjaIpbXrY2x1z554hrZelo/nzX4 G5ADxk5DTxkDa05T1PWwofpfw1YlB6JL/8HSC4/TS1De/I2EqEib3W6YJr6wtje1 5Hb+Gnx6Nrqr+S1S6e6I+DMMkj121BF64X9R1jQvbbadDlSe4ZRMH3+nCZmQHHzC vrgILGYm/uUIqlnWEKK27t6Cb7D7PI+atS0bqKYMqVi83arWUAYSlBsFcUqz+i3k HZkyMGCZ1jE4fRuoCVJ+BIefCTt6xNiveeuLsuccmtp5dkTnWWNhtTWCgE9A8Pzt DkpmsVkBRGTJBQ== X-ME-Sender: Received: from v4.ozlabs.ibm.com (unknown [122.99.82.10]) by mail.messagingengine.com (Postfix) with ESMTPA id 4B8FF240F8; Thu, 18 Jan 2018 00:05:34 -0500 (EST) From: Samuel Mendoza-Jonas To: petitboot@lists.ozlabs.org Subject: [[RFC PATCH] v2 05/14] lib/version: Version parsing and comparison Date: Thu, 18 Jan 2018 16:05:08 +1100 Message-Id: <20180118050517.2442-6-sam@mendozajonas.com> X-Mailer: git-send-email 2.15.1 In-Reply-To: <20180118050517.2442-1-sam@mendozajonas.com> References: <20180118050517.2442-1-sam@mendozajonas.com> X-BeenThere: petitboot@lists.ozlabs.org X-Mailman-Version: 2.1.24 Precedence: list List-Id: Petitboot bootloader development List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Cc: Samuel Mendoza-Jonas MIME-Version: 1.0 Errors-To: petitboot-bounces+incoming=patchwork.ozlabs.org@lists.ozlabs.org Sender: "Petitboot" Skiboot defines a versioning scheme [0] to interpret version strings read from the the VERSION MTD partition or the device tree on OpenPOWER platforms. 'lib/version' implements this scheme and allows Petitboot to compare two sets of package version strings and determine which is newer. [0] https://github.com/open-power/skiboot/blob/master/doc/device-tree/ibm,firmware-versions.rst Signed-off-by: Samuel Mendoza-Jonas --- lib/Makefile.am | 2 + lib/version/version.c | 422 ++++++++++++++++++++++++++++++++++++++++ lib/version/version.h | 31 +++ test/lib/Makefile.am | 3 +- test/lib/test-version-parsing.c | 104 ++++++++++ 5 files changed, 561 insertions(+), 1 deletion(-) create mode 100644 lib/version/version.c create mode 100644 lib/version/version.h create mode 100644 test/lib/test-version-parsing.c diff --git a/lib/Makefile.am b/lib/Makefile.am index bb7dfe4..6915314 100644 --- a/lib/Makefile.am +++ b/lib/Makefile.am @@ -58,6 +58,8 @@ lib_libpbcore_la_SOURCES = \ lib/util/util.h \ lib/flash/config.h \ lib/flash/flash.h \ + lib/version/version.c \ + lib/version/version.h \ $(gpg_int_SOURCES) if ENABLE_MTD diff --git a/lib/version/version.c b/lib/version/version.c new file mode 100644 index 0000000..0f23c64 --- /dev/null +++ b/lib/version/version.c @@ -0,0 +1,422 @@ +/* + * Copyright (C) 2017 IBM Corporation + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; version 2 of the License. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +#include +#include +#include +#include +#include +#include + +#include "version.h" + +static int get_epoch(void *ctx, char *version, char **pos) +{ + char *c, *tmp; + int result; + + *pos = version; + + c = strchr(version, ':'); + if (!c) + return 0; + + tmp = talloc_strndup(ctx, version, c - version + 1); + if (!tmp) + return -1; + + *pos = c + 1; + result = strtoul(tmp, NULL, 10); + + talloc_free(tmp); + return result; +} + +static bool is_numeric(const char *s) +{ + unsigned int i; + + for (i = 0; i < strlen(s); i++) + if (!isdigit(s[i])) + return false; + + return true; +} + +enum character_order { + CLASS_TILDE = 0, + CLASS_ALPHA = 1, + CLASS_NONALPHA = 2, +}; + +static enum character_order lexical_class(char c) +{ + if (c == '~') + return CLASS_TILDE; + if (isalpha(c)) + return CLASS_ALPHA; + return CLASS_NONALPHA; +} + +/* + * Compare two version strings. A negative result means v2 is 'less' than v1, + * a positive result means v2 is 'greater' than v1, and 0 means the two + * versions are equal + */ +static int compare_string(const char *v1, const char *v2) +{ + enum character_order class1, class2; + unsigned int i; + + for (i = 0; i < strlen(v1) && i < strlen(v2); i++) { + if (v1[i] == v2[i]) + continue; + + class1 = lexical_class(v1[i]); + class2 = lexical_class(v2[i]); + + if (class1 == class2) + return v2[i] - v1[i]; + else + return class2 - class1; + } + + /* Either equal or different length strings */ + return strlen(v2) > strlen(v1); +} + +/* + * Compare two individual version string fields. These are assumed NOT to + * include a leading 'v', separating '-' characters, or the '~' character. + * */ +static int compare_numeric_fields(char *v1, char *v2) +{ + char *ltok, *rtok, *lsaveptr, *rsaveptr; + + ltok = strtok_r(v1, ".", &lsaveptr); + rtok = strtok_r(v2, ".", &rsaveptr); + + while (ltok && rtok) { + int l, r, cmp; + + if (is_numeric(ltok) && is_numeric(rtok)) { + /* Actual version numbers */ + l = strtoul(ltok, NULL, 10); + r = strtoul(rtok, NULL, 10); + if (r - l) + return r - l; + } else { + /* Compare as strings */ + cmp = compare_string(ltok, rtok); + pb_log("compare .: %s vs %s gave %d\n", ltok, rtok, cmp); + if (cmp) + return cmp; + } + + ltok = strtok_r(NULL, ".", &lsaveptr); + rtok = strtok_r(NULL, ".", &rsaveptr); + } + + /* Is one version longer than the other? */ + if (ltok && !rtok) + return -1; + if (!ltok && rtok) + return 1; + + /* Equal */ + return 0; +} + +static int tilde_check(const char *tilde1, const char *tilde2) +{ + if (!tilde1 && !tilde2) + return 0; + + /* vx.y~anything sorts older than vx.y */ + if (tilde1 && !tilde2) + return 1; + if (tilde2 && !tilde1) + return -1; + + return compare_string(tilde1, tilde2); +} + +/* + * Skip any leading description from the version string. + * "The version string may include a description at the start of it. This + * description can contain any set of characters but **must not** contain + * a '-' followed by a digit. It also **must not** contain '-v' or '-V' followed + * by a digit." + */ +const char *skip_description(const char *str) +{ + const char *version_start = str; + + while (version_start && *version_start != '\0') { + int len = strlen(version_start); + if (isdigit(*version_start)) + return version_start; + if (*version_start == '-') { + if (len < 2) + return NULL; + if (isdigit(*(version_start + 1))) + return version_start + 1; + if (*(version_start + 1) == 'v' || + *(version_start + 1) == 'V' ) + if (isdigit(*(version_start + 2))) + return version_start + 1; + } + if ((*version_start == 'v' || *version_start == 'V') && + isdigit(*(version_start + 1))) + return version_start; + version_start++; + } + + pb_debug("version looks like all description\n"); + return NULL; +} + +/* + * Compare two version strings, returning true if the 'remote' version is newer. + * This follows the version semantics described in the Skiboot firmware-versions + * document: + * https://github.com/open-power/skiboot/blob/master/doc/device-tree/ibm,firmware-versions.rst + * In short this compares each version string field by field, and breaks on the + * first difference, eg. + * v1.14-46 + * sorts newer than + * v1.14-45-g78d89280c3f9-dirty + */ +bool compare_version(void *ctx, const char *current, const char *new) +{ + int epoch_current, epoch_new; + char *pos_l = NULL, *pos_r = NULL; + char *ltok, *rtok, *lsaveptr = NULL, *rsaveptr = NULL, *ldot, *rdot; + char *v1, *v2; + bool result = false; + + if (!current || !new) + return false; + + v1 = talloc_strdup(ctx, skip_description(current)); + v2 = talloc_strdup(ctx, skip_description(new)); + + if (!v1 || !v2) + goto out; + + /* Check first whether either version has a non-zero epoch */ + epoch_current = get_epoch(ctx, v1, &pos_l); + epoch_new = get_epoch(ctx, v2, &pos_r); + + if (epoch_current < 0 || epoch_new < 0) { + pb_log("Error parsing epoch from version\n"); + goto out; + } + + if (!pos_l || !pos_r) { + pb_log("Could not parse version after epoch\n"); + goto out; + } + + if (epoch_current != epoch_new) { + result = epoch_new > epoch_current; + goto out; + } + + /* Get the first hypen-separated field from each version */ + ltok = strtok_r(pos_l, "-", &lsaveptr); + rtok = strtok_r(pos_r, "-", &rsaveptr); + + if (!ltok || !rtok) { + result = compare_string(pos_l, pos_r) > 0; + goto out; + } + + /* The first field may have a leading 'v' character */ + if (ltok[0] == 'v' || ltok[0] == 'V') + ltok++; + if (rtok[0] == 'v' || rtok[0] == 'V') + rtok++; + + /* Handle all non-leading-numeric parts, and watch out for git (-g) and + * patch (-p) strings */ + while (ltok && rtok) { + char *ltilde, *rtilde; + int cmp; + + /* Check for tildes first and process at end */ + if ((ltilde = strchr(ltok, '~')) != NULL) + *ltilde++ = '\0'; + if ((rtilde = strchr(rtok, '~')) != NULL) + *rtilde++ = '\0'; + + + if ((ltok[0] == 'p' && rtok[0] == 'p') || + (ltok[0] == 'g' && rtok[0] == 'g')) { + /* Newer on any difference */ + cmp = strncmp(ltok, rtok, strlen(ltok)); + if (!cmp) + cmp = tilde_check(ltilde, rtilde); + if (cmp) { + result = true; + break; + } + } else if (ltok[0] == 'p' || rtok[0] == 'p' || + ltok[0] == 'g' || rtok[0] == 'g') { + if (ltok[0] == 'g' && rtok[0] != 'g') + result = true; + else if (ltok[0] != 'g' && rtok[0] == 'g') + result = false; + else if (ltok[0] == 'p' && rtok[0] != 'p') + result = true; + else if (ltok[0] != 'p' && rtok[0] == 'p') + result = false; + break; + } + + ldot = strchr(ltok, '.'); + rdot = strchr(rtok, '.'); + + /* Too different to really compare, assume newer version */ + if ((rdot && !ldot) || (!rdot && ldot)) { + pb_log("Current and new version strings appear to have different formats\n"); + result = true; + break; + } + + if (rdot && ldot) + cmp = compare_numeric_fields(ltok, rtok); + else + cmp = compare_string(ltok, rtok); + + if (!cmp) + cmp = tilde_check(ltilde, rtilde); + + if (cmp) { + result = cmp > 0; + break; + } + + ltok = strtok_r(NULL, "-", &lsaveptr); + rtok = strtok_r(NULL, "-", &rsaveptr); + } + + /* Is one version longer than the other? */ + if ((ltok && !rtok) || (!ltok && rtok)) + result = rtok && !ltok; + +out: + talloc_free(v1); + talloc_free(v2); + + return result; +} + +/* Construct an array of firmware_version structs from a provided buffer. + * If the buffer also contains a url to an update binary, return that as well */ +unsigned int parse_metadata(void *ctx, char *buf, int len, + struct firmware_version **versions, char **update_source) +{ + struct firmware_version *tmp = NULL; + unsigned int n_versions = 0; + char *tok, *saveptr = NULL, *name_sep; + char *update_tmp = NULL; + + tok = strtok_r(buf, "\n", &saveptr); + if (!tok) { + pb_log("Failed to parse metadata\n"); + return 0; + } + + while (tok && tok < buf + len) { + char *pair = talloc_strdup(ctx, tok); + name_sep = strchr(pair, '\t'); + if (!name_sep) { + /* Try spaces */ + name_sep = strchr(pair, ' '); + if (!name_sep) { + pb_log("Metadata format unknown\n"); + break; + } + } + *name_sep++ = '\0'; + + /* Skip all consectutive additional whitespace */ + while (*name_sep == '\t' || *name_sep == ' ') + name_sep++; + + if (strncmp(pair, "update_file", strlen("update_file")) == 0) { + /* pull out the temp update source */ + update_tmp = talloc_strdup(ctx, name_sep); + tok = strtok_r(NULL, "\n", &saveptr); + continue; + } + + tmp = talloc_realloc(ctx, tmp, struct firmware_version, n_versions + 1); + if (!tmp) { + pb_log("Got lost when parsing metadata\n"); + n_versions = 0; + break; + } + + tmp[n_versions].name = talloc_strdup(tmp, pair); + tmp[n_versions].version = talloc_strdup(tmp, name_sep); + n_versions++; + + tok = strtok_r(NULL, "\n", &saveptr); + } + + *update_source = update_tmp; + *versions = tmp; + + return n_versions; +} + +bool compare_metadata_versions(void *ctx, struct firmware_version *current, + unsigned int n_current, struct firmware_version *new, + unsigned int n_new) +{ + bool update = false; + unsigned int i, j; + + if (!current || !new) { + pb_log("%s: Missing version information\n", __func__); + return false; + } + + /* Why do people keep making me do string manipulation in C */ + for (i = 0; i < n_current; i++) { + for (j = 0; j < n_new; j++) { + if (strncmp(current[i].name, new[j].name, + strlen(current[i].name)) == 0) + break; + } + if (j >= n_new) { + /* Didn't find a match */ + continue; + } + + /* Compare current[i] against new[j] */ + if (compare_version(ctx, current[i].version, new[j].version)) { + pb_log("versions: %s version newer: %s\n", + new[j].name, new[j].version); + update = true; + } + } + + return update; +} diff --git a/lib/version/version.h b/lib/version/version.h new file mode 100644 index 0000000..b11a980 --- /dev/null +++ b/lib/version/version.h @@ -0,0 +1,31 @@ +/* + * Copyright (C) 2017 IBM Corporation + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; version 2 of the License. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +#ifndef VERSION_H +#define VERSION_H + +#include + +unsigned int parse_metadata(void *ctx, char *buf, int len, + struct firmware_version **versions, char **update_source); +const char *skip_description(const char *str); +bool compare_version(void *ctx, const char *current, const char *new); +bool compare_metadata_versions(void *ctx, struct firmware_version *current, + unsigned int n_current, struct firmware_version *new, + unsigned int n_new); + +#endif /* VERSION_H */ diff --git a/test/lib/Makefile.am b/test/lib/Makefile.am index 9636b08..ce92636 100644 --- a/test/lib/Makefile.am +++ b/test/lib/Makefile.am @@ -23,7 +23,8 @@ lib_TESTS = \ test/lib/test-process-parent-stdout \ test/lib/test-process-both \ test/lib/test-process-stdout-eintr \ - test/lib/test-fold + test/lib/test-fold \ + test/lib/test-version-parsing $(lib_TESTS): LIBS += $(core_lib) diff --git a/test/lib/test-version-parsing.c b/test/lib/test-version-parsing.c new file mode 100644 index 0000000..8458e0d --- /dev/null +++ b/test/lib/test-version-parsing.c @@ -0,0 +1,104 @@ + +#include +#include +#include +#include + +#include +#include +#include + +char *versions_a[] = { + "1.14-45-g78d89280c3f9-dirty", + "1.14-45-g78d89280c3f9-dirty", + "1.14-45-g78d89280c3f9-dirty", + "1.14-45-g78d89280c3f9-dirty", + "1.14-45-g78d89280c3f9-dirty", + "1.14-45-g78d89280c3f9-dirty", + "1.0", + "1.0.1", + "1.0", + "1.0", + + "1.0", + "1.0-g1234~bar" +}; + +char *versions_b[] = { + "1.14-45-g78d89280c3f9-dirty", + "1.14-45-g78d89280c3f9", + "1.14-45-g123456789abc", + "1.14-46", + "1.15", + "1:1.0", + "1.0~daily20170201", + "1.0~daily20170201", + "1.0.1", + "1.0beta", + + "1.0~foo", + "1.0-g1234" +}; + +bool expected[] = { + false, + false, + true, + true, + true, + true, + false, + false, + true, + true, + + false, + true +}; + +char *descriptions[3][2] = { + {"foo-bar-v1.2", "v1.2"}, + {"v1.2", "v1.2"}, + {"1.14-45-g78d89280c3f9-dirty", "1.14-45-g78d89280c3f9-dirty"} +}; + +int main(void) +{ + void *ctx; + + size_t alen, blen, expected_len, desc_len, i; + bool result; + + alen = sizeof(versions_a) / sizeof(versions_a[0]); + blen = sizeof(versions_b) / sizeof(versions_b[0]); + desc_len = sizeof(descriptions) / sizeof(descriptions[0]); + expected_len = sizeof(expected) / sizeof(expected[0]); + + assert((alen == blen) & (alen == expected_len)); + + ctx = talloc_new(NULL); + + for (i = 0; i < desc_len; i++) { + result = strncmp(skip_description(descriptions[i][0]), + descriptions[i][1], strlen(descriptions[i][1])) == 0; + printf("%s -> %s: %s\n", + descriptions[i][0], descriptions[i][1], + result ? "PASS" : "FAIL"); + if (!result) + printf("\tGot %s\n", skip_description(descriptions[i][0])); + assert(result); + } + + + for (i = 0; i < alen; i++) { + result = compare_version(ctx, versions_a[i], versions_b[i]); + printf("%s < %s: %s (%s)\n", versions_a[i], versions_b[i], + result ? "true" : "false", + result == expected[i] ? "PASS" : "FAIL"); + assert(result == expected[i]); + } + + talloc_free(ctx); + + return EXIT_SUCCESS; +}