Bug 380942

Created attachment 105965 [details]
Initial implementation

Here's an initial implementation.  Some notes:

* You *must* use --fair-sched=yes.  If you don't, you'll get garbage
  results and no warning.

* The implementation reduces SCHEDULING_QUANTUM from 100000 to 1200,
  so as to give reasonable pseudo-parallel interleaving of threads.
  That is a fine enough interleaving to pick up more than 90% of all
  RFOs from execution of parallel layout algorithms in Firefox.  If
  you have very frequent cache line transfers then you may need to
  set this even lower to get accurate stats.

* The reduction in SCHEDULING_QUANTUM makes Valgrind run more slowly,
  although not catastrophically so.

* This doesn't really simulate the MESI protocol directly.  Instead
  it keeps track of which thread has most recently accessed each
  cache line sized piece of memory, and observes transfers of ownership
  between these cache line sized pieces of memory.

* As a result you can simulate MESI (like) behaviour for any number of
  threads.  It's unrelated to the hardware in your machine.  The line
  size is currently hardwired to 64 bytes.

* Use the flag --simulate-mesi=yes.  You can't use any of the other
  Callgrind simulation facilities (caches, branches, prefetchers etc)
  at the same time.

* The simulation tries to distinguish between true and false sharing.

* This is all very experimental.  It's not really clear whether the RFO
  detection and the true-vs-false sharing detection reflect reality
  accurately enough to be useful.

* 4 different kinds of costs are computed:
     RFOr      -- requests for ownership (transfers) due to reads
     RFOw      -- RFOs due to writes
     RFOrTrue  -- RFOs due to reads, with true sharing
     RFOwTrue  -- RFOs due to writes, with true sharing

* You can display the results in KCachegrind in the normal way.

* Although it is not necessary, it is useful to program the following
  formulas into KCachegrind:

     RFO = RFOr + RFOw              -- total number of RFOs

     RFOTrue = RFOrTrue + RFOwTrue  -- total number of RFOs from true sharing

     RFOFalse = RFOr + RFOw - RFOrTrue - RFOwTrue
                                    -- total number of RFOs from false sharing

Nice!

State transitions look good.
Getting read of the empty Ir simulation can be done after merging.

But to really distinguish between true and false sharing, remembering the last access is not really enough. It may identify true sharing as false sharing.

E.g. multiple accesses from the same thread could cover all of a cache line, yet it is identified as false sharing if the first access of another thread does not overlap with the last access of the original thread.

The real solution would be to maintain a bitmap (on a 64-bit architecture,
using a 64-bit integer for a cacheline size of 64 bytes is a perfect match).
Updating the bitmap may be slightly slower, but checking for overlap is
just an AND operation.
I actually do that in the simulator for "cache use"; we can copy it from
there.

Created attachment 156636 [details]
valgrind-bug380942-Callgrind-MESI.diff-2023Feb23-rebased

Here's the same patch rebased to V sources of 23 Feb 2023.  --fair-sched=yes
has been hardwired (see comment 1) and the scheduling quantum has been reduced
from 1200 to 800, for safety.

TL;DR to build is now:

  git clone https://sourceware.org/git/valgrind.git mesi2023
  cd mesi2023
  patch -p1 < valgrind-bug380942-Callgrind-MESI.diff-2023Feb23-rebased
  ./autogen.sh
  ./configure --prefix=`pwd`/Inst --enable-only64bit
  make -j 8 all
  make -j 8 install

To run:

  /path/to/mesi2023/Inst/bin/valgrind \
     --tool=callgrind --simulate-mesi=yes <program and args>
  kcachegrind callgrind.out.<PID>

See comment 1 for more details on the RFO events.  These are the "requests for
ownership" (cache line transfers) which contain the info of interest here.