risc-v linux kernelでcrypt/xor.c実装の効率化を考える（考察のみ


# crypt/xor.c は小さいし調査しやすい

cryptの中の実装で、一番小さいのは多分、xorだと思う。
ということで、この部分についてもう少しバイナリベースで調査を進めてみた。

# TL;DR

- risc-v用のxor.hがないので、genericな実装を参照しているよ
- だけど、ものすごいsimpleな実装だから<del>遅いよ！</del> コンパイラ次第で遅くなるよ！gcc9ならそこそこ早いかも！
- RISC-VだとSIMDじゃなくてVECTORがあるから、要検討かもね！
- でも、RISC-Vボードがないから、誰も検討できない…

# 実験方法

```bash
$ riscv32-unknown-linux-gnu-gcc --version
riscv32-unknown-linux-gnu-gcc (GCC) 9.2.0
Copyright (C) 2019 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

$ make ARCH=riscv CROSS_COMPILE=riscv32-unknown-linux-gnu- menuconfig

```

`CONFIG_BTRFS_FS=y`すると、いもづるで`CONFIG_XOR_BLOCKS=y`になる。

# xor.h がないけど何とかなる

`xor.c` のコードを見ると `xor.h` へのincludeがある。でも、arch/riscv 以下にはないぞ？と焦りました。

```c:crypt/xor.c
#include <linux/module.h>
#include <linux/gfp.h>
#include <linux/raid/xor.h>
#include <linux/jiffies.h>
#include <linux/preempt.h>
#include <asm/xor.h>
```

他アーキテクチャ含めてみると…うん、確かにRISC-V用が存在しないことが確認できる。まさか、ここでおしまいかなーと思ったのですが、そうは問屋が卸さない。

```bash:コンパイル前
$find arch -name "xor.h"
arch/alpha/include/asm/xor.h
arch/arm/include/asm/xor.h
arch/arm64/include/asm/xor.h
arch/ia64/include/asm/xor.h
arch/powerpc/include/asm/xor.h
arch/s390/include/asm/xor.h
arch/sparc/include/asm/xor.h
arch/um/include/asm/xor.h
arch/x86/include/asm/xor.h
```

これではコンパイルができないの…？と思ったら、コンパイル時に自動生成されたヘッダで、汎用の`xor.h`に繋げることで、問題なく動かします。

```bash:コンパイル後
$ find arch -name "xor.h"
arch/alpha/include/asm/xor.h
arch/arm/include/asm/xor.h
arch/arm64/include/asm/xor.h
arch/ia64/include/asm/xor.h
arch/powerpc/include/asm/xor.h
arch/riscv/include/generated/asm/xor.h
arch/s390/include/asm/xor.h
arch/sparc/include/asm/xor.h
arch/um/include/asm/xor.h
arch/x86/include/asm/xor.h

$ cat arch/riscv/include/generated/asm/xor.h
#include <asm-generic/xor.h>

$ find include -name "xor.h"
include/asm-generic/xor.h
```

# 先にxor.hのコードを確認しておく。

ソースコード{`include/asm-genetic/xor.h`) を見ると、うーん、実にシンプルな感じですね…基本に忠実です、確実に。

```c:include/asm-generic/xor.h
static void
xor_8regs_2(unsigned long bytes, unsigned long *p1, unsigned long *p2)
{
    long lines = bytes / (sizeof (long)) / 8;

    do {
        p1[0] ^= p2[0];
        p1[1] ^= p2[1];
        p1[2] ^= p2[2];
        p1[3] ^= p2[3];
        p1[4] ^= p2[4];
        p1[5] ^= p2[5];
        p1[6] ^= p2[6];
        p1[7] ^= p2[7];
        p1 += 8;
        p2 += 8;
    } while (--lines > 0);
}
```


# 楽しいdisassemble time

よし、それではさっそく xor.o を disassmbleして、どんなのができているのかを見てみよう！！

## まずsymbolを確認する。

シンボルとして何が定義されているのかを確認すると以下を観察できる。

- xorは、8regs と、32regs がある。
    - 8 regs = 8 bit = unsigned char (先の例)
    - 32 regs = 32 bit = unsigned int
- xorは、2,3,4.5をまとめて処理する系がある。



```bash:xor.oのシンボル

$ riscv32-unknown-linux-gnu-objdump -t xor.o

xor.o:     file format elf64-littleriscv

SYMBOL TABLE:
0000000000000000 l    df *ABS*  0000000000000000 xor.c
0000000000000000 l    d  .text  0000000000000000 .text
0000000000000000 l    d  .data  0000000000000000 .data
0000000000000000 l    d  .bss   0000000000000000 .bss
0000000000000000 l    d  __ksymtab_strings      0000000000000000 __ksymtab_strings
0000000000000000 l       __ksymtab_strings      0000000000000000 __kstrtab_xor_blocks
000000000000000b l       __ksymtab_strings      0000000000000000 __kstrtabns_xor_blocks
0000000000000000 l     F .text  0000000000000082 xor_8regs_2
0000000000000082 l     F .text  00000000000000bc xor_8regs_3
000000000000013e l     F .text  0000000000000104 xor_8regs_4
0000000000000242 l     F .text  0000000000000168 xor_8regs_5
00000000000003aa l     F .text  000000000000008c xor_32regs_2
0000000000000436 l     F .text  00000000000000c0 xor_32regs_3
00000000000004f6 l     F .text  0000000000000112 xor_32regs_4
0000000000000608 l     F .text  0000000000000160 xor_32regs_5
0000000000000000 l     O .sbss  0000000000000008 active_template
0000000000000000 l    d  .exit.text     0000000000000000 .exit.text
0000000000000000 l     F .exit.text     000000000000000c xor_exit
0000000000000000 l    d  .rodata.str1.8 0000000000000000 .rodata.str1.8
0000000000000000 l    d  .init.text     0000000000000000 .init.text
0000000000000000 l     F .init.text     00000000000000c6 do_xor_speed
00000000000000c6 l     F .init.text     00000000000000f6 calibrate_xor_blocks
00000000000007d8 l     F .text  000000000000015e xor_32regs_p_5
0000000000000936 l     F .text  0000000000000112 xor_32regs_p_4
0000000000000a48 l     F .text  00000000000000c4 xor_32regs_p_3
0000000000000b0c l     F .text  0000000000000092 xor_32regs_p_2
0000000000000b9e l     F .text  0000000000000150 xor_8regs_p_5
0000000000000cee l     F .text  0000000000000108 xor_8regs_p_4
0000000000000df6 l     F .text  00000000000000c0 xor_8regs_p_3
0000000000000eb6 l     F .text  0000000000000088 xor_8regs_p_2
0000000000000000 l       .data  0000000000000000 .LANCHOR1
0000000000000000 l     O .data  0000000000000038 xor_block_8regs
0000000000000038 l     O .data  0000000000000038 xor_block_8regs_p
0000000000000070 l     O .data  0000000000000038 xor_block_32regs
00000000000000a8 l     O .data  0000000000000038 xor_block_32regs_p
0000000000000000 l    d  .exitcall.exit 0000000000000000 .exitcall.exit
0000000000000000 l     O .exitcall.exit 0000000000000008 __exitcall_xor_exit
0000000000000000 l    d  .init.data     0000000000000000 .init.data
＜略>
```

## バイナリを確認する

バイナリの中身を確認すると8byte単位で、xorして保持していますね。
それにしてもうん、非常に人間の可読性はきつい（読めないことはない）。unrollingしたりなんだりした結果ですね…

```plaintext:memo
a0 = bytes
a1 = *p1
a2 = *p2
```

```bash:xor.oのasm
$ riscv32-unknown-linux-gnu-objdump -d xor.o

xor.o:     file format elf64-littleriscv


Disassembly of section .text:

0000000000000000 <xor_8regs_2>:
   0:   1141                    addi    sp,sp,-16    % Stack確保
   2:   e422                    sd      s0,8(sp)     %
   4:   0800                    addi    s0,sp,16     %
   6:   8119                    srli    a0,a0,0x6    % a0 = bytes >> 8

0000000000000008 <.L2>:
   8:   00063803                ld      a6,0(a2)    % a6 = p2[0]
   c:   6194                    ld      a3,0(a1)    % a3 = p1[0]
   e:   6598                    ld      a4,8(a1)    %  a4 = p1[8]
  10:   699c                    ld      a5,16(a1)   %   a5 = p1[16]
  12:   0106c6b3                xor     a3,a3,a6    % a3 = a3 ^ a6
  16:   e194                    sd      a3,0(a1)    % p1[0] = a3
  18:   6614                    ld      a3,8(a2)    %  a3 = p1[8]
  1a:   0185b883                ld      a7,24(a1)   %    a7 = p1[24]
  1e:   0205b803                ld      a6,32(a1)   %     a6 = p1[32]
  22:   8f35                    xor     a4,a4,a3    %  a4 = a4 ^ a3
  24:   e598                    sd      a4,8(a1)    %  p1[8] = a4
  26:   01063303                ld      t1,16(a2)   %   t1 = p2[16]
  2a:   7594                    ld      a3,40(a1)   %      a3 = a1[40]
  2c:   7998                    ld      a4,48(a1)   %       a4 = a1[48]
  2e:   0067c7b3                xor     a5,a5,t1    %   a5 = a5 ^ t1
  32:   e99c                    sd      a5,16(a1)   %   p1[16] = a5
  34:   01863303                ld      t1,24(a2)   %    t1 = p2[24]
  38:   7d9c                    ld      a5,56(a1)   %        a5 = p1[56]
  3a:   04058593                addi    a1,a1,64    % ＜a1 = a1 + 64＞
  3e:   0068c8b3                xor     a7,a7,t1    %    a7 = a7 ^ t1
  42:   fd15bc23                sd      a7,-40(a1)  %    p1[-40] = a7 (実質24)
  46:   02063883                ld      a7,32(a2)   %     a7 = p2[32]
  4a:   04060613                addi    a2,a2,64    % ＜a2 = a2 + 64＞
  4e:   157d                    addi    a0,a0,-1    % ＜a0 = a0 - 1＞
  50:   01184833                xor     a6,a6,a7    %     a6 = a6 ^ a7
  54:   ff05b023                sd      a6,-32(a1)  %     p1[-32] = a6(実質32)
  58:   fe863803                ld      a6,-24(a2)  %      a6 = p2[-24](実質40)
  5c:   0106c6b3                xor     a3,a3,a6    %      a3 = a3 ^ a6
  60:   fed5b423                sd      a3,-24(a1)  %      p1[-24] = a3(実質40)
  64:   ff063683                ld      a3,-16(a2)  %       a3 = a2[-16](実質48)
  68:   8f35                    xor     a4,a4,a3    %       a4 = a4 ^ a3
  6a:   fee5b823                sd      a4,-16(a1)  %       a1[-16] = a4(実質48)
  6e:   ff863703                ld      a4,-8(a2)   %        a4 = a2[-8](実質56)
  72:   8fb9                    xor     a5,a5,a4    %        a5 = a5 ^ a4
  74:   fef5bc23                sd      a5,-8(a1)   %        p1[-8] = a5 (実質56)
  78:   f8a048e3                bgtz    a0,8 <.L2>  % if(a0 > 0) goto L2
  7c:   6422                    ld      s0,8(sp)    % 
  7e:   0141                    addi    sp,sp,16    % Stack復元
  80:   8082                    ret
```

# これは（常に）最適解ではない！（という妄想）

RISC-Vには、Vector Extensionがある。SIMDではない。繰り返すが、SIMDではない。

一番良いのは、こちらの fixstars様の記事をよく読むことなのですが……。

https://proc-cpuinfo.fixstars.com/2019/10/riscv-v 簡単にいうと「何をどれだけ並列で処理するのかは、コンパイル時ではなく実行時に任せる」こともできる、という感じ。

妄想だけで記載するとこんな感じ。
これで、64x8 でも、32x8 でも、32x4 でも、それなりに動くはず……

```
loop:
	vlsetvli t0, a0, e128,m8  % 128bit単位で8要素ずつa0回。今回の回数はt0に入る。
	vle.v    v1, (a1), vm     % v1 = *a1
	vle.v    v2, (a2), vm     % v2 = *a2
	vor.vv   v1, v1, v2, vm   % v1 = v1 ^ v2
    vse.v    v1, (a1)         % p1 = v1
	addi     a1, t0           % a1 = a1 - t0
	addi     a2, t0           % a2 = a2 - t0
	sub      a0, a0, t0       % a0 = a0 - t0
	bnez     a0, loop         % 繰り返し
```

以上です。