Bug Summary

File:src/lib/libc/db/btree/bt_seq.c
Warning:line 374, column 10
Access to field 'pgno' results in a dereference of a null pointer (loaded from variable 'h')

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -cc1 -triple amd64-unknown-openbsd7.0 -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name bt_seq.c -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -mrelocation-model pic -pic-level 1 -fhalf-no-semantic-interposition -mframe-pointer=all -relaxed-aliasing -fno-rounding-math -mconstructor-aliases -munwind-tables -target-cpu x86-64 -target-feature +retpoline-indirect-calls -target-feature +retpoline-indirect-branches -tune-cpu generic -debugger-tuning=gdb -fcoverage-compilation-dir=/usr/src/lib/libc/obj -resource-dir /usr/local/lib/clang/13.0.0 -include namespace.h -I /usr/src/lib/libc/include -I /usr/src/lib/libc/hidden -D __LIBC__ -D APIWARN -D YP -I /usr/src/lib/libc/yp -I /usr/src/lib/libc -I /usr/src/lib/libc/gdtoa -I /usr/src/lib/libc/arch/amd64/gdtoa -D INFNAN_CHECK -D MULTIPLE_THREADS -D NO_FENV_H -D USE_LOCALE -I /usr/src/lib/libc -I /usr/src/lib/libc/citrus -D RESOLVSORT -D FLOATING_POINT -D PRINTF_WIDE_CHAR -D SCANF_WIDE_CHAR -D FUTEX -D PIC -internal-isystem /usr/local/lib/clang/13.0.0/include -internal-externc-isystem /usr/include -O2 -fdebug-compilation-dir=/usr/src/lib/libc/obj -ferror-limit 19 -fwrapv -D_RET_PROTECTOR -ret-protector -fgnuc-version=4.2.1 -vectorize-loops -vectorize-slp -fno-builtin-malloc -fno-builtin-calloc -fno-builtin-realloc -fno-builtin-valloc -fno-builtin-free -fno-builtin-strdup -fno-builtin-strndup -analyzer-output=html -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /home/ben/Projects/vmm/scan-build/2022-01-12-194120-40624-1 -x c /usr/src/lib/libc/db/btree/bt_seq.c
1/* $OpenBSD: bt_seq.c,v 1.11 2005/08/05 13:03:00 espie Exp $ */
2
3/*-
4 * Copyright (c) 1990, 1993, 1994
5 * The Regents of the University of California. All rights reserved.
6 *
7 * This code is derived from software contributed to Berkeley by
8 * Mike Olson.
9 *
10 * Redistribution and use in source and binary forms, with or without
11 * modification, are permitted provided that the following conditions
12 * are met:
13 * 1. Redistributions of source code must retain the above copyright
14 * notice, this list of conditions and the following disclaimer.
15 * 2. Redistributions in binary form must reproduce the above copyright
16 * notice, this list of conditions and the following disclaimer in the
17 * documentation and/or other materials provided with the distribution.
18 * 3. Neither the name of the University nor the names of its contributors
19 * may be used to endorse or promote products derived from this software
20 * without specific prior written permission.
21 *
22 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
23 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
24 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
25 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
26 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
27 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
28 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
29 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
30 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
31 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
32 * SUCH DAMAGE.
33 */
34
35#include <sys/types.h>
36
37#include <errno(*__errno()).h>
38#include <stddef.h>
39#include <stdio.h>
40#include <stdlib.h>
41
42#include <db.h>
43#include "btree.h"
44
45static int __bt_first(BTREE *, const DBT *, EPG *, int *);
46static int __bt_seqadv(BTREE *, EPG *, int);
47static int __bt_seqset(BTREE *, EPG *, DBT *, int);
48
49/*
50 * Sequential scan support.
51 *
52 * The tree can be scanned sequentially, starting from either end of the
53 * tree or from any specific key. A scan request before any scanning is
54 * done is initialized as starting from the least node.
55 */
56
57/*
58 * __bt_seq --
59 * Btree sequential scan interface.
60 *
61 * Parameters:
62 * dbp: pointer to access method
63 * key: key for positioning and return value
64 * data: data return value
65 * flags: R_CURSOR, R_FIRST, R_LAST, R_NEXT, R_PREV.
66 *
67 * Returns:
68 * RET_ERROR, RET_SUCCESS or RET_SPECIAL if there's no next key.
69 */
70int
71__bt_seq(const DB *dbp, DBT *key, DBT *data, u_int flags)
72{
73 BTREE *t;
74 EPG e;
75 int status;
76
77 t = dbp->internal;
78
79 /* Toss any page pinned across calls. */
80 if (t->bt_pinned != NULL((void*)0)) {
1
Assuming field 'bt_pinned' is equal to NULL
→
2
←
Taking false branch
→
81 mpool_put(t->bt_mp, t->bt_pinned, 0);
82 t->bt_pinned = NULL((void*)0);
83 }
84
85 /*
86 * If scan unitialized as yet, or starting at a specific record, set
87 * the scan to a specific key. Both __bt_seqset and __bt_seqadv pin
88 * the page the cursor references if they're successful.
89 */
90 switch (flags) {
3
←
Control jumps to 'case 1:' at line 100
→
91 case R_NEXT7:
92 case R_PREV9:
93 if (F_ISSET(&t->bt_cursor, CURS_INIT)((&t->bt_cursor)->flags & (0x08))) {
94 status = __bt_seqadv(t, &e, flags);
95 break;
96 }
97 /* FALLTHROUGH */
98 case R_FIRST3:
99 case R_LAST6:
100 case R_CURSOR1:
101 status = __bt_seqset(t, &e, key, flags);
4
←
Calling '__bt_seqset'
→
102 break;
103 default:
104 errno(*__errno()) = EINVAL22;
105 return (RET_ERROR-1);
106 }
107
108 if (status == RET_SUCCESS0) {
109 __bt_setcur(t, e.page->pgno, e.index);
110
111 status =
112 __bt_ret(t, &e, key, &t->bt_rkey, data, &t->bt_rdata, 0);
113
114 /*
115 * If the user is doing concurrent access, we copied the
116 * key/data, toss the page.
117 */
118 if (F_ISSET(t, B_DB_LOCK)((t)->flags & (0x04000)))
119 mpool_put(t->bt_mp, e.page, 0);
120 else
121 t->bt_pinned = e.page;
122 }
123 return (status);
124}
125
126/*
127 * __bt_seqset --
128 * Set the sequential scan to a specific key.
129 *
130 * Parameters:
131 * t: tree
132 * ep: storage for returned key
133 * key: key for initial scan position
134 * flags: R_CURSOR, R_FIRST, R_LAST, R_NEXT, R_PREV
135 *
136 * Side effects:
137 * Pins the page the cursor references.
138 *
139 * Returns:
140 * RET_ERROR, RET_SUCCESS or RET_SPECIAL if there's no next key.
141 */
142static int
143__bt_seqset(BTREE *t, EPG *ep, DBT *key, int flags)
144{
145 PAGE *h;
146 pgno_t pg;
147 int exact;
148
149 /*
150 * Find the first, last or specific key in the tree and point the
151 * cursor at it. The cursor may not be moved until a new key has
152 * been found.
153 */
154 switch (flags) {
5
←
Control jumps to 'case 1:' at line 155
→
155 case R_CURSOR1: /* Keyed scan. */
156 /*
157 * Find the first instance of the key or the smallest key
158 * which is greater than or equal to the specified key.
159 */
160 if (key->data == NULL((void*)0) || key->size == 0) {
6
←
Assuming field 'data' is not equal to NULL
→
7
←
Assuming field 'size' is not equal to 0
→
8
←
Taking false branch
→
161 errno(*__errno()) = EINVAL22;
162 return (RET_ERROR-1);
163 }
164 return (__bt_first(t, key, ep, &exact));
9
←
Calling '__bt_first'
→
165 case R_FIRST3: /* First record. */
166 case R_NEXT7:
167 /* Walk down the left-hand side of the tree. */
168 for (pg = P_ROOT1;;) {
169 if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL((void*)0))
170 return (RET_ERROR-1);
171
172 /* Check for an empty tree. */
173 if (NEXTINDEX(h)(((h)->lower - (sizeof(pgno_t) + sizeof(pgno_t) + sizeof(pgno_t
) + sizeof(u_int32_t) + sizeof(indx_t) + sizeof(indx_t))) / sizeof
(indx_t)) == 0) {
174 mpool_put(t->bt_mp, h, 0);
175 return (RET_SPECIAL1);
176 }
177
178 if (h->flags & (P_BLEAF0x02 | P_RLEAF0x10))
179 break;
180 pg = GETBINTERNAL(h, 0)((BINTERNAL *)((char *)(h) + (h)->linp[0]))->pgno;
181 mpool_put(t->bt_mp, h, 0);
182 }
183 ep->page = h;
184 ep->index = 0;
185 break;
186 case R_LAST6: /* Last record. */
187 case R_PREV9:
188 /* Walk down the right-hand side of the tree. */
189 for (pg = P_ROOT1;;) {
190 if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL((void*)0))
191 return (RET_ERROR-1);
192
193 /* Check for an empty tree. */
194 if (NEXTINDEX(h)(((h)->lower - (sizeof(pgno_t) + sizeof(pgno_t) + sizeof(pgno_t
) + sizeof(u_int32_t) + sizeof(indx_t) + sizeof(indx_t))) / sizeof
(indx_t)) == 0) {
195 mpool_put(t->bt_mp, h, 0);
196 return (RET_SPECIAL1);
197 }
198
199 if (h->flags & (P_BLEAF0x02 | P_RLEAF0x10))
200 break;
201 pg = GETBINTERNAL(h, NEXTINDEX(h) - 1)((BINTERNAL *)((char *)(h) + (h)->linp[(((h)->lower - (
sizeof(pgno_t) + sizeof(pgno_t) + sizeof(pgno_t) + sizeof(u_int32_t
) + sizeof(indx_t) + sizeof(indx_t))) / sizeof(indx_t)) - 1])
)->pgno;
202 mpool_put(t->bt_mp, h, 0);
203 }
204
205 ep->page = h;
206 ep->index = NEXTINDEX(h)(((h)->lower - (sizeof(pgno_t) + sizeof(pgno_t) + sizeof(pgno_t
) + sizeof(u_int32_t) + sizeof(indx_t) + sizeof(indx_t))) / sizeof
(indx_t)) - 1;
207 break;
208 }
209 return (RET_SUCCESS0);
210}
211
212/*
213 * __bt_seqadvance --
214 * Advance the sequential scan.
215 *
216 * Parameters:
217 * t: tree
218 * flags: R_NEXT, R_PREV
219 *
220 * Side effects:
221 * Pins the page the new key/data record is on.
222 *
223 * Returns:
224 * RET_ERROR, RET_SUCCESS or RET_SPECIAL if there's no next key.
225 */
226static int
227__bt_seqadv(BTREE *t, EPG *ep, int flags)
228{
229 CURSOR *c;
230 PAGE *h;
231 indx_t idx;
232 pgno_t pg;
233 int exact;
234
235 /*
236 * There are a couple of states that we can be in. The cursor has
237 * been initialized by the time we get here, but that's all we know.
238 */
239 c = &t->bt_cursor;
240
241 /*
242 * The cursor was deleted where there weren't any duplicate records,
243 * so the key was saved. Find out where that key would go in the
244 * current tree. It doesn't matter if the returned key is an exact
245 * match or not -- if it's an exact match, the record was added after
246 * the delete so we can just return it. If not, as long as there's
247 * a record there, return it.
248 */
249 if (F_ISSET(c, CURS_ACQUIRE)((c)->flags & (0x01)))
250 return (__bt_first(t, &c->key, ep, &exact));
251
252 /* Get the page referenced by the cursor. */
253 if ((h = mpool_get(t->bt_mp, c->pg.pgno, 0)) == NULL((void*)0))
254 return (RET_ERROR-1);
255
256 /*
257 * Find the next/previous record in the tree and point the cursor at
258 * it. The cursor may not be moved until a new key has been found.
259 */
260 switch (flags) {
261 case R_NEXT7: /* Next record. */
262 /*
263 * The cursor was deleted in duplicate records, and moved
264 * forward to a record that has yet to be returned. Clear
265 * that flag, and return the record.
266 */
267 if (F_ISSET(c, CURS_AFTER)((c)->flags & (0x02)))
268 goto usecurrent;
269 idx = c->pg.index;
270 if (++idx == NEXTINDEX(h)(((h)->lower - (sizeof(pgno_t) + sizeof(pgno_t) + sizeof(pgno_t
) + sizeof(u_int32_t) + sizeof(indx_t) + sizeof(indx_t))) / sizeof
(indx_t))) {
271 pg = h->nextpg;
272 mpool_put(t->bt_mp, h, 0);
273 if (pg == P_INVALID0)
274 return (RET_SPECIAL1);
275 if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL((void*)0))
276 return (RET_ERROR-1);
277 idx = 0;
278 }
279 break;
280 case R_PREV9: /* Previous record. */
281 /*
282 * The cursor was deleted in duplicate records, and moved
283 * backward to a record that has yet to be returned. Clear
284 * that flag, and return the record.
285 */
286 if (F_ISSET(c, CURS_BEFORE)((c)->flags & (0x04))) {
287usecurrent: F_CLR(c, CURS_AFTER | CURS_BEFORE)(c)->flags &= ~(0x02 | 0x04);
288 ep->page = h;
289 ep->index = c->pg.index;
290 return (RET_SUCCESS0);
291 }
292 idx = c->pg.index;
293 if (idx == 0) {
294 pg = h->prevpg;
295 mpool_put(t->bt_mp, h, 0);
296 if (pg == P_INVALID0)
297 return (RET_SPECIAL1);
298 if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL((void*)0))
299 return (RET_ERROR-1);
300 idx = NEXTINDEX(h)(((h)->lower - (sizeof(pgno_t) + sizeof(pgno_t) + sizeof(pgno_t
) + sizeof(u_int32_t) + sizeof(indx_t) + sizeof(indx_t))) / sizeof
(indx_t)) - 1;
301 } else
302 --idx;
303 break;
304 }
305
306 ep->page = h;
307 ep->index = idx;
308 return (RET_SUCCESS0);
309}
310
311/*
312 * __bt_first --
313 * Find the first entry.
314 *
315 * Parameters:
316 * t: the tree
317 * key: the key
318 * erval: return EPG
319 * exactp: pointer to exact match flag
320 *
321 * Returns:
322 * The first entry in the tree greater than or equal to key,
323 * or RET_SPECIAL if no such key exists.
324 */
325static int
326__bt_first(BTREE *t, const DBT *key, EPG *erval, int *exactp)
327{
328 PAGE *h;
329 EPG *ep, save;
330 pgno_t pg;
331
332 /*
333 * Find any matching record; __bt_search pins the page.
334 *
335 * If it's an exact match and duplicates are possible, walk backwards
336 * in the tree until we find the first one. Otherwise, make sure it's
337 * a valid key (__bt_search may return an index just past the end of a
338 * page) and return it.
339 */
340 if ((ep = __bt_search(t, key, exactp)) == NULL((void*)0))
10
←
Assuming the condition is false
→
11
←
Taking false branch
→
341 return (0);
342 if (*exactp) {
12
←
Assuming the condition is true
→
13
←
Taking true branch
→
343 if (F_ISSET(t, B_NODUPS)((t)->flags & (0x00020))) {
14
←
Assuming the condition is false
→
15
←
Taking false branch
→
344 *erval = *ep;
345 return (RET_SUCCESS0);
346 }
347
348 /*
349 * Walk backwards, as long as the entry matches and there are
350 * keys left in the tree. Save a copy of each match in case
351 * we go too far.
352 */
353 save = *ep;
354 h = ep->page;
355 do {
356 if (save.page->pgno != ep->page->pgno) {
16
←
Assuming 'save.page->pgno' is equal to 'ep->page->pgno'
→
17
←
Taking false branch
→
357 mpool_put(t->bt_mp, save.page, 0);
358 save = *ep;
359 } else
360 save.index = ep->index;
361
362 /*
363 * Don't unpin the page the last (or original) match
364 * was on, but make sure it's unpinned if an error
365 * occurs.
366 */
367 if (ep->index == 0) {
18
←
Assuming field 'index' is equal to 0
→
19
←
Taking true branch
→
368 if (h->prevpg == P_INVALID0)
20
←
Assuming field 'prevpg' is not equal to P_INVALID
→
21
←
Taking false branch
→
369 break;
370 if (h->pgno
21.1
'h->pgno' is equal to 'save.page->pgno'
 != save.page->pgno)
22
←
Taking false branch
→
371 mpool_put(t->bt_mp, h, 0);
372 if ((h = mpool_get(t->bt_mp,
23
←
Value assigned to 'h'
→
24
←
Assuming pointer value is null
→
25
←
Taking true branch
→
373 h->prevpg, 0)) == NULL((void*)0)) {
374 if (h->pgno == save.page->pgno)
26
←
Access to field 'pgno' results in a dereference of a null pointer (loaded from variable 'h')
375 mpool_put(t->bt_mp,
376 save.page, 0);
377 return (RET_ERROR-1);
378 }
379 ep->page = h;
380 ep->index = NEXTINDEX(h)(((h)->lower - (sizeof(pgno_t) + sizeof(pgno_t) + sizeof(pgno_t
) + sizeof(u_int32_t) + sizeof(indx_t) + sizeof(indx_t))) / sizeof
(indx_t));
381 }
382 --ep->index;
383 } while (__bt_cmp(t, key, ep) == 0);
384
385 /*
386 * Reach here with the last page that was looked at pinned,
387 * which may or may not be the same as the last (or original)
388 * match page. If it's not useful, release it.
389 */
390 if (h->pgno != save.page->pgno)
391 mpool_put(t->bt_mp, h, 0);
392
393 *erval = save;
394 return (RET_SUCCESS0);
395 }
396
397 /* If at the end of a page, find the next entry. */
398 if (ep->index == NEXTINDEX(ep->page)(((ep->page)->lower - (sizeof(pgno_t) + sizeof(pgno_t) +
sizeof(pgno_t) + sizeof(u_int32_t) + sizeof(indx_t) + sizeof
(indx_t))) / sizeof(indx_t))) {
399 h = ep->page;
400 pg = h->nextpg;
401 mpool_put(t->bt_mp, h, 0);
402 if (pg == P_INVALID0)
403 return (RET_SPECIAL1);
404 if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL((void*)0))
405 return (RET_ERROR-1);
406 ep->index = 0;
407 ep->page = h;
408 }
409 *erval = *ep;
410 return (RET_SUCCESS0);
411}
412
413/*
414 * __bt_setcur --
415 * Set the cursor to an entry in the tree.
416 *
417 * Parameters:
418 * t: the tree
419 * pgno: page number
420 * idx: page index
421 */
422void
423__bt_setcur(BTREE *t, pgno_t pgno, u_int idx)
424{
425 /* Lose any already deleted key. */
426 if (t->bt_cursor.key.data != NULL((void*)0)) {
427 free(t->bt_cursor.key.data);
428 t->bt_cursor.key.size = 0;
429 t->bt_cursor.key.data = NULL((void*)0);
430 }
431 F_CLR(&t->bt_cursor, CURS_ACQUIRE | CURS_AFTER | CURS_BEFORE)(&t->bt_cursor)->flags &= ~(0x01 | 0x02 | 0x04);
432
433 /* Update the cursor. */
434 t->bt_cursor.pg.pgno = pgno;
435 t->bt_cursor.pg.index = idx;
436 F_SET(&t->bt_cursor, CURS_INIT)(&t->bt_cursor)->flags |= (0x08);
437}