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