1 /* $NetBSD: bt_debug.c,v 1.7 1997/07/13 18:51:50 christos Exp $ */ 2 3 /*- 4 * Copyright (c) 1990, 1993, 1994 5 * The Regents of the University of California. All rights reserved. 6 * 7 * This code is derived from software contributed to Berkeley by 8 * Mike Olson. 9 * 10 * Redistribution and use in source and binary forms, with or without 11 * modification, are permitted provided that the following conditions 12 * are met: 13 * 1. Redistributions of source code must retain the above copyright 14 * notice, this list of conditions and the following disclaimer. 15 * 2. Redistributions in binary form must reproduce the above copyright 16 * notice, this list of conditions and the following disclaimer in the 17 * documentation and/or other materials provided with the distribution. 18 * 3. All advertising materials mentioning features or use of this software 19 * must display the following acknowledgement: 20 * This product includes software developed by the University of 21 * California, Berkeley and its contributors. 22 * 4. Neither the name of the University nor the names of its contributors 23 * may be used to endorse or promote products derived from this software 24 * without specific prior written permission. 25 * 26 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 27 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 28 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 29 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 30 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 31 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 32 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 33 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 34 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 35 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 36 * SUCH DAMAGE. 37 */ 38 39 #include <sys/cdefs.h> 40 #if defined(LIBC_SCCS) && !defined(lint) 41 #if 0 42 static char sccsid[] = "@(#)bt_debug.c 8.5 (Berkeley) 8/17/94"; 43 #else 44 __RCSID("$NetBSD: bt_debug.c,v 1.7 1997/07/13 18:51:50 christos Exp $"); 45 #endif 46 #endif /* LIBC_SCCS and not lint */ 47 48 #include <sys/param.h> 49 50 #include <stdio.h> 51 #include <stdlib.h> 52 #include <string.h> 53 54 #include <db.h> 55 #include "btree.h" 56 57 #ifdef DEBUG 58 /* 59 * BT_DUMP -- Dump the tree 60 * 61 * Parameters: 62 * dbp: pointer to the DB 63 */ 64 void 65 __bt_dump(dbp) 66 DB *dbp; 67 { 68 BTREE *t; 69 PAGE *h; 70 pgno_t i; 71 char *sep; 72 73 t = dbp->internal; 74 (void)fprintf(stderr, "%s: pgsz %d", 75 F_ISSET(t, B_INMEM) ? "memory" : "disk", t->bt_psize); 76 if (F_ISSET(t, R_RECNO)) 77 (void)fprintf(stderr, " keys %lu", t->bt_nrecs); 78 #undef X 79 #define X(flag, name) \ 80 if (F_ISSET(t, flag)) { \ 81 (void)fprintf(stderr, "%s%s", sep, name); \ 82 sep = ", "; \ 83 } 84 if (t->flags != 0) { 85 sep = " flags ("; 86 X(R_FIXLEN, "FIXLEN"); 87 X(B_INMEM, "INMEM"); 88 X(B_NODUPS, "NODUPS"); 89 X(B_RDONLY, "RDONLY"); 90 X(R_RECNO, "RECNO"); 91 X(B_METADIRTY,"METADIRTY"); 92 (void)fprintf(stderr, ")\n"); 93 } 94 #undef X 95 96 for (i = P_ROOT; (h = mpool_get(t->bt_mp, i, 0)) != NULL; ++i) { 97 __bt_dpage(h); 98 (void)mpool_put(t->bt_mp, h, 0); 99 } 100 } 101 102 /* 103 * BT_DMPAGE -- Dump the meta page 104 * 105 * Parameters: 106 * h: pointer to the PAGE 107 */ 108 void 109 __bt_dmpage(h) 110 PAGE *h; 111 { 112 BTMETA *m; 113 char *sep; 114 115 m = (BTMETA *)h; 116 (void)fprintf(stderr, "magic %lx\n", m->magic); 117 (void)fprintf(stderr, "version %lu\n", m->version); 118 (void)fprintf(stderr, "psize %lu\n", m->psize); 119 (void)fprintf(stderr, "free %lu\n", m->free); 120 (void)fprintf(stderr, "nrecs %lu\n", m->nrecs); 121 (void)fprintf(stderr, "flags %lu", m->flags); 122 #undef X 123 #define X(flag, name) \ 124 if (m->flags & flag) { \ 125 (void)fprintf(stderr, "%s%s", sep, name); \ 126 sep = ", "; \ 127 } 128 if (m->flags) { 129 sep = " ("; 130 X(B_NODUPS, "NODUPS"); 131 X(R_RECNO, "RECNO"); 132 (void)fprintf(stderr, ")"); 133 } 134 } 135 136 /* 137 * BT_DNPAGE -- Dump the page 138 * 139 * Parameters: 140 * n: page number to dump. 141 */ 142 void 143 __bt_dnpage(dbp, pgno) 144 DB *dbp; 145 pgno_t pgno; 146 { 147 BTREE *t; 148 PAGE *h; 149 150 t = dbp->internal; 151 if ((h = mpool_get(t->bt_mp, pgno, 0)) != NULL) { 152 __bt_dpage(h); 153 (void)mpool_put(t->bt_mp, h, 0); 154 } 155 } 156 157 /* 158 * BT_DPAGE -- Dump the page 159 * 160 * Parameters: 161 * h: pointer to the PAGE 162 */ 163 void 164 __bt_dpage(h) 165 PAGE *h; 166 { 167 BINTERNAL *bi; 168 BLEAF *bl; 169 RINTERNAL *ri; 170 RLEAF *rl; 171 indx_t cur, top; 172 char *sep; 173 174 (void)fprintf(stderr, " page %d: (", h->pgno); 175 #undef X 176 #define X(flag, name) \ 177 if (h->flags & flag) { \ 178 (void)fprintf(stderr, "%s%s", sep, name); \ 179 sep = ", "; \ 180 } 181 sep = ""; 182 X(P_BINTERNAL, "BINTERNAL") /* types */ 183 X(P_BLEAF, "BLEAF") 184 X(P_RINTERNAL, "RINTERNAL") /* types */ 185 X(P_RLEAF, "RLEAF") 186 X(P_OVERFLOW, "OVERFLOW") 187 X(P_PRESERVE, "PRESERVE"); 188 (void)fprintf(stderr, ")\n"); 189 #undef X 190 191 (void)fprintf(stderr, "\tprev %2d next %2d", h->prevpg, h->nextpg); 192 if (h->flags & P_OVERFLOW) 193 return; 194 195 top = NEXTINDEX(h); 196 (void)fprintf(stderr, " lower %3d upper %3d nextind %d\n", 197 h->lower, h->upper, top); 198 for (cur = 0; cur < top; cur++) { 199 (void)fprintf(stderr, "\t[%03d] %4d ", cur, h->linp[cur]); 200 switch (h->flags & P_TYPE) { 201 case P_BINTERNAL: 202 bi = GETBINTERNAL(h, cur); 203 (void)fprintf(stderr, 204 "size %03d pgno %03d", bi->ksize, bi->pgno); 205 if (bi->flags & P_BIGKEY) 206 (void)fprintf(stderr, " (indirect)"); 207 else if (bi->ksize) 208 (void)fprintf(stderr, 209 " {%.*s}", (int)bi->ksize, bi->bytes); 210 break; 211 case P_RINTERNAL: 212 ri = GETRINTERNAL(h, cur); 213 (void)fprintf(stderr, "entries %03d pgno %03d", 214 ri->nrecs, ri->pgno); 215 break; 216 case P_BLEAF: 217 bl = GETBLEAF(h, cur); 218 if (bl->flags & P_BIGKEY) 219 (void)fprintf(stderr, 220 "big key page %lu size %u/", 221 *(pgno_t *)bl->bytes, 222 *(u_int32_t *)(bl->bytes + sizeof(pgno_t))); 223 else if (bl->ksize) 224 (void)fprintf(stderr, "%s/", bl->bytes); 225 if (bl->flags & P_BIGDATA) 226 (void)fprintf(stderr, 227 "big data page %lu size %u", 228 *(pgno_t *)(bl->bytes + bl->ksize), 229 *(u_int32_t *)(bl->bytes + bl->ksize + 230 sizeof(pgno_t))); 231 else if (bl->dsize) 232 (void)fprintf(stderr, "%.*s", 233 (int)bl->dsize, bl->bytes + bl->ksize); 234 break; 235 case P_RLEAF: 236 rl = GETRLEAF(h, cur); 237 if (rl->flags & P_BIGDATA) 238 (void)fprintf(stderr, 239 "big data page %lu size %u", 240 *(pgno_t *)rl->bytes, 241 *(u_int32_t *)(rl->bytes + sizeof(pgno_t))); 242 else if (rl->dsize) 243 (void)fprintf(stderr, 244 "%.*s", (int)rl->dsize, rl->bytes); 245 break; 246 } 247 (void)fprintf(stderr, "\n"); 248 } 249 } 250 #endif 251 252 #ifdef STATISTICS 253 /* 254 * BT_STAT -- Gather/print the tree statistics 255 * 256 * Parameters: 257 * dbp: pointer to the DB 258 */ 259 void 260 __bt_stat(dbp) 261 DB *dbp; 262 { 263 extern u_long bt_cache_hit, bt_cache_miss, bt_pfxsaved, bt_rootsplit; 264 extern u_long bt_sortsplit, bt_split; 265 BTREE *t; 266 PAGE *h; 267 pgno_t i, pcont, pinternal, pleaf; 268 u_long ifree, lfree, nkeys; 269 int levels; 270 271 t = dbp->internal; 272 pcont = pinternal = pleaf = 0; 273 nkeys = ifree = lfree = 0; 274 for (i = P_ROOT; (h = mpool_get(t->bt_mp, i, 0)) != NULL; ++i) { 275 switch (h->flags & P_TYPE) { 276 case P_BINTERNAL: 277 case P_RINTERNAL: 278 ++pinternal; 279 ifree += h->upper - h->lower; 280 break; 281 case P_BLEAF: 282 case P_RLEAF: 283 ++pleaf; 284 lfree += h->upper - h->lower; 285 nkeys += NEXTINDEX(h); 286 break; 287 case P_OVERFLOW: 288 ++pcont; 289 break; 290 } 291 (void)mpool_put(t->bt_mp, h, 0); 292 } 293 294 /* Count the levels of the tree. */ 295 for (i = P_ROOT, levels = 0 ;; ++levels) { 296 h = mpool_get(t->bt_mp, i, 0); 297 if (h->flags & (P_BLEAF|P_RLEAF)) { 298 if (levels == 0) 299 levels = 1; 300 (void)mpool_put(t->bt_mp, h, 0); 301 break; 302 } 303 i = F_ISSET(t, R_RECNO) ? 304 GETRINTERNAL(h, 0)->pgno : 305 GETBINTERNAL(h, 0)->pgno; 306 (void)mpool_put(t->bt_mp, h, 0); 307 } 308 309 (void)fprintf(stderr, "%d level%s with %ld keys", 310 levels, levels == 1 ? "" : "s", nkeys); 311 if (F_ISSET(t, R_RECNO)) 312 (void)fprintf(stderr, " (%ld header count)", t->bt_nrecs); 313 (void)fprintf(stderr, 314 "\n%lu pages (leaf %ld, internal %ld, overflow %ld)\n", 315 pinternal + pleaf + pcont, pleaf, pinternal, pcont); 316 (void)fprintf(stderr, "%ld cache hits, %ld cache misses\n", 317 bt_cache_hit, bt_cache_miss); 318 (void)fprintf(stderr, "%ld splits (%ld root splits, %ld sort splits)\n", 319 bt_split, bt_rootsplit, bt_sortsplit); 320 pleaf *= t->bt_psize - BTDATAOFF; 321 if (pleaf) 322 (void)fprintf(stderr, 323 "%.0f%% leaf fill (%ld bytes used, %ld bytes free)\n", 324 ((double)(pleaf - lfree) / pleaf) * 100, 325 pleaf - lfree, lfree); 326 pinternal *= t->bt_psize - BTDATAOFF; 327 if (pinternal) 328 (void)fprintf(stderr, 329 "%.0f%% internal fill (%ld bytes used, %ld bytes free\n", 330 ((double)(pinternal - ifree) / pinternal) * 100, 331 pinternal - ifree, ifree); 332 if (bt_pfxsaved) 333 (void)fprintf(stderr, "prefix checking removed %lu bytes.\n", 334 bt_pfxsaved); 335 } 336 #endif 337