linux-kernel.bell 3.1 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384
  1. // SPDX-License-Identifier: GPL-2.0+
  2. (*
  3. * Copyright (C) 2015 Jade Alglave <j.alglave@ucl.ac.uk>,
  4. * Copyright (C) 2016 Luc Maranget <luc.maranget@inria.fr> for Inria
  5. * Copyright (C) 2017 Alan Stern <stern@rowland.harvard.edu>,
  6. * Andrea Parri <parri.andrea@gmail.com>
  7. *
  8. * An earlier version of this file appeared in the companion webpage for
  9. * "Frightening small children and disconcerting grown-ups: Concurrency
  10. * in the Linux kernel" by Alglave, Maranget, McKenney, Parri, and Stern,
  11. * which appeared in ASPLOS 2018.
  12. *)
  13. "Linux-kernel memory consistency model"
  14. enum Accesses = 'once (*READ_ONCE,WRITE_ONCE*) ||
  15. 'release (*smp_store_release*) ||
  16. 'acquire (*smp_load_acquire*) ||
  17. 'noreturn (* R of non-return RMW *)
  18. instructions R[{'once,'acquire,'noreturn}]
  19. instructions W[{'once,'release}]
  20. instructions RMW[{'once,'acquire,'release}]
  21. enum Barriers = 'wmb (*smp_wmb*) ||
  22. 'rmb (*smp_rmb*) ||
  23. 'mb (*smp_mb*) ||
  24. 'barrier (*barrier*) ||
  25. 'rcu-lock (*rcu_read_lock*) ||
  26. 'rcu-unlock (*rcu_read_unlock*) ||
  27. 'sync-rcu (*synchronize_rcu*) ||
  28. 'before-atomic (*smp_mb__before_atomic*) ||
  29. 'after-atomic (*smp_mb__after_atomic*) ||
  30. 'after-spinlock (*smp_mb__after_spinlock*) ||
  31. 'after-unlock-lock (*smp_mb__after_unlock_lock*)
  32. instructions F[Barriers]
  33. (* SRCU *)
  34. enum SRCU = 'srcu-lock || 'srcu-unlock || 'sync-srcu
  35. instructions SRCU[SRCU]
  36. (* All srcu events *)
  37. let Srcu = Srcu-lock | Srcu-unlock | Sync-srcu
  38. (* Compute matching pairs of nested Rcu-lock and Rcu-unlock *)
  39. let rcu-rscs = let rec
  40. unmatched-locks = Rcu-lock \ domain(matched)
  41. and unmatched-unlocks = Rcu-unlock \ range(matched)
  42. and unmatched = unmatched-locks | unmatched-unlocks
  43. and unmatched-po = [unmatched] ; po ; [unmatched]
  44. and unmatched-locks-to-unlocks =
  45. [unmatched-locks] ; po ; [unmatched-unlocks]
  46. and matched = matched | (unmatched-locks-to-unlocks \
  47. (unmatched-po ; unmatched-po))
  48. in matched
  49. (* Validate nesting *)
  50. flag ~empty Rcu-lock \ domain(rcu-rscs) as unbalanced-rcu-locking
  51. flag ~empty Rcu-unlock \ range(rcu-rscs) as unbalanced-rcu-locking
  52. (* Compute matching pairs of nested Srcu-lock and Srcu-unlock *)
  53. let srcu-rscs = let rec
  54. unmatched-locks = Srcu-lock \ domain(matched)
  55. and unmatched-unlocks = Srcu-unlock \ range(matched)
  56. and unmatched = unmatched-locks | unmatched-unlocks
  57. and unmatched-po = ([unmatched] ; po ; [unmatched]) & loc
  58. and unmatched-locks-to-unlocks =
  59. ([unmatched-locks] ; po ; [unmatched-unlocks]) & loc
  60. and matched = matched | (unmatched-locks-to-unlocks \
  61. (unmatched-po ; unmatched-po))
  62. in matched
  63. (* Validate nesting *)
  64. flag ~empty Srcu-lock \ domain(srcu-rscs) as unbalanced-srcu-locking
  65. flag ~empty Srcu-unlock \ range(srcu-rscs) as unbalanced-srcu-locking
  66. (* Check for use of synchronize_srcu() inside an RCU critical section *)
  67. flag ~empty rcu-rscs & (po ; [Sync-srcu] ; po) as invalid-sleep
  68. (* Validate SRCU dynamic match *)
  69. flag ~empty different-values(srcu-rscs) as srcu-bad-nesting
  70. (* Compute marked and plain memory accesses *)
  71. let Marked = (~M) | IW | Once | Release | Acquire | domain(rmw) | range(rmw) |
  72. LKR | LKW | UL | LF | RL | RU
  73. let Plain = M \ Marked