2
* See the file LICENSE for redistribution information.
4
* Copyright (c) 1996-2001
5
* Sleepycat Software. All rights reserved.
8
* Copyright (c) 1990, 1993, 1994, 1995, 1996
9
* Keith Bostic. All rights reserved.
12
* Copyright (c) 1990, 1993, 1994, 1995
13
* The Regents of the University of California. All rights reserved.
15
* This code is derived from software contributed to Berkeley by
18
* Redistribution and use in source and binary forms, with or without
19
* modification, are permitted provided that the following conditions
21
* 1. Redistributions of source code must retain the above copyright
22
* notice, this list of conditions and the following disclaimer.
23
* 2. Redistributions in binary form must reproduce the above copyright
24
* notice, this list of conditions and the following disclaimer in the
25
* documentation and/or other materials provided with the distribution.
26
* 3. Neither the name of the University nor the names of its contributors
27
* may be used to endorse or promote products derived from this software
28
* without specific prior written permission.
30
* THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
31
* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
32
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
33
* ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
34
* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
35
* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
36
* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
37
* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
38
* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
39
* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
43
#include "db_config.h"
46
static const char revid[] = "$Id: db_overflow.c,v 11.33 2001/06/14 20:56:40 krinsky Exp $";
49
#ifndef NO_SYSTEM_INCLUDES
50
#include <sys/types.h>
58
#include "db_verify.h"
63
* Big key and data entries are stored on linked lists of pages. The initial
64
* reference is a structure with the total length of the item and the page
65
* number where it begins. Each entry in the linked list contains a pointer
66
* to the next page of data, and so on.
71
* Get an offpage item.
73
* PUBLIC: int __db_goff __P((DB *, DBT *,
74
* PUBLIC: u_int32_t, db_pgno_t, void **, u_int32_t *));
77
__db_goff(dbp, dbt, tlen, pgno, bpp, bpsz)
88
u_int32_t curoff, needed, start;
95
* Check if the buffer is big enough; if it is not and we are
96
* allowed to malloc space, then we'll malloc it. If we are
97
* not (DB_DBT_USERMEM), then we'll set the dbt and return
100
if (F_ISSET(dbt, DB_DBT_PARTIAL)) {
104
else if (dbt->dlen > tlen - start)
105
needed = tlen - start;
113
/* Allocate any necessary memory. */
114
if (F_ISSET(dbt, DB_DBT_USERMEM)) {
115
if (needed > dbt->ulen) {
119
} else if (F_ISSET(dbt, DB_DBT_MALLOC)) {
120
if ((ret = __os_umalloc(dbenv, needed, &dbt->data)) != 0)
122
} else if (F_ISSET(dbt, DB_DBT_REALLOC)) {
123
if ((ret = __os_urealloc(dbenv, needed, &dbt->data)) != 0)
125
} else if (*bpsz == 0 || *bpsz < needed) {
126
if ((ret = __os_realloc(dbenv, needed, bpp)) != 0)
134
* Step through the linked list of pages, copying the data on each
135
* one into the buffer. Never copy more than the total data length.
138
for (curoff = 0, p = dbt->data; pgno != PGNO_INVALID && needed > 0;) {
139
if ((ret = memp_fget(dbp->mpf, &pgno, 0, &h)) != 0) {
140
(void)__db_pgerr(dbp, pgno);
143
/* Check if we need any bytes from this page. */
144
if (curoff + OV_LEN(h) >= start) {
145
src = (u_int8_t *)h + P_OVERHEAD;
147
if (start > curoff) {
148
src += start - curoff;
149
bytes -= start - curoff;
153
memcpy(p, src, bytes);
159
(void)memp_fput(dbp->mpf, h, 0);
166
* Put an offpage item.
168
* PUBLIC: int __db_poff __P((DBC *, const DBT *, db_pgno_t *));
171
__db_poff(dbc, dbt, pgnop)
178
DB_LSN new_lsn, null_lsn;
186
* Allocate pages and copy the key/data item into them. Calculate the
187
* number of bytes we get for pages we fill completely with a single
191
pagespace = P_MAXSPACE(dbp->pgsize);
196
sz = dbt->size; sz > 0; p += pagespace, sz -= pagespace) {
198
* Reduce pagespace so we terminate the loop correctly and
199
* don't copy too much data.
205
* Allocate and initialize a new page and copy all or part of
206
* the item onto the page. If sz is less than pagespace, we
207
* have a partial record.
209
if ((ret = __db_new(dbc, P_OVERFLOW, &pagep)) != 0)
211
if (DB_LOGGING(dbc)) {
213
tmp_dbt.size = pagespace;
215
if ((ret = __db_big_log(dbp->dbenv, dbc->txn,
216
&new_lsn, 0, DB_ADD_BIG, dbp->log_fileid,
217
PGNO(pagep), lastp ? PGNO(lastp) : PGNO_INVALID,
218
PGNO_INVALID, &tmp_dbt, &LSN(pagep),
219
lastp == NULL ? &null_lsn : &LSN(lastp),
222
(void)memp_fput(dbp->mpf,
223
lastp, DB_MPOOL_DIRTY);
228
LSN_NOT_LOGGED(new_lsn);
229
/* Move lsn onto page. */
231
LSN(lastp) = new_lsn;
232
LSN(pagep) = new_lsn;
234
P_INIT(pagep, dbp->pgsize,
235
PGNO(pagep), PGNO_INVALID, PGNO_INVALID, 0, P_OVERFLOW);
236
OV_LEN(pagep) = pagespace;
238
memcpy((u_int8_t *)pagep + P_OVERHEAD, p, pagespace);
241
* If this is the first entry, update the user's info.
242
* Otherwise, update the entry on the last page filled
243
* in and release that page.
246
*pgnop = PGNO(pagep);
248
lastp->next_pgno = PGNO(pagep);
249
pagep->prev_pgno = PGNO(lastp);
250
(void)memp_fput(dbp->mpf, lastp, DB_MPOOL_DIRTY);
255
memp_fput(dbp->mpf, lastp, DB_MPOOL_DIRTY)) != 0 && ret == 0)
262
* Increment/decrement the reference count on an overflow page.
264
* PUBLIC: int __db_ovref __P((DBC *, db_pgno_t, int32_t));
267
__db_ovref(dbc, pgno, adjust)
277
if ((ret = memp_fget(dbp->mpf, &pgno, 0, &h)) != 0) {
278
(void)__db_pgerr(dbp, pgno);
282
if (DB_LOGGING(dbc)) {
283
if ((ret = __db_ovref_log(dbp->dbenv, dbc->txn,
284
&LSN(h), 0, dbp->log_fileid, h->pgno, adjust,
288
LSN_NOT_LOGGED(LSN(h));
291
(void)memp_fput(dbp->mpf, h, DB_MPOOL_DIRTY);
297
* Delete an offpage chain of overflow pages.
299
* PUBLIC: int __db_doff __P((DBC *, db_pgno_t));
314
if ((ret = memp_fget(dbp->mpf, &pgno, 0, &pagep)) != 0) {
315
(void)__db_pgerr(dbp, pgno);
319
DB_ASSERT(TYPE(pagep) == P_OVERFLOW);
321
* If it's referenced by more than one key/data item,
322
* decrement the reference count and return.
324
if (OV_REF(pagep) > 1) {
325
(void)memp_fput(dbp->mpf, pagep, 0);
326
return (__db_ovref(dbc, pgno, -1));
329
if (DB_LOGGING(dbc)) {
330
tmp_dbt.data = (u_int8_t *)pagep + P_OVERHEAD;
331
tmp_dbt.size = OV_LEN(pagep);
333
if ((ret = __db_big_log(dbp->dbenv, dbc->txn,
334
&LSN(pagep), 0, DB_REM_BIG, dbp->log_fileid,
335
PGNO(pagep), PREV_PGNO(pagep),
336
NEXT_PGNO(pagep), &tmp_dbt,
337
&LSN(pagep), &null_lsn, &null_lsn)) != 0) {
338
(void)memp_fput(dbp->mpf, pagep, 0);
342
LSN_NOT_LOGGED(LSN(pagep));
343
pgno = pagep->next_pgno;
344
if ((ret = __db_free(dbc, pagep)) != 0)
346
} while (pgno != PGNO_INVALID);
353
* Match on overflow pages.
355
* Given a starting page number and a key, return <0, 0, >0 to indicate if the
356
* key on the page is less than, equal to or greater than the key specified.
357
* We optimize this by doing chunk at a time comparison unless the user has
358
* specified a comparison function. In this case, we need to materialize
359
* the entire object and call their comparison routine.
361
* PUBLIC: int __db_moff __P((DB *, const DBT *, db_pgno_t, u_int32_t,
362
* PUBLIC: int (*)(DB *, const DBT *, const DBT *), int *));
365
__db_moff(dbp, dbt, pgno, tlen, cmpfunc, cmpp)
370
int (*cmpfunc) __P((DB *, const DBT *, const DBT *)), *cmpp;
375
u_int32_t bufsize, cmp_bytes, key_left;
380
* If there is a user-specified comparison function, build a
381
* contiguous copy of the key, and call it.
383
if (cmpfunc != NULL) {
384
memset(&local_dbt, 0, sizeof(local_dbt));
388
if ((ret = __db_goff(dbp,
389
&local_dbt, tlen, pgno, &buf, &bufsize)) != 0)
391
/* Pass the key as the first argument */
392
*cmpp = cmpfunc(dbp, dbt, &local_dbt);
393
__os_free(dbp->dbenv, buf, bufsize);
397
/* While there are both keys to compare. */
398
for (*cmpp = 0, p1 = dbt->data,
399
key_left = dbt->size; key_left > 0 && pgno != PGNO_INVALID;) {
400
if ((ret = memp_fget(dbp->mpf, &pgno, 0, &pagep)) != 0)
403
cmp_bytes = OV_LEN(pagep) < key_left ? OV_LEN(pagep) : key_left;
405
key_left -= cmp_bytes;
407
(u_int8_t *)pagep + P_OVERHEAD; cmp_bytes-- > 0; ++p1, ++p2)
409
*cmpp = (long)*p1 - (long)*p2;
412
pgno = NEXT_PGNO(pagep);
413
if ((ret = memp_fput(dbp->mpf, pagep, 0)) != 0)
418
if (key_left > 0) /* DBT is longer than the page key. */
420
else if (tlen > 0) /* DBT is shorter than the page key. */
429
* __db_vrfy_overflow --
430
* Verify overflow page.
432
* PUBLIC: int __db_vrfy_overflow __P((DB *, VRFY_DBINFO *, PAGE *, db_pgno_t,
433
* PUBLIC: u_int32_t));
436
__db_vrfy_overflow(dbp, vdp, h, pgno, flags)
444
int isbad, ret, t_ret;
447
if ((ret = __db_vrfy_getpageinfo(vdp, pgno, &pip)) != 0)
450
if ((ret = __db_vrfy_datapage(dbp, vdp, h, pgno, flags)) != 0) {
451
if (ret == DB_VERIFY_BAD)
457
pip->refcount = OV_REF(h);
458
if (pip->refcount < 1) {
460
"Overflow page %lu has zero reference count",
465
/* Just store for now. */
466
pip->olen = HOFFSET(h);
468
err: if ((t_ret = __db_vrfy_putpageinfo(dbp->dbenv, vdp, pip)) != 0)
470
return ((ret == 0 && isbad == 1) ? DB_VERIFY_BAD : ret);
474
* __db_vrfy_ovfl_structure --
475
* Walk a list of overflow pages, avoiding cycles and marking
478
* PUBLIC: int __db_vrfy_ovfl_structure
479
* PUBLIC: __P((DB *, VRFY_DBINFO *, db_pgno_t, u_int32_t, u_int32_t));
482
__db_vrfy_ovfl_structure(dbp, vdp, pgno, tlen, flags)
491
db_pgno_t next, prev;
492
int isbad, p, ret, t_ret;
496
DB_ASSERT(pgset != NULL);
499
/* This shouldn't happen, but just to be sure. */
500
if (!IS_VALID_PGNO(pgno))
501
return (DB_VERIFY_BAD);
504
* Check the first prev_pgno; it ought to be PGNO_INVALID,
505
* since there's no prev page.
507
if ((ret = __db_vrfy_getpageinfo(vdp, pgno, &pip)) != 0)
510
/* The refcount is stored on the first overflow page. */
511
refcount = pip->refcount;
513
if (pip->type != P_OVERFLOW) {
515
"Overflow page %lu of invalid type",
516
(u_long)pgno, (u_long)pip->type));
518
goto err; /* Unsafe to continue. */
521
prev = pip->prev_pgno;
522
if (prev != PGNO_INVALID) {
524
"First overflow page %lu has a prev_pgno", (u_long)pgno));
530
* This is slightly gross. Btree leaf pages reference
531
* individual overflow trees multiple times if the overflow page
532
* is the key to a duplicate set. The reference count does not
533
* reflect this multiple referencing. Thus, if this is called
534
* during the structure verification of a btree leaf page, we
535
* check to see whether we've seen it from a leaf page before
536
* and, if we have, adjust our count of how often we've seen it
539
* (This will screw up if it's actually referenced--and
540
* correctly refcounted--from two different leaf pages, but
541
* that's a very unlikely brokenness that we're not checking for
545
if (LF_ISSET(ST_OVFL_LEAF)) {
546
if (F_ISSET(pip, VRFY_OVFL_LEAFSEEN)) {
548
__db_vrfy_pgset_dec(pgset, pgno)) != 0)
551
F_SET(pip, VRFY_OVFL_LEAFSEEN);
554
if ((ret = __db_vrfy_pgset_get(pgset, pgno, &p)) != 0)
558
* We may have seen this elsewhere, if the overflow entry
559
* has been promoted to an internal page.
561
if ((u_int32_t)p > refcount) {
563
"Page %lu encountered twice in overflow traversal",
568
if ((ret = __db_vrfy_pgset_inc(pgset, pgno)) != 0)
571
/* Keep a running tab on how much of the item we've seen. */
574
/* Send feedback to the application about our progress. */
575
if (!LF_ISSET(DB_SALVAGE))
576
__db_vrfy_struct_feedback(dbp, vdp);
578
next = pip->next_pgno;
580
/* Are we there yet? */
581
if (next == PGNO_INVALID)
585
* We've already checked this when we saved it, but just
588
if (!IS_VALID_PGNO(next)) {
591
"Overflow page %lu has bad next_pgno",
597
if ((ret = __db_vrfy_putpageinfo(dbp->dbenv, vdp, pip)) != 0 ||
598
(ret = __db_vrfy_getpageinfo(vdp, next, &pip)) != 0)
600
if (pip->prev_pgno != pgno) {
602
"Overflow page %lu has bogus prev_pgno value",
606
* It's safe to continue because we have separate
617
"Overflow item incomplete on page %lu", (u_long)pgno));
621
__db_vrfy_putpageinfo(dbp->dbenv, vdp, pip)) != 0 && ret == 0)
623
return ((ret == 0 && isbad == 1) ? DB_VERIFY_BAD : ret);
628
* Get an overflow item, very carefully, from an untrusted database,
629
* in the context of the salvager.
631
* PUBLIC: int __db_safe_goff __P((DB *, VRFY_DBINFO *, db_pgno_t,
632
* PUBLIC: DBT *, void **, u_int32_t));
635
__db_safe_goff(dbp, vdp, pgno, dbt, buf, flags)
645
u_int32_t bytesgot, bytes;
646
u_int8_t *src, *dest;
649
bytesgot = bytes = 0;
652
while ((pgno != PGNO_INVALID) && (IS_VALID_PGNO(pgno))) {
654
* Mark that we're looking at this page; if we've seen it
657
if ((ret = __db_salvage_markdone(vdp, pgno)) != 0)
660
if ((ret = memp_fget(dbp->mpf, &pgno, 0, &h)) != 0)
664
* Make sure it's really an overflow page, unless we're
665
* being aggressive, in which case we pretend it is.
667
if (!LF_ISSET(DB_AGGRESSIVE) && TYPE(h) != P_OVERFLOW) {
672
src = (u_int8_t *)h + P_OVERHEAD;
675
if (bytes + P_OVERHEAD > dbp->pgsize)
676
bytes = dbp->pgsize - P_OVERHEAD;
678
if ((ret = __os_realloc(dbp->dbenv,
679
bytesgot + bytes, buf)) != 0)
682
dest = (u_int8_t *)*buf + bytesgot;
685
memcpy(dest, src, bytes);
689
if ((ret = memp_fput(dbp->mpf, h, 0)) != 0)
695
* If we're being aggressive, salvage a partial datum if there
696
* was an error somewhere along the way.
698
if (ret == 0 || LF_ISSET(DB_AGGRESSIVE)) {
699
dbt->size = bytesgot;
703
/* If we broke out on error, don't leave pages pinned. */
704
if (h != NULL && (t_ret = memp_fput(dbp->mpf, h, 0)) != 0 && ret == 0)
added
removed
db/db/db_overflow.c
