* [PATCH v2] tools/memory-model: Document herd7 (abstract) representation
@ 2024-06-05 13:49 Andrea Parri
2024-06-05 15:53 ` Alan Stern
0 siblings, 1 reply; 5+ messages in thread
From: Andrea Parri @ 2024-06-05 13:49 UTC (permalink / raw)
To: stern, will, peterz, boqun.feng, npiggin, dhowells, j.alglave,
luc.maranget, paulmck, akiyks, dlustig, joel
Cc: linux-kernel, linux-arch, hernan.poncedeleon, jonas.oberhauser,
Andrea Parri
tools/memory-model/ and herdtool7 are closely linked: the latter is
responsible for (pre)processing each C-like macro of a litmus test,
and for providing the LKMM with a set of events, or "representation",
corresponding to the given macro. Provide herd-representation.txt
to document the representations of the concurrency macros, following
their "classification" in Documentation/atomic_t.txt.
Suggested-by: Hernan Ponce de Leon <hernan.poncedeleon@huaweicloud.com>
Signed-off-by: Andrea Parri <parri.andrea@gmail.com>
---
Changes since v1[1]:
- add legenda/notations
- add some SRCU, locking macros
- update formatting of failure cases
- update README file
[1] https://lore.kernel.org/lkml/20240524151356.236071-1-parri.andrea@gmail.com/
tools/memory-model/Documentation/README | 7 +-
.../Documentation/herd-representation.txt | 107 ++++++++++++++++++
2 files changed, 113 insertions(+), 1 deletion(-)
create mode 100644 tools/memory-model/Documentation/herd-representation.txt
diff --git a/tools/memory-model/Documentation/README b/tools/memory-model/Documentation/README
index db90a26dbdf40..1f73014cc48a3 100644
--- a/tools/memory-model/Documentation/README
+++ b/tools/memory-model/Documentation/README
@@ -33,7 +33,8 @@ o You are familiar with Linux-kernel concurrency and the use of
o You are familiar with Linux-kernel concurrency and the use
of LKMM, and would like to learn about LKMM's requirements,
- rationale, and implementation: explanation.txt
+ rationale, and implementation: explanation.txt and
+ herd-representation.txt
o You are interested in the publications related to LKMM, including
hardware manuals, academic literature, standards-committee
@@ -57,6 +58,10 @@ control-dependencies.txt
explanation.txt
Detailed description of the memory model.
+herd-representation.txt
+ The (abstract) representation of the Linux-kernel concurrency
+ primitives in terms of events.
+
litmus-tests.txt
The format, features, capabilities, and limitations of the litmus
tests that LKMM can evaluate.
diff --git a/tools/memory-model/Documentation/herd-representation.txt b/tools/memory-model/Documentation/herd-representation.txt
new file mode 100644
index 0000000000000..1860995a3d5a5
--- /dev/null
+++ b/tools/memory-model/Documentation/herd-representation.txt
@@ -0,0 +1,107 @@
+#
+# Legenda:
+# R, a Load event
+# W, a Store event
+# F, a Fence event
+# LKR, a Lock-Read event
+# LKW, a Lock-Write event
+# UL, an Unlock event
+# LF, a Lock-Fail event
+# RL, a Read-Locked event
+# RU, a Read-Unlocked event
+# R*, a Load event included in RMW
+# W*, a Store event included in RMW
+# SRCU, a Sleepable-Read-Copy-Update event
+#
+# po, a Program-Order link
+# rmw, a Read-Modify-Write link
+# lk-rmw, a Lock-Read-Modify-Write link
+#
+# By convention, a blank entry/representation means "same as the preceding entry".
+#
+ ------------------------------------------------------------------------------
+ | C macro | Events |
+ ------------------------------------------------------------------------------
+ | Non-RMW ops | |
+ ------------------------------------------------------------------------------
+ | READ_ONCE | R[once] |
+ | atomic_read | |
+ | WRITE_ONCE | W[once] |
+ | atomic_set | |
+ | smp_load_acquire | R[acquire] |
+ | atomic_read_acquire | |
+ | smp_store_release | W[release] |
+ | atomic_set_release | |
+ | smp_store_mb | W[once] ->po F[mb] |
+ | smp_mb | F[mb] |
+ | smp_rmb | F[rmb] |
+ | smp_wmb | F[wmb] |
+ | smp_mb__before_atomic | F[before-atomic] |
+ | smp_mb__after_atomic | F[after-atomic] |
+ | spin_unlock | UL |
+ | spin_is_locked | On success: RL |
+ | | On failure: RU |
+ | smp_mb__after_spinlock | F[after-spinlock] |
+ | smp_mb__after_unlock_lock | F[after-unlock-lock] |
+ | rcu_read_lock | F[rcu-lock] |
+ | rcu_read_unlock | F[rcu-unlock] |
+ | synchronize_rcu | F[sync-rcu] |
+ | rcu_dereference | R[once] |
+ | rcu_assign_pointer | W[release] |
+ | srcu_read_lock | R[srcu-lock] |
+ | srcu_down_read | |
+ | srcu_read_unlock | W[srcu-unlock] |
+ | srcu_up_read | |
+ | synchronize_srcu | SRCU[sync-srcu] |
+ | smp_mb__after_srcu_read_unlock | F[after-srcu-read-unlock] |
+ ------------------------------------------------------------------------------
+ | RMW ops w/o return value | |
+ ------------------------------------------------------------------------------
+ | atomic_add | R*[noreturn] ->rmw W*[once] |
+ | atomic_and | |
+ | spin_lock | LKR ->lk-rmw LKW |
+ ------------------------------------------------------------------------------
+ | RMW ops w/ return value | |
+ ------------------------------------------------------------------------------
+ | atomic_add_return | F[mb] ->po R*[once] |
+ | | ->rmw W*[once] ->po F[mb] |
+ | atomic_fetch_add | |
+ | atomic_fetch_and | |
+ | atomic_xchg | |
+ | xchg | |
+ | atomic_add_negative | |
+ | atomic_add_return_relaxed | R*[once] ->rmw W*[once] |
+ | atomic_fetch_add_relaxed | |
+ | atomic_fetch_and_relaxed | |
+ | atomic_xchg_relaxed | |
+ | xchg_relaxed | |
+ | atomic_add_negative_relaxed | |
+ | atomic_add_return_acquire | R*[acquire] ->rmw W*[once] |
+ | atomic_fetch_add_acquire | |
+ | atomic_fetch_and_acquire | |
+ | atomic_xchg_acquire | |
+ | xchg_acquire | |
+ | atomic_add_negative_acquire | |
+ | atomic_add_return_release | R*[once] ->rmw W*[release] |
+ | atomic_fetch_add_release | |
+ | atomic_fetch_and_release | |
+ | atomic_xchg_release | |
+ | xchg_release | |
+ | atomic_add_negative_release | |
+ ------------------------------------------------------------------------------
+ | Conditional RMW ops | |
+ ------------------------------------------------------------------------------
+ | atomic_cmpxchg | On success: F[mb] ->po R*[once] |
+ | | ->rmw W*[once] ->po F[mb] |
+ | | On failure: R*[once] |
+ | cmpxchg | |
+ | atomic_add_unless | |
+ | atomic_cmpxchg_relaxed | On success: R*[once] ->rmw W*[once] |
+ | | On failure: R*[once] |
+ | atomic_cmpxchg_acquire | On success: R*[acquire] ->rmw W*[once] |
+ | | On failure: R*[once] |
+ | atomic_cmpxchg_release | On success: R*[once] ->rmw W*[release] |
+ | | On failure: R*[once] |
+ | spin_trylock | On success: LKR ->lk-rmw LKW |
+ | | On failure: LF |
+ ------------------------------------------------------------------------------
--
2.34.1
^ permalink raw reply related [flat|nested] 5+ messages in thread
* Re: [PATCH v2] tools/memory-model: Document herd7 (abstract) representation
2024-06-05 13:49 [PATCH v2] tools/memory-model: Document herd7 (abstract) representation Andrea Parri
@ 2024-06-05 15:53 ` Alan Stern
2024-06-05 16:52 ` Andrea Parri
0 siblings, 1 reply; 5+ messages in thread
From: Alan Stern @ 2024-06-05 15:53 UTC (permalink / raw)
To: Andrea Parri
Cc: will, peterz, boqun.feng, npiggin, dhowells, j.alglave,
luc.maranget, paulmck, akiyks, dlustig, joel, linux-kernel,
linux-arch, hernan.poncedeleon, jonas.oberhauser
On Wed, Jun 05, 2024 at 03:49:18PM +0200, Andrea Parri wrote:
> tools/memory-model/ and herdtool7 are closely linked: the latter is
> responsible for (pre)processing each C-like macro of a litmus test,
> and for providing the LKMM with a set of events, or "representation",
> corresponding to the given macro. Provide herd-representation.txt
> to document the representations of the concurrency macros, following
> their "classification" in Documentation/atomic_t.txt.
>
> Suggested-by: Hernan Ponce de Leon <hernan.poncedeleon@huaweicloud.com>
> Signed-off-by: Andrea Parri <parri.andrea@gmail.com>
> --- /dev/null
> +++ b/tools/memory-model/Documentation/herd-representation.txt
> @@ -0,0 +1,107 @@
> +#
> +# Legenda:
> +# R, a Load event
> +# W, a Store event
> +# F, a Fence event
> +# LKR, a Lock-Read event
> +# LKW, a Lock-Write event
> +# UL, an Unlock event
> +# LF, a Lock-Fail event
> +# RL, a Read-Locked event
> +# RU, a Read-Unlocked event
> +# R*, a Load event included in RMW
> +# W*, a Store event included in RMW
> +# SRCU, a Sleepable-Read-Copy-Update event
> +#
> +# po, a Program-Order link
> +# rmw, a Read-Modify-Write link
> +# lk-rmw, a Lock-Read-Modify-Write link
I wonder if we really need a special notation for lk-rmw. Is anything
wrong with using the normal rmw notation for these links?
Alan
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [PATCH v2] tools/memory-model: Document herd7 (abstract) representation
2024-06-05 15:53 ` Alan Stern
@ 2024-06-05 16:52 ` Andrea Parri
2024-06-05 17:55 ` Alan Stern
0 siblings, 1 reply; 5+ messages in thread
From: Andrea Parri @ 2024-06-05 16:52 UTC (permalink / raw)
To: Alan Stern
Cc: will, peterz, boqun.feng, npiggin, dhowells, j.alglave,
luc.maranget, paulmck, akiyks, dlustig, joel, linux-kernel,
linux-arch, hernan.poncedeleon, jonas.oberhauser
> I wonder if we really need a special notation for lk-rmw. Is anything
> wrong with using the normal rmw notation for these links?
I don't think we need the special notation: in fact, herd7 doesn't know
anything about these lk-rmw or rmw links between lock events until after
tools/memory-model/ (the .cat file) has established such links cf.
(* Link Lock-Reads to their RMW-partner Lock-Writes *)
let lk-rmw = ([LKR] ; po-loc ; [LKW]) \ (po ; po)
let rmw = rmw | lk-rmw
I was trying to be informative (since that says "lk-rmw is a subrelation
of rmw) but, in order to be faithful to the scope of this document (herd
representation), the doc should really just indicate LKR ->po LKW.
Thoughts?
Andrea
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [PATCH v2] tools/memory-model: Document herd7 (abstract) representation
2024-06-05 16:52 ` Andrea Parri
@ 2024-06-05 17:55 ` Alan Stern
2024-06-05 19:48 ` Andrea Parri
0 siblings, 1 reply; 5+ messages in thread
From: Alan Stern @ 2024-06-05 17:55 UTC (permalink / raw)
To: Andrea Parri
Cc: will, peterz, boqun.feng, npiggin, dhowells, j.alglave,
luc.maranget, paulmck, akiyks, dlustig, joel, linux-kernel,
linux-arch, hernan.poncedeleon, jonas.oberhauser
On Wed, Jun 05, 2024 at 06:52:18PM +0200, Andrea Parri wrote:
> > I wonder if we really need a special notation for lk-rmw. Is anything
> > wrong with using the normal rmw notation for these links?
>
> I don't think we need the special notation: in fact, herd7 doesn't know
> anything about these lk-rmw or rmw links between lock events until after
> tools/memory-model/ (the .cat file) has established such links cf.
>
> (* Link Lock-Reads to their RMW-partner Lock-Writes *)
> let lk-rmw = ([LKR] ; po-loc ; [LKW]) \ (po ; po)
> let rmw = rmw | lk-rmw
>
> I was trying to be informative (since that says "lk-rmw is a subrelation
> of rmw) but, in order to be faithful to the scope of this document (herd
> representation), the doc should really just indicate LKR ->po LKW.
>
> Thoughts?
I agree; be faithful to the document's scope and just say LKR ->po LKW.
Were there other things like this in the table? I didn't notice any.
Alan
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [PATCH v2] tools/memory-model: Document herd7 (abstract) representation
2024-06-05 17:55 ` Alan Stern
@ 2024-06-05 19:48 ` Andrea Parri
0 siblings, 0 replies; 5+ messages in thread
From: Andrea Parri @ 2024-06-05 19:48 UTC (permalink / raw)
To: Alan Stern
Cc: will, peterz, boqun.feng, npiggin, dhowells, j.alglave,
luc.maranget, paulmck, akiyks, dlustig, joel, linux-kernel,
linux-arch, hernan.poncedeleon, jonas.oberhauser
On Wed, Jun 05, 2024 at 01:55:08PM -0400, Alan Stern wrote:
> On Wed, Jun 05, 2024 at 06:52:18PM +0200, Andrea Parri wrote:
> > > I wonder if we really need a special notation for lk-rmw. Is anything
> > > wrong with using the normal rmw notation for these links?
> >
> > I don't think we need the special notation: in fact, herd7 doesn't know
> > anything about these lk-rmw or rmw links between lock events until after
> > tools/memory-model/ (the .cat file) has established such links cf.
> >
> > (* Link Lock-Reads to their RMW-partner Lock-Writes *)
> > let lk-rmw = ([LKR] ; po-loc ; [LKW]) \ (po ; po)
> > let rmw = rmw | lk-rmw
> >
> > I was trying to be informative (since that says "lk-rmw is a subrelation
> > of rmw) but, in order to be faithful to the scope of this document (herd
> > representation), the doc should really just indicate LKR ->po LKW.
> >
> > Thoughts?
>
> I agree; be faithful to the document's scope and just say LKR ->po LKW.
>
> Were there other things like this in the table? I didn't notice any.
None that I can think of, the others look good to me.
I'll do this change for v3. Thank you for the suggestion.
Andrea
^ permalink raw reply [flat|nested] 5+ messages in thread
end of thread, other threads:[~2024-06-05 19:48 UTC | newest]
Thread overview: 5+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2024-06-05 13:49 [PATCH v2] tools/memory-model: Document herd7 (abstract) representation Andrea Parri
2024-06-05 15:53 ` Alan Stern
2024-06-05 16:52 ` Andrea Parri
2024-06-05 17:55 ` Alan Stern
2024-06-05 19:48 ` Andrea Parri
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).