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