Re: LKMM: Making RMW barriers explicit

Boqun Feng
2024-05-24T18:47:33Z

On Fri, May 24, 2024 at 08:09:28PM +0200, Jonas Oberhauser wrote:
[...]
> >
> > Question: Since R and RMW have different lists of allowable tags, how
> > does herd7 decide which tags are allowed for an event that is in both
> > the R and RMW sets?
>
> After looking over the patch draft for herd7 written by Hernan [1], my best
> guess is: it doen't. It seems that after herd7 detects you are using LKMM it

Right, you can event put a 'acquire tag to WRITE_ONCE():

-WRITE_ONCE(X,V) { __store{once}(X,V); }
+WRITE_ONCE(X,V) { __store{acquire}(X,V); }

, herd won't complain, but it may change the model behavior.

Here is what I know from the herd code:

* First, normally herd just put whatever the tag you specify in
.def file to the accesses event (it has to be one of the tags
in Access list in .bell file).

* An access event looks like:

(read_or_write?, ..., anonatation, is_atomic?, ...)

"is_atomic?" means whether the event comes from an rmw
primitives. So a READ_ONCE() will look like:

(read, ..., once, false, ...)

and a WRITE_ONCE() will look like:

(write, ..., once, false, ...)

the read part of an atomic_add_return_relaxed() is:

(read, ..., once, true, ...)

note that the "is_atomic?" is how this event ends up in "RMW"
set.

> simply drops all tags except 'acquire on read and 'release on store.

Right, herd does some extra work to filter out RELEASE reads and ACQUIRE
writes for rwm atomics, basically, when herd is generating events for an
rmw atomic, if it's not "mb", it will only kill 'acquire for read and
'release on store, otherwise, it changes the annotation part to 'once.
Funny example, if you do a __atomic_fetch_op{hello}(..), herd will treat
it as a __atomic_fetch_op{once}(..) because of this.

> Everything else becomes 'once (and 'mb adds some F[mb] sometimes).
>
> That means that if one were to go through with the earlier suggestion to
> distinguish between the smp_mb() Mb and the cmpxchg() Mb, e.g. by calling
> the latter RmwMb, current herd7 would always erase the RmwMb tag because it
> is not called "acquire" or "release".
> The same would happen of course if you introduced an RmwAcquire tag.
>
> So there are several options:
>
> - treat the tags as a syntactic thing which is always present, and
> specify their meaning purely in the cat file, analogous to what you
> have defined above. This is personally my favorite solution. To
> implement this in herd7 we would simply remove all the current special
> cases for the LKMM barriers, which I like.
>

Agreed.

> However then we need to actually define the behavior of herd if
> an inappropriate tag (like release on a load) is provided. Since the
> restriction is actually mostly enforced by the .def file - by simply
> not providing a smp_store_acquire() etc. -, that only concerns RMWs,
> where xchg_acquire() would apply the Acquire tag to the write also.
>
> The easiest solution is to simply remove the syntax for specifying
> restrictions - it seems it is not doing much right now anyways - and
> do the filtering inside .bell, with things like
>
> (* only writes can have Release tags *)
> let Release = Release & W \ (RMW \ rng(rmw))
>
> One good thing about this way is that it would work even without
> modifying herd, since it is in a sense idempotent with the

Well, we still need to turn off the "smart" annotation rewritting in
herd (e.g. -> once), but I think that's a good thing: it simplifies the
internal work herd does, and it also helps people on other tools
understand LKMM better.

> transformations done by herd.
>
> FWIW, in our internal weak memory model in Dresden we did exactly this,

so the model doesn't work elsewhere even in Germany? ;-) Sorry, couldn'
t resist ;-) ;-) ;-)

> and use REL for the syntax and Rel for the semantic release ordering to
> make the distinction more clear, with things like:
>
> let Acq = (ACQ | SC) & (R | F)
> let Rel = (REL | SC) & (W | F)
>
> (SC is our equivalent to LKMM's Mb)
>
> - treat the tags as semantic markers that are only present or not under
> some circumstances, and define the semantics fully based on the present
> tags. The circumstances are currently hardcoded in herd7, but we should
> move them out with some syntax like __cmpxchg{acquire}{once}.
>
> This requires touching the parser and of course still has the issue
> with the acquire tag appearing on the store as well.
>
> - provide a full syntax for defining the event sequence that is
> expected. For example, for a cmpxchg we could do
>
> cmpxchg = { F[success-cmpxchg]; c = R&RMW[once]; if (c==v) {
> W&RMW[once]; } F[success-cmpxchg] }
>
> and then define in .bell that a success-cmpxchg is an mb if it is
> directly next to a cmpxchg that succeeds.
>
> The advantage is that you can customize the representation to whatever
> kernel devs thing is the most intuitive. The downside is that it
> requires major rewrites to herd7, someone to think about a reasonable
> language for specifying this etc.
>

I no doubt am the fan of the first approach, herd is powerful because
the ability to customize the semantic rules for model ordering models,
moving more parts from herd internals to the cat file (or bell file) is
always a good thing to me.

Regards,
Boqun

>
>
> Best wishes,
> jonas
>
>
>
> [1] https://github.com/herd/herdtools7/pull/865
>