2 * Copyright (c) 1990, 1993, 1994
3 * The Regents of the University of California. All rights reserved.
5 * This code is derived from software contributed to Berkeley by
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
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.
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
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 */
45 * Contains buffer management
57 #include <sys/param.h>
73 static BUFHEAD
*newbuf
__P((HTAB
*, u_int32_t
, BUFHEAD
*));
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; \
81 /* Insert B after P */
82 #define BUF_INSERT(B, P) { \
83 (B)->next = (P)->next; \
86 (B)->next->prev = (B); \
89 #define MRU hashp->bufhead.next
90 #define LRU hashp->bufhead.prev
92 #define MRU_INSERT(B) BUF_INSERT((B), &hashp->bufhead)
93 #define LRU_INSERT(B) BUF_INSERT((B), LRU)
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.
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.
105 __get_buf(hashp
, addr
, prev_bp
, newpage
)
109 int newpage
; /* If prev_bp set, indicates a new overflow page. */
111 register BUFHEAD
*bp
;
112 register u_int32_t is_disk_mask
;
113 register int is_disk
, segment_ndx
;
120 if (!bp
|| (bp
->addr
!= addr
))
125 /* Grab buffer out of directory */
126 segment_ndx
= addr
& (hashp
->SGSIZE
- 1);
128 /* valid segment ensured by __call_hash() */
129 segp
= hashp
->dir
[addr
>> hashp
->SSHIFT
];
131 assert(segp
!= NULL
);
133 bp
= PTROF(segp
[segment_ndx
]);
134 is_disk_mask
= ISDISK(segp
[segment_ndx
]);
135 is_disk
= is_disk_mask
|| !hashp
->new_file
;
139 bp
= newbuf(hashp
, addr
, prev_bp
);
141 __get_page(hashp
, bp
->page
, addr
, !prev_bp
, is_disk
, 0))
145 (BUFHEAD
*)((ptrdiff_t)bp
| is_disk_mask
);
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.
157 * If newbuf finds an error (returning NULL), it also sets errno.
160 newbuf(hashp
, addr
, prev_bp
)
165 register BUFHEAD
*bp
; /* The buffer we're going to use */
166 register BUFHEAD
*xbp
; /* Temp pointer */
167 register BUFHEAD
*next_xbp
;
170 u_int16_t oaddr
, *shortp
;
175 * If LRU buffer is pinned, the buffer pool is too small. We need to
176 * allocate more buffers.
178 if (hashp
->nbufs
|| (bp
->flags
& BUF_PIN
)) {
179 /* Allocate a new one */
180 if ((bp
= (BUFHEAD
*)malloc(sizeof(BUFHEAD
))) == NULL
)
183 memset(bp
, 0xff, sizeof(BUFHEAD
));
185 if ((bp
->page
= (char *)malloc(hashp
->BSIZE
)) == NULL
) {
190 memset(bp
->page
, 0xff, hashp
->BSIZE
);
195 /* Kick someone out */
198 * If this is an overflow page with addr 0, it's already been
199 * flushed back in an overflow chain and initialized.
201 if ((bp
->addr
!= 0) || (bp
->flags
& BUF_BUCKET
)) {
203 * Set oaddr before __put_page so that you get it
204 * before bytes are swapped.
206 shortp
= (u_int16_t
*)bp
->page
;
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))
213 * Update the pointer to this page (i.e. invalidate it).
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.
220 if (IS_BUCKET(bp
->flags
)) {
221 segment_ndx
= bp
->addr
& (hashp
->SGSIZE
- 1);
222 segp
= hashp
->dir
[bp
->addr
>> hashp
->SSHIFT
];
224 assert(segp
!= NULL
);
227 if (hashp
->new_file
&&
228 ((bp
->flags
& BUF_MOD
) ||
229 ISDISK(segp
[segment_ndx
])))
230 segp
[segment_ndx
] = (BUFHEAD
*)BUF_DISK
;
232 segp
[segment_ndx
] = NULL
;
235 * Since overflow pages can only be access by means of
236 * their bucket, free overflow pages associated with
239 for (xbp
= bp
; xbp
->ovfl
;) {
240 next_xbp
= xbp
->ovfl
;
244 /* Check that ovfl pointer is up date. */
245 if (IS_BUCKET(xbp
->flags
) ||
246 (oaddr
!= xbp
->addr
))
249 shortp
= (u_int16_t
*)xbp
->page
;
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))
264 /* Now assign this buffer */
267 (void)fprintf(stderr
, "NEWBUF1: %d->ovfl was %d is now %d\n",
268 bp
->addr
, (bp
->ovfl
? bp
->ovfl
->addr
: 0), 0);
273 * If prev_bp is set, this is an overflow page, hook it in to
274 * the buffer overflow links.
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));
284 bp
->flags
= BUF_BUCKET
;
290 __buf_init(hashp
, nbytes
)
297 bfp
= &(hashp
->bufhead
);
298 npages
= (nbytes
+ hashp
->BSIZE
- 1) >> hashp
->BSHIFT
;
299 npages
= MAX(npages
, MIN_BUFFERS
);
301 hashp
->nbufs
= npages
;
305 * This space is calloc'd so these are already null.
315 __buf_free(hashp
, do_free
, to_disk
)
317 int do_free
, to_disk
;
321 /* Need to make sure that buffer manager has been initialized */
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))
332 /* Check if we are freeing stuff */
346 __reclaim_buf(hashp
, bp
)