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 * 4. 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
30#if defined(LIBC_SCCS) && !defined(lint)
31static char sccsid[] = "@(#)mpool.c	8.5 (Berkeley) 7/26/94";
32#endif /* LIBC_SCCS and not lint */
33#include <sys/cdefs.h>
34__FBSDID("$FreeBSD: src/lib/libc/db/mpool/mpool.c,v 1.16 2009/03/28 04:00:46 delphij Exp $");
35
36#include "namespace.h"
37#include <sys/param.h>
38#include <sys/queue.h>
39#include <sys/stat.h>
40
41#include <errno.h>
42#include <stdio.h>
43#include <stdlib.h>
44#include <string.h>
45#include <unistd.h>
46#include "un-namespace.h"
47
48#include <db.h>
49
50#define	__MPOOLINTERFACE_PRIVATE
51#include <mpool.h>
52
53static BKT *mpool_bkt(MPOOL *);
54static BKT *mpool_look(MPOOL *, pgno_t);
55static int  mpool_write(MPOOL *, BKT *);
56
57/*
58 * mpool_open --
59 *	Initialize a memory pool.
60 */
61/* ARGSUSED */
62MPOOL *
63mpool_open(void *key, int fd, pgno_t pagesize, pgno_t maxcache)
64{
65	struct stat sb;
66	MPOOL *mp;
67	int entry;
68
69	/*
70	 * Get information about the file.
71	 *
72	 * XXX
73	 * We don't currently handle pipes, although we should.
74	 */
75	if (_fstat(fd, &sb))
76		return (NULL);
77	if (!S_ISREG(sb.st_mode)) {
78		errno = ESPIPE;
79		return (NULL);
80	}
81
82	/* Allocate and initialize the MPOOL cookie. */
83	if ((mp = (MPOOL *)calloc(1, sizeof(MPOOL))) == NULL)
84		return (NULL);
85	TAILQ_INIT(&mp->lqh);
86	for (entry = 0; entry < HASHSIZE; ++entry)
87		TAILQ_INIT(&mp->hqh[entry]);
88	mp->maxcache = maxcache;
89	mp->npages = sb.st_size / pagesize;
90	mp->pagesize = pagesize;
91	mp->fd = fd;
92	return (mp);
93}
94
95/*
96 * mpool_filter --
97 *	Initialize input/output filters.
98 */
99void
100mpool_filter(MPOOL *mp, void (*pgin) (void *, pgno_t, void *),
101    void (*pgout) (void *, pgno_t, void *), void *pgcookie)
102{
103	mp->pgin = pgin;
104	mp->pgout = pgout;
105	mp->pgcookie = pgcookie;
106}
107
108/*
109 * mpool_new --
110 *	Get a new page of memory.
111 */
112void *
113mpool_new(mp, pgnoaddr)
114	MPOOL *mp;
115	pgno_t *pgnoaddr;
116{
117	struct _hqh *head;
118	BKT *bp;
119
120	if (mp->npages == MAX_PAGE_NUMBER) {
121		(void)fprintf(stderr, "mpool_new: page allocation overflow.\n");
122		LIBC_ABORT("page allocation overflow");
123	}
124#ifdef STATISTICS
125	++mp->pagenew;
126#endif
127	/*
128	 * Get a BKT from the cache.  Assign a new page number, attach
129	 * it to the head of the hash chain, the tail of the lru chain,
130	 * and return.
131	 */
132	if ((bp = mpool_bkt(mp)) == NULL)
133		return (NULL);
134	*pgnoaddr = bp->pgno = mp->npages++;
135	bp->flags = MPOOL_PINNED;
136
137	head = &mp->hqh[HASHKEY(bp->pgno)];
138	TAILQ_INSERT_HEAD(head, bp, hq);
139	TAILQ_INSERT_TAIL(&mp->lqh, bp, q);
140	return (bp->page);
141}
142
143/*
144 * mpool_get
145 *	Get a page.
146 */
147/* ARGSUSED */
148void *
149mpool_get(MPOOL *mp, pgno_t pgno,
150    u_int flags)		/* XXX not used? */
151{
152	struct _hqh *head;
153	BKT *bp;
154	off_t off;
155	int nr;
156
157	/* Check for attempt to retrieve a non-existent page. */
158	if (pgno >= mp->npages) {
159		errno = EINVAL;
160		return (NULL);
161	}
162
163#ifdef STATISTICS
164	++mp->pageget;
165#endif
166
167	/* Check for a page that is cached. */
168	if ((bp = mpool_look(mp, pgno)) != NULL) {
169#ifdef DEBUG
170		if (bp->flags & MPOOL_PINNED) {
171			(void)fprintf(stderr,
172			    "mpool_get: page %d already pinned\n", bp->pgno);
173			LIBC_ABORT("page %d already pinned", bp->pgno);
174		}
175#endif
176		/*
177		 * Move the page to the head of the hash chain and the tail
178		 * of the lru chain.
179		 */
180		head = &mp->hqh[HASHKEY(bp->pgno)];
181		TAILQ_REMOVE(head, bp, hq);
182		TAILQ_INSERT_HEAD(head, bp, hq);
183		TAILQ_REMOVE(&mp->lqh, bp, q);
184		TAILQ_INSERT_TAIL(&mp->lqh, bp, q);
185
186		/* Return a pinned page. */
187		bp->flags |= MPOOL_PINNED;
188		return (bp->page);
189	}
190
191	/* Get a page from the cache. */
192	if ((bp = mpool_bkt(mp)) == NULL)
193		return (NULL);
194
195	/* Read in the contents. */
196#ifdef STATISTICS
197	++mp->pageread;
198#endif
199	off = mp->pagesize * pgno;
200	nr = pread(mp->fd, bp->page, mp->pagesize, off);
201	if (nr != mp->pagesize) {
202		if (nr >= 0)
203			errno = EFTYPE;
204		return (NULL);
205	}
206
207	/* Set the page number, pin the page. */
208	bp->pgno = pgno;
209	bp->flags = MPOOL_PINNED;
210
211	/*
212	 * Add the page to the head of the hash chain and the tail
213	 * of the lru chain.
214	 */
215	head = &mp->hqh[HASHKEY(bp->pgno)];
216	TAILQ_INSERT_HEAD(head, bp, hq);
217	TAILQ_INSERT_TAIL(&mp->lqh, bp, q);
218
219	/* Run through the user's filter. */
220	if (mp->pgin != NULL)
221		(mp->pgin)(mp->pgcookie, bp->pgno, bp->page);
222
223	return (bp->page);
224}
225
226/*
227 * mpool_put
228 *	Return a page.
229 */
230/* ARGSUSED */
231int
232mpool_put(MPOOL *mp, void *page, u_int flags)
233{
234	BKT *bp;
235
236#ifdef STATISTICS
237	++mp->pageput;
238#endif
239	bp = (BKT *)((char *)page - sizeof(BKT));
240#ifdef DEBUG
241	if (!(bp->flags & MPOOL_PINNED)) {
242		(void)fprintf(stderr,
243		    "mpool_put: page %d not pinned\n", bp->pgno);
244		LIBC_ABORT("page %d not pinned", bp->pgno);
245	}
246#endif
247	bp->flags &= ~MPOOL_PINNED;
248	bp->flags |= flags & MPOOL_DIRTY;
249	return (RET_SUCCESS);
250}
251
252/*
253 * mpool_close
254 *	Close the buffer pool.
255 */
256int
257mpool_close(MPOOL *mp)
258{
259	BKT *bp;
260
261	/* Free up any space allocated to the lru pages. */
262	while (!TAILQ_EMPTY(&mp->lqh)) {
263		bp = TAILQ_FIRST(&mp->lqh);
264		TAILQ_REMOVE(&mp->lqh, bp, q);
265		free(bp);
266	}
267
268	/* Free the MPOOL cookie. */
269	free(mp);
270	return (RET_SUCCESS);
271}
272
273/*
274 * mpool_sync
275 *	Sync the pool to disk.
276 */
277int
278mpool_sync(MPOOL *mp)
279{
280	BKT *bp;
281
282	/* Walk the lru chain, flushing any dirty pages to disk. */
283	TAILQ_FOREACH(bp, &mp->lqh, q) {
284		if (bp->flags & MPOOL_DIRTY) {
285			if (mpool_write(mp, bp) == RET_ERROR) {
286				return (RET_ERROR);
287			} else {
288				/* 4874757: Re-run through the user's pgin filter. */
289				if (mp->pgin != NULL)
290					(mp->pgin)(mp->pgcookie, bp->pgno, bp->page);
291			}
292		}
293	}
294
295	/* Sync the file descriptor. */
296	return (_fsync(mp->fd) ? RET_ERROR : RET_SUCCESS);
297}
298
299/*
300 * mpool_bkt
301 *	Get a page from the cache (or create one).
302 */
303static BKT *
304mpool_bkt(MPOOL *mp)
305{
306	struct _hqh *head;
307	BKT *bp;
308
309	/* If under the max cached, always create a new page. */
310	if (mp->curcache < mp->maxcache)
311		goto new;
312
313	/*
314	 * If the cache is max'd out, walk the lru list for a buffer we
315	 * can flush.  If we find one, write it (if necessary) and take it
316	 * off any lists.  If we don't find anything we grow the cache anyway.
317	 * The cache never shrinks.
318	 */
319	TAILQ_FOREACH(bp, &mp->lqh, q)
320		if (!(bp->flags & MPOOL_PINNED)) {
321			/* Flush if dirty. */
322			if (bp->flags & MPOOL_DIRTY &&
323			    mpool_write(mp, bp) == RET_ERROR)
324				return (NULL);
325#ifdef STATISTICS
326			++mp->pageflush;
327#endif
328			/* Remove from the hash and lru queues. */
329			head = &mp->hqh[HASHKEY(bp->pgno)];
330			TAILQ_REMOVE(head, bp, hq);
331			TAILQ_REMOVE(&mp->lqh, bp, q);
332#ifdef DEBUG
333			{ void *spage;
334				spage = bp->page;
335				memset(bp, 0xff, sizeof(BKT) + mp->pagesize);
336				bp->page = spage;
337			}
338#endif
339			return (bp);
340		}
341
342new:	if ((bp = (BKT *)calloc(1, sizeof(BKT) + mp->pagesize)) == NULL)
343		return (NULL);
344#ifdef STATISTICS
345	++mp->pagealloc;
346#endif
347	bp->page = (char *)bp + sizeof(BKT);
348	++mp->curcache;
349	return (bp);
350}
351
352/*
353 * mpool_write
354 *	Write a page to disk.
355 */
356static int
357mpool_write(MPOOL *mp, BKT *bp)
358{
359	off_t off;
360
361#ifdef STATISTICS
362	++mp->pagewrite;
363#endif
364
365	/* Run through the user's filter. */
366	if (mp->pgout)
367		(mp->pgout)(mp->pgcookie, bp->pgno, bp->page);
368
369	off = mp->pagesize * bp->pgno;
370	if (pwrite(mp->fd, bp->page, mp->pagesize, off) != mp->pagesize)
371		return (RET_ERROR);
372
373	bp->flags &= ~MPOOL_DIRTY;
374	return (RET_SUCCESS);
375}
376
377/*
378 * mpool_look
379 *	Lookup a page in the cache.
380 */
381static BKT *
382mpool_look(MPOOL *mp, pgno_t pgno)
383{
384	struct _hqh *head;
385	BKT *bp;
386
387	head = &mp->hqh[HASHKEY(pgno)];
388	TAILQ_FOREACH(bp, head, hq)
389		if (bp->pgno == pgno) {
390#ifdef STATISTICS
391			++mp->cachehit;
392#endif
393			return (bp);
394		}
395#ifdef STATISTICS
396	++mp->cachemiss;
397#endif
398	return (NULL);
399}
400
401#ifdef STATISTICS
402/*
403 * mpool_stat
404 *	Print out cache statistics.
405 */
406void
407mpool_stat(MPOOL *mp)
408{
409	BKT *bp;
410	int cnt;
411	char *sep;
412
413	(void)fprintf(stderr, "%lu pages in the file\n", mp->npages);
414	(void)fprintf(stderr,
415	    "page size %lu, cacheing %lu pages of %lu page max cache\n",
416	    mp->pagesize, mp->curcache, mp->maxcache);
417	(void)fprintf(stderr, "%lu page puts, %lu page gets, %lu page new\n",
418	    mp->pageput, mp->pageget, mp->pagenew);
419	(void)fprintf(stderr, "%lu page allocs, %lu page flushes\n",
420	    mp->pagealloc, mp->pageflush);
421	if (mp->cachehit + mp->cachemiss)
422		(void)fprintf(stderr,
423		    "%.0f%% cache hit rate (%lu hits, %lu misses)\n",
424		    ((double)mp->cachehit / (mp->cachehit + mp->cachemiss))
425		    * 100, mp->cachehit, mp->cachemiss);
426	(void)fprintf(stderr, "%lu page reads, %lu page writes\n",
427	    mp->pageread, mp->pagewrite);
428
429	sep = "";
430	cnt = 0;
431	TAILQ_FOREACH(bp, &mp->lqh, q) {
432		(void)fprintf(stderr, "%s%d", sep, bp->pgno);
433		if (bp->flags & MPOOL_DIRTY)
434			(void)fprintf(stderr, "d");
435		if (bp->flags & MPOOL_PINNED)
436			(void)fprintf(stderr, "P");
437		if (++cnt == 10) {
438			sep = "\n";
439			cnt = 0;
440		} else
441			sep = ", ";
442
443	}
444	(void)fprintf(stderr, "\n");
445}
446#endif
447