1#include <block/block.h>
2#include <block/sched.h>
3#include <console/printf.h>
4#include <math/min_max.h>
5#include <mem/alloc.h>
6#include <stdint.h>
7#include <sync/spinlock.h>
8#include <thread/workqueue.h>
9#include <time/time.h>
10
11static inline uint64_t get_boost_depth(struct bio_request *req) {
12 if (req->boost_count >= 3)
13 return 2;
14 else if (req->boost_count >= 1)
15 return 1;
16
17 return 0;
18}
19
20static inline uint64_t get_boosted_prio(struct bio_request *req) {
21 uint64_t step = get_boost_depth(req);
22 uint64_t prio = req->priority + BIO_SCHED_STARVATION_BOOST + step;
23 uint64_t max_prio = BIO_SCHED_MAX;
24 return MIN(prio, max_prio);
25}
26
27static bool should_boost(struct bio_request *req) {
28 uint64_t curr_timestamp = time_get_ms();
29
30 enforce(req->disk);
31
32 struct bio_scheduler_ops *ops = req->disk->ops;
33 uint64_t base_wait = ops->max_wait_time[req->priority];
34
35 /* reduce wait time threshold by 2^boost_count, with a max shift cap */
36 uint64_t shift = req->boost_count > BIO_SCHED_BOOST_SHIFT_LIMIT
37 ? BIO_SCHED_BOOST_SHIFT_LIMIT
38 : req->boost_count;
39
40 uint64_t adjusted_wait = base_wait >> shift;
41
42 if (adjusted_wait < ops->min_wait_ms)
43 adjusted_wait = ops->min_wait_ms;
44
45 return curr_timestamp > (req->enqueue_time + adjusted_wait);
46}
47
48static bool do_boost_prio(struct bio_scheduler *sched, struct bio_request *req)
49 TSA_CALLER_HOLDS(&sched->lock) {
50 enum bio_request_priority new_prio = get_boosted_prio(req);
51
52 struct bio_scheduler_ops *ops = sched->disk->ops;
53
54 if (req->priority == new_prio)
55 return false;
56
57 uint64_t target_request_count = sched->queues[new_prio].request_count;
58 uint64_t target_occupance_limit = ops->boost_occupance_limit[new_prio];
59
60 /* update the timestamp so we don't try to
61 * boost this request again for a while */
62 if (target_request_count > target_occupance_limit) {
63 update_request_timestamp(req);
64 return false;
65 }
66
67 bio_sched_dequeue_internal(sched, req);
68 req->priority = new_prio;
69 req->boost_count++;
70
71 /* re-insert to new level */
72 bio_sched_enqueue_internal(sched, req);
73 return true;
74}
75
76static inline bool try_boost(struct bio_scheduler *sched,
77 struct bio_request *req)
78 TSA_CALLER_HOLDS(&sched->lock) {
79 if (should_boost(req))
80 return do_boost_prio(sched, req);
81
82 return false;
83}
84
85/* this will be called with the lock already acquired */
86bool bio_sched_boost_starved(struct bio_scheduler *sched) {
87 MUTEX_ASSERT_HELD(&sched->lock);
88 bool boosted_any = false;
89
90 for (int64_t i = BIO_RQ_HIGH; i >= 0; i--) {
91 struct bio_rqueue *queue = &sched->queues[i];
92
93 uint64_t checks_left = queue->request_count;
94
95 if (checks_left > BIO_SCHED_MAX_BOOST_SCAN)
96 checks_left = BIO_SCHED_MAX_BOOST_SCAN;
97
98 struct list_node *iter, *temp;
99
100 list_for_each_safe(iter, temp, &queue->list) {
101 struct bio_request *rq = bio_request_from_list_node(iter);
102 if (!rq->skip && try_boost(sched, req: rq)) {
103 boosted_any = true;
104 goto next_level;
105 }
106
107 if (--checks_left == 0)
108 goto next_level;
109 }
110
111 next_level:
112 continue;
113 }
114
115 return boosted_any;
116}
117