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