Skip to content
Snippets Groups Projects
Select Git revision
  • riscv-sqoscfg-rfc-v2
  • riscv-cbqri-rfc-v2
  • riscv-cbqri-rfc
  • master default protected
  • v6.3-rc6
  • v6.3-rc5
  • v6.3-rc4
  • v6.3-rc3
  • v6.3-rc2
  • v6.3-rc1
  • v6.2
  • v6.2-rc8
  • v6.2-rc7
  • v6.2-rc6
  • v6.2-rc5
  • v6.2-rc4
  • v6.2-rc3
  • v6.2-rc2
  • v6.2-rc1
  • v6.1
  • v6.1-rc8
  • v6.1-rc7
  • v6.1-rc6
  • v6.1-rc5
24 results
Search by author
  • Any Author
0 authors
  1. Jan 04, 2023
    • Jonas Oberhauser's avatar
      tools: memory-model: Make plain accesses carry dependencies · 9ba7d3b3
      Jonas Oberhauser authored 
      As reported by Viktor, plain accesses in LKMM are weaker than
accesses to registers: the latter carry dependencies but the former
do not. This is exemplified in the following snippet:

  int r = READ_ONCE(*x);
  WRITE_ONCE(*y, r);

Here a data dependency links the READ_ONCE() to the WRITE_ONCE(),
preserving their order, because the model treats r as a register.
If r is turned into a memory location accessed by plain accesses,
however, the link is broken and the order between READ_ONCE() and
WRITE_ONCE() is no longer preserved.

This is too conservative, since any optimizations on plain
accesses that might break dependencies are also possible on
registers; it also contradicts the intuitive notion of "dependency"
as the data stored by the WRITE_ONCE() does depend on the data read
by the READ_ONCE(), independently of whether r is a register or a
memory location.

This is resolved by redefining all dependencies to include
dependencies carried by memory accesses; a dependency is said to be
carried by memory accesses (in the model: carry-dep) from one load
to another load if the initial load is followed by an arbitrarily
long sequence alternating between stores and loads of the same
thread, where the data of each store depends on the previous load,
and is read by the next load.

Any dependency linking the final load in the sequence to another
access also links the initial load in the sequence to that access.

More deep details can be found in this LKML discussion:

https://lore.kernel.org/lkml/d86295788ad14a02874ab030ddb8a6f8@huawei.com/



Reported-by: default avatarViktor Vafeiadis <viktor@mpi-sws.org>
Signed-off-by: default avatarJonas Oberhauser <jonas.oberhauser@huawei.com>
Reviewed-by: default avatarAlan Stern <stern@rowland.harvard.edu>
Signed-off-by: default avatarPaul E. McKenney <paulmck@kernel.org>
      9ba7d3b3
    • Alan Stern's avatar
      tools: memory-model: Add rmw-sequences to the LKMM · ebd50e29
      Alan Stern authored 
      
Viktor (as relayed by Jonas) has pointed out a weakness in the Linux
Kernel Memory Model.  Namely, the memory ordering properties of atomic
operations are not monotonic: An atomic op with full-barrier semantics
does not always provide ordering as strong as one with release-barrier
semantics.

The following litmus test illustrates the problem:

--------------------------------------------------
C atomics-not-monotonic

{}

P0(int *x, atomic_t *y)
{
	WRITE_ONCE(*x, 1);
	smp_wmb();
	atomic_set(y, 1);
}

P1(atomic_t *y)
{
	int r1;

	r1 = atomic_inc_return(y);
}

P2(int *x, atomic_t *y)
{
	int r2;
	int r3;

	r2 = atomic_read(y);
	smp_rmb();
	r3 = READ_ONCE(*x);
}

exists (2:r2=2 /\ 2:r3=0)
--------------------------------------------------

The litmus test is allowed as shown with atomic_inc_return(), which
has full-barrier semantics.  But if the operation is changed to
atomic_inc_return_release(), which only has release-barrier semantics,
the litmus test is forbidden.  Clearly this violates monotonicity.

The reason is because the LKMM treats full-barrier atomic ops as if
they were written:

	mb();
	load();
	store();
	mb();

(where the load() and store() are the two parts of an atomic RMW op),
whereas it treats release-barrier atomic ops as if they were written:

	load();
	release_barrier();
	store();

The difference is that here the release barrier orders the load part
of the atomic op before the store part with A-cumulativity, whereas
the mb()'s above do not.  This means that release-barrier atomics can
effectively extend the cumul-fence relation but full-barrier atomics
cannot.

To resolve this problem we introduce the rmw-sequence relation,
representing an arbitrarily long sequence of atomic RMW operations in
which each operation reads from the previous one, and explicitly allow
it to extend cumul-fence.  This modification of the memory model is
sound; it holds for PPC because of B-cumulativity, it holds for TSO
and ARM64 because of other-multicopy atomicity, and we can assume that
atomic ops on all other architectures will be implemented so as to
make it hold for them.

For similar reasons we also allow rmw-sequence to extend the
w-post-bounded relation, which is analogous to cumul-fence in some
ways.

Reported-by: default avatarViktor Vafeiadis <viktor@mpi-sws.org>
Signed-off-by: default avatarAlan Stern <stern@rowland.harvard.edu>
Reviewed-by: default avatarJonas Oberhauser <jonas.oberhauser@huawei.com>
Signed-off-by: default avatarPaul E. McKenney <paulmck@kernel.org>
      ebd50e29
  3. Oct 19, 2022
  5. Aug 31, 2022
  7. May 03, 2022
  9. Feb 02, 2022
  11. Dec 01, 2021
  13. Jul 27, 2021
  15. Jul 20, 2021
  17. May 11, 2021
  19. Apr 06, 2021
  21. Mar 15, 2021
  23. Mar 08, 2021
  25. Jan 04, 2021
  27. Nov 07, 2020
  29. Oct 27, 2020
  31. Sep 04, 2020
  33. Sep 03, 2020
  35. Jul 21, 2020
  37. Jun 29, 2020