[Tarantool-patches] [PATCH v2 1/5] box: introduce matrix clock
Serge Petrenko
sergepetrenko at tarantool.org
Wed Mar 18 22:47:44 MSK 2020
From: Georgy Kirichenko <georgy at tarantool.org>
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.
@sergepetrenko: refactoring & rewrite comments to doxygen style.
Part of #980, #3794
Prerequisite #4114
---
src/box/CMakeLists.txt | 4 +
src/box/mclock.c | 394 +++++++++++++++++++++++++++++++++++++++
src/box/mclock.h | 151 +++++++++++++++
src/box/wal.c | 1 -
test/unit/CMakeLists.txt | 2 +
test/unit/mclock.result | 18 ++
test/unit/mclock.test.c | 160 ++++++++++++++++
7 files changed, 729 insertions(+), 1 deletion(-)
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 56758bd2f..cbffab046 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})
@@ -134,6 +137,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..de4ca2a08
--- /dev/null
+++ b/src/box/mclock.c
@@ -0,0 +1,394 @@
+/*
+ * Copyright 2010-2020, 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 whether vclock contains any ids unknown to the matrix
+ * clock and initialize the corresponding column, if it does.
+ *
+ * @param mclock Matrix clock.
+ * @param id the replica id vector clock comes from.
+ * @param vclock Vector clock.
+ */
+static void
+mclock_adjust_col_map(struct mclock *mclock, uint32_t id,
+ const struct vclock *vclock)
+{
+ assert(id < VCLOCK_MAX);
+ /* 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 < VCLOCK_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);
+ /* Buuild 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 < VCLOCK_MAX;
+ row_id = bit_iterator_next(&row_map_it)) {
+ if (row_id != id)
+ mclock->order[col_id][i++] = row_id;
+ }
+ }
+}
+
+/**
+ * Fetch the n-th largest lsn for the given replica id from the
+ * matrix clock.
+ *
+ * @param mclock Matrix clock.
+ * @param col_id Replica id to fetch lsn for.
+ * @param pos The position of desired lsn in ordered array.
+ *
+ * @return An lsn from the \a pos position in the ordered array
+ * corresponding to \a col_id.
+ */
+static inline int64_t
+mclock_get_pos_lsn(const struct mclock *mclock, uint32_t col_id, uint32_t pos)
+{
+ assert(col_id < VCLOCK_MAX);
+ assert(pos < VCLOCK_MAX);
+ uint32_t row_id = mclock->order[col_id][pos];
+ return vclock_get(mclock->vclock + row_id, col_id);
+}
+
+/**
+ * Search the ordered array corresponding to the given replica id
+ * for the range which contains entries with given lsn.
+ *
+ * @param mclock Matrix clock.
+ * @param col_id Replica id to perform search for.
+ * @param lsn Lsn to match.
+ * @param[in,out] from The beginning of the found range.
+ * @param[in,out] to The end of the found range.
+ */
+static inline void
+mclock_find_range(const struct mclock *mclock, uint32_t col_id, int64_t lsn,
+ uint32_t *from, uint32_t *to)
+{
+ /* Setup initial search ranges for the binary search. */
+ uint32_t from_lo = *from, from_hi = *to;
+ uint32_t to_lo = *from, to_hi = *to;
+ /* Look for `from' position. */
+ while (from_hi - from_lo > 1) {
+ uint32_t mid = (from_lo + from_hi) / 2;
+ int64_t mid_lsn = mclock_get_pos_lsn(mclock, col_id, mid);
+ if (mid_lsn <= lsn)
+ from_hi = mid;
+ else
+ from_lo = mid;
+ /*
+ * Optimization: check if we could decrease
+ * the `to' search range.
+ */
+ if (mid_lsn < lsn)
+ to_hi = MIN(mid, to_hi);
+ else
+ to_lo = MAX(mid, to_lo);
+ }
+ if (mclock_get_pos_lsn(mclock, col_id, from_lo) > lsn)
+ *from = from_hi;
+ else
+ *from = from_lo;
+ /* Look for `to' position. */
+ while (to_hi - to_lo > 1) {
+ uint32_t mid = (to_lo + to_hi) / 2;
+ int64_t mid_lsn = mclock_get_pos_lsn(mclock, col_id, mid);
+ if (mid_lsn < lsn)
+ to_hi = mid;
+ else
+ to_lo = mid;
+ }
+ *to = to_hi;
+}
+
+/**
+ * Make space for an array element being moved from \a old_pos
+ * to \a new pos. In order to do so, shift all array members
+ * between old pos and new pos in the direction of \a old_pos,
+ * effectively making space for the element at \a new_pos and
+ * rewriting it at \a old_pos at the same time.
+ *
+ * @param mclock Matrix clock.
+ * @param col_id The column id to shift.
+ * @param old_pos The previous position of the array element
+ * being moved.
+ * @param new_pos Desired position of the array element being
+ * moved.
+ */
+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.
+ *
+ * @param mclock Matrix clock.
+ * @param id Replica id whose vclock to update.
+ * @param vclock Vector clock.
+ */
+static void
+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 < VCLOCK_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 > 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);
+ }
+
+ 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);
+}
+
+/**
+ * Delete the vclock coming from a replica with given id.
+ *
+ * @param mclock Matrix clock.
+ * @param id Replica id whose vclock to remove.
+ */
+static void
+mclock_delete_vclock(struct mclock *mclock, uint32_t id)
+{
+ assert((mclock->row_map & (1 << id)) != 0);
+ 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 < VCLOCK_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);
+}
+
+void
+mclock_update(struct mclock *mclock, uint32_t id, const struct vclock *vclock)
+{
+ /* Vclock is zero - delete the corresponding entry. */
+ if (vclock_sum(vclock) == 0) {
+ if ((mclock->row_map & (1 << id)) != 0)
+ mclock_delete_vclock(mclock, id);
+ return;
+ }
+ /*
+ * 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]);
+ 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 < VCLOCK_MAX;
+ col_id = bit_iterator_next(&col_map_it)) {
+ mclock->order[col_id][count - 1] = id;
+ }
+ }
+ mclock_update_vclock(mclock, id, vclock);
+}
+
+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 < VCLOCK_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_get_row(struct mclock *mclock, uint32_t id, struct vclock *vclock)
+{
+ if (mclock->row_map && (1 << id) == 0)
+ return -1;
+ vclock_copy(vclock, mclock->vclock + id);
+ return 0;
+}
+
+int
+mclock_get_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 < VCLOCK_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 < VCLOCK_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..fb734a6d5
--- /dev/null
+++ b/src/box/mclock.h
@@ -0,0 +1,151 @@
+#ifndef INCLUDES_TARANTOOL_MCLOCK_H
+#define INCLUDES_TARANTOOL_MCLOCK_H
+/*
+ * Copyright 2010-2020, 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) */
+
+/**
+ * The matrix clock structure contains vclocks as seen by
+ * cluster members.
+ */
+struct mclock {
+ /** A bit map containing row ids present in the mclock. */
+ uint32_t row_map;
+ /**
+ * A bit map ofd component ids set in any of the
+ * contained vclocks.
+ */
+ uint32_t col_map;
+ /**
+ * An array of vclocks indexed by replica ids.
+ */
+ struct vclock vclock[VCLOCK_MAX];
+ /**
+ * Per column ordered map. Each row describes an ordered
+ * map of attached replica identifiers where the biggest
+ * 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 the following vclocks:
+ * 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 as follows:
+ * {{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);
+
+/** Reset mclock. */
+void
+mclock_destroy(struct mclock *mclock);
+
+/**
+ * Update a vclock identified by replica id and
+ * sort mclock members.
+ */
+void
+mclock_update(struct mclock *mclock, uint32_t id, const struct vclock *vclock);
+
+/**
+ * Build a vclock each component of which is less than or equal
+ * to offset + 1 (or count + offset + 1 if offset < 0)
+ * corresponding components of contained vclocks.
+ * So mclock_get(mclock, 0) selects the biggest lsns for each
+ * column and mclock_get(-1) will select the smallest lsns for
+ * each column.
+ * For instance if we have mclock with the following vclocks:
+ * 1: {1: 10, 2: 12, 3: 0}
+ * 2: {1: 10, 2: 14, 3: 1}
+ * 3: {1: 0, 2: 8, 3: 4}
+ * mclock_get(0) will build vclock {1: 10, 2: 14, 3: 4}
+ * whereas mclock_get(2) build {1: 0, 2: 8, 3: 0}
+ *
+ * @param mclock Matrix clock.
+ * @param offset The count of components which are greater than
+ * the output vclock.
+ *
+ * @return A vclock whose each component is less than or equal to
+ * offset + 1 other vclocks' components.
+ */
+int
+mclock_get(struct mclock *mclock, int32_t offset, struct vclock *vclock);
+
+/**
+ * Get a vclock corresponding to the given replica id.
+ *
+ * @param mclock Matrix clock.
+ * @param id Replica id.
+ * @param[out] vclock Found vclock.
+ *
+ * @return 0 vclock was found
+ * -1 vclock corresponding to \a id isn't in mclock.
+ */
+int
+mclock_get_row(struct mclock *mclock, uint32_t id, struct vclock *vclock);
+
+/**
+ * Fetch a column from a matrix clock. Such column describes
+ * the id replica lsn visible by cluster members.
+ *
+ * Get a column from the matrix clock. The column contains the
+ * vclock components corresponding to the given id as seen by
+ * cluster members.
+ *
+ * @param mclock Matrix clock.
+ * @param id Replica id indicating vclock component to fetch.
+ * @param[out] vclock Found column.
+ *
+ * @return 0 the column was found
+ * -1 the corresponding column isn't in mclock.
+ */
+int
+mclock_get_col(struct mclock *mclock, uint32_t id, struct vclock *vclock);
+
+/** Check the mclock integrity. */
+bool
+mclock_check(struct mclock *mclock);
+
+#if defined(__cplusplus)
+} /* extern "C" */
+#endif /* defined(__cplusplus) */
+
+#endif /* INCLUDES_TARANTOOL_MCLOCK_H */
diff --git a/src/box/wal.c b/src/box/wal.c
index 1668c9348..ecbe0919e 100644
--- a/src/box/wal.c
+++ b/src/box/wal.c
@@ -1429,7 +1429,6 @@ wal_notify_watchers(struct wal_writer *writer, unsigned events)
wal_watcher_notify(watcher, events);
}
-
/**
* After fork, the WAL writer thread disappears.
* Make sure that atexit() handlers in the child do
diff --git a/test/unit/CMakeLists.txt b/test/unit/CMakeLists.txt
index 4ac08de8d..dd3e5f0c3 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..675cbeee3
--- /dev/null
+++ b/test/unit/mclock.test.c
@@ -0,0 +1,160 @@
+/*
+ * Copyright 2010-2020, 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.21.1 (Apple Git-122.3)
More information about the Tarantool-patches
mailing list