Posts

07 Oct 2023

创建一个简单的内核模块

创建一个简单的内核模块 #

内核模块文件:

#include <linux/module.h>
#include <linux/init.h>

static int __init my_test_init(void)
{
	printk(KERN_EMERG "my first kernel module init\n");
	return 0;
}

static void __exit my_test_exit(void)
{
	printk("goodbye\n");
}

module_init(my_test_init);
module_exit(my_test_exit);

MODULE_LICENSE("GPL");
MODULE_AUTHOR("rlk");
MODULE_DESCRIPTION("my test kernel module");
MODULE_ALIAS("mytest");
  1. <linux/init.h> 对应的是 include/linux/init.h,包含了 module_init()module_exit() 的函数声明。module_init 表示这是模块入口,module_exit 告诉内核该模块的退出函数。

  2. <linux/module.h> 对应的是 include/linux/module.h 包含了 MODULE_AUTHOR() 等一些宏的声明。

接着来看如何编译内核模块:

#BASEINCLUDE ?= /home/rlk/rlk/runninglinuxkernel_5.0
BASEINCLUDE ?= /lib/modules/`uname -r`/build

CONFIG_MODULE_SIG=n

mytest-objs := my_test.o 

obj-m	:=   mytest.o
all : 
	$(MAKE) -C $(BASEINCLUDE) M=$(PWD) modules;

clean:
	$(MAKE) -C $(BASEINCLUDE) M=$(PWD) clean;
	rm -f *.ko;
  1. BASEINCLUDE 指向正在运行 Linux 的内核编译目录。
  2. <模块名>-objs := <目标文件>.o 表示该内核模块需要哪些目标文件
  3. obj-m := <模块名>.o 表示要生成的模块

插入模块:

03 Oct 2023

搭建 Linux Kernel 开发环境

第一步先进行源码拉取,这里使用的是一个特别版本:https://github.com/runninglinuxkernel/runninglinuxkernel_5.0.git

我们还需要下载 ARM 编译工具链:https://developer.arm.com/downloads/-/arm-gnu-toolchain-downloads (我使用的是10.3的版本)

编译 Kernel #

run_rlk_arm64.sh 这段脚本中提供了下面这几行代码来编译 kernel:

make_kernel_image(){
	echo "start build kernel image..."
	make debian_defconfig
	make -j $JOBCOUNT
}

运行:

./run_rlk_arm64.sh build_kernel

从上面的代码可以看出,编译内核只需要两步:

  1. 配置编译选项:make menuconfig 或者 make %_defconfigmenuconfig 是 Linux 提供的一种文字式图形化配置方式,依赖 libncurses5-devmake %_defconfig 会依赖下面的这几行,在固定的路径去读取相应的 config 文件
# scripts/kconfig/Makefile

%_defconfig: $(obj)/conf
	$(Q)$< $(silent) --defconfig=arch/$(SRCARCH)/configs/$@ $(Kconfig)
  1. make -j$(nproc) 编译

如果是替换本机的 Linux 内核还需要做以下的几步: 3. make modules_install 4. make install

编译 rootfs #

kernel_build=$PWD/rootfs_debian_arm64/usr/src/linux/

prepare_rootfs(){
	if [ ! -d $rootfs_path ]; then
		echo "decompressing rootfs..."
		# split -d -b 80m rootfs_debian_arm64.tar.xz -- rootfs_debian_arm64.part 
		cat rootfs_debian_arm64.part0* > rootfs_debian_arm64.tar.xz
		tar -Jxf rootfs_debian_arm64.tar.xz
	fi
}

build_kernel_devel(){
	kernver="$(cat include/config/kernel.release)"
	echo "kernel version: $kernver"

	mkdir -p $kernel_build
	rm rootfs_debian_arm64/lib/modules/$kernver/build
	cp -a include $kernel_build
	cp Makefile .config Module.symvers System.map vmlinux $kernel_build
	mkdir -p $kernel_build/arch/arm64/
	mkdir -p $kernel_build/arch/arm64/kernel/

	cp -a arch/arm64/include $kernel_build/arch/arm64/
	cp -a arch/arm64/Makefile $kernel_build/arch/arm64/
	cp arch/arm64/kernel/module.lds $kernel_build/arch/arm64/kernel/

	ln -s /usr/src/linux rootfs_debian_arm64/lib/modules/$kernver/build

	# ln to debian linux-5.0/scripts
	ln -s /usr/src/linux-kbuild/scripts rootfs_debian_arm64/usr/src/linux/scripts
	#ln -s /usr/src/linux-kbuild/tools rootfs_debian_arm64/usr/src/linux/tools
}

build_rootfs(){
	if [ ! -f $rootfs_image ]; then
		make install
		make modules_install -j $JOBCOUNT
		# make headers_install

		build_kernel_devel

		echo "making image..."
		dd if=/dev/zero of=$rootfs_image bs=1M count=$rootfs_size
		mkfs.ext4 $rootfs_image
		mkdir -p tmpfs
		echo "copy data into rootfs..."
		mount -t ext4 $rootfs_image tmpfs/ -o loop
		cp -af $rootfs_path/* tmpfs/
		umount tmpfs
		chmod 777 $rootfs_image

		rm -rf $rootfs_path
	fi
}

使用 Qemu 运行 #

  1. 编译 QEMU,编译选项记得开启 --enable-kvm --enable-virtfs
  2. 使用下面的脚本运行
run_qemu_debian(){
	cmd="$QEMU -m 1024 -cpu cortex-a57 -smp 4 -M virt,gic-version=3,its=on,iommu=smmuv3\
		-nographic $SMP -kernel arch/arm64/boot/Image \
		-append \"$kernel_arg $debug_arg $rootfs_arg $crash_arg $dyn_arg\"\
		-drive if=none,file=$rootfs_image,format=raw,id=hd0\
		-device virtio-blk-device,drive=hd0\
		--fsdev local,id=kmod_dev,path=./kmodules,security_model=none\
		-device virtio-9p-pci,fsdev=kmod_dev,mount_tag=kmod_mount\
		$DBG"
	echo "running:"
	echo $cmd
	eval $cmd

}

调试内核 #

我们使用 gdb 加 qemu 来调试内核

07 May 2023

[论文笔记] Ac-Key: Adaptive Caching for LSM-based Key-Value Stores

LSM Tree 是一种对写友好但是对读不友好的数据库。LSM Tree 在查找一个 key-value 的时候需要先在 memtable 中查找,然后是各个层级的 SST 中去查找,所以查找一个 key-value 的时候需要多次 I/O 操作,这对于读多场景下的性能是有很大的影响的。

有多种方法可以优化 LSM Tree 下的读取性能,AC-Key 这篇文章是从缓存角度来进行优化。

给 LSM-Tree 实现 cache 有几个挑战:

  1. LSM是一个分层的数据结构,那么根据kv对所处的层级不同,cache命中带来的收益也是不同的。根据LSM读取数据的方式,一般来说,kv对所处的层级越深,那么cache命中带来的收益就越大。因为KV对的大小并不是固定的,所以LSM树的缓冲策略需要做到缓冲的数据所占用的DRAM空间与节省的IO之间的平衡。
  2. 对于点查与范围查询这两种类型的工作负载需要采用不同的缓冲策略。依赖来说缓冲kv对有助于调查,缓冲blockcache有助于范围查询和点查,另外,对于大value可以选择缓冲value的pointer。对于这三种类型的cache,如何动态调整它们的内存占比,以便获取最大的收益是一个挑战。

因此单一的传统的缓存算法在 LSM-Tree 上的效果并不好。

设计 #

需要考虑4个点:

  1. 缓存KV和KP条目的优点应该结合起来,以有效地提供点查找服务。
  2. 缓存块和KV/KP条目各自具有支持范围查询和点查找的优势。
  3. 缓存算法应该考虑不同缓存条目所占用的DRAM大小和节省的存储I/O数量的差异,尊重LSM-KVS的独特分层结构。
  4. 缓存算法应该适应工作负载的变化。

Caching Efficiency Factor #

论文提出了一个缓存因子 E 来权衡 cache benefit 和 cache cost 之间的关系。

E.png
E 是节省的 IO 次数和所占的 cache space 之间的比值。这个 E 在文章中用在两个地方

  1. ARC 中 L1 和 L2 之间容量的调整
  2. LRU 替换策略

(这个 E 是否可以使用 AI 来辅助确定?)

06 May 2023

[论文笔记]Arc: A Self-Tuning, Low Overhead Replacement Cache

Arc 是一种 LRU 改进算法,在很多负载环境中性能优于常用的 LRU 算法。

基本思想 #

我们需要先了解一下什么是 recency,什么是 frequency。recency 是最近访问时间,frequency 是访问频率。LRU 只基于了 recency,LFU 基于 frequency。所以这两个算法都没有同时利用好 frequency 和 recency,所以在面对不同 workload 的时候性能会有所下降。ARC 其实就是结合了 recency 和 frequency。

DBL #

作者在论文中先引入 DBL 这个算法。 DBL 提出用两个 LRU 来缓存。一个为 L1,用来存放首次访问的数据,另外一个为 L2,用来存放至少访问了两次的数据。如果一个 LRU 的大小是 c,则总的缓存大小是 2c。

Fig.1 是 DBL 的算法。

dbl1.png
也就是说,如果 x 在 L1 或 L2 中,则将 x 移到 L2 的 MRU 端。如果都不在,分为两种情况:第一种是 L1 有 c 个缓存项了。则需要删掉 L1 中的一个页面,然后将 x 放到 L1 的 MRU 端。第二种情况是L1 少于 c 个缓存项,但是如果总的缓存项等于 2c,则需要删掉 L2 LRU 端的项来存放 x。如果小于 2c,则直接插入 L1 的 MRU。(不清楚 LRU 和 MRU 分别指什么的可以看 Fig 2)

04 May 2023

Leveldb 源码解析—— Arena 内存池

内存池的主要作用是减少 mallocnew 的次数,因为每次内存分配都需要经过系统调用,这种开销是十分巨大的,所以通过内存池可以减少这种开销。

Leveldb 的内存池代码放在 util/arena.ccutil/arena.h 中。

class Arena {
 public:
  // ...
 private:
  // ...

  // Allocation state
  char* alloc_ptr_;
  size_t alloc_bytes_remaining_;

  // Array of new[] allocated memory blocks
  std::vector<char*> blocks_;

  // Total memory usage of the arena.
  //
  // TODO(costan): This member is accessed via atomics, but the others are
  //               accessed without any locking. Is this OK?
  std::atomic<size_t> memory_usage_;
};

alloc_ptr_ 指向的是内存块中未分配内存的其实地址的指针

03 May 2023

Quickstart

Install #

brew install hugo

docs

Download Theme #

git clone https://github.com/adityatelange/hugo-PaperMod themes/PaperMod --depth=1

wiki