Nov 9, 2013

jiffies和NO_HZ

Linux内核中很多事件都是时间驱动的, 通俗讲就是动作的发生都要以时间为条件, 例如延迟, 定时以及周期执行等.

jiffies

为了让内核能够感知时间, 硬件提供了时钟发生器, 它可以被编程以某个固定频率自行触发时间中断, 然后内核藉由中断服务程序来处理时间驱动的事件. 时钟发生器的频率就是HZ, 意味着时钟发生器每HZ分之一秒产生一个节拍, 而自系统启动以来产生的总节拍数就是全局变量jiffies.

jiffies变量的类型是unsigned long, 如果体系结构为32位, 时钟频率为1000, 这个变量大概50天后就会溢出. 所以使用jiffies的关键是不要直接进行比较而要使用内核提供的宏, 例如:

<linux/jiffies.h>
#define time_after(a,b) ...
#define time_before(a,b) ...
#define time_in_range(a,b,c) ...

NO_HZ

回过来说HZ, 它的值应该被设定为多少呢? 频率低了的话, 精度不够, 影响整个系统的实时性; 频率高虽然能提高精度和实时性, 但又会造成系统负担过重, 大量的时间被用来处理时钟中断服务程序. 而且由于使用场景的不同, HZ并没有一个通用的理想值, 内核的默认值也曾多次改变.

为了兼顾实时性和能耗, 内核从2.6.17开始引入了tickless的特性, 也被称为NO_HZ. 发展到现在(3.10之后, 目前3.12), 内核为此功能提供了三个选项:

  1. CONFIG_HZ_PERIODIC, 每个节拍都不会被忽略.
  2. CONFIG_NO_HZ_IDLE, 默认设置, 节拍在空闲的CPU上会被忽略.
  3. CONFIG_NO_HZ_FULL, 节拍在空闲的或者只有一个可执行任务的CPU上会被忽略.

之所以默认启用是因为tickless有着立竿见影的好处, 省电和降低负载, 尤其是在移动, 虚拟化和高性能运算等环境下.

ref:

1, https://lwn.net/Articles/549580/
2, https://www.kernel.org/doc/Documentation/timers


Jun 26, 2013

用Kprobes调试内核

Kprobes是一种运行时动态调试内核的机制, 你可以用它设置断点并收集调试信息, 甚至改变内核行为.

Kprobes分三种, 普通kprobes以及基于普通kprobes的jprobes和kretprobes. kprobes可以注入某个地址, jprobes用来注入某个函数入口, 而kretprobes则用来注入某个函数返回.

实现原理

Kprobes的实现主要利用了处理器的异常和单步执行特性. 以普通kprobes举例, 注册时它会复制一份被注入的指令, 并加入断点(例如x86的int 3), 当CPU执行到被注入的指令时就会陷入到Kprobes中, 此时Kprobes先运行钩子函数”pre_handler”, 然后单步执行被复制的指令, 并且由于是单步执行模式, 指令执行完毕后会再次触发异常而陷入到Kprobes中, 此时Kprobes会运行钩子函数”post_handler”并最终返回.

使用方法

通常情况下, Kprobes以内核模块的形式工作, 模块的init函数用来注册Kprobes, exit函数相应得用来注销, pre_handler和post_handler分别在单步执行被复制的指令前后运行, fault_handler则在单步执行发生异常时运行.

Kprobes模块写起来很简单, 下面是一个内核源码中的例子, 演示如何在每次do_fork()的时候打印选定寄存器中的内容.

#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/kprobes.h>

/* For each probe you need to allocate a kprobe structure */
static struct kprobe kp = {
	.symbol_name	= "do_fork",
};

/* kprobe pre_handler: called just before the probed instruction is executed */
static int handler_pre(struct kprobe *p, struct pt_regs *regs)
{
	printk(KERN_INFO "pre_handler: p->addr = 0x%p, ip = %lx,"
			" flags = 0x%lx\n",
		p->addr, regs->ip, regs->flags);

	/* A dump_stack() here will give a stack backtrace */
	return 0;
}

/* kprobe post_handler: called after the probed instruction is executed */
static void handler_post(struct kprobe *p, struct pt_regs *regs,
				unsigned long flags)
{
	printk(KERN_INFO "post_handler: p->addr = 0x%p, flags = 0x%lx\n",
		p->addr, regs->flags);
}

/*
 * fault_handler: this is called if an exception is generated for any
 * instruction within the pre- or post-handler, or when Kprobes
 * single-steps the probed instruction.
 */
static int handler_fault(struct kprobe *p, struct pt_regs *regs, int trapnr)
{
	printk(KERN_INFO "fault_handler: p->addr = 0x%p, trap #%dn",
		p->addr, trapnr);
	/* Return 0 because we don't handle the fault. */
	return 0;
}

static int __init kprobe_init(void)
{
	int ret;
	kp.pre_handler = handler_pre;
	kp.post_handler = handler_post;
	kp.fault_handler = handler_fault;

	ret = register_kprobe(&kp);
	if (ret < 0) {
		printk(KERN_INFO "register_kprobe failed, returned %d\n", ret);
		return ret;
	}
	printk(KERN_INFO "Planted kprobe at %p\n", kp.addr);
	return 0;
}

static void __exit kprobe_exit(void)
{
	unregister_kprobe(&kp);
	printk(KERN_INFO "kprobe at %p unregistered\n", kp.addr);
}

module_init(kprobe_init)
module_exit(kprobe_exit)
MODULE_LICENSE("GPL");

这只是一个简单的打印示例, Kprobes还可以修改被注入函数的上下文, 如内核数据结构和寄存器, 并且都是在运行时动态修改, 多么美好!

ref:

1, https://lwn.net/Articles/132196/
2, https://www.kernel.org/doc/Documentation/kprobes.txt
3, http://www.ibm.com/developerworks/library/l-kprobes/index.html


Dec 28, 2012

内核中的编译器屏障rep_nop()

最近在看Linux内核中mutex_lock()和spin_lock()实现, 发现一个很有意思的函数调用: rep_nop()

/* REP NOP (PAUSE) is a good thing to insert into busy-wait loops. */
static inline void rep_nop(void)
{
	asm volatile("rep; nop" ::: "memory");
}

汇编指令rep的本意是重复执行rep后的指令直到ecx寄存器中的值变成0为止. 但是这里为什么要重复nop呢? 于是反汇编, 发现rep;nop其实是被翻译成了pause指令.

以下摘自Intel软件开发者手册第二卷第四章(下载地址):

Improves the performance of spin-wait loops. When executing a “spin-wait loop,” processors will suffer a severe performance penalty when exiting the loop because it detects a possible memory order violation. The PAUSE instruction provides a hint to the processor that the code sequence is a spin-wait loop. The processor uses this hint to avoid the memory order violation in most situations, which greatly improves processor performance. For this reason, it is recommended that a PAUSE instruction be placed in all spin-wait loops.

An additional function of the PAUSE instruction is to reduce the power consumed by a processor while executing a spin loop. A processor can execute a spin-wait loop extremely quickly, causing the processor to consume a lot of power while it waits for the resource it is spinning on to become available. Inserting a pause instruction in a spin-wait loop greatly reduces the processor’s power consumption.

This instruction was introduced in the Pentium 4 processors, but is backward compatible with all IA-32 processors. In earlier IA-32 processors, the PAUSE instruction operates like a NOP instruction. The Pentium 4 and Intel Xeon processors implement the PAUSE instruction as a delay. The delay is finite and can be zero for some processors. This instruction does not change the architectural state of the processor (that is, it performs essentially a delaying no-op operation).

This instruction’s operation is the same in non-64-bit modes and 64-bit mode.

简单说, Intel推荐在spin-wait loops中使用pause指令, 因为它既可以避免性能损失, 避开内存序列冲突, 还可以减少电源消耗, 并且不会有兼容性问题.

PS, 至于为什么mutex_lock()的实现也是spin-wait loop, 则是因为内核引入了spinning mutexes的特性, 详细信息在此: https://lkml.org/lkml/2009/1/14/393


Aug 24, 2012

Vim神级插件: EasyMotion

Vim的移动操作很强大, hjkl左下上右, wb按词移动, fF前后搜索等等, 方便, 快速. 但也有软肋, 跨越多行的精确跳转就相当不尽人意. 幸好, 有一款堪称神级表现的插件: EasyMotion.

简单说, 它提供了一组对应默认移动操作的键绑定, 能搜索并高亮所有可能的选择以供跳转, 类似Vimperator里链接跳转的方式, 效果相当棒, 就像下面这样(via YouTube):

总之, 强烈推荐! 具体说明和下载见项目地址: https://github.com/Lokaltog/vim-easymotion/


Jul 8, 2012

Linux在x86-64下的虚拟内存布局

普通x86架构下的Linux内存布局大家应该都很清楚了. 物理内存分为ZONE_DMA, ZONE_NORMAL和ZONE_HIGHMEM三个区, 虚拟内存则一般是0-3G为用户空间, 3G-(4G-1)为内核空间. 那么, x86-64架构下呢?

有多大

首先, 目前大部分的操作系统和应用程序并不需要16EB( 2^64 )如此巨大的地址空间, 实现64位长的地址只会增加系统的复杂度和地址转换的成本, 带不来任何好处. 所以目前的x86-64架构CPU都遵循AMD的Canonical form, 即只有虚拟地址的最低48位才会在地址转换时被使用, 且任何虚拟地址的48位至63位必须与47位一致(sign extension). 也就是说, 总的虚拟地址空间为256TB( 2^48 ).

如何布局

然后, 在这256TB的虚拟内存空间中, 0000000000000000 - 00007fffffffffff(128TB)为用户空间, ffff800000000000 - ffffffffffffffff(128TB)为内核空间. 这里需要注意的是, 内核空间中有很多空洞, 越过第一个空洞后, ffff880000000000 - ffffc7ffffffffff(64TB)才是直接映射物理内存的区域, 也就是说默认的PAGE_OFFSET为ffff880000000000. 从这里我们也可以看出, 这么大的直接映射区域足够映射所有的物理内存, 所以目前x86-64架构下是不存在高端内存, 也就是ZONE_HIGHMEM这个区域的(参考这篇).

如何映射

64位寻址模式是PAE的扩展. 页大小支持PAE所支持的4K和2M, 以及独有的1G. 页表分为4级, 不但扩展了PAE的Page-Directory Pointer Table, 还添加了一个Page-Map Level 4(PML4)映射表. 巧妙之处在于, 这个表不但可以通过扩展来支持以后的完整64位地址空间, 也兼容很有可能出现的第5级页表.

ref:

1, https://en.wikipedia.org/wiki/X86-64
2, https://en.wikipedia.org/wiki/Physical_Address_Extension
3, http://lxr.linux.no/#linux+v3.4/Documentation/x86/x86_64/mm.txt


May 26, 2012

Gràcies, Pep

四年十四冠. 感谢你, 瓜迪奥拉, 感谢你带给我那么多的快乐.


May 1, 2012

用LUKS/dm-crypt加密块设备

What and How

LUKS是Linux下块设备加密的标准组件, 不同于文件系统级别的eCryptfs等, LUKS更底层, 也更方便.

用LUKS建立加密分区很简单, 只需安装cryptsetup, 然后执行下面的命令按提示设置密码就可以了, 建议不加额外参数, 选用默认的加密算法, 效率不会差太多, 但是更安全.

# cryptsetup luksFormat /dev/sdXY

打开加密分区的命令如下, 验证成功后会在/dev/mapper/下生成名为foo的块设备, 之后建立文件系统, 挂载, 卸载等操作和普通的块设备一致.

# cryptsetup luksOpen /dev/sdXY foo

关闭加密分区也很简单, 先卸载foo, 然后执行下面的命令就是了:

# cryptsetup luksClose /dev/mapper/foo

加密现有Linux系统

基于安全的考虑, 我把笔记本上现有的Linux系统迁移到了LVM over LUKS的环境, 必要的操作有下面这几个:

  1. 备份boot, root, home等分区
  2. 建立LVM over LUKS分区环境
  3. 恢复boot, root, home等分区
  4. 修改grub, fstab, crypttab
  5. 重新生成initramfs

因为这些操作都比较危险, 我就不详细说了, 具体可以参考这里这里.

自动挂载已加密移动硬盘

另外, 我也把移动硬盘加密了, udev的自动挂载规则贴在下面, 依赖pmount, 能够自动弹出终端以便于输入密码验证.

KERNEL!="sd[b-z]*", GOTO="automount_exit"

ACTION=="add", SUBSYSTEM=="block", PROGRAM=="/sbin/blkid -o value -s TYPE %N", RESULT!="crypto_LUKS", RUN+="/bin/su adam -c '/usr/bin/pmount %k'"
ACTION=="add", SUBSYSTEM=="block", PROGRAM=="/sbin/blkid -o value -s TYPE %N", RESULT=="crypto_LUKS", RUN+="/bin/su adam -c '/usr/bin/xterm -display :0.0 -e /usr/bin/pmount %k'"

ACTION=="remove", SUBSYSTEM=="block", RUN+="/bin/su adam -c '/usr/bin/pumount %k'"

LABEL="automount_exit"

Apr 5, 2012

搭建内核开发调试环境

闲来无事, 总结一下内核开发调试环境的搭建过程, 希望能对和我一样的内核新手们有所帮助.

方案

我的测试系统在QEMU中运行, Host和Guest的架构都是x86_64, 用Busybox生成的initrd做为根文件系统, KGDB做为调试器.

生成内核

内核中需要打开的选项是CONFIG_EXPERIMENTAL, CONFIG_DEBUG_INFO, CONFIG_KGDBCONFIG_KGDB_SERIAL_CONSOLE, 同时需要关闭CONFIG_DEBUG_RODATA选项. 然后make bzImage编译生成内核. 具体选项的意义可以去翻内核文档, 这里就不罗嗦了.

生成根文件系统

打开Busybox的CONFIG_STATICCONFIG_INSTALL_NO_USR选项, 执行makemake install编译并生成, 然后参照下面的步骤创建initrd根文件系统:

mkdir temp && cd temp

#创建系统目录
mkdir -p dev etc/init.d mnt proc root sys tmp
chmod a+rwxt tmp

cp -rf ../busybox/_install/* ./

#挂载系统目录
cat << EOF > etc/fstab
proc  /proc  proc  defaults  0  0
sysfs  /sys  sysfs defaults  0  0
tmpfs  /tmp  tmpfs defaults  0  0
EOF

cat << EOF > etc/inittab
::sysinit:/etc/init.d/rcS
::respawn:-/bin/sh
tty2::askfirst:-/bin/sh
::ctrlaltdel:/bin/umount -a -r
EOF

cat << EOF > etc/init.d/rcS
#!bin/sh
/bin/mount -a
#用mdev生成设备文件
/sbin/mdev -s
EOF

chmod 755 etc/init.d/rcS

find ./ | cpio -o -H newc | gzip > ../rootfs.img

启动QEMU

qemu-system-x86_64 -kernel kernel.img -append \
"root=/dev/ram rdinit=/sbin/init" -initrd rootfs.img 或
qemu-system-x86_64 -kernel kernel.img -append \
"root=/dev/ram rdinit=/sbin/init kgdboc=ttyS0,115200 kgdbwait" \
-initrd rootfs.img -serial tcp::1234,server 第二个命令开启了KGDB, 将Guest系统的串口映射到了Host系统的1234端口, 并在启动过程中等待gdb的连接.

启动gdb

内核开启KGDB的情况下, 执行gdb vmlinux, 其中vmlinux是未压缩的内核. 然后target remote localhost:1234连接kgdb.

接下来就和普通的gdb没什么大的区别了, 比如在sched_clock函数处设置断点break sched_clock, continue继续运行, 到达断点后打印jiffies_64变量print jiffies_64等等.

另外, 运行过程中可以在测试系统里执行echo g > /proc/sysrq-trigger让gdb重新得到控制权.

For 懒人

顺手在github上建了个项目, 可以自动搭建整个内核开发调试环境, 详见README.

http://github.com/adam8157/kernel-studio

git clone git://github.com/adam8157/kernel-studio.git

Feb 9, 2012

迁移到Octopress

长久以来我就对Wordpress有着诸多不满: 冗余, 速度慢, 非静态, 依赖数据库, 迁移成本高… 但是苦于没有合适的替代品, 只能忍受. 直到我最近发现了Octopress.

什么是Octopress

Octopress是一个基于Jekyll的静态博客生成系统

Octopress有什么优点

  • 纯静态: 最终发布的只有HTML, Javascript和CSS

  • Markdown: 使用Markdown作为源文件语言, 易写易读

  • 搭建方便: 简洁的Ruby框架, 操作十分简单方便

  • 迁移成本低: 因为是静态网页, 对主机要求低, 且迁移方便

  • 版本控制友好: 整个项目和文章源代码都是纯文本(图片等除外), 方便版本控制

如何搭建和迁移


Feb 2, 2012

Markdown真不错

Markdown是个轻量级的标记语言, 容易读, 容易写. 具体的介绍和语法可以去项目主页查看.

除了直接在某些网站(例如github)上使用, 还可以通过pandoc把Markdown文件转换成HTML, MediaWiki, LaTeX, 甚至Groff, Texinfo, DocBook, OpenDocument, EPUB. 更厉害的是, pandoc还可以套用LaTeX模板和CSS样式表, 真乃神器!

于是我参考这里写了个幻灯片模板, 调用pandoc和latex生成pdf, 相当舒服.