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