[[RFC PATCH] v2 05/14] lib/version: Version parsing and comparison
Samuel Mendoza-Jonas
sam at mendozajonas.com
Thu Jan 18 16:05:08 AEDT 2018
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 <sam at mendozajonas.com>
---
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 <ctype.h>
+#include <talloc/talloc.h>
+#include <log/log.h>
+#include <string.h>
+#include <stdlib.h>
+#include <stdio.h>
+
+#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 <types/types.h>
+
+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 <stdlib.h>
+#include <string.h>
+#include <assert.h>
+#include <stdbool.h>
+
+#include <version/version.h>
+#include <waiter/waiter.h>
+#include <talloc/talloc.h>
+
+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;
+}
--
2.15.1
More information about the Petitboot
mailing list