bt_debug.c revision 1573
11573Srgrimes/*- 21573Srgrimes * Copyright (c) 1990, 1993 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 * 3. All advertising materials mentioning features or use of this software 171573Srgrimes * must display the following acknowledgement: 181573Srgrimes * This product includes software developed by the University of 191573Srgrimes * California, Berkeley and its contributors. 201573Srgrimes * 4. Neither the name of the University nor the names of its contributors 211573Srgrimes * may be used to endorse or promote products derived from this software 221573Srgrimes * without specific prior written permission. 231573Srgrimes * 241573Srgrimes * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 251573Srgrimes * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 261573Srgrimes * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 271573Srgrimes * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 281573Srgrimes * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 291573Srgrimes * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 301573Srgrimes * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 311573Srgrimes * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 321573Srgrimes * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 331573Srgrimes * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 341573Srgrimes * SUCH DAMAGE. 351573Srgrimes */ 361573Srgrimes 371573Srgrimes#if defined(LIBC_SCCS) && !defined(lint) 381573Srgrimesstatic char sccsid[] = "@(#)bt_debug.c 8.2 (Berkeley) 2/21/94"; 391573Srgrimes#endif /* LIBC_SCCS and not lint */ 401573Srgrimes 411573Srgrimes#include <sys/param.h> 421573Srgrimes 431573Srgrimes#include <stdio.h> 441573Srgrimes#include <stdlib.h> 451573Srgrimes#include <string.h> 461573Srgrimes 471573Srgrimes#include <db.h> 481573Srgrimes#include "btree.h" 491573Srgrimes 501573Srgrimes#ifdef DEBUG 511573Srgrimes/* 521573Srgrimes * BT_DUMP -- Dump the tree 531573Srgrimes * 541573Srgrimes * Parameters: 551573Srgrimes * dbp: pointer to the DB 561573Srgrimes */ 571573Srgrimesvoid 581573Srgrimes__bt_dump(dbp) 591573Srgrimes DB *dbp; 601573Srgrimes{ 611573Srgrimes BTREE *t; 621573Srgrimes PAGE *h; 631573Srgrimes pgno_t i; 641573Srgrimes char *sep; 651573Srgrimes 661573Srgrimes t = dbp->internal; 671573Srgrimes (void)fprintf(stderr, "%s: pgsz %d", 681573Srgrimes ISSET(t, B_INMEM) ? "memory" : "disk", t->bt_psize); 691573Srgrimes if (ISSET(t, R_RECNO)) 701573Srgrimes (void)fprintf(stderr, " keys %lu", t->bt_nrecs); 711573Srgrimes#undef X 721573Srgrimes#define X(flag, name) \ 731573Srgrimes if (ISSET(t, flag)) { \ 741573Srgrimes (void)fprintf(stderr, "%s%s", sep, name); \ 751573Srgrimes sep = ", "; \ 761573Srgrimes } 771573Srgrimes if (t->bt_flags) { 781573Srgrimes sep = " flags ("; 791573Srgrimes X(B_DELCRSR, "DELCRSR"); 801573Srgrimes X(R_FIXLEN, "FIXLEN"); 811573Srgrimes X(B_INMEM, "INMEM"); 821573Srgrimes X(B_NODUPS, "NODUPS"); 831573Srgrimes X(B_RDONLY, "RDONLY"); 841573Srgrimes X(R_RECNO, "RECNO"); 851573Srgrimes X(B_SEQINIT, "SEQINIT"); 861573Srgrimes X(B_METADIRTY,"METADIRTY"); 871573Srgrimes (void)fprintf(stderr, ")\n"); 881573Srgrimes } 891573Srgrimes#undef X 901573Srgrimes 911573Srgrimes for (i = P_ROOT; (h = mpool_get(t->bt_mp, i, 0)) != NULL; ++i) { 921573Srgrimes __bt_dpage(h); 931573Srgrimes (void)mpool_put(t->bt_mp, h, 0); 941573Srgrimes } 951573Srgrimes} 961573Srgrimes 971573Srgrimes/* 981573Srgrimes * BT_DMPAGE -- Dump the meta page 991573Srgrimes * 1001573Srgrimes * Parameters: 1011573Srgrimes * h: pointer to the PAGE 1021573Srgrimes */ 1031573Srgrimesvoid 1041573Srgrimes__bt_dmpage(h) 1051573Srgrimes PAGE *h; 1061573Srgrimes{ 1071573Srgrimes BTMETA *m; 1081573Srgrimes char *sep; 1091573Srgrimes 1101573Srgrimes m = (BTMETA *)h; 1111573Srgrimes (void)fprintf(stderr, "magic %lx\n", m->m_magic); 1121573Srgrimes (void)fprintf(stderr, "version %lu\n", m->m_version); 1131573Srgrimes (void)fprintf(stderr, "psize %lu\n", m->m_psize); 1141573Srgrimes (void)fprintf(stderr, "free %lu\n", m->m_free); 1151573Srgrimes (void)fprintf(stderr, "nrecs %lu\n", m->m_nrecs); 1161573Srgrimes (void)fprintf(stderr, "flags %lu", m->m_flags); 1171573Srgrimes#undef X 1181573Srgrimes#define X(flag, name) \ 1191573Srgrimes if (m->m_flags & flag) { \ 1201573Srgrimes (void)fprintf(stderr, "%s%s", sep, name); \ 1211573Srgrimes sep = ", "; \ 1221573Srgrimes } 1231573Srgrimes if (m->m_flags) { 1241573Srgrimes sep = " ("; 1251573Srgrimes X(B_NODUPS, "NODUPS"); 1261573Srgrimes X(R_RECNO, "RECNO"); 1271573Srgrimes (void)fprintf(stderr, ")"); 1281573Srgrimes } 1291573Srgrimes} 1301573Srgrimes 1311573Srgrimes/* 1321573Srgrimes * BT_DNPAGE -- Dump the page 1331573Srgrimes * 1341573Srgrimes * Parameters: 1351573Srgrimes * n: page number to dump. 1361573Srgrimes */ 1371573Srgrimesvoid 1381573Srgrimes__bt_dnpage(dbp, pgno) 1391573Srgrimes DB *dbp; 1401573Srgrimes pgno_t pgno; 1411573Srgrimes{ 1421573Srgrimes BTREE *t; 1431573Srgrimes PAGE *h; 1441573Srgrimes 1451573Srgrimes t = dbp->internal; 1461573Srgrimes if ((h = mpool_get(t->bt_mp, pgno, 0)) != NULL) { 1471573Srgrimes __bt_dpage(h); 1481573Srgrimes (void)mpool_put(t->bt_mp, h, 0); 1491573Srgrimes } 1501573Srgrimes} 1511573Srgrimes 1521573Srgrimes/* 1531573Srgrimes * BT_DPAGE -- Dump the page 1541573Srgrimes * 1551573Srgrimes * Parameters: 1561573Srgrimes * h: pointer to the PAGE 1571573Srgrimes */ 1581573Srgrimesvoid 1591573Srgrimes__bt_dpage(h) 1601573Srgrimes PAGE *h; 1611573Srgrimes{ 1621573Srgrimes BINTERNAL *bi; 1631573Srgrimes BLEAF *bl; 1641573Srgrimes RINTERNAL *ri; 1651573Srgrimes RLEAF *rl; 1661573Srgrimes indx_t cur, top; 1671573Srgrimes char *sep; 1681573Srgrimes 1691573Srgrimes (void)fprintf(stderr, " page %d: (", h->pgno); 1701573Srgrimes#undef X 1711573Srgrimes#define X(flag, name) \ 1721573Srgrimes if (h->flags & flag) { \ 1731573Srgrimes (void)fprintf(stderr, "%s%s", sep, name); \ 1741573Srgrimes sep = ", "; \ 1751573Srgrimes } 1761573Srgrimes sep = ""; 1771573Srgrimes X(P_BINTERNAL, "BINTERNAL") /* types */ 1781573Srgrimes X(P_BLEAF, "BLEAF") 1791573Srgrimes X(P_RINTERNAL, "RINTERNAL") /* types */ 1801573Srgrimes X(P_RLEAF, "RLEAF") 1811573Srgrimes X(P_OVERFLOW, "OVERFLOW") 1821573Srgrimes X(P_PRESERVE, "PRESERVE"); 1831573Srgrimes (void)fprintf(stderr, ")\n"); 1841573Srgrimes#undef X 1851573Srgrimes 1861573Srgrimes (void)fprintf(stderr, "\tprev %2d next %2d", h->prevpg, h->nextpg); 1871573Srgrimes if (h->flags & P_OVERFLOW) 1881573Srgrimes return; 1891573Srgrimes 1901573Srgrimes top = NEXTINDEX(h); 1911573Srgrimes (void)fprintf(stderr, " lower %3d upper %3d nextind %d\n", 1921573Srgrimes h->lower, h->upper, top); 1931573Srgrimes for (cur = 0; cur < top; cur++) { 1941573Srgrimes (void)fprintf(stderr, "\t[%03d] %4d ", cur, h->linp[cur]); 1951573Srgrimes switch(h->flags & P_TYPE) { 1961573Srgrimes case P_BINTERNAL: 1971573Srgrimes bi = GETBINTERNAL(h, cur); 1981573Srgrimes (void)fprintf(stderr, 1991573Srgrimes "size %03d pgno %03d", bi->ksize, bi->pgno); 2001573Srgrimes if (bi->flags & P_BIGKEY) 2011573Srgrimes (void)fprintf(stderr, " (indirect)"); 2021573Srgrimes else if (bi->ksize) 2031573Srgrimes (void)fprintf(stderr, 2041573Srgrimes " {%.*s}", (int)bi->ksize, bi->bytes); 2051573Srgrimes break; 2061573Srgrimes case P_RINTERNAL: 2071573Srgrimes ri = GETRINTERNAL(h, cur); 2081573Srgrimes (void)fprintf(stderr, "entries %03d pgno %03d", 2091573Srgrimes ri->nrecs, ri->pgno); 2101573Srgrimes break; 2111573Srgrimes case P_BLEAF: 2121573Srgrimes bl = GETBLEAF(h, cur); 2131573Srgrimes if (bl->flags & P_BIGKEY) 2141573Srgrimes (void)fprintf(stderr, 2151573Srgrimes "big key page %lu size %u/", 2161573Srgrimes *(pgno_t *)bl->bytes, 2171573Srgrimes *(size_t *)(bl->bytes + sizeof(pgno_t))); 2181573Srgrimes else if (bl->ksize) 2191573Srgrimes (void)fprintf(stderr, "%s/", bl->bytes); 2201573Srgrimes if (bl->flags & P_BIGDATA) 2211573Srgrimes (void)fprintf(stderr, 2221573Srgrimes "big data page %lu size %u", 2231573Srgrimes *(pgno_t *)(bl->bytes + bl->ksize), 2241573Srgrimes *(size_t *)(bl->bytes + bl->ksize + 2251573Srgrimes sizeof(pgno_t))); 2261573Srgrimes else if (bl->dsize) 2271573Srgrimes (void)fprintf(stderr, "%.*s", 2281573Srgrimes (int)bl->dsize, bl->bytes + bl->ksize); 2291573Srgrimes break; 2301573Srgrimes case P_RLEAF: 2311573Srgrimes rl = GETRLEAF(h, cur); 2321573Srgrimes if (rl->flags & P_BIGDATA) 2331573Srgrimes (void)fprintf(stderr, 2341573Srgrimes "big data page %lu size %u", 2351573Srgrimes *(pgno_t *)rl->bytes, 2361573Srgrimes *(size_t *)(rl->bytes + sizeof(pgno_t))); 2371573Srgrimes else if (rl->dsize) 2381573Srgrimes (void)fprintf(stderr, 2391573Srgrimes "%.*s", (int)rl->dsize, rl->bytes); 2401573Srgrimes break; 2411573Srgrimes } 2421573Srgrimes (void)fprintf(stderr, "\n"); 2431573Srgrimes } 2441573Srgrimes} 2451573Srgrimes#endif 2461573Srgrimes 2471573Srgrimes#ifdef STATISTICS 2481573Srgrimes/* 2491573Srgrimes * BT_STAT -- Gather/print the tree statistics 2501573Srgrimes * 2511573Srgrimes * Parameters: 2521573Srgrimes * dbp: pointer to the DB 2531573Srgrimes */ 2541573Srgrimesvoid 2551573Srgrimes__bt_stat(dbp) 2561573Srgrimes DB *dbp; 2571573Srgrimes{ 2581573Srgrimes extern u_long bt_cache_hit, bt_cache_miss, bt_pfxsaved, bt_rootsplit; 2591573Srgrimes extern u_long bt_sortsplit, bt_split; 2601573Srgrimes BTREE *t; 2611573Srgrimes PAGE *h; 2621573Srgrimes pgno_t i, pcont, pinternal, pleaf; 2631573Srgrimes u_long ifree, lfree, nkeys; 2641573Srgrimes int levels; 2651573Srgrimes 2661573Srgrimes t = dbp->internal; 2671573Srgrimes pcont = pinternal = pleaf = 0; 2681573Srgrimes nkeys = ifree = lfree = 0; 2691573Srgrimes for (i = P_ROOT; (h = mpool_get(t->bt_mp, i, 0)) != NULL; ++i) { 2701573Srgrimes switch(h->flags & P_TYPE) { 2711573Srgrimes case P_BINTERNAL: 2721573Srgrimes case P_RINTERNAL: 2731573Srgrimes ++pinternal; 2741573Srgrimes ifree += h->upper - h->lower; 2751573Srgrimes break; 2761573Srgrimes case P_BLEAF: 2771573Srgrimes case P_RLEAF: 2781573Srgrimes ++pleaf; 2791573Srgrimes lfree += h->upper - h->lower; 2801573Srgrimes nkeys += NEXTINDEX(h); 2811573Srgrimes break; 2821573Srgrimes case P_OVERFLOW: 2831573Srgrimes ++pcont; 2841573Srgrimes break; 2851573Srgrimes } 2861573Srgrimes (void)mpool_put(t->bt_mp, h, 0); 2871573Srgrimes } 2881573Srgrimes 2891573Srgrimes /* Count the levels of the tree. */ 2901573Srgrimes for (i = P_ROOT, levels = 0 ;; ++levels) { 2911573Srgrimes h = mpool_get(t->bt_mp, i, 0); 2921573Srgrimes if (h->flags & (P_BLEAF|P_RLEAF)) { 2931573Srgrimes if (levels == 0) 2941573Srgrimes levels = 1; 2951573Srgrimes (void)mpool_put(t->bt_mp, h, 0); 2961573Srgrimes break; 2971573Srgrimes } 2981573Srgrimes i = ISSET(t, R_RECNO) ? 2991573Srgrimes GETRINTERNAL(h, 0)->pgno : 3001573Srgrimes GETBINTERNAL(h, 0)->pgno; 3011573Srgrimes (void)mpool_put(t->bt_mp, h, 0); 3021573Srgrimes } 3031573Srgrimes 3041573Srgrimes (void)fprintf(stderr, "%d level%s with %ld keys", 3051573Srgrimes levels, levels == 1 ? "" : "s", nkeys); 3061573Srgrimes if (ISSET(t, R_RECNO)) 3071573Srgrimes (void)fprintf(stderr, " (%ld header count)", t->bt_nrecs); 3081573Srgrimes (void)fprintf(stderr, 3091573Srgrimes "\n%lu pages (leaf %ld, internal %ld, overflow %ld)\n", 3101573Srgrimes pinternal + pleaf + pcont, pleaf, pinternal, pcont); 3111573Srgrimes (void)fprintf(stderr, "%ld cache hits, %ld cache misses\n", 3121573Srgrimes bt_cache_hit, bt_cache_miss); 3131573Srgrimes (void)fprintf(stderr, "%ld splits (%ld root splits, %ld sort splits)\n", 3141573Srgrimes bt_split, bt_rootsplit, bt_sortsplit); 3151573Srgrimes pleaf *= t->bt_psize - BTDATAOFF; 3161573Srgrimes if (pleaf) 3171573Srgrimes (void)fprintf(stderr, 3181573Srgrimes "%.0f%% leaf fill (%ld bytes used, %ld bytes free)\n", 3191573Srgrimes ((double)(pleaf - lfree) / pleaf) * 100, 3201573Srgrimes pleaf - lfree, lfree); 3211573Srgrimes pinternal *= t->bt_psize - BTDATAOFF; 3221573Srgrimes if (pinternal) 3231573Srgrimes (void)fprintf(stderr, 3241573Srgrimes "%.0f%% internal fill (%ld bytes used, %ld bytes free\n", 3251573Srgrimes ((double)(pinternal - ifree) / pinternal) * 100, 3261573Srgrimes pinternal - ifree, ifree); 3271573Srgrimes if (bt_pfxsaved) 3281573Srgrimes (void)fprintf(stderr, "prefix checking removed %lu bytes.\n", 3291573Srgrimes bt_pfxsaved); 3301573Srgrimes} 3311573Srgrimes#endif 332