xref: /DragonOS/kernel/src/libs/futex/futex.rs (revision 2eab6dd743e94a86a685f1f3c01e599adf86610a)
1 use alloc::{
2     collections::LinkedList,
3     sync::{Arc, Weak},
4 };
5 use core::hash::{Hash, Hasher};
6 use core::{
7     intrinsics::{likely, unlikely},
8     mem,
9     sync::atomic::AtomicU64,
10 };
11 use log::warn;
12 
13 use hashbrown::HashMap;
14 use system_error::SystemError;
15 
16 use crate::{
17     arch::{CurrentIrqArch, MMArch},
18     exception::InterruptArch,
19     libs::spinlock::{SpinLock, SpinLockGuard},
20     mm::{ucontext::AddressSpace, MemoryManagementArch, VirtAddr},
21     process::{Pid, ProcessControlBlock, ProcessManager},
22     sched::{schedule, SchedMode},
23     syscall::user_access::{UserBufferReader, UserBufferWriter},
24     time::{
25         timer::{next_n_us_timer_jiffies, Timer, WakeUpHelper},
26         PosixTimeSpec,
27     },
28 };
29 
30 use super::constant::*;
31 
32 static mut FUTEX_DATA: Option<FutexData> = None;
33 
34 pub struct FutexData {
35     data: SpinLock<HashMap<FutexKey, FutexHashBucket>>,
36 }
37 
38 impl FutexData {
futex_map() -> SpinLockGuard<'static, HashMap<FutexKey, FutexHashBucket>>39     pub fn futex_map() -> SpinLockGuard<'static, HashMap<FutexKey, FutexHashBucket>> {
40         unsafe { FUTEX_DATA.as_ref().unwrap().data.lock() }
41     }
42 
try_remove(key: &FutexKey) -> Option<FutexHashBucket>43     pub fn try_remove(key: &FutexKey) -> Option<FutexHashBucket> {
44         unsafe {
45             let mut guard = FUTEX_DATA.as_ref().unwrap().data.lock();
46             if let Some(futex) = guard.get(key) {
47                 if futex.chain.is_empty() {
48                     return guard.remove(key);
49                 }
50             }
51         }
52         None
53     }
54 }
55 
56 pub struct Futex;
57 
58 // 对于同一个futex的进程或线程将会在这个bucket等待
59 pub struct FutexHashBucket {
60     // 该futex维护的等待队列
61     chain: LinkedList<Arc<FutexObj>>,
62 }
63 
64 impl FutexHashBucket {
65     /// ## 判断是否在bucket里
contains(&self, futex_q: &FutexObj) -> bool66     pub fn contains(&self, futex_q: &FutexObj) -> bool {
67         self.chain
68             .iter()
69             .filter(|x| futex_q.pcb.ptr_eq(&x.pcb) && x.key == futex_q.key)
70             .count()
71             != 0
72     }
73 
74     /// 让futex_q在该bucket上挂起
75     ///
76     /// 进入该函数前,需要关中断
77     #[inline(always)]
sleep_no_sched(&mut self, futex_q: Arc<FutexObj>) -> Result<(), SystemError>78     pub fn sleep_no_sched(&mut self, futex_q: Arc<FutexObj>) -> Result<(), SystemError> {
79         assert!(!CurrentIrqArch::is_irq_enabled());
80         self.chain.push_back(futex_q);
81 
82         ProcessManager::mark_sleep(true)?;
83 
84         Ok(())
85     }
86 
87     /// ## 唤醒队列中的最多nr_wake个进程
88     ///
89     /// return: 唤醒的进程数
90     #[inline(always)]
wake_up( &mut self, key: FutexKey, bitset: Option<u32>, nr_wake: u32, ) -> Result<usize, SystemError>91     pub fn wake_up(
92         &mut self,
93         key: FutexKey,
94         bitset: Option<u32>,
95         nr_wake: u32,
96     ) -> Result<usize, SystemError> {
97         let mut count = 0;
98         let mut pop_count = 0;
99         while let Some(futex_q) = self.chain.pop_front() {
100             if futex_q.key == key {
101                 // TODO: 考虑优先级继承的机制
102 
103                 if let Some(bitset) = bitset {
104                     if futex_q.bitset != bitset {
105                         self.chain.push_back(futex_q);
106                         continue;
107                     }
108                 }
109 
110                 // 唤醒
111                 if futex_q.pcb.upgrade().is_some() {
112                     self.remove(futex_q.clone());
113                     ProcessManager::wakeup(&futex_q.pcb.upgrade().unwrap())?;
114                 }
115 
116                 // 判断唤醒数
117                 count += 1;
118                 if count >= nr_wake {
119                     break;
120                 }
121             } else {
122                 self.chain.push_back(futex_q);
123             }
124             // 判断是否循环完队列了
125             pop_count += 1;
126             if pop_count >= self.chain.len() {
127                 break;
128             }
129         }
130         Ok(count as usize)
131     }
132 
133     /// 将FutexObj从bucket中删除
remove(&mut self, futex: Arc<FutexObj>)134     pub fn remove(&mut self, futex: Arc<FutexObj>) {
135         self.chain
136             .extract_if(|x| Arc::ptr_eq(x, &futex))
137             .for_each(drop);
138     }
139 }
140 
141 #[derive(Debug)]
142 pub struct FutexObj {
143     pcb: Weak<ProcessControlBlock>,
144     key: FutexKey,
145     bitset: u32,
146     // TODO: 优先级继承
147 }
148 
149 pub enum FutexAccess {
150     FutexRead,
151     FutexWrite,
152 }
153 
154 #[allow(dead_code)]
155 #[derive(Hash, PartialEq, Eq, Clone, Debug)]
156 /// ### 用于定位内核唯一的futex
157 pub enum InnerFutexKey {
158     Shared(SharedKey),
159     Private(PrivateKey),
160 }
161 
162 #[derive(Hash, PartialEq, Eq, Clone, Debug)]
163 pub struct FutexKey {
164     ptr: u64,
165     word: u64,
166     offset: u32,
167     key: InnerFutexKey,
168 }
169 
170 /// 不同进程间通过文件共享futex变量,表明该变量在文件中的位置
171 #[derive(Hash, PartialEq, Eq, Clone, Debug)]
172 pub struct SharedKey {
173     i_seq: u64,
174     page_offset: u64,
175 }
176 
177 /// 同一进程的不同线程共享futex变量,表明该变量在进程地址空间中的位置
178 #[derive(Clone, Debug)]
179 pub struct PrivateKey {
180     // 所在的地址空间
181     address_space: Option<Weak<AddressSpace>>,
182     // 表示所在页面的初始地址
183     address: u64,
184 }
185 
186 impl Hash for PrivateKey {
hash<H: Hasher>(&self, state: &mut H)187     fn hash<H: Hasher>(&self, state: &mut H) {
188         self.address.hash(state);
189     }
190 }
191 
192 impl Eq for PrivateKey {}
193 
194 impl PartialEq for PrivateKey {
eq(&self, other: &Self) -> bool195     fn eq(&self, other: &Self) -> bool {
196         if self.address_space.is_none() && other.address_space.is_none() {
197             return self.address == other.address;
198         } else {
199             return self
200                 .address_space
201                 .as_ref()
202                 .unwrap_or(&Weak::default())
203                 .ptr_eq(other.address_space.as_ref().unwrap_or(&Weak::default()))
204                 && self.address == other.address;
205         }
206     }
207 }
208 
209 impl Futex {
210     /// ### 初始化FUTEX_DATA
init()211     pub fn init() {
212         unsafe {
213             FUTEX_DATA = Some(FutexData {
214                 data: SpinLock::new(HashMap::new()),
215             })
216         };
217     }
218 
219     /// ### 让当前进程在指定futex上等待直到futex_wake显式唤醒
futex_wait( uaddr: VirtAddr, flags: FutexFlag, val: u32, abs_time: Option<PosixTimeSpec>, bitset: u32, ) -> Result<usize, SystemError>220     pub fn futex_wait(
221         uaddr: VirtAddr,
222         flags: FutexFlag,
223         val: u32,
224         abs_time: Option<PosixTimeSpec>,
225         bitset: u32,
226     ) -> Result<usize, SystemError> {
227         if bitset == 0 {
228             return Err(SystemError::EINVAL);
229         }
230 
231         // 获取全局hash表的key值
232         let key = Self::get_futex_key(
233             uaddr,
234             flags.contains(FutexFlag::FLAGS_SHARED),
235             FutexAccess::FutexRead,
236         )?;
237 
238         let mut futex_map_guard = FutexData::futex_map();
239         let bucket = futex_map_guard.get_mut(&key);
240         let bucket_mut = match bucket {
241             Some(bucket) => bucket,
242             None => {
243                 let bucket = FutexHashBucket {
244                     chain: LinkedList::new(),
245                 };
246                 futex_map_guard.insert(key.clone(), bucket);
247                 futex_map_guard.get_mut(&key).unwrap()
248             }
249         };
250 
251         // 使用UserBuffer读取futex
252         let user_reader =
253             UserBufferReader::new(uaddr.as_ptr::<u32>(), core::mem::size_of::<u32>(), true)?;
254 
255         // 从用户空间读取到futex的val
256         let mut uval = 0;
257 
258         // 读取
259         // 这里只尝试一种方式去读取用户空间,与linux不太一致
260         // 对于linux,如果bucket被锁住时读取失败,将会将bucket解锁后重新读取
261         user_reader.copy_one_from_user::<u32>(&mut uval, 0)?;
262 
263         // 不满足wait条件,返回错误
264         if uval != val {
265             return Err(SystemError::EAGAIN_OR_EWOULDBLOCK);
266         }
267 
268         let pcb = ProcessManager::current_pcb();
269         // 创建超时计时器任务
270         let mut timer = None;
271         if let Some(time) = abs_time {
272             let wakeup_helper = WakeUpHelper::new(pcb.clone());
273 
274             let sec = time.tv_sec;
275             let nsec = time.tv_nsec;
276             let jiffies = next_n_us_timer_jiffies((nsec / 1000 + sec * 1_000_000) as u64);
277 
278             let wake_up = Timer::new(wakeup_helper, jiffies);
279 
280             wake_up.activate();
281             timer = Some(wake_up);
282         }
283 
284         let futex_q = Arc::new(FutexObj {
285             pcb: Arc::downgrade(&pcb),
286             key: key.clone(),
287             bitset,
288         });
289         let irq_guard = unsafe { CurrentIrqArch::save_and_disable_irq() };
290         // 满足条件则将当前进程在该bucket上挂起
291         bucket_mut.sleep_no_sched(futex_q.clone()).map_err(|e| {
292             warn!("error:{e:?}");
293             e
294         })?;
295         drop(futex_map_guard);
296         drop(irq_guard);
297         schedule(SchedMode::SM_NONE);
298 
299         // 被唤醒后的检查
300         let mut futex_map_guard = FutexData::futex_map();
301         let bucket = futex_map_guard.get_mut(&key);
302         let bucket_mut = match bucket {
303             // 如果该pcb不在链表里面了或者该链表已经被释放,就证明是正常的Wake操作
304             Some(bucket_mut) => {
305                 if !bucket_mut.contains(&futex_q) {
306                     // 取消定时器任务
307                     if let Some(timer) = timer {
308                         timer.cancel();
309                     }
310                     return Ok(0);
311                 }
312                 // 非正常唤醒,返回交给下层
313                 bucket_mut
314             }
315             None => {
316                 // 取消定时器任务
317                 if let Some(timer) = timer {
318                     timer.cancel();
319                 }
320                 return Ok(0);
321             }
322         };
323 
324         // 如果是超时唤醒,则返回错误
325         if timer.is_some() && timer.clone().unwrap().timeout() {
326             bucket_mut.remove(futex_q);
327 
328             return Err(SystemError::ETIMEDOUT);
329         }
330 
331         // TODO: 如果没有挂起的信号,则重新判断是否满足wait要求,重新进入wait
332 
333         // 经过前面的几个判断,到这里之后,
334         // 当前进程被唤醒大概率是其他进程更改了uval,需要重新去判断当前进程是否满足wait
335 
336         // 到这里之后,前面的唤醒条件都不满足,则是被信号唤醒
337         // 需要处理信号然后重启futex系统调用
338 
339         // 取消定时器任务
340         if let Some(timer) = timer {
341             if !timer.timeout() {
342                 timer.cancel();
343             }
344         }
345 
346         Ok(0)
347     }
348 
349     // ### 唤醒指定futex上挂起的最多nr_wake个进程
futex_wake( uaddr: VirtAddr, flags: FutexFlag, nr_wake: u32, bitset: u32, ) -> Result<usize, SystemError>350     pub fn futex_wake(
351         uaddr: VirtAddr,
352         flags: FutexFlag,
353         nr_wake: u32,
354         bitset: u32,
355     ) -> Result<usize, SystemError> {
356         if bitset == 0 {
357             return Err(SystemError::EINVAL);
358         }
359 
360         // 获取futex_key,并且判断地址空间合法性
361         let key = Self::get_futex_key(
362             uaddr,
363             flags.contains(FutexFlag::FLAGS_SHARED),
364             FutexAccess::FutexRead,
365         )?;
366         let mut binding = FutexData::futex_map();
367         let bucket_mut = binding.get_mut(&key).ok_or(SystemError::EINVAL)?;
368 
369         // 确保后面的唤醒操作是有意义的
370         if bucket_mut.chain.is_empty() {
371             return Ok(0);
372         }
373         // 从队列中唤醒
374         let count = bucket_mut.wake_up(key.clone(), Some(bitset), nr_wake)?;
375 
376         drop(binding);
377 
378         FutexData::try_remove(&key);
379 
380         Ok(count)
381     }
382 
383     /// ### 唤醒制定uaddr1上的最多nr_wake个进程,然后将uaddr1最多nr_requeue个进程移动到uaddr2绑定的futex上
futex_requeue( uaddr1: VirtAddr, flags: FutexFlag, uaddr2: VirtAddr, nr_wake: i32, nr_requeue: i32, cmpval: Option<u32>, requeue_pi: bool, ) -> Result<usize, SystemError>384     pub fn futex_requeue(
385         uaddr1: VirtAddr,
386         flags: FutexFlag,
387         uaddr2: VirtAddr,
388         nr_wake: i32,
389         nr_requeue: i32,
390         cmpval: Option<u32>,
391         requeue_pi: bool,
392     ) -> Result<usize, SystemError> {
393         if nr_requeue < 0 || nr_wake < 0 {
394             return Err(SystemError::EINVAL);
395         }
396 
397         // 暂时不支持优先级继承
398         if requeue_pi {
399             return Err(SystemError::ENOSYS);
400         }
401 
402         let key1 = Self::get_futex_key(
403             uaddr1,
404             flags.contains(FutexFlag::FLAGS_SHARED),
405             FutexAccess::FutexRead,
406         )?;
407         let key2 = Self::get_futex_key(uaddr2, flags.contains(FutexFlag::FLAGS_SHARED), {
408             match requeue_pi {
409                 true => FutexAccess::FutexWrite,
410                 false => FutexAccess::FutexRead,
411             }
412         })?;
413 
414         if requeue_pi && key1 == key2 {
415             return Err(SystemError::EINVAL);
416         }
417 
418         if likely(cmpval.is_some()) {
419             let uval_reader =
420                 UserBufferReader::new(uaddr1.as_ptr::<u32>(), core::mem::size_of::<u32>(), true)?;
421             let curval = uval_reader.read_one_from_user::<u32>(0)?;
422 
423             // 判断是否满足条件
424             if *curval != cmpval.unwrap() {
425                 return Err(SystemError::EAGAIN_OR_EWOULDBLOCK);
426             }
427         }
428 
429         let mut futex_data_guard = FutexData::futex_map();
430         if !requeue_pi {
431             // 唤醒nr_wake个进程
432             let bucket_1_mut = futex_data_guard.get_mut(&key1).ok_or(SystemError::EINVAL)?;
433             let ret = bucket_1_mut.wake_up(key1.clone(), None, nr_wake as u32)?;
434             // 将bucket1中最多nr_requeue个任务转移到bucket2
435             for _ in 0..nr_requeue {
436                 let bucket_1_mut = futex_data_guard.get_mut(&key1).ok_or(SystemError::EINVAL)?;
437                 let futex_q = bucket_1_mut.chain.pop_front();
438                 match futex_q {
439                     Some(futex_q) => {
440                         let bucket_2_mut =
441                             futex_data_guard.get_mut(&key2).ok_or(SystemError::EINVAL)?;
442                         bucket_2_mut.chain.push_back(futex_q);
443                     }
444                     None => {
445                         break;
446                     }
447                 }
448             }
449 
450             return Ok(ret);
451         } else {
452             // 暂时不支持优先级继承
453             todo!()
454         }
455     }
456 
457     /// ### 唤醒futex上的进程的同时进行一些操作
futex_wake_op( uaddr1: VirtAddr, flags: FutexFlag, uaddr2: VirtAddr, nr_wake: i32, nr_wake2: i32, op: i32, ) -> Result<usize, SystemError>458     pub fn futex_wake_op(
459         uaddr1: VirtAddr,
460         flags: FutexFlag,
461         uaddr2: VirtAddr,
462         nr_wake: i32,
463         nr_wake2: i32,
464         op: i32,
465     ) -> Result<usize, SystemError> {
466         let key1 = Futex::get_futex_key(
467             uaddr1,
468             flags.contains(FutexFlag::FLAGS_SHARED),
469             FutexAccess::FutexRead,
470         )?;
471         let key2 = Futex::get_futex_key(
472             uaddr2,
473             flags.contains(FutexFlag::FLAGS_SHARED),
474             FutexAccess::FutexWrite,
475         )?;
476 
477         let mut futex_data_guard = FutexData::futex_map();
478         let bucket1 = futex_data_guard.get_mut(&key1).ok_or(SystemError::EINVAL)?;
479         let mut wake_count = 0;
480 
481         // 唤醒uaddr1中的进程
482         wake_count += bucket1.wake_up(key1, None, nr_wake as u32)?;
483 
484         match Self::futex_atomic_op_inuser(op as u32, uaddr2) {
485             Ok(ret) => {
486                 // 操作成功则唤醒uaddr2中的进程
487                 if ret {
488                     let bucket2 = futex_data_guard.get_mut(&key2).ok_or(SystemError::EINVAL)?;
489                     wake_count += bucket2.wake_up(key2, None, nr_wake2 as u32)?;
490                 }
491             }
492             Err(e) => {
493                 // TODO:retry?
494                 return Err(e);
495             }
496         }
497 
498         Ok(wake_count)
499     }
500 
get_futex_key( uaddr: VirtAddr, fshared: bool, _access: FutexAccess, ) -> Result<FutexKey, SystemError>501     fn get_futex_key(
502         uaddr: VirtAddr,
503         fshared: bool,
504         _access: FutexAccess,
505     ) -> Result<FutexKey, SystemError> {
506         let mut address = uaddr.data();
507 
508         // 计算相对页的偏移量
509         let offset = address & (MMArch::PAGE_SIZE - 1);
510         // 判断内存对齐
511         if uaddr.data() & (core::mem::size_of::<u32>() - 1) != 0 {
512             return Err(SystemError::EINVAL);
513         }
514 
515         // 目前address指向所在页面的起始地址
516         address -= offset;
517 
518         // 若不是进程间共享的futex,则返回Private
519         if !fshared {
520             return Ok(FutexKey {
521                 ptr: 0,
522                 word: 0,
523                 offset: offset as u32,
524                 key: InnerFutexKey::Private(PrivateKey {
525                     address: address as u64,
526                     address_space: None,
527                 }),
528             });
529         }
530 
531         // 获取到地址所在地址空间
532         let address_space = AddressSpace::current()?;
533         // TODO: 判断是否为匿名映射,是匿名映射才返回PrivateKey
534         return Ok(FutexKey {
535             ptr: 0,
536             word: 0,
537             offset: offset as u32,
538             key: InnerFutexKey::Private(PrivateKey {
539                 address: address as u64,
540                 address_space: Some(Arc::downgrade(&address_space)),
541             }),
542         });
543 
544         // 未实现共享内存机制,贡献内存部分应该通过inode构建SharedKey
545         // todo!("Shared memory not implemented");
546     }
547 
futex_atomic_op_inuser(encoded_op: u32, uaddr: VirtAddr) -> Result<bool, SystemError>548     pub fn futex_atomic_op_inuser(encoded_op: u32, uaddr: VirtAddr) -> Result<bool, SystemError> {
549         let op = FutexOP::from_bits((encoded_op & 0x70000000) >> 28).ok_or(SystemError::ENOSYS)?;
550         let cmp =
551             FutexOpCMP::from_bits((encoded_op & 0x0f000000) >> 24).ok_or(SystemError::ENOSYS)?;
552 
553         let sign_extend32 = |value: u32, index: i32| {
554             let shift = (31 - index) as u8;
555             return (value << shift) >> shift;
556         };
557 
558         let mut oparg = sign_extend32((encoded_op & 0x00fff000) >> 12, 11);
559         let cmparg = sign_extend32(encoded_op & 0x00000fff, 11);
560 
561         if (encoded_op & (FutexOP::FUTEX_OP_OPARG_SHIFT.bits() << 28) != 0) && oparg > 31 {
562             warn!(
563                 "futex_wake_op: pid:{} tries to shift op by {}; fix this program",
564                 ProcessManager::current_pcb().pid().data(),
565                 oparg
566             );
567 
568             oparg &= 31;
569         }
570 
571         // TODO: 这个汇编似乎是有问题的,目前不好测试
572         let old_val = Self::arch_futex_atomic_op_inuser(op, oparg, uaddr)?;
573 
574         match cmp {
575             FutexOpCMP::FUTEX_OP_CMP_EQ => {
576                 return Ok(cmparg == old_val);
577             }
578             FutexOpCMP::FUTEX_OP_CMP_NE => {
579                 return Ok(cmparg != old_val);
580             }
581             FutexOpCMP::FUTEX_OP_CMP_LT => {
582                 return Ok(cmparg < old_val);
583             }
584             FutexOpCMP::FUTEX_OP_CMP_LE => {
585                 return Ok(cmparg <= old_val);
586             }
587             FutexOpCMP::FUTEX_OP_CMP_GE => {
588                 return Ok(cmparg >= old_val);
589             }
590             FutexOpCMP::FUTEX_OP_CMP_GT => {
591                 return Ok(cmparg > old_val);
592             }
593             _ => {
594                 return Err(SystemError::ENOSYS);
595             }
596         }
597     }
598 
599     /// ### 对futex进行操作
600     ///
601     /// 进入该方法会关闭中断保证修改的原子性,所以进入该方法前应确保中断锁已释放
602     ///
603     /// ### return uaddr原来的值
604     #[allow(unused_assignments)]
arch_futex_atomic_op_inuser( op: FutexOP, oparg: u32, uaddr: VirtAddr, ) -> Result<u32, SystemError>605     pub fn arch_futex_atomic_op_inuser(
606         op: FutexOP,
607         oparg: u32,
608         uaddr: VirtAddr,
609     ) -> Result<u32, SystemError> {
610         let guard = unsafe { CurrentIrqArch::save_and_disable_irq() };
611 
612         let reader =
613             UserBufferReader::new(uaddr.as_ptr::<u32>(), core::mem::size_of::<u32>(), true)?;
614 
615         let oldval = reader.read_one_from_user::<u32>(0)?;
616 
617         let atomic_addr = AtomicU64::new(uaddr.data() as u64);
618         // 这个指针是指向指针的指针
619         let ptr = atomic_addr.as_ptr();
620         match op {
621             FutexOP::FUTEX_OP_SET => unsafe {
622                 *((*ptr) as *mut u32) = oparg;
623             },
624             FutexOP::FUTEX_OP_ADD => unsafe {
625                 *((*ptr) as *mut u32) += oparg;
626             },
627             FutexOP::FUTEX_OP_OR => unsafe {
628                 *((*ptr) as *mut u32) |= oparg;
629             },
630             FutexOP::FUTEX_OP_ANDN => unsafe {
631                 *((*ptr) as *mut u32) &= oparg;
632             },
633             FutexOP::FUTEX_OP_XOR => unsafe {
634                 *((*ptr) as *mut u32) ^= oparg;
635             },
636             _ => return Err(SystemError::ENOSYS),
637         }
638 
639         drop(guard);
640 
641         Ok(*oldval)
642     }
643 }
644 
645 //用于指示在处理robust list是最多处理多少个条目
646 const ROBUST_LIST_LIMIT: isize = 2048;
647 
648 #[derive(Debug, Copy, Clone)]
649 pub struct RobustList {
650     next: VirtAddr,
651 }
652 
653 #[derive(Debug, Copy, Clone)]
654 pub struct RobustListHead {
655     list: RobustList,
656     futex_offset: isize,
657     list_op_pending: VirtAddr,
658 }
659 
660 impl RobustListHead {
661     /// # 获得futex的用户空间地址
futex_uaddr(&self, entry: VirtAddr) -> VirtAddr662     pub fn futex_uaddr(&self, entry: VirtAddr) -> VirtAddr {
663         return VirtAddr::new(entry.data() + self.futex_offset as usize);
664     }
665 
666     /// #获得list_op_peding的用户空间地址
pending_uaddr(&self) -> Option<VirtAddr>667     pub fn pending_uaddr(&self) -> Option<VirtAddr> {
668         if self.list_op_pending.is_null() {
669             return None;
670         } else {
671             return Some(self.futex_uaddr(self.list_op_pending));
672         }
673     }
674 
675     /// # 在内核注册robust list
676     /// ## 参数
677     /// - head_uaddr:robust list head用户空间地址
678     /// - len:robust list head的长度
set_robust_list(head_uaddr: VirtAddr, len: usize) -> Result<usize, SystemError>679     pub fn set_robust_list(head_uaddr: VirtAddr, len: usize) -> Result<usize, SystemError> {
680         let robust_list_head_len = mem::size_of::<&RobustListHead>();
681         if unlikely(len != robust_list_head_len) {
682             return Err(SystemError::EINVAL);
683         }
684 
685         let user_buffer_reader = UserBufferReader::new(
686             head_uaddr.as_ptr::<RobustListHead>(),
687             mem::size_of::<RobustListHead>(),
688             true,
689         )?;
690         let robust_list_head = *user_buffer_reader.read_one_from_user::<RobustListHead>(0)?;
691 
692         // 向内核注册robust list
693         ProcessManager::current_pcb().set_robust_list(Some(robust_list_head));
694 
695         return Ok(0);
696     }
697 
698     /// # 获取robust list head到用户空间
699     /// ## 参数
700     /// - pid:当前进程/线程的pid
701     /// -
get_robust_list( pid: usize, head_uaddr: VirtAddr, len_ptr_uaddr: VirtAddr, ) -> Result<usize, SystemError>702     pub fn get_robust_list(
703         pid: usize,
704         head_uaddr: VirtAddr,
705         len_ptr_uaddr: VirtAddr,
706     ) -> Result<usize, SystemError> {
707         // 获取当前进程的process control block
708         let pcb: Arc<ProcessControlBlock> = if pid == 0 {
709             ProcessManager::current_pcb()
710         } else {
711             ProcessManager::find(Pid::new(pid)).ok_or(SystemError::ESRCH)?
712         };
713 
714         // TODO: 检查当前进程是否能ptrace另一个进程
715         let ptrace = true;
716         if !ptrace {
717             return Err(SystemError::EPERM);
718         }
719 
720         //获取当前线程的robust list head 和 长度
721         let robust_list_head = (*pcb.get_robust_list()).ok_or(SystemError::EINVAL)?;
722 
723         // 将len拷贝到用户空间len_ptr
724         let mut user_writer = UserBufferWriter::new(
725             len_ptr_uaddr.as_ptr::<usize>(),
726             core::mem::size_of::<usize>(),
727             true,
728         )?;
729         user_writer.copy_one_to_user(&mem::size_of::<RobustListHead>(), 0)?;
730         // 将head拷贝到用户空间head
731         let mut user_writer = UserBufferWriter::new(
732             head_uaddr.as_ptr::<RobustListHead>(),
733             mem::size_of::<RobustListHead>(),
734             true,
735         )?;
736         user_writer.copy_one_to_user(&robust_list_head, 0)?;
737 
738         return Ok(0);
739     }
740 
741     /// # 进程/线程退出时清理工作
742     /// ## 参数
743     /// - current:当前进程/线程的pcb
744     /// - pid:当前进程/线程的pid
exit_robust_list(pcb: Arc<ProcessControlBlock>)745     pub fn exit_robust_list(pcb: Arc<ProcessControlBlock>) {
746         //指向当前进程的robust list头部的指针
747         let head = match *pcb.get_robust_list() {
748             Some(rl) => rl,
749             None => {
750                 return;
751             }
752         };
753         // 遍历当前进程/线程的robust list
754         for futex_uaddr in head.futexes() {
755             let ret = Self::handle_futex_death(futex_uaddr, pcb.pid().into() as u32);
756             if ret.is_err() {
757                 return;
758             }
759         }
760         pcb.set_robust_list(None);
761     }
762 
763     /// # 返回robust list的迭代器,将robust list list_op_pending 放到最后(如果存在)
futexes(&self) -> FutexIterator<'_>764     fn futexes(&self) -> FutexIterator<'_> {
765         return FutexIterator::new(self);
766     }
767 
768     /// # 处理进程即将死亡时,进程已经持有的futex,唤醒其他等待该futex的线程
769     /// ## 参数
770     /// - futex_uaddr:futex的用户空间地址
771     /// - pid: 当前进程/线程的pid
handle_futex_death(futex_uaddr: VirtAddr, pid: u32) -> Result<usize, SystemError>772     fn handle_futex_death(futex_uaddr: VirtAddr, pid: u32) -> Result<usize, SystemError> {
773         let futex_val = {
774             if futex_uaddr.is_null() {
775                 return Err(SystemError::EINVAL);
776             }
777             let user_buffer_reader = UserBufferReader::new(
778                 futex_uaddr.as_ptr::<u32>(),
779                 core::mem::size_of::<u32>(),
780                 true,
781             )?;
782             *user_buffer_reader.read_one_from_user::<u32>(0)?
783         };
784 
785         let mut uval = futex_val;
786         loop {
787             // 该futex可能被其他进程占有
788             let owner = uval & FUTEX_TID_MASK;
789             if owner != pid {
790                 break;
791             }
792 
793             // 判断是否有FUTEX_WAITERS和标记FUTEX_OWNER_DIED
794             let mval = (uval & FUTEX_WAITERS) | FUTEX_OWNER_DIED;
795 
796             // 读取用户空间目前的futex字段,判断在此之前futex是否有被修改
797             let user_buffer_reader = UserBufferReader::new(
798                 futex_uaddr.as_ptr::<u32>(),
799                 core::mem::size_of::<u32>(),
800                 true,
801             )?;
802             let nval = *user_buffer_reader.read_one_from_user::<u32>(0)?;
803             if nval != mval {
804                 uval = nval;
805                 let mut user_buffer_writer = UserBufferWriter::new(
806                     futex_uaddr.as_ptr::<u32>(),
807                     core::mem::size_of::<u32>(),
808                     true,
809                 )?;
810                 user_buffer_writer.copy_one_to_user(&mval, 0)?;
811                 continue;
812             }
813 
814             // 有等待者,进行唤醒操作
815             if nval & FUTEX_WAITERS != 0 {
816                 let mut flags = FutexFlag::FLAGS_MATCH_NONE;
817                 flags.insert(FutexFlag::FLAGS_SHARED);
818                 Futex::futex_wake(futex_uaddr, flags, 1, FUTEX_BITSET_MATCH_ANY)?;
819             }
820             break;
821         }
822 
823         return Ok(0);
824     }
825 }
826 
827 pub struct FutexIterator<'a> {
828     robust_list_head: &'a RobustListHead,
829     entry: VirtAddr,
830     count: isize,
831 }
832 
833 impl<'a> FutexIterator<'a> {
new(robust_list_head: &'a RobustListHead) -> Self834     pub fn new(robust_list_head: &'a RobustListHead) -> Self {
835         return Self {
836             robust_list_head,
837             entry: robust_list_head.list.next,
838             count: 0,
839         };
840     }
841 
is_end(&mut self) -> bool842     fn is_end(&mut self) -> bool {
843         return self.count < 0;
844     }
845 }
846 
847 impl<'a> Iterator for FutexIterator<'a> {
848     type Item = VirtAddr;
849 
next(&mut self) -> Option<Self::Item>850     fn next(&mut self) -> Option<Self::Item> {
851         if self.is_end() {
852             return None;
853         }
854 
855         while self.entry.data() != &self.robust_list_head.list as *const RobustList as usize {
856             if self.count == ROBUST_LIST_LIMIT {
857                 break;
858             }
859             if self.entry.is_null() {
860                 return None;
861             }
862 
863             //获取futex val地址
864             let futex_uaddr = if self.entry.data() != self.robust_list_head.list_op_pending.data() {
865                 Some(self.robust_list_head.futex_uaddr(self.entry))
866             } else {
867                 None
868             };
869 
870             let user_buffer_reader = UserBufferReader::new(
871                 self.entry.as_ptr::<RobustList>(),
872                 mem::size_of::<RobustList>(),
873                 true,
874             )
875             .ok()?;
876             let next_entry = user_buffer_reader
877                 .read_one_from_user::<RobustList>(0)
878                 .ok()?;
879 
880             self.entry = next_entry.next;
881 
882             self.count += 1;
883 
884             if futex_uaddr.is_some() {
885                 return futex_uaddr;
886             }
887         }
888         self.count -= 1;
889         self.robust_list_head.pending_uaddr()
890     }
891 }
892