Apr 30, 2016

自动处理Make的依赖关系

Make是如何工作的

简单说, Makefile中指定目标和依赖, 然后Make运行的时候会检测文件的时间信息, 如果目标落后于依赖的修改时间则目标需要重新生成, 以此达到按需生成, 节省时间的目的.

实际场景中的问题是什么

举个简单的例子:

OBJS := foo.o bar.o

program: $(OBJS)
	gcc $(OBJS) -o program

%.o: %.c
	gcc -c $(CFLAGS) $< -o $@

这个Makefile表达的意思是由foo.cbar.c生成program, 中间目标文件分别依赖相应的源文件. 但是实际场景远没有这么简单, 例如每个.o还会各自依赖很多不同的.h头文件, 怎么办? 挨个列出来么? 太麻烦了, 而且依赖关系还可能会变化.

依赖关系能自动生成么

当然可以, 直接看代码:

OBJS := foo.o bar.o

program: $(OBJS)
	gcc $(OBJS) -o program

-include $(OBJS:.o=.d)

%.o: %.c
	gcc -MD -MP -c $(CFLAGS) $< -o $@

相较于之前的版本, 这次每个.o的编译过程中都会生成一个Makefile语法的.d文件, 里面列出了gcc分析得出的依赖关系. 所以当我们把这些.d文件包含进来之后, Make就可以知道详细的依赖关系信息, 进而判断哪些依赖发生了变化, 哪些目标需要重新生成.

PS, 如果你不想把系统头文件也列在依赖里面, 可以把参数-MD换成-MMD.


Mar 14, 2016

Linux下的性能分析工具: Perf

什么是Perf

Perf是一个与Linux Kernel紧密结合的软件性能分析工具.

Perf的工作原理

Perf的基本原理是hook事件, 对被分析对象进行采样, 获取数据并分析. 例如在时钟中断触发时采样context可以分析函数的运行时间, 在cache miss触发时采样可以分析缓存的工作效率. 此外, Perf还支持缺页, 进程切换, 具体内核函数等事件, 具体可以参考perf list.

Perf怎么用

  • perf stat ./a.out, perf stat -p 1234, 分析程序的整体性能, 可以看到程序的CPU使用率, 进程切换次数, cache利用情况等等.

  • perf top, 类似top命令, 可以分析整个系统当前的状态, 例如寻找当前系统最耗时的用户进程或者内核函数.

  • perf recordperf report, 可以记录并分析一段时间内的性能事件.

  • perf --help :)

Happy π day!

这只是篇简介, 主旨是要说明Perf很强大很易用以及更新一下blog. 另外, 圆周率日快乐!

ref:

1, https://perf.wiki.kernel.org/
2, http://www.brendangregg.com/perf.html


Aug 31, 2015

龟兔算法为什么有效

什么是龟兔算法

检测单链表上的环有个很经典的算法叫做”弗洛伊德判圈算法”, 也叫”龟兔算法”.

龟兔算法的基本思路

是否有环

我们让龟(tortoise)和兔(hare)从单链表的起点出发, 每次龟走一步, 兔走两步, 如果time_a步之后龟兔相遇, 则该链表有环.

环的长度

上述算法刚判断出存在环时, 龟和兔位于同一节点. 此时让兔不动, 而龟不断前进, 肯定又会相遇, 而这一次龟前进的步数显然就是环的长度length.

环的起点

还是之前所说龟兔相遇的节点, 首先兔保持原位, 而把龟置回链表起点, 然后龟和兔同时走, 每次都走一步, 经过time_b步最终再次相遇, 则这次相遇的节点就是环的起点start.

龟兔算法为什么有效

假设兔每次走step步, 那么只要单链表中存在环, 而且龟到达环的起点之后, 龟和兔之间的路程差能够是环长度length的整数倍, 则二者就能相遇. 即:

((step - 1) * time_a) % length == 0  && time_a >= start

其中start和length是固定的, time_a却无限增长, 所以总会有机会整除, 所以龟兔算法可以判断是否有环.

略过显而易见的长度计算, 接着说查找环的起点. 当仅当step为2, 即兔每次走两步时, 根据前面的条件得知time_a能被length整除. 于是我们接着假设time_b为龟到达环的起点start后绕了n圈再次到达起点, 即time_b == start + n * length, 则兔此时的位置(假设绕了m圈)是time_a + time_b - m * length, 代入后为time_a + start + (n - m) * length, 因为step为2时time_a能被length整除, 所以兔此时正好也在起点start处, 所以龟兔算法可以找到环的起点.


Apr 26, 2015

Hybrid bootable USB stick for legacy BIOS & UEFI

This is a simple note for people who are googling this topic right now, and you are welcome.

Backgrounds

  • Legacy BIOS needs bootloaders to be installed into MBR and the reserved space after it.

  • UEFI only needs bootloaders in ESP(EFI System Partition).

  • There is no resource competition between legacy BIOS and UEFI requirements.

Preparations

  • grub-pc-bin and grub-efi-amd64-bin packages for Debian users.

  • An USB storage stick, MBR or GPT. Some unallocated space(1MB is enough) at the beginning of disk if you are using GPT.

  • A vfat partition with the “boot” flag.

Cooking

# mount /dev/sdb1 /media/sdb1

# grub-install --target=i386-pc --boot-directory=/media/sdb1/boot /dev/sdb

# grub-install --target=x86_64-efi --efi-directory=/media/sdb1/ --boot-directory=/media/sdb1/boot --removable /dev/sdb

Configuration(just a template)

# /media/sdb1/boot/grub/grub.cfg
set root=(hd0,1)

menuentry "FreeDOS" {
        linux16  /boot/freedos/memdisk
        initrd16 /boot/freedos/balder10.img
}
menuentry "Memtest86+" {
        loopback loop /boot/systemrescuecd-x86-x.y.z.iso
        linux16 (loop)/bootdisk/memtestp
}
menuentry "Ubuntu xx.yy" {
        set isofile="/boot/ubuntu-xx.yy-desktop-amd64.iso"
        loopback loop $isofile
        linux (loop)/casper/vmlinuz.efi boot=casper iso-scan/filename=$isofile noprompt noeject
        initrd (loop)/casper/initrd.lz
}
menuentry "SystemRescueCd" {
        set isofile="/boot/systemrescuecd-x86-x.y.z.iso"
        loopback loop $isofile
        linux   (loop)/isolinux/rescue64 docache isoloop=$isofile
        initrd  (loop)/isolinux/initram.igz
}
menuentry "Install Debian GNU/Linux" {
        linux   /boot/debian/vmlinuz priority=low recommends=false
        initrd  /boot/debian/initrd.gz
}
menuentry "Debian GNU/Linux Rescue Mode" {
        linux   /boot/debian/vmlinuz priority=low recommends=false rescue/enable=true
        initrd  /boot/debian/initrd.gz
}

Done, enjoy fixing others’ computers then, which I already quit :D


Nov 23, 2014

使用GNU GLOBAL索引代码

什么是GLOBAL

GLOBAL是GNU出品的一款代码索引工具.

GLOBAL有什么优点

  • 原生支持C, C++, 汇编等6种语言的代码索引, 借助插件支持的更多达25种

  • 支持多种查找功能, 例如最常用的查找定义, 调用和文件位置等

  • 提供gtags-cscope命令, 兼容cscope

  • 相对于cscope, 查找匹配更加快速和准确

  • 支持增量更新, 而且比cscope的增量更新快很多很多

  • 开发活跃, 上一次发布新版本是两个月前, 而cscope的上一次是两年前

如何使用GLOBAL

简单讲, 在代码目录中执行gtags -i建立索引数据库, 然后使用global命令查找匹配. 例如global symbol查看symbol的定义, global -r symbol查看symbol在哪被引用, 等等. 详见: https://www.gnu.org/software/global/globaldoc_toc.html

Vim中使用GLOBAL的小技巧

继承Vim中cscope的接口和键绑定:

:set cscopeprg=gtags-cscope

自动从当前文件夹递归向上搜索索引数据库并加载:

function! LoadDatabase()
	let db = findfile("GTAGS", ".;")
	if (!empty(db))
		set nocscopeverbose
		exe "cs add " . db
		set cscopeverbose
	endif
endfunction
autocmd BufEnter *.[ch] call LoadDatabase()

Aug 5, 2014

为什么Linux内核(目前)依赖GCC

最近围绕着Linux内核编译环境发生了很多有趣的事情. 先是LLVMLinux的[1]大批特性进入mainline, 内核几乎可以用Clang编译了[2], 后来又是Linus Torvalds狂喷GCC 4.9.0[3], 很有意思. 而这些事情都有一个共同的背景: 目前Linux内核编译依赖GCC. 那么, 为什么?

不通用的命令参数

Linux内核使用了很多GCC的命令参数来进行优化, 其它编译器也一直在试图兼容, 但目前尚未有能完美兼容GCC参数的其它编译器出现.

不支持的内联汇编

__asm__ 并不被其它编译器全面支持, 或者所支持的架构平台有限, 即使是如此简单的用法:

asm("movl %ecx, %eax");

特殊的C语言扩展

GCC支持很多独有的特殊C扩展, 例如绑定变量与寄存器, 函数嵌套等, 此外大多数其它编译器也不支持结构体中的变长数组, 但是内核中存在, 例如:

void func(int i) {
	struct foo_t {
		char a[i];
	} foo;
}

特殊的段标记

内核中使用了很多段标记例如__refdata, __initdata和__exitdata来优化链接器的行为, 这些特性大多也是GCC独有.

#define __refdata       __section(.ref.data)
#define __initdata      __section(.init.data)
#define __exitdata      __section(.exit.data)

GCC的特殊行为或者bug

有时候GCC的某个行为是特殊的甚至是错误的, 但是却恰好迎合了某段代码的需要. 例如IA-64平台上GCC会自动重读一个指向volatile数据的指针的指向内容[4].

ref:

1, http://llvm.linuxfoundation.org
2, http://www.phoronix.com/scan.php?page=news_item&px=MTY2MjY
3, http://www.phoronix.com/scan.php?page=news_item&px=MTc1MDQ
4, https://software.intel.com/en-us/articles/intel-c-compiler-for-linux-kernel-building


Apr 7, 2014

MSI under Linux

什么是MSI

MSI(Message Signaled Interrupts)是一种中断形式, 依靠设备将约定数据写入指定地址来通知CPU中断的产生.

MSI从PCI 2.2开始支持, 在PCI 3.0中得到扩展. 支持更多中断以及拥有独立配置各个中断能力的MSI-X则从PCI 3.0开始被支持.

MSI的优点

相对基于引脚的中断响应方式, 首先MSI支持更多的中断且不需要复用, 其次启用MSI的设备的数据写入和中断触发是串行的, 驱动接收到中断信号的时候就可以确定数据已经准备就绪, 而不需要检查相应设备的寄存器, 这提升了性能.

如何在Linux下使用MSI

PCI设备默认以基于引脚的中断响应方式初始化, 然后由驱动来检测是否支持MSI并决定是否启用, 如果启用MSI失败则会回退到基于引脚的中断响应方式. 下面是关于MSI的几个重要的内核函数:

启用MSI并给设备分配一个中断:

int pci_enable_msi(struct pci_dev *dev)

允许驱动申请minvec至maxvec个中断:

int pci_enable_msi_range(struct pci_dev *dev, int minvec, int maxvec)

获取设备申请的中断向量个数:

int pci_msi_vec_count(struct pci_dev *dev)

禁用MSI, 回退到基于引脚的中断响应方式:

void pci_disable_msi(struct pci_dev *dev)

ref:

1, https://en.wikipedia.org/wiki/Message_Signaled_Interrupts
2, https://www.kernel.org/doc/Documentation/PCI/MSI-HOWTO.txt


Apr 2, 2014

What is dentry

dentry, 既directory entry的缩写, 是Linux VFS中用来管理树状目录的结构, 在内存中生成, 并不存在于实际的文件系统中.

dentry的结构

dentry结构的定义(linux/include/dcache.h)如下:

struct dentry {
        /* RCU lookup touched fields */
        unsigned int d_flags;           /* protected by d_lock */
        seqcount_t d_seq;               /* per dentry seqlock */
        struct hlist_bl_node d_hash;    /* lookup hash list */
        struct dentry *d_parent;        /* parent directory */
        struct qstr d_name;
        struct inode *d_inode;          /* Where the name belongs to - NULL is
                                         * negative */
        unsigned char d_iname[DNAME_INLINE_LEN];        /* small names */

        /* Ref lookup also touches following */
        struct lockref d_lockref;       /* per-dentry lock and refcount */
        const struct dentry_operations *d_op;
        struct super_block *d_sb;       /* The root of the dentry tree */
        unsigned long d_time;           /* used by d_revalidate */
        void *d_fsdata;                 /* fs-specific data */

        struct list_head d_lru;         /* LRU list */
        /*
         * d_child and d_rcu can share memory
         */
        union {
                struct list_head d_child;       /* child of parent list */
                struct rcu_head d_rcu;
        } d_u;
        struct list_head d_subdirs;     /* our children */
        struct hlist_node d_alias;      /* inode alias list */
};

这其中比较基本和重要的成员是d_parent, d_child, d_name和d_inode, 分别用来记录上级目录, 下级成员(如果当前dentry为目录文件), 文件名以及所指向的inode.

dentry如何形成树状结构

区别于记录文件数据的inode, dentry只用来记录文件的组织和管理信息. 路径就是由多个dentry连接而成的, 例如/home/user/foo路径中的根目录/, 目录home, 目录user和文件foo各自都是一个dentry结构. 所有的dentry索引起来就形成了文件系统的树状结构.


Dec 31, 2013

Why can't vmlinux be booted

In short, because vmlinux is only the image of bare kernel, which is running after system booted.

ref:

https://en.wikipedia.org/wiki/Vmlinux


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