btree/bt_stat.c

   1 /*-
   2  * See the file LICENSE for redistribution information.
   3  *
   4  * Copyright (c) 1996-2009 Oracle.  All rights reserved.
   5  *
   6  * $Id$
   7  */
   8
   9 #include "db_config.h"
  10
  11 #include "db_int.h"
  12 #include "dbinc/db_page.h"
  13 #include "dbinc/btree.h"
  14 #include "dbinc/lock.h"
  15 #include "dbinc/mp.h"
  16 #include "dbinc/partition.h"
  17
  18 #ifdef HAVE_STATISTICS
  19 /*
  20  * __bam_stat --
  21  *      Gather/print the btree statistics
  22  *
  23  * PUBLIC: int __bam_stat __P((DBC *, void *, u_int32_t));
  24  */
  25 int
  26 __bam_stat(dbc, spp, flags)
  27         DBC *dbc;
  28         void *spp;
  29         u_int32_t flags;
  30 {
  31         BTMETA *meta;
  32         BTREE *t;
  33         BTREE_CURSOR *cp;
  34         DB *dbp;
  35         DB_BTREE_STAT *sp;
  36         DB_LOCK lock, metalock;
  37         DB_MPOOLFILE *mpf;
  38         ENV *env;
  39         PAGE *h;
  40         db_pgno_t pgno;
  41         int ret, t_ret, write_meta;
  42
  43         dbp = dbc->dbp;
  44         env = dbp->env;
  45
  46         meta = NULL;
  47         t = dbp->bt_internal;
  48         sp = NULL;
  49         LOCK_INIT(metalock);
  50         LOCK_INIT(lock);
  51         mpf = dbp->mpf;
  52         h = NULL;
  53         ret = write_meta = 0;
  54
  55         cp = (BTREE_CURSOR *)dbc->internal;
  56
  57         /* Allocate and clear the structure. */
  58         if ((ret = __os_umalloc(env, sizeof(*sp), &sp)) != 0)
  59                 goto err;
  60         memset(sp, 0, sizeof(*sp));
  61
  62         /* Get the metadata page for the entire database. */
  63         pgno = PGNO_BASE_MD;
  64         if ((ret = __db_lget(dbc, 0, pgno, DB_LOCK_READ, 0, &metalock)) != 0)
  65                 goto err;
  66         if ((ret = __memp_fget(mpf, &pgno,
  67              dbc->thread_info, dbc->txn, 0, &meta)) != 0)
  68                 goto err;
  69
  70         if (flags == DB_FAST_STAT)
  71                 goto meta_only;
  72
  73         /* Walk the metadata free list, counting pages. */
  74         for (sp->bt_free = 0, pgno = meta->dbmeta.free; pgno != PGNO_INVALID;) {
  75                 ++sp->bt_free;
  76
  77                 if ((ret = __memp_fget(mpf, &pgno,
  78                      dbc->thread_info, dbc->txn, 0, &h)) != 0)
  79                         goto err;
  80
  81                 pgno = h->next_pgno;
  82                 if ((ret = __memp_fput(mpf,
  83                     dbc->thread_info, h, dbc->priority)) != 0)
  84                         goto err;
  85                 h = NULL;
  86         }
  87
  88         /* Get the root page. */
  89         pgno = cp->root;
  90         if ((ret = __db_lget(dbc, 0, pgno, DB_LOCK_READ, 0, &lock)) != 0)
  91                 goto err;
  92         if ((ret = __memp_fget(mpf, &pgno,
  93              dbc->thread_info, dbc->txn, 0, &h)) != 0)
  94                 goto err;
  95
  96         /* Get the levels from the root page. */
  97         sp->bt_levels = h->level;
  98
  99         /* Discard the root page. */
 100         ret = __memp_fput(mpf, dbc->thread_info, h, dbc->priority);
 101         h = NULL;
 102         if ((t_ret = __LPUT(dbc, lock)) != 0 && ret == 0)
 103                 ret = t_ret;
 104         if (ret != 0)
 105                 goto err;
 106
 107         /* Walk the tree. */
 108         if ((ret = __bam_traverse(dbc,
 109             DB_LOCK_READ, cp->root, __bam_stat_callback, sp)) != 0)
 110                 goto err;
 111
 112 #ifdef HAVE_COMPRESSION
 113         if (DB_IS_COMPRESSED(dbp) && (ret = __bam_compress_count(dbc,
 114             &sp->bt_nkeys, &sp->bt_ndata)) != 0)
 115                 goto err;
 116 #endif
 117
 118         /*
 119          * Get the subdatabase metadata page if it's not the same as the
 120          * one we already have.
 121          */
 122         write_meta = !F_ISSET(dbp, DB_AM_RDONLY) &&
 123             (!MULTIVERSION(dbp) || dbc->txn != NULL);
 124 meta_only:
 125         if (t->bt_meta != PGNO_BASE_MD || write_meta) {
 126                 ret = __memp_fput(mpf, dbc->thread_info, meta, dbc->priority);
 127                 meta = NULL;
 128                 if ((t_ret = __LPUT(dbc, metalock)) != 0 && ret == 0)
 129                         ret = t_ret;
 130                 if (ret != 0)
 131                         goto err;
 132
 133                 if ((ret = __db_lget(dbc,
 134                     0, t->bt_meta, write_meta ? DB_LOCK_WRITE : DB_LOCK_READ,
 135                     0, &metalock)) != 0)
 136                         goto err;
 137                 if ((ret = __memp_fget(mpf, &t->bt_meta,
 138                      dbc->thread_info, dbc->txn,
 139                     write_meta ? DB_MPOOL_DIRTY : 0, &meta)) != 0)
 140                         goto err;
 141         }
 142         if (flags == DB_FAST_STAT) {
 143                 if (dbp->type == DB_RECNO ||
 144                     (dbp->type == DB_BTREE && F_ISSET(dbp, DB_AM_RECNUM))) {
 145                         if ((ret = __db_lget(dbc, 0,
 146                             cp->root, DB_LOCK_READ, 0, &lock)) != 0)
 147                                 goto err;
 148                         if ((ret = __memp_fget(mpf, &cp->root,
 149                              dbc->thread_info, dbc->txn, 0, &h)) != 0)
 150                                 goto err;
 151
 152                         sp->bt_nkeys = RE_NREC(h);
 153                 } else
 154                         sp->bt_nkeys = meta->dbmeta.key_count;
 155
 156                 sp->bt_ndata = dbp->type == DB_RECNO ?
 157                    sp->bt_nkeys : meta->dbmeta.record_count;
 158         }
 159
 160         /* Get metadata page statistics. */
 161         sp->bt_metaflags = meta->dbmeta.flags;
 162         sp->bt_minkey = meta->minkey;
 163         sp->bt_re_len = meta->re_len;
 164         sp->bt_re_pad = meta->re_pad;
 165         /*
 166          * Don't take the page number from the meta-data page -- that value is
 167          * only maintained in the primary database, we may have been called on
 168          * a subdatabase.  (Yes, I read the primary database meta-data page
 169          * earlier in this function, but I'm asking the underlying cache so the
 170          * code for the Hash and Btree methods is the same.)
 171          */
 172         if ((ret = __memp_get_last_pgno(dbp->mpf, &pgno)) != 0)
 173                 goto err;
 174         sp->bt_pagecnt = pgno + 1;
 175         sp->bt_pagesize = meta->dbmeta.pagesize;
 176         sp->bt_magic = meta->dbmeta.magic;
 177         sp->bt_version = meta->dbmeta.version;
 178
 179         if (write_meta != 0) {
 180                 meta->dbmeta.key_count = sp->bt_nkeys;
 181                 meta->dbmeta.record_count = sp->bt_ndata;
 182         }
 183
 184         *(DB_BTREE_STAT **)spp = sp;
 185
 186 err:    /* Discard the second page. */
 187         if ((t_ret = __LPUT(dbc, lock)) != 0 && ret == 0)
 188                 ret = t_ret;
 189         if (h != NULL && (t_ret = __memp_fput(mpf,
 190             dbc->thread_info, h, dbc->priority)) != 0 && ret == 0)
 191                 ret = t_ret;
 192
 193         /* Discard the metadata page. */
 194         if ((t_ret = __LPUT(dbc, metalock)) != 0 && ret == 0)
 195                 ret = t_ret;
 196         if (meta != NULL && (t_ret = __memp_fput(mpf,
 197             dbc->thread_info, meta, dbc->priority)) != 0 && ret == 0)
 198                 ret = t_ret;
 199
 200         if (ret != 0 && sp != NULL) {
 201                 __os_ufree(env, sp);
 202                 *(DB_BTREE_STAT **)spp = NULL;
 203         }
 204
 205         return (ret);
 206 }
 207
 208 /*
 209  * __bam_stat_print --
 210  *      Display btree/recno statistics.
 211  *
 212  * PUBLIC: int __bam_stat_print __P((DBC *, u_int32_t));
 213  */
 214 int
 215 __bam_stat_print(dbc, flags)
 216         DBC *dbc;
 217         u_int32_t flags;
 218 {
 219         static const FN fn[] = {
 220                 { BTM_DUP,      "duplicates" },
 221                 { BTM_RECNO,    "recno" },
 222                 { BTM_RECNUM,   "record-numbers" },
 223                 { BTM_FIXEDLEN, "fixed-length" },
 224                 { BTM_RENUMBER, "renumber" },
 225                 { BTM_SUBDB,    "multiple-databases" },
 226                 { BTM_DUPSORT,  "sorted duplicates" },
 227                 { BTM_COMPRESS, "compressed" },
 228                 { 0,            NULL }
 229         };
 230         DB *dbp;
 231         DB_BTREE_STAT *sp;
 232         ENV *env;
 233         int lorder, ret;
 234         const char *s;
 235
 236         dbp = dbc->dbp;
 237         env = dbp->env;
 238 #ifdef HAVE_PARTITION
 239         if (DB_IS_PARTITIONED(dbp)) {
 240                 if ((ret = __partition_stat(dbc, &sp, flags)) != 0)
 241                         return (ret);
 242         } else
 243 #endif
 244         if ((ret = __bam_stat(dbc, &sp, LF_ISSET(DB_FAST_STAT))) != 0)
 245                 return (ret);
 246
 247         if (LF_ISSET(DB_STAT_ALL)) {
 248                 __db_msg(env, "%s", DB_GLOBAL(db_line));
 249                 __db_msg(env, "Default Btree/Recno database information:");
 250         }
 251
 252         __db_msg(env, "%lx\tBtree magic number", (u_long)sp->bt_magic);
 253         __db_msg(env, "%lu\tBtree version number", (u_long)sp->bt_version);
 254
 255         (void)__db_get_lorder(dbp, &lorder);
 256         switch (lorder) {
 257         case 1234:
 258                 s = "Little-endian";
 259                 break;
 260         case 4321:
 261                 s = "Big-endian";
 262                 break;
 263         default:
 264                 s = "Unrecognized byte order";
 265                 break;
 266         }
 267         __db_msg(env, "%s\tByte order", s);
 268         __db_prflags(env, NULL, sp->bt_metaflags, fn, NULL, "\tFlags");
 269         if (dbp->type == DB_BTREE)
 270                 __db_dl(env, "Minimum keys per-page", (u_long)sp->bt_minkey);
 271         if (dbp->type == DB_RECNO) {
 272                 __db_dl(env,
 273                     "Fixed-length record size", (u_long)sp->bt_re_len);
 274                 __db_msg(env,
 275                     "%#x\tFixed-length record pad", (u_int)sp->bt_re_pad);
 276         }
 277         __db_dl(env,
 278             "Underlying database page size", (u_long)sp->bt_pagesize);
 279         if (dbp->type == DB_BTREE)
 280                 __db_dl(env, "Overflow key/data size",
 281                     ((BTREE_CURSOR *)dbc->internal)->ovflsize);
 282         __db_dl(env, "Number of levels in the tree", (u_long)sp->bt_levels);
 283         __db_dl(env, dbp->type == DB_BTREE ?
 284             "Number of unique keys in the tree" :
 285             "Number of records in the tree", (u_long)sp->bt_nkeys);
 286         __db_dl(env,
 287             "Number of data items in the tree", (u_long)sp->bt_ndata);
 288
 289         __db_dl(env,
 290             "Number of tree internal pages", (u_long)sp->bt_int_pg);
 291         __db_dl_pct(env,
 292             "Number of bytes free in tree internal pages",
 293             (u_long)sp->bt_int_pgfree,
 294             DB_PCT_PG(sp->bt_int_pgfree, sp->bt_int_pg, sp->bt_pagesize), "ff");
 295
 296         __db_dl(env,
 297             "Number of tree leaf pages", (u_long)sp->bt_leaf_pg);
 298         __db_dl_pct(env, "Number of bytes free in tree leaf pages",
 299             (u_long)sp->bt_leaf_pgfree, DB_PCT_PG(
 300             sp->bt_leaf_pgfree, sp->bt_leaf_pg, sp->bt_pagesize), "ff");
 301
 302         __db_dl(env,
 303             "Number of tree duplicate pages", (u_long)sp->bt_dup_pg);
 304         __db_dl_pct(env,
 305             "Number of bytes free in tree duplicate pages",
 306             (u_long)sp->bt_dup_pgfree,
 307             DB_PCT_PG(sp->bt_dup_pgfree, sp->bt_dup_pg, sp->bt_pagesize), "ff");
 308
 309         __db_dl(env,
 310             "Number of tree overflow pages", (u_long)sp->bt_over_pg);
 311         __db_dl_pct(env, "Number of bytes free in tree overflow pages",
 312             (u_long)sp->bt_over_pgfree, DB_PCT_PG(
 313             sp->bt_over_pgfree, sp->bt_over_pg, sp->bt_pagesize), "ff");
 314         __db_dl(env, "Number of empty pages", (u_long)sp->bt_empty_pg);
 315
 316         __db_dl(env, "Number of pages on the free list", (u_long)sp->bt_free);
 317
 318         __os_ufree(env, sp);
 319
 320         return (0);
 321 }
 322
 323 /*
 324  * __bam_stat_callback --
 325  *      Statistics callback.
 326  *
 327  * PUBLIC: int __bam_stat_callback __P((DBC *, PAGE *, void *, int *));
 328  */
 329 int
 330 __bam_stat_callback(dbc, h, cookie, putp)
 331         DBC *dbc;
 332         PAGE *h;
 333         void *cookie;
 334         int *putp;
 335 {
 336         DB *dbp;
 337         DB_BTREE_STAT *sp;
 338         db_indx_t indx, *inp, top;
 339         u_int8_t type;
 340
 341         dbp = dbc->dbp;
 342         sp = cookie;
 343         *putp = 0;
 344         top = NUM_ENT(h);
 345         inp = P_INP(dbp, h);
 346
 347         switch (TYPE(h)) {
 348         case P_IBTREE:
 349         case P_IRECNO:
 350                 ++sp->bt_int_pg;
 351                 sp->bt_int_pgfree += P_FREESPACE(dbp, h);
 352                 break;
 353         case P_LBTREE:
 354                 if (top == 0)
 355                         ++sp->bt_empty_pg;
 356
 357                 /* Correct for on-page duplicates and deleted items. */
 358                 for (indx = 0; indx < top; indx += P_INDX) {
 359                         type = GET_BKEYDATA(dbp, h, indx + O_INDX)->type;
 360                         /* Ignore deleted items. */
 361                         if (B_DISSET(type))
 362                                 continue;
 363
 364                         /* Ignore duplicate keys. */
 365                         if (indx + P_INDX >= top ||
 366                             inp[indx] != inp[indx + P_INDX])
 367                                 ++sp->bt_nkeys;
 368
 369                         /* Ignore off-page duplicates. */
 370                         if (B_TYPE(type) != B_DUPLICATE)
 371                                 ++sp->bt_ndata;
 372                 }
 373
 374                 ++sp->bt_leaf_pg;
 375                 sp->bt_leaf_pgfree += P_FREESPACE(dbp, h);
 376                 break;
 377         case P_LRECNO:
 378                 if (top == 0)
 379                         ++sp->bt_empty_pg;
 380
 381                 /*
 382                  * If walking a recno tree, then each of these items is a key.
 383                  * Otherwise, we're walking an off-page duplicate set.
 384                  */
 385                 if (dbp->type == DB_RECNO) {
 386                         /*
 387                          * Correct for deleted items in non-renumbering Recno
 388                          * databases.
 389                          */
 390                         if (F_ISSET(dbp, DB_AM_RENUMBER)) {
 391                                 sp->bt_nkeys += top;
 392                                 sp->bt_ndata += top;
 393                         } else
 394                                 for (indx = 0; indx < top; indx += O_INDX) {
 395                                         type = GET_BKEYDATA(dbp, h, indx)->type;
 396                                         if (!B_DISSET(type)) {
 397                                                 ++sp->bt_ndata;
 398                                                 ++sp->bt_nkeys;
 399                                         }
 400                                 }
 401
 402                         ++sp->bt_leaf_pg;
 403                         sp->bt_leaf_pgfree += P_FREESPACE(dbp, h);
 404                 } else {
 405                         sp->bt_ndata += top;
 406
 407                         ++sp->bt_dup_pg;
 408                         sp->bt_dup_pgfree += P_FREESPACE(dbp, h);
 409                 }
 410                 break;
 411         case P_LDUP:
 412                 if (top == 0)
 413                         ++sp->bt_empty_pg;
 414
 415                 /* Correct for deleted items. */
 416                 for (indx = 0; indx < top; indx += O_INDX)
 417                         if (!B_DISSET(GET_BKEYDATA(dbp, h, indx)->type))
 418                                 ++sp->bt_ndata;
 419
 420                 ++sp->bt_dup_pg;
 421                 sp->bt_dup_pgfree += P_FREESPACE(dbp, h);
 422                 break;
 423         case P_OVERFLOW:
 424                 ++sp->bt_over_pg;
 425                 sp->bt_over_pgfree += P_OVFLSPACE(dbp, dbp->pgsize, h);
 426                 break;
 427         default:
 428                 return (__db_pgfmt(dbp->env, h->pgno));
 429         }
 430         return (0);
 431 }
 432
 433 /*
 434  * __bam_print_cursor --
 435  *      Display the current internal cursor.
 436  *
 437  * PUBLIC: void __bam_print_cursor __P((DBC *));
 438  */
 439 void
 440 __bam_print_cursor(dbc)
 441         DBC *dbc;
 442 {
 443         static const FN fn[] = {
 444                 { C_DELETED,    "C_DELETED" },
 445                 { C_RECNUM,     "C_RECNUM" },
 446                 { C_RENUMBER,   "C_RENUMBER" },
 447                 { 0,            NULL }
 448         };
 449         ENV *env;
 450         BTREE_CURSOR *cp;
 451
 452         env = dbc->env;
 453         cp = (BTREE_CURSOR *)dbc->internal;
 454
 455         STAT_ULONG("Overflow size", cp->ovflsize);
 456         if (dbc->dbtype == DB_RECNO)
 457                 STAT_ULONG("Recno", cp->recno);
 458         STAT_ULONG("Order", cp->order);
 459         __db_prflags(env, NULL, cp->flags, fn, NULL, "\tInternal Flags");
 460 }
 461
 462 #else /* !HAVE_STATISTICS */
 463
 464 int
 465 __bam_stat(dbc, spp, flags)
 466         DBC *dbc;
 467         void *spp;
 468         u_int32_t flags;
 469 {
 470         COMPQUIET(spp, NULL);
 471         COMPQUIET(flags, 0);
 472
 473         return (__db_stat_not_built(dbc->env));
 474 }
 475
 476 int
 477 __bam_stat_print(dbc, flags)
 478         DBC *dbc;
 479         u_int32_t flags;
 480 {
 481         COMPQUIET(flags, 0);
 482
 483         return (__db_stat_not_built(dbc->env));
 484 }
 485 #endif
 486
 487 #ifndef HAVE_BREW
 488 /*
 489  * __bam_key_range --
 490  *      Return proportion of keys relative to given key.  The numbers are
 491  *      slightly skewed due to on page duplicates.
 492  *
 493  * PUBLIC: int __bam_key_range __P((DBC *, DBT *, DB_KEY_RANGE *, u_int32_t));
 494  */
 495 int
 496 __bam_key_range(dbc, dbt, kp, flags)
 497         DBC *dbc;
 498         DBT *dbt;
 499         DB_KEY_RANGE *kp;
 500         u_int32_t flags;
 501 {
 502         BTREE_CURSOR *cp;
 503         EPG *sp;
 504         double factor;
 505         int exact, ret;
 506
 507         COMPQUIET(flags, 0);
 508
 509         if ((ret = __bam_search(dbc, PGNO_INVALID,
 510             dbt, SR_STK_ONLY, 1, NULL, &exact)) != 0)
 511                 return (ret);
 512
 513         cp = (BTREE_CURSOR *)dbc->internal;
 514         kp->less = kp->greater = 0.0;
 515
 516         factor = 1.0;
 517
 518         /* Correct the leaf page. */
 519         cp->csp->entries /= 2;
 520         cp->csp->indx /= 2;
 521         for (sp = cp->sp; sp <= cp->csp; ++sp) {
 522                 /*
 523                  * At each level we know that pages greater than indx contain
 524                  * keys greater than what we are looking for and those less
 525                  * than indx are less than.  The one pointed to by indx may
 526                  * have some less, some greater or even equal.  If indx is
 527                  * equal to the number of entries, then the key is out of range
 528                  * and everything is less.
 529                  */
 530                 if (sp->indx == 0)
 531                         kp->greater += factor * (sp->entries - 1)/sp->entries;
 532                 else if (sp->indx == sp->entries)
 533                         kp->less += factor;
 534                 else {
 535                         kp->less += factor * sp->indx / sp->entries;
 536                         kp->greater += factor *
 537                             ((sp->entries - sp->indx) - 1) / sp->entries;
 538                 }
 539                 factor *= 1.0/sp->entries;
 540         }
 541
 542         /*
 543          * If there was an exact match then assign 1 n'th to the key itself.
 544          * Otherwise that factor belongs to those greater than the key, unless
 545          * the key was out of range.
 546          */
 547         if (exact)
 548                 kp->equal = factor;
 549         else {
 550                 if (kp->less != 1)
 551                         kp->greater += factor;
 552                 kp->equal = 0;
 553         }
 554
 555         BT_STK_CLR(cp);
 556
 557         return (0);
 558 }
 559 #endif
 560
 561 /*
 562  * __bam_traverse --
 563  *      Walk a Btree database.
 564  *
 565  * PUBLIC: int __bam_traverse __P((DBC *, db_lockmode_t,
 566  * PUBLIC:     db_pgno_t, int (*)(DBC *, PAGE *, void *, int *), void *));
 567  */
 568 int
 569 __bam_traverse(dbc, mode, root_pgno, callback, cookie)
 570         DBC *dbc;
 571         db_lockmode_t mode;
 572         db_pgno_t root_pgno;
 573         int (*callback)__P((DBC *, PAGE *, void *, int *));
 574         void *cookie;
 575 {
 576         BINTERNAL *bi;
 577         BKEYDATA *bk;
 578         DB *dbp;
 579         DB_LOCK lock;
 580         DB_MPOOLFILE *mpf;
 581         PAGE *h;
 582         RINTERNAL *ri;
 583         db_indx_t indx, *inp;
 584         int already_put, ret, t_ret;
 585
 586         dbp = dbc->dbp;
 587         mpf = dbp->mpf;
 588         already_put = 0;
 589
 590         if ((ret = __db_lget(dbc, 0, root_pgno, mode, 0, &lock)) != 0)
 591                 return (ret);
 592         if ((ret = __memp_fget(mpf, &root_pgno,
 593              dbc->thread_info, dbc->txn, 0, &h)) != 0) {
 594                 (void)__TLPUT(dbc, lock);
 595                 return (ret);
 596         }
 597
 598         switch (TYPE(h)) {
 599         case P_IBTREE:
 600                 for (indx = 0; indx < NUM_ENT(h); indx += O_INDX) {
 601                         bi = GET_BINTERNAL(dbp, h, indx);
 602                         if (B_TYPE(bi->type) == B_OVERFLOW &&
 603                             (ret = __db_traverse_big(dbc,
 604                             ((BOVERFLOW *)bi->data)->pgno,
 605                             callback, cookie)) != 0)
 606                                 goto err;
 607                         if ((ret = __bam_traverse(
 608                             dbc, mode, bi->pgno, callback, cookie)) != 0)
 609                                 goto err;
 610                 }
 611                 break;
 612         case P_IRECNO:
 613                 for (indx = 0; indx < NUM_ENT(h); indx += O_INDX) {
 614                         ri = GET_RINTERNAL(dbp, h, indx);
 615                         if ((ret = __bam_traverse(
 616                             dbc, mode, ri->pgno, callback, cookie)) != 0)
 617                                 goto err;
 618                 }
 619                 break;
 620         case P_LBTREE:
 621                 inp = P_INP(dbp, h);
 622                 for (indx = 0; indx < NUM_ENT(h); indx += P_INDX) {
 623                         bk = GET_BKEYDATA(dbp, h, indx);
 624                         if (B_TYPE(bk->type) == B_OVERFLOW &&
 625                             (indx + P_INDX >= NUM_ENT(h) ||
 626                             inp[indx] != inp[indx + P_INDX])) {
 627                                 if ((ret = __db_traverse_big(dbc,
 628                                     GET_BOVERFLOW(dbp, h, indx)->pgno,
 629                                     callback, cookie)) != 0)
 630                                         goto err;
 631                         }
 632                         bk = GET_BKEYDATA(dbp, h, indx + O_INDX);
 633                         if (B_TYPE(bk->type) == B_DUPLICATE &&
 634                             (ret = __bam_traverse(dbc, mode,
 635                             GET_BOVERFLOW(dbp, h, indx + O_INDX)->pgno,
 636                             callback, cookie)) != 0)
 637                                 goto err;
 638                         if (B_TYPE(bk->type) == B_OVERFLOW &&
 639                             (ret = __db_traverse_big(dbc,
 640                             GET_BOVERFLOW(dbp, h, indx + O_INDX)->pgno,
 641                             callback, cookie)) != 0)
 642                                 goto err;
 643                 }
 644                 break;
 645         case P_LDUP:
 646         case P_LRECNO:
 647                 for (indx = 0; indx < NUM_ENT(h); indx += O_INDX) {
 648                         bk = GET_BKEYDATA(dbp, h, indx);
 649                         if (B_TYPE(bk->type) == B_OVERFLOW &&
 650                             (ret = __db_traverse_big(dbc,
 651                             GET_BOVERFLOW(dbp, h, indx)->pgno,
 652                             callback, cookie)) != 0)
 653                                 goto err;
 654                 }
 655                 break;
 656         default:
 657                 return (__db_pgfmt(dbp->env, h->pgno));
 658         }
 659
 660         ret = callback(dbc, h, cookie, &already_put);
 661
 662 err:    if (!already_put && (t_ret = __memp_fput(mpf,
 663             dbc->thread_info, h, dbc->priority)) != 0 && ret == 0)
 664                 ret = t_ret;
 665         if ((t_ret = __TLPUT(dbc, lock)) != 0 && ret == 0)
 666                 ret = t_ret;
 667
 668         return (ret);
 669 }