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