From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp33.i.mail.ru (smtp33.i.mail.ru [94.100.177.93]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by dev.tarantool.org (Postfix) with ESMTPS id 3A54D4696CA for ; Wed, 12 Feb 2020 12:39:26 +0300 (MSK) From: Georgy Kirichenko Date: Wed, 12 Feb 2020 12:39:16 +0300 Message-Id: In-Reply-To: References: MIME-Version: 1.0 Content-Transfer-Encoding: 8bit Subject: [Tarantool-patches] [PATCH v4 07/11] wal: matrix clock structure List-Id: Tarantool development patches List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , To: tarantool-patches@dev.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. 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 ``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 + * 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 ``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 + * 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 + +#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 ``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 + * 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 + +#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