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(target_arch = "x86_64")] 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(target_arch = "x86_64")] 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 fn inner_try_upgradeable_read(&self) -> Option<RwLockUpgradableGuard<T>> { 269 // 获得UPGRADER守卫不需要查看读者位 270 // 如果获得读者锁失败,不需要撤回fetch_or的原子操作 271 if self.lock.fetch_or(UPGRADED, Ordering::Acquire) & (WRITER | UPGRADED) == 0 { 272 return Some(RwLockUpgradableGuard { 273 inner: self, 274 data: unsafe { &mut *self.data.get() }, 275 irq_guard: None, 276 }); 277 } else { 278 return None; 279 } 280 } 281 282 #[allow(dead_code)] 283 #[inline] 284 /// @brief 获得UPGRADER守卫 285 pub fn upgradeable_read(&self) -> RwLockUpgradableGuard<T> { 286 loop { 287 match self.try_upgradeable_read() { 288 Some(guard) => return guard, 289 None => spin_loop(), 290 } 291 } 292 } 293 294 #[inline] 295 /// @brief 获得UPGRADER守卫 296 pub fn upgradeable_read_irqsave(&self) -> RwLockUpgradableGuard<T> { 297 loop { 298 let irq_guard = unsafe { CurrentIrqArch::save_and_disable_irq() }; 299 match self.try_upgradeable_read() { 300 Some(mut guard) => { 301 guard.irq_guard = Some(irq_guard); 302 return guard; 303 } 304 None => spin_loop(), 305 } 306 } 307 } 308 309 #[allow(dead_code)] 310 #[inline] 311 //extremely unsafe behavior 312 /// @brief 强制减少READER数 313 pub unsafe fn force_read_decrement(&self) { 314 debug_assert!(self.lock.load(Ordering::Relaxed) & !WRITER > 0); 315 self.lock.fetch_sub(READER, Ordering::Release); 316 } 317 318 #[allow(dead_code)] 319 #[inline] 320 //extremely unsafe behavior 321 /// @brief 强制给WRITER解锁 322 pub unsafe fn force_write_unlock(&self) { 323 debug_assert_eq!(self.lock.load(Ordering::Relaxed) & !(WRITER | UPGRADED), 0); 324 self.lock.fetch_and(!(WRITER | UPGRADED), Ordering::Release); 325 } 326 327 #[allow(dead_code)] 328 pub unsafe fn get_mut(&mut self) -> &mut T { 329 unsafe { &mut *self.data.get() } 330 } 331 } 332 333 impl<T: Default> Default for RwLock<T> { 334 fn default() -> Self { 335 Self::new(Default::default()) 336 } 337 } 338 339 /// @brief 由原有的值创建新的锁 340 impl<T> From<T> for RwLock<T> { 341 fn from(data: T) -> Self { 342 return Self::new(data); 343 } 344 } 345 346 impl<'rwlock, T> RwLockReadGuard<'rwlock, T> { 347 /// @brief 释放守卫,获得保护的值的不可变引用 348 /// 349 /// ## Safety 350 /// 351 /// 由于这样做可能导致守卫在另一个线程中被释放，从而导致pcb的preempt count不正确， 352 /// 因此必须小心的手动维护好preempt count。 353 /// 354 /// 并且，leak还可能导致锁的状态不正确。因此请仔细考虑是否真的需要使用这个函数。 355 #[allow(dead_code)] 356 #[inline] 357 pub unsafe fn leak(this: Self) -> &'rwlock T { 358 let this = ManuallyDrop::new(this); 359 return unsafe { &*this.data }; 360 } 361 } 362 363 impl<'rwlock, T> RwLockUpgradableGuard<'rwlock, T> { 364 #[allow(dead_code)] 365 #[inline] 366 /// @brief 尝试将UPGRADER守卫升级为WRITER守卫 367 pub fn try_upgrade(mut self) -> Result<RwLockWriteGuard<'rwlock, T>, Self> { 368 let res = self.inner.lock.compare_exchange( 369 UPGRADED, 370 WRITER, 371 Ordering::Acquire, 372 Ordering::Relaxed, 373 ); 374 //当且仅当只有UPGRADED守卫时可以升级 375 376 if res.is_ok() { 377 let inner = self.inner; 378 let irq_guard = self.irq_guard.take(); 379 mem::forget(self); 380 381 Ok(RwLockWriteGuard { 382 data: unsafe { &mut *inner.data.get() }, 383 inner, 384 irq_guard, 385 }) 386 } else { 387 Err(self) 388 } 389 } 390 391 #[allow(dead_code)] 392 #[inline] 393 /// @brief 将upgrader升级成writer 394 pub fn upgrade(mut self) -> RwLockWriteGuard<'rwlock, T> { 395 loop { 396 self = match self.try_upgrade() { 397 Ok(writeguard) => return writeguard, 398 Err(former) => former, 399 }; 400 401 spin_loop(); 402 } 403 } 404 405 #[allow(dead_code)] 406 #[inline] 407 /// @brief UPGRADER降级为READER 408 pub fn downgrade(mut self) -> RwLockReadGuard<'rwlock, T> { 409 while self.inner.current_reader().is_err() { 410 spin_loop(); 411 } 412 413 let inner: &RwLock<T> = self.inner; 414 let irq_guard = self.irq_guard.take(); 415 // 自动移去UPGRADED比特位 416 mem::drop(self); 417 418 RwLockReadGuard { 419 data: unsafe { &*inner.data.get() }, 420 lock: &inner.lock, 421 irq_guard, 422 } 423 } 424 425 #[allow(dead_code)] 426 #[inline] 427 /// @brief 返回内部数据的引用,消除守卫 428 /// 429 /// ## Safety 430 /// 431 /// 由于这样做可能导致守卫在另一个线程中被释放，从而导致pcb的preempt count不正确， 432 /// 因此必须小心的手动维护好preempt count。 433 /// 434 /// 并且，leak还可能导致锁的状态不正确。因此请仔细考虑是否真的需要使用这个函数。 435 pub unsafe fn leak(this: Self) -> &'rwlock T { 436 let this: ManuallyDrop<RwLockUpgradableGuard<'_, T>> = ManuallyDrop::new(this); 437 438 unsafe { &*this.data } 439 } 440 } 441 442 impl<'rwlock, T> RwLockWriteGuard<'rwlock, T> { 443 #[allow(dead_code)] 444 #[inline] 445 /// @brief 返回内部数据的引用,消除守卫 446 /// 447 /// ## Safety 448 /// 449 /// 由于这样做可能导致守卫在另一个线程中被释放，从而导致pcb的preempt count不正确， 450 /// 因此必须小心的手动维护好preempt count。 451 /// 452 /// 并且，leak还可能导致锁的状态不正确。因此请仔细考虑是否真的需要使用这个函数。 453 pub unsafe fn leak(this: Self) -> &'rwlock T { 454 let this = ManuallyDrop::new(this); 455 456 return unsafe { &*this.data }; 457 } 458 459 #[allow(dead_code)] 460 #[inline] 461 /// @brief 将WRITER降级为READER 462 pub fn downgrade(mut self) -> RwLockReadGuard<'rwlock, T> { 463 while self.inner.current_reader().is_err() { 464 spin_loop(); 465 } 466 //本质上来说绝对保证没有任何读者 467 468 let inner = self.inner; 469 let irq_guard = self.irq_guard.take(); 470 mem::drop(self); 471 472 return RwLockReadGuard { 473 data: unsafe { &*inner.data.get() }, 474 lock: &inner.lock, 475 irq_guard, 476 }; 477 } 478 479 #[allow(dead_code)] 480 #[inline] 481 /// @brief 将WRITER降级为UPGRADER 482 pub fn downgrade_to_upgradeable(mut self) -> RwLockUpgradableGuard<'rwlock, T> { 483 debug_assert_eq!( 484 self.inner.lock.load(Ordering::Acquire) & (WRITER | UPGRADED), 485 WRITER 486 ); 487 488 self.inner.lock.store(UPGRADED, Ordering::Release); 489 490 let inner = self.inner; 491 492 let irq_guard = self.irq_guard.take(); 493 mem::forget(self); 494 495 return RwLockUpgradableGuard { 496 inner, 497 data: unsafe { &*inner.data.get() }, 498 irq_guard, 499 }; 500 } 501 } 502 503 impl<'rwlock, T> Deref for RwLockReadGuard<'rwlock, T> { 504 type Target = T; 505 506 fn deref(&self) -> &Self::Target { 507 return unsafe { &*self.data }; 508 } 509 } 510 511 impl<'rwlock, T> Deref for RwLockUpgradableGuard<'rwlock, T> { 512 type Target = T; 513 514 fn deref(&self) -> &Self::Target { 515 return unsafe { &*self.data }; 516 } 517 } 518 519 impl<'rwlock, T> Deref for RwLockWriteGuard<'rwlock, T> { 520 type Target = T; 521 522 fn deref(&self) -> &Self::Target { 523 return unsafe { &*self.data }; 524 } 525 } 526 527 impl<'rwlock, T> DerefMut for RwLockWriteGuard<'rwlock, T> { 528 fn deref_mut(&mut self) -> &mut Self::Target { 529 return unsafe { &mut *self.data }; 530 } 531 } 532 533 impl<'rwlock, T> Drop for RwLockReadGuard<'rwlock, T> { 534 fn drop(&mut self) { 535 debug_assert!(self.lock.load(Ordering::Relaxed) & !(WRITER | UPGRADED) > 0); 536 self.lock.fetch_sub(READER, Ordering::Release); 537 ProcessManager::preempt_enable(); 538 } 539 } 540 541 impl<'rwlock, T> Drop for RwLockUpgradableGuard<'rwlock, T> { 542 fn drop(&mut self) { 543 debug_assert_eq!( 544 self.inner.lock.load(Ordering::Relaxed) & (WRITER | UPGRADED), 545 UPGRADED 546 ); 547 self.inner.lock.fetch_sub(UPGRADED, Ordering::AcqRel); 548 ProcessManager::preempt_enable(); 549 //这里为啥要AcqRel? Release应该就行了? 550 } 551 } 552 553 impl<'rwlock, T> Drop for RwLockWriteGuard<'rwlock, T> { 554 fn drop(&mut self) { 555 debug_assert_eq!(self.inner.lock.load(Ordering::Relaxed) & WRITER, WRITER); 556 self.inner 557 .lock 558 .fetch_and(!(WRITER | UPGRADED), Ordering::Release); 559 self.irq_guard.take(); 560 ProcessManager::preempt_enable(); 561 } 562 } 563