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 105void 106gs_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 114void 115gs_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 127void 128gs_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 136void 137gs_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 145void 146gs_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 154struct bio * 155gs_bioq_first(struct bio_queue_head *head) 156{ 157 158 return (TAILQ_FIRST(&head->queue)); 159} 160 161struct bio * 162gs_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 */ 177static inline uoff_t 178gs_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 */ 191void 192gs_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} 227