sys/geom/sched/subr_disk.c

   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$");
  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 }