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 Iterator for FutexIterator<'_> { 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