[05/10] lib/version: Version parsing and comparison

Message ID 20170825055940.24134-6-sam@mendozajonas.com
State New
Headers show

Commit Message

Samuel Mendoza-Jonas Aug. 25, 2017, 5:59 a.m.
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@mendozajonas.com>
---
 lib/Makefile.am                 |   2 +
 lib/version/version.c           | 417 ++++++++++++++++++++++++++++++++++++++++
 lib/version/version.h           |  31 +++
 test/lib/Makefile.am            |   3 +-
 test/lib/test-version-parsing.c | 104 ++++++++++
 5 files changed, 556 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

Patch

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..688d675
--- /dev/null
+++ b/lib/version/version.c
@@ -0,0 +1,417 @@ 
+/*
+ *  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) {
+			pb_log("Metadata format unknown\n");
+			break;
+		}
+		*name_sep++ = '\0';
+
+		/* Skip all consectutive additional tabs */
+		while (*name_sep == '\t')
+			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;
+}