[Tarantool-patches] [PATCH v4 07/11] wal: matrix clock structure

Georgy Kirichenko georgy at tarantool.org
Wed Feb 12 12:39:16 MSK 2020


A matrix clock which allows to maintain a set of vclocks and
their components order. The main target is to be able to
build a vclock which contains lsns each one is less or equal
that n corresponding lsn from a matrix clock.

The purpose of the matrix clock is to evaluate a vclock
which is already processed by wal consumers like relays
or to obtain a majority vclock to commit journal entries
in case of synchronous replication.

Part of #980, #3794
---
 src/box/CMakeLists.txt   |   4 +
 src/box/mclock.c         | 374 +++++++++++++++++++++++++++++++++++++++
 src/box/mclock.h         | 125 +++++++++++++
 test/unit/CMakeLists.txt |   2 +
 test/unit/mclock.result  |  18 ++
 test/unit/mclock.test.c  | 160 +++++++++++++++++
 6 files changed, 683 insertions(+)
 create mode 100644 src/box/mclock.c
 create mode 100644 src/box/mclock.h
 create mode 100644 test/unit/mclock.result
 create mode 100644 test/unit/mclock.test.c

diff --git a/src/box/CMakeLists.txt b/src/box/CMakeLists.txt
index 0cc154ba5..32f922dd7 100644
--- a/src/box/CMakeLists.txt
+++ b/src/box/CMakeLists.txt
@@ -32,6 +32,9 @@ target_link_libraries(box_error core stat)
 add_library(vclock STATIC vclock.c)
 target_link_libraries(vclock core)
 
+add_library(mclock STATIC mclock.c)
+target_link_libraries(mclock vclock core)
+
 add_library(xrow STATIC xrow.c iproto_constants.c)
 target_link_libraries(xrow server core small vclock misc box_error
                       scramble ${MSGPUCK_LIBRARIES})
@@ -133,6 +136,7 @@ add_library(box STATIC
     execute.c
     sql_stmt_cache.c
     wal.c
+    mclock.c
     call.c
     merger.c
     ${lua_sources}
diff --git a/src/box/mclock.c b/src/box/mclock.c
new file mode 100644
index 000000000..c05838836
--- /dev/null
+++ b/src/box/mclock.c
@@ -0,0 +1,374 @@
+/*
+ * Copyright 2010-2016, Tarantool AUTHORS, please see AUTHORS file.
+ *
+ * Redistribution and use in source and binary forms, with or
+ * without modification, are permitted provided that the following
+ * conditions are met:
+ *
+ * 1. Redistributions of source code must retain the above
+ *    copyright notice, this list of conditions and the
+ *    following disclaimer.
+ *
+ * 2. Redistributions in binary form must reproduce the above
+ *    copyright notice, this list of conditions and the following
+ *    disclaimer in the documentation and/or other materials
+ *    provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY <COPYRIGHT HOLDER> ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
+ * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
+ * <COPYRIGHT HOLDER> OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
+ * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
+ * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
+ * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF
+ * THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+#include "mclock.h"
+
+void
+mclock_create(struct mclock *mclock)
+{
+	memset(mclock, 0, sizeof(struct mclock));
+}
+
+void
+mclock_destroy(struct mclock *mclock)
+{
+	memset(mclock, 0, sizeof(struct mclock));
+}
+
+/*
+ * Check if passed vclock contain unknown replica
+ * identifiers. In case of new replica identifier
+ * the column map is adjusted and corresponding ordered
+ * array is built. Also new vclock is placed at the first
+ * position in the ordered array because there are no more
+ * non-zero entries in this column.
+ */
+static void
+mclock_adjust_col_map(struct mclock *mclock, uint32_t id,
+		      const struct vclock *vclock)
+{
+	/* Evaluate new matrix column identifiers. */
+	uint32_t new_col_map = vclock->map & ~mclock->col_map;
+	struct bit_iterator col_map_it;
+	bit_iterator_init(&col_map_it, &new_col_map, sizeof(new_col_map), true);
+	for (size_t col_id = bit_iterator_next(&col_map_it); col_id < SIZE_MAX;
+	     col_id = bit_iterator_next(&col_map_it)) {
+		/* Register new replica identifier. */
+		mclock->col_map |= (1 << col_id);
+		struct bit_iterator row_map_it;
+		bit_iterator_init(&row_map_it, &mclock->row_map,
+				  sizeof(mclock->row_map), true);
+		/* Rebuild an order map for given column. */
+		mclock->order[col_id][0] = id;
+		for (size_t row_id = bit_iterator_next(&row_map_it), i = 1;
+		     row_id < SIZE_MAX;
+		     row_id = bit_iterator_next(&row_map_it)) {
+			if (row_id != id)
+				mclock->order[col_id][i++] = row_id;
+		}
+	}
+}
+
+/* Fetches a lsn on given column and position (not row). */
+static inline int64_t
+mclock_get_pos_lsn(const struct mclock *mclock, uint32_t col_id, uint32_t pos)
+{
+	uint32_t row_id = mclock->order[col_id][pos];
+	return vclock_get(mclock->vclock + row_id, col_id);
+}
+
+/*
+ * Locate a range which contains given lsn for given column
+ * identifier. Function return two values by pointer: to and from.
+ * The first one contain the least position which lsn greater or
+ * equal than given lsn, the second one contains the bigger position
+ * which lsn less than the given one. So all lsns on positions
+ * between `*from` and  `*to -1` are equal to given lsn.
+ * For instance if we have lsn array like {12, 10, 10, 7, 6}
+ * then for lsn == 10 we will get *from == 1 and *to == 3
+ * whereas for lsn == 8 the result should be: *from == 3 and *to == 3
+ */
+static inline void
+mclock_find_range(const struct mclock *mclock, uint32_t col_id, int64_t lsn,
+		  uint32_t *from, uint32_t *to)
+{
+	/* Logarithic search, setup initial search ranges. */
+	uint32_t b = *from, e = *to;
+	uint32_t b_to = *from, e_to = *to;
+	/* Look for `from' position. */
+	while (e - b > 1) {
+		uint32_t m = (b + e) / 2;
+		int64_t m_lsn = mclock_get_pos_lsn(mclock, col_id, m);
+		if (m_lsn <= lsn)
+			e = m;
+		else
+			b = m;
+		/*
+		 * Optimization: check if we could decrease
+		 * the `to' search range.
+		 */
+		if (m_lsn < lsn)
+			e_to = MIN(m, e_to);
+		else
+			b_to = MAX(m, b_to);
+	}
+	if (mclock_get_pos_lsn(mclock, col_id, b) > lsn)
+		*from = e;
+	else
+		*from = b;
+	/* Look for `to' position. */
+	while (e_to - b_to > 1) {
+		uint32_t m = (b_to + e_to) / 2;
+		int64_t m_lsn = mclock_get_pos_lsn(mclock, col_id, m);
+		if (m_lsn < lsn)
+			e_to = m;
+		else
+			b_to = m;
+	}
+	*to = e_to;
+}
+
+/*
+ * Shift a sequence between old_pos and new_pos one
+ * step up (new_pos > old_pos, erasing head member)
+ * or down (new_pos < old_pos, erasing tail member).
+ */
+static inline void
+mclock_shift(struct mclock *mclock, uint32_t col_id, uint32_t old_pos,
+	     uint32_t new_pos)
+{
+	if (old_pos > new_pos) {
+		memmove(mclock->order[col_id] + new_pos + 1,
+			mclock->order[col_id] + new_pos,
+			(old_pos - new_pos) * sizeof(**mclock->order));
+	} else if (old_pos < new_pos) {
+		memmove(mclock->order[col_id] + old_pos,
+			mclock->order[col_id] + old_pos + 1,
+			(new_pos - old_pos) * sizeof(**mclock->order));
+	}
+}
+
+/*
+ * Update replica vclock and reorder mclock members.
+ */
+static int
+mclock_update_vclock(struct mclock *mclock, uint32_t id, const struct vclock *vclock)
+{
+	uint32_t count = __builtin_popcount(mclock->row_map);
+	mclock_adjust_col_map(mclock, id, vclock);
+	/* Perform reordering for each column. */
+	struct bit_iterator col_map_it;
+	bit_iterator_init(&col_map_it, &mclock->col_map, sizeof(mclock->col_map), true);
+	for (size_t col_id = bit_iterator_next(&col_map_it); col_id < SIZE_MAX;
+	     col_id = bit_iterator_next(&col_map_it)) {
+		int64_t new_lsn = vclock_get(vclock, col_id);
+		int64_t old_lsn = vclock_get(mclock->vclock + id, col_id);
+
+		if (old_lsn == new_lsn)
+			continue;
+		/*
+		 * Find a positions range which contains given
+		 * replica id for current column (old lsn position).
+		 */
+		uint32_t from = 0, to = count;
+		mclock_find_range(mclock, col_id, old_lsn, &from, &to);
+		assert(to > from);
+		uint32_t old_pos = from, new_pos;
+		while (old_pos < to) {
+			uint32_t replica_id = mclock->order[col_id][old_pos];
+			if (replica_id == id)
+				break;
+			++old_pos;
+		}
+		/* Replica id should be found. */
+		assert(old_pos < to);
+		if (new_lsn == old_lsn) {
+			/*
+			 * Lsn was not changed put replica id on the
+			 * last position in corresponding range.
+			 */
+			new_pos = to - 1;
+		}
+		else if (new_lsn > mclock_get_pos_lsn(mclock, col_id, 0)) {
+			/*
+			 * New lsn is the biggest one so put on
+			 * the first position in a column.
+			 */
+			new_pos = 0;
+		}
+		else if (new_lsn <= mclock_get_pos_lsn(mclock, col_id,
+						       count - 1)) {
+			/* The least one - the last position. */
+			new_pos = count - 1;
+		}
+		else {
+			/* Find a range of position which contains new lsn. */
+			if (new_lsn > old_lsn)
+				from = 0;
+			else
+				to = count;
+			mclock_find_range(mclock, col_id, new_lsn, &from, &to);
+			/* Take care about positions shift - to the
+			 * head or to the tail of column order map.
+			 */
+			new_pos = to - (new_lsn <= old_lsn? 1: 0);
+		}
+		assert(new_pos < count);
+		if (old_pos == new_pos)
+			continue;
+		mclock_shift(mclock, col_id, old_pos, new_pos);
+		mclock->order[col_id][new_pos] = id;
+	}
+	vclock_copy(&mclock->vclock[id], vclock);
+	return 0;
+}
+
+/*
+ * Delete replica vclock.
+ */
+static int
+mclock_delete_vclock(struct mclock *mclock, uint32_t id)
+{
+	uint32_t count = __builtin_popcount(mclock->row_map);
+	/* Perform reordering for each column. */
+	struct bit_iterator col_map_it;
+	bit_iterator_init(&col_map_it, &mclock->col_map, sizeof(mclock->col_map), true);
+	for (size_t col_id = bit_iterator_next(&col_map_it); col_id < SIZE_MAX;
+	     col_id = bit_iterator_next(&col_map_it)) {
+		int64_t old_lsn = vclock_get(mclock->vclock + id, col_id);
+		/*
+		 * Find a positions range which contains given
+		 * replica id for current column (old lsn position).
+		 */
+		uint32_t from = 0, to = count;
+		mclock_find_range(mclock, col_id, old_lsn, &from, &to);
+		assert(to > from);
+		uint32_t old_pos = from, new_pos = count - 1;
+		while (old_pos < to) {
+			uint32_t replica_id = mclock->order[col_id][old_pos];
+			if (replica_id == id)
+				break;
+			++old_pos;
+		}
+		/* Replica id should be found. */
+		assert(old_pos < to);
+		new_pos = count - 1;
+
+		if (old_pos == new_pos)
+			continue;
+		mclock_shift(mclock, col_id, old_pos, new_pos);
+	}
+	mclock->row_map ^= (1 << id);
+	return 0;
+}
+int
+mclock_update(struct mclock *mclock, uint32_t id, const struct vclock *vclock)
+{
+	/*
+	 * The given id is not registered and
+	 * vclock is zero - nothing to do.
+	 */
+	if ((mclock->row_map & (1 << id)) == 0 && vclock_sum(vclock) == 0)
+		return 0;
+	if (vclock_sum(vclock) == 0) {
+		mclock_delete_vclock(mclock, id);
+		return 0;
+	}
+	/*
+	 * The given replica id is not yet attached so
+	 * put a zero vclock on the last position with
+	 * corresponding replica identifier.
+	 */
+	if ((mclock->row_map & (1 << id)) == 0) {
+		vclock_create(&mclock->vclock[id]);
+		/* Put the given vclock at the last position. */
+		mclock->row_map |= 1 << id;
+		uint32_t count = __builtin_popcount(mclock->row_map);
+		struct bit_iterator col_map_it;
+		bit_iterator_init(&col_map_it, &mclock->col_map, sizeof(mclock->col_map), true);
+		for (size_t col_id = bit_iterator_next(&col_map_it); col_id < SIZE_MAX;
+		     col_id = bit_iterator_next(&col_map_it)) {
+			mclock->order[col_id][count - 1] = id;
+		}
+	}
+	mclock_update_vclock(mclock, id, vclock);
+	return 0;
+}
+
+int
+mclock_get(struct mclock *mclock, int32_t offset, struct vclock *vclock)
+{
+	int32_t count = __builtin_popcount(mclock->row_map);
+	/* Check if given offset is out of mclock range. */
+	if (offset >= count || offset < -count) {
+		vclock_create(vclock);
+		return -1;
+	}
+	offset = (offset + count) % count;
+	vclock_create(vclock);
+	/* Fetch lsn for each known replica identifier. */
+	struct bit_iterator col_map_it;
+	bit_iterator_init(&col_map_it, &mclock->col_map, sizeof(mclock->col_map), true);
+	for (size_t col_id = bit_iterator_next(&col_map_it); col_id < SIZE_MAX;
+	     col_id = bit_iterator_next(&col_map_it)) {
+		int64_t lsn = mclock_get_pos_lsn(mclock, col_id, offset);
+		if (lsn > 0)
+			vclock_follow(vclock, col_id, lsn);
+	}
+	return 0;
+}
+
+int
+mclock_extract_row(struct mclock *mclock, uint32_t id, struct vclock *vclock)
+{
+	if (mclock->row_map && (1 << id) == 0) {
+		vclock_create(vclock);
+		return -1;
+	}
+	vclock_copy(vclock, mclock->vclock + id);
+	return 0;
+}
+
+int
+mclock_extract_col(struct mclock *mclock, uint32_t id, struct vclock *vclock)
+{
+	vclock_create(vclock);
+	if (mclock->col_map && (1 << id) == 0)
+		return -1;
+
+	struct bit_iterator row_map_it;
+	bit_iterator_init(&row_map_it, &mclock->row_map,
+			  sizeof(mclock->row_map), true);
+	for (size_t row_id = bit_iterator_next(&row_map_it);
+	     row_id < SIZE_MAX; row_id = bit_iterator_next(&row_map_it)) {
+		int64_t lsn = vclock_get(mclock->vclock + row_id, id);
+		if (lsn == 0)
+			continue;
+		vclock_follow(vclock, row_id, lsn);
+	}
+
+	return 0;
+}
+
+bool
+mclock_check(struct mclock *mclock)
+{
+	uint32_t count = __builtin_popcount(mclock->row_map);
+	struct bit_iterator col_map_it;
+	bit_iterator_init(&col_map_it, &mclock->col_map, sizeof(mclock->col_map), true);
+	for (size_t col_id = bit_iterator_next(&col_map_it); col_id < SIZE_MAX;
+	     col_id = bit_iterator_next(&col_map_it)) {
+		for (uint32_t n = 0; n < count - 1; ++n)
+			if (mclock_get_pos_lsn(mclock, col_id, n) <
+			    mclock_get_pos_lsn(mclock, col_id, n + 1))
+				return false;
+	}
+	return true;
+}
diff --git a/src/box/mclock.h b/src/box/mclock.h
new file mode 100644
index 000000000..759cfda05
--- /dev/null
+++ b/src/box/mclock.h
@@ -0,0 +1,125 @@
+#ifndef INCLUDES_TARANTOOL_MCLOCK_H
+#define INCLUDES_TARANTOOL_MCLOCK_H
+/*
+ * Copyright 2010-2016, Tarantool AUTHORS, please see AUTHORS file.
+ *
+ * Redistribution and use in source and binary forms, with or
+ * without modification, are permitted provided that the following
+ * conditions are met:
+ *
+ * 1. Redistributions of source code must retain the above
+ *    copyright notice, this list of conditions and the
+ *    following disclaimer.
+ *
+ * 2. Redistributions in binary form must reproduce the above
+ *    copyright notice, this list of conditions and the following
+ *    disclaimer in the documentation and/or other materials
+ *    provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY <COPYRIGHT HOLDER> ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
+ * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
+ * <COPYRIGHT HOLDER> OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
+ * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
+ * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
+ * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF
+ * THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+#include <stdlib.h>
+
+#include "vclock.h"
+
+#if defined(__cplusplus)
+extern "C" {
+#endif /* defined(__cplusplus) */
+
+/**
+ * Matrix clock structure contains vclocks identified
+ * by replica identifiers int it rows and maintains
+ * the column order for each known replica identifier.
+ */
+struct mclock {
+	/** Map of attached replica vclocks. */
+	unsigned int row_map;
+	/** Map of known replica identifies. */
+	unsigned int col_map;
+	/**
+	 * Contained vclock array addressable by
+	 * corresponding replica identifier.
+	 */
+	struct vclock vclock[VCLOCK_MAX];
+	/**
+	 * Per column ordered map. Each row describes
+	 * an ordered map of attached replica identifiers
+	 * where the most bigger lsn is on the first position.
+	 * In case of sequence of the equal lsns the latest is
+	 * on the last position in the sequence.
+	 * For instance if we have vclock like:
+	 *  1: {1: 10, 2: 12, 3: 0}
+	 *  2: {1: 10, 2: 14, 3: 1}
+	 *  3: {1: 0, 2: 8, 3: 4}
+	 * The order map will look like:
+	 *  {{1, 2, 3}, {2, 1, 3}, {3, 2, 1}}
+	 */
+	uint8_t order[VCLOCK_MAX][VCLOCK_MAX];
+};
+
+/** Create a mclock structure. */
+void
+mclock_create(struct mclock *mclock);
+
+/** Release allocated resources. */
+void
+mclock_destroy(struct mclock *mclock);
+
+/**
+ * Update a vclock identified by replica id and
+ * sort mclock members.
+ */
+int
+mclock_update(struct mclock *mclock, uint32_t id, const struct vclock *vclock);
+
+/**
+ * Build a vclock each component of which is less or equal than
+ * offset + 1 (or count + offset + 1 if offset < 0) corresponding
+ * component of containing vclocks. So mclock_get(mclock, 0) selects the
+ * biggest lsns for each column.
+ * For instance if we have mclock like:
+ *  1: {1: 10, 2: 12, 3: 0}
+ *  2: {1: 10, 2: 14, 3: 1}
+ *  3: {1: 0, 2: 8, 3: 4}
+ * Then mclock_get(0) builds {1: 10, 2: 14, 3: 4}
+ * whereas  mclock_get(2) build {1: 0, 2: 8, 3: 0}
+ */
+int
+mclock_get(struct mclock *mclock, int32_t offset, struct vclock *vclock);
+
+/**
+ * Fetch a row from a matrix clock.
+ */
+int
+mclock_extract_row(struct mclock *mclock, uint32_t id, struct vclock *vclock);
+
+/**
+ * Extract a column from a matrix clock. Such column describes
+ * the id replica lsn visible by cluster members.
+ */
+int
+mclock_extract_col(struct mclock *mclock, uint32_t id,  struct vclock *vclock);
+
+/*
+ * Function which checks the matrix clock consistence.
+ */
+bool
+mclock_check(struct mclock *mclock);
+
+#if defined(__cplusplus)
+} /* extern "C" */
+#endif /* defined(__cplusplus) */
+
+#endif /* INCLUDES_TARANTOOL_MCLOCK_H */
diff --git a/test/unit/CMakeLists.txt b/test/unit/CMakeLists.txt
index 4a57597e9..40db199e0 100644
--- a/test/unit/CMakeLists.txt
+++ b/test/unit/CMakeLists.txt
@@ -65,6 +65,8 @@ add_executable(bloom.test bloom.cc)
 target_link_libraries(bloom.test salad)
 add_executable(vclock.test vclock.cc)
 target_link_libraries(vclock.test vclock unit)
+add_executable(mclock.test mclock.test.c)
+target_link_libraries(mclock.test mclock vclock bit unit)
 add_executable(xrow.test xrow.cc)
 target_link_libraries(xrow.test xrow unit)
 add_executable(decimal.test decimal.c)
diff --git a/test/unit/mclock.result b/test/unit/mclock.result
new file mode 100644
index 000000000..eb3aa649d
--- /dev/null
+++ b/test/unit/mclock.result
@@ -0,0 +1,18 @@
+1..2
+    1..1
+	*** test_random_stress ***
+    ok 1 - random stress
+	*** test_random_stress: done ***
+ok 1 - subtests
+    1..8
+	*** test_func ***
+    ok 1 - consistency 1
+    ok 2 - first vclock 1
+    ok 3 - last vclock 1
+    ok 4 - second vclock
+    ok 5 - consistency 2
+    ok 6 - consistency 3
+    ok 7 - first vclock - 2
+    ok 8 - last vclock - 2
+	*** test_func: done ***
+ok 2 - subtests
diff --git a/test/unit/mclock.test.c b/test/unit/mclock.test.c
new file mode 100644
index 000000000..cd3a6538e
--- /dev/null
+++ b/test/unit/mclock.test.c
@@ -0,0 +1,160 @@
+/*
+ * Copyright 2010-2015, Tarantool AUTHORS, please see AUTHORS file.
+ *
+ * Redistribution and use in source and binary forms, with or
+ * without modification, are permitted provided that the following
+ * conditions are met:
+ *
+ * 1. Redistributions of source code must retain the above
+ *    copyright notice, this list of conditions and the
+ *    following disclaimer.
+ *
+ * 2. Redistributions in binary form must reproduce the above
+ *    copyright notice, this list of conditions and the following
+ *    disclaimer in the documentation and/or other materials
+ *    provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY <COPYRIGHT HOLDER> ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
+ * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
+ * <COPYRIGHT HOLDER> OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
+ * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
+ * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
+ * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF
+ * THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+#include "unit.h"
+#include <stdarg.h>
+
+#include "box/mclock.h"
+
+static void
+test_random_stress()
+{
+	srand(time(NULL));
+	plan(1);
+	header();
+	struct mclock mclock;
+	mclock_create(&mclock);
+	bool ok = true;
+	for (int i = 0; i < 50000; ++i) {
+		struct vclock vclock;
+		vclock_create(&vclock);
+		uint32_t id = rand() % 31 + 1;
+		/* Count of non-zero items. */
+		int tm = rand() % 31;
+		for (int t = 0; t < tm;) {
+			uint32_t j = rand() % 31 + 1;
+			if (vclock_get(&vclock, j) > 0)
+				continue;
+			vclock_follow(&vclock, j, rand() + 1);
+			++t;
+		}
+		mclock_update(&mclock, id, &vclock);
+		if (!(ok = mclock_check(&mclock)))
+			break;
+	}
+	struct vclock vclock;
+	vclock_create(&vclock);
+	for (int i = 1; i < 32; ++i)
+		mclock_update(&mclock, i, &vclock);
+	mclock_destroy(&mclock);
+	is(ok, true, "random stress");
+	footer();
+	check_plan();
+}
+
+static void
+test_func()
+{
+	plan(8);
+	header();
+	struct mclock mclock;
+	mclock_create(&mclock);
+	struct vclock v1, v2, v3;
+	vclock_create(&v1);
+	vclock_follow(&v1, 1, 11);
+	vclock_follow(&v1, 2, 21);
+	vclock_follow(&v1, 3, 31);
+	vclock_create(&v2);
+	vclock_follow(&v2, 1, 22);
+	vclock_follow(&v2, 2, 12);
+	vclock_follow(&v2, 3, 30);
+	vclock_create(&v3);
+	vclock_follow(&v3, 2, 32);
+	vclock_follow(&v3, 3, 2);
+	vclock_follow(&v3, 4, 5);
+	mclock_update(&mclock, 1, &v1);
+	mclock_update(&mclock, 2, &v2);
+	mclock_update(&mclock, 3, &v3);
+	is(mclock_check(&mclock), true, "consistency 1");
+
+	struct vclock v, t;
+	vclock_create(&t);
+	vclock_follow(&t, 1, 22);
+	vclock_follow(&t, 2, 32);
+	vclock_follow(&t, 3, 31);
+	vclock_follow(&t, 4, 5);
+
+	mclock_get(&mclock, 0, &v);
+	is(vclock_compare(&v, &t), 0, "first vclock 1");
+
+	vclock_create(&t);
+	vclock_follow(&t, 2, 12);
+	vclock_follow(&t, 3, 2);
+
+	mclock_get(&mclock, -1, &v);
+	is(vclock_compare(&v, &t), 0, "last vclock 1");
+
+	vclock_create(&t);
+	vclock_follow(&t, 1, 11);
+	vclock_follow(&t, 2, 21);
+	vclock_follow(&t, 3, 30);
+
+	mclock_get(&mclock, 1, &v);
+	is(vclock_compare(&v, &t), 0, "second vclock");
+
+	vclock_follow(&v1, 1, 40);
+	vclock_follow(&v1, 4, 10);
+	mclock_update(&mclock, 1, &v1);
+	is(mclock_check(&mclock), true, "consistency 2");
+	vclock_follow(&v2, 2, 35);
+	vclock_follow(&v2, 4, 3);
+	mclock_update(&mclock, 2, &v2);
+	is(mclock_check(&mclock), true, "consistency 3");
+
+	vclock_create(&t);
+	vclock_follow(&t, 1, 40);
+	vclock_follow(&t, 2, 35);
+	vclock_follow(&t, 3, 31);
+	vclock_follow(&t, 4, 10);
+
+	mclock_get(&mclock, 0, &v);
+	is(vclock_compare(&v, &t), 0, "first vclock - 2");
+
+	vclock_create(&t);
+	vclock_follow(&t, 2, 21);
+	vclock_follow(&t, 3, 2);
+	vclock_follow(&t, 4, 3);
+
+	mclock_get(&mclock, -1, &v);
+	is(vclock_compare(&v, &t), 0, "last vclock - 2");
+
+	footer();
+	check_plan();
+
+}
+
+int main(void)
+{
+	plan(2);
+	test_random_stress();
+	test_func();
+	check_plan();
+}
+
-- 
2.25.0



More information about the Tarantool-patches mailing list