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