1 /* $NetBSD: bt_debug.c,v 1.19 2016/10/09 11:48:24 joerg 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 HAVE_NBTOOL_CONFIG_H
36 #include "nbtool_config.h"
37 #endif
38
39 #include <sys/cdefs.h>
40 __RCSID("$NetBSD: bt_debug.c,v 1.19 2016/10/09 11:48:24 joerg Exp $");
41
42 #include <assert.h>
43 #include <stdio.h>
44 #include <stdlib.h>
45 #include <string.h>
46
47 #include <db.h>
48 #include "btree.h"
49
50 #if defined(DEBUG) || defined(STATISTICS)
51
52 static FILE *tracefp;
53
54 /*
55 * __bt_dinit --
56 * initialize debugging.
57 */
58 static void
__bt_dinit(void)59 __bt_dinit(void)
60 {
61 if (tracefp != NULL)
62 return;
63
64 #ifndef TRACE_TO_STDERR
65 if ((tracefp = fopen("/tmp/__bt_debug", "w")) != NULL)
66 return;
67 #endif
68 tracefp = stderr;
69 }
70 #endif
71
72
73 #ifdef DEBUG
74 /*
75 * BT_DUMP -- Dump the tree
76 *
77 * Parameters:
78 * dbp: pointer to the DB
79 */
80 void
__bt_dump(DB * dbp)81 __bt_dump(DB *dbp)
82 {
83 BTREE *t;
84 PAGE *h;
85 pgno_t i;
86 const char *sep;
87
88 __bt_dinit();
89
90 t = dbp->internal;
91 (void)fprintf(tracefp, "%s: pgsz %d",
92 F_ISSET(t, B_INMEM) ? "memory" : "disk", t->bt_psize);
93 if (F_ISSET(t, R_RECNO))
94 (void)fprintf(tracefp, " keys %lu", (unsigned long) t->bt_nrecs);
95 #undef X
96 #define X(flag, name) \
97 if (F_ISSET(t, flag)) { \
98 (void)fprintf(tracefp, "%s%s", sep, name); \
99 sep = ", "; \
100 }
101 if (t->flags != 0) {
102 sep = " flags (";
103 X(R_FIXLEN, "FIXLEN");
104 X(B_INMEM, "INMEM");
105 X(B_NODUPS, "NODUPS");
106 X(B_RDONLY, "RDONLY");
107 X(R_RECNO, "RECNO");
108 X(B_METADIRTY,"METADIRTY");
109 (void)fprintf(tracefp, ")\n");
110 }
111 #undef X
112
113 for (i = P_ROOT; i < t->bt_mp->npages &&
114 (h = mpool_get(t->bt_mp, i, MPOOL_IGNOREPIN)) != NULL; ++i)
115 __bt_dpage(h);
116
117 (void)fflush(tracefp);
118 }
119
120 /*
121 * BT_DMPAGE -- Dump the meta page
122 *
123 * Parameters:
124 * h: pointer to the PAGE
125 */
126 void
__bt_dmpage(PAGE * h)127 __bt_dmpage(PAGE *h)
128 {
129 BTMETA *m;
130 const char *sep;
131
132 m = (BTMETA *)(void *)h;
133 (void)fprintf(tracefp, "magic %lx\n", (unsigned long) m->magic);
134 (void)fprintf(tracefp, "version %lu\n", (unsigned long) m->version);
135 (void)fprintf(tracefp, "psize %lu\n", (unsigned long) m->psize);
136 (void)fprintf(tracefp, "free %lu\n", (unsigned long) m->free);
137 (void)fprintf(tracefp, "nrecs %lu\n", (unsigned long) m->nrecs);
138 (void)fprintf(tracefp, "flags %lu", (unsigned long) m->flags);
139 #undef X
140 #define X(flag, name) \
141 if (m->flags & flag) { \
142 (void)fprintf(tracefp, "%s%s", sep, name); \
143 sep = ", "; \
144 }
145 if (m->flags) {
146 sep = " (";
147 X(B_NODUPS, "NODUPS");
148 X(R_RECNO, "RECNO");
149 (void)fprintf(tracefp, ")");
150 }
151 (void)fprintf(tracefp, "\n");
152 (void)fflush(tracefp);
153 }
154
155 static pgno_t
__bt_pgno_t(const void * m)156 __bt_pgno_t(const void *m)
157 {
158 pgno_t r;
159 memcpy(&r, m, sizeof(r));
160 return r;
161 }
162
163 static uint32_t
__bt_uint32_t(const void * m)164 __bt_uint32_t(const void *m)
165 {
166 uint32_t r;
167 memcpy(&r, m, sizeof(r));
168 return r;
169 }
170
171 /*
172 * BT_DNPAGE -- Dump the page
173 *
174 * Parameters:
175 * n: page number to dump.
176 */
177 void
__bt_dnpage(DB * dbp,pgno_t pgno)178 __bt_dnpage(DB *dbp, pgno_t pgno)
179 {
180 BTREE *t;
181 PAGE *h;
182
183 __bt_dinit();
184
185 t = dbp->internal;
186 if ((h = mpool_get(t->bt_mp, pgno, MPOOL_IGNOREPIN)) != NULL) {
187 __bt_dpage(h);
188 (void)mpool_put(t->bt_mp, h, 0);
189 }
190 (void)fflush(tracefp);
191 }
192
193 /*
194 * BT_DPAGE -- Dump the page
195 *
196 * Parameters:
197 * h: pointer to the PAGE
198 */
199 void
__bt_dpage(PAGE * h)200 __bt_dpage(PAGE *h)
201 {
202 BINTERNAL *bi;
203 BLEAF *bl;
204 RINTERNAL *ri;
205 RLEAF *rl;
206 indx_t cur, top;
207 const char *sep;
208
209 __bt_dinit();
210
211 (void)fprintf(tracefp, " page %d: (", h->pgno);
212 #undef X
213 #define X(flag, name) \
214 if (h->flags & flag) { \
215 (void)fprintf(tracefp, "%s%s", sep, name); \
216 sep = ", "; \
217 }
218 sep = "";
219 X(P_BINTERNAL, "BINTERNAL") /* types */
220 X(P_BLEAF, "BLEAF")
221 X(P_RINTERNAL, "RINTERNAL") /* types */
222 X(P_RLEAF, "RLEAF")
223 X(P_OVERFLOW, "OVERFLOW")
224 X(P_PRESERVE, "PRESERVE");
225 (void)fprintf(tracefp, ")\n");
226 #undef X
227
228 (void)fprintf(tracefp, "\tprev %2d next %2d", h->prevpg, h->nextpg);
229 if (h->flags & P_OVERFLOW)
230 return;
231
232 top = NEXTINDEX(h);
233 (void)fprintf(tracefp, " lower %3d upper %3d nextind %d\n",
234 h->lower, h->upper, top);
235 for (cur = 0; cur < top; cur++) {
236 (void)fprintf(tracefp, "\t[%03d] %4d ", cur, h->linp[cur]);
237 switch (h->flags & P_TYPE) {
238 case P_BINTERNAL:
239 bi = GETBINTERNAL(h, cur);
240 (void)fprintf(tracefp,
241 "size %03d pgno %03d", bi->ksize, bi->pgno);
242 if (bi->flags & P_BIGKEY)
243 (void)fprintf(tracefp, " (indirect)");
244 else if (bi->ksize)
245 (void)fprintf(tracefp,
246 " {%.*s}", (int)bi->ksize, bi->bytes);
247 break;
248 case P_RINTERNAL:
249 ri = GETRINTERNAL(h, cur);
250 (void)fprintf(tracefp, "entries %03d pgno %03d",
251 ri->nrecs, ri->pgno);
252 break;
253 case P_BLEAF:
254 bl = GETBLEAF(h, cur);
255 if (bl->flags & P_BIGKEY)
256 (void)fprintf(tracefp,
257 "big key page %lu size %u/",
258 (unsigned long) __bt_pgno_t(bl->bytes),
259 __bt_uint32_t(bl->bytes + sizeof(pgno_t)));
260 else if (bl->ksize)
261 (void)fprintf(tracefp, "%s/", bl->bytes);
262 if (bl->flags & P_BIGDATA)
263 (void)fprintf(tracefp,
264 "big data page %lu size %u",
265 (unsigned long)
266 __bt_pgno_t(bl->bytes + bl->ksize),
267 __bt_uint32_t(bl->bytes + bl->ksize +
268 sizeof(pgno_t)));
269 else if (bl->dsize)
270 (void)fprintf(tracefp, "%.*s",
271 (int)bl->dsize, bl->bytes + bl->ksize);
272 break;
273 case P_RLEAF:
274 rl = GETRLEAF(h, cur);
275 if (rl->flags & P_BIGDATA)
276 (void)fprintf(tracefp,
277 "big data page %lu size %u",
278 (unsigned long) __bt_pgno_t(rl->bytes),
279 __bt_uint32_t(rl->bytes + sizeof(pgno_t)));
280 else if (rl->dsize)
281 (void)fprintf(tracefp,
282 "%.*s", (int)rl->dsize, rl->bytes);
283 break;
284 }
285 (void)fprintf(tracefp, "\n");
286 }
287 (void)fflush(tracefp);
288 }
289 #endif
290
291 #ifdef STATISTICS
292 /*
293 * BT_STAT -- Gather/print the tree statistics
294 *
295 * Parameters:
296 * dbp: pointer to the DB
297 */
298 void
__bt_stat(DB * dbp)299 __bt_stat(DB *dbp)
300 {
301 extern unsigned long bt_cache_hit, bt_cache_miss, bt_pfxsaved, bt_rootsplit;
302 extern unsigned long bt_sortsplit, bt_split;
303 BTREE *t;
304 PAGE *h;
305 pgno_t i, pcont, pinternal, pleaf;
306 unsigned long ifree, lfree, nkeys;
307 int levels;
308
309 __bt_dinit();
310
311 t = dbp->internal;
312 pcont = pinternal = pleaf = 0;
313 nkeys = ifree = lfree = 0;
314 for (i = P_ROOT; i < t->bt_mp->npages &&
315 (h = mpool_get(t->bt_mp, i, MPOOL_IGNOREPIN)) != NULL; ++i) {
316 switch (h->flags & P_TYPE) {
317 case P_BINTERNAL:
318 case P_RINTERNAL:
319 ++pinternal;
320 ifree += h->upper - h->lower;
321 break;
322 case P_BLEAF:
323 case P_RLEAF:
324 ++pleaf;
325 lfree += h->upper - h->lower;
326 nkeys += NEXTINDEX(h);
327 break;
328 case P_OVERFLOW:
329 ++pcont;
330 break;
331 }
332 (void)mpool_put(t->bt_mp, h, 0);
333 }
334
335 /* Count the levels of the tree. */
336 for (i = P_ROOT, levels = 0 ;; ++levels) {
337 h = mpool_get(t->bt_mp, i, MPOOL_IGNOREPIN);
338 if (h->flags & (P_BLEAF|P_RLEAF)) {
339 if (levels == 0)
340 levels = 1;
341 (void)mpool_put(t->bt_mp, h, 0);
342 break;
343 }
344 i = F_ISSET(t, R_RECNO) ?
345 GETRINTERNAL(h, 0)->pgno :
346 GETBINTERNAL(h, 0)->pgno;
347 (void)mpool_put(t->bt_mp, h, 0);
348 }
349
350 (void)fprintf(tracefp, "%d level%s with %ld keys",
351 levels, levels == 1 ? "" : "s", nkeys);
352 if (F_ISSET(t, R_RECNO))
353 (void)fprintf(tracefp, " (%ld header count)", (long)t->bt_nrecs);
354 (void)fprintf(tracefp,
355 "\n%lu pages (leaf %ld, internal %ld, overflow %ld)\n",
356 (long)pinternal + pleaf + pcont, (long)pleaf, (long)pinternal,
357 (long)pcont);
358 (void)fprintf(tracefp, "%ld cache hits, %ld cache misses\n",
359 bt_cache_hit, bt_cache_miss);
360 (void)fprintf(tracefp, "%ld splits (%ld root splits, %ld sort splits)\n",
361 bt_split, bt_rootsplit, bt_sortsplit);
362 pleaf *= t->bt_psize - BTDATAOFF;
363 if (pleaf)
364 (void)fprintf(tracefp,
365 "%.0f%% leaf fill (%ld bytes used, %ld bytes free)\n",
366 ((double)(pleaf - lfree) / pleaf) * 100,
367 pleaf - lfree, lfree);
368 pinternal *= t->bt_psize - BTDATAOFF;
369 if (pinternal)
370 (void)fprintf(tracefp,
371 "%.0f%% internal fill (%ld bytes used, %ld bytes free\n",
372 ((double)(pinternal - ifree) / pinternal) * 100,
373 pinternal - ifree, ifree);
374 if (bt_pfxsaved)
375 (void)fprintf(tracefp, "prefix checking removed %lu bytes.\n",
376 bt_pfxsaved);
377 (void)fflush(tracefp);
378 }
379 #endif
380