---
# System prepended metadata

title: 'linux2021: dmefs'
tags: [linux2021]

---

# 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