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 let value; 134 135 if reader_value.is_err() { 136 return None; //获取失败 137 } else { 138 value = reader_value.unwrap(); 139 } 140 141 //判断有没有writer和upgrader 142 //注意, 若upgrader存在,已经存在的读者继续占有锁,但新读者不允许获得锁 143 if value & (WRITER | UPGRADED) != 0 { 144 self.lock.fetch_sub(READER, Ordering::Release); 145 return None; 146 } else { 147 return Some(RwLockReadGuard { 148 data: unsafe { &*self.data.get() }, 149 lock: &self.lock, 150 irq_guard: None, 151 }); 152 } 153 } 154 155 #[allow(dead_code)] 156 #[inline] 157 /// @brief 获得READER的守卫 158 pub fn read(&self) -> RwLockReadGuard<T> { 159 loop { 160 match self.try_read() { 161 Some(guard) => return guard, 162 None => spin_loop(), 163 } 164 } //忙等待 165 } 166 167 /// 关中断并获取读者守卫 168 pub fn read_irqsave(&self) -> RwLockReadGuard<T> { 169 loop { 170 let irq_guard = unsafe { CurrentIrqArch::save_and_disable_irq() }; 171 match self.try_read() { 172 Some(mut guard) => { 173 guard.irq_guard = Some(irq_guard); 174 return guard; 175 } 176 None => spin_loop(), 177 } 178 } 179 } 180 181 /// 尝试关闭中断并获取读者守卫 182 pub fn try_read_irqsave(&self) -> Option<RwLockReadGuard<T>> { 183 let irq_guard = unsafe { CurrentIrqArch::save_and_disable_irq() }; 184 if let Some(mut guard) = self.try_read() { 185 guard.irq_guard = Some(irq_guard); 186 return Some(guard); 187 } else { 188 return None; 189 } 190 } 191 192 #[allow(dead_code)] 193 #[inline] 194 /// @brief 获取读者+UPGRADER的数量, 不能保证能否获得同步值 195 pub fn reader_count(&self) -> u32 { 196 let state = self.lock.load(Ordering::Relaxed); 197 return state / READER + (state & UPGRADED) / UPGRADED; 198 } 199 200 #[allow(dead_code)] 201 #[inline] 202 /// @brief 获取写者数量,不能保证能否获得同步值 203 pub fn writer_count(&self) -> u32 { 204 return (self.lock.load(Ordering::Relaxed) & WRITER) / WRITER; 205 } 206 207 #[cfg(any(target_arch = "x86_64", target_arch = "riscv64"))] 208 #[allow(dead_code)] 209 #[inline] 210 /// @brief 尝试获得WRITER守卫 211 pub fn try_write(&self) -> Option<RwLockWriteGuard<T>> { 212 ProcessManager::preempt_disable(); 213 let r = self.inner_try_write(); 214 if r.is_none() { 215 ProcessManager::preempt_enable(); 216 } 217 218 return r; 219 } //当架构为arm时,有些代码需要作出调整compare_exchange=>compare_exchange_weak 220 221 #[cfg(any(target_arch = "x86_64", target_arch = "riscv64"))] 222 #[allow(dead_code)] 223 fn inner_try_write(&self) -> Option<RwLockWriteGuard<T>> { 224 let res: bool = self 225 .lock 226 .compare_exchange(0, WRITER, Ordering::Acquire, Ordering::Relaxed) 227 .is_ok(); 228 //只有lock大小为0的时候能获得写者守卫 229 if res { 230 return Some(RwLockWriteGuard { 231 data: unsafe { &mut *self.data.get() }, 232 inner: self, 233 irq_guard: None, 234 }); 235 } else { 236 return None; 237 } 238 } 239 240 #[allow(dead_code)] 241 #[inline] 242 /// @brief 获得WRITER守卫 243 pub fn write(&self) -> RwLockWriteGuard<T> { 244 loop { 245 match self.try_write() { 246 Some(guard) => return guard, 247 None => spin_loop(), 248 } 249 } 250 } 251 252 #[allow(dead_code)] 253 #[inline] 254 /// @brief 获取WRITER守卫并关中断 255 pub fn write_irqsave(&self) -> RwLockWriteGuard<T> { 256 loop { 257 let irq_guard = unsafe { CurrentIrqArch::save_and_disable_irq() }; 258 match self.try_write() { 259 Some(mut guard) => { 260 guard.irq_guard = Some(irq_guard); 261 return guard; 262 } 263 None => spin_loop(), 264 } 265 } 266 } 267 268 #[allow(dead_code)] 269 #[inline] 270 /// @brief 尝试获得UPGRADER守卫 271 pub fn try_upgradeable_read(&self) -> Option<RwLockUpgradableGuard<T>> { 272 ProcessManager::preempt_disable(); 273 let r = self.inner_try_upgradeable_read(); 274 if r.is_none() { 275 ProcessManager::preempt_enable(); 276 } 277 278 return r; 279 } 280 281 #[allow(dead_code)] 282 pub fn try_upgradeable_read_irqsave(&self) -> Option<RwLockUpgradableGuard<T>> { 283 let irq_guard = unsafe { CurrentIrqArch::save_and_disable_irq() }; 284 ProcessManager::preempt_disable(); 285 let mut r = self.inner_try_upgradeable_read(); 286 if r.is_none() { 287 ProcessManager::preempt_enable(); 288 } else { 289 r.as_mut().unwrap().irq_guard = Some(irq_guard); 290 } 291 292 return r; 293 } 294 295 fn inner_try_upgradeable_read(&self) -> Option<RwLockUpgradableGuard<T>> { 296 // 获得UPGRADER守卫不需要查看读者位 297 // 如果获得读者锁失败,不需要撤回fetch_or的原子操作 298 if self.lock.fetch_or(UPGRADED, Ordering::Acquire) & (WRITER | UPGRADED) == 0 { 299 return Some(RwLockUpgradableGuard { 300 inner: self, 301 data: unsafe { &mut *self.data.get() }, 302 irq_guard: None, 303 }); 304 } else { 305 return None; 306 } 307 } 308 309 #[allow(dead_code)] 310 #[inline] 311 /// @brief 获得UPGRADER守卫 312 pub fn upgradeable_read(&self) -> RwLockUpgradableGuard<T> { 313 loop { 314 match self.try_upgradeable_read() { 315 Some(guard) => return guard, 316 None => spin_loop(), 317 } 318 } 319 } 320 321 #[inline] 322 /// @brief 获得UPGRADER守卫 323 pub fn upgradeable_read_irqsave(&self) -> RwLockUpgradableGuard<T> { 324 loop { 325 let irq_guard = unsafe { CurrentIrqArch::save_and_disable_irq() }; 326 match self.try_upgradeable_read() { 327 Some(mut guard) => { 328 guard.irq_guard = Some(irq_guard); 329 return guard; 330 } 331 None => spin_loop(), 332 } 333 } 334 } 335 336 #[allow(dead_code)] 337 #[inline] 338 //extremely unsafe behavior 339 /// @brief 强制减少READER数 340 pub unsafe fn force_read_decrement(&self) { 341 debug_assert!(self.lock.load(Ordering::Relaxed) & !WRITER > 0); 342 self.lock.fetch_sub(READER, Ordering::Release); 343 } 344 345 #[allow(dead_code)] 346 #[inline] 347 //extremely unsafe behavior 348 /// @brief 强制给WRITER解锁 349 pub unsafe fn force_write_unlock(&self) { 350 debug_assert_eq!(self.lock.load(Ordering::Relaxed) & !(WRITER | UPGRADED), 0); 351 self.lock.fetch_and(!(WRITER | UPGRADED), Ordering::Release); 352 } 353 354 #[allow(dead_code)] 355 pub unsafe fn get_mut(&mut self) -> &mut T { 356 unsafe { &mut *self.data.get() } 357 } 358 } 359 360 impl<T: Default> Default for RwLock<T> { 361 fn default() -> Self { 362 Self::new(Default::default()) 363 } 364 } 365 366 /// @brief 由原有的值创建新的锁 367 impl<T> From<T> for RwLock<T> { 368 fn from(data: T) -> Self { 369 return Self::new(data); 370 } 371 } 372 373 impl<'rwlock, T> RwLockReadGuard<'rwlock, T> { 374 /// @brief 释放守卫,获得保护的值的不可变引用 375 /// 376 /// ## Safety 377 /// 378 /// 由于这样做可能导致守卫在另一个线程中被释放，从而导致pcb的preempt count不正确， 379 /// 因此必须小心的手动维护好preempt count。 380 /// 381 /// 并且，leak还可能导致锁的状态不正确。因此请仔细考虑是否真的需要使用这个函数。 382 #[allow(dead_code)] 383 #[inline] 384 pub unsafe fn leak(this: Self) -> &'rwlock T { 385 let this = ManuallyDrop::new(this); 386 return unsafe { &*this.data }; 387 } 388 } 389 390 impl<'rwlock, T> RwLockUpgradableGuard<'rwlock, T> { 391 #[allow(dead_code)] 392 #[inline] 393 /// @brief 尝试将UPGRADER守卫升级为WRITER守卫 394 pub fn try_upgrade(mut self) -> Result<RwLockWriteGuard<'rwlock, T>, Self> { 395 let res = self.inner.lock.compare_exchange( 396 UPGRADED, 397 WRITER, 398 Ordering::Acquire, 399 Ordering::Relaxed, 400 ); 401 //当且仅当只有UPGRADED守卫时可以升级 402 403 if res.is_ok() { 404 let inner = self.inner; 405 let irq_guard = self.irq_guard.take(); 406 mem::forget(self); 407 408 Ok(RwLockWriteGuard { 409 data: unsafe { &mut *inner.data.get() }, 410 inner, 411 irq_guard, 412 }) 413 } else { 414 Err(self) 415 } 416 } 417 418 #[allow(dead_code)] 419 #[inline] 420 /// @brief 将upgrader升级成writer 421 pub fn upgrade(mut self) -> RwLockWriteGuard<'rwlock, T> { 422 loop { 423 self = match self.try_upgrade() { 424 Ok(writeguard) => return writeguard, 425 Err(former) => former, 426 }; 427 428 spin_loop(); 429 } 430 } 431 432 #[allow(dead_code)] 433 #[inline] 434 /// @brief UPGRADER降级为READER 435 pub fn downgrade(mut self) -> RwLockReadGuard<'rwlock, T> { 436 while self.inner.current_reader().is_err() { 437 spin_loop(); 438 } 439 440 let inner: &RwLock<T> = self.inner; 441 let irq_guard = self.irq_guard.take(); 442 // 自动移去UPGRADED比特位 443 mem::drop(self); 444 445 RwLockReadGuard { 446 data: unsafe { &*inner.data.get() }, 447 lock: &inner.lock, 448 irq_guard, 449 } 450 } 451 452 #[allow(dead_code)] 453 #[inline] 454 /// @brief 返回内部数据的引用,消除守卫 455 /// 456 /// ## Safety 457 /// 458 /// 由于这样做可能导致守卫在另一个线程中被释放，从而导致pcb的preempt count不正确， 459 /// 因此必须小心的手动维护好preempt count。 460 /// 461 /// 并且，leak还可能导致锁的状态不正确。因此请仔细考虑是否真的需要使用这个函数。 462 pub unsafe fn leak(this: Self) -> &'rwlock T { 463 let this: ManuallyDrop<RwLockUpgradableGuard<'_, T>> = ManuallyDrop::new(this); 464 465 unsafe { &*this.data } 466 } 467 } 468 469 impl<'rwlock, T> RwLockWriteGuard<'rwlock, T> { 470 #[allow(dead_code)] 471 #[inline] 472 /// @brief 返回内部数据的引用,消除守卫 473 /// 474 /// ## Safety 475 /// 476 /// 由于这样做可能导致守卫在另一个线程中被释放，从而导致pcb的preempt count不正确， 477 /// 因此必须小心的手动维护好preempt count。 478 /// 479 /// 并且，leak还可能导致锁的状态不正确。因此请仔细考虑是否真的需要使用这个函数。 480 pub unsafe fn leak(this: Self) -> &'rwlock T { 481 let this = ManuallyDrop::new(this); 482 483 return unsafe { &*this.data }; 484 } 485 486 #[allow(dead_code)] 487 #[inline] 488 /// @brief 将WRITER降级为READER 489 pub fn downgrade(mut self) -> RwLockReadGuard<'rwlock, T> { 490 while self.inner.current_reader().is_err() { 491 spin_loop(); 492 } 493 //本质上来说绝对保证没有任何读者 494 495 let inner = self.inner; 496 let irq_guard = self.irq_guard.take(); 497 mem::drop(self); 498 499 return RwLockReadGuard { 500 data: unsafe { &*inner.data.get() }, 501 lock: &inner.lock, 502 irq_guard, 503 }; 504 } 505 506 #[allow(dead_code)] 507 #[inline] 508 /// @brief 将WRITER降级为UPGRADER 509 pub fn downgrade_to_upgradeable(mut self) -> RwLockUpgradableGuard<'rwlock, T> { 510 debug_assert_eq!( 511 self.inner.lock.load(Ordering::Acquire) & (WRITER | UPGRADED), 512 WRITER 513 ); 514 515 self.inner.lock.store(UPGRADED, Ordering::Release); 516 517 let inner = self.inner; 518 519 let irq_guard = self.irq_guard.take(); 520 mem::forget(self); 521 522 return RwLockUpgradableGuard { 523 inner, 524 data: unsafe { &*inner.data.get() }, 525 irq_guard, 526 }; 527 } 528 } 529 530 impl<'rwlock, T> Deref for RwLockReadGuard<'rwlock, T> { 531 type Target = T; 532 533 fn deref(&self) -> &Self::Target { 534 return unsafe { &*self.data }; 535 } 536 } 537 538 impl<'rwlock, T> Deref for RwLockUpgradableGuard<'rwlock, T> { 539 type Target = T; 540 541 fn deref(&self) -> &Self::Target { 542 return unsafe { &*self.data }; 543 } 544 } 545 546 impl<'rwlock, T> Deref for RwLockWriteGuard<'rwlock, T> { 547 type Target = T; 548 549 fn deref(&self) -> &Self::Target { 550 return unsafe { &*self.data }; 551 } 552 } 553 554 impl<'rwlock, T> DerefMut for RwLockWriteGuard<'rwlock, T> { 555 fn deref_mut(&mut self) -> &mut Self::Target { 556 return unsafe { &mut *self.data }; 557 } 558 } 559 560 impl<'rwlock, T> Drop for RwLockReadGuard<'rwlock, T> { 561 fn drop(&mut self) { 562 debug_assert!(self.lock.load(Ordering::Relaxed) & !(WRITER | UPGRADED) > 0); 563 self.lock.fetch_sub(READER, Ordering::Release); 564 ProcessManager::preempt_enable(); 565 } 566 } 567 568 impl<'rwlock, T> Drop for RwLockUpgradableGuard<'rwlock, T> { 569 fn drop(&mut self) { 570 debug_assert_eq!( 571 self.inner.lock.load(Ordering::Relaxed) & (WRITER | UPGRADED), 572 UPGRADED 573 ); 574 self.inner.lock.fetch_sub(UPGRADED, Ordering::AcqRel); 575 ProcessManager::preempt_enable(); 576 //这里为啥要AcqRel? Release应该就行了? 577 } 578 } 579 580 impl<'rwlock, T> Drop for RwLockWriteGuard<'rwlock, T> { 581 fn drop(&mut self) { 582 debug_assert_eq!(self.inner.lock.load(Ordering::Relaxed) & WRITER, WRITER); 583 self.inner 584 .lock 585 .fetch_and(!(WRITER | UPGRADED), Ordering::Release); 586 self.irq_guard.take(); 587 ProcessManager::preempt_enable(); 588 } 589 } 590