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