Skip to contentSkip to conversation

tools/memory-model: Document herd7 (abstract) representation

PATCH Superseded Andrea Parri 2 participants 5 messages Jun 5, 2024

Subsystems (2)

v2 of 4 Superseded Latest is v4 →

lore
Share & tools
lore

Andrea Parri

author maintainer
#0 lore raw

PATCH v2 1/1 tools/memory-model: Document herd7 (abstract) representation

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.

---
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/[email protected]/

 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
tools/memory-model/Documentation/README +6 -1
index db90a26dbdf40..1f73014cc48a3 100644
@@ -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.
tools/memory-model/Documentation/herd-representation.txt new file +107 -0

107 lines not on this page · raw message

Signature · 1 line
2.34.1
maintainer
#1 lore raw
Quoted 21 lines · 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.

tools/memory-model/Documentation/herd-representation.txt new file +8 -0
@@ -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

tools/memory-model/Documentation/herd-representation.txt line 18

Quoted 10 lines
tools/memory-model/Documentation/herd-representation.txt new file +10 -0
+#	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

author maintainer
#2 lore raw
Quoted 2 lines

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

maintainer
#3 lore raw
Quoted 11 lines · Andrea Parri
Quoted 2 lines

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

Quoted 5 lines

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

author maintainer
#4 lore raw
Quoted 16 lines · Alan Stern
Quoted 15 lines · Andrea Parri
Quoted 2 lines

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.

Quoted 5 lines
Quoted 1 line

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