网络子系统29_桥接转发数据库

转：http://blog.csdn.net/nerdx/article/details/12223547

//  转发数据库
//      1.容量
//          net_bridge->hash[BR_HASH_SIZE]，其中BR_HASH_SIZE为(1<<8)，有256个bucket
//      2.老化机制，
//          2.1 gc函数，到期时会顺序遍历age_list上的转发项，修改gc函数下一次到期时间为age_list中第一个没有过期的转发项的剩余时间。
//          2.2 age_list链表，保存除本机l2地址以外的所有转发项，按照到期时间进行排序，新添加或更新的转发项保存在age_list尾部。


//  网桥转发数据库初始化
//  调用路径：br_init->br_fdb_init
1.1 void __init br_fdb_init(void)
{
    //创建转发项的SLAB cache
    br_fdb_cache = kmem_cache_create("bridge_fdb_cache",
                     sizeof(struct net_bridge_fdb_entry),
                     0,
                     SLAB_HWCACHE_ALIGN, NULL, NULL);
}


//  查询转发项
//      __br_fdb_xxx不会递增net_bridge_fdb_entry的引用计数，br_fdb_xxx会递增net_bridge_fdb_entry的引用计数
//  参数：
//      addr，目的l2地址
//  函数主要任务：
//      hash l2地址到正确的bucket，遍历bucket查找具有相同l2地址的转发项
2.1 struct net_bridge_fdb_entry *__br_fdb_get(struct net_bridge *br,
                      const unsigned char *addr)
{
    struct hlist_node *h;
    struct net_bridge_fdb_entry *fdb;
    //net_bridge->hash为转发数据库的hash表
    hlist_for_each_entry_rcu(fdb, h, &br->hash[br_mac_hash(addr)], hlist) {//遍历对应的bucket的链表
        if (!memcmp(fdb->addr.addr, addr, ETH_ALEN)) {//比较转发项的地址与查询的地址
            if (unlikely(has_expired(br, fdb)))
                break;
            return fdb;//找到返回转发项
        }
    }

    return NULL;//否则返回null
}

//  添加转发项
//      转发数据库由hash_lock保护
2.2 int br_fdb_insert(struct net_bridge *br, struct net_bridge_port *source,
          const unsigned char *addr, int is_local)
{
    int ret;

    spin_lock_bh(&br->hash_lock);//获取hash表的锁，关下半部中断
    ret = fdb_insert(br, source, addr, is_local);//
    spin_unlock_bh(&br->hash_lock);
    return ret;
}
//  调用路径：br_fdb_insert->fdb_insert
//  函数主要任务：
//      1.遍历对应的bucket
//      2.如果对应的转发项已经存在
//          2.1 转发项为本机地址，添加的地址为本机地址，返回
//          2.2 转发项非本机，添加的地址为本机，更新已有的转发项
//          2.3 转发项非本机，添加的地址非本机
//              2.3.1 如果转发项静态配置，则不更新已有转发项
//              2.3.2 否则从age_list上删除转发项，更新已有转发项
//      3.转发项不存在，分配新的转发项，更新转发项，添加到hash表

//  对已有选项的更新：
//      1.设置转发项是否为本机
//      2.本机转发项设置为static
//      3.非本机转发项添加到age_list上
2.3 static int fdb_insert(struct net_bridge *br, struct net_bridge_port *source,
          const unsigned char *addr, int is_local)
{
    struct hlist_node *h;
    struct net_bridge_fdb_entry *fdb;
    int hash = br_mac_hash(addr);

    if (!is_valid_ether_addr(addr))//非全0，非广播或多播地址
        return -EADDRNOTAVAIL;

    hlist_for_each_entry(fdb, h, &br->hash[hash], hlist) {//遍历对应的bucket
        if (!memcmp(fdb->addr.addr, addr, ETH_ALEN)) {//已存在l2地址对应的转发项
            if (fdb->is_local) {//转发项为本机地址
                if (is_local) //要添加的本机地址已经存在，直接返回
                    return 0;

                return -EEXIST;//返回错误
            }

            if (is_local) {//转发项非本机地址，将此转发项修改为本机地址
                printk(KERN_WARNING "%s adding interface with same address "
                       "as a received packet\n",
                       source->dev->name);
                goto update;
            }

            if (fdb->is_static)//转发项静态配置
                return 0;

            list_del(&fdb->u.age_list);//将fdb从br->age_list链表上删除
            goto update;
        }
    }

    fdb = kmem_cache_alloc(br_fdb_cache, GFP_ATOMIC);//分配新的转发项
    if (!fdb)
        return ENOMEM;

    memcpy(fdb->addr.addr, addr, ETH_ALEN);//复制l2地址
    atomic_set(&fdb->use_count, 1);
    hlist_add_head_rcu(&fdb->hlist, &br->hash[hash]);//添加到对应的bucket

    if (!timer_pending(&br->gc_timer)) {
        br->gc_timer.expires = jiffies + hold_time(br);
        add_timer(&br->gc_timer);//启动垃圾回收定时器
    }

 update:
    fdb->dst = source;//到达此l2地址的端口
    fdb->is_local = is_local;//指示是否为本机地址
    fdb->is_static = is_local;//本机地址为静态配置地址
    fdb->ageing_timer = jiffies;//最近一次被使用的时间
    if (!is_local)
        list_add_tail(&fdb->u.age_list, &br->age_list);//对于非本机地址的转发项，添加到br->age_list链表，执行垃圾回收机制

    return 0;
}

//  垃圾回收定时器
//      除本机地址外的所有转发项，链接在lru链表中，遍历链表，直到最后一个没有过期的转发项。
//  转发项到期时间：
//      1.正常情况下，300HZ
//      2.拓扑发生变化时，short aging机制，过期时间为15HZ

//  函数主要任务：
//      1.遍历age_list，释放过期的转发项
//      2.修改gc下一次到期时间为最近到期的邻居项的到期时间。
2.5 void br_fdb_cleanup(unsigned long _data)
{
    struct net_bridge *br = (struct net_bridge *)_data;
    struct list_head *l, *n;
    unsigned long delay;
    //在获取转发数据库的锁之后进行清理操作
    spin_lock_bh(&br->hash_lock);
    //1.当拓扑发生改变时，启动short aging机制，过期时间为15HZ，转发数据库中的项很快过期
    //2.在正常情况下，过期时间为300HZ
    delay = hold_time(br);

    list_for_each_safe(l, n, &br->age_list) {//安全方式遍历age_list
        struct net_bridge_fdb_entry *f;
        unsigned long expires;

        f = list_entry(l, struct net_bridge_fdb_entry, u.age_list);
        expires = f->ageing_timer + delay;//转发项的到期时间

        if (time_before_eq(expires, jiffies)) {//如果转发项到期
            WARN_ON(f->is_static);
            pr_debug("expire age %lu jiffies %lu\n",
                 f->ageing_timer, jiffies);
            fdb_delete(f);
        } else {
            mod_timer(&br->gc_timer, expires);//第一个没有过期的转发项，之后的所有转发项都不会过期，则调整gc_timer的下一次运行时间，返回
            break;
        }
    }
    spin_unlock_bh(&br->hash_lock);
}

//  调用路径br_fdb_cleanup->fdb_delete
2.6 static __inline__ void fdb_delete(struct net_bridge_fdb_entry *f)
{
    hlist_del_rcu(&f->hlist);//从hash表上删除此转发项
    if (!f->is_static)//is_static=1，说明为本机地址，本机地址不会出现在age_list上
        list_del(&f->u.age_list);//从age_list上删除此转发项

    br_fdb_put(f);//递减引用计数，为0时，直接释放
}