Linux内核分析 - 网络[十三]：校验和

内核版本：2.6.34
报文的IP校验和、ICMP校验和、TCP/UDP校验和使用相同的算法，在RFC1071中定义，网上这方面的资料和例子很多，就不解释算法流程了，而是侧重于在实现的变化和技巧。

The checksum algorithm is simply to add up all the 16-bit words in one's complement and then to take the one's complement of the sum.
      校验和的计算可以分为两步：累加、取反。这个划分很重要，它大大减少了校验和计算的消耗。校验和计算首要要明确一点：校验和计算是很耗时的！原因并不在于 算法复杂，而是在于输入数据的庞大，试想传送500M文件，则内核要校验500M字节的数据，并且对于每个报文，都是要进行校验和。所以协议栈的校验和实 现并不是简单明了的，使用了很多方法来规避这种开销。

第一：推迟校验和计算
      按照协议的规定，报文到达每一层，首先验证校验和是否正确，丢弃掉不正确的报文，再才会进行后续操作。对于传输层下的协议，内核是这样做的，因为IP只需 要校验IP报头，最多60字节；而对于网络层上的协议，内核就不是这样做的，ICMP/TCP/UDP都需要校验报文的内容，而这部分消耗是很大的。
      以UDP为例，在报文传递到UDP处理时，它并不会去验证校验和是否正确，而是直接将报文skb插入到相应socket的接收队列 sk_receive_queue中。等到真正有程序要接收这个报文，从接收队列中取出时，内核才去计算校验和。考量下这种做法，由于推迟了校验和计算， 因此很多错误的报文都被接收了，它们会占用处理报文的流程，直到报文准备进入用户空间时，这时候才计算了校验和，发现错误并丢弃掉。这样看似乎平白无故增 加了开销，必竟校验和的计算是一定要进行的。但这样做，将校验和计算推迟到了拷贝报文到用户空间时，这两个操作的绑定是很关键的。本来，校验和计算要遍历 一次报文，而拷贝又要遍历一次报文，这样就是两次遍历操作，合并后用一次遍历搞定，它所节约的开销是远远多于额外支付的。

第二：分离校验和计算步骤
      开始提到校验和的计算分为两步：累加、取反，将这两步分开后，会发现校验和是可以一部分一部分计算的，最后再用每部分计算的值求和取反。这个特性在另一方 面对拷贝和校验和计算同时进行提供了支持。并且，由于报文可能是分片重组的，这样报文内容并不是一起存储在线性地址空间中，而是将分片挂在第一个分片 skb的frag_list上，这部分内容是存储在非线性地址空间的。因此，拷贝会一个分片一个分片的进行，由于校验和计算的划分，它也可以一个分片一个 分片的计算。csum_partial()和csum_fold()就是为此而生的，前者计算累加，后者计算取反。
      所以一般校验和会这样计算，skb_checksum()计算skb的累加和，并和之前已经计算出的累加和skb->csum相加，然后csum_fold()对最后结果取反，就是得到的校验和。

sum = csum_fold(skb_checksum(skb, 0, len, skb->csum));

第三：改进校验和计算
      RFC1071中校验和计算是每16bit为单位的，但实际在累加这一步是可以调整的，内核计算是每32bit计算的，单位越大，循环就少，效率也自然会高。下面要说明的是32bit累加与16bit累加结果是一致的。
      假设要计算8个字节的校验和，这8字节按每16bit分成4份：1,2,3,4。左边是每16bit累加的过程，右边是每32bit累加的过程： 

      会出现疑惑的地方就是累加的进位问题，左边16bit累加进位加到sum中，右边32bit累加进位也要加到sum中，至于2,4相加产生的进位，和 16bit累加进位的结果是一样的。下面就是32bit累加的代码段，w>result判断是否产生了进位，假设X+Y=Z产生了进位溢出，则X& lt;Z且Y

unsigned int carry = 0;
do {
 unsigned int w = *(unsigned int *) buff;
 count--;
 buff += 4;
 result += carry;
 result += w;
 carry = (w > result);
} while (count);
result += carry;
result = (result & 0xffff) + (result >> 16);

第四：校验和计算技巧
      节省校验和最好的办法就是不计算校验和，这在某些情况下是可行的，比如大流量发包时或局域网中，这时效率比正确性更为重要。 skb->ip_summed参数就是为此目的，CHECKSUM_UNNECESSARY就跳过校验和计算。或者用户在发包时设置校验和字段 checksum=0，也会跳过校验和计算。

skb->ip_summed = CHECKSUM_UNNECESSARY;

      另外为了加速校验和计算，很多网卡都提供了硬件计算校验和，特别的，linux使用了skb->ip_summed和skb->csum来使 用硬件计算能力来帮助校验TCP/UDP报文。CHECKSUM_COMPLETE表示硬件进行了计算，计算结果存储在skb->csum中。

skb->ip_summed == CHECKSUM_COMPLETE;

      在很多芯片的实现上，校验和的计算代码都是用汇编来实现了，这也是出于校验和计算的效率考虑。

最后，简单分析下校验和计算的两个核心函数。
do_csum() 校验和累加
      校验和计算的主体部分是32bit为单位计算的，并假设buff起始地址是对齐过的，长度也是对齐过的。因此，传入的buff要进行处理以满足假设。 

保证计算的起始地址是字节对齐
      这里的对齐有16bit对齐和32bit对齐。起始地址是对齐是为了效率，比如起始地址是奇数，那么累加时用16bit或32bit就很可能跨越一个int范围，即读一个数要两次内存操作；对齐后读一个数都只用一次内存操作。
      如果不是偶数字节，则odd=1，处理掉第一个字节，使超地址变成偶数。

odd = 1 & (unsigned long) buff;
if (odd) {
#ifdef __LITTLE_ENDIAN
 result += (*buff << 8);
#else
 result = *buff;
#endif
 len--;
 buff++;
}

      当然处理掉第一个字节后，从buff计算校验和与从buf+1计算校验和结果显然是不同的，下面这步在校验和计算完成后，就是为了处理这种差异的。

if (odd)
 result = ((result >> 8) & 0xff) | ((result & 0xff) << 8);

      还是以例子说明，一个5字节的buff，起始地址addr(1)=0x1，下面是传统计算和从偶数地址开始计算的对比，要注意的是累加进程中是循环进位 的，即溢出的进位会加到最低位。因此，无论哪种方法，1,3,5累加进位会加到2+4中，而2,4累加进位会加到1+3+5中，这也是最后调换前后 8bit的值就可以保证两者相等原因。 

保证计算的长度是偶数字节
      长度对齐理由很简单，累加是以16bit为单位的，因此主体部分只计算偶数字节，如果有多余的一个字节len & 1，则进行如下处理。

if (len & 1)
#ifdef __LITTLE_ENDIAN
  result += *buff;
#else
  result += (*buff << 8);
#endif

      最后是计算的主体部分，可以看到，它并不是单纯的16bit累加，而是用32bit累加do-while循环。当然，为了进行32bit累加，要将起始地址处理成32bit对齐，长度也要处理成32bit对齐。

count = len >> 1;  /* nr of 16-bit words.. */
if (count) {
 if (2 & (unsigned long) buff) {
  result += *(unsigned short *) buff;
  count--;
  len -= 2;
  buff += 2;
 }
 count >>= 1;  /* nr of 32-bit words.. */
 if (count) {
  unsigned int carry = 0;
  do {
   unsigned int w = *(unsigned int *) buff;
   count--;
   buff += 4;
   result += carry;
   result += w;
   carry = (w > result);
  } while (count);
  result += carry;
  result = (result & 0xffff) + (result >> 16);
 }
 if (len & 2) {
  result += *(unsigned short *) buff;
  buff += 2;
 }
}

csum_fold() 校验和取反
      取反操作很简单，~sum

static inline __sum16 csum_fold(__wsum csum)
{
 u32 sum = (__force u32)csum;
 sum = (sum & 0xffff) + (sum >> 16);
 sum = (sum & 0xffff) + (sum >> 16);
 return (__force __sum16)~sum;
}