db/hash/hash_verify.c

   1 /*-
   2  * See the file LICENSE for redistribution information.
   3  *
   4  * Copyright (c) 1999-2001
   5  *      Sleepycat Software.  All rights reserved.
   6  *
   7  * Id: hash_verify.c,v 1.39 2001/07/02 01:05:39 bostic Exp
   8  */
   9
  10 #include "db_config.h"
  11
  12 #ifndef lint
  13 static const char revid[] = "Id: hash_verify.c,v 1.39 2001/07/02 01:05:39 bostic Exp ";
  14 #endif /* not lint */
  15
  16 #ifndef NO_SYSTEM_INCLUDES
  17 #include <sys/types.h>
  18
  19 #include <string.h>
  20 #endif
  21
  22 #include "db_int.h"
  23 #include "db_page.h"
  24 #include "db_verify.h"
  25 #include "btree.h"
  26 #include "hash.h"
  27
  28 static int __ham_dups_unsorted __P((DB *, u_int8_t *, u_int32_t));
  29 static int __ham_vrfy_bucket __P((DB *, VRFY_DBINFO *, HMETA *, u_int32_t,
  30     u_int32_t));
  31 static int __ham_vrfy_item __P((DB *,
  32     VRFY_DBINFO *, db_pgno_t, PAGE *, u_int32_t, u_int32_t));
  33
  34 /*
  35  * XXX Doing a db->del followed by a db->put for the same record
  36  * causes the nelem/page count to go awry, causing db->verify failure.
  37  * Turn off the message for now.
  38  */
  39 int db_hash_nelem_debug = 0;
  40
  41 /*
  42  * __ham_vrfy_meta --
  43  *      Verify the hash-specific part of a metadata page.
  44  *
  45  *      Note that unlike btree, we don't save things off, because we
  46  *      will need most everything again to verify each page and the
  47  *      amount of state here is significant.
  48  *
  49  * PUBLIC: int __ham_vrfy_meta __P((DB *, VRFY_DBINFO *, HMETA *,
  50  * PUBLIC:     db_pgno_t, u_int32_t));
  51  */
  52 int
  53 __ham_vrfy_meta(dbp, vdp, m, pgno, flags)
  54         DB *dbp;
  55         VRFY_DBINFO *vdp;
  56         HMETA *m;
  57         db_pgno_t pgno;
  58         u_int32_t flags;
  59 {
  60         HASH *hashp;
  61         VRFY_PAGEINFO *pip;
  62         int i, ret, t_ret, isbad;
  63         u_int32_t pwr, mbucket;
  64         u_int32_t (*hfunc) __P((DB *, const void *, u_int32_t));
  65
  66         if ((ret = __db_vrfy_getpageinfo(vdp, pgno, &pip)) != 0)
  67                 return (ret);
  68         isbad = 0;
  69
  70         hashp = dbp->h_internal;
  71
  72         if (hashp != NULL && hashp->h_hash != NULL)
  73                 hfunc = hashp->h_hash;
  74         else
  75                 hfunc = __ham_func5;
  76
  77         /*
  78          * If we haven't already checked the common fields in pagezero,
  79          * check them.
  80          */
  81         if (!F_ISSET(pip, VRFY_INCOMPLETE) &&
  82             (ret = __db_vrfy_meta(dbp, vdp, &m->dbmeta, pgno, flags)) != 0) {
  83                 if (ret == DB_VERIFY_BAD)
  84                         isbad = 1;
  85                 else
  86                         goto err;
  87         }
  88
  89         /* h_charkey */
  90         if (!LF_ISSET(DB_NOORDERCHK))
  91                 if (m->h_charkey != hfunc(dbp, CHARKEY, sizeof(CHARKEY))) {
  92                         EPRINT((dbp->dbenv,
  93 "Database has different custom hash function; reverify with DB_NOORDERCHK set"
  94                             ));
  95                         /*
  96                          * Return immediately;  this is probably a sign
  97                          * of user error rather than database corruption, so
  98                          * we want to avoid extraneous errors.
  99                          */
 100                         isbad = 1;
 101                         goto err;
 102                 }
 103
 104         /* max_bucket must be less than the last pgno. */
 105         if (m->max_bucket > vdp->last_pgno) {
 106                 EPRINT((dbp->dbenv,
 107                     "Impossible max_bucket %lu on meta page %lu",
 108                     (u_long)m->max_bucket, (u_long)pgno));
 109                 /*
 110                  * Most other fields depend somehow on max_bucket, so
 111                  * we just return--there will be lots of extraneous
 112                  * errors.
 113                  */
 114                 isbad = 1;
 115                 goto err;
 116         }
 117
 118         /*
 119          * max_bucket, high_mask and low_mask: high_mask must be one
 120          * less than the next power of two above max_bucket, and
 121          * low_mask must be one less than the power of two below it.
 122          *
 123          *
 124          */
 125         pwr = (m->max_bucket == 0) ? 1 : 1 << __db_log2(m->max_bucket + 1);
 126         if (m->high_mask != pwr - 1) {
 127                 EPRINT((dbp->dbenv,
 128                     "Incorrect high_mask %lu on page %lu, should be %lu",
 129                     (u_long)m->high_mask, (u_long)pgno, (u_long)pwr - 1));
 130                 isbad = 1;
 131         }
 132         pwr >>= 1;
 133         if (m->low_mask != pwr - 1) {
 134                 EPRINT((dbp->dbenv,
 135                     "Incorrect low_mask %lu on page %lu, should be %lu",
 136                     (u_long)m->low_mask, (u_long)pgno, (u_long)pwr - 1));
 137                 isbad = 1;
 138         }
 139
 140         /* ffactor: no check possible. */
 141         pip->h_ffactor = m->ffactor;
 142
 143         /*
 144          * nelem: just make sure it's not astronomical for now. This is the
 145          * same check that hash_upgrade does, since there was a bug in 2.X
 146          * which could make nelem go "negative".
 147          */
 148         if (m->nelem > 0x80000000) {
 149             if (db_hash_nelem_debug) {
 150                 EPRINT((dbp->dbenv,
 151                     "Suspiciously high nelem of %lu on page %lu",
 152                     (u_long)m->nelem, (u_long)pgno));
 153                 isbad = 1;
 154             }
 155                 pip->h_nelem = 0;
 156         } else
 157                 pip->h_nelem = m->nelem;
 158
 159         /* flags */
 160         if (F_ISSET(&m->dbmeta, DB_HASH_DUP))
 161                 F_SET(pip, VRFY_HAS_DUPS);
 162         if (F_ISSET(&m->dbmeta, DB_HASH_DUPSORT))
 163                 F_SET(pip, VRFY_HAS_DUPSORT);
 164         /* XXX: Why is the DB_HASH_SUBDB flag necessary? */
 165
 166         /* spares array */
 167         for (i = 0; m->spares[i] != 0 && i < NCACHED; i++) {
 168                 /*
 169                  * We set mbucket to the maximum bucket that would use a given
 170                  * spares entry;  we want to ensure that it's always less
 171                  * than last_pgno.
 172                  */
 173                 mbucket = (1 << i) - 1;
 174                 if (BS_TO_PAGE(mbucket, m->spares) > vdp->last_pgno) {
 175                         EPRINT((dbp->dbenv,
 176                             "Spares array entry %d, page %lu is invalid",
 177                             i, (u_long)pgno));
 178                         isbad = 1;
 179                 }
 180         }
 181
 182 err:    if ((t_ret =
 183             __db_vrfy_putpageinfo(dbp->dbenv, vdp, pip)) != 0 && ret == 0)
 184                 ret = t_ret;
 185         return ((ret == 0 && isbad == 1) ? DB_VERIFY_BAD : ret);
 186 }
 187
 188 /*
 189  * __ham_vrfy --
 190  *      Verify hash page.
 191  *
 192  * PUBLIC: int __ham_vrfy __P((DB *, VRFY_DBINFO *, PAGE *, db_pgno_t,
 193  * PUBLIC:     u_int32_t));
 194  */
 195 int
 196 __ham_vrfy(dbp, vdp, h, pgno, flags)
 197         DB *dbp;
 198         VRFY_DBINFO *vdp;
 199         PAGE *h;
 200         db_pgno_t pgno;
 201         u_int32_t flags;
 202 {
 203         VRFY_PAGEINFO *pip;
 204         u_int32_t ent, himark, inpend;
 205         int isbad, ret, t_ret;
 206
 207         isbad = 0;
 208         if ((ret = __db_vrfy_getpageinfo(vdp, pgno, &pip)) != 0)
 209                 return (ret);
 210
 211         /* Sanity check our flags and page type. */
 212         if ((ret = __db_fchk(dbp->dbenv, "__ham_vrfy",
 213             flags, DB_AGGRESSIVE | DB_NOORDERCHK | DB_SALVAGE)) != 0)
 214                 goto err;
 215
 216         if (TYPE(h) != P_HASH) {
 217                 TYPE_ERR_PRINT(dbp->dbenv, "__ham_vrfy", pgno, TYPE(h));
 218                 DB_ASSERT(0);
 219                 ret = EINVAL;
 220                 goto err;
 221         }
 222
 223         /* Verify and save off fields common to all PAGEs. */
 224         if ((ret = __db_vrfy_datapage(dbp, vdp, h, pgno, flags)) != 0) {
 225                 if (ret == DB_VERIFY_BAD)
 226                         isbad = 1;
 227                 else
 228                         goto err;
 229         }
 230
 231         /*
 232          * Verify inp[].  Each offset from 0 to NUM_ENT(h) must be lower
 233          * than the previous one, higher than the current end of the inp array,
 234          * and lower than the page size.
 235          *
 236          * In any case, we return immediately if things are bad, as it would
 237          * be unsafe to proceed.
 238          */
 239         for (ent = 0, himark = dbp->pgsize,
 240             inpend = (u_int8_t *)h->inp - (u_int8_t *)h;
 241             ent < NUM_ENT(h); ent++)
 242                 if (h->inp[ent] >= himark) {
 243                         EPRINT((dbp->dbenv,
 244                             "Item %lu on page %lu out of order or nonsensical",
 245                             (u_long)ent, (u_long)pgno));
 246                         isbad = 1;
 247                         goto err;
 248                 } else if (inpend >= himark) {
 249                         EPRINT((dbp->dbenv,
 250                             "inp array collided with data on page %lu",
 251                             (u_long)pgno));
 252                         isbad = 1;
 253                         goto err;
 254
 255                 } else {
 256                         himark = h->inp[ent];
 257                         inpend += sizeof(db_indx_t);
 258                         if ((ret = __ham_vrfy_item(
 259                             dbp, vdp, pgno, h, ent, flags)) != 0)
 260                                 goto err;
 261                 }
 262
 263 err:    if ((t_ret =
 264             __db_vrfy_putpageinfo(dbp->dbenv, vdp, pip)) != 0 && ret == 0)
 265                 ret = t_ret;
 266         return (ret == 0 && isbad == 1 ? DB_VERIFY_BAD : ret);
 267 }
 268
 269 /*
 270  * __ham_vrfy_item --
 271  *      Given a hash page and an offset, sanity-check the item itself,
 272  *      and save off any overflow items or off-page dup children as necessary.
 273  */
 274 static int
 275 __ham_vrfy_item(dbp, vdp, pgno, h, i, flags)
 276         DB *dbp;
 277         VRFY_DBINFO *vdp;
 278         db_pgno_t pgno;
 279         PAGE *h;
 280         u_int32_t i, flags;
 281 {
 282         HOFFPAGE hop;
 283         HOFFDUP hod;
 284         VRFY_CHILDINFO child;
 285         VRFY_PAGEINFO *pip;
 286         db_indx_t offset, len, dlen, elen;
 287         int ret, t_ret;
 288         u_int8_t *databuf;
 289
 290         if ((ret = __db_vrfy_getpageinfo(vdp, pgno, &pip)) != 0)
 291                 return (ret);
 292
 293         switch (HPAGE_TYPE(h, i)) {
 294         case H_KEYDATA:
 295                 /* Nothing to do here--everything but the type field is data */
 296                 break;
 297         case H_DUPLICATE:
 298                 /* Are we a datum or a key?  Better be the former. */
 299                 if (i % 2 == 0) {
 300                         EPRINT((dbp->dbenv,
 301                             "Hash key stored as duplicate at page %lu item %lu",
 302                             (u_long)pip->pgno, (u_long)i));
 303                 }
 304                 /*
 305                  * Dups are encoded as a series within a single HKEYDATA,
 306                  * in which each dup is surrounded by a copy of its length
 307                  * on either side (so that the series can be walked in either
 308                  * direction.  We loop through this series and make sure
 309                  * each dup is reasonable.
 310                  *
 311                  * Note that at this point, we've verified item i-1, so
 312                  * it's safe to use LEN_HKEYDATA (which looks at inp[i-1]).
 313                  */
 314                 len = LEN_HKEYDATA(h, dbp->pgsize, i);
 315                 databuf = HKEYDATA_DATA(P_ENTRY(h, i));
 316                 for (offset = 0; offset < len; offset += DUP_SIZE(dlen)) {
 317                         memcpy(&dlen, databuf + offset, sizeof(db_indx_t));
 318
 319                         /* Make sure the length is plausible. */
 320                         if (offset + DUP_SIZE(dlen) > len) {
 321                                 EPRINT((dbp->dbenv,
 322                             "Duplicate item %lu, page %lu has bad length",
 323                                     (u_long)i, (u_long)pip->pgno));
 324                                 ret = DB_VERIFY_BAD;
 325                                 goto err;
 326                         }
 327
 328                         /*
 329                          * Make sure the second copy of the length is the
 330                          * same as the first.
 331                          */
 332                         memcpy(&elen,
 333                             databuf + offset + dlen + sizeof(db_indx_t),
 334                             sizeof(db_indx_t));
 335                         if (elen != dlen) {
 336                                 EPRINT((dbp->dbenv,
 337                 "Duplicate item %lu, page %lu has two different lengths",
 338                                     (u_long)i, (u_long)pip->pgno));
 339                                 ret = DB_VERIFY_BAD;
 340                                 goto err;
 341                         }
 342                 }
 343                 F_SET(pip, VRFY_HAS_DUPS);
 344                 if (!LF_ISSET(DB_NOORDERCHK) &&
 345                     __ham_dups_unsorted(dbp, databuf, len))
 346                         F_SET(pip, VRFY_DUPS_UNSORTED);
 347                 break;
 348         case H_OFFPAGE:
 349                 /* Offpage item.  Make sure pgno is sane, save off. */
 350                 memcpy(&hop, P_ENTRY(h, i), HOFFPAGE_SIZE);
 351                 if (!IS_VALID_PGNO(hop.pgno) || hop.pgno == pip->pgno ||
 352                     hop.pgno == PGNO_INVALID) {
 353                         EPRINT((dbp->dbenv,
 354                             "Offpage item %lu, page %lu has bad pgno %lu",
 355                             (u_long)i, (u_long)pip->pgno, (u_long)hop.pgno));
 356                         ret = DB_VERIFY_BAD;
 357                         goto err;
 358                 }
 359                 memset(&child, 0, sizeof(VRFY_CHILDINFO));
 360                 child.pgno = hop.pgno;
 361                 child.type = V_OVERFLOW;
 362                 child.tlen = hop.tlen; /* This will get checked later. */
 363                 if ((ret = __db_vrfy_childput(vdp, pip->pgno, &child)) != 0)
 364                         goto err;
 365                 break;
 366         case H_OFFDUP:
 367                 /* Offpage duplicate item.  Same drill. */
 368                 memcpy(&hod, P_ENTRY(h, i), HOFFDUP_SIZE);
 369                 if (!IS_VALID_PGNO(hod.pgno) || hod.pgno == pip->pgno ||
 370                     hod.pgno == PGNO_INVALID) {
 371                         EPRINT((dbp->dbenv,
 372                             "Offpage item %lu, page %lu has bad page number",
 373                             (u_long)i, (u_long)pip->pgno));
 374                         ret = DB_VERIFY_BAD;
 375                         goto err;
 376                 }
 377                 memset(&child, 0, sizeof(VRFY_CHILDINFO));
 378                 child.pgno = hod.pgno;
 379                 child.type = V_DUPLICATE;
 380                 if ((ret = __db_vrfy_childput(vdp, pip->pgno, &child)) != 0)
 381                         goto err;
 382                 F_SET(pip, VRFY_HAS_DUPS);
 383                 break;
 384         default:
 385                 EPRINT((dbp->dbenv,
 386                     "Item %i, page %lu has bad type",
 387                     (u_long)i, (u_long)pip->pgno));
 388                 ret = DB_VERIFY_BAD;
 389                 break;
 390         }
 391
 392 err:    if ((t_ret =
 393             __db_vrfy_putpageinfo(dbp->dbenv, vdp, pip)) != 0 && ret == 0)
 394                 ret = t_ret;
 395         return (ret);
 396 }
 397
 398 /*
 399  * __ham_vrfy_structure --
 400  *      Verify the structure of a hash database.
 401  *
 402  * PUBLIC: int __ham_vrfy_structure __P((DB *, VRFY_DBINFO *, db_pgno_t,
 403  * PUBLIC:     u_int32_t));
 404  */
 405 int
 406 __ham_vrfy_structure(dbp, vdp, meta_pgno, flags)
 407         DB *dbp;
 408         VRFY_DBINFO *vdp;
 409         db_pgno_t meta_pgno;
 410         u_int32_t flags;
 411 {
 412         DB *pgset;
 413         HMETA *m;
 414         PAGE *h;
 415         VRFY_PAGEINFO *pip;
 416         int isbad, p, ret, t_ret;
 417         db_pgno_t pgno;
 418         u_int32_t bucket, spares_entry;
 419
 420         ret = isbad = 0;
 421         h = NULL;
 422         pgset = vdp->pgset;
 423
 424         if ((ret = __db_vrfy_pgset_get(pgset, meta_pgno, &p)) != 0)
 425                 return (ret);
 426         if (p != 0) {
 427                 EPRINT((dbp->dbenv,
 428                     "Hash meta page %lu referenced twice", (u_long)meta_pgno));
 429                 return (DB_VERIFY_BAD);
 430         }
 431         if ((ret = __db_vrfy_pgset_inc(pgset, meta_pgno)) != 0)
 432                 return (ret);
 433
 434         /* Get the meta page;  we'll need it frequently. */
 435         if ((ret = memp_fget(dbp->mpf, &meta_pgno, 0, &m)) != 0)
 436                 return (ret);
 437
 438         /* Loop through bucket by bucket. */
 439         for (bucket = 0; bucket <= m->max_bucket; bucket++)
 440                 if ((ret =
 441                     __ham_vrfy_bucket(dbp, vdp, m, bucket, flags)) != 0) {
 442                         if (ret == DB_VERIFY_BAD)
 443                                 isbad = 1;
 444                         else
 445                                 goto err;
 446                     }
 447
 448         /*
 449          * There may be unused hash pages corresponding to buckets
 450          * that have been allocated but not yet used.  These may be
 451          * part of the current doubling above max_bucket, or they may
 452          * correspond to buckets that were used in a transaction
 453          * that then aborted.
 454          *
 455          * Loop through them, as far as the spares array defines them,
 456          * and make sure they're all empty.
 457          *
 458          * Note that this should be safe, since we've already verified
 459          * that the spares array is sane.
 460          */
 461         for (bucket = m->max_bucket + 1; spares_entry = __db_log2(bucket + 1),
 462             spares_entry < NCACHED && m->spares[spares_entry] != 0; bucket++) {
 463                 pgno = BS_TO_PAGE(bucket, m->spares);
 464                 if ((ret = __db_vrfy_getpageinfo(vdp, pgno, &pip)) != 0)
 465                         goto err;
 466
 467                 /* It's okay if these pages are totally zeroed;  unmark it. */
 468                 F_CLR(pip, VRFY_IS_ALLZEROES);
 469
 470                 if (pip->type != P_HASH) {
 471                         EPRINT((dbp->dbenv,
 472                             "Hash bucket %lu maps to non-hash page %lu",
 473                             (u_long)bucket, (u_long)pgno));
 474                         isbad = 1;
 475                 } else if (pip->entries != 0) {
 476                         EPRINT((dbp->dbenv,
 477                             "Non-empty page %lu in unused hash bucket %lu",
 478                             (u_long)pgno, (u_long)bucket));
 479                         isbad = 1;
 480                 } else {
 481                         if ((ret = __db_vrfy_pgset_get(pgset, pgno, &p)) != 0)
 482                                 goto err;
 483                         if (p != 0) {
 484                                 EPRINT((dbp->dbenv,
 485                                     "Hash page %lu above max_bucket referenced",
 486                                     (u_long)pgno));
 487                                 isbad = 1;
 488                         } else {
 489                                 if ((ret =
 490                                     __db_vrfy_pgset_inc(pgset, pgno)) != 0)
 491                                         goto err;
 492                                 if ((ret = __db_vrfy_putpageinfo(dbp->dbenv,
 493                                     vdp, pip)) != 0)
 494                                         goto err;
 495                                 continue;
 496                         }
 497                 }
 498
 499                 /* If we got here, it's an error. */
 500                 (void)__db_vrfy_putpageinfo(dbp->dbenv, vdp, pip);
 501                 goto err;
 502         }
 503
 504 err:    if ((t_ret = memp_fput(dbp->mpf, m, 0)) != 0)
 505                 return (t_ret);
 506         if (h != NULL && (t_ret = memp_fput(dbp->mpf, h, 0)) != 0)
 507                 return (t_ret);
 508         return ((isbad == 1 && ret == 0) ? DB_VERIFY_BAD: ret);
 509 }
 510
 511 /*
 512  * __ham_vrfy_bucket --
 513  *      Verify a given bucket.
 514  */
 515 static int
 516 __ham_vrfy_bucket(dbp, vdp, m, bucket, flags)
 517         DB *dbp;
 518         VRFY_DBINFO *vdp;
 519         HMETA *m;
 520         u_int32_t bucket, flags;
 521 {
 522         HASH *hashp;
 523         VRFY_CHILDINFO *child;
 524         VRFY_PAGEINFO *mip, *pip;
 525         int ret, t_ret, isbad, p;
 526         db_pgno_t pgno, next_pgno;
 527         DBC *cc;
 528         u_int32_t (*hfunc) __P((DB *, const void *, u_int32_t));
 529
 530         isbad = 0;
 531         pip = NULL;
 532         cc = NULL;
 533
 534         hashp = dbp->h_internal;
 535         if (hashp != NULL && hashp->h_hash != NULL)
 536                 hfunc = hashp->h_hash;
 537         else
 538                 hfunc = __ham_func5;
 539
 540         if ((ret = __db_vrfy_getpageinfo(vdp, PGNO(m), &mip)) != 0)
 541                 return (ret);
 542
 543         /* Calculate the first pgno for this bucket. */
 544         pgno = BS_TO_PAGE(bucket, m->spares);
 545
 546         if ((ret = __db_vrfy_getpageinfo(vdp, pgno, &pip)) != 0)
 547                 goto err;
 548
 549         /* Make sure we got a plausible page number. */
 550         if (pgno > vdp->last_pgno || pip->type != P_HASH) {
 551                 EPRINT((dbp->dbenv, "Bucket %lu has impossible first page %lu",
 552                     (u_long)bucket, (u_long)pgno));
 553                 /* Unsafe to continue. */
 554                 isbad = 1;
 555                 goto err;
 556         }
 557
 558         if (pip->prev_pgno != PGNO_INVALID) {
 559                 EPRINT((dbp->dbenv,
 560                     "First hash page %lu in bucket %lu has a prev_pgno",
 561                     (u_long)pgno));
 562                 isbad = 1;
 563         }
 564
 565         /*
 566          * Set flags for dups and sorted dups.
 567          */
 568         flags |= F_ISSET(mip, VRFY_HAS_DUPS) ? ST_DUPOK : 0;
 569         flags |= F_ISSET(mip, VRFY_HAS_DUPSORT) ? ST_DUPSORT : 0;
 570
 571         /* Loop until we find a fatal bug, or until we run out of pages. */
 572         for (;;) {
 573                 /* Provide feedback on our progress to the application. */
 574                 if (!LF_ISSET(DB_SALVAGE))
 575                         __db_vrfy_struct_feedback(dbp, vdp);
 576
 577                 if ((ret = __db_vrfy_pgset_get(vdp->pgset, pgno, &p)) != 0)
 578                         goto err;
 579                 if (p != 0) {
 580                         EPRINT((dbp->dbenv,
 581                             "Hash page %lu referenced twice", (u_long)pgno));
 582                         isbad = 1;
 583                         /* Unsafe to continue. */
 584                         goto err;
 585                 } else if ((ret = __db_vrfy_pgset_inc(vdp->pgset, pgno)) != 0)
 586                         goto err;
 587
 588                 /*
 589                  * Hash pages that nothing has ever hashed to may never
 590                  * have actually come into existence, and may appear to be
 591                  * entirely zeroed.  This is acceptable, and since there's
 592                  * no real way for us to know whether this has actually
 593                  * occurred, we clear the "wholly zeroed" flag on every
 594                  * hash page.  A wholly zeroed page, by nature, will appear
 595                  * to have no flags set and zero entries, so should
 596                  * otherwise verify correctly.
 597                  */
 598                 F_CLR(pip, VRFY_IS_ALLZEROES);
 599
 600                 /* If we have dups, our meta page had better know about it. */
 601                 if (F_ISSET(pip, VRFY_HAS_DUPS)
 602                     && !F_ISSET(mip, VRFY_HAS_DUPS)) {
 603                         EPRINT((dbp->dbenv,
 604                     "Duplicates present in non-duplicate database, page %lu",
 605                             (u_long)pgno));
 606                         isbad = 1;
 607                 }
 608
 609                 /*
 610                  * If the database has sorted dups, this page had better
 611                  * not have unsorted ones.
 612                  */
 613                 if (F_ISSET(mip, VRFY_HAS_DUPSORT) &&
 614                     F_ISSET(pip, VRFY_DUPS_UNSORTED)) {
 615                         EPRINT((dbp->dbenv,
 616                             "Unsorted dups in sorted-dup database, page %lu",
 617                             (u_long)pgno));
 618                         isbad = 1;
 619                 }
 620
 621                 /* Walk overflow chains and offpage dup trees. */
 622                 if ((ret = __db_vrfy_childcursor(vdp, &cc)) != 0)
 623                         goto err;
 624                 for (ret = __db_vrfy_ccset(cc, pip->pgno, &child); ret == 0;
 625                     ret = __db_vrfy_ccnext(cc, &child))
 626                         if (child->type == V_OVERFLOW) {
 627                                 if ((ret = __db_vrfy_ovfl_structure(dbp, vdp,
 628                                     child->pgno, child->tlen, flags)) != 0) {
 629                                         if (ret == DB_VERIFY_BAD)
 630                                                 isbad = 1;
 631                                         else
 632                                                 goto err;
 633                                 }
 634                         } else if (child->type == V_DUPLICATE) {
 635                                 if ((ret = __db_vrfy_duptype(dbp,
 636                                     vdp, child->pgno, flags)) != 0) {
 637                                         isbad = 1;
 638                                         continue;
 639                                 }
 640                                 if ((ret = __bam_vrfy_subtree(dbp, vdp,
 641                                     child->pgno, NULL, NULL,
 642                                     flags | ST_RECNUM | ST_DUPSET, NULL,
 643                                     NULL, NULL)) != 0) {
 644                                         if (ret == DB_VERIFY_BAD)
 645                                                 isbad = 1;
 646                                         else
 647                                                 goto err;
 648                                 }
 649                         }
 650                 if ((ret = __db_vrfy_ccclose(cc)) != 0)
 651                         goto err;
 652                 cc = NULL;
 653
 654                 /* If it's safe to check that things hash properly, do so. */
 655                 if (isbad == 0 && !LF_ISSET(DB_NOORDERCHK) &&
 656                     (ret = __ham_vrfy_hashing(dbp, pip->entries,
 657                     m, bucket, pgno, flags, hfunc)) != 0) {
 658                         if (ret == DB_VERIFY_BAD)
 659                                 isbad = 1;
 660                         else
 661                                 goto err;
 662                 }
 663
 664                 next_pgno = pip->next_pgno;
 665                 ret = __db_vrfy_putpageinfo(dbp->dbenv, vdp, pip);
 666
 667                 pip = NULL;
 668                 if (ret != 0)
 669                         goto err;
 670
 671                 if (next_pgno == PGNO_INVALID)
 672                         break;          /* End of the bucket. */
 673
 674                 /* We already checked this, but just in case... */
 675                 if (!IS_VALID_PGNO(next_pgno)) {
 676                         DB_ASSERT(0);
 677                         EPRINT((dbp->dbenv,
 678                             "Hash page %lu has bad next_pgno", (u_long)pgno));
 679                         isbad = 1;
 680                         goto err;
 681                 }
 682
 683                 if ((ret = __db_vrfy_getpageinfo(vdp, next_pgno, &pip)) != 0)
 684                         goto err;
 685
 686                 if (pip->prev_pgno != pgno) {
 687                         EPRINT((dbp->dbenv, "Hash page %lu has bad prev_pgno",
 688                             (u_long)next_pgno));
 689                         isbad = 1;
 690                 }
 691                 pgno = next_pgno;
 692         }
 693
 694 err:    if (cc != NULL && ((t_ret = __db_vrfy_ccclose(cc)) != 0) && ret == 0)
 695                 ret = t_ret;
 696         if (mip != NULL && ((t_ret =
 697             __db_vrfy_putpageinfo(dbp->dbenv, vdp, mip)) != 0) && ret == 0)
 698                 ret = t_ret;
 699         if (pip != NULL && ((t_ret =
 700             __db_vrfy_putpageinfo(dbp->dbenv, vdp, pip)) != 0) && ret == 0)
 701                 ret = t_ret;
 702         return ((ret == 0 && isbad == 1) ? DB_VERIFY_BAD : ret);
 703 }
 704
 705 /*
 706  * __ham_vrfy_hashing --
 707  *      Verify that all items on a given hash page hash correctly.
 708  *
 709  * PUBLIC: int __ham_vrfy_hashing __P((DB *,
 710  * PUBLIC:     u_int32_t, HMETA *, u_int32_t, db_pgno_t, u_int32_t,
 711  * PUBLIC:     u_int32_t (*) __P((DB *, const void *, u_int32_t))));
 712  */
 713 int
 714 __ham_vrfy_hashing(dbp, nentries, m, thisbucket, pgno, flags, hfunc)
 715         DB *dbp;
 716         u_int32_t nentries;
 717         HMETA *m;
 718         u_int32_t thisbucket;
 719         db_pgno_t pgno;
 720         u_int32_t flags;
 721         u_int32_t (*hfunc) __P((DB *, const void *, u_int32_t));
 722 {
 723         DBT dbt;
 724         PAGE *h;
 725         db_indx_t i;
 726         int ret, t_ret, isbad;
 727         u_int32_t hval, bucket;
 728
 729         ret = isbad = 0;
 730         memset(&dbt, 0, sizeof(DBT));
 731         F_SET(&dbt, DB_DBT_REALLOC);
 732
 733         if ((ret = memp_fget(dbp->mpf, &pgno, 0, &h)) != 0)
 734                 return (ret);
 735
 736         for (i = 0; i < nentries; i += 2) {
 737                 /*
 738                  * We've already verified the page integrity and that of any
 739                  * overflow chains linked off it;  it is therefore safe to use
 740                  * __db_ret.  It's also not all that much slower, since we have
 741                  * to copy every hash item to deal with alignment anyway;  we
 742                  * can tweak this a bit if this proves to be a bottleneck,
 743                  * but for now, take the easy route.
 744                  */
 745                 if ((ret = __db_ret(dbp, h, i, &dbt, NULL, NULL)) != 0)
 746                         goto err;
 747                 hval = hfunc(dbp, dbt.data, dbt.size);
 748
 749                 bucket = hval & m->high_mask;
 750                 if (bucket > m->max_bucket)
 751                         bucket = bucket & m->low_mask;
 752
 753                 if (bucket != thisbucket) {
 754                         EPRINT((dbp->dbenv,
 755                             "Item %lu on page %lu hashes incorrectly",
 756                             (u_long)i, (u_long)pgno));
 757                         isbad = 1;
 758                 }
 759         }
 760
 761 err:    if (dbt.data != NULL)
 762                 __os_free(dbp->dbenv, dbt.data, 0);
 763         if ((t_ret = memp_fput(dbp->mpf, h, 0)) != 0)
 764                 return (t_ret);
 765
 766         return ((ret == 0 && isbad == 1) ? DB_VERIFY_BAD : ret);
 767 }
 768
 769 /*
 770  * __ham_salvage --
 771  *      Safely dump out anything that looks like a key on an alleged
 772  *      hash page.
 773  *
 774  * PUBLIC: int __ham_salvage __P((DB *, VRFY_DBINFO *, db_pgno_t, PAGE *,
 775  * PUBLIC:     void *, int (*)(void *, const void *), u_int32_t));
 776  */
 777 int
 778 __ham_salvage(dbp, vdp, pgno, h, handle, callback, flags)
 779         DB *dbp;
 780         VRFY_DBINFO *vdp;
 781         db_pgno_t pgno;
 782         PAGE *h;
 783         void *handle;
 784         int (*callback) __P((void *, const void *));
 785         u_int32_t flags;
 786 {
 787         DBT dbt, unkdbt;
 788         db_pgno_t dpgno;
 789         int ret, err_ret, t_ret;
 790         u_int32_t himark, tlen;
 791         u_int8_t *hk;
 792         void *buf;
 793         u_int32_t dlen, len, i;
 794
 795         memset(&dbt, 0, sizeof(DBT));
 796         dbt.flags = DB_DBT_REALLOC;
 797
 798         memset(&unkdbt, 0, sizeof(DBT));
 799         unkdbt.size = strlen("UNKNOWN") + 1;
 800         unkdbt.data = "UNKNOWN";
 801
 802         err_ret = 0;
 803
 804         /*
 805          * Allocate a buffer for overflow items.  Start at one page;
 806          * __db_safe_goff will realloc as needed.
 807          */
 808         if ((ret = __os_malloc(dbp->dbenv, dbp->pgsize, &buf)) != 0)
 809                 return (ret);
 810
 811         himark = dbp->pgsize;
 812         for (i = 0;; i++) {
 813                 /* If we're not aggressive, break when we hit NUM_ENT(h). */
 814                 if (!LF_ISSET(DB_AGGRESSIVE) && i >= NUM_ENT(h))
 815                         break;
 816
 817                 /* Verify the current item. */
 818                 ret = __db_vrfy_inpitem(dbp,
 819                     h, pgno, i, 0, flags, &himark, NULL);
 820                 /* If this returned a fatality, it's time to break. */
 821                 if (ret == DB_VERIFY_FATAL)
 822                         break;
 823
 824                 if (ret == 0) {
 825                         hk = P_ENTRY(h, i);
 826                         len = LEN_HKEYDATA(h, dbp->pgsize, i);
 827                         if ((u_int32_t)(hk + len - (u_int8_t *)h) >
 828                             dbp->pgsize) {
 829                                 /*
 830                                  * Item is unsafely large;  either continue
 831                                  * or set it to the whole page, depending on
 832                                  * aggressiveness.
 833                                  */
 834                                 if (!LF_ISSET(DB_AGGRESSIVE))
 835                                         continue;
 836                                 len = dbp->pgsize -
 837                                     (u_int32_t)(hk - (u_int8_t *)h);
 838                                 err_ret = DB_VERIFY_BAD;
 839                         }
 840                         switch (HPAGE_PTYPE(hk)) {
 841                         default:
 842                                 if (!LF_ISSET(DB_AGGRESSIVE))
 843                                         break;
 844                                 err_ret = DB_VERIFY_BAD;
 845                                 /* FALLTHROUGH */
 846                         case H_KEYDATA:
 847 keydata:                        memcpy(buf, HKEYDATA_DATA(hk), len);
 848                                 dbt.size = len;
 849                                 dbt.data = buf;
 850                                 if ((ret = __db_prdbt(&dbt,
 851                                     0, " ", handle, callback, 0, NULL)) != 0)
 852                                         err_ret = ret;
 853                                 break;
 854                         case H_OFFPAGE:
 855                                 if (len < HOFFPAGE_SIZE) {
 856                                         err_ret = DB_VERIFY_BAD;
 857                                         continue;
 858                                 }
 859                                 memcpy(&dpgno,
 860                                     HOFFPAGE_PGNO(hk), sizeof(dpgno));
 861                                 if ((ret = __db_safe_goff(dbp, vdp,
 862                                     dpgno, &dbt, &buf, flags)) != 0) {
 863                                         err_ret = ret;
 864                                         (void)__db_prdbt(&unkdbt, 0, " ",
 865                                             handle, callback, 0, NULL);
 866                                         break;
 867                                 }
 868                                 if ((ret = __db_prdbt(&dbt,
 869                                     0, " ", handle, callback, 0, NULL)) != 0)
 870                                         err_ret = ret;
 871                                 break;
 872                         case H_OFFDUP:
 873                                 if (len < HOFFPAGE_SIZE) {
 874                                         err_ret = DB_VERIFY_BAD;
 875                                         continue;
 876                                 }
 877                                 memcpy(&dpgno,
 878                                     HOFFPAGE_PGNO(hk), sizeof(dpgno));
 879                                 /* UNKNOWN iff pgno is bad or we're a key. */
 880                                 if (!IS_VALID_PGNO(dpgno) || (i % 2 == 0)) {
 881                                         if ((ret = __db_prdbt(&unkdbt, 0, " ",
 882                                             handle, callback, 0, NULL)) != 0)
 883                                                 err_ret = ret;
 884                                 } else if ((ret = __db_salvage_duptree(dbp,
 885                                     vdp, dpgno, &dbt, handle, callback,
 886                                     flags | SA_SKIPFIRSTKEY)) != 0)
 887                                         err_ret = ret;
 888                                 break;
 889                         case H_DUPLICATE:
 890                                 /*
 891                                  * We're a key;  printing dups will seriously
 892                                  * foul the output.  If we're being aggressive,
 893                                  * pretend this is a key and let the app.
 894                                  * programmer sort out the mess.
 895                                  */
 896                                 if (i % 2 == 0) {
 897                                         err_ret = ret;
 898                                         if (LF_ISSET(DB_AGGRESSIVE))
 899                                                 goto keydata;
 900                                         break;
 901                                 }
 902
 903                                 /* Too small to have any data. */
 904                                 if (len <
 905                                     HKEYDATA_SIZE(2 * sizeof(db_indx_t))) {
 906                                         err_ret = DB_VERIFY_BAD;
 907                                         continue;
 908                                 }
 909
 910                                 /* Loop until we hit the total length. */
 911                                 for (tlen = 0; tlen + sizeof(db_indx_t) < len;
 912                                     tlen += dlen) {
 913                                         tlen += sizeof(db_indx_t);
 914                                         memcpy(&dlen, hk, sizeof(db_indx_t));
 915                                         /*
 916                                          * If dlen is too long, print all the
 917                                          * rest of the dup set in a chunk.
 918                                          */
 919                                         if (dlen + tlen > len)
 920                                                 dlen = len - tlen;
 921                                         memcpy(buf, hk + tlen, dlen);
 922                                         dbt.size = dlen;
 923                                         dbt.data = buf;
 924                                         if ((ret = __db_prdbt(&dbt, 0, " ",
 925                                             handle, callback, 0, NULL)) != 0)
 926                                                 err_ret = ret;
 927                                         tlen += sizeof(db_indx_t);
 928                                 }
 929                                 break;
 930                         }
 931                 }
 932         }
 933
 934         __os_free(dbp->dbenv, buf, 0);
 935         if ((t_ret = __db_salvage_markdone(vdp, pgno)) != 0)
 936                 return (t_ret);
 937         return ((ret == 0 && err_ret != 0) ? err_ret : ret);
 938 }
 939
 940 /*
 941  * __ham_meta2pgset --
 942  *      Return the set of hash pages corresponding to the given
 943  *      known-good meta page.
 944  *
 945  * PUBLIC: int __ham_meta2pgset __P((DB *, VRFY_DBINFO *, HMETA *, u_int32_t,
 946  * PUBLIC:     DB *));
 947  */
 948 int __ham_meta2pgset(dbp, vdp, hmeta, flags, pgset)
 949         DB *dbp;
 950         VRFY_DBINFO *vdp;
 951         HMETA *hmeta;
 952         u_int32_t flags;
 953         DB *pgset;
 954 {
 955         PAGE *h;
 956         db_pgno_t pgno;
 957         u_int32_t bucket, totpgs;
 958         int ret, val;
 959
 960         /*
 961          * We don't really need flags, but leave them for consistency with
 962          * __bam_meta2pgset.
 963          */
 964         COMPQUIET(flags, 0);
 965
 966         DB_ASSERT(pgset != NULL);
 967
 968         totpgs = 0;
 969
 970         /*
 971          * Loop through all the buckets, pushing onto pgset the corresponding
 972          * page(s) for each one.
 973          */
 974         for (bucket = 0; bucket <= hmeta->max_bucket; bucket++) {
 975                 pgno = BS_TO_PAGE(bucket, hmeta->spares);
 976
 977                 /*
 978                  * We know the initial pgno is safe because the spares array has
 979                  * been verified.
 980                  *
 981                  * Safely walk the list of pages in this bucket.
 982                  */
 983                 for (;;) {
 984                         if ((ret = memp_fget(dbp->mpf, &pgno, 0, &h)) != 0)
 985                                 return (ret);
 986                         if (TYPE(h) == P_HASH) {
 987
 988                                 /*
 989                                  * Make sure we don't go past the end of
 990                                  * pgset.
 991                                  */
 992                                 if (++totpgs > vdp->last_pgno) {
 993                                         (void)memp_fput(dbp->mpf, h, 0);
 994                                         return (DB_VERIFY_BAD);
 995                                 }
 996                                 if ((ret =
 997                                     __db_vrfy_pgset_inc(pgset, pgno)) != 0) {
 998                                         (void)memp_fput(dbp->mpf, h, 0);
 999                                         return (ret);
1000                                 }
1001
1002                                 pgno = NEXT_PGNO(h);
1003                         } else
1004                                 pgno = PGNO_INVALID;
1005
1006                         if ((ret = memp_fput(dbp->mpf, h, 0)) != 0)
1007                                 return (ret);
1008
1009                         /* If the new pgno is wonky, go onto the next bucket. */
1010                         if (!IS_VALID_PGNO(pgno) ||
1011                             pgno == PGNO_INVALID)
1012                                 break;
1013
1014                         /*
1015                          * If we've touched this page before, we have a cycle;
1016                          * go on to the next bucket.
1017                          */
1018                         if ((ret = __db_vrfy_pgset_get(pgset, pgno, &val)) != 0)
1019                                 return (ret);
1020                         if (val != 0)
1021                                 break;
1022                 }
1023         }
1024         return (0);
1025 }
1026
1027 /*
1028  * __ham_dups_unsorted --
1029  *      Takes a known-safe hash duplicate set and its total length.
1030  *      Returns 1 if there are out-of-order duplicates in this set,
1031  *      0 if there are not.
1032  */
1033 static int
1034 __ham_dups_unsorted(dbp, buf, len)
1035         DB *dbp;
1036         u_int8_t *buf;
1037         u_int32_t len;
1038 {
1039         DBT a, b;
1040         db_indx_t offset, dlen;
1041         int (*func) __P((DB *, const DBT *, const DBT *));
1042
1043         memset(&a, 0, sizeof(DBT));
1044         memset(&b, 0, sizeof(DBT));
1045
1046         func = (dbp->dup_compare == NULL) ? __bam_defcmp : dbp->dup_compare;
1047
1048         /*
1049          * Loop through the dup set until we hit the end or we find
1050          * a pair of dups that's out of order.  b is always the current
1051          * dup, a the one before it.
1052          */
1053         for (offset = 0; offset < len; offset += DUP_SIZE(dlen)) {
1054                 memcpy(&dlen, buf + offset, sizeof(db_indx_t));
1055                 b.data = buf + offset + sizeof(db_indx_t);
1056                 b.size = dlen;
1057
1058                 if (a.data != NULL && func(dbp, &a, &b) > 0)
1059                         return (1);
1060
1061                 a.data = b.data;
1062                 a.size = b.size;
1063         }
1064
1065         return (0);
1066 }