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  * The bioq_disksort() (and the specification of the bioq API)
   10  * have been written by Luigi Rizzo and Fabio Checconi under the same
   11  * license as above.
   12  */
   13 
   14 #include <sys/cdefs.h>
   15 __FBSDID("$FreeBSD: releng/11.1/sys/kern/subr_disk.c 212160 2010-09-02 19:40:28Z gibbs $");
   16 
   17 #include "opt_geom.h"
   18 
   19 #include <sys/param.h>
   20 #include <sys/systm.h>
   21 #include <sys/bio.h>
   22 #include <sys/conf.h>
   23 #include <sys/disk.h>
   24 #include <geom/geom_disk.h>
   25 
   26 /*-
   27  * Disk error is the preface to plaintive error messages
   28  * about failing disk transfers.  It prints messages of the form
   29  *      "hp0g: BLABLABLA cmd=read fsbn 12345 of 12344-12347"
   30  * blkdone should be -1 if the position of the error is unknown.
   31  * The message is printed with printf.
   32  */
   33 void
   34 disk_err(struct bio *bp, const char *what, int blkdone, int nl)
   35 {
   36         daddr_t sn;
   37 
   38         if (bp->bio_dev != NULL)
   39                 printf("%s: %s ", devtoname(bp->bio_dev), what);
   40         else if (bp->bio_disk != NULL)
   41                 printf("%s%d: %s ",
   42                     bp->bio_disk->d_name, bp->bio_disk->d_unit, what);
   43         else
   44                 printf("disk??: %s ", what);
   45         switch(bp->bio_cmd) {
   46         case BIO_READ:          printf("cmd=read "); break;
   47         case BIO_WRITE:         printf("cmd=write "); break;
   48         case BIO_DELETE:        printf("cmd=delete "); break;
   49         case BIO_GETATTR:       printf("cmd=getattr "); break;
   50         case BIO_FLUSH:         printf("cmd=flush "); break;
   51         default:                printf("cmd=%x ", bp->bio_cmd); break;
   52         }
   53         sn = bp->bio_pblkno;
   54         if (bp->bio_bcount <= DEV_BSIZE) {
   55                 printf("fsbn %jd%s", (intmax_t)sn, nl ? "\n" : "");
   56                 return;
   57         }
   58         if (blkdone >= 0) {
   59                 sn += blkdone;
   60                 printf("fsbn %jd of ", (intmax_t)sn);
   61         }
   62         printf("%jd-%jd", (intmax_t)bp->bio_pblkno,
   63             (intmax_t)(bp->bio_pblkno + (bp->bio_bcount - 1) / DEV_BSIZE));
   64         if (nl)
   65                 printf("\n");
   66 }
   67 
   68 /*
   69  * BIO queue implementation
   70  *
   71  * Please read carefully the description below before making any change
   72  * to the code, or you might change the behaviour of the data structure
   73  * in undesirable ways.
   74  *
   75  * A bioq stores disk I/O request (bio), normally sorted according to
   76  * the distance of the requested position (bio->bio_offset) from the
   77  * current head position (bioq->last_offset) in the scan direction, i.e.
   78  *
   79  *      (uoff_t)(bio_offset - last_offset)
   80  *
   81  * Note that the cast to unsigned (uoff_t) is fundamental to insure
   82  * that the distance is computed in the scan direction.
   83  *
   84  * The main methods for manipulating the bioq are:
   85  *
   86  *   bioq_disksort()    performs an ordered insertion;
   87  *
   88  *   bioq_first()       return the head of the queue, without removing;
   89  *
   90  *   bioq_takefirst()   return and remove the head of the queue,
   91  *              updating the 'current head position' as
   92  *              bioq->last_offset = bio->bio_offset + bio->bio_length;
   93  *
   94  * When updating the 'current head position', we assume that the result of
   95  * bioq_takefirst() is dispatched to the device, so bioq->last_offset
   96  * represents the head position once the request is complete.
   97  *
   98  * If the bioq is manipulated using only the above calls, it starts
   99  * with a sorted sequence of requests with bio_offset >= last_offset,
  100  * possibly followed by another sorted sequence of requests with
  101  * 0 <= bio_offset < bioq->last_offset 
  102  *
  103  * NOTE: historical behaviour was to ignore bio->bio_length in the
  104  *      update, but its use tracks the head position in a better way.
  105  *      Historical behaviour was also to update the head position when
  106  *      the request under service is complete, rather than when the
  107  *      request is extracted from the queue. However, the current API
  108  *      has no method to update the head position; secondly, once
  109  *      a request has been submitted to the disk, we have no idea of
  110  *      the actual head position, so the final one is our best guess.
  111  *
  112  * --- Direct queue manipulation ---
  113  *
  114  * A bioq uses an underlying TAILQ to store requests, so we also
  115  * export methods to manipulate the TAILQ, in particular:
  116  *
  117  * bioq_insert_tail()   insert an entry at the end.
  118  *              It also creates a 'barrier' so all subsequent
  119  *              insertions through bioq_disksort() will end up
  120  *              after this entry;
  121  *
  122  * bioq_insert_head()   insert an entry at the head, update
  123  *              bioq->last_offset = bio->bio_offset so that
  124  *              all subsequent insertions through bioq_disksort()
  125  *              will end up after this entry;
  126  *
  127  * bioq_remove()        remove a generic element from the queue, act as
  128  *              bioq_takefirst() if invoked on the head of the queue.
  129  *
  130  * The semantic of these methods is the same as the operations
  131  * on the underlying TAILQ, but with additional guarantees on
  132  * subsequent bioq_disksort() calls. E.g. bioq_insert_tail()
  133  * can be useful for making sure that all previous ops are flushed
  134  * to disk before continuing.
  135  *
  136  * Updating bioq->last_offset on a bioq_insert_head() guarantees
  137  * that the bio inserted with the last bioq_insert_head() will stay
  138  * at the head of the queue even after subsequent bioq_disksort().
  139  *
  140  * Note that when the direct queue manipulation functions are used,
  141  * the queue may contain multiple inversion points (i.e. more than
  142  * two sorted sequences of requests).
  143  *
  144  */
  145 
  146 void
  147 bioq_init(struct bio_queue_head *head)
  148 {
  149 
  150         TAILQ_INIT(&head->queue);
  151         head->last_offset = 0;
  152         head->insert_point = NULL;
  153 }
  154 
  155 void
  156 bioq_remove(struct bio_queue_head *head, struct bio *bp)
  157 {
  158 
  159         if (head->insert_point == NULL) {
  160                 if (bp == TAILQ_FIRST(&head->queue))
  161                         head->last_offset = bp->bio_offset + bp->bio_length;
  162         } else if (bp == head->insert_point)
  163                 head->insert_point = NULL;
  164 
  165         TAILQ_REMOVE(&head->queue, bp, bio_queue);
  166 }
  167 
  168 void
  169 bioq_flush(struct bio_queue_head *head, struct devstat *stp, int error)
  170 {
  171         struct bio *bp;
  172 
  173         while ((bp = bioq_takefirst(head)) != NULL)
  174                 biofinish(bp, stp, error);
  175 }
  176 
  177 void
  178 bioq_insert_head(struct bio_queue_head *head, struct bio *bp)
  179 {
  180 
  181         if (head->insert_point == NULL)
  182                 head->last_offset = bp->bio_offset;
  183         TAILQ_INSERT_HEAD(&head->queue, bp, bio_queue);
  184 }
  185 
  186 void
  187 bioq_insert_tail(struct bio_queue_head *head, struct bio *bp)
  188 {
  189 
  190         TAILQ_INSERT_TAIL(&head->queue, bp, bio_queue);
  191         head->insert_point = bp;
  192         head->last_offset = bp->bio_offset;
  193 }
  194 
  195 struct bio *
  196 bioq_first(struct bio_queue_head *head)
  197 {
  198 
  199         return (TAILQ_FIRST(&head->queue));
  200 }
  201 
  202 struct bio *
  203 bioq_takefirst(struct bio_queue_head *head)
  204 {
  205         struct bio *bp;
  206 
  207         bp = TAILQ_FIRST(&head->queue);
  208         if (bp != NULL)
  209                 bioq_remove(head, bp);
  210         return (bp);
  211 }
  212 
  213 /*
  214  * Compute the sorting key. The cast to unsigned is
  215  * fundamental for correctness, see the description
  216  * near the beginning of the file.
  217  */
  218 static inline uoff_t
  219 bioq_bio_key(struct bio_queue_head *head, struct bio *bp)
  220 {
  221 
  222         return ((uoff_t)(bp->bio_offset - head->last_offset));
  223 }
  224 
  225 /*
  226  * Seek sort for disks.
  227  *
  228  * Sort all requests in a single queue while keeping
  229  * track of the current position of the disk with last_offset.
  230  * See above for details.
  231  */
  232 void
  233 bioq_disksort(struct bio_queue_head *head, struct bio *bp)
  234 {
  235         struct bio *cur, *prev;
  236         uoff_t key;
  237 
  238         if ((bp->bio_flags & BIO_ORDERED) != 0) {
  239                 /*
  240                  * Ordered transactions can only be dispatched
  241                  * after any currently queued transactions.  They
  242                  * also have barrier semantics - no transactions
  243                  * queued in the future can pass them.
  244                  */
  245                 bioq_insert_tail(head, bp);
  246                 return;
  247         }
  248 
  249         prev = NULL;
  250         key = bioq_bio_key(head, bp);
  251         cur = TAILQ_FIRST(&head->queue);
  252 
  253         if (head->insert_point) {
  254                 prev = head->insert_point;
  255                 cur = TAILQ_NEXT(head->insert_point, bio_queue);
  256         }
  257 
  258         while (cur != NULL && key >= bioq_bio_key(head, cur)) {
  259                 prev = cur;
  260                 cur = TAILQ_NEXT(cur, bio_queue);
  261         }
  262 
  263         if (prev == NULL)
  264                 TAILQ_INSERT_HEAD(&head->queue, bp, bio_queue);
  265         else
  266                 TAILQ_INSERT_AFTER(&head->queue, prev, bp, bio_queue);
  267 }

Cache object: 43f96eb075df03954abc51a1bbdd13b4


[ 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.