verify-dup-pivots.cc 5.17 KB
Newer Older
1 2
/* -*- mode: C++; c-basic-offset: 4; indent-tabs-mode: nil -*- */
// vim: ft=cpp:expandtab:ts=8:sw=4:softtabstop=4:
3
#ident "$Id$"
4 5 6 7
#ident "Copyright (c) 2011 Tokutek Inc.  All rights reserved."

// generate a tree with duplicate pivots and check that brt->verify finds them

8

9
#include <ft-cachetable-wrappers.h>
10 11
#include "test.h"

12 13 14
static FTNODE
make_node(FT_HANDLE brt, int height) {
    FTNODE node = NULL;
15
    int n_children = (height == 0) ? 1 : 0;
16
    toku_create_new_ftnode(brt, &node, height, n_children);
17
    if (n_children) BP_STATE(node,0) = PT_AVAIL;
18 19 20 21
    return node;
}

static void
22
append_leaf(FTNODE leafnode, void *key, size_t keylen, void *val, size_t vallen) {
23 24 25 26 27 28
    assert(leafnode->height == 0);

    DBT thekey; toku_fill_dbt(&thekey, key, keylen);
    DBT theval; toku_fill_dbt(&theval, val, vallen);

    // get an index that we can use to create a new leaf entry
29
    uint32_t idx = toku_omt_size(BLB_BUFFER(leafnode, 0));
30 31

    // apply an insert to the leaf node
32
    MSN msn = next_dummymsn();
33
    FT_MSG_S cmd = { FT_INSERT, msn, xids_get_root_xids(), .u={.id = { &thekey, &theval }} };
34
    toku_ft_bn_apply_cmd_once(BLB(leafnode, 0), &cmd, idx, NULL, TXNID_NONE, make_gc_info(false), NULL, NULL);
35 36 37 38 39 40

    // dont forget to dirty the node
    leafnode->dirty = 1;
}

static void
41
populate_leaf(FTNODE leafnode, int seq, int n, int *minkey, int *maxkey) {
42 43 44 45 46 47 48 49 50
    for (int i = 0; i < n; i++) {
        int k = htonl(seq + i);
        int v = seq + i;
        append_leaf(leafnode, &k, sizeof k, &v, sizeof v);
    }
    *minkey = htonl(seq);
    *maxkey = htonl(seq + n - 1);
}

51 52 53
static FTNODE
make_tree(FT_HANDLE brt, int height, int fanout, int nperleaf, int *seq, int *minkey, int *maxkey) {
    FTNODE node;
54 55 56 57 58 59 60 61
    if (height == 0) {
        node = make_node(brt, 0);
        populate_leaf(node, *seq, nperleaf, minkey, maxkey);
        *seq += nperleaf;
    } else {
        node = make_node(brt, height);
        int minkeys[fanout], maxkeys[fanout];
        for (int childnum = 0; childnum < fanout; childnum++) {
62
            FTNODE child = make_tree(brt, height-1, fanout, nperleaf, seq, &minkeys[childnum], &maxkeys[childnum]);
63
            if (childnum == 0) {
64
                toku_ft_nonleaf_append_child(node, child, NULL);
65
            } else {
66
                int k = maxkeys[0]; // use duplicate pivots, should result in a broken tree
67
                DBT pivotkey;
John Esmet's avatar
John Esmet committed
68
                toku_ft_nonleaf_append_child(node, child, toku_fill_dbt(&pivotkey, &k, sizeof k));
69
            }
70
            toku_unpin_ftnode(brt->ft, child);
71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92
        }
        *minkey = minkeys[0];
        *maxkey = maxkeys[0];
        for (int i = 1; i < fanout; i++) {
            if (memcmp(minkey, &minkeys[i], sizeof minkeys[i]) > 0)
                *minkey = minkeys[i];
            if (memcmp(maxkey, &maxkeys[i], sizeof maxkeys[i]) < 0)
                *maxkey = maxkeys[i];
        }
    }
    return node;
}

static UU() void
deleted_row(UU() DB *db, UU() DBT *key, UU() DBT *val) {
}

static void 
test_make_tree(int height, int fanout, int nperleaf, int do_verify) {
    int r;

    // cleanup
93
    char fname[]= __SRCFILE__ ".ft_handle";
94
    r = unlink(fname);
95 96 97 98
    if (r != 0) {
        assert(r == -1);
        assert(get_error_errno() == ENOENT);
    }
99 100 101

    // create a cachetable
    CACHETABLE ct = NULL;
102
    toku_cachetable_create(&ct, 0, ZERO_LSN, NULL_LOGGER);
103 104 105

    // create the brt
    TOKUTXN null_txn = NULL;
106 107
    FT_HANDLE brt = NULL;
    r = toku_open_ft_handle(fname, 1, &brt, 1024, 256, TOKU_DEFAULT_COMPRESSION_METHOD, ct, null_txn, toku_builtin_compare_fun);
108 109 110 111
    assert(r == 0);

    // make a tree
    int seq = 0, minkey, maxkey;
112
    FTNODE newroot = make_tree(brt, height, fanout, nperleaf, &seq, &minkey, &maxkey);
113 114 115

    // discard the old root block
    // set the new root to point to the new tree
116
    toku_ft_set_new_root_blocknum(brt->ft, newroot->thisnodename);
117 118

    // unpin the new root
119
    toku_unpin_ftnode(brt->ft, newroot);
120 121

    if (do_verify) {
122
        r = toku_verify_ft(brt);
123 124 125 126
        assert(r != 0);
    }

    // flush to the file system
127
    r = toku_close_ft_handle_nolsn(brt, 0);     
128 129 130
    assert(r == 0);

    // shutdown the cachetable
131
    toku_cachetable_close(&ct);
132 133 134 135 136 137 138 139 140 141 142 143 144
}

static int
usage(void) {
    return 1;
}

int
test_main (int argc , const char *argv[]) {
    int height = 1;
    int fanout = 3;
    int nperleaf = 8;
    int do_verify = 1;
145
    initialize_dummymsn();
146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176
    for (int i = 1; i < argc; i++) {
        const char *arg = argv[i];
        if (strcmp(arg, "-v") == 0) {
            verbose++;
            continue;
        }
        if (strcmp(arg, "-q") == 0) {
            verbose = 0;
            continue;
        }
        if (strcmp(arg, "--height") == 0 && i+1 < argc) {
            height = atoi(argv[++i]);
            continue;
        }
        if (strcmp(arg, "--fanout") == 0 && i+1 < argc) {
            fanout = atoi(argv[++i]);
            continue;
        }
        if (strcmp(arg, "--nperleaf") == 0 && i+1 < argc) {
            nperleaf = atoi(argv[++i]);
            continue;
        }
        if (strcmp(arg, "--verify") == 0 && i+1 < argc) {
            do_verify = atoi(argv[++i]);
            continue;
        }
        return usage();
    }
    test_make_tree(height, fanout, nperleaf, do_verify);
    return 0;
}