e3ce22bc19ca5a0370ec29c4670aa0b74eecc095
[dragonfly.git] / lib / libc / db / hash / hash_buf.c
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  * $FreeBSD: src/lib/libc/db/hash/hash_buf.c,v 1.4.8.1 2001/03/05 07:38:05 obrien Exp $
33  * $DragonFly: src/lib/libc/db/hash/hash_buf.c,v 1.7 2005/11/19 20:46:32 swildner Exp $
34  *
35  * @(#)hash_buf.c       8.5 (Berkeley) 7/15/94
36  */
37
38 /*
39  * PACKAGE: hash
40  *
41  * DESCRIPTION:
42  *      Contains buffer management
43  *
44  * ROUTINES:
45  * External
46  *      __buf_init
47  *      __get_buf
48  *      __buf_free
49  *      __reclaim_buf
50  * Internal
51  *      newbuf
52  */
53
54 #include <sys/param.h>
55
56 #include <stddef.h>
57 #include <stdio.h>
58 #include <stdlib.h>
59
60 #ifdef DEBUG
61 #include <assert.h>
62 #endif
63
64 #include <db.h>
65 #include "hash.h"
66 #include "page.h"
67 #include "extern.h"
68
69 static BUFHEAD *newbuf (HTAB *, u_int32_t, BUFHEAD *);
70
71 /* Unlink B from its place in the lru */
72 #define BUF_REMOVE(B) { \
73         (B)->prev->next = (B)->next; \
74         (B)->next->prev = (B)->prev; \
75 }
76
77 /* Insert B after P */
78 #define BUF_INSERT(B, P) { \
79         (B)->next = (P)->next; \
80         (B)->prev = (P); \
81         (P)->next = (B); \
82         (B)->next->prev = (B); \
83 }
84
85 #define MRU     hashp->bufhead.next
86 #define LRU     hashp->bufhead.prev
87
88 #define MRU_INSERT(B)   BUF_INSERT((B), &hashp->bufhead)
89 #define LRU_INSERT(B)   BUF_INSERT((B), LRU)
90
91 /*
92  * We are looking for a buffer with address "addr".  If prev_bp is NULL, then
93  * address is a bucket index.  If prev_bp is not NULL, then it points to the
94  * page previous to an overflow page that we are trying to find.
95  *
96  * CAVEAT:  The buffer header accessed via prev_bp's ovfl field may no longer
97  * be valid.  Therefore, you must always verify that its address matches the
98  * address you are seeking.
99  *
100  * Parameters:
101  *      newpage:        If prev_bp set, indicates a new overflow page
102  */
103 extern BUFHEAD *
104 __get_buf(HTAB *hashp, u_int32_t addr, BUFHEAD *prev_bp, int newpage)
105 {
106         BUFHEAD *bp;
107         u_int32_t is_disk_mask;
108         int is_disk, segment_ndx;
109         SEGMENT segp;
110
111         is_disk = 0;
112         is_disk_mask = 0;
113         segment_ndx = 0;
114         segp = NULL;
115         if (prev_bp) {
116                 bp = prev_bp->ovfl;
117                 if (!bp || (bp->addr != addr))
118                         bp = NULL;
119                 if (!newpage)
120                         is_disk = BUF_DISK;
121         } else {
122                 /* Grab buffer out of directory */
123                 segment_ndx = addr & (hashp->SGSIZE - 1);
124
125                 /* valid segment ensured by __call_hash() */
126                 segp = hashp->dir[addr >> hashp->SSHIFT];
127 #ifdef DEBUG
128                 assert(segp != NULL);
129 #endif
130                 bp = PTROF(segp[segment_ndx]);
131                 is_disk_mask = ISDISK(segp[segment_ndx]);
132                 is_disk = is_disk_mask || !hashp->new_file;
133         }
134
135         if (!bp) {
136                 bp = newbuf(hashp, addr, prev_bp);
137                 if (!bp ||
138                     __get_page(hashp, bp->page, addr, !prev_bp, is_disk, 0))
139                         return (NULL);
140                 if (!prev_bp)
141                         segp[segment_ndx] =
142                             (BUFHEAD *)((ptrdiff_t)bp | is_disk_mask);
143         } else {
144                 BUF_REMOVE(bp);
145                 MRU_INSERT(bp);
146         }
147         return (bp);
148 }
149
150 /*
151  * We need a buffer for this page. Either allocate one, or evict a resident
152  * one (if we have as many buffers as we're allowed) and put this one in.
153  *
154  * If newbuf finds an error (returning NULL), it also sets errno.
155  */
156 static BUFHEAD *
157 newbuf(HTAB *hashp, u_int32_t addr, BUFHEAD *prev_bp)
158 {
159         BUFHEAD *bp;            /* The buffer we're going to use */
160         BUFHEAD *xbp;           /* Temp pointer */
161         BUFHEAD *next_xbp;
162         SEGMENT segp;
163         int segment_ndx;
164         u_int16_t oaddr, *shortp;
165
166         oaddr = 0;
167         bp = LRU;
168         /*
169          * If LRU buffer is pinned, the buffer pool is too small. We need to
170          * allocate more buffers.
171          */
172         if (hashp->nbufs || (bp->flags & BUF_PIN)) {
173                 /* Allocate a new one */
174                 if ((bp = (BUFHEAD *)malloc(sizeof(BUFHEAD))) == NULL)
175                         return (NULL);
176 #ifdef PURIFY
177                 memset(bp, 0xff, sizeof(BUFHEAD));
178 #endif
179                 if ((bp->page = (char *)malloc(hashp->BSIZE)) == NULL) {
180                         free(bp);
181                         return (NULL);
182                 }
183 #ifdef PURIFY
184                 memset(bp->page, 0xff, hashp->BSIZE);
185 #endif
186                 if (hashp->nbufs)
187                         hashp->nbufs--;
188         } else {
189                 /* Kick someone out */
190                 BUF_REMOVE(bp);
191                 /*
192                  * If this is an overflow page with addr 0, it's already been
193                  * flushed back in an overflow chain and initialized.
194                  */
195                 if ((bp->addr != 0) || (bp->flags & BUF_BUCKET)) {
196                         /*
197                          * Set oaddr before __put_page so that you get it
198                          * before bytes are swapped.
199                          */
200                         shortp = (u_int16_t *)bp->page;
201                         if (shortp[0])
202                                 oaddr = shortp[shortp[0] - 1];
203                         if ((bp->flags & BUF_MOD) && __put_page(hashp, bp->page,
204                             bp->addr, (int)IS_BUCKET(bp->flags), 0))
205                                 return (NULL);
206                         /*
207                          * Update the pointer to this page (i.e. invalidate it).
208                          *
209                          * If this is a new file (i.e. we created it at open
210                          * time), make sure that we mark pages which have been
211                          * written to disk so we retrieve them from disk later,
212                          * rather than allocating new pages.
213                          */
214                         if (IS_BUCKET(bp->flags)) {
215                                 segment_ndx = bp->addr & (hashp->SGSIZE - 1);
216                                 segp = hashp->dir[bp->addr >> hashp->SSHIFT];
217 #ifdef DEBUG
218                                 assert(segp != NULL);
219 #endif
220
221                                 if (hashp->new_file &&
222                                     ((bp->flags & BUF_MOD) ||
223                                     ISDISK(segp[segment_ndx])))
224                                         segp[segment_ndx] = (BUFHEAD *)BUF_DISK;
225                                 else
226                                         segp[segment_ndx] = NULL;
227                         }
228                         /*
229                          * Since overflow pages can only be access by means of
230                          * their bucket, free overflow pages associated with
231                          * this bucket.
232                          */
233                         for (xbp = bp; xbp->ovfl;) {
234                                 next_xbp = xbp->ovfl;
235                                 xbp->ovfl = 0;
236                                 xbp = next_xbp;
237
238                                 /* Check that ovfl pointer is up date. */
239                                 if (IS_BUCKET(xbp->flags) ||
240                                     (oaddr != xbp->addr))
241                                         break;
242
243                                 shortp = (u_int16_t *)xbp->page;
244                                 if (shortp[0])
245                                         /* set before __put_page */
246                                         oaddr = shortp[shortp[0] - 1];
247                                 if ((xbp->flags & BUF_MOD) && __put_page(hashp,
248                                     xbp->page, xbp->addr, 0, 0))
249                                         return (NULL);
250                                 xbp->addr = 0;
251                                 xbp->flags = 0;
252                                 BUF_REMOVE(xbp);
253                                 LRU_INSERT(xbp);
254                         }
255                 }
256         }
257
258         /* Now assign this buffer */
259         bp->addr = addr;
260 #ifdef DEBUG1
261         fprintf(stderr, "NEWBUF1: %d->ovfl was %d is now %d\n",
262             bp->addr, (bp->ovfl ? bp->ovfl->addr : 0), 0);
263 #endif
264         bp->ovfl = NULL;
265         if (prev_bp) {
266                 /*
267                  * If prev_bp is set, this is an overflow page, hook it in to
268                  * the buffer overflow links.
269                  */
270 #ifdef DEBUG1
271                 fprintf(stderr, "NEWBUF2: %d->ovfl was %d is now %d\n",
272                     prev_bp->addr, (prev_bp->ovfl ? bp->ovfl->addr : 0),
273                     (bp ? bp->addr : 0));
274 #endif
275                 prev_bp->ovfl = bp;
276                 bp->flags = 0;
277         } else
278                 bp->flags = BUF_BUCKET;
279         MRU_INSERT(bp);
280         return (bp);
281 }
282
283 extern void
284 __buf_init(HTAB *hashp, int nbytes)
285 {
286         BUFHEAD *bfp;
287         int npages;
288
289         bfp = &(hashp->bufhead);
290         npages = (nbytes + hashp->BSIZE - 1) >> hashp->BSHIFT;
291         npages = MAX(npages, MIN_BUFFERS);
292
293         hashp->nbufs = npages;
294         bfp->next = bfp;
295         bfp->prev = bfp;
296         /*
297          * This space is calloc'd so these are already null.
298          *
299          * bfp->ovfl = NULL;
300          * bfp->flags = 0;
301          * bfp->page = NULL;
302          * bfp->addr = 0;
303          */
304 }
305
306 extern int
307 __buf_free(HTAB *hashp, int do_free, int to_disk)
308 {
309         BUFHEAD *bp;
310
311         /* Need to make sure that buffer manager has been initialized */
312         if (!LRU)
313                 return (0);
314         for (bp = LRU; bp != &hashp->bufhead;) {
315                 /* Check that the buffer is valid */
316                 if (bp->addr || IS_BUCKET(bp->flags)) {
317                         if (to_disk && (bp->flags & BUF_MOD) &&
318                             __put_page(hashp, bp->page,
319                             bp->addr, IS_BUCKET(bp->flags), 0))
320                                 return (-1);
321                 }
322                 /* Check if we are freeing stuff */
323                 if (do_free) {
324                         if (bp->page)
325                                 free(bp->page);
326                         BUF_REMOVE(bp);
327                         free(bp);
328                         bp = LRU;
329                 } else
330                         bp = bp->prev;
331         }
332         return (0);
333 }
334
335 extern void
336 __reclaim_buf(HTAB *hashp, BUFHEAD *bp)
337 {
338         bp->ovfl = 0;
339         bp->addr = 0;
340         bp->flags = 0;
341         BUF_REMOVE(bp);
342         LRU_INSERT(bp);
343 }