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