# [Batch](https://github.com/c-blake/batch) -- 一種以減少處理器模式切換的發生次數來提昇系統呼叫執行效率的方法
contributed by < `foxhoundsk` >
## 實驗環境

Ubuntu 20.04.1 LTS
Kernel: 5.8.0-36-generic
Memory: 32 GB

Architecture:                    x86_64
CPU op-mode(s):                  32-bit, 64-bit
Byte Order:                      Little Endian
Address sizes:                   43 bits physical, 48 bits virtual
CPU(s):                          16
On-line CPU(s) list:             0-15
Thread(s) per core:              2
Core(s) per socket:              8
Socket(s):                       1
NUMA node(s):                    1
Vendor ID:                       AuthenticAMD
CPU family:                      23
Model:                           113
Model name:                      AMD Ryzen 7 3700X 8-Core Processor
Stepping:                        0
Frequency boost:                 enabled
CPU MHz:                         1867.087
CPU max MHz:                     3600.0000
CPU min MHz:                     2200.0000
BogoMIPS:                        7186.60
Virtualization:                  AMD-V
L1d cache:                       256 KiB
L1i cache:                       256 KiB
L2 cache:                        4 MiB
L3 cache:                        32 MiB
NUMA node0 CPU(s):               0-15
Vulnerability Itlb multihit:     Not affected
Vulnerability L1tf:              Not affected
Vulnerability Mds:               Not affected
Vulnerability Meltdown:          Not affected
Vulnerability Spec store bypass: Mitigation; Speculative Store Bypass disabled via prctl and seccomp
Vulnerability Spectre v1:        Mitigation; usercopy/swapgs barriers and __user pointer sanitization
Vulnerability Spectre v2:        Mitigation; Full AMD retpoline, IBPB conditional, STIBP conditional, RSB filling
Vulnerability Srbds:             Not affected
Vulnerability Tsx async abort:   Not affected
Flags:                           fpu vme de pse tsc msr ...

## 系統呼叫時 CPU 模式切換的成本量測
本量測使用 [eBPF](https://en.wikipedia.org/wiki/Berkeley_Packet_Filter) 將 kernel 端的量測程式掛載 (hook) 到特定系統呼叫 (以 [getuid(2)](https://man7.org/linux/man-pages/man2/geteuid.2.html)為例) 的進入點，也就是 `__x64_sys_getuid`。user 端則是使用以 [vDSO](https://man7.org/linux/man-pages/man7/vdso.7.html) 實做的系統呼叫 [clock_gettime(3)](https://man7.org/linux/man-pages/man3/clock_gettime.3.html) 來提取 timestamp。此外，kernel 端的掛載點 (hook point) 我們分別使用了 kprobe 以及 kretprobe，以量測進入/離開 kernel mode 的時間開銷。
### 測試程式碼
user 端程式碼：
- 進入 kernel ([程式碼](https://gist.github.com/foxhoundsk/8b25a5a0e7a0f57b2a0e0d8a19efda14#file-user_enter_kern-c))

    uint64_t delta = 1000000;
    for (int i = 0; i < TEST_CNT; i++) {
        clock_gettime(CLOCK_MONOTONIC, &tp);
        syscall(__NR_getuid); /* dummy call */

        if (unlikely(bpf_map_lookup_elem(bpf_map_fd, &key, &map))) {
            fprintf(stderr, "Failed to lookup map element\n");
            perror("lookup");
            exit(-1);
        }

        delta += map.ts - (1000000000 * tp.tv_sec + tp.tv_nsec);
    }
    printf("avg: %fns\n", (double) delta / TEST_CNT);

- 離開 kernel ([程式碼](https://gist.github.com/foxhoundsk/8b25a5a0e7a0f57b2a0e0d8a19efda14#file-user_ret_from_kern-c))

    uint64_t delta = 0;
    for (int i = 0; i < TEST_CNT; i++) {

        syscall(__NR_getuid); /* dummy call */
        clock_gettime(CLOCK_MONOTONIC, &tp);

        if (unlikely(bpf_map_lookup_elem(bpf_map_fd, &key, &map))) {
            fprintf(stderr, "Failed to lookup map element\n");
            perror("lookup");
            exit(-1);
        }

        delta += (1000000000 * tp.tv_sec + tp.tv_nsec) - map.ts;
    }
    printf("avg: %fns\n", (double) delta / TEST_CNT);

- 完整系統呼叫 ([程式碼](https://gist.github.com/foxhoundsk/8b25a5a0e7a0f57b2a0e0d8a19efda14#file-complete_syscall_overhead-c))

    for (int i = 0; i < TEST_CNT; i++) {
        clock_gettime(CLOCK_MONOTONIC, &t1);
        syscall(__NR_getuid); /* dummy call */
        clock_gettime(CLOCK_MONOTONIC, &tp);

        delta += (1000000000 * tp.tv_sec + tp.tv_nsec) - (1000000000 * t1.tv_sec + t1.tv_nsec);
    }
    printf("avg: %fns\n", (double) delta / TEST_CNT);

[kernel 端程式碼](https://gist.github.com/foxhoundsk/8b25a5a0e7a0f57b2a0e0d8a19efda14#file-bpf_kern-c)：

SEC("getuid")
int kp_sys_batch(struct pt_regs *ctx)
{
	__u32 i = 0;
	struct reals *r;

	r = bpf_map_lookup_elem(&reals, &i);
	if (!r)
		return 1;

	r->ts = bpf_ktime_get_ns();
	return 0;
}

### 測試結果
- 進入 kernel: ~77ns
- 離開 kernel: ~69ns
- 完整系統呼叫: ~65ns

由實驗結果可以觀察到量測進/出 kernel 的程式有額外的執行成本，導致其兩者的量測結果比執行完整系統呼叫所花的時間還要久。

此外，使用 isolcpus 搭配 taskset 執行測試依舊得到幾乎相同的結果，推測是機器負載不重的關係，因為使用 `time -v` 觀察測試程式的 [resource usage](https://man7.org/linux/man-pages/man2/getrusage.2.html) 得到以下輸出：

Command being timed: "./test"
        User time (seconds): 0.13
        System time (seconds): 0.64
        Percent of CPU this job got: 91%
        Elapsed (wall clock) time (h:mm:ss or m:ss): 0:00.85
        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): 2032
        Average resident set size (kbytes): 0
        Major (requiring I/O) page faults: 0
        Minor (reclaiming a frame) page faults: 214
        Voluntary context switches: 7
        Involuntary context switches: 79
        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

其中 `Involuntary context switches` 在 有/沒有 使用 isolcpus 的 CPU 時，數值幾乎相同 (個位數差距)。

值得一提的是，倘若將量測「離開 kernel」的程式碼中的 kretprobe (`r:kp_sys_batch`) 改成 kprobe (`p:kp_sys_batch`)，量測結果會是 ~48ns。也就是說，此量測包含了 `getuid` 本身 (不含進出 kernel 的開銷) 的執行時間。

如果用同樣測量方式，但將「取平均值」改為「取最小值」，則：
- 進入 kernel: 10ns
- 離開 kernel: 50ns

目前想到造成額外執行成本的可能是「呼叫 `clock_gettime` 以及 `bpf_ktime_get_ns` 的間隔時間過短」，導致其中的 seqlock (\[[1](https://elixir.bootlin.com/linux/latest/source/lib/vdso/gettimeofday.c#L66)] \[[2](https://elixir.bootlin.com/linux/latest/source/kernel/time/timekeeping.c#L478)]) 發生 retry (相關資料結構在讀取過程中被 writer 修改，故需重新讀取)。或是，相關資料結構正在被修改，導致在 CS (critical section) 的進入點 ([vdso_read_begin](https://elixir.bootlin.com/linux/latest/source/lib/vdso/gettimeofday.c#L66)) 自旋 (spinning) (`bpf_ktime_get_ns` 的 CS 進入點不會有自旋的發生，因為該處用的 seqlock 是 [latch sequence counter](https://www.kernel.org/doc/html/latest/locking/seqlock.html#latch-sequence-counters-seqcount-latch-t))。

若將對 seqlock 做的推測套用到上述刻意做的修改中 (將量測「離開 kernel」的程式碼中用到的 kretprobe 修改為 kprobe ...)，可以解釋為什麼可以得到 ~48ns 的量測結果。原因是「呼叫 `clock_gettime` 以及 `bpf_ktime_get_ns` 的間隔時間增加了」。

但若是將量測「進入 kernel」的程式碼所用到的 kprobe 修改為 kretprobe，得到的結果則是 ~128ns。如此一來這套理論就被推翻了！

不知道有沒有人對此額外開銷有什麼看法？雖然這邊沒有成功算出正確的模式切換時間開銷，但在下方對 [Batch](https://github.com/c-blake/batch) 做相關實驗時有間接算出處理器模式切換的開銷，結果為 ~23ns。

除了上述測量方式，還想到一種方法：「使用 isolcpus 以及 taskset 於 userspace 使用 RDTSC，kernelspace 的部份則以核心模組掛載 k[ret]probe 至特定系統呼叫，並於其 callback 中使用 [get_cycles](https://elixir.bootlin.com/linux/latest/source/arch/x86/include/asm/tsc.h#L21) 提取 TSC 的內容」。

## [Batch](https://github.com/c-blake/batch)
典型系統呼叫發生時，除了執行對應系統呼叫以外，還會有處理器模式切換的操作發生，後者雖然在現代處理器以及作業系統上產生的開銷相較早期已經減少許多，但如果我們可以減少這個開銷的發生次數，在系統呼叫頻繁發生的情境下 (資料庫、網頁伺服器等等)，還是可以得到可觀的效能提昇。

[Batch](https://github.com/c-blake/batch) 提出一種藉由減少處理器模式切換的發生次數來增加系統呼叫效率的方法，類似手法可參見 [FlexSC](https://www.usenix.org/legacy/events/osdi10/tech/full_papers/Soares.pdf)。

Batch 使用核心模組將 kernel 中尚未實做的系統呼叫 (`__NR_afs_syscall`) 替換成自己實做的系統呼叫 ([sys_batch](https://github.com/c-blake/batch/blob/master/module/batch.c#L79))，後者顧名思義是用於做批次 (透過單趟處理器模式切換執行多個系統呼叫) 執行系統呼叫的系統呼叫。應用程式僅需將特定資料結構 (其中包含系統呼叫號碼、參數、存放回傳值的記憶體位置等等) 做填寫，即可發出 `sys_batch` 系統呼叫令作業系統於單個系統呼叫中執行多個系統呼叫。

值得一提的是，Batch 可一口氣處理多個有相依性的系統呼叫，例如：open -> read -> close。同樣範例下，FlexSC 在每一個系統呼叫發出後均需等待位於 userspace 的 dispatcher 將特定資料結構做標記，以令 kernel space 中處理系統呼叫的 daemon 開始執行系統呼叫，執行完成後對應執行緒才得以往下執行下一個系統呼叫。

由此可見，FlexSC 的效能在現今 processor microarchitecture 以及作業系統中要做到效能提升的話，相對於 Batch 來說會較困難，但是 Batch 需要對應用程式做不少的改寫 (FlexSC 以 pthread library 為目標做改寫，所以應用程式僅需做些許的修改並在啟動時將 pthread library 的 shared object (.so) 做替換 (`LD_PRELOAD=...`) 即可。

### 典型系統呼叫 vs Batch 批次處理系統呼叫
本實驗以 [getuid(2)](https://man7.org/linux/man-pages/man2/geteuid.2.html) 系統呼叫作為實驗對象，量測典型系統呼叫以及 Batch 的效能差異。

測試程式碼：([改寫自 Batch 的範例](https://github.com/c-blake/batch/blob/master/examples/getuids.c))
- 典型系統呼叫

    #include <stdio.h>          // fprintf stderr
    #include <stdlib.h>         // calloc
    #include <time.h>           // timespec clock_gettime CLOCK_MONOTONIC
    #include "linux/batch.h"    // syscall_t batch

    int N[] = {  1,  2,   3,   4,   5,   6,    7,  8,  9, 10,
                16, 20,  24,  32,  36,  40,   44, 50, 60, 70,
                80, 90, 100, 128, 256, 384, 512, 768, 1024,
                1512, 2048, 2512, 3096, 3512, 4096 };

    int main(int ac, char **av) {
        struct timespec t0, t1;
        unsigned long   dt;
        int             i, j, k, m, nn = sizeof N / sizeof *N, zz;
        syscall_t      *bat = (syscall_t *)calloc(4096, sizeof *bat);
        long           *rvs = (long *)calloc(4096, sizeof *rvs);

        for (i = 0; i < N[nn - 1]; i++)             //Assume last biggest
                bat[i].nr = __NR_getuid;
        printf("N\tm\tns\trs\n");
        for (k = 0; k < nn; k++) {
                unsigned long min = 1000000000000;  //Min out of 10 trials
                unsigned long rs = 0;
                m = 1000000 / (360 + 46*N[k]);      //Make similar real-time
                for (i = 0; i < 10; i++) {
                        clock_gettime(CLOCK_MONOTONIC, &t0);
                        for (j = 0; j < m; j++)
                                for (zz = 0; zz < N[k]; zz++)
                                        rs += getuid();
                        clock_gettime(CLOCK_MONOTONIC, &t1);
                        dt = ((t1.tv_sec - t0.tv_sec) * 1000000000 +
                                t1.tv_nsec - t0.tv_nsec) / m;
                        if (dt < min)
                                min = dt;
                }
                printf("%d\t%d\t%ld\t%lu\n", N[k], m, min, rs);
        }       // NOTE: adjust for user-space loop & gettime overheads
        return 0;
    }

- Batch

    #include <stdio.h>          // fprintf stderr
    #include <stdlib.h>         // calloc
    #include <time.h>           // timespec clock_gettime CLOCK_MONOTONIC
    #include "linux/batch.h"    // syscall_t batch

    int N[] = {  1,  2,   3,   4,   5,   6,    7,  8,  9, 10,
                16, 20,  24,  32,  36,  40,   44, 50, 60, 70,
                80, 90, 100, 128, 256, 384, 512, 768, 1024, 
                1512, 2048, 2512, 3096, 3512, 4096 };

    int main(int ac, char **av) {
        struct timespec t0, t1;
        unsigned long   dt;
        int             i, j, k, m, nn = sizeof N / sizeof *N, zz;
        syscall_t      *bat = (syscall_t *)calloc(4096, sizeof *bat);
        long           *rvs = (long *)calloc(4096, sizeof *rvs);

        for (i = 0; i < N[nn - 1]; i++)             //Assume last biggest
            bat[i].nr = __NR_getuid;
        printf("N\tm\tns\trs\n");
        for (k = 0; k < nn; k++) {
            unsigned long min = 1000000000000;  //Min out of 10 trials
            unsigned long rs = 0;
            m = 1000000 / (360 + 46*N[k]);      //Make similar real-time
            for (i = 0; i < 10; i++) {
                clock_gettime(CLOCK_MONOTONIC, &t0);
                for (j = 0; j < m; j++)
                    rs += batch(rvs, bat, N[k], 0, 0);
                clock_gettime(CLOCK_MONOTONIC, &t1);
                dt = (t1.tv_sec - t0.tv_sec) * 1000000000 +
                    t1.tv_nsec - t0.tv_nsec / m;
                if (dt < min)
                    min = dt;
            }
            printf("%d\t%d\t%ld\t%lu\n", N[k], m, min, rs);
        }	// NOTE: adjust for user-space loop & gettime overheads
        return 0;
    }

#### 實驗結果
- 單位時間內系統呼叫數量對應平均花費時間：

- 單位時間內系統呼叫數量對應單一系統呼叫平均花費時間：

由實驗結果可發現，在現代處理器以及作業系統 (以 Linux 為例) 上，[Batch](https://github.com/c-blake/batch) 所提出的批次處理系統呼叫的方法相較於典型系統呼叫，在密集執行 `getuid` 系統呼叫時可提升約 48% 的效能。

換句話說，典型系統呼叫發生時所產生的模式切換的開銷為 ~23ns。然而，實際開銷應略小於此數據，因為 Batch 在 kernel code 中有使用到 [copy_to_user / copy_from_user](https://github.com/c-blake/batch/blob/master/module/batch.c#L102)，此倆函式隨著欲複製內容 (單次批次處理系統呼叫的數量) 大小的增長，將成為不可忽略的開銷。