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 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 of 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 (bp == TAILQ_FIRST(&head->queue)) 160 head->last_offset = bp->bio_offset + bp->bio_length; 161 162 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 head->last_offset = bp->bio_offset; 182 TAILQ_INSERT_HEAD(&head->queue, bp, bio_queue); 183 } 184 185 void 186 bioq_insert_tail(struct bio_queue_head *head, struct bio *bp) 187 { 188 189 TAILQ_INSERT_TAIL(&head->queue, bp, bio_queue); 190 head->insert_point = bp; 191 } 192 193 struct bio * 194 bioq_first(struct bio_queue_head *head) 195 { 196 197 return (TAILQ_FIRST(&head->queue)); 198 } 199 200 struct bio * 201 bioq_takefirst(struct bio_queue_head *head) 202 { 203 struct bio *bp; 204 205 bp = TAILQ_FIRST(&head->queue); 206 if (bp != NULL) 207 bioq_remove(head, bp); 208 return (bp); 209 } 210 211 /* 212 * Compute the sorting key. The cast to unsigned is 213 * fundamental for correctness, see the description 214 * near the beginning of the file. 215 */ 216 static inline uoff_t 217 bioq_bio_key(struct bio_queue_head *head, struct bio *bp) 218 { 219 220 return ((uoff_t)(bp->bio_offset - head->last_offset)); 221 } 222 223 /* 224 * Seek sort for disks. 225 * 226 * Sort all requests in a single queue while keeping 227 * track of the current position of the disk with last_offset. 228 * See above for details. 229 */ 230 void 231 bioq_disksort(struct bio_queue_head *head, struct bio *bp) 232 { 233 struct bio *cur, *prev = NULL; 234 uoff_t key = bioq_bio_key(head, bp); 235 236 cur = TAILQ_FIRST(&head->queue); 237 238 if (head->insert_point) 239 cur = head->insert_point; 240 241 while (cur != NULL && key >= bioq_bio_key(head, cur)) { 242 prev = cur; 243 cur = TAILQ_NEXT(cur, bio_queue); 244 } 245 246 if (prev == NULL) 247 TAILQ_INSERT_HEAD(&head->queue, bp, bio_queue); 248 else 249 TAILQ_INSERT_AFTER(&head->queue, prev, bp, bio_queue); 250 } 251