text: /*-
   * Copyright (c) 1998 Michael Smith <msmith@freebsd.org>
   * Copyright 2015 Toomas Soome <tsoome@me.com>
   * All rights reserved.
   *
   * Redistribution and use in source and binary forms, with or without
   * modification, are permitted provided that the following conditions
   * are met:
   * 1. Redistributions of source code must retain the above copyright
   *    notice, this list of conditions and the following disclaimer.
   * 2. Redistributions in binary form must reproduce the above copyright
   *    notice, this list of conditions and the following disclaimer in the
   *    documentation and/or other materials provided with the distribution.
   *
   * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
   * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
   * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
   * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
   * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
   * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
   * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
   * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
   * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
   * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
   * SUCH DAMAGE.
   */
  
  #include <sys/cdefs.h>
  #include <sys/param.h>
  __FBSDID("$FreeBSD: releng/11.0/sys/boot/common/bcache.c 298900 2016-05-01 21:06:59Z allanjude $");
  
  /*
   * Simple hashed block cache
   */
  
  #include <sys/stdint.h>
  
  #include <stand.h>
  #include <string.h>
  #include <strings.h>
  
  #include "bootstrap.h"
  
  /* #define BCACHE_DEBUG */
  
  #ifdef BCACHE_DEBUG
  # define DEBUG(fmt, args...)	printf("%s: " fmt "\n" , __func__ , ## args)
  #else
  # define DEBUG(fmt, args...)
  #endif
  
  struct bcachectl
  {
      daddr_t	bc_blkno;
      int		bc_count;
  };
  
  /*
   * bcache per device node. cache is allocated on device first open and freed
   * on last close, to save memory. The issue there is the size; biosdisk
   * supports up to 31 (0x1f) devices. Classic setup would use single disk
   * to boot from, but this has changed with zfs.
   */
  struct bcache {
      struct bcachectl	*bcache_ctl;
      caddr_t		bcache_data;
      u_int		bcache_nblks;
      size_t		ra;
  };
  
  static u_int bcache_total_nblks;	/* set by bcache_init */
  static u_int bcache_blksize;		/* set by bcache_init */
  static u_int bcache_numdev;		/* set by bcache_add_dev */
  /* statistics */
  static u_int bcache_units;	/* number of devices with cache */
  static u_int bcache_unit_nblks;	/* nblocks per unit */
  static u_int bcache_hits;
  static u_int bcache_misses;
  static u_int bcache_ops;
  static u_int bcache_bypasses;
  static u_int bcache_bcount;
  static u_int bcache_rablks;
  
  #define	BHASH(bc, blkno)	((blkno) & ((bc)->bcache_nblks - 1))
  #define	BCACHE_LOOKUP(bc, blkno)	\
  	((bc)->bcache_ctl[BHASH((bc), (blkno))].bc_blkno != (blkno))
  #define	BCACHE_READAHEAD	256
  #define	BCACHE_MINREADAHEAD	32
  
  static void	bcache_invalidate(struct bcache *bc, daddr_t blkno);
  static void	bcache_insert(struct bcache *bc, daddr_t blkno);
  static void	bcache_free_instance(struct bcache *bc);
  
  /*
   * Initialise the cache for (nblks) of (bsize).
   */
  void
  bcache_init(u_int nblks, size_t bsize)
  {
      /* set up control data */
      bcache_total_nblks = nblks;
      bcache_blksize = bsize;
  }
  
  /*
   * add number of devices to bcache. we have to divide cache space
   * between the devices, so bcache_add_dev() can be used to set up the
   * number. The issue is, we need to get the number before actual allocations.
   * bcache_add_dev() is supposed to be called from device init() call, so the
   * assumption is, devsw dv_init is called for plain devices first, and
   * for zfs, last.
   */
  void
  bcache_add_dev(int devices)
  {
      bcache_numdev += devices;
  }
  
  void *
  bcache_allocate(void)
  {
      u_int i;
      struct bcache *bc = malloc(sizeof (struct bcache));
      int disks = bcache_numdev;
  
      if (disks == 0)
  	disks = 1;	/* safe guard */
  
      if (bc == NULL) {
  	errno = ENOMEM;
  	return (bc);
      }
  
      /*
       * the bcache block count must be power of 2 for hash function
       */
      i = fls(disks) - 1;		/* highbit - 1 */
      if (disks > (1 << i))	/* next power of 2 */
  	i++;
  
      bc->bcache_nblks = bcache_total_nblks >> i;
      bcache_unit_nblks = bc->bcache_nblks;
      bc->bcache_data = malloc(bc->bcache_nblks * bcache_blksize);
      if (bc->bcache_data == NULL) {
  	/* dont error out yet. fall back to 32 blocks and try again */
  	bc->bcache_nblks = 32;
  	bc->bcache_data = malloc(bc->bcache_nblks * bcache_blksize);
      }
  
      bc->bcache_ctl = malloc(bc->bcache_nblks * sizeof(struct bcachectl));
  
      if ((bc->bcache_data == NULL) || (bc->bcache_ctl == NULL)) {
  	bcache_free_instance(bc);
  	errno = ENOMEM;
  	return(NULL);
      }
  
      /* Flush the cache */
      for (i = 0; i < bc->bcache_nblks; i++) {
  	bc->bcache_ctl[i].bc_count = -1;
  	bc->bcache_ctl[i].bc_blkno = -1;
      }
      bcache_units++;
      bc->ra = BCACHE_READAHEAD;	/* optimistic read ahead */
      return (bc);
  }
  
  void
  bcache_free(void *cache)
  {
      struct bcache *bc = cache;
  
      if (bc == NULL)
  	return;
  
      bcache_free_instance(bc);
      bcache_units--;
  }
  
  /*
   * Handle a write request; write directly to the disk, and populate the
   * cache with the new values.
   */
  static int
  write_strategy(void *devdata, int rw, daddr_t blk, size_t offset,
      size_t size, char *buf, size_t *rsize)
  {
      struct bcache_devdata	*dd = (struct bcache_devdata *)devdata;
      struct bcache		*bc = dd->dv_cache;
      daddr_t			i, nblk;
  
      nblk = size / bcache_blksize;
  
      /* Invalidate the blocks being written */
      for (i = 0; i < nblk; i++) {
  	bcache_invalidate(bc, blk + i);
      }
  
      /* Write the blocks */
      return (dd->dv_strategy(dd->dv_devdata, rw, blk, offset, size, buf, rsize));
  }
  
  /*
   * Handle a read request; fill in parts of the request that can
   * be satisfied by the cache, use the supplied strategy routine to do
   * device I/O and then use the I/O results to populate the cache. 
   */
  static int
  read_strategy(void *devdata, int rw, daddr_t blk, size_t offset,
      size_t size, char *buf, size_t *rsize)
  {
      struct bcache_devdata	*dd = (struct bcache_devdata *)devdata;
      struct bcache		*bc = dd->dv_cache;
      size_t			i, nblk, p_size, r_size, complete, ra;
      int				result;
      daddr_t			p_blk;
      caddr_t			p_buf;
  
      if (bc == NULL) {
  	errno = ENODEV;
  	return (-1);
      }
  
      if (rsize != NULL)
  	*rsize = 0;
  
      nblk = size / bcache_blksize;
      if ((nblk == 0 && size != 0) || offset != 0)
  	nblk++;
      result = 0;
      complete = 1;
  
      /* Satisfy any cache hits up front, break on first miss */
      for (i = 0; i < nblk; i++) {
  	if (BCACHE_LOOKUP(bc, (daddr_t)(blk + i))) {
  	    bcache_misses += (nblk - i);
  	    complete = 0;
  	    if (nblk - i > BCACHE_MINREADAHEAD && bc->ra > BCACHE_MINREADAHEAD)
  		bc->ra >>= 1;	/* reduce read ahead */
  	    break;
  	} else {
  	    bcache_hits++;
  	}
      }
  
     if (complete) {	/* whole set was in cache, return it */
  	if (bc->ra < BCACHE_READAHEAD)
  		bc->ra <<= 1;	/* increase read ahead */
  	bcopy(bc->bcache_data + (bcache_blksize * BHASH(bc, blk)) + offset,
  	    buf, size);
  	goto done;
     }
  
      /*
       * Fill in any misses. From check we have i pointing to first missing
       * block, read in all remaining blocks + readahead.
       * We have space at least for nblk - i before bcache wraps.
       */
      p_blk = blk + i;
      p_buf = bc->bcache_data + (bcache_blksize * BHASH(bc, p_blk));
      r_size = bc->bcache_nblks - BHASH(bc, p_blk); /* remaining blocks */
  
      p_size = MIN(r_size, nblk - i);	/* read at least those blocks */
  
      ra = bc->bcache_nblks - BHASH(bc, p_blk + p_size);
      if (ra != bc->bcache_nblks) { /* do we have RA space? */
  	ra = MIN(bc->ra, ra);
  	p_size += ra;
      }
  
      /* invalidate bcache */
      for (i = 0; i < p_size; i++) {
  	bcache_invalidate(bc, p_blk + i);
      }
  
      r_size = 0;
      /*
       * with read-ahead, it may happen we are attempting to read past
       * disk end, as bcache has no information about disk size.
       * in such case we should get partial read if some blocks can be
       * read or error, if no blocks can be read.
       * in either case we should return the data in bcache and only
       * return error if there is no data.
       */
      result = dd->dv_strategy(dd->dv_devdata, rw, p_blk, 0,
  	p_size * bcache_blksize, p_buf, &r_size);
  
      r_size /= bcache_blksize;
      for (i = 0; i < r_size; i++)
  	bcache_insert(bc, p_blk + i);
  
      /* update ra statistics */
      if (r_size != 0) {
  	if (r_size < p_size)
  	    bcache_rablks += (p_size - r_size);
  	else
  	    bcache_rablks += ra;
      }
  
      /* check how much data can we copy */
      for (i = 0; i < nblk; i++) {
  	if (BCACHE_LOOKUP(bc, (daddr_t)(blk + i)))
  	    break;
      }
  
      size = i * bcache_blksize;
      if (size != 0) {
  	bcopy(bc->bcache_data + (bcache_blksize * BHASH(bc, blk)) + offset,
  	    buf, size);
  	result = 0;
      }
  
   done:
      if ((result == 0) && (rsize != NULL))
  	*rsize = size;
      return(result);
  }
  
  /* 
   * Requests larger than 1/2 cache size will be bypassed and go
   * directly to the disk.  XXX tune this.
   */
  int
  bcache_strategy(void *devdata, int rw, daddr_t blk, size_t offset,
      size_t size, char *buf, size_t *rsize)
  {
      struct bcache_devdata	*dd = (struct bcache_devdata *)devdata;
      struct bcache		*bc = dd->dv_cache;
      u_int bcache_nblks = 0;
      int nblk, cblk, ret;
      size_t csize, isize, total;
  
      bcache_ops++;
  
      if (bc != NULL)
  	bcache_nblks = bc->bcache_nblks;
  
      /* bypass large requests, or when the cache is inactive */
      if (bc == NULL ||
  	(offset == 0 && ((size * 2 / bcache_blksize) > bcache_nblks))) {
  	DEBUG("bypass %d from %d", size / bcache_blksize, blk);
  	bcache_bypasses++;
  	return (dd->dv_strategy(dd->dv_devdata, rw, blk, offset, size, buf,
  	    rsize));
      }
  
      /* normalize offset */
      while (offset >= bcache_blksize) {
  	blk++;
  	offset -= bcache_blksize;
      }
  
      switch (rw) {
      case F_READ:
  	nblk = size / bcache_blksize;
  	if (offset || (size != 0 && nblk == 0))
  	    nblk++;	/* read at least one block */
  
  	ret = 0;
  	total = 0;
  	while(size) {
  	    cblk = bcache_nblks - BHASH(bc, blk); /* # of blocks left */
  	    cblk = MIN(cblk, nblk);
  
  	    if (size <= bcache_blksize)
  		csize = size;
  	    else {
  		csize = cblk * bcache_blksize;
  		if (offset)
  		    csize -= (bcache_blksize - offset);
  	    }
  
  	    ret = read_strategy(devdata, rw, blk, offset,
  		csize, buf+total, &isize);
  
  	    /*
  	     * we may have error from read ahead, if we have read some data
  	     * return partial read.
  	     */
  	    if (ret != 0 || isize == 0) {
  		if (total != 0)
  		    ret = 0;
  		break;
  	    }
  	    blk += (offset+isize) / bcache_blksize;
  	    offset = 0;
  	    total += isize;
  	    size -= isize;
  	    nblk = size / bcache_blksize;
  	}
  
  	if (rsize)
  	    *rsize = total;
  
  	return (ret);
      case F_WRITE:
  	return write_strategy(devdata, rw, blk, offset, size, buf, rsize);
      }
      return -1;
  }
  
  /*
   * Free allocated bcache instance
   */
  static void
  bcache_free_instance(struct bcache *bc)
  {
      if (bc != NULL) {
  	if (bc->bcache_ctl)
  	    free(bc->bcache_ctl);
  	if (bc->bcache_data)
  	    free(bc->bcache_data);
  	free(bc);
      }
  }
  
  /*
   * Insert a block into the cache.
   */
  static void
  bcache_insert(struct bcache *bc, daddr_t blkno)
  {
      u_int	cand;
      
      cand = BHASH(bc, blkno);
  
      DEBUG("insert blk %llu -> %u # %d", blkno, cand, bcache_bcount);
      bc->bcache_ctl[cand].bc_blkno = blkno;
      bc->bcache_ctl[cand].bc_count = bcache_bcount++;
  }
  
  /*
   * Invalidate a block from the cache.
   */
  static void
  bcache_invalidate(struct bcache *bc, daddr_t blkno)
  {
      u_int	i;
      
      i = BHASH(bc, blkno);
      if (bc->bcache_ctl[i].bc_blkno == blkno) {
  	bc->bcache_ctl[i].bc_count = -1;
  	bc->bcache_ctl[i].bc_blkno = -1;
  	DEBUG("invalidate blk %llu", blkno);
      }
  }
  
  #ifndef BOOT2
  COMMAND_SET(bcachestat, "bcachestat", "get disk block cache stats", command_bcache);
  
  static int
  command_bcache(int argc, char *argv[])
  {
      if (argc != 1) {
  	command_errmsg = "wrong number of arguments";
  	return(CMD_ERROR);
      }
  
      printf("\ncache blocks: %d\n", bcache_total_nblks);
      printf("cache blocksz: %d\n", bcache_blksize);
      printf("cache readahead: %d\n", bcache_rablks);
      printf("unit cache blocks: %d\n", bcache_unit_nblks);
      printf("cached units: %d\n", bcache_units);
      printf("%d ops  %d bypasses  %d hits  %d misses\n", bcache_ops,
  	bcache_bypasses, bcache_hits, bcache_misses);
      return(CMD_OK);
  }
  #endif
  