linux路由实现分析Series---(5)

声明：本文为原创

#####请转贴时保留以下内容######

作者：GTT

本文档归属http://oldtown.cublog.cn/.转载请注明出处!

请提出宝贵意见Mail:[e-mail]

Linux Version：2.6.33

提示：本文是介绍linux 如何实现ipv4路由！

 

现在来看看是怎么创建一条路由项目的。

用户命令和路由守护进程都会添加、删除、修改路由表项的，
这些都是通过内核路由子系统中的一组程序来实现的。
下面看看内核是如何网对这些操作实现的。
fib_table_insert与fib_table_delete被用于添加和删除路由表项，
先主要关注路由表项的追加。

fib_table_insert的source code如下

int fib_table_insert(struct fib_table *tb, struct fib_config *cfg)
{
    struct fn_hash *table = (struct fn_hash *) tb->tb_data;
    struct fib_node *new_f = NULL;
    struct fib_node *f;
    struct fib_alias *fa, *new_fa;
    struct fn_zone *fz;
    struct fib_info *fi;
    u8 tos = cfg->fc_tos;
    __be32 key;
    int err;

    if (cfg->fc_dst_len > 32) return -EINVAL;//判断网络掩码长度
    fz = table->fn_zones[cfg->fc_dst_len];//取得对应网络掩码长度的fn_zone

    if (!fz && !(fz = fn_new_zone(table, cfg->fc_dst_len))) return -ENOBUFS;//fn_zone不存在则创建新的fn_zone

    key = 0;
    if (cfg->fc_dst) {
        if (cfg->fc_dst & ~FZ_MASK(fz)) return -EINVAL;
        key = fz_key(cfg->fc_dst, fz);//根据地址和网络掩码构造搜索key

    }

    fi = fib_create_info(cfg); //创建fib_info
    if (IS_ERR(fi)) return PTR_ERR(fi);

    //判断fn_zone的容量是否需要改变
    if (fz->fz_nent > (fz->fz_divisor<<1) && fz->fz_divisor < FZ_MAX_DIVISOR &&
        (cfg->fc_dst_len == 32 || (1 << cfg->fc_dst_len) > fz->fz_divisor))
        fn_rehash_zone(fz);//改变fn_zone的容量

    f = fib_find_node(fz, key);//根据上面计算的key查找fib_node
    if (!f) fa = NULL;
    else fa = fib_find_alias(&f->fn_alias, tos, fi->fib_priority);//查找fib_alaias

    /* Now fa, if non-NULL, points to the first fib alias
     * with the same keys [prefix,tos,priority], if such key already exists or to the node before which we will insert new one.
     * If fa is NULL, we will need to allocate a new one and insert to the head of f.
     * If f is NULL, no fib node matched the destination key and we need to allocate a new one of those as well.
     */
    //根据tos和fib_priority查找fib_alaias
    if (fa && fa->fa_tos == tos && fa->fa_info->fib_priority == fi->fib_priority) {
        struct fib_alias *fa_first, *fa_match;

        err = -EEXIST;
        if (cfg->fc_nlflags & NLM_F_EXCL) goto out;//此标志代表，如果存在，则什么也不做

        /* We have 2 goals:
         * 1. Find exact match for type, scope, fib_info to avoid duplicate routes
         * 2. Find next 'fa' (or head), NLM_F_APPEND inserts before it
         */
        fa_match = NULL;
        fa_first = fa;
        fa = list_entry(fa->fa_list.prev, struct fib_alias, fa_list);
        list_for_each_entry_continue(fa, &f->fn_alias, fa_list) {
            if (fa->fa_tos != tos) break;
            if (fa->fa_info->fib_priority != fi->fib_priority) break;
            if (fa->fa_type == cfg->fc_type && fa->fa_scope == cfg->fc_scope && fa->fa_info == fi) {
                fa_match = fa;
                break;
            }
        }
        //此标志代表，存在则代替
        if (cfg->fc_nlflags & NLM_F_REPLACE) {
            struct fib_info *fi_drop;
            u8 state;

            fa = fa_first;
            if (fa_match) {
                if (fa == fa_match) err = 0;
                goto out;
            }
            write_lock_bh(&fib_hash_lock);
            fi_drop = fa->fa_info;
            fa->fa_info = fi;
            fa->fa_type = cfg->fc_type;
            fa->fa_scope = cfg->fc_scope;
            state = fa->fa_state;
            fa->fa_state &= ~FA_S_ACCESSED;
            fib_hash_genid++;
            write_unlock_bh(&fib_hash_lock);

            fib_release_info(fi_drop);
            if (state & FA_S_ACCESSED)
                rt_cache_flush(cfg->fc_nlinfo.nl_net, -1);
            rtmsg_fib(RTM_NEWROUTE, key, fa, cfg->fc_dst_len, tb->tb_id,
                  &cfg->fc_nlinfo, NLM_F_REPLACE);
            return 0;
        }

        /* Error if we find a perfect match which uses the same scope, type, and nexthop information. */
        if (fa_match) goto out;
        //不为NLM_F_APPEND时，NLM_F_APPEND此标志代表处理尾部追加
        if (!(cfg->fc_nlflags & NLM_F_APPEND)) fa = fa_first;
    }

    err = -ENOENT;
    if (!(cfg->fc_nlflags & NLM_F_CREATE)) goto out;//此标志代表要创建，下面是关于创建的代码，不创建就退出

    err = -ENOBUFS;
    //如果fib_node不存在，创建并初始化一个新的fib_node实例
    if (!f) {
        new_f = kmem_cache_zalloc(fn_hash_kmem, GFP_KERNEL);
        if (new_f == NULL) goto out;

        INIT_HLIST_NODE(&new_f->fn_hash);
        INIT_LIST_HEAD(&new_f->fn_alias);
        new_f->fn_key = key;
        f = new_f;
    }

    new_fa = &f->fn_embedded_alias;
    if (new_fa->fa_info != NULL) {
        new_fa = kmem_cache_alloc(fn_alias_kmem, GFP_KERNEL);//创建一个新的fib_alias实例
        if (new_fa == NULL) goto out;
    }
    //初始化fib_alias实例
    new_fa->fa_info = fi;
    new_fa->fa_tos = tos;
    new_fa->fa_type = cfg->fc_type;
    new_fa->fa_scope = cfg->fc_scope;
    new_fa->fa_state = 0;

    /* Insert new entry to the list. */
    write_lock_bh(&fib_hash_lock);
    if (new_f) fib_insert_node(fz, new_f); //插入fz_hash表

    list_add_tail(&new_fa->fa_list, (fa ? &fa->fa_list : &f->fn_alias)); //将fib_alias实例链接到其fib_node上

    fib_hash_genid++;//路由表项id增加
    write_unlock_bh(&fib_hash_lock);

    if (new_f) fz->fz_nent++;//路由表项数增加
    rt_cache_flush(cfg->fc_nlinfo.nl_net, -1); //flush路由缓存

    //发送Netlink广播RTM_NEWROUTE
    rtmsg_fib(RTM_NEWROUTE, key, new_fa, cfg->fc_dst_len, tb->tb_id, &cfg->fc_nlinfo, 0);
    return 0;

out:
    if (new_f) kmem_cache_free(fn_hash_kmem, new_f);
    fib_release_info(fi);
    return err;
}

添加一条新的路由表项是通过fib_table_insert方法来实现的，
这个方法实际上被许多操作调用：除了插入新的路由项以外，
还处理appending、changing和replacing。
这些不同的操作是由传入的NLM_F_XXX flags参数来区分的。

flag定义如下

/* Modifiers to NEW request */
#define NLM_F_REPLACE 0x100 /* Override existing */
#define NLM_F_EXCL 0x200    /* Do not touch, if it exists */
#define NLM_F_CREATE 0x400  /* Create, if it does not exist */
#define NLM_F_APPEND 0x800  /* Add to end of list */

不同操作和不同需求使得这个方法的逻辑变得复杂。
例如，TOS值不同的多个路由表项可能有着同一个目的地。当内核添加一条新路由表项
时，如果路由表中已经存在目的地与TOS都相同的路由表项，则函数返回错误。
然而，该条件实际上是替换路由表项的前提条件。
所以，由fib_table_insert方法所进行的路由查找需要根据命令类型返回不同的结果。

插入一条新路由表项可能触发一个zone hash表容量的动态变化，
这是通过fn_rehash_zone方法来实现的。
当路由表项指定一个首选源地址时，新的fib_info结构
被添加到fib_info_devhash hash表内。表示该路由表项下一跳的每一个fib_nh结构也被添加到
fib_info_devhash hash表内。
当一个替换（replace）操作用一条新的路由项来替换一条已存在的路由项时，
内核flush路由缓存表以便不再使用旧的路由项。
无论是哪一种操作类型，都要生成一个Netlink消息来通知感兴趣的子系统。

根据网络掩码长度取得相应的fn_zone。fn_zone不存在则创建新的fn_zone。
根据目标IP地址和网络掩码构造搜索key，然后创建fib_info，
判断fn_zone的容量是否需要改变，需要改变的话，则改变fn_zone的容量。
根据上面计算的key查找fib_node，查找到和没查找到分别处理
    Ⅰ如果查找到fib_node，则根据TOS,fib_priority,继续查找fib_alaias。
       如果fib_alaias存在，则根据netlink传入的参数来分别处理。
        ①NLM_F_EXCL     ：存在则什么也不做
        ②NLM_F_REPLACE：存在则代替
        ③NLM_F_APPEND ：处理尾部追加
        ④NLM_F_CREATE  ：追加
    Ⅱ如果没查找到fib_node，则创建并初始化一个新的fib_node实例

如果fib_alias没查找到创建并初始化一个新的fib_alias实例

fn_zone的容量的变化

//判断fn_zone的容量是否需要改变
    if (fz->fz_nent > (fz->fz_divisor<<1) && fz->fz_divisor < FZ_MAX_DIVISOR &&
        (cfg->fc_dst_len == 32 || (1 << cfg->fc_dst_len) > fz->fz_divisor))
        fn_rehash_zone(fz);

对于33个哈希表，由fn_hash*指针指向的的每一个hash表的容量是独立变化的。
当hash表中元素数量超过hash表的容量的两倍时，改变hash表的容量。
hash表的容量存储在fz_divisor变量中，

当元素数量fz_nent超过一个设置的限定值fz_divisor*2时，将增加hash表的容量fz_hash。
一个hash表的容量可以不断增长直到到达最大上限值FZ_MAX_DIVISOR。
这样的处理方法主要是为了限制对hash表的查找时间。
保持hash表中元素数量低于这个限定值可以使查找加快。
一个hash表的最大容量是跟一page内存大小相关联的。计算方法如下，
#define FZ_MAX_DIVISOR ((PAGE_SIZE<可以看出，如果是i386结构体系中1page为4k,MAX_ORDER等于11，所以得出分配
的容量就是4k<<11，即8MB。struct hlist_head包含一个指针，
所以在32位处理器上FZ_MAX_DIVISOR的值为8MB/4B,即最大可以有2M个hash元素。
2M个什么概念，有2097152个，普通的机器不可能超过的。
当通过fn_new_zone接口第一次创建一个hash表时，该hash表的缺省容量为16。（default route是1）。
在哈希表容量扩展的前两次，容量首先为256，然后是1024。
随后的容量扩展总是在当前容量基础上翻一倍。
hash表的容量目前版本是不能缩小的。