File: | src/lib/libc/db/hash/hash_page.c |
Warning: | line 330, column 4 Value stored to 'n' is never read |
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; |
Value stored to 'n' is never read | |
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 |