开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > 数据库系统 > MySQL数据库 > 查看源码
bt_verify.c
资源名称：mysql-3.23.35.tar.gz　[点击查看]
上传用户：tsgydb
上传日期：2007-04-14
资源大小：10674k
文件大小：57k
源码类别：

MySQL数据库

开发平台：

Visual C++

bt_verify.c：源码内容
  1. /*-
  2.  * See the file LICENSE for redistribution information.
  3.  *
  4.  * Copyright (c) 1999, 2000
  5.  * Sleepycat Software.  All rights reserved.
  6.  *
  7.  * $Id: bt_verify.c,v 1.44 2000/12/06 19:55:44 ubell Exp $
  8.  */
  10. #include "db_config.h"
  12. #ifndef lint
  13. static const char revid[] = "$Id: bt_verify.c,v 1.44 2000/12/06 19:55:44 ubell Exp $";
  14. #endif /* not lint */
  16. #ifndef NO_SYSTEM_INCLUDES
  17. #include <sys/types.h>
  19. #include <string.h>
  20. #endif
  22. #include "db_int.h"
  23. #include "db_page.h"
  24. #include "db_verify.h"
  25. #include "btree.h"
  27. static int __bam_safe_getdata __P((DB *, PAGE *, u_int32_t, int, DBT *, int *));
  28. static int __bam_vrfy_inp __P((DB *, VRFY_DBINFO *, PAGE *, db_pgno_t,
  29.     db_indx_t *, u_int32_t));
  30. static int __bam_vrfy_treeorder __P((DB *, db_pgno_t, PAGE *, BINTERNAL *,
  31.     BINTERNAL *, int (*)(DB *, const DBT *, const DBT *), u_int32_t));
  32. static int __ram_vrfy_inp __P((DB *, VRFY_DBINFO *, PAGE *, db_pgno_t,
  33.     db_indx_t *, u_int32_t));
  35. #define OKFLAGS (DB_AGGRESSIVE | DB_NOORDERCHK | DB_SALVAGE)
  37. /*
  38.  * __bam_vrfy_meta --
  39.  * Verify the btree-specific part of a metadata page.
  40.  *
  41.  * PUBLIC: int __bam_vrfy_meta __P((DB *, VRFY_DBINFO *, BTMETA *,
  42.  * PUBLIC:     db_pgno_t, u_int32_t));
  43.  */
  44. int
  45. __bam_vrfy_meta(dbp, vdp, meta, pgno, flags)
  46. DB *dbp;
  47. VRFY_DBINFO *vdp;
  48. BTMETA *meta;
  49. db_pgno_t pgno;
  50. u_int32_t flags;
  51. {
  52. VRFY_PAGEINFO *pip;
  53. int isbad, t_ret, ret;
  54. db_indx_t ovflsize;
  56. if ((ret = __db_vrfy_getpageinfo(vdp, pgno, &pip)) != 0)
  57. return (ret);
  59. isbad = 0;
  61. /*
  62.  * If VRFY_INCOMPLETE is not set, then we didn't come through
  63.  * __db_vrfy_pagezero and didn't incompletely
  64.  * check this page--we haven't checked it at all.
  65.  * Thus we need to call __db_vrfy_meta and check the common fields.
  66.  *
  67.  * If VRFY_INCOMPLETE is set, we've already done all the same work
  68.  * in __db_vrfy_pagezero, so skip the check.
  69.  */
  70. if (!F_ISSET(pip, VRFY_INCOMPLETE) &&
  71.     (ret = __db_vrfy_meta(dbp, vdp, &meta->dbmeta, pgno, flags)) != 0) {
  72. if (ret == DB_VERIFY_BAD)
  73. isbad = 1;
  74. else
  75. goto err;
  76. }
  78. /* bt_minkey:  must be >= 2; must produce sensible ovflsize */
  80. /* avoid division by zero */
  81. ovflsize = meta->minkey > 0 ?
  82.     B_MINKEY_TO_OVFLSIZE(meta->minkey, dbp->pgsize) : 0;
  84. if (meta->minkey < 2 ||
  85.     ovflsize > B_MINKEY_TO_OVFLSIZE(DEFMINKEYPAGE, dbp->pgsize)) {
  86. pip->bt_minkey = 0;
  87. isbad = 1;
  88. EPRINT((dbp->dbenv,
  89.     "Nonsensical bt_minkey value %lu on metadata page %lu",
  90.     (u_long)meta->minkey, (u_long)pgno));
  91. } else
  92. pip->bt_minkey = meta->minkey;
  94. /* bt_maxkey: no constraints (XXX: right?) */
  95. pip->bt_maxkey = meta->maxkey;
  97. /* re_len: no constraints on this (may be zero or huge--we make rope) */
  98. pip->re_len = meta->re_len;
  100. /*
  101.  * The root must not be current page or 0 and it must be within
  102.  * database.  If this metadata page is the master meta data page
  103.  * of the file, then the root page had better be page 1.
  104.  */
  105. pip->root = 0;
  106. if (meta->root == PGNO_INVALID
  107.     || meta->root == pgno || !IS_VALID_PGNO(meta->root) ||
  108.     (pgno == PGNO_BASE_MD && meta->root != 1)) {
  109. isbad = 1;
  110. EPRINT((dbp->dbenv,
  111.     "Nonsensical root page %lu on metadata page %lu",
  112.     (u_long)meta->root, (u_long)vdp->last_pgno));
  113. } else
  114. pip->root = meta->root;
  116. /* Flags. */
  117. if (F_ISSET(&meta->dbmeta, BTM_RENUMBER))
  118. F_SET(pip, VRFY_IS_RRECNO);
  120. if (F_ISSET(&meta->dbmeta, BTM_SUBDB)) {
  121. /*
  122.  * If this is a master db meta page, it had better not have
  123.  * duplicates.
  124.  */
  125. if (F_ISSET(&meta->dbmeta, BTM_DUP) && pgno == PGNO_BASE_MD) {
  126. isbad = 1;
  127. EPRINT((dbp->dbenv,
  128. "Btree metadata page %lu has both duplicates and multiple databases",
  129.     (u_long)pgno));
  130. }
  131. F_SET(pip, VRFY_HAS_SUBDBS);
  132. }
  134. if (F_ISSET(&meta->dbmeta, BTM_DUP))
  135. F_SET(pip, VRFY_HAS_DUPS);
  136. if (F_ISSET(&meta->dbmeta, BTM_DUPSORT))
  137. F_SET(pip, VRFY_HAS_DUPSORT);
  138. if (F_ISSET(&meta->dbmeta, BTM_RECNUM))
  139. F_SET(pip, VRFY_HAS_RECNUMS);
  140. if (F_ISSET(pip, VRFY_HAS_RECNUMS) && F_ISSET(pip, VRFY_HAS_DUPS)) {
  141. EPRINT((dbp->dbenv,
  142.     "Btree metadata page %lu illegally has both recnums and dups",
  143.     (u_long)pgno));
  144. isbad = 1;
  145. }
  147. if (F_ISSET(&meta->dbmeta, BTM_RECNO)) {
  148. F_SET(pip, VRFY_IS_RECNO);
  149. dbp->type = DB_RECNO;
  150. } else if (F_ISSET(pip, VRFY_IS_RRECNO)) {
  151. isbad = 1;
  152. EPRINT((dbp->dbenv,
  153.     "Metadata page %lu has renumber flag set but is not recno",
  154.     (u_long)pgno));
  155. }
  157. if (F_ISSET(pip, VRFY_IS_RECNO) && F_ISSET(pip, VRFY_HAS_DUPS)) {
  158. EPRINT((dbp->dbenv,
  159.     "Recno metadata page %lu specifies duplicates",
  160.     (u_long)pgno));
  161. isbad = 1;
  162. }
  164. if (F_ISSET(&meta->dbmeta, BTM_FIXEDLEN))
  165. F_SET(pip, VRFY_IS_FIXEDLEN);
  166. else if (pip->re_len > 0) {
  167. /*
  168.  * It's wrong to have an re_len if it's not a fixed-length
  169.  * database
  170.  */
  171. isbad = 1;
  172. EPRINT((dbp->dbenv,
  173.     "re_len of %lu in non-fixed-length database",
  174.     (u_long)pip->re_len));
  175. }
  177. /*
  178.  * We do not check that the rest of the page is 0, because it may
  179.  * not be and may still be correct.
  180.  */
  182. err: if ((t_ret = __db_vrfy_putpageinfo(vdp, pip)) != 0 && ret == 0)
  183. ret = t_ret;
  184. return ((ret == 0 && isbad == 1) ? DB_VERIFY_BAD : ret);
  185. }
  187. /*
  188.  * __ram_vrfy_leaf --
  189.  * Verify a recno leaf page.
  190.  *
  191.  * PUBLIC: int __ram_vrfy_leaf __P((DB *, VRFY_DBINFO *, PAGE *, db_pgno_t,
  192.  * PUBLIC:     u_int32_t));
  193.  */
  194. int
  195. __ram_vrfy_leaf(dbp, vdp, h, pgno, flags)
  196. DB *dbp;
  197. VRFY_DBINFO *vdp;
  198. PAGE *h;
  199. db_pgno_t pgno;
  200. u_int32_t flags;
  201. {
  202. BKEYDATA *bk;
  203. VRFY_PAGEINFO *pip;
  204. db_indx_t i;
  205. int ret, t_ret, isbad;
  206. u_int32_t re_len_guess, len;
  208. isbad = 0;
  209. if ((ret = __db_vrfy_getpageinfo(vdp, pgno, &pip)) != 0)
  210. return (ret);
  212. if ((ret = __db_fchk(dbp->dbenv,
  213.     "__ram_vrfy_leaf", flags, OKFLAGS)) != 0)
  214. goto err;
  216. if (TYPE(h) != P_LRECNO) {
  217. /* We should not have been called. */
  218. TYPE_ERR_PRINT(dbp->dbenv, "__ram_vrfy_leaf", pgno, TYPE(h));
  219. DB_ASSERT(0);
  220. ret = EINVAL;
  221. goto err;
  222. }
  224. /*
  225.  * Verify (and, if relevant, save off) page fields common to
  226.  * all PAGEs.
  227.  */
  228. if ((ret = __db_vrfy_datapage(dbp, vdp, h, pgno, flags)) != 0) {
  229. if (ret == DB_VERIFY_BAD)
  230. isbad = 1;
  231. else
  232. goto err;
  233. }
  235. /*
  236.  * Verify inp[].  Return immediately if it returns DB_VERIFY_BAD;
  237.  * further checks are dangerous.
  238.  */
  239. if ((ret = __bam_vrfy_inp(dbp,
  240.     vdp, h, pgno, &pip->entries, flags)) != 0)
  241. goto err;
  243. if (F_ISSET(pip, VRFY_HAS_DUPS)) {
  244. EPRINT((dbp->dbenv,
  245.     "Recno database has dups on page %lu", (u_long)pgno));
  246. ret = DB_VERIFY_BAD;
  247. goto err;
  248. }
  250. /*
  251.  * Walk through inp and see if the lengths of all the records are the
  252.  * same--if so, this may be a fixed-length database, and we want to
  253.  * save off this value.  We know inp to be safe if we've gotten this
  254.  * far.
  255.  */
  256. re_len_guess = 0;
  257. for (i = 0; i < NUM_ENT(h); i++) {
  258. bk = GET_BKEYDATA(h, i);
  259. /* KEYEMPTY.  Go on. */
  260. if (B_DISSET(bk->type))
  261. continue;
  262. if (bk->type == B_OVERFLOW)
  263. len = ((BOVERFLOW *)bk)->tlen;
  264. else if (bk->type == B_KEYDATA)
  265. len = bk->len;
  266. else {
  267. isbad = 1;
  268. EPRINT((dbp->dbenv,
  269.     "Nonsensical type for item %lu, page %lu",
  270.     (u_long)i, (u_long)pgno));
  271. continue;
  272. }
  273. if (re_len_guess == 0)
  274. re_len_guess = len;
  276. /*
  277.  * Is this item's len the same as the last one's?  If not,
  278.  * reset to 0 and break--we don't have a single re_len.
  279.  * Otherwise, go on to the next item.
  280.  */
  281. if (re_len_guess != len) {
  282. re_len_guess = 0;
  283. break;
  284. }
  285. }
  286. pip->re_len = re_len_guess;
  288. /* Save off record count. */
  289. pip->rec_cnt = NUM_ENT(h);
  291. err: if ((t_ret = __db_vrfy_putpageinfo(vdp, pip)) != 0 && ret == 0)
  292. ret = t_ret;
  293. return ((ret == 0 && isbad == 1) ? DB_VERIFY_BAD : 0);
  294. }
  296. /*
  297.  * __bam_vrfy --
  298.  * Verify a btree leaf or internal page.
  299.  *
  300.  * PUBLIC: int __bam_vrfy __P((DB *, VRFY_DBINFO *, PAGE *, db_pgno_t,
  301.  * PUBLIC:     u_int32_t));
  302.  */
  303. int
  304. __bam_vrfy(dbp, vdp, h, pgno, flags)
  305. DB *dbp;
  306. VRFY_DBINFO *vdp;
  307. PAGE *h;
  308. db_pgno_t pgno;
  309. u_int32_t flags;
  310. {
  311. VRFY_PAGEINFO *pip;
  312. int ret, t_ret, isbad;
  314. isbad = 0;
  315. if ((ret = __db_vrfy_getpageinfo(vdp, pgno, &pip)) != 0)
  316. return (ret);
  318. switch (TYPE(h)) {
  319. case P_IBTREE:
  320. case P_IRECNO:
  321. case P_LBTREE:
  322. case P_LDUP:
  323. break;
  324. default:
  325. TYPE_ERR_PRINT(dbp->dbenv, "__bam_vrfy", pgno, TYPE(h));
  326. DB_ASSERT(0);
  327. ret = EINVAL;
  328. goto err;
  329. }
  331. /*
  332.  * Verify (and, if relevant, save off) page fields common to
  333.  * all PAGEs.
  334.  */
  335. if ((ret = __db_vrfy_datapage(dbp, vdp, h, pgno, flags)) != 0) {
  336. if (ret == DB_VERIFY_BAD)
  337. isbad = 1;
  338. else
  339. goto err;
  340. }
  342. /*
  343.  * The record count is, on internal pages, stored in an overloaded
  344.  * next_pgno field.  Save it off;  we'll verify it when we check
  345.  * overall database structure.  We could overload the field
  346.  * in VRFY_PAGEINFO, too, but this seems gross, and space
  347.  * is not at such a premium.
  348.  */
  349. pip->rec_cnt = RE_NREC(h);
  351. /*
  352.  * Verify inp[].
  353.  */
  354. if (TYPE(h) == P_IRECNO) {
  355. if ((ret = __ram_vrfy_inp(dbp,
  356.     vdp, h, pgno, &pip->entries, flags)) != 0)
  357. goto err;
  358. } else if ((ret = __bam_vrfy_inp(dbp,
  359.     vdp, h, pgno, &pip->entries, flags)) != 0) {
  360. if (ret == DB_VERIFY_BAD)
  361. isbad = 1;
  362. else
  363. goto err;
  364. EPRINT((dbp->dbenv,
  365.     "item order check on page %lu unsafe: skipping",
  366.     (u_long)pgno));
  367. } else if (!LF_ISSET(DB_NOORDERCHK) && (ret =
  368.     __bam_vrfy_itemorder(dbp, vdp, h, pgno, 0, 0, 0, flags)) != 0) {
  369. /*
  370.  * We know that the elements of inp are reasonable.
  371.  *
  372.  * Check that elements fall in the proper order.
  373.  */
  374. if (ret == DB_VERIFY_BAD)
  375. isbad = 1;
  376. else
  377. goto err;
  378. }
  380. err: if ((t_ret = __db_vrfy_putpageinfo(vdp, pip)) != 0 && ret == 0)
  381. ret = t_ret;
  382. return ((ret == 0 && isbad == 1) ? DB_VERIFY_BAD : 0);
  383. }
  385. /*
  386.  * __ram_vrfy_inp --
  387.  * Verify that all entries in a P_IRECNO inp[] array are reasonable,
  388.  * and count them.  Note that P_LRECNO uses __bam_vrfy_inp;
  389.  * P_IRECNOs are a special, and simpler, case, since they have
  390.  * RINTERNALs rather than BKEYDATA/BINTERNALs.
  391.  */
  392. static int
  393. __ram_vrfy_inp(dbp, vdp, h, pgno, nentriesp, flags)
  394. DB *dbp;
  395. VRFY_DBINFO *vdp;
  396. PAGE *h;
  397. db_pgno_t pgno;
  398. db_indx_t *nentriesp;
  399. u_int32_t flags;
  400. {
  401. RINTERNAL *ri;
  402. VRFY_CHILDINFO child;
  403. VRFY_PAGEINFO *pip;
  404. int ret, t_ret, isbad;
  405. u_int32_t himark, i, offset, nentries;
  406. u_int8_t *pagelayout, *p;
  408. isbad = 0;
  409. memset(&child, 0, sizeof(VRFY_CHILDINFO));
  410. nentries = 0;
  411. pagelayout = NULL;
  413. if ((ret = __db_vrfy_getpageinfo(vdp, pgno, &pip)) != 0)
  414. return (ret);
  416. if (TYPE(h) != P_IRECNO) {
  417. TYPE_ERR_PRINT(dbp->dbenv, "__ram_vrfy_inp", pgno, TYPE(h));
  418. DB_ASSERT(0);
  419. ret = EINVAL;
  420. goto err;
  421. }
  423. himark = dbp->pgsize;
  424. if ((ret =
  425.     __os_malloc(dbp->dbenv, dbp->pgsize, NULL, &pagelayout)) != 0)
  426. goto err;
  427. memset(pagelayout, 0, dbp->pgsize);
  428. for (i = 0; i < NUM_ENT(h); i++) {
  429. if ((u_int8_t *)h->inp + i >= (u_int8_t *)h + himark) {
  430. EPRINT((dbp->dbenv,
  431.     "Page %lu entries listing %lu overlaps data",
  432.     (u_long)pgno, (u_long)i));
  433. ret = DB_VERIFY_BAD;
  434. goto err;
  435. }
  436. offset = h->inp[i];
  437. /*
  438.  * Check that the item offset is reasonable:  it points
  439.  * somewhere after the inp array and before the end of the
  440.  * page.
  441.  */
  442. if (offset <= (u_int32_t)((u_int8_t *)h->inp + i -
  443.     (u_int8_t *)h) ||
  444.     offset > (u_int32_t)(dbp->pgsize - RINTERNAL_SIZE)) {
  445. isbad = 1;
  446. EPRINT((dbp->dbenv,
  447.     "Bad offset %lu at page %lu index %lu",
  448.     (u_long)offset, (u_long)pgno, (u_long)i));
  449. continue;
  450. }
  452. /* Update the high-water mark (what HOFFSET should be) */
  453. if (offset < himark)
  454. himark = offset;
  456. nentries++;
  458. /* Make sure this RINTERNAL is not multiply referenced. */
  459. ri = GET_RINTERNAL(h, i);
  460. if (pagelayout[offset] == 0) {
  461. pagelayout[offset] = 1;
  462. child.pgno = ri->pgno;
  463. child.type = V_RECNO;
  464. child.nrecs = ri->nrecs;
  465. if ((ret = __db_vrfy_childput(vdp, pgno, &child)) != 0)
  466. goto err;
  467. } else {
  468. EPRINT((dbp->dbenv,
  469. "RINTERNAL structure at offset %lu, page %lu referenced twice",
  470.     (u_long)offset, (u_long)pgno));
  471. isbad = 1;
  472. }
  473. }
  475. for (p = pagelayout + himark;
  476.     p < pagelayout + dbp->pgsize;
  477.     p += RINTERNAL_SIZE)
  478. if (*p != 1) {
  479. EPRINT((dbp->dbenv,
  480.     "Gap between items at offset %lu, page %lu",
  481.     (u_long)(p - pagelayout), (u_long)pgno));
  482. isbad = 1;
  483. }
  485. if ((db_indx_t)himark != HOFFSET(h)) {
  486. EPRINT((dbp->dbenv, "Bad HOFFSET %lu, appears to be %lu",
  487.     (u_long)(HOFFSET(h)), (u_long)himark));
  488. isbad = 1;
  489. }
  491. *nentriesp = nentries;
  493. err: if ((t_ret = __db_vrfy_putpageinfo(vdp, pip)) != 0 && ret == 0)
  494. ret = t_ret;
  495. if (pagelayout != NULL)
  496. __os_free(pagelayout, dbp->pgsize);
  497. return ((ret == 0 && isbad == 1) ? DB_VERIFY_BAD : ret);
  498. }
  500. /*
  501.  * __bam_vrfy_inp --
  502.  * Verify that all entries in inp[] array are reasonable;
  503.  * count them.
  504.  */
  505. static int
  506. __bam_vrfy_inp(dbp, vdp, h, pgno, nentriesp, flags)
  507. DB *dbp;
  508. VRFY_DBINFO *vdp;
  509. PAGE *h;
  510. db_pgno_t pgno;
  511. db_indx_t *nentriesp;
  512. u_int32_t flags;
  513. {
  514. BKEYDATA *bk;
  515. BOVERFLOW *bo;
  516. VRFY_CHILDINFO child;
  517. VRFY_PAGEINFO *pip;
  518. int isbad, initem, isdupitem, ret, t_ret;
  519. u_int32_t himark, offset; /* These would be db_indx_ts but for algnmt.*/
  520. u_int32_t i, endoff, nentries;
  521. u_int8_t *pagelayout;
  523. isbad = isdupitem = 0;
  524. nentries = 0;
  525. memset(&child, 0, sizeof(VRFY_CHILDINFO));
  526. if ((ret = __db_vrfy_getpageinfo(vdp, pgno, &pip)) != 0)
  527. return (ret);
  529. switch (TYPE(h)) {
  530. case P_IBTREE:
  531. case P_LBTREE:
  532. case P_LDUP:
  533. case P_LRECNO:
  534. break;
  535. default:
  536. /*
  537.  * In the salvager, we might call this from a page which
  538.  * we merely suspect is a btree page.  Otherwise, it
  539.  * shouldn't get called--if it is, that's a verifier bug.
  540.  */
  541. if (LF_ISSET(DB_SALVAGE))
  542. break;
  543. TYPE_ERR_PRINT(dbp->dbenv, "__bam_vrfy_inp", pgno, TYPE(h));
  544. DB_ASSERT(0);
  545. ret = EINVAL;
  546. goto err;
  547. }
  549. /*
  550.  * Loop through inp[], the array of items, until we either
  551.  * run out of entries or collide with the data.  Keep track
  552.  * of h_offset in himark.
  553.  *
  554.  * For each element in inp[i], make sure it references a region
  555.  * that starts after the end of the inp array (as defined by
  556.  * NUM_ENT(h)), ends before the beginning of the page, doesn't
  557.  * overlap any other regions, and doesn't have a gap between
  558.  * it and the region immediately after it.
  559.  */
  560. himark = dbp->pgsize;
  561. if ((ret = __os_malloc(dbp->dbenv,
  562.     dbp->pgsize, NULL, &pagelayout)) != 0)
  563. goto err;
  564. memset(pagelayout, 0, dbp->pgsize);
  565. for (i = 0; i < NUM_ENT(h); i++) {
  567. ret = __db_vrfy_inpitem(dbp,
  568.     h, pgno, i, 1, flags, &himark, &offset);
  569. if (ret == DB_VERIFY_BAD) {
  570. isbad = 1;
  571. continue;
  572. } else if (ret == DB_VERIFY_FATAL) {
  573. isbad = 1;
  574. goto err;
  575. } else if (ret != 0)
  576. DB_ASSERT(0);
  578. /*
  579.  * We now have a plausible beginning for the item, and we know
  580.  * its length is safe.
  581.  *
  582.  * Mark the beginning and end in pagelayout so we can make sure
  583.  * items have no overlaps or gaps.
  584.  */
  585. bk = GET_BKEYDATA(h, i);
  586. #define ITEM_BEGIN 1
  587. #define ITEM_END 2
  588. if (pagelayout[offset] == 0)
  589. pagelayout[offset] = ITEM_BEGIN;
  590. else if (pagelayout[offset] == ITEM_BEGIN) {
  591. /*
  592.  * Having two inp entries that point at the same patch
  593.  * of page is legal if and only if the page is
  594.  * a btree leaf and they're onpage duplicate keys--
  595.  * that is, if (i % P_INDX) == 0.
  596.  */
  597. if ((i % P_INDX == 0) && (TYPE(h) == P_LBTREE)) {
  598. /* Flag for later. */
  599. F_SET(pip, VRFY_HAS_DUPS);
  601. /* Bump up nentries so we don't undercount. */
  602. nentries++;
  604. /*
  605.  * We'll check to make sure the end is
  606.  * equal, too.
  607.  */
  608. isdupitem = 1;
  609. } else {
  610. isbad = 1;
  611. EPRINT((dbp->dbenv,
  612.     "Duplicated item %lu on page %lu",
  613.     (u_long)i, (u_long)pgno));
  614. }
  615. }
  617. /*
  618.  * Mark the end.  Its location varies with the page type
  619.  * and the item type.
  620.  *
  621.  * If the end already has a sign other than 0, do nothing--
  622.  * it's an overlap that we'll catch later.
  623.  */
  624. switch(B_TYPE(bk->type)) {
  625. case B_KEYDATA:
  626. if (TYPE(h) == P_IBTREE)
  627. /* It's a BINTERNAL. */
  628. endoff = offset + BINTERNAL_SIZE(bk->len) - 1;
  629. else
  630. endoff = offset + BKEYDATA_SIZE(bk->len) - 1;
  631. break;
  632. case B_DUPLICATE:
  633. /*
  634.  * Flag that we have dups; we'll check whether
  635.  * that's okay during the structure check.
  636.  */
  637. F_SET(pip, VRFY_HAS_DUPS);
  638. /* FALLTHROUGH */
  639. case B_OVERFLOW:
  640. /*
  641.  * Overflow entries on internal pages are stored
  642.  * as the _data_ of a BINTERNAL;  overflow entries
  643.  * on leaf pages are stored as the entire entry.
  644.  */
  645. endoff = offset +
  646.     ((TYPE(h) == P_IBTREE) ?
  647.     BINTERNAL_SIZE(BOVERFLOW_SIZE) :
  648.     BOVERFLOW_SIZE) - 1;
  649. break;
  650. default:
  651. /*
  652.  * We'll complain later;  for now, just mark
  653.  * a minimum.
  654.  */
  655. endoff = offset + BKEYDATA_SIZE(0) - 1;
  656. break;
  657. }
  659. /*
  660.  * If this is an onpage duplicate key we've seen before,
  661.  * the end had better coincide too.
  662.  */
  663. if (isdupitem && pagelayout[endoff] != ITEM_END) {
  664. EPRINT((dbp->dbenv,
  665.     "Duplicated item %lu on page %lu",
  666.     (u_long)i, (u_long)pgno));
  667. isbad = 1;
  668. } else if (pagelayout[endoff] == 0)
  669. pagelayout[endoff] = ITEM_END;
  670. isdupitem = 0;
  672. /*
  673.  * There should be no deleted items in a quiescent tree,
  674.  * except in recno.
  675.  */
  676. if (B_DISSET(bk->type) && TYPE(h) != P_LRECNO) {
  677. isbad = 1;
  678. EPRINT((dbp->dbenv,
  679.     "Item %lu on page %lu marked deleted",
  680.     (u_long)i, (u_long)pgno));
  681. }
  683. /*
  684.  * Check the type and such of bk--make sure it's reasonable
  685.  * for the pagetype.
  686.  */
  687. switch (B_TYPE(bk->type)) {
  688. case B_KEYDATA:
  689. /*
  690.  * This is a normal, non-overflow BKEYDATA or BINTERNAL.
  691.  * The only thing to check is the len, and that's
  692.  * already been done.
  693.  */
  694. break;
  695. case B_DUPLICATE:
  696. if (TYPE(h) == P_IBTREE) {
  697. isbad = 1;
  698. EPRINT((dbp->dbenv,
  699. "Duplicate page referenced by internal btree page %lu at item %lu",
  700.     (u_long)pgno, (u_long)i));
  701. break;
  702. } else if (TYPE(h) == P_LRECNO) {
  703. isbad = 1;
  704. EPRINT((dbp->dbenv,
  705. "Duplicate page referenced by recno page %lu at item %lu",
  706.     (u_long)pgno, (u_long)i));
  707. break;
  708. }
  709. /* FALLTHROUGH */
  710. case B_OVERFLOW:
  711. bo = (TYPE(h) == P_IBTREE) ?
  712.     (BOVERFLOW *)(((BINTERNAL *)bk)->data) :
  713.     (BOVERFLOW *)bk;
  715. if (B_TYPE(bk->type) == B_OVERFLOW)
  716. /* Make sure tlen is reasonable. */
  717. if (bo->tlen > dbp->pgsize * vdp->last_pgno) {
  718. isbad = 1;
  719. EPRINT((dbp->dbenv,
  720. "Impossible tlen %lu, item %lu, page %lu",
  721.     (u_long)bo->tlen, (u_long)i,
  722.     (u_long)pgno));
  723. /* Don't save as a child. */
  724. break;
  725. }
  727. if (!IS_VALID_PGNO(bo->pgno) || bo->pgno == pgno ||
  728.     bo->pgno == PGNO_INVALID) {
  729. isbad = 1;
  730. EPRINT((dbp->dbenv,
  731.     "Offpage item %lu, page %lu has bad pgno",
  732.     (u_long)i, (u_long)pgno));
  733. /* Don't save as a child. */
  734. break;
  735. }
  737. child.pgno = bo->pgno;
  738. child.type = (B_TYPE(bk->type) == B_OVERFLOW ?
  739.     V_OVERFLOW : V_DUPLICATE);
  740. child.tlen = bo->tlen;
  741. if ((ret = __db_vrfy_childput(vdp, pgno, &child)) != 0)
  742. goto err;
  743. break;
  744. default:
  745. isbad = 1;
  746. EPRINT((dbp->dbenv,
  747.     "Item %lu on page %lu of invalid type %lu",
  748.     (u_long)i, (u_long)pgno));
  749. break;
  750. }
  751. }
  753. /*
  754.  * Now, loop through and make sure the items are contiguous and
  755.  * non-overlapping.
  756.  */
  757. initem = 0;
  758. for (i = himark; i < dbp->pgsize; i++)
  759. if (initem == 0)
  760. switch (pagelayout[i]) {
  761. case 0:
  762. /* May be just for alignment. */
  763. if (i != ALIGN(i, sizeof(u_int32_t)))
  764. continue;
  766. isbad = 1;
  767. EPRINT((dbp->dbenv,
  768.     "Gap between items, page %lu offset %lu",
  769.     (u_long)pgno, (u_long)i));
  770. /* Find the end of the gap */
  771. for ( ; pagelayout[i + 1] == 0 &&
  772.     (size_t)(i + 1) < dbp->pgsize; i++)
  773. ;
  774. break;
  775. case ITEM_BEGIN:
  776. /* We've found an item. Check its alignment. */
  777. if (i != ALIGN(i, sizeof(u_int32_t))) {
  778. isbad = 1;
  779. EPRINT((dbp->dbenv,
  780.     "Offset %lu page %lu unaligned",
  781.     (u_long)i, (u_long)pgno));
  782. }
  783. initem = 1;
  784. nentries++;
  785. break;
  786. case ITEM_END:
  787. /*
  788.  * We've hit the end of an item even though
  789.  * we don't think we're in one;  must
  790.  * be an overlap.
  791.  */
  792. isbad = 1;
  793. EPRINT((dbp->dbenv,
  794.     "Overlapping items, page %lu offset %lu",
  795.     (u_long)pgno, (u_long)i));
  796. break;
  797. default:
  798. /* Should be impossible. */
  799. DB_ASSERT(0);
  800. ret = EINVAL;
  801. goto err;
  802. }
  803. else
  804. switch (pagelayout[i]) {
  805. case 0:
  806. /* In the middle of an item somewhere. Okay. */
  807. break;
  808. case ITEM_END:
  809. /* End of an item; switch to out-of-item mode.*/
  810. initem = 0;
  811. break;
  812. case ITEM_BEGIN:
  813. /*
  814.  * Hit a second item beginning without an
  815.  * end.  Overlap.
  816.  */
  817. isbad = 1;
  818. EPRINT((dbp->dbenv,
  819.     "Overlapping items, page %lu offset %lu",
  820.     (u_long)pgno, (u_long)i));
  821. break;
  822. }
  824. (void)__os_free(pagelayout, dbp->pgsize);
  826. /* Verify HOFFSET. */
  827. if ((db_indx_t)himark != HOFFSET(h)) {
  828. EPRINT((dbp->dbenv, "Bad HOFFSET %lu, appears to be %lu",
  829.     (u_long)HOFFSET(h), (u_long)himark));
  830. isbad = 1;
  831. }
  833. err: if (nentriesp != NULL)
  834. *nentriesp = nentries;
  836. if ((t_ret = __db_vrfy_putpageinfo(vdp, pip)) != 0 && ret == 0)
  837. ret = t_ret;
  839. return ((isbad == 1 && ret == 0) ? DB_VERIFY_BAD : ret);
  840. }
  842. /*
  843.  * __bam_vrfy_itemorder --
  844.  * Make sure the items on a page sort correctly.
  845.  *
  846.  * Assumes that NUM_ENT(h) and inp[0]..inp[NUM_ENT(h) - 1] are
  847.  * reasonable;  be sure that __bam_vrfy_inp has been called first.
  848.  *
  849.  * If ovflok is set, it also assumes that overflow page chains
  850.  * hanging off the current page have been sanity-checked, and so we
  851.  * can use __bam_cmp to verify their ordering.  If it is not set,
  852.  * and we run into an overflow page, carp and return DB_VERIFY_BAD;
  853.  * we shouldn't be called if any exist.
  854.  *
  855.  * PUBLIC: int __bam_vrfy_itemorder __P((DB *, VRFY_DBINFO *, PAGE *,
  856.  * PUBLIC:     db_pgno_t, u_int32_t, int, int, u_int32_t));
  857.  */
  858. int
  859. __bam_vrfy_itemorder(dbp, vdp, h, pgno, nentries, ovflok, hasdups, flags)
  860. DB *dbp;
  861. VRFY_DBINFO *vdp;
  862. PAGE *h;
  863. db_pgno_t pgno;
  864. u_int32_t nentries;
  865. int ovflok, hasdups;
  866. u_int32_t flags;
  867. {
  868. DBT dbta, dbtb, dup1, dup2, *p1, *p2, *tmp;
  869. BTREE *bt;
  870. BINTERNAL *bi;
  871. BKEYDATA *bk;
  872. BOVERFLOW *bo;
  873. VRFY_PAGEINFO *pip;
  874. db_indx_t i;
  875. int cmp, freedup1, freedup2, isbad, ret, t_ret;
  876. int (*dupfunc) __P((DB *, const DBT *, const DBT *));
  877. int (*func) __P((DB *, const DBT *, const DBT *));
  878. void *buf1, *buf2, *tmpbuf;
  880. /*
  881.  * We need to work in the ORDERCHKONLY environment where we might
  882.  * not have a pip, but we also may need to work in contexts where
  883.  * NUM_ENT isn't safe.
  884.  */
  885. if (vdp != NULL) {
  886. if ((ret = __db_vrfy_getpageinfo(vdp, pgno, &pip)) != 0)
  887. return (ret);
  888. nentries = pip->entries;
  889. } else
  890. pip = NULL;
  892. ret = isbad = 0;
  893. bo = NULL; /* Shut up compiler. */
  895. memset(&dbta, 0, sizeof(DBT));
  896. F_SET(&dbta, DB_DBT_REALLOC);
  898. memset(&dbtb, 0, sizeof(DBT));
  899. F_SET(&dbtb, DB_DBT_REALLOC);
  901. buf1 = buf2 = NULL;
  903. DB_ASSERT(!LF_ISSET(DB_NOORDERCHK));
  905. dupfunc = (dbp->dup_compare == NULL) ? __bam_defcmp : dbp->dup_compare;
  906. if (TYPE(h) == P_LDUP)
  907. func = dupfunc;
  908. else {
  909. func = __bam_defcmp;
  910. if (dbp->bt_internal != NULL) {
  911. bt = (BTREE *)dbp->bt_internal;
  912. if (bt->bt_compare != NULL)
  913. func = bt->bt_compare;
  914. }
  915. }
  917. /*
  918.  * We alternate our use of dbta and dbtb so that we can walk
  919.  * through the page key-by-key without copying a dbt twice.
  920.  * p1 is always the dbt for index i - 1, and p2 for index i.
  921.  */
  922. p1 = &dbta;
  923. p2 = &dbtb;
  925. /*
  926.  * Loop through the entries.  nentries ought to contain the
  927.  * actual count, and so is a safe way to terminate the loop;  whether
  928.  * we inc. by one or two depends on whether we're a leaf page--
  929.  * on a leaf page, we care only about keys.  On internal pages
  930.  * and LDUP pages, we want to check the order of all entries.
  931.  *
  932.  * Note that on IBTREE pages, we start with item 1, since item
  933.  * 0 doesn't get looked at by __bam_cmp.
  934.  */
  935. for (i = (TYPE(h) == P_IBTREE) ? 1 : 0; i < nentries;
  936.     i += (TYPE(h) == P_LBTREE) ? P_INDX : O_INDX) {
  937. /*
  938.  * Put key i-1, now in p2, into p1, by swapping DBTs and bufs.
  939.  */
  940. tmp = p1;
  941. p1 = p2;
  942. p2 = tmp;
  943. tmpbuf = buf1;
  944. buf1 = buf2;
  945. buf2 = tmpbuf;
  947. /*
  948.  * Get key i into p2.
  949.  */
  950. switch (TYPE(h)) {
  951. case P_IBTREE:
  952. bi = GET_BINTERNAL(h, i);
  953. if (B_TYPE(bi->type) == B_OVERFLOW) {
  954. bo = (BOVERFLOW *)(bi->data);
  955. goto overflow;
  956. } else {
  957. p2->data = bi->data;
  958. p2->size = bi->len;
  959. }
  961. /*
  962.  * The leftmost key on an internal page must be
  963.  * len 0, since it's just a placeholder and
  964.  * automatically sorts less than all keys.
  965.  *
  966.  * XXX
  967.  * This criterion does not currently hold!
  968.  * See todo list item #1686.  Meanwhile, it's harmless
  969.  * to just not check for it.
  970.  */
  971. #if 0
  972. if (i == 0 && bi->len != 0) {
  973. isbad = 1;
  974. EPRINT((dbp->dbenv,
  975. "Lowest key on internal page %lu of nonzero length",
  976.     (u_long)pgno));
  977. }
  978. #endif
  979. break;
  980. case P_LBTREE:
  981. case P_LDUP:
  982. bk = GET_BKEYDATA(h, i);
  983. if (B_TYPE(bk->type) == B_OVERFLOW) {
  984. bo = (BOVERFLOW *)bk;
  985. goto overflow;
  986. } else {
  987. p2->data = bk->data;
  988. p2->size = bk->len;
  989. }
  990. break;
  991. default:
  992. /*
  993.  * This means our caller screwed up and sent us
  994.  * an inappropriate page.
  995.  */
  996. TYPE_ERR_PRINT(dbp->dbenv,
  997.     "__bam_vrfy_itemorder", pgno, TYPE(h))
  998. DB_ASSERT(0);
  999. ret = EINVAL;
  1000. goto err;
  1001. }
  1003. if (0) {
  1004. /*
  1005.  * If ovflok != 1, we can't safely go chasing
  1006.  * overflow pages with the normal routines now;
  1007.  * they might be unsafe or nonexistent.  Mark this
  1008.  * page as incomplete and return.
  1009.  *
  1010.  * Note that we don't need to worry about freeing
  1011.  * buffers, since they can't have been allocated
  1012.  * if overflow items are unsafe.
  1013.  */
  1014. overflow: if (!ovflok) {
  1015. F_SET(pip, VRFY_INCOMPLETE);
  1016. goto err;
  1017. }
  1019. /*
  1020.  * Overflow items are safe to chase.  Do so.
  1021.  * Fetch the overflow item into p2->data,
  1022.  * NULLing it or reallocing it as appropriate.
  1023.  *
  1024.  * (We set p2->data to buf2 before the call
  1025.  * so we're sure to realloc if we can and if p2
  1026.  * was just pointing at a non-overflow item.)
  1027.  */
  1028. p2->data = buf2;
  1029. if ((ret = __db_goff(dbp,
  1030.     p2, bo->tlen, bo->pgno, NULL, NULL)) != 0) {
  1031. isbad = 1;
  1032. EPRINT((dbp->dbenv,
  1033.     "Error %lu in fetching overflow item %lu, page %lu",
  1034.     (u_long)ret, (u_long)i, (u_long)pgno));
  1035. }
  1036. /* In case it got realloc'ed and thus changed. */
  1037. buf2 = p2->data;
  1038. }
  1040. /* Compare with the last key. */
  1041. if (p1->data != NULL && p2->data != NULL) {
  1042. cmp = func(dbp, p1, p2);
  1044. /* comparison succeeded */
  1045. if (cmp > 0) {
  1046. isbad = 1;
  1047. EPRINT((dbp->dbenv,
  1048.     "Out-of-order key, page %lu item %lu",
  1049.     (u_long)pgno, (u_long)i));
  1050. /* proceed */
  1051. } else if (cmp == 0) {
  1052. /*
  1053.  * If they compared equally, this
  1054.  * had better be a (sub)database with dups.
  1055.  * Mark it so we can check during the
  1056.  * structure check.
  1057.  */
  1058. if (pip != NULL)
  1059. F_SET(pip, VRFY_HAS_DUPS);
  1060. else if (hasdups == 0) {
  1061. isbad = 1;
  1062. EPRINT((dbp->dbenv,
  1063. "Database with no duplicates has duplicated keys on page %lu",
  1064.     (u_long)pgno));
  1065. }
  1067. /*
  1068.  * If we're a btree leaf, check to see
  1069.  * if the data items of these on-page dups are
  1070.  * in sorted order.  If not, flag this, so
  1071.  * that we can make sure during the
  1072.  * structure checks that the DUPSORT flag
  1073.  * is unset.
  1074.  *
  1075.  * At this point i points to a duplicate key.
  1076.  * Compare the datum before it (same key)
  1077.  * to the datum after it, i.e. i-1 to i+1.
  1078.  */
  1079. if (TYPE(h) == P_LBTREE) {
  1080. /*
  1081.  * Unsafe;  continue and we'll pick
  1082.  * up the bogus nentries later.
  1083.  */
  1084. if (i + 1 >= (db_indx_t)nentries)
  1085. continue;
  1087. /*
  1088.  * We don't bother with clever memory
  1089.  * management with on-page dups,
  1090.  * as it's only really a big win
  1091.  * in the overflow case, and overflow
  1092.  * dups are probably (?) rare.
  1093.  */
  1094. if (((ret = __bam_safe_getdata(dbp,
  1095.     h, i - 1, ovflok, &dup1,
  1096.     &freedup1)) != 0) ||
  1097.     ((ret = __bam_safe_getdata(dbp,
  1098.     h, i + 1, ovflok, &dup2,
  1099.     &freedup2)) != 0))
  1100. goto err;
  1102. /*
  1103.  * If either of the data are NULL,
  1104.  * it's because they're overflows and
  1105.  * it's not safe to chase them now.
  1106.  * Mark an incomplete and return.
  1107.  */
  1108. if (dup1.data == NULL ||
  1109.     dup2.data == NULL) {
  1110. DB_ASSERT(!ovflok);
  1111. F_SET(pip, VRFY_INCOMPLETE);
  1112. goto err;
  1113. }
  1115. /*
  1116.  * If the dups are out of order,
  1117.  * flag this.  It's not an error
  1118.  * until we do the structure check
  1119.  * and see whether DUPSORT is set.
  1120.  */
  1121. if (dupfunc(dbp, &dup1, &dup2) > 0)
  1122. F_SET(pip, VRFY_DUPS_UNSORTED);
  1124. if (freedup1)
  1125. __os_free(dup1.data, 0);
  1126. if (freedup2)
  1127. __os_free(dup2.data, 0);
  1128. }
  1129. }
  1130. }
  1131. }
  1133. err: if (pip != NULL &&
  1134.     ((t_ret = __db_vrfy_putpageinfo(vdp, pip)) != 0) && ret == 0)
  1135. ret = t_ret;
  1137. if (buf1 != NULL)
  1138. __os_free(buf1, 0);
  1139. if (buf2 != NULL)
  1140. __os_free(buf2, 0);
  1142. return ((ret == 0 && isbad == 1) ? DB_VERIFY_BAD : ret);
  1143. }
  1145. /*
  1146.  * __bam_vrfy_structure --
  1147.  * Verify the tree structure of a btree database (including the master
  1148.  * database containing subdbs).
  1149.  *
  1150.  * PUBLIC: int __bam_vrfy_structure __P((DB *, VRFY_DBINFO *, db_pgno_t,
  1151.  * PUBLIC:     u_int32_t));
  1152.  */
  1153. int
  1154. __bam_vrfy_structure(dbp, vdp, meta_pgno, flags)
  1155. DB *dbp;
  1156. VRFY_DBINFO *vdp;
  1157. db_pgno_t meta_pgno;
  1158. u_int32_t flags;
  1159. {
  1160. DB *pgset;
  1161. VRFY_PAGEINFO *mip, *rip;
  1162. db_pgno_t root, p;
  1163. int t_ret, ret;
  1164. u_int32_t nrecs, level, relen, stflags;
  1166. mip = rip = 0;
  1167. pgset = vdp->pgset;
  1169. if ((ret = __db_vrfy_getpageinfo(vdp, meta_pgno, &mip)) != 0)
  1170. return (ret);
  1172. if ((ret = __db_vrfy_pgset_get(pgset, meta_pgno, (int *)&p)) != 0)
  1173. goto err;
  1174. if (p != 0) {
  1175. EPRINT((dbp->dbenv,
  1176.     "Btree metadata page number %lu observed twice",
  1177.     (u_long)meta_pgno));
  1178. ret = DB_VERIFY_BAD;
  1179. goto err;
  1180. }
  1181. if ((ret = __db_vrfy_pgset_inc(pgset, meta_pgno)) != 0)
  1182. goto err;
  1184. root = mip->root;
  1186. if (root == 0) {
  1187. EPRINT((dbp->dbenv,
  1188.     "Btree metadata page %lu has no root", (u_long)meta_pgno));
  1189. ret = DB_VERIFY_BAD;
  1190. goto err;
  1191. }
  1193. if ((ret = __db_vrfy_getpageinfo(vdp, root, &rip)) != 0)
  1194. goto err;
  1196. switch (rip->type) {
  1197. case P_IBTREE:
  1198. case P_LBTREE:
  1199. stflags = flags | ST_TOPLEVEL;
  1200. if (F_ISSET(mip, VRFY_HAS_DUPS))
  1201. stflags |= ST_DUPOK;
  1202. if (F_ISSET(mip, VRFY_HAS_DUPSORT))
  1203. stflags |= ST_DUPSORT;
  1204. if (F_ISSET(mip, VRFY_HAS_RECNUMS))
  1205. stflags |= ST_RECNUM;
  1206. ret = __bam_vrfy_subtree(dbp,
  1207.     vdp, root, NULL, NULL, stflags, NULL, NULL, NULL);
  1208. break;
  1209. case P_IRECNO:
  1210. case P_LRECNO:
  1211. stflags = flags | ST_RECNUM | ST_IS_RECNO | ST_TOPLEVEL;
  1212. if (mip->re_len > 0)
  1213. stflags |= ST_RELEN;
  1214. if ((ret = __bam_vrfy_subtree(dbp, vdp,
  1215.     root, NULL, NULL, stflags, &level, &nrecs, &relen)) != 0)
  1216. goto err;
  1217. /*
  1218.  * Even if mip->re_len > 0, re_len may come back zero if the
  1219.  * tree is empty.  It should be okay to just skip the check in
  1220.  * this case, as if there are any non-deleted keys at all,
  1221.  * that should never happen.
  1222.  */
  1223. if (mip->re_len > 0 && relen > 0 && mip->re_len != relen) {
  1224. EPRINT((dbp->dbenv,
  1225.  "Recno database with meta page %lu has bad re_len %lu",
  1226.     (u_long)meta_pgno, (u_long)relen));
  1227. ret = DB_VERIFY_BAD;
  1228. goto err;
  1229. }
  1230. ret = 0;
  1231. break;
  1232. case P_LDUP:
  1233. EPRINT((dbp->dbenv,
  1234.     "Duplicate tree referenced from metadata page %lu",
  1235.     (u_long)meta_pgno));
  1236. ret = DB_VERIFY_BAD;
  1237. break;
  1238. default:
  1239. EPRINT((dbp->dbenv,
  1240.     "Btree root of incorrect type %lu on meta page %lu",
  1241.     (u_long)rip->type, (u_long)meta_pgno));
  1242. ret = DB_VERIFY_BAD;
  1243. break;
  1244. }
  1246. err: if (mip != NULL &&
  1247.     ((t_ret = __db_vrfy_putpageinfo(vdp, mip)) != 0) && ret == 0)
  1248. t_ret = ret;
  1249. if (rip != NULL &&
  1250.     ((t_ret = __db_vrfy_putpageinfo(vdp, rip)) != 0) && ret == 0)
  1251. t_ret = ret;
  1252. return (ret);
  1253. }
  1255. /*
  1256.  * __bam_vrfy_subtree--
  1257.  * Verify a subtree (or entire) btree with specified root.
  1258.  *
  1259.  * Note that this is public because it must be called to verify
  1260.  * offpage dup trees, including from hash.
  1261.  *
  1262.  * PUBLIC: int __bam_vrfy_subtree __P((DB *, VRFY_DBINFO *, db_pgno_t, void *,
  1263.  * PUBLIC:     void *, u_int32_t, u_int32_t *, u_int32_t *, u_int32_t *));
  1264.  */
  1265. int
  1266. __bam_vrfy_subtree(dbp,
  1267.     vdp, pgno, l, r, flags, levelp, nrecsp, relenp)
  1268. DB *dbp;
  1269. VRFY_DBINFO *vdp;
  1270. db_pgno_t pgno;
  1271. void *l, *r;
  1272. u_int32_t flags, *levelp, *nrecsp, *relenp;
  1273. {
  1274. BINTERNAL *li, *ri, *lp, *rp;
  1275. DB *pgset;
  1276. DBC *cc;
  1277. PAGE *h;
  1278. VRFY_CHILDINFO *child;
  1279. VRFY_PAGEINFO *pip;
  1280. db_recno_t nrecs, child_nrecs;
  1281. db_indx_t i;
  1282. int ret, t_ret, isbad, toplevel, p;
  1283. int (*func) __P((DB *, const DBT *, const DBT *));
  1284. u_int32_t level, child_level, stflags, child_relen, relen;
  1286. ret = isbad = 0;
  1287. nrecs = 0;
  1288. h = NULL;
  1289. relen = 0;
  1290. rp = (BINTERNAL *)r;
  1291. lp = (BINTERNAL *)l;
  1293. /* Provide feedback on our progress to the application. */
  1294. if (!LF_ISSET(DB_SALVAGE))
  1295. __db_vrfy_struct_feedback(dbp, vdp);
  1297. if ((ret = __db_vrfy_getpageinfo(vdp, pgno, &pip)) != 0)
  1298. return (ret);
  1300. cc = NULL;
  1301. level = pip->bt_level;
  1303. toplevel = LF_ISSET(ST_TOPLEVEL);
  1304. LF_CLR(ST_TOPLEVEL);
  1306. /*
  1307.  * We are recursively descending a btree, starting from the root
  1308.  * and working our way out to the leaves.
  1309.  *
  1310.  * There are four cases we need to deal with:
  1311.  * 1. pgno is a recno leaf page.  Any children are overflows.
  1312.  * 2. pgno is a duplicate leaf page.  Any children
  1313.  *    are overflow pages;  traverse them, and then return
  1314.  *    level and nrecs.
  1315.  * 3. pgno is an ordinary leaf page.  Check whether dups are
  1316.  *    allowed, and if so, traverse any off-page dups or
  1317.  *    overflows.  Then return nrecs and level.
  1318.  * 4. pgno is a recno internal page.  Recursively check any
  1319.  *    child pages, making sure their levels are one lower
  1320.  *    and their nrecs sum to ours.
  1321.  * 5. pgno is a btree internal page.  Same as #4, plus we
  1322.  *    must verify that for each pair of BINTERNAL entries
  1323.  *    N and N+1, the leftmost item on N's child sorts
  1324.  *    greater than N, and the rightmost item on N's child
  1325.  *    sorts less than N+1.
  1326.  *
  1327.  * Furthermore, in any sorted page type (P_LDUP, P_LBTREE, P_IBTREE),
  1328.  * we need to verify the internal sort order is correct if,
  1329.  * due to overflow items, we were not able to do so earlier.
  1330.  */
  1331. switch (pip->type) {
  1332. case P_LRECNO:
  1333. case P_LDUP:
  1334. case P_LBTREE:
  1335. /*
  1336.  * Cases 1, 2 and 3 (overflow pages are common to all three);
  1337.  * traverse child list, looking for overflows.
  1338.  */
  1339. if ((ret = __db_vrfy_childcursor(vdp, &cc)) != 0)
  1340. goto err;
  1341. for (ret = __db_vrfy_ccset(cc, pgno, &child); ret == 0;
  1342.     ret = __db_vrfy_ccnext(cc, &child))
  1343. if (child->type == V_OVERFLOW &&
  1344.     (ret = __db_vrfy_ovfl_structure(dbp, vdp,
  1345.     child->pgno, child->tlen,
  1346.     flags | ST_OVFL_LEAF)) != 0) {
  1347. if (ret == DB_VERIFY_BAD)
  1348. isbad = 1;
  1349. else
  1350. goto done;
  1351. }
  1353. if ((ret = __db_vrfy_ccclose(cc)) != 0)
  1354. goto err;
  1355. cc = NULL;
  1357. /* Case 1 */
  1358. if (pip->type == P_LRECNO) {
  1359. if (!LF_ISSET(ST_IS_RECNO) &&
  1360.     !(LF_ISSET(ST_DUPOK) && !LF_ISSET(ST_DUPSORT))) {
  1361. isbad = 1;
  1362. EPRINT((dbp->dbenv,
  1363.     "Recno leaf page %lu in non-recno tree",
  1364.     (u_long)pgno));
  1365. goto done;
  1366. }
  1367. goto leaf;
  1368. } else if (LF_ISSET(ST_IS_RECNO)) {
  1369. /*
  1370.  * It's a non-recno leaf.  Had better not be a recno
  1371.  * subtree.
  1372.  */
  1373. isbad = 1;
  1374. EPRINT((dbp->dbenv,
  1375.     "Non-recno leaf page %lu in recno tree",
  1376.     (u_long)pgno));
  1377. goto done;
  1378. }
  1380. /* Case 2--no more work. */
  1381. if (pip->type == P_LDUP)
  1382. goto leaf;
  1384. /* Case 3 */
  1386. /* Check if we have any dups. */
  1387. if (F_ISSET(pip, VRFY_HAS_DUPS)) {
  1388. /* If dups aren't allowed in this btree, trouble. */
  1389. if (!LF_ISSET(ST_DUPOK)) {
  1390. isbad = 1;
  1391. EPRINT((dbp->dbenv,
  1392.     "Duplicates on page %lu in non-dup btree",
  1393.     (u_long)pgno));
  1394. } else {
  1395. /*
  1396.  * We correctly have dups.  If any are off-page,
  1397.  * traverse those btrees recursively.
  1398.  */
  1399. if ((ret =
  1400.     __db_vrfy_childcursor(vdp, &cc)) != 0)
  1401. goto err;
  1402. for (ret = __db_vrfy_ccset(cc, pgno, &child);
  1403.     ret == 0;
  1404.     ret = __db_vrfy_ccnext(cc, &child)) {
  1405. stflags = flags | ST_RECNUM | ST_DUPSET;
  1406. /* Skip any overflow entries. */
  1407. if (child->type == V_DUPLICATE) {
  1408. if ((ret = __db_vrfy_duptype(
  1409.     dbp, vdp, child->pgno,
  1410.     stflags)) != 0) {
  1411. isbad = 1;
  1412. /* Next child. */
  1413. continue;
  1414. }
  1415. if ((ret = __bam_vrfy_subtree(
  1416.     dbp, vdp, child->pgno, NULL,
  1417.     NULL, stflags, NULL, NULL,
  1418.     NULL)) != 0) {
  1419. if (ret !=
  1420.     DB_VERIFY_BAD)
  1421. goto err;
  1422. else
  1423. isbad = 1;
  1424. }
  1425. }
  1426. }
  1428. if ((ret = __db_vrfy_ccclose(cc)) != 0)
  1429. goto err;
  1430. cc = NULL;
  1432. /*
  1433.  * If VRFY_DUPS_UNSORTED is set,
  1434.  * ST_DUPSORT had better not be.
  1435.  */
  1436. if (F_ISSET(pip, VRFY_DUPS_UNSORTED) &&
  1437.     LF_ISSET(ST_DUPSORT)) {
  1438. EPRINT((dbp->dbenv,
  1439.     "Unsorted duplicate set at page %lu in sorted-dup database",
  1440.     (u_long)pgno));
  1441. isbad = 1;
  1442. }
  1443. }
  1444. }
  1445. goto leaf;
  1446. break;
  1447. case P_IBTREE:
  1448. case P_IRECNO:
  1449. /* We handle these below. */
  1450. break;
  1451. default:
  1452. /*
  1453.  * If a P_IBTREE or P_IRECNO contains a reference to an
  1454.  * invalid page, we'll wind up here;  handle it gracefully.
  1455.  * Note that the code at the "done" label assumes that the
  1456.  * current page is a btree/recno one of some sort;  this
  1457.  * is not the case here, so we goto err.
  1458.  */
  1459. EPRINT((dbp->dbenv,
  1460.     "Page %lu is of inappropriate type %lu",
  1461.     (u_long)pgno, (u_long)pip->type));
  1462. ret = DB_VERIFY_BAD;
  1463. goto err;
  1464. }
  1466. /*
  1467.  * Cases 4 & 5: This is a btree or recno internal page.  For each child,
  1468.  * recurse, keeping a running count of nrecs and making sure the level
  1469.  * is always reasonable.
  1470.  */
  1471. if ((ret = __db_vrfy_childcursor(vdp, &cc)) != 0)
  1472. goto err;
  1473. for (ret = __db_vrfy_ccset(cc, pgno, &child); ret == 0;
  1474.     ret = __db_vrfy_ccnext(cc, &child))
  1475. if (child->type == V_RECNO) {
  1476. if (pip->type != P_IRECNO) {
  1477. TYPE_ERR_PRINT(dbp->dbenv, "__bam_vrfy_subtree",
  1478.     pgno, pip->type);
  1479. DB_ASSERT(0);
  1480. ret = EINVAL;
  1481. goto err;
  1482. }
  1483. if ((ret = __bam_vrfy_subtree(dbp, vdp, child->pgno,
  1484.     NULL, NULL, flags, &child_level, &child_nrecs,
  1485.     &child_relen)) != 0) {
  1486. if (ret != DB_VERIFY_BAD)
  1487. goto done;
  1488. else
  1489. isbad = 1;
  1490. }
  1492. if (LF_ISSET(ST_RELEN)) {
  1493. if (relen == 0)
  1494. relen = child_relen;
  1495. /*
  1496.  * child_relen may be zero if the child subtree
  1497.  * is empty.
  1498.  */
  1499. else if (child_relen > 0 &&
  1500.     relen != child_relen) {
  1501. isbad = 1;
  1502. EPRINT((dbp->dbenv,
  1503.    "Recno page %lu returned bad re_len",
  1504.     (u_long)child->pgno));
  1505. }
  1506. if (relenp)
  1507. *relenp = relen;
  1508. }
  1509. if (LF_ISSET(ST_RECNUM))
  1510. nrecs += child_nrecs;
  1511. if (level != child_level + 1) {
  1512. isbad = 1;
  1513. EPRINT((dbp->dbenv, "%s%lu%s%lu%s%lu",
  1514.     "Recno level incorrect on page ",
  1515.     (u_long)child->pgno, ": got ",
  1516.     (u_long)child_level, ", expected ",
  1517.     (u_long)(level - 1)));
  1518. }
  1519. } else if (child->type == V_OVERFLOW &&
  1520.     (ret = __db_vrfy_ovfl_structure(dbp, vdp,
  1521.     child->pgno, child->tlen, flags)) != 0) {
  1522. if (ret == DB_VERIFY_BAD)
  1523. isbad = 1;
  1524. else
  1525. goto done;
  1526. }
  1528. if ((ret = __db_vrfy_ccclose(cc)) != 0)
  1529. goto err;
  1530. cc = NULL;
  1532. /* We're done with case 4. */
  1533. if (pip->type == P_IRECNO)
  1534. goto done;
  1536. /*
  1537.  * Case 5.  Btree internal pages.
  1538.  * As described above, we need to iterate through all the
  1539.  * items on the page and make sure that our children sort appropriately
  1540.  * with respect to them.
  1541.  *
  1542.  * For each entry, li will be the "left-hand" key for the entry
  1543.  * itself, which must sort lower than all entries on its child;
  1544.  * ri will be the key to its right, which must sort greater.
  1545.  */
  1546. if (h == NULL && (ret = memp_fget(dbp->mpf, &pgno, 0, &h)) != 0)
  1547. goto err;
  1548. for (i = 0; i < pip->entries; i += O_INDX) {
  1549. li = GET_BINTERNAL(h, i);
  1550. ri = (i + O_INDX < pip->entries) ?
  1551.     GET_BINTERNAL(h, i + O_INDX) : NULL;
  1553. /*
  1554.  * The leftmost key is forcibly sorted less than all entries,
  1555.  * so don't bother passing it.
  1556.  */
  1557. if ((ret = __bam_vrfy_subtree(dbp, vdp, li->pgno,
  1558.     i == 0 ? NULL : li, ri, flags, &child_level,
  1559.     &child_nrecs, NULL)) != 0) {
  1560. if (ret != DB_VERIFY_BAD)
  1561. goto done;
  1562. else
  1563. isbad = 1;
  1564. }
  1566. if (LF_ISSET(ST_RECNUM)) {
  1567. /*
  1568.  * Keep a running tally on the actual record count so
  1569.  * we can return it to our parent (if we have one) or
  1570.  * compare it to the NRECS field if we're a root page.
  1571.  */
  1572. nrecs += child_nrecs;
  1574. /*
  1575.  * Make sure the actual record count of the child
  1576.  * is equal to the value in the BINTERNAL structure.
  1577.  */
  1578. if (li->nrecs != child_nrecs) {
  1579. isbad = 1;
  1580. EPRINT((dbp->dbenv,
  1581. "Item %lu page %lu has incorrect record count of %lu, should be %lu",
  1582.     (u_long)i, (u_long)pgno, (u_long)li->nrecs,
  1583.     (u_long)child_nrecs));
  1584. }
  1585. }
  1587. if (level != child_level + 1) {
  1588. isbad = 1;
  1589. EPRINT((dbp->dbenv, "%s%lu%s%lu%s%lu",
  1590.     "Btree level incorrect on page ", (u_long)li->pgno,
  1591.     ": got ", (u_long)child_level, ", expected ",
  1592.     (u_long)(level - 1)));
  1593. }
  1594. }
  1596. if (0) {
  1597. leaf: level = LEAFLEVEL;
  1598. if (LF_ISSET(ST_RECNUM))
  1599. nrecs = pip->rec_cnt;
  1601. /* XXX
  1602.  * We should verify that the record count on a leaf page
  1603.  * is the sum of the number of keys and the number of
  1604.  * records in its off-page dups.  This requires looking
  1605.  * at the page again, however, and it may all be changing
  1606.  * soon, so for now we don't bother.
  1607.  */
  1609. if (LF_ISSET(ST_RELEN) && relenp)
  1610. *relenp = pip->re_len;
  1611. }
  1612. done: if (F_ISSET(pip, VRFY_INCOMPLETE) && isbad == 0 && ret == 0) {
  1613. /*
  1614.  * During the page-by-page pass, item order verification was
  1615.  * not finished due to the presence of overflow items.  If
  1616.  * isbad == 0, though, it's now safe to do so, as we've
  1617.  * traversed any child overflow pages.  Do it.
  1618.  */
  1619. if (h == NULL && (ret = memp_fget(dbp->mpf, &pgno, 0, &h)) != 0)
  1620. goto err;
  1621. if ((ret = __bam_vrfy_itemorder(dbp,
  1622.     vdp, h, pgno, 0, 1, 0, flags)) != 0)
  1623. goto err;
  1624. F_CLR(pip, VRFY_INCOMPLETE);
  1625. }
  1627. /*
  1628.  * Our parent has sent us BINTERNAL pointers to parent records
  1629.  * so that we can verify our place with respect to them.  If it's
  1630.  * appropriate--we have a default sort function--verify this.
  1631.  */
  1632. if (isbad == 0 && ret == 0 && !LF_ISSET(DB_NOORDERCHK) && lp != NULL) {
  1633. if (h == NULL && (ret = memp_fget(dbp->mpf, &pgno, 0, &h)) != 0)
  1634. goto err;
  1636. /*
  1637.  * __bam_vrfy_treeorder needs to know what comparison function
  1638.  * to use.  If ST_DUPSET is set, we're in a duplicate tree
  1639.  * and we use the duplicate comparison function;  otherwise,
  1640.  * use the btree one.  If unset, use the default, of course.
  1641.  */
  1642. func = LF_ISSET(ST_DUPSET) ? dbp->dup_compare :
  1643.     ((BTREE *)dbp->bt_internal)->bt_compare;
  1644. if (func == NULL)
  1645. func = __bam_defcmp;
  1647. if ((ret = __bam_vrfy_treeorder(
  1648.     dbp, pgno, h, lp, rp, func, flags)) != 0) {
  1649. if (ret == DB_VERIFY_BAD)
  1650. isbad = 1;
  1651. else
  1652. goto err;
  1653. }
  1654. }
  1656. /*
  1657.  * This is guaranteed to succeed for leaf pages, but no harm done.
  1658.  *
  1659.  * Internal pages below the top level do not store their own
  1660.  * record numbers, so we skip them.
  1661.  */
  1662. if (LF_ISSET(ST_RECNUM) && nrecs != pip->rec_cnt && toplevel) {
  1663. isbad = 1;
  1664. EPRINT((dbp->dbenv,
  1665.     "Bad record count on page %lu: got %lu, expected %lu",
  1666.     (u_long)pgno, (u_long)nrecs, (u_long)pip->rec_cnt));
  1667. }
  1669. if (levelp)
  1670. *levelp = level;
  1671. if (nrecsp)
  1672. *nrecsp = nrecs;
  1674. pgset = vdp->pgset;
  1675. if ((ret = __db_vrfy_pgset_get(pgset, pgno, &p)) != 0)
  1676. goto err;
  1677. if (p != 0) {
  1678. isbad = 1;
  1679. EPRINT((dbp->dbenv, "Page %lu linked twice", (u_long)pgno));
  1680. } else if ((ret = __db_vrfy_pgset_inc(pgset, pgno)) != 0)
  1681. goto err;
  1683. err: if (h != NULL && (t_ret = memp_fput(dbp->mpf, h, 0)) != 0 && ret == 0)
  1684. ret = t_ret;
  1685. if ((t_ret = __db_vrfy_putpageinfo(vdp, pip)) != 0 && ret == 0)
  1686. ret = t_ret;
  1687. if (cc != NULL && ((t_ret = __db_vrfy_ccclose(cc)) != 0) && ret == 0)
  1688. ret = t_ret;
  1689. return ((ret == 0 && isbad == 1) ? DB_VERIFY_BAD : ret);
  1690. }
  1692. /*
  1693.  * __bam_vrfy_treeorder --
  1694.  * Verify that the lowest key on a page sorts greater than the
  1695.  * BINTERNAL which points to it (lp), and the highest key
  1696.  * sorts less than the BINTERNAL above that (rp).
  1697.  *
  1698.  * If lp is NULL, this means that it was the leftmost key on the
  1699.  * parent, which (regardless of sort function) sorts less than
  1700.  * all keys.  No need to check it.
  1701.  *
  1702.  * If rp is NULL, lp was the highest key on the parent, so there's
  1703.  * no higher key we must sort less than.
  1704.  */
  1705. static int
  1706. __bam_vrfy_treeorder(dbp, pgno, h, lp, rp, func, flags)
  1707. DB *dbp;
  1708. db_pgno_t pgno;
  1709. PAGE *h;
  1710. BINTERNAL *lp, *rp;
  1711. int (*func) __P((DB *, const DBT *, const DBT *));
  1712. u_int32_t flags;
  1713. {
  1714. BOVERFLOW *bo;
  1715. DBT dbt;
  1716. db_indx_t last;
  1717. int ret, cmp;
  1719. memset(&dbt, 0, sizeof(DBT));
  1720. F_SET(&dbt, DB_DBT_MALLOC);
  1721. ret = 0;
  1723. switch (TYPE(h)) {
  1724. case P_IBTREE:
  1725. case P_LDUP:
  1726. last = NUM_ENT(h) - O_INDX;
  1727. break;
  1728. case P_LBTREE:
  1729. last = NUM_ENT(h) - P_INDX;
  1730. break;
  1731. default:
  1732. TYPE_ERR_PRINT(dbp->dbenv,
  1733.     "__bam_vrfy_treeorder", pgno, TYPE(h));
  1734. DB_ASSERT(0);
  1735. return (EINVAL);
  1736. }
  1738. /*
  1739.  * The key on page h, the child page, is more likely to be
  1740.  * an overflow page, so we pass its offset, rather than lp/rp's,
  1741.  * into __bam_cmp.  This will take advantage of __db_moff.
  1742.  */
  1744. /*
  1745.  * Skip first-item check if we're an internal page--the first
  1746.  * entry on an internal page is treated specially by __bam_cmp,
  1747.  * so what's on the page shouldn't matter.  (Plus, since we're passing
  1748.  * our page and item 0 as to __bam_cmp, we'll sort before our
  1749.  * parent and falsely report a failure.)
  1750.  */
  1751. if (lp != NULL && TYPE(h) != P_IBTREE) {
  1752. if (lp->type == B_KEYDATA) {
  1753. dbt.data = lp->data;
  1754. dbt.size = lp->len;
  1755. } else if (lp->type == B_OVERFLOW) {
  1756. bo = (BOVERFLOW *)lp->data;
  1757. if ((ret = __db_goff(dbp, &dbt, bo->tlen, bo->pgno,
  1758.     NULL, NULL)) != 0)
  1759. return (ret);
  1760. } else {
  1761. DB_ASSERT(0);
  1762. EPRINT((dbp->dbenv,
  1763.     "Unknown type for internal record"));
  1764. return (EINVAL);
  1765. }
  1767. /* On error, fall through, free if neeeded, and return. */
  1768. if ((ret = __bam_cmp(dbp, &dbt, h, 0, func, &cmp)) == 0) {
  1769. if (cmp > 0) {
  1770. EPRINT((dbp->dbenv,
  1771.     "First item on page %lu sorted greater than parent entry",
  1772.     (u_long)PGNO(h)));
  1773. ret = DB_VERIFY_BAD;
  1774. }
  1775. } else
  1776. EPRINT((dbp->dbenv,
  1777.     "First item on page %lu had comparison error",
  1778.     (u_long)PGNO(h)));
  1780. if (dbt.data != lp->data)
  1781. __os_free(dbt.data, 0);
  1782. if (ret != 0)
  1783. return (ret);
  1784. }
  1786. if (rp != NULL) {
  1787. if (rp->type == B_KEYDATA) {
  1788. dbt.data = rp->data;
  1789. dbt.size = rp->len;
  1790. } else if (rp->type == B_OVERFLOW) {
  1791. bo = (BOVERFLOW *)rp->data;
  1792. if ((ret = __db_goff(dbp, &dbt, bo->tlen, bo->pgno,
  1793.     NULL, NULL)) != 0)
  1794. return (ret);
  1795. } else {
  1796. DB_ASSERT(0);
  1797. EPRINT((dbp->dbenv,
  1798.     "Unknown type for internal record"));
  1799. return (EINVAL);
  1800. }
  1802. /* On error, fall through, free if neeeded, and return. */
  1803. if ((ret = __bam_cmp(dbp, &dbt, h, last, func, &cmp)) == 0) {
  1804. if (cmp < 0) {
  1805. EPRINT((dbp->dbenv,
  1806.     "Last item on page %lu sorted greater than parent entry",
  1807.     (u_long)PGNO(h)));
  1808. ret = DB_VERIFY_BAD;
  1809. }
  1810. } else
  1811. EPRINT((dbp->dbenv,
  1812.     "Last item on page %lu had comparison error",
  1813.     (u_long)PGNO(h)));
  1815. if (dbt.data != rp->data)
  1816. __os_free(dbt.data, 0);
  1817. }
  1819. return (ret);
  1820. }
  1822. /*
  1823.  * __bam_salvage --
  1824.  * Safely dump out anything that looks like a key on an alleged
  1825.  * btree leaf page.
  1826.  *
  1827.  * PUBLIC: int __bam_salvage __P((DB *, VRFY_DBINFO *, db_pgno_t, u_int32_t,
  1828.  * PUBLIC:     PAGE *, void *, int (*)(void *, const void *), DBT *,
  1829.  * PUBLIC:     u_int32_t));
  1830.  */
  1831. int
  1832. __bam_salvage(dbp, vdp, pgno, pgtype, h, handle, callback, key, flags)
  1833. DB *dbp;
  1834. VRFY_DBINFO *vdp;
  1835. db_pgno_t pgno;
  1836. u_int32_t pgtype;
  1837. PAGE *h;
  1838. void *handle;
  1839. int (*callback) __P((void *, const void *));
  1840. DBT *key;
  1841. u_int32_t flags;
  1842. {
  1843. DBT dbt, unkdbt;
  1844. BKEYDATA *bk;
  1845. BOVERFLOW *bo;
  1846. db_indx_t i, beg, end;
  1847. u_int32_t himark;
  1848. u_int8_t *pgmap;
  1849. void *ovflbuf;
  1850. int t_ret, ret, err_ret;
  1852. /* Shut up lint. */
  1853. COMPQUIET(end, 0);
  1855. ovflbuf = pgmap = NULL;
  1856. err_ret = ret = 0;
  1858. memset(&dbt, 0, sizeof(DBT));
  1859. dbt.flags = DB_DBT_REALLOC;
  1861. memset(&unkdbt, 0, sizeof(DBT));
  1862. unkdbt.size = strlen("UNKNOWN") + 1;
  1863. unkdbt.data = "UNKNOWN";
  1865. /*
  1866.  * Allocate a buffer for overflow items.  Start at one page;
  1867.  * __db_safe_goff will realloc as needed.
  1868.  */
  1869. if ((ret = __os_malloc(dbp->dbenv, dbp->pgsize, NULL, &ovflbuf)) != 0)
  1870. return (ret);
  1872. if (LF_ISSET(DB_AGGRESSIVE)) {
  1873. if ((ret =
  1874.     __os_malloc(dbp->dbenv, dbp->pgsize, NULL, &pgmap)) != 0)
  1875. goto err;
  1876. memset(pgmap, 0, dbp->pgsize);
  1877. }
  1879. /*
  1880.  * Loop through the inp array, spitting out key/data pairs.
  1881.  *
  1882.  * If we're salvaging normally, loop from 0 through NUM_ENT(h).
  1883.  * If we're being aggressive, loop until we hit the end of the page--
  1884.  * NUM_ENT() may be bogus.
  1885.  */
  1886. himark = dbp->pgsize;
  1887. for (i = 0;; i += O_INDX) {
  1888. /* If we're not aggressive, break when we hit NUM_ENT(h). */
  1889. if (!LF_ISSET(DB_AGGRESSIVE) && i >= NUM_ENT(h))
  1890. break;
  1892. /* Verify the current item. */
  1893. ret = __db_vrfy_inpitem(dbp,
  1894.     h, pgno, i, 1, flags, &himark, NULL);
  1895. /* If this returned a fatality, it's time to break. */
  1896. if (ret == DB_VERIFY_FATAL) {
  1897. /*
  1898.  * Don't return DB_VERIFY_FATAL;  it's private
  1899.  * and means only that we can't go on with this
  1900.  * page, not with the whole database.  It's
  1901.  * not even an error if we've run into it
  1902.  * after NUM_ENT(h).
  1903.  */
  1904. ret = (i < NUM_ENT(h)) ? DB_VERIFY_BAD : 0;
  1905. break;
  1906. }
  1908. /*
  1909.  * If this returned 0, it's safe to print or (carefully)
  1910.  * try to fetch.
  1911.  */
  1912. if (ret == 0) {
  1913. /*
  1914.  * We only want to print deleted items if
  1915.  * DB_AGGRESSIVE is set.
  1916.  */
  1917. bk = GET_BKEYDATA(h, i);
  1918. if (!LF_ISSET(DB_AGGRESSIVE) && B_DISSET(bk->type))
  1919. continue;
  1921. /*
  1922.  * We're going to go try to print the next item.  If
  1923.  * key is non-NULL, we're a dup page, so we've got to
  1924.  * print the key first, unless SA_SKIPFIRSTKEY is set
  1925.  * and we're on the first entry.
  1926.  */
  1927. if (key != NULL &&
  1928.     (i != 0 || !LF_ISSET(SA_SKIPFIRSTKEY)))
  1929. if ((ret = __db_prdbt(key,
  1930.     0, " ", handle, callback, 0, NULL)) != 0)
  1931. err_ret = ret;
  1933. beg = h->inp[i];
  1934. switch (B_TYPE(bk->type)) {
  1935. case B_DUPLICATE:
  1936. end = beg + BOVERFLOW_SIZE - 1;
  1937. /*
  1938.  * If we're not on a normal btree leaf page,
  1939.  * there shouldn't be off-page
  1940.  * dup sets.  Something's confused;  just
  1941.  * drop it, and the code to pick up unlinked
  1942.  * offpage dup sets will print it out
  1943.  * with key "UNKNOWN" later.
  1944.  */
  1945. if (pgtype != P_LBTREE)
  1946. break;
  1948. bo = (BOVERFLOW *)bk;
  1950. /*
  1951.  * If the page number is unreasonable, or
  1952.  * if this is supposed to be a key item,
  1953.  * just spit out "UNKNOWN"--the best we
  1954.  * can do is run into the data items in the
  1955.  * unlinked offpage dup pass.
  1956.  */
  1957. if (!IS_VALID_PGNO(bo->pgno) ||
  1958.     (i % P_INDX == 0)) {
  1959. /* Not much to do on failure. */
  1960. if ((ret = __db_prdbt(&unkdbt, 0, " ",
  1961.     handle, callback, 0, NULL)) != 0)
  1962. err_ret = ret;
  1963. break;
  1964. }
  1966. if ((ret = __db_salvage_duptree(dbp,
  1967.     vdp, bo->pgno, &dbt, handle, callback,
  1968. flags | SA_SKIPFIRSTKEY)) != 0)
  1969. err_ret = ret;
  1971. break;
  1972. case B_KEYDATA:
  1973. end = ALIGN(beg + bk->len, sizeof(u_int32_t)) - 1;
  1974. dbt.data = bk->data;
  1975. dbt.size = bk->len;
  1976. if ((ret = __db_prdbt(&dbt,
  1977.     0, " ", handle, callback, 0, NULL)) != 0)
  1978. err_ret = ret;
  1979. break;
  1980. case B_OVERFLOW:
  1981. end = beg + BOVERFLOW_SIZE - 1;
  1982. bo = (BOVERFLOW *)bk;
  1983. if ((ret = __db_safe_goff(dbp, vdp,
  1984.     bo->pgno, &dbt, &ovflbuf, flags)) != 0) {
  1985. err_ret = ret;
  1986. /* We care about err_ret more. */
  1987. (void)__db_prdbt(&unkdbt, 0, " ",
  1988.     handle, callback, 0, NULL);
  1989. break;
  1990. }
  1991. if ((ret = __db_prdbt(&dbt,
  1992.     0, " ", handle, callback, 0, NULL)) != 0)
  1993. err_ret = ret;
  1994. break;
  1995. default:
  1996. /*
  1997.  * We should never get here;  __db_vrfy_inpitem
  1998.  * should not be returning 0 if bk->type
  1999.  * is unrecognizable.
  2000.  */
  2001. DB_ASSERT(0);
  2002. return (EINVAL);
  2003. }
  2005. /*
  2006.  * If we're being aggressive, mark the beginning
  2007.  * and end of the item;  we'll come back and print
  2008.  * whatever "junk" is in the gaps in case we had
  2009.  * any bogus inp elements and thereby missed stuff.
  2010.  */
  2011. if (LF_ISSET(DB_AGGRESSIVE)) {
  2012. pgmap[beg] = ITEM_BEGIN;
  2013. pgmap[end] = ITEM_END;
  2014. }
  2015. }
  2016. }
  2018. /*
  2019.  * If i is odd and this is a btree leaf, we've printed out a key but not
  2020.  * a datum; fix this imbalance by printing an "UNKNOWN".
  2021.  */
  2022. if (pgtype == P_LBTREE && (i % P_INDX == 1) && ((ret =
  2023.     __db_prdbt(&unkdbt, 0, " ", handle, callback, 0, NULL)) != 0))
  2024. err_ret = ret;
  2026. err: if (pgmap != NULL)
  2027. __os_free(pgmap, 0);
  2028. __os_free(ovflbuf, 0);
  2030. /* Mark this page as done. */
  2031. if ((t_ret = __db_salvage_markdone(vdp, pgno)) != 0)
  2032. return (t_ret);
  2034. return ((err_ret != 0) ? err_ret : ret);
  2035. }
  2037. /*
  2038.  * __bam_salvage_walkdupint --
  2039.  * Walk a known-good btree or recno internal page which is part of
  2040.  * a dup tree, calling __db_salvage_duptree on each child page.
  2041.  *
  2042.  * PUBLIC: int __bam_salvage_walkdupint __P((DB *, VRFY_DBINFO *, PAGE *,
  2043.  * PUBLIC:     DBT *, void *, int (*)(void *, const void *), u_int32_t));
  2044.  */
  2045. int
  2046. __bam_salvage_walkdupint(dbp, vdp, h, key, handle, callback, flags)
  2047. DB *dbp;
  2048. VRFY_DBINFO *vdp;
  2049. PAGE *h;
  2050. DBT *key;
  2051. void *handle;
  2052. int (*callback) __P((void *, const void *));
  2053. u_int32_t flags;
  2054. {
  2055. RINTERNAL *ri;
  2056. BINTERNAL *bi;
  2057. int ret, t_ret;
  2058. db_indx_t i;
  2060. ret = 0;
  2061. for (i = 0; i < NUM_ENT(h); i++) {
  2062. switch (TYPE(h)) {
  2063. case P_IBTREE:
  2064. bi = GET_BINTERNAL(h, i);
  2065. if ((t_ret = __db_salvage_duptree(dbp,
  2066.     vdp, bi->pgno, key, handle, callback, flags)) != 0)
  2067. ret = t_ret;
  2068. case P_IRECNO:
  2069. ri = GET_RINTERNAL(h, i);
  2070. if ((t_ret = __db_salvage_duptree(dbp,
  2071.     vdp, ri->pgno, key, handle, callback, flags)) != 0)
  2072. ret = t_ret;
  2073. break;
  2074. default:
  2075. __db_err(dbp->dbenv,
  2076.     "__bam_salvage_walkdupint called on non-int. page");
  2077. DB_ASSERT(0);
  2078. return (EINVAL);
  2079. }
  2080. /* Pass SA_SKIPFIRSTKEY, if set, on to the 0th child only. */
  2081. flags &= ~LF_ISSET(SA_SKIPFIRSTKEY);
  2082. }
  2084. return (ret);
  2085. }
  2087. /*
  2088.  * __bam_meta2pgset --
  2089.  * Given a known-good meta page, return in pgsetp a 0-terminated list of
  2090.  * db_pgno_t's corresponding to the pages in the btree.
  2091.  *
  2092.  * We do this by a somewhat sleazy method, to avoid having to traverse the
  2093.  * btree structure neatly:  we walk down the left side to the very
  2094.  * first leaf page, then we mark all the pages in the chain of
  2095.  * NEXT_PGNOs (being wary of cycles and invalid ones), then we
  2096.  * consolidate our scratch array into a nice list, and return.  This
  2097.  * avoids the memory management hassles of recursion and the
  2098.  * trouble of walking internal pages--they just don't matter, except
  2099.  * for the left branch.
  2100.  *
  2101.  * PUBLIC: int __bam_meta2pgset __P((DB *, VRFY_DBINFO *, BTMETA *,
  2102.  * PUBLIC:     u_int32_t, DB *));
  2103.  */
  2104. int
  2105. __bam_meta2pgset(dbp, vdp, btmeta, flags, pgset)
  2106. DB *dbp;
  2107. VRFY_DBINFO *vdp;
  2108. BTMETA *btmeta;
  2109. u_int32_t flags;
  2110. DB *pgset;
  2111. {
  2112. BINTERNAL *bi;
  2113. PAGE *h;
  2114. RINTERNAL *ri;
  2115. db_pgno_t current, p;
  2116. int err_ret, ret;
  2118. h = NULL;
  2119. ret = err_ret = 0;
  2120. DB_ASSERT(pgset != NULL);
  2121. for (current = btmeta->root;;) {
  2122. if (!IS_VALID_PGNO(current) || current == PGNO(btmeta)) {
  2123. err_ret = DB_VERIFY_BAD;
  2124. goto err;
  2125. }
  2126. if ((ret = memp_fget(dbp->mpf, &current, 0, &h)) != 0) {
  2127. err_ret = ret;
  2128. goto err;
  2129. }
  2131. switch (TYPE(h)) {
  2132. case P_IBTREE:
  2133. case P_IRECNO:
  2134. if ((ret = __bam_vrfy(dbp,
  2135.     vdp, h, current, flags | DB_NOORDERCHK)) != 0) {
  2136. err_ret = ret;
  2137. goto err;
  2138. }
  2139. if (TYPE(h) == P_IBTREE) {
  2140. bi = GET_BINTERNAL(h, 0);
  2141. current = bi->pgno;
  2142. } else { /* P_IRECNO */
  2143. ri = GET_RINTERNAL(h, 0);
  2144. current = ri->pgno;
  2145. }
  2146. break;
  2147. case P_LBTREE:
  2148. case P_LRECNO:
  2149. goto traverse;
  2150. default:
  2151. err_ret = DB_VERIFY_BAD;
  2152. goto err;
  2153. }
  2155. if ((ret = memp_fput(dbp->mpf, h, 0)) != 0)
  2156. err_ret = ret;
  2157. h = NULL;
  2158. }
  2160. /*
  2161.  * At this point, current is the pgno of leaf page h, the 0th in the
  2162.  * tree we're concerned with.
  2163.  */
  2164. traverse:
  2165. while (IS_VALID_PGNO(current) && current != PGNO_INVALID) {
  2166. if (h == NULL &&
  2167.     (ret = memp_fget(dbp->mpf, &current, 0, &h) != 0)) {
  2168. err_ret = ret;
  2169. break;
  2170. }
  2172. if ((ret = __db_vrfy_pgset_get(pgset, current, (int *)&p)) != 0)
  2173. goto err;
  2175. if (p != 0) {
  2176. /*
  2177.  * We've found a cycle.  Return success anyway--
  2178.  * our caller may as well use however much of
  2179.  * the pgset we've come up with.
  2180.  */
  2181. break;
  2182. }
  2183. if ((ret = __db_vrfy_pgset_inc(pgset, current)) != 0)
  2184. goto err;
  2186. current = NEXT_PGNO(h);
  2187. if ((ret = memp_fput(dbp->mpf, h, 0)) != 0)
  2188. err_ret = ret;
  2189. h = NULL;
  2190. }
  2192. err: if (h != NULL)
  2193. (void)memp_fput(dbp->mpf, h, 0);
  2195. return (ret == 0 ? err_ret : ret);
  2196. }
  2198. /*
  2199.  * __bam_safe_getdata --
  2200.  *
  2201.  * Utility function for __bam_vrfy_itemorder.  Safely gets the datum at
  2202.  * index i, page h, and sticks it in DBT dbt.  If ovflok is 1 and i's an
  2203.  * overflow item, we do a safe_goff to get the item and signal that we need
  2204.  * to free dbt->data;  if ovflok is 0, we leaves the DBT zeroed.
  2205.  */
  2206. static int
  2207. __bam_safe_getdata(dbp, h, i, ovflok, dbt, freedbtp)
  2208. DB *dbp;
  2209. PAGE *h;
  2210. u_int32_t i;
  2211. int ovflok;
  2212. DBT *dbt;
  2213. int *freedbtp;
  2214. {
  2215. BKEYDATA *bk;
  2216. BOVERFLOW *bo;
  2218. memset(dbt, 0, sizeof(DBT));
  2219. *freedbtp = 0;
  2221. bk = GET_BKEYDATA(h, i);
  2222. if (B_TYPE(bk->type) == B_OVERFLOW) {
  2223. if (!ovflok)
  2224. return (0);
  2226. bo = (BOVERFLOW *)bk;
  2227. F_SET(dbt, DB_DBT_MALLOC);
  2229. *freedbtp = 1;
  2230. return (__db_goff(dbp, dbt, bo->tlen, bo->pgno, NULL, NULL));
  2231. } else {
  2232. dbt->data = bk->data;
  2233. dbt->size = bk->len;
  2234. }
  2236. return (0);
  2237. }