rwlock.rs 18 KB

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