1 /*-
2 * Copyright (c) 1990, 1993, 1994
3 * The Regents of the University of California. All rights reserved.
4 *
5 * This code is derived from software contributed to Berkeley by
6 * Margo Seltzer.
7 *
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
10 * are met:
11 * 1. Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 * 2. Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in the
15 * documentation and/or other materials provided with the distribution.
16 * 3. All advertising materials mentioning features or use of this software
17 * must display the following acknowledgement:
18 * This product includes software developed by the University of
19 * California, Berkeley and its contributors.
20 * 4. Neither the name of the University nor the names of its contributors
21 * may be used to endorse or promote products derived from this software
22 * without specific prior written permission.
23 *
24 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
25 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
26 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
27 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
28 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
29 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
30 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
31 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
32 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
33 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
34 * SUCH DAMAGE.
35 */
36
37 #if defined(LIBC_SCCS) && !defined(lint)
38 static char sccsid[] = "@(#)hash_buf.c 8.5 (Berkeley) 7/15/94";
39 #endif /* LIBC_SCCS and not lint */
40
41 /*
42 * PACKAGE: hash
43 *
44 * DESCRIPTION:
45 * Contains buffer management
46 *
47 * ROUTINES:
48 * External
49 * __buf_init
50 * __get_buf
51 * __buf_free
52 * __reclaim_buf
53 * Internal
54 * newbuf
55 */
56
57 #include <sys/param.h>
58
59 #include <errno.h>
60 #include <stddef.h>
61 #include <stdio.h>
62 #include <stdlib.h>
63
64 #ifdef DEBUG
65 #include <assert.h>
66 #endif
67
68 #include <db.h>
69 #include "hash.h"
70 #include "page.h"
71 #include "extern.h"
72
73 static BUFHEAD *newbuf __P((HTAB *, u_int32_t, BUFHEAD *));
74
75 /* Unlink B from its place in the lru */
76 #define BUF_REMOVE(B) { \
77 (B)->prev->next = (B)->next; \
78 (B)->next->prev = (B)->prev; \
79 }
80
81 /* Insert B after P */
82 #define BUF_INSERT(B, P) { \
83 (B)->next = (P)->next; \
84 (B)->prev = (P); \
85 (P)->next = (B); \
86 (B)->next->prev = (B); \
87 }
88
89 #define MRU hashp->bufhead.next
90 #define LRU hashp->bufhead.prev
91
92 #define MRU_INSERT(B) BUF_INSERT((B), &hashp->bufhead)
93 #define LRU_INSERT(B) BUF_INSERT((B), LRU)
94
95 /*
96 * We are looking for a buffer with address "addr". If prev_bp is NULL, then
97 * address is a bucket index. If prev_bp is not NULL, then it points to the
98 * page previous to an overflow page that we are trying to find.
99 *
100 * CAVEAT: The buffer header accessed via prev_bp's ovfl field may no longer
101 * be valid. Therefore, you must always verify that its address matches the
102 * address you are seeking.
103 */
104 extern BUFHEAD *
105 __get_buf(hashp, addr, prev_bp, newpage)
106 HTAB *hashp;
107 u_int32_t addr;
108 BUFHEAD *prev_bp;
109 int newpage; /* If prev_bp set, indicates a new overflow page. */
110 {
111 register BUFHEAD *bp;
112 register u_int32_t is_disk_mask;
113 register int is_disk, segment_ndx;
114 SEGMENT segp;
115
116 is_disk = 0;
117 is_disk_mask = 0;
118 if (prev_bp) {
119 bp = prev_bp->ovfl;
120 if (!bp || (bp->addr != addr))
121 bp = NULL;
122 if (!newpage)
123 is_disk = BUF_DISK;
124 } else {
125 /* Grab buffer out of directory */
126 segment_ndx = addr & (hashp->SGSIZE - 1);
127
128 /* valid segment ensured by __call_hash() */
129 segp = hashp->dir[addr >> hashp->SSHIFT];
130 #ifdef DEBUG
131 assert(segp != NULL);
132 #endif
133 bp = PTROF(segp[segment_ndx]);
134 is_disk_mask = ISDISK(segp[segment_ndx]);
135 is_disk = is_disk_mask || !hashp->new_file;
136 }
137
138 if (!bp) {
139 bp = newbuf(hashp, addr, prev_bp);
140 if (!bp ||
141 __get_page(hashp, bp->page, addr, !prev_bp, is_disk, 0))
142 return (NULL);
143 if (!prev_bp)
144 segp[segment_ndx] =
145 (BUFHEAD *)((ptrdiff_t)bp | is_disk_mask);
146 } else {
147 BUF_REMOVE(bp);
148 MRU_INSERT(bp);
149 }
150 return (bp);
151 }
152
153 /*
154 * We need a buffer for this page. Either allocate one, or evict a resident
155 * one (if we have as many buffers as we're allowed) and put this one in.
156 *
157 * If newbuf finds an error (returning NULL), it also sets errno.
158 */
159 static BUFHEAD *
newbuf(hashp,addr,prev_bp)160 newbuf(hashp, addr, prev_bp)
161 HTAB *hashp;
162 u_int32_t addr;
163 BUFHEAD *prev_bp;
164 {
165 register BUFHEAD *bp; /* The buffer we're going to use */
166 register BUFHEAD *xbp; /* Temp pointer */
167 register BUFHEAD *next_xbp;
168 SEGMENT segp;
169 int segment_ndx;
170 u_int16_t oaddr, *shortp;
171
172 oaddr = 0;
173 bp = LRU;
174 /*
175 * If LRU buffer is pinned, the buffer pool is too small. We need to
176 * allocate more buffers.
177 */
178 if (hashp->nbufs || (bp->flags & BUF_PIN)) {
179 /* Allocate a new one */
180 if ((bp = (BUFHEAD *)malloc(sizeof(BUFHEAD))) == NULL)
181 return (NULL);
182 #ifdef PURIFY
183 memset(bp, 0xff, sizeof(BUFHEAD));
184 #endif
185 if ((bp->page = (char *)malloc(hashp->BSIZE)) == NULL) {
186 free(bp);
187 return (NULL);
188 }
189 #ifdef PURIFY
190 memset(bp->page, 0xff, hashp->BSIZE);
191 #endif
192 if (hashp->nbufs)
193 hashp->nbufs--;
194 } else {
195 /* Kick someone out */
196 BUF_REMOVE(bp);
197 /*
198 * If this is an overflow page with addr 0, it's already been
199 * flushed back in an overflow chain and initialized.
200 */
201 if ((bp->addr != 0) || (bp->flags & BUF_BUCKET)) {
202 /*
203 * Set oaddr before __put_page so that you get it
204 * before bytes are swapped.
205 */
206 shortp = (u_int16_t *)bp->page;
207 if (shortp[0])
208 oaddr = shortp[shortp[0] - 1];
209 if ((bp->flags & BUF_MOD) && __put_page(hashp, bp->page,
210 bp->addr, (int)IS_BUCKET(bp->flags), 0))
211 return (NULL);
212 /*
213 * Update the pointer to this page (i.e. invalidate it).
214 *
215 * If this is a new file (i.e. we created it at open
216 * time), make sure that we mark pages which have been
217 * written to disk so we retrieve them from disk later,
218 * rather than allocating new pages.
219 */
220 if (IS_BUCKET(bp->flags)) {
221 segment_ndx = bp->addr & (hashp->SGSIZE - 1);
222 segp = hashp->dir[bp->addr >> hashp->SSHIFT];
223 #ifdef DEBUG
224 assert(segp != NULL);
225 #endif
226
227 if (hashp->new_file &&
228 ((bp->flags & BUF_MOD) ||
229 ISDISK(segp[segment_ndx])))
230 segp[segment_ndx] = (BUFHEAD *)BUF_DISK;
231 else
232 segp[segment_ndx] = NULL;
233 }
234 /*
235 * Since overflow pages can only be access by means of
236 * their bucket, free overflow pages associated with
237 * this bucket.
238 */
239 for (xbp = bp; xbp->ovfl;) {
240 next_xbp = xbp->ovfl;
241 xbp->ovfl = 0;
242 xbp = next_xbp;
243
244 /* Check that ovfl pointer is up date. */
245 if (IS_BUCKET(xbp->flags) ||
246 (oaddr != xbp->addr))
247 break;
248
249 shortp = (u_int16_t *)xbp->page;
250 if (shortp[0])
251 /* set before __put_page */
252 oaddr = shortp[shortp[0] - 1];
253 if ((xbp->flags & BUF_MOD) && __put_page(hashp,
254 xbp->page, xbp->addr, 0, 0))
255 return (NULL);
256 xbp->addr = 0;
257 xbp->flags = 0;
258 BUF_REMOVE(xbp);
259 LRU_INSERT(xbp);
260 }
261 }
262 }
263
264 /* Now assign this buffer */
265 bp->addr = addr;
266 #ifdef DEBUG1
267 (void)fprintf(stderr, "NEWBUF1: %d->ovfl was %d is now %d\n",
268 bp->addr, (bp->ovfl ? bp->ovfl->addr : 0), 0);
269 #endif
270 bp->ovfl = NULL;
271 if (prev_bp) {
272 /*
273 * If prev_bp is set, this is an overflow page, hook it in to
274 * the buffer overflow links.
275 */
276 #ifdef DEBUG1
277 (void)fprintf(stderr, "NEWBUF2: %d->ovfl was %d is now %d\n",
278 prev_bp->addr, (prev_bp->ovfl ? bp->ovfl->addr : 0),
279 (bp ? bp->addr : 0));
280 #endif
281 prev_bp->ovfl = bp;
282 bp->flags = 0;
283 } else
284 bp->flags = BUF_BUCKET;
285 MRU_INSERT(bp);
286 return (bp);
287 }
288
289 extern void
290 __buf_init(hashp, nbytes)
291 HTAB *hashp;
292 int nbytes;
293 {
294 BUFHEAD *bfp;
295 int npages;
296
297 bfp = &(hashp->bufhead);
298 npages = (nbytes + hashp->BSIZE - 1) >> hashp->BSHIFT;
299 npages = MAX(npages, MIN_BUFFERS);
300
301 hashp->nbufs = npages;
302 bfp->next = bfp;
303 bfp->prev = bfp;
304 /*
305 * This space is calloc'd so these are already null.
306 *
307 * bfp->ovfl = NULL;
308 * bfp->flags = 0;
309 * bfp->page = NULL;
310 * bfp->addr = 0;
311 */
312 }
313
314 extern int
315 __buf_free(hashp, do_free, to_disk)
316 HTAB *hashp;
317 int do_free, to_disk;
318 {
319 BUFHEAD *bp;
320
321 /* Need to make sure that buffer manager has been initialized */
322 if (!LRU)
323 return (0);
324 for (bp = LRU; bp != &hashp->bufhead;) {
325 /* Check that the buffer is valid */
326 if (bp->addr || IS_BUCKET(bp->flags)) {
327 if (to_disk && (bp->flags & BUF_MOD) &&
328 __put_page(hashp, bp->page,
329 bp->addr, IS_BUCKET(bp->flags), 0))
330 return (-1);
331 }
332 /* Check if we are freeing stuff */
333 if (do_free) {
334 if (bp->page)
335 free(bp->page);
336 BUF_REMOVE(bp);
337 free(bp);
338 bp = LRU;
339 } else
340 bp = bp->prev;
341 }
342 return (0);
343 }
344
345 extern void
346 __reclaim_buf(hashp, bp)
347 HTAB *hashp;
348 BUFHEAD *bp;
349 {
350 bp->ovfl = 0;
351 bp->addr = 0;
352 bp->flags = 0;
353 BUF_REMOVE(bp);
354 LRU_INSERT(bp);
355 }
356