NOTEBOOK

ffs, fls, __ffs, __fls

好久没写notebook了，最近在做的事情是为google/syzkaller添加Linux RISC-V KVM Fuzz的相关实现，幸运地找到了一些bug，并且部分已经被社区接收了。

	补丁修复位置	补丁	状态
15	arch/riscv/kvm	BUG: unable to handle kernel paging request in kvm_riscv_vcpu_pmu_ctr_cfg_match	待分析
14	mm	[BUG] WARNING in unlink_anon_vmas(), [PATCH mm-hotfixes] mm/rmap: clear vma->anon_vma on error	已被maintainer确认并修复
13	arch/riscv/kvm	[PATCH] RISC-V: KVM: Fix double-free of sdata in kvm_pmu_clear_snapshot_area()	待审阅
12	arch/riscv/kvm, tools/testing/selftests/kvm	[PATCH v5 0/2] RISC-V: KVM: Fix array out-of-bounds in firmware counter reads	已审阅
11	arch/riscv/kvm	[PATCH] RISC-V: KVM: Fix potential UAF in kvm_riscv_aia_imsic_has_attr()	进入主线
10	arch/riscv/kvm	[PATCH v3] RISC-V: KVM: Fix use-after-free in kvm_riscv_aia_aplic_has_attr()	进入主线
9	arch/riscv/kvm	[PATCH] RISC-V: KVM: Change imsic->vsfile_lock from rwlock_t to raw_spinlock_t	讨论中
8	arch/riscv/kvm	[PATCH v2] RISC-V: KVM: Fix null pointer dereference in kvm_riscv_vcpu_aia_rmw_topei()	进入主线
7	arch/riscv/kvm	[PATCH v2] RISC-V: KVM: Fix use-after-free in kvm_riscv_gstage_get_leaf()	进入主线
6	arch/riscv/kvm	[PATCH] RISC-V: KVM: Skip IMSIC update if vCPU IMSIC state is not initialized	进入主线
5	arch/riscv/kvm	[PATCH] RISC-V: KVM: Fix null pointer dereference in kvm_riscv_aia_imsic_rw_attr()	进入主线
4	arch/riscv/kvm	[PATCH v4] RISC-V: KVM: Fix null pointer dereference in kvm_riscv_aia_imsic_has_attr()	进入主线
3	arch/riscv/kvm, tools/testing/selftests/kvm	[PATCH v10 0/3] RISC-V: KVM: Validate SBI STA shmem alignment	已审阅
2	arch/riscv/kernel	[PATCH v2] riscv: fix KUnit test_kprobes crash when building with Clang	进入主线
1	arch/riscv/kernel	[PATCH] riscv: stacktrace: Disable KASAN checks for non-current tasks	进入主线

好，言归正传，今天在分析 BUG: unable to handle kernel paging request in kvm_riscv_vcpu_pmu_ctr_cfg_match 时遇到了 ffs, fls, __ffs, __fls这些helper函数，一开始搞不明白，后面在LLM的帮助下才知道是怎么回事。

1 先看源码

这些函数都是位操作工具函数，定义在arch/riscv/include/asm/bitops.h里面：

// 没必要看源码，看注释就行
/**
 * ffs - find first set bit in a word
 * @x: the word to search
 *
 * This is defined the same way as the libc and compiler builtin ffs routines.
 *
 * ffs(value) returns 0 if value is 0 or the position of the first set bit if
 * value is nonzero. The first (least significant) bit is at position 1.
 */
#define ffs(x) (__builtin_constant_p(x) ? __builtin_ffs(x) : variable_ffs(x))

/**
 * fls - find last set bit in a word
 * @x: the word to search
 *
 * This is defined in a similar way as ffs, but returns the position of the most
 * significant set bit.
 *
 * fls(value) returns 0 if value is 0 or the position of the last set bit if
 * value is nonzero. The last (most significant) bit is at position 32.
 */
#define fls(x)							\
({								\
	typeof(x) x_ = (x);					\
	__builtin_constant_p(x_) ?				\
	 ((x_ != 0) ? (32 - __builtin_clz(x_)) : 0)		\
	 :							\
	 variable_fls(x_);					\
})

/**
 * __ffs - find first set bit in a long word
 * @word: The word to search
 *
 * Undefined if no set bit exists, so code should check against 0 first.
 */
#define __ffs(word)				\
	(__builtin_constant_p(word) ?		\
	 (unsigned long)__builtin_ctzl(word) :	\
	 variable__ffs(word))

/**
 * __fls - find last set bit in a long word
 * @word: the word to search
 *
 * Undefined if no set bit exists, so code should check against 0 first.
 */
#define __fls(word)							\
	(__builtin_constant_p(word) ?					\
	 (unsigned long)(BITS_PER_LONG - 1 - __builtin_clzl(word)) :	\
	 variable__fls(word))

好了，翻译一下：ffs指的是Find First Set bit, fls指的是Find Last Set bit; 加上__之后，代表着最低为是索引0，否则是1.

2 看一个例子

data = 0b00101000
ffs(data) = 4
fls(data) = 6
__ffs(data) = 3 
__fls(data) = 5