Verification of Memory Reordering Using Nim language

Verify「CPU memory reordering」

Question

According to Memory Reordering Caught in the Act open_in_new, Intel CPU may sometimes reorder memory instructions. Memory reordering has a great effect on lock-free programming. The goal of this article is to verify memory reordering.

Given two integers X and Y, somewhere in memory, they are initialized to 0. Now we have two processors which run parallelly and execute machine codes.

Intel CPU may execute "Memory instruction reordering" and the actual execution order has become:

There are four situations: r1 = 1, r2 = 0 or r1 = 0, r2 = 1 or r1 = 1, r2 = 1 or r1 = 0, r2 = 0. Among them, r1 = 0, r2 = 0 is caused by Intel CPU "Memory instruction reordering" which is also the goal of our verification.

CPU Info

Now list my CPU Info:

Name	Processors	Cores	Cache
Intel(R) Core(TM) i5-7200U CPU @ 2.50GHz	4	2	3 MB Intel® Smart Cache

$ cat /proc/cpuinfo       # Watch cpu info
$ lscpu                   # View summary

Deduction

To verify this process, we use Nim language. Providing that we have four variables, run two worker threads in multi-core processor and disable compiler's Memory reordering optimization to watch the process of cpu's Memory reordering optimization.

First we initialize x and y to zero. Then we run x = 1; r1 = y; in worker thread 1 and run y = 1; r2 = x; in worker thread 2. Finally we print the number of which r1 = 0, r2 = 0 occurs (Number of occurrences, number of iterations).

Thread 1:

x = 1
r1 = y

Thread 2:

y = 1
r2 = x

Results:

r1 == 0 and r2 == 0

Programming

First, choose a "wake <-> wait" mechanism for the threads to keep the worker threads in order. For simplicity, we manually write a simple semaphore implementation.

This semaphore implementation uses Linux's eventfd and eventfd is an efficient thread communication mechanism which is very suitable as a semaphore implementation(reference eventfd(2) — Linux manual page).

import std/posix
import std/os

# Provide semaphore-like semantics for reads from the new file descriptor.
const EFD_SEMAPHORE = 1 

proc eventfd(initval: cuint, flags: cint): cint {.
  importc: "eventfd", 
  header: "sys/eventfd.h"
.}

type
  Semaphore = object
    fd: cint

template checkOSError(syscall: untyped) =
  let n = syscall
  if n < 0:
    raiseOSError(osLastError()) 

proc initSemaphore(): Semaphore =
  # create eventfd in semaphore mode
  result.fd = eventfd(0, EFD_SEMAPHORE)

proc wait(s: var Semaphore) =
  var buf: uint64
  checkOSError s.fd.read(buf.addr, 8) 

proc signal(s: var Semaphore) = 
  var buf: uint64 = 1
  checkOSError s.fd.write(buf.addr, 8)

Implement thread functions:

import std/random

var 
  beginSem1 = initSemaphore()   # for thread 1 synchronization
  endSem1 = initSemaphore()     # for thread 1 synchronization

  beginSem2 = initSemaphore()   # for thread 2 synchronization
  endSem2 = initSemaphore()     # for thread 2 synchronization

  x: int
  y: int

  r1: int
  r2: int

const Format{.strdefine.} = "logging"  # Specify the format of the console print log

proc threadFunc1() {.thread.} =
  randomize()                          # Initialize "Random Number Generator"
  while true:
    beginSem1.wait()                   # Wait for the main thread to initiate a signal
    while rand(100) mod 8 == 0: break  # Calculate the random number
                                       # deliberately make the two threads run staggered

    # ----------------------------- transaction! -------------------------------
    x = 1
    {.emit: """asm volatile("" ::: "memory");""".} # Disable compiler reordering
    r1 = y
    # --------------------------------------------------------------------------

    endSem1.signal()                   # Notify the main thread that an iteration is complete

proc threadFunc2() {.thread.} =
  randomize()                          # Initialize "Random Number Generator"
  while true:
    beginSem2.wait()                   # Wait for the main thread to initiate a signal
    while rand(100) mod 8 == 0: break  # Calculate the random number
                                       # deliberately make the two threads run staggered

    # ----------------------------- transaction! -------------------------------
    y = 1
    {.emit: """asm volatile("" ::: "memory");""".} # Disable compiler reordering
    r2 = x
    # --------------------------------------------------------------------------

    endSem2.signal()                   # Notify the main thread that an iteration is complete

proc main() =
  var
    thread1: Thread[void]
    thread2: Thread[void]

  createThread(thread1, threadFunc1)
  createThread(thread2, threadFunc2)

  # Repeat experiment
  var n = 0                            # Number of reorders
  var counter = 0                      # The number of worker thread iterations
  while true:
    x = 0
    y = 0

    beginSem1.signal()
    beginSem2.signal()
    endSem1.wait()
    endSem2.wait()

    counter.inc()
    if r1 == 0 and r2 == 0:            # CPU memory reordering occurs
      n.inc()
      when Format == "csv":            # Output csv format: -d:Format=csv
        echo $n, ", ", $counter
      else:                            # Output log format
        echo "Reorders detected (n=" & $n & ", counter=" & $counter & ")"

  joinThread(thread1)
  joinThread(thread2)

main()

Experimental results

Open the console, run the program, and output the log:

$ nim c -r -d:release reordering.nim

Reorders detected (n=1, counter=1)
Reorders detected (n=2, counter=509)
Reorders detected (n=3, counter=512)
Reorders detected (n=4, counter=21185)
Reorders detected (n=5, counter=21400)
Reorders detected (n=6, counter=21486)
Reorders detected (n=7, counter=21490)
Reorders detected (n=8, counter=21553)
Reorders detected (n=9, counter=31530)
Reorders detected (n=10, counter=31612)
Reorders detected (n=11, counter=32948)
Reorders detected (n=12, counter=36575)
Reorders detected (n=13, counter=39927)
Reorders detected (n=14, counter=59147)
Reorders detected (n=15, counter=59165)
Reorders detected (n=16, counter=59168)
Reorders detected (n=17, counter=60922)
Reorders detected (n=18, counter=62117)
Reorders detected (n=19, counter=62121)
Reorders detected (n=20, counter=62130)
Reorders detected (n=21, counter=62407)
Reorders detected (n=22, counter=65811)
Reorders detected (n=23, counter=65829)
Reorders detected (n=24, counter=69376)
Reorders detected (n=25, counter=72983)
Reorders detected (n=26, counter=76600)
Reorders detected (n=27, counter=78803)
Reorders detected (n=28, counter=79768)
Reorders detected (n=29, counter=83267)
Reorders detected (n=30, counter=83304)
...

Further, let's make a csv file and a chart to view the trend of CPU memory reordering.

We have defined the Format symbol in the program to help control the format of the printed log. -d:Format=cs prints csv data format (number of reordering occurrences\t worker thread iterations).

Write a python script (reordering.py), read the resulting csv file (reordering.csv) and generate a graph (reordering.png).

# reordering.py

import matplotlib.pyplot as plt
import numpy as np
import pandas as pd
import csv
import seaborn as sns

sns.set(style="darkgrid")

xdata = [] # Number of worker thread iterations
ydata = [] # Occurrence of reorders

with open("reordering.csv") as f:
  fcsv = csv.reader(f)
  headers = next(fcsv)
  for row in fcsv:
    xdata.append(float(row[1]))
    ydata.append(float(row[0]))

df = pd.DataFrame(dict(counter=xdata, n=ydata))

g = sns.relplot(
  x="counter", 
  y="n", 
  height=4, 
  linewidth=2, 
  aspect=1.3, 
  kind="line", 
  data=df
)
g.fig.autofmt_xdate() 
plt.savefig('reordering.png')

Run our program:

$ nim c -r -d:release reordering.nim > reordering.csv
$ python3 reordering.py

Generate csv file (reordering.csv):

1, 1524
2, 6342
3, 6396
4, 6404
5, 6612
6, 6665
7, 6706
8, 6787
9, 6789
10, 6793
11, 6821
12, 6833
13, 6845
14, 6860
15, 6869
16, 6872
...
991, 4272196
992, 4272227
993, 4272232
994, 4272236
995, 4272242
996, 4272277
997, 4272280
998, 4272293
999, 4272305
1000, 4275173
...

Generate a graph (reordering.png) --- Basically present a linear trend:

Blog