[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