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