1 #![allow(dead_code)] 2 use core::{ 3 cell::UnsafeCell, 4 hint::spin_loop, 5 mem::{self, ManuallyDrop}, 6 ops::{Deref, DerefMut}, 7 sync::atomic::{AtomicU32, Ordering}, 8 }; 9 10 use system_error::SystemError; 11 12 use crate::{ 13 arch::CurrentIrqArch, 14 exception::{InterruptArch, IrqFlagsGuard}, 15 process::ProcessManager, 16 }; 17 18 ///RwLock读写锁 19 20 /// @brief READER位占据从右往左数第三个比特位 21 const READER: u32 = 1 << 2; 22 23 /// @brief UPGRADED位占据从右到左数第二个比特位 24 const UPGRADED: u32 = 1 << 1; 25 26 /// @brief WRITER位占据最右边的比特位 27 const WRITER: u32 = 1; 28 29 const READER_BIT: u32 = 2; 30 31 /// @brief 读写锁的基本数据结构 32 /// @param lock 32位原子变量,最右边的两位从左到右分别是UPGRADED,WRITER (标志位) 33 /// 剩下的bit位存储READER数量(除了MSB) 34 /// 对于标志位,0代表无, 1代表有 35 /// 对于剩下的比特位表征READER的数量的多少 36 /// lock的MSB必须为0,否则溢出 37 #[derive(Debug)] 38 pub struct RwLock<T> { 39 lock: AtomicU32, 40 data: UnsafeCell<T>, 41 } 42 43 /// @brief READER守卫的数据结构 44 /// @param lock 是对RwLock的lock属性值的只读引用 45 pub struct RwLockReadGuard<'a, T: 'a> { 46 data: *const T, 47 lock: &'a AtomicU32, 48 irq_guard: Option<IrqFlagsGuard>, 49 } 50 51 /// @brief UPGRADED是介于READER和WRITER之间的一种锁,它可以升级为WRITER, 52 /// UPGRADED守卫的数据结构,注册UPGRADED锁只需要查看UPGRADED和WRITER的比特位 53 /// 但是当UPGRADED守卫注册后,不允许有新的读者锁注册 54 /// @param inner 是对RwLock数据结构的只读引用 55 pub struct RwLockUpgradableGuard<'a, T: 'a> { 56 data: *const T, 57 inner: &'a RwLock<T>, 58 irq_guard: Option<IrqFlagsGuard>, 59 } 60 61 /// @brief WRITER守卫的数据结构 62 /// @param data RwLock的data的可变引用 63 /// @param inner 是对RwLock数据结构的只读引用 64 pub struct RwLockWriteGuard<'a, T: 'a> { 65 data: *mut T, 66 inner: &'a RwLock<T>, 67 irq_guard: Option<IrqFlagsGuard>, 68 } 69 70 unsafe impl<T: Send> Send for RwLock<T> {} 71 unsafe impl<T: Send + Sync> Sync for RwLock<T> {} 72 73 /// @brief RwLock的API 74 impl<T> RwLock<T> { 75 #[inline] 76 /// @brief RwLock的初始化 77 pub const fn new(data: T) -> Self { 78 return RwLock { 79 lock: AtomicU32::new(0), 80 data: UnsafeCell::new(data), 81 }; 82 } 83 84 #[allow(dead_code)] 85 #[inline] 86 /// @brief 将读写锁的皮扒掉,返回内在的data,返回的是一个真身而非引用 87 pub fn into_inner(self) -> T { 88 let RwLock { data, .. } = self; 89 return data.into_inner(); 90 } 91 92 #[allow(dead_code)] 93 #[inline] 94 /// @brief 返回data的raw pointer, 95 /// unsafe 96 pub fn as_mut_ptr(&self) -> *mut T { 97 return self.data.get(); 98 } 99 100 #[allow(dead_code)] 101 #[inline] 102 /// @brief 获取实时的读者数并尝试加1,如果增加值成功则返回增加1后的读者数,否则panic 103 fn current_reader(&self) -> Result<u32, SystemError> { 104 const MAX_READERS: u32 = core::u32::MAX >> READER_BIT >> 1; //右移3位 105 106 let value = self.lock.fetch_add(READER, Ordering::Acquire); 107 //value二进制形式的MSB不能为1, 否则导致溢出 108 109 if value > MAX_READERS << READER_BIT { 110 self.lock.fetch_sub(READER, Ordering::Release); 111 //panic!("Too many lock readers, cannot safely proceed"); 112 return Err(SystemError::EOVERFLOW); 113 } else { 114 return Ok(value); 115 } 116 } 117 118 #[allow(dead_code)] 119 #[inline] 120 /// @brief 尝试获取READER守卫 121 pub fn try_read(&self) -> Option<RwLockReadGuard<T>> { 122 ProcessManager::preempt_disable(); 123 let r = self.inner_try_read(); 124 if r.is_none() { 125 ProcessManager::preempt_enable(); 126 } 127 return r; 128 } 129 130 fn inner_try_read(&self) -> Option<RwLockReadGuard<T>> { 131 let reader_value = self.current_reader(); 132 //得到自增后的reader_value, 包括了尝试获得READER守卫的进程 133 134 let value = if let Ok(rv) = reader_value { 135 rv 136 } else { 137 return None; 138 }; 139 140 //判断有没有writer和upgrader 141 //注意, 若upgrader存在,已经存在的读者继续占有锁,但新读者不允许获得锁 142 if value & (WRITER | UPGRADED) != 0 { 143 self.lock.fetch_sub(READER, Ordering::Release); 144 return None; 145 } else { 146 return Some(RwLockReadGuard { 147 data: unsafe { &*self.data.get() }, 148 lock: &self.lock, 149 irq_guard: None, 150 }); 151 } 152 } 153 154 #[allow(dead_code)] 155 #[inline] 156 /// @brief 获得READER的守卫 157 pub fn read(&self) -> RwLockReadGuard<T> { 158 loop { 159 match self.try_read() { 160 Some(guard) => return guard, 161 None => spin_loop(), 162 } 163 } //忙等待 164 } 165 166 /// 关中断并获取读者守卫 167 pub fn read_irqsave(&self) -> RwLockReadGuard<T> { 168 loop { 169 let irq_guard = unsafe { CurrentIrqArch::save_and_disable_irq() }; 170 match self.try_read() { 171 Some(mut guard) => { 172 guard.irq_guard = Some(irq_guard); 173 return guard; 174 } 175 None => spin_loop(), 176 } 177 } 178 } 179 180 /// 尝试关闭中断并获取读者守卫 181 pub fn try_read_irqsave(&self) -> Option<RwLockReadGuard<T>> { 182 let irq_guard = unsafe { CurrentIrqArch::save_and_disable_irq() }; 183 if let Some(mut guard) = self.try_read() { 184 guard.irq_guard = Some(irq_guard); 185 return Some(guard); 186 } else { 187 return None; 188 } 189 } 190 191 #[allow(dead_code)] 192 #[inline] 193 /// @brief 获取读者+UPGRADER的数量, 不能保证能否获得同步值 194 pub fn reader_count(&self) -> u32 { 195 let state = self.lock.load(Ordering::Relaxed); 196 return state / READER + (state & UPGRADED) / UPGRADED; 197 } 198 199 #[allow(dead_code)] 200 #[inline] 201 /// @brief 获取写者数量,不能保证能否获得同步值 202 pub fn writer_count(&self) -> u32 { 203 return (self.lock.load(Ordering::Relaxed) & WRITER) / WRITER; 204 } 205 206 #[cfg(any(target_arch = "x86_64", target_arch = "riscv64"))] 207 #[allow(dead_code)] 208 #[inline] 209 /// @brief 尝试获得WRITER守卫 210 pub fn try_write(&self) -> Option<RwLockWriteGuard<T>> { 211 ProcessManager::preempt_disable(); 212 let r = self.inner_try_write(); 213 if r.is_none() { 214 ProcessManager::preempt_enable(); 215 } 216 217 return r; 218 } //当架构为arm时,有些代码需要作出调整compare_exchange=>compare_exchange_weak 219 220 #[cfg(any(target_arch = "x86_64", target_arch = "riscv64"))] 221 #[allow(dead_code)] 222 #[inline] 223 pub fn try_write_irqsave(&self) -> Option<RwLockWriteGuard<T>> { 224 ProcessManager::preempt_disable(); 225 let irq_guard = unsafe { CurrentIrqArch::save_and_disable_irq() }; 226 let r = self.inner_try_write().map(|mut g| { 227 g.irq_guard = Some(irq_guard); 228 g 229 }); 230 if r.is_none() { 231 ProcessManager::preempt_enable(); 232 } 233 234 return r; 235 } 236 237 #[cfg(any(target_arch = "x86_64", target_arch = "riscv64"))] 238 #[allow(dead_code)] 239 fn inner_try_write(&self) -> Option<RwLockWriteGuard<T>> { 240 let res: bool = self 241 .lock 242 .compare_exchange(0, WRITER, Ordering::Acquire, Ordering::Relaxed) 243 .is_ok(); 244 //只有lock大小为0的时候能获得写者守卫 245 if res { 246 return Some(RwLockWriteGuard { 247 data: unsafe { &mut *self.data.get() }, 248 inner: self, 249 irq_guard: None, 250 }); 251 } else { 252 return None; 253 } 254 } 255 256 #[allow(dead_code)] 257 #[inline] 258 /// @brief 获得WRITER守卫 259 pub fn write(&self) -> RwLockWriteGuard<T> { 260 loop { 261 match self.try_write() { 262 Some(guard) => return guard, 263 None => spin_loop(), 264 } 265 } 266 } 267 268 #[allow(dead_code)] 269 #[inline] 270 /// @brief 获取WRITER守卫并关中断 271 pub fn write_irqsave(&self) -> RwLockWriteGuard<T> { 272 loop { 273 let irq_guard = unsafe { CurrentIrqArch::save_and_disable_irq() }; 274 match self.try_write() { 275 Some(mut guard) => { 276 guard.irq_guard = Some(irq_guard); 277 return guard; 278 } 279 None => spin_loop(), 280 } 281 } 282 } 283 284 #[allow(dead_code)] 285 #[inline] 286 /// @brief 尝试获得UPGRADER守卫 287 pub fn try_upgradeable_read(&self) -> Option<RwLockUpgradableGuard<T>> { 288 ProcessManager::preempt_disable(); 289 let r = self.inner_try_upgradeable_read(); 290 if r.is_none() { 291 ProcessManager::preempt_enable(); 292 } 293 294 return r; 295 } 296 297 #[allow(dead_code)] 298 pub fn try_upgradeable_read_irqsave(&self) -> Option<RwLockUpgradableGuard<T>> { 299 let irq_guard = unsafe { CurrentIrqArch::save_and_disable_irq() }; 300 ProcessManager::preempt_disable(); 301 let mut r = self.inner_try_upgradeable_read(); 302 if r.is_none() { 303 ProcessManager::preempt_enable(); 304 } else { 305 r.as_mut().unwrap().irq_guard = Some(irq_guard); 306 } 307 308 return r; 309 } 310 311 fn inner_try_upgradeable_read(&self) -> Option<RwLockUpgradableGuard<T>> { 312 // 获得UPGRADER守卫不需要查看读者位 313 // 如果获得读者锁失败,不需要撤回fetch_or的原子操作 314 if self.lock.fetch_or(UPGRADED, Ordering::Acquire) & (WRITER | UPGRADED) == 0 { 315 return Some(RwLockUpgradableGuard { 316 inner: self, 317 data: unsafe { &mut *self.data.get() }, 318 irq_guard: None, 319 }); 320 } else { 321 return None; 322 } 323 } 324 325 #[allow(dead_code)] 326 #[inline] 327 /// @brief 获得UPGRADER守卫 328 pub fn upgradeable_read(&self) -> RwLockUpgradableGuard<T> { 329 loop { 330 match self.try_upgradeable_read() { 331 Some(guard) => return guard, 332 None => spin_loop(), 333 } 334 } 335 } 336 337 #[inline] 338 /// @brief 获得UPGRADER守卫 339 pub fn upgradeable_read_irqsave(&self) -> RwLockUpgradableGuard<T> { 340 loop { 341 let irq_guard = unsafe { CurrentIrqArch::save_and_disable_irq() }; 342 match self.try_upgradeable_read() { 343 Some(mut guard) => { 344 guard.irq_guard = Some(irq_guard); 345 return guard; 346 } 347 None => spin_loop(), 348 } 349 } 350 } 351 352 #[allow(dead_code)] 353 #[inline] 354 //extremely unsafe behavior 355 /// @brief 强制减少READER数 356 pub unsafe fn force_read_decrement(&self) { 357 debug_assert!(self.lock.load(Ordering::Relaxed) & !WRITER > 0); 358 self.lock.fetch_sub(READER, Ordering::Release); 359 } 360 361 #[allow(dead_code)] 362 #[inline] 363 //extremely unsafe behavior 364 /// @brief 强制给WRITER解锁 365 pub unsafe fn force_write_unlock(&self) { 366 debug_assert_eq!(self.lock.load(Ordering::Relaxed) & !(WRITER | UPGRADED), 0); 367 self.lock.fetch_and(!(WRITER | UPGRADED), Ordering::Release); 368 } 369 370 #[allow(dead_code)] 371 pub unsafe fn get_mut(&mut self) -> &mut T { 372 unsafe { &mut *self.data.get() } 373 } 374 375 #[allow(dead_code)] 376 pub unsafe fn force_get_ref(&self) -> &T { 377 unsafe { &*self.data.get() } 378 } 379 } 380 381 impl<T: Default> Default for RwLock<T> { 382 fn default() -> Self { 383 Self::new(Default::default()) 384 } 385 } 386 387 /// @brief 由原有的值创建新的锁 388 impl<T> From<T> for RwLock<T> { 389 fn from(data: T) -> Self { 390 return Self::new(data); 391 } 392 } 393 394 impl<'rwlock, T> RwLockReadGuard<'rwlock, T> { 395 /// @brief 释放守卫,获得保护的值的不可变引用 396 /// 397 /// ## Safety 398 /// 399 /// 由于这样做可能导致守卫在另一个线程中被释放，从而导致pcb的preempt count不正确， 400 /// 因此必须小心的手动维护好preempt count。 401 /// 402 /// 并且，leak还可能导致锁的状态不正确。因此请仔细考虑是否真的需要使用这个函数。 403 #[allow(dead_code)] 404 #[inline] 405 pub unsafe fn leak(this: Self) -> &'rwlock T { 406 let this = ManuallyDrop::new(this); 407 return unsafe { &*this.data }; 408 } 409 } 410 411 impl<'rwlock, T> RwLockUpgradableGuard<'rwlock, T> { 412 #[allow(dead_code)] 413 #[inline] 414 /// @brief 尝试将UPGRADER守卫升级为WRITER守卫 415 pub fn try_upgrade(mut self) -> Result<RwLockWriteGuard<'rwlock, T>, Self> { 416 let res = self.inner.lock.compare_exchange( 417 UPGRADED, 418 WRITER, 419 Ordering::Acquire, 420 Ordering::Relaxed, 421 ); 422 //当且仅当只有UPGRADED守卫时可以升级 423 424 if res.is_ok() { 425 let inner = self.inner; 426 let irq_guard = self.irq_guard.take(); 427 mem::forget(self); 428 429 Ok(RwLockWriteGuard { 430 data: unsafe { &mut *inner.data.get() }, 431 inner, 432 irq_guard, 433 }) 434 } else { 435 Err(self) 436 } 437 } 438 439 #[allow(dead_code)] 440 #[inline] 441 /// @brief 将upgrader升级成writer 442 pub fn upgrade(mut self) -> RwLockWriteGuard<'rwlock, T> { 443 loop { 444 self = match self.try_upgrade() { 445 Ok(writeguard) => return writeguard, 446 Err(former) => former, 447 }; 448 449 spin_loop(); 450 } 451 } 452 453 #[allow(dead_code)] 454 #[inline] 455 /// @brief UPGRADER降级为READER 456 pub fn downgrade(mut self) -> RwLockReadGuard<'rwlock, T> { 457 while self.inner.current_reader().is_err() { 458 spin_loop(); 459 } 460 461 let inner: &RwLock<T> = self.inner; 462 let irq_guard = self.irq_guard.take(); 463 // 自动移去UPGRADED比特位 464 mem::drop(self); 465 466 RwLockReadGuard { 467 data: unsafe { &*inner.data.get() }, 468 lock: &inner.lock, 469 irq_guard, 470 } 471 } 472 473 #[allow(dead_code)] 474 #[inline] 475 /// @brief 返回内部数据的引用,消除守卫 476 /// 477 /// ## Safety 478 /// 479 /// 由于这样做可能导致守卫在另一个线程中被释放，从而导致pcb的preempt count不正确， 480 /// 因此必须小心的手动维护好preempt count。 481 /// 482 /// 并且，leak还可能导致锁的状态不正确。因此请仔细考虑是否真的需要使用这个函数。 483 pub unsafe fn leak(this: Self) -> &'rwlock T { 484 let this: ManuallyDrop<RwLockUpgradableGuard<'_, T>> = ManuallyDrop::new(this); 485 486 unsafe { &*this.data } 487 } 488 } 489 490 impl<'rwlock, T> RwLockWriteGuard<'rwlock, T> { 491 #[allow(dead_code)] 492 #[inline] 493 /// @brief 返回内部数据的引用,消除守卫 494 /// 495 /// ## Safety 496 /// 497 /// 由于这样做可能导致守卫在另一个线程中被释放，从而导致pcb的preempt count不正确， 498 /// 因此必须小心的手动维护好preempt count。 499 /// 500 /// 并且，leak还可能导致锁的状态不正确。因此请仔细考虑是否真的需要使用这个函数。 501 pub unsafe fn leak(this: Self) -> &'rwlock T { 502 let this = ManuallyDrop::new(this); 503 504 return unsafe { &*this.data }; 505 } 506 507 #[allow(dead_code)] 508 #[inline] 509 /// @brief 将WRITER降级为READER 510 pub fn downgrade(mut self) -> RwLockReadGuard<'rwlock, T> { 511 while self.inner.current_reader().is_err() { 512 spin_loop(); 513 } 514 //本质上来说绝对保证没有任何读者 515 516 let inner = self.inner; 517 let irq_guard = self.irq_guard.take(); 518 mem::drop(self); 519 520 return RwLockReadGuard { 521 data: unsafe { &*inner.data.get() }, 522 lock: &inner.lock, 523 irq_guard, 524 }; 525 } 526 527 #[allow(dead_code)] 528 #[inline] 529 /// @brief 将WRITER降级为UPGRADER 530 pub fn downgrade_to_upgradeable(mut self) -> RwLockUpgradableGuard<'rwlock, T> { 531 debug_assert_eq!( 532 self.inner.lock.load(Ordering::Acquire) & (WRITER | UPGRADED), 533 WRITER 534 ); 535 536 self.inner.lock.store(UPGRADED, Ordering::Release); 537 538 let inner = self.inner; 539 540 let irq_guard = self.irq_guard.take(); 541 mem::forget(self); 542 543 return RwLockUpgradableGuard { 544 inner, 545 data: unsafe { &*inner.data.get() }, 546 irq_guard, 547 }; 548 } 549 } 550 551 impl<'rwlock, T> Deref for RwLockReadGuard<'rwlock, T> { 552 type Target = T; 553 554 fn deref(&self) -> &Self::Target { 555 return unsafe { &*self.data }; 556 } 557 } 558 559 impl<'rwlock, T> Deref for RwLockUpgradableGuard<'rwlock, T> { 560 type Target = T; 561 562 fn deref(&self) -> &Self::Target { 563 return unsafe { &*self.data }; 564 } 565 } 566 567 impl<'rwlock, T> Deref for RwLockWriteGuard<'rwlock, T> { 568 type Target = T; 569 570 fn deref(&self) -> &Self::Target { 571 return unsafe { &*self.data }; 572 } 573 } 574 575 impl<'rwlock, T> DerefMut for RwLockWriteGuard<'rwlock, T> { 576 fn deref_mut(&mut self) -> &mut Self::Target { 577 return unsafe { &mut *self.data }; 578 } 579 } 580 581 impl<'rwlock, T> Drop for RwLockReadGuard<'rwlock, T> { 582 fn drop(&mut self) { 583 debug_assert!(self.lock.load(Ordering::Relaxed) & !(WRITER | UPGRADED) > 0); 584 self.lock.fetch_sub(READER, Ordering::Release); 585 ProcessManager::preempt_enable(); 586 } 587 } 588 589 impl<'rwlock, T> Drop for RwLockUpgradableGuard<'rwlock, T> { 590 fn drop(&mut self) { 591 debug_assert_eq!( 592 self.inner.lock.load(Ordering::Relaxed) & (WRITER | UPGRADED), 593 UPGRADED 594 ); 595 self.inner.lock.fetch_sub(UPGRADED, Ordering::AcqRel); 596 ProcessManager::preempt_enable(); 597 //这里为啥要AcqRel? Release应该就行了? 598 } 599 } 600 601 impl<'rwlock, T> Drop for RwLockWriteGuard<'rwlock, T> { 602 fn drop(&mut self) { 603 debug_assert_eq!(self.inner.lock.load(Ordering::Relaxed) & WRITER, WRITER); 604 self.inner 605 .lock 606 .fetch_and(!(WRITER | UPGRADED), Ordering::Release); 607 self.irq_guard.take(); 608 ProcessManager::preempt_enable(); 609 } 610 } 611