Linux TCP/IP协议栈的通用编码模式

2007-03-28 13:00
和其他内核功能一样，每个网络功能都是内核成员中的一个。因此，它必须合理且公平的使用内存, CPU和其他共享资源。绝大多数功能并非内核中一段独立的程序，而是根据该功能而或多或少的与内核中其他部分相互影响。因此它们总是试图，尽可能的，使用类似的体系结构来实现类似的功能。
对许多内核组件来说有些需求是通用的，比如为同一数据结构分配好几个实例，或者跟踪一个数据结构的参考以避免不安全的内存重分配，等等。下面我们来看linux解决这些需求的一些通用的方法。我们也会谈到在查看内核编码时可能遇到的通用的编码技巧。
1.缓存
内核使用kmalloc和kfree来分配和释放内存。这两个函数的使用方法和用户空间的函数 malloc 和free的使用方法类似.
一个内核组件通常需要分配一个数据结构的多个实例。如果分配和释放频繁发生，相关内核组件的初始化函数(比如路由子系统中的fib_hash_init函数)通常会分配一个特殊的内存缓存以加速内存分配。当一个内存块释放时，它会被返回给与分配时相同的内存缓存。
以下是一些需要内核来维护内存缓存的网络数据结构：
Socket buffer descriptors
这个缓存，由net/core/sk_buff.c中的skb_init分配，它用于分配sk_buff结构。sk_buff结构可能是网络子系统中分配和释放频率最高的数据结构。
Neighboring protocol mappings
邻居协议使用内存缓存来分配neighbour结构，这个结构保存L3到L2的地址映射关系。
Routing tables
路由代码使用两个内存缓存来分配两种数据结构，这两种数据结构定义了路由表。
以下是使用内存缓存时会用到的一些函数：
kmem_cache_create
kmem_cache_destroy
建立或销毁缓存 .
kmem_cache_alloc
kmem_cache_free
从内存缓存中分配或释放一个对象。它们通常会在一个包装函数中被调用，这个包装函数在更高的层次上处理分配和释放的请求。比如：kfree_skb函数处理释放sk_buff的请求，但是只有在所有对此结构的引用释放之后并且相关的子系统（比如，防火墙）已执行了清除操作之后，才调用kmem_cache_free释放这个sk_buff。
从一个给定的内存缓存中能够分配多少个实例的数量限制通常在kmem_cache_alloc的包装函数中指定，但是有时也可以通过/proc文件系统中的参数来调整。
2. 缓存和哈希表
使用缓存来提升性能的技巧很常见。在网络代码中，有L3到L2映射的缓存(比如IPV4中的ARP缓存)，路由表缓存，等等。
缓存的查找函数通常都有一个输入值来说明在缓存查找没有命中的情况下，是否需要分配一个新的元素并把它加入到缓存中。而其他类型的查找函数都只会把没有命中的元素添加进去。
缓存通常使用哈希表来实现。内核提供了许多数据结构，比如单向和双向的链表，这些数据结构可以直接用来实现简单的哈希表。
处理相同哈希值的标准方法是把这些元素放入一个链表。但是，遍历这些链表所花的时间通常要比通过哈希值来查找元素所用的时间长。因此，要尽量采用冲突几率小的哈希函数。
如果哈希表(不管它是否用作缓存)的查找时间是一个子系统的关键参数，那么就应该实现一个机制，通过增加哈希表的大小来减小平均的冲突几率，这样可以减小平均的查找时间
你也可以在其他子系统，比如neighboring layer，看到通过给键值增加一个随机变量使得哈希值在缓存bucket中可以均匀的分布。这样可以减小DoS(Denial of Service)的危害，因为这类DoS 都是通过特定参数使得哈希表的表项都集中在同一个哈希值上。
3. 引用计数器
如果一段代码访问一个已经被释放的数据结构，内核是不会感到高兴的，用户也不会为内核的反映而高兴的。为了避免这些烦人的问题，同时也让垃圾收集机制运行得更简便和高效，许多数据结构都会保持一个引用计数。好的内核程序员每次访问一个数据结构时，都会相应的增加或减小这个数据的引用计数。对于那些需要引用计数的数据结构，相应的拥有这个数据结构的内核模块通常会导出两个增加和减小引用计数的函数。这些函数通常被命名为xxx_hold(增加引用计数)和xxx_release(减小引用计数)。有时，减小引用计数的函数也可能被命名为xxx_put(例如
dev_put用于减小net_device结构的引用计数)。
虽然我们假设内核程序员都非常认真，但是，内核程序员也是人，所以他们不可能总是写出没有bug的代码。使用引用计数是一个简单但是有效的方法来防止释放那些还在使用的数据结构。但是，这个方法也不可能解决所有的问题。以下就是一些忘记增加或减小引用计数而引起的后果：
如果你释放了一个数据结构，但是忘了调用xxx_release函数，内核就永远都不会允许释放这个数据结构(除非另一个有bug的代码恰好错误地调用了两次减小引用计数的函数)。这将会导致内存被逐步耗尽.
如果你引用了一个数据结构，但是忘了调用xxx_hold函数，在某一时刻你恰好是这个数据结构的唯一引用者，这时，这个数据结构会被提前释放，原因就是你没有增加它的引用计数。这种情况的危害要比前一个更大。如果你后续的操作试图引用这个结构，将导致其他数据被破坏，或者导致内核立即崩溃。
如果需要释放一个数据结构，就要先通知这个结构的引用者，让它们先减小这个结构的引用计数。这可以通过notification chain来实现。
在以下情况下，需要增加数据结构的引用计数：
两个数据结构有紧密的关系。在这种情况下，一个结构会包含一个初始化指向另一个结构的指针。
一个定时器函数需要访问一个数据结构。在定时器运行时，会增加这个数据结构的引用计数，这样做的原因是：在定时器执行完成前，你不希望这个数据结构被提前释放了。
成功地在一个链表或哈希表中找到一个匹配的表项。在大多数情况下，这个查找到的表项会被查找者使用。因此，在查找函数里面，成功匹配的数据结构需要增加它的引用计数，而这个引用计数会被查找者减小。
当数据结构的最后一个引用被释放后，这个数据结构就可以被释放了，因为它现在已没 有什么作用了。当然，这并不是一个必须的操作。
4. 垃圾收集
内存是一种共享并且有限的资源，所以不应该浪费，尤其是在内核中。因为内核没有使用虚拟内存。大多数的内核子系统都实现了某种类型的垃圾收集机制去收集那些无用的或者过期的数据结构所占用的内存。从已有的实现来看，主要有以下两种垃圾收集机制：
异步
这种类型的垃圾收集机制与具体的事件无关。它使用一个定时器函数去定时检查一组数据结构并把可以释放的数据结构释放掉。判断一个数据结构是否可以被释放的条件依赖于子系统的功能和内部逻辑，但是一个基本的条件就是这个数据结构的引用计数为0。
同步
当内存短缺时，如果不能等到异步的垃圾收集函数定时运行，内核可以激活一个立即执行的垃圾收集函数。在这个函数里，判断一个数据结构是否可以被释放的条件可以和异步的垃圾收集函数不一样(例如，它可以释放一些引用计数不为0的数据结构)。
5. 函数指针和虚拟函数表 (VFTs)
使用函数指针是一个可以得到清晰的C语言代码的同时又能利用面向对象语言的某些优点的好方法。在定义数据结构时(对象)，你可以包含一组函数指针(方法)。一部分或全部的数据结构操作可以通过这些函数来完成。在C语言中，数据结构中的函数指针如下所示：
struct sock {            ...            void     (*sk_state_change)(struct sock *sk);            void     (*sk_data_ready)(struct sock *sk, int bytes);      ...      }; 使用函数指针最大的好处是在初始化对象时，可以根据对象的不同或对象作用的不同而把函数指针赋为不同的值。这样，同样是调用sk_state_change函数，可以就会激活不同sock对象的不同函数。
在网络代码中，函数指针被大量的使用。以下就是一些例子：
在路由子系统中，处理进入或发出包时，它会初始化sk_buff中的两个函数指针。
当一个包准备好往网络设备发送时，它会被传递给net_device结构中的hard_start_xmit函数指针。这个指针在网络设备驱动和网络设备绑定时被赋值。
当L3的协议发送一个包时，它会调用一组函数指针中的一个。这些指针在L3的地址解析协议处理中被初始化。具体调用哪个函数要看它被初始化成哪个函数，L3到L2的地址解析过程是透明的(例如，IPv4使用arp协议)。如果地址解析过程没有必要，这些函数指针会被赋为其他值。
在上面的例子中，我们可以看到，函数指针可以被用作不同内核组件之间的接口；或者是一个子系统在不同的条件下调用不同函数的机制；或者是被用做允许不同的协议，驱动程序或功能可以使用各自不同的方法的机制。
我们来看一个例子。当一个设备驱动向内核注册一个网络设备后，内核会执行一些与设备类型无关的函数。在某些点上，它会调用net_device结构中的一些函数指针来让设备驱动做一些事情。设备驱动可以把这些函数指针初始化为自己的函数，也可以把它置为NULL，这表示内核执行缺省函数就可以了。
在调用函数指针前，要先检查一下函数指针的值，以避免引用空指针。下面是一个从register_netdevice取得的快照例子：
if (dev->init && dev->init(dev) != 0) {          ...      } 函数指针有一个主要的缺点：它使得阅读源代码变得困难一些。当阅读一个给定的代码路径时，你可能会关注其中的函数指针调用。在这种情况下，你需要先了解这个函数指针是如何被初始化的之后，才能阅读后续的代码。函数指针初始化与很多不同的因素有关：
如果函数指针的赋值与特定的数据有关，比如协议标识或者收到包的是某个特定的驱动程序。这种情况下，很容易找到真正的函数。比如，如果drivers/net/3c59x.c驱动收到一个包，你可以在设备初始化函数中找到net_device结构中的函数指针被赋值为那些值。.
如果函数指针的赋值与更复杂的逻辑相关，比如L3到L2地址映射中的状态值。这种情况下，函数指针被赋为何值与外部的事件相关，因而难以预测。
一组函数指针放到一个数据结构中，通常叫做一个虚函数表(VFT)。当虚函数表被用做两个子系统间的接口，比如L3和L4间的接口；或者被导出做为某个内核组件的接口(一组对象)时，它里面可能包含很多不同的指针，这些指针在不同的协议或功能中使用。每一个功能可能只用到一小部分函数指针。当然，如果虚函数表用得过度，就会变得非常庞大，这种情况下，可能需要重新设计你的数据结构。
6. goto 语句
没有哪个c程序员会喜欢goto语句的。如果不看goto语句的历史(计算机编程历史上最长也是最有名的争论之一)，我的总结是，goto语句是个过时的东西，但是为什么linux内核还在使用它？
任何一段使用goto语句的代码都可以用无goto语句的代码重写。使用goto语句会降低代码的可读性，同时会增加调试的难度。因为你不能完全确定执行goto之后的语句所需的条件。
让我们来做这样的类比：给定树中的任意节点，你可以明确知道从根到节点的路径。但是如果是随机缠绕的葡萄藤，你就不能总是得到一条从根到节点的唯一路径。
但是，由于c语言没有提供异常捕获机制(其他语言里。异常捕获通常也是被禁止的， 因为使用异常捕获会导致性能下降，并且增加代码的复杂性)，小心地使用goto语句可以很容易地将代码跳转到异常处理代码中。在内核编程中，特别是网络代码，异常事件很常见，所以，goto语句就成了一个方便的工具。虽然内核中使用了goto语句，但是我并不主张开发人员滥用它。尽管内核中有超过30,000条goto语句，但是它们主要用于在同一个函数里面返回不同的值，或者跳出超过一层的嵌套。
7. 容器Vector定义
某些情况下，一个数据结构会在末尾包含一个可选的数据块。如下面的例子所示
struct abc {       int age;      char *name[20];      ...      char     placeholder[0];    }
可选块从placeholder开始。请注意，placeholder被定义成长度为0的Vector。这就意味着，在给abc分配空间时，同时也分配了一个可选块，placeholder就是块的指针。如果不需要可选块，placeholder就只是一个指向结构末尾的指针，它不占用任何空间。
因此，如果abc在不同的代码中被使用，每一个代码都使用相同的基本定义(避免做同样的事情而采用不同的方法)，同时可以根据自己的需求来扩展abc。
1.2.8. 条件编译 (#ifdef and family)
编译器的条件编译有时很有必要。过度地使用条件编译会降低代码的可读性，但是我可以声明，linux内核没有滥用它们。条件编译可以在多种情况下使用，但是我们感兴趣的是它用于检查内核是否支持某一特性。make xconfig这样配置工具会决定某一特性是编译到内核，或者完全不支持，或者编译成内核模块。
使用#ifdef或#if defined检查内核是否支持某一特性的例子如下：
包含或者不包含数据结构的某个成员
struct sk_buff {       ...   #ifdef CONFIG_NETFILTER_DEBUG       unsigned int nf_debug;   #endif       ...   }
在这个例子中，netfilter的调试功能需要sk_buff结构中的nf_debug项。如果内核不支持netfilter
调试功能(只有一小部分开发人员需要这项功能)，就没必要包含这一项， 否则它只会使得每个网络包占用更多的内存。
函数中，包含或不包含某段代码
int ip_route_input(...)   {       ...           if (rth->fl.fl4_dst == daddr && rth->fl.fl4_src == saddr &&               rth->fl.iif == iif &&               rth->fl.oif == 0 &&   #ifndef CONFIG_IP_ROUTE_FWMARK               rth->fl.fl4_fwmark == skb->nfmark &&   #endif               rth->fl.fl4_tos == tos) {               ...           }   }
为一个函数选择正确的原型
#ifdef CONFIG_IP_MULTIPLE_TABLES   struct fib_table * fib_hash_init(int id)   #else   struct fib_table * _ _init fib_hash_init(int id)   {       ...   }
为函数选择正确的定义
#ifndef CONFIG_IP_MULTIPLE_TABLES   ...   static inline struct fib_table *fib_get_table(int id)   {       if (id != RT_TABLE_LOCAL)           return ip_fib_main_table;       return ip_fib_local_table   }   ...   #else   ...   static inline struct fib_table *fib_get_table(int id)   {       if (id == 0)           id = RT_TABLE_MAIN;       return fib_tables[id];   }   ...   #endif
请注意这个例子和前一个例子的区别。在前一个例子中，函数体在 #ifdef/#endif 块之外， 而这个例子中，每一块都包含一个完整的函数定义。
变量定义或初始化，还有宏，都可以使用条件编译。
知道某个函数或宏有多个定义非常重要，具体使用哪个函数或者宏与条件编译有关，前面就有这样的例子。否则，你看的函数，变量或者宏的定义可能不是你所希望看到的那个。
9. 条件检查的编译优化
大多数时候，内核会把一个变量与一个外部值比较来看某一条件是否已满足，这种比较的结果很大程度上是可以预测的。这样的例子很常见，例如，检查合法性的代码。内核使用likely和
unlikely两个宏来分别表示返回的结果是true(1)或false(0)。这两个宏使用gcc可根据它的返回值来优化编译结果的特性来提升代码的性能。
这里有个例子。我们假设调用do_something函数，在出错的情况下，我们调用handle_error来处理错误：
err = do_something(x,y,z);   if (err)       handle_error(err); 如果do_something很少出错，我们可以将代码重写为：
err = do_something(x,y,z);   if (unlikely(err))       handle_error(err); 一个能够使用likely和unlikely宏来优化代码的例子是处理ip option。由于ip option只在特定的情况下出现，内核可以假设大多数的ip包都没有ip option.当内核转发一个ip包时，它不需要关心
Ip option选项。在ip_forward_finish里面，处理转发包的最后阶段，这个函数使用unlikely宏来检查是否有ip选项需要处理。
10. 互斥
锁在网络代码中大量使用，你会发现本书的每个话题都会涉及到它。互斥，锁机制和同步是编程领域中的一个很有意思，但也很复杂的话题，尤其是在内核编程领域。经过多年的发展和优化，linux内核中已经包含了多种途径来完成代码的互斥。这里我们重点描述网络代码中用的锁。
每种互斥机制都有它适用的环境。下面描述的是网络代码中常见的互斥机制：
自旋锁
这个锁，同一时刻只能由一个线程占有。其他试图得到锁的线程会重复尝试得到锁直到这个锁被释放。由于循环会有一定的消耗，所以，这个锁一般用在多处理器系统里面，而且开发者都希望线程占有锁的时间不会太长。由于其他尝试得到锁的线程也有一定的消耗，所以，占有锁的线程，其执行过程不能睡眠。
读写自旋锁
如果一个锁的用户可以明确分为只读和读写两类，这种情况下，推荐使用读写自旋锁。自旋锁和读写自旋锁的区别在于后者可以由多个读者同时占有，但是，如果写者获得了锁，读者就不能获取这个锁。由于读者的优先级比写者高，所以这个锁适用于读者多(或者只读的锁定请求多)，而写者少(或者写的锁定请求少)的情况。
如果锁被读者获得，写者就不能获得这个锁；只有读者释放了这个锁，写者才能获得这个锁。
读-拷贝-更新Read-Read-Update(RCU)
RCU是linux最新提供的一种互斥机制。它在以下情况下表现良好：
读请求多而读写请求很少
获得锁的代码自动执行，而且不会睡眠.
被锁保护的数据结构通过指针访问
第一条规则与性能有关，后面两条规则是使用RCU时的限制条件。
值得注意的是，按照第一条规则的条件，一般都使用读写自旋锁来做为RCU的替代。为了理解为什么在某些情况下RCU的性能要高于读写自旋锁，你需要考虑其他一些因素，比如SMP系统中的处理器缓存的影响等。
网络代码中使用RCU的例子是路由子系统。路由查找的次数比路由更新的次数多，而且路由查找代码不会在中途被阻塞。
内核提供了信号量，但是本书描述的网络代码中很少用到它。
11.主机字节顺序和网络字节顺序序的转换
多于一个字节的数据结构在内存中的存储有两种不同的格式：Little Endian和 Big Endian。Little Endian格式把最低字节存储在最低的地址中，而Big Endian刚好与此相反。linux操作系统使用的存储格式与具体的处理器有关。例如，intel处理器使用Little Endian模型，而Motorola处理器使用Big Endian模型。
假设我们的linux主机从远端的主机上收到了一个IP包。由于不知道这个包在远端的主机上是以何种方式发送的，我们就不知道如何去读取这个包的包头。因为这个原因，每个协议簇都必须定义它的网络包的存储格式。比如，TCP/IP协议栈就使用Big Endian模型。
但是内核开发人员依然面临一个问题：必须编写可以在不同处理器，不同存储模式下使用的代码。有些处理器的存储模式可能与网络包的存储模式一致，这种情况下，就不需要转换网络包的存储格式。
但是，每次内核读写ip头中超过一个字节的变量时，它都必须首先将网络字节序转换成主机字节序或是相反。这个原则同样适用于TCP/IP协议栈中的其他协议。如果网络字节序和本机字节序一致，转换函数就执行一个空操作，因为它们之间不需要转换。这样做可以提高代码的可移植性，因为这种情况下，只有转换函数是与平台相关的。
表1列出了转换两字节和四字节变量时用到的函数：
Table 1. Byte-ordering conversion routines
Macro
Meaning (short is 2 bytes, long is 4 bytes)
htons
Host-to-network byte order (short)
htonl
Host-to-network byte order (long)
ntohs
Network-to-host byte order (short)
ntohl
Network-to-host byte order (long)
 
这些宏的定义放在include/linux/byteorder/generic.h头文件中。下面是每个平台如何把本平台的存储格式与这些宏的定义关联起来的：
每个平台相关的目录下include/asm-XXX/，都有一个文件byteorder.h。
这个文件包含include/linux/byteorder/big_endian.h和include/linux/byteorder/little_endian.h两个文件中的一个，具体包含哪个，与处理器的存储格式有关
little_endian.h和big_endian.h两个文件都包含通用文件include/linux/byteorder/generic.h。表1中的宏的定义依赖于little_endian.h和big_endian.h中定义的宏，这样，不同平台的存储格式就会影响到表1中定义的宏。
表1中定义的每个宏xxx都有一个与之对应的宏__constant_xxx，用于转换常量的存储格式，例如，一个枚举类型的元素。值得注意的是，表1中的宏是通用的宏，不管它的输入值是常量还是变量。
我们前面说过，存储格式对超过一个字节的数据项非常重要。存储格式对超过一个字节的位域定义同样非常重要。例如，IPV4的头部定义。内核使用_ LITTLE_ENDIAN_BITFIELD和_ _BIG_ENDIAN_BITFIELD两个条件编译参数来控制数据结构的定义，这两个条件在前面所述的
little_endian.h和big_endian.h两个文件中定义。
12. Catching Bugs
追踪有些函数只能在某种条件下调用，或者不能在某种条件下调用。内核使用BUG_ON和BUG_TRAP宏来捕获那些未满足条件的函数调用。如果BUG_TRAP的输入值是false
， 内核打印一段告警信息。而BUG_ON会打印一段出错信息并且使内核崩溃。
13. Statistics
在实现某项功能时，统计某个特定条件出现的次数是个好习惯。比如统计缓存命中和失败的次数，内存分配成功和失败的次数等。本书会列出并描述每一个在网络代码中出现的统计变量。
14. 计时
内核经常需要测量从某个给定时刻开始经过了多长时间。例如，某个cpu使用量大的任务通常会在给定的时间段后释放cpu。如果被重新调度后，它会继续运行。这对内核程序非常重要，虽然linux内核支持内核抢占。网络代码中，一个常见的例子就是实现垃圾收集的例程。
内核空间中时间用时钟嘀哒来计量。一个嘀哒是两个连续的时钟中断之间的时间隔。时钟处理不同的任务(在这里，我们不关注它们)，并且每秒发生HZ次。HZ是一个体系结构相关的变量。例如，如果在i386机器上把它初始化为1000，就意味着每秒发生1000次时钟中断，并且两个连续中断之间的时间隔是1毫秒。
每一次时钟中断都会把全局变量jiffies加一。这就意味着，在任何时刻，jiffies代表从开机到现在所发生的嘀哒的数量，并且n*HZ值一般都表示n秒。
如果一个函数需要测量时间隔，它可以把当前的jiffies值保存到一个局部变量中，然后把这个值与后续时刻的jiffies相比较以求得它们之间的差值。通过这个差值(两个时刻间的嘀哒数量)就可以计算出从计时开始经过了多长时间。
下面的例子展示了一个函数，它需要执行一些任务，但是它占用cpu的时间不能超过一个嘀哒数。当do_something完成时，它把job_done置为一个非零值，然后函数就可以返回了：
unsigned long start_time = jiffies;   int job_done = 0;   do {       do_something(&job_done);       If (job_done)           return;   while (jiffies - start_time < 1);