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