From f449f278dd3c70e479a035f50a9bb817a9b433ba Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Sun, 7 Apr 2024 17:24:08 +0200 Subject: Adding upstream version 3.2.6. Signed-off-by: Daniel Baumann --- tests/contrib/test_qp-cow.c | 282 ++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 282 insertions(+) create mode 100644 tests/contrib/test_qp-cow.c (limited to 'tests/contrib/test_qp-cow.c') diff --git a/tests/contrib/test_qp-cow.c b/tests/contrib/test_qp-cow.c new file mode 100644 index 0000000..4cd8c6c --- /dev/null +++ b/tests/contrib/test_qp-cow.c @@ -0,0 +1,282 @@ +/* Copyright (C) 2021 CZ.NIC, z.s.p.o. + Copyright (C) 2018 Tony Finch + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see . + */ + +#include +#include +#include +#include +#include +#include +#include + +#include "contrib/qp-trie/trie.h" +#include "contrib/string.h" +#include "libknot/attribute.h" +#include "libknot/errcode.h" +#include "tap/basic.h" + +/* Constants. */ +#define MAX_KEYLEN 64 +#define MAX_LEAVES 12345 +#define MAX_MUTATIONS 123 +#define MAX_TRANSACTIONS 1234 + +enum cowstate { + cow_absent, // not in trie + cow_unmarked, + cow_shared, + cow_old, // deleted from new trie + cow_new, // added to new trie + deadbeef, +}; + +struct cowleaf { + char *key; + size_t len; + int cowstate; +}; + +static inline size_t +prng(size_t max) { + /* good enough these days */ + return (size_t)rand() % max; +} + +static struct cowleaf * +grow_leaves(size_t maxlen, size_t leaves) +{ + struct cowleaf *leaf = bcalloc(leaves, sizeof(*leaf)); + + trie_t *trie = trie_create(NULL); + if (!trie) sysbail("trie_create"); + + for (size_t i = 0; i < leaves; i++) { + trie_val_t *valp; + char *str = NULL; + size_t len = 0; + do { + free(str); + len = prng(maxlen); + str = bmalloc(len + 1); + for (size_t j = 0; j < len; j++) + str[j] = "0123456789" + "ABCDEFGHIJKLMNOPQRSTUVWXYZ" + "abcdefghijklmnopqrstuvwxyz" + [prng(62)]; + str[len] = '\0'; + valp = trie_get_ins(trie, (uint8_t *)str, (uint32_t)len); + if (!valp) bail("trie_get_ins"); + } while (*valp != NULL); + *valp = &leaf[i]; + leaf[i].key = str; + leaf[i].len = len; + leaf[i].cowstate = cow_absent; + } + trie_free(trie); + + return (leaf); +} + +static void +dead_leaves(struct cowleaf *leaf, size_t leaves) +{ + for (size_t i = 0; i < leaves; i++) + free(leaf[i].key); + free(leaf); +} + +static void +mark_cb(trie_val_t val, const uint8_t *key, size_t len, void *d) +{ + struct cowleaf *leaf = val; + assert(leaf->cowstate == cow_unmarked && + "leaf should go from unmarked to shared exactly once"); + leaf->cowstate = cow_shared; + (void)key; + (void)len; + (void)d; +} + +static void +commit_rollback(trie_val_t val, const uint8_t *key, size_t len, void *d) +{ + struct cowleaf *leaf = val; + int *commit = d; + if (*commit) + assert((leaf->cowstate == cow_shared || + leaf->cowstate == cow_old) && + "committing deletes from old trie"); + else + assert((leaf->cowstate == cow_shared || + leaf->cowstate == cow_new) && + "roll back deletes from new trie"); + if (leaf->cowstate != cow_shared) + leaf->cowstate = deadbeef; + (void)key; + (void)len; +} + +static void +del_cow(trie_cow_t *x, struct cowleaf *leaf) +{ + _unused_ trie_val_t val; + assert(KNOT_EOK == trie_del_cow(x, + (uint8_t *)leaf->key, + (uint32_t)leaf->len, + &val)); + assert(val == leaf); +} + +static void +usage(void) { + fprintf(stderr, + "usage: test_qp-cow [-k N] [-l N] [-t N]\n" + " -k N maximum key length (default %d)\n" + " -l N number of leaves (default %d)\n" + " -m N mutations per transaction (default %d)\n" + " -t N number of transactions (default %d)\n", + MAX_KEYLEN, + MAX_LEAVES, + MAX_MUTATIONS, + MAX_TRANSACTIONS); + exit(1); +} + +int +main(int argc, char *argv[]) +{ + size_t keylen = MAX_KEYLEN; + size_t leaves = MAX_LEAVES; + int mutations = MAX_MUTATIONS; + int transactions = MAX_TRANSACTIONS; + + int opt; + while ((opt = getopt(argc, argv, "k:l:m:t:h")) != -1) + switch (opt) { + case('k'): + keylen = (unsigned)atoi(optarg); + continue; + case('l'): + leaves = (unsigned)atoi(optarg); + continue; + case('m'): + mutations = atoi(optarg); + continue; + case('t'): + transactions = atoi(optarg); + continue; + default: + usage(); + } + + if (argc != optind) + usage(); + + plan(transactions); + + struct cowleaf *leaf = grow_leaves(keylen, leaves); + trie_t *t = trie_create(NULL); + + for (int round = 0; round < transactions; round++) { + trie_cow_t *x = trie_cow(t, mark_cb, NULL); + if (!x) sysbail("trie_cow"); + + int hits = prng(mutations); + for (int hit = 0; hit < hits; hit++) { + size_t i = prng(leaves); + switch (leaf[i].cowstate) { + case(cow_absent): { + trie_val_t *val = + trie_get_cow(x, + (uint8_t *)leaf[i].key, + (uint32_t)leaf[i].len); + if (!val) sysbail("trie_get_cow"); + assert(*val == NULL && "new leaf"); + *val = &leaf[i]; + leaf[i].cowstate = cow_new; + } break; + case(cow_unmarked): { + del_cow(x, &leaf[i]); + assert(leaf[i].cowstate == cow_shared && + "state changed unmarked -> shared"); + leaf[i].cowstate = cow_old; + } break; + case(cow_shared): { + del_cow(x, &leaf[i]); + assert(leaf[i].cowstate == cow_shared && + "state remained shared"); + leaf[i].cowstate = cow_old; + } break; + case(cow_new): { + del_cow(x, &leaf[i]); + assert(leaf[i].cowstate == cow_new && + "state remained new"); + leaf[i].cowstate = cow_absent; + } break; + case(cow_old): { + // don't want to mess with old tree + } break; + case(deadbeef): { + assert(!"deadbeef should not be possible"); + } break; + default: + assert(!"bug - unhandled state"); + } + } + + int commit = !prng(2); + if (commit) + t = trie_cow_commit(x, commit_rollback, &commit); + else + t = trie_cow_rollback(x, commit_rollback, &commit); + + trie_it_t *it = trie_it_begin(t); + while (!trie_it_finished(it)) { + trie_val_t *val = trie_it_val(it); + assert(val != NULL); + struct cowleaf *l = *val; + if (commit) + assert((l->cowstate == cow_unmarked || + l->cowstate == cow_shared || + l->cowstate == cow_new) && + "committing expected state"); + else + assert((l->cowstate == cow_unmarked || + l->cowstate == cow_shared || + l->cowstate == cow_old) && + "roll back expected state"); + l->cowstate = cow_unmarked; + trie_it_next(it); + } + trie_it_free(it); + + for (size_t i = 0; i < leaves; i++) { + assert((leaf[i].cowstate == cow_unmarked || + leaf[i].cowstate == cow_absent || + leaf[i].cowstate == deadbeef) && + "cleanup leaves either unmarked or dead"); + if (leaf[i].cowstate == deadbeef) + leaf[i].cowstate = cow_absent; + } + ok(1, "transaction done"); + } + + trie_free(t); + dead_leaves(leaf, leaves); + + return 0; +} -- cgit v1.2.3