Merge from vendor branch BIND:
[dragonfly.git] / lib / libc / db / mpool / mpool.c
1 /*-
2  * Copyright (c) 1990, 1993, 1994
3  *      The Regents of the University of California.  All rights reserved.
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions
7  * are met:
8  * 1. Redistributions of source code must retain the above copyright
9  *    notice, this list of conditions and the following disclaimer.
10  * 2. Redistributions in binary form must reproduce the above copyright
11  *    notice, this list of conditions and the following disclaimer in the
12  *    documentation and/or other materials provided with the distribution.
13  * 3. Neither the name of the University nor the names of its contributors
14  *    may be used to endorse or promote products derived from this software
15  *    without specific prior written permission.
16  *
17  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
18  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
21  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
22  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
23  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
24  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
25  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
26  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
27  * SUCH DAMAGE.
28  *
29  * $FreeBSD: src/lib/libc/db/mpool/mpool.c,v 1.5.2.1 2001/03/05 23:05:01 obrien Exp $
30  * $DragonFly: src/lib/libc/db/mpool/mpool.c,v 1.7 2005/11/19 20:46:32 swildner Exp $
31  *
32  * @(#)mpool.c  8.5 (Berkeley) 7/26/94
33  */
34
35 #include "namespace.h"
36 #include <sys/param.h>
37 #include <sys/queue.h>
38 #include <sys/stat.h>
39
40 #include <errno.h>
41 #include <stdio.h>
42 #include <stdlib.h>
43 #include <string.h>
44 #include <unistd.h>
45 #include "un-namespace.h"
46
47 #include <db.h>
48
49 #define __MPOOLINTERFACE_PRIVATE
50 #include <mpool.h>
51
52 static BKT *mpool_bkt (MPOOL *);
53 static BKT *mpool_look (MPOOL *, pgno_t);
54 static int  mpool_write (MPOOL *, BKT *);
55
56 /*
57  * mpool_open --
58  *      Initialize a memory pool.
59  */
60 MPOOL *
61 mpool_open(void *key __unused, int fd, pgno_t pagesize, pgno_t maxcache)
62 {
63         struct stat sb;
64         MPOOL *mp;
65         int entry;
66
67         /*
68          * Get information about the file.
69          *
70          * XXX
71          * We don't currently handle pipes, although we should.
72          */
73         if (_fstat(fd, &sb))
74                 return (NULL);
75         if (!S_ISREG(sb.st_mode)) {
76                 errno = ESPIPE;
77                 return (NULL);
78         }
79
80         /* Allocate and initialize the MPOOL cookie. */
81         if ((mp = (MPOOL *)calloc(1, sizeof(MPOOL))) == NULL)
82                 return (NULL);
83         TAILQ_INIT(&mp->lqh);
84         for (entry = 0; entry < HASHSIZE; ++entry)
85                 TAILQ_INIT(&mp->hqh[entry]);
86         mp->maxcache = maxcache;
87         mp->npages = sb.st_size / pagesize;
88         mp->pagesize = pagesize;
89         mp->fd = fd;
90         return (mp);
91 }
92
93 /*
94  * mpool_filter --
95  *      Initialize input/output filters.
96  */
97 void
98 mpool_filter(MPOOL *mp, void (*pgin)(void *, pgno_t, void *),
99              void (*pgout)(void *, pgno_t, void *), void *pgcookie)
100 {
101         mp->pgin = pgin;
102         mp->pgout = pgout;
103         mp->pgcookie = pgcookie;
104 }
105         
106 /*
107  * mpool_new --
108  *      Get a new page of memory.
109  */
110 void *
111 mpool_new(MPOOL *mp, pgno_t *pgnoaddr)
112 {
113         struct _hqh *head;
114         BKT *bp;
115
116         if (mp->npages == MAX_PAGE_NUMBER) {
117                 fprintf(stderr, "mpool_new: page allocation overflow.\n");
118                 abort();
119         }
120 #ifdef STATISTICS
121         ++mp->pagenew;
122 #endif
123         /*
124          * Get a BKT from the cache.  Assign a new page number, attach
125          * it to the head of the hash chain, the tail of the lru chain,
126          * and return.
127          */
128         if ((bp = mpool_bkt(mp)) == NULL)
129                 return (NULL);
130         *pgnoaddr = bp->pgno = mp->npages++;
131         bp->flags = MPOOL_PINNED;
132
133         head = &mp->hqh[HASHKEY(bp->pgno)];
134         TAILQ_INSERT_HEAD(head, bp, hq);
135         TAILQ_INSERT_TAIL(&mp->lqh, bp, q);
136         return (bp->page);
137 }
138
139 /*
140  * mpool_get
141  *      Get a page.
142  */
143 void *
144 mpool_get(MPOOL *mp, pgno_t pgno, u_int flags __unused)
145 {
146         struct _hqh *head;
147         BKT *bp;
148         off_t off;
149         int nr;
150
151         /* Check for attempt to retrieve a non-existent page. */
152         if (pgno >= mp->npages) {
153                 errno = EINVAL;
154                 return (NULL);
155         }
156
157 #ifdef STATISTICS
158         ++mp->pageget;
159 #endif
160
161         /* Check for a page that is cached. */
162         if ((bp = mpool_look(mp, pgno)) != NULL) {
163 #ifdef DEBUG
164                 if (bp->flags & MPOOL_PINNED) {
165                         fprintf(stderr,
166                             "mpool_get: page %d already pinned\n", bp->pgno);
167                         abort();
168                 }
169 #endif
170                 /*
171                  * Move the page to the head of the hash chain and the tail
172                  * of the lru chain.
173                  */
174                 head = &mp->hqh[HASHKEY(bp->pgno)];
175                 TAILQ_REMOVE(head, bp, hq);
176                 TAILQ_INSERT_HEAD(head, bp, hq);
177                 TAILQ_REMOVE(&mp->lqh, bp, q);
178                 TAILQ_INSERT_TAIL(&mp->lqh, bp, q);
179
180                 /* Return a pinned page. */
181                 bp->flags |= MPOOL_PINNED;
182                 return (bp->page);
183         }
184
185         /* Get a page from the cache. */
186         if ((bp = mpool_bkt(mp)) == NULL)
187                 return (NULL);
188
189         /* Read in the contents. */
190 #ifdef STATISTICS
191         ++mp->pageread;
192 #endif
193         off = mp->pagesize * pgno;
194         if (lseek(mp->fd, off, SEEK_SET) != off)
195                 return (NULL);
196         if ((nr = _read(mp->fd, bp->page, mp->pagesize)) != mp->pagesize) {
197                 if (nr >= 0)
198                         errno = EFTYPE;
199                 return (NULL);
200         }
201
202         /* Set the page number, pin the page. */
203         bp->pgno = pgno;
204         bp->flags = MPOOL_PINNED;
205
206         /*
207          * Add the page to the head of the hash chain and the tail
208          * of the lru chain.
209          */
210         head = &mp->hqh[HASHKEY(bp->pgno)];
211         TAILQ_INSERT_HEAD(head, bp, hq);
212         TAILQ_INSERT_TAIL(&mp->lqh, bp, q);
213
214         /* Run through the user's filter. */
215         if (mp->pgin != NULL)
216                 (mp->pgin)(mp->pgcookie, bp->pgno, bp->page);
217
218         return (bp->page);
219 }
220
221 /*
222  * mpool_put
223  *      Return a page.
224  */
225 int
226 mpool_put(MPOOL *mp __unused, void *page, u_int flags)
227 {
228         BKT *bp;
229
230 #ifdef STATISTICS
231         ++mp->pageput;
232 #endif
233         bp = (BKT *)((char *)page - sizeof(BKT));
234 #ifdef DEBUG
235         if (!(bp->flags & MPOOL_PINNED)) {
236                 fprintf(stderr,
237                     "mpool_put: page %d not pinned\n", bp->pgno);
238                 abort();
239         }
240 #endif
241         bp->flags &= ~MPOOL_PINNED;
242         bp->flags |= flags & MPOOL_DIRTY;
243         return (RET_SUCCESS);
244 }
245
246 /*
247  * mpool_close
248  *      Close the buffer pool.
249  */
250 int
251 mpool_close(MPOOL *mp)
252 {
253         BKT *bp;
254
255         /* Free up any space allocated to the lru pages. */
256         while (!TAILQ_EMPTY(&mp->lqh)) {
257                 bp = TAILQ_FIRST(&mp->lqh);
258                 TAILQ_REMOVE(&mp->lqh, bp, q);
259                 free(bp);
260         }
261
262         /* Free the MPOOL cookie. */
263         free(mp);
264         return (RET_SUCCESS);
265 }
266
267 /*
268  * mpool_sync
269  *      Sync the pool to disk.
270  */
271 int
272 mpool_sync(MPOOL *mp)
273 {
274         BKT *bp;
275
276         /* Walk the lru chain, flushing any dirty pages to disk. */
277         TAILQ_FOREACH(bp, &mp->lqh, q)
278                 if (bp->flags & MPOOL_DIRTY &&
279                     mpool_write(mp, bp) == RET_ERROR)
280                         return (RET_ERROR);
281
282         /* Sync the file descriptor. */
283         return (_fsync(mp->fd) ? RET_ERROR : RET_SUCCESS);
284 }
285
286 /*
287  * mpool_bkt
288  *      Get a page from the cache (or create one).
289  */
290 static BKT *
291 mpool_bkt(MPOOL *mp)
292 {
293         struct _hqh *head;
294         BKT *bp;
295
296         /* If under the max cached, always create a new page. */
297         if (mp->curcache < mp->maxcache)
298                 goto new;
299
300         /*
301          * If the cache is max'd out, walk the lru list for a buffer we
302          * can flush.  If we find one, write it (if necessary) and take it
303          * off any lists.  If we don't find anything we grow the cache anyway.
304          * The cache never shrinks.
305          */
306         TAILQ_FOREACH(bp, &mp->lqh, q)
307                 if (!(bp->flags & MPOOL_PINNED)) {
308                         /* Flush if dirty. */
309                         if (bp->flags & MPOOL_DIRTY &&
310                             mpool_write(mp, bp) == RET_ERROR)
311                                 return (NULL);
312 #ifdef STATISTICS
313                         ++mp->pageflush;
314 #endif
315                         /* Remove from the hash and lru queues. */
316                         head = &mp->hqh[HASHKEY(bp->pgno)];
317                         TAILQ_REMOVE(head, bp, hq);
318                         TAILQ_REMOVE(&mp->lqh, bp, q);
319 #ifdef DEBUG
320                         { void *spage;
321                                 spage = bp->page;
322                                 memset(bp, 0xff, sizeof(BKT) + mp->pagesize);
323                                 bp->page = spage;
324                         }
325 #endif
326                         return (bp);
327                 }
328
329 new:    if ((bp = (BKT *)malloc(sizeof(BKT) + mp->pagesize)) == NULL)
330                 return (NULL);
331 #ifdef STATISTICS
332         ++mp->pagealloc;
333 #endif
334 #if defined(DEBUG) || defined(PURIFY)
335         memset(bp, 0xff, sizeof(BKT) + mp->pagesize);
336 #endif
337         bp->page = (char *)bp + sizeof(BKT);
338         ++mp->curcache;
339         return (bp);
340 }
341
342 /*
343  * mpool_write
344  *      Write a page to disk.
345  */
346 static int
347 mpool_write(MPOOL *mp, BKT *bp)
348 {
349         off_t off;
350
351 #ifdef STATISTICS
352         ++mp->pagewrite;
353 #endif
354
355         /* Run through the user's filter. */
356         if (mp->pgout)
357                 (mp->pgout)(mp->pgcookie, bp->pgno, bp->page);
358
359         off = mp->pagesize * bp->pgno;
360         if (lseek(mp->fd, off, SEEK_SET) != off)
361                 return (RET_ERROR);
362         if (_write(mp->fd, bp->page, mp->pagesize) != mp->pagesize)
363                 return (RET_ERROR);
364
365         bp->flags &= ~MPOOL_DIRTY;
366         return (RET_SUCCESS);
367 }
368
369 /*
370  * mpool_look
371  *      Lookup a page in the cache.
372  */
373 static BKT *
374 mpool_look(MPOOL *mp, pgno_t pgno)
375 {
376         struct _hqh *head;
377         BKT *bp;
378
379         head = &mp->hqh[HASHKEY(pgno)];
380         TAILQ_FOREACH(bp, head, hq)
381                 if (bp->pgno == pgno) {
382 #ifdef STATISTICS
383                         ++mp->cachehit;
384 #endif
385                         return (bp);
386                 }
387 #ifdef STATISTICS
388         ++mp->cachemiss;
389 #endif
390         return (NULL);
391 }
392
393 #ifdef STATISTICS
394 /*
395  * mpool_stat
396  *      Print out cache statistics.
397  */
398 void
399 mpool_stat(MPOOL *mp)
400 {
401         BKT *bp;
402         int cnt;
403         char *sep;
404
405         fprintf(stderr, "%lu pages in the file\n", mp->npages);
406         fprintf(stderr,
407             "page size %lu, cacheing %lu pages of %lu page max cache\n",
408             mp->pagesize, mp->curcache, mp->maxcache);
409         fprintf(stderr, "%lu page puts, %lu page gets, %lu page new\n",
410             mp->pageput, mp->pageget, mp->pagenew);
411         fprintf(stderr, "%lu page allocs, %lu page flushes\n",
412             mp->pagealloc, mp->pageflush);
413         if (mp->cachehit + mp->cachemiss)
414                 fprintf(stderr,
415                     "%.0f%% cache hit rate (%lu hits, %lu misses)\n", 
416                     ((double)mp->cachehit / (mp->cachehit + mp->cachemiss))
417                     * 100, mp->cachehit, mp->cachemiss);
418         fprintf(stderr, "%lu page reads, %lu page writes\n",
419             mp->pageread, mp->pagewrite);
420
421         sep = "";
422         cnt = 0;
423         TAILQ_FOREACH(bp, &mp->lqh, q) {
424                 fprintf(stderr, "%s%d", sep, bp->pgno);
425                 if (bp->flags & MPOOL_DIRTY)
426                         fprintf(stderr, "d");
427                 if (bp->flags & MPOOL_PINNED)
428                         fprintf(stderr, "P");
429                 if (++cnt == 10) {
430                         sep = "\n";
431                         cnt = 0;
432                 } else
433                         sep = ", ";
434                         
435         }
436         fprintf(stderr, "\n");
437 }
438 #endif