1 /*  Copyright (C) 2011 CZ.NIC, z.s.p.o. <knot-dns@labs.nic.cz>
2 
3     This program is free software: you can redistribute it and/or modify
4     it under the terms of the GNU General Public License as published by
5     the Free Software Foundation, either version 3 of the License, or
6     (at your option) any later version.
7 
8     This program is distributed in the hope that it will be useful,
9     but WITHOUT ANY WARRANTY; without even the implied warranty of
10     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
11     GNU General Public License for more details.
12 
13     You should have received a copy of the GNU General Public License
14     along with this program.  If not, see <https://www.gnu.org/licenses/>.
15  */
16 
17 #include <stdbool.h>
18 #include <stdio.h>
19 #include <string.h>
20 #include <time.h>
21 #include <unistd.h>
22 #include <tap/basic.h>
23 #include <tap/files.h>
24 
25 #include "contrib/string.h"
26 #include "libknot/libknot.h"
27 #include "contrib/mempattern.h"
28 #include "contrib/openbsd/strlcpy.h"
29 #include "contrib/ucw/mempool.h"
30 
31 /* UCW array sorting defines. */
32 #define ASORT_PREFIX(X) str_key_##X
33 #define ASORT_KEY_TYPE char*
34 #define ASORT_LT(x, y) (strcmp((x), (y)) < 0)
35 #include "contrib/ucw/array-sort.h"
36 
37 /* Constants. */
38 #define KEY_MAXLEN 64
39 #define KEY_SET(key, str) key.data = (str); key.len = strlen(str) + 1
40 
41 /*! \brief Generate random key. */
42 static const char *alphabet = "abcdefghijklmn0123456789";
str_key_rand(size_t len,knot_mm_t * pool)43 static char *str_key_rand(size_t len, knot_mm_t *pool)
44 {
45 	char *s = mm_alloc(pool, len);
46 	memset(s, 0, len);
47 	for (unsigned i = 0; i < len - 1; ++i) {
48 		s[i] = alphabet[rand() % strlen(alphabet)];
49 	}
50 	return s;
51 }
52 
knot_db_test_set(unsigned nkeys,char ** keys,void * opts,const knot_db_api_t * api,knot_mm_t * pool)53 static void knot_db_test_set(unsigned nkeys, char **keys, void *opts,
54                             const knot_db_api_t *api, knot_mm_t *pool)
55 {
56 	if (api == NULL) {
57 		skip("API not compiled in");
58 		return;
59 	}
60 
61 	/* Create database */
62 	knot_db_t *db = NULL;
63 	int ret = api->init(&db, pool, opts);
64 	ok(ret == KNOT_EOK && db != NULL, "%s: create", api->name);
65 
66 	/* Start WR transaction. */
67 	knot_db_txn_t txn;
68 	ret = api->txn_begin(db, &txn, 0);
69 	is_int(KNOT_EOK, ret, "%s: txn_begin(WR)", api->name);
70 
71 	/* Insert keys */
72 	knot_db_val_t key, val;
73 	bool passed = true;
74 	for (unsigned i = 0; i < nkeys; ++i) {
75 		KEY_SET(key, keys[i]);
76 		val.len = sizeof(void*);
77 		val.data = &key.data;
78 
79 		ret = api->insert(&txn, &key, &val, 0);
80 		if (ret != KNOT_EOK && ret != KNOT_EEXIST) {
81 			passed = false;
82 			break;
83 		}
84 	}
85 	ok(passed, "%s: insert", api->name);
86 
87 	/* Commit WR transaction. */
88 	ret = api->txn_commit(&txn);
89 	is_int(KNOT_EOK, ret, "%s: txn_commit(WR)", api->name);
90 
91 	/* Start RD transaction. */
92 	ret = api->txn_begin(db, &txn, KNOT_DB_RDONLY);
93 	is_int(KNOT_EOK, ret, "%s: txn_begin(RD)", api->name);
94 
95 	/* Lookup all keys */
96 	passed = true;
97 	for (unsigned i = 0; i < nkeys; ++i) {
98 		KEY_SET(key, keys[i]);
99 
100 		ret = api->find(&txn, &key, &val, 0);
101 		if (ret != KNOT_EOK) {
102 			passed = false;
103 			break;
104 		}
105 
106 		const char **stored_key = val.data;
107 		if (strcmp(*stored_key, keys[i]) != 0) {
108 			diag("%s: mismatch on element '%u'", api->name, i);
109 			passed = false;
110 			break;
111 		}
112 	}
113 	ok(passed, "%s: lookup all keys", api->name);
114 
115 	/* Fetch dataset size. */
116 	int db_size = api->count(&txn);
117 	ok(db_size > 0 && db_size <= nkeys, "%s: count %d", api->name, db_size);
118 
119 	/* Unsorted iteration */
120 	int iterated = 0;
121 	knot_db_iter_t *it = api->iter_begin(&txn, 0);
122 	while (it != NULL) {
123 		++iterated;
124 		it = api->iter_next(it);
125 	}
126 	api->iter_finish(it);
127 	is_int(db_size, iterated, "%s: unsorted iteration", api->name);
128 
129 	/* Sorted iteration. */
130 	char first_key[KEY_MAXLEN] = { '\0' };
131 	char second_key[KEY_MAXLEN] = { '\0' };
132 	char last_key[KEY_MAXLEN] = { '\0' };
133 	char key_buf[KEY_MAXLEN] = {'\0'};
134 	iterated = 0;
135 	memset(&key, 0, sizeof(key));
136 	it = api->iter_begin(&txn, KNOT_DB_SORTED);
137 	while (it != NULL) {
138 		api->iter_key(it, &key);
139 		if (iterated > 0) { /* Only if previous exists. */
140 			if (strcmp(key_buf, key.data) > 0) {
141 				diag("%s: iter_sort '%s' <= '%s' FAIL\n",
142 				     api->name, key_buf, (const char *)key.data);
143 				break;
144 			}
145 			if (iterated == 1) {
146 				memcpy(second_key, key.data, key.len);
147 			}
148 		} else {
149 			memcpy(first_key, key.data, key.len);
150 		}
151 		++iterated;
152 		memcpy(key_buf, key.data, key.len);
153 		it = api->iter_next(it);
154 	}
155 	strlcpy(last_key, key_buf, sizeof(last_key));
156 	is_int(db_size, iterated, "%s: sorted iteration", api->name);
157 	api->iter_finish(it);
158 
159 	/* Interactive iteration. */
160 	it = api->iter_begin(&txn, KNOT_DB_NOOP);
161 	if (it != NULL) { /* If supported. */
162 		ret = 0;
163 		/* Check if first and last keys are reachable */
164 		it = api->iter_seek(it, NULL, KNOT_DB_FIRST);
165 		ret += api->iter_key(it, &key);
166 		is_string(first_key, key.data, "%s: iter_set(FIRST)", api->name);
167 		/* Check left/right iteration. */
168 		it = api->iter_seek(it, &key, KNOT_DB_NEXT);
169 		ret += api->iter_key(it, &key);
170 		is_string(second_key, key.data, "%s: iter_set(NEXT)", api->name);
171 		it = api->iter_seek(it, &key, KNOT_DB_PREV);
172 		ret += api->iter_key(it, &key);
173 		is_string(first_key, key.data, "%s: iter_set(PREV)", api->name);
174 		it = api->iter_seek(it, &key, KNOT_DB_LAST);
175 		ret += api->iter_key(it, &key);
176 		is_string(last_key, key.data, "%s: iter_set(LAST)", api->name);
177 		/* Check if prev(last_key + 1) is the last_key */
178 		strlcpy(key_buf, last_key, sizeof(key_buf));
179 		key_buf[0] += 1;
180 		KEY_SET(key, key_buf);
181 		it = api->iter_seek(it, &key, KNOT_DB_LEQ);
182 		ret += api->iter_key(it, &key);
183 		is_string(last_key, key.data, "%s: iter_set(LEQ)", api->name);
184 		/* Check if next(first_key - 1) is the first_key */
185 		strlcpy(key_buf, first_key, sizeof(key_buf));
186 		key_buf[0] -= 1;
187 		KEY_SET(key, key_buf);
188 		it = api->iter_seek(it, &key, KNOT_DB_GEQ);
189 		ret += api->iter_key(it, &key);
190 		is_string(first_key, key.data, "%s: iter_set(GEQ)", api->name);
191 		api->iter_finish(it);
192 		is_int(ret, 0, "%s: iter_* error codes", api->name);
193 	}
194 	api->txn_abort(&txn);
195 
196 	/* Deleting during iteration. */
197 	const uint8_t DEL_MAX_CNT = 3;
198 	api->txn_begin(db, &txn, 0);
199 	api->clear(&txn);
200 	for (uint8_t i = 0; i < DEL_MAX_CNT; ++i) {
201 		key.data = &i;
202 		key.len = sizeof(i);
203 		val.data = NULL;
204 		val.len = 0;
205 
206 		ret = api->insert(&txn, &key, &val, 0);
207 		is_int(KNOT_EOK, ret, "%s: add key '%u'", api->name, i);
208 	}
209 	it = api->iter_begin(&txn, KNOT_DB_NOOP);
210 	if (it != NULL) { /* If supported. */
211 		is_int(DEL_MAX_CNT, api->count(&txn), "%s: key count before", api->name);
212 		it = api->iter_seek(it, NULL, KNOT_DB_FIRST);
213 		uint8_t pos = 0;
214 		while (it != NULL) {
215 			ret = api->iter_key(it, &key);
216 			is_int(KNOT_EOK, ret, "%s: iter key before del", api->name);
217 			is_int(pos, ((uint8_t *)(key.data))[0], "%s: iter compare key '%u'",
218 			       api->name, pos);
219 
220 			ret = knot_db_lmdb_iter_del(it);
221 			is_int(KNOT_EOK, ret, "%s: iter del", api->name);
222 
223 			it = api->iter_next(it);
224 
225 			ret = api->iter_key(it, &key);
226 			if (++pos < DEL_MAX_CNT) {
227 				is_int(KNOT_EOK, ret, "%s: iter key after del", api->name);
228 				is_int(pos, ((uint8_t *)key.data)[0], "%s: iter compare key '%u",
229 				       api->name, pos);
230 			} else {
231 				is_int(KNOT_EINVAL, ret, "%s: iter key after del", api->name);
232 			}
233 		}
234 		api->iter_finish(it);
235 		is_int(0, api->count(&txn), "%s: key count after", api->name);
236 	}
237 	api->txn_abort(&txn);
238 
239 	/* Clear database and recheck. */
240 	ret =  api->txn_begin(db, &txn, 0);
241 	ret += api->clear(&txn);
242 	ret += api->txn_commit(&txn);
243 	is_int(0, ret, "%s: clear()", api->name);
244 
245 	/* Check if the database is empty. */
246 	api->txn_begin(db, &txn, KNOT_DB_RDONLY);
247 	db_size = api->count(&txn);
248 	is_int(0, db_size, "%s: count after clear = %d", api->name, db_size);
249 	api->txn_abort(&txn);
250 
251 	api->deinit(db);
252 }
253 
main(int argc,char * argv[])254 int main(int argc, char *argv[])
255 {
256 	plan_lazy();
257 
258 	knot_mm_t pool;
259 	mm_ctx_mempool(&pool, MM_DEFAULT_BLKSIZE);
260 
261 	char *dbid = test_mkdtemp();
262 	ok(dbid != NULL, "make temporary directory");
263 
264 	/* Random keys. */
265 	unsigned nkeys = 10000;
266 	char **keys = mm_alloc(&pool, sizeof(char*) * nkeys);
267 	for (unsigned i = 0; i < nkeys; ++i) {
268 		keys[i] = str_key_rand(KEY_MAXLEN, &pool);
269 	}
270 
271 	/* Sort random keys. */
272 	str_key_sort(keys, nkeys);
273 
274 	/* Execute test set for all backends. */
275 	struct knot_db_lmdb_opts lmdb_opts = KNOT_DB_LMDB_OPTS_INITIALIZER;
276 	lmdb_opts.path = dbid;
277 	struct knot_db_trie_opts trie_opts = KNOT_DB_TRIE_OPTS_INITIALIZER;
278 	knot_db_test_set(nkeys, keys, &lmdb_opts, knot_db_lmdb_api(), &pool);
279 	knot_db_test_set(nkeys, keys, &trie_opts, knot_db_trie_api(), &pool);
280 
281 	/* Cleanup. */
282 	mp_delete(pool.ctx);
283 	test_rm_rf(dbid);
284 	free(dbid);
285 
286 	return 0;
287 }
288