Home | History | Annotate | Line # | Download | only in fsck_lfs
bufcache.c revision 1.2
      1  1.2  perseant /* $NetBSD: bufcache.c,v 1.2 2003/03/31 19:56:59 perseant Exp $ */
      2  1.1  perseant /*-
      3  1.1  perseant  * Copyright (c) 2003 The NetBSD Foundation, Inc.
      4  1.1  perseant  * All rights reserved.
      5  1.1  perseant  *
      6  1.1  perseant  * This code is derived from software contributed to The NetBSD Foundation
      7  1.1  perseant  * by Konrad E. Schroder <perseant (at) hhhh.org>.
      8  1.1  perseant  *
      9  1.1  perseant  * Redistribution and use in source and binary forms, with or without
     10  1.1  perseant  * modification, are permitted provided that the following conditions
     11  1.1  perseant  * are met:
     12  1.1  perseant  * 1. Redistributions of source code must retain the above copyright
     13  1.1  perseant  *    notice, this list of conditions and the following disclaimer.
     14  1.1  perseant  * 2. Redistributions in binary form must reproduce the above copyright
     15  1.1  perseant  *    notice, this list of conditions and the following disclaimer in the
     16  1.1  perseant  *    documentation and/or other materials provided with the distribution.
     17  1.1  perseant  * 3. All advertising materials mentioning features or use of this software
     18  1.1  perseant  *    must display the following acknowledgement:
     19  1.1  perseant  *	This product includes software developed by the NetBSD
     20  1.1  perseant  *	Foundation, Inc. and its contributors.
     21  1.1  perseant  * 4. Neither the name of The NetBSD Foundation nor the names of its
     22  1.1  perseant  *    contributors may be used to endorse or promote products derived
     23  1.1  perseant  *    from this software without specific prior written permission.
     24  1.1  perseant  *
     25  1.1  perseant  * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
     26  1.1  perseant  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
     27  1.1  perseant  * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
     28  1.1  perseant  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
     29  1.1  perseant  * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
     30  1.1  perseant  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
     31  1.1  perseant  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
     32  1.1  perseant  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
     33  1.1  perseant  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
     34  1.1  perseant  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
     35  1.1  perseant  * POSSIBILITY OF SUCH DAMAGE.
     36  1.1  perseant  */
     37  1.1  perseant 
     38  1.1  perseant #include <sys/types.h>
     39  1.1  perseant #include <sys/param.h>
     40  1.1  perseant #include <sys/time.h>
     41  1.1  perseant #include <sys/buf.h>
     42  1.1  perseant #include <sys/queue.h>
     43  1.1  perseant #include <sys/mount.h>
     44  1.1  perseant 
     45  1.1  perseant #include <assert.h>
     46  1.1  perseant #include <err.h>
     47  1.1  perseant #include <stdio.h>
     48  1.1  perseant #include <stdlib.h>
     49  1.1  perseant #include <string.h>
     50  1.1  perseant #include <unistd.h>
     51  1.1  perseant 
     52  1.1  perseant #include "bufcache.h"
     53  1.1  perseant #include "vnode.h"
     54  1.1  perseant 
     55  1.1  perseant /*
     56  1.1  perseant  * Definitions for the buffer free lists.
     57  1.1  perseant  */
     58  1.1  perseant #define	BQUEUES		3	/* number of free buffer queues */
     59  1.1  perseant 
     60  1.1  perseant #define	BQ_LOCKED	0	/* super-blocks &c */
     61  1.1  perseant #define	BQ_LRU		1	/* lru, useful buffers */
     62  1.1  perseant #define	BQ_AGE		2	/* rubbish */
     63  1.1  perseant 
     64  1.1  perseant TAILQ_HEAD(bqueues, ubuf) bufqueues[BQUEUES];
     65  1.1  perseant 
     66  1.1  perseant #define HASH_MAX 101
     67  1.1  perseant 
     68  1.1  perseant struct bufhash_struct bufhash[HASH_MAX];
     69  1.1  perseant 
     70  1.1  perseant int maxbufs = BUF_CACHE_SIZE;
     71  1.1  perseant int nbufs = 0;
     72  1.1  perseant int cachehits = 0;
     73  1.1  perseant int cachemisses = 0;
     74  1.1  perseant int hashmax = 0;
     75  1.1  perseant off_t locked_queue_bytes = 0;
     76  1.1  perseant 
     77  1.1  perseant /* Simple buffer hash function */
     78  1.1  perseant static int
     79  1.1  perseant vl_hash(struct uvnode * vp, daddr_t lbn)
     80  1.1  perseant {
     81  1.1  perseant 	return (int)((unsigned long) vp + lbn) % HASH_MAX;
     82  1.1  perseant }
     83  1.1  perseant 
     84  1.1  perseant /* Initialize buffer cache */
     85  1.1  perseant void
     86  1.1  perseant bufinit(void)
     87  1.1  perseant {
     88  1.1  perseant 	int i;
     89  1.1  perseant 
     90  1.1  perseant 	for (i = 0; i < BQUEUES; i++) {
     91  1.1  perseant 		TAILQ_INIT(&bufqueues[i]);
     92  1.1  perseant 	}
     93  1.1  perseant 	for (i = 0; i < HASH_MAX; i++)
     94  1.1  perseant 		LIST_INIT(&bufhash[HASH_MAX]);
     95  1.1  perseant }
     96  1.1  perseant 
     97  1.1  perseant /* Print statistics of buffer cache usage */
     98  1.1  perseant void
     99  1.1  perseant bufstats(void)
    100  1.1  perseant {
    101  1.1  perseant 	printf("buffer cache: %d hits %d misses (%2.2f%%); hash depth %d\n",
    102  1.1  perseant 	    cachehits, cachemisses,
    103  1.1  perseant 	    (cachehits * 100.0) / (cachehits + cachemisses),
    104  1.1  perseant 	    hashmax);
    105  1.1  perseant }
    106  1.1  perseant 
    107  1.1  perseant /*
    108  1.1  perseant  * Remove a buffer from the cache.
    109  1.1  perseant  * Caller must remove the buffer from its free list.
    110  1.1  perseant  */
    111  1.1  perseant void
    112  1.1  perseant buf_destroy(struct ubuf * bp)
    113  1.1  perseant {
    114  1.1  perseant 	bp->b_flags |= B_NEEDCOMMIT;
    115  1.1  perseant 	LIST_REMOVE(bp, b_vnbufs);
    116  1.1  perseant 	LIST_REMOVE(bp, b_hash);
    117  1.1  perseant 	free(bp->b_data);
    118  1.1  perseant 	free(bp);
    119  1.1  perseant 	--nbufs;
    120  1.1  perseant }
    121  1.1  perseant 
    122  1.1  perseant /* Remove a buffer from its free list. */
    123  1.1  perseant void
    124  1.1  perseant bremfree(struct ubuf * bp)
    125  1.1  perseant {
    126  1.1  perseant 	struct bqueues *dp = NULL;
    127  1.1  perseant 
    128  1.1  perseant 	/*
    129  1.1  perseant 	 * We only calculate the head of the freelist when removing
    130  1.1  perseant 	 * the last element of the list as that is the only time that
    131  1.1  perseant 	 * it is needed (e.g. to reset the tail pointer).
    132  1.1  perseant 	 *
    133  1.1  perseant 	 * NB: This makes an assumption about how tailq's are implemented.
    134  1.1  perseant 	 */
    135  1.2  perseant 	if (bp->b_flags & B_LOCKED) {
    136  1.1  perseant 		locked_queue_bytes -= bp->b_bcount;
    137  1.2  perseant 	}
    138  1.1  perseant 	if (TAILQ_NEXT(bp, b_freelist) == NULL) {
    139  1.1  perseant 		for (dp = bufqueues; dp < &bufqueues[BQUEUES]; dp++)
    140  1.1  perseant 			if (dp->tqh_last == &bp->b_freelist.tqe_next)
    141  1.1  perseant 				break;
    142  1.1  perseant 		if (dp == &bufqueues[BQUEUES])
    143  1.1  perseant 			errx(1, "bremfree: lost tail");
    144  1.1  perseant 	}
    145  1.1  perseant 	++bp->b_vp->v_usecount;
    146  1.1  perseant 	TAILQ_REMOVE(dp, bp, b_freelist);
    147  1.1  perseant }
    148  1.1  perseant 
    149  1.1  perseant /* Return a buffer if it is in the cache, otherwise return NULL. */
    150  1.1  perseant struct ubuf *
    151  1.1  perseant incore(struct uvnode * vp, int lbn)
    152  1.1  perseant {
    153  1.1  perseant 	struct ubuf *bp;
    154  1.1  perseant 	int hash, depth;
    155  1.1  perseant 
    156  1.1  perseant 	hash = vl_hash(vp, lbn);
    157  1.1  perseant 	/* XXX use a real hash instead. */
    158  1.1  perseant 	depth = 0;
    159  1.1  perseant 	LIST_FOREACH(bp, &bufhash[hash], b_hash) {
    160  1.1  perseant 		if (++depth > hashmax)
    161  1.1  perseant 			hashmax = depth;
    162  1.1  perseant 		if (bp->b_vp == vp && bp->b_lblkno == lbn) {
    163  1.1  perseant 			return bp;
    164  1.1  perseant 		}
    165  1.1  perseant 	}
    166  1.1  perseant 	return NULL;
    167  1.1  perseant }
    168  1.1  perseant 
    169  1.1  perseant /*
    170  1.1  perseant  * Return a buffer of the given size, lbn and uvnode.
    171  1.1  perseant  * If none is in core, make a new one.
    172  1.1  perseant  */
    173  1.1  perseant struct ubuf *
    174  1.1  perseant getblk(struct uvnode * vp, daddr_t lbn, int size)
    175  1.1  perseant {
    176  1.1  perseant 	struct ubuf *bp;
    177  1.1  perseant 
    178  1.1  perseant 	/*
    179  1.1  perseant 	 * First check the buffer cache lists.
    180  1.1  perseant 	 */
    181  1.1  perseant 	if ((bp = incore(vp, lbn)) != NULL) {
    182  1.1  perseant 		assert(!(bp->b_flags & B_NEEDCOMMIT));
    183  1.1  perseant 		assert(!(bp->b_flags & B_BUSY));
    184  1.1  perseant 		assert(bp->b_bcount == size);
    185  1.1  perseant 		bp->b_flags |= B_BUSY;
    186  1.1  perseant 		bremfree(bp);
    187  1.1  perseant 		return bp;
    188  1.1  perseant 	}
    189  1.1  perseant 	/*
    190  1.1  perseant 	 * Not on the list.
    191  1.1  perseant 	 * Get a new block of the appropriate size and use that.
    192  1.1  perseant 	 * If not enough space, free blocks from the AGE and LRU lists
    193  1.1  perseant 	 * to make room.
    194  1.1  perseant 	 */
    195  1.1  perseant 	while (nbufs >= maxbufs) {
    196  1.1  perseant 		bp = TAILQ_FIRST(&bufqueues[BQ_AGE]);
    197  1.1  perseant 		if (bp)
    198  1.1  perseant 			TAILQ_REMOVE(&bufqueues[BQ_AGE], bp, b_freelist);
    199  1.1  perseant 		if (bp == NULL) {
    200  1.1  perseant 			bp = TAILQ_FIRST(&bufqueues[BQ_LRU]);
    201  1.1  perseant 			if (bp)
    202  1.1  perseant 				TAILQ_REMOVE(&bufqueues[BQ_AGE], bp,
    203  1.1  perseant 				    b_freelist);
    204  1.1  perseant 		}
    205  1.1  perseant 		if (bp) {
    206  1.1  perseant 			if (bp->b_flags & B_DELWRI)
    207  1.1  perseant 				VOP_STRATEGY(bp);
    208  1.1  perseant 			buf_destroy(bp);
    209  1.1  perseant 		}
    210  1.1  perseant #ifdef DEBUG
    211  1.1  perseant 		else {
    212  1.1  perseant 			warnx("no free buffers, allocating more than %d",
    213  1.1  perseant 			    maxbufs);
    214  1.1  perseant 		}
    215  1.1  perseant #endif
    216  1.1  perseant 	}
    217  1.1  perseant 	++nbufs;
    218  1.1  perseant 	bp = (struct ubuf *) malloc(sizeof(*bp));
    219  1.1  perseant 	memset(bp, 0, sizeof(*bp));
    220  1.1  perseant 	bp->b_data = malloc(size);
    221  1.1  perseant 	memset(bp->b_data, 0, size);
    222  1.1  perseant 
    223  1.1  perseant 	bp->b_vp = vp;
    224  1.1  perseant 	bp->b_blkno = bp->b_lblkno = lbn;
    225  1.1  perseant 	bp->b_bcount = size;
    226  1.1  perseant 	LIST_INSERT_HEAD(&bufhash[vl_hash(vp, lbn)], bp, b_hash);
    227  1.1  perseant 	LIST_INSERT_HEAD(&vp->v_cleanblkhd, bp, b_vnbufs);
    228  1.1  perseant 	bp->b_flags = B_BUSY;
    229  1.1  perseant 
    230  1.1  perseant 	return bp;
    231  1.1  perseant }
    232  1.1  perseant 
    233  1.1  perseant /* Write a buffer to disk according to its strategy routine. */
    234  1.1  perseant void
    235  1.1  perseant bwrite(struct ubuf * bp)
    236  1.1  perseant {
    237  1.1  perseant 	bp->b_flags &= ~(B_READ | B_DONE | B_DELWRI | B_LOCKED);
    238  1.1  perseant 	VOP_STRATEGY(bp);
    239  1.1  perseant 	bp->b_flags |= B_DONE;
    240  1.1  perseant 	reassignbuf(bp, bp->b_vp);
    241  1.1  perseant 	brelse(bp);
    242  1.1  perseant }
    243  1.1  perseant 
    244  1.1  perseant /* Put a buffer back on its free list, clear B_BUSY. */
    245  1.1  perseant void
    246  1.1  perseant brelse(struct ubuf * bp)
    247  1.1  perseant {
    248  1.1  perseant 	int age;
    249  1.1  perseant 
    250  1.1  perseant 	assert(!(bp->b_flags & B_NEEDCOMMIT));
    251  1.1  perseant 	assert(bp->b_flags & B_BUSY);
    252  1.1  perseant 
    253  1.1  perseant 	age = bp->b_flags & B_AGE;
    254  1.1  perseant 	bp->b_flags &= ~(B_BUSY | B_AGE);
    255  1.1  perseant 	if (bp->b_flags & B_INVAL) {
    256  1.1  perseant 		buf_destroy(bp);
    257  1.1  perseant 		return;
    258  1.1  perseant 	}
    259  1.1  perseant 	if (bp->b_flags & B_LOCKED) {
    260  1.1  perseant 		locked_queue_bytes += bp->b_bcount;
    261  1.1  perseant 		TAILQ_INSERT_TAIL(&bufqueues[BQ_LOCKED], bp, b_freelist);
    262  1.1  perseant 	} else if (age) {
    263  1.1  perseant 		TAILQ_INSERT_TAIL(&bufqueues[BQ_AGE], bp, b_freelist);
    264  1.1  perseant 	} else {
    265  1.1  perseant 		TAILQ_INSERT_TAIL(&bufqueues[BQ_LRU], bp, b_freelist);
    266  1.1  perseant 	}
    267  1.1  perseant 	--bp->b_vp->v_usecount;
    268  1.1  perseant }
    269  1.1  perseant 
    270  1.1  perseant /* Read the given block from disk, return it B_BUSY. */
    271  1.1  perseant int
    272  1.1  perseant bread(struct uvnode * vp, daddr_t lbn, int size, struct ucred * unused,
    273  1.1  perseant     struct ubuf ** bpp)
    274  1.1  perseant {
    275  1.1  perseant 	struct ubuf *bp;
    276  1.1  perseant 	daddr_t daddr;
    277  1.1  perseant 	int error, count;
    278  1.1  perseant 
    279  1.1  perseant 	bp = getblk(vp, lbn, size);
    280  1.1  perseant 	*bpp = bp;
    281  1.1  perseant 	if (bp->b_flags & (B_DELWRI | B_DONE)) {
    282  1.1  perseant 		++cachehits;
    283  1.1  perseant 		return 0;
    284  1.1  perseant 	}
    285  1.1  perseant 	++cachemisses;
    286  1.1  perseant 
    287  1.1  perseant 	/*
    288  1.1  perseant 	 * Not found.  Need to find that block's location on disk,
    289  1.1  perseant 	 * and load it in.
    290  1.1  perseant 	 */
    291  1.1  perseant 	daddr = -1;
    292  1.1  perseant 	error = VOP_BMAP(vp, lbn, &daddr);
    293  1.1  perseant 	bp->b_blkno = daddr;
    294  1.1  perseant 	if (daddr >= 0) {
    295  1.1  perseant 		count = pread(vp->v_fd, bp->b_data, bp->b_bcount,
    296  1.1  perseant 				dbtob((off_t) daddr));
    297  1.1  perseant 		if (count == bp->b_bcount) {
    298  1.1  perseant 			bp->b_flags |= B_DONE;
    299  1.1  perseant 			return 0;
    300  1.1  perseant 		}
    301  1.1  perseant 		return -1;
    302  1.1  perseant 	}
    303  1.1  perseant 	memset(bp->b_data, 0, bp->b_bcount);
    304  1.1  perseant 	return 0;
    305  1.1  perseant }
    306  1.1  perseant 
    307  1.1  perseant /* Move a buffer between dirty and clean block lists. */
    308  1.1  perseant void
    309  1.1  perseant reassignbuf(struct ubuf * bp, struct uvnode * vp)
    310  1.1  perseant {
    311  1.1  perseant 	LIST_REMOVE(bp, b_vnbufs);
    312  1.1  perseant 	if (bp->b_flags & B_DELWRI) {
    313  1.1  perseant 		LIST_INSERT_HEAD(&vp->v_dirtyblkhd, bp, b_vnbufs);
    314  1.1  perseant 	} else {
    315  1.1  perseant 		LIST_INSERT_HEAD(&vp->v_cleanblkhd, bp, b_vnbufs);
    316  1.1  perseant 	}
    317  1.1  perseant }
    318