1 #include "common/completion.h"
2 #include "common/kthread.h"
3
4 /**
5 * @brief 初始化一个completion变量
6 *
7 * @param x completion
8 */
completion_init(struct completion * x)9 void completion_init(struct completion *x)
10 {
11 x->done = 0;
12 wait_queue_head_init(&x->wait_queue);
13 }
14
15 /**
16 * @brief 唤醒一个wait_queue中的节点
17 *
18 * @param x completion
19 */
complete(struct completion * x)20 void complete(struct completion *x)
21 {
22
23 spin_lock(&x->wait_queue.lock);
24
25 if (x->done != COMPLETE_ALL)
26 ++(x->done);
27 wait_queue_wakeup_on_stack(&x->wait_queue, -1UL); // -1UL代表所有节点都满足条件,暂时这么写
28
29 spin_unlock(&x->wait_queue.lock);
30 }
31
32 /**
33 * @brief 永久标记done为Complete_All, 并从wait_queue中删除所有节点
34 *
35 * @param x completion
36 */
complete_all(struct completion * x)37 void complete_all(struct completion *x)
38 {
39 spin_lock(&x->wait_queue.lock);
40
41 x->done = COMPLETE_ALL; // 永久赋值
42 while (!list_empty(&x->wait_queue.wait_list))
43 wait_queue_wakeup_on_stack(&x->wait_queue, -1UL); // -1UL代表所有节点都满足条件,暂时这么写
44
45 spin_unlock(&x->wait_queue.lock);
46 }
47
48 /**
49 * @brief 辅助函数：通用的处理wait命令的函数(即所有wait_for_completion函数最核心部分在这里)
50 *
51 * @param x completion
52 * @param action 函数指针
53 * @param timeout 一个非负整数
54 * @param state 你要设置进程的状态为state
55 * @return long - 返回剩余的timeout
56 */
__wait_for_common(struct completion * x,long (* action)(long),long timeout,int state)57 static long __wait_for_common(struct completion *x, long (*action)(long), long timeout, int state)
58 {
59 if (!x->done)
60 {
61 DECLARE_WAIT_ON_STACK_SELF(wait);
62
63 while (!x->done && timeout > 0)
64 {
65 // 加入等待队列, 但是不会调度走
66 if (list_empty(&wait.wait_list))
67 list_append(&x->wait_queue.wait_list, &wait.wait_list);
68 wait.pcb->state = state; // 清除运行位, 并设置为interuptible/uninteruptible
69
70 spin_unlock(&x->wait_queue.lock);
71
72 timeout = action(timeout);
73 spin_lock(&x->wait_queue.lock);
74 }
75 if (!x->done)
76 return timeout; // 仍然没有complete, 但是被其他进程唤醒
77
78 wait.pcb->state = PROC_RUNNING; // 设置为运行, 并清空state， 所以使用等号赋值
79 if (!list_empty(&wait.wait_list))
80 list_del_init(&wait.wait_list); // 必须使用del_init
81 }
82 if (x->done != COMPLETE_ALL)
83 --(x->done);
84 return timeout ? timeout : 1; // 这里linux返回1，不知道为啥
85 }
86
87 /**
88 * @brief 等待completion命令唤醒进程, 同时设置pcb->state为uninteruptible.
89 *
90 * @param x completion
91 */
wait_for_completion(struct completion * x)92 void wait_for_completion(struct completion *x)
93 {
94 spin_lock(&x->wait_queue.lock);
95 __wait_for_common(x, &schedule_timeout_ms, MAX_TIMEOUT, PROC_UNINTERRUPTIBLE);
96 spin_unlock(&x->wait_queue.lock);
97 }
98
99 /**
100 * @brief 等待指定时间，超时后就返回, 同时设置pcb->state为uninteruptible.
101 *
102 * @param x completion
103 * @param timeout 非负整数，等待指定时间，超时后就返回/ 或者提前done，则返回剩余timeout时间
104 * @return long - 返回剩余的timeout
105 */
wait_for_completion_timeout(struct completion * x,long timeout)106 long wait_for_completion_timeout(struct completion *x, long timeout)
107 {
108 BUG_ON(timeout < 0);
109 spin_lock(&x->wait_queue.lock);
110 timeout = __wait_for_common(x, &schedule_timeout_ms, timeout, PROC_UNINTERRUPTIBLE);
111 spin_unlock(&x->wait_queue.lock);
112 return timeout;
113 }
114
115 /**
116 * @brief 等待completion的完成，但是可以被中断（我也不太懂可以被中断是什么意思，就是pcb->state=interuptible）
117 *
118 * @param x completion
119 */
wait_for_completion_interruptible(struct completion * x)120 void wait_for_completion_interruptible(struct completion *x)
121 {
122 spin_lock(&x->wait_queue.lock);
123 __wait_for_common(x, &schedule_timeout_ms, MAX_TIMEOUT, PROC_INTERRUPTIBLE);
124 spin_unlock(&x->wait_queue.lock);
125 }
126
127 /**
128 * @brief 等待指定时间，超时后就返回, 等待completion的完成，但是可以被中断.
129 *
130 * @param x completion
131 * @param timeout 非负整数，等待指定时间，超时后就返回/ 或者提前done，则返回剩余timeout时间
132 * @return long - 返回剩余的timeout
133 */
wait_for_completion_interruptible_timeout(struct completion * x,long timeout)134 long wait_for_completion_interruptible_timeout(struct completion *x, long timeout)
135 {
136 BUG_ON(timeout < 0);
137
138 spin_lock(&x->wait_queue.lock);
139 timeout = __wait_for_common(x, &schedule_timeout_ms, timeout, PROC_INTERRUPTIBLE);
140 spin_unlock(&x->wait_queue.lock);
141 return timeout;
142 }
143
144 /**
145 * @brief 尝试获取completion的一个done！如果您在wait之前加上这个函数作为判断，说不定会加快运行速度。
146 *
147 * @param x completion
148 * @return true - 表示不需要wait_for_completion，并且已经获取到了一个completion(即返回true意味着done已经被 减1 ) \
149 * @return false - 表示当前done=0，您需要进入等待，即wait_for_completion
150 */
try_wait_for_completion(struct completion * x)151 bool try_wait_for_completion(struct completion *x)
152 {
153 if (!READ_ONCE(x->done))
154 return false;
155
156 bool ret = true;
157 spin_lock(&x->wait_queue.lock);
158
159 if (!x->done)
160 ret = false;
161 else if (x->done != COMPLETE_ALL)
162 --(x->done);
163
164 spin_unlock(&x->wait_queue.lock);
165 return ret;
166 }
167
168 /**
169 * @brief 测试一个completion是否有waiter。(即done是不是等于0)
170 *
171 * @param x completion
172 * @return true
173 * @return false
174 */
completion_done(struct completion * x)175 bool completion_done(struct completion *x)
176 {
177
178 if (!READ_ONCE(x->done))
179 return false;
180
181 // 这里的意义是: 如果是多线程的情况下，您有可能需要等待另一个进程的complete操作, 才算真正意义上的completed!
182 spin_lock(&x->wait_queue.lock);
183
184 if (!READ_ONCE(x->done))
185 {
186 spin_unlock(&x->wait_queue.lock);
187 return false;
188 }
189 spin_unlock(&x->wait_queue.lock);
190 return true;
191 }
192
193 /**
194 * @brief 对completion数组进行wait操作
195 *
196 * @param x completion array
197 * @param n len of the array
198 */
wait_for_multicompletion(struct completion x[],int n)199 void wait_for_multicompletion(struct completion x[], int n)
200 {
201 for (int i = 0; i < n; i++) // 对每一个completion都等一遍
202 {
203 if (!completion_done(&x[i])) // 如果没有done，直接wait
204 {
205 wait_for_completion(&x[i]);
206 }
207 else if (!try_wait_for_completion(&x[i])) //上面测试过done>0，那么这里尝试去获取一个done，如果失败了，就继续wait
208 {
209 wait_for_completion(&x[i]);
210 }
211 }
212 }
213
214 /**
215 * @brief 等待者, 等待wait_for_completion
216 *
217 * @param one_to_one
218 * @param one_to_many
219 * @param many_to_one
220 */
__test_completion_waiter(void * input_data)221 int __test_completion_waiter(void *input_data)
222 {
223 struct __test_data *data = (struct __test_data *)input_data;
224 // kdebug("THE %d WAITER BEGIN", -data->id);
225 // 测试一对多能不能实现等待 - 由外部统一放闸一起跑
226 if (!try_wait_for_completion(data->one_to_many))
227 {
228 wait_for_completion(data->one_to_many);
229 }
230
231 // 测试一对一能不能实现等待
232 if (!try_wait_for_completion(data->one_to_many))
233 {
234 wait_for_completion(data->one_to_many);
235 }
236
237 // 完成上面两个等待, 执行complete声明自己已经完成
238 complete(data->many_to_one);
239 // kdebug("THE %d WAITER SOLVED", -data->id);
240 return true;
241 }
242
243 /**
244 * @brief 执行者，执行complete
245 *
246 * @param one_to_one
247 * @param one_to_many
248 * @param many_to_one
249 */
__test_completion_worker(void * input_data)250 int __test_completion_worker(void *input_data)
251 {
252 struct __test_data *data = (struct __test_data *)input_data;
253 // kdebug("THE %d WORKER BEGIN", data->id);
254 // 测试一对多能不能实现等待 - 由外部统一放闸一起跑
255 if (!try_wait_for_completion(data->one_to_many))
256 {
257 wait_for_completion(data->one_to_many);
258 }
259
260 schedule_timeout_ms(50);
261 // for(uint64_t i=0;i<1e7;++i)
262 // pause();
263 complete(data->one_to_one);
264
265 // 完成上面两个等待, 执行complete声明自己已经完成
266 complete(data->many_to_one);
267 // kdebug("THE %d WORKER SOLVED", data->id);
268 return true;
269 }
270
271 /**
272 * @brief 测试函数
273 *
274 */
__test_completion()275 void __test_completion()
276 {
277 // kdebug("BEGIN COMPLETION TEST");
278 const int N = 100;
279 struct completion *one_to_one = kzalloc(sizeof(struct completion) * N, 0);
280 struct completion *one_to_many = kzalloc(sizeof(struct completion), 0);
281 struct completion *waiter_many_to_one = kzalloc(sizeof(struct completion) * N, 0);
282 struct completion *worker_many_to_one = kzalloc(sizeof(struct completion) * N, 0);
283 struct __test_data *waiter_data = kzalloc(sizeof(struct __test_data) * N, 0);
284 struct __test_data *worker_data = kzalloc(sizeof(struct __test_data) * N, 0);
285
286 completion_init(one_to_many);
287 for (int i = 0; i < N; i++)
288 {
289 completion_init(&one_to_one[i]);
290 completion_init(&waiter_many_to_one[i]);
291 completion_init(&worker_many_to_one[i]);
292 }
293
294 for (int i = 0; i < N; i++)
295 {
296 waiter_data[i].id = -i; // waiter
297 waiter_data[i].many_to_one = &waiter_many_to_one[i];
298 waiter_data[i].one_to_one = &one_to_one[i];
299 waiter_data[i].one_to_many = one_to_many;
300 kthread_run(__test_completion_waiter, &waiter_data[i], "the %dth waiter", i);
301 }
302
303 for (int i = 0; i < N; i++)
304 {
305 worker_data[i].id = i; // worker
306 worker_data[i].many_to_one = &worker_many_to_one[i];
307 worker_data[i].one_to_one = &one_to_one[i];
308 worker_data[i].one_to_many = one_to_many;
309 kthread_run(__test_completion_worker, &worker_data[i], "the %dth worker", i);
310 }
311
312 complete_all(one_to_many);
313 // kdebug("all of the waiters and workers begin running");
314
315 // kdebug("BEGIN COUNTING");
316
317 wait_for_multicompletion(waiter_many_to_one, N);
318 wait_for_multicompletion(worker_many_to_one, N);
319 // kdebug("all of the waiters and workers complete");
320
321 kfree(one_to_one);
322 kfree(one_to_many);
323 kfree(waiter_many_to_one);
324 kfree(worker_many_to_one);
325 kfree(waiter_data);
326 kfree(worker_data);
327 // kdebug("completion test done.");
328 }