hash_verify.c

Go to the documentation of this file.
00001 /*-
00002  * See the file LICENSE for redistribution information.
00003  *
00004  * Copyright (c) 1999, 2000
00005  *      Sleepycat Software.  All rights reserved.
00006  *
00007  * $Id: hash__verify_8c-source.html,v 1.1 2008/06/08 10:19:40 sebdiaz Exp $
00008  */
00009 
00010 #include "config.h"
00011 
00012 #ifndef lint
00013 static const char revid[] = "$Id: hash__verify_8c-source.html,v 1.1 2008/06/08 10:19:40 sebdiaz Exp $";
00014 #endif /* not lint */
00015 
00016 #ifndef NO_SYSTEM_INCLUDES
00017 #include <sys/types.h>
00018 
00019 #include <errno.h>
00020 #include <string.h>
00021 #endif
00022 
00023 #include "db_int.h"
00024 #include "db_page.h"
00025 #include "db_verify.h"
00026 #include "btree.h"
00027 #include "hash.h"
00028 
00029 static int __ham_dups_unsorted __P((DB *, u_int8_t *, u_int32_t));
00030 static int __ham_vrfy_bucket __P((DB *, VRFY_DBINFO *, HMETA *, u_int32_t,
00031     u_int32_t));
00032 static int __ham_vrfy_item __P((DB *,
00033     VRFY_DBINFO *, db_pgno_t, PAGE *, u_int32_t, u_int32_t));
00034 
00035 /*
00036  * CDB___ham_vrfy_meta --
00037  *      Verify the hash-specific part of a metadata page.
00038  *
00039  *      Note that unlike btree, we don't save things off, because we
00040  *      will need most everything again to verify each page and the
00041  *      amount of state here is significant.
00042  *
00043  * PUBLIC: int CDB___ham_vrfy_meta __P((DB *, VRFY_DBINFO *, HMETA *,
00044  * PUBLIC:     db_pgno_t, u_int32_t));
00045  */
00046 int
00047 CDB___ham_vrfy_meta(dbp, vdp, m, pgno, flags)
00048         DB *dbp;
00049         VRFY_DBINFO *vdp;
00050         HMETA *m;
00051         db_pgno_t pgno;
00052         u_int32_t flags;
00053 {
00054         HASH *hashp;
00055         VRFY_PAGEINFO *pip;
00056         int i, ret, t_ret, isbad;
00057         u_int32_t pwr, mbucket;
00058         u_int32_t (*hfunc) __P((const void *, u_int32_t));
00059 
00060         if ((ret = CDB___db_vrfy_getpageinfo(vdp, pgno, &pip)) != 0)
00061                 return (ret);
00062         isbad = 0;
00063 
00064         hashp = dbp->h_internal;
00065 
00066         if (hashp != NULL && hashp->h_hash != NULL)
00067                 hfunc = hashp->h_hash;
00068         else
00069                 hfunc = CDB___ham_func5;
00070 
00071         /*
00072          * If we haven't already checked the common fields in pagezero,
00073          * check them.
00074          */
00075         if (!F_ISSET(pip, VRFY_INCOMPLETE) &&
00076             (ret = CDB___db_vrfy_meta(dbp, vdp, &m->dbmeta, pgno, flags)) != 0) {
00077                 if (ret == DB_VERIFY_BAD)
00078                         isbad = 1;
00079                 else
00080                         goto err;
00081         }
00082 
00083         /* h_charkey */
00084         if (!LF_ISSET(DB_NOORDERCHK))
00085                 if (m->h_charkey != hfunc(CHARKEY, sizeof(CHARKEY))) {
00086                         EPRINT((dbp->dbenv,
00087 "Database has different custom hash function; reverify with DB_NOORDERCHK set"
00088                             ));
00089                         /*
00090                          * Return immediately;  this is probably a sign
00091                          * of user error rather than database corruption, so
00092                          * we want to avoid extraneous errors.
00093                          */
00094                         isbad = 1;
00095                         goto err;
00096                 }
00097 
00098         /* max_bucket must be less than the last pgno. */
00099         if (m->max_bucket > vdp->last_pgno) {
00100                 EPRINT((dbp->dbenv,
00101                     "Impossible max_bucket %lu on meta page %lu",
00102                     m->max_bucket, pgno));
00103                 /*
00104                  * Most other fields depend somehow on max_bucket, so
00105                  * we just return--there will be lots of extraneous
00106                  * errors.
00107                  */
00108                 isbad = 1;
00109                 goto err;
00110         }
00111 
00112         /*
00113          * max_bucket, high_mask and low_mask: high_mask must be one
00114          * less than the next power of two above max_bucket, and
00115          * low_mask must be one less than the power of two below it.
00116          *
00117          *
00118          */
00119         pwr = (m->max_bucket == 0) ? 1 : 1 << CDB___db_log2(m->max_bucket + 1);
00120         if (m->high_mask != pwr - 1) {
00121                 EPRINT((dbp->dbenv,
00122                     "Incorrect high_mask %lu on page %lu, should be %lu",
00123                     m->high_mask, pgno, pwr - 1));
00124                 isbad = 1;
00125         }
00126         pwr >>= 1;
00127         if (m->low_mask != pwr - 1) {
00128                 EPRINT((dbp->dbenv,
00129                     "Incorrect low_mask %lu on page %lu, should be %lu",
00130                     m->low_mask, pgno, pwr - 1));
00131                 isbad = 1;
00132         }
00133 
00134         /* ffactor: no check possible. */
00135         pip->h_ffactor = m->ffactor;
00136 
00137         /*
00138          * nelem: just make sure it's not astronomical for now. This is the
00139          * same check that hash_upgrade does, since there was a bug in 2.X
00140          * which could make nelem go "negative".
00141          */
00142         if (m->nelem > 0x80000000) {
00143                 EPRINT((dbp->dbenv,
00144                     "Suspiciously high nelem of %lu on page %lu",
00145                     m->nelem, pgno));
00146                 isbad = 1;
00147                 pip->h_nelem = 0;
00148         } else
00149                 pip->h_nelem = m->nelem;
00150 
00151         /* flags */
00152         if (F_ISSET(&m->dbmeta, DB_HASH_DUP))
00153                 F_SET(pip, VRFY_HAS_DUPS);
00154         if (F_ISSET(&m->dbmeta, DB_HASH_DUPSORT))
00155                 F_SET(pip, VRFY_HAS_DUPSORT);
00156         /* XXX: Why is the DB_HASH_SUBDB flag necessary? */
00157 
00158         /* spares array */
00159         for (i = 0; m->spares[i] != 0 && i < NCACHED; i++) {
00160                 /*
00161                  * We set mbucket to the maximum bucket that would use a given
00162                  * spares entry;  we want to ensure that it's always less
00163                  * than last_pgno.
00164                  */
00165                 mbucket = (1 << i) - 1;
00166                 if (mbucket + m->spares[CDB___db_log2(mbucket + 1)] >
00167                     vdp->last_pgno) {
00168                         EPRINT((dbp->dbenv,
00169                             "Spares array entry %lu, page %lu is invalid",
00170                             i, pgno));
00171                         isbad = 1;
00172                 }
00173         }
00174 
00175 err:    if ((t_ret = CDB___db_vrfy_putpageinfo(vdp, pip)) != 0 && ret == 0)
00176                 ret = t_ret;
00177         return ((ret == 0 && isbad == 1) ? DB_VERIFY_BAD : ret);
00178 }
00179 
00180 /*
00181  * CDB___ham_vrfy --
00182  *      Verify hash page.
00183  *
00184  * PUBLIC: int CDB___ham_vrfy __P((DB *, VRFY_DBINFO *, PAGE *, db_pgno_t,
00185  * PUBLIC:     u_int32_t));
00186  */
00187 int
00188 CDB___ham_vrfy(dbp, vdp, h, pgno, flags)
00189         DB *dbp;
00190         VRFY_DBINFO *vdp;
00191         PAGE *h;
00192         db_pgno_t pgno;
00193         u_int32_t flags;
00194 {
00195         VRFY_PAGEINFO *pip;
00196         db_indx_t ent, himark, inpend;
00197         int isbad, ret, t_ret;
00198 
00199         isbad = 0;
00200         if ((ret = CDB___db_vrfy_getpageinfo(vdp, pgno, &pip)) != 0)
00201                 return (ret);
00202 
00203         /* Sanity check our flags and page type. */
00204         if ((ret = CDB___db_fchk(dbp->dbenv, "CDB___ham_vrfy",
00205             flags, DB_AGGRESSIVE | DB_NOORDERCHK | DB_SALVAGE)) != 0)
00206                 goto err;
00207 
00208         if (TYPE(h) != P_HASH) {
00209                 TYPE_ERR_PRINT(dbp->dbenv, "CDB___ham_vrfy", pgno, TYPE(h));
00210                 DB_ASSERT(0);
00211                 ret = EINVAL;
00212                 goto err;
00213         }
00214 
00215         /* Verify and save off fields common to all PAGEs. */
00216         if ((ret = CDB___db_vrfy_datapage(dbp, vdp, h, pgno, flags)) != 0) {
00217                 if (ret == DB_VERIFY_BAD)
00218                         isbad = 1;
00219                 else
00220                         goto err;
00221         }
00222 
00223         /*
00224          * Verify inp[].  Each offset from 0 to NUM_ENT(h) must be lower
00225          * than the previous one, higher than the current end of the inp array,
00226          * and lower than the page size.
00227          *
00228          * In any case, we return immediately if things are bad, as it would
00229          * be unsafe to proceed.
00230          */
00231         for (ent = 0, himark = dbp->pgsize,
00232             inpend = (u_int8_t *)h->inp - (u_int8_t *)h;
00233             ent < NUM_ENT(h); ent++)
00234                 if (h->inp[ent] >= himark) {
00235                         EPRINT((dbp->dbenv,
00236                             "Item %lu on page %lu out of order or nonsensical",
00237                             ent, pgno));
00238                         isbad = 1;
00239                         goto err;
00240                 } else if (inpend >= himark) {
00241                         EPRINT((dbp->dbenv,
00242                             "inp array collided with data on page %lu",
00243                             pgno));
00244                         isbad = 1;
00245                         goto err;
00246 
00247                 } else {
00248                         himark = h->inp[ent];
00249                         inpend += sizeof(db_indx_t);
00250                         if ((ret = __ham_vrfy_item(
00251                             dbp, vdp, pgno, h, ent, flags)) != 0)
00252                                 goto err;
00253                 }
00254 
00255 err:    if ((t_ret = CDB___db_vrfy_putpageinfo(vdp, pip)) != 0 && ret == 0)
00256                 ret = t_ret;
00257         return (ret == 0 && isbad == 1 ? DB_VERIFY_BAD : ret);
00258 }
00259 
00260 /*
00261  * __ham_vrfy_item --
00262  *      Given a hash page and an offset, sanity-check the item itself,
00263  *      and save off any overflow items or off-page dup children as necessary.
00264  */
00265 static int
00266 __ham_vrfy_item(dbp, vdp, pgno, h, i, flags)
00267         DB *dbp;
00268         VRFY_DBINFO *vdp;
00269         db_pgno_t pgno;
00270         PAGE *h;
00271         u_int32_t i, flags;
00272 {
00273         HOFFPAGE hop;
00274         HOFFDUP hod;
00275         VRFY_CHILDINFO child;
00276         VRFY_PAGEINFO *pip;
00277         db_indx_t offset, len, dlen, elen;
00278         int ret, t_ret;
00279         u_int8_t *databuf;
00280 
00281         if ((ret = CDB___db_vrfy_getpageinfo(vdp, pgno, &pip)) != 0)
00282                 return (ret);
00283 
00284         switch (HPAGE_TYPE(h, i)) {
00285         case H_KEYDATA:
00286                 /* Nothing to do here--everything but the type field is data */
00287                 break;
00288         case H_DUPLICATE:
00289                 /* Are we a datum or a key?  Better be the former. */
00290                 if (i % 2 == 0) {
00291                         EPRINT((dbp->dbenv,
00292                             "Hash key stored as duplicate at page %lu item %lu",
00293                             pip->pgno, i));
00294                 }
00295                 /*
00296                  * Dups are encoded as a series within a single HKEYDATA,
00297                  * in which each dup is surrounded by a copy of its length
00298                  * on either side (so that the series can be walked in either
00299                  * direction.  We loop through this series and make sure
00300                  * each dup is reasonable.
00301                  *
00302                  * Note that at this point, we've verified item i-1, so
00303                  * it's safe to use LEN_HKEYDATA (which looks at inp[i-1]).
00304                  */
00305                 len = LEN_HKEYDATA(h, dbp->pgsize, i);
00306                 databuf = HKEYDATA_DATA(P_ENTRY(h, i));
00307                 for (offset = 0; offset < len; offset += DUP_SIZE(dlen)) {
00308                         memcpy(&dlen, databuf + offset, sizeof(db_indx_t));
00309 
00310                         /* Make sure the length is plausible. */
00311                         if (offset + DUP_SIZE(dlen) > len) {
00312                                 EPRINT((dbp->dbenv,
00313                             "Duplicate item %lu, page %lu has bad length",
00314                                     i, pip->pgno));
00315                                 ret = DB_VERIFY_BAD;
00316                                 goto err;
00317                         }
00318 
00319                         /*
00320                          * Make sure the second copy of the length is the
00321                          * same as the first.
00322                          */
00323                         memcpy(&elen,
00324                             databuf + offset + dlen + sizeof(db_indx_t),
00325                             sizeof(db_indx_t));
00326                         if (elen != dlen) {
00327                                 EPRINT((dbp->dbenv,
00328                 "Duplicate item %lu, page %lu has two different lengths",
00329                                     i, pip->pgno));
00330                                 ret = DB_VERIFY_BAD;
00331                                 goto err;
00332                         }
00333                 }
00334                 F_SET(pip, VRFY_HAS_DUPS);
00335                 if (!LF_ISSET(DB_NOORDERCHK) &&
00336                     __ham_dups_unsorted(dbp, databuf, len))
00337                         F_SET(pip, VRFY_DUPS_UNSORTED);
00338                 break;
00339         case H_OFFPAGE:
00340                 /* Offpage item.  Make sure pgno is sane, save off. */
00341                 memcpy(&hop, P_ENTRY(h, i), HOFFPAGE_SIZE);
00342                 if (!IS_VALID_PGNO(hop.pgno) || hop.pgno == pip->pgno ||
00343                     hop.pgno == PGNO_INVALID) {
00344                         EPRINT((dbp->dbenv,
00345                             "Offpage item %lu, page %lu has bad page number",
00346                             i, pip->pgno));
00347                         ret = DB_VERIFY_BAD;
00348                         goto err;
00349                 }
00350                 memset(&child, 0, sizeof(VRFY_CHILDINFO));
00351                 child.pgno = hop.pgno;
00352                 child.type = V_OVERFLOW;
00353                 child.tlen = hop.tlen; /* This will get checked later. */
00354                 if ((ret = CDB___db_vrfy_childput(vdp, pip->pgno, &child)) != 0)
00355                         goto err;
00356                 break;
00357         case H_OFFDUP:
00358                 /* Offpage duplicate item.  Same drill. */
00359                 memcpy(&hod, P_ENTRY(h, i), HOFFDUP_SIZE);
00360                 if (!IS_VALID_PGNO(hod.pgno) || hod.pgno == pip->pgno ||
00361                     hod.pgno == PGNO_INVALID) {
00362                         EPRINT((dbp->dbenv,
00363                             "Offpage item %lu, page %lu has bad page number",
00364                             i, pip->pgno));
00365                         ret = DB_VERIFY_BAD;
00366                         goto err;
00367                 }
00368                 memset(&child, 0, sizeof(VRFY_CHILDINFO));
00369                 child.pgno = hod.pgno;
00370                 child.type = V_DUPLICATE;
00371                 if ((ret = CDB___db_vrfy_childput(vdp, pip->pgno, &child)) != 0)
00372                         goto err;
00373                 F_SET(pip, VRFY_HAS_DUPS);
00374                 break;
00375         default:
00376                 EPRINT((dbp->dbenv,
00377                     "Item %i, page %lu has bad type", i, pip->pgno));
00378                 ret = DB_VERIFY_BAD;
00379                 break;
00380         }
00381 
00382 err:    if ((t_ret = CDB___db_vrfy_putpageinfo(vdp, pip)) != 0 && ret == 0)
00383                 ret = t_ret;
00384         return (ret);
00385 }
00386 
00387 /*
00388  * CDB___ham_vrfy_structure --
00389  *      Verify the structure of a hash database.
00390  *
00391  * PUBLIC: int CDB___ham_vrfy_structure __P((DB *, VRFY_DBINFO *, db_pgno_t,
00392  * PUBLIC:     u_int32_t));
00393  */
00394 int
00395 CDB___ham_vrfy_structure(dbp, vdp, meta_pgno, flags)
00396         DB *dbp;
00397         VRFY_DBINFO *vdp;
00398         db_pgno_t meta_pgno;
00399         u_int32_t flags;
00400 {
00401         DB *pgset;
00402         HMETA *m;
00403         PAGE *h;
00404         VRFY_PAGEINFO *pip;
00405         int isbad, p, ret, t_ret;
00406         db_pgno_t pgno;
00407         u_int32_t bucket;
00408 
00409         ret = isbad = 0;
00410         h = NULL;
00411         pgset = vdp->pgset;
00412 
00413         if ((ret = CDB___db_vrfy_pgset_get(pgset, meta_pgno, &p)) != 0)
00414                 return (ret);
00415         if (p != 0) {
00416                 EPRINT((dbp->dbenv,
00417                     "Hash meta page %lu referenced twice", meta_pgno));
00418                 return (DB_VERIFY_BAD);
00419         }
00420         if ((ret = CDB___db_vrfy_pgset_inc(pgset, meta_pgno)) != 0)
00421                 return (ret);
00422 
00423         /* Get the meta page;  we'll need it frequently. */
00424         if ((ret = CDB_memp_fget(dbp->mpf, &meta_pgno, 0, &m)) != 0)
00425                 return (ret);
00426 
00427         /* Loop through bucket by bucket. */
00428         for (bucket = 0; bucket <= m->max_bucket; bucket++)
00429                 if ((ret =
00430                     __ham_vrfy_bucket(dbp, vdp, m, bucket, flags)) != 0) {
00431                         if (ret == DB_VERIFY_BAD)
00432                                 isbad = 1;
00433                         else
00434                                 goto err;
00435                     }
00436 
00437         /*
00438          * There may be unused hash pages corresponding to buckets
00439          * that are part of the current doubling but which are higher
00440          * than max_bucket.  Loop through them, too, and make sure they're
00441          * all empty.
00442          */
00443         for (bucket = m->max_bucket + 1; bucket <= m->high_mask; bucket++) {
00444                 pgno = bucket + m->spares[CDB___db_log2(bucket + 1)];
00445                 if ((ret = CDB___db_vrfy_getpageinfo(vdp, pgno, &pip)) != 0)
00446                         goto err;
00447 
00448                 /* It's okay if these pages are totally zeroed;  unmark it. */
00449                 F_CLR(pip, VRFY_IS_ALLZEROES);
00450 
00451                 if (pip->type != P_HASH) {
00452                         EPRINT((dbp->dbenv,
00453                             "Hash bucket %lu maps to non-hash page %lu",
00454                             bucket, pgno));
00455                         isbad = 1;
00456                 } else if (pip->entries != 0) {
00457                         EPRINT((dbp->dbenv,
00458                             "Non-empty page %lu in unused hash bucket %lu",
00459                             pgno, bucket));
00460                         isbad = 1;
00461                 } else {
00462                         if ((ret = CDB___db_vrfy_pgset_get(pgset, pgno, &p)) != 0)
00463                                 goto err;
00464                         if (p != 0) {
00465                                 EPRINT((dbp->dbenv,
00466                                     "Hash page %lu above max_bucket referenced",
00467                                     pgno));
00468                                 isbad = 1;
00469                         } else {
00470                                 if ((ret =
00471                                     CDB___db_vrfy_pgset_inc(pgset, pgno)) != 0)
00472                                         goto err;
00473                                 if ((ret =
00474                                     CDB___db_vrfy_putpageinfo(vdp, pip)) != 0)
00475                                         goto err;
00476                                 continue;
00477                         }
00478                 }
00479 
00480                 /* If we got here, it's an error. */
00481                 (void)CDB___db_vrfy_putpageinfo(vdp, pip);
00482                 goto err;
00483         }
00484 
00485 err:    if ((t_ret = CDB_memp_fput(dbp->mpf, m, 0)) != 0)
00486                 return (t_ret);
00487         if (h != NULL && (t_ret = CDB_memp_fput(dbp->mpf, h, 0)) != 0)
00488                 return (t_ret);
00489         return ((isbad == 1 && ret == 0) ? DB_VERIFY_BAD: ret);
00490 }
00491 
00492 /*
00493  * __ham_vrfy_bucket --
00494  *      Verify a given bucket.
00495  */
00496 static int
00497 __ham_vrfy_bucket(dbp, vdp, m, bucket, flags)
00498         DB *dbp;
00499         VRFY_DBINFO *vdp;
00500         HMETA *m;
00501         u_int32_t bucket, flags;
00502 {
00503         HASH *hashp;
00504         VRFY_CHILDINFO *child;
00505         VRFY_PAGEINFO *mip, *pip;
00506         int ret, t_ret, isbad, p;
00507         db_pgno_t pgno, next_pgno;
00508         DBC *cc;
00509         u_int32_t (*hfunc) __P((const void *, u_int32_t));
00510 
00511         isbad = 0;
00512         pip = NULL;
00513         cc = NULL;
00514 
00515         hashp = dbp->h_internal;
00516         if (hashp != NULL && hashp->h_hash != NULL)
00517                 hfunc = hashp->h_hash;
00518         else
00519                 hfunc = CDB___ham_func5;
00520 
00521         if ((ret = CDB___db_vrfy_getpageinfo(vdp, PGNO(m), &mip)) != 0)
00522                 return (ret);
00523 
00524         /* Calculate the first pgno for this bucket. */
00525         pgno = bucket + m->spares[CDB___db_log2(bucket + 1)];
00526 
00527         if ((ret = CDB___db_vrfy_getpageinfo(vdp, pgno, &pip)) != 0)
00528                 goto err;
00529 
00530         /* Make sure we got a plausible page number. */
00531         if (pgno > vdp->last_pgno || pip->type != P_HASH) {
00532                 EPRINT((dbp->dbenv, "Bucket %lu has impossible first page %lu",
00533                     bucket, pgno));
00534                 /* Unsafe to continue. */
00535                 isbad = 1;
00536                 goto err;
00537         }
00538 
00539         if (pip->prev_pgno != PGNO_INVALID) {
00540                 EPRINT((dbp->dbenv,
00541                     "First hash page %lu in bucket %lu has a prev_pgno", pgno));
00542                 isbad = 1;
00543         }
00544 
00545         /*
00546          * Set flags for dups and sorted dups.
00547          */
00548         flags |= F_ISSET(mip, VRFY_HAS_DUPS) ? ST_DUPOK : 0;
00549         flags |= F_ISSET(mip, VRFY_HAS_DUPSORT) ? ST_DUPSORT : 0;
00550 
00551         /* Loop until we find a fatal bug, or until we run out of pages. */
00552         for (;;) {
00553                 if ((ret = CDB___db_vrfy_pgset_get(vdp->pgset, pgno, &p)) != 0)
00554                         goto err;
00555                 if (p != 0) {
00556                         EPRINT((dbp->dbenv,
00557                             "Hash page %lu referenced twice", pgno));
00558                         isbad = 1;
00559                         /* Unsafe to continue. */
00560                         goto err;
00561                 } else if ((ret = CDB___db_vrfy_pgset_inc(vdp->pgset, pgno)) != 0)
00562                         goto err;
00563 
00564                 /*
00565                  * Hash pages that nothing has ever hashed to may never
00566                  * have actually come into existence, and may appear to be
00567                  * entirely zeroed.  This is acceptable, and since there's
00568                  * no real way for us to know whether this has actually
00569                  * occurred, we clear the "wholly zeroed" flag on every
00570                  * hash page.  A wholly zeroed page, by nature, will appear
00571                  * to have no flags set and zero entries, so should
00572                  * otherwise verify correctly.
00573                  */
00574                 F_CLR(pip, VRFY_IS_ALLZEROES);
00575 
00576                 /* If we have dups, our meta page had better know about it. */
00577                 if (F_ISSET(pip, VRFY_HAS_DUPS)
00578                     && !F_ISSET(mip, VRFY_HAS_DUPS)) {
00579                         EPRINT((dbp->dbenv,
00580                     "Duplicates present in non-duplicate database, page %lu",
00581                             pgno));
00582                         isbad = 1;
00583                 }
00584 
00585                 /*
00586                  * If the database has sorted dups, this page had better
00587                  * not have unsorted ones.
00588                  */
00589                 if (F_ISSET(mip, VRFY_HAS_DUPSORT) &&
00590                     F_ISSET(pip, VRFY_DUPS_UNSORTED)) {
00591                         EPRINT((dbp->dbenv,
00592                             "Unsorted dups in sorted-dup database, page %lu",
00593                             pgno));
00594                         isbad = 1;
00595                 }
00596 
00597                 /* Walk overflow chains and offpage dup trees. */
00598                 if ((ret = CDB___db_vrfy_childcursor(vdp, &cc)) != 0)
00599                         goto err;
00600                 for (ret = CDB___db_vrfy_ccset(cc, pip->pgno, &child); ret == 0;
00601                     ret = CDB___db_vrfy_ccnext(cc, &child))
00602                         if (child->type == V_OVERFLOW) {
00603                                 if ((ret = CDB___db_vrfy_ovfl_structure(dbp, vdp,
00604                                     child->pgno, child->tlen, flags)) != 0) {
00605                                         if (ret == DB_VERIFY_BAD)
00606                                                 isbad = 1;
00607                                         else
00608                                                 goto err;
00609                                 }
00610                         } else if (child->type == V_DUPLICATE) {
00611                                 if ((ret = CDB___db_vrfy_duptype(dbp,
00612                                     vdp, child->pgno, flags)) != 0) {
00613                                         isbad = 1;
00614                                         continue;
00615                                 }
00616                                 if ((ret = CDB___bam_vrfy_subtree(dbp, vdp,
00617                                     child->pgno, NULL, NULL,
00618                                     flags | ST_RECNUM, NULL,
00619                                     NULL, NULL)) != 0) {
00620                                         if (ret == DB_VERIFY_BAD)
00621                                                 isbad = 1;
00622                                         else
00623                                                 goto err;
00624                                 }
00625                         }
00626                 if ((ret = CDB___db_vrfy_ccclose(cc)) != 0)
00627                         goto err;
00628                 cc = NULL;
00629 
00630                 /* If it's safe to check that things hash properly, do so. */
00631                 if (isbad == 0 && !LF_ISSET(DB_NOORDERCHK) &&
00632                     (ret = CDB___ham_vrfy_hashing(dbp, pip->entries,
00633                     m, bucket, pgno, flags, hfunc)) != 0) {
00634                         if (ret == DB_VERIFY_BAD)
00635                                 isbad = 1;
00636                         else
00637                                 goto err;
00638                 }
00639 
00640                 next_pgno = pip->next_pgno;
00641                 ret = CDB___db_vrfy_putpageinfo(vdp, pip);
00642 
00643                 pip = NULL;
00644                 if (ret != 0)
00645                         goto err;
00646 
00647                 if (next_pgno == PGNO_INVALID)
00648                         break;          /* End of the bucket. */
00649 
00650                 /* We already checked this, but just in case... */
00651                 if (!IS_VALID_PGNO(next_pgno)) {
00652                         DB_ASSERT(0);
00653                         EPRINT((dbp->dbenv,
00654                             "Hash page %lu has bad next_pgno", pgno));
00655                         isbad = 1;
00656                         goto err;
00657                 }
00658 
00659                 if ((ret = CDB___db_vrfy_getpageinfo(vdp, next_pgno, &pip)) != 0)
00660                         goto err;
00661 
00662                 if (pip->prev_pgno != pgno) {
00663                         EPRINT((dbp->dbenv, "Hash page %lu has bad prev_pgno",
00664                             next_pgno));
00665                         isbad = 1;
00666                 }
00667                 pgno = next_pgno;
00668         }
00669 
00670 err:    if (cc != NULL && ((t_ret = CDB___db_vrfy_ccclose(cc)) != 0) && ret == 0)
00671                 ret = t_ret;
00672         if (mip != NULL && ((t_ret = CDB___db_vrfy_putpageinfo(vdp, mip)) != 0) &&
00673             ret == 0)
00674                 ret = t_ret;
00675         if (pip != NULL && ((t_ret = CDB___db_vrfy_putpageinfo(vdp, pip)) != 0) &&
00676             ret == 0)
00677                 ret = t_ret;
00678         return ((ret == 0 && isbad == 1) ? DB_VERIFY_BAD : ret);
00679 }
00680 
00681 /*
00682  * CDB___ham_vrfy_hashing --
00683  *      Verify that all items on a given hash page hash correctly.
00684  *
00685  * PUBLIC: int CDB___ham_vrfy_hashing __P((DB *,
00686  * PUBLIC:     u_int32_t, HMETA *, u_int32_t, db_pgno_t, u_int32_t,
00687  * PUBLIC:     u_int32_t (*) __P((const void *, u_int32_t))));
00688  */
00689 int
00690 CDB___ham_vrfy_hashing(dbp, nentries, m, thisbucket, pgno, flags, hfunc)
00691         DB *dbp;
00692         u_int32_t nentries;
00693         HMETA *m;
00694         u_int32_t thisbucket;
00695         db_pgno_t pgno;
00696         u_int32_t flags;
00697         u_int32_t (*hfunc) __P((const void *, u_int32_t));
00698 {
00699         DBT dbt;
00700         PAGE *h;
00701         db_indx_t i;
00702         int ret, t_ret, isbad;
00703         u_int32_t hval, bucket;
00704 
00705         ret = isbad = 0;
00706         memset(&dbt, 0, sizeof(DBT));
00707         F_SET(&dbt, DB_DBT_REALLOC);
00708 
00709         if ((ret = CDB_memp_fget(dbp->mpf, &pgno, 0, &h)) != 0)
00710                 return (ret);
00711 
00712         for (i = 0; i < nentries; i += 2) {
00713                 /*
00714                  * We've already verified the page integrity and that of any
00715                  * overflow chains linked off it;  it is therefore safe to use
00716                  * CDB___db_ret.  It's also not all that much slower, since we have
00717                  * to copy every hash item to deal with alignment anyway;  we
00718                  * can tweak this a bit if this proves to be a bottleneck,
00719                  * but for now, take the easy route.
00720                  */
00721                 if ((ret = CDB___db_ret(dbp, h, i, &dbt, NULL, NULL)) != 0)
00722                         goto err;
00723                 hval = hfunc(dbt.data, dbt.size);
00724 
00725                 bucket = hval & m->high_mask;
00726                 if (bucket > m->max_bucket)
00727                         bucket = bucket & m->low_mask;
00728 
00729                 if (bucket != thisbucket) {
00730                         EPRINT((dbp->dbenv,
00731                             "Item %lu on page %lu hashes incorrectly",
00732                             i, pgno));
00733                         isbad = 1;
00734                 }
00735         }
00736 
00737 err:    if (dbt.data != NULL)
00738                 CDB___os_free(dbt.data, 0);
00739         if ((t_ret = CDB_memp_fput(dbp->mpf, h, 0)) != 0)
00740                 return (t_ret);
00741 
00742         return ((ret == 0 && isbad == 1) ? DB_VERIFY_BAD : ret);
00743 }
00744 
00745 /*
00746  * CDB___ham_salvage --
00747  *      Safely dump out anything that looks like a key on an alleged
00748  *      hash page.
00749  *
00750  * PUBLIC: int CDB___ham_salvage __P((DB *, VRFY_DBINFO *, db_pgno_t, PAGE *,
00751  * PUBLIC:     void *, int (*)(void *, const void *), u_int32_t));
00752  */
00753 int
00754 CDB___ham_salvage(dbp, vdp, pgno, h, handle, callback, flags)
00755         DB *dbp;
00756         VRFY_DBINFO *vdp;
00757         db_pgno_t pgno;
00758         PAGE *h;
00759         void *handle;
00760         int (*callback) __P((void *, const void *));
00761         u_int32_t flags;
00762 {
00763         DBT dbt, unkdbt;
00764         db_pgno_t dpgno;
00765         int ret, err_ret, t_ret;
00766         u_int32_t himark, tlen;
00767         u_int8_t *hk;
00768         void *buf;
00769         db_indx_t dlen, len, i;
00770 
00771         memset(&dbt, 0, sizeof(DBT));
00772         dbt.flags = DB_DBT_REALLOC;
00773 
00774         memset(&unkdbt, 0, sizeof(DBT));
00775         unkdbt.size = strlen("UNKNOWN") + 1;
00776         unkdbt.data = "UNKNOWN";
00777 
00778         err_ret = 0;
00779 
00780         /*
00781          * Allocate a buffer for overflow items.  Start at one page;
00782          * CDB___db_safe_goff will realloc as needed.
00783          */
00784         if ((ret = CDB___os_malloc(dbp->dbenv, dbp->pgsize, NULL, &buf)) != 0)
00785                 return (ret);
00786 
00787         himark = dbp->pgsize;
00788         for (i = 0;; i++) {
00789                 /* If we're not aggressive, break when we hit NUM_ENT(h). */
00790                 if (!LF_ISSET(DB_AGGRESSIVE) && i >= NUM_ENT(h))
00791                         break;
00792 
00793                 /* Verify the current item. */
00794                 ret = CDB___db_vrfy_inpitem(dbp,
00795                     h, pgno, i, 0, flags, &himark, NULL);
00796                 /* If this returned a fatality, it's time to break. */
00797                 if (ret == DB_VERIFY_FATAL)
00798                         break;
00799 
00800                 if (ret == 0) {
00801                         hk = P_ENTRY(h, i);
00802                         len = LEN_HKEYDATA(h, dbp->pgsize, i);
00803                         if ((u_int32_t)(hk + len - (u_int8_t *)h) >
00804                             dbp->pgsize) {
00805                                 /*
00806                                  * Item is unsafely large;  either continue
00807                                  * or set it to the whole page, depending on
00808                                  * aggressiveness.
00809                                  */
00810                                 if (!LF_ISSET(DB_AGGRESSIVE))
00811                                         continue;
00812                                 len = dbp->pgsize -
00813                                     (u_int32_t)(hk - (u_int8_t *)h);
00814                                 err_ret = DB_VERIFY_BAD;
00815                         }
00816                         switch (HPAGE_PTYPE(hk)) {
00817                         default:
00818                                 if (!LF_ISSET(DB_AGGRESSIVE))
00819                                         break;
00820                                 err_ret = DB_VERIFY_BAD;
00821                                 /* FALLTHROUGH */
00822                         case H_KEYDATA:
00823 keydata:                        memcpy(buf, HKEYDATA_DATA(hk), len);
00824                                 dbt.size = len;
00825                                 dbt.data = buf;
00826                                 if ((ret = CDB___db_prdbt(&dbt,
00827                                     0, " ", handle, callback, 0, NULL)) != 0)
00828                                         err_ret = ret;
00829                                 break;
00830                         case H_OFFPAGE:
00831                                 if (len < HOFFPAGE_SIZE) {
00832                                         err_ret = DB_VERIFY_BAD;
00833                                         continue;
00834                                 }
00835                                 memcpy(&dpgno,
00836                                     HOFFPAGE_PGNO(hk), sizeof(dpgno));
00837                                 if ((ret = CDB___db_safe_goff(dbp, vdp,
00838                                     dpgno, &dbt, &buf, flags)) != 0) {
00839                                         err_ret = ret;
00840                                         (void)CDB___db_prdbt(&unkdbt, 0, " ",
00841                                             handle, callback, 0, NULL);
00842                                         break;
00843                                 }
00844                                 if ((ret = CDB___db_prdbt(&dbt,
00845                                     0, " ", handle, callback, 0, NULL)) != 0)
00846                                         err_ret = ret;
00847                                 break;
00848                         case H_OFFDUP:
00849                                 if (len < HOFFPAGE_SIZE) {
00850                                         err_ret = DB_VERIFY_BAD;
00851                                         continue;
00852                                 }
00853                                 memcpy(&dpgno,
00854                                     HOFFPAGE_PGNO(hk), sizeof(dpgno));
00855                                 /* UNKNOWN iff pgno is bad or we're a key. */
00856                                 if (!IS_VALID_PGNO(dpgno) || (i % 2 == 0)) {
00857                                         if ((ret = CDB___db_prdbt(&unkdbt, 0, " ",
00858                                             handle, callback, 0, NULL)) != 0)
00859                                                 err_ret = ret;
00860                                 } else if ((ret = CDB___db_salvage_duptree(dbp,
00861                                     vdp, dpgno, &dbt, handle, callback,
00862                                     flags | SA_SKIPFIRSTKEY)) != 0)
00863                                         err_ret = ret;
00864                                 break;
00865                         case H_DUPLICATE:
00866                                 /*
00867                                  * We're a key;  printing dups will seriously
00868                                  * foul the output.  If we're being aggressive,
00869                                  * pretend this is a key and let the app.
00870                                  * programmer sort out the mess.
00871                                  */
00872                                 if (i % 2 == 0) {
00873                                         err_ret = ret;
00874                                         if (LF_ISSET(DB_AGGRESSIVE))
00875                                                 goto keydata;
00876                                         break;
00877                                 }
00878 
00879                                 /* Too small to have any data. */
00880                                 if (len <
00881                                     HKEYDATA_SIZE(2 * sizeof(db_indx_t))) {
00882                                         err_ret = DB_VERIFY_BAD;
00883                                         continue;
00884                                 }
00885 
00886                                 /* Loop until we hit the total length. */
00887                                 for (tlen = 0; tlen + sizeof(db_indx_t) < len;
00888                                     tlen += dlen) {
00889                                         tlen += sizeof(db_indx_t);
00890                                         memcpy(&dlen, hk, sizeof(db_indx_t));
00891                                         /*
00892                                          * If dlen is too long, print all the
00893                                          * rest of the dup set in a chunk.
00894                                          */
00895                                         if (dlen + tlen > len)
00896                                                 dlen = len - tlen;
00897                                         memcpy(buf, hk + tlen, dlen);
00898                                         dbt.size = dlen;
00899                                         dbt.data = buf;
00900                                         if ((ret = CDB___db_prdbt(&dbt, 0, " ",
00901                                             handle, callback, 0, NULL)) != 0)
00902                                                 err_ret = ret;
00903                                         tlen += sizeof(db_indx_t);
00904                                 }
00905                                 break;
00906                         }
00907                 }
00908         }
00909 
00910         if ((t_ret = CDB___db_salvage_markdone(vdp, pgno)) != 0)
00911                 return (t_ret);
00912         return ((ret == 0 && err_ret != 0) ? err_ret : ret);
00913 }
00914 
00915 /*
00916  * CDB___ham_meta2pgset --
00917  *      Return the set of hash pages corresponding to the given
00918  *      known-good meta page.
00919  *
00920  * PUBLIC: int CDB___ham_meta2pgset __P((DB *, VRFY_DBINFO *, HMETA *, u_int32_t,
00921  * PUBLIC:     DB *));
00922  */
00923 int CDB___ham_meta2pgset(dbp, vdp, hmeta, flags, pgset)
00924         DB *dbp;
00925         VRFY_DBINFO *vdp;
00926         HMETA *hmeta;
00927         u_int32_t flags;
00928         DB *pgset;
00929 {
00930         PAGE *h;
00931         db_pgno_t pgno;
00932         u_int32_t bucket, totpgs;
00933         int ret, val;
00934 
00935         /*
00936          * We don't really need flags, but leave them for consistency with
00937          * CDB___bam_meta2pgset.
00938          */
00939         COMPQUIET(flags, 0);
00940 
00941         DB_ASSERT(pgset != NULL);
00942 
00943         totpgs = 0;
00944 
00945         /*
00946          * Loop through all the buckets, pushing onto pgset the corresponding
00947          * page(s) for each one.
00948          */
00949         for (bucket = 0; bucket <= hmeta->max_bucket; bucket++) {
00950                 pgno = bucket + hmeta->spares[CDB___db_log2(bucket + 1)];
00951 
00952                 /*
00953                  * We know the initial pgno is safe because the spares array has
00954                  * been verified.
00955                  *
00956                  * Safely walk the list of pages in this bucket.
00957                  */
00958                 for (;;) {
00959                         if ((ret = CDB_memp_fget(dbp->mpf, &pgno, 0, &h)) != 0)
00960                                 return (ret);
00961                         if (TYPE(h) == P_HASH) {
00962 
00963                                 /*
00964                                  * Make sure we don't go past the end of
00965                                  * pgset.
00966                                  */
00967                                 if (++totpgs > vdp->last_pgno) {
00968                                         (void)CDB_memp_fput(dbp->mpf, h, 0);
00969                                         return (DB_VERIFY_BAD);
00970                                 }
00971                                 if ((ret =
00972                                     CDB___db_vrfy_pgset_inc(pgset, pgno)) != 0)
00973                                         return (ret);
00974 
00975                                 pgno = NEXT_PGNO(h);
00976                         } else
00977                                 pgno = PGNO_INVALID;
00978 
00979                         if ((ret = CDB_memp_fput(dbp->mpf, h, 0)) != 0)
00980                                 return (ret);
00981 
00982                         /* If the new pgno is wonky, go onto the next bucket. */
00983                         if (!IS_VALID_PGNO(pgno) ||
00984                             pgno == PGNO_INVALID)
00985                                 goto nextbucket;
00986 
00987                         /*
00988                          * If we've touched this page before, we have a cycle;
00989                          * go on to the next bucket.
00990                          */
00991                         if ((ret = CDB___db_vrfy_pgset_get(pgset, pgno, &val)) != 0)
00992                                 return (ret);
00993                         if (val != 0)
00994                                 goto nextbucket;
00995                 }
00996 nextbucket:     ;
00997         }
00998         return (0);
00999 }
01000 
01001 /*
01002  * __ham_dups_unsorted --
01003  *      Takes a known-safe hash duplicate set and its total length.
01004  *      Returns 1 if there are out-of-order duplicates in this set,
01005  *      0 if there are not.
01006  */
01007 static int
01008 __ham_dups_unsorted(dbp, buf, len)
01009         DB *dbp;
01010         u_int8_t *buf;
01011         u_int32_t len;
01012 {
01013         DBT a, b;
01014         db_indx_t offset, dlen;
01015         int (*func) __P((const DBT *, const DBT *));
01016 
01017         memset(&a, 0, sizeof(DBT));
01018         memset(&b, 0, sizeof(DBT));
01019 
01020         func = (dbp->dup_compare == NULL) ? CDB___bam_defcmp : dbp->dup_compare;
01021 
01022         /*
01023          * Loop through the dup set until we hit the end or we find
01024          * a pair of dups that's out of order.  b is always the current
01025          * dup, a the one before it.
01026          */
01027         for (offset = 0; offset < len; offset += DUP_SIZE(dlen)) {
01028                 memcpy(&dlen, buf + offset, sizeof(db_indx_t));
01029                 b.data = buf + offset + sizeof(db_indx_t);
01030                 b.size = dlen;
01031 
01032                 if (a.data != NULL && func(&a, &b) > 0)
01033                         return (1);
01034 
01035                 a.data = b.data;
01036                 a.size = b.size;
01037         }
01038 
01039         return (0);
01040 }

Generated on Sun Jun 8 10:56:37 2008 for GNUmifluz by  doxygen 1.5.5