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