1 /*-
2 * See the file LICENSE for redistribution information.
3 *
4 * Copyright (c) 1996, 2013 Oracle and/or its affiliates. All rights reserved.
5 */
6 /*
7 * Copyright (c) 1990, 1993, 1994, 1995, 1996
8 * Keith Bostic. All rights reserved.
9 */
10 /*
11 * Copyright (c) 1990, 1993, 1994, 1995
12 * The Regents of the University of California. All rights reserved.
13 *
14 * This code is derived from software contributed to Berkeley by
15 * Mike Olson.
16 *
17 * Redistribution and use in source and binary forms, with or without
18 * modification, are permitted provided that the following conditions
19 * are met:
20 * 1. Redistributions of source code must retain the above copyright
21 * notice, this list of conditions and the following disclaimer.
22 * 2. Redistributions in binary form must reproduce the above copyright
23 * notice, this list of conditions and the following disclaimer in the
24 * documentation and/or other materials provided with the distribution.
25 * 3. Neither the name of the University nor the names of its contributors
26 * may be used to endorse or promote products derived from this software
27 * without specific prior written permission.
28 *
29 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
30 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
31 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
32 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
33 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
34 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
35 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
36 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
37 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
38 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
39 * SUCH DAMAGE.
40 *
41 * $Id$
42 */
43
44 #include "db_config.h"
45
46 #include "db_int.h"
47 #include "dbinc/db_page.h"
48 #include "dbinc/db_am.h"
49 #include "dbinc/db_verify.h"
50 #include "dbinc/mp.h"
51
52 /*
53 * __db_vrfy_overflow --
54 * Verify overflow page.
55 *
56 * PUBLIC: int __db_vrfy_overflow __P((DB *, VRFY_DBINFO *, PAGE *, db_pgno_t,
57 * PUBLIC: u_int32_t));
58 */
59 int
__db_vrfy_overflow(dbp,vdp,h,pgno,flags)60 __db_vrfy_overflow(dbp, vdp, h, pgno, flags)
61 DB *dbp;
62 VRFY_DBINFO *vdp;
63 PAGE *h;
64 db_pgno_t pgno;
65 u_int32_t flags;
66 {
67 VRFY_PAGEINFO *pip;
68 int isbad, ret, t_ret;
69
70 isbad = 0;
71 if ((ret = __db_vrfy_getpageinfo(vdp, pgno, &pip)) != 0)
72 return (ret);
73
74 if ((ret = __db_vrfy_datapage(dbp, vdp, h, pgno, flags)) != 0) {
75 if (ret == DB_VERIFY_BAD)
76 isbad = 1;
77 else
78 goto err;
79 }
80
81 pip->refcount = OV_REF(h);
82 if (pip->refcount < 1) {
83 EPRINT((dbp->env, DB_STR_A("0676",
84 "Page %lu: overflow page has zero reference count", "%lu"),
85 (u_long)pgno));
86 isbad = 1;
87 }
88
89 /* Just store for now. */
90 pip->olen = HOFFSET(h);
91
92 err: if ((t_ret = __db_vrfy_putpageinfo(dbp->env, vdp, pip)) != 0)
93 ret = t_ret;
94 return ((ret == 0 && isbad == 1) ? DB_VERIFY_BAD : ret);
95 }
96
97 /*
98 * __db_vrfy_ovfl_structure --
99 * Walk a list of overflow pages, avoiding cycles and marking
100 * pages seen.
101 *
102 * PUBLIC: int __db_vrfy_ovfl_structure
103 * PUBLIC: __P((DB *, VRFY_DBINFO *, db_pgno_t, u_int32_t, u_int32_t));
104 */
105 int
__db_vrfy_ovfl_structure(dbp,vdp,pgno,tlen,flags)106 __db_vrfy_ovfl_structure(dbp, vdp, pgno, tlen, flags)
107 DB *dbp;
108 VRFY_DBINFO *vdp;
109 db_pgno_t pgno;
110 u_int32_t tlen;
111 u_int32_t flags;
112 {
113 DB *pgset;
114 ENV *env;
115 VRFY_PAGEINFO *pip;
116 db_pgno_t next, prev;
117 int isbad, ret, seen_cnt, t_ret;
118 u_int32_t refcount;
119
120 env = dbp->env;
121 pgset = vdp->pgset;
122 DB_ASSERT(env, pgset != NULL);
123 isbad = 0;
124
125 /* This shouldn't happen, but just to be sure. */
126 if (!IS_VALID_PGNO(pgno))
127 return (DB_VERIFY_BAD);
128
129 /*
130 * Check the first prev_pgno; it ought to be PGNO_INVALID,
131 * since there's no prev page.
132 */
133 if ((ret = __db_vrfy_getpageinfo(vdp, pgno, &pip)) != 0)
134 return (ret);
135
136 /* The refcount is stored on the first overflow page. */
137 refcount = pip->refcount;
138
139 if (pip->type != P_OVERFLOW) {
140 EPRINT((env, DB_STR_A("0677",
141 "Page %lu: overflow page of invalid type %lu", "%lu %lu"),
142 (u_long)pgno, (u_long)pip->type));
143 ret = DB_VERIFY_BAD;
144 goto err; /* Unsafe to continue. */
145 }
146
147 prev = pip->prev_pgno;
148 if (prev != PGNO_INVALID) {
149 EPRINT((env, DB_STR_A("0678",
150 "Page %lu: first page in overflow chain has a prev_pgno %lu",
151 "%lu %lu"), (u_long)pgno, (u_long)prev));
152 isbad = 1;
153 }
154
155 for (;;) {
156 /*
157 * We may have seen this page elsewhere, if the overflow entry
158 * has been promoted to an internal page; we just want to
159 * make sure that each overflow page is seen exactly as many
160 * times as its refcount dictates.
161 *
162 * Note that this code also serves to keep us from looping
163 * infinitely if there's a cycle in an overflow chain.
164 */
165 if ((ret = __db_vrfy_pgset_get(pgset,
166 vdp->thread_info, vdp->txn, pgno, &seen_cnt)) != 0)
167 goto err;
168 if ((u_int32_t)seen_cnt > refcount) {
169 EPRINT((env, DB_STR_A("0679",
170 "Page %lu: encountered too many times in overflow traversal",
171 "%lu"), (u_long)pgno));
172 ret = DB_VERIFY_BAD;
173 goto err;
174 }
175 if ((ret = __db_vrfy_pgset_inc(
176 pgset, vdp->thread_info, vdp->txn, pgno)) != 0)
177 goto err;
178
179 /*
180 * Each overflow page can be referenced multiple times,
181 * because it's possible for overflow Btree keys to get
182 * promoted to internal pages. We want to make sure that
183 * each page is referenced from a Btree leaf (or Hash data
184 * page, which we consider a "leaf" here) exactly once; if
185 * the parent was a leaf, set a flag to indicate that we've
186 * seen this page in a leaf context.
187 *
188 * If the parent is not a leaf--in which case it's a Btree
189 * internal page--we don't need to bother doing any further
190 * verification, as we'll do it when we hit the leaf (or
191 * complain that we never saw the leaf). Only the first
192 * page in an overflow chain should ever have a refcount
193 * greater than 1, and the combination of the LEAFSEEN check
194 * and the fact that we bail after the first page for
195 * non-leaves should ensure this.
196 *
197 * Note that each "child" of a page, such as an overflow page,
198 * is stored and verified in a structure check exactly once,
199 * so this code does not need to contend with the fact that
200 * overflow chains used as Btree duplicate keys may be
201 * referenced multiply from a single Btree leaf page.
202 */
203 if (LF_ISSET(DB_ST_OVFL_LEAF)) {
204 if (F_ISSET(pip, VRFY_OVFL_LEAFSEEN)) {
205 EPRINT((env, DB_STR_A("0680",
206 "Page %lu: overflow page linked twice from leaf or data page",
207 "%lu"), (u_long)pgno));
208 ret = DB_VERIFY_BAD;
209 goto err;
210 }
211 F_SET(pip, VRFY_OVFL_LEAFSEEN);
212 }
213
214 /*
215 * We want to verify each overflow chain only once, and
216 * although no chain should be linked more than once from a
217 * leaf page, we can't guarantee that it'll be linked that
218 * once if it's linked from an internal page and the key
219 * is gone.
220 *
221 * seen_cnt is the number of times we'd encountered this page
222 * before calling this function.
223 */
224 if (seen_cnt == 0) {
225 /*
226 * Keep a running tab on how much of the item we've
227 * seen.
228 */
229 tlen -= pip->olen;
230
231 /* Send the application feedback about our progress. */
232 if (!LF_ISSET(DB_SALVAGE))
233 __db_vrfy_struct_feedback(dbp, vdp);
234 } else
235 goto done;
236
237 next = pip->next_pgno;
238
239 /* Are we there yet? */
240 if (next == PGNO_INVALID)
241 break;
242
243 /*
244 * We've already checked this when we saved it, but just
245 * to be sure...
246 */
247 if (!IS_VALID_PGNO(next)) {
248 EPRINT((env, DB_STR_A("0681",
249 "Page %lu: bad next_pgno %lu on overflow page",
250 "%lu %lu"), (u_long)pgno, (u_long)next));
251 ret = DB_VERIFY_BAD;
252 goto err;
253 }
254
255 if ((ret = __db_vrfy_putpageinfo(env, vdp, pip)) != 0 ||
256 (ret = __db_vrfy_getpageinfo(vdp, next, &pip)) != 0)
257 return (ret);
258 if (pip->prev_pgno != pgno) {
259 EPRINT((env, DB_STR_A("0682",
260 "Page %lu: bad prev_pgno %lu on overflow page (should be %lu)",
261 "%lu %lu %lu"), (u_long)next,
262 (u_long)pip->prev_pgno, (u_long)pgno));
263 isbad = 1;
264 /*
265 * It's safe to continue because we have separate
266 * cycle detection.
267 */
268 }
269
270 pgno = next;
271 }
272
273 if (tlen > 0) {
274 isbad = 1;
275 EPRINT((env, DB_STR_A("0683",
276 "Page %lu: overflow item incomplete", "%lu"),
277 (u_long)pgno));
278 }
279
280 done:
281 err: if ((t_ret =
282 __db_vrfy_putpageinfo(env, vdp, pip)) != 0 && ret == 0)
283 ret = t_ret;
284 return ((ret == 0 && isbad == 1) ? DB_VERIFY_BAD : ret);
285 }
286
287 /*
288 * __db_safe_goff --
289 * Get an overflow item, very carefully, from an untrusted database,
290 * in the context of the salvager.
291 *
292 * PUBLIC: int __db_safe_goff __P((DB *, VRFY_DBINFO *,
293 * PUBLIC: db_pgno_t, DBT *, void *, u_int32_t *, u_int32_t));
294 */
295 int
__db_safe_goff(dbp,vdp,pgno,dbt,buf,bufsz,flags)296 __db_safe_goff(dbp, vdp, pgno, dbt, buf, bufsz, flags)
297 DB *dbp;
298 VRFY_DBINFO *vdp;
299 db_pgno_t pgno;
300 DBT *dbt;
301 void *buf;
302 u_int32_t *bufsz;
303 u_int32_t flags;
304 {
305 DB_MPOOLFILE *mpf;
306 PAGE *h;
307 int ret, t_ret;
308 u_int32_t bytesgot, bytes;
309 u_int8_t *src, *dest;
310
311 mpf = dbp->mpf;
312 h = NULL;
313 ret = t_ret = 0;
314 bytesgot = bytes = 0;
315
316 DB_ASSERT(dbp->env, bufsz != NULL);
317
318 /*
319 * Back up to the start of the overflow chain (if necessary) via the
320 * prev pointer of the overflow page. This guarantees we transverse the
321 * longest possible chains of overflow pages and won't be called again
322 * with a pgno earlier in the chain, stepping on ourselves.
323 */
324 for (;;) {
325 if ((ret = __memp_fget(
326 mpf, &pgno, vdp->thread_info, NULL, 0, &h)) != 0)
327 return (ret);
328
329 if (PREV_PGNO(h) == PGNO_INVALID ||
330 !IS_VALID_PGNO(PREV_PGNO(h)))
331 break;
332
333 pgno = PREV_PGNO(h);
334
335 if ((ret = __memp_fput(mpf,
336 vdp->thread_info, h, DB_PRIORITY_UNCHANGED)) != 0)
337 return (ret);
338 }
339 if ((ret = __memp_fput(
340 mpf, vdp->thread_info, h, DB_PRIORITY_UNCHANGED)) != 0)
341 return (ret);
342
343 h = NULL;
344
345 while ((pgno != PGNO_INVALID) && (IS_VALID_PGNO(pgno))) {
346 /*
347 * Mark that we're looking at this page; if we've seen it
348 * already, quit.
349 */
350 if ((ret = __db_salvage_markdone(vdp, pgno)) != 0)
351 break;
352
353 if ((ret = __memp_fget(mpf, &pgno,
354 vdp->thread_info, NULL, 0, &h)) != 0)
355 break;
356
357 /*
358 * Make sure it's really an overflow page, unless we're
359 * being aggressive, in which case we pretend it is.
360 */
361 if (!LF_ISSET(DB_AGGRESSIVE) && TYPE(h) != P_OVERFLOW) {
362 ret = DB_VERIFY_BAD;
363 break;
364 }
365
366 src = (u_int8_t *)h + P_OVERHEAD(dbp);
367 bytes = OV_LEN(h);
368
369 if (bytes + P_OVERHEAD(dbp) > dbp->pgsize)
370 bytes = dbp->pgsize - P_OVERHEAD(dbp);
371
372 /*
373 * Realloc if buf is too small
374 */
375 if (bytesgot + bytes > *bufsz) {
376 if ((ret =
377 __os_realloc(dbp->env, bytesgot + bytes, buf)) != 0)
378 break;
379 *bufsz = bytesgot + bytes;
380 }
381
382 dest = *(u_int8_t **)buf + bytesgot;
383 bytesgot += bytes;
384
385 memcpy(dest, src, bytes);
386
387 pgno = NEXT_PGNO(h);
388
389 if ((ret = __memp_fput(mpf,
390 vdp->thread_info, h, DB_PRIORITY_UNCHANGED)) != 0)
391 break;
392 h = NULL;
393 }
394
395 /*
396 * If we're being aggressive, salvage a partial datum if there
397 * was an error somewhere along the way.
398 */
399 if (ret == 0 || LF_ISSET(DB_AGGRESSIVE)) {
400 dbt->size = bytesgot;
401 dbt->data = *(void **)buf;
402 }
403
404 /* If we broke out on error, don't leave pages pinned. */
405 if (h != NULL && (t_ret = __memp_fput(mpf,
406 vdp->thread_info, h, DB_PRIORITY_UNCHANGED)) != 0 && ret == 0)
407 ret = t_ret;
408
409 return (ret);
410 }
411