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 void set_coalesced(struct bio_request *into,
11 struct bio_request *from) {
12 into->is_aggregate = true;
13 from->skip = true;
14}
15
16static bool try_do_coalesce(struct block_device *disk, struct bio_request *into,
17 struct bio_request *from) {
18 if (disk->ops->should_coalesce(disk, into, from)) {
19 disk->ops->do_coalesce(disk, into, from);
20 set_coalesced(into, from);
21 return true;
22 }
23 return false;
24}
25
26/* Try to merge candidates in the same queue */
27static bool try_merge_candidates(struct block_device *disk,
28 struct bio_request *iter,
29 struct bio_request *start,
30 struct bio_rqueue *queue) {
31 struct bio_request *candidate = NULL, *tmp;
32 bool merged = false;
33 uint8_t coalesces_left = BIO_SCHED_MAX_COALESCES;
34
35 list_for_each_entry_safe_continue(candidate, tmp, &queue->list, list) {
36 if (candidate == start)
37 break;
38
39 if (candidate->skip || candidate->priority != iter->priority)
40 continue;
41
42 if (try_do_coalesce(disk, into: iter, from: candidate)) {
43 coalesces_left--;
44 merged = true;
45 }
46
47 if (!coalesces_left)
48 break;
49 }
50
51 return merged;
52}
53
54/* Try to coalesce candidate from lower queue with higher queue */
55static bool check_higher_queue(struct bio_scheduler *sched,
56 struct bio_rqueue *higher,
57 struct bio_request *candidate) {
58 struct block_device *disk = sched->disk;
59 struct bio_request *iter, *tmp;
60
61 list_for_each_entry_safe(iter, tmp, &higher->list, list) {
62 if (iter->skip)
63 continue;
64
65 if (try_do_coalesce(disk, into: iter, from: candidate))
66 return true; /* only one coalesce per candidate */
67 }
68
69 return false;
70}
71
72/* Cross-priority coalescing between two adjacent queues */
73static bool coalesce_adjacent_queues(struct block_device *disk,
74 struct bio_rqueue *lower,
75 struct bio_rqueue *higher) {
76 if (list_empty(head: &lower->list) || list_empty(head: &higher->list))
77 return false;
78
79 if (!lower->dirty || !higher->dirty)
80 return false;
81
82 struct bio_scheduler *sched = disk->scheduler;
83 struct bio_request *candidate, *tmp;
84 bool coalesced = false;
85 uint8_t coalesces_left = BIO_SCHED_MAX_COALESCES;
86
87 list_for_each_entry_safe(candidate, tmp, &lower->list, list) {
88 if (candidate->skip)
89 continue;
90
91 if (check_higher_queue(sched, higher, candidate)) {
92 coalesces_left--;
93 coalesced = true;
94 }
95
96 if (!coalesces_left)
97 break;
98 }
99
100 lower->dirty = false;
101 higher->dirty = false;
102 return coalesced;
103}
104
105/* Coalesce requests inside a single priority queue */
106static bool coalesce_priority_queue(struct block_device *disk,
107 struct bio_rqueue *queue) {
108 if (list_empty(head: &queue->list))
109 return false;
110
111 if (!queue->dirty)
112 return false;
113
114 struct bio_request *start =
115 list_first_entry(&queue->list, struct bio_request, list);
116 struct bio_request *rq, *tmp;
117 bool coalesced = false;
118 uint8_t coalesces_left = BIO_SCHED_MAX_COALESCES;
119
120 list_for_each_entry_safe(rq, tmp, &queue->list, list) {
121 if (!rq->skip && try_merge_candidates(disk, iter: rq, start, queue)) {
122 coalesces_left--;
123 coalesced = true;
124 }
125
126 if (!coalesces_left)
127 break;
128 }
129
130 queue->dirty = false;
131 return coalesced;
132}
133
134/* Try to coalesce across all queues and priorities */
135bool bio_sched_try_coalesce(struct bio_scheduler *sched) {
136 struct block_device *disk = sched->disk;
137 if (bdev_skip_coalesce(disk))
138 return false;
139
140 bool coalesced_any = false;
141
142 /* coalesce within each priority queue */
143 for (int prio = 0; prio < BIO_SCHED_LEVELS; prio++) {
144 if (coalesce_priority_queue(disk, queue: &sched->queues[prio]))
145 coalesced_any = true;
146 }
147
148 /* cross-priority coalescing */
149 for (int prio = 0; prio < BIO_SCHED_LEVELS - 1; prio++) {
150 if (coalesce_adjacent_queues(disk, lower: &sched->queues[prio],
151 higher: &sched->queues[prio + 1]))
152 coalesced_any = true;
153 }
154
155 return coalesced_any;
156}
157