diff options
Diffstat (limited to 'storage/bdb/db/db_overflow.c')
| -rw-r--r-- | storage/bdb/db/db_overflow.c | 726 |
1 files changed, 726 insertions, 0 deletions
diff --git a/storage/bdb/db/db_overflow.c b/storage/bdb/db/db_overflow.c new file mode 100644 index 00000000000..27dcb41a2ff --- /dev/null +++ b/storage/bdb/db/db_overflow.c @@ -0,0 +1,726 @@ +/*- + * See the file LICENSE for redistribution information. + * + * Copyright (c) 1996-2002 + * Sleepycat Software. All rights reserved. + */ +/* + * Copyright (c) 1990, 1993, 1994, 1995, 1996 + * Keith Bostic. All rights reserved. + */ +/* + * Copyright (c) 1990, 1993, 1994, 1995 + * The Regents of the University of California. All rights reserved. + * + * This code is derived from software contributed to Berkeley by + * Mike Olson. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * 3. Neither the name of the University nor the names of its contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + */ + +#include "db_config.h" + +#ifndef lint +static const char revid[] = "$Id: db_overflow.c,v 11.46 2002/08/08 03:57:48 bostic Exp $"; +#endif /* not lint */ + +#ifndef NO_SYSTEM_INCLUDES +#include <sys/types.h> + +#include <string.h> +#endif + +#include "db_int.h" +#include "dbinc/db_page.h" +#include "dbinc/db_am.h" +#include "dbinc/db_verify.h" + +/* + * Big key/data code. + * + * Big key and data entries are stored on linked lists of pages. The initial + * reference is a structure with the total length of the item and the page + * number where it begins. Each entry in the linked list contains a pointer + * to the next page of data, and so on. + */ + +/* + * __db_goff -- + * Get an offpage item. + * + * PUBLIC: int __db_goff __P((DB *, DBT *, + * PUBLIC: u_int32_t, db_pgno_t, void **, u_int32_t *)); + */ +int +__db_goff(dbp, dbt, tlen, pgno, bpp, bpsz) + DB *dbp; + DBT *dbt; + u_int32_t tlen; + db_pgno_t pgno; + void **bpp; + u_int32_t *bpsz; +{ + DB_ENV *dbenv; + DB_MPOOLFILE *mpf; + PAGE *h; + db_indx_t bytes; + u_int32_t curoff, needed, start; + u_int8_t *p, *src; + int ret; + + dbenv = dbp->dbenv; + mpf = dbp->mpf; + + /* + * Check if the buffer is big enough; if it is not and we are + * allowed to malloc space, then we'll malloc it. If we are + * not (DB_DBT_USERMEM), then we'll set the dbt and return + * appropriately. + */ + if (F_ISSET(dbt, DB_DBT_PARTIAL)) { + start = dbt->doff; + if (start > tlen) + needed = 0; + else if (dbt->dlen > tlen - start) + needed = tlen - start; + else + needed = dbt->dlen; + } else { + start = 0; + needed = tlen; + } + + /* Allocate any necessary memory. */ + if (F_ISSET(dbt, DB_DBT_USERMEM)) { + if (needed > dbt->ulen) { + dbt->size = needed; + return (ENOMEM); + } + } else if (F_ISSET(dbt, DB_DBT_MALLOC)) { + if ((ret = __os_umalloc(dbenv, needed, &dbt->data)) != 0) + return (ret); + } else if (F_ISSET(dbt, DB_DBT_REALLOC)) { + if ((ret = __os_urealloc(dbenv, needed, &dbt->data)) != 0) + return (ret); + } else if (*bpsz == 0 || *bpsz < needed) { + if ((ret = __os_realloc(dbenv, needed, bpp)) != 0) + return (ret); + *bpsz = needed; + dbt->data = *bpp; + } else + dbt->data = *bpp; + + /* + * Step through the linked list of pages, copying the data on each + * one into the buffer. Never copy more than the total data length. + */ + dbt->size = needed; + for (curoff = 0, p = dbt->data; pgno != PGNO_INVALID && needed > 0;) { + if ((ret = mpf->get(mpf, &pgno, 0, &h)) != 0) + return (ret); + + /* Check if we need any bytes from this page. */ + if (curoff + OV_LEN(h) >= start) { + src = (u_int8_t *)h + P_OVERHEAD(dbp); + bytes = OV_LEN(h); + if (start > curoff) { + src += start - curoff; + bytes -= start - curoff; + } + if (bytes > needed) + bytes = needed; + memcpy(p, src, bytes); + p += bytes; + needed -= bytes; + } + curoff += OV_LEN(h); + pgno = h->next_pgno; + (void)mpf->put(mpf, h, 0); + } + return (0); +} + +/* + * __db_poff -- + * Put an offpage item. + * + * PUBLIC: int __db_poff __P((DBC *, const DBT *, db_pgno_t *)); + */ +int +__db_poff(dbc, dbt, pgnop) + DBC *dbc; + const DBT *dbt; + db_pgno_t *pgnop; +{ + DB *dbp; + DBT tmp_dbt; + DB_LSN new_lsn, null_lsn; + DB_MPOOLFILE *mpf; + PAGE *pagep, *lastp; + db_indx_t pagespace; + u_int32_t sz; + u_int8_t *p; + int ret, t_ret; + + /* + * Allocate pages and copy the key/data item into them. Calculate the + * number of bytes we get for pages we fill completely with a single + * item. + */ + dbp = dbc->dbp; + mpf = dbp->mpf; + pagespace = P_MAXSPACE(dbp, dbp->pgsize); + + ret = 0; + lastp = NULL; + for (p = dbt->data, + sz = dbt->size; sz > 0; p += pagespace, sz -= pagespace) { + /* + * Reduce pagespace so we terminate the loop correctly and + * don't copy too much data. + */ + if (sz < pagespace) + pagespace = sz; + + /* + * Allocate and initialize a new page and copy all or part of + * the item onto the page. If sz is less than pagespace, we + * have a partial record. + */ + if ((ret = __db_new(dbc, P_OVERFLOW, &pagep)) != 0) + break; + if (DBC_LOGGING(dbc)) { + tmp_dbt.data = p; + tmp_dbt.size = pagespace; + ZERO_LSN(null_lsn); + if ((ret = __db_big_log(dbp, dbc->txn, + &new_lsn, 0, DB_ADD_BIG, PGNO(pagep), + lastp ? PGNO(lastp) : PGNO_INVALID, + PGNO_INVALID, &tmp_dbt, &LSN(pagep), + lastp == NULL ? &null_lsn : &LSN(lastp), + &null_lsn)) != 0) { + if (lastp != NULL) + (void)mpf->put(mpf, + lastp, DB_MPOOL_DIRTY); + lastp = pagep; + break; + } + } else + LSN_NOT_LOGGED(new_lsn); + + /* Move LSN onto page. */ + if (lastp != NULL) + LSN(lastp) = new_lsn; + LSN(pagep) = new_lsn; + + P_INIT(pagep, dbp->pgsize, + PGNO(pagep), PGNO_INVALID, PGNO_INVALID, 0, P_OVERFLOW); + OV_LEN(pagep) = pagespace; + OV_REF(pagep) = 1; + memcpy((u_int8_t *)pagep + P_OVERHEAD(dbp), p, pagespace); + + /* + * If this is the first entry, update the user's info. + * Otherwise, update the entry on the last page filled + * in and release that page. + */ + if (lastp == NULL) + *pgnop = PGNO(pagep); + else { + lastp->next_pgno = PGNO(pagep); + pagep->prev_pgno = PGNO(lastp); + (void)mpf->put(mpf, lastp, DB_MPOOL_DIRTY); + } + lastp = pagep; + } + if (lastp != NULL && + (t_ret = mpf->put(mpf, lastp, DB_MPOOL_DIRTY)) != 0 && ret == 0) + ret = t_ret; + return (ret); +} + +/* + * __db_ovref -- + * Increment/decrement the reference count on an overflow page. + * + * PUBLIC: int __db_ovref __P((DBC *, db_pgno_t, int32_t)); + */ +int +__db_ovref(dbc, pgno, adjust) + DBC *dbc; + db_pgno_t pgno; + int32_t adjust; +{ + DB *dbp; + DB_MPOOLFILE *mpf; + PAGE *h; + int ret; + + dbp = dbc->dbp; + mpf = dbp->mpf; + + if ((ret = mpf->get(mpf, &pgno, 0, &h)) != 0) { + __db_pgerr(dbp, pgno, ret); + return (ret); + } + + if (DBC_LOGGING(dbc)) { + if ((ret = __db_ovref_log(dbp, + dbc->txn, &LSN(h), 0, h->pgno, adjust, &LSN(h))) != 0) { + (void)mpf->put(mpf, h, 0); + return (ret); + } + } else + LSN_NOT_LOGGED(LSN(h)); + OV_REF(h) += adjust; + + (void)mpf->put(mpf, h, DB_MPOOL_DIRTY); + return (0); +} + +/* + * __db_doff -- + * Delete an offpage chain of overflow pages. + * + * PUBLIC: int __db_doff __P((DBC *, db_pgno_t)); + */ +int +__db_doff(dbc, pgno) + DBC *dbc; + db_pgno_t pgno; +{ + DB *dbp; + PAGE *pagep; + DB_LSN null_lsn; + DB_MPOOLFILE *mpf; + DBT tmp_dbt; + int ret; + + dbp = dbc->dbp; + mpf = dbp->mpf; + + do { + if ((ret = mpf->get(mpf, &pgno, 0, &pagep)) != 0) { + __db_pgerr(dbp, pgno, ret); + return (ret); + } + + DB_ASSERT(TYPE(pagep) == P_OVERFLOW); + /* + * If it's referenced by more than one key/data item, + * decrement the reference count and return. + */ + if (OV_REF(pagep) > 1) { + (void)mpf->put(mpf, pagep, 0); + return (__db_ovref(dbc, pgno, -1)); + } + + if (DBC_LOGGING(dbc)) { + tmp_dbt.data = (u_int8_t *)pagep + P_OVERHEAD(dbp); + tmp_dbt.size = OV_LEN(pagep); + ZERO_LSN(null_lsn); + if ((ret = __db_big_log(dbp, dbc->txn, + &LSN(pagep), 0, DB_REM_BIG, + PGNO(pagep), PREV_PGNO(pagep), + NEXT_PGNO(pagep), &tmp_dbt, + &LSN(pagep), &null_lsn, &null_lsn)) != 0) { + (void)mpf->put(mpf, pagep, 0); + return (ret); + } + } else + LSN_NOT_LOGGED(LSN(pagep)); + pgno = pagep->next_pgno; + if ((ret = __db_free(dbc, pagep)) != 0) + return (ret); + } while (pgno != PGNO_INVALID); + + return (0); +} + +/* + * __db_moff -- + * Match on overflow pages. + * + * Given a starting page number and a key, return <0, 0, >0 to indicate if the + * key on the page is less than, equal to or greater than the key specified. + * We optimize this by doing chunk at a time comparison unless the user has + * specified a comparison function. In this case, we need to materialize + * the entire object and call their comparison routine. + * + * PUBLIC: int __db_moff __P((DB *, const DBT *, db_pgno_t, u_int32_t, + * PUBLIC: int (*)(DB *, const DBT *, const DBT *), int *)); + */ +int +__db_moff(dbp, dbt, pgno, tlen, cmpfunc, cmpp) + DB *dbp; + const DBT *dbt; + db_pgno_t pgno; + u_int32_t tlen; + int (*cmpfunc) __P((DB *, const DBT *, const DBT *)), *cmpp; +{ + DBT local_dbt; + DB_MPOOLFILE *mpf; + PAGE *pagep; + void *buf; + u_int32_t bufsize, cmp_bytes, key_left; + u_int8_t *p1, *p2; + int ret; + + mpf = dbp->mpf; + + /* + * If there is a user-specified comparison function, build a + * contiguous copy of the key, and call it. + */ + if (cmpfunc != NULL) { + memset(&local_dbt, 0, sizeof(local_dbt)); + buf = NULL; + bufsize = 0; + + if ((ret = __db_goff(dbp, + &local_dbt, tlen, pgno, &buf, &bufsize)) != 0) + return (ret); + /* Pass the key as the first argument */ + *cmpp = cmpfunc(dbp, dbt, &local_dbt); + __os_free(dbp->dbenv, buf); + return (0); + } + + /* While there are both keys to compare. */ + for (*cmpp = 0, p1 = dbt->data, + key_left = dbt->size; key_left > 0 && pgno != PGNO_INVALID;) { + if ((ret = mpf->get(mpf, &pgno, 0, &pagep)) != 0) + return (ret); + + cmp_bytes = OV_LEN(pagep) < key_left ? OV_LEN(pagep) : key_left; + tlen -= cmp_bytes; + key_left -= cmp_bytes; + for (p2 = (u_int8_t *)pagep + P_OVERHEAD(dbp); + cmp_bytes-- > 0; ++p1, ++p2) + if (*p1 != *p2) { + *cmpp = (long)*p1 - (long)*p2; + break; + } + pgno = NEXT_PGNO(pagep); + if ((ret = mpf->put(mpf, pagep, 0)) != 0) + return (ret); + if (*cmpp != 0) + return (0); + } + if (key_left > 0) /* DBT is longer than the page key. */ + *cmpp = 1; + else if (tlen > 0) /* DBT is shorter than the page key. */ + *cmpp = -1; + else + *cmpp = 0; + + return (0); +} + +/* + * __db_vrfy_overflow -- + * Verify overflow page. + * + * PUBLIC: int __db_vrfy_overflow __P((DB *, VRFY_DBINFO *, PAGE *, db_pgno_t, + * PUBLIC: u_int32_t)); + */ +int +__db_vrfy_overflow(dbp, vdp, h, pgno, flags) + DB *dbp; + VRFY_DBINFO *vdp; + PAGE *h; + db_pgno_t pgno; + u_int32_t flags; +{ + VRFY_PAGEINFO *pip; + int isbad, ret, t_ret; + + isbad = 0; + if ((ret = __db_vrfy_getpageinfo(vdp, pgno, &pip)) != 0) + return (ret); + + if ((ret = __db_vrfy_datapage(dbp, vdp, h, pgno, flags)) != 0) { + if (ret == DB_VERIFY_BAD) + isbad = 1; + else + goto err; + } + + pip->refcount = OV_REF(h); + if (pip->refcount < 1) { + EPRINT((dbp->dbenv, + "Page %lu: overflow page has zero reference count", + (u_long)pgno)); + isbad = 1; + } + + /* Just store for now. */ + pip->olen = HOFFSET(h); + +err: if ((t_ret = __db_vrfy_putpageinfo(dbp->dbenv, vdp, pip)) != 0) + ret = t_ret; + return ((ret == 0 && isbad == 1) ? DB_VERIFY_BAD : ret); +} + +/* + * __db_vrfy_ovfl_structure -- + * Walk a list of overflow pages, avoiding cycles and marking + * pages seen. + * + * PUBLIC: int __db_vrfy_ovfl_structure + * PUBLIC: __P((DB *, VRFY_DBINFO *, db_pgno_t, u_int32_t, u_int32_t)); + */ +int +__db_vrfy_ovfl_structure(dbp, vdp, pgno, tlen, flags) + DB *dbp; + VRFY_DBINFO *vdp; + db_pgno_t pgno; + u_int32_t tlen; + u_int32_t flags; +{ + DB *pgset; + VRFY_PAGEINFO *pip; + db_pgno_t next, prev; + int isbad, p, ret, t_ret; + u_int32_t refcount; + + pgset = vdp->pgset; + DB_ASSERT(pgset != NULL); + isbad = 0; + + /* This shouldn't happen, but just to be sure. */ + if (!IS_VALID_PGNO(pgno)) + return (DB_VERIFY_BAD); + + /* + * Check the first prev_pgno; it ought to be PGNO_INVALID, + * since there's no prev page. + */ + if ((ret = __db_vrfy_getpageinfo(vdp, pgno, &pip)) != 0) + return (ret); + + /* The refcount is stored on the first overflow page. */ + refcount = pip->refcount; + + if (pip->type != P_OVERFLOW) { + EPRINT((dbp->dbenv, + "Page %lu: overflow page of invalid type %lu", + (u_long)pgno, (u_long)pip->type)); + ret = DB_VERIFY_BAD; + goto err; /* Unsafe to continue. */ + } + + prev = pip->prev_pgno; + if (prev != PGNO_INVALID) { + EPRINT((dbp->dbenv, + "Page %lu: first page in overflow chain has a prev_pgno %lu", + (u_long)pgno, (u_long)prev)); + isbad = 1; + } + + for (;;) { + /* + * This is slightly gross. Btree leaf pages reference + * individual overflow trees multiple times if the overflow page + * is the key to a duplicate set. The reference count does not + * reflect this multiple referencing. Thus, if this is called + * during the structure verification of a btree leaf page, we + * check to see whether we've seen it from a leaf page before + * and, if we have, adjust our count of how often we've seen it + * accordingly. + * + * (This will screw up if it's actually referenced--and + * correctly refcounted--from two different leaf pages, but + * that's a very unlikely brokenness that we're not checking for + * anyway.) + */ + + if (LF_ISSET(ST_OVFL_LEAF)) { + if (F_ISSET(pip, VRFY_OVFL_LEAFSEEN)) { + if ((ret = + __db_vrfy_pgset_dec(pgset, pgno)) != 0) + goto err; + } else + F_SET(pip, VRFY_OVFL_LEAFSEEN); + } + + if ((ret = __db_vrfy_pgset_get(pgset, pgno, &p)) != 0) + goto err; + + /* + * We may have seen this elsewhere, if the overflow entry + * has been promoted to an internal page. + */ + if ((u_int32_t)p > refcount) { + EPRINT((dbp->dbenv, + "Page %lu: encountered twice in overflow traversal", + (u_long)pgno)); + ret = DB_VERIFY_BAD; + goto err; + } + if ((ret = __db_vrfy_pgset_inc(pgset, pgno)) != 0) + goto err; + + /* Keep a running tab on how much of the item we've seen. */ + tlen -= pip->olen; + + /* Send feedback to the application about our progress. */ + if (!LF_ISSET(DB_SALVAGE)) + __db_vrfy_struct_feedback(dbp, vdp); + + next = pip->next_pgno; + + /* Are we there yet? */ + if (next == PGNO_INVALID) + break; + + /* + * We've already checked this when we saved it, but just + * to be sure... + */ + if (!IS_VALID_PGNO(next)) { + DB_ASSERT(0); + EPRINT((dbp->dbenv, + "Page %lu: bad next_pgno %lu on overflow page", + (u_long)pgno, (u_long)next)); + ret = DB_VERIFY_BAD; + goto err; + } + + if ((ret = __db_vrfy_putpageinfo(dbp->dbenv, vdp, pip)) != 0 || + (ret = __db_vrfy_getpageinfo(vdp, next, &pip)) != 0) + return (ret); + if (pip->prev_pgno != pgno) { + EPRINT((dbp->dbenv, + "Page %lu: bad prev_pgno %lu on overflow page (should be %lu)", + (u_long)next, (u_long)pip->prev_pgno, + (u_long)pgno)); + isbad = 1; + /* + * It's safe to continue because we have separate + * cycle detection. + */ + } + + pgno = next; + } + + if (tlen > 0) { + isbad = 1; + EPRINT((dbp->dbenv, + "Page %lu: overflow item incomplete", (u_long)pgno)); + } + +err: if ((t_ret = + __db_vrfy_putpageinfo(dbp->dbenv, vdp, pip)) != 0 && ret == 0) + ret = t_ret; + return ((ret == 0 && isbad == 1) ? DB_VERIFY_BAD : ret); +} + +/* + * __db_safe_goff -- + * Get an overflow item, very carefully, from an untrusted database, + * in the context of the salvager. + * + * PUBLIC: int __db_safe_goff __P((DB *, VRFY_DBINFO *, db_pgno_t, + * PUBLIC: DBT *, void **, u_int32_t)); + */ +int +__db_safe_goff(dbp, vdp, pgno, dbt, buf, flags) + DB *dbp; + VRFY_DBINFO *vdp; + db_pgno_t pgno; + DBT *dbt; + void **buf; + u_int32_t flags; +{ + DB_MPOOLFILE *mpf; + PAGE *h; + int ret, t_ret; + u_int32_t bytesgot, bytes; + u_int8_t *src, *dest; + + mpf = dbp->mpf; + h = NULL; + ret = t_ret = 0; + bytesgot = bytes = 0; + + while ((pgno != PGNO_INVALID) && (IS_VALID_PGNO(pgno))) { + /* + * Mark that we're looking at this page; if we've seen it + * already, quit. + */ + if ((ret = __db_salvage_markdone(vdp, pgno)) != 0) + break; + + if ((ret = mpf->get(mpf, &pgno, 0, &h)) != 0) + break; + + /* + * Make sure it's really an overflow page, unless we're + * being aggressive, in which case we pretend it is. + */ + if (!LF_ISSET(DB_AGGRESSIVE) && TYPE(h) != P_OVERFLOW) { + ret = DB_VERIFY_BAD; + break; + } + + src = (u_int8_t *)h + P_OVERHEAD(dbp); + bytes = OV_LEN(h); + + if (bytes + P_OVERHEAD(dbp) > dbp->pgsize) + bytes = dbp->pgsize - P_OVERHEAD(dbp); + + if ((ret = __os_realloc(dbp->dbenv, + bytesgot + bytes, buf)) != 0) + break; + + dest = (u_int8_t *)*buf + bytesgot; + bytesgot += bytes; + + memcpy(dest, src, bytes); + + pgno = NEXT_PGNO(h); + + if ((ret = mpf->put(mpf, h, 0)) != 0) + break; + h = NULL; + } + + /* + * If we're being aggressive, salvage a partial datum if there + * was an error somewhere along the way. + */ + if (ret == 0 || LF_ISSET(DB_AGGRESSIVE)) { + dbt->size = bytesgot; + dbt->data = *buf; + } + + /* If we broke out on error, don't leave pages pinned. */ + if (h != NULL && (t_ret = mpf->put(mpf, h, 0)) != 0 && ret == 0) + ret = t_ret; + + return (ret); +} |