| File: | src/lib/libc/db/hash/hash_buf.c |
| Warning: | line 328, column 7 Use of memory after it is freed |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
| 1 | /* $OpenBSD: hash_buf.c,v 1.19 2015/01/16 16:48:51 deraadt 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: hash | |||
| 37 | * | |||
| 38 | * DESCRIPTION: | |||
| 39 | * Contains buffer management | |||
| 40 | * | |||
| 41 | * ROUTINES: | |||
| 42 | * External | |||
| 43 | * __buf_init | |||
| 44 | * __get_buf | |||
| 45 | * __buf_free | |||
| 46 | * __reclaim_buf | |||
| 47 | * Internal | |||
| 48 | * newbuf | |||
| 49 | */ | |||
| 50 | ||||
| 51 | #include <errno(*__errno()).h> | |||
| 52 | #include <stddef.h> | |||
| 53 | #include <stdio.h> | |||
| 54 | #include <stdlib.h> | |||
| 55 | #include <string.h> | |||
| 56 | ||||
| 57 | #ifdef DEBUG | |||
| 58 | #include <assert.h> | |||
| 59 | #endif | |||
| 60 | ||||
| 61 | #include <db.h> | |||
| 62 | #include "hash.h" | |||
| 63 | #include "page.h" | |||
| 64 | #include "extern.h" | |||
| 65 | ||||
| 66 | #define MAXIMUM(a, b)(((a) > (b)) ? (a) : (b)) (((a) > (b)) ? (a) : (b)) | |||
| 67 | ||||
| 68 | static BUFHEAD *newbuf(HTAB *, u_int32_t, BUFHEAD *); | |||
| 69 | ||||
| 70 | /* Unlink B from its place in the lru */ | |||
| 71 | #define BUF_REMOVE(B){ (B)->prev->next = (B)->next; (B)->next->prev = (B)->prev; } { \ | |||
| 72 | (B)->prev->next = (B)->next; \ | |||
| 73 | (B)->next->prev = (B)->prev; \ | |||
| 74 | } | |||
| 75 | ||||
| 76 | /* Insert B after P */ | |||
| 77 | #define BUF_INSERT(B, P){ (B)->next = (P)->next; (B)->prev = (P); (P)->next = (B); (B)->next->prev = (B); } { \ | |||
| 78 | (B)->next = (P)->next; \ | |||
| 79 | (B)->prev = (P); \ | |||
| 80 | (P)->next = (B); \ | |||
| 81 | (B)->next->prev = (B); \ | |||
| 82 | } | |||
| 83 | ||||
| 84 | #define MRUhashp->bufhead.next hashp->bufhead.next | |||
| 85 | #define LRUhashp->bufhead.prev hashp->bufhead.prev | |||
| 86 | ||||
| 87 | #define MRU_INSERT(B){ ((B))->next = (&hashp->bufhead)->next; ((B))-> prev = (&hashp->bufhead); (&hashp->bufhead)-> next = ((B)); ((B))->next->prev = ((B)); } BUF_INSERT((B), &hashp->bufhead){ ((B))->next = (&hashp->bufhead)->next; ((B))-> prev = (&hashp->bufhead); (&hashp->bufhead)-> next = ((B)); ((B))->next->prev = ((B)); } | |||
| 88 | #define LRU_INSERT(B){ ((B))->next = (hashp->bufhead.prev)->next; ((B))-> prev = (hashp->bufhead.prev); (hashp->bufhead.prev)-> next = ((B)); ((B))->next->prev = ((B)); } BUF_INSERT((B), LRU){ ((B))->next = (hashp->bufhead.prev)->next; ((B))-> prev = (hashp->bufhead.prev); (hashp->bufhead.prev)-> next = ((B)); ((B))->next->prev = ((B)); } | |||
| 89 | ||||
| 90 | /* | |||
| 91 | * We are looking for a buffer with address "addr". If prev_bp is NULL, then | |||
| 92 | * address is a bucket index. If prev_bp is not NULL, then it points to the | |||
| 93 | * page previous to an overflow page that we are trying to find. | |||
| 94 | * | |||
| 95 | * CAVEAT: The buffer header accessed via prev_bp's ovfl field may no longer | |||
| 96 | * be valid. Therefore, you must always verify that its address matches the | |||
| 97 | * address you are seeking. | |||
| 98 | */ | |||
| 99 | BUFHEAD * | |||
| 100 | __get_buf(HTAB *hashp, u_int32_t addr, | |||
| 101 | BUFHEAD *prev_bp, /* If prev_bp set, indicates a new overflow page. */ | |||
| 102 | int newpage) | |||
| 103 | { | |||
| 104 | BUFHEAD *bp; | |||
| 105 | u_int32_t is_disk_mask; | |||
| 106 | int is_disk, segment_ndx; | |||
| 107 | SEGMENT segp; | |||
| 108 | ||||
| 109 | is_disk = 0; | |||
| 110 | is_disk_mask = 0; | |||
| 111 | if (prev_bp) { | |||
| 112 | bp = prev_bp->ovfl; | |||
| 113 | if (!bp || (bp->addr != addr)) | |||
| 114 | bp = NULL((void*)0); | |||
| 115 | if (!newpage) | |||
| 116 | is_disk = BUF_DISK0x0002; | |||
| 117 | } else { | |||
| 118 | /* Grab buffer out of directory */ | |||
| 119 | segment_ndx = addr & (hashp->SGSIZEhdr.ssize - 1); | |||
| 120 | ||||
| 121 | /* valid segment ensured by __call_hash() */ | |||
| 122 | segp = hashp->dir[addr >> hashp->SSHIFThdr.sshift]; | |||
| 123 | #ifdef DEBUG | |||
| 124 | assert(segp != NULL((void*)0)); | |||
| 125 | #endif | |||
| 126 | bp = PTROF(segp[segment_ndx])((BUFHEAD *)((ptrdiff_t)(segp[segment_ndx])&~0x3)); | |||
| 127 | is_disk_mask = ISDISK(segp[segment_ndx])((u_int32_t)(ptrdiff_t)(segp[segment_ndx])&0x2); | |||
| 128 | is_disk = is_disk_mask || !hashp->new_file; | |||
| 129 | } | |||
| 130 | ||||
| 131 | if (!bp) { | |||
| 132 | bp = newbuf(hashp, addr, prev_bp); | |||
| 133 | if (!bp || | |||
| 134 | __get_page(hashp, bp->page, addr, !prev_bp, is_disk, 0)) | |||
| 135 | return (NULL((void*)0)); | |||
| 136 | if (!prev_bp) | |||
| 137 | segp[segment_ndx] = | |||
| 138 | (BUFHEAD *)((ptrdiff_t)bp | is_disk_mask); | |||
| 139 | } else { | |||
| 140 | BUF_REMOVE(bp){ (bp)->prev->next = (bp)->next; (bp)->next->prev = (bp)->prev; }; | |||
| 141 | MRU_INSERT(bp){ ((bp))->next = (&hashp->bufhead)->next; ((bp)) ->prev = (&hashp->bufhead); (&hashp->bufhead )->next = ((bp)); ((bp))->next->prev = ((bp)); }; | |||
| 142 | } | |||
| 143 | return (bp); | |||
| 144 | } | |||
| 145 | ||||
| 146 | /* | |||
| 147 | * We need a buffer for this page. Either allocate one, or evict a resident | |||
| 148 | * one (if we have as many buffers as we're allowed) and put this one in. | |||
| 149 | * | |||
| 150 | * If newbuf finds an error (returning NULL), it also sets errno. | |||
| 151 | */ | |||
| 152 | static BUFHEAD * | |||
| 153 | newbuf(HTAB *hashp, u_int32_t addr, BUFHEAD *prev_bp) | |||
| 154 | { | |||
| 155 | BUFHEAD *bp; /* The buffer we're going to use */ | |||
| 156 | BUFHEAD *xbp; /* Temp pointer */ | |||
| 157 | BUFHEAD *next_xbp; | |||
| 158 | SEGMENT segp; | |||
| 159 | int segment_ndx; | |||
| 160 | u_int16_t oaddr, *shortp; | |||
| 161 | ||||
| 162 | oaddr = 0; | |||
| 163 | bp = LRUhashp->bufhead.prev; | |||
| 164 | ||||
| 165 | /* It is bad to overwrite the page under the cursor. */ | |||
| 166 | if (bp == hashp->cpage) { | |||
| 167 | BUF_REMOVE(bp){ (bp)->prev->next = (bp)->next; (bp)->next->prev = (bp)->prev; }; | |||
| 168 | MRU_INSERT(bp){ ((bp))->next = (&hashp->bufhead)->next; ((bp)) ->prev = (&hashp->bufhead); (&hashp->bufhead )->next = ((bp)); ((bp))->next->prev = ((bp)); }; | |||
| 169 | bp = LRUhashp->bufhead.prev; | |||
| 170 | } | |||
| 171 | ||||
| 172 | /* If prev_bp is part of bp overflow, create a new buffer. */ | |||
| 173 | if (hashp->nbufs == 0 && prev_bp && bp->ovfl) { | |||
| 174 | BUFHEAD *ovfl; | |||
| 175 | ||||
| 176 | for (ovfl = bp->ovfl; ovfl ; ovfl = ovfl->ovfl) { | |||
| 177 | if (ovfl == prev_bp) { | |||
| 178 | hashp->nbufs++; | |||
| 179 | break; | |||
| 180 | } | |||
| 181 | } | |||
| 182 | } | |||
| 183 | ||||
| 184 | /* | |||
| 185 | * If LRU buffer is pinned, the buffer pool is too small. We need to | |||
| 186 | * allocate more buffers. | |||
| 187 | */ | |||
| 188 | if (hashp->nbufs || (bp->flags & BUF_PIN0x0008) || bp == hashp->cpage) { | |||
| 189 | /* Allocate a new one */ | |||
| 190 | if ((bp = (BUFHEAD *)malloc(sizeof(BUFHEAD))) == NULL((void*)0)) | |||
| 191 | return (NULL((void*)0)); | |||
| 192 | memset(bp, 0xff, sizeof(BUFHEAD)); | |||
| 193 | if ((bp->page = (char *)malloc(hashp->BSIZEhdr.bsize)) == NULL((void*)0)) { | |||
| 194 | free(bp); | |||
| 195 | return (NULL((void*)0)); | |||
| 196 | } | |||
| 197 | memset(bp->page, 0xff, hashp->BSIZEhdr.bsize); | |||
| 198 | if (hashp->nbufs) | |||
| 199 | hashp->nbufs--; | |||
| 200 | } else { | |||
| 201 | /* Kick someone out */ | |||
| 202 | BUF_REMOVE(bp){ (bp)->prev->next = (bp)->next; (bp)->next->prev = (bp)->prev; }; | |||
| 203 | /* | |||
| 204 | * If this is an overflow page with addr 0, it's already been | |||
| 205 | * flushed back in an overflow chain and initialized. | |||
| 206 | */ | |||
| 207 | if ((bp->addr != 0) || (bp->flags & BUF_BUCKET0x0004)) { | |||
| 208 | /* | |||
| 209 | * Set oaddr before __put_page so that you get it | |||
| 210 | * before bytes are swapped. | |||
| 211 | */ | |||
| 212 | shortp = (u_int16_t *)bp->page; | |||
| 213 | if (shortp[0]) | |||
| 214 | oaddr = shortp[shortp[0] - 1]; | |||
| 215 | if ((bp->flags & BUF_MOD0x0001) && __put_page(hashp, bp->page, | |||
| 216 | bp->addr, (int)IS_BUCKET(bp->flags)((bp->flags) & 0x0004), 0)) | |||
| 217 | return (NULL((void*)0)); | |||
| 218 | /* | |||
| 219 | * Update the pointer to this page (i.e. invalidate it). | |||
| 220 | * | |||
| 221 | * If this is a new file (i.e. we created it at open | |||
| 222 | * time), make sure that we mark pages which have been | |||
| 223 | * written to disk so we retrieve them from disk later, | |||
| 224 | * rather than allocating new pages. | |||
| 225 | */ | |||
| 226 | if (IS_BUCKET(bp->flags)((bp->flags) & 0x0004)) { | |||
| 227 | segment_ndx = bp->addr & (hashp->SGSIZEhdr.ssize - 1); | |||
| 228 | segp = hashp->dir[bp->addr >> hashp->SSHIFThdr.sshift]; | |||
| 229 | #ifdef DEBUG | |||
| 230 | assert(segp != NULL((void*)0)); | |||
| 231 | #endif | |||
| 232 | ||||
| 233 | if (hashp->new_file && | |||
| 234 | ((bp->flags & BUF_MOD0x0001) || | |||
| 235 | ISDISK(segp[segment_ndx])((u_int32_t)(ptrdiff_t)(segp[segment_ndx])&0x2))) | |||
| 236 | segp[segment_ndx] = (BUFHEAD *)BUF_DISK0x0002; | |||
| 237 | else | |||
| 238 | segp[segment_ndx] = NULL((void*)0); | |||
| 239 | } | |||
| 240 | /* | |||
| 241 | * Since overflow pages can only be access by means of | |||
| 242 | * their bucket, free overflow pages associated with | |||
| 243 | * this bucket. | |||
| 244 | */ | |||
| 245 | for (xbp = bp; xbp->ovfl;) { | |||
| 246 | next_xbp = xbp->ovfl; | |||
| 247 | xbp->ovfl = 0; | |||
| 248 | xbp = next_xbp; | |||
| 249 | ||||
| 250 | /* Check that ovfl pointer is up date. */ | |||
| 251 | if (IS_BUCKET(xbp->flags)((xbp->flags) & 0x0004) || | |||
| 252 | (oaddr != xbp->addr)) | |||
| 253 | break; | |||
| 254 | ||||
| 255 | shortp = (u_int16_t *)xbp->page; | |||
| 256 | if (shortp[0]) | |||
| 257 | /* set before __put_page */ | |||
| 258 | oaddr = shortp[shortp[0] - 1]; | |||
| 259 | if ((xbp->flags & BUF_MOD0x0001) && __put_page(hashp, | |||
| 260 | xbp->page, xbp->addr, 0, 0)) | |||
| 261 | return (NULL((void*)0)); | |||
| 262 | xbp->addr = 0; | |||
| 263 | xbp->flags = 0; | |||
| 264 | BUF_REMOVE(xbp){ (xbp)->prev->next = (xbp)->next; (xbp)->next-> prev = (xbp)->prev; }; | |||
| 265 | LRU_INSERT(xbp){ ((xbp))->next = (hashp->bufhead.prev)->next; ((xbp ))->prev = (hashp->bufhead.prev); (hashp->bufhead.prev )->next = ((xbp)); ((xbp))->next->prev = ((xbp)); }; | |||
| 266 | } | |||
| 267 | } | |||
| 268 | } | |||
| 269 | ||||
| 270 | /* Now assign this buffer */ | |||
| 271 | bp->addr = addr; | |||
| 272 | #ifdef DEBUG1 | |||
| 273 | (void)fprintf(stderr(&__sF[2]), "NEWBUF1: %d->ovfl was %d is now %d\n", | |||
| 274 | bp->addr, (bp->ovfl ? bp->ovfl->addr : 0), 0); | |||
| 275 | #endif | |||
| 276 | bp->ovfl = NULL((void*)0); | |||
| 277 | if (prev_bp) { | |||
| 278 | /* | |||
| 279 | * If prev_bp is set, this is an overflow page, hook it in to | |||
| 280 | * the buffer overflow links. | |||
| 281 | */ | |||
| 282 | #ifdef DEBUG1 | |||
| 283 | (void)fprintf(stderr(&__sF[2]), "NEWBUF2: %d->ovfl was %d is now %d\n", | |||
| 284 | prev_bp->addr, (prev_bp->ovfl ? prev_bp->ovfl->addr : 0), | |||
| 285 | (bp ? bp->addr : 0)); | |||
| 286 | #endif | |||
| 287 | prev_bp->ovfl = bp; | |||
| 288 | bp->flags = 0; | |||
| 289 | } else | |||
| 290 | bp->flags = BUF_BUCKET0x0004; | |||
| 291 | MRU_INSERT(bp){ ((bp))->next = (&hashp->bufhead)->next; ((bp)) ->prev = (&hashp->bufhead); (&hashp->bufhead )->next = ((bp)); ((bp))->next->prev = ((bp)); }; | |||
| 292 | return (bp); | |||
| 293 | } | |||
| 294 | ||||
| 295 | void | |||
| 296 | __buf_init(HTAB *hashp, int nbytes) | |||
| 297 | { | |||
| 298 | BUFHEAD *bfp; | |||
| 299 | int npages; | |||
| 300 | ||||
| 301 | bfp = &(hashp->bufhead); | |||
| 302 | npages = (nbytes + hashp->BSIZEhdr.bsize - 1) >> hashp->BSHIFThdr.bshift; | |||
| 303 | npages = MAXIMUM(npages, MIN_BUFFERS)(((npages) > (6)) ? (npages) : (6)); | |||
| 304 | ||||
| 305 | hashp->nbufs = npages; | |||
| 306 | bfp->next = bfp; | |||
| 307 | bfp->prev = bfp; | |||
| 308 | /* | |||
| 309 | * This space is calloc'd so these are already null. | |||
| 310 | * | |||
| 311 | * bfp->ovfl = NULL; | |||
| 312 | * bfp->flags = 0; | |||
| 313 | * bfp->page = NULL; | |||
| 314 | * bfp->addr = 0; | |||
| 315 | */ | |||
| 316 | } | |||
| 317 | ||||
| 318 | int | |||
| 319 | __buf_free(HTAB *hashp, int do_free, int to_disk) | |||
| 320 | { | |||
| 321 | BUFHEAD *bp; | |||
| 322 | ||||
| 323 | /* Need to make sure that buffer manager has been initialized */ | |||
| 324 | if (!LRUhashp->bufhead.prev) | |||
| ||||
| 325 | return (0); | |||
| 326 | for (bp = LRUhashp->bufhead.prev; bp != &hashp->bufhead;) { | |||
| 327 | /* Check that the buffer is valid */ | |||
| 328 | if (bp->addr || IS_BUCKET(bp->flags)((bp->flags) & 0x0004)) { | |||
| ||||
| 329 | if (to_disk && (bp->flags & BUF_MOD0x0001) && | |||
| 330 | __put_page(hashp, bp->page, | |||
| 331 | bp->addr, IS_BUCKET(bp->flags)((bp->flags) & 0x0004), 0)) | |||
| 332 | return (-1); | |||
| 333 | } | |||
| 334 | /* Check if we are freeing stuff */ | |||
| 335 | if (do_free) { | |||
| 336 | if (bp->page) { | |||
| 337 | (void)memset(bp->page, 0, hashp->BSIZEhdr.bsize); | |||
| 338 | free(bp->page); | |||
| 339 | } | |||
| 340 | BUF_REMOVE(bp){ (bp)->prev->next = (bp)->next; (bp)->next->prev = (bp)->prev; }; | |||
| 341 | free(bp); | |||
| 342 | bp = LRUhashp->bufhead.prev; | |||
| 343 | } else | |||
| 344 | bp = bp->prev; | |||
| 345 | } | |||
| 346 | return (0); | |||
| 347 | } | |||
| 348 | ||||
| 349 | void | |||
| 350 | __reclaim_buf(HTAB *hashp, BUFHEAD *bp) | |||
| 351 | { | |||
| 352 | bp->ovfl = 0; | |||
| 353 | bp->addr = 0; | |||
| 354 | bp->flags = 0; | |||
| 355 | BUF_REMOVE(bp){ (bp)->prev->next = (bp)->next; (bp)->next->prev = (bp)->prev; }; | |||
| 356 | LRU_INSERT(bp){ ((bp))->next = (hashp->bufhead.prev)->next; ((bp)) ->prev = (hashp->bufhead.prev); (hashp->bufhead.prev )->next = ((bp)); ((bp))->next->prev = ((bp)); }; | |||
| 357 | } |