Futex 简述

Posted on 2021/04/06 by qing

简介：futex 全称为Fast User-space Mutex，是Linux 2.5.7 内核引入的锁原语，不同于其他进程间通信IPC原语（如信号量Semaphore、信号Signal和各种锁pthread_mutex_lock），futex更轻量级、快速，一般应用开发人员可能很少用到，但可基于futex实现各类读写锁、屏障（barriers）和信号机制等。

相关背景

在Linux的早期版本（内核Linux 2.5.7 版本以前），进程间通信（Inter-Process Communication，IPC）沿用的是传统Unix系统和System V 的IPC，如信号量（Semaphores）和Socket 等，这些IPC 均基于系统调用（System Call）。这类方法的缺点是当系统竞争度较低时，每次都进行系统调用，会造成较大系统开销。

原理和做法

用户程序每次调用IPC机制都会产生系统调用，程序发生用户态和内核态的切换，futex 的基本思想是竞争态总是很少发生的，只有在竞争态才需要进入内核，否则在用户态即可完成。futex的两个目标是：1）尽量避免系统调用；2）避免不必要的上下文切换（导致的TLB失效等）。

具体而言，任务获取一个futex 将发起带锁的减指令，并验证数值结果值是否为0（加上了锁），如果成功则可继续执行程序，失败（为已经占用的锁继续加锁）则任务在内核被阻塞。为相同futex 变量的加锁的任务被阻塞后放在同一个队列，解锁任务通过减少变量（只有一个加锁且锁队列为空）或进入内核从锁队列唤醒任务。

注意：futex 在Linux 的内核实现为一个系统调用（SYS_futex），用户程序如果直接调用它肯定会进入内核态，它还需要和其他语句（如原子操作）配合使用，新手在未理解其futex 原理和并发控制机制时极易犯错，这也是为什么不推荐直接使用它的原因。

继续阅读 →

记一次有趣的Bug – 返回值被截断为32位

Posted on 2020/10/19 by qing

上周修改了hdrt 库文件中头文件的include 关系，结果出现了一个有趣的bug。具体表现为：当函数foo() 调用某个函数fun_called()，返回的值ret_val 总是从64位被截断为32位。

首先，在foo() 函数头和func_called 函数尾输出ret_val，确认是返回值是在调用过程中被截断了。

其次，在gdb 中查看生成的代码，发现ret_val所存储的寄存器rax （返回值一般存储在rax寄存器中）在被返回时，被cltq 指令截断了高32 位。

  0x555555565adb <foo+42> callq 0x555555569874<fun_called>
  0x555555565ae0 <foo+47> cltq
  0x555555565ae2 <foo+49> mov %rax,-0x8(%rbp)
  0x555555565ae6 <foo+53> cmpq $0x0,-0x8(%rbp)
  0x555555565aeb <foo+58> jne 0x555555565b2e <foo+125>

最后，查了相关资料https://stackoverflow.com/a/26209434/1424948 可能原因是：

1）函数声明（prototype）中没有fun_called 的声明；

2）没有引用包含fun_called 声明的头文件。

默认情况下，调用函数foo 在不知道被调用函数fun_called 的返回值类型的情况下，会按照int 类型大小的值处理，即32位。

对于这个bug 其实有两个建议：

1 非特殊情况不要用强制类型转换（即type cast），(char *)这类转换会屏蔽很多暴露问题的warning；

2 要查看/消除warning，例如这个bug 实际隐藏在了warning 中，因为返回值被编译当做默认的int 类型返回时，获取返回值变量不是int 时则告警了类型不匹配。

利用/proc精确计算Linux系统的CPU利用率

Posted on 2020/09/25 by qing

Linux 系统并未提供直接获取CPU 利用率的接口，一些应用程序通过访问/proc 文件系统中系统的状态统计从而计算得到CPU利用率。常用查看进程及其相关信息的top 命令和htop 命令即属于这一类。

本文简单介绍如何利用/proc/stat 文件计算CPU 利用率，这种经典方法在top 和htop 工具中也被采用，在StackOverflow 也有说明；接着，将上面经典方法获取的CPU 利用率和一种极端情况下的单核单任务的CPU占用率进行比较，单核单任务指的是，在隔离的单独CPU 和核心上只运行该程序（如果你对这有疑问，可以参考下core affinity 、core isolation 和non irqbalance）。

看下图htop 工具的截图：该系统有8个CPU核心，每个核心的CPU利用率位于图上方横向柱状图。8个核心中1-7都是被隔离的，1/3/4/5/6/7每个核心都分配了一个名称为grt_simple_conc_ispc 的线程，每个线程CPU 占用率（CPU%）位于图下方第5 列，可以看出CPU利用率（上方）和每个程序占CPU利用率（下方）结果是有差异的。

方法一

一种最直接计算程序占用CPU 使用率的计算方法是，采样N 次，如果有R 次该程序正在执行，则其占用CPU使用率为 R/N × 100%。

Linux 在/proc/{pid}/stat 文件中记录进程ID 为pid 的进程统计信息（按照类别分为几十个字段，详见 https://man7.org/linux/man-pages/man5/proc.5.html ）。如果进程状态字符是R ，则表示进程正在运行（Running），如果状态字符是S ，则表示进程正在睡眠（Sleeping）。

将该方法作为CPU 利用率的前提是：该CPU 核心只运行该进程，尽量少地被中断。

计算CPU 利用率经典方法（方法二）

工具（如top 和htop）定时采样读取/proc/stat 文件内容，该文件记录了每个CPU核心所处不同状态的累计时间，再通过以下公式可计算得到指定核心CPU利用率：

previdle   = previdle + previowait
idle     = idle + iowait
prevnoidle  = prevuser + prevnice + prevsystem + previrq + prevsoftirq + prevsteal
noidle    = user + nice + system + irq + softirq + steal
prevtotal   = previdle + prevnonidle
total     = idle + nonidle
total_delta  = total - prevtotal
idle_delta  = idle - previdle
CPU_usage    = (total_delta - idle_delta)/total_delta

以prev开头的变量是上一次采用数据，否则是当前采样数据，通过计算两次采样之间的CPU空闲时间（idle_delta）和总计时间（total_delta）得到CPU利用率，这是procs/top 工具默认使用的方法，也是最常见CPU利用率统计方法。

方法三

方法和约束情况类似于方法一，周期性读取/proc/{pid}/stat文件，获取进程用户态时间utime 和核态时间stime，按照如下公式计算CPU利用率

CPU_usage = （utime+stime)/sample_interval

其中，utime和stime代表进程用户态时间和核态时间，sample_interval是采样间隔。

下面是负载由轻到高，三种方法得到的CPU 利用率：

Linux 内核文档PDF版（Linux kernel v5.8 documents pdf version）

Posted on 2020/07/14 by qing

你也可以在自己的Linux kernel 源码目录执行以下命令生成自己的pdf，但何必自己造轮子呢。

sudo apt-get install sphinxsearch
sudo apt-get install python-sphinx-rtd-theme
sudo apt-get install texlive-latex-recommended
sudo apt-get install texlive-base
sudo apt-get install graphviz
sudo apt-get install imagemagick
/usr/bin/virtualenv ~/sphinx_version
. ~/sphinx_version/bin/activate
pip install -r Documentation/sphinx/requirements.txt
make pdfdocs

安装RTAI5.2 基于Ubuntu18.04和4.14.111 内核

Posted on 2019/09/11 by qing

本文记录在我笔记本上安装最新版本RTAI（5.2）的过程和中间遇到的问题及解决方法，虽然不能覆盖所有问题，但希望能给后来者一些帮助。

安装的主要步骤：

1、安装操作系统和工具；

2、给内核打补丁并配置；

3、安装打补丁的内核与RTAI。

步骤一：安装操作系统和工具

1.1 安装操作系统

我选择的是Ubuntu18.04，因为这是带Linux 4.**.***内核的最新Ubuntu 版本（Ubuntu19.04 是以Linux5.**内核开始了）。而RTAI5.2 支持的最新内核版本即为4.14.111；

1.2 安装工具

这些工具是内核编译时需要的，下面命令可以保存为脚本执行

sudo apt install libncurses5-dev
sudo apt install libssl-dev
sudo apt install bison
sudo apt install flex
sudo apt install libssl-dev
sudo apt install libelf-dev
sudo apt install make gcc
sudo apt install patch
sudo apt install unzip
sudo apt install autoconf

注意：如果你使用的是不同的Linux 发布版（Redhat或openSUSE），有些包的名称是不同的，比如对于Redhat，libssl的安装包是libssl-devel。

注意：如果你采用的是Ubuntu16.04，那么可能因为包依赖的原因，你无法用apt install 命令安装libssl1.1，而这个包是在编译4.14.111 内核时必须的，所以建议你要么换更高版本OS，要么在Ubuntu 网站（ https://packages.debian.org/stretch/amd64/libssl1.1/download ）手动安装该包（sudo dpkg -i libssl1.1_1.1.0k-1~deb9u1_amd64.deb）。

1.3 安装已编译的Linux 内核4.14.111 （可选的）

该步骤是可选的，它会给系统安装上Linux4.14.111 的内核，从而获得一个默认的内核配置文件供后面使用，如果你是第一次安装RTAI，建议你执行该步骤。

在内核网站 https://kernel.ubuntu.com/~kernel-ppa/mainline/v4.14.111/ 下载内核安装包：

cd ~/Downloads/
wget https://kernel.ubuntu.com/~kernel-ppa/mainline/v4.14.111/linux-headers-4.14.111-0414111_4.14.111-0414111.201904052241_all.deb
wget https://kernel.ubuntu.com/~kernel-ppa/mainline/v4.14.111/linux-headers-4.14.111-0414111-lowlatency_4.14.111-0414111.201904052241_amd64.deb
wget https://kernel.ubuntu.com/~kernel-ppa/mainline/v4.14.111/linux-image-unsigned-4.14.111-0414111-lowlatency_4.14.111-0414111.201904052241_amd64.deb`
wget https://kernel.ubuntu.com/~kernel-ppa/mainline/v4.14.111/linux-modules-4.14.111-0414111-lowlatency_4.14.111-0414111.201904052241_amd64.deb

然后使用dpkg -i 命令安装

sudo dpkg -i *.deb #执行该命令是可能会遇到错，再重新执行该命令可以解决；
sudo update-grub
sudo reboot

重启后可以在Grub （长按shift进入Grub）中看到安装后的内核有“Generic” 和“lowlatency” 两种。如果进入Grub 有困难，在Grub 配置文件（/etc/default/grub）中修改配置`GRUB_TIMEOUT_STYLE=hidden` 为`GRUB_TIMEOUT_STYLE=false`并更新Grub 菜单`sudo update-grub`。

步骤二：内核打补丁和编译

2.1 下载内核 （https://cdn.kernel.org/pub/linux/kernel/v4.x/）

内核的名称为 linux-4.1.111.tar.gz，为之后编译和安装方便，将源码解压到`/usr/src` 中，并创建一个软链接到该源码目录。

cd /usr/src
sudo tar xvf linux-4.1.111.tar.gz
sudo ln -sf linux-4.1.111 linux

然后，从`/boot` 中拷贝配置文件：

cd /usr/src/linux
sudo cp /boot/config-4.14.111-0414111-lowlatency .config

如果你已经有了一个配置文件（比如你安装过老版本RTAI，在其Linux 内核中拷贝其配置文件即可）uIf you already have a configuration file (e.g. in your old RTAI patched Linux system), just copy it to the source path(`/usr/src/linux`).

2.2 给内核打补丁（Ubuntu 的补丁和RTAI 的补丁）

Ubuntu 是Linux 的一个发行版本，并对Linux 内核代码做了少量修改，所以在编译内核前应该打上Ubuntu 的补丁（https://kernel.ubuntu.com/~kernel-ppa/mainline/v4.14.111/）。

cd ~/Downloads/
wget https://kernel.ubuntu.com/~kernel-ppa/mainline/v4.14.111/0001-base-packaging.patch
wget https://kernel.ubuntu.com/~kernel-ppa/mainline/v4.14.111/0002-UBUNTU-SAUCE-add-vmlinux.strip-to-BOOT_TARGETS1-on-p.patch
wget https://kernel.ubuntu.com/~kernel-ppa/mainline/v4.14.111/0003-UBUNTU-SAUCE-tools-hv-lsvmbus-add-manual-page.patch
wget https://kernel.ubuntu.com/~kernel-ppa/mainline/v4.14.111/0004-adhoc-from-__future__-import-syncconfig.patch
wget https://kernel.ubuntu.com/~kernel-ppa/mainline/v4.14.111/0005-UBUNTU-SAUCE-no-up-disable-pie-when-gcc-has-it-enabl.patch
wget https://kernel.ubuntu.com/~kernel-ppa/mainline/v4.14.111/0006-debian-changelog.patch
wget https://kernel.ubuntu.com/~kernel-ppa/mainline/v4.14.111/0007-configs-based-on-Ubuntu-4.14.0-11.13.patch
cd /usr/src/linux
sudo patch -p1 < ~/Downloads/0001-base-packaging.patch
sudo patch -p1 < ~/Downloads/0002-UBUNTU-SAUCE-add-vmlinux.strip-to-BOOT_TARGETS1-on-p.patch
sudo patch -p1 < ~/Downloads/0003-UBUNTU-SAUCE-tools-hv-lsvmbus-add-manual-page.patch
sudo patch -p1 < ~/Downloads/0004-adhoc-from-__future__-import-syncconfig.patch
sudo patch -p1 < ~/Downloads/0005-UBUNTU-SAUCE-no-up-disable-pie-when-gcc-has-it-enabl.patch
sudo patch -p1 < ~/Downloads/0006-debian-changelog.patch
sudo patch -p1 < ~/Downloads/0007-configs-based-on-Ubuntu-4.14.0-11.13.patch

下载RTAI5.2 并给内核打上相应的补丁：

wget https://www.rtai.org/userfiles/downloads/RTAI/rtai-5.2.tar.bz2
sudo cp rtai-5.2.tar.bz2 /usr/src/
sudo tar xvf rtai-5.2.tar.bz2
sudo ln -sf rtai-5.2 rtai
cd /usr/src/linux
sudo patch -p1 < /usr/src/rtai/base/arch/x86/patches/hal-linux-4.14.111-x86-3.patch

同样方便起见，我们也为rtai 的源码创建了一个软链接。

注意：安装RTAI补丁和PREEMPT-RT补丁的过程是类似的，如果你想安装PREEMPT-RT补丁，它的地址在这里。下载xz或gz格式后的补丁，可以用xz工具解压发现，是一个个编了序号的补丁，通过下面命令逐个应用补丁

patch -p1 -i /path/to/004-patch.x.y.z

也可以通过下面命令应用所有补丁

xzcat /path/to/patch.xz | patch -p1

bzcat /path/to/patch.xz | patch -p1

2.3 配置内核

配置内核主要参考下面的资料：

RTAI-5.2 源码目录下的关于配置的备注文件 README.CONF_RMRKS
https://github.com/relacs/makertai
https://www.rtai.org/userfiles/downloads/RTAILAB/RTAI-TARGET-HOWTO.txt
https://github.com/relacs/makertai

如果你的配置文件是从其他老的内核里拷贝过来的，首先应执行：

cd /usr/src/linux
sudo make oldconfig

否则直接执行：

sudo make menuconfig

下面是配置项中应修改的部分：

[改为 -rtai] General setup -> Local Version
[改为 None] General setup -> Stack Protector buffer overflow detection
[Enable] Processor type and features -> Interrupt pipeline
[Disable] Power management and ACPI options -> CPU Frequency Scaling
[Disable] Power management and ACPI options -> ACPI Support -> Processor
[Disable] Power management and ACPI options -> CPU Idle -> CPU idle PM support
[Disable] Kernel hacking -> Compile-time checks and compiler options -> Compile the kernel with debug info
[Disable] Kernel hacking -> Tracers
[Disable] Device Drivers -> Microsoft Hyper-V guest support
[Disable] Device Drivers -> Staging drivers -> Data acquisition support (comedi)

在 README.CONF_RMRKS 文件中要求disable `AUDITSYSCALL`，但是我们在选项中没有找到这一项。一个可替代的方法是编辑 `/usr/src/linux/init/Kconfig`文件，找到`AUDITSYSCALL` 如下部分：

config AUDITSYSCALL
def_bool y
depends on AUDIT && HAVE_ARCH_AUDITSYSCALL

替换为：

config AUDITSYSCALL
    bool “Enable system-call auditing support”
    depends on AUDIT && HAVE_ARCH_AUDITSYSCALL
    default y if SECURITY_SELINUX
    help
      Enable low-overhead system-call auditing infrastructure that
      can be used independently or with another kernel subsystem,
      such as SELinux.

然后，你就可以在‘General Setup’选项下看到`ADUITSYSCALL`，取消即可。

如果你的主机是多CPU 或多核的，那么 `Processor type and features` 下的SMP 选项要使能（enabled），并且最大CPU 个数（`Maximum numbers of CPUs`）不应小于物理核心个数（即不考虑Hyperthreading）。因此，建议你在BIOS 中取消Hyperthreading。

步骤三：编译安装内核和RTAI

3.1 编译和安装Linux 内核

cd /usr/src/linux
sudo touch REPORTING-BUGS
sudo make -j3
sudo make modules
sudo make modules_install
sudo make install
sudo update-initramfs –c -k 4.14.111-rtai [注意修改这里的版本名称]
sudo update-grub [注意修改/etc/default/grub 启动项为自己的内核]
sudo reboot

从Linux 内核网站下载的4.14.111 版本的源码目录下没有`REPORTING-BUGS`这个文件，可能会导致你在编译的时候遇到`recipe for target ‘kernel_headers’ failed` 的错误，所以我们首先创建了这个文件。

如果一切顺利的的话，你重启后将在Grub 上看到你自己编译的内核选项：ubuntu18.04_4.14.111-rtai 。

3.2 安装RTAI5.2

RTAI 需要autotools 生成链接编译工具：

cd /usr/src/rtai
sudo autoconf
sudo ./configure

接着配置RTAI ：

sudo cp ../linux/.config .rtai_config
sudo make menuconfig

将CPU 个数（`number of CPUs`）设置为实际的物理核心个数即可。

sudo make
sudo make install

如果在编译时遇到下面的错误：

make:execup: .//config.guess: Permission denied
make:execup: .//config.sub: Permission denied

手动修改权限后再编译：

chmod 764 ./config.guess
chmod 764 ./config.sub

RTAI 默认的安装路径是`/usr/realtime`，其中`modules`目录下是编译后的模块库， `testSuite` 目录下是RTAI 的测试程序，通过手动加载模块和运行测试程序可以验证RTAI是否安装成功。

cd /usr/realtime/modules
sudo insmod rtai_hal.ko
sudo insmod rtai_sched.ko
sudo insmod rtai_fifos.ko
sudo insmod rtai_sem.ko
sudo insmod rtai_shm.ko
sudo insmod rtai_rtdm.ko

一般来说，负责进程调度的 rtai_sched.ko 模块如果加载后无死机，则安装成功。

可能遇到的问题

最后罗列一些可能遇到的问题：

1 编译内核时， `implicit declaration of function ‘ipipe_root_**_syscalls’ did you mean ‘ipipe_handle_syscall’ ……` 错误

原因：在内核配置里，ipipeline 没有使能（Enable）;

2 加载`sudo insmod rtai_hal.ko` 和`sudo insmod rtai_` 后，系统冻死，键盘和鼠标均无响应

可能原因：General setup -> Stack Protector buffer overflow detection 选项默认是`Strong`，应设置为`None`或 `Regular`，更多配置项参考 README.CONF_RMRKS 。

3 不能进入编译Linux内核后的系统，提示`Gave up waiting for root file system device. Common problems: …… ALERT! UUID=8e478c20-25e4-49c0-…… does not exist. Drop to the shell`.

可能原因：系统无法识别存储设备，注意配置内核时关于存储的驱动（SATA/PATA）要使能，因为我是在U盘中安装的系统，因此U盘相关的驱动也得使能。

4 当准备加载 rtai_hal.ko 模块时，提示`ERROR: Could not insert module rtai_hal.ko: Operation not permitted`错误，系统日志Syslog(`/var/log/syslog`) 提示`RTAI[hal] RTAI configured with less than num online CPUs`。

可能原因：RTAI 配置的CPU 个数比实际CPU 核心数要多，切记不要算上超线程（Hyperthreading）。

以上错误远不能包含所有你在安装RTAI 时遇到的问题，但你还可以借助下面的工具来帮助你的调试。

一些有用的命令和工具

Dmesg

dmesg

Syslog

sudo cat /var/logsys

Systemctl

Systemctl -failed # 查看哪些内核没有被正常加载

RTAI 官网和邮件列表

www.rtai.org

Dpkg

dpkg –list | grep linux-image

mkinitramfs

寻找最大容错的扁平XOR 码

Posted on 2018/09/18 by qing

参考：

[1] Finding the most fault-tolerant flat XOR-based erasure codes for storage systems [PDF]

[2] Determining fault tolerance of XOR-based erasure codes efficiently [PDF]

本文内容主要来源于上面两篇文章，主要讨论暴力搜寻方法具有最大容错能力（most fault-tolerant）的扁平（Flat）XOR 码。

XOR 码是通过异或运算（exclusive OR）进行数据编码、解码和重建的编码方法，其生成矩阵可以用1/0 二进制矩阵表示。

扁平码是一种每个节点只保存一个符号（数据块），即生成矩阵的每一行（列）对应一个节点。k 和m 分别表示原始数据块个数和校验块个数的话，扁平码的生成矩阵是一个(k+m)×k 大小的0/1 矩阵。常见的RS 码是扁平码，但不是XOR 码；CRS 码不是扁平码，是XOR 码。

暴力搜索通过遍历所有的解空间（所有可能的(k, m) 编码），通过计算每个解的性质，找到满足条件的编码。一个(k+m)×k 大小的0/1 矩阵有2^((m+k)×k) 种可能的二进制矩阵，如果将编码限制在系统码中，则有2^(m×k) 种可能的二进制矩阵。

[2] 中介绍了一种ME （Minimal Erasures）算法，是暴力搜索的关键，该算法通过找到最小失效列表（Minimal Erasure List）寻找某种编码的最大容错能力。ME 算法会用到几个术语：

汉明距离（Hamming distance）：如果一个编码的汉明矩阵是d，那么它能容忍的最大失效节点少于d 个。

失效样式（Erasure pattern）：一组失效（的数据块）使得有一个原始数据块无法被恢复。

失效列表（Erasure list）：所有失效样式的集合。

失效矢量（Erasure vector）：长度为m 的矢量，其中第i 个元素是失效列表中长度为i 的失效样式个数的总和。比如 < 0, 0, 3, 7, …> 表示有失效列表中有3 个长度为3 的失效样式，有7 个长度为4 的失效样式。失效矢量中第d 个值是第一个非零值（小于d 的失效均可恢复）。

最小失效（Minimal Erasure，ME）是一种特殊的失效样式，它的每个失效元素都是必须的，如果去掉其中之一，它就不再是失效样式。

最小失效列表（Minimal Erausre List，MEL）是一个编码的所有最小失效的集合。

最小失效矢量（Minimal Erasure Vector，MEV）是一个长度为m 的矢量，其第i 个元素是MEL 中长度为i 的ME 的个数。

ME 算法具体详见[2] ，其输入是编码的生成矩阵（或Tanner 图），输出为MEL 和MEV。下图给出了 m < 8 和 k < 8 的结果。

下图是m < 11 和 k < 21 所有扁平XOR 码的最大汉明距离。

下图是m < 11 和 k < 21 所有扁平XOR 码中具有最优容错的个数。

下图是下图是m < 11 和 k < 21 所有扁平XOR 码中能够达到最大汉明距离的个数。

[1] 还介绍了如何减少搜索的解空间等优化的方法，并指出搜索算法有部分是Python 写的，用C 能够进一步提高运算速度，并增加m 和k 的值。

12 3 4 5 6 下一页最后一页

呆鸥

Brains first and then Hard Work