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/geom/sched/subr_disk.c

Version: -  FREEBSD  -  FREEBSD-13-STABLE  -  FREEBSD-13-0  -  FREEBSD-12-STABLE  -  FREEBSD-12-0  -  FREEBSD-11-STABLE  -  FREEBSD-11-0  -  FREEBSD-10-STABLE  -  FREEBSD-10-0  -  FREEBSD-9-STABLE  -  FREEBSD-9-0  -  FREEBSD-8-STABLE  -  FREEBSD-8-0  -  FREEBSD-7-STABLE  -  FREEBSD-7-0  -  FREEBSD-6-STABLE  -  FREEBSD-6-0  -  FREEBSD-5-STABLE  -  FREEBSD-5-0  -  FREEBSD-4-STABLE  -  FREEBSD-3-STABLE  -  FREEBSD22  -  l41  -  OPENBSD  -  linux-2.6  -  MK84  -  PLAN9  -  xnu-8792 
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/8.3/sys/geom/sched/subr_disk.c 212939 2010-09-20 23:39:00Z 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 #include "g_sched.h"
   26 
   27 /*
   28  * BIO queue implementation
   29  *
   30  * Please read carefully the description below before making any change
   31  * to the code, or you might change the behaviour of the data structure
   32  * in undesirable ways.
   33  *
   34  * A bioq stores disk I/O request (bio), normally sorted according to
   35  * the distance of the requested position (bio->bio_offset) from the
   36  * current head position (bioq->last_offset) in the scan direction, i.e.
   37  *
   38  *      (uoff_t)(bio_offset - last_offset)
   39  *
   40  * Note that the cast to unsigned (uoff_t) is fundamental to insure
   41  * that the distance is computed in the scan direction.
   42  *
   43  * The main methods for manipulating the bioq are:
   44  *
   45  *   bioq_disksort()    performs an ordered insertion;
   46  *
   47  *   bioq_first()       return the head of the queue, without removing;
   48  *
   49  *   bioq_takefirst()   return and remove the head of the queue,
   50  *              updating the 'current head position' as
   51  *              bioq->last_offset = bio->bio_offset + bio->bio_length;
   52  *
   53  * When updating the 'current head position', we assume that the result of
   54  * bioq_takefirst() is dispatched to the device, so bioq->last_offset
   55  * represents the head position once the request is complete.
   56  *
   57  * If the bioq is manipulated using only the above calls, it starts
   58  * with a sorted sequence of requests with bio_offset >= last_offset,
   59  * possibly followed by another sorted sequence of requests with
   60  * 0 <= bio_offset < bioq->last_offset 
   61  *
   62  * NOTE: historical behaviour was to ignore bio->bio_length in the
   63  *      update, but its use tracks the head position in a better way.
   64  *      Historical behaviour was also to update the head position when
   65  *      the request under service is complete, rather than when the
   66  *      request is extracted from the queue. However, the current API
   67  *      has no method to update the head position; secondly, once
   68  *      a request has been submitted to the disk, we have no idea of
   69  *      the actual head position, so the final one is our best guess.
   70  *
   71  * --- Direct queue manipulation ---
   72  *
   73  * A bioq uses an underlying TAILQ to store requests, so we also
   74  * export methods to manipulate the TAILQ, in particular:
   75  *
   76  * bioq_insert_tail()   insert an entry at the end.
   77  *              It also creates a 'barrier' so all subsequent
   78  *              insertions through bioq_disksort() will end up
   79  *              after this entry;
   80  *
   81  * bioq_insert_head()   insert an entry at the head, update
   82  *              bioq->last_offset = bio->bio_offset so that
   83  *              all subsequent insertions through bioq_disksort()
   84  *              will end up after this entry;
   85  *
   86  * bioq_remove()        remove a generic element from the queue, act as
   87  *              bioq_takefirst() if invoked on the head of the queue.
   88  *
   89  * The semantic of these methods is the same as the operations
   90  * on the underlying TAILQ, but with additional guarantees on
   91  * subsequent bioq_disksort() calls. E.g. bioq_insert_tail()
   92  * can be useful for making sure that all previous ops are flushed
   93  * to disk before continuing.
   94  *
   95  * Updating bioq->last_offset on a bioq_insert_head() guarantees
   96  * that the bio inserted with the last bioq_insert_head() will stay
   97  * at the head of the queue even after subsequent bioq_disksort().
   98  *
   99  * Note that when the direct queue manipulation functions are used,
  100  * the queue may contain multiple inversion points (i.e. more than
  101  * two sorted sequences of requests).
  102  *
  103  */
  104 
  105 void
  106 gs_bioq_init(struct bio_queue_head *head)
  107 {
  108 
  109         TAILQ_INIT(&head->queue);
  110         head->last_offset = 0;
  111         head->insert_point = NULL;
  112 }
  113 
  114 void
  115 gs_bioq_remove(struct bio_queue_head *head, struct bio *bp)
  116 {
  117 
  118         if (head->insert_point == NULL) {
  119                 if (bp == TAILQ_FIRST(&head->queue))
  120                         head->last_offset = bp->bio_offset + bp->bio_length;
  121         } else if (bp == head->insert_point)
  122                 head->insert_point = NULL;
  123 
  124         TAILQ_REMOVE(&head->queue, bp, bio_queue);
  125 }
  126 
  127 void
  128 gs_bioq_flush(struct bio_queue_head *head, struct devstat *stp, int error)
  129 {
  130         struct bio *bp;
  131 
  132         while ((bp = gs_bioq_takefirst(head)) != NULL)
  133                 biofinish(bp, stp, error);
  134 }
  135 
  136 void
  137 gs_bioq_insert_head(struct bio_queue_head *head, struct bio *bp)
  138 {
  139 
  140         if (head->insert_point == NULL)
  141                 head->last_offset = bp->bio_offset;
  142         TAILQ_INSERT_HEAD(&head->queue, bp, bio_queue);
  143 }
  144 
  145 void
  146 gs_bioq_insert_tail(struct bio_queue_head *head, struct bio *bp)
  147 {
  148 
  149         TAILQ_INSERT_TAIL(&head->queue, bp, bio_queue);
  150         head->insert_point = bp;
  151         head->last_offset = bp->bio_offset;
  152 }
  153 
  154 struct bio *
  155 gs_bioq_first(struct bio_queue_head *head)
  156 {
  157 
  158         return (TAILQ_FIRST(&head->queue));
  159 }
  160 
  161 struct bio *
  162 gs_bioq_takefirst(struct bio_queue_head *head)
  163 {
  164         struct bio *bp;
  165 
  166         bp = TAILQ_FIRST(&head->queue);
  167         if (bp != NULL)
  168                 gs_bioq_remove(head, bp);
  169         return (bp);
  170 }
  171 
  172 /*
  173  * Compute the sorting key. The cast to unsigned is
  174  * fundamental for correctness, see the description
  175  * near the beginning of the file.
  176  */
  177 static inline uoff_t
  178 gs_bioq_bio_key(struct bio_queue_head *head, struct bio *bp)
  179 {
  180 
  181         return ((uoff_t)(bp->bio_offset - head->last_offset));
  182 }
  183 
  184 /*
  185  * Seek sort for disks.
  186  *
  187  * Sort all requests in a single queue while keeping
  188  * track of the current position of the disk with last_offset.
  189  * See above for details.
  190  */
  191 void
  192 gs_bioq_disksort(struct bio_queue_head *head, struct bio *bp)
  193 {
  194         struct bio *cur, *prev;
  195         uoff_t key;
  196 
  197         if ((bp->bio_flags & BIO_ORDERED) != 0) {
  198                 /*
  199                  * Ordered transactions can only be dispatched
  200                  * after any currently queued transactions.  They
  201                  * also have barrier semantics - no transactions
  202                  * queued in the future can pass them.
  203                  */
  204                 gs_bioq_insert_tail(head, bp);
  205                 return;
  206         }
  207 
  208         prev = NULL;
  209         key = gs_bioq_bio_key(head, bp);
  210         cur = TAILQ_FIRST(&head->queue);
  211 
  212         if (head->insert_point) {
  213                 prev = head->insert_point;
  214                 cur = TAILQ_NEXT(head->insert_point, bio_queue);
  215         }
  216 
  217         while (cur != NULL && key >= gs_bioq_bio_key(head, cur)) {
  218                 prev = cur;
  219                 cur = TAILQ_NEXT(cur, bio_queue);
  220         }
  221 
  222         if (prev == NULL)
  223                 TAILQ_INSERT_HEAD(&head->queue, bp, bio_queue);
  224         else
  225                 TAILQ_INSERT_AFTER(&head->queue, prev, bp, bio_queue);
  226 }

Cache object: 21e5b735a2bcaf4fbbcf6d7782a1df2a


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