1971462beSGnoCiYeH use alloc::{ 2971462beSGnoCiYeH collections::LinkedList, 3971462beSGnoCiYeH sync::{Arc, Weak}, 4971462beSGnoCiYeH }; 5971462beSGnoCiYeH use core::hash::{Hash, Hasher}; 6971462beSGnoCiYeH use core::{intrinsics::likely, sync::atomic::AtomicU64}; 7971462beSGnoCiYeH use hashbrown::HashMap; 8*91e9d4abSLoGin use system_error::SystemError; 9971462beSGnoCiYeH 10971462beSGnoCiYeH use crate::{ 11971462beSGnoCiYeH arch::{sched::sched, CurrentIrqArch, MMArch}, 12971462beSGnoCiYeH exception::InterruptArch, 13971462beSGnoCiYeH libs::spinlock::{SpinLock, SpinLockGuard}, 14971462beSGnoCiYeH mm::{ucontext::AddressSpace, MemoryManagementArch, VirtAddr}, 15971462beSGnoCiYeH process::{ProcessControlBlock, ProcessManager}, 16*91e9d4abSLoGin syscall::user_access::UserBufferReader, 17971462beSGnoCiYeH time::{ 18971462beSGnoCiYeH timer::{next_n_us_timer_jiffies, Timer, WakeUpHelper}, 19971462beSGnoCiYeH TimeSpec, 20971462beSGnoCiYeH }, 21971462beSGnoCiYeH }; 22971462beSGnoCiYeH 23971462beSGnoCiYeH use super::constant::*; 24971462beSGnoCiYeH 25971462beSGnoCiYeH static mut FUTEX_DATA: Option<FutexData> = None; 26971462beSGnoCiYeH 27971462beSGnoCiYeH pub struct FutexData { 28971462beSGnoCiYeH data: SpinLock<HashMap<FutexKey, FutexHashBucket>>, 29971462beSGnoCiYeH } 30971462beSGnoCiYeH 31971462beSGnoCiYeH impl FutexData { 32971462beSGnoCiYeH pub fn futex_map() -> SpinLockGuard<'static, HashMap<FutexKey, FutexHashBucket>> { 33971462beSGnoCiYeH unsafe { FUTEX_DATA.as_ref().unwrap().data.lock() } 34971462beSGnoCiYeH } 35971462beSGnoCiYeH 36971462beSGnoCiYeH pub fn try_remove(key: &FutexKey) -> Option<FutexHashBucket> { 37971462beSGnoCiYeH unsafe { 38971462beSGnoCiYeH let mut guard = FUTEX_DATA.as_ref().unwrap().data.lock(); 39971462beSGnoCiYeH if let Some(futex) = guard.get(key) { 40971462beSGnoCiYeH if futex.chain.is_empty() { 41971462beSGnoCiYeH return guard.remove(key); 42971462beSGnoCiYeH } 43971462beSGnoCiYeH } 44971462beSGnoCiYeH } 45971462beSGnoCiYeH None 46971462beSGnoCiYeH } 47971462beSGnoCiYeH } 48971462beSGnoCiYeH 49971462beSGnoCiYeH pub struct Futex; 50971462beSGnoCiYeH 51971462beSGnoCiYeH // 对于同一个futex的进程或线程将会在这个bucket等待 52971462beSGnoCiYeH pub struct FutexHashBucket { 53971462beSGnoCiYeH // 该futex维护的等待队列 54971462beSGnoCiYeH chain: LinkedList<Arc<FutexObj>>, 55971462beSGnoCiYeH } 56971462beSGnoCiYeH 57971462beSGnoCiYeH impl FutexHashBucket { 58971462beSGnoCiYeH /// ## 判断是否在bucket里 59971462beSGnoCiYeH pub fn contains(&self, futex_q: &FutexObj) -> bool { 60971462beSGnoCiYeH self.chain 61971462beSGnoCiYeH .iter() 62971462beSGnoCiYeH .filter(|x| futex_q.pcb.ptr_eq(&x.pcb) && x.key == futex_q.key) 63971462beSGnoCiYeH .count() 64971462beSGnoCiYeH != 0 65971462beSGnoCiYeH } 66971462beSGnoCiYeH 67971462beSGnoCiYeH /// 让futex_q在该bucket上挂起 68971462beSGnoCiYeH /// 69971462beSGnoCiYeH /// 进入该函数前,需要关中断 70971462beSGnoCiYeH #[inline(always)] 71971462beSGnoCiYeH pub fn sleep_no_sched(&mut self, futex_q: Arc<FutexObj>) -> Result<(), SystemError> { 72971462beSGnoCiYeH assert!(CurrentIrqArch::is_irq_enabled() == false); 73971462beSGnoCiYeH self.chain.push_back(futex_q); 74971462beSGnoCiYeH 75971462beSGnoCiYeH ProcessManager::mark_sleep(true)?; 76971462beSGnoCiYeH 77971462beSGnoCiYeH Ok(()) 78971462beSGnoCiYeH } 79971462beSGnoCiYeH 80971462beSGnoCiYeH /// ## 唤醒队列中的最多nr_wake个进程 81971462beSGnoCiYeH /// 82971462beSGnoCiYeH /// return: 唤醒的进程数 83971462beSGnoCiYeH #[inline(always)] 84971462beSGnoCiYeH pub fn wake_up( 85971462beSGnoCiYeH &mut self, 86971462beSGnoCiYeH key: FutexKey, 87971462beSGnoCiYeH bitset: Option<u32>, 88971462beSGnoCiYeH nr_wake: u32, 89971462beSGnoCiYeH ) -> Result<usize, SystemError> { 90971462beSGnoCiYeH let mut count = 0; 91971462beSGnoCiYeH let mut pop_count = 0; 92971462beSGnoCiYeH while let Some(futex_q) = self.chain.pop_front() { 93971462beSGnoCiYeH if futex_q.key == key { 94971462beSGnoCiYeH // TODO: 考虑优先级继承的机制 95971462beSGnoCiYeH 96971462beSGnoCiYeH if let Some(bitset) = bitset { 97971462beSGnoCiYeH if futex_q.bitset != bitset { 98971462beSGnoCiYeH self.chain.push_back(futex_q); 99971462beSGnoCiYeH continue; 100971462beSGnoCiYeH } 101971462beSGnoCiYeH } 102971462beSGnoCiYeH 103971462beSGnoCiYeH // 唤醒 104971462beSGnoCiYeH if futex_q.pcb.upgrade().is_some() { 105971462beSGnoCiYeH self.remove(futex_q.clone()); 106971462beSGnoCiYeH ProcessManager::wakeup(&futex_q.pcb.upgrade().unwrap())?; 107971462beSGnoCiYeH } 108971462beSGnoCiYeH 109971462beSGnoCiYeH // 判断唤醒数 110971462beSGnoCiYeH count += 1; 111971462beSGnoCiYeH if count >= nr_wake { 112971462beSGnoCiYeH break; 113971462beSGnoCiYeH } 114971462beSGnoCiYeH } else { 115971462beSGnoCiYeH self.chain.push_back(futex_q); 116971462beSGnoCiYeH } 117971462beSGnoCiYeH // 判断是否循环完队列了 118971462beSGnoCiYeH pop_count += 1; 119971462beSGnoCiYeH if pop_count >= self.chain.len() { 120971462beSGnoCiYeH break; 121971462beSGnoCiYeH } 122971462beSGnoCiYeH } 123971462beSGnoCiYeH Ok(count as usize) 124971462beSGnoCiYeH } 125971462beSGnoCiYeH 126971462beSGnoCiYeH /// 将FutexObj从bucket中删除 127971462beSGnoCiYeH pub fn remove(&mut self, futex: Arc<FutexObj>) { 1281a72a751SLoGin self.chain 1291a72a751SLoGin .extract_if(|x| Arc::ptr_eq(x, &futex)) 1301a72a751SLoGin .for_each(drop); 131971462beSGnoCiYeH } 132971462beSGnoCiYeH } 133971462beSGnoCiYeH 134971462beSGnoCiYeH #[derive(Debug)] 135971462beSGnoCiYeH pub struct FutexObj { 136971462beSGnoCiYeH pcb: Weak<ProcessControlBlock>, 137971462beSGnoCiYeH key: FutexKey, 138971462beSGnoCiYeH bitset: u32, 139971462beSGnoCiYeH // TODO: 优先级继承 140971462beSGnoCiYeH } 141971462beSGnoCiYeH 142971462beSGnoCiYeH pub enum FutexAccess { 143971462beSGnoCiYeH FutexRead, 144971462beSGnoCiYeH FutexWrite, 145971462beSGnoCiYeH } 146971462beSGnoCiYeH 147971462beSGnoCiYeH #[allow(dead_code)] 148971462beSGnoCiYeH #[derive(Hash, PartialEq, Eq, Clone, Debug)] 149971462beSGnoCiYeH /// ### 用于定位内核唯一的futex 150971462beSGnoCiYeH pub enum InnerFutexKey { 151971462beSGnoCiYeH Shared(SharedKey), 152971462beSGnoCiYeH Private(PrivateKey), 153971462beSGnoCiYeH } 154971462beSGnoCiYeH 155971462beSGnoCiYeH #[derive(Hash, PartialEq, Eq, Clone, Debug)] 156971462beSGnoCiYeH pub struct FutexKey { 157971462beSGnoCiYeH ptr: u64, 158971462beSGnoCiYeH word: u64, 159971462beSGnoCiYeH offset: u32, 160971462beSGnoCiYeH key: InnerFutexKey, 161971462beSGnoCiYeH } 162971462beSGnoCiYeH 163971462beSGnoCiYeH /// 不同进程间通过文件共享futex变量,表明该变量在文件中的位置 164971462beSGnoCiYeH #[derive(Hash, PartialEq, Eq, Clone, Debug)] 165971462beSGnoCiYeH pub struct SharedKey { 166971462beSGnoCiYeH i_seq: u64, 167971462beSGnoCiYeH page_offset: u64, 168971462beSGnoCiYeH } 169971462beSGnoCiYeH 170971462beSGnoCiYeH /// 同一进程的不同线程共享futex变量,表明该变量在进程地址空间中的位置 171971462beSGnoCiYeH #[derive(Clone, Debug)] 172971462beSGnoCiYeH pub struct PrivateKey { 173971462beSGnoCiYeH // 所在的地址空间 174971462beSGnoCiYeH address_space: Option<Weak<AddressSpace>>, 175971462beSGnoCiYeH // 表示所在页面的初始地址 176971462beSGnoCiYeH address: u64, 177971462beSGnoCiYeH } 178971462beSGnoCiYeH 179971462beSGnoCiYeH impl Hash for PrivateKey { 1801a72a751SLoGin fn hash<H: Hasher>(&self, state: &mut H) { 181971462beSGnoCiYeH self.address.hash(state); 182971462beSGnoCiYeH } 183971462beSGnoCiYeH } 184971462beSGnoCiYeH 185971462beSGnoCiYeH impl Eq for PrivateKey {} 186971462beSGnoCiYeH 187971462beSGnoCiYeH impl PartialEq for PrivateKey { 188971462beSGnoCiYeH fn eq(&self, other: &Self) -> bool { 189971462beSGnoCiYeH if self.address_space.is_none() && other.address_space.is_none() { 190971462beSGnoCiYeH return self.address == other.address; 191971462beSGnoCiYeH } else { 192971462beSGnoCiYeH return self 193971462beSGnoCiYeH .address_space 194971462beSGnoCiYeH .as_ref() 195971462beSGnoCiYeH .unwrap_or(&Weak::default()) 196971462beSGnoCiYeH .ptr_eq(&other.address_space.as_ref().unwrap_or(&Weak::default())) 197971462beSGnoCiYeH && self.address == other.address; 198971462beSGnoCiYeH } 199971462beSGnoCiYeH } 200971462beSGnoCiYeH } 201971462beSGnoCiYeH 202971462beSGnoCiYeH impl Futex { 203971462beSGnoCiYeH /// ### 初始化FUTEX_DATA 204971462beSGnoCiYeH pub fn init() { 205971462beSGnoCiYeH unsafe { 206971462beSGnoCiYeH FUTEX_DATA = Some(FutexData { 207971462beSGnoCiYeH data: SpinLock::new(HashMap::new()), 208971462beSGnoCiYeH }) 209971462beSGnoCiYeH }; 210971462beSGnoCiYeH } 211971462beSGnoCiYeH 212971462beSGnoCiYeH /// ### 让当前进程在指定futex上等待直到futex_wake显式唤醒 213971462beSGnoCiYeH pub fn futex_wait( 214971462beSGnoCiYeH uaddr: VirtAddr, 215971462beSGnoCiYeH flags: FutexFlag, 216971462beSGnoCiYeH val: u32, 217971462beSGnoCiYeH abs_time: Option<TimeSpec>, 218971462beSGnoCiYeH bitset: u32, 219971462beSGnoCiYeH ) -> Result<usize, SystemError> { 220971462beSGnoCiYeH if bitset == 0 { 221971462beSGnoCiYeH return Err(SystemError::EINVAL); 222971462beSGnoCiYeH } 223971462beSGnoCiYeH 224971462beSGnoCiYeH // 获取全局hash表的key值 225971462beSGnoCiYeH let key = Self::get_futex_key( 226971462beSGnoCiYeH uaddr, 227971462beSGnoCiYeH flags.contains(FutexFlag::FLAGS_SHARED), 228971462beSGnoCiYeH FutexAccess::FutexRead, 229971462beSGnoCiYeH )?; 230971462beSGnoCiYeH 231971462beSGnoCiYeH let mut futex_map_guard = FutexData::futex_map(); 232971462beSGnoCiYeH let bucket = futex_map_guard.get_mut(&key); 233971462beSGnoCiYeH let bucket_mut = match bucket { 234971462beSGnoCiYeH Some(bucket) => bucket, 235971462beSGnoCiYeH None => { 236971462beSGnoCiYeH let bucket = FutexHashBucket { 237971462beSGnoCiYeH chain: LinkedList::new(), 238971462beSGnoCiYeH }; 239971462beSGnoCiYeH futex_map_guard.insert(key.clone(), bucket); 240971462beSGnoCiYeH futex_map_guard.get_mut(&key).unwrap() 241971462beSGnoCiYeH } 242971462beSGnoCiYeH }; 243971462beSGnoCiYeH 244971462beSGnoCiYeH // 使用UserBuffer读取futex 245971462beSGnoCiYeH let user_reader = 246971462beSGnoCiYeH UserBufferReader::new(uaddr.as_ptr::<u32>(), core::mem::size_of::<u32>(), true)?; 247971462beSGnoCiYeH 248971462beSGnoCiYeH // 从用户空间读取到futex的val 249971462beSGnoCiYeH let mut uval = 0; 250971462beSGnoCiYeH 251971462beSGnoCiYeH // 读取 252971462beSGnoCiYeH // 这里只尝试一种方式去读取用户空间,与linux不太一致 253971462beSGnoCiYeH // 对于linux,如果bucket被锁住时读取失败,将会将bucket解锁后重新读取 254971462beSGnoCiYeH user_reader.copy_one_from_user::<u32>(&mut uval, 0)?; 255971462beSGnoCiYeH 256971462beSGnoCiYeH // 不满足wait条件,返回错误 257971462beSGnoCiYeH if uval != val { 258971462beSGnoCiYeH return Err(SystemError::EAGAIN_OR_EWOULDBLOCK); 259971462beSGnoCiYeH } 260971462beSGnoCiYeH 261971462beSGnoCiYeH let pcb = ProcessManager::current_pcb(); 262971462beSGnoCiYeH // 创建超时计时器任务 263971462beSGnoCiYeH let mut timer = None; 264971462beSGnoCiYeH if !abs_time.is_none() { 265971462beSGnoCiYeH let time = abs_time.unwrap(); 266971462beSGnoCiYeH 267971462beSGnoCiYeH let wakeup_helper = WakeUpHelper::new(pcb.clone()); 268971462beSGnoCiYeH 269971462beSGnoCiYeH let sec = time.tv_sec; 270971462beSGnoCiYeH let nsec = time.tv_nsec; 271971462beSGnoCiYeH let jiffies = next_n_us_timer_jiffies((nsec / 1000 + sec * 1_000_000) as u64); 272971462beSGnoCiYeH 273971462beSGnoCiYeH let wake_up = Timer::new(wakeup_helper, jiffies); 274971462beSGnoCiYeH 275971462beSGnoCiYeH wake_up.activate(); 276971462beSGnoCiYeH timer = Some(wake_up); 277971462beSGnoCiYeH } 278971462beSGnoCiYeH 279971462beSGnoCiYeH let futex_q = Arc::new(FutexObj { 280971462beSGnoCiYeH pcb: Arc::downgrade(&pcb), 281971462beSGnoCiYeH key: key.clone(), 282971462beSGnoCiYeH bitset, 283971462beSGnoCiYeH }); 284971462beSGnoCiYeH let irq_guard = unsafe { CurrentIrqArch::save_and_disable_irq() }; 285971462beSGnoCiYeH // 满足条件则将当前进程在该bucket上挂起 286971462beSGnoCiYeH bucket_mut.sleep_no_sched(futex_q.clone()).map_err(|e| { 287971462beSGnoCiYeH kwarn!("error:{e:?}"); 288971462beSGnoCiYeH e 289971462beSGnoCiYeH })?; 290971462beSGnoCiYeH drop(futex_map_guard); 291971462beSGnoCiYeH drop(irq_guard); 292971462beSGnoCiYeH sched(); 293971462beSGnoCiYeH 294971462beSGnoCiYeH // 被唤醒后的检查 295971462beSGnoCiYeH let mut futex_map_guard = FutexData::futex_map(); 296971462beSGnoCiYeH let bucket = futex_map_guard.get_mut(&key); 297971462beSGnoCiYeH let bucket_mut = match bucket { 298971462beSGnoCiYeH // 如果该pcb不在链表里面了或者该链表已经被释放,就证明是正常的Wake操作 299971462beSGnoCiYeH Some(bucket_mut) => { 300971462beSGnoCiYeH if !bucket_mut.contains(&futex_q) { 301971462beSGnoCiYeH // 取消定时器任务 302971462beSGnoCiYeH if timer.is_some() { 303971462beSGnoCiYeH timer.unwrap().cancel(); 304971462beSGnoCiYeH } 305971462beSGnoCiYeH return Ok(0); 306971462beSGnoCiYeH } 307971462beSGnoCiYeH // 非正常唤醒,返回交给下层 308971462beSGnoCiYeH bucket_mut 309971462beSGnoCiYeH } 310971462beSGnoCiYeH None => { 311971462beSGnoCiYeH // 取消定时器任务 312971462beSGnoCiYeH if timer.is_some() { 313971462beSGnoCiYeH timer.unwrap().cancel(); 314971462beSGnoCiYeH } 315971462beSGnoCiYeH return Ok(0); 316971462beSGnoCiYeH } 317971462beSGnoCiYeH }; 318971462beSGnoCiYeH 319971462beSGnoCiYeH // 如果是超时唤醒,则返回错误 320971462beSGnoCiYeH if timer.is_some() { 321971462beSGnoCiYeH if timer.clone().unwrap().timeout() { 322971462beSGnoCiYeH bucket_mut.remove(futex_q); 323971462beSGnoCiYeH 324971462beSGnoCiYeH return Err(SystemError::ETIMEDOUT); 325971462beSGnoCiYeH } 326971462beSGnoCiYeH } 327971462beSGnoCiYeH 328971462beSGnoCiYeH // TODO: 如果没有挂起的信号,则重新判断是否满足wait要求,重新进入wait 329971462beSGnoCiYeH 330971462beSGnoCiYeH // 经过前面的几个判断,到这里之后, 331971462beSGnoCiYeH // 当前进程被唤醒大概率是其他进程更改了uval,需要重新去判断当前进程是否满足wait 332971462beSGnoCiYeH 333971462beSGnoCiYeH // 到这里之后,前面的唤醒条件都不满足,则是被信号唤醒 334971462beSGnoCiYeH // 需要处理信号然后重启futex系统调用 335971462beSGnoCiYeH 336971462beSGnoCiYeH // 取消定时器任务 337971462beSGnoCiYeH if timer.is_some() { 338971462beSGnoCiYeH let timer = timer.unwrap(); 339971462beSGnoCiYeH if !timer.timeout() { 340971462beSGnoCiYeH timer.cancel(); 341971462beSGnoCiYeH } 342971462beSGnoCiYeH } 343971462beSGnoCiYeH Ok(0) 344971462beSGnoCiYeH } 345971462beSGnoCiYeH 346971462beSGnoCiYeH // ### 唤醒指定futex上挂起的最多nr_wake个进程 347971462beSGnoCiYeH pub fn futex_wake( 348971462beSGnoCiYeH uaddr: VirtAddr, 349971462beSGnoCiYeH flags: FutexFlag, 350971462beSGnoCiYeH nr_wake: u32, 351971462beSGnoCiYeH bitset: u32, 352971462beSGnoCiYeH ) -> Result<usize, SystemError> { 353971462beSGnoCiYeH if bitset == 0 { 354971462beSGnoCiYeH return Err(SystemError::EINVAL); 355971462beSGnoCiYeH } 356971462beSGnoCiYeH 357971462beSGnoCiYeH // 获取futex_key,并且判断地址空间合法性 358971462beSGnoCiYeH let key = Self::get_futex_key( 359971462beSGnoCiYeH uaddr, 360971462beSGnoCiYeH flags.contains(FutexFlag::FLAGS_SHARED), 361971462beSGnoCiYeH FutexAccess::FutexRead, 362971462beSGnoCiYeH )?; 363971462beSGnoCiYeH let mut binding = FutexData::futex_map(); 364971462beSGnoCiYeH let bucket_mut = binding.get_mut(&key).ok_or(SystemError::EINVAL)?; 365971462beSGnoCiYeH 366971462beSGnoCiYeH // 确保后面的唤醒操作是有意义的 367971462beSGnoCiYeH if bucket_mut.chain.is_empty() { 368971462beSGnoCiYeH return Ok(0); 369971462beSGnoCiYeH } 370971462beSGnoCiYeH // 从队列中唤醒 371971462beSGnoCiYeH let count = bucket_mut.wake_up(key.clone(), Some(bitset), nr_wake)?; 372971462beSGnoCiYeH 373971462beSGnoCiYeH drop(binding); 374971462beSGnoCiYeH 375971462beSGnoCiYeH FutexData::try_remove(&key); 376971462beSGnoCiYeH 377971462beSGnoCiYeH Ok(count) 378971462beSGnoCiYeH } 379971462beSGnoCiYeH 380971462beSGnoCiYeH /// ### 唤醒制定uaddr1上的最多nr_wake个进程,然后将uaddr1最多nr_requeue个进程移动到uaddr2绑定的futex上 381971462beSGnoCiYeH pub fn futex_requeue( 382971462beSGnoCiYeH uaddr1: VirtAddr, 383971462beSGnoCiYeH flags: FutexFlag, 384971462beSGnoCiYeH uaddr2: VirtAddr, 385971462beSGnoCiYeH nr_wake: i32, 386971462beSGnoCiYeH nr_requeue: i32, 387971462beSGnoCiYeH cmpval: Option<u32>, 388971462beSGnoCiYeH requeue_pi: bool, 389971462beSGnoCiYeH ) -> Result<usize, SystemError> { 390971462beSGnoCiYeH if nr_requeue < 0 || nr_wake < 0 { 391971462beSGnoCiYeH return Err(SystemError::EINVAL); 392971462beSGnoCiYeH } 393971462beSGnoCiYeH 394971462beSGnoCiYeH // 暂时不支持优先级继承 395971462beSGnoCiYeH if requeue_pi { 396971462beSGnoCiYeH return Err(SystemError::ENOSYS); 397971462beSGnoCiYeH } 398971462beSGnoCiYeH 399971462beSGnoCiYeH let key1 = Self::get_futex_key( 400971462beSGnoCiYeH uaddr1, 401971462beSGnoCiYeH flags.contains(FutexFlag::FLAGS_SHARED), 402971462beSGnoCiYeH FutexAccess::FutexRead, 403971462beSGnoCiYeH )?; 404971462beSGnoCiYeH let key2 = Self::get_futex_key(uaddr2, flags.contains(FutexFlag::FLAGS_SHARED), { 405971462beSGnoCiYeH match requeue_pi { 406971462beSGnoCiYeH true => FutexAccess::FutexWrite, 407971462beSGnoCiYeH false => FutexAccess::FutexRead, 408971462beSGnoCiYeH } 409971462beSGnoCiYeH })?; 410971462beSGnoCiYeH 411971462beSGnoCiYeH if requeue_pi && key1 == key2 { 412971462beSGnoCiYeH return Err(SystemError::EINVAL); 413971462beSGnoCiYeH } 414971462beSGnoCiYeH 415971462beSGnoCiYeH if likely(!cmpval.is_none()) { 416971462beSGnoCiYeH let uval_reader = 417971462beSGnoCiYeH UserBufferReader::new(uaddr1.as_ptr::<u32>(), core::mem::size_of::<u32>(), true)?; 418971462beSGnoCiYeH let curval = uval_reader.read_one_from_user::<u32>(0)?; 419971462beSGnoCiYeH 420971462beSGnoCiYeH // 判断是否满足条件 421971462beSGnoCiYeH if *curval != cmpval.unwrap() { 422971462beSGnoCiYeH return Err(SystemError::EAGAIN_OR_EWOULDBLOCK); 423971462beSGnoCiYeH } 424971462beSGnoCiYeH } 425971462beSGnoCiYeH 426971462beSGnoCiYeH let mut futex_data_guard = FutexData::futex_map(); 427971462beSGnoCiYeH if !requeue_pi { 428971462beSGnoCiYeH // 唤醒nr_wake个进程 429971462beSGnoCiYeH let bucket_1_mut = futex_data_guard.get_mut(&key1).ok_or(SystemError::EINVAL)?; 430971462beSGnoCiYeH let ret = bucket_1_mut.wake_up(key1.clone(), None, nr_wake as u32)?; 431971462beSGnoCiYeH // 将bucket1中最多nr_requeue个任务转移到bucket2 432971462beSGnoCiYeH for _ in 0..nr_requeue { 433971462beSGnoCiYeH let bucket_1_mut = futex_data_guard.get_mut(&key1).ok_or(SystemError::EINVAL)?; 434971462beSGnoCiYeH let futex_q = bucket_1_mut.chain.pop_front(); 435971462beSGnoCiYeH match futex_q { 436971462beSGnoCiYeH Some(futex_q) => { 437971462beSGnoCiYeH let bucket_2_mut = 438971462beSGnoCiYeH futex_data_guard.get_mut(&key2).ok_or(SystemError::EINVAL)?; 439971462beSGnoCiYeH bucket_2_mut.chain.push_back(futex_q); 440971462beSGnoCiYeH } 441971462beSGnoCiYeH None => { 442971462beSGnoCiYeH break; 443971462beSGnoCiYeH } 444971462beSGnoCiYeH } 445971462beSGnoCiYeH } 446971462beSGnoCiYeH 447971462beSGnoCiYeH return Ok(ret); 448971462beSGnoCiYeH } else { 449971462beSGnoCiYeH // 暂时不支持优先级继承 450971462beSGnoCiYeH todo!() 451971462beSGnoCiYeH } 452971462beSGnoCiYeH } 453971462beSGnoCiYeH 454971462beSGnoCiYeH /// ### 唤醒futex上的进程的同时进行一些操作 455971462beSGnoCiYeH pub fn futex_wake_op( 456971462beSGnoCiYeH uaddr1: VirtAddr, 457971462beSGnoCiYeH flags: FutexFlag, 458971462beSGnoCiYeH uaddr2: VirtAddr, 459971462beSGnoCiYeH nr_wake: i32, 460971462beSGnoCiYeH nr_wake2: i32, 461971462beSGnoCiYeH op: i32, 462971462beSGnoCiYeH ) -> Result<usize, SystemError> { 463971462beSGnoCiYeH let key1 = Futex::get_futex_key( 464971462beSGnoCiYeH uaddr1, 465971462beSGnoCiYeH flags.contains(FutexFlag::FLAGS_SHARED), 466971462beSGnoCiYeH FutexAccess::FutexRead, 467971462beSGnoCiYeH )?; 468971462beSGnoCiYeH let key2 = Futex::get_futex_key( 469971462beSGnoCiYeH uaddr2, 470971462beSGnoCiYeH flags.contains(FutexFlag::FLAGS_SHARED), 471971462beSGnoCiYeH FutexAccess::FutexWrite, 472971462beSGnoCiYeH )?; 473971462beSGnoCiYeH 474971462beSGnoCiYeH let mut futex_data_guard = FutexData::futex_map(); 475971462beSGnoCiYeH let bucket1 = futex_data_guard.get_mut(&key1).ok_or(SystemError::EINVAL)?; 476971462beSGnoCiYeH let mut wake_count = 0; 477971462beSGnoCiYeH 478971462beSGnoCiYeH // 唤醒uaddr1中的进程 479971462beSGnoCiYeH wake_count += bucket1.wake_up(key1, None, nr_wake as u32)?; 480971462beSGnoCiYeH 481971462beSGnoCiYeH match Self::futex_atomic_op_inuser(op as u32, uaddr2) { 482971462beSGnoCiYeH Ok(ret) => { 483971462beSGnoCiYeH // 操作成功则唤醒uaddr2中的进程 484971462beSGnoCiYeH if ret { 485971462beSGnoCiYeH let bucket2 = futex_data_guard.get_mut(&key2).ok_or(SystemError::EINVAL)?; 486971462beSGnoCiYeH wake_count += bucket2.wake_up(key2, None, nr_wake2 as u32)?; 487971462beSGnoCiYeH } 488971462beSGnoCiYeH } 489971462beSGnoCiYeH Err(e) => { 490971462beSGnoCiYeH // TODO:retry? 491971462beSGnoCiYeH return Err(e); 492971462beSGnoCiYeH } 493971462beSGnoCiYeH } 494971462beSGnoCiYeH 495971462beSGnoCiYeH Ok(wake_count) 496971462beSGnoCiYeH } 497971462beSGnoCiYeH 498971462beSGnoCiYeH fn get_futex_key( 499971462beSGnoCiYeH uaddr: VirtAddr, 500971462beSGnoCiYeH fshared: bool, 501971462beSGnoCiYeH _access: FutexAccess, 502971462beSGnoCiYeH ) -> Result<FutexKey, SystemError> { 503971462beSGnoCiYeH let mut address = uaddr.data(); 504971462beSGnoCiYeH 505971462beSGnoCiYeH // 计算相对页的偏移量 506971462beSGnoCiYeH let offset = address & (MMArch::PAGE_SIZE - 1); 507971462beSGnoCiYeH // 判断内存对齐 508971462beSGnoCiYeH if !(uaddr.data() & (core::mem::size_of::<u32>() - 1) == 0) { 509971462beSGnoCiYeH return Err(SystemError::EINVAL); 510971462beSGnoCiYeH } 511971462beSGnoCiYeH 512971462beSGnoCiYeH // 目前address指向所在页面的起始地址 513971462beSGnoCiYeH address -= offset; 514971462beSGnoCiYeH 515971462beSGnoCiYeH // 若不是进程间共享的futex,则返回Private 516971462beSGnoCiYeH if !fshared { 517971462beSGnoCiYeH return Ok(FutexKey { 518971462beSGnoCiYeH ptr: 0, 519971462beSGnoCiYeH word: 0, 520971462beSGnoCiYeH offset: offset as u32, 521971462beSGnoCiYeH key: InnerFutexKey::Private(PrivateKey { 522971462beSGnoCiYeH address: address as u64, 523971462beSGnoCiYeH address_space: None, 524971462beSGnoCiYeH }), 525971462beSGnoCiYeH }); 526971462beSGnoCiYeH } 527971462beSGnoCiYeH 528971462beSGnoCiYeH // 获取到地址所在地址空间 529971462beSGnoCiYeH let address_space = AddressSpace::current()?; 530971462beSGnoCiYeH // TODO: 判断是否为匿名映射,是匿名映射才返回PrivateKey 531971462beSGnoCiYeH return Ok(FutexKey { 532971462beSGnoCiYeH ptr: 0, 533971462beSGnoCiYeH word: 0, 534971462beSGnoCiYeH offset: offset as u32, 535971462beSGnoCiYeH key: InnerFutexKey::Private(PrivateKey { 536971462beSGnoCiYeH address: address as u64, 537971462beSGnoCiYeH address_space: Some(Arc::downgrade(&address_space)), 538971462beSGnoCiYeH }), 539971462beSGnoCiYeH }); 540971462beSGnoCiYeH 541971462beSGnoCiYeH // 未实现共享内存机制,贡献内存部分应该通过inode构建SharedKey 542971462beSGnoCiYeH // todo!("Shared memory not implemented"); 543971462beSGnoCiYeH } 544971462beSGnoCiYeH 545971462beSGnoCiYeH pub fn futex_atomic_op_inuser(encoded_op: u32, uaddr: VirtAddr) -> Result<bool, SystemError> { 546971462beSGnoCiYeH let op = FutexOP::from_bits((encoded_op & 0x70000000) >> 28).ok_or(SystemError::ENOSYS)?; 547971462beSGnoCiYeH let cmp = 548971462beSGnoCiYeH FutexOpCMP::from_bits((encoded_op & 0x0f000000) >> 24).ok_or(SystemError::ENOSYS)?; 549971462beSGnoCiYeH 550971462beSGnoCiYeH let sign_extend32 = |value: u32, index: i32| { 551971462beSGnoCiYeH let shift = (31 - index) as u8; 552971462beSGnoCiYeH return (value << shift) >> shift; 553971462beSGnoCiYeH }; 554971462beSGnoCiYeH 555971462beSGnoCiYeH let mut oparg = sign_extend32((encoded_op & 0x00fff000) >> 12, 11); 556971462beSGnoCiYeH let cmparg = sign_extend32(encoded_op & 0x00000fff, 11); 557971462beSGnoCiYeH 558971462beSGnoCiYeH if encoded_op & (FutexOP::FUTEX_OP_OPARG_SHIFT.bits() << 28) != 0 { 559971462beSGnoCiYeH if oparg > 31 { 560971462beSGnoCiYeH kwarn!( 561971462beSGnoCiYeH "futex_wake_op: pid:{} tries to shift op by {}; fix this program", 562971462beSGnoCiYeH ProcessManager::current_pcb().pid().data(), 563971462beSGnoCiYeH oparg 564971462beSGnoCiYeH ); 565971462beSGnoCiYeH 566971462beSGnoCiYeH oparg &= 31; 567971462beSGnoCiYeH } 568971462beSGnoCiYeH } 569971462beSGnoCiYeH 570971462beSGnoCiYeH // TODO: 这个汇编似乎是有问题的,目前不好测试 571971462beSGnoCiYeH let old_val = Self::arch_futex_atomic_op_inuser(op, oparg, uaddr)?; 572971462beSGnoCiYeH 573971462beSGnoCiYeH match cmp { 574971462beSGnoCiYeH FutexOpCMP::FUTEX_OP_CMP_EQ => { 575971462beSGnoCiYeH return Ok(cmparg == old_val); 576971462beSGnoCiYeH } 577971462beSGnoCiYeH FutexOpCMP::FUTEX_OP_CMP_NE => { 578971462beSGnoCiYeH return Ok(cmparg != old_val); 579971462beSGnoCiYeH } 580971462beSGnoCiYeH FutexOpCMP::FUTEX_OP_CMP_LT => { 581971462beSGnoCiYeH return Ok(cmparg < old_val); 582971462beSGnoCiYeH } 583971462beSGnoCiYeH FutexOpCMP::FUTEX_OP_CMP_LE => { 584971462beSGnoCiYeH return Ok(cmparg <= old_val); 585971462beSGnoCiYeH } 586971462beSGnoCiYeH FutexOpCMP::FUTEX_OP_CMP_GE => { 587971462beSGnoCiYeH return Ok(cmparg >= old_val); 588971462beSGnoCiYeH } 589971462beSGnoCiYeH FutexOpCMP::FUTEX_OP_CMP_GT => { 590971462beSGnoCiYeH return Ok(cmparg > old_val); 591971462beSGnoCiYeH } 592971462beSGnoCiYeH _ => { 593971462beSGnoCiYeH return Err(SystemError::ENOSYS); 594971462beSGnoCiYeH } 595971462beSGnoCiYeH } 596971462beSGnoCiYeH } 597971462beSGnoCiYeH 598971462beSGnoCiYeH /// ### 对futex进行操作 599971462beSGnoCiYeH /// 600971462beSGnoCiYeH /// 进入该方法会关闭中断保证修改的原子性,所以进入该方法前应确保中断锁已释放 601971462beSGnoCiYeH /// 602971462beSGnoCiYeH /// ### return uaddr原来的值 603971462beSGnoCiYeH #[allow(unused_assignments)] 604971462beSGnoCiYeH pub fn arch_futex_atomic_op_inuser( 605971462beSGnoCiYeH op: FutexOP, 606971462beSGnoCiYeH oparg: u32, 607971462beSGnoCiYeH uaddr: VirtAddr, 608971462beSGnoCiYeH ) -> Result<u32, SystemError> { 609971462beSGnoCiYeH let guard = unsafe { CurrentIrqArch::save_and_disable_irq() }; 610971462beSGnoCiYeH 611971462beSGnoCiYeH let reader = 612971462beSGnoCiYeH UserBufferReader::new(uaddr.as_ptr::<u32>(), core::mem::size_of::<u32>(), true)?; 613971462beSGnoCiYeH 614971462beSGnoCiYeH let oldval = reader.read_one_from_user::<u32>(0)?; 615971462beSGnoCiYeH 616971462beSGnoCiYeH let atomic_addr = AtomicU64::new(uaddr.data() as u64); 617971462beSGnoCiYeH // 这个指针是指向指针的指针 6181a72a751SLoGin let ptr = atomic_addr.as_ptr(); 619971462beSGnoCiYeH match op { 620971462beSGnoCiYeH FutexOP::FUTEX_OP_SET => unsafe { 621971462beSGnoCiYeH *((*ptr) as *mut u32) = oparg; 622971462beSGnoCiYeH }, 623971462beSGnoCiYeH FutexOP::FUTEX_OP_ADD => unsafe { 624971462beSGnoCiYeH *((*ptr) as *mut u32) += oparg; 625971462beSGnoCiYeH }, 626971462beSGnoCiYeH FutexOP::FUTEX_OP_OR => unsafe { 627971462beSGnoCiYeH *((*ptr) as *mut u32) |= oparg; 628971462beSGnoCiYeH }, 629971462beSGnoCiYeH FutexOP::FUTEX_OP_ANDN => unsafe { 630971462beSGnoCiYeH *((*ptr) as *mut u32) &= oparg; 631971462beSGnoCiYeH }, 632971462beSGnoCiYeH FutexOP::FUTEX_OP_XOR => unsafe { 633971462beSGnoCiYeH *((*ptr) as *mut u32) ^= oparg; 634971462beSGnoCiYeH }, 635971462beSGnoCiYeH _ => return Err(SystemError::ENOSYS), 636971462beSGnoCiYeH } 637971462beSGnoCiYeH 638971462beSGnoCiYeH drop(guard); 639971462beSGnoCiYeH 640971462beSGnoCiYeH Ok(*oldval) 641971462beSGnoCiYeH } 642971462beSGnoCiYeH } 643971462beSGnoCiYeH 644971462beSGnoCiYeH #[no_mangle] 645971462beSGnoCiYeH unsafe extern "C" fn rs_futex_init() { 646971462beSGnoCiYeH Futex::init(); 647971462beSGnoCiYeH } 648