开源算法 | kernelchina

TUBOSS 2014-10-14

展开全文

开源代码学习（open source code learning）

Submitted by kernelchina on Tue, 2012-02-14 13:23

开源算法

本站建立在Linode虚拟主机上http://www./?r=ae1d176c39756bdf939b5110bf19612529216448

开源世界中的算法与数据结构 3 – Linux IPv6 FIB表实现

Submitted by appleleaf on Thu, 2011-12-01 13:24

开源算法

在Linux 2.4 IPv4 FIB的数据结构基础上实现IPv6的FIB是否可行呢？如果读了我前面这篇文字你应该会有一个判断。IPv4的FIB实现可以说有些拙劣，如果照搬一个IPv6版本，最差情况下需要进行128次hash key计算这还不包括链表的查找过程。看了一下Linux 2.6的IPv6 FIB实现，已经有了调整，用了Patrix（Radix）树实现了这个算法，下面是一些背景知识：

首先是Trie树，下图是Wiki http://en./wiki/Trie 之中的一个例子

Trie树，尤其是二叉Trie树属于：是一直被使用，从未被（教科书）重视的东东。其特点是键值的内容成为树的检索路径，例如上图的to，tea等几条键值标明的路径。如果要对trie分类的话，我想只能按照出度来分类，上图假定键值的每一字节取值a-z，则这个trie是26叉trie树，最小出度的Trie树是二叉Trie树，简称BTrie。

所谓PATRICIA Tree或Radix Tree是同一种数据结构，不是标准Trie树，是Trie树的优化变异，Wiki http://en./wiki/Radix_tree上有如下图：

romane和romanus以及romulus有共同前缀rom，此处r是根，om本应为两个节点，现在合并为一个，这个就是Radix树的优化思路，优化之后，可以减少tree的层次，提高匹配速度。而IPv6 FIB就实现为一种二叉 Radix树，其实现结构同这种标准的Radix树还有少许改动，下面简介其实现：

其节点数据结构如下：

struct fib6_node {

struct fib6_node *parent; -- 因为其lookup算法实现要求回溯，所以引入了parent指针，如果按照标准的radix树Wiki实现，则不需要这个节点。

struct fib6_node *left;

struct fib6_node *right;

开源世界中的算法与数据结构 3 – Linux Kernel List 和GList

Submitted by appleleaf on Fri, 2011-11-25 14:14

开源算法

List是工程师的基本功，这里并不描述list增删这些细节的内容，仅仅根据我的理解写一下工程中List库的设计和实践考量。

看过几个不同的list库的实现，基本上涉及到如下的设计考量：

1.List数据结构上的差异

有没有头结点，是否循环，是否双向。这样就有多种组合，不罗嗦。

2.list的读写的保护。

3.List直接指针遍历还是仿照STL的Iterator方式遍历。

4.List同实际用户数据是采取一体式还是干湿分离式。

5.系统对于数据结构和算法的影响

1.从数据结构上将，Linux Kernel之中的List是双向无头节点链表。

空链表如下：

非空链表如下：

我觉得维护头结点的理由之一就是可以存放list size，而无需用户在应用部分进行维护。如果没有list size，用户需要在List删减的结束的时候维护list size，如果不愿意如此麻烦，只能悲催的在需要读取链表长度的时候for 循环并“++”一遍。实际上glist库提供get length之类的函数就是遍历list“++”

guint
g_list_length (GList *list)
{
guint length;
length = 0;
while (list)
    {
      length++;
      list = list->next;
    }
return length;
}

开源世界中的算法与数据结构 2 – Linux Skbuff实现

Submitted by appleleaf on Mon, 2011-11-21 16:31

开源算法

兼回忆贴，大概在03年开始接触Linux的协议栈代码，那个时候还找不到什么参考书，有些东西自己搞明白了但是也从来没想过在那个论坛发个帖子什么的，也没有现在的记录总结的习惯. 后来有一本08年版的《TCP/IP Architecture, Design and Implementation in Linux》其中解析了Linux2.4 协议栈的多数代码，其中第五章专门涉及skbuff的代码实现讲解，非常详细，这个小短文不翻译整个章节，各种网文很多，只是想根据关键部分说一下我理解的设计背后的原因。

skbuff的形态1

上面是最基本的一个sk_buff了，一个TCP报文的skbuff示意图，这里隐含着一些内容：

报文分析的标准模式

skbuff采用的大块控制结构对象指向数据区是标准的实现模式，例如BSD这样的OS以及工程实现中都是这样的。

参数的集中

与其提供多个对象或者多个参数保存报文信息，不如将其集中起来存放，即便于功能扩展时保持接口稳定性，又减少了接口参数，更加容易理解和记忆。的时候仅仅是因为缩减参数长度这一简单理由，我们就搞一个XXContext的数据结构，收容各种变量，而不顾内聚耦合之类的编程标准。

skb_shared_info是个什么东东，为什么放在了数据报文的尾部？

代码中的注解是，这个部分数据是各个skbuff之间共享的。这个结构其实是控制结构，但是为什么放在数据区呢？我的理解是，因为其在多个克隆的skbuff之间共享，如果放在控制区则会造成克隆后的skbuff之中数据冗余。

skbuff的形态2 - 带有Paged Data的skbuff

上图可见除了标准数据区的报文内容外，skb_shared_info会有多个frag部分指向离散存储的Page数据。所有Page数据和标准数据区的数据的总和是报文内容。我并未遇到过这种情况，根据【1】中的描述，在使用Scatter-gather DMA技术的时候可以利用Paged Data。http://bbs./BLOG_ARTICLE_73287.HTM之中描述了Scatter-gather DMA技术。因为“连续的存储器地址在物理上不一定是连续的，所以DMA传输要分成多次完成。”，采用Scatter-gather技术的优点是，通过DMA传送多块离散数据之后产生一次中断，这样减少了中断次数。