June, 2011 中的文章

Alice 和 Bob 终于相爱了……

2011 年 June 27日 by 王 聪

From: http://9gag.com/gag/150995

上过网络安全课的都知道，Bob 和 Alice 一直有一腿，要不干嘛他们之间老是发送加密的信息……

如今，他们终于走到一起了！于是我又开始相信爱情了！！

   Life    1 评论

四表妹二三事

2011 年 June 25日 by 王 聪

说起四表妹，恐怕知道她的人无不感叹：她是一朵奇女子，女人中的奇葩。

认识四表妹是在酒桌上，她一出场就把我镇住了。话说我认识的女人也不少，可像她那样首次出场就不把我这外人放眼里的还真不多……当时一起吃饭的是我们三个男人和四表妹，按理说有女士在场我们怎么也得收敛点儿啊，讲黄段子我们还没好意思开口她先开始了，这反倒显得我们几个男人很羞涩了。吃完还不够，她表示酒还没喝够，于是我们跑到大排档接着喝，结果可想而知，她是喝得最多的。

后来和她混熟了，发现她简直是个活宝，走到哪里都是焦点。她在男人圈和女人圈都混得开，人送外号四表妹。四表妹长着一张萝莉脸，正儿八经卖起萌来也能捕获不少男人的心，可是，又不知有多少人看到这张脸然后听到她开口第一句话之后铩羽而归，因为她的发言通常以“你妹啊……”、“我草！”等口头禅开始。有时我甚至怀疑她是不是在黑道上混过，天天以“老娘”、“爷”自居。总之，一副女流氓的德行。

不过，那只是表象，四表妹其实挺有才的。上能搞计算机编程写代码，下能搞文艺摄影织毛衣！女人会的洗衣做饭打扫卫生她都会，男人会的换灯泡修马桶修电脑她也行。用她自己的话说是，“思想上的女流氓，生活上的好姑娘”。我说，我草，这不简直就是二十一世纪新女性的典范嘛！

四表妹的故事有很多，三天三夜都讲不完，何况她每天还在孜孜不倦地制造着新的传说呢。我在这里只选取三个印象深刻的讲一下：

1. 跟四表妹表白过的男生可不少，其中不知哪个倒霉蛋跟她表白时说，“我喜欢你。”她特淡定地回了一句，“其实我也挺喜欢我自己的……”然后就没有然后了！

2. 某理工男在一MM面前炫耀，拿出一张电路图比比划划，MM一脸崇拜地表情，娇嫩地说 ：”你好厉害，我好崇拜你！” 恰好四表妹经过，瞄了一眼，然后淡淡地说，“你这个地方画短路了。” 理工男顿时就凌乱了……

3. 四表妹那天去昌平，出了地铁要打黑车才能到。一个开黑车的男人看到她，拿个烤串儿签子站路边儿威胁她：“你不坐车我扎你了！”这要是换了别的姑娘八成就吓蒙了，可惜他运气太差，这次遇到的对手是四表妹。四表妹打小儿是被吓大的，她马上换了一张哀伤的脸，说了一句：“来吧，我有艾滋！”然后他扭头就走开了……

这就是四表妹，萝莉的脸，纯爷们儿的心，看似女流氓，实则好姑娘！

无论怎么说，可她毕竟还是个小女人，再坚强的外表也掩饰不住苦逼的内心。别人不懂我懂。她所谓的“人生苦短”我总算明白是“人生苦逼而且短暂”的意思了！所以那天我跟她说，别人都觉得我们乐观坚强，可是他们不知道，其实哪一个乐观的人背后不都藏着一段苦逼的故事！

   Life    12 Comments

各种 tunnel

2011 年 June 23日 by 王 聪

网络中有各种各样的 tunnel，让人眼花缭乱。这里简单分析一下各种 tunnel 的作用。

概括地讲，所谓 tunnel 就是把下一层（比如IPv4层）的包封装到上一层（比如 SSH，HTTP）或者同一层（比如IPv6层）的协议中进行传输，从而实现网络之间的穿透。很明显，这种实现有个前提，那就是，发送端和接收端必须各有一个解析这种包的程序或者内核模块才能实现正常通信。

看最简单的例子，SSH Tunnel，在贵国局域网中的大家都懂的。在本地你需要做端口映射，在中转的ssh 服务器上你需要做port forward。当然，把 HTTP 做到 SSH 之上，算是TCP over TCP了。不过还有更狠的，叫 PingTunnel，基于ICMP的。

这是应用层上的 tunnel，下面看重点，内核中的 tunnel。内核中的那几个 tunnel 可以通过 ip tunnel 命令看到：

% ip tunnel help
Usage: ip tunnel { add | change | del | show | prl | 6rd } [ NAME ]
          [ mode { ipip | gre | sit | isatap } ] [ remote ADDR ] [ local ADDR ]
          [ [i|o]seq ] [ [i|o]key KEY ] [ [i|o]csum ]
          [ prl-default ADDR ] [ prl-nodefault ADDR ] [ prl-delete ADDR ]
          [ 6rd-prefix ADDR ] [ 6rd-relay_prefix ADDR ] [ 6rd-reset ]
          [ ttl TTL ] [ tos TOS ] [ [no]pmtudisc ] [ dev PHYS_DEV ]
...

有四个：ipip、gre、sit、isatap。我们一个一个地看。

ipip 是把 IP 层封装到 IP 层的一个 tunnel，看起来似乎是浪费，实则不然。它的作用其实基本上就相当于一个基于IP层的网桥！我们知道，普通的网桥是基于mac层的，根本不需 IP，而这个 ipip 则是通过两端的路由做一个 tunnel，把两个本来不通的网络通过点对点连接起来。ipip 的源代码在内核 net/ipv4/ipip.c 中可以找到。

gre 和它类似，但它功能还要更强大一些，还支持广播，它可以取代 ipip。它的源代码在 net/ipv4/gre.c。更多介绍看这篇文章。

sit 和 isatap 都是 IPv6 over IPv4 的 tunnel，它们的源代码在 net/ipv6/sit.c 中。它们之间也不同，和IPv6的地址有关，写在这里恐怕放不下了，故省略。

别慌，反过来的也有，叫 ip6_tunnel，IPv4 over IPv6。见源代码 net/ipv6/ip6_tunnel.c。

我在前面一篇文章中介绍的 tun 设备，从名字你也看得出来，它不就是 tunnel 的前三个字母嘛！vpnc 使用的就是这个 tunnel，建立一个点对点的通讯，在本地机器上有守候进程vpnc，在远端有vpn服务器。

IPSec 还用到一个叫 L2TP 的 tunnel，在内核源代码 net/l2tp 中，PPTP 是另外一个，在 drivers/net/pptp.c 中实现。这两个比较复杂，我也不熟悉。更多介绍请看内核文档 Documentation/networking/l2tp.txt。

   Linux Application    1 评论

关于 tun/tap 设备

2011 年 June 19日 by 王 聪

长期以来对tun和tap这对兄弟分不太清，今天下定决心研究了一下代码，总算是搞明白了。

首先它们都是从/dev/net/tun里ioctl出来的虚拟设备，一个是通过IFF_TUN，另一个是 IFF_TAP。最好的例子莫过于vpnc里面的代码了。

PLAIN TEXT
C:
  1. int tun_open(char *dev, enum if_mode_enum mode)
  2. {
  3.         struct ifreq ifr;
  4.         int fd, err;
  5.  
  6.         if ((fd = open("/dev/net/tun", O_RDWR)) <0) {
  7.                 error(0, errno,
  8.                         "can't open /dev/net/tun, check that it is either device char 10 200 or (with DevFS) a symlink to ../misc/net/tun (not misc/net/tun)");
  9.                 return -1;
  10.         }
  11.  
  12.         memset(&ifr, 0, sizeof(ifr));
  13.         ifr.ifr_flags = ((mode == IF_MODE_TUN) ? IFF_TUN : IFF_TAP) | IFF_NO_PI;
  14.         if (*dev)
  15.                 strncpy(ifr.ifr_name, dev, IFNAMSIZ);
  16.  
  17.         if ((err = ioctl(fd, TUNSETIFF, (void *)&ifr)) <0) {
  18.                 close(fd);
  19.                 return err;
  20.         }
  21.         strcpy(dev, ifr.ifr_name);
  22.         return fd;
  23. }

用的ioctl的命令都是同一个TUNSETIFF。

虽然是出自一个娘，但它们仍然有大的不同。tun是点对点的设备，而tap是一个普通的以太网卡设备。也就是说，tun设备其实完全不需要有物理地址的！它收到和发出的包不需要arp，也不需要有数据链路层的头！而tap设备则是有完整的物理地址和完整的以太网帧。

用一个实际的例子来验证一下：

tap0      Link encap:Ethernet  HWaddr 0E:78:39:78:E7:A7
          inet addr:192.168.1.109  Bcast:192.168.1.255  Mask:255.255.255.0
          inet6 addr: fe80::c78:39ff:fe78:e7a7/64 Scope:Link
          UP BROADCAST RUNNING MULTICAST  MTU:1500  Metric:1
          RX packets:0 errors:0 dropped:0 overruns:0 frame:0
          TX packets:0 errors:0 dropped:21 overruns:0 carrier:0
          collisions:0 txqueuelen:500
          RX bytes:0 (0.0 b)  TX bytes:0 (0.0 b)

tun0      Link encap:UNSPEC  HWaddr 00-00-00-00-00-00-00-00-00-00-00-00-00-00-00-00
          inet addr:X.X.X.X  P-t-P:X.X.X.X  Mask:255.255.255.255
          UP POINTOPOINT RUNNING NOARP MULTICAST  MTU:1412  Metric:1
          RX packets:6 errors:0 dropped:0 overruns:0 frame:0
          TX packets:6 errors:0 dropped:0 overruns:0 carrier:0
          collisions:0 txqueuelen:500
          RX bytes:690 (690.0 b)  TX bytes:402 (402.0 b)

% ethtool -i tun0
driver: tun
version: 1.6
firmware-version: N/A
bus-info: tun
% ethtool -i tap0
driver: tun
version: 1.6
firmware-version: N/A
bus-info: tap

继续回来看代码。还是vpnc的代码 tunip.c，看它发送的时候做了什么处理：

PLAIN TEXT
C:
  1. static int tun_send_ip(struct sa_block *s)
  2. {
  3.         int sent, len;
  4.         uint8_t *start;
  5.  
  6.         start = s->ipsec.rx.buf;
  7.         len   = s->ipsec.rx.buflen;
  8.  
  9.         if (opt_if_mode == IF_MODE_TAP) {
  10. #ifndef __sun__
  11.                 /*
  12.                  * Add ethernet header before s->ipsec.rx.buf where
  13.                  * at least ETH_HLEN bytes should be available.
  14.                  */
  15.                 struct ether_header *eth_hdr = (struct ether_header *) (s->ipsec.rx.buf - ETH_HLEN);
  16.  
  17.                 memcpy(eth_hdr->ether_dhost, s->tun_hwaddr, ETH_ALEN);
  18.                 memcpy(eth_hdr->ether_shost, s->tun_hwaddr, ETH_ALEN);
  19.  
  20.                 /* Use a different MAC as source */
  21.                 eth_hdr->ether_shost[0] ^= 0x80; /* toggle some visible bit */
  22.                 eth_hdr->ether_type = htons(ETHERTYPE_IP);
  23.  
  24.                 start = (uint8_t *) eth_hdr;
  25.                 len += ETH_HLEN;
  26. #endif
  27.         }
  28.  
  29.         sent = tun_write(s->tun_fd, start, len);
  30.         if (sent != len)
  31.                 syslog(LOG_ERR, "truncated in: %d -> %d\n", len, sent);
  32.         hex_dump("Tx pkt", start, len, NULL);
  33.         return 1;
  34. }

从上面的代码我们很容易看出：

1. 所谓发送就是对/dev/net/tun进行写操作。对称的，所谓接收就是读操作。
2. 如果是tap设备，发送时还要多加一个以太网的头。

我们再看内核中对应的代码是怎么处理的，在drivers/net/tun.c 中的 tun_get_user()：

PLAIN TEXT
C:
  1. switch (tun->flags & TUN_TYPE_MASK) {
  2.         case TUN_TUN_DEV:
  3.                 if (tun->flags & TUN_NO_PI) {
  4.                 //...
  5.                 }
  6.  
  7.                 skb_reset_mac_header(skb);
  8.                 skb->protocol = pi.proto;
  9.                 skb->dev = tun->dev;
  10.                 break;
  11.         case TUN_TAP_DEV:
  12.                 skb->protocol = eth_type_trans(skb, tun->dev);
  13.                 break;

内核直接忽略了 tun 设备的以太网帧。现在，整个流程我们就已经很清楚了。

可是，上面只是用vpnc的例子。我们知道，实际中像kvm虚拟机才是tap的使用大户，我们很有必要看一下kvm是怎么使用tap设备的。为了方便起见，我们不看 qemu-kvm，因为它的代码过于复杂，我们看一个简单的kvm tools的实现。

这部分的主要代码在 virtio/net.c里面，virtio_net__tap_init()是在启动虚拟机时初始化tap设备的，然后启动两个线程分别监控tap设备的收发，代码是virtio_net_rx_thread()和virtio_net_tx_thread()，它们负责把进来的IO操作转换成对/dev/net/tun的读写。可是，IO操作是怎么进来的呢？这是关键。

顺着代码里的“针”一个个找下去，我们不难发现，IO操作是由kvm模拟出来的。首先它会把CPU指令中对应的IO操作进行转化，这部分在内核中，arch/x86/kvm/emulate.c::x86_emulate_insn()：

PLAIN TEXT
C:
  1. do_io_in:
  2.                 c->dst.bytes = min(c->dst.bytes, 4u);
  3.                 if (!emulator_io_permited(ctxt, ops, c->src.val, c->dst.bytes)) {
  4.                         emulate_gp(ctxt, 0);
  5.                         goto done;
  6.                 }
  7.                 if (!pio_in_emulated(ctxt, ops, c->dst.bytes, c->src.val,
  8.                                      &c->dst.val))
  9.                         goto done; /* IO is needed */
  10.                 break;

pio_in_emulated() 调用的 emulator_pio_in_emulated() 会进一步触发KVM_EXIT_IO：

PLAIN TEXT
C:
  1. static int emulator_pio_in_emulated(int size, unsigned short port, void *val,
  2.                              unsigned int count, struct kvm_vcpu *vcpu)
  3. {
  4.         if (vcpu->arch.pio.count)
  5.                 goto data_avail;
  6.  
  7.         trace_kvm_pio(0, port, size, 1);
  8.  
  9.         vcpu->arch.pio.port = port;
  10.         vcpu->arch.pio.in = 1;
  11.         vcpu->arch.pio.count  = count;
  12.         vcpu->arch.pio.size = size;
  13.  
  14.         if (!kernel_pio(vcpu, vcpu->arch.pio_data)) {
  15.         data_avail:
  16.                 memcpy(val, vcpu->arch.pio_data, size * count);
  17.                 vcpu->arch.pio.count = 0;
  18.                 return 1;
  19.         }
  20.  
  21.         vcpu->run->exit_reason = KVM_EXIT_IO;
  22.         vcpu->run->io.direction = KVM_EXIT_IO_IN;
  23.         vcpu->run->io.size = size;
  24.         vcpu->run->io.data_offset = KVM_PIO_PAGE_OFFSET * PAGE_SIZE;
  25.         vcpu->run->io.count = count;
  26.         vcpu->run->io.port = port;
  27.  
  28.         return 0;
  29. }

内核部分结束，转到用户空间，用户空间的 vcpu 会捕捉到这个事件，在 kvm-cpu.c::kvm_cpu__start() 中：

PLAIN TEXT
C:
  1. case KVM_EXIT_IO: {
  2.                         bool ret;
  3.  
  4.                         ret = kvm__emulate_io(cpu->kvm,
  5.                                         cpu->kvm_run->io.port,
  6.                                         (u8 *)cpu->kvm_run +
  7.                                         cpu->kvm_run->io.data_offset,
  8.                                         cpu->kvm_run->io.direction,
  9.                                         cpu->kvm_run->io.size,
  10.                                         cpu->kvm_run->io.count);
  11.  
  12.                         if (!ret)
  13.                                 goto panic_kvm;
  14.                         break;
  15.                 }

kvm__emulate_io() 就会调用在 virtio/net.c 注册的 virtio_net_pci_io_in()，数据就这样流向了 tap 网卡了。

   Linux Application    3 Comments

关于 loop device

2011 年 June 18日 by 王 聪

我们平时挂载一个img文件一般是通过mount -o loop来挂载，而它实际上等价于下面两步：

losetup /dev/loop0 example.img
mount /dev/loop0 /home/you/dir

我们可以看 util-linux-ng 源代码中的 mount/mount.c 文件，在 loop_check() 里有这么一段代码：

PLAIN TEXT
C:
  1. if (!*loopdev || !**loopdev)
  2.           *loopdev = find_unused_loop_device();
  3.         if (!*loopdev)
  4.           return EX_SYSERR;     /* no more loop devices */
  5.         if (verbose)
  6.           printf(_("mount: going to use the loop device %s\n"), *loopdev);
  7.  
  8.         if ((res = set_loop(*loopdev, *loopfile, offset, sizelimit,
  9.                             opt_encryption, pfd, &loop_opts))) {

第一步是把文件和某个空闲的loop设备相关联起来，这里是 /dev/loop0。用的是系统调用ioctl(LOOP_SET_FD)，这样以来对 /dev/loop0 的读写就会转化成对 example.img 的读写了。

第二步就容易理解了，和挂载普通块设备没什么区别了。mount之所以把这两步合为一步是想让你省去手工搜索空闲的loop设备。

现在看看它是怎么工作的：调用 LOOP_SET_FD 的时候内核会把 img 对应的 struct file 关联到设备对应的 lo->lo_backing_file 上去。同时，内核启动一个内核线程来监控 /dev/loopX 的读写请求（loop_thread()），对于每一个 bio，它都会进行相应的转换，对应到对 lo->lo_backing_file 上的读写。以写为例，我们可以看do_lo_send_write()：

PLAIN TEXT
C:
  1. static int do_lo_send_write(struct loop_device *lo, struct bio_vec *bvec,
  2.                 loff_t pos, struct page *page)
  3. {
  4.         int ret = lo_do_transfer(lo, WRITE, page, 0, bvec->bv_page,
  5.                         bvec->bv_offset, bvec->bv_len, pos>> 9);
  6.         if (likely(!ret))
  7.                 return __do_lo_send_write(lo->lo_backing_file,
  8.                                 page_address(page), bvec->bv_len,
  9.                                 pos);
  10.         printk(KERN_ERR "loop: Transfer error at byte offset %llu, "
  11.                         "length %i.\n", (unsigned long long)pos, bvec->bv_len);
  12.         if (ret> 0)
  13.                 ret = -EIO;
  14.         return ret;
  15. }

而__do_lo_send_write() 直接就调用 file->f_op->write() 了。

   Linux Application    1 评论

Sleep sort

2011 年 June 16日 by 王 聪

4chan BBS 上一个排序的程序火了，它叫休眠排序，很有意思。

PLAIN TEXT
BASH:
  1. #!/bin/bash
  2. function f() {
  3.     sleep "$1"
  4.     echo "$1"
  5. }
  6. while [ -n "$1" ]
  7. do
  8.     f "$1" &
  9.     shift
  10. done
  11. wait

其实它的原理很简单，就是，要对N个整数进行排序的话，启动N个进程（线程），每个进程休眠对应的整数指定的秒数，然后再打印该数，最后你在终端上看到的肯定是排序之后的结果了……看了之后你会不会也觉得这太坑爹了？！可是，它就是能工作，而且占用CPU很少！

值得一提的是底下回复中给出的OpenMP版本（如果要尝试的话需要安装openmpi）和Perl版本。

PLAIN TEXT
C:
  1. /*
  2.  * @file sleepsort.c
  3.  * @brief sorts numbers
  4.  *
  5.  * @compile gcc sleepsort.c -fopenmp -o sleepsort
  6.  *
  7.  * @author Gerald Jay Sussman (Massachvsetts Institvte of Technology)
  8.  */
  9.  
  10. #include <stdio.h>
  11. #include <stdlib.h>
  12. #include <omp.h>
  13.  
  14. int main(int argc, char **argv) {
  15.   int i;
  16.  
  17.   omp_set_num_threads(argc);
  18.  
  19. #pragma omp parallel for
  20.   for (i = 0; i <argc - 1; i++) {
  21.     long int this = atol(argv[i+1]);
  22.  
  23.     sleep(this);
  24.  
  25.     printf("%ld\n", this);
  26.     fflush(stdout);
  27.   }
  28.  
  29.   return 0;
  30. }

PLAIN TEXT
PERL:
  1. fork and sleep $_, say, last for @ARGV; 1 while 1 <=> -wait

除了不能对浮点数和负数进行排序，它还有一个缺点，那就是其中某个进程需要睡眠最大的那个数指定的时间，然后才能得出最后结果。下面有人提出了改进，我试了试，没有一个完美的。理想的情况下它应该能够对正负整数、浮点数进行排序，而且最坏也不要花太多时间，感兴趣的同学可以自己改进一下。

   Programming    7 Comments

推荐一部科幻片

2011 年 June 14日 by 王 聪

众所周知，明天要上映一部宏伟的科幻片，我郑重推荐大家拉着自己的妹子或者小伙儿去电影院看一下。主要理由有三点：

1. 该片用生动的例子向我们讲述了如何激情地组建一个派对；

2. 该片用隐喻的手法向我们展示了那时候多么好：学生不用上课，工人不用上班，搞革命还可以搞一搞革命女青年……

3. 该片励志，片中有那么多持有贵国绿卡的明星出镜，这告诉我们移民要趁早。

有不少人对该片拿下八亿票房表示质疑，我看主要是因为嫉妒，导演定八亿这个目标实在是太谦虚了！全国有七千多万高危人群，一人买一张50元的电影票都够35亿了！更何况还有那么多像我这样不明真相的群众。所以，我觉得该片拿下八亿美元不成问题！

   Life    2 Comments

Kernel Crash Logging and Core Dump

2011 年 June 1日 by 王 聪

这里是今天在 LinuxCon Japan 2011 上讲的 slides，没想到来的听众那么多，整个房间差不多要坐满了……

   Linux Kernel    1 评论