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 of 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 (bp == TAILQ_FIRST(&head->queue))
 119                 head->last_offset = bp->bio_offset + bp->bio_length;
 120
 121         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         head->last_offset = bp->bio_offset;
 141         TAILQ_INSERT_HEAD(&head->queue, bp, bio_queue);
 142 }
 143
 144 void
 145 gs_bioq_insert_tail(struct bio_queue_head *head, struct bio *bp)
 146 {
 147
 148         TAILQ_INSERT_TAIL(&head->queue, bp, bio_queue);
 149         head->insert_point = bp;
 150 }
 151
 152 struct bio *
 153 gs_bioq_first(struct bio_queue_head *head)
 154 {
 155
 156         return (TAILQ_FIRST(&head->queue));
 157 }
 158
 159 struct bio *
 160 gs_bioq_takefirst(struct bio_queue_head *head)
 161 {
 162         struct bio *bp;
 163
 164         bp = TAILQ_FIRST(&head->queue);
 165         if (bp != NULL)
 166                 gs_bioq_remove(head, bp);
 167         return (bp);
 168 }
 169
 170 /*
 171  * Compute the sorting key. The cast to unsigned is
 172  * fundamental for correctness, see the description
 173  * near the beginning of the file.
 174  */
 175 static inline uoff_t
 176 gs_bioq_bio_key(struct bio_queue_head *head, struct bio *bp)
 177 {
 178
 179         return ((uoff_t)(bp->bio_offset - head->last_offset));
 180 }
 181
 182 /*
 183  * Seek sort for disks.
 184  *
 185  * Sort all requests in a single queue while keeping
 186  * track of the current position of the disk with last_offset.
 187  * See above for details.
 188  */
 189 void
 190 gs_bioq_disksort(struct bio_queue_head *head, struct bio *bp)
 191 {
 192         struct bio *cur, *prev = NULL;
 193         uoff_t key = gs_bioq_bio_key(head, bp);
 194
 195         cur = TAILQ_FIRST(&head->queue);
 196
 197         if (head->insert_point)
 198                 cur = head->insert_point;
 199
 200         while (cur != NULL && key >= gs_bioq_bio_key(head, cur)) {
 201                 prev = cur;
 202                 cur = TAILQ_NEXT(cur, bio_queue);
 203         }
 204
 205         if (prev == NULL)
 206                 TAILQ_INSERT_HEAD(&head->queue, bp, bio_queue);
 207         else
 208                 TAILQ_INSERT_AFTER(&head->queue, prev, bp, bio_queue);
 209 }