多线程共享与伪共享检测

多线程/进程之间使用缓存一致性协议来保证每个包含独立缓存对象的核心在共享使用内存数据时的一致性，缓存一致性协议保证了缓存实体中的任何更新都会对相同位置的其他缓存进行全部更新。MESI协议是最著名的一致性协议，支持现代CPU中缓存回写。通过监控内存事务保持一致性，一致性问题可以得到缓解，但是是有代价的，导致CPU访存空转，浪费系统带宽，两种具有代表性的内存一致性问题是“真共享”和“伪共享”。

“真共享”

多线程同时访问相同变量时，为真共享，下列代码简单说明了该问题：

let mut sum: u64 = 0;
{ // parallel section
    for i in 0..N {
        sum += i; // sum is shared between all threads
    }   
}

数据竞争是未定义行为，C++下Clang的Thread sanitizer和helgrind可以一定程度检查出数据竞争。而Rust中的数据竞争检测在编译阶段就通过其所有权机制和借用检查器实现，具体的，Rust利用RAII机制在作用域结束时释放对象持有的内存，该内存有且只有一个对象持有，借用检查器是Rust在编译期预防数据竞争的主要手段，确保了在任何时候只有一个线程可以“借用”内存区域。

而在C++中，将sum变量变为原子变量有助于解决真共享发生的数据竞争问题。但是在进行内存顺序的排序、串行化的内存操作之后，会极为影响性能，详细见Perfbook关于多线程Counter的相关设计。

而另外一个解决真共享的方法是使用TLS（Thread Local Storage，TLS）。通过TLS在给定的多线程下，每个线程都可以分配内存来存储该线程内的独占数据，线程之间便可不竞争全局变量。在C++使用thread_local关键字修饰某个变量为线程独占，而在Rust下使用 thread_local 宏可以初始化线程局部变量，然后在线程内部使用该变量的 with 方法获取变量值，或者使用attribute的的#[thread_local]进行标记，或者，可以使用thread_local第三方库，具体例子见下面代码：

thread_local! {
    static MACRO_TLS: std::cell::RefCell<Foo> = std::cell::RefCell::new(Foo(0));
}

#[thread_local]
static mut ATTR_TLS: Foo = Foo(0);

fn main() {
    let _ = std::thread::spawn(|| unsafe {
        MACRO_TLS.with(|f| {
            println!("foo: {}", f.borrow_mut().0);
        });
    })
    .join();
}

#include <iostream>
#include <mutex>
#include <string>
#include <thread>
 
thread_local unsigned int rage = 1; 
std::mutex cout_mutex;
 
void increase_rage(const std::string& thread_name)
{
    ++rage; // modifying outside a lock is okay; this is a thread-local variable
    std::lock_guard<std::mutex> lock(cout_mutex);
    std::cout << "Rage counter for " << thread_name << ": " << rage << '\n';
}
 
int main()
{
    std::thread a(increase_rage, "a"), b(increase_rage, "b");
 
    {
        std::lock_guard<std::mutex> lock(cout_mutex);
        std::cout << "Rage counter for main: " << rage << '\n';
    }
 
    a.join();
    b.join();
}

C++的例子来自于cppreference, 当使用该关键字声明时，每个线程都有自己的副本，当通过名称引用时，将使用与当前线程关联的副本。而如果在类的成员上使用thread_local关键字修饰，则在同一个线程内该类的多个成员都会共享该变量，这一点和static关键字一致。

“伪共享”

当多个不同的线程修改恰巧位于同一缓存行的不同变量时，称为“伪共享”。下面使用一段代码来说明该问题：

#define _MULTI_THREADED
#define _GNU_SOURCE
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdint.h>
#include <unistd.h>
#include <sched.h>
#include <pthread.h>
#include <numa.h>
#include <sys/types.h>

/*
 * A thread on each numa node seems to provoke cache misses
 */
#define         LOOP_CNT        (5 * 1024 * 1024)

#if defined(__x86_64__) || defined(__i386__)
static __inline__ uint64_t rdtsc() {
    unsigned hi, lo;
    __asm__ __volatile__ ( "rdtsc" : "=a"(lo), "=d"(hi));
    return ( (uint64_t)lo) | ( ((uint64_t)hi) << 32);
}

#elif defined(__aarch64__)
static __inline__ uint64_t rdtsc(void)
{
    uint64_t val;

    /*
     * According to ARM DDI 0487F.c, from Armv8.0 to Armv8.5 inclusive, the
     * system counter is at least 56 bits wide; from Armv8.6, the counter
     * must be 64 bits wide.  So the system counter could be less than 64
     * bits wide and it is attributed with the flag 'cap_user_time_short'
     * is true.
     */
    asm volatile("mrs %0, cntvct_el0" : "=r" (val));

    return val;
}
#endif


/*
 * Create a struct where reader fields share a cacheline with the hot lock field.
 * Compiling with -DNO_FALSE_SHARING inserts padding to avoid that sharing.
 */
typedef struct _buf {
  long lock0;
  long lock1;
  long reserved1;
#if defined(NO_FALSE_SHARING)
  long pad[5];   // to keep the 'lock*' fields on their own cacheline.
#else
  long pad[1];  // to provoke false sharing.
#endif
  long reader1;
  long reader2;
  long reader3;
  long reader4;
} buf __attribute__((aligned (64)));

buf buf1;
buf buf2;

volatile int wait_to_begin = 1;
struct thread_data *thread;
int max_node_num;
int num_threads;
char * lock_thd_name = "lock_th";
char * reader_thd_name = "reader_thd";

#define checkResults(string, val) {             \
 if (val) {                                     \
   printf("Failed with %d at %s", val, string); \
   exit(1);                                     \
 }                                              \
}

struct thread_data {
    pthread_t tid;
    long tix;
    long node;
    char *name;
};

/*
 * Bind a thread to the specified numa node.
*/
void setAffinity(void *parm) {
   volatile uint64_t rc, j;
   int node        = ((struct thread_data *)parm)->node;
   char *func_name = ((struct thread_data *)parm)->name;

   numa_run_on_node(node);
   pthread_setname_np(pthread_self(),func_name);
}

/*
 * Thread function to simulate the false sharing.
 * The "lock" threads will test-n-set the lock field,
 * while the reader threads will just read the other fields
 * in the struct.
 */
extern void *read_write_func(void *parm) {

   int tix = ((struct thread_data *)parm)->tix;
   uint64_t start, stop, j;
   char *thd_name = ((struct thread_data *)parm)->name;

   // Pin each thread to a numa node.
   setAffinity(parm);

   // Wait for all threads to get created before starting.
   while(wait_to_begin) ;

   start = rdtsc();
   for(j=0; j<LOOP_CNT; j++) {

      // Check for lock thread.
      if (*thd_name == *lock_thd_name) {
          __sync_lock_test_and_set(&buf1.lock0, 1 );
          buf1.lock0 += 1;
          buf2.lock1 = 1;

      } else {
         // Reader threads.

         switch(tix % max_node_num) {
            volatile long var;
            case 0:
              var = *(volatile uint64_t *)&buf1.reader1;
              var = *(volatile uint64_t *)&buf2.reader1;
              break;
            case 1:
              var = *(volatile uint64_t *)&buf1.reader2;
              var = *(volatile uint64_t *)&buf2.reader2;
              break;
            case 2:
              var = *(volatile uint64_t *)&buf1.reader3;
              var = *(volatile uint64_t *)&buf2.reader3;
              break;
            case 3:
              var = *(volatile uint64_t *)&buf1.reader4;
              var = *(volatile uint64_t *)&buf2.reader4;
              break;
         };
     };
  }  // End of for LOOP_CNT loop

  // Print out stats
  //
  stop = rdtsc();
  int cpu = sched_getcpu();
  int node = numa_node_of_cpu(cpu);
  printf("%ld mticks, %s (thread %d), on node %d (cpu %d).\n", (stop-start)/1000000, thd_name, tix, node, cpu);

  return NULL;
}

int main ( int argc, char *argv[] )
{
  int     i, n, rc=0;

  if ( argc != 2 ) /* argc should be 2 for correct execution */
  {
   printf( "usage: %s <n>\n", argv[0] );
   printf( "where \"n\" is the number of threads per node\n");
   exit(1);
  }

  if ( numa_available() < 0 )
  {
   printf( "NUMA not available\n" );
   exit(1);
  }

  int thread_cnt = atoi(argv[1]);

  max_node_num = numa_max_node();
  if ( max_node_num == 0 )
    max_node_num = 1;
  int node_cnt = max_node_num + 1;

  // Use "thread_cnt" threads per node.
  num_threads = (max_node_num +1) * thread_cnt;

  thread = malloc( sizeof(struct thread_data) * num_threads);

  // Create the first half of threads as lock threads.
  // Assign each thread a successive round robin node to
  // be pinned to (later after it gets created.)
  //
  for (i=0; i<=(num_threads/2 - 1); i++) {
     thread[i].tix = i;
     thread[i].node = i%node_cnt;
     thread[i].name = lock_thd_name;
     rc = pthread_create(&thread[i].tid, NULL, read_write_func, &thread[i]);
     checkResults("pthread_create()\n", rc);
     usleep(500);
  }

  // Create the second half of threads as reader threads.
  // Assign each thread a successive round robin node to
  // be pinned to (later after it gets created.)
  //
  for (i=((num_threads/2)); i<(num_threads); i++) {
     thread[i].tix = i;
     thread[i].node = i%node_cnt;
     thread[i].name = reader_thd_name;
     rc = pthread_create(&thread[i].tid, NULL, read_write_func, &thread[i]);
     checkResults("pthread_create()\n", rc);
     usleep(500);
  }

  // Sync to let threads start together
  usleep(500);
  wait_to_begin = 0;

  for (i=0; i <num_threads; i++) {
     rc = pthread_join(thread[i].tid, NULL);
     checkResults("pthread_join()\n", rc);
  }

  return 0;
}

这段代码是一个多线程的C代码。具体地，通过创建不同的线程并将它们绑定到特定的NUMA节点，伪造伪共享的效果：

• NUMA
  将每个线程绑定到特定的NUMA节点，确保线程在特定物理内存位置上运行；

• 高精度计时
  使用rdtsc指令测量代码段的执行时间；

• 伪共享和缓存行对齐
  结构体buf中成员可能会因为缓存行对齐而共享相同的缓存行。

  这里有两种编译模式：

  1. 默认模式下只有一个长整型的填充，用于触发伪共享；
  2. 另一模式通过定义 NO_FALSE_SHARING 预处理宏，增加额外的填充以避免伪共享。

下面是一些代码的详细解释和补充说明，可以按需跳过：

1. 结构体 buf 的设计：这个结构体有两个锁变量 lock0 和 lock1，以及四个变量 reader1 到 reader4。根据编译选项，这些变量可能位于同一缓存行（为了故意制造伪共享），或者通过插入填充以分开到不同的缓存行（为了避免伪共享）。

2. 线程功能 read_write_func：每个线程都会执行这个函数。如果是锁线程（通过名称判断），它会连续设置并增加锁变量；如果是读取线程，它则会读取指定的读变量。这样设计是为了在锁和读取之间制造大量的内存访问和潜在的竞争。

3. 主函数：首先检查 NUMA 是否可用，然后解析命令行参数来确定每个 NUMA 节点应创建多少线程。之后，为每个线程分配一个结构体 thread_data，用于存储线程的元数据，如线程 ID、所属 NUMA 节点和线程名称。然后创建线程，先是锁线程后是读取线程，每个线程都通过 pthread_create 调用启动。

下面介绍perf工具如何检查伪共享，以及如何解读结果。Linux perf工具和Intel VTune Profiler都支持检测伪共享。这里仅对perf工具进行展开，perf c2c会匹配不同线程的内存保存和和加载地址，并查看是否有在被修改的缓存行的命中。
这里先对上述C代码进行编译和运行，并在同时收集perf data：

clang -g false_sharing_example.c -pthread -lnuma -o false_sharing

./false_sharing.exe <number of threads per node>

sudo perf c2c record -F 60000 -a -u --ldlat 50 sleep 3

结果：

结果1：HITM代表的是在修改后的cacheline中命中的负载，这是伪共享发生的关键指标。 Remote HITM是跨NUMA节点，是最贵的操作；

结果2：第二个结果是个排序的热度，按cacheline的远程HITM或本地HITM进行排序，Rmt LLC Load Hitm标记了跨NUMA节点；

结果3：访问cache line的平均延迟、CPU时钟周期、线程pid、函数之类的信息，具体的：

• Shared Data Cache Line Table：每一行代表一个缓存行，列出内存地址、所属NUMA节点、页面访问计数（PA cnt）、命中次数（Hitm）、以及其他的一些命中和失效统计数据。
  可以看出缓存行地址分别有超过50,000次的总访问（Total records），它们在本地节点（LclHitm）和远程节点（RmtHitm）上的命中次数，这可以显示出在不同节点间的数据共享模式。
• Shared Cache Line Distribution Pareto：展示缓存行命中的分布情况。可以看到远程命中（RmtHitm）和本地命中（LclHitm）的百分比，这是衡量NUMA节点之间内存访问效率的重要指标。
  比如，对于第一行（#0）的缓存行，有大约30%的访问是本地命中，也有相似的百分比是远程命中，有相当比例的内存访问需要跨越 NUMA 节点，这通常会导致更高的延迟。
• Code address, cycles, and symbols：列出了代码地址与其对应的 CPU 周期数，这有助于识别哪些函数可能对缓存行产生影响，并估计它们的影响大小。
  例如，对于不同的代码地址，有不同的本地和远程命中次数（lcl hitm 和 rmt hitm），可以识别出哪些代码路径可能导致不必要的远程内存访问。