Linux路由表(转)

Linux 路由表的结构如下：

  fib_table是路由表的数据结构：

 struct  {
          struct  tb_hlist;
                       tb_id;
          unsigned         tb_stamp;
          int              (*tb_lookup)(struct  *tb, const struct  *flp, struct  *);
          int              (*tb_insert)(struct  *, struct  *);
          int              (*tb_delete)(struct  *, struct  *);
          int              (*tb_dump)(struct  *, struct  *skb,
                                       struct  *);
          int              (*tb_flush)(struct  *);
          void             (*tb_select_default)(struct  *,
                                               const struct  *flp, struct  *);
 
          unsigned char    tb_data[0];
 };

在这个数据结构中有tb_data[0]这个空数组，它实际上是一个指针，在初始化的时候：
struct * ( )
         (tb->tb_data, 0, sizeof(struct ));

被指向结构fn_hash，而fn_hash的定义是：
 struct  {
          struct    *fn_zones[33];
          struct    *fn_zone_list;
 };

这就是32＋1位掩码，每个对应一个fn_zone的结构。

fn_zone的定义是：
 struct  {
          struct            *fz_next;       /* Next not empty zone   */
          struct         *fz_hash;       /* Hash table pointer    */
          int                      fz_nent;        /* Number of entries     */
 
          int                      fz_divisor;     /* Hash divisor          */
                               fz_hashmask;    /* (fz_divisor - 1)      */
 #define (fz)          ((fz)->fz_hashmask)
 
          int                      fz_order;       /* Zone order            */
                            fz_mask;
 #define (fz)              ((fz)->fz_mask)
 };

它的各个成员含义是：
struct fn_zone *fz_next ：连接到下一个活动的zone(至少有一条路由的zone叫做活动zone),链表的头指向fn_hash的fn_zone_list。
struct hlist_head *fz_hash：指向本zone内的路由条目，是一个hash表。
int fz_nent：本zone内部的路由条目数量
int fz_divisor：路由hash表的大小，这个大小是可变的，缺省是16。
u32 fz_hashmask：这是一个为效率而存在的成员，值是fz_advisor-1，目的是用低开销的AND操作取代高开销的取模操作。
int fz_order：掩码位长度
u32 fz_mask：掩码位

有两个宏被定义以简化操作：
#define FZ_HASHMASK(fz) ((fz)->fz_hashmask) 
#define FZ_MASK(fz) ((fz)->fz_mask)

fn_zone里的fz_hash是一个哈希表指针，哈希表由fib_node数组组成，通过fz_hash指针引用。
在用hlist_head时，定义的是*fz_hash而不是fz_hash，这就是一个链表头数组，而不单纯是一个链表。 在这里，我们看到fz_hash按照divisor的值大小初始化：
static struct *(int )
{
          unsigned long = * sizeof(struct );

          if ( <= ) {
                  return (, );
          } else {
                  return (struct *)
                         (, ());
          }
}

这里是哈希函数：
static inline ( , struct *fz)
{
          = ()>>(32 - fz->fz_order);
          ^= (>>20);
          ^= (>>10);
          ^= (>>5);
          &= (fz);
          return ;
}

路由查找的时候，通过对键值k的哈希，得出哈希值指向对应的链表。
                  = &fz->fz_hash[(k, fz)];
                 (, , , ) {
                          if (->fn_key != k)
                                  continue;

                          = (&->fn_alias,
                                                   flp, ,
                                                  ->fn_key, fz->fz_mask,
                                                   fz->fz_order);
                          if ( <= 0)
                                  goto ;
                  }
  

而这里的f就是fib_node,也就是这个链表的元素，定义如下： struct {
          struct        ;
          struct          fn_alias;
                            fn_key;
};fn_key就是路由前缀，fn_alias定义如下：
struct {
          struct          fa_list;
          struct rcu_head rcu;
          struct           *fa_info;
                                fa_tos;
                                fa_type;
                                fa_scope;
                                fa_state;

};

fn_alias 用以区分到达同一目标的不同路由，区分依据是目标地址以外的配置参数：

struct list_head fa_list

链表项。

struct fib_info *fa_info

指向fib_info，fib_info说明了如果匹配，如何进行处理。

u8 fa_tos：TOS位

u8 fa_type：RTN_LOCAL, RTN_UNICAST或者RTN_BORADCAST

u8 fa_scope：RT_SCOPE_HOST(本地)，RT_SCOPE_LINK(远程)

u8 fa_state：如下

FA_S_ACCESSED：如果路由使用，就标记，用于cache操作。

 fib_info的结构定义为：
 struct  {
          struct         fib_hash;
          struct         fib_lhash;
          int                      fib_treeref;
                          fib_clntref;
          int                      fib_dead;
          unsigned                 fib_flags;
          int                      fib_protocol;
                            fib_prefsrc;
                               fib_priority;
                               fib_metrics[];
 #define  fib_metrics[-1]
 #define  fib_metrics[-1]
 #define  fib_metrics[-1]
 #define  fib_metrics[-1]
          int                      fib_nhs;
 #ifdef CONFIG_IP_ROUTE_MULTIPATH
          int                      fib_power;
 #endif
 #ifdef CONFIG_IP_ROUTE_MULTIPATH_CACHED
                               fib_mp_alg;
 #endif
          struct            [0];
 #define fib_dev         [0].nh_dev
 };

fib_info存储着重要的路由信息，条目如下：

struct hlist_node fib_hash

struct hlist_node fib_lhash

这两条将fib_info纳入两个全局性的哈希表，后一个是源路由用的。

int fib_treeref atomic_t fib_clntref

存储成功的路由查询次数。

int fib_dead

删除路由时使用，标志路由不可用。

…

Fib中还有还有fib_nh更具体地指出路由下一跳信息，可参见