Bug Summary

File:s/lib/dbm/src/h_page.c
Warning:line 1040, column 9
Array access (from variable 'freep') results in a null pointer dereference

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -clear-ast-before-backend -disable-llvm-verifier -discard-value-names -main-file-name h_page.c -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 -analyzer-config-compatibility-mode=true -mrelocation-model pic -pic-level 2 -fhalf-no-semantic-interposition -mframe-pointer=all -fmath-errno -ffp-contract=on -fno-rounding-math -mconstructor-aliases -funwind-tables=2 -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -fdebug-compilation-dir=/var/lib/jenkins/workspace/nss-scan-build/nss/lib/dbm/src -ffunction-sections -fdata-sections -fcoverage-compilation-dir=/var/lib/jenkins/workspace/nss-scan-build/nss/lib/dbm/src -resource-dir /usr/lib/llvm-19/lib/clang/19 -D HAVE_STRERROR -D LINUX -D linux -D XP_UNIX -D XP_UNIX -D DEBUG -U NDEBUG -D _DEFAULT_SOURCE -D _BSD_SOURCE -D _POSIX_SOURCE -D SDB_MEASURE_USE_TEMP_DIR -D _REENTRANT -D DEBUG -U NDEBUG -D _DEFAULT_SOURCE -D _BSD_SOURCE -D _POSIX_SOURCE -D SDB_MEASURE_USE_TEMP_DIR -D _REENTRANT -D NSS_DISABLE_SSE3 -D NSS_NO_INIT_SUPPORT -D USE_UTIL_DIRECTLY -D NO_NSPR_10_SUPPORT -D SSL_DISABLE_DEPRECATED_CIPHER_SUITE_NAMES -D STDC_HEADERS -D HAVE_STRERROR -D HAVE_SNPRINTF -D MEMMOVE -D __DBINTERFACE_PRIVATE -I ../../../../dist/Linux6.12_x86_64_gcc_glibc_PTH_64_DBG.OBJ/include -I ../../../../dist/public/dbm -I ../../../../dist/private/dbm -internal-isystem /usr/lib/llvm-19/lib/clang/19/include -internal-isystem /usr/local/include -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/14/../../../../x86_64-linux-gnu/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -std=c99 -ferror-limit 19 -fgnuc-version=4.2.1 -fskip-odr-check-in-gmf -analyzer-output=html -analyzer-config stable-report-filename=true -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /tmp/scan-build-2025-01-06-222215-268153-1 -x c h_page.c
1/*-
2 * Copyright (c) 1990, 1993, 1994
3 * The Regents of the University of California. All rights reserved.
4 *
5 * This code is derived from software contributed to Berkeley by
6 * Margo Seltzer.
7 *
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
10 * are met:
11 * 1. Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 * 2. Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in the
15 * documentation and/or other materials provided with the distribution.
16 * 3. ***REMOVED*** - see
17 * ftp://ftp.cs.berkeley.edu/pub/4bsd/README.Impt.License.Change
18 * 4. 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#if defined(unix)
36#define MY_LSEEKnew_lseek lseek
37#else
38#define MY_LSEEKnew_lseek new_lseek
39extern long new_lseek(int fd, long pos, int start);
40#endif
41
42#if defined(LIBC_SCCS) && !defined(lint)
43static char sccsid[] = "@(#)hash_page.c 8.7 (Berkeley) 8/16/94";
44#endif /* LIBC_SCCS and not lint */
45
46/*
47 * PACKAGE: hashing
48 *
49 * DESCRIPTION:
50 * Page manipulation for hashing package.
51 *
52 * ROUTINES:
53 *
54 * External
55 * __get_page
56 * __add_ovflpage
57 * Internal
58 * overflow_page
59 * open_temp
60 */
61#ifndef macintosh
62#include <sys/types.h>
63#endif
64
65#if defined(macintosh)
66#include <unistd.h>
67#endif
68
69#include <errno(*__errno_location ()).h>
70#include <fcntl.h>
71#if defined(_WIN32) || defined(_WINDOWS)
72#include <io.h>
73#endif
74#include <signal.h>
75#include <stdio.h>
76#include <stdlib.h>
77#include <string.h>
78
79#if !defined(_WIN32) && !defined(_WINDOWS) && !defined(macintosh)
80#include <unistd.h>
81#endif
82
83#include <assert.h>
84
85#include "mcom_db.h"
86#include "hash.h"
87#include "page.h"
88/* #include "extern.h" */
89
90extern int mkstempflags(char *path, int extraFlags);
91
92static uint32 *fetch_bitmap(HTAB *, uint32);
93static uint32 first_free(uint32);
94static int open_temp(HTAB *);
95static uint16 overflow_page(HTAB *);
96static void squeeze_key(uint16 *, const DBT *, const DBT *);
97static int ugly_split(HTAB *, uint32, BUFHEAD *, BUFHEAD *, int, int);
98
99#define PAGE_INIT(P){ ((uint16 *)(P))[0] = 0; ((uint16 *)(P))[1] = hashp->hdr.
bsize - 3 * sizeof(uint16); ((uint16 *)(P))[2] = hashp->hdr
.bsize; } \
100 { \
101 ((uint16 *)(P))[0] = 0; \
102 ((uint16 *)(P))[1] = hashp->BSIZEhdr.bsize - 3 * sizeof(uint16); \
103 ((uint16 *)(P))[2] = hashp->BSIZEhdr.bsize; \
104 }
105
106/* implement a new lseek using lseek that
107 * writes zero's when extending a file
108 * beyond the end.
109 */
110long
111new_lseek(int fd, long offset, int origin)
112{
113 long cur_pos = 0;
114 long end_pos = 0;
115 long seek_pos = 0;
116
117 if (origin == SEEK_CUR1) {
118 if (offset < 1)
119 return (lseek(fd, offset, SEEK_CUR1));
120
121 cur_pos = lseek(fd, 0, SEEK_CUR1);
122
123 if (cur_pos < 0)
124 return (cur_pos);
125 }
126
127 end_pos = lseek(fd, 0, SEEK_END2);
128 if (end_pos < 0)
129 return (end_pos);
130
131 if (origin == SEEK_SET0)
132 seek_pos = offset;
133 else if (origin == SEEK_CUR1)
134 seek_pos = cur_pos + offset;
135 else if (origin == SEEK_END2)
136 seek_pos = end_pos + offset;
137 else {
138 assert(0)((0) ? (void) (0) : __assert_fail ("0", "h_page.c", 138, __extension__
__PRETTY_FUNCTION__));
139 return (-1);
140 }
141
142 /* the seek position desired is before the
143 * end of the file. We don't need
144 * to do anything special except the seek.
145 */
146 if (seek_pos <= end_pos)
147 return (lseek(fd, seek_pos, SEEK_SET0));
148
149 /* the seek position is beyond the end of the
150 * file. Write zero's to the end.
151 *
152 * we are already at the end of the file so
153 * we just need to "write()" zeros for the
154 * difference between seek_pos-end_pos and
155 * then seek to the position to finish
156 * the call
157 */
158 {
159 char buffer[1024];
160 long len = seek_pos - end_pos;
161 memset(buffer, 0, 1024);
162 while (len > 0) {
163 if (write(fd, buffer, (size_t)(1024 > len ? len : 1024)) < 0)
164 return (-1);
165 len -= 1024;
166 }
167 return (lseek(fd, seek_pos, SEEK_SET0));
168 }
169}
170
171/*
172 * This is called AFTER we have verified that there is room on the page for
173 * the pair (PAIRFITS has returned true) so we go right ahead and start moving
174 * stuff on.
175 */
176static void
177putpair(char *p, const DBT *key, DBT *val)
178{
179 register uint16 *bp, n, off;
180
181 bp = (uint16 *)p;
182
183 /* Enter the key first. */
184 n = bp[0];
185
186 off = OFFSET(bp)((bp)[(bp)[0] + 2]) - key->size;
187 memmove(p + off, key->data, key->size);
188 bp[++n] = off;
189
190 /* Now the data. */
191 off -= val->size;
192 memmove(p + off, val->data, val->size);
193 bp[++n] = off;
194
195 /* Adjust page info. */
196 bp[0] = n;
197 bp[n + 1] = off - ((n + 3) * sizeof(uint16));
198 bp[n + 2] = off;
199}
200
201/*
202 * Returns:
203 * 0 OK
204 * -1 error
205 */
206extern int
207dbm_delpair(HTAB *hashp, BUFHEAD *bufp, int ndx)
208{
209 register uint16 *bp, newoff;
210 register int n;
211 uint16 pairlen;
212
213 bp = (uint16 *)bufp->page;
214 n = bp[0];
215
216 if (bp[ndx + 1] < REAL_KEY4)
217 return (dbm_big_delete(hashp, bufp));
218 if (ndx != 1)
219 newoff = bp[ndx - 1];
220 else
221 newoff = hashp->BSIZEhdr.bsize;
222 pairlen = newoff - bp[ndx + 1];
223
224 if (ndx != (n - 1)) {
225 /* Hard Case -- need to shuffle keys */
226 register int i;
227 register char *src = bufp->page + (int)OFFSET(bp)((bp)[(bp)[0] + 2]);
228 uint32 dst_offset = (uint32)OFFSET(bp)((bp)[(bp)[0] + 2]) + (uint32)pairlen;
229 register char *dst = bufp->page + dst_offset;
230 uint32 length = bp[ndx + 1] - OFFSET(bp)((bp)[(bp)[0] + 2]);
231
232 /*
233 * +-----------+XXX+---------+XXX+---------+---------> +infinity
234 * | | | |
235 * 0 src_offset dst_offset BSIZE
236 *
237 * Dst_offset is > src_offset, so if src_offset were bad, dst_offset
238 * would be too, therefore we check only dst_offset.
239 *
240 * If dst_offset is >= BSIZE, either OFFSET(bp), or pairlen, or both
241 * is corrupted.
242 *
243 * Once we know dst_offset is < BSIZE, we can subtract it from BSIZE
244 * to get an upper bound on length.
245 */
246 if (dst_offset > (uint32)hashp->BSIZEhdr.bsize)
247 return (DATABASE_CORRUPTED_ERROR-999);
248
249 if (length > (uint32)(hashp->BSIZEhdr.bsize - dst_offset))
250 return (DATABASE_CORRUPTED_ERROR-999);
251
252 memmove(dst, src, length);
253
254 /* Now adjust the pointers */
255 for (i = ndx + 2; i <= n; i += 2) {
256 if (bp[i + 1] == OVFLPAGE0) {
257 bp[i - 2] = bp[i];
258 bp[i - 1] = bp[i + 1];
259 } else {
260 bp[i - 2] = bp[i] + pairlen;
261 bp[i - 1] = bp[i + 1] + pairlen;
262 }
263 }
264 }
265 /* Finally adjust the page data */
266 bp[n] = OFFSET(bp)((bp)[(bp)[0] + 2]) + pairlen;
267 bp[n - 1] = bp[n + 1] + pairlen + 2 * sizeof(uint16);
268 bp[0] = n - 2;
269 hashp->NKEYShdr.nkeys--;
270
271 bufp->flags |= BUF_MOD0x0001;
272 return (0);
273}
274/*
275 * Returns:
276 * 0 ==> OK
277 * -1 ==> Error
278 */
279extern int
280dbm_split_page(HTAB *hashp, uint32 obucket, uint32 nbucket)
281{
282 register BUFHEAD *new_bufp, *old_bufp;
283 register uint16 *ino;
284 register uint16 *tmp_uint16_array;
285 register char *np;
286 DBT key, val;
287 uint16 n, ndx;
288 int retval;
289 uint16 copyto, diff, moved;
290 size_t off;
291 char *op;
292
293 copyto = (uint16)hashp->BSIZEhdr.bsize;
294 off = (uint16)hashp->BSIZEhdr.bsize;
295 old_bufp = dbm_get_buf(hashp, obucket, NULL((void*)0), 0);
296 if (old_bufp == NULL((void*)0))
297 return (-1);
298 new_bufp = dbm_get_buf(hashp, nbucket, NULL((void*)0), 0);
299 if (new_bufp == NULL((void*)0))
300 return (-1);
301
302 old_bufp->flags |= (BUF_MOD0x0001 | BUF_PIN0x0008);
303 new_bufp->flags |= (BUF_MOD0x0001 | BUF_PIN0x0008);
304
305 ino = (uint16 *)(op = old_bufp->page);
306 np = new_bufp->page;
307
308 moved = 0;
309
310 for (n = 1, ndx = 1; n < ino[0]; n += 2) {
311 if (ino[n + 1] < REAL_KEY4) {
312 retval = ugly_split(hashp, obucket, old_bufp, new_bufp,
313 (int)copyto, (int)moved);
314 old_bufp->flags &= ~BUF_PIN0x0008;
315 new_bufp->flags &= ~BUF_PIN0x0008;
316 return (retval);
317 }
318 key.data = (uint8 *)op + ino[n];
319
320 /* check here for ino[n] being greater than
321 * off. If it is then the database has
322 * been corrupted.
323 */
324 if (ino[n] > off)
325 return (DATABASE_CORRUPTED_ERROR-999);
326
327 key.size = off - ino[n];
328
329#ifdef DEBUG1
330 /* make sure the size is positive */
331 assert(((int)key.size) > -1)((((int)key.size) > -1) ? (void) (0) : __assert_fail ("((int)key.size) > -1"
, "h_page.c", 331, __extension__ __PRETTY_FUNCTION__));
332#endif
333
334 if (dbm_call_hash(hashp, (char *)key.data, key.size) == obucket) {
335 /* Don't switch page */
336 diff = copyto - off;
337 if (diff) {
338 copyto = ino[n + 1] + diff;
339 memmove(op + copyto, op + ino[n + 1],
340 off - ino[n + 1]);
341 ino[ndx] = copyto + ino[n] - ino[n + 1];
342 ino[ndx + 1] = copyto;
343 } else
344 copyto = ino[n + 1];
345 ndx += 2;
346 } else {
347 /* Switch page */
348 val.data = (uint8 *)op + ino[n + 1];
349 val.size = ino[n] - ino[n + 1];
350
351 /* if the pair doesn't fit something is horribly
352 * wrong. LJM
353 */
354 tmp_uint16_array = (uint16 *)np;
355 if (!PAIRFITS(tmp_uint16_array, &key, &val)(((tmp_uint16_array)[2] >= 4) && ((2 * sizeof(uint16
) + ((&key))->size + ((&val))->size) + (2 * sizeof
(uint16))) <= (((tmp_uint16_array))[((tmp_uint16_array))[0
] + 1])))
356 return (DATABASE_CORRUPTED_ERROR-999);
357
358 putpair(np, &key, &val);
359 moved += 2;
360 }
361
362 off = ino[n + 1];
363 }
364
365 /* Now clean up the page */
366 ino[0] -= moved;
367 FREESPACE(ino)((ino)[(ino)[0] + 1]) = copyto - sizeof(uint16) * (ino[0] + 3);
368 OFFSET(ino)((ino)[(ino)[0] + 2]) = copyto;
369
370#ifdef DEBUG3
371 (void)fprintf(stderrstderr, "split %d/%d\n",
372 ((uint16 *)np)[0] / 2,
373 ((uint16 *)op)[0] / 2);
374#endif
375 /* unpin both pages */
376 old_bufp->flags &= ~BUF_PIN0x0008;
377 new_bufp->flags &= ~BUF_PIN0x0008;
378 return (0);
379}
380
381/*
382 * Called when we encounter an overflow or big key/data page during split
383 * handling. This is special cased since we have to begin checking whether
384 * the key/data pairs fit on their respective pages and because we may need
385 * overflow pages for both the old and new pages.
386 *
387 * The first page might be a page with regular key/data pairs in which case
388 * we have a regular overflow condition and just need to go on to the next
389 * page or it might be a big key/data pair in which case we need to fix the
390 * big key/data pair.
391 *
392 * Returns:
393 * 0 ==> success
394 * -1 ==> failure
395 */
396
397/* the maximum number of loops we will allow UGLY split to chew
398 * on before we assume the database is corrupted and throw it
399 * away.
400 */
401#define MAX_UGLY_SPLIT_LOOPS10000 10000
402
403static int
404ugly_split(HTAB *hashp, uint32 obucket, BUFHEAD *old_bufp,
405 BUFHEAD *new_bufp, /* Same as __split_page. */ int copyto, int moved)
406/* int copyto; First byte on page which contains key/data values. */
407/* int moved; Number of pairs moved to new page. */
408{
409 register BUFHEAD *bufp; /* Buffer header for ino */
410 register uint16 *ino; /* Page keys come off of */
411 register uint16 *np; /* New page */
412 register uint16 *op; /* Page keys go on to if they aren't moving */
413 uint32 loop_detection = 0;
414
415 BUFHEAD *last_bfp; /* Last buf header OVFL needing to be freed */
416 DBT key, val;
417 SPLIT_RETURN ret;
418 uint16 n, off, ov_addr, scopyto;
419 char *cino; /* Character value of ino */
420 int status;
421
422 bufp = old_bufp;
423 ino = (uint16 *)old_bufp->page;
424 np = (uint16 *)new_bufp->page;
425 op = (uint16 *)old_bufp->page;
426 last_bfp = NULL((void*)0);
427 scopyto = (uint16)copyto; /* ANSI */
428
429 if (ino[0] < 1) {
430 return DATABASE_CORRUPTED_ERROR-999;
431 }
432 n = ino[0] - 1;
433 while (n < ino[0]) {
434
435 /* this function goes nuts sometimes and never returns.
436 * I havent found the problem yet but I need a solution
437 * so if we loop too often we assume a database curruption error
438 * :LJM
439 */
440 loop_detection++;
441
442 if (loop_detection > MAX_UGLY_SPLIT_LOOPS10000)
443 return DATABASE_CORRUPTED_ERROR-999;
444
445 if (ino[2] < REAL_KEY4 && ino[2] != OVFLPAGE0) {
446 if ((status = dbm_big_split(hashp, old_bufp,
447 new_bufp, bufp, bufp->addr, obucket, &ret)))
448 return (status);
449 old_bufp = ret.oldp;
450 if (!old_bufp)
451 return (-1);
452 op = (uint16 *)old_bufp->page;
453 new_bufp = ret.newp;
454 if (!new_bufp)
455 return (-1);
456 np = (uint16 *)new_bufp->page;
457 bufp = ret.nextp;
458 if (!bufp)
459 return (0);
460 cino = (char *)bufp->page;
461 ino = (uint16 *)cino;
462 last_bfp = ret.nextp;
463 } else if (ino[n + 1] == OVFLPAGE0) {
464 ov_addr = ino[n];
465 /*
466 * Fix up the old page -- the extra 2 are the fields
467 * which contained the overflow information.
468 */
469 if (ino[0] < (moved + 2)) {
470 return DATABASE_CORRUPTED_ERROR-999;
471 }
472 ino[0] -= (moved + 2);
473 if (scopyto < sizeof(uint16) * (ino[0] + 3)) {
474 return DATABASE_CORRUPTED_ERROR-999;
475 }
476 FREESPACE(ino)((ino)[(ino)[0] + 1]) =
477 scopyto - sizeof(uint16) * (ino[0] + 3);
478 OFFSET(ino)((ino)[(ino)[0] + 2]) = scopyto;
479
480 bufp = dbm_get_buf(hashp, ov_addr, bufp, 0);
481 if (!bufp)
482 return (-1);
483
484 ino = (uint16 *)bufp->page;
485 n = 1;
486 scopyto = hashp->BSIZEhdr.bsize;
487 moved = 0;
488
489 if (last_bfp)
490 dbm_free_ovflpage(hashp, last_bfp);
491 last_bfp = bufp;
492 }
493 /* Move regular sized pairs of there are any */
494 off = hashp->BSIZEhdr.bsize;
495 for (n = 1; (n < ino[0]) && (ino[n + 1] >= REAL_KEY4); n += 2) {
496 cino = (char *)ino;
497 key.data = (uint8 *)cino + ino[n];
498 if (off < ino[n]) {
499 return DATABASE_CORRUPTED_ERROR-999;
500 }
501 key.size = off - ino[n];
502 val.data = (uint8 *)cino + ino[n + 1];
503 if (ino[n] < ino[n + 1]) {
504 return DATABASE_CORRUPTED_ERROR-999;
505 }
506 val.size = ino[n] - ino[n + 1];
507 off = ino[n + 1];
508
509 if (dbm_call_hash(hashp, (char *)key.data, key.size) == obucket) {
510 /* Keep on old page */
511 if (PAIRFITS(op, (&key), (&val))(((op)[2] >= 4) && ((2 * sizeof(uint16) + (((&
key)))->size + (((&val)))->size) + (2 * sizeof(uint16
))) <= (((op))[((op))[0] + 1])))
512 putpair((char *)op, &key, &val);
513 else {
514 old_bufp =
515 dbm_add_ovflpage(hashp, old_bufp);
516 if (!old_bufp)
517 return (-1);
518 op = (uint16 *)old_bufp->page;
519 putpair((char *)op, &key, &val);
520 }
521 old_bufp->flags |= BUF_MOD0x0001;
522 } else {
523 /* Move to new page */
524 if (PAIRFITS(np, (&key), (&val))(((np)[2] >= 4) && ((2 * sizeof(uint16) + (((&
key)))->size + (((&val)))->size) + (2 * sizeof(uint16
))) <= (((np))[((np))[0] + 1])))
525 putpair((char *)np, &key, &val);
526 else {
527 new_bufp =
528 dbm_add_ovflpage(hashp, new_bufp);
529 if (!new_bufp)
530 return (-1);
531 np = (uint16 *)new_bufp->page;
532 putpair((char *)np, &key, &val);
533 }
534 new_bufp->flags |= BUF_MOD0x0001;
535 }
536 }
537 }
538 if (last_bfp)
539 dbm_free_ovflpage(hashp, last_bfp);
540 return (0);
541}
542
543/*
544 * Add the given pair to the page
545 *
546 * Returns:
547 * 0 ==> OK
548 * 1 ==> failure
549 */
550extern int
551dbm_addel(HTAB *hashp, BUFHEAD *bufp, const DBT *key, const DBT *val)
552{
553 register uint16 *bp, *sop;
554 int do_expand;
555
556 bp = (uint16 *)bufp->page;
557 do_expand = 0;
558 while (bp[0] && (bp[2] < REAL_KEY4 || bp[bp[0]] < REAL_KEY4))
1
Assuming the condition is false
→
559 /* Exception case */
560 if (bp[2] == FULL_KEY_DATA3 && bp[0] == 2)
561 /* This is the last page of a big key/data pair
562 and we need to add another page */
563 break;
564 else if (bp[2] < REAL_KEY4 && bp[bp[0]] != OVFLPAGE0) {
565 bufp = dbm_get_buf(hashp, bp[bp[0] - 1], bufp, 0);
566 if (!bufp) {
567#ifdef DEBUG1
568 assert(0)((0) ? (void) (0) : __assert_fail ("0", "h_page.c", 568, __extension__
__PRETTY_FUNCTION__));
569#endif
570 return (-1);
571 }
572 bp = (uint16 *)bufp->page;
573 } else
574 /* Try to squeeze key on this page */
575 if (FREESPACE(bp)((bp)[(bp)[0] + 1]) > PAIRSIZE(key, val)(2 * sizeof(uint16) + (key)->size + (val)->size)) {
576 {
577 squeeze_key(bp, key, val);
578
579 /* LJM: I added this because I think it was
580 * left out on accident.
581 * if this isn't incremented nkeys will not
582 * be the actual number of keys in the db.
583 */
584 hashp->NKEYShdr.nkeys++;
585 return (0);
586 }
587 } else {
588 bufp = dbm_get_buf(hashp, bp[bp[0] - 1], bufp, 0);
589 if (!bufp) {
590#ifdef DEBUG1
591 assert(0)((0) ? (void) (0) : __assert_fail ("0", "h_page.c", 591, __extension__
__PRETTY_FUNCTION__));
592#endif
593 return (-1);
594 }
595 bp = (uint16 *)bufp->page;
596 }
597
598 if (PAIRFITS(bp, key, val)(((bp)[2] >= 4) && ((2 * sizeof(uint16) + ((key))->
size + ((val))->size) + (2 * sizeof(uint16))) <= (((bp)
)[((bp))[0] + 1])))
2
←
Assuming the condition is false
→
599 putpair(bufp->page, key, (DBT *)val);
600 else {
601 do_expand = 1;
602 bufp = dbm_add_ovflpage(hashp, bufp);
3
←
Calling 'dbm_add_ovflpage'
→
603 if (!bufp) {
604#ifdef DEBUG1
605 assert(0)((0) ? (void) (0) : __assert_fail ("0", "h_page.c", 605, __extension__
__PRETTY_FUNCTION__));
606#endif
607 return (-1);
608 }
609 sop = (uint16 *)bufp->page;
610
611 if (PAIRFITS(sop, key, val)(((sop)[2] >= 4) && ((2 * sizeof(uint16) + ((key))
->size + ((val))->size) + (2 * sizeof(uint16))) <= (
((sop))[((sop))[0] + 1])))
612 putpair((char *)sop, key, (DBT *)val);
613 else if (dbm_big_insert(hashp, bufp, key, val)) {
614#ifdef DEBUG1
615 assert(0)((0) ? (void) (0) : __assert_fail ("0", "h_page.c", 615, __extension__
__PRETTY_FUNCTION__));
616#endif
617 return (-1);
618 }
619 }
620 bufp->flags |= BUF_MOD0x0001;
621 /*
622 * If the average number of keys per bucket exceeds the fill factor,
623 * expand the table.
624 */
625 hashp->NKEYShdr.nkeys++;
626 if (do_expand ||
627 (hashp->NKEYShdr.nkeys / (hashp->MAX_BUCKEThdr.max_bucket + 1) > hashp->FFACTORhdr.ffactor))
628 return (dbm_expand_table(hashp));
629 return (0);
630}
631
632/*
633 *
634 * Returns:
635 * pointer on success
636 * NULL on error
637 */
638extern BUFHEAD *
639dbm_add_ovflpage(HTAB *hashp, BUFHEAD *bufp)
640{
641 register uint16 *sp;
642 uint16 ndx, ovfl_num;
643#ifdef DEBUG1
644 int tmp1, tmp2;
645#endif
646 sp = (uint16 *)bufp->page;
647
648 /* Check if we are dynamically determining the fill factor */
649 if (hashp->FFACTORhdr.ffactor == DEF_FFACTOR65536l) {
4
←
Assuming field 'ffactor' is not equal to DEF_FFACTOR
→
5
←
Taking false branch
→
650 hashp->FFACTORhdr.ffactor = sp[0] >> 1;
651 if (hashp->FFACTORhdr.ffactor < MIN_FFACTOR4)
652 hashp->FFACTORhdr.ffactor = MIN_FFACTOR4;
653 }
654 bufp->flags |= BUF_MOD0x0001;
655 ovfl_num = overflow_page(hashp);
6
←
Calling 'overflow_page'
→
656#ifdef DEBUG1
657 tmp1 = bufp->addr;
658 tmp2 = bufp->ovfl ? bufp->ovfl->addr : 0;
659#endif
660 if (!ovfl_num || !(bufp->ovfl = dbm_get_buf(hashp, ovfl_num, bufp, 1)))
661 return (NULL((void*)0));
662 bufp->ovfl->flags |= BUF_MOD0x0001;
663#ifdef DEBUG1
664 (void)fprintf(stderrstderr, "ADDOVFLPAGE: %d->ovfl was %d is now %d\n",
665 tmp1, tmp2, bufp->ovfl->addr);
666#endif
667 ndx = sp[0];
668 /*
669 * Since a pair is allocated on a page only if there's room to add
670 * an overflow page, we know that the OVFL information will fit on
671 * the page.
672 */
673 sp[ndx + 4] = OFFSET(sp)((sp)[(sp)[0] + 2]);
674 sp[ndx + 3] = FREESPACE(sp)((sp)[(sp)[0] + 1]) - OVFLSIZE(2 * sizeof(uint16));
675 sp[ndx + 1] = ovfl_num;
676 sp[ndx + 2] = OVFLPAGE0;
677 sp[0] = ndx + 2;
678#ifdef HASH_STATISTICS
679 hash_overflows++;
680#endif
681 return (bufp->ovfl);
682}
683
684/*
685 * Returns:
686 * 0 indicates SUCCESS
687 * -1 indicates FAILURE
688 */
689extern int
690dbm_get_page(HTAB *hashp,
691 char *p,
692 uint32 bucket,
693 int is_bucket,
694 int is_disk,
695 int is_bitmap)
696{
697 register int fd, page;
698 size_t size;
699 int rsize;
700 uint16 *bp;
701
702 fd = hashp->fp;
703 size = hashp->BSIZEhdr.bsize;
704
705 if ((fd == -1) || !is_disk) {
706 PAGE_INIT(p){ ((uint16 *)(p))[0] = 0; ((uint16 *)(p))[1] = hashp->hdr.
bsize - 3 * sizeof(uint16); ((uint16 *)(p))[2] = hashp->hdr
.bsize; };
707 return (0);
708 }
709 if (is_bucket)
710 page = BUCKET_TO_PAGE(bucket)(bucket) + hashp->hdr.hdrpages + ((bucket) ? hashp->hdr
.spares[dbm_log2((uint32)((bucket) + 1)) - 1] : 0);
711 else
712 page = OADDR_TO_PAGE(bucket)((1 << (((uint32)((bucket))) >> 11)) - 1) + hashp
->hdr.hdrpages + (((1 << (((uint32)((bucket))) >>
11)) - 1) ? hashp->hdr.spares[dbm_log2((uint32)(((1 <<
(((uint32)((bucket))) >> 11)) - 1) + 1)) - 1] : 0) + (
((bucket))&0x7FF);;
713 if ((MY_LSEEKnew_lseek(fd, (off_t)page << hashp->BSHIFThdr.bshift, SEEK_SET0) == -1) ||
714 ((rsize = read(fd, p, size)) == -1))
715 return (-1);
716
717 bp = (uint16 *)p;
718 if (!rsize)
719 bp[0] = 0; /* We hit the EOF, so initialize a new page */
720 else if ((unsigned)rsize != size) {
721 errno(*__errno_location ()) = EFTYPE22;
722 return (-1);
723 }
724
725 if (!is_bitmap && !bp[0]) {
726 PAGE_INIT(p){ ((uint16 *)(p))[0] = 0; ((uint16 *)(p))[1] = hashp->hdr.
bsize - 3 * sizeof(uint16); ((uint16 *)(p))[2] = hashp->hdr
.bsize; };
727 } else {
728
729 if (hashp->LORDERhdr.lorder != BYTE_ORDER1234) {
730 register int i, max;
731
732 if (is_bitmap) {
733 max = hashp->BSIZEhdr.bsize >> 2; /* divide by 4 */
734 for (i = 0; i < max; i++)
735 M_32_SWAP(((int *)p)[i]){ uint32 _tmp = ((int *)p)[i]; ((char *)&((int *)p)[i])[0
] = ((char *)&_tmp)[3]; ((char *)&((int *)p)[i])[1] =
((char *)&_tmp)[2]; ((char *)&((int *)p)[i])[2] = ((
char *)&_tmp)[1]; ((char *)&((int *)p)[i])[3] = ((char
*)&_tmp)[0]; };
736 } else {
737 M_16_SWAP(bp[0]){ uint16 _tmp = bp[0]; ((char *)&bp[0])[0] = ((char *)&
_tmp)[1]; ((char *)&bp[0])[1] = ((char *)&_tmp)[0]; };
738 max = bp[0] + 2;
739
740 /* bound the size of max by
741 * the maximum number of entries
742 * in the array
743 */
744 if ((unsigned)max > (size / sizeof(uint16)))
745 return (DATABASE_CORRUPTED_ERROR-999);
746
747 /* do the byte order swap
748 */
749 for (i = 1; i <= max; i++)
750 M_16_SWAP(bp[i]){ uint16 _tmp = bp[i]; ((char *)&bp[i])[0] = ((char *)&
_tmp)[1]; ((char *)&bp[i])[1] = ((char *)&_tmp)[0]; };
751 }
752 }
753
754 /* check the validity of the page here
755 * (after doing byte order swaping if necessary)
756 */
757 if (!is_bitmap && bp[0] != 0) {
758 uint16 num_keys = bp[0];
759 uint16 offset;
760 uint16 i;
761
762 /* bp[0] is supposed to be the number of
763 * entries currently in the page. If
764 * bp[0] is too large (larger than the whole
765 * page) then the page is corrupted
766 */
767 if (bp[0] > (size / sizeof(uint16)))
768 return (DATABASE_CORRUPTED_ERROR-999);
769
770 /* bound free space */
771 if (FREESPACE(bp)((bp)[(bp)[0] + 1]) > size)
772 return (DATABASE_CORRUPTED_ERROR-999);
773
774 /* check each key and data offset to make
775 * sure they are all within bounds they
776 * should all be less than the previous
777 * offset as well.
778 */
779 offset = size;
780 for (i = 1; i <= num_keys; i += 2) {
781 /* ignore overflow pages etc. */
782 if (bp[i + 1] >= REAL_KEY4) {
783
784 if (bp[i] > offset || bp[i + 1] > bp[i])
785 return (DATABASE_CORRUPTED_ERROR-999);
786
787 offset = bp[i + 1];
788 } else {
789 /* there are no other valid keys after
790 * seeing a non REAL_KEY
791 */
792 break;
793 }
794 }
795 }
796 }
797 return (0);
798}
799
800/*
801 * Write page p to disk
802 *
803 * Returns:
804 * 0 ==> OK
805 * -1 ==>failure
806 */
807extern int
808dbm_put_page(HTAB *hashp, char *p, uint32 bucket, int is_bucket, int is_bitmap)
809{
810 register int fd, page;
811 size_t size;
812 int wsize;
813 off_t offset;
814
815 size = hashp->BSIZEhdr.bsize;
816 if ((hashp->fp == -1) && open_temp(hashp))
817 return (-1);
818 fd = hashp->fp;
819
820 if (hashp->LORDERhdr.lorder != BYTE_ORDER1234) {
821 register int i;
822 register int max;
823
824 if (is_bitmap) {
825 max = hashp->BSIZEhdr.bsize >> 2; /* divide by 4 */
826 for (i = 0; i < max; i++)
827 M_32_SWAP(((int *)p)[i]){ uint32 _tmp = ((int *)p)[i]; ((char *)&((int *)p)[i])[0
] = ((char *)&_tmp)[3]; ((char *)&((int *)p)[i])[1] =
((char *)&_tmp)[2]; ((char *)&((int *)p)[i])[2] = ((
char *)&_tmp)[1]; ((char *)&((int *)p)[i])[3] = ((char
*)&_tmp)[0]; };
828 } else {
829 max = ((uint16 *)p)[0] + 2;
830
831 /* bound the size of max by
832 * the maximum number of entries
833 * in the array
834 */
835 if ((unsigned)max > (size / sizeof(uint16)))
836 return (DATABASE_CORRUPTED_ERROR-999);
837
838 for (i = 0; i <= max; i++)
839 M_16_SWAP(((uint16 *)p)[i]){ uint16 _tmp = ((uint16 *)p)[i]; ((char *)&((uint16 *)p)
[i])[0] = ((char *)&_tmp)[1]; ((char *)&((uint16 *)p)
[i])[1] = ((char *)&_tmp)[0]; };
840 }
841 }
842
843 if (is_bucket)
844 page = BUCKET_TO_PAGE(bucket)(bucket) + hashp->hdr.hdrpages + ((bucket) ? hashp->hdr
.spares[dbm_log2((uint32)((bucket) + 1)) - 1] : 0);
845 else
846 page = OADDR_TO_PAGE(bucket)((1 << (((uint32)((bucket))) >> 11)) - 1) + hashp
->hdr.hdrpages + (((1 << (((uint32)((bucket))) >>
11)) - 1) ? hashp->hdr.spares[dbm_log2((uint32)(((1 <<
(((uint32)((bucket))) >> 11)) - 1) + 1)) - 1] : 0) + (
((bucket))&0x7FF);;
847 offset = (off_t)page << hashp->BSHIFThdr.bshift;
848 if ((MY_LSEEKnew_lseek(fd, offset, SEEK_SET0) == -1) ||
849 ((wsize = write(fd, p, size)) == -1))
850 /* Errno is set */
851 return (-1);
852 if ((unsigned)wsize != size) {
853 errno(*__errno_location ()) = EFTYPE22;
854 return (-1);
855 }
856#if defined(_WIN32) || defined(_WINDOWS)
857 if (offset + size > hashp->file_size) {
858 hashp->updateEOF = 1;
859 }
860#endif
861 /* put the page back the way it was so that it isn't byteswapped
862 * if it remains in memory - LJM
863 */
864 if (hashp->LORDERhdr.lorder != BYTE_ORDER1234) {
865 register int i;
866 register int max;
867
868 if (is_bitmap) {
869 max = hashp->BSIZEhdr.bsize >> 2; /* divide by 4 */
870 for (i = 0; i < max; i++)
871 M_32_SWAP(((int *)p)[i]){ uint32 _tmp = ((int *)p)[i]; ((char *)&((int *)p)[i])[0
] = ((char *)&_tmp)[3]; ((char *)&((int *)p)[i])[1] =
((char *)&_tmp)[2]; ((char *)&((int *)p)[i])[2] = ((
char *)&_tmp)[1]; ((char *)&((int *)p)[i])[3] = ((char
*)&_tmp)[0]; };
872 } else {
873 uint16 *bp = (uint16 *)p;
874
875 M_16_SWAP(bp[0]){ uint16 _tmp = bp[0]; ((char *)&bp[0])[0] = ((char *)&
_tmp)[1]; ((char *)&bp[0])[1] = ((char *)&_tmp)[0]; };
876 max = bp[0] + 2;
877
878 /* no need to bound the size if max again
879 * since it was done already above
880 */
881
882 /* do the byte order re-swap
883 */
884 for (i = 1; i <= max; i++)
885 M_16_SWAP(bp[i]){ uint16 _tmp = bp[i]; ((char *)&bp[i])[0] = ((char *)&
_tmp)[1]; ((char *)&bp[i])[1] = ((char *)&_tmp)[0]; };
886 }
887 }
888
889 return (0);
890}
891
892#define BYTE_MASK((1 << 5) - 1) ((1 << INT_BYTE_SHIFT5) - 1)
893/*
894 * Initialize a new bitmap page. Bitmap pages are left in memory
895 * once they are read in.
896 */
897extern int
898dbm_ibitmap(HTAB *hashp, int pnum, int nbits, int ndx)
899{
900 uint32 *ip;
901 size_t clearbytes, clearints;
902
903 if ((ip = (uint32 *)malloc((size_t)hashp->BSIZEhdr.bsize)) == NULL((void*)0))
904 return (1);
905 hashp->nmaps++;
906 clearints = ((nbits - 1) >> INT_BYTE_SHIFT5) + 1;
907 clearbytes = clearints << INT_TO_BYTE2;
908 (void)memset((char *)ip, 0, clearbytes);
909 (void)memset(((char *)ip) + clearbytes, 0xFF,
910 hashp->BSIZEhdr.bsize - clearbytes);
911 ip[clearints - 1] = ALL_SET((uint32)0xFFFFFFFF) << (nbits & BYTE_MASK((1 << 5) - 1));
912 SETBIT(ip, 0)((ip)[(0) / 32] |= (1 << ((0) % 32)));
913 hashp->BITMAPShdr.bitmaps[ndx] = (uint16)pnum;
914 hashp->mapp[ndx] = ip;
915 return (0);
916}
917
918static uint32
919first_free(uint32 map)
920{
921 register uint32 i, mask;
922
923 mask = 0x1;
924 for (i = 0; i < BITS_PER_MAP32; i++) {
925 if (!(mask & map))
926 return (i);
927 mask = mask << 1;
928 }
929 return (i);
930}
931
932static uint16
933overflow_page(HTAB *hashp)
934{
935 register uint32 *freep = NULL((void*)0);
7
←
'freep' initialized to a null pointer value
→
936 register int max_free, offset, splitnum;
937 uint16 addr;
938 uint32 i;
939 int bit, first_page, free_bit, free_page, in_use_bits, j;
940#ifdef DEBUG2
941 int tmp1, tmp2;
942#endif
943 splitnum = hashp->OVFL_POINThdr.ovfl_point;
944 max_free = hashp->SPAREShdr.spares[splitnum];
945
946 free_page = (max_free - 1) >> (hashp->BSHIFThdr.bshift + BYTE_SHIFT3);
8
←
Assuming right operand of bit shift is non-negative but less than 32
→
947 free_bit = (max_free - 1) & ((hashp->BSIZEhdr.bsize << BYTE_SHIFT3) - 1);
948
949 /* Look through all the free maps to find the first free block */
950 first_page = hashp->LAST_FREEDhdr.last_freed >> (hashp->BSHIFThdr.bshift + BYTE_SHIFT3);
951 for (i = first_page; i <= (unsigned)free_page; i++) {
9
←
Assuming 'i' is > 'free_page'
→
10
←
Loop condition is false. Execution continues on line 975
→
952 if (!(freep = (uint32 *)hashp->mapp[i]) &&
953 !(freep = fetch_bitmap(hashp, i)))
954 return (0);
955 if (i == (unsigned)free_page)
956 in_use_bits = free_bit;
957 else
958 in_use_bits = (hashp->BSIZEhdr.bsize << BYTE_SHIFT3) - 1;
959
960 if (i == (unsigned)first_page) {
961 bit = hashp->LAST_FREEDhdr.last_freed &
962 ((hashp->BSIZEhdr.bsize << BYTE_SHIFT3) - 1);
963 j = bit / BITS_PER_MAP32;
964 bit = bit & ~(BITS_PER_MAP32 - 1);
965 } else {
966 bit = 0;
967 j = 0;
968 }
969 for (; bit <= in_use_bits; j++, bit += BITS_PER_MAP32)
970 if (freep[j] != ALL_SET((uint32)0xFFFFFFFF))
971 goto found;
972 }
973
974 /* No Free Page Found */
975 hashp->LAST_FREEDhdr.last_freed = hashp->SPAREShdr.spares[splitnum];
976 hashp->SPAREShdr.spares[splitnum]++;
977 offset = hashp->SPAREShdr.spares[splitnum] -
978 (splitnum ? hashp->SPAREShdr.spares[splitnum - 1] : 0);
11
←
Assuming 'splitnum' is 0
→
12
←
'?' condition is false
→
979
980#define OVMSG"HASH: Out of overflow pages. Increase page size\n" "HASH: Out of overflow pages. Increase page size\n"
981 if (offset > SPLITMASK0x7FF) {
13
←
Assuming 'offset' is <= SPLITMASK
→
14
←
Taking false branch
→
982 if (++splitnum >= NCACHED32) {
983#ifndef macintosh
984 (void)fwrite(OVMSG"HASH: Out of overflow pages. Increase page size\n", 1, sizeof(OVMSG"HASH: Out of overflow pages. Increase page size\n") - 1, stderrstderr);
985#endif
986 return (0);
987 }
988 hashp->OVFL_POINThdr.ovfl_point = splitnum;
989 hashp->SPAREShdr.spares[splitnum] = hashp->SPAREShdr.spares[splitnum - 1];
990 hashp->SPAREShdr.spares[splitnum - 1]--;
991 offset = 1;
992 }
993
994 /* Check if we need to allocate a new bitmap page */
995 if (free_bit == (hashp->BSIZEhdr.bsize << BYTE_SHIFT3) - 1) {
15
←
Assuming the condition is false
→
16
←
Taking false branch
→
996 free_page++;
997 if (free_page >= NCACHED32) {
998#ifndef macintosh
999 (void)fwrite(OVMSG"HASH: Out of overflow pages. Increase page size\n", 1, sizeof(OVMSG"HASH: Out of overflow pages. Increase page size\n") - 1, stderrstderr);
1000#endif
1001 return (0);
1002 }
1003 /*
1004 * This is tricky. The 1 indicates that you want the new page
1005 * allocated with 1 clear bit. Actually, you are going to
1006 * allocate 2 pages from this map. The first is going to be
1007 * the map page, the second is the overflow page we were
1008 * looking for. The init_bitmap routine automatically, sets
1009 * the first bit of itself to indicate that the bitmap itself
1010 * is in use. We would explicitly set the second bit, but
1011 * don't have to if we tell init_bitmap not to leave it clear
1012 * in the first place.
1013 */
1014 if (dbm_ibitmap(hashp,
1015 (int)OADDR_OF(splitnum, offset)((uint32)((uint32)(splitnum) << 11) + (offset)), 1, free_page))
1016 return (0);
1017 hashp->SPAREShdr.spares[splitnum]++;
1018#ifdef DEBUG2
1019 free_bit = 2;
1020#endif
1021 offset++;
1022 if (offset > SPLITMASK0x7FF) {
1023 if (++splitnum >= NCACHED32) {
1024#ifndef macintosh
1025 (void)fwrite(OVMSG"HASH: Out of overflow pages. Increase page size\n", 1, sizeof(OVMSG"HASH: Out of overflow pages. Increase page size\n") - 1, stderrstderr);
1026#endif
1027 return (0);
1028 }
1029 hashp->OVFL_POINThdr.ovfl_point = splitnum;
1030 hashp->SPAREShdr.spares[splitnum] = hashp->SPAREShdr.spares[splitnum - 1];
1031 hashp->SPAREShdr.spares[splitnum - 1]--;
1032 offset = 0;
1033 }
1034 } else {
1035 /*
1036 * Free_bit addresses the last used bit. Bump it to address
1037 * the first available bit.
1038 */
1039 free_bit++;
1040 SETBIT(freep, free_bit)((freep)[(free_bit) / 32] |= (1 << ((free_bit) % 32)));
17
←
Assuming right operand of bit shift is non-negative
→
18
←
Array access (from variable 'freep') results in a null pointer dereference
1041 }
1042
1043 /* Calculate address of the new overflow page */
1044 addr = OADDR_OF(splitnum, offset)((uint32)((uint32)(splitnum) << 11) + (offset));
1045#ifdef DEBUG2
1046 (void)fprintf(stderrstderr, "OVERFLOW_PAGE: ADDR: %d BIT: %d PAGE %d\n",
1047 addr, free_bit, free_page);
1048#endif
1049 return (addr);
1050
1051found:
1052 bit = bit + first_free(freep[j]);
1053 SETBIT(freep, bit)((freep)[(bit) / 32] |= (1 << ((bit) % 32)));
1054#ifdef DEBUG2
1055 tmp1 = bit;
1056 tmp2 = i;
1057#endif
1058 /*
1059 * Bits are addressed starting with 0, but overflow pages are addressed
1060 * beginning at 1. Bit is a bit addressnumber, so we need to increment
1061 * it to convert it to a page number.
1062 */
1063 bit = 1 + bit + (i * (hashp->BSIZEhdr.bsize << BYTE_SHIFT3));
1064 if (bit >= hashp->LAST_FREEDhdr.last_freed)
1065 hashp->LAST_FREEDhdr.last_freed = bit - 1;
1066
1067 /* Calculate the split number for this page */
1068 for (i = 0; (i < (unsigned)splitnum) && (bit > hashp->SPAREShdr.spares[i]); i++) {
1069 }
1070 offset = (i ? bit - hashp->SPAREShdr.spares[i - 1] : bit);
1071 if (offset >= SPLITMASK0x7FF)
1072 return (0); /* Out of overflow pages */
1073 addr = OADDR_OF(i, offset)((uint32)((uint32)(i) << 11) + (offset));
1074#ifdef DEBUG2
1075 (void)fprintf(stderrstderr, "OVERFLOW_PAGE: ADDR: %d BIT: %d PAGE %d\n",
1076 addr, tmp1, tmp2);
1077#endif
1078
1079 /* Allocate and return the overflow page */
1080 return (addr);
1081}
1082
1083/*
1084 * Mark this overflow page as free.
1085 */
1086extern void
1087dbm_free_ovflpage(HTAB *hashp, BUFHEAD *obufp)
1088{
1089 uint16 addr;
1090 uint32 *freep;
1091 uint32 bit_address, free_page, free_bit;
1092 uint16 ndx;
1093
1094 if (!obufp || !obufp->addr)
1095 return;
1096
1097 addr = obufp->addr;
1098#ifdef DEBUG1
1099 (void)fprintf(stderrstderr, "Freeing %d\n", addr);
1100#endif
1101 ndx = (((uint16)addr) >> SPLITSHIFT11);
1102 bit_address =
1103 (ndx ? hashp->SPAREShdr.spares[ndx - 1] : 0) + (addr & SPLITMASK0x7FF) - 1;
1104 if (bit_address < (uint32)hashp->LAST_FREEDhdr.last_freed)
1105 hashp->LAST_FREEDhdr.last_freed = bit_address;
1106 free_page = (bit_address >> (hashp->BSHIFThdr.bshift + BYTE_SHIFT3));
1107 free_bit = bit_address & ((hashp->BSIZEhdr.bsize << BYTE_SHIFT3) - 1);
1108
1109 if (!(freep = hashp->mapp[free_page]))
1110 freep = fetch_bitmap(hashp, free_page);
1111
1112#ifdef DEBUG1
1113 /*
1114 * This had better never happen. It means we tried to read a bitmap
1115 * that has already had overflow pages allocated off it, and we
1116 * failed to read it from the file.
1117 */
1118 if (!freep) {
1119 assert(0)((0) ? (void) (0) : __assert_fail ("0", "h_page.c", 1119, __extension__
__PRETTY_FUNCTION__));
1120 return;
1121 }
1122#endif
1123 CLRBIT(freep, free_bit)((freep)[(free_bit) / 32] &= ~(1 << ((free_bit) % 32
)));
1124#ifdef DEBUG2
1125 (void)fprintf(stderrstderr, "FREE_OVFLPAGE: ADDR: %d BIT: %d PAGE %d\n",
1126 obufp->addr, free_bit, free_page);
1127#endif
1128 dbm_reclaim_buf(hashp, obufp);
1129}
1130
1131/*
1132 * Returns:
1133 * 0 success
1134 * -1 failure
1135 */
1136static int
1137open_temp(HTAB *hashp)
1138{
1139#if !defined(_WIN32) && !defined(_WINDOWS) && !defined(macintosh)
1140 sigset_t set, oset;
1141#endif
1142#if !defined(macintosh)
1143 char *tmpdir;
1144 size_t len;
1145 char last;
1146#endif
1147 static const char namestr[] = "/_hashXXXXXX";
1148 char filename[1024];
1149
1150#if !defined(_WIN32) && !defined(_WINDOWS) && !defined(macintosh)
1151 /* Block signals; make sure file goes away at process exit. */
1152 (void)sigfillset(&set);
1153 (void)sigprocmask(SIG_BLOCK0, &set, &oset);
1154#endif
1155
1156 filename[0] = 0;
1157#if defined(macintosh)
1158 strcat(filename, namestr + 1);
1159#else
1160 tmpdir = getenv("TMP");
1161 if (!tmpdir)
1162 tmpdir = getenv("TMPDIR");
1163 if (!tmpdir)
1164 tmpdir = getenv("TEMP");
1165 if (!tmpdir)
1166 tmpdir = ".";
1167 len = strlen(tmpdir);
1168 if (len && len < (sizeof filename - sizeof namestr)) {
1169 strcpy(filename, tmpdir);
1170 }
1171 len = strlen(filename);
1172 last = tmpdir[len - 1];
1173 strcat(filename, (last == '/' || last == '\\') ? namestr + 1 : namestr);
1174#endif
1175
1176#if defined(_WIN32) || defined(_WINDOWS)
1177 if ((hashp->fp = mkstempflags(filename, _O_BINARY | _O_TEMPORARY)) != -1) {
1178 if (hashp->filename) {
1179 free(hashp->filename);
1180 }
1181 hashp->filename = strdup(filename);
1182 hashp->is_temp = 1;
1183 }
1184#else
1185 if ((hashp->fp = mkstemp(filename)) != -1) {
1186 (void)unlink(filename);
1187#if !defined(macintosh)
1188 (void)fcntl(hashp->fp, F_SETFD2, 1);
1189#endif
1190 }
1191#endif
1192
1193#if !defined(_WIN32) && !defined(_WINDOWS) && !defined(macintosh)
1194 (void)sigprocmask(SIG_SETMASK2, &oset, (sigset_t *)NULL((void*)0));
1195#endif
1196 return (hashp->fp != -1 ? 0 : -1);
1197}
1198
1199/*
1200 * We have to know that the key will fit, but the last entry on the page is
1201 * an overflow pair, so we need to shift things.
1202 */
1203static void
1204squeeze_key(uint16 *sp, const DBT *key, const DBT *val)
1205{
1206 register char *p;
1207 uint16 free_space, n, off, pageno;
1208
1209 p = (char *)sp;
1210 n = sp[0];
1211 free_space = FREESPACE(sp)((sp)[(sp)[0] + 1]);
1212 off = OFFSET(sp)((sp)[(sp)[0] + 2]);
1213
1214 pageno = sp[n - 1];
1215 off -= key->size;
1216 sp[n - 1] = off;
1217 memmove(p + off, key->data, key->size);
1218 off -= val->size;
1219 sp[n] = off;
1220 memmove(p + off, val->data, val->size);
1221 sp[0] = n + 2;
1222 sp[n + 1] = pageno;
1223 sp[n + 2] = OVFLPAGE0;
1224 FREESPACE(sp)((sp)[(sp)[0] + 1]) = free_space - PAIRSIZE(key, val)(2 * sizeof(uint16) + (key)->size + (val)->size);
1225 OFFSET(sp)((sp)[(sp)[0] + 2]) = off;
1226}
1227
1228static uint32 *
1229fetch_bitmap(HTAB *hashp, uint32 ndx)
1230{
1231 if (ndx >= (unsigned)hashp->nmaps)
1232 return (NULL((void*)0));
1233 if ((hashp->mapp[ndx] = (uint32 *)malloc((size_t)hashp->BSIZEhdr.bsize)) == NULL((void*)0))
1234 return (NULL((void*)0));
1235 if (dbm_get_page(hashp,
1236 (char *)hashp->mapp[ndx], hashp->BITMAPShdr.bitmaps[ndx], 0, 1, 1)) {
1237 free(hashp->mapp[ndx]);
1238 hashp->mapp[ndx] = NULL((void*)0); /* NEW: 9-11-95 */
1239 return (NULL((void*)0));
1240 }
1241 return (hashp->mapp[ndx]);
1242}
1243
1244#ifdef DEBUG4
1245int
1246print_chain(int addr)
1247{
1248 BUFHEAD *bufp;
1249 short *bp, oaddr;
1250
1251 (void)fprintf(stderrstderr, "%d ", addr);
1252 bufp = dbm_get_buf(hashp, addr, NULL((void*)0), 0);
1253 bp = (short *)bufp->page;
1254 while (bp[0] && ((bp[bp[0]] == OVFLPAGE0) ||
1255 ((bp[0] > 2) && bp[2] < REAL_KEY4))) {
1256 oaddr = bp[bp[0] - 1];
1257 (void)fprintf(stderrstderr, "%d ", (int)oaddr);
1258 bufp = dbm_get_buf(hashp, (int)oaddr, bufp, 0);
1259 bp = (short *)bufp->page;
1260 }
1261 (void)fprintf(stderrstderr, "\n");
1262}
1263#endif