The Design and Implementation of the FreeBSD Operating System, Second Edition
Now available: The Design and Implementation of the FreeBSD Operating System (Second Edition)


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]

FreeBSD/Linux Kernel Cross Reference
sys/kern/subr_disk.c

Version: -  FREEBSD  -  FREEBSD-12-STABLE  -  FREEBSD-12-0  -  FREEBSD-11-STABLE  -  FREEBSD-11-2  -  FREEBSD-11-1  -  FREEBSD-11-0  -  FREEBSD-10-STABLE  -  FREEBSD-10-4  -  FREEBSD-10-3  -  FREEBSD-10-2  -  FREEBSD-10-1  -  FREEBSD-10-0  -  FREEBSD-9-STABLE  -  FREEBSD-9-3  -  FREEBSD-9-2  -  FREEBSD-9-1  -  FREEBSD-9-0  -  FREEBSD-8-STABLE  -  FREEBSD-8-4  -  FREEBSD-8-3  -  FREEBSD-8-2  -  FREEBSD-8-1  -  FREEBSD-8-0  -  FREEBSD-7-STABLE  -  FREEBSD-7-4  -  FREEBSD-7-3  -  FREEBSD-7-2  -  FREEBSD-7-1  -  FREEBSD-7-0  -  FREEBSD-6-STABLE  -  FREEBSD-6-4  -  FREEBSD-6-3  -  FREEBSD-6-2  -  FREEBSD-6-1  -  FREEBSD-6-0  -  FREEBSD-5-STABLE  -  FREEBSD-5-5  -  FREEBSD-5-4  -  FREEBSD-5-3  -  FREEBSD-5-2  -  FREEBSD-5-1  -  FREEBSD-5-0  -  FREEBSD-4-STABLE  -  FREEBSD-3-STABLE  -  FREEBSD22  -  linux-2.6  -  linux-2.4.22  -  MK83  -  MK84  -  PLAN9  -  DFBSD  -  NETBSD  -  NETBSD5  -  NETBSD4  -  NETBSD3  -  NETBSD20  -  OPENBSD  -  xnu-517  -  xnu-792  -  xnu-792.6.70  -  xnu-1228  -  xnu-1456.1.26  -  xnu-1699.24.8  -  xnu-2050.18.24  -  OPENSOLARIS  -  minix-3-1-1 
SearchContext: -  none  -  3  -  10 

    1 /*-
    2  * ----------------------------------------------------------------------------
    3  * "THE BEER-WARE LICENSE" (Revision 42):
    4  * <phk@FreeBSD.ORG> wrote this file.  As long as you retain this notice you
    5  * can do whatever you want with this stuff. If we meet some day, and you think
    6  * this stuff is worth it, you can buy me a beer in return.   Poul-Henning Kamp
    7  * ----------------------------------------------------------------------------
    8  */
    9 
   10 #include <sys/cdefs.h>
   11 __FBSDID("$FreeBSD$");
   12 
   13 #include "opt_geom.h"
   14 
   15 #include <sys/param.h>
   16 #include <sys/systm.h>
   17 #include <sys/bio.h>
   18 #include <sys/conf.h>
   19 #include <sys/disk.h>
   20 #include <geom/geom_disk.h>
   21 
   22 /*-
   23  * Disk error is the preface to plaintive error messages
   24  * about failing disk transfers.  It prints messages of the form
   25  *      "hp0g: BLABLABLA cmd=read fsbn 12345 of 12344-12347"
   26  * blkdone should be -1 if the position of the error is unknown.
   27  * The message is printed with printf.
   28  */
   29 void
   30 disk_err(struct bio *bp, const char *what, int blkdone, int nl)
   31 {
   32         daddr_t sn;
   33 
   34         if (bp->bio_dev != NULL)
   35                 printf("%s: %s ", devtoname(bp->bio_dev), what);
   36         else if (bp->bio_disk != NULL)
   37                 printf("%s%d: %s ",
   38                     bp->bio_disk->d_name, bp->bio_disk->d_unit, what);
   39         else
   40                 printf("disk??: %s ", what);
   41         switch(bp->bio_cmd) {
   42         case BIO_READ:          printf("cmd=read "); break;
   43         case BIO_WRITE:         printf("cmd=write "); break;
   44         case BIO_DELETE:        printf("cmd=delete "); break;
   45         case BIO_GETATTR:       printf("cmd=getattr "); break;
   46         case BIO_FLUSH:         printf("cmd=flush "); break;
   47         default:                printf("cmd=%x ", bp->bio_cmd); break;
   48         }
   49         sn = bp->bio_pblkno;
   50         if (bp->bio_bcount <= DEV_BSIZE) {
   51                 printf("fsbn %jd%s", (intmax_t)sn, nl ? "\n" : "");
   52                 return;
   53         }
   54         if (blkdone >= 0) {
   55                 sn += blkdone;
   56                 printf("fsbn %jd of ", (intmax_t)sn);
   57         }
   58         printf("%jd-%jd", (intmax_t)bp->bio_pblkno,
   59             (intmax_t)(bp->bio_pblkno + (bp->bio_bcount - 1) / DEV_BSIZE));
   60         if (nl)
   61                 printf("\n");
   62 }
   63 
   64 /*
   65  * BIO queue implementation
   66  */
   67 
   68 void
   69 bioq_init(struct bio_queue_head *head)
   70 {
   71         TAILQ_INIT(&head->queue);
   72         head->last_offset = 0;
   73         head->insert_point = NULL;
   74 }
   75 
   76 void
   77 bioq_remove(struct bio_queue_head *head, struct bio *bp)
   78 {
   79         if (bp == head->insert_point) {
   80                 head->last_offset = bp->bio_offset;
   81                 head->insert_point = TAILQ_NEXT(bp, bio_queue);
   82                 if (head->insert_point == NULL) {
   83                         head->last_offset = 0;
   84                         head->insert_point = TAILQ_FIRST(&head->queue);
   85                 }
   86         }
   87         TAILQ_REMOVE(&head->queue, bp, bio_queue);
   88 }
   89 
   90 void
   91 bioq_flush(struct bio_queue_head *head, struct devstat *stp, int error)
   92 {
   93         struct bio *bp;
   94 
   95         while ((bp = bioq_takefirst(head)) != NULL)
   96                 biofinish(bp, stp, error);
   97 }
   98 
   99 void
  100 bioq_insert_head(struct bio_queue_head *head, struct bio *bp)
  101 {
  102 
  103         if (TAILQ_EMPTY(&head->queue))
  104                 head->insert_point = bp;
  105         TAILQ_INSERT_HEAD(&head->queue, bp, bio_queue);
  106 }
  107 
  108 void
  109 bioq_insert_tail(struct bio_queue_head *head, struct bio *bp)
  110 {
  111 
  112         if (TAILQ_EMPTY(&head->queue))
  113                 head->insert_point = bp;
  114         TAILQ_INSERT_TAIL(&head->queue, bp, bio_queue);
  115 }
  116 
  117 struct bio *
  118 bioq_first(struct bio_queue_head *head)
  119 {
  120 
  121         return (TAILQ_FIRST(&head->queue));
  122 }
  123 
  124 struct bio *
  125 bioq_takefirst(struct bio_queue_head *head)
  126 {
  127         struct bio *bp;
  128 
  129         bp = TAILQ_FIRST(&head->queue);
  130         if (bp != NULL)
  131                 bioq_remove(head, bp);
  132         return (bp);
  133 }
  134 
  135 /*
  136  * Seek sort for disks.
  137  *
  138  * The disksort algorithm sorts all requests in a single queue while keeping
  139  * track of the current position of the disk with insert_point and
  140  * last_offset.  last_offset is the offset of the last block sent to disk, or
  141  * 0 once we reach the end.  insert_point points to the first buf after
  142  * last_offset, and is used to slightly speed up insertions.  Blocks are
  143  * always sorted in ascending order and the queue always restarts at 0.
  144  * This implements the one-way scan which optimizes disk seek times.
  145  */
  146 void
  147 bioq_disksort(bioq, bp)
  148         struct bio_queue_head *bioq;
  149         struct bio *bp;
  150 {
  151         struct bio *bq;
  152         struct bio *bn;
  153 
  154         /*
  155          * If the queue is empty then it's easy.
  156          */
  157         if (bioq_first(bioq) == NULL) {
  158                 bioq_insert_tail(bioq, bp);
  159                 return;
  160         }
  161         /*
  162          * Optimize for sequential I/O by seeing if we go at the tail.
  163          */
  164         bq = TAILQ_LAST(&bioq->queue, bio_queue);
  165         if (bp->bio_offset > bq->bio_offset) {
  166                 TAILQ_INSERT_AFTER(&bioq->queue, bq, bp, bio_queue);
  167                 return;
  168         }
  169         /*
  170          * Pick our scan start based on the last request.  A poor man's
  171          * binary search.
  172          */
  173         if (bp->bio_offset >= bioq->last_offset) { 
  174                 bq = bioq->insert_point;
  175                 /*
  176                  * If we're before the next bio and after the last offset,
  177                  * update insert_point;
  178                  */
  179                 if (bp->bio_offset < bq->bio_offset) {
  180                         bioq->insert_point = bp;
  181                         TAILQ_INSERT_BEFORE(bq, bp, bio_queue);
  182                         return;
  183                 }
  184         } else
  185                 bq = TAILQ_FIRST(&bioq->queue);
  186         if (bp->bio_offset < bq->bio_offset) {
  187                 TAILQ_INSERT_BEFORE(bq, bp, bio_queue);
  188                 return;
  189         }
  190         /* Insertion sort */
  191         while ((bn = TAILQ_NEXT(bq, bio_queue)) != NULL) {
  192                 if (bp->bio_offset < bn->bio_offset)
  193                         break;
  194                 bq = bn;
  195         }
  196         TAILQ_INSERT_AFTER(&bioq->queue, bq, bp, bio_queue);
  197 }

Cache object: 61241c219317badd12993540ac9cf4bf


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]


This page is part of the FreeBSD/Linux Linux Kernel Cross-Reference, and was automatically generated using a modified version of the LXR engine.