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