1 /* -*- mode: C++; c-basic-offset: 4; indent-tabs-mode: nil -*- */
2 // vim: ft=cpp:expandtab:ts=8:sw=4:softtabstop=4:
3 #ident "$Id$"
4 /*======
5 This file is part of PerconaFT.
6
7
8 Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved.
9
10 PerconaFT is free software: you can redistribute it and/or modify
11 it under the terms of the GNU General Public License, version 2,
12 as published by the Free Software Foundation.
13
14 PerconaFT is distributed in the hope that it will be useful,
15 but WITHOUT ANY WARRANTY; without even the implied warranty of
16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 GNU General Public License for more details.
18
19 You should have received a copy of the GNU General Public License
20 along with PerconaFT. If not, see <http://www.gnu.org/licenses/>.
21
22 ----------------------------------------
23
24 PerconaFT is free software: you can redistribute it and/or modify
25 it under the terms of the GNU Affero General Public License, version 3,
26 as published by the Free Software Foundation.
27
28 PerconaFT is distributed in the hope that it will be useful,
29 but WITHOUT ANY WARRANTY; without even the implied warranty of
30 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
31 GNU Affero General Public License for more details.
32
33 You should have received a copy of the GNU Affero General Public License
34 along with PerconaFT. If not, see <http://www.gnu.org/licenses/>.
35 ======= */
36
37 #ident "Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved."
38
39 /**
40 * Test that various queries behave correctly
41 *
42 * Zardosht says:
43 *
44 * write a test that inserts a bunch of elements into the tree,
45 * and then verify that the following types of queries work:
46 * - db->get
47 * - next
48 * - prev
49 * - set_range
50 * - set_range_reverse
51 * - first
52 * - last
53 * - current
54 *
55 * do it on a table with:
56 * - just a leaf node
57 * - has internal nodes (make node size 4K and bn size 1K)
58 * - big cachetable such that everything fits
59 * - small cachetable such that not a lot fits
60 *
61 * make sure APIs are the callback APIs (getf_XXX)
62 * make sure your callbacks all return TOKUDB_CURSOR_CONTINUE,
63 * so we ensure that returning TOKUDB_CURSOR_CONTINUE does not
64 * mess anything up.
65 */
66
67 #include "test.h"
68
69 enum cursor_type {
70 FIRST,
71 LAST,
72 NEXT,
73 PREV,
74 CURRENT,
75 SET,
76 SET_RANGE,
77 SET_RANGE_REVERSE
78 };
79
80 /**
81 * Calculate or verify that a value for a given key is correct
82 * Returns 0 if the value is correct, nonzero otherwise.
83 */
get_value_by_key(DBT * key,DBT * value)84 static void get_value_by_key(DBT * key, DBT * value)
85 {
86 // keys/values are always stored in the DBT in net order
87 int * CAST_FROM_VOIDP(k, key->data);
88 int v = toku_ntohl(*k) * 2 + 1;
89 memcpy(value->data, &v, sizeof(int));
90 }
91
verify_value_by_key(DBT * key,DBT * value)92 static void verify_value_by_key(DBT * key, DBT * value)
93 {
94 assert(key->size == sizeof(int));
95 assert(value->size == sizeof(int));
96
97 int expected;
98 DBT expected_dbt;
99 expected_dbt.data = &expected;
100 expected_dbt.size = sizeof(int);
101 get_value_by_key(key, &expected_dbt);
102
103 int * CAST_FROM_VOIDP(v, value->data);
104 assert(*v == expected);
105 }
106
107 /**
108 * Callback for cursors, can be either traversing
109 * forward, backward, or not at all.
110 */
111 struct cursor_cb_info {
112 int last_key_seen;
113 enum cursor_type type;
114 };
cursor_cb(DBT const * key,DBT const * value,void * extra)115 static int cursor_cb(DBT const * key,
116 DBT const * value, void * extra)
117 {
118 struct cursor_cb_info * CAST_FROM_VOIDP(info, extra);
119 int * CAST_FROM_VOIDP(kbuf, key->data);
120 int k = ntohl(*kbuf);
121
122 switch (info->type) {
123 // point queries, just verify the pair
124 // is correct.
125 case SET:
126 case SET_RANGE:
127 case SET_RANGE_REVERSE:
128 case FIRST:
129 case LAST:
130 case CURRENT:
131 verify_value_by_key((DBT *) key, (DBT *) value);
132 break;
133 case NEXT:
134 // verify the last key we saw was the previous
135 verify_value_by_key((DBT *) key, (DBT *) value);
136 if (k < 0) {
137 assert(k == info->last_key_seen - 1);
138 }
139 break;
140 case PREV:
141 // verify the last key we saw was the next
142 verify_value_by_key((DBT *) key, (DBT *) value);
143 if (k < info->last_key_seen) {
144 assert(k == info->last_key_seen - 1);
145 }
146 break;
147 default:
148 assert(0);
149 }
150
151 info->last_key_seen = k;
152 return TOKUDB_CURSOR_CONTINUE;
153 }
154
155 /**
156 * Fill a FT with the the given number of rows.
157 */
fill_db(DB_ENV * env,DB * db,int num_rows)158 static void fill_db(DB_ENV * env, DB * db, int num_rows)
159 {
160 int r;
161 DB_TXN * txn;
162 DBT key, value;
163
164 printf("filling db\n");
165
166 int i, j;
167 const int ins_per_txn = 1000;
168 assert(num_rows % ins_per_txn == 0);
169 for (i = 0; i < num_rows; i+= ins_per_txn) {
170 r = env->txn_begin(env, NULL, &txn, 0); { int chk_r = r; CKERR(chk_r); }
171 for (j = 0; j < ins_per_txn && (i + j) < num_rows; j++) {
172 int v, k = toku_htonl(i + j);
173 dbt_init(&key, &k, sizeof(int));
174 dbt_init(&value, &v, sizeof(int));
175 get_value_by_key(&key, &value);
176 r = db->put(db, txn, &key, &value, 0); { int chk_r = r; CKERR(chk_r); }
177 }
178 r = txn->commit(txn, 0); { int chk_r = r; CKERR(chk_r); }
179 }
180 }
181
init_env(DB_ENV ** env,size_t ct_size)182 static void init_env(DB_ENV ** env, size_t ct_size)
183 {
184 int r;
185 const int envflags = DB_INIT_MPOOL | DB_CREATE | DB_THREAD |
186 DB_INIT_LOCK | DB_INIT_LOG | DB_INIT_TXN | DB_PRIVATE;
187
188 printf("initializing environment\n");
189
190 toku_os_recursive_delete(TOKU_TEST_FILENAME);
191 r = toku_os_mkdir(TOKU_TEST_FILENAME, 0755); { int chk_r = r; CKERR(chk_r); }
192
193 r = db_env_create(env, 0); { int chk_r = r; CKERR(chk_r); }
194 assert(ct_size < 1024 * 1024 * 1024L);
195 r = (*env)->set_cachesize(*env, 0, ct_size, 1); { int chk_r = r; CKERR(chk_r); }
196 r = (*env)->open(*env, TOKU_TEST_FILENAME, envflags, 0755); { int chk_r = r; CKERR(chk_r); }
197 }
198
init_db(DB_ENV * env,DB ** db)199 static void init_db(DB_ENV * env, DB ** db)
200 {
201 int r;
202 const int node_size = 4096;
203 const int bn_size = 1024;
204
205 printf("initializing db\n");
206
207 DB_TXN * txn;
208 r = db_create(db, env, 0); { int chk_r = r; CKERR(chk_r); }
209 r = (*db)->set_readpagesize(*db, bn_size); { int chk_r = r; CKERR(chk_r); }
210 r = (*db)->set_pagesize(*db, node_size); { int chk_r = r; CKERR(chk_r); }
211 r = env->txn_begin(env, NULL, &txn, 0); { int chk_r = r; CKERR(chk_r); }
212 r = (*db)->open(*db, txn, "db", NULL, DB_BTREE, DB_CREATE, 0644); { int chk_r = r; CKERR(chk_r); }
213 r = txn->commit(txn, 0); { int chk_r = r; CKERR(chk_r); }
214 }
215
cleanup_env_and_db(DB_ENV * env,DB * db)216 static void cleanup_env_and_db(DB_ENV * env, DB * db)
217 {
218 int r;
219
220 printf("cleaning up environment and db\n");
221 r = db->close(db, 0); { int chk_r = r; CKERR(chk_r); }
222 r = env->close(env, 0); { int chk_r = r; CKERR(chk_r); }
223 }
224
do_test(size_t ct_size,int num_keys)225 static void do_test(size_t ct_size, int num_keys)
226 {
227 int i, r;
228 DB * db;
229 DB_ENV * env;
230
231 printf("doing tests for ct_size %lu, num_keys %d\n",
232 ct_size, num_keys);
233
234 // initialize everything and insert data
235 init_env(&env, ct_size);
236 assert(env != NULL);
237 init_db(env, &db);
238 assert(db != NULL);
239 fill_db(env, db, num_keys);
240
241 const int last_key = num_keys - 1;
242
243 // test c_getf_first
244 printf("testing c getf first\n");
245 {
246 DBC * dbc;
247 DB_TXN * txn;
248 struct cursor_cb_info info;
249 r = env->txn_begin(env, NULL, &txn, 0); { int chk_r = r; CKERR(chk_r); }
250 r = db->cursor(db, txn, &dbc, 0); { int chk_r = r; CKERR(chk_r); }
251 info.last_key_seen = -1;
252 info.type = FIRST;
253 r = dbc->c_getf_first(dbc, 0, cursor_cb, &info); { int chk_r = r; CKERR(chk_r); }
254 assert(info.last_key_seen == 0);
255 r = dbc->c_close(dbc); { int chk_r = r; CKERR(chk_r); }
256 r = txn->commit(txn, 0); { int chk_r = r; CKERR(chk_r); }
257 }
258
259 // test c_getf_last
260 printf("testing c getf last\n");
261 {
262 DBC * dbc;
263 DB_TXN * txn;
264 struct cursor_cb_info info;
265 r = env->txn_begin(env, NULL, &txn, 0); { int chk_r = r; CKERR(chk_r); }
266 r = db->cursor(db, txn, &dbc, 0); { int chk_r = r; CKERR(chk_r); }
267 info.last_key_seen = -1;
268 info.type = LAST;
269 r = dbc->c_getf_last(dbc, 0, cursor_cb, &info); { int chk_r = r; CKERR(chk_r); }
270 assert(info.last_key_seen == last_key);
271 r = dbc->c_close(dbc); { int chk_r = r; CKERR(chk_r); }
272 r = txn->commit(txn, 0); { int chk_r = r; CKERR(chk_r); }
273 }
274
275 // test c_getf_next
276 printf("testing c getf next\n");
277 {
278 DBC * dbc;
279 DB_TXN * txn;
280 struct cursor_cb_info info;
281 r = env->txn_begin(env, NULL, &txn, 0); { int chk_r = r; CKERR(chk_r); }
282 r = db->cursor(db, txn, &dbc, 0); { int chk_r = r; CKERR(chk_r); }
283 info.last_key_seen = -1;
284 //info.type = FIRST;
285 //r = dbc->c_getf_first(dbc, 0, cursor_cb, &info); { int chk_r =
286 //r; CKERR(chk_r); }
287 //assert(info.last_key_seen == 0);
288 info.type = NEXT;
289 while ((r = dbc->c_getf_next(dbc, 0, cursor_cb, &info)) == 0);
290 assert(r == DB_NOTFOUND);
291 if (info.last_key_seen != last_key) {
292 printf("last keen seen %d, wanted %d\n",
293 info.last_key_seen, last_key);
294 }
295 assert(info.last_key_seen == last_key);
296 r = dbc->c_close(dbc); { int chk_r = r; CKERR(chk_r); }
297 r = txn->commit(txn, 0); { int chk_r = r; CKERR(chk_r); }
298 }
299
300 // test c_getf_prev
301 printf("testing c getf prev\n");
302 {
303 DBC * dbc;
304 DB_TXN * txn;
305 struct cursor_cb_info info;
306 r = env->txn_begin(env, NULL, &txn, 0); { int chk_r = r; CKERR(chk_r); }
307 r = db->cursor(db, txn, &dbc, 0); { int chk_r = r; CKERR(chk_r); }
308 info.last_key_seen = -1;
309 //info.type = LAST;
310 //r = dbc->c_getf_last(dbc, 0, cursor_cb, &info); { int chk_r = r;
311 //CKERR(chk_r); }
312 //assert(info.last_key_seen == last_key);
313 info.type = PREV;
314 while ((r = dbc->c_getf_prev(dbc, 0, cursor_cb, &info)) == 0);
315 assert(r == DB_NOTFOUND);
316 assert(info.last_key_seen == 0);
317 r = dbc->c_close(dbc); { int chk_r = r; CKERR(chk_r); }
318 r = txn->commit(txn, 0); { int chk_r = r; CKERR(chk_r); }
319 }
320
321 printf("testing db->get, c getf set, current\n");
322 {
323 DBC * dbc;
324 DB_TXN * txn;
325 struct cursor_cb_info info;
326 r = env->txn_begin(env, NULL, &txn, 0); { int chk_r = r; CKERR(chk_r); }
327 r = db->cursor(db, txn, &dbc, 0); { int chk_r = r; CKERR(chk_r); }
328 for (i = 0; i < 1000; i++) {
329 DBT key;
330 int k = random() % num_keys;
331 int nk = toku_htonl(k);
332 dbt_init(&key, &nk, sizeof(int));
333
334 // test c_getf_set
335 info.last_key_seen = -1;
336 info.type = SET;
337 r = dbc->c_getf_set(dbc, 0, &key, cursor_cb, &info); { int chk_r = r; CKERR(chk_r); }
338 assert(info.last_key_seen == k);
339
340 // test c_getf_current
341 info.last_key_seen = -1;
342 info.type = CURRENT;
343 r = dbc->c_getf_current(dbc, 0, cursor_cb, &info); { int chk_r = r; CKERR(chk_r); }
344 assert(info.last_key_seen == k);
345
346 // test db->get (point query)
347 DBT value;
348 memset(&value, 0, sizeof(DBT));
349 r = db->get(db, txn, &key, &value, 0); { int chk_r = r; CKERR(chk_r); }
350 verify_value_by_key(&key, &value);
351 }
352 r = dbc->c_close(dbc); { int chk_r = r; CKERR(chk_r); }
353 r = txn->commit(txn, 0); { int chk_r = r; CKERR(chk_r); }
354 }
355
356 // delete some elements over a variable stride,
357 // this will let us test range/reverse
358 const int stride = num_keys / 10;
359 printf("deleting some elements in stride %d\n", stride);
360 {
361 DBC * dbc;
362 DB_TXN * txn;
363 DBT key;
364 r = env->txn_begin(env, NULL, &txn, 0); { int chk_r = r; CKERR(chk_r); }
365 r = db->cursor(db, txn, &dbc, 0); { int chk_r = r; CKERR(chk_r); }
366 for (i = 0; i < num_keys; i += stride) {
367 int k = toku_htonl(i);
368 dbt_init(&key, &k, sizeof(int));
369 r = db->del(db, txn, &key, 0);
370 }
371 r = dbc->c_close(dbc); { int chk_r = r; CKERR(chk_r); }
372 r = txn->commit(txn, 0); { int chk_r = r; CKERR(chk_r); }
373 }
374
375 // test getf set range and range reverse
376 printf("testing getf set range and range reverse\n");
377 {
378 DBC * dbc;
379 DB_TXN * txn;
380 DBT key;
381 struct cursor_cb_info info;
382 r = env->txn_begin(env, NULL, &txn, 0); { int chk_r = r; CKERR(chk_r); }
383 r = db->cursor(db, txn, &dbc, 0); { int chk_r = r; CKERR(chk_r); }
384 for (i = 0; i < num_keys; i += stride) {
385 int k = toku_htonl(i);
386 dbt_init(&key, &k, sizeof(int));
387
388 // we should have only actually seen the next
389 // key after i if i was not the last key,
390 // otherwise there's nothing after that key
391 info.last_key_seen = -1;
392 info.type = SET_RANGE;
393 r = dbc->c_getf_set_range(dbc, 0, &key, cursor_cb, &info);
394 if (i == last_key) {
395 assert(r == DB_NOTFOUND);
396 } else {
397 assert(info.last_key_seen == i + 1);
398 }
399
400 // we should have only actually seen the prev
401 // key if i was not the first key, otherwise
402 // there's nothing before that key.
403 info.last_key_seen = -1;
404 info.type = SET_RANGE_REVERSE;
405 r = dbc->c_getf_set_range_reverse(dbc, 0, &key, cursor_cb, &info);
406 if (i == 0) {
407 assert(r == DB_NOTFOUND);
408 } else {
409 assert(info.last_key_seen == i - 1);
410 { int chk_r = r; CKERR(chk_r); }
411 }
412 }
413 r = dbc->c_close(dbc); { int chk_r = r; CKERR(chk_r); }
414 r = txn->commit(txn, 0); { int chk_r = r; CKERR(chk_r); }
415 }
416
417 cleanup_env_and_db(env, db);
418 }
419
test_main(int argc,char * const argv[])420 int test_main(int argc, char * const argv[])
421 {
422 default_parse_args(argc, argv);
423
424 // just a leaf, fits in cachetable
425 do_test(1L*1024*1024, 1000);
426 // with internal nodes, fits in cachetable
427 do_test(4L*1024*1024, 100000);
428 // with internal nodes, does not fit in cachetable
429 do_test(1L*1024*1024, 1000000);
430
431 return 0;
432 }
433
434