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 | } |