# linux2021: dmefs
###### tags: `linux2021`
:::warning
你的 GitHub 帳號名稱真棒，好似生來就是要開發 Linux 核心原始程式碼，後者有一堆 fs (file system)
:notes: jserv
:::
:::success
感謝老師的注意!
這名稱是 **D**ennis + **me**mory + **f**ile **s**ystem 而得，確實是為了 Linux 而創
:tada: dmefs
:::
## 測驗 α - 1
舉出 Linux 核心原始程式碼裡頭 bit rotation 的案例並說明
在 `include/linux/bitops.h`，Linux Kernel 定義了一連串 inline bit rotation function
以 64 bit rotation 為例
rotation left 為 `static inline __u64 rol64(__u64 word, unsigned int shift)`
rotation right 為 `static inline __u64 ror64(__u64 word, unsigned int shift)`
在 Linux Kernel 版本`v5.14-rc1`中，搜尋`ror32`發現在`lib/crypto/sha256.c`[1]有使用，程式碼如下：
```cpp
#define e0(x) (ror32(x, 2) ^ ror32(x, 13) ^ ror32(x, 22))
#define e1(x) (ror32(x, 6) ^ ror32(x, 11) ^ ror32(x, 25))
#define s0(x) (ror32(x, 7) ^ ror32(x, 18) ^ (x >> 3))
#define s1(x) (ror32(x, 17) ^ ror32(x, 19) ^ (x >> 10))
```
SHA256[2] 是 SHA-2 (Secure Hash Algorithm - 2)的其中一種演算法，這種演算法會使用到 ror32
而搜尋`rol32`則發現在`fs/ext4/hash.c`[3]有使用，摘錄程式碼如下：
```cpp
/*
* The generic round function. The application is so specific that
* we don't bother protecting all the arguments with parens, as is generally
* good macro practice, in favor of extra legibility.
* Rotation is separate from addition to prevent recomputation
*/
#define ROUND(f, a, b, c, d, x, s) \
(a += f(b, c, d) + x, a = rol32(a, s))
```
MD4 的計算過程中會使用到
在搜尋的過程中發現 hash algorithm 常使用到 bit rotation
reference:
[1]https://en.wikipedia.org/wiki/SHA-2
[2]https://elixir.bootlin.com/linux/v5.14-rc1/source/lib/crypto/sha256.c#L50
[3]https://elixir.bootlin.com/linux/v5.14-rc1/source/fs/ext4/hash.c#L45
## 測驗 α - 2
題目: x86_64 指令集具備 rotr 和 rotl 指令，上述 C 程式碼經過編譯器最佳化 (例如使用 gcc) 後，能否運用到這二個指令呢？
首先觀察`rotl8` 及`rotr8`，測試程式碼如下，名稱為`rot8.c`
```clike=
#include <stdint.h>
#include <stdio.h>
#define __DECLARE_ROTATE(bits, type) \
static inline type rotl##bits(const type v, int c) \
{ \
const int mask = (bits) - (1); \
c &= mask; \
\
return (v << c) | (v >> (-c & mask)); \
} \
\
static inline type rotr##bits(const type v, int c) \
{ \
const int mask = (bits) - (1); \
c &= mask; \
\
return (v >> c) | (v << (-c & mask)); \
}
#define DECLARE_ROTATE(bits) __DECLARE_ROTATE(bits, uint##bits##_t)
DECLARE_ROTATE(8);
void
foo(int i)
{
printf("rotl8: 0x%x\n", rotl8(i, 1));
printf("rotr8: 0x%x\n", rotr8(i, 1));
}
int
main(int argc, char const* argv[])
{
uint8_t i = 0x88;
foo(i);
return 0;
}
```
執行以下指令後可以產生無最佳化 assembly code ，名稱為`rot8.s`
`$ gcc -S -fverbose-asm -O0 rot8.c`
摘錄`rot8.s`中關於`rotl8`的操作
```=
.text
.type rotl8, @function
rotl8:
.LFB0:
.cfi_startproc
pushq %rbp #
.cfi_def_cfa_offset 16
.cfi_offset 6, -16
movq %rsp, %rbp #,
.cfi_def_cfa_register 6
movl %edi, %eax # v, tmp93
movl %esi, -24(%rbp) # c, c
movb %al, -20(%rbp) # tmp94, v
# rotate.c:23: DECLARE_ROTATE(8);
movl $7, -4(%rbp) #, mask
movl -4(%rbp), %eax # mask, tmp95
andl %eax, -24(%rbp) # tmp95, c
movzbl -20(%rbp), %edx # v, _1
movl -24(%rbp), %eax # c, tmp96
movl %eax, %ecx # tmp96, tmp100
sall %cl, %edx # tmp100, _1
movl %edx, %eax # _1, _2
movl %eax, %esi # _2, _3
movzbl -20(%rbp), %edx # v, _4
movl -24(%rbp), %eax # c, tmp97
negl %eax # _5
andl -4(%rbp), %eax # mask, _6
movl %eax, %ecx # _6, tmp102
sarl %cl, %edx # tmp102, _4
movl %edx, %eax # _4, _7
orl %esi, %eax # _3, _9
popq %rbp #
.cfi_def_cfa 7, 8
ret
.cfi_endproc
```
從 line 16 開始是 rotl8 的 function body，操作就跟`rot8.c`的定義一樣，並沒有使用`rotl`的指令。我把 c 的程式碼當成註解改寫一下`rot8.s`，如下
```=
.text
.type rotl8, @function
rotl8:
.LFB0:
.cfi_startproc
pushq %rbp #
.cfi_def_cfa_offset 16
.cfi_offset 6, -16
movq %rsp, %rbp #,
.cfi_def_cfa_register 6
movl %edi, %eax # v, tmp93
movl %esi, -24(%rbp) # c, c
movb %al, -20(%rbp) # tmp94, v
# rotate.c:23: DECLARE_ROTATE(8);
# const int mask = (bits) - (1)
movl $7, -4(%rbp) #, mask
movl -4(%rbp), %eax # mask, tmp95
# c &= mask;
andl %eax, -24(%rbp) # tmp95, c
movzbl -20(%rbp), %edx # v, _1
movl -24(%rbp), %eax # c, tmp96
movl %eax, %ecx # tmp96, tmp100
# v << c
sall %cl, %edx # tmp100, _1
movl %edx, %eax # _1, _2
movl %eax, %esi # _2, _3
movzbl -20(%rbp), %edx # v, _4
movl -24(%rbp), %eax # c, tmp97
# -c
negl %eax # _5
# -c & mask
andl -4(%rbp), %eax # mask, _6
movl %eax, %ecx # _6, tmp102
# v >> (-c & mask)
sarl %cl, %edx # tmp102, _4
movl %edx, %eax # _4, _7
# (v << c) || (v >> (-c & mask))
orl %esi, %eax # _3, _9
popq %rbp #
.cfi_def_cfa 7, 8
ret
.cfi_endproc
```
接著執行以下指令產生 O1 後的程式碼
`$ gcc -S -fverbose-asm -O1 rot8.c`
發現`rotl8`及`rotr8`的 function body 已經不見了，觀察 foo function body，可以看見編譯器使用`rolb`及`rorb`最佳化
```=
.text
.globl foo
.type foo, @function
foo:
.LFB25:
.cfi_startproc
endbr64
pushq %rbx #
.cfi_def_cfa_offset 16
.cfi_offset 3, -16
movl %edi, %ebx # tmp92, i
# rotate.c:31: printf("rotl8: 0x%x\n", rotl8(i, 1));
movl %edi, %edx # i, tmp88
rolb %dl # tmp88
movzbl %dl, %edx # tmp88, tmp89
# /usr/include/x86_64-linux-gnu/bits/stdio2.h:107: return __printf_chk (__USE_FORTIFY_LEVEL - 1, __fmt, __va_arg_pack ());
leaq .LC0(%rip), %rsi #,
movl $1, %edi #,
movl $0, %eax #,
call __printf_chk@PLT #
# rotate.c:32: printf("rotr8: 0x%x\n", rotr8(i, 1));
rorb %bl # tmp90
movzbl %bl, %edx # tmp90, tmp91
# /usr/include/x86_64-linux-gnu/bits/stdio2.h:107: return __printf_chk (__USE_FORTIFY_LEVEL - 1, __fmt, __va_arg_pack ());
leaq .LC1(%rip), %rsi #,
movl $1, %edi #,
movl $0, %eax #,
call __printf_chk@PLT #
# rotate.c:39: }
popq %rbx #
.cfi_def_cfa_offset 8
ret
.cfi_endproc
```
總結上述觀察，沒有最佳化時，不會使用`rol`, `ror`指令，開啟最佳化`O1`時，就會使用`rol`, `ror`指令
reference:
https://en.wikipedia.org/wiki/X86_instruction_listings
https://stackoverflow.com/questions/8021874/how-can-i-compile-to-assembly-with-gcc
https://stackoverflow.com/questions/38335212/calling-printf-in-x86-64-using-gnu-assembler
## 測驗 β - 1
說明 align_up 程式碼的運作原理
已知align_up 可針對給定的 alignment 數值，輸出大於等於 alignment 的記憶體對齊地址
```c=
#include <stdint.h>
static inline uintptr_t align_up(uintptr_t sz, size_t alignment)
{
uintptr_t mask = alignment - 1;
if ((alignment & mask) == 0) { /* power of two? */
return ((sz + mask) & ~mask);
}
return (((sz + mask) / alignment) * alignment);
}
```
首先看一般情況，也就是 alignment 不是 power of 2 時，
對齊後的記憶體位置為:
$result = ((sz + (alignment - 1)) / alginment) * alignment$
分為兩種情況討論
|sz MOD alignment|result|
|----------------|------|
| 0 | sz |
| not 0 | sz+1 |
當 sz 可被 alignment 整除時，加上 (alignment-1)之後除以 alignement 不會進位，但只要 sz 除以 aliment 不為0，加上 (alignment-1)之後除以 alignement 一定會進位，所以:
((**(sz + mask)** / alignment) * alignment) 是為了進位
(((sz + mask) **/ alignment) * alignment**) 是為了將 mask 的值清零
所有情況都可以這樣計算，不過當 alignment 是 power of 2 時可以只用 bit operation 算出結果，不需要**乘除**這種耗費時間的運算
當 alignment 是 power of 2 時，想法一樣，先進位，再把 mask 清零，所以:
**(sz + mask)** & ~mask 進位
(sz + mask) **& ~mask** 把 mask 的值清零
## 測驗 β - 2
在 Linux 核心原始程式碼找出類似 align_up 的程式碼，並舉例說明其用法
在`include/uapi/linux/const.h`可以發現
```c=
#define __ALIGN_KERNEL(x, a) __ALIGN_KERNEL_MASK(x, (typeof(x))(a) - 1)
#define __ALIGN_KERNEL_MASK(x, mask) (((x) + (mask)) & ~(mask))
```
`include/linux/align.h`有使用到 __ALIGN_KERNEL，分別是`ALIGN`及`ALIGN_DOWN`
```c=
/* SPDX-License-Identifier: GPL-2.0 */
#ifndef _LINUX_ALIGN_H
#define _LINUX_ALIGN_H
#include <linux/const.h>
/* @a is a power of 2 value */
#define ALIGN(x, a) __ALIGN_KERNEL((x), (a))
#define ALIGN_DOWN(x, a) __ALIGN_KERNEL((x) - ((a) - 1), (a))
#define __ALIGN_MASK(x, mask) __ALIGN_KERNEL_MASK((x), (mask))
#define PTR_ALIGN(p, a) ((typeof(p))ALIGN((unsigned long)(p), (a)))
#define PTR_ALIGN_DOWN(p, a) ((typeof(p))ALIGN_DOWN((unsigned long)(p), (a)))
#define IS_ALIGNED(x, a) (((x) & ((typeof(x))(a) - 1)) == 0)
#endif /* _LINUX_ALIGN_H */
```
`ALIGN` 的功能就如同 align_up ，針對給定的 alignment 數值，輸出大於等於 alignment 的記憶體對齊地址:
`ALIGN_DOWN` 則是針對給定的 alignment 數值，輸出小於等於 alignment 的記憶體對齊地址
參考執行輸出
```c
ALIGN_DOWN(120, 4) = 120
ALIGN_DOWN(121, 4) = 120
ALIGN_DOWN(122, 4) = 120
ALIGN_DOWN(123, 4) = 120
```
`ALIGN` 在 `arch/riscv/include/asm/processor.h` 有被使用，用來計算在 riscv 架構 kernel stack 中，registers 儲存的位置
```c=
// arch/riscv/include/asm/processor.h
#define STACK_ALIGN 16
#define task_pt_regs(tsk) \
((struct pt_regs *)(task_stack_page(tsk) + THREAD_SIZE \
- ALIGN(sizeof(struct pt_regs), STACK_ALIGN)))
#define KSTK_EIP(tsk) (task_pt_regs(tsk)->epc)
#define KSTK_ESP(tsk) (task_pt_regs(tsk)->sp)
```
THREAD_SIZE 在 64位元為 16KB
`KSTK_EIP`是 Privileged Control Registers - Exception Program Counter
`KSTK_ESP`是 General-purpose Registers - Stack pointer
`ALIGN_DOWN` 在 `arch/arm64/kernel/module-plts.c`有被使用，用來判斷兩個 structure 是否相同，程式碼如下:
```c=
bool plt_entries_equal(const struct plt_entry *a, const struct plt_entry *b)
{
u64 p, q;
/*
* Check whether both entries refer to the same target:
* do the cheapest checks first.
* If the 'add' or 'br' opcodes are different, then the target
* cannot be the same.
*/
if (a->add != b->add || a->br != b->br)
return false;
p = ALIGN_DOWN((u64)a, SZ_4K);
q = ALIGN_DOWN((u64)b, SZ_4K);
/*
* If the 'adrp' opcodes are the same then we just need to check
* that they refer to the same 4k region.
*/
if (a->adrp == b->adrp && p == q)
return true;
return (p + aarch64_insn_adrp_get_offset(le32_to_cpu(a->adrp))) ==
(q + aarch64_insn_adrp_get_offset(le32_to_cpu(b->adrp)));
}
```
reference:
https://www.ocf.berkeley.edu/~qmn/linux/riscv.html
Sign in with Wallet
Connect another wallet