orthopush-flush.cc 47.5 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 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55
/*
COPYING CONDITIONS NOTICE:

  This program is free software; you can redistribute it and/or modify
  it under the terms of version 2 of the GNU General Public License as
  published by the Free Software Foundation, and provided that the
  following conditions are met:

      * Redistributions of source code must retain this COPYING
        CONDITIONS NOTICE, the COPYRIGHT NOTICE (below), the
        DISCLAIMER (below), the UNIVERSITY PATENT NOTICE (below), the
        PATENT MARKING NOTICE (below), and the PATENT RIGHTS
        GRANT (below).

      * Redistributions in binary form must reproduce this COPYING
        CONDITIONS NOTICE, the COPYRIGHT NOTICE (below), the
        DISCLAIMER (below), the UNIVERSITY PATENT NOTICE (below), the
        PATENT MARKING NOTICE (below), and the PATENT RIGHTS
        GRANT (below) in the documentation and/or other materials
        provided with the distribution.

  You should have received a copy of the GNU General Public License
  along with this program; if not, write to the Free Software
  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
  02110-1301, USA.

COPYRIGHT NOTICE:

  TokuDB, Tokutek Fractal Tree Indexing Library.
  Copyright (C) 2007-2013 Tokutek, Inc.

DISCLAIMER:

  This program is distributed in the hope that it will be useful, but
  WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  General Public License for more details.

UNIVERSITY PATENT NOTICE:

  The technology is licensed by the Massachusetts Institute of
  Technology, Rutgers State University of New Jersey, and the Research
  Foundation of State University of New York at Stony Brook under
  United States of America Serial No. 11/760379 and to the patents
  and/or patent applications resulting from it.

PATENT MARKING NOTICE:

  This software is covered by US Patent No. 8,185,551.

PATENT RIGHTS GRANT:

56
  "THIS IMPLEMENTATION" means the copyrightable works distributed by
57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87
  Tokutek as part of the Fractal Tree project.

  "PATENT CLAIMS" means the claims of patents that are owned or
  licensable by Tokutek, both currently or in the future; and that in
  the absence of this license would be infringed by THIS
  IMPLEMENTATION or by using or running THIS IMPLEMENTATION.

  "PATENT CHALLENGE" shall mean a challenge to the validity,
  patentability, enforceability and/or non-infringement of any of the
  PATENT CLAIMS or otherwise opposing any of the PATENT CLAIMS.

  Tokutek hereby grants to you, for the term and geographical scope of
  the PATENT CLAIMS, a non-exclusive, no-charge, royalty-free,
  irrevocable (except as stated in this section) patent license to
  make, have made, use, offer to sell, sell, import, transfer, and
  otherwise run, modify, and propagate the contents of THIS
  IMPLEMENTATION, where such license applies only to the PATENT
  CLAIMS.  This grant does not include claims that would be infringed
  only as a consequence of further modifications of THIS
  IMPLEMENTATION.  If you or your agent or licensee institute or order
  or agree to the institution of patent litigation against any entity
  (including a cross-claim or counterclaim in a lawsuit) alleging that
  THIS IMPLEMENTATION constitutes direct or contributory patent
  infringement, or inducement of patent infringement, then any rights
  granted to you under this License shall terminate as of the date
  such litigation is filed.  If you or your agent or exclusive
  licensee institute or order or agree to the institution of a PATENT
  CHALLENGE, then Tokutek may terminate any rights granted to you
  under this License.
*/

88
#ident "Copyright (c) 2007-2013 Tokutek Inc.  All rights reserved."
Zardosht Kasheff's avatar
Zardosht Kasheff committed
89 90 91

#include "test.h"

92

93
#include "ule.h"
Zardosht Kasheff's avatar
Zardosht Kasheff committed
94 95 96

static TOKUTXN const null_txn = 0;
static DB * const null_db = 0;
Leif Walsh's avatar
Leif Walsh committed
97
static const char *fname = TOKU_TEST_FILENAME;
Zardosht Kasheff's avatar
Zardosht Kasheff committed
98

Zardosht Kasheff's avatar
Zardosht Kasheff committed
99
static int dummy_cmp(DB *db __attribute__((unused)),
Zardosht Kasheff's avatar
Zardosht Kasheff committed
100
                     const DBT *a, const DBT *b) {
101
    int c;
Zardosht Kasheff's avatar
Zardosht Kasheff committed
102
    if (a->size > b->size) {
103
        c = memcmp(a->data, b->data, b->size);
Zardosht Kasheff's avatar
Zardosht Kasheff committed
104
    } else if (a->size < b->size) {
105
        c = memcmp(a->data, b->data, a->size);
Zardosht Kasheff's avatar
Zardosht Kasheff committed
106 107 108
    } else {
        return memcmp(a->data, b->data, a->size);
    }
109 110 111 112
    if (c == 0) {
        c = a->size - b->size;
    }
    return c;
Zardosht Kasheff's avatar
Zardosht Kasheff committed
113 114
}

115
// generate size random bytes into dest
Zardosht Kasheff's avatar
Zardosht Kasheff committed
116 117 118 119
static void
rand_bytes(void *dest, int size)
{
    long *l;
120
    for (CAST_FROM_VOIDP(l, dest); (unsigned int) size >= (sizeof *l); ++l, size -= (sizeof *l)) {
Zardosht Kasheff's avatar
Zardosht Kasheff committed
121 122 123 124 125 126 127
        *l = random();
    }
    for (char *c = (char *) l; size > 0; ++c, --size) {
        *c = random() & 0xff;
    }
}

128 129
// generate size random bytes into dest, with a lot less entropy (every
// group of 4 bytes is the same)
Zardosht Kasheff's avatar
Zardosht Kasheff committed
130 131 132 133
static void
rand_bytes_limited(void *dest, int size)
{
    long *l;
134
    for (CAST_FROM_VOIDP(l, dest); (size_t) size >= (sizeof *l); ++l, size -= (sizeof *l)) {
Zardosht Kasheff's avatar
Zardosht Kasheff committed
135
        char c = random() & 0xff;
136 137
        for (char *p = (char *) l; (size_t) (p - (char *) l) < (sizeof *l); ++p) {
            *p = c;
Zardosht Kasheff's avatar
Zardosht Kasheff committed
138 139 140
        }
    }
    char c = random() & 0xff;
141 142
    for (char *p = (char *) l; size > 0; ++p, --size) {
        *p = c;
Zardosht Kasheff's avatar
Zardosht Kasheff committed
143 144 145
    }
}

146 147
// generate a random message with xids and a key starting with pfx, insert
// it in bnc, and save it in output params save and is_fresh_out
Zardosht Kasheff's avatar
Zardosht Kasheff committed
148
static void
149
insert_random_message(NONLEAF_CHILDINFO bnc, FT_MSG_S **save, bool *is_fresh_out, XIDS xids, int pfx)
Zardosht Kasheff's avatar
Zardosht Kasheff committed
150
{
151 152
    int keylen = (random() % 128) + 16;
    int vallen = (random() % 128) + 16;
Zardosht Kasheff's avatar
Zardosht Kasheff committed
153 154 155 156 157 158 159 160 161
    void *key = toku_xmalloc(keylen + (sizeof pfx));
    void *val = toku_xmalloc(vallen);
    *(int *) key = pfx;
    rand_bytes((char *) key + (sizeof pfx), keylen);
    rand_bytes(val, vallen);
    MSN msn = next_dummymsn();
    bool is_fresh = (random() & 0x100) == 0;

    DBT *keydbt, *valdbt;
162 163
    XMALLOC(keydbt);
    XMALLOC(valdbt);
Zardosht Kasheff's avatar
Zardosht Kasheff committed
164 165
    toku_fill_dbt(keydbt, key, keylen + (sizeof pfx));
    toku_fill_dbt(valdbt, val, vallen);
166
    FT_MSG_S *XMALLOC(result);
167
    result->type = FT_INSERT;
Zardosht Kasheff's avatar
Zardosht Kasheff committed
168 169 170 171 172 173 174
    result->msn = msn;
    result->xids = xids;
    result->u.id.key = keydbt;
    result->u.id.val = valdbt;
    *save = result;
    *is_fresh_out = is_fresh;

175 176 177
    toku_bnc_insert_msg(bnc, key, keylen + (sizeof pfx), val, vallen,
                        FT_INSERT, msn, xids, is_fresh,
                        NULL, dummy_cmp);
Zardosht Kasheff's avatar
Zardosht Kasheff committed
178 179
}

180 181
// generate a random message with xids and a key starting with pfx, insert
// it into blb, and save it in output param save
Zardosht Kasheff's avatar
Zardosht Kasheff committed
182
static void
183
insert_random_message_to_bn(FT_HANDLE t, BASEMENTNODE blb, LEAFENTRY *save, XIDS xids, int pfx)
Zardosht Kasheff's avatar
Zardosht Kasheff committed
184 185
{
    int keylen = (random() % 16) + 16;
186 187 188
    int vallen = (random() % 128) + 16;
    uint32_t *pfxp;
    char key[(sizeof *pfxp) + keylen];
189
    char val[vallen];
190 191 192 193
    pfxp = (uint32_t *) &key[0];
    *pfxp = pfx;
    char *randkeyp = &key[sizeof *pfxp];
    rand_bytes_limited(randkeyp, keylen);
Zardosht Kasheff's avatar
Zardosht Kasheff committed
194 195 196
    rand_bytes(val, vallen);
    MSN msn = next_dummymsn();

197 198 199
    DBT keydbt_s, *keydbt, valdbt_s, *valdbt;
    keydbt = &keydbt_s;
    valdbt = &valdbt_s;
200
    toku_fill_dbt(keydbt, key, (sizeof *pfxp) + keylen);
Zardosht Kasheff's avatar
Zardosht Kasheff committed
201
    toku_fill_dbt(valdbt, val, vallen);
202 203
    FT_MSG_S msg;
    msg.type = FT_INSERT;
204 205 206 207 208
    msg.msn = msn;
    msg.xids = xids;
    msg.u.id.key = keydbt;
    msg.u.id.val = valdbt;
    size_t memsize;
209
    int64_t numbytes;
210 211
    toku_le_apply_msg(&msg, NULL, TXNID_NONE, make_gc_info(false), &memsize, save, NULL, NULL, NULL, &numbytes);
    toku_ft_bn_apply_cmd(t->ft->compare_fun, t->ft->update_fun, NULL, blb, &msg, TXNID_NONE, make_gc_info(false), NULL, NULL);
212 213 214
    if (msn.msn > blb->max_msn_applied.msn) {
        blb->max_msn_applied = msn;
    }
Zardosht Kasheff's avatar
Zardosht Kasheff committed
215 216
}

217 218 219 220 221
// generate a random message with xids and a key starting with pfx, insert
// it into blb1 and also into blb2, and save it in output param save
//
// used for making two leaf nodes the same in order to compare the result
// of 'maybe_apply' and a normal buffer flush
222
static void
223
insert_same_message_to_bns(FT_HANDLE t, BASEMENTNODE blb1, BASEMENTNODE blb2, LEAFENTRY *save, XIDS xids, int pfx)
224 225
{
    int keylen = (random() % 16) + 16;
226 227 228
    int vallen = (random() % 128) + 16;
    uint32_t *pfxp;
    char key[(sizeof *pfxp) + keylen];
229
    char val[vallen];
230 231 232 233
    pfxp = (uint32_t *) &key[0];
    *pfxp = pfx;
    char *randkeyp = &key[sizeof *pfxp];
    rand_bytes_limited(randkeyp, keylen);
234 235 236 237 238 239
    rand_bytes(val, vallen);
    MSN msn = next_dummymsn();

    DBT keydbt_s, *keydbt, valdbt_s, *valdbt;
    keydbt = &keydbt_s;
    valdbt = &valdbt_s;
240
    toku_fill_dbt(keydbt, key, (sizeof *pfxp) + keylen);
241
    toku_fill_dbt(valdbt, val, vallen);
242 243
    FT_MSG_S msg;
    msg.type = FT_INSERT;
244 245 246 247 248
    msg.msn = msn;
    msg.xids = xids;
    msg.u.id.key = keydbt;
    msg.u.id.val = valdbt;
    size_t memsize;
249
    int64_t numbytes;
250 251
    toku_le_apply_msg(&msg, NULL, TXNID_NONE, make_gc_info(false), &memsize, save, NULL, NULL, NULL, &numbytes);
    toku_ft_bn_apply_cmd(t->ft->compare_fun, t->ft->update_fun, NULL, blb1, &msg, TXNID_NONE, make_gc_info(false), NULL, NULL);
252 253 254
    if (msn.msn > blb1->max_msn_applied.msn) {
        blb1->max_msn_applied = msn;
    }
255
    toku_ft_bn_apply_cmd(t->ft->compare_fun, t->ft->update_fun, NULL, blb2, &msg, TXNID_NONE, make_gc_info(false), NULL, NULL);
256 257 258 259 260
    if (msn.msn > blb2->max_msn_applied.msn) {
        blb2->max_msn_applied = msn;
    }
}

Zardosht Kasheff's avatar
Zardosht Kasheff committed
261
struct orthopush_flush_update_fun_extra {
262 263
    DBT new_val;
    int *num_applications;
Zardosht Kasheff's avatar
Zardosht Kasheff committed
264 265 266
};

static int
Zardosht Kasheff's avatar
Zardosht Kasheff committed
267
orthopush_flush_update_fun(DB * UU(db), const DBT *UU(key), const DBT *UU(old_val), const DBT *extra,
Zardosht Kasheff's avatar
Zardosht Kasheff committed
268
                           void (*set_val)(const DBT *new_val, void *set_extra), void *set_extra) {
269
    struct orthopush_flush_update_fun_extra *CAST_FROM_VOIDP(e, extra->data);
270 271
    (*e->num_applications)++;
    set_val(&e->new_val, set_extra);
Zardosht Kasheff's avatar
Zardosht Kasheff committed
272 273 274
    return 0;
}

275 276 277 278 279 280
// generate a random update message with xids and a key starting with pfx,
// insert it into blb, and save it in output param save, and update the
// max msn so far in max_msn
//
// the update message will overwrite the value with something generated
// here, and add one to the int pointed to by applied
Zardosht Kasheff's avatar
Zardosht Kasheff committed
281
static void
282
insert_random_update_message(NONLEAF_CHILDINFO bnc, FT_MSG_S **save, bool is_fresh, XIDS xids, int pfx, int *applied, MSN *max_msn)
Zardosht Kasheff's avatar
Zardosht Kasheff committed
283 284
{
    int keylen = (random() % 16) + 16;
285
    int vallen = (random() % 16) + 16;
Zardosht Kasheff's avatar
Zardosht Kasheff committed
286
    void *key = toku_xmalloc(keylen + (sizeof pfx));
287
    struct orthopush_flush_update_fun_extra *XMALLOC(update_extra);
Zardosht Kasheff's avatar
Zardosht Kasheff committed
288 289
    *(int *) key = pfx;
    rand_bytes_limited((char *) key + (sizeof pfx), keylen);
290 291 292
    toku_fill_dbt(&update_extra->new_val, toku_xmalloc(vallen), vallen);
    rand_bytes(update_extra->new_val.data, vallen);
    update_extra->num_applications = applied;
Zardosht Kasheff's avatar
Zardosht Kasheff committed
293 294 295
    MSN msn = next_dummymsn();

    DBT *keydbt, *valdbt;
296 297
    XMALLOC(keydbt);
    XMALLOC(valdbt);
Zardosht Kasheff's avatar
Zardosht Kasheff committed
298
    toku_fill_dbt(keydbt, key, keylen + (sizeof pfx));
299
    toku_fill_dbt(valdbt, update_extra, sizeof *update_extra);
300
    FT_MSG_S *XMALLOC(result);
301
    result->type = FT_UPDATE;
Zardosht Kasheff's avatar
Zardosht Kasheff committed
302 303 304 305 306 307
    result->msn = msn;
    result->xids = xids;
    result->u.id.key = keydbt;
    result->u.id.val = valdbt;
    *save = result;

308 309 310 311
    toku_bnc_insert_msg(bnc, key, keylen + (sizeof pfx),
                        update_extra, sizeof *update_extra,
                        FT_UPDATE, msn, xids, is_fresh,
                        NULL, dummy_cmp);
312 313 314
    if (msn.msn > max_msn->msn) {
        *max_msn = msn;
    }
Zardosht Kasheff's avatar
Zardosht Kasheff committed
315 316 317 318
}

const int M = 1024 * 1024;

319 320
// flush from one internal node to another, where both only have one
// buffer
Zardosht Kasheff's avatar
Zardosht Kasheff committed
321
static void
322
flush_to_internal(FT_HANDLE t) {
Zardosht Kasheff's avatar
Zardosht Kasheff committed
323 324
    int r;

325 326
    FT_MSG_S **MALLOC_N(4096,parent_messages);  // 128k / 32 = 4096
    FT_MSG_S **MALLOC_N(4096,child_messages);
327 328 329 330
    bool *MALLOC_N(4096,parent_messages_is_fresh);
    bool *MALLOC_N(4096,child_messages_is_fresh);
    memset(parent_messages_is_fresh, 0, 4096*(sizeof parent_messages_is_fresh[0]));
    memset(child_messages_is_fresh, 0, 4096*(sizeof child_messages_is_fresh[0]));
Zardosht Kasheff's avatar
Zardosht Kasheff committed
331 332 333 334 335 336 337 338 339 340

    XIDS xids_0 = xids_get_root_xids();
    XIDS xids_123, xids_234;
    r = xids_create_child(xids_0, &xids_123, (TXNID)123);
    CKERR(r);
    r = xids_create_child(xids_0, &xids_234, (TXNID)234);
    CKERR(r);

    NONLEAF_CHILDINFO child_bnc = toku_create_empty_nl();
    int i;
341
    for (i = 0; toku_bnc_memory_used(child_bnc) < 128*1024; ++i) {
Zardosht Kasheff's avatar
Zardosht Kasheff committed
342 343 344 345 346
        insert_random_message(child_bnc, &child_messages[i], &child_messages_is_fresh[i], xids_123, 0);
    }
    int num_child_messages = i;

    NONLEAF_CHILDINFO parent_bnc = toku_create_empty_nl();
347
    for (i = 0; toku_bnc_memory_used(parent_bnc) < 128*1024; ++i) {
Zardosht Kasheff's avatar
Zardosht Kasheff committed
348 349 350 351
        insert_random_message(parent_bnc, &parent_messages[i], &parent_messages_is_fresh[i], xids_234, 0);
    }
    int num_parent_messages = i;

352
    FTNODE XMALLOC(child);
Zardosht Kasheff's avatar
Zardosht Kasheff committed
353
    BLOCKNUM blocknum = { 42 };
Zardosht Kasheff's avatar
Zardosht Kasheff committed
354
    toku_initialize_empty_ftnode(child, blocknum, 1, 1, FT_LAYOUT_VERSION, 0);
Zardosht Kasheff's avatar
Zardosht Kasheff committed
355 356 357 358
    destroy_nonleaf_childinfo(BNC(child, 0));
    set_BNC(child, 0, child_bnc);
    BP_STATE(child, 0) = PT_AVAIL;

John Esmet's avatar
John Esmet committed
359
    toku_bnc_flush_to_child(t->ft, parent_bnc, child, TXNID_NONE);
Zardosht Kasheff's avatar
Zardosht Kasheff committed
360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427

    int parent_messages_present[num_parent_messages];
    int child_messages_present[num_child_messages];
    memset(parent_messages_present, 0, sizeof parent_messages_present);
    memset(child_messages_present, 0, sizeof child_messages_present);

    FIFO_ITERATE(child_bnc->buffer, key, keylen, val, vallen, type, msn, xids, is_fresh,
                 {
                     DBT keydbt;
                     DBT valdbt;
                     toku_fill_dbt(&keydbt, key, keylen);
                     toku_fill_dbt(&valdbt, val, vallen);
                     int found = 0;
                     for (i = 0; i < num_parent_messages; ++i) {
                         if (dummy_cmp(NULL, &keydbt, parent_messages[i]->u.id.key) == 0 &&
                             msn.msn == parent_messages[i]->msn.msn) {
                             assert(parent_messages_present[i] == 0);
                             assert(found == 0);
                             assert(dummy_cmp(NULL, &valdbt, parent_messages[i]->u.id.val) == 0);
                             assert(type == parent_messages[i]->type);
                             assert(xids_get_innermost_xid(xids) == xids_get_innermost_xid(parent_messages[i]->xids));
                             assert(parent_messages_is_fresh[i] == is_fresh);
                             parent_messages_present[i]++;
                             found++;
                         }
                     }
                     for (i = 0; i < num_child_messages; ++i) {
                         if (dummy_cmp(NULL, &keydbt, child_messages[i]->u.id.key) == 0 &&
                             msn.msn == child_messages[i]->msn.msn) {
                             assert(child_messages_present[i] == 0);
                             assert(found == 0);
                             assert(dummy_cmp(NULL, &valdbt, child_messages[i]->u.id.val) == 0);
                             assert(type == child_messages[i]->type);
                             assert(xids_get_innermost_xid(xids) == xids_get_innermost_xid(child_messages[i]->xids));
                             assert(child_messages_is_fresh[i] == is_fresh);
                             child_messages_present[i]++;
                             found++;
                         }
                     }
                     assert(found == 1);
                 });

    for (i = 0; i < num_parent_messages; ++i) {
        assert(parent_messages_present[i] == 1);
    }
    for (i = 0; i < num_child_messages; ++i) {
        assert(child_messages_present[i] == 1);
    }

    xids_destroy(&xids_0);
    xids_destroy(&xids_123);
    xids_destroy(&xids_234);

    for (i = 0; i < num_parent_messages; ++i) {
        toku_free(parent_messages[i]->u.id.key->data);
        toku_free((DBT *) parent_messages[i]->u.id.key);
        toku_free(parent_messages[i]->u.id.val->data);
        toku_free((DBT *) parent_messages[i]->u.id.val);
        toku_free(parent_messages[i]);
    }
    for (i = 0; i < num_child_messages; ++i) {
        toku_free(child_messages[i]->u.id.key->data);
        toku_free((DBT *) child_messages[i]->u.id.key);
        toku_free(child_messages[i]->u.id.val->data);
        toku_free((DBT *) child_messages[i]->u.id.val);
        toku_free(child_messages[i]);
    }
    destroy_nonleaf_childinfo(parent_bnc);
428
    toku_ftnode_free(&child);
Zardosht Kasheff's avatar
Zardosht Kasheff committed
429 430 431 432 433 434
    toku_free(parent_messages);
    toku_free(child_messages);
    toku_free(parent_messages_is_fresh);
    toku_free(child_messages_is_fresh);
}

435
// flush from one internal node to another, where the child has 8 buffers
Zardosht Kasheff's avatar
Zardosht Kasheff committed
436
static void
437
flush_to_internal_multiple(FT_HANDLE t) {
Zardosht Kasheff's avatar
Zardosht Kasheff committed
438 439
    int r;

440 441
    FT_MSG_S **MALLOC_N(4096,parent_messages);  // 128k / 32 = 4096
    FT_MSG_S **MALLOC_N(4096,child_messages);
442 443 444 445
    bool *MALLOC_N(4096,parent_messages_is_fresh);
    bool *MALLOC_N(4096,child_messages_is_fresh);
    memset(parent_messages_is_fresh, 0, 4096*(sizeof parent_messages_is_fresh[0]));
    memset(child_messages_is_fresh, 0, 4096*(sizeof child_messages_is_fresh[0]));
Zardosht Kasheff's avatar
Zardosht Kasheff committed
446 447 448 449 450 451 452 453 454

    XIDS xids_0 = xids_get_root_xids();
    XIDS xids_123, xids_234;
    r = xids_create_child(xids_0, &xids_123, (TXNID)123);
    CKERR(r);
    r = xids_create_child(xids_0, &xids_234, (TXNID)234);
    CKERR(r);

    NONLEAF_CHILDINFO child_bncs[8];
455
    FT_MSG childkeys[7];
Zardosht Kasheff's avatar
Zardosht Kasheff committed
456 457 458 459 460 461 462 463
    int i;
    for (i = 0; i < 8; ++i) {
        child_bncs[i] = toku_create_empty_nl();
        if (i < 7) {
            childkeys[i] = NULL;
        }
    }
    int total_size = 0;
464
    for (i = 0; total_size < 128*1024; ++i) {
465
        total_size -= toku_bnc_memory_used(child_bncs[i%8]);
Zardosht Kasheff's avatar
Zardosht Kasheff committed
466
        insert_random_message(child_bncs[i%8], &child_messages[i], &child_messages_is_fresh[i], xids_123, i%8);
467
        total_size += toku_bnc_memory_used(child_bncs[i%8]);
Zardosht Kasheff's avatar
Zardosht Kasheff committed
468 469 470 471 472 473 474 475 476
        if (i % 8 < 7) {
            if (childkeys[i%8] == NULL || dummy_cmp(NULL, child_messages[i]->u.id.key, childkeys[i%8]->u.id.key) > 0) {
                childkeys[i%8] = child_messages[i];
            }
        }
    }
    int num_child_messages = i;

    NONLEAF_CHILDINFO parent_bnc = toku_create_empty_nl();
477
    for (i = 0; toku_bnc_memory_used(parent_bnc) < 128*1024; ++i) {
Zardosht Kasheff's avatar
Zardosht Kasheff committed
478 479 480 481
        insert_random_message(parent_bnc, &parent_messages[i], &parent_messages_is_fresh[i], xids_234, 0);
    }
    int num_parent_messages = i;

482
    FTNODE XMALLOC(child);
Zardosht Kasheff's avatar
Zardosht Kasheff committed
483
    BLOCKNUM blocknum = { 42 };
Zardosht Kasheff's avatar
Zardosht Kasheff committed
484
    toku_initialize_empty_ftnode(child, blocknum, 1, 8, FT_LAYOUT_VERSION, 0);
Zardosht Kasheff's avatar
Zardosht Kasheff committed
485 486 487 488 489
    for (i = 0; i < 8; ++i) {
        destroy_nonleaf_childinfo(BNC(child, i));
        set_BNC(child, i, child_bncs[i]);
        BP_STATE(child, i) = PT_AVAIL;
        if (i < 7) {
490
            toku_clone_dbt(&child->childkeys[i], *childkeys[i]->u.id.key);
Zardosht Kasheff's avatar
Zardosht Kasheff committed
491 492 493
        }
    }

John Esmet's avatar
John Esmet committed
494
    toku_bnc_flush_to_child(t->ft, parent_bnc, child, TXNID_NONE);
Zardosht Kasheff's avatar
Zardosht Kasheff committed
495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569

    int total_messages = 0;
    for (i = 0; i < 8; ++i) {
        total_messages += toku_bnc_n_entries(BNC(child, i));
    }
    assert(total_messages == num_parent_messages + num_child_messages);
    int parent_messages_present[num_parent_messages];
    int child_messages_present[num_child_messages];
    memset(parent_messages_present, 0, sizeof parent_messages_present);
    memset(child_messages_present, 0, sizeof child_messages_present);

    for (int j = 0; j < 8; ++j) {
        FIFO_ITERATE(child_bncs[j]->buffer, key, keylen, val, vallen, type, msn, xids, is_fresh,
                     {
                         DBT keydbt;
                         DBT valdbt;
                         toku_fill_dbt(&keydbt, key, keylen);
                         toku_fill_dbt(&valdbt, val, vallen);
                         int found = 0;
                         for (i = 0; i < num_parent_messages; ++i) {
                             if (dummy_cmp(NULL, &keydbt, parent_messages[i]->u.id.key) == 0 &&
                                 msn.msn == parent_messages[i]->msn.msn) {
                                 assert(parent_messages_present[i] == 0);
                                 assert(found == 0);
                                 assert(dummy_cmp(NULL, &valdbt, parent_messages[i]->u.id.val) == 0);
                                 assert(type == parent_messages[i]->type);
                                 assert(xids_get_innermost_xid(xids) == xids_get_innermost_xid(parent_messages[i]->xids));
                                 assert(parent_messages_is_fresh[i] == is_fresh);
                                 parent_messages_present[i]++;
                                 found++;
                             }
                         }
                         for (i = 0; i < num_child_messages; ++i) {
                             if (dummy_cmp(NULL, &keydbt, child_messages[i]->u.id.key) == 0 &&
                                 msn.msn == child_messages[i]->msn.msn) {
                                 assert(child_messages_present[i] == 0);
                                 assert(found == 0);
                                 assert(dummy_cmp(NULL, &valdbt, child_messages[i]->u.id.val) == 0);
                                 assert(type == child_messages[i]->type);
                                 assert(xids_get_innermost_xid(xids) == xids_get_innermost_xid(child_messages[i]->xids));
                                 assert(child_messages_is_fresh[i] == is_fresh);
                                 child_messages_present[i]++;
                                 found++;
                             }
                         }
                         assert(found == 1);
                     });
    }

    for (i = 0; i < num_parent_messages; ++i) {
        assert(parent_messages_present[i] == 1);
    }
    for (i = 0; i < num_child_messages; ++i) {
        assert(child_messages_present[i] == 1);
    }

    xids_destroy(&xids_0);
    xids_destroy(&xids_123);
    xids_destroy(&xids_234);

    for (i = 0; i < num_parent_messages; ++i) {
        toku_free(parent_messages[i]->u.id.key->data);
        toku_free((DBT *) parent_messages[i]->u.id.key);
        toku_free(parent_messages[i]->u.id.val->data);
        toku_free((DBT *) parent_messages[i]->u.id.val);
        toku_free(parent_messages[i]);
    }
    for (i = 0; i < num_child_messages; ++i) {
        toku_free(child_messages[i]->u.id.key->data);
        toku_free((DBT *) child_messages[i]->u.id.key);
        toku_free(child_messages[i]->u.id.val->data);
        toku_free((DBT *) child_messages[i]->u.id.val);
        toku_free(child_messages[i]);
    }
    destroy_nonleaf_childinfo(parent_bnc);
570
    toku_ftnode_free(&child);
Zardosht Kasheff's avatar
Zardosht Kasheff committed
571 572 573 574 575 576
    toku_free(parent_messages);
    toku_free(child_messages);
    toku_free(parent_messages_is_fresh);
    toku_free(child_messages_is_fresh);
}

577 578 579 580 581 582 583 584
// flush from one internal node to a leaf node, which has 8 basement
// nodes
//
// if make_leaf_up_to_date is true, then apply the messages that are stale
// in the parent to the leaf before doing the flush, otherwise assume the
// leaf was just read off disk
//
// if use_flush is true, use a buffer flush, otherwise, use maybe_apply
Zardosht Kasheff's avatar
Zardosht Kasheff committed
585
static void
586
flush_to_leaf(FT_HANDLE t, bool make_leaf_up_to_date, bool use_flush) {
Zardosht Kasheff's avatar
Zardosht Kasheff committed
587 588
    int r;

589
    FT_MSG_S **MALLOC_N(4096,parent_messages);  // 128k / 32 = 4096
590 591 592 593 594
    LEAFENTRY *MALLOC_N(4096,child_messages);
    bool *MALLOC_N(4096,parent_messages_is_fresh);
    memset(parent_messages_is_fresh, 0, 4096*(sizeof parent_messages_is_fresh[0]));
    int *MALLOC_N(4096,parent_messages_applied);
    memset(parent_messages_applied, 0, 4096*(sizeof parent_messages_applied[0]));
Zardosht Kasheff's avatar
Zardosht Kasheff committed
595 596 597 598 599 600 601

    XIDS xids_0 = xids_get_root_xids();
    XIDS xids_123, xids_234;
    r = xids_create_child(xids_0, &xids_123, (TXNID)123);
    CKERR(r);
    r = xids_create_child(xids_0, &xids_234, (TXNID)234);
    CKERR(r);
602
    
Zardosht Kasheff's avatar
Zardosht Kasheff committed
603 604 605 606 607 608 609 610 611
    BASEMENTNODE child_blbs[8];
    DBT childkeys[7];
    int i;
    for (i = 0; i < 8; ++i) {
        child_blbs[i] = toku_create_empty_bn();
        if (i < 7) {
            toku_init_dbt(&childkeys[i]);
        }
    }
612

613
    FTNODE XMALLOC(child);
614
    BLOCKNUM blocknum = { 42 };
Zardosht Kasheff's avatar
Zardosht Kasheff committed
615
    toku_initialize_empty_ftnode(child, blocknum, 0, 8, FT_LAYOUT_VERSION, 0);
616 617 618 619 620 621
    for (i = 0; i < 8; ++i) {
        destroy_basement_node(BLB(child, i));
        set_BLB(child, i, child_blbs[i]);
        BP_STATE(child, i) = PT_AVAIL;
    }

Zardosht Kasheff's avatar
Zardosht Kasheff committed
622
    int total_size = 0;
623
    for (i = 0; total_size < 128*1024; ++i) {
Zardosht Kasheff's avatar
Zardosht Kasheff committed
624
        total_size -= child_blbs[i%8]->n_bytes_in_buffer;
625
        insert_random_message_to_bn(t, child_blbs[i%8], &child_messages[i], xids_123, i%8);
Zardosht Kasheff's avatar
Zardosht Kasheff committed
626 627
        total_size += child_blbs[i%8]->n_bytes_in_buffer;
        if (i % 8 < 7) {
Yoni Fogel's avatar
Yoni Fogel committed
628
            uint32_t keylen;
629
            char *CAST_FROM_VOIDP(key, le_key_and_len(child_messages[i], &keylen));
Zardosht Kasheff's avatar
Zardosht Kasheff committed
630
            DBT keydbt;
631
            if (childkeys[i%8].size == 0 || dummy_cmp(NULL, toku_fill_dbt(&keydbt, key, keylen), &childkeys[i%8]) > 0) {
Zardosht Kasheff's avatar
Zardosht Kasheff committed
632 633 634 635 636 637
                toku_fill_dbt(&childkeys[i%8], key, keylen);
            }
        }
    }
    int num_child_messages = i;

638
    for (i = 0; i < num_child_messages; ++i) {
Yoni Fogel's avatar
Yoni Fogel committed
639
        uint32_t keylen;
640
        char *CAST_FROM_VOIDP(key, le_key_and_len(child_messages[i], &keylen));
641 642 643 644 645 646 647
        DBT keydbt;
        if (i % 8 < 7) {
            assert(dummy_cmp(NULL, toku_fill_dbt(&keydbt, key, keylen), &childkeys[i%8]) <= 0);
        }
    }

    {
648 649
        int num_stale = random() % 2000;
        memset(&parent_messages_is_fresh[num_stale], true, (4096 - num_stale) * (sizeof parent_messages_is_fresh[0]));
650
    }
Zardosht Kasheff's avatar
Zardosht Kasheff committed
651
    NONLEAF_CHILDINFO parent_bnc = toku_create_empty_nl();
652
    MSN max_parent_msn = MIN_MSN;
653
    for (i = 0; toku_bnc_memory_used(parent_bnc) < 128*1024; ++i) {
654
        insert_random_update_message(parent_bnc, &parent_messages[i], parent_messages_is_fresh[i], xids_234, i%8, &parent_messages_applied[i], &max_parent_msn);
Zardosht Kasheff's avatar
Zardosht Kasheff committed
655 656 657
    }
    int num_parent_messages = i;

658
    for (i = 0; i < 7; ++i) {
659
        toku_clone_dbt(&child->childkeys[i], childkeys[i]);
Zardosht Kasheff's avatar
Zardosht Kasheff committed
660 661 662 663 664
    }

    if (make_leaf_up_to_date) {
        for (i = 0; i < num_parent_messages; ++i) {
            if (!parent_messages_is_fresh[i]) {
665
                toku_ft_leaf_apply_cmd(t->ft->compare_fun, t->ft->update_fun, &t->ft->descriptor, child, -1, parent_messages[i], make_gc_info(false), NULL, NULL);
Zardosht Kasheff's avatar
Zardosht Kasheff committed
666 667
            }
        }
668 669 670
        for (i = 0; i < 8; ++i) {
            BLB(child, i)->stale_ancestor_messages_applied = true;
        }
Zardosht Kasheff's avatar
Zardosht Kasheff committed
671
    } else {
672 673 674
        for (i = 0; i < 8; ++i) {
            BLB(child, i)->stale_ancestor_messages_applied = false;
        }
Zardosht Kasheff's avatar
Zardosht Kasheff committed
675 676
    }

677 678 679 680 681 682 683 684
    for (i = 0; i < num_parent_messages; ++i) {
        if (make_leaf_up_to_date && !parent_messages_is_fresh[i]) {
            assert(parent_messages_applied[i] == 1);
        } else {
            assert(parent_messages_applied[i] == 0);
        }
    }

Zardosht Kasheff's avatar
Zardosht Kasheff committed
685
    if (use_flush) {
John Esmet's avatar
John Esmet committed
686
        toku_bnc_flush_to_child(t->ft, parent_bnc, child, TXNID_NONE);
687
        destroy_nonleaf_childinfo(parent_bnc);
Zardosht Kasheff's avatar
Zardosht Kasheff committed
688
    } else {
689
        FTNODE XMALLOC(parentnode);
Zardosht Kasheff's avatar
Zardosht Kasheff committed
690
        BLOCKNUM parentblocknum = { 17 };
Zardosht Kasheff's avatar
Zardosht Kasheff committed
691
        toku_initialize_empty_ftnode(parentnode, parentblocknum, 1, 1, FT_LAYOUT_VERSION, 0);
692 693 694
        destroy_nonleaf_childinfo(BNC(parentnode, 0));
        set_BNC(parentnode, 0, parent_bnc);
        BP_STATE(parentnode, 0) = PT_AVAIL;
695
        parentnode->max_msn_applied_to_node_on_disk = max_parent_msn;
Zardosht Kasheff's avatar
Zardosht Kasheff committed
696 697
        struct ancestors ancestors = { .node = parentnode, .childnum = 0, .next = NULL };
        const struct pivot_bounds infinite_bounds = { .lower_bound_exclusive = NULL, .upper_bound_inclusive = NULL };
Yoni Fogel's avatar
Yoni Fogel committed
698
        bool msgs_applied;
699
        toku_apply_ancestors_messages_to_node(t, child, &ancestors, &infinite_bounds, &msgs_applied, -1);
700 701 702 703 704 705

        FIFO_ITERATE(parent_bnc->buffer, key, keylen, val, vallen, type, msn, xids, is_fresh,
                     {
                         key = key; keylen = keylen; val = val; vallen = vallen; type = type; msn = msn; xids = xids;
                         assert(!is_fresh);
                     });
706 707
        invariant(parent_bnc->fresh_message_tree.size() + parent_bnc->stale_message_tree.size()
                  == (uint32_t) num_parent_messages);
708

709
        toku_ftnode_free(&parentnode);
Zardosht Kasheff's avatar
Zardosht Kasheff committed
710 711 712 713
    }

    int total_messages = 0;
    for (i = 0; i < 8; ++i) {
714
        total_messages += toku_omt_size(BLB_BUFFER(child, i));
Zardosht Kasheff's avatar
Zardosht Kasheff committed
715
    }
716 717 718 719 720
    assert(total_messages <= num_parent_messages + num_child_messages);

    for (i = 0; i < num_parent_messages; ++i) {
        assert(parent_messages_applied[i] == 1);
    }
Zardosht Kasheff's avatar
Zardosht Kasheff committed
721

722 723 724 725
    int parent_messages_present[num_parent_messages];
    int child_messages_present[num_child_messages];
    memset(parent_messages_present, 0, sizeof parent_messages_present);
    memset(child_messages_present, 0, sizeof child_messages_present);
Zardosht Kasheff's avatar
Zardosht Kasheff committed
726
    for (int j = 0; j < 8; ++j) {
727
        OMT omt = BLB_BUFFER(child, j);
Yoni Fogel's avatar
Yoni Fogel committed
728 729
        uint32_t len = toku_omt_size(omt);
        for (uint32_t idx = 0; idx < len; ++idx) {
730 731 732 733 734 735
            LEAFENTRY le;
            DBT keydbt, valdbt;
            {
                OMTVALUE v;
                r = toku_omt_fetch(omt, idx, &v);
                assert_zero(r);
736
                CAST_FROM_VOIDP(le, v);
Yoni Fogel's avatar
Yoni Fogel committed
737
                uint32_t keylen, vallen;
738 739 740 741 742 743 744 745 746
                void *keyp = le_key_and_len(le, &keylen);
                void *valp = le_latest_val_and_len(le, &vallen);
                toku_fill_dbt(&keydbt, keyp, keylen);
                toku_fill_dbt(&valdbt, valp, vallen);
            }
            int found = 0;
            for (i = num_parent_messages - 1; i >= 0; --i) {
                if (dummy_cmp(NULL, &keydbt, parent_messages[i]->u.id.key) == 0) {
                    if (found == 0) {
747
                        struct orthopush_flush_update_fun_extra *CAST_FROM_VOIDP(e, parent_messages[i]->u.id.val->data);
748 749 750 751 752 753 754
                        assert(dummy_cmp(NULL, &valdbt, &e->new_val) == 0);
                        found++;
                    }
                    assert(parent_messages_present[i] == 0);
                    parent_messages_present[i]++;
                }
            }
755 756
            for (i = j + (~7 & (num_child_messages - 1)); i >= 0; i -= 8) {
                if (i >= num_child_messages) { continue; }
757 758
                DBT childkeydbt, childvaldbt;
                {
Yoni Fogel's avatar
Yoni Fogel committed
759
                    uint32_t keylen, vallen;
760 761 762 763 764 765 766 767 768 769 770 771 772 773 774
                    void *keyp = le_key_and_len(child_messages[i], &keylen);
                    void *valp = le_latest_val_and_len(child_messages[i], &vallen);
                    toku_fill_dbt(&childkeydbt, keyp, keylen);
                    toku_fill_dbt(&childvaldbt, valp, vallen);
                }
                if (dummy_cmp(NULL, &keydbt, &childkeydbt) == 0) {
                    if (found == 0) {
                        assert(dummy_cmp(NULL, &valdbt, &childvaldbt) == 0);
                        found++;
                    }
                    assert(child_messages_present[i] == 0);
                    child_messages_present[i]++;
                }
            }
        }
Zardosht Kasheff's avatar
Zardosht Kasheff committed
775 776 777 778 779 780 781 782 783 784 785 786 787 788 789 790
    }

    for (i = 0; i < num_parent_messages; ++i) {
        assert(parent_messages_present[i] == 1);
    }
    for (i = 0; i < num_child_messages; ++i) {
        assert(child_messages_present[i] == 1);
    }

    xids_destroy(&xids_0);
    xids_destroy(&xids_123);
    xids_destroy(&xids_234);

    for (i = 0; i < num_parent_messages; ++i) {
        toku_free(parent_messages[i]->u.id.key->data);
        toku_free((DBT *) parent_messages[i]->u.id.key);
791
        struct orthopush_flush_update_fun_extra *CAST_FROM_VOIDP(extra, parent_messages[i]->u.id.val->data);
792
        toku_free(extra->new_val.data);
Zardosht Kasheff's avatar
Zardosht Kasheff committed
793 794 795 796 797 798 799
        toku_free(parent_messages[i]->u.id.val->data);
        toku_free((DBT *) parent_messages[i]->u.id.val);
        toku_free(parent_messages[i]);
    }
    for (i = 0; i < num_child_messages; ++i) {
        toku_free(child_messages[i]);
    }
800
    toku_ftnode_free(&child);
Zardosht Kasheff's avatar
Zardosht Kasheff committed
801 802 803
    toku_free(parent_messages);
    toku_free(child_messages);
    toku_free(parent_messages_is_fresh);
804 805 806
    toku_free(parent_messages_applied);
}

807 808 809 810 811 812
// flush from one internal node to a leaf node, which has 8 basement
// nodes, but only using maybe_apply, and with actual pivot bounds
//
// if make_leaf_up_to_date is true, then apply the messages that are stale
// in the parent to the leaf before doing the flush, otherwise assume the
// leaf was just read off disk
813
static void
814
flush_to_leaf_with_keyrange(FT_HANDLE t, bool make_leaf_up_to_date) {
815 816
    int r;

817
    FT_MSG_S **MALLOC_N(4096,parent_messages);  // 128k / 32 = 4k
818 819 820 821 822
    LEAFENTRY *MALLOC_N(4096,child_messages);
    bool *MALLOC_N(4096,parent_messages_is_fresh);
    memset(parent_messages_is_fresh, 0, 4096*(sizeof parent_messages_is_fresh[0]));
    int *MALLOC_N(4096,parent_messages_applied);
    memset(parent_messages_applied, 0, 4096*(sizeof parent_messages_applied[0]));
823 824 825 826 827 828 829 830 831 832 833 834 835 836 837 838

    XIDS xids_0 = xids_get_root_xids();
    XIDS xids_123, xids_234;
    r = xids_create_child(xids_0, &xids_123, (TXNID)123);
    CKERR(r);
    r = xids_create_child(xids_0, &xids_234, (TXNID)234);
    CKERR(r);

    BASEMENTNODE child_blbs[8];
    DBT childkeys[8];
    int i;
    for (i = 0; i < 8; ++i) {
        child_blbs[i] = toku_create_empty_bn();
        toku_init_dbt(&childkeys[i]);
    }

839
    FTNODE XMALLOC(child);
840
    BLOCKNUM blocknum = { 42 };
Zardosht Kasheff's avatar
Zardosht Kasheff committed
841
    toku_initialize_empty_ftnode(child, blocknum, 0, 8, FT_LAYOUT_VERSION, 0);
842 843 844 845 846 847 848
    for (i = 0; i < 8; ++i) {
        destroy_basement_node(BLB(child, i));
        set_BLB(child, i, child_blbs[i]);
        BP_STATE(child, i) = PT_AVAIL;
    }

    int total_size = 0;
849
    for (i = 0; total_size < 128*1024; ++i) {
850
        total_size -= child_blbs[i%8]->n_bytes_in_buffer;
851
        insert_random_message_to_bn(t, child_blbs[i%8], &child_messages[i], xids_123, i%8);
852
        total_size += child_blbs[i%8]->n_bytes_in_buffer;
Yoni Fogel's avatar
Yoni Fogel committed
853
        uint32_t keylen;
854
        char *CAST_FROM_VOIDP(key, le_key_and_len(child_messages[i], &keylen));
855 856 857 858 859 860 861 862
        DBT keydbt;
        if (childkeys[i%8].size == 0 || dummy_cmp(NULL, toku_fill_dbt(&keydbt, key, keylen), &childkeys[i%8]) > 0) {
            toku_fill_dbt(&childkeys[i%8], key, keylen);
        }
    }
    int num_child_messages = i;

    for (i = 0; i < num_child_messages; ++i) {
Yoni Fogel's avatar
Yoni Fogel committed
863
        uint32_t keylen;
864
        char *CAST_FROM_VOIDP(key, le_key_and_len(child_messages[i], &keylen));
865 866 867 868 869
        DBT keydbt;
        assert(dummy_cmp(NULL, toku_fill_dbt(&keydbt, key, keylen), &childkeys[i%8]) <= 0);
    }

    {
870 871
        int num_stale = random() % 2000;
        memset(&parent_messages_is_fresh[num_stale], true, (4096 - num_stale) * (sizeof parent_messages_is_fresh[0]));
872 873 874
    }
    NONLEAF_CHILDINFO parent_bnc = toku_create_empty_nl();
    MSN max_parent_msn = MIN_MSN;
875
    for (i = 0; toku_bnc_memory_used(parent_bnc) < 128*1024; ++i) {
876 877 878 879 880
        insert_random_update_message(parent_bnc, &parent_messages[i], parent_messages_is_fresh[i], xids_234, i%8, &parent_messages_applied[i], &max_parent_msn);
    }
    int num_parent_messages = i;

    for (i = 0; i < 7; ++i) {
881
        toku_clone_dbt(&child->childkeys[i], childkeys[i]);
882 883 884 885 886 887
    }

    if (make_leaf_up_to_date) {
        for (i = 0; i < num_parent_messages; ++i) {
            if (dummy_cmp(NULL, parent_messages[i]->u.id.key, &childkeys[7]) <= 0 &&
                !parent_messages_is_fresh[i]) {
888
                toku_ft_leaf_apply_cmd(t->ft->compare_fun, t->ft->update_fun, &t->ft->descriptor, child, -1, parent_messages[i], make_gc_info(false), NULL, NULL);
889 890 891 892 893 894 895 896 897 898 899 900
            }
        }
        for (i = 0; i < 8; ++i) {
            BLB(child, i)->stale_ancestor_messages_applied = true;
        }
    } else {
        for (i = 0; i < 8; ++i) {
            BLB(child, i)->stale_ancestor_messages_applied = false;
        }
    }

    for (i = 0; i < num_parent_messages; ++i) {
901 902 903
        if (make_leaf_up_to_date &&
            dummy_cmp(NULL, parent_messages[i]->u.id.key, &childkeys[7]) <= 0 &&
            !parent_messages_is_fresh[i]) {
904 905 906 907 908 909
            assert(parent_messages_applied[i] == 1);
        } else {
            assert(parent_messages_applied[i] == 0);
        }
    }

910
    FTNODE XMALLOC(parentnode);
911
    BLOCKNUM parentblocknum = { 17 };
Zardosht Kasheff's avatar
Zardosht Kasheff committed
912
    toku_initialize_empty_ftnode(parentnode, parentblocknum, 1, 1, FT_LAYOUT_VERSION, 0);
913 914 915 916 917
    destroy_nonleaf_childinfo(BNC(parentnode, 0));
    set_BNC(parentnode, 0, parent_bnc);
    BP_STATE(parentnode, 0) = PT_AVAIL;
    parentnode->max_msn_applied_to_node_on_disk = max_parent_msn;
    struct ancestors ancestors = { .node = parentnode, .childnum = 0, .next = NULL };
918 919 920 921 922
    DBT lbe, ubi;
    const struct pivot_bounds bounds = {
        .lower_bound_exclusive = toku_init_dbt(&lbe),
        .upper_bound_inclusive = toku_clone_dbt(&ubi, childkeys[7])
    };
Yoni Fogel's avatar
Yoni Fogel committed
923
    bool msgs_applied;
924
    toku_apply_ancestors_messages_to_node(t, child, &ancestors, &bounds, &msgs_applied, -1);
925 926 927 928 929 930 931 932 933 934 935 936 937 938 939 940 941 942 943

    FIFO_ITERATE(parent_bnc->buffer, key, keylen, val, vallen, type, msn, xids, is_fresh,
                 {
                     val = val; vallen = vallen; type = type; msn = msn; xids = xids;
                     DBT keydbt;
                     toku_fill_dbt(&keydbt, key, keylen);
                     if (dummy_cmp(NULL, &keydbt, &childkeys[7]) > 0) {
                         for (i = 0; i < num_parent_messages; ++i) {
                             if (dummy_cmp(NULL, &keydbt, parent_messages[i]->u.id.key) == 0 &&
                                 msn.msn == parent_messages[i]->msn.msn) {
                                 assert(is_fresh == parent_messages_is_fresh[i]);
                                 break;
                             }
                         }
                     } else {
                         assert(!is_fresh);
                     }
                 });

944
    toku_ftnode_free(&parentnode);
945 946 947 948 949 950 951 952 953 954 955 956 957 958 959 960 961 962 963 964 965 966

    int total_messages = 0;
    for (i = 0; i < 8; ++i) {
        total_messages += toku_omt_size(BLB_BUFFER(child, i));
    }
    assert(total_messages <= num_parent_messages + num_child_messages);

    for (i = 0; i < num_parent_messages; ++i) {
        if (dummy_cmp(NULL, parent_messages[i]->u.id.key, &childkeys[7]) <= 0) {
            assert(parent_messages_applied[i] == 1);
        } else {
            assert(parent_messages_applied[i] == 0);
        }
    }

    xids_destroy(&xids_0);
    xids_destroy(&xids_123);
    xids_destroy(&xids_234);

    for (i = 0; i < num_parent_messages; ++i) {
        toku_free(parent_messages[i]->u.id.key->data);
        toku_free((DBT *) parent_messages[i]->u.id.key);
967
        struct orthopush_flush_update_fun_extra *CAST_FROM_VOIDP(extra, parent_messages[i]->u.id.val->data);
968 969 970 971 972 973 974 975
        toku_free(extra->new_val.data);
        toku_free(parent_messages[i]->u.id.val->data);
        toku_free((DBT *) parent_messages[i]->u.id.val);
        toku_free(parent_messages[i]);
    }
    for (i = 0; i < num_child_messages; ++i) {
        toku_free(child_messages[i]);
    }
976
    toku_free(ubi.data);
977
    toku_ftnode_free(&child);
978 979 980 981 982 983
    toku_free(parent_messages);
    toku_free(child_messages);
    toku_free(parent_messages_is_fresh);
    toku_free(parent_messages_applied);
}

984 985 986 987 988 989 990
// create identical leaf nodes and then buffer flush to one and
// maybe_apply to the other, and compare the results, they should be the
// same.
//
// if make_leaf_up_to_date is true, then apply the messages that are stale
// in the parent to the leaf before doing the flush, otherwise assume the
// leaf was just read off disk
991
static void
992
compare_apply_and_flush(FT_HANDLE t, bool make_leaf_up_to_date) {
993 994
    int r;

995
    FT_MSG_S **MALLOC_N(4096,parent_messages);  // 128k / 32 = 4k
996 997 998 999 1000
    LEAFENTRY *MALLOC_N(4096,child_messages);
    bool *MALLOC_N(4096,parent_messages_is_fresh);
    memset(parent_messages_is_fresh, 0, 4096*(sizeof parent_messages_is_fresh[0]));
    int *MALLOC_N(4096,parent_messages_applied);
    memset(parent_messages_applied, 0, 4096*(sizeof parent_messages_applied[0]));
1001 1002 1003 1004 1005 1006 1007 1008 1009 1010 1011 1012 1013 1014 1015 1016 1017 1018 1019 1020

    XIDS xids_0 = xids_get_root_xids();
    XIDS xids_123, xids_234;
    r = xids_create_child(xids_0, &xids_123, (TXNID)123);
    CKERR(r);
    r = xids_create_child(xids_0, &xids_234, (TXNID)234);
    CKERR(r);

    BASEMENTNODE child1_blbs[8], child2_blbs[8];
    DBT child1keys[7], child2keys[7];
    int i;
    for (i = 0; i < 8; ++i) {
        child1_blbs[i] = toku_create_empty_bn();
        child2_blbs[i] = toku_create_empty_bn();
        if (i < 7) {
            toku_init_dbt(&child1keys[i]);
            toku_init_dbt(&child2keys[i]);
        }
    }

1021
    FTNODE XMALLOC(child1), XMALLOC(child2);
1022
    BLOCKNUM blocknum = { 42 };
Zardosht Kasheff's avatar
Zardosht Kasheff committed
1023 1024
    toku_initialize_empty_ftnode(child1, blocknum, 0, 8, FT_LAYOUT_VERSION, 0);
    toku_initialize_empty_ftnode(child2, blocknum, 0, 8, FT_LAYOUT_VERSION, 0);
1025 1026 1027 1028 1029 1030 1031 1032 1033 1034
    for (i = 0; i < 8; ++i) {
        destroy_basement_node(BLB(child1, i));
        set_BLB(child1, i, child1_blbs[i]);
        BP_STATE(child1, i) = PT_AVAIL;
        destroy_basement_node(BLB(child2, i));
        set_BLB(child2, i, child2_blbs[i]);
        BP_STATE(child2, i) = PT_AVAIL;
    }

    int total_size = 0;
1035
    for (i = 0; total_size < 128*1024; ++i) {
1036
        total_size -= child1_blbs[i%8]->n_bytes_in_buffer;
1037
        insert_same_message_to_bns(t, child1_blbs[i%8], child2_blbs[i%8], &child_messages[i], xids_123, i%8);
1038 1039
        total_size += child1_blbs[i%8]->n_bytes_in_buffer;
        if (i % 8 < 7) {
Yoni Fogel's avatar
Yoni Fogel committed
1040
            uint32_t keylen;
1041
            char *CAST_FROM_VOIDP(key, le_key_and_len(child_messages[i], &keylen));
1042 1043 1044 1045 1046 1047 1048 1049 1050 1051
            DBT keydbt;
            if (child1keys[i%8].size == 0 || dummy_cmp(NULL, toku_fill_dbt(&keydbt, key, keylen), &child1keys[i%8]) > 0) {
                toku_fill_dbt(&child1keys[i%8], key, keylen);
                toku_fill_dbt(&child2keys[i%8], key, keylen);
            }
        }
    }
    int num_child_messages = i;

    for (i = 0; i < num_child_messages; ++i) {
Yoni Fogel's avatar
Yoni Fogel committed
1052
        uint32_t keylen;
1053
        char *CAST_FROM_VOIDP(key, le_key_and_len(child_messages[i], &keylen));
1054 1055 1056 1057 1058 1059 1060 1061
        DBT keydbt;
        if (i % 8 < 7) {
            assert(dummy_cmp(NULL, toku_fill_dbt(&keydbt, key, keylen), &child1keys[i%8]) <= 0);
            assert(dummy_cmp(NULL, toku_fill_dbt(&keydbt, key, keylen), &child2keys[i%8]) <= 0);
        }
    }

    {
1062 1063
        int num_stale = random() % 2000;
        memset(&parent_messages_is_fresh[num_stale], true, (4096 - num_stale) * (sizeof parent_messages_is_fresh[0]));
1064 1065 1066
    }
    NONLEAF_CHILDINFO parent_bnc = toku_create_empty_nl();
    MSN max_parent_msn = MIN_MSN;
1067
    for (i = 0; toku_bnc_memory_used(parent_bnc) < 128*1024; ++i) {
1068 1069 1070 1071 1072
        insert_random_update_message(parent_bnc, &parent_messages[i], parent_messages_is_fresh[i], xids_234, i%8, &parent_messages_applied[i], &max_parent_msn);
    }
    int num_parent_messages = i;

    for (i = 0; i < 7; ++i) {
1073 1074
        toku_clone_dbt(&child1->childkeys[i], child1keys[i]);
        toku_clone_dbt(&child2->childkeys[i], child2keys[i]);
1075 1076 1077 1078 1079
    }

    if (make_leaf_up_to_date) {
        for (i = 0; i < num_parent_messages; ++i) {
            if (!parent_messages_is_fresh[i]) {
1080 1081
                toku_ft_leaf_apply_cmd(t->ft->compare_fun, t->ft->update_fun, &t->ft->descriptor, child1, -1, parent_messages[i], make_gc_info(false), NULL, NULL);
                toku_ft_leaf_apply_cmd(t->ft->compare_fun, t->ft->update_fun, &t->ft->descriptor, child2, -1, parent_messages[i], make_gc_info(false), NULL, NULL);
1082 1083 1084 1085 1086 1087 1088 1089 1090 1091 1092 1093 1094
            }
        }
        for (i = 0; i < 8; ++i) {
            BLB(child1, i)->stale_ancestor_messages_applied = true;
            BLB(child2, i)->stale_ancestor_messages_applied = true;
        }
    } else {
        for (i = 0; i < 8; ++i) {
            BLB(child1, i)->stale_ancestor_messages_applied = false;
            BLB(child2, i)->stale_ancestor_messages_applied = false;
        }
    }

John Esmet's avatar
John Esmet committed
1095
    toku_bnc_flush_to_child(t->ft, parent_bnc, child1, TXNID_NONE);
1096

1097
    FTNODE XMALLOC(parentnode);
1098
    BLOCKNUM parentblocknum = { 17 };
Zardosht Kasheff's avatar
Zardosht Kasheff committed
1099
    toku_initialize_empty_ftnode(parentnode, parentblocknum, 1, 1, FT_LAYOUT_VERSION, 0);
1100 1101 1102 1103 1104 1105
    destroy_nonleaf_childinfo(BNC(parentnode, 0));
    set_BNC(parentnode, 0, parent_bnc);
    BP_STATE(parentnode, 0) = PT_AVAIL;
    parentnode->max_msn_applied_to_node_on_disk = max_parent_msn;
    struct ancestors ancestors = { .node = parentnode, .childnum = 0, .next = NULL };
    const struct pivot_bounds infinite_bounds = { .lower_bound_exclusive = NULL, .upper_bound_inclusive = NULL };
Yoni Fogel's avatar
Yoni Fogel committed
1106
    bool msgs_applied;
1107
    toku_apply_ancestors_messages_to_node(t, child2, &ancestors, &infinite_bounds, &msgs_applied, -1);
1108 1109 1110 1111 1112 1113

    FIFO_ITERATE(parent_bnc->buffer, key, keylen, val, vallen, type, msn, xids, is_fresh,
                 {
                     key = key; keylen = keylen; val = val; vallen = vallen; type = type; msn = msn; xids = xids;
                     assert(!is_fresh);
                 });
1114 1115
    invariant(parent_bnc->fresh_message_tree.size() + parent_bnc->stale_message_tree.size()
              == (uint32_t) num_parent_messages);
1116

1117
    toku_ftnode_free(&parentnode);
1118 1119 1120 1121

    for (int j = 0; j < 8; ++j) {
        OMT omt1 = BLB_BUFFER(child1, j);
        OMT omt2 = BLB_BUFFER(child2, j);
Yoni Fogel's avatar
Yoni Fogel committed
1122
        uint32_t len = toku_omt_size(omt1);
1123
        assert(len == toku_omt_size(omt2));
Yoni Fogel's avatar
Yoni Fogel committed
1124
        for (uint32_t idx = 0; idx < len; ++idx) {
1125 1126 1127 1128 1129 1130
            LEAFENTRY le1, le2;
            DBT key1dbt, val1dbt, key2dbt, val2dbt;
            {
                OMTVALUE v;
                r = toku_omt_fetch(omt1, idx, &v);
                assert_zero(r);
1131
                CAST_FROM_VOIDP(le1, v);
Yoni Fogel's avatar
Yoni Fogel committed
1132
                uint32_t keylen, vallen;
1133 1134 1135 1136 1137 1138 1139 1140 1141
                void *keyp = le_key_and_len(le1, &keylen);
                void *valp = le_latest_val_and_len(le1, &vallen);
                toku_fill_dbt(&key1dbt, keyp, keylen);
                toku_fill_dbt(&val1dbt, valp, vallen);
            }
            {
                OMTVALUE v;
                r = toku_omt_fetch(omt2, idx, &v);
                assert_zero(r);
1142
                CAST_FROM_VOIDP(le2, v);
Yoni Fogel's avatar
Yoni Fogel committed
1143
                uint32_t keylen, vallen;
1144 1145 1146 1147 1148 1149 1150 1151 1152 1153 1154 1155 1156 1157 1158 1159 1160
                void *keyp = le_key_and_len(le2, &keylen);
                void *valp = le_latest_val_and_len(le2, &vallen);
                toku_fill_dbt(&key2dbt, keyp, keylen);
                toku_fill_dbt(&val2dbt, valp, vallen);
            }
            assert(dummy_cmp(NULL, &key1dbt, &key2dbt) == 0);
            assert(dummy_cmp(NULL, &val1dbt, &val2dbt) == 0);
        }
    }

    xids_destroy(&xids_0);
    xids_destroy(&xids_123);
    xids_destroy(&xids_234);

    for (i = 0; i < num_parent_messages; ++i) {
        toku_free(parent_messages[i]->u.id.key->data);
        toku_free((DBT *) parent_messages[i]->u.id.key);
1161
        struct orthopush_flush_update_fun_extra *CAST_FROM_VOIDP(extra, parent_messages[i]->u.id.val->data);
1162 1163 1164 1165 1166 1167 1168 1169
        toku_free(extra->new_val.data);
        toku_free(parent_messages[i]->u.id.val->data);
        toku_free((DBT *) parent_messages[i]->u.id.val);
        toku_free(parent_messages[i]);
    }
    for (i = 0; i < num_child_messages; ++i) {
        toku_free(child_messages[i]);
    }
1170 1171
    toku_ftnode_free(&child1);
    toku_ftnode_free(&child2);
1172 1173 1174 1175 1176 1177
    toku_free(parent_messages);
    toku_free(child_messages);
    toku_free(parent_messages_is_fresh);
    toku_free(parent_messages_applied);
}

1178 1179 1180 1181 1182 1183 1184 1185 1186 1187 1188 1189 1190 1191 1192
static void
parse_args(int argc, const char *argv[]) {
    const char *progname=argv[0];
    argc--; argv++;
    while (argc>0) {
        if (strcmp(argv[0],"-v")==0) {
            verbose=1;
        } else if (strcmp(argv[0],"-q")==0) {
            verbose=0;
        } else {
            fprintf(stderr, "Usage:\n %s [-v] [-q]\n", progname);
            exit(1);
        }
        argc--; argv++;
    }
Zardosht Kasheff's avatar
Zardosht Kasheff committed
1193 1194 1195 1196
}

int
test_main (int argc, const char *argv[]) {
1197
    parse_args(argc, argv);
Zardosht Kasheff's avatar
Zardosht Kasheff committed
1198

1199
    initialize_dummymsn();
Zardosht Kasheff's avatar
Zardosht Kasheff committed
1200 1201
    int r;
    CACHETABLE ct;
1202
    toku_cachetable_create(&ct, 0, ZERO_LSN, NULL_LOGGER);
Zardosht Kasheff's avatar
Zardosht Kasheff committed
1203
    unlink(fname);
1204 1205
    FT_HANDLE t;
    r = toku_open_ft_handle(fname, 1, &t, 128*1024, 4096, TOKU_DEFAULT_COMPRESSION_METHOD, ct, null_txn, toku_builtin_compare_fun); assert(r==0);
1206
    toku_ft_set_update(t, orthopush_flush_update_fun);
1207
    // HACK
1208
    t->ft->update_fun = orthopush_flush_update_fun;
Zardosht Kasheff's avatar
Zardosht Kasheff committed
1209

1210
    for (int i = 0; i < 10; ++i) {
Zardosht Kasheff's avatar
Zardosht Kasheff committed
1211
        flush_to_internal(t);
1212 1213
    }
    for (int i = 0; i < 10; ++i) {
Zardosht Kasheff's avatar
Zardosht Kasheff committed
1214
        flush_to_internal_multiple(t);
1215 1216 1217 1218
    }
    for (int i = 0; i < 3; ++i) {
        flush_to_leaf(t, false, false);
        flush_to_leaf(t, false, true);
Zardosht Kasheff's avatar
Zardosht Kasheff committed
1219
        flush_to_leaf(t, true, false);
1220 1221 1222
        flush_to_leaf(t, true, true);
    }
    for (int i = 0; i < 10; ++i) {
1223 1224
        flush_to_leaf_with_keyrange(t, false);
        flush_to_leaf_with_keyrange(t, true);
1225 1226
        compare_apply_and_flush(t, false);
        compare_apply_and_flush(t, true);
Zardosht Kasheff's avatar
Zardosht Kasheff committed
1227 1228
    }

1229
    r = toku_close_ft_handle_nolsn(t, 0);          assert(r==0);
1230
    toku_cachetable_close(&ct);
Zardosht Kasheff's avatar
Zardosht Kasheff committed
1231 1232 1233

    return 0;
}