作者：nanxiao

uftrace工具介绍

uftrace是一个追踪和分析C/C++程序的工具，其灵感来自于Linux kernel的ftrace框架（项目主页：https://github.com/namhyung/uftrace）。

（1）安装。
uftrace依赖于elfutils项目中的libelf，所以要首先安装libelf，而uftrace的安装则很简单：

# git clone https://github.com/namhyung/uftrace.git
# cd uftrace
# make
# make install

（2）使用。
以这个简单程序（test.cpp）为例：

#include <cstdio>

class A {
public:
        A() {printf("A is created\n");}
        ~A() {printf("A is destroyed\n");}
};

int main() {
        A a;
        return 0;
}

uftrace要求编译时指定-pg或-finstrument-functions选项：

# g++ -pg test.cpp

编译成功后，通过uftrace工具可以对程序进行分析：

# uftrace a.out
A is created
A is destroyed
# DURATION    TID     FUNCTION
   4.051 us [ 8083] | __cxa_atexit();
            [ 8083] | main() {
            [ 8083] |   A::A() {
  13.340 us [ 8083] |     puts();
  17.321 us [ 8083] |   } /* A::A */
            [ 8083] |   A::~A() {
   1.815 us [ 8083] |     puts();
   4.679 us [ 8083] |   } /* A::~A */
  26.051 us [ 8083] | } /* main */

可以看到输出结果包含了程序的运行流程以及各个函数的执行时间。另外也可以使用-k选项追踪内核的相关函数：

# uftrace -k a.out
A is created
A is destroyed
# DURATION    TID     FUNCTION
   1.048 us [ 8091] | __cxa_atexit();
   0.978 us [ 8091] | sys_clock_gettime();
   0.768 us [ 8091] | main();
            [ 8091] | sys_clock_gettime() {
            [ 8091] |   A::A() {
   0.699 us [ 8091] |   } /* sys_clock_gettime */
            [ 8091] |   sys_clock_gettime() {
            [ 8091] |     puts() {
   0.768 us [ 8091] |     } /* sys_clock_gettime */
            [ 8091] |     sys_newfstat() {
   1.466 us [ 8091] |       smp_irq_work_interrupt();
   4.819 us [ 8091] |     } /* sys_newfstat */
   3.422 us [ 8091] |     __do_page_fault();
            [ 8091] |     sys_clock_gettime() {
   1.327 us [ 8091] |       smp_irq_work_interrupt();
   3.701 us [ 8091] |     } /* puts */
......

通常我们需要把运行结果保存下来，便于以后分析，这时可以使用uftrace的record功能：

# uftrace record a.out
A is created
A is destroyed
# ls
a.out  test.cpp  uftrace.data

可以看到在当前目录下多了一个uftrace.data的文件夹，里面记录了关于这次程序运行的信息，随后就可以对程序进行分析了。举个例子，可以使用uftrace的replay功能对程序的运行进行一遍“回看”：

# uftrace replay
# DURATION    TID     FUNCTION
   3.980 us [ 8104] | __cxa_atexit();
            [ 8104] | main() {
            [ 8104] |   A::A() {
  30.660 us [ 8104] |     puts();
  34.781 us [ 8104] |   } /* A::A */
            [ 8104] |   A::~A() {
  27.378 us [ 8104] |     puts();
  30.591 us [ 8104] |   } /* A::~A */
  69.632 us [ 8104] | } /* main */

综上所述，uftrace在下面这两个方面可以给我们很大帮助：
（1）了解程序的执行流程；
（2）度量函数的运行时间，确定热点。
感兴趣的朋友不妨亲自一试！

time和/usr/bin/time

当我在bash中敲入time命令时，运行的其实是bash内置的time命令：

$ time

real    0m0.000s
user    0m0.000s
sys     0m0.000s
$ type time
time is a shell keyword

这个time命令有一个-p选项，表示以posix格式输出：

$ time -p
real 0.00
user 0.00
sys 0.00

除此以外，还有一个time命令。不过我当前的机器并没有安装这个程序：

$ which time
which: no time in (/home/xiaonan/.cargo/bin:/usr/local/sbin:/usr/local/bin:/usr/bin:/opt/cuda/bin:/usr/lib/jvm/default/bin:/usr/bin/site_perl:/usr/bin/vendor_perl:/usr/bin/core_perl)

安装一下，对比bash内置的time命令：

$ sudo pacman -S time
$ type time
time is a shell keyword
$ which time
/usr/bin/time

单独运行“/usr/bin/time -p”，只会输出命令的帮助选项：

$ /usr/bin/time -p
Usage: /usr/bin/time [-apvV] [-f format] [-o file] [--append] [--verbose]
       [--portability] [--format=format] [--output=file] [--version]
       [--help] command [arg...]

需要加上具体的需要度量时间的命令：

$ /usr/bin/time -p echo

real 0.00
user 0.00
sys 0.00

此外也可以给出命令执行的详细信息：

$ /usr/bin/time -v echo

    Command being timed: "echo"
    User time (seconds): 0.00
    System time (seconds): 0.00
    Percent of CPU this job got: 0%
    Elapsed (wall clock) time (h:mm:ss or m:ss): 0:00.00
    Average shared text size (kbytes): 0
    Average unshared data size (kbytes): 0
    Average stack size (kbytes): 0
    Average total size (kbytes): 0
    Maximum resident set size (kbytes): 1536
    Average resident set size (kbytes): 0
    Major (requiring I/O) page faults: 0
    Minor (reclaiming a frame) page faults: 70
    Voluntary context switches: 1
    Involuntary context switches: 1
    Swaps: 0
    File system inputs: 0
    File system outputs: 0
    Socket messages sent: 0
    Socket messages received: 0
    Signals delivered: 0
    Page size (bytes): 4096
    Exit status: 0

参考资料：
/usr/bin/time: not the command you think you know。

Linux系统查看可用内存

http://www.linuxatemyram.com/提到使用free命令查看Linux系统使用内存时，used一项会把当前cache的大小也会加进去，这样会造成free这一栏显示的内存特别少：

$ free -m
               total        used        free      shared  buff/cache   available
Mem:           1504        1491          13           0         855      869
Swap:          2047           6        2041

可是实际上，cache根据应用程序的需要是可以回收利用的，因此free这一栏并不能真实地表现有多少“可以使用”的内存。实际系统可用内存应该以available数据为准。

linuxatemyram所提到的free命令也许是比较老的版本，我尝试了RHEL 7.2，Ubuntu 16.04和Arch Linux这3个Linux发行版，均没有出现used包含cache的情况：

$ free -m
              total        used        free      shared  buff/cache   available
Mem:          64325       47437        3150        1860       13737       14373

另外，从man free命令中也可以得到，目前计算used的值是要减掉free和buff/cache的：

used Used memory (calculated as total – free – buffers – cache)

可以使用-w命令行选项得到buff和cache各自使用的数量：

$ free -wm
              total        used        free      shared     buffers       cache   available
Mem:          64325       48287        2476        1859        1430       12131       13524

需要注意的是，free表示的是当前完全没有被程序使用的内存；而cache在有需要时，是可以被释放出来以供其它进程使用的（当然，并不是所有cache都可以释放，比如当前被用作ramfs的内存）。而available才真正表明系统目前可以提供给应用程序使用的内存。/proc/meminfo从3.14内核版本开始提供MemAvailable的值；在2.6.27~3.14版本之间，是free程序自己计算available的值；早于2.6.27版本，available的值则同free一样。

参考资料：
Understanding output of free in Ubuntu 16.04；
How can I get the amount of available memory portably across distributions?。

HE-API项目简介

HE-API提供一个统一的接口，屏蔽了底层使用的SHE library的细节，使对加密不是很了解的人也可以轻松掌握（代码在这里）。HE-API目前只支持HElib，通过使用不同的编译选项（FXPT，BINARY）来生成支持不同数据类型的库：helib.a.fxpt，helib.a.binary和helib.a.ulong。下面以testInteger函数为例，来分析如何使用：

template <unsigned long nb_tests>
int testInteger() {
  // Determine if the test should run
  #ifdef BINARY
  unsigned long run = HE::supports_bit_encryption;
  #else
  unsigned long run = HE::supports_unsigned_encryption;
  #endif

  if (!run) {
    return 0;
  }

  timing t;

  gmp_randclass prng(gmp_randinit_default);
//  prng.seed(0);
  prng.seed(time(NULL)); // To set different seeds

  void* parameters = nullptr;
  void* sk = nullptr;
  void* pk = nullptr;
  void* evk = nullptr;

  // Init
  t.start();
  HE::init(&parameters);
  t.stop("Init");

  // Keygen
  t.start();
  HE::keygen(parameters, &sk, &pk, &evk);
  t.stop("Keygen");
  // HE::serialize_sk("sk.bin", sk);
  // std::cout << "serialized?" << std::endl;

  // Random messages
  unsigned long* messages1 = new unsigned long[nb_tests];
  unsigned long* messages2 = new unsigned long[nb_tests];
  for (unsigned long i = 0; i < nb_tests; i++) {
    messages1[i] =
        mpz_class(prng.get_z_range(HE::plaintext_modulus)).get_ui();
    messages2[i] =
        mpz_class(prng.get_z_range(HE::plaintext_modulus)).get_ui();
  }

  // Encrypt
  void** ciphertexts1 = new void* [nb_tests];
  void** ciphertexts2 = new void* [nb_tests];
  t.start();
  for (unsigned long i = 0; i < nb_tests; i++) {
    HE::encryptInteger(pk, &(ciphertexts1[i]), messages1[i]);
    HE::encryptInteger(pk, &(ciphertexts2[i]), messages2[i]);
  }
  t.stop("Encrypt Integer", nb_tests * 2);

  // Decrypt
  unsigned long* messages1_decrypted = new unsigned long[nb_tests];
  unsigned long* messages2_decrypted = new unsigned long[nb_tests];
  t.start();
  for (unsigned long i = 0; i < nb_tests; i++) {
    HE::decryptInteger(sk, pk, ciphertexts1[i], &(messages1_decrypted[i]));
    HE::decryptInteger(sk, pk, ciphertexts2[i], &(messages2_decrypted[i]));
  }
  t.stop("Decrypt Integer", nb_tests * 2);

  // Correctness of decryption
  for (unsigned long i = 0; i < nb_tests; i++) {
    assert(messages1[i] == messages1_decrypted[i]);
    assert(messages2[i] == messages2_decrypted[i]);
  }

  // Homomorphic additions
  unsigned long* messages_added = new unsigned long[nb_tests];
  for (unsigned long i = 0; i < nb_tests; i++) {
    messages_added[i] = (messages1[i] + messages2[i]) % HE::plaintext_modulus;
  }
  void** ciphertexts_added = new void* [nb_tests];
  t.start();
  for (unsigned long i = 0; i < nb_tests; i++) {
    HE::add(pk, evk, &(ciphertexts_added[i]), ciphertexts1[i], ciphertexts2[i]);
  }
  t.stop("Homomorphic Addition", nb_tests);

  // Correctness of addition
  unsigned long* messages_added_decrypted = new unsigned long[nb_tests];
  for (unsigned long i = 0; i < nb_tests; i++) {
    HE::decryptInteger(sk, pk, ciphertexts_added[i],
                     &(messages_added_decrypted[i]));
    assert(messages_added_decrypted[i] == messages_added[i]);
  }

  // Homomorphic multiplications
  unsigned long* messages_multiplied = new unsigned long[nb_tests];
  for (unsigned long i = 0; i < nb_tests; i++) {
    messages_multiplied[i] = (messages1[i] * messages2[i]) % HE::plaintext_modulus;
  }
  void** ciphertexts_multiplied = new void* [nb_tests];
  t.start();
  for (unsigned long i = 0; i < nb_tests; i++) {
    HE::mul(pk, evk, &(ciphertexts_multiplied[i]), ciphertexts1[i],
          ciphertexts2[i]);
  }
  t.stop("Homomorphic Multiplication", nb_tests);

  // Correctness of multiplication
  unsigned long* messages_multiplied_decrypted = new unsigned long[nb_tests];
  for (unsigned long i = 0; i < nb_tests; i++) {
    HE::decryptInteger(sk, pk, ciphertexts_multiplied[i],
                     &(messages_multiplied_decrypted[i]));
    assert(messages_multiplied_decrypted[i] == messages_multiplied[i]);
  }

  delete[] messages1;
  delete[] messages2;
  delete[] messages_added;
  delete[] messages_added_decrypted;
  delete[] messages_multiplied;
  delete[] messages_multiplied_decrypted;

  for(long i=0; i< nb_tests; i++)
  {
      HE::freeup_ciphertext(pk,ciphertexts1[i]);
      HE::freeup_ciphertext(pk,ciphertexts2[i]);
      HE::freeup_ciphertext(pk,ciphertexts_added[i]);
      HE::freeup_ciphertext(pk,ciphertexts_multiplied[i]);
  }

  delete[] ciphertexts1;
  delete[] ciphertexts2;
  delete[] ciphertexts_added;
  delete[] ciphertexts_multiplied;

  HE::freeup_keys(parameters,sk,pk,evk);

  return 0;
}

（1）HE-API使用了gmp项目：
a）gmp_randclass类用来生成随机数：

......
gmp_randclass prng(gmp_randinit_default);
//  prng.seed(0);
prng.seed(time(NULL)); // To set different seeds
......
messages1[i] =
        mpz_class(prng.get_z_range(HE::plaintext_modulus)).get_ui();
messages2[i] =
        mpz_class(prng.get_z_range(HE::plaintext_modulus)).get_ui();

b）mpz_class用来表示整数。get_ui()返回mpz_class的最低位的unsigned long。以Binary为例，mpz_class(prng.get_z_range(HE::plaintext_modulus)).get_ui();随机返回0和1。

（2）另外就是需要注意加法和乘法时的取模运算：

......
messages_added[i] = (messages1[i] + messages2[i]) % HE::plaintext_modulus;
......
messages_multiplied[i] = (messages1[i] * messages2[i]) % HE::plaintext_modulus;

仍以Binary为例，此时PLAINTEXT_MODULUS的值为2，即要对2取模。操作数是1个bit，取值为0或1，加密结果对应的也是0或1。

P.S.，在编译HEAT使用HElib时可能会遇到错误，具体参考这个issue。

CUDA编程笔记（17）——Matrix transpose (shared memory)

An Efficient Matrix Transpose in CUDA C/C++中Coalesced Transpose Via Shared Memory一节讲述如何使用shared memory高效地实现matrix transpose：

__global__ void transposeCoalesced(float *odata, const float *idata)
{
  __shared__ float tile[TILE_DIM][TILE_DIM];

  int x = blockIdx.x * TILE_DIM + threadIdx.x;
  int y = blockIdx.y * TILE_DIM + threadIdx.y;
  int width = gridDim.x * TILE_DIM;

  for (int j = 0; j < TILE_DIM; j += BLOCK_ROWS)
 tile[threadIdx.y+j][threadIdx.x] = idata[(y+j)*width + x];

  __syncthreads();

  x = blockIdx.y * TILE_DIM + threadIdx.x;  // transpose block offset
  y = blockIdx.x * TILE_DIM + threadIdx.y;

  for (int j = 0; j < TILE_DIM; j += BLOCK_ROWS)
 odata[(y+j)*width + x] = tile[threadIdx.x][threadIdx.y + j];
}

（1）idata和odata分别是表示1024X1024个float元素的matrix的连续内存：

IMG_20170216_145959[1]

（2）关于blockIdx和threadIdx的取值，参考下面的图：

IMG_20170216_151045[1]

shared memory请参考下面的图：

IMG_20170216_151058[1]

（3）在下列代码中：

for (int j = 0; j < TILE_DIM; j += BLOCK_ROWS)
    tile[threadIdx.y+j][threadIdx.x] = idata[(y+j)*width + x];

每一个block是32X8大小，需要循环4次，把一个block内容copy到tile这个shared memory中。idata是按行读取的，因此是coalesced。

IMG_20170216_152636[1]

（4）最难理解的在最后一部分：

x = blockIdx.y * TILE_DIM + threadIdx.x;  // transpose block offset
y = blockIdx.x * TILE_DIM + threadIdx.y;

for (int j = 0; j < TILE_DIM; j += BLOCK_ROWS)
    odata[(y+j)*width + x] = tile[threadIdx.x][threadIdx.y + j];

对比从idata读取数据和写数据到odata：

......
tile[threadIdx.y+j][threadIdx.x] = idata[(y+j)*width + x];
......
odata[(y+j)*width + x] = tile[threadIdx.x][threadIdx.y + j];
......

可以看到是把tile做了transpose的数据（行变列，列变行）传给odata。而确定需要把tile放到哪里位置的代码：

x = blockIdx.y * TILE_DIM + threadIdx.x;  // transpose block offset
y = blockIdx.x * TILE_DIM + threadIdx.y;

假设blockIdx.x为31，blockIdx.y为0，threadIdx.x为1，threadIdx.y为2。根据上述代码，计算x和y：

x = 0 * 32 + 1;
y = 31 * 32 + 2;

根据下面的图，可以看到是把东北角的内容copy的西南角：

IMG_20170216_155616[1]

与*NIX有关的杂志

本文介绍一些我接触过的与*nix有关的杂志。

首先要提到的就是Linux Journal（官方网址：http://www.linuxjournal.com/）。根据Wikipedia的介绍，这应该是最早的一本介绍Linux的杂志：

Linux Journal was the first magazine to be published about the Linux kernel and operating systems based on it. It was established in 1994.

不过Linux Journal现在不再发行纸质版了，只提供电子版。该杂志这段时间有一项促销活动：即截至到今年3月28日前，你只需花28.5美元（使用优惠码：2017ARCH可免10美元），就可以购买到从1994年到2016年杂志的电子合订版：

1

个人觉得还是很划算的，虽然有些文章已经年代久远，但是还是很有参考价值的。另外，Linux Journal也会将其文章发布到官网上供读者免费阅读。因次，是否愿意花钱买合订本或者订阅，就“仁者见仁，智者见智”了。

再说一下Linux Format（官方网址：http://www.linuxformat.com/）和Linux Voice（官方网址：https://www.linuxvoice.com/），二者都是英国出版的Linux杂志。不知是否因为Linux Voice的主创团队均出自Linux Format的缘故，二者有太多类似之处：都同时提供纸质版和电子版，都提供过刊的免费下载，等等。也许是由于版权原因，我在国内没见到过这两种杂志。在国外我阅读过纸质版，制作很精美，每期还附赠光盘。感兴趣的朋友可以下载它们提供的过刊了解一下。

以上提到的都是以Linux为主题的杂志，再介绍一个以BSD为主打内容的杂志：BSD magazine（官方网址：https://bsdmag.org/）。这是一本真正免费的杂志，订阅以后，你不需花一分钱，就会收到每一期。从这本杂志里，你可以获悉时下BSD家族的最新动态，虽然偶尔也会有Linux的内容出现。去年年底，这本杂志一度宣布要停刊了，不过目前又撤销了这个决定。我个人很希望这本杂志可以继续办下去。

最后，我很希望自己的国家能有一本中文版的Linux杂志。但是想想现在的情形，我们的时间都被其它的事物占去了，也许根本无法诞生这样一本杂志了。。。

后记：对于其它的类似杂志，比如：http://www.linux-magazine.com/。因为我没有一点了解，就不发表评论了。

如何选择Linux发行版？

@YeimMeMeMes 在其个人社交媒体主页上贴出了一张如何选择Linux发行版的图（原图链接：https://pbs.twimg.com/media/C3PoAagWMAAe5YT.jpg:large）：

C3PoAagWMAAe5YT

因为这幅图上所列举的大部分Linux发行版我都没怎么使用过，所以我没有资格对这张图是否合理发表评论，仅供读者参考。下面我仅对我曾经使用过的一些Linux发行版谈些感受：

（1）这个图上并没有出现一些Linux的商业版本，譬如，RedHat的Red Hat Enterprise Linux，SuSE的SUSE Linux Enterprise Server，等等。我以前做过这两个Linux商业版本上的测试工作，感觉还是很稳定的。给我一个很深的印象就是在Red Hat Enterprise Linux上编译和安装最新版本的Linux内核总是非常顺利，而在其它发行版上有时会遇到一些莫名其妙的问题。从去年开始，Red Hat Enterprise Linux对开发者已经免费了（可参考这篇文章：As in beer: Red Hat offers RHEL free to developers），有兴趣的朋友可以体验一下。

（2）最近两个月，在工作中我主要使用Arch Linux。Arch Linux在软件包更新方面非常及时。有时你发现当前软件包不是最新的，只要在其网站上提一个请求，很快就会有维护者响应。如果你总是希望可以使用上最新的软件版本，不妨尝试一下Arch Linux。

Linux系统上如何查看进程（线程）所运行的CPU

本文介绍如何在Linux系统上查看某个进程（线程）所运行的CPU，但在此之前我们需要弄清楚两个基本概念：

（1）Linux操作系统上的进程和线程没有本质区别，在内核看来都是一个task。属于同一个进程的各个线程共享某些资源，每一个线程都有一个ID，而“主线程”的线程ID同进程ID，也就是我们常说的PID是一样的。

（2）使用lscpu命令，可以得到当前系统CPU的数量：

$ lscpu
......
CPU(s):                24
On-line CPU(s) list:   0-23
Thread(s) per core:    2
Core(s) per socket:    6
Socket(s):             2
......

系统有2个物理CPU（Socket(s): 2），每个CPU有6个core（Core(s) per socket: 6），而每个core又有2个hardware thread（Thread(s) per core: 2）。所以整个系统上一共有2X6X2=24（CPU(s):24）个逻辑CPU，也就是实际运行程序的CPU。

使用htop命令可以得到进程（线程）所运行的CPU信息，但是htop默认情况下不会显示这一信息：

1
开启方法如下：
（1）启动htop后，按F2（Setup）：

2
（2） 在Setup中选择Columns，然后在Available Columns中选择PROCESSOR - ID of the CPU the process last executed, 接下来按F5（Add）和F10（Done）即可：

3

现在htop就会显示CPU的相关信息了。需要注意的是，其实htop显示的只是“进程（线程）之前所运行的CPU”，而不是“进程（线程）当前所运行的CPU”，因为有可能在htop显示的同时，操作系统已经把进程（线程）调度到其它CPU上运行了。

下面是一个运行时会包含4个线程的程序：

#include <omp.h>

int main(void){

        #pragma omp parallel num_threads(4)
        for(;;)
        {
        }

        return 0;
}

编译并运行代码：

$ gcc -fopenmp thread.c
$ ./a.out &
[1] 17235

使用htop命令可以得到各个线程ID，以及在哪个CPU上运行：

4

参考资料：
How to find out which CPU core a process is running on；
闲侃CPU（一）。

Linux线程模型浅析

Linux的线程是“轻量级进程”（Light-Weight Process，即LWP）。在Linux系统上运行一个程序时，操作系统会为这个程序创建一个进程，其实也就是“主线程”，后续则可以产生出更多的线程。每个进程都有一个PID（Process ID），每个线程也会有一个TID（Thread ID），属于同一进程的线程各自有拥有不同的TID，但它们的PID是相同的，都等于“主线程”的TID。因此从本质上来讲，Linux系统下的进程和线程没有区别，只不过同一进程中的线程可以共享某些资源。下面看一个例子：

#include <unistd.h>
#include <omp.h>

int main(void){

        #pragma omp parallel num_threads(4)
        for(;;)
        {
            sleep(1);
        }

        return 0;
}

编译并在后台运行这个程序：

$ gcc -fopenmp threads.c
$ ./a.out &
[1] 9802

进程的PID是9802，用ps -T pid命令查看进程的线程信息：

$ ps -T 9802
  PID  SPID TTY      STAT   TIME COMMAND
 9802  9802 pts/1    Sl     0:00 ./a.out
 9802  9803 pts/1    Sl     0:00 ./a.out
 9802  9804 pts/1    Sl     0:00 ./a.out
 9802  9805 pts/1    Sl     0:00 ./a.out

其中SPID即为TID。可以看到当前进程的PID是9802，共包含4个线程，其TID依次为：9802，9803，9804和9805，其中PID和SPID相同的线程即为主线程。

CUDA编程笔记（16）——Shared Memory

这篇笔记摘自Professional CUDA C Programming：

Global memory is large, on-board memory and is characterized by relatively high latencies. Shared memory is smaller, low-latency on-chip memory that offers much higher bandwidth than global memory. You can think of it as a program-managed cache. Shared memory is generally useful as:
➤ An intra-block thread communication channel
➤ A program-managed cache for global memory data
➤ Scratch pad memory for transforming data to improve global memory access patterns

Shared memory is partitioned among all resident thread blocks on an SM; therefore, shared memory is a critical resource that limits device parallelism. The more shared memory used by a kernel, the fewer possible concurrently active thread blocks.