sys/boot/common/bcache.c

   1 /*-
   2  * Copyright (c) 1998 Michael Smith <msmith@freebsd.org>
   3  * 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  *
  14  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
  15  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  16  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  17  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  18  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  19  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  20  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  21  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  22  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  23  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  24  * SUCH DAMAGE.
  25  *
  26  * $FreeBSD: src/sys/boot/common/bcache.c,v 1.12 2003/08/25 23:30:41 obrien Exp $
  27  * $DragonFly: src/sys/boot/common/bcache.c,v 1.3 2003/11/10 06:08:31 dillon Exp $
  28  */
  29
  30 /*
  31  * Simple LRU block cache
  32  */
  33
  34 #include <stand.h>
  35 #include <string.h>
  36 #include <bitstring.h>
  37
  38 #include "bootstrap.h"
  39
  40 /* #define BCACHE_DEBUG */
  41
  42 #ifdef BCACHE_DEBUG
  43 #define BCACHE_TIMEOUT  10
  44 # define DEBUG(fmt, args...)    printf("%s: " fmt "\n" , __func__ , ## args)
  45 #else
  46 #define BCACHE_TIMEOUT  2
  47 # define DEBUG(fmt, args...)
  48 #endif
  49
  50
  51 struct bcachectl
  52 {
  53     daddr_t     bc_blkno;
  54     time_t      bc_stamp;
  55     int         bc_count;
  56 };
  57
  58 static struct bcachectl *bcache_ctl;
  59 static caddr_t          bcache_data;
  60 static bitstr_t         *bcache_miss;
  61 static u_int            bcache_nblks;
  62 static u_int            bcache_blksize;
  63 static u_int            bcache_hits, bcache_misses, bcache_ops, bcache_bypasses;
  64 static u_int            bcache_flushes;
  65 static u_int            bcache_bcount;
  66
  67 static void     bcache_invalidate(daddr_t blkno);
  68 static void     bcache_insert(caddr_t buf, daddr_t blkno);
  69 static int      bcache_lookup(caddr_t buf, daddr_t blkno);
  70
  71 /*
  72  * Initialise the cache for (nblks) of (bsize).
  73  */
  74 int
  75 bcache_init(u_int nblks, size_t bsize)
  76 {
  77     /* discard any old contents */
  78     if (bcache_data != NULL) {
  79         free(bcache_data);
  80         bcache_data = NULL;
  81         free(bcache_ctl);
  82     }
  83
  84     /* Allocate control structures */
  85     bcache_nblks = nblks;
  86     bcache_blksize = bsize;
  87     bcache_data = malloc(bcache_nblks * bcache_blksize);
  88     bcache_ctl = (struct bcachectl *)malloc(bcache_nblks * sizeof(struct bcachectl));
  89     bcache_miss = bit_alloc((bcache_nblks + 1) / 2);
  90     if ((bcache_data == NULL) || (bcache_ctl == NULL) || (bcache_miss == NULL)) {
  91         if (bcache_miss)
  92             free(bcache_miss);
  93         if (bcache_ctl)
  94             free(bcache_ctl);
  95         if (bcache_data)
  96             free(bcache_data);
  97         bcache_data = NULL;
  98         return(ENOMEM);
  99     }
 100
 101     return(0);
 102 }
 103
 104 /*
 105  * Flush the cache
 106  */
 107 void
 108 bcache_flush(void)
 109 {
 110     u_int       i;
 111
 112     bcache_flushes++;
 113
 114     /* Flush the cache */
 115     for (i = 0; i < bcache_nblks; i++) {
 116         bcache_ctl[i].bc_count = -1;
 117         bcache_ctl[i].bc_blkno = -1;
 118     }
 119 }
 120
 121 /*
 122  * Handle a write request; write directly to the disk, and populate the
 123  * cache with the new values.
 124  */
 125 static int
 126 write_strategy(void *devdata, int unit, int rw, daddr_t blk, size_t size,
 127                 char *buf, size_t *rsize)
 128 {
 129     struct bcache_devdata       *dd = (struct bcache_devdata *)devdata;
 130     daddr_t                     i, nblk;
 131     int                         err;
 132
 133     nblk = size / bcache_blksize;
 134
 135     /* Invalidate the blocks being written */
 136     for (i = 0; i < nblk; i++) {
 137         bcache_invalidate(blk + i);
 138     }
 139
 140     /* Write the blocks */
 141     err = dd->dv_strategy(dd->dv_devdata, rw, blk, size, buf, rsize);
 142
 143     /* Populate the block cache with the new data */
 144     if (err == 0) {
 145         for (i = 0; i < nblk; i++) {
 146             bcache_insert(buf + (i * bcache_blksize),blk + i);
 147         }
 148     }
 149
 150     return err;
 151 }
 152
 153 /*
 154  * Handle a read request; fill in parts of the request that can
 155  * be satisfied by the cache, use the supplied strategy routine to do
 156  * device I/O and then use the I/O results to populate the cache.
 157  */
 158 static int
 159 read_strategy(void *devdata, int unit, int rw, daddr_t blk, size_t size,
 160                 char *buf, size_t *rsize)
 161 {
 162     struct bcache_devdata       *dd = (struct bcache_devdata *)devdata;
 163     int                         p_size, result;
 164     daddr_t                     p_blk, i, j, nblk;
 165     caddr_t                     p_buf;
 166
 167     nblk = size / bcache_blksize;
 168     result = 0;
 169
 170     /* Satisfy any cache hits up front */
 171     for (i = 0; i < nblk; i++) {
 172         if (bcache_lookup(buf + (bcache_blksize * i), blk + i)) {
 173             bit_set(bcache_miss, i);    /* cache miss */
 174             bcache_misses++;
 175         } else {
 176             bit_clear(bcache_miss, i);  /* cache hit */
 177             bcache_hits++;
 178         }
 179     }
 180
 181     /* Go back and fill in any misses  XXX optimise */
 182     p_blk = -1;
 183     p_buf = NULL;
 184     p_size = 0;
 185     for (i = 0; i < nblk; i++) {
 186         if (bit_test(bcache_miss, i)) {
 187             /* miss, add to pending transfer */
 188             if (p_blk == -1) {
 189                 p_blk = blk + i;
 190                 p_buf = buf + (bcache_blksize * i);
 191                 p_size = 1;
 192             } else {
 193                 p_size++;
 194             }
 195         } else if (p_blk != -1) {
 196             /* hit, complete pending transfer */
 197             result = dd->dv_strategy(dd->dv_devdata, rw, p_blk, p_size * bcache_blksize, p_buf, NULL);
 198             if (result != 0)
 199                 goto done;
 200             for (j = 0; j < p_size; j++)
 201                 bcache_insert(p_buf + (j * bcache_blksize), p_blk + j);
 202             p_blk = -1;
 203         }
 204     }
 205     if (p_blk != -1) {
 206         /* pending transfer left */
 207         result = dd->dv_strategy(dd->dv_devdata, rw, p_blk, p_size * bcache_blksize, p_buf, NULL);
 208         if (result != 0)
 209             goto done;
 210         for (j = 0; j < p_size; j++)
 211             bcache_insert(p_buf + (j * bcache_blksize), p_blk + j);
 212     }
 213
 214  done:
 215     if ((result == 0) && (rsize != NULL))
 216         *rsize = size;
 217     return(result);
 218 }
 219
 220 /*
 221  * Requests larger than 1/2 the cache size will be bypassed and go
 222  * directly to the disk.  XXX tune this.
 223  */
 224 int
 225 bcache_strategy(void *devdata, int unit, int rw, daddr_t blk, size_t size,
 226                 char *buf, size_t *rsize)
 227 {
 228     static int                  bcache_unit = -1;
 229     struct bcache_devdata       *dd = (struct bcache_devdata *)devdata;
 230
 231     bcache_ops++;
 232
 233     if(bcache_unit != unit) {
 234         bcache_flush();
 235         bcache_unit = unit;
 236     }
 237
 238     /* bypass large requests, or when the cache is inactive */
 239     if ((bcache_data == NULL) || ((size * 2 / bcache_blksize) > bcache_nblks)) {
 240         DEBUG("bypass %d from %d", size / bcache_blksize, blk);
 241         bcache_bypasses++;
 242         return(dd->dv_strategy(dd->dv_devdata, rw, blk, size, buf, rsize));
 243     }
 244
 245     switch (rw) {
 246     case F_READ:
 247         return read_strategy(devdata, unit, rw, blk, size, buf, rsize);
 248     case F_WRITE:
 249         return write_strategy(devdata, unit, rw, blk, size, buf, rsize);
 250     }
 251     return -1;
 252 }
 253
 254
 255 /*
 256  * Insert a block into the cache.  Retire the oldest block to do so, if required.
 257  *
 258  * XXX the LRU algorithm will fail after 2^31 blocks have been transferred.
 259  */
 260 static void
 261 bcache_insert(caddr_t buf, daddr_t blkno)
 262 {
 263     time_t      now;
 264     int         cand, ocount;
 265     u_int       i;
 266
 267     time(&now);
 268     cand = 0;                           /* assume the first block */
 269     ocount = bcache_ctl[0].bc_count;
 270
 271     /* find the oldest block */
 272     for (i = 1; i < bcache_nblks; i++) {
 273         if (bcache_ctl[i].bc_blkno == blkno) {
 274             /* reuse old entry */
 275             cand = i;
 276             break;
 277         }
 278         if (bcache_ctl[i].bc_count < ocount) {
 279             ocount = bcache_ctl[i].bc_count;
 280             cand = i;
 281         }
 282     }
 283
 284     DEBUG("insert blk %d -> %d @ %d # %d", blkno, cand, now, bcache_bcount);
 285     bcopy(buf, bcache_data + (bcache_blksize * cand), bcache_blksize);
 286     bcache_ctl[cand].bc_blkno = blkno;
 287     bcache_ctl[cand].bc_stamp = now;
 288     bcache_ctl[cand].bc_count = bcache_bcount++;
 289 }
 290
 291 /*
 292  * Look for a block in the cache.  Blocks more than BCACHE_TIMEOUT seconds old
 293  * may be stale (removable media) and thus are discarded.  Copy the block out
 294  * if successful and return zero, or return nonzero on failure.
 295  */
 296 static int
 297 bcache_lookup(caddr_t buf, daddr_t blkno)
 298 {
 299     time_t      now;
 300     u_int       i;
 301
 302     time(&now);
 303
 304     for (i = 0; i < bcache_nblks; i++)
 305         /* cache hit? */
 306         if ((bcache_ctl[i].bc_blkno == blkno) && ((bcache_ctl[i].bc_stamp + BCACHE_TIMEOUT) >= now)) {
 307             bcopy(bcache_data + (bcache_blksize * i), buf, bcache_blksize);
 308             DEBUG("hit blk %d <- %d (now %d then %d)", blkno, i, now, bcache_ctl[i].bc_stamp);
 309             return(0);
 310         }
 311     return(ENOENT);
 312 }
 313
 314 /*
 315  * Invalidate a block from the cache.
 316  */
 317 static void
 318 bcache_invalidate(daddr_t blkno)
 319 {
 320     u_int       i;
 321
 322     for (i = 0; i < bcache_nblks; i++) {
 323         if (bcache_ctl[i].bc_blkno == blkno) {
 324             bcache_ctl[i].bc_count = -1;
 325             bcache_ctl[i].bc_blkno = -1;
 326             DEBUG("invalidate blk %d", blkno);
 327             break;
 328         }
 329     }
 330 }
 331
 332 COMMAND_SET(bcachestat, "bcachestat", "get disk block cache stats", command_bcache);
 333
 334 static int
 335 command_bcache(int argc, char *argv[])
 336 {
 337     u_int       i;
 338
 339     for (i = 0; i < bcache_nblks; i++) {
 340         printf("%08x %04x %04x|", bcache_ctl[i].bc_blkno, (unsigned int)bcache_ctl[i].bc_stamp & 0xffff, bcache_ctl[i].bc_count & 0xffff);
 341         if (((i + 1) % 4) == 0)
 342             printf("\n");
 343     }
 344     printf("\n%d ops  %d bypasses  %d hits  %d misses  %d flushes\n", bcache_ops, bcache_bypasses, bcache_hits, bcache_misses, bcache_flushes);
 345     return(CMD_OK);
 346 }
 347