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 // generate a tree with duplicate pivots and check that ft->verify finds them
40
41
42 #include <ft-cachetable-wrappers.h>
43 #include "test.h"
44
45 static FTNODE
make_node(FT_HANDLE ft,int height)46 make_node(FT_HANDLE ft, int height) {
47 FTNODE node = NULL;
48 int n_children = (height == 0) ? 1 : 0;
49 toku_create_new_ftnode(ft, &node, height, n_children);
50 if (n_children) BP_STATE(node,0) = PT_AVAIL;
51 return node;
52 }
53
54 static void
append_leaf(FTNODE leafnode,void * key,size_t keylen,void * val,size_t vallen)55 append_leaf(FTNODE leafnode, void *key, size_t keylen, void *val, size_t vallen) {
56 assert(leafnode->height == 0);
57
58 DBT thekey; toku_fill_dbt(&thekey, key, keylen);
59 DBT theval; toku_fill_dbt(&theval, val, vallen);
60
61 // get an index that we can use to create a new leaf entry
62 uint32_t idx = BLB_DATA(leafnode, 0)->num_klpairs();
63
64 // apply an insert to the leaf node
65 MSN msn = next_dummymsn();
66 ft_msg msg(&thekey, &theval, FT_INSERT, msn, toku_xids_get_root_xids());
67 txn_gc_info gc_info(nullptr, TXNID_NONE, TXNID_NONE, false);
68 toku_ft_bn_apply_msg_once(
69 BLB(leafnode, 0),
70 msg,
71 idx,
72 keylen,
73 NULL,
74 &gc_info,
75 NULL,
76 NULL,
77 NULL);
78
79 // don't forget to dirty the node
80 leafnode->set_dirty();
81 }
82
83 static void
populate_leaf(FTNODE leafnode,int seq,int n,int * minkey,int * maxkey)84 populate_leaf(FTNODE leafnode, int seq, int n, int *minkey, int *maxkey) {
85 for (int i = 0; i < n; i++) {
86 int k = htonl(seq + i);
87 int v = seq + i;
88 append_leaf(leafnode, &k, sizeof k, &v, sizeof v);
89 }
90 *minkey = htonl(seq);
91 *maxkey = htonl(seq + n - 1);
92 }
93
94 static FTNODE
make_tree(FT_HANDLE ft,int height,int fanout,int nperleaf,int * seq,int * minkey,int * maxkey)95 make_tree(FT_HANDLE ft, int height, int fanout, int nperleaf, int *seq, int *minkey, int *maxkey) {
96 FTNODE node;
97 if (height == 0) {
98 node = make_node(ft, 0);
99 populate_leaf(node, *seq, nperleaf, minkey, maxkey);
100 *seq += nperleaf;
101 } else {
102 node = make_node(ft, height);
103 int minkeys[fanout], maxkeys[fanout];
104 for (int childnum = 0; childnum < fanout; childnum++) {
105 FTNODE child = make_tree(ft, height-1, fanout, nperleaf, seq, &minkeys[childnum], &maxkeys[childnum]);
106 if (childnum == 0) {
107 toku_ft_nonleaf_append_child(node, child, NULL);
108 } else {
109 int k = maxkeys[0]; // use duplicate pivots, should result in a broken tree
110 DBT pivotkey;
111 toku_ft_nonleaf_append_child(node, child, toku_fill_dbt(&pivotkey, &k, sizeof k));
112 }
113 toku_unpin_ftnode(ft->ft, child);
114 }
115 *minkey = minkeys[0];
116 *maxkey = maxkeys[0];
117 for (int i = 1; i < fanout; i++) {
118 if (memcmp(minkey, &minkeys[i], sizeof minkeys[i]) > 0)
119 *minkey = minkeys[i];
120 if (memcmp(maxkey, &maxkeys[i], sizeof maxkeys[i]) < 0)
121 *maxkey = maxkeys[i];
122 }
123 }
124 return node;
125 }
126
UU()127 static UU() void
128 deleted_row(UU() DB *db, UU() DBT *key, UU() DBT *val) {
129 }
130
131 static void
test_make_tree(int height,int fanout,int nperleaf,int do_verify)132 test_make_tree(int height, int fanout, int nperleaf, int do_verify) {
133 int r;
134
135 // cleanup
136 const char *fname = TOKU_TEST_FILENAME;
137 r = unlink(fname);
138 if (r != 0) {
139 assert(r == -1);
140 assert(get_error_errno() == ENOENT);
141 }
142
143 // create a cachetable
144 CACHETABLE ct = NULL;
145 toku_cachetable_create(&ct, 0, ZERO_LSN, nullptr);
146
147 // create the ft
148 TOKUTXN null_txn = NULL;
149 FT_HANDLE ft = NULL;
150 r = toku_open_ft_handle(fname, 1, &ft, 1024, 256, TOKU_DEFAULT_COMPRESSION_METHOD, ct, null_txn, toku_builtin_compare_fun);
151 assert(r == 0);
152
153 // make a tree
154 int seq = 0, minkey, maxkey;
155 FTNODE newroot = make_tree(ft, height, fanout, nperleaf, &seq, &minkey, &maxkey);
156
157 // discard the old root block
158 // set the new root to point to the new tree
159 toku_ft_set_new_root_blocknum(ft->ft, newroot->blocknum);
160
161 // unpin the new root
162 toku_unpin_ftnode(ft->ft, newroot);
163
164 if (do_verify) {
165 r = toku_verify_ft(ft);
166 assert(r != 0);
167 }
168
169 // flush to the file system
170 r = toku_close_ft_handle_nolsn(ft, 0);
171 assert(r == 0);
172
173 // shutdown the cachetable
174 toku_cachetable_close(&ct);
175 }
176
177 static int
usage(void)178 usage(void) {
179 return 1;
180 }
181
182 int
test_main(int argc,const char * argv[])183 test_main (int argc , const char *argv[]) {
184 int height = 1;
185 int fanout = 3;
186 int nperleaf = 8;
187 int do_verify = 1;
188 initialize_dummymsn();
189 for (int i = 1; i < argc; i++) {
190 const char *arg = argv[i];
191 if (strcmp(arg, "-v") == 0) {
192 verbose++;
193 continue;
194 }
195 if (strcmp(arg, "-q") == 0) {
196 verbose = 0;
197 continue;
198 }
199 if (strcmp(arg, "--height") == 0 && i+1 < argc) {
200 height = atoi(argv[++i]);
201 continue;
202 }
203 if (strcmp(arg, "--fanout") == 0 && i+1 < argc) {
204 fanout = atoi(argv[++i]);
205 continue;
206 }
207 if (strcmp(arg, "--nperleaf") == 0 && i+1 < argc) {
208 nperleaf = atoi(argv[++i]);
209 continue;
210 }
211 if (strcmp(arg, "--verify") == 0 && i+1 < argc) {
212 do_verify = atoi(argv[++i]);
213 continue;
214 }
215 return usage();
216 }
217 test_make_tree(height, fanout, nperleaf, do_verify);
218 return 0;
219 }
220