1/* @title: I/O Request Scheduling */
2#pragma once
3#include <atomic.h>
4#include <block/bcache.h>
5#include <block/bio.h>
6#include <block/block.h>
7#include <fs/detect.h>
8#include <sch/sched.h>
9#include <stdbool.h>
10#include <stdint.h>
11#include <sync/mutex.h>
12#include <thread/workqueue.h>
13#include <tsa.h>
14
15/*
16 * This is the asynchronous block device
17 * IO request scheduler, referred to as the
18 * "bio scheduler", or "bio sched".
19 *
20 * ===================== Overview =======================
21 *
22 * The bio scheduler is a generic block IO scheduler that
23 * block devices are expected to implement device-specific
24 * policies to allow the scheduler to perform optimizations.
25 *
26 * The two main device-specific optimizations are coalescing and reordering.
27 *
28 * Coalescing allows two requests to get merged into one,
29 * and reordering simply changes the order in which
30 * requests are dispatched, allowing for some block devices
31 * to operate more efficiently.
32 *
33 * When coalescing succeeds, the request with the lower LBA is marked
34 * as `is_aggregate`, and the one with the higher LBA is marked `skip`.
35 *
36 * ===================== Queue Structure =======================
37 *
38 * The scheduler uses a 5-level MLFQ to keep track of requests.
39 * Each level is a different request priority level.
40 *
41 * The head of each MLFQ is always the first request in the queue
42 * to get dispatched, and the head->next is the next, and so on.
43 *
44 * The highest priority requests (BIO_RQ_URGENT) entirely skip
45 * the queue and are immediately dispatched, giving them no
46 * time to get coalesced or reordered.
47 *
48 * ===================== Request Boosting =======================
49 *
50 * Over time, requests are boosted according to device specific
51 * policies. All of the device specific policies are contained
52 * in a per-device `struct bio_scheduler_ops`.
53 *
54 * Boosts prevent request starvation, as sometimes,
55 * requests may not get manually dispatched, and thus
56 * spend lots of time in the queue without getting executed.
57 *
58 * All timestamps for requests are stored in milliseconds, and are taken
59 * from the current time during the enqueue.
60 *
61 * The FIRST boost will occur when a request has spent enough
62 * time (`ops->max_wait_time[queue_level]`) in the queue.
63 *
64 * This is determined via the following for the FIRST boost:
65 *
66 * int base_wait = ops->max_wait_time[queue_level];
67 * bool should_boost = current_time > (enqueue_time + base_wait);
68 *
69 * After the first boost, however, the following
70 * boosts become accelerated to prevent large batches
71 * of initially low-priority requests from taking up space
72 * in higher priority queues.
73 *
74 * This adjusted timestamp is computed by simply
75 * taking the amount of boosts a request has had,
76 * and performing the following operation:
77 *
78 * int adjusted_wait = base_wait >> req->boost_count;
79 *
80 * Where the shift can be limited by changing BIO_SCHED_BOOST_SHIFT_LIMIT.
81 *
82 * In addition to this, the levels that the request is boosted by also changes.
83 * The first request will always boost the request by one priority level, but
84 * following boosts will be different.
85 *
86 * The new priority is computed with the following operation:
87 *
88 * int get_boost_depth(int boost_count) {
89 * if (boost_count >= 3)
90 * return 2;
91 * else if (boost_count >= 1)
92 * return 1;
93 *
94 * return 0;
95 * }
96 *
97 * int step = get_boost_depth(req->boost_count);
98 * int new_prio = req->prio + 1 + step; // '1' is the initial boost
99 *
100 * Where `new_prio` is limited to the BIO_SCHED_MAX priority level.
101 *
102 * Request starvation is automatically checked every `ops->tick_ms`
103 * milliseconds.
104 */
105
106/* how many queue levels the bio_scheduler has */
107#define BIO_SCHED_LEVELS 5
108#define BIO_SCHED_MAX (BIO_SCHED_LEVELS - 1)
109
110/* first boosts can only boost priority by this much */
111#define BIO_SCHED_STARVATION_BOOST 1
112
113/* max of 2^4 threshold reduction */
114#define BIO_SCHED_BOOST_SHIFT_LIMIT 4
115
116/* max to scan before bail */
117#define BIO_SCHED_COALESCE_SCAN_LIMIT 8
118
119#define BIO_SCHED_MAX_BOOST_SCAN 32
120
121/* max coalesces in one enqueue() */
122#define BIO_SCHED_MAX_COALESCES 4
123
124struct bio_rqueue {
125 struct list_head list;
126
127 uint64_t request_count;
128
129 /* coalescing */
130 bool dirty;
131};
132
133struct bio_scheduler {
134 struct block_device *disk;
135 struct mutex lock;
136 uint64_t total_requests;
137 struct bio_rqueue queues[BIO_SCHED_LEVELS];
138 struct delayed_work tick_work;
139 bool defer_pending;
140};
141
142struct bio_scheduler_ops {
143 bool (*should_coalesce)(struct block_device *dev,
144 const struct bio_request *a,
145 const struct bio_request *b);
146
147 void (*do_coalesce)(struct block_device *dev, struct bio_request *into,
148 struct bio_request *from);
149
150 void (*reorder)(struct block_device *dev);
151
152 /* maximum request wait time for each queue level before first boost */
153 uint32_t max_wait_time[BIO_SCHED_LEVELS];
154
155 /* maximum requests in all queues before high priority
156 * requests start getting auto-dispatched */
157 uint32_t dispatch_threshold;
158
159 /* maximum number of requests in a target queue to allow
160 * a boosted request to boost to that level */
161 uint64_t boost_occupance_limit[BIO_SCHED_LEVELS];
162
163 /* amount of time to wait between starvation
164 * checks to boost starving requests */
165 uint64_t tick_ms;
166
167 /* absolute minimum amount of time waited for
168 * any request to get boosted
169 *
170 * used for requests that have been starving
171 * for a long time to prevent them from
172 * immediately boosting at the first
173 * possible opportunity */
174 uint64_t min_wait_ms;
175};
176
177bool noop_should_coalesce(struct block_device *disk,
178 const struct bio_request *a,
179 const struct bio_request *b);
180
181void noop_do_coalesce(struct block_device *disk, struct bio_request *into,
182 struct bio_request *from);
183
184void noop_reorder(struct block_device *disk);
185
186void bio_sched_enqueue(struct block_device *disk, struct bio_request *req);
187
188void bio_sched_dequeue(struct block_device *disk, struct bio_request *req);
189
190void bio_sched_enqueue_internal(struct bio_scheduler *sched,
191 struct bio_request *req)
192 TSA_CALLER_HOLDS(&sched->lock);
193void bio_sched_dequeue_internal(struct bio_scheduler *sched,
194 struct bio_request *req)
195 TSA_CALLER_HOLDS(&sched->lock);
196
197void bio_sched_dispatch_partial(struct block_device *disk,
198 enum bio_request_priority prio);
199
200void bio_sched_dispatch_all(struct block_device *disk);
201
202void bio_sched_try_early_dispatch(struct bio_scheduler *sched)
203 TSA_CALLER_HOLDS(&sched->lock);
204
205bool bio_sched_try_coalesce(struct bio_scheduler *sched)
206 TSA_CALLER_HOLDS(&sched->lock);
207bool bio_sched_boost_starved(struct bio_scheduler *sched)
208 TSA_CALLER_HOLDS(&sched->lock);
209
210struct bio_scheduler *bio_sched_create(struct block_device *disk,
211 struct bio_scheduler_ops *ops);
212
213static inline void update_request_timestamp(struct bio_request *req) {
214 req->enqueue_time = time_get_ms();
215}
216
217static inline bool submit_if_urgent(struct bio_scheduler *sched,
218 struct bio_request *req) {
219 if (req->priority == BIO_RQ_URGENT) {
220 /* VIP request - skip the queue ! */
221 sched->disk->submit_bio_async(sched->disk, req);
222 return true;
223 }
224 return false;
225}
226
227static inline bool sched_is_empty(struct bio_scheduler *sched) {
228 for (uint32_t i = 0; i < BIO_SCHED_LEVELS; i++)
229 if (!list_head_empty(h: &sched->queues[i].list))
230 return false;
231
232 return true;
233}
234
235static inline bool submit_if_skip_sched(struct bio_scheduler *sched,
236 struct bio_request *req) {
237 if (bdev_skip_sched(disk: sched->disk)) {
238 sched->disk->submit_bio_async(sched->disk, req);
239 return true;
240 }
241 return false;
242}
243