2 * SPDX-License-Identifier: Beerware
4 * ----------------------------------------------------------------------------
5 * "THE BEER-WARE LICENSE" (Revision 42):
6 * <phk@FreeBSD.ORG> wrote this file. As long as you retain this notice you
7 * can do whatever you want with this stuff. If we meet some day, and you think
8 * this stuff is worth it, you can buy me a beer in return. Poul-Henning Kamp
9 * ----------------------------------------------------------------------------
11 * The bioq_disksort() (and the specification of the bioq API)
12 * have been written by Luigi Rizzo and Fabio Checconi under the same
16 #include <sys/cdefs.h>
17 __FBSDID("$FreeBSD$");
21 #include <sys/param.h>
22 #include <sys/systm.h>
26 #include <geom/geom_disk.h>
29 * Disk error is the preface to plaintive error messages
30 * about failing disk transfers. It prints messages of the form
31 * "hp0g: BLABLABLA cmd=read fsbn 12345 of 12344-12347"
32 * blkdone should be -1 if the position of the error is unknown.
33 * The message is printed with printf.
36 disk_err(struct bio *bp, const char *what, int blkdone, int nl)
40 if (bp->bio_dev != NULL)
41 printf("%s: %s ", devtoname(bp->bio_dev), what);
42 else if (bp->bio_disk != NULL)
44 bp->bio_disk->d_name, bp->bio_disk->d_unit, what);
46 printf("disk??: %s ", what);
48 case BIO_READ: printf("cmd=read "); break;
49 case BIO_WRITE: printf("cmd=write "); break;
50 case BIO_DELETE: printf("cmd=delete "); break;
51 case BIO_GETATTR: printf("cmd=getattr "); break;
52 case BIO_FLUSH: printf("cmd=flush "); break;
53 default: printf("cmd=%x ", bp->bio_cmd); break;
56 if (bp->bio_bcount <= DEV_BSIZE) {
57 printf("fsbn %jd%s", (intmax_t)sn, nl ? "\n" : "");
62 printf("fsbn %jd of ", (intmax_t)sn);
64 printf("%jd-%jd", (intmax_t)bp->bio_pblkno,
65 (intmax_t)(bp->bio_pblkno + (bp->bio_bcount - 1) / DEV_BSIZE));
71 * BIO queue implementation
73 * Please read carefully the description below before making any change
74 * to the code, or you might change the behaviour of the data structure
75 * in undesirable ways.
77 * A bioq stores disk I/O request (bio), normally sorted according to
78 * the distance of the requested position (bio->bio_offset) from the
79 * current head position (bioq->last_offset) in the scan direction, i.e.
81 * (uoff_t)(bio_offset - last_offset)
83 * Note that the cast to unsigned (uoff_t) is fundamental to insure
84 * that the distance is computed in the scan direction.
86 * The main methods for manipulating the bioq are:
88 * bioq_disksort() performs an ordered insertion;
90 * bioq_first() return the head of the queue, without removing;
92 * bioq_takefirst() return and remove the head of the queue,
93 * updating the 'current head position' as
94 * bioq->last_offset = bio->bio_offset + bio->bio_length;
96 * When updating the 'current head position', we assume that the result of
97 * bioq_takefirst() is dispatched to the device, so bioq->last_offset
98 * represents the head position once the request is complete.
100 * If the bioq is manipulated using only the above calls, it starts
101 * with a sorted sequence of requests with bio_offset >= last_offset,
102 * possibly followed by another sorted sequence of requests with
103 * 0 <= bio_offset < bioq->last_offset
105 * NOTE: historical behaviour was to ignore bio->bio_length in the
106 * update, but its use tracks the head position in a better way.
107 * Historical behaviour was also to update the head position when
108 * the request under service is complete, rather than when the
109 * request is extracted from the queue. However, the current API
110 * has no method to update the head position; secondly, once
111 * a request has been submitted to the disk, we have no idea of
112 * the actual head position, so the final one is our best guess.
114 * --- Direct queue manipulation ---
116 * A bioq uses an underlying TAILQ to store requests, so we also
117 * export methods to manipulate the TAILQ, in particular:
119 * bioq_insert_tail() insert an entry at the end.
120 * It also creates a 'barrier' so all subsequent
121 * insertions through bioq_disksort() will end up
124 * bioq_insert_head() insert an entry at the head, update
125 * bioq->last_offset = bio->bio_offset so that
126 * all subsequent insertions through bioq_disksort()
127 * will end up after this entry;
129 * bioq_remove() remove a generic element from the queue, act as
130 * bioq_takefirst() if invoked on the head of the queue.
132 * The semantic of these methods is the same as the operations
133 * on the underlying TAILQ, but with additional guarantees on
134 * subsequent bioq_disksort() calls. E.g. bioq_insert_tail()
135 * can be useful for making sure that all previous ops are flushed
136 * to disk before continuing.
138 * Updating bioq->last_offset on a bioq_insert_head() guarantees
139 * that the bio inserted with the last bioq_insert_head() will stay
140 * at the head of the queue even after subsequent bioq_disksort().
142 * Note that when the direct queue manipulation functions are used,
143 * the queue may contain multiple inversion points (i.e. more than
144 * two sorted sequences of requests).
149 bioq_init(struct bio_queue_head *head)
152 TAILQ_INIT(&head->queue);
153 head->last_offset = 0;
154 head->insert_point = NULL;
158 bioq_remove(struct bio_queue_head *head, struct bio *bp)
161 if (head->insert_point == NULL) {
162 if (bp == TAILQ_FIRST(&head->queue))
163 head->last_offset = bp->bio_offset + bp->bio_length;
164 } else if (bp == head->insert_point)
165 head->insert_point = NULL;
167 TAILQ_REMOVE(&head->queue, bp, bio_queue);
171 bioq_flush(struct bio_queue_head *head, struct devstat *stp, int error)
175 while ((bp = bioq_takefirst(head)) != NULL)
176 biofinish(bp, stp, error);
180 bioq_insert_head(struct bio_queue_head *head, struct bio *bp)
183 if (head->insert_point == NULL)
184 head->last_offset = bp->bio_offset;
185 TAILQ_INSERT_HEAD(&head->queue, bp, bio_queue);
189 bioq_insert_tail(struct bio_queue_head *head, struct bio *bp)
192 TAILQ_INSERT_TAIL(&head->queue, bp, bio_queue);
193 head->insert_point = bp;
194 head->last_offset = bp->bio_offset;
198 bioq_first(struct bio_queue_head *head)
201 return (TAILQ_FIRST(&head->queue));
205 bioq_takefirst(struct bio_queue_head *head)
209 bp = TAILQ_FIRST(&head->queue);
211 bioq_remove(head, bp);
216 * Compute the sorting key. The cast to unsigned is
217 * fundamental for correctness, see the description
218 * near the beginning of the file.
221 bioq_bio_key(struct bio_queue_head *head, struct bio *bp)
224 return ((uoff_t)(bp->bio_offset - head->last_offset));
228 * Seek sort for disks.
230 * Sort all requests in a single queue while keeping
231 * track of the current position of the disk with last_offset.
232 * See above for details.
235 bioq_disksort(struct bio_queue_head *head, struct bio *bp)
237 struct bio *cur, *prev;
240 if ((bp->bio_flags & BIO_ORDERED) != 0) {
242 * Ordered transactions can only be dispatched
243 * after any currently queued transactions. They
244 * also have barrier semantics - no transactions
245 * queued in the future can pass them.
247 bioq_insert_tail(head, bp);
252 key = bioq_bio_key(head, bp);
253 cur = TAILQ_FIRST(&head->queue);
255 if (head->insert_point) {
256 prev = head->insert_point;
257 cur = TAILQ_NEXT(head->insert_point, bio_queue);
260 while (cur != NULL && key >= bioq_bio_key(head, cur)) {
262 cur = TAILQ_NEXT(cur, bio_queue);
266 TAILQ_INSERT_HEAD(&head->queue, bp, bio_queue);
268 TAILQ_INSERT_AFTER(&head->queue, prev, bp, bio_queue);