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