注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

还东国的博客

行之苟有恒,久久自芬芳

 
 
 

日志

 
 

TCP/IP驱动十三 ——内核中的路由1  

2013-08-28 23:12:15|  分类: TCPIP驱动 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

TCP/IP驱动十三  ——内核中的路由1

fib_table中最后是一个零长度的数组,这个的作用大家可以参考“LINUX编程”中“linux内核中platform框架中的一个小技巧”和“结构体最后的长度为01数组的作用”中的两篇博文。下面是其它代码:

Include\net\ip_fib.c

struct fib_table {

         struct hlist_node tb_hlist;

         u32            tb_id;

         unsigned  tb_stamp;

         int              tb_default;

         int              (*tb_lookup)(struct fib_table *tb, const struct flowi *flp, struct fib_result *res);

         int              (*tb_insert)(struct fib_table *, struct fib_config *);

         int              (*tb_delete)(struct fib_table *, struct fib_config *);

         int              (*tb_dump)(struct fib_table *table, struct sk_buff *skb,

                                          struct netlink_callback *cb);

         int              (*tb_flush)(struct fib_table *table);

         void           (*tb_select_default)(struct fib_table *table,

                                                    const struct flowi *flp, struct fib_result *res);

 

         unsigned char         tb_data[0];

};

net\ipv4\fib_hash.c

struct fib_table *fib_hash_table(u32 id)

{

         struct fib_table *tb;

 

         tb = kmalloc(sizeof(struct fib_table) + sizeof(struct fn_hash),

                        GFP_KERNEL);

         if (tb == NULL)

                   return NULL;

 

         tb->tb_id = id;

         tb->tb_default = -1;

         tb->tb_lookup = fn_hash_lookup;

         tb->tb_insert = fn_hash_insert;

         tb->tb_delete = fn_hash_delete;

         tb->tb_flush = fn_hash_flush;

         tb->tb_select_default = fn_hash_select_default;

         tb->tb_dump = fn_hash_dump;

         memset(tb->tb_data, 0, sizeof(struct fn_hash));

         return tb;

}

大家可以看到在分配tb指针的空间时,将fn_hash这个数据结构体的空间也一起分配了。跳过去看看:

路由区结构定义:

struct fn_zone {

         struct fn_zone          *fz_next; /* Next not empty zone  */

         struct hlist_head     *fz_hash;          /* Hash table pointer       */

         int                       fz_nent;   /* Number of entries       */包含的路由节总数

 

         int                       fz_divisor;         /* Hash divisor                   */哈希桶数量

         u32                     fz_hashmask;  /* (fz_divisor - 1)      */确定哈希桶的掩码

#define FZ_HASHMASK(fz)                ((fz)->fz_hashmask)

 

         int                       fz_order; /* Zone order            */子网掩码位数

         __be32                       fz_mask;   子网掩码

#define FZ_MASK(fz)                 ((fz)->fz_mask)

};

 

/* NOTE. On fast computers evaluation of fz_hashmask and fz_mask

 * can be cheaper than memory lookup, so that FZ_* macros are used.

 */

路由区队列结构定义:

struct fn_hash {

         struct fn_zone *fn_zones[33];//路由区表或称路由区队列

         struct fn_zone *fn_zone_list;//指向第一个路由区表

};

这里fn_hash中的第一个变量,代表着子网掩码所能指代的33套路由区,也就是比如10.1.1.0/24(放入第25套路由区),在内核的代码中:

static struct fn_zone *

fn_new_zone(struct fn_hash *table, int z)

{

         int i;

         struct fn_zone *fz = kzalloc(sizeof(struct fn_zone), GFP_KERNEL);

         if (!fz)

                   return NULL;

 

         if (z) {

                   fz->fz_divisor = 16;

         } else {

                   fz->fz_divisor = 1;

         }

         fz->fz_hashmask = (fz->fz_divisor - 1);

         fz->fz_hash = fz_hash_alloc(fz->fz_divisor);

         if (!fz->fz_hash) {

                   kfree(fz);

                   return NULL;

         }

         fz->fz_order = z;

         fz->fz_mask = inet_make_mask(z);

 

         /* Find the first not empty zone with more specific mask */

         for (i=z+1; i<=32; i++)

                   if (table->fn_zones[i])

                            break;

         write_lock_bh(&fib_hash_lock);

         if (i>32) {

                   /* No more specific masks, we are the first. */

                  fz->fz_next = table->fn_zone_list;

                   table->fn_zone_list = fz;

         } else {

                  fz->fz_next = table->fn_zones[i]->fz_next;

                   table->fn_zones[i]->fz_next = fz;

         }

         table->fn_zones[z] = fz;

         fib_hash_genid++;

         write_unlock_bh(&fib_hash_lock);

         return fz;

}

这个链表的组成是逆向的,即掩码的长度是从长到短。http://blog.csdn.net/qy532846454/article/details/6423496

在上面的

for (i=z+1; i<=32; i++)

                   if (table->fn_zones[i])

                            break;

明显可以看到第一次创建的时候所有的fn_zones[0~32]均为空,所以第一个创建的肯定是33,然后反向依次创建。

如果大于32容易看出是一个链表,如果小于32,也就是else中的部分(红色部分)可以这样分析:

假设:初始从Z=1开始(0也一样)

28  fn_zones[0]

29  fn_zones[1]

30 fn_zones[2]

31  fn_zones[3]

32  fn_zones[4]

 

32~28简写成f32~f28, 新创建的fn_zonef,表头fn_zone_lista,结合红色代码,看插入过程,那么根据(for (i=z+1; i<=32; i++)),又是逆向:

TCP/IP驱动十三  ——内核中的路由1 - 还东国 - 还东国的博客
 TCP/IP驱动十三  ——内核中的路由1 - 还东国 - 还东国的博客
 

这样就如网上的资料所言,创建了一个以fn_zone_list为头的链表队列。这也算是一种小技巧吧,每次在这个上面都耽误时间。

下一篇再讲fn_zonefz_hash哈希桶。

今天算是前进了一小点点。

  评论这张
 
阅读(633)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017