xref: /freebsd/sys/kern/subr_disk.c (revision 4c8945a06b01a5c8122cdeb402af36bb46a06acc)
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 as 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 (head->insert_point == NULL) {
160 		if (bp == TAILQ_FIRST(&head->queue))
161 			head->last_offset = bp->bio_offset + bp->bio_length;
162 	} else 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 	if (head->insert_point == NULL)
182 		head->last_offset = bp->bio_offset;
183 	TAILQ_INSERT_HEAD(&head->queue, bp, bio_queue);
184 }
185 
186 void
187 bioq_insert_tail(struct bio_queue_head *head, struct bio *bp)
188 {
189 
190 	TAILQ_INSERT_TAIL(&head->queue, bp, bio_queue);
191 	head->insert_point = bp;
192 	head->last_offset = bp->bio_offset;
193 }
194 
195 struct bio *
196 bioq_first(struct bio_queue_head *head)
197 {
198 
199 	return (TAILQ_FIRST(&head->queue));
200 }
201 
202 struct bio *
203 bioq_takefirst(struct bio_queue_head *head)
204 {
205 	struct bio *bp;
206 
207 	bp = TAILQ_FIRST(&head->queue);
208 	if (bp != NULL)
209 		bioq_remove(head, bp);
210 	return (bp);
211 }
212 
213 /*
214  * Compute the sorting key. The cast to unsigned is
215  * fundamental for correctness, see the description
216  * near the beginning of the file.
217  */
218 static inline uoff_t
219 bioq_bio_key(struct bio_queue_head *head, struct bio *bp)
220 {
221 
222 	return ((uoff_t)(bp->bio_offset - head->last_offset));
223 }
224 
225 /*
226  * Seek sort for disks.
227  *
228  * Sort all requests in a single queue while keeping
229  * track of the current position of the disk with last_offset.
230  * See above for details.
231  */
232 void
233 bioq_disksort(struct bio_queue_head *head, struct bio *bp)
234 {
235 	struct bio *cur, *prev;
236 	uoff_t key;
237 
238 	if ((bp->bio_flags & BIO_ORDERED) != 0) {
239 		/*
240 		 * Ordered transactions can only be dispatched
241 		 * after any currently queued transactions.  They
242 		 * also have barrier semantics - no transactions
243 		 * queued in the future can pass them.
244 		 */
245 		bioq_insert_tail(head, bp);
246 		return;
247 	}
248 
249 	prev = NULL;
250 	key = bioq_bio_key(head, bp);
251 	cur = TAILQ_FIRST(&head->queue);
252 
253 	if (head->insert_point) {
254 		prev = head->insert_point;
255 		cur = TAILQ_NEXT(head->insert_point, bio_queue);
256 	}
257 
258 	while (cur != NULL && key >= bioq_bio_key(head, cur)) {
259 		prev = cur;
260 		cur = TAILQ_NEXT(cur, bio_queue);
261 	}
262 
263 	if (prev == NULL)
264 		TAILQ_INSERT_HEAD(&head->queue, bp, bio_queue);
265 	else
266 		TAILQ_INSERT_AFTER(&head->queue, prev, bp, bio_queue);
267 }
268