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