11573Srgrimes/*- 214272Spst * Copyright (c) 1990, 1993, 1994 31573Srgrimes * The Regents of the University of California. All rights reserved. 41573Srgrimes * 51573Srgrimes * This code is derived from software contributed to Berkeley by 61573Srgrimes * Mike Olson. 71573Srgrimes * 81573Srgrimes * Redistribution and use in source and binary forms, with or without 91573Srgrimes * modification, are permitted provided that the following conditions 101573Srgrimes * are met: 111573Srgrimes * 1. Redistributions of source code must retain the above copyright 121573Srgrimes * notice, this list of conditions and the following disclaimer. 131573Srgrimes * 2. Redistributions in binary form must reproduce the above copyright 141573Srgrimes * notice, this list of conditions and the following disclaimer in the 151573Srgrimes * documentation and/or other materials provided with the distribution. 161573Srgrimes * 4. Neither the name of the University nor the names of its contributors 171573Srgrimes * may be used to endorse or promote products derived from this software 181573Srgrimes * without specific prior written permission. 191573Srgrimes * 201573Srgrimes * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 211573Srgrimes * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 221573Srgrimes * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 231573Srgrimes * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 241573Srgrimes * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 251573Srgrimes * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 261573Srgrimes * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 271573Srgrimes * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 281573Srgrimes * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 291573Srgrimes * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 301573Srgrimes * SUCH DAMAGE. 311573Srgrimes */ 321573Srgrimes 331573Srgrimes#if defined(LIBC_SCCS) && !defined(lint) 3414272Spststatic char sccsid[] = "@(#)bt_debug.c 8.5 (Berkeley) 8/17/94"; 351573Srgrimes#endif /* LIBC_SCCS and not lint */ 3692986Sobrien#include <sys/cdefs.h> 3792986Sobrien__FBSDID("$FreeBSD: releng/11.0/lib/libc/db/btree/bt_debug.c 190498 2009-03-28 07:31:02Z delphij $"); 381573Srgrimes 391573Srgrimes#include <sys/param.h> 401573Srgrimes 411573Srgrimes#include <stdio.h> 421573Srgrimes#include <stdlib.h> 431573Srgrimes#include <string.h> 441573Srgrimes 451573Srgrimes#include <db.h> 461573Srgrimes#include "btree.h" 471573Srgrimes 481573Srgrimes#ifdef DEBUG 491573Srgrimes/* 501573Srgrimes * BT_DUMP -- Dump the tree 511573Srgrimes * 521573Srgrimes * Parameters: 531573Srgrimes * dbp: pointer to the DB 541573Srgrimes */ 551573Srgrimesvoid 56189291Sdelphij__bt_dump(DB *dbp) 571573Srgrimes{ 581573Srgrimes BTREE *t; 591573Srgrimes PAGE *h; 601573Srgrimes pgno_t i; 611573Srgrimes char *sep; 621573Srgrimes 631573Srgrimes t = dbp->internal; 64190342Sdelphij (void)fprintf(stderr, "%s: pgsz %u", 6514272Spst F_ISSET(t, B_INMEM) ? "memory" : "disk", t->bt_psize); 6614272Spst if (F_ISSET(t, R_RECNO)) 67135024Skuriyama (void)fprintf(stderr, " keys %u", t->bt_nrecs); 681573Srgrimes#undef X 691573Srgrimes#define X(flag, name) \ 7014272Spst if (F_ISSET(t, flag)) { \ 711573Srgrimes (void)fprintf(stderr, "%s%s", sep, name); \ 721573Srgrimes sep = ", "; \ 731573Srgrimes } 7414272Spst if (t->flags != 0) { 751573Srgrimes sep = " flags ("; 761573Srgrimes X(R_FIXLEN, "FIXLEN"); 771573Srgrimes X(B_INMEM, "INMEM"); 781573Srgrimes X(B_NODUPS, "NODUPS"); 791573Srgrimes X(B_RDONLY, "RDONLY"); 801573Srgrimes X(R_RECNO, "RECNO"); 811573Srgrimes X(B_METADIRTY,"METADIRTY"); 821573Srgrimes (void)fprintf(stderr, ")\n"); 831573Srgrimes } 841573Srgrimes#undef X 851573Srgrimes 86190498Sdelphij for (i = P_ROOT; 87190498Sdelphij (h = mpool_get(t->bt_mp, i, MPOOL_IGNOREPIN)) != NULL; ++i) 881573Srgrimes __bt_dpage(h); 891573Srgrimes} 901573Srgrimes 911573Srgrimes/* 921573Srgrimes * BT_DMPAGE -- Dump the meta page 931573Srgrimes * 941573Srgrimes * Parameters: 951573Srgrimes * h: pointer to the PAGE 961573Srgrimes */ 971573Srgrimesvoid 98189291Sdelphij__bt_dmpage(PAGE *h) 991573Srgrimes{ 1001573Srgrimes BTMETA *m; 1011573Srgrimes char *sep; 1021573Srgrimes 1031573Srgrimes m = (BTMETA *)h; 104135024Skuriyama (void)fprintf(stderr, "magic %x\n", m->magic); 105135024Skuriyama (void)fprintf(stderr, "version %u\n", m->version); 106135024Skuriyama (void)fprintf(stderr, "psize %u\n", m->psize); 107135024Skuriyama (void)fprintf(stderr, "free %u\n", m->free); 108135024Skuriyama (void)fprintf(stderr, "nrecs %u\n", m->nrecs); 109135024Skuriyama (void)fprintf(stderr, "flags %u", m->flags); 1101573Srgrimes#undef X 1111573Srgrimes#define X(flag, name) \ 11214272Spst if (m->flags & flag) { \ 1131573Srgrimes (void)fprintf(stderr, "%s%s", sep, name); \ 1141573Srgrimes sep = ", "; \ 1151573Srgrimes } 11614272Spst if (m->flags) { 1171573Srgrimes sep = " ("; 1181573Srgrimes X(B_NODUPS, "NODUPS"); 1191573Srgrimes X(R_RECNO, "RECNO"); 1201573Srgrimes (void)fprintf(stderr, ")"); 1211573Srgrimes } 1221573Srgrimes} 1231573Srgrimes 1241573Srgrimes/* 1251573Srgrimes * BT_DNPAGE -- Dump the page 1261573Srgrimes * 1271573Srgrimes * Parameters: 1281573Srgrimes * n: page number to dump. 1291573Srgrimes */ 1301573Srgrimesvoid 131189291Sdelphij__bt_dnpage(DB *dbp, pgno_t pgno) 1321573Srgrimes{ 1331573Srgrimes BTREE *t; 1341573Srgrimes PAGE *h; 1351573Srgrimes 1361573Srgrimes t = dbp->internal; 137190498Sdelphij if ((h = mpool_get(t->bt_mp, pgno, MPOOL_IGNOREPIN)) != NULL) 1381573Srgrimes __bt_dpage(h); 1391573Srgrimes} 1401573Srgrimes 1411573Srgrimes/* 1421573Srgrimes * BT_DPAGE -- Dump the page 1431573Srgrimes * 1441573Srgrimes * Parameters: 1451573Srgrimes * h: pointer to the PAGE 1461573Srgrimes */ 1471573Srgrimesvoid 148189291Sdelphij__bt_dpage(PAGE *h) 1491573Srgrimes{ 1501573Srgrimes BINTERNAL *bi; 1511573Srgrimes BLEAF *bl; 1521573Srgrimes RINTERNAL *ri; 1531573Srgrimes RLEAF *rl; 1541573Srgrimes indx_t cur, top; 1551573Srgrimes char *sep; 1561573Srgrimes 157190342Sdelphij (void)fprintf(stderr, " page %u: (", h->pgno); 1581573Srgrimes#undef X 1591573Srgrimes#define X(flag, name) \ 1601573Srgrimes if (h->flags & flag) { \ 1611573Srgrimes (void)fprintf(stderr, "%s%s", sep, name); \ 1621573Srgrimes sep = ", "; \ 1631573Srgrimes } 1641573Srgrimes sep = ""; 1651573Srgrimes X(P_BINTERNAL, "BINTERNAL") /* types */ 1661573Srgrimes X(P_BLEAF, "BLEAF") 1671573Srgrimes X(P_RINTERNAL, "RINTERNAL") /* types */ 1681573Srgrimes X(P_RLEAF, "RLEAF") 1691573Srgrimes X(P_OVERFLOW, "OVERFLOW") 1701573Srgrimes X(P_PRESERVE, "PRESERVE"); 1711573Srgrimes (void)fprintf(stderr, ")\n"); 1721573Srgrimes#undef X 1731573Srgrimes 174190342Sdelphij (void)fprintf(stderr, "\tprev %2u next %2u", h->prevpg, h->nextpg); 1751573Srgrimes if (h->flags & P_OVERFLOW) 1761573Srgrimes return; 1771573Srgrimes 1781573Srgrimes top = NEXTINDEX(h); 1791573Srgrimes (void)fprintf(stderr, " lower %3d upper %3d nextind %d\n", 1801573Srgrimes h->lower, h->upper, top); 1811573Srgrimes for (cur = 0; cur < top; cur++) { 1821573Srgrimes (void)fprintf(stderr, "\t[%03d] %4d ", cur, h->linp[cur]); 18314272Spst switch (h->flags & P_TYPE) { 1841573Srgrimes case P_BINTERNAL: 1851573Srgrimes bi = GETBINTERNAL(h, cur); 1861573Srgrimes (void)fprintf(stderr, 1871573Srgrimes "size %03d pgno %03d", bi->ksize, bi->pgno); 1881573Srgrimes if (bi->flags & P_BIGKEY) 1891573Srgrimes (void)fprintf(stderr, " (indirect)"); 1901573Srgrimes else if (bi->ksize) 1911573Srgrimes (void)fprintf(stderr, 1921573Srgrimes " {%.*s}", (int)bi->ksize, bi->bytes); 1931573Srgrimes break; 1941573Srgrimes case P_RINTERNAL: 1951573Srgrimes ri = GETRINTERNAL(h, cur); 1961573Srgrimes (void)fprintf(stderr, "entries %03d pgno %03d", 1971573Srgrimes ri->nrecs, ri->pgno); 1981573Srgrimes break; 1991573Srgrimes case P_BLEAF: 2001573Srgrimes bl = GETBLEAF(h, cur); 2011573Srgrimes if (bl->flags & P_BIGKEY) 2021573Srgrimes (void)fprintf(stderr, 203135024Skuriyama "big key page %u size %u/", 2041573Srgrimes *(pgno_t *)bl->bytes, 20514272Spst *(u_int32_t *)(bl->bytes + sizeof(pgno_t))); 2061573Srgrimes else if (bl->ksize) 207135024Skuriyama (void)fprintf(stderr, "%.*s/", 208135024Skuriyama bl->ksize, bl->bytes); 2091573Srgrimes if (bl->flags & P_BIGDATA) 2101573Srgrimes (void)fprintf(stderr, 211135024Skuriyama "big data page %u size %u", 2121573Srgrimes *(pgno_t *)(bl->bytes + bl->ksize), 21314272Spst *(u_int32_t *)(bl->bytes + bl->ksize + 2141573Srgrimes sizeof(pgno_t))); 2151573Srgrimes else if (bl->dsize) 2161573Srgrimes (void)fprintf(stderr, "%.*s", 2171573Srgrimes (int)bl->dsize, bl->bytes + bl->ksize); 2181573Srgrimes break; 2191573Srgrimes case P_RLEAF: 2201573Srgrimes rl = GETRLEAF(h, cur); 2211573Srgrimes if (rl->flags & P_BIGDATA) 2221573Srgrimes (void)fprintf(stderr, 223135024Skuriyama "big data page %u size %u", 2241573Srgrimes *(pgno_t *)rl->bytes, 22514272Spst *(u_int32_t *)(rl->bytes + sizeof(pgno_t))); 2261573Srgrimes else if (rl->dsize) 2271573Srgrimes (void)fprintf(stderr, 2281573Srgrimes "%.*s", (int)rl->dsize, rl->bytes); 2291573Srgrimes break; 2301573Srgrimes } 2311573Srgrimes (void)fprintf(stderr, "\n"); 2321573Srgrimes } 2331573Srgrimes} 2341573Srgrimes#endif 2351573Srgrimes 2361573Srgrimes#ifdef STATISTICS 2371573Srgrimes/* 2381573Srgrimes * BT_STAT -- Gather/print the tree statistics 2391573Srgrimes * 2401573Srgrimes * Parameters: 2411573Srgrimes * dbp: pointer to the DB 2421573Srgrimes */ 2431573Srgrimesvoid 244189291Sdelphij__bt_stat(DB *dbp) 2451573Srgrimes{ 2461573Srgrimes extern u_long bt_cache_hit, bt_cache_miss, bt_pfxsaved, bt_rootsplit; 2471573Srgrimes extern u_long bt_sortsplit, bt_split; 2481573Srgrimes BTREE *t; 2491573Srgrimes PAGE *h; 2501573Srgrimes pgno_t i, pcont, pinternal, pleaf; 2511573Srgrimes u_long ifree, lfree, nkeys; 2521573Srgrimes int levels; 2531573Srgrimes 2541573Srgrimes t = dbp->internal; 2551573Srgrimes pcont = pinternal = pleaf = 0; 2561573Srgrimes nkeys = ifree = lfree = 0; 257190498Sdelphij for (i = P_ROOT; 258190498Sdelphij (h = mpool_get(t->bt_mp, i, MPOOL_IGNOREPIN)) != NULL; ++i) 25914272Spst switch (h->flags & P_TYPE) { 2601573Srgrimes case P_BINTERNAL: 2611573Srgrimes case P_RINTERNAL: 2621573Srgrimes ++pinternal; 2631573Srgrimes ifree += h->upper - h->lower; 2641573Srgrimes break; 2651573Srgrimes case P_BLEAF: 2661573Srgrimes case P_RLEAF: 2671573Srgrimes ++pleaf; 2681573Srgrimes lfree += h->upper - h->lower; 2691573Srgrimes nkeys += NEXTINDEX(h); 2701573Srgrimes break; 2711573Srgrimes case P_OVERFLOW: 2721573Srgrimes ++pcont; 2731573Srgrimes break; 2741573Srgrimes } 2751573Srgrimes 2761573Srgrimes /* Count the levels of the tree. */ 2771573Srgrimes for (i = P_ROOT, levels = 0 ;; ++levels) { 278190498Sdelphij h = mpool_get(t->bt_mp, i, MPOOL_IGNOREPIN); 2791573Srgrimes if (h->flags & (P_BLEAF|P_RLEAF)) { 2801573Srgrimes if (levels == 0) 2811573Srgrimes levels = 1; 2821573Srgrimes break; 2831573Srgrimes } 28414272Spst i = F_ISSET(t, R_RECNO) ? 2851573Srgrimes GETRINTERNAL(h, 0)->pgno : 2861573Srgrimes GETBINTERNAL(h, 0)->pgno; 2871573Srgrimes } 2881573Srgrimes 289190342Sdelphij (void)fprintf(stderr, "%d level%s with %lu keys", 2901573Srgrimes levels, levels == 1 ? "" : "s", nkeys); 29114272Spst if (F_ISSET(t, R_RECNO)) 292190342Sdelphij (void)fprintf(stderr, " (%u header count)", t->bt_nrecs); 2931573Srgrimes (void)fprintf(stderr, 294190342Sdelphij "\n%u pages (leaf %u, internal %u, overflow %u)\n", 2951573Srgrimes pinternal + pleaf + pcont, pleaf, pinternal, pcont); 296190342Sdelphij (void)fprintf(stderr, "%lu cache hits, %lu cache misses\n", 2971573Srgrimes bt_cache_hit, bt_cache_miss); 298135024Skuriyama (void)fprintf(stderr, "%lu splits (%lu root splits, %lu sort splits)\n", 2991573Srgrimes bt_split, bt_rootsplit, bt_sortsplit); 3001573Srgrimes pleaf *= t->bt_psize - BTDATAOFF; 3011573Srgrimes if (pleaf) 3021573Srgrimes (void)fprintf(stderr, 303190342Sdelphij "%.0f%% leaf fill (%lu bytes used, %lu bytes free)\n", 3041573Srgrimes ((double)(pleaf - lfree) / pleaf) * 100, 3051573Srgrimes pleaf - lfree, lfree); 3061573Srgrimes pinternal *= t->bt_psize - BTDATAOFF; 3071573Srgrimes if (pinternal) 3081573Srgrimes (void)fprintf(stderr, 309190342Sdelphij "%.0f%% internal fill (%lu bytes used, %lu bytes free\n", 3101573Srgrimes ((double)(pinternal - ifree) / pinternal) * 100, 3111573Srgrimes pinternal - ifree, ifree); 3121573Srgrimes if (bt_pfxsaved) 3131573Srgrimes (void)fprintf(stderr, "prefix checking removed %lu bytes.\n", 3141573Srgrimes bt_pfxsaved); 3151573Srgrimes} 3161573Srgrimes#endif 317