bt_stat.c 11.1 KB
Newer Older
unknown's avatar
unknown committed
1 2 3
/*-
 * See the file LICENSE for redistribution information.
 *
unknown's avatar
unknown committed
4
 * Copyright (c) 1996-2002
unknown's avatar
unknown committed
5 6 7 8 9 10
 *	Sleepycat Software.  All rights reserved.
 */

#include "db_config.h"

#ifndef lint
unknown's avatar
unknown committed
11
static const char revid[] = "$Id: bt_stat.c,v 11.52 2002/05/30 15:40:27 krinsky Exp $";
unknown's avatar
unknown committed
12 13 14 15 16 17 18 19 20
#endif /* not lint */

#ifndef NO_SYSTEM_INCLUDES
#include <sys/types.h>

#include <string.h>
#endif

#include "db_int.h"
unknown's avatar
unknown committed
21 22 23 24 25
#include "dbinc/db_page.h"
#include "dbinc/db_shash.h"
#include "dbinc/btree.h"
#include "dbinc/lock.h"
#include "dbinc/log.h"
unknown's avatar
unknown committed
26 27 28 29 30

/*
 * __bam_stat --
 *	Gather/print the btree statistics
 *
unknown's avatar
unknown committed
31
 * PUBLIC: int __bam_stat __P((DB *, void *, u_int32_t));
unknown's avatar
unknown committed
32 33
 */
int
unknown's avatar
unknown committed
34
__bam_stat(dbp, spp, flags)
unknown's avatar
unknown committed
35 36 37 38 39 40 41 42 43 44
	DB *dbp;
	void *spp;
	u_int32_t flags;
{
	BTMETA *meta;
	BTREE *t;
	BTREE_CURSOR *cp;
	DBC *dbc;
	DB_BTREE_STAT *sp;
	DB_LOCK lock, metalock;
unknown's avatar
unknown committed
45
	DB_MPOOLFILE *mpf;
unknown's avatar
unknown committed
46 47
	PAGE *h;
	db_pgno_t pgno;
unknown's avatar
unknown committed
48
	int ret, t_ret, write_meta;
unknown's avatar
unknown committed
49 50 51 52 53 54 55

	PANIC_CHECK(dbp->dbenv);
	DB_ILLEGAL_BEFORE_OPEN(dbp, "DB->stat");

	meta = NULL;
	t = dbp->bt_internal;
	sp = NULL;
unknown's avatar
unknown committed
56 57 58
	LOCK_INIT(metalock);
	LOCK_INIT(lock);
	mpf = dbp->mpf;
unknown's avatar
unknown committed
59 60
	h = NULL;
	ret = 0;
unknown's avatar
unknown committed
61
	write_meta = 0;
unknown's avatar
unknown committed
62 63 64 65 66 67 68 69 70 71 72 73 74

	/* Check for invalid flags. */
	if ((ret = __db_statchk(dbp, flags)) != 0)
		return (ret);

	/* Acquire a cursor. */
	if ((ret = dbp->cursor(dbp, NULL, &dbc, 0)) != 0)
		return (ret);
	cp = (BTREE_CURSOR *)dbc->internal;

	DEBUG_LWRITE(dbc, NULL, "bam_stat", NULL, NULL, flags);

	/* Allocate and clear the structure. */
unknown's avatar
unknown committed
75
	if ((ret = __os_umalloc(dbp->dbenv, sizeof(*sp), &sp)) != 0)
unknown's avatar
unknown committed
76 77 78 79 80 81 82
		goto err;
	memset(sp, 0, sizeof(*sp));

	/* Get the metadata page for the entire database. */
	pgno = PGNO_BASE_MD;
	if ((ret = __db_lget(dbc, 0, pgno, DB_LOCK_READ, 0, &metalock)) != 0)
		goto err;
unknown's avatar
unknown committed
83
	if ((ret = mpf->get(mpf, &pgno, 0, (PAGE **)&meta)) != 0)
unknown's avatar
unknown committed
84 85
		goto err;

unknown's avatar
unknown committed
86 87 88 89 90
	if (flags == DB_RECORDCOUNT || flags == DB_CACHED_COUNTS)
		flags = DB_FAST_STAT;
	if (flags == DB_FAST_STAT)
		goto meta_only;

unknown's avatar
unknown committed
91 92 93 94
	/* Walk the metadata free list, counting pages. */
	for (sp->bt_free = 0, pgno = meta->dbmeta.free; pgno != PGNO_INVALID;) {
		++sp->bt_free;

unknown's avatar
unknown committed
95
		if ((ret = mpf->get(mpf, &pgno, 0, &h)) != 0)
unknown's avatar
unknown committed
96 97 98
			goto err;

		pgno = h->next_pgno;
unknown's avatar
unknown committed
99
		if ((ret = mpf->put(mpf, h, 0)) != 0)
unknown's avatar
unknown committed
100 101 102 103 104 105 106 107
			goto err;
		h = NULL;
	}

	/* Get the root page. */
	pgno = cp->root;
	if ((ret = __db_lget(dbc, 0, pgno, DB_LOCK_READ, 0, &lock)) != 0)
		goto err;
unknown's avatar
unknown committed
108
	if ((ret = mpf->get(mpf, &pgno, 0, &h)) != 0)
unknown's avatar
unknown committed
109 110 111 112 113 114
		goto err;

	/* Get the levels from the root page. */
	sp->bt_levels = h->level;

	/* Discard the root page. */
unknown's avatar
unknown committed
115
	if ((ret = mpf->put(mpf, h, 0)) != 0)
unknown's avatar
unknown committed
116 117 118 119 120 121 122 123 124 125 126 127 128
		goto err;
	h = NULL;
	__LPUT(dbc, lock);

	/* Walk the tree. */
	if ((ret = __bam_traverse(dbc,
	    DB_LOCK_READ, cp->root, __bam_stat_callback, sp)) != 0)
		goto err;

	/*
	 * Get the subdatabase metadata page if it's not the same as the
	 * one we already have.
	 */
unknown's avatar
unknown committed
129 130 131 132
	write_meta = !F_ISSET(dbp, DB_AM_RDONLY);
meta_only:
	if (t->bt_meta != PGNO_BASE_MD || write_meta != 0) {
		if ((ret = mpf->put(mpf, meta, 0)) != 0)
unknown's avatar
unknown committed
133 134 135 136 137
			goto err;
		meta = NULL;
		__LPUT(dbc, metalock);

		if ((ret = __db_lget(dbc,
unknown's avatar
unknown committed
138
		    0, t->bt_meta, write_meta == 0 ?
unknown's avatar
unknown committed
139 140
		    DB_LOCK_READ : DB_LOCK_WRITE, 0, &metalock)) != 0)
			goto err;
unknown's avatar
unknown committed
141
		if ((ret = mpf->get(mpf, &t->bt_meta, 0, (PAGE **)&meta)) != 0)
unknown's avatar
unknown committed
142 143
			goto err;
	}
unknown's avatar
unknown committed
144 145 146 147 148 149 150 151 152 153 154 155 156 157 158
	if (flags == DB_FAST_STAT) {
		if (dbp->type == DB_RECNO ||
		    (dbp->type == DB_BTREE && F_ISSET(dbp, DB_AM_RECNUM))) {
			if ((ret = __db_lget(dbc, 0,
			    cp->root, DB_LOCK_READ, 0, &lock)) != 0)
				goto err;
			if ((ret =
			    mpf->get(mpf, &cp->root, 0, (PAGE **)&h)) != 0)
				goto err;

			sp->bt_nkeys = RE_NREC(h);
		} else
			sp->bt_nkeys = meta->dbmeta.key_count;
		sp->bt_ndata = meta->dbmeta.record_count;
	}
unknown's avatar
unknown committed
159 160 161 162 163 164 165 166 167 168

	/* Get metadata page statistics. */
	sp->bt_metaflags = meta->dbmeta.flags;
	sp->bt_maxkey = meta->maxkey;
	sp->bt_minkey = meta->minkey;
	sp->bt_re_len = meta->re_len;
	sp->bt_re_pad = meta->re_pad;
	sp->bt_pagesize = meta->dbmeta.pagesize;
	sp->bt_magic = meta->dbmeta.magic;
	sp->bt_version = meta->dbmeta.version;
unknown's avatar
unknown committed
169 170

	if (write_meta != 0) {
unknown's avatar
unknown committed
171 172 173 174
		meta->dbmeta.key_count = sp->bt_nkeys;
		meta->dbmeta.record_count = sp->bt_ndata;
	}

unknown's avatar
unknown committed
175
	*(DB_BTREE_STAT **)spp = sp;
unknown's avatar
unknown committed
176

unknown's avatar
unknown committed
177 178 179
err:	/* Discard the second page. */
	__LPUT(dbc, lock);
	if (h != NULL && (t_ret = mpf->put(mpf, h, 0)) != 0 && ret == 0)
unknown's avatar
unknown committed
180 181
		ret = t_ret;

unknown's avatar
unknown committed
182 183 184 185
	/* Discard the metadata page. */
	__LPUT(dbc, metalock);
	if (meta != NULL && (t_ret = mpf->put(
	    mpf, meta, write_meta == 0 ? 0 : DB_MPOOL_DIRTY)) != 0 && ret == 0)
unknown's avatar
unknown committed
186 187 188 189 190
		ret = t_ret;

	if ((t_ret = dbc->c_close(dbc)) != 0 && ret == 0)
		ret = t_ret;

unknown's avatar
unknown committed
191 192 193 194 195
	if (ret != 0 && sp != NULL) {
		__os_ufree(dbp->dbenv, sp);
		*(DB_BTREE_STAT **)spp = NULL;
	}

unknown's avatar
unknown committed
196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217
	return (ret);
}

/*
 * __bam_traverse --
 *	Walk a Btree database.
 *
 * PUBLIC: int __bam_traverse __P((DBC *, db_lockmode_t,
 * PUBLIC:     db_pgno_t, int (*)(DB *, PAGE *, void *, int *), void *));
 */
int
__bam_traverse(dbc, mode, root_pgno, callback, cookie)
	DBC *dbc;
	db_lockmode_t mode;
	db_pgno_t root_pgno;
	int (*callback)__P((DB *, PAGE *, void *, int *));
	void *cookie;
{
	BINTERNAL *bi;
	BKEYDATA *bk;
	DB *dbp;
	DB_LOCK lock;
unknown's avatar
unknown committed
218
	DB_MPOOLFILE *mpf;
unknown's avatar
unknown committed
219 220 221 222 223 224
	PAGE *h;
	RINTERNAL *ri;
	db_indx_t indx;
	int already_put, ret, t_ret;

	dbp = dbc->dbp;
unknown's avatar
unknown committed
225 226
	mpf = dbp->mpf;
	already_put = 0;
unknown's avatar
unknown committed
227 228 229

	if ((ret = __db_lget(dbc, 0, root_pgno, mode, 0, &lock)) != 0)
		return (ret);
unknown's avatar
unknown committed
230 231 232 233
	if ((ret = mpf->get(mpf, &root_pgno, 0, &h)) != 0) {
		__LPUT(dbc, lock);
		return (ret);
	}
unknown's avatar
unknown committed
234 235 236 237

	switch (TYPE(h)) {
	case P_IBTREE:
		for (indx = 0; indx < NUM_ENT(h); indx += O_INDX) {
unknown's avatar
unknown committed
238
			bi = GET_BINTERNAL(dbp, h, indx);
unknown's avatar
unknown committed
239 240 241 242 243 244 245
			if (B_TYPE(bi->type) == B_OVERFLOW &&
			    (ret = __db_traverse_big(dbp,
			    ((BOVERFLOW *)bi->data)->pgno,
			    callback, cookie)) != 0)
				goto err;
			if ((ret = __bam_traverse(
			    dbc, mode, bi->pgno, callback, cookie)) != 0)
unknown's avatar
unknown committed
246
				goto err;
unknown's avatar
unknown committed
247 248 249 250
		}
		break;
	case P_IRECNO:
		for (indx = 0; indx < NUM_ENT(h); indx += O_INDX) {
unknown's avatar
unknown committed
251
			ri = GET_RINTERNAL(dbp, h, indx);
unknown's avatar
unknown committed
252 253
			if ((ret = __bam_traverse(
			    dbc, mode, ri->pgno, callback, cookie)) != 0)
unknown's avatar
unknown committed
254
				goto err;
unknown's avatar
unknown committed
255 256 257 258
		}
		break;
	case P_LBTREE:
		for (indx = 0; indx < NUM_ENT(h); indx += P_INDX) {
unknown's avatar
unknown committed
259
			bk = GET_BKEYDATA(dbp, h, indx);
unknown's avatar
unknown committed
260 261
			if (B_TYPE(bk->type) == B_OVERFLOW &&
			    (ret = __db_traverse_big(dbp,
unknown's avatar
unknown committed
262
			    GET_BOVERFLOW(dbp, h, indx)->pgno,
unknown's avatar
unknown committed
263 264
			    callback, cookie)) != 0)
				goto err;
unknown's avatar
unknown committed
265
			bk = GET_BKEYDATA(dbp, h, indx + O_INDX);
unknown's avatar
unknown committed
266 267
			if (B_TYPE(bk->type) == B_DUPLICATE &&
			    (ret = __bam_traverse(dbc, mode,
unknown's avatar
unknown committed
268
			    GET_BOVERFLOW(dbp, h, indx + O_INDX)->pgno,
unknown's avatar
unknown committed
269 270 271 272
			    callback, cookie)) != 0)
				goto err;
			if (B_TYPE(bk->type) == B_OVERFLOW &&
			    (ret = __db_traverse_big(dbp,
unknown's avatar
unknown committed
273
			    GET_BOVERFLOW(dbp, h, indx + O_INDX)->pgno,
unknown's avatar
unknown committed
274 275 276 277 278 279 280
			    callback, cookie)) != 0)
				goto err;
		}
		break;
	case P_LDUP:
	case P_LRECNO:
		for (indx = 0; indx < NUM_ENT(h); indx += O_INDX) {
unknown's avatar
unknown committed
281
			bk = GET_BKEYDATA(dbp, h, indx);
unknown's avatar
unknown committed
282 283
			if (B_TYPE(bk->type) == B_OVERFLOW &&
			    (ret = __db_traverse_big(dbp,
unknown's avatar
unknown committed
284
			    GET_BOVERFLOW(dbp, h, indx)->pgno,
unknown's avatar
unknown committed
285 286 287 288 289 290
			    callback, cookie)) != 0)
				goto err;
		}
		break;
	}

unknown's avatar
unknown committed
291
	ret = callback(dbp, h, cookie, &already_put);
unknown's avatar
unknown committed
292

unknown's avatar
unknown committed
293
err:	if (!already_put && (t_ret = mpf->put(mpf, h, 0)) != 0 && ret != 0)
unknown's avatar
unknown committed
294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313
		ret = t_ret;
	__LPUT(dbc, lock);

	return (ret);
}

/*
 * __bam_stat_callback --
 *	Statistics callback.
 *
 * PUBLIC: int __bam_stat_callback __P((DB *, PAGE *, void *, int *));
 */
int
__bam_stat_callback(dbp, h, cookie, putp)
	DB *dbp;
	PAGE *h;
	void *cookie;
	int *putp;
{
	DB_BTREE_STAT *sp;
unknown's avatar
unknown committed
314
	db_indx_t indx, *inp, top;
unknown's avatar
unknown committed
315 316 317 318 319
	u_int8_t type;

	sp = cookie;
	*putp = 0;
	top = NUM_ENT(h);
unknown's avatar
unknown committed
320
	inp = P_INP(dbp, h);
unknown's avatar
unknown committed
321 322 323 324 325

	switch (TYPE(h)) {
	case P_IBTREE:
	case P_IRECNO:
		++sp->bt_int_pg;
unknown's avatar
unknown committed
326
		sp->bt_int_pgfree += P_FREESPACE(dbp, h);
unknown's avatar
unknown committed
327 328 329 330 331
		break;
	case P_LBTREE:
		/* Correct for on-page duplicates and deleted items. */
		for (indx = 0; indx < top; indx += P_INDX) {
			if (indx + P_INDX >= top ||
unknown's avatar
unknown committed
332
			    inp[indx] != inp[indx + P_INDX])
unknown's avatar
unknown committed
333 334
				++sp->bt_nkeys;

unknown's avatar
unknown committed
335
			type = GET_BKEYDATA(dbp, h, indx + O_INDX)->type;
unknown's avatar
unknown committed
336 337 338 339 340
			if (!B_DISSET(type) && B_TYPE(type) != B_DUPLICATE)
				++sp->bt_ndata;
		}

		++sp->bt_leaf_pg;
unknown's avatar
unknown committed
341
		sp->bt_leaf_pgfree += P_FREESPACE(dbp, h);
unknown's avatar
unknown committed
342 343 344 345 346 347 348 349 350 351 352 353 354
		break;
	case P_LRECNO:
		/*
		 * If walking a recno tree, then each of these items is a key.
		 * Otherwise, we're walking an off-page duplicate set.
		 */
		if (dbp->type == DB_RECNO) {
			sp->bt_nkeys += top;

			/*
			 * Correct for deleted items in non-renumbering
			 * Recno databases.
			 */
unknown's avatar
unknown committed
355
			if (F_ISSET(dbp, DB_AM_RENUMBER))
unknown's avatar
unknown committed
356 357 358
				sp->bt_ndata += top;
			else
				for (indx = 0; indx < top; indx += O_INDX) {
unknown's avatar
unknown committed
359
					type = GET_BKEYDATA(dbp, h, indx)->type;
unknown's avatar
unknown committed
360 361 362 363 364
					if (!B_DISSET(type))
						++sp->bt_ndata;
				}

			++sp->bt_leaf_pg;
unknown's avatar
unknown committed
365
			sp->bt_leaf_pgfree += P_FREESPACE(dbp, h);
unknown's avatar
unknown committed
366 367 368 369
		} else {
			sp->bt_ndata += top;

			++sp->bt_dup_pg;
unknown's avatar
unknown committed
370
			sp->bt_dup_pgfree += P_FREESPACE(dbp, h);
unknown's avatar
unknown committed
371 372 373 374 375
		}
		break;
	case P_LDUP:
		/* Correct for deleted items. */
		for (indx = 0; indx < top; indx += O_INDX)
unknown's avatar
unknown committed
376
			if (!B_DISSET(GET_BKEYDATA(dbp, h, indx)->type))
unknown's avatar
unknown committed
377 378 379
				++sp->bt_ndata;

		++sp->bt_dup_pg;
unknown's avatar
unknown committed
380
		sp->bt_dup_pgfree += P_FREESPACE(dbp, h);
unknown's avatar
unknown committed
381 382 383
		break;
	case P_OVERFLOW:
		++sp->bt_over_pg;
unknown's avatar
unknown committed
384
		sp->bt_over_pgfree += P_OVFLSPACE(dbp, dbp->pgsize, h);
unknown's avatar
unknown committed
385 386
		break;
	default:
unknown's avatar
unknown committed
387
		return (__db_pgfmt(dbp->dbenv, h->pgno));
unknown's avatar
unknown committed
388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419
	}
	return (0);
}

/*
 * __bam_key_range --
 *	Return proportion of keys relative to given key.  The numbers are
 *	slightly skewed due to on page duplicates.
 *
 * PUBLIC: int __bam_key_range __P((DB *,
 * PUBLIC:     DB_TXN *, DBT *, DB_KEY_RANGE *, u_int32_t));
 */
int
__bam_key_range(dbp, txn, dbt, kp, flags)
	DB *dbp;
	DB_TXN *txn;
	DBT *dbt;
	DB_KEY_RANGE *kp;
	u_int32_t flags;
{
	BTREE_CURSOR *cp;
	DBC *dbc;
	EPG *sp;
	double factor;
	int exact, ret, t_ret;

	PANIC_CHECK(dbp->dbenv);
	DB_ILLEGAL_BEFORE_OPEN(dbp, "DB->key_range");

	if (flags != 0)
		return (__db_ferr(dbp->dbenv, "DB->key_range", 0));

unknown's avatar
unknown committed
420 421 422 423
	/* Check for consistent transaction usage. */
	if ((ret = __db_check_txn(dbp, txn, DB_LOCK_INVALIDID, 1)) != 0)
		return (ret);

unknown's avatar
unknown committed
424 425 426 427 428 429
	/* Acquire a cursor. */
	if ((ret = dbp->cursor(dbp, txn, &dbc, 0)) != 0)
		return (ret);

	DEBUG_LWRITE(dbc, NULL, "bam_key_range", NULL, NULL, 0);

unknown's avatar
unknown committed
430 431
	if ((ret = __bam_search(dbc, PGNO_INVALID,
	    dbt, S_STK_ONLY, 1, NULL, &exact)) != 0)
unknown's avatar
unknown committed
432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481
		goto err;

	cp = (BTREE_CURSOR *)dbc->internal;
	kp->less = kp->greater = 0.0;

	factor = 1.0;
	/* Correct the leaf page. */
	cp->csp->entries /= 2;
	cp->csp->indx /= 2;
	for (sp = cp->sp; sp <= cp->csp; ++sp) {
		/*
		 * At each level we know that pages greater than indx contain
		 * keys greater than what we are looking for and those less
		 * than indx are less than.  The one pointed to by indx may
		 * have some less, some greater or even equal.  If indx is
		 * equal to the number of entries, then the key is out of range
		 * and everything is less.
		 */
		if (sp->indx == 0)
			kp->greater += factor * (sp->entries - 1)/sp->entries;
		else if (sp->indx == sp->entries)
			kp->less += factor;
		else {
			kp->less += factor * sp->indx / sp->entries;
			kp->greater += factor *
			    (sp->entries - sp->indx - 1) / sp->entries;
		}
		factor *= 1.0/sp->entries;
	}

	/*
	 * If there was an exact match then assign 1 n'th to the key itself.
	 * Otherwise that factor belongs to those greater than the key, unless
	 * the key was out of range.
	 */
	if (exact)
		kp->equal = factor;
	else {
		if (kp->less != 1)
			kp->greater += factor;
		kp->equal = 0;
	}

	BT_STK_CLR(cp);

err:	if ((t_ret = dbc->c_close(dbc)) != 0 && ret == 0)
		ret = t_ret;

	return (ret);
}