summaryrefslogtreecommitdiffstats
path: root/tests/contrib/test_qp-cow.c
diff options
context:
space:
mode:
Diffstat (limited to 'tests/contrib/test_qp-cow.c')
-rw-r--r--tests/contrib/test_qp-cow.c282
1 files changed, 282 insertions, 0 deletions
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. <knot-dns@labs.nic.cz>
+ Copyright (C) 2018 Tony Finch <dot@dotat.at>
+
+ 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 <https://www.gnu.org/licenses/>.
+ */
+
+#include <assert.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <time.h>
+#include <err.h>
+#include <unistd.h>
+
+#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;
+}
generated by cgit v1.2.3 (git 2.39.1) at 2024-05-02 18:43:06 +0000