From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp15.mail.ru (smtp15.mail.ru [94.100.176.133]) (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 844C3469719 for ; Wed, 18 Mar 2020 22:48:25 +0300 (MSK) From: Serge Petrenko Date: Wed, 18 Mar 2020 22:47:44 +0300 Message-Id: <680467d22cb2864fb4c2d18ac33c4cccb272ebbb.1584558067.git.sergepetrenko@tarantool.org> In-Reply-To: References: MIME-Version: 1.0 Content-Transfer-Encoding: 8bit Subject: [Tarantool-patches] [PATCH v2 1/5] box: introduce matrix clock List-Id: Tarantool development patches List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , To: v.shpilevoy@tarantool.org, kostja.osipov@gmail.com, georgy@tarantool.org Cc: tarantool-patches@dev.tarantool.org From: Georgy Kirichenko 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 ``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 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 ``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) */ + +/** + * 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 ``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.21.1 (Apple Git-122.3)