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.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)) |
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) { \ |
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) { \ |
78 |
|
|
(B)->next = (P)->next; \ |
79 |
|
|
(B)->prev = (P); \ |
80 |
|
|
(P)->next = (B); \ |
81 |
|
|
(B)->next->prev = (B); \ |
82 |
|
|
} |
83 |
|
|
|
84 |
|
|
#define MRU hashp->bufhead.next |
85 |
|
|
#define LRU hashp->bufhead.prev |
86 |
|
|
|
87 |
|
|
#define MRU_INSERT(B) BUF_INSERT((B), &hashp->bufhead) |
88 |
|
|
#define LRU_INSERT(B) BUF_INSERT((B), LRU) |
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 |
✗✓ |
7768 |
if (prev_bp) { |
112 |
|
|
bp = prev_bp->ovfl; |
113 |
|
|
if (!bp || (bp->addr != addr)) |
114 |
|
|
bp = NULL; |
115 |
|
|
if (!newpage) |
116 |
|
|
is_disk = BUF_DISK; |
117 |
|
|
} else { |
118 |
|
|
/* Grab buffer out of directory */ |
119 |
|
3884 |
segment_ndx = addr & (hashp->SGSIZE - 1); |
120 |
|
|
|
121 |
|
|
/* valid segment ensured by __call_hash() */ |
122 |
|
3884 |
segp = hashp->dir[addr >> hashp->SSHIFT]; |
123 |
|
|
#ifdef DEBUG |
124 |
|
|
assert(segp != NULL); |
125 |
|
|
#endif |
126 |
|
3884 |
bp = PTROF(segp[segment_ndx]); |
127 |
|
3884 |
is_disk_mask = ISDISK(segp[segment_ndx]); |
128 |
✓✗ |
11652 |
is_disk = is_disk_mask || !hashp->new_file; |
129 |
|
|
} |
130 |
|
|
|
131 |
✓✓ |
3884 |
if (!bp) { |
132 |
|
3333 |
bp = newbuf(hashp, addr, prev_bp); |
133 |
✓✗✗✓
|
6666 |
if (!bp || |
134 |
|
3333 |
__get_page(hashp, bp->page, addr, !prev_bp, is_disk, 0)) |
135 |
|
|
return (NULL); |
136 |
✓✗ |
3333 |
if (!prev_bp) |
137 |
|
3333 |
segp[segment_ndx] = |
138 |
|
3333 |
(BUFHEAD *)((ptrdiff_t)bp | is_disk_mask); |
139 |
|
|
} else { |
140 |
|
551 |
BUF_REMOVE(bp); |
141 |
|
551 |
MRU_INSERT(bp); |
142 |
|
|
} |
143 |
|
3884 |
return (bp); |
144 |
|
3884 |
} |
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 |
|
6666 |
bp = LRU; |
164 |
|
|
|
165 |
|
|
/* It is bad to overwrite the page under the cursor. */ |
166 |
✗✓ |
3333 |
if (bp == hashp->cpage) { |
167 |
|
|
BUF_REMOVE(bp); |
168 |
|
|
MRU_INSERT(bp); |
169 |
|
|
bp = LRU; |
170 |
|
|
} |
171 |
|
|
|
172 |
|
|
/* If prev_bp is part of bp overflow, create a new buffer. */ |
173 |
✗✓✗✗
|
3333 |
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 |
✗✓✗✗ ✗✗ |
3333 |
if (hashp->nbufs || (bp->flags & BUF_PIN) || bp == hashp->cpage) { |
189 |
|
|
/* Allocate a new one */ |
190 |
✗✓ |
3333 |
if ((bp = (BUFHEAD *)malloc(sizeof(BUFHEAD))) == NULL) |
191 |
|
|
return (NULL); |
192 |
|
3333 |
memset(bp, 0xff, sizeof(BUFHEAD)); |
193 |
✗✓ |
3333 |
if ((bp->page = (char *)malloc(hashp->BSIZE)) == NULL) { |
194 |
|
|
free(bp); |
195 |
|
|
return (NULL); |
196 |
|
|
} |
197 |
|
3333 |
memset(bp->page, 0xff, hashp->BSIZE); |
198 |
✓✗ |
3333 |
if (hashp->nbufs) |
199 |
|
3333 |
hashp->nbufs--; |
200 |
|
|
} else { |
201 |
|
|
/* Kick someone out */ |
202 |
|
|
BUF_REMOVE(bp); |
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_BUCKET)) { |
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_MOD) && __put_page(hashp, bp->page, |
216 |
|
|
bp->addr, (int)IS_BUCKET(bp->flags), 0)) |
217 |
|
|
return (NULL); |
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)) { |
227 |
|
|
segment_ndx = bp->addr & (hashp->SGSIZE - 1); |
228 |
|
|
segp = hashp->dir[bp->addr >> hashp->SSHIFT]; |
229 |
|
|
#ifdef DEBUG |
230 |
|
|
assert(segp != NULL); |
231 |
|
|
#endif |
232 |
|
|
|
233 |
|
|
if (hashp->new_file && |
234 |
|
|
((bp->flags & BUF_MOD) || |
235 |
|
|
ISDISK(segp[segment_ndx]))) |
236 |
|
|
segp[segment_ndx] = (BUFHEAD *)BUF_DISK; |
237 |
|
|
else |
238 |
|
|
segp[segment_ndx] = NULL; |
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) || |
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_MOD) && __put_page(hashp, |
260 |
|
|
xbp->page, xbp->addr, 0, 0)) |
261 |
|
|
return (NULL); |
262 |
|
|
xbp->addr = 0; |
263 |
|
|
xbp->flags = 0; |
264 |
|
|
BUF_REMOVE(xbp); |
265 |
|
|
LRU_INSERT(xbp); |
266 |
|
|
} |
267 |
|
|
} |
268 |
|
|
} |
269 |
|
|
|
270 |
|
|
/* Now assign this buffer */ |
271 |
|
3333 |
bp->addr = addr; |
272 |
|
|
#ifdef DEBUG1 |
273 |
|
|
(void)fprintf(stderr, "NEWBUF1: %d->ovfl was %d is now %d\n", |
274 |
|
|
bp->addr, (bp->ovfl ? bp->ovfl->addr : 0), 0); |
275 |
|
|
#endif |
276 |
|
3333 |
bp->ovfl = NULL; |
277 |
✗✓ |
3333 |
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, "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_BUCKET; |
291 |
|
3333 |
MRU_INSERT(bp); |
292 |
|
3333 |
return (bp); |
293 |
|
3333 |
} |
294 |
|
|
|
295 |
|
|
void |
296 |
|
|
__buf_init(HTAB *hashp, int nbytes) |
297 |
|
|
{ |
298 |
|
|
BUFHEAD *bfp; |
299 |
|
|
int npages; |
300 |
|
|
|
301 |
|
2360 |
bfp = &(hashp->bufhead); |
302 |
|
1180 |
npages = (nbytes + hashp->BSIZE - 1) >> hashp->BSHIFT; |
303 |
|
1180 |
npages = MAXIMUM(npages, MIN_BUFFERS); |
304 |
|
|
|
305 |
|
1180 |
hashp->nbufs = npages; |
306 |
|
1180 |
bfp->next = bfp; |
307 |
|
1180 |
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 |
|
1180 |
} |
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 |
✗✓ |
2140 |
if (!LRU) |
325 |
|
|
return (0); |
326 |
✓✓ |
5133 |
for (bp = LRU; bp != &hashp->bufhead;) { |
327 |
|
|
/* Check that the buffer is valid */ |
328 |
✓✓✗✓
|
5133 |
if (bp->addr || IS_BUCKET(bp->flags)) { |
329 |
✗✓✗✗ ✗✗ |
2993 |
if (to_disk && (bp->flags & BUF_MOD) && |
330 |
|
|
__put_page(hashp, bp->page, |
331 |
|
|
bp->addr, IS_BUCKET(bp->flags), 0)) |
332 |
|
|
return (-1); |
333 |
|
|
} |
334 |
|
|
/* Check if we are freeing stuff */ |
335 |
✓✗ |
2993 |
if (do_free) { |
336 |
✓✗ |
2993 |
if (bp->page) { |
337 |
|
2993 |
(void)memset(bp->page, 0, hashp->BSIZE); |
338 |
|
2993 |
free(bp->page); |
339 |
|
2993 |
} |
340 |
|
2993 |
BUF_REMOVE(bp); |
341 |
|
2993 |
free(bp); |
342 |
|
2993 |
bp = LRU; |
343 |
|
2993 |
} else |
344 |
|
|
bp = bp->prev; |
345 |
|
|
} |
346 |
|
1070 |
return (0); |
347 |
|
1070 |
} |
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); |
356 |
|
|
LRU_INSERT(bp); |
357 |
|
|
} |