1 // #![allow(dead_code)]
2 use core::intrinsics::unlikely;
3 
4 use alloc::{collections::LinkedList, sync::Arc, vec::Vec};
5 
6 use crate::{
7     arch::{sched::sched, CurrentIrqArch},
8     exception::InterruptArch,
9     kerror,
10     process::{ProcessControlBlock, ProcessManager, ProcessState},
11 };
12 
13 use super::{
14     mutex::MutexGuard,
15     spinlock::{SpinLock, SpinLockGuard},
16 };
17 
18 #[derive(Debug)]
19 struct InnerWaitQueue {
20     /// 等待队列的链表
21     wait_list: LinkedList<Arc<ProcessControlBlock>>,
22 }
23 
24 /// 被自旋锁保护的等待队列
25 #[derive(Debug)]
26 pub struct WaitQueue(SpinLock<InnerWaitQueue>);
27 
28 #[allow(dead_code)]
29 impl WaitQueue {
30     pub const INIT: WaitQueue = WaitQueue(SpinLock::new(InnerWaitQueue::INIT));
31 
32     /// @brief 让当前进程在等待队列上进行等待，并且，允许被信号打断
sleep(&self)33     pub fn sleep(&self) {
34         before_sleep_check(0);
35         let mut guard: SpinLockGuard<InnerWaitQueue> = self.0.lock_irqsave();
36         ProcessManager::mark_sleep(true).unwrap_or_else(|e| {
37             panic!("sleep error: {:?}", e);
38         });
39         guard.wait_list.push_back(ProcessManager::current_pcb());
40         drop(guard);
41         sched();
42     }
43 
44     /// @brief 让当前进程在等待队列上进行等待，并且,在释放waitqueue的锁之前，执行f函数闭包
sleep_with_func<F>(&self, f: F) where F: FnOnce(),45     pub fn sleep_with_func<F>(&self, f: F)
46     where
47         F: FnOnce(),
48     {
49         before_sleep_check(0);
50         let mut guard: SpinLockGuard<InnerWaitQueue> = self.0.lock();
51         let irq_guard = unsafe { CurrentIrqArch::save_and_disable_irq() };
52         ProcessManager::mark_sleep(true).unwrap_or_else(|e| {
53             panic!("sleep error: {:?}", e);
54         });
55         drop(irq_guard);
56         guard.wait_list.push_back(ProcessManager::current_pcb());
57         f();
58 
59         drop(guard);
60         sched();
61     }
62 
63     /// @brief 让当前进程在等待队列上进行等待. 但是，在释放waitqueue的锁之后，不会调用调度函数。
64     /// 这样的设计，是为了让调用者可以在执行本函数之后，执行一些操作，然后再【手动调用调度函数】。
65     ///
66     /// 执行本函数前，需要确保处于【中断禁止】状态。
67     ///
68     /// 尽管sleep_with_func和sleep_without_schedule都可以实现这个功能，但是，sleep_with_func会在释放锁之前，执行f函数闭包。
69     ///
70     /// 考虑这样一个场景：
71     /// 等待队列位于某个自旋锁保护的数据结构A中，我们希望在进程睡眠的同时，释放数据结构A的锁。
72     /// 在这种情况下，如果使用sleep_with_func，所有权系统不会允许我们这么做。
73     /// 因此，sleep_without_schedule的设计，正是为了解决这个问题。
74     ///
75     /// 由于sleep_without_schedule不会调用调度函数，因此，如果开发者忘记在执行本函数之后，手动调用调度函数，
76     /// 由于时钟中断到来或者‘其他cpu kick了当前cpu’，可能会导致一些未定义的行为。
sleep_without_schedule(&self)77     pub unsafe fn sleep_without_schedule(&self) {
78         before_sleep_check(1);
79         // 安全检查：确保当前处于中断禁止状态
80         assert!(CurrentIrqArch::is_irq_enabled() == false);
81         let mut guard: SpinLockGuard<InnerWaitQueue> = self.0.lock();
82         ProcessManager::mark_sleep(true).unwrap_or_else(|e| {
83             panic!("sleep error: {:?}", e);
84         });
85         guard.wait_list.push_back(ProcessManager::current_pcb());
86         drop(guard);
87     }
88 
sleep_without_schedule_uninterruptible(&self)89     pub unsafe fn sleep_without_schedule_uninterruptible(&self) {
90         before_sleep_check(0);
91         // 安全检查：确保当前处于中断禁止状态
92         assert!(CurrentIrqArch::is_irq_enabled() == false);
93         let mut guard: SpinLockGuard<InnerWaitQueue> = self.0.lock();
94         ProcessManager::mark_sleep(false).unwrap_or_else(|e| {
95             panic!("sleep error: {:?}", e);
96         });
97         guard.wait_list.push_back(ProcessManager::current_pcb());
98         drop(guard);
99     }
100     /// @brief 让当前进程在等待队列上进行等待，并且，不允许被信号打断
sleep_uninterruptible(&self)101     pub fn sleep_uninterruptible(&self) {
102         before_sleep_check(0);
103         let mut guard: SpinLockGuard<InnerWaitQueue> = self.0.lock();
104         let irq_guard = unsafe { CurrentIrqArch::save_and_disable_irq() };
105         ProcessManager::mark_sleep(false).unwrap_or_else(|e| {
106             panic!("sleep error: {:?}", e);
107         });
108         drop(irq_guard);
109         guard.wait_list.push_back(ProcessManager::current_pcb());
110         drop(guard);
111         sched();
112     }
113 
114     /// @brief 让当前进程在等待队列上进行等待，并且，允许被信号打断。
115     /// 在当前进程的pcb加入队列后，解锁指定的自旋锁。
sleep_unlock_spinlock<T>(&self, to_unlock: SpinLockGuard<T>)116     pub fn sleep_unlock_spinlock<T>(&self, to_unlock: SpinLockGuard<T>) {
117         before_sleep_check(1);
118         let mut guard: SpinLockGuard<InnerWaitQueue> = self.0.lock();
119         let irq_guard = unsafe { CurrentIrqArch::save_and_disable_irq() };
120         ProcessManager::mark_sleep(true).unwrap_or_else(|e| {
121             panic!("sleep error: {:?}", e);
122         });
123         drop(irq_guard);
124         guard.wait_list.push_back(ProcessManager::current_pcb());
125         drop(to_unlock);
126         drop(guard);
127         sched();
128     }
129 
130     /// @brief 让当前进程在等待队列上进行等待，并且，允许被信号打断。
131     /// 在当前进程的pcb加入队列后，解锁指定的Mutex。
sleep_unlock_mutex<T>(&self, to_unlock: MutexGuard<T>)132     pub fn sleep_unlock_mutex<T>(&self, to_unlock: MutexGuard<T>) {
133         before_sleep_check(1);
134         let mut guard: SpinLockGuard<InnerWaitQueue> = self.0.lock();
135         let irq_guard = unsafe { CurrentIrqArch::save_and_disable_irq() };
136         ProcessManager::mark_sleep(true).unwrap_or_else(|e| {
137             panic!("sleep error: {:?}", e);
138         });
139         drop(irq_guard);
140         guard.wait_list.push_back(ProcessManager::current_pcb());
141         drop(to_unlock);
142         drop(guard);
143         sched();
144     }
145 
146     /// @brief 让当前进程在等待队列上进行等待，并且，不允许被信号打断。
147     /// 在当前进程的pcb加入队列后，解锁指定的自旋锁。
sleep_uninterruptible_unlock_spinlock<T>(&self, to_unlock: SpinLockGuard<T>)148     pub fn sleep_uninterruptible_unlock_spinlock<T>(&self, to_unlock: SpinLockGuard<T>) {
149         before_sleep_check(1);
150         let mut guard: SpinLockGuard<InnerWaitQueue> = self.0.lock();
151         let irq_guard = unsafe { CurrentIrqArch::save_and_disable_irq() };
152         ProcessManager::mark_sleep(false).unwrap_or_else(|e| {
153             panic!("sleep error: {:?}", e);
154         });
155         drop(irq_guard);
156         guard.wait_list.push_back(ProcessManager::current_pcb());
157         drop(to_unlock);
158         drop(guard);
159         sched();
160     }
161 
162     /// @brief 让当前进程在等待队列上进行等待，并且，不允许被信号打断。
163     /// 在当前进程的pcb加入队列后，解锁指定的Mutex。
sleep_uninterruptible_unlock_mutex<T>(&self, to_unlock: MutexGuard<T>)164     pub fn sleep_uninterruptible_unlock_mutex<T>(&self, to_unlock: MutexGuard<T>) {
165         before_sleep_check(1);
166         let mut guard: SpinLockGuard<InnerWaitQueue> = self.0.lock();
167         let irq_guard = unsafe { CurrentIrqArch::save_and_disable_irq() };
168         ProcessManager::mark_sleep(false).unwrap_or_else(|e| {
169             panic!("sleep error: {:?}", e);
170         });
171         drop(irq_guard);
172 
173         guard.wait_list.push_back(ProcessManager::current_pcb());
174 
175         drop(to_unlock);
176         drop(guard);
177         sched();
178     }
179 
180     /// @brief 唤醒在队列中等待的第一个进程。
181     /// 如果这个进程的state与给定的state进行and操作之后，结果不为0,则唤醒它。
182     ///
183     /// @param state 用于判断的state，如果队列第一个进程与这个state相同，或者为None(表示不进行这个判断)，则唤醒这个进程。
184     ///
185     /// @return true 成功唤醒进程
186     /// @return false 没有唤醒进程
wakeup(&self, state: Option<ProcessState>) -> bool187     pub fn wakeup(&self, state: Option<ProcessState>) -> bool {
188         let mut guard: SpinLockGuard<InnerWaitQueue> = self.0.lock_irqsave();
189         // 如果队列为空，则返回
190         if guard.wait_list.is_empty() {
191             return false;
192         }
193         // 如果队列头部的pcb的state与给定的state相与，结果不为0，则唤醒
194         if let Some(state) = state {
195             if guard
196                 .wait_list
197                 .front()
198                 .unwrap()
199                 .sched_info()
200                 .inner_lock_read_irqsave()
201                 .state()
202                 != state
203             {
204                 return false;
205             }
206         }
207         let to_wakeup = guard.wait_list.pop_front().unwrap();
208         drop(guard);
209         let res = ProcessManager::wakeup(&to_wakeup).is_ok();
210         return res;
211     }
212 
213     /// @brief 唤醒在队列中，符合条件的所有进程。
214     ///
215     /// @param state 用于判断的state，如果一个进程与这个state相同，或者为None(表示不进行这个判断)，则唤醒这个进程。
wakeup_all(&self, state: Option<ProcessState>)216     pub fn wakeup_all(&self, state: Option<ProcessState>) {
217         let mut guard: SpinLockGuard<InnerWaitQueue> = self.0.lock_irqsave();
218         // 如果队列为空，则返回
219         if guard.wait_list.is_empty() {
220             return;
221         }
222 
223         let mut to_push_back: Vec<Arc<ProcessControlBlock>> = Vec::new();
224         // 如果队列头部的pcb的state与给定的state相与，结果不为0，则唤醒
225         while let Some(to_wakeup) = guard.wait_list.pop_front() {
226             let mut wake = false;
227             if let Some(state) = state {
228                 if to_wakeup.sched_info().inner_lock_read_irqsave().state() == state {
229                     wake = true;
230                 }
231             } else {
232                 wake = true;
233             }
234 
235             if wake {
236                 ProcessManager::wakeup(&to_wakeup).unwrap_or_else(|e| {
237                     kerror!("wakeup pid: {:?} error: {:?}", to_wakeup.pid(), e);
238                 });
239                 continue;
240             } else {
241                 to_push_back.push(to_wakeup);
242             }
243         }
244 
245         for to_wakeup in to_push_back {
246             guard.wait_list.push_back(to_wakeup);
247         }
248     }
249 
250     /// @brief 获得当前等待队列的大小
len(&self) -> usize251     pub fn len(&self) -> usize {
252         return self.0.lock().wait_list.len();
253     }
254 }
255 
256 impl InnerWaitQueue {
257     pub const INIT: InnerWaitQueue = InnerWaitQueue {
258         wait_list: LinkedList::new(),
259     };
260 }
261 
before_sleep_check(max_preempt: usize)262 fn before_sleep_check(max_preempt: usize) {
263     let pcb = ProcessManager::current_pcb();
264     if unlikely(pcb.preempt_count() > max_preempt) {
265         kwarn!(
266             "Process {:?}: Try to sleep when preempt count is {}",
267             pcb.pid(),
268             pcb.preempt_count()
269         );
270     }
271 }
272 
273 /// 事件等待队列
274 #[derive(Debug)]
275 pub struct EventWaitQueue {
276     wait_list: SpinLock<Vec<(u64, Arc<ProcessControlBlock>)>>,
277 }
278 
279 #[allow(dead_code)]
280 impl EventWaitQueue {
new() -> Self281     pub fn new() -> Self {
282         Self {
283             wait_list: SpinLock::new(Vec::new()),
284         }
285     }
286 
287     /// ## 让当前进程在该队列上等待感兴趣的事件
288     ///
289     /// ### 参数
290     /// - events: 进程感兴趣的事件，events最好是为位表示，一位表示一个事件
291     ///
292     /// 注意，使用前应该注意有可能其他地方定义了冲突的事件，可能会导致未定义行为
sleep(&self, events: u64)293     pub fn sleep(&self, events: u64) {
294         before_sleep_check(0);
295         let mut guard = self.wait_list.lock_irqsave();
296         ProcessManager::mark_sleep(true).unwrap_or_else(|e| {
297             panic!("sleep error: {:?}", e);
298         });
299         guard.push((events, ProcessManager::current_pcb()));
300         drop(guard);
301         sched();
302     }
303 
sleep_without_schedule(&self, events: u64)304     pub unsafe fn sleep_without_schedule(&self, events: u64) {
305         before_sleep_check(1);
306         let mut guard = self.wait_list.lock_irqsave();
307         ProcessManager::mark_sleep(true).unwrap_or_else(|e| {
308             panic!("sleep error: {:?}", e);
309         });
310         guard.push((events, ProcessManager::current_pcb()));
311         drop(guard);
312     }
313 
sleep_unlock_spinlock<T>(&self, events: u64, to_unlock: SpinLockGuard<T>)314     pub fn sleep_unlock_spinlock<T>(&self, events: u64, to_unlock: SpinLockGuard<T>) {
315         before_sleep_check(1);
316         let mut guard = self.wait_list.lock_irqsave();
317         let irq_guard = unsafe { CurrentIrqArch::save_and_disable_irq() };
318         ProcessManager::mark_sleep(true).unwrap_or_else(|e| {
319             panic!("sleep error: {:?}", e);
320         });
321         drop(irq_guard);
322         guard.push((events, ProcessManager::current_pcb()));
323         drop(to_unlock);
324         drop(guard);
325         sched();
326     }
327 
328     /// ### 唤醒该队列上等待events的进程
329     ///
330     ///  ### 参数
331     /// - events: 发生的事件
332     ///
333     /// 需要注意的是，只要触发了events中的任意一件事件，进程都会被唤醒
wakeup_any(&self, events: u64) -> usize334     pub fn wakeup_any(&self, events: u64) -> usize {
335         let mut ret = 0;
336 
337         let mut wq_guard = self.wait_list.lock_irqsave();
338         wq_guard.retain(|(es, pcb)| {
339             if *es & events > 0 {
340                 // 有感兴趣的事件
341                 if ProcessManager::wakeup(pcb).is_ok() {
342                     ret += 1;
343                     return false;
344                 } else {
345                     return true;
346                 }
347             } else {
348                 return true;
349             }
350         });
351         ret
352     }
353 
354     /// ### 唤醒该队列上等待events的进程
355     ///
356     ///  ### 参数
357     /// - events: 发生的事件
358     ///
359     /// 需要注意的是，只有满足所有事件的进程才会被唤醒
wakeup(&self, events: u64) -> usize360     pub fn wakeup(&self, events: u64) -> usize {
361         let mut ret = 0;
362         let mut wq_guard = self.wait_list.lock_irqsave();
363         wq_guard.retain(|(es, pcb)| {
364             if *es == events {
365                 // 有感兴趣的事件
366                 if ProcessManager::wakeup(pcb).is_ok() {
367                     ret += 1;
368                     return false;
369                 } else {
370                     return true;
371                 }
372             } else {
373                 return true;
374             }
375         });
376         ret
377     }
378 
wakeup_all(&self)379     pub fn wakeup_all(&self) {
380         self.wakeup_any(u64::MAX);
381     }
382 }
383