| File: | src/lib/libc/db/hash/hash_page.c |
| Warning: | line 746, column 3 Array access (from variable 'freep') results in an undefined pointer dereference |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
| 1 | /* $OpenBSD: hash_page.c,v 1.23 2016/12/18 17:07:58 krw 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 | * Margo Seltzer. | |||
| 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 | /* | |||
| 36 | * PACKAGE: hashing | |||
| 37 | * | |||
| 38 | * DESCRIPTION: | |||
| 39 | * Page manipulation for hashing package. | |||
| 40 | * | |||
| 41 | * ROUTINES: | |||
| 42 | * | |||
| 43 | * External | |||
| 44 | * __get_page | |||
| 45 | * __add_ovflpage | |||
| 46 | * Internal | |||
| 47 | * overflow_page | |||
| 48 | * open_temp | |||
| 49 | */ | |||
| 50 | ||||
| 51 | #include <errno(*__errno()).h> | |||
| 52 | #include <fcntl.h> | |||
| 53 | #include <limits.h> | |||
| 54 | #include <signal.h> | |||
| 55 | #include <stdio.h> | |||
| 56 | #include <stdlib.h> | |||
| 57 | #include <string.h> | |||
| 58 | #include <unistd.h> | |||
| 59 | #ifdef DEBUG | |||
| 60 | #include <assert.h> | |||
| 61 | #endif | |||
| 62 | ||||
| 63 | #include <db.h> | |||
| 64 | #include "hash.h" | |||
| 65 | #include "page.h" | |||
| 66 | #include "extern.h" | |||
| 67 | ||||
| 68 | static u_int32_t *fetch_bitmap(HTAB *, int); | |||
| 69 | static u_int32_t first_free(u_int32_t); | |||
| 70 | static int open_temp(HTAB *); | |||
| 71 | static u_int16_t overflow_page(HTAB *); | |||
| 72 | static void putpair(char *, const DBT *, const DBT *); | |||
| 73 | static void squeeze_key(u_int16_t *, const DBT *, const DBT *); | |||
| 74 | static int ugly_split(HTAB *, u_int32_t, BUFHEAD *, BUFHEAD *, int, int); | |||
| 75 | ||||
| 76 | #define PAGE_INIT(P){ ((u_int16_t *)(P))[0] = 0; ((u_int16_t *)(P))[1] = hashp-> hdr.bsize - 3 * sizeof(u_int16_t); ((u_int16_t *)(P))[2] = hashp ->hdr.bsize; } { \ | |||
| 77 | ((u_int16_t *)(P))[0] = 0; \ | |||
| 78 | ((u_int16_t *)(P))[1] = hashp->BSIZEhdr.bsize - 3 * sizeof(u_int16_t); \ | |||
| 79 | ((u_int16_t *)(P))[2] = hashp->BSIZEhdr.bsize; \ | |||
| 80 | } | |||
| 81 | ||||
| 82 | /* | |||
| 83 | * This is called AFTER we have verified that there is room on the page for | |||
| 84 | * the pair (PAIRFITS has returned true) so we go right ahead and start moving | |||
| 85 | * stuff on. | |||
| 86 | */ | |||
| 87 | static void | |||
| 88 | putpair(char *p, const DBT *key, const DBT *val) | |||
| 89 | { | |||
| 90 | u_int16_t *bp, n, off; | |||
| 91 | ||||
| 92 | bp = (u_int16_t *)p; | |||
| 93 | ||||
| 94 | /* Enter the key first. */ | |||
| 95 | n = bp[0]; | |||
| 96 | ||||
| 97 | off = OFFSET(bp)((bp)[(bp)[0]+2]) - key->size; | |||
| 98 | memmove(p + off, key->data, key->size); | |||
| 99 | bp[++n] = off; | |||
| 100 | ||||
| 101 | /* Now the data. */ | |||
| 102 | off -= val->size; | |||
| 103 | memmove(p + off, val->data, val->size); | |||
| 104 | bp[++n] = off; | |||
| 105 | ||||
| 106 | /* Adjust page info. */ | |||
| 107 | bp[0] = n; | |||
| 108 | bp[n + 1] = off - ((n + 3) * sizeof(u_int16_t)); | |||
| 109 | bp[n + 2] = off; | |||
| 110 | } | |||
| 111 | ||||
| 112 | /* | |||
| 113 | * Returns: | |||
| 114 | * 0 OK | |||
| 115 | * -1 error | |||
| 116 | */ | |||
| 117 | int | |||
| 118 | __delpair(HTAB *hashp, BUFHEAD *bufp, int ndx) | |||
| 119 | { | |||
| 120 | u_int16_t *bp, newoff, pairlen; | |||
| 121 | int n; | |||
| 122 | ||||
| 123 | bp = (u_int16_t *)bufp->page; | |||
| 124 | n = bp[0]; | |||
| 125 | ||||
| 126 | if (bp[ndx + 1] < REAL_KEY4) | |||
| 127 | return (__big_delete(hashp, bufp)); | |||
| 128 | if (ndx != 1) | |||
| 129 | newoff = bp[ndx - 1]; | |||
| 130 | else | |||
| 131 | newoff = hashp->BSIZEhdr.bsize; | |||
| 132 | pairlen = newoff - bp[ndx + 1]; | |||
| 133 | ||||
| 134 | if (ndx != (n - 1)) { | |||
| 135 | /* Hard Case -- need to shuffle keys */ | |||
| 136 | int i; | |||
| 137 | char *src = bufp->page + (int)OFFSET(bp)((bp)[(bp)[0]+2]); | |||
| 138 | char *dst = src + (int)pairlen; | |||
| 139 | memmove(dst, src, bp[ndx + 1] - OFFSET(bp)((bp)[(bp)[0]+2])); | |||
| 140 | ||||
| 141 | /* Now adjust the pointers */ | |||
| 142 | for (i = ndx + 2; i <= n; i += 2) { | |||
| 143 | if (bp[i + 1] == OVFLPAGE0) { | |||
| 144 | bp[i - 2] = bp[i]; | |||
| 145 | bp[i - 1] = bp[i + 1]; | |||
| 146 | } else { | |||
| 147 | bp[i - 2] = bp[i] + pairlen; | |||
| 148 | bp[i - 1] = bp[i + 1] + pairlen; | |||
| 149 | } | |||
| 150 | } | |||
| 151 | if (ndx == hashp->cndx) { | |||
| 152 | /* | |||
| 153 | * We just removed pair we were "pointing" to. | |||
| 154 | * By moving back the cndx we ensure subsequent | |||
| 155 | * hash_seq() calls won't skip over any entries. | |||
| 156 | */ | |||
| 157 | hashp->cndx -= 2; | |||
| 158 | } | |||
| 159 | } | |||
| 160 | /* Finally adjust the page data */ | |||
| 161 | bp[n] = OFFSET(bp)((bp)[(bp)[0]+2]) + pairlen; | |||
| 162 | bp[n - 1] = bp[n + 1] + pairlen + 2 * sizeof(u_int16_t); | |||
| 163 | bp[0] = n - 2; | |||
| 164 | hashp->NKEYShdr.nkeys--; | |||
| 165 | ||||
| 166 | bufp->flags |= BUF_MOD0x0001; | |||
| 167 | return (0); | |||
| 168 | } | |||
| 169 | /* | |||
| 170 | * Returns: | |||
| 171 | * 0 ==> OK | |||
| 172 | * -1 ==> Error | |||
| 173 | */ | |||
| 174 | int | |||
| 175 | __split_page(HTAB *hashp, u_int32_t obucket, u_int32_t nbucket) | |||
| 176 | { | |||
| 177 | BUFHEAD *new_bufp, *old_bufp; | |||
| 178 | u_int16_t *ino; | |||
| 179 | char *np; | |||
| 180 | DBT key, val; | |||
| 181 | int n, ndx, retval; | |||
| 182 | u_int16_t copyto, diff, off, moved; | |||
| 183 | char *op; | |||
| 184 | ||||
| 185 | copyto = (u_int16_t)hashp->BSIZEhdr.bsize; | |||
| 186 | off = (u_int16_t)hashp->BSIZEhdr.bsize; | |||
| 187 | old_bufp = __get_buf(hashp, obucket, NULL((void *)0), 0); | |||
| 188 | if (old_bufp == NULL((void *)0)) | |||
| 189 | return (-1); | |||
| 190 | new_bufp = __get_buf(hashp, nbucket, NULL((void *)0), 0); | |||
| 191 | if (new_bufp == NULL((void *)0)) | |||
| 192 | return (-1); | |||
| 193 | ||||
| 194 | old_bufp->flags |= (BUF_MOD0x0001 | BUF_PIN0x0008); | |||
| 195 | new_bufp->flags |= (BUF_MOD0x0001 | BUF_PIN0x0008); | |||
| 196 | ||||
| 197 | ino = (u_int16_t *)(op = old_bufp->page); | |||
| 198 | np = new_bufp->page; | |||
| 199 | ||||
| 200 | moved = 0; | |||
| 201 | ||||
| 202 | for (n = 1, ndx = 1; n < ino[0]; n += 2) { | |||
| 203 | if (ino[n + 1] < REAL_KEY4) { | |||
| 204 | retval = ugly_split(hashp, obucket, old_bufp, new_bufp, | |||
| 205 | (int)copyto, (int)moved); | |||
| 206 | old_bufp->flags &= ~BUF_PIN0x0008; | |||
| 207 | new_bufp->flags &= ~BUF_PIN0x0008; | |||
| 208 | return (retval); | |||
| 209 | ||||
| 210 | } | |||
| 211 | key.data = (u_char *)op + ino[n]; | |||
| 212 | key.size = off - ino[n]; | |||
| 213 | ||||
| 214 | if (__call_hash(hashp, key.data, key.size) == obucket) { | |||
| 215 | /* Don't switch page */ | |||
| 216 | diff = copyto - off; | |||
| 217 | if (diff) { | |||
| 218 | copyto = ino[n + 1] + diff; | |||
| 219 | memmove(op + copyto, op + ino[n + 1], | |||
| 220 | off - ino[n + 1]); | |||
| 221 | ino[ndx] = copyto + ino[n] - ino[n + 1]; | |||
| 222 | ino[ndx + 1] = copyto; | |||
| 223 | } else | |||
| 224 | copyto = ino[n + 1]; | |||
| 225 | ndx += 2; | |||
| 226 | } else { | |||
| 227 | /* Switch page */ | |||
| 228 | val.data = (u_char *)op + ino[n + 1]; | |||
| 229 | val.size = ino[n] - ino[n + 1]; | |||
| 230 | putpair(np, &key, &val); | |||
| 231 | moved += 2; | |||
| 232 | } | |||
| 233 | ||||
| 234 | off = ino[n + 1]; | |||
| 235 | } | |||
| 236 | ||||
| 237 | /* Now clean up the page */ | |||
| 238 | ino[0] -= moved; | |||
| 239 | FREESPACE(ino)((ino)[(ino)[0]+1]) = copyto - sizeof(u_int16_t) * (ino[0] + 3); | |||
| 240 | OFFSET(ino)((ino)[(ino)[0]+2]) = copyto; | |||
| 241 | ||||
| 242 | #ifdef DEBUG3 | |||
| 243 | (void)fprintf(stderr(&__sF[2]), "split %d/%d\n", | |||
| 244 | ((u_int16_t *)np)[0] / 2, | |||
| 245 | ((u_int16_t *)op)[0] / 2); | |||
| 246 | #endif | |||
| 247 | /* unpin both pages */ | |||
| 248 | old_bufp->flags &= ~BUF_PIN0x0008; | |||
| 249 | new_bufp->flags &= ~BUF_PIN0x0008; | |||
| 250 | return (0); | |||
| 251 | } | |||
| 252 | ||||
| 253 | /* | |||
| 254 | * Called when we encounter an overflow or big key/data page during split | |||
| 255 | * handling. This is special cased since we have to begin checking whether | |||
| 256 | * the key/data pairs fit on their respective pages and because we may need | |||
| 257 | * overflow pages for both the old and new pages. | |||
| 258 | * | |||
| 259 | * The first page might be a page with regular key/data pairs in which case | |||
| 260 | * we have a regular overflow condition and just need to go on to the next | |||
| 261 | * page or it might be a big key/data pair in which case we need to fix the | |||
| 262 | * big key/data pair. | |||
| 263 | * | |||
| 264 | * Returns: | |||
| 265 | * 0 ==> success | |||
| 266 | * -1 ==> failure | |||
| 267 | */ | |||
| 268 | static int | |||
| 269 | ugly_split(HTAB *hashp, | |||
| 270 | u_int32_t obucket, /* Same as __split_page. */ | |||
| 271 | BUFHEAD *old_bufp, | |||
| 272 | BUFHEAD *new_bufp, | |||
| 273 | int copyto, /* First byte on page which contains key/data values. */ | |||
| 274 | int moved) /* Number of pairs moved to new page. */ | |||
| 275 | { | |||
| 276 | BUFHEAD *bufp; /* Buffer header for ino */ | |||
| 277 | u_int16_t *ino; /* Page keys come off of */ | |||
| 278 | u_int16_t *np; /* New page */ | |||
| 279 | u_int16_t *op; /* Page keys go on to if they aren't moving */ | |||
| 280 | ||||
| 281 | BUFHEAD *last_bfp; /* Last buf header OVFL needing to be freed */ | |||
| 282 | DBT key, val; | |||
| 283 | SPLIT_RETURN ret; | |||
| 284 | u_int16_t n, off, ov_addr, scopyto; | |||
| 285 | char *cino; /* Character value of ino */ | |||
| 286 | ||||
| 287 | bufp = old_bufp; | |||
| 288 | ino = (u_int16_t *)old_bufp->page; | |||
| 289 | np = (u_int16_t *)new_bufp->page; | |||
| 290 | op = (u_int16_t *)old_bufp->page; | |||
| 291 | last_bfp = NULL((void *)0); | |||
| 292 | scopyto = (u_int16_t)copyto; /* ANSI */ | |||
| 293 | ||||
| 294 | n = ino[0] - 1; | |||
| 295 | while (n < ino[0]) { | |||
| 296 | if (ino[2] < REAL_KEY4 && ino[2] != OVFLPAGE0) { | |||
| 297 | if (__big_split(hashp, old_bufp, | |||
| 298 | new_bufp, bufp, bufp->addr, obucket, &ret)) | |||
| 299 | return (-1); | |||
| 300 | old_bufp = ret.oldp; | |||
| 301 | if (!old_bufp) | |||
| 302 | return (-1); | |||
| 303 | op = (u_int16_t *)old_bufp->page; | |||
| 304 | new_bufp = ret.newp; | |||
| 305 | if (!new_bufp) | |||
| 306 | return (-1); | |||
| 307 | np = (u_int16_t *)new_bufp->page; | |||
| 308 | bufp = ret.nextp; | |||
| 309 | if (!bufp) | |||
| 310 | return (0); | |||
| 311 | cino = (char *)bufp->page; | |||
| 312 | ino = (u_int16_t *)cino; | |||
| 313 | last_bfp = ret.nextp; | |||
| 314 | } else if (ino[n + 1] == OVFLPAGE0) { | |||
| 315 | ov_addr = ino[n]; | |||
| 316 | /* | |||
| 317 | * Fix up the old page -- the extra 2 are the fields | |||
| 318 | * which contained the overflow information. | |||
| 319 | */ | |||
| 320 | ino[0] -= (moved + 2); | |||
| 321 | FREESPACE(ino)((ino)[(ino)[0]+1]) = | |||
| 322 | scopyto - sizeof(u_int16_t) * (ino[0] + 3); | |||
| 323 | OFFSET(ino)((ino)[(ino)[0]+2]) = scopyto; | |||
| 324 | ||||
| 325 | bufp = __get_buf(hashp, ov_addr, bufp, 0); | |||
| 326 | if (!bufp) | |||
| 327 | return (-1); | |||
| 328 | ||||
| 329 | ino = (u_int16_t *)bufp->page; | |||
| 330 | n = 1; | |||
| 331 | scopyto = hashp->BSIZEhdr.bsize; | |||
| 332 | moved = 0; | |||
| 333 | ||||
| 334 | if (last_bfp) | |||
| 335 | __free_ovflpage(hashp, last_bfp); | |||
| 336 | last_bfp = bufp; | |||
| 337 | } | |||
| 338 | /* Move regular sized pairs of there are any */ | |||
| 339 | off = hashp->BSIZEhdr.bsize; | |||
| 340 | for (n = 1; (n < ino[0]) && (ino[n + 1] >= REAL_KEY4); n += 2) { | |||
| 341 | cino = (char *)ino; | |||
| 342 | key.data = (u_char *)cino + ino[n]; | |||
| 343 | key.size = off - ino[n]; | |||
| 344 | val.data = (u_char *)cino + ino[n + 1]; | |||
| 345 | val.size = ino[n] - ino[n + 1]; | |||
| 346 | off = ino[n + 1]; | |||
| 347 | ||||
| 348 | if (__call_hash(hashp, key.data, key.size) == obucket) { | |||
| 349 | /* Keep on old page */ | |||
| 350 | if (PAIRFITS(op, (&key), (&val))(((op)[2] >= 4) && ((2*sizeof(u_int16_t) + (((& key)))->size + (((&val)))->size) + (2*sizeof(u_int16_t ))) <= (((op))[((op))[0]+1]))) | |||
| 351 | putpair((char *)op, &key, &val); | |||
| 352 | else { | |||
| 353 | old_bufp = | |||
| 354 | __add_ovflpage(hashp, old_bufp); | |||
| 355 | if (!old_bufp) | |||
| 356 | return (-1); | |||
| 357 | op = (u_int16_t *)old_bufp->page; | |||
| 358 | putpair((char *)op, &key, &val); | |||
| 359 | } | |||
| 360 | old_bufp->flags |= BUF_MOD0x0001; | |||
| 361 | } else { | |||
| 362 | /* Move to new page */ | |||
| 363 | if (PAIRFITS(np, (&key), (&val))(((np)[2] >= 4) && ((2*sizeof(u_int16_t) + (((& key)))->size + (((&val)))->size) + (2*sizeof(u_int16_t ))) <= (((np))[((np))[0]+1]))) | |||
| 364 | putpair((char *)np, &key, &val); | |||
| 365 | else { | |||
| 366 | new_bufp = | |||
| 367 | __add_ovflpage(hashp, new_bufp); | |||
| 368 | if (!new_bufp) | |||
| 369 | return (-1); | |||
| 370 | np = (u_int16_t *)new_bufp->page; | |||
| 371 | putpair((char *)np, &key, &val); | |||
| 372 | } | |||
| 373 | new_bufp->flags |= BUF_MOD0x0001; | |||
| 374 | } | |||
| 375 | } | |||
| 376 | } | |||
| 377 | if (last_bfp) | |||
| 378 | __free_ovflpage(hashp, last_bfp); | |||
| 379 | return (0); | |||
| 380 | } | |||
| 381 | ||||
| 382 | /* | |||
| 383 | * Add the given pair to the page | |||
| 384 | * | |||
| 385 | * Returns: | |||
| 386 | * 0 ==> OK | |||
| 387 | * 1 ==> failure | |||
| 388 | */ | |||
| 389 | int | |||
| 390 | __addel(HTAB *hashp, BUFHEAD *bufp, const DBT *key, const DBT *val) | |||
| 391 | { | |||
| 392 | u_int16_t *bp, *sop; | |||
| 393 | int do_expand; | |||
| 394 | ||||
| 395 | bp = (u_int16_t *)bufp->page; | |||
| 396 | do_expand = 0; | |||
| 397 | while (bp[0] && (bp[2] < REAL_KEY4 || bp[bp[0]] < REAL_KEY4)) | |||
| ||||
| 398 | /* Exception case */ | |||
| 399 | if (bp[2] == FULL_KEY_DATA3 && bp[0] == 2) | |||
| 400 | /* This is the last page of a big key/data pair | |||
| 401 | and we need to add another page */ | |||
| 402 | break; | |||
| 403 | else if (bp[2] < REAL_KEY4 && bp[bp[0]] != OVFLPAGE0) { | |||
| 404 | bufp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0); | |||
| 405 | if (!bufp) | |||
| 406 | return (-1); | |||
| 407 | bp = (u_int16_t *)bufp->page; | |||
| 408 | } else if (bp[bp[0]] != OVFLPAGE0) { | |||
| 409 | /* Short key/data pairs, no more pages */ | |||
| 410 | break; | |||
| 411 | } else { | |||
| 412 | /* Try to squeeze key on this page */ | |||
| 413 | if (bp[2] >= REAL_KEY4 && | |||
| 414 | FREESPACE(bp)((bp)[(bp)[0]+1]) >= PAIRSIZE(key, val)(2*sizeof(u_int16_t) + (key)->size + (val)->size)) { | |||
| 415 | squeeze_key(bp, key, val); | |||
| 416 | goto stats; | |||
| 417 | } else { | |||
| 418 | bufp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0); | |||
| 419 | if (!bufp) | |||
| 420 | return (-1); | |||
| 421 | bp = (u_int16_t *)bufp->page; | |||
| 422 | } | |||
| 423 | } | |||
| 424 | ||||
| 425 | if (PAIRFITS(bp, key, val)(((bp)[2] >= 4) && ((2*sizeof(u_int16_t) + ((key)) ->size + ((val))->size) + (2*sizeof(u_int16_t))) <= ( ((bp))[((bp))[0]+1]))) | |||
| 426 | putpair(bufp->page, key, val); | |||
| 427 | else { | |||
| 428 | do_expand = 1; | |||
| 429 | bufp = __add_ovflpage(hashp, bufp); | |||
| 430 | if (!bufp) | |||
| 431 | return (-1); | |||
| 432 | sop = (u_int16_t *)bufp->page; | |||
| 433 | ||||
| 434 | if (PAIRFITS(sop, key, val)(((sop)[2] >= 4) && ((2*sizeof(u_int16_t) + ((key) )->size + ((val))->size) + (2*sizeof(u_int16_t))) <= (((sop))[((sop))[0]+1]))) | |||
| 435 | putpair((char *)sop, key, val); | |||
| 436 | else | |||
| 437 | if (__big_insert(hashp, bufp, key, val)) | |||
| 438 | return (-1); | |||
| 439 | } | |||
| 440 | stats: | |||
| 441 | bufp->flags |= BUF_MOD0x0001; | |||
| 442 | /* | |||
| 443 | * If the average number of keys per bucket exceeds the fill factor, | |||
| 444 | * expand the table. | |||
| 445 | */ | |||
| 446 | hashp->NKEYShdr.nkeys++; | |||
| 447 | if (do_expand || | |||
| 448 | (hashp->NKEYShdr.nkeys / (hashp->MAX_BUCKEThdr.max_bucket + 1) > hashp->FFACTORhdr.ffactor)) | |||
| 449 | return (__expand_table(hashp)); | |||
| 450 | return (0); | |||
| 451 | } | |||
| 452 | ||||
| 453 | /* | |||
| 454 | * | |||
| 455 | * Returns: | |||
| 456 | * pointer on success | |||
| 457 | * NULL on error | |||
| 458 | */ | |||
| 459 | BUFHEAD * | |||
| 460 | __add_ovflpage(HTAB *hashp, BUFHEAD *bufp) | |||
| 461 | { | |||
| 462 | u_int16_t *sp, ndx, ovfl_num; | |||
| 463 | #ifdef DEBUG1 | |||
| 464 | int tmp1, tmp2; | |||
| 465 | #endif | |||
| 466 | sp = (u_int16_t *)bufp->page; | |||
| 467 | ||||
| 468 | /* Check if we are dynamically determining the fill factor */ | |||
| 469 | if (hashp->FFACTORhdr.ffactor == DEF_FFACTOR65536) { | |||
| 470 | hashp->FFACTORhdr.ffactor = sp[0] >> 1; | |||
| 471 | if (hashp->FFACTORhdr.ffactor < MIN_FFACTOR4) | |||
| 472 | hashp->FFACTORhdr.ffactor = MIN_FFACTOR4; | |||
| 473 | } | |||
| 474 | bufp->flags |= BUF_MOD0x0001; | |||
| 475 | ovfl_num = overflow_page(hashp); | |||
| 476 | #ifdef DEBUG1 | |||
| 477 | tmp1 = bufp->addr; | |||
| 478 | tmp2 = bufp->ovfl ? bufp->ovfl->addr : 0; | |||
| 479 | #endif | |||
| 480 | if (!ovfl_num || !(bufp->ovfl = __get_buf(hashp, ovfl_num, bufp, 1))) | |||
| 481 | return (NULL((void *)0)); | |||
| 482 | bufp->ovfl->flags |= BUF_MOD0x0001; | |||
| 483 | #ifdef DEBUG1 | |||
| 484 | (void)fprintf(stderr(&__sF[2]), "ADDOVFLPAGE: %d->ovfl was %d is now %d\n", | |||
| 485 | tmp1, tmp2, bufp->ovfl->addr); | |||
| 486 | #endif | |||
| 487 | ndx = sp[0]; | |||
| 488 | /* | |||
| 489 | * Since a pair is allocated on a page only if there's room to add | |||
| 490 | * an overflow page, we know that the OVFL information will fit on | |||
| 491 | * the page. | |||
| 492 | */ | |||
| 493 | sp[ndx + 4] = OFFSET(sp)((sp)[(sp)[0]+2]); | |||
| 494 | sp[ndx + 3] = FREESPACE(sp)((sp)[(sp)[0]+1]) - OVFLSIZE(2*sizeof(u_int16_t)); | |||
| 495 | sp[ndx + 1] = ovfl_num; | |||
| 496 | sp[ndx + 2] = OVFLPAGE0; | |||
| 497 | sp[0] = ndx + 2; | |||
| 498 | #ifdef HASH_STATISTICS | |||
| 499 | hash_overflows++; | |||
| 500 | #endif | |||
| 501 | return (bufp->ovfl); | |||
| 502 | } | |||
| 503 | ||||
| 504 | /* | |||
| 505 | * Returns: | |||
| 506 | * 0 indicates SUCCESS | |||
| 507 | * -1 indicates FAILURE | |||
| 508 | */ | |||
| 509 | int | |||
| 510 | __get_page(HTAB *hashp, char *p, u_int32_t bucket, int is_bucket, int is_disk, | |||
| 511 | int is_bitmap) | |||
| 512 | { | |||
| 513 | int fd, page, size, rsize; | |||
| 514 | u_int16_t *bp; | |||
| 515 | ||||
| 516 | fd = hashp->fp; | |||
| 517 | size = hashp->BSIZEhdr.bsize; | |||
| 518 | ||||
| 519 | if ((fd == -1) || !is_disk) { | |||
| 520 | PAGE_INIT(p){ ((u_int16_t *)(p))[0] = 0; ((u_int16_t *)(p))[1] = hashp-> hdr.bsize - 3 * sizeof(u_int16_t); ((u_int16_t *)(p))[2] = hashp ->hdr.bsize; }; | |||
| 521 | return (0); | |||
| 522 | } | |||
| 523 | if (is_bucket) | |||
| 524 | page = BUCKET_TO_PAGE(bucket)(bucket) + hashp->hdr.hdrpages + ((bucket) ? hashp->hdr .spares[__log2((bucket)+1)-1] : 0); | |||
| 525 | else | |||
| 526 | page = OADDR_TO_PAGE(bucket)((1 << (((u_int32_t)((bucket))) >> 11)) -1) + hashp ->hdr.hdrpages + (((1 << (((u_int32_t)((bucket))) >> 11)) -1) ? hashp->hdr.spares[__log2(((1 << (((u_int32_t )((bucket))) >> 11)) -1)+1)-1] : 0) + (((bucket)) & 0x7FF);; | |||
| 527 | if ((rsize = pread(fd, p, size, (off_t)page << hashp->BSHIFThdr.bshift)) == -1) | |||
| 528 | return (-1); | |||
| 529 | bp = (u_int16_t *)p; | |||
| 530 | if (!rsize) | |||
| 531 | bp[0] = 0; /* We hit the EOF, so initialize a new page */ | |||
| 532 | else | |||
| 533 | if (rsize != size) { | |||
| 534 | errno(*__errno()) = EFTYPE79; | |||
| 535 | return (-1); | |||
| 536 | } | |||
| 537 | if (!is_bitmap && !bp[0]) { | |||
| 538 | PAGE_INIT(p){ ((u_int16_t *)(p))[0] = 0; ((u_int16_t *)(p))[1] = hashp-> hdr.bsize - 3 * sizeof(u_int16_t); ((u_int16_t *)(p))[2] = hashp ->hdr.bsize; }; | |||
| 539 | } else | |||
| 540 | if (hashp->LORDERhdr.lorder != BYTE_ORDER1234) { | |||
| 541 | int i, max; | |||
| 542 | ||||
| 543 | if (is_bitmap) { | |||
| 544 | max = hashp->BSIZEhdr.bsize >> 2; /* divide by 4 */ | |||
| 545 | for (i = 0; i < max; i++) | |||
| 546 | M_32_SWAP(((int *)p)[i]){ u_int32_t _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]; }; | |||
| 547 | } else { | |||
| 548 | M_16_SWAP(bp[0]){ u_int16_t _tmp = bp[0]; ((char *)&bp[0])[0] = ((char *) &_tmp)[1]; ((char *)&bp[0])[1] = ((char *)&_tmp)[ 0]; }; | |||
| 549 | max = bp[0] + 2; | |||
| 550 | for (i = 1; i <= max; i++) | |||
| 551 | M_16_SWAP(bp[i]){ u_int16_t _tmp = bp[i]; ((char *)&bp[i])[0] = ((char *) &_tmp)[1]; ((char *)&bp[i])[1] = ((char *)&_tmp)[ 0]; }; | |||
| 552 | } | |||
| 553 | } | |||
| 554 | return (0); | |||
| 555 | } | |||
| 556 | ||||
| 557 | /* | |||
| 558 | * Write page p to disk | |||
| 559 | * | |||
| 560 | * Returns: | |||
| 561 | * 0 ==> OK | |||
| 562 | * -1 ==>failure | |||
| 563 | */ | |||
| 564 | int | |||
| 565 | __put_page(HTAB *hashp, char *p, u_int32_t bucket, int is_bucket, int is_bitmap) | |||
| 566 | { | |||
| 567 | int fd, page, size, wsize; | |||
| 568 | ||||
| 569 | size = hashp->BSIZEhdr.bsize; | |||
| 570 | if ((hashp->fp == -1) && open_temp(hashp)) | |||
| 571 | return (-1); | |||
| 572 | fd = hashp->fp; | |||
| 573 | ||||
| 574 | if (hashp->LORDERhdr.lorder != BYTE_ORDER1234) { | |||
| 575 | int i, max; | |||
| 576 | ||||
| 577 | if (is_bitmap) { | |||
| 578 | max = hashp->BSIZEhdr.bsize >> 2; /* divide by 4 */ | |||
| 579 | for (i = 0; i < max; i++) | |||
| 580 | M_32_SWAP(((int *)p)[i]){ u_int32_t _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]; }; | |||
| 581 | } else { | |||
| 582 | max = ((u_int16_t *)p)[0] + 2; | |||
| 583 | for (i = 0; i <= max; i++) | |||
| 584 | M_16_SWAP(((u_int16_t *)p)[i]){ u_int16_t _tmp = ((u_int16_t *)p)[i]; ((char *)&((u_int16_t *)p)[i])[0] = ((char *)&_tmp)[1]; ((char *)&((u_int16_t *)p)[i])[1] = ((char *)&_tmp)[0]; }; | |||
| 585 | } | |||
| 586 | } | |||
| 587 | if (is_bucket) | |||
| 588 | page = BUCKET_TO_PAGE(bucket)(bucket) + hashp->hdr.hdrpages + ((bucket) ? hashp->hdr .spares[__log2((bucket)+1)-1] : 0); | |||
| 589 | else | |||
| 590 | page = OADDR_TO_PAGE(bucket)((1 << (((u_int32_t)((bucket))) >> 11)) -1) + hashp ->hdr.hdrpages + (((1 << (((u_int32_t)((bucket))) >> 11)) -1) ? hashp->hdr.spares[__log2(((1 << (((u_int32_t )((bucket))) >> 11)) -1)+1)-1] : 0) + (((bucket)) & 0x7FF);; | |||
| 591 | if ((wsize = pwrite(fd, p, size, (off_t)page << hashp->BSHIFThdr.bshift)) == -1) | |||
| 592 | /* Errno is set */ | |||
| 593 | return (-1); | |||
| 594 | if (wsize != size) { | |||
| 595 | errno(*__errno()) = EFTYPE79; | |||
| 596 | return (-1); | |||
| 597 | } | |||
| 598 | return (0); | |||
| 599 | } | |||
| 600 | ||||
| 601 | #define BYTE_MASK((1 << 5) -1) ((1 << INT_BYTE_SHIFT5) -1) | |||
| 602 | /* | |||
| 603 | * Initialize a new bitmap page. Bitmap pages are left in memory | |||
| 604 | * once they are read in. | |||
| 605 | */ | |||
| 606 | int | |||
| 607 | __ibitmap(HTAB *hashp, int pnum, int nbits, int ndx) | |||
| 608 | { | |||
| 609 | u_int32_t *ip; | |||
| 610 | int clearbytes, clearints; | |||
| 611 | ||||
| 612 | if ((ip = (u_int32_t *)malloc(hashp->BSIZEhdr.bsize)) == NULL((void *)0)) | |||
| 613 | return (1); | |||
| 614 | hashp->nmaps++; | |||
| 615 | clearints = ((nbits - 1) >> INT_BYTE_SHIFT5) + 1; | |||
| 616 | clearbytes = clearints << INT_TO_BYTE2; | |||
| 617 | (void)memset((char *)ip, 0, clearbytes); | |||
| 618 | (void)memset(((char *)ip) + clearbytes, 0xFF, | |||
| 619 | hashp->BSIZEhdr.bsize - clearbytes); | |||
| 620 | ip[clearints - 1] = ALL_SET((u_int32_t)0xFFFFFFFF) << (nbits & BYTE_MASK((1 << 5) -1)); | |||
| 621 | SETBIT(ip, 0)((ip)[(0)/32] |= (1<<((0)%32))); | |||
| 622 | hashp->BITMAPShdr.bitmaps[ndx] = (u_int16_t)pnum; | |||
| 623 | hashp->mapp[ndx] = ip; | |||
| 624 | return (0); | |||
| 625 | } | |||
| 626 | ||||
| 627 | static u_int32_t | |||
| 628 | first_free(u_int32_t map) | |||
| 629 | { | |||
| 630 | u_int32_t i, mask; | |||
| 631 | ||||
| 632 | mask = 0x1; | |||
| 633 | for (i = 0; i < BITS_PER_MAP32; i++) { | |||
| 634 | if (!(mask & map)) | |||
| 635 | return (i); | |||
| 636 | mask = mask << 1; | |||
| 637 | } | |||
| 638 | return (i); | |||
| 639 | } | |||
| 640 | ||||
| 641 | static u_int16_t | |||
| 642 | overflow_page(HTAB *hashp) | |||
| 643 | { | |||
| 644 | u_int32_t *freep; | |||
| 645 | int max_free, offset, splitnum; | |||
| 646 | u_int16_t addr; | |||
| 647 | int bit, first_page, free_bit, free_page, i, in_use_bits, j; | |||
| 648 | #ifdef DEBUG2 | |||
| 649 | int tmp1, tmp2; | |||
| 650 | #endif | |||
| 651 | splitnum = hashp->OVFL_POINThdr.ovfl_point; | |||
| 652 | max_free = hashp->SPAREShdr.spares[splitnum]; | |||
| 653 | ||||
| 654 | free_page = (max_free - 1) >> (hashp->BSHIFThdr.bshift + BYTE_SHIFT3); | |||
| 655 | free_bit = (max_free - 1) & ((hashp->BSIZEhdr.bsize << BYTE_SHIFT3) - 1); | |||
| 656 | ||||
| 657 | /* Look through all the free maps to find the first free block */ | |||
| 658 | first_page = hashp->LAST_FREEDhdr.last_freed >>(hashp->BSHIFThdr.bshift + BYTE_SHIFT3); | |||
| 659 | for ( i = first_page; i <= free_page; i++ ) { | |||
| 660 | if (!(freep = (u_int32_t *)hashp->mapp[i]) && | |||
| 661 | !(freep = fetch_bitmap(hashp, i))) | |||
| 662 | return (0); | |||
| 663 | if (i == free_page) | |||
| 664 | in_use_bits = free_bit; | |||
| 665 | else | |||
| 666 | in_use_bits = (hashp->BSIZEhdr.bsize << BYTE_SHIFT3) - 1; | |||
| 667 | ||||
| 668 | if (i == first_page) { | |||
| 669 | bit = hashp->LAST_FREEDhdr.last_freed & | |||
| 670 | ((hashp->BSIZEhdr.bsize << BYTE_SHIFT3) - 1); | |||
| 671 | j = bit / BITS_PER_MAP32; | |||
| 672 | bit = bit & ~(BITS_PER_MAP32 - 1); | |||
| 673 | } else { | |||
| 674 | bit = 0; | |||
| 675 | j = 0; | |||
| 676 | } | |||
| 677 | for (; bit <= in_use_bits; j++, bit += BITS_PER_MAP32) | |||
| 678 | if (freep[j] != ALL_SET((u_int32_t)0xFFFFFFFF)) | |||
| 679 | goto found; | |||
| 680 | } | |||
| 681 | ||||
| 682 | /* No Free Page Found */ | |||
| 683 | hashp->LAST_FREEDhdr.last_freed = hashp->SPAREShdr.spares[splitnum]; | |||
| 684 | hashp->SPAREShdr.spares[splitnum]++; | |||
| 685 | offset = hashp->SPAREShdr.spares[splitnum] - | |||
| 686 | (splitnum ? hashp->SPAREShdr.spares[splitnum - 1] : 0); | |||
| 687 | ||||
| 688 | #define OVMSG"HASH: Out of overflow pages. Increase page size\n" "HASH: Out of overflow pages. Increase page size\n" | |||
| 689 | if (offset > SPLITMASK0x7FF) { | |||
| 690 | if (++splitnum >= NCACHED32) { | |||
| 691 | (void)write(STDERR_FILENO2, OVMSG"HASH: Out of overflow pages. Increase page size\n", sizeof(OVMSG"HASH: Out of overflow pages. Increase page size\n") - 1); | |||
| 692 | errno(*__errno()) = EFBIG27; | |||
| 693 | return (0); | |||
| 694 | } | |||
| 695 | hashp->OVFL_POINThdr.ovfl_point = splitnum; | |||
| 696 | hashp->SPAREShdr.spares[splitnum] = hashp->SPAREShdr.spares[splitnum-1]; | |||
| 697 | hashp->SPAREShdr.spares[splitnum-1]--; | |||
| 698 | offset = 1; | |||
| 699 | } | |||
| 700 | ||||
| 701 | /* Check if we need to allocate a new bitmap page */ | |||
| 702 | if (free_bit == (hashp->BSIZEhdr.bsize << BYTE_SHIFT3) - 1) { | |||
| 703 | free_page++; | |||
| 704 | if (free_page >= NCACHED32) { | |||
| 705 | (void)write(STDERR_FILENO2, OVMSG"HASH: Out of overflow pages. Increase page size\n", sizeof(OVMSG"HASH: Out of overflow pages. Increase page size\n") - 1); | |||
| 706 | errno(*__errno()) = EFBIG27; | |||
| 707 | return (0); | |||
| 708 | } | |||
| 709 | /* | |||
| 710 | * This is tricky. The 1 indicates that you want the new page | |||
| 711 | * allocated with 1 clear bit. Actually, you are going to | |||
| 712 | * allocate 2 pages from this map. The first is going to be | |||
| 713 | * the map page, the second is the overflow page we were | |||
| 714 | * looking for. The init_bitmap routine automatically, sets | |||
| 715 | * the first bit of itself to indicate that the bitmap itself | |||
| 716 | * is in use. We would explicitly set the second bit, but | |||
| 717 | * don't have to if we tell init_bitmap not to leave it clear | |||
| 718 | * in the first place. | |||
| 719 | */ | |||
| 720 | if (__ibitmap(hashp, | |||
| 721 | (int)OADDR_OF(splitnum, offset)((u_int32_t)((u_int32_t)(splitnum) << 11) + (offset)), 1, free_page)) | |||
| 722 | return (0); | |||
| 723 | hashp->SPAREShdr.spares[splitnum]++; | |||
| 724 | #ifdef DEBUG2 | |||
| 725 | free_bit = 2; | |||
| 726 | #endif | |||
| 727 | offset++; | |||
| 728 | if (offset > SPLITMASK0x7FF) { | |||
| 729 | if (++splitnum >= NCACHED32) { | |||
| 730 | (void)write(STDERR_FILENO2, OVMSG"HASH: Out of overflow pages. Increase page size\n", | |||
| 731 | sizeof(OVMSG"HASH: Out of overflow pages. Increase page size\n") - 1); | |||
| 732 | errno(*__errno()) = EFBIG27; | |||
| 733 | return (0); | |||
| 734 | } | |||
| 735 | hashp->OVFL_POINThdr.ovfl_point = splitnum; | |||
| 736 | hashp->SPAREShdr.spares[splitnum] = hashp->SPAREShdr.spares[splitnum-1]; | |||
| 737 | hashp->SPAREShdr.spares[splitnum-1]--; | |||
| 738 | offset = 0; | |||
| 739 | } | |||
| 740 | } else { | |||
| 741 | /* | |||
| 742 | * Free_bit addresses the last used bit. Bump it to address | |||
| 743 | * the first available bit. | |||
| 744 | */ | |||
| 745 | free_bit++; | |||
| 746 | SETBIT(freep, free_bit)((freep)[(free_bit)/32] |= (1<<((free_bit)%32))); | |||
| ||||
| 747 | } | |||
| 748 | ||||
| 749 | /* Calculate address of the new overflow page */ | |||
| 750 | addr = OADDR_OF(splitnum, offset)((u_int32_t)((u_int32_t)(splitnum) << 11) + (offset)); | |||
| 751 | #ifdef DEBUG2 | |||
| 752 | (void)fprintf(stderr(&__sF[2]), "OVERFLOW_PAGE: ADDR: %d BIT: %d PAGE %d\n", | |||
| 753 | addr, free_bit, free_page); | |||
| 754 | #endif | |||
| 755 | return (addr); | |||
| 756 | ||||
| 757 | found: | |||
| 758 | bit = bit + first_free(freep[j]); | |||
| 759 | SETBIT(freep, bit)((freep)[(bit)/32] |= (1<<((bit)%32))); | |||
| 760 | #ifdef DEBUG2 | |||
| 761 | tmp1 = bit; | |||
| 762 | tmp2 = i; | |||
| 763 | #endif | |||
| 764 | /* | |||
| 765 | * Bits are addressed starting with 0, but overflow pages are addressed | |||
| 766 | * beginning at 1. Bit is a bit addressnumber, so we need to increment | |||
| 767 | * it to convert it to a page number. | |||
| 768 | */ | |||
| 769 | bit = 1 + bit + (i * (hashp->BSIZEhdr.bsize << BYTE_SHIFT3)); | |||
| 770 | if (bit >= hashp->LAST_FREEDhdr.last_freed) | |||
| 771 | hashp->LAST_FREEDhdr.last_freed = bit - 1; | |||
| 772 | ||||
| 773 | /* Calculate the split number for this page */ | |||
| 774 | for (i = 0; (i < splitnum) && (bit > hashp->SPAREShdr.spares[i]); i++); | |||
| 775 | offset = (i ? bit - hashp->SPAREShdr.spares[i - 1] : bit); | |||
| 776 | if (offset >= SPLITMASK0x7FF) { | |||
| 777 | (void)write(STDERR_FILENO2, OVMSG"HASH: Out of overflow pages. Increase page size\n", sizeof(OVMSG"HASH: Out of overflow pages. Increase page size\n") - 1); | |||
| 778 | errno(*__errno()) = EFBIG27; | |||
| 779 | return (0); /* Out of overflow pages */ | |||
| 780 | } | |||
| 781 | addr = OADDR_OF(i, offset)((u_int32_t)((u_int32_t)(i) << 11) + (offset)); | |||
| 782 | #ifdef DEBUG2 | |||
| 783 | (void)fprintf(stderr(&__sF[2]), "OVERFLOW_PAGE: ADDR: %d BIT: %d PAGE %d\n", | |||
| 784 | addr, tmp1, tmp2); | |||
| 785 | #endif | |||
| 786 | ||||
| 787 | /* Allocate and return the overflow page */ | |||
| 788 | return (addr); | |||
| 789 | } | |||
| 790 | ||||
| 791 | /* | |||
| 792 | * Mark this overflow page as free. | |||
| 793 | */ | |||
| 794 | void | |||
| 795 | __free_ovflpage(HTAB *hashp, BUFHEAD *obufp) | |||
| 796 | { | |||
| 797 | u_int16_t addr; | |||
| 798 | u_int32_t *freep; | |||
| 799 | int bit_address, free_page, free_bit; | |||
| 800 | u_int16_t ndx; | |||
| 801 | ||||
| 802 | addr = obufp->addr; | |||
| 803 | #ifdef DEBUG1 | |||
| 804 | (void)fprintf(stderr(&__sF[2]), "Freeing %d\n", addr); | |||
| 805 | #endif | |||
| 806 | ndx = (((u_int16_t)addr) >> SPLITSHIFT11); | |||
| 807 | bit_address = | |||
| 808 | (ndx ? hashp->SPAREShdr.spares[ndx - 1] : 0) + (addr & SPLITMASK0x7FF) - 1; | |||
| 809 | if (bit_address < hashp->LAST_FREEDhdr.last_freed) | |||
| 810 | hashp->LAST_FREEDhdr.last_freed = bit_address; | |||
| 811 | free_page = (bit_address >> (hashp->BSHIFThdr.bshift + BYTE_SHIFT3)); | |||
| 812 | free_bit = bit_address & ((hashp->BSIZEhdr.bsize << BYTE_SHIFT3) - 1); | |||
| 813 | ||||
| 814 | if (!(freep = hashp->mapp[free_page])) | |||
| 815 | freep = fetch_bitmap(hashp, free_page); | |||
| 816 | #ifdef DEBUG | |||
| 817 | /* | |||
| 818 | * This had better never happen. It means we tried to read a bitmap | |||
| 819 | * that has already had overflow pages allocated off it, and we | |||
| 820 | * failed to read it from the file. | |||
| 821 | */ | |||
| 822 | if (!freep) | |||
| 823 | assert(0); | |||
| 824 | #endif | |||
| 825 | CLRBIT(freep, free_bit)((freep)[(free_bit)/32] &= ~(1<<((free_bit)%32))); | |||
| 826 | #ifdef DEBUG2 | |||
| 827 | (void)fprintf(stderr(&__sF[2]), "FREE_OVFLPAGE: ADDR: %d BIT: %d PAGE %d\n", | |||
| 828 | obufp->addr, free_bit, free_page); | |||
| 829 | #endif | |||
| 830 | __reclaim_buf(hashp, obufp); | |||
| 831 | } | |||
| 832 | ||||
| 833 | /* | |||
| 834 | * Returns: | |||
| 835 | * 0 success | |||
| 836 | * -1 failure | |||
| 837 | */ | |||
| 838 | static int | |||
| 839 | open_temp(HTAB *hashp) | |||
| 840 | { | |||
| 841 | sigset_t set, oset; | |||
| 842 | int len; | |||
| 843 | char *envtmp = NULL((void *)0); | |||
| 844 | char path[PATH_MAX1024]; | |||
| 845 | ||||
| 846 | if (issetugid() == 0) | |||
| 847 | envtmp = getenv("TMPDIR"); | |||
| 848 | len = snprintf(path, | |||
| 849 | sizeof(path), "%s/_hash.XXXXXX", envtmp ? envtmp : "/tmp"); | |||
| 850 | if (len < 0 || len >= sizeof(path)) { | |||
| 851 | errno(*__errno()) = ENAMETOOLONG63; | |||
| 852 | return (-1); | |||
| 853 | } | |||
| 854 | ||||
| 855 | /* Block signals; make sure file goes away at process exit. */ | |||
| 856 | (void)sigfillset(&set); | |||
| 857 | (void)sigprocmask(SIG_BLOCK1, &set, &oset); | |||
| 858 | if ((hashp->fp = mkostemp(path, O_CLOEXEC0x10000)) != -1) { | |||
| 859 | (void)unlink(path); | |||
| 860 | } | |||
| 861 | (void)sigprocmask(SIG_SETMASK3, &oset, (sigset_t *)NULL((void *)0)); | |||
| 862 | return (hashp->fp != -1 ? 0 : -1); | |||
| 863 | } | |||
| 864 | ||||
| 865 | /* | |||
| 866 | * We have to know that the key will fit, but the last entry on the page is | |||
| 867 | * an overflow pair, so we need to shift things. | |||
| 868 | */ | |||
| 869 | static void | |||
| 870 | squeeze_key(u_int16_t *sp, const DBT *key, const DBT *val) | |||
| 871 | { | |||
| 872 | char *p; | |||
| 873 | u_int16_t free_space, n, off, pageno; | |||
| 874 | ||||
| 875 | p = (char *)sp; | |||
| 876 | n = sp[0]; | |||
| 877 | free_space = FREESPACE(sp)((sp)[(sp)[0]+1]); | |||
| 878 | off = OFFSET(sp)((sp)[(sp)[0]+2]); | |||
| 879 | ||||
| 880 | pageno = sp[n - 1]; | |||
| 881 | off -= key->size; | |||
| 882 | sp[n - 1] = off; | |||
| 883 | memmove(p + off, key->data, key->size); | |||
| 884 | off -= val->size; | |||
| 885 | sp[n] = off; | |||
| 886 | memmove(p + off, val->data, val->size); | |||
| 887 | sp[0] = n + 2; | |||
| 888 | sp[n + 1] = pageno; | |||
| 889 | sp[n + 2] = OVFLPAGE0; | |||
| 890 | FREESPACE(sp)((sp)[(sp)[0]+1]) = free_space - PAIRSIZE(key, val)(2*sizeof(u_int16_t) + (key)->size + (val)->size); | |||
| 891 | OFFSET(sp)((sp)[(sp)[0]+2]) = off; | |||
| 892 | } | |||
| 893 | ||||
| 894 | static u_int32_t * | |||
| 895 | fetch_bitmap(HTAB *hashp, int ndx) | |||
| 896 | { | |||
| 897 | if (ndx >= hashp->nmaps) | |||
| 898 | return (NULL((void *)0)); | |||
| 899 | if ((hashp->mapp[ndx] = (u_int32_t *)malloc(hashp->BSIZEhdr.bsize)) == NULL((void *)0)) | |||
| 900 | return (NULL((void *)0)); | |||
| 901 | if (__get_page(hashp, | |||
| 902 | (char *)hashp->mapp[ndx], hashp->BITMAPShdr.bitmaps[ndx], 0, 1, 1)) { | |||
| 903 | free(hashp->mapp[ndx]); | |||
| 904 | return (NULL((void *)0)); | |||
| 905 | } | |||
| 906 | return (hashp->mapp[ndx]); | |||
| 907 | } | |||
| 908 | ||||
| 909 | #ifdef DEBUG4 | |||
| 910 | int | |||
| 911 | print_chain(int addr) | |||
| 912 | { | |||
| 913 | BUFHEAD *bufp; | |||
| 914 | short *bp, oaddr; | |||
| 915 | ||||
| 916 | (void)fprintf(stderr(&__sF[2]), "%d ", addr); | |||
| 917 | bufp = __get_buf(hashp, addr, NULL((void *)0), 0); | |||
| 918 | bp = (short *)bufp->page; | |||
| 919 | while (bp[0] && ((bp[bp[0]] == OVFLPAGE0) || | |||
| 920 | ((bp[0] > 2) && bp[2] < REAL_KEY4))) { | |||
| 921 | oaddr = bp[bp[0] - 1]; | |||
| 922 | (void)fprintf(stderr(&__sF[2]), "%d ", (int)oaddr); | |||
| 923 | bufp = __get_buf(hashp, (int)oaddr, bufp, 0); | |||
| 924 | bp = (short *)bufp->page; | |||
| 925 | } | |||
| 926 | (void)fprintf(stderr(&__sF[2]), "\n"); | |||
| 927 | } | |||
| 928 | #endif |