Php文档 Php问答行业资讯 Php论坛 Php手册 Php博客

游戏榜单

软件榜单

关闭导航

热搜榜

热门下载

热门标签

关闭搜索

php爱好者> php文档>(zz)Linux-网桥原理分析（三）

(zz)Linux-网桥原理分析（三）

时间：2010-11-14 来源：yinguochun1234

5网桥数据结构

网桥最主要有三个数据结构：struct net_bridge，struct net_bridge_port，struct net_bridge_fdb_entry，他们之间的关系如下图：

展开来如下图：

说明：

1. 其中最左边的net_device是一个代表网桥的虚拟设备结构，它关联了一个net_bridge结构，这是网桥设备所特有的数据结构。

2. 在net_bridge结构中，port_list成员下挂一个链表，链表中的每一个节点（net_bridge_port结构）关联到一个真实的网口设备的net_device。网口设备也通过其br_port指针做反向的关联（那么显然，一个网口最多只能同时被绑定到一个网桥）。

3. net_bridge结构中还维护了一个hash表，是用来处理地址学习的。当网桥准备转发一个报文时，以报文的目的Mac地址为key，如果可以在 hash表中索引到一个net_bridge_fdb_entry结构，通过这个结构能找到一个网口设备的net_device，于是报文就应该从这个网口转发出去；否则，报文将从所有网口转发。

各个结构体具体内容如下：

struct net_bridge

struct net_bridge
{
    spinlock_t            lock; //读写锁

    //网桥所有端口的链表,其中每个元素都是一个net_bridge_port结构

    struct list_head        port_list;
    struct net_device        *dev; //网桥对应的设备

    struct net_device_stats        statistics; //网桥对应的虚拟网卡的统计数据

    spinlock_t            hash_lock; //hash表的锁

    /*--CAM: 保存forwarding database的一个hash链表(这个也就是地址学习的东东,
    所以通过hash能快速定位),这里每个元素都是一个net_bridge_fsb_entry结构--*/
    struct hlist_head        hash[BR_HASH_SIZE];
    struct list_head        age_list;

    /* STP */ //与stp 协议对应的数据

    bridge_id            designated_root;
    bridge_id            bridge_id;
    u32                root_path_cost;
    unsigned long            max_age;
    unsigned long            hello_time;
    unsigned long            forward_delay;
    unsigned long            bridge_max_age;
    unsigned long            ageing_time;
    unsigned long            bridge_hello_time;
    unsigned long            bridge_forward_delay;

    u16                root_port;
    unsigned char            stp_enabled;
    unsigned char            topology_change;
    unsigned char            topology_change_detected;
    //stp要用的一些定时器列表。

    struct timer_list        hello_timer;
    struct timer_list        tcn_timer;
    struct timer_list        topology_change_timer;
    struct timer_list        gc_timer;
    struct kobject            ifobj;
}

2. struct net_bridge_port

struct net_bridge_port
{
    struct net_bridge        *br; //从属于的网桥设备

    struct net_device        *dev;//表示链接到这个端口的物理设备

    struct list_head        list;

    /* STP */ //stp相关的一些参数。

    u8                priority;
    u8                state;
    u16                port_no; //本端口在网桥中的编号

    unsigned char            topology_change_ack;
    unsigned char            config_pending;
    port_id                port_id;
    port_id                designated_port;
    bridge_id            designated_root;
    bridge_id            designated_bridge;
    u32                path_cost;
    u32                designated_cost;
    //端口定时器，也就是stp控制超时的一些定时器列表

    struct timer_list        forward_delay_timer;
    struct timer_list        hold_timer;
    struct timer_list        message_age_timer;
    struct kobject            kobj;
    struct rcu_head            rcu;
}

3. struct net_bridge_fdb_entry

struct net_bridge_fdb_entry
{
    struct hlist_node        hlist;
    //桥的端口(最主要的两个域就是这个域和下面的mac地址域)

    struct net_bridge_port *dst;

    struct rcu_head            rcu; //当使用RCU策略，才用到


    atomic_t                use_count; //引用计数

    unsigned long            ageing_timer; //MAC超时时间

    mac_addr                addr; //mac地址。


    unsigned char            is_local; //是否为本机的MAC地址

    unsigned char            is_static; //是否为静态MAC地址

}

6 网桥数据库的维护

这里所说的网桥数据库指的是CAM表，即struct net_bridge结构中的hash表，数据库的维护对应的是对结构struct net_bridge_fdb_entry的操作；

众所周知，网桥需要维护一个MAC地址-端口映射表，端口是指网桥自身提供的端口，而MAC地址是指与端口相连的另一端的MAC地址。当网桥收到一个报文时，先获取它的源MAC，更新数据库，然后读取该报文的目标MAC地址，查找该数据库，如果找到，根据找到条目的端口进行转发；否则会把数据包向除入口端口以外的所有端口转发。

6.1 数据库的创建和销毁

数据库使用kmem_cache_create函数进行创建，使用kmem_cache_desctory进行销毁。路径：[/net/bridge/br_fdb.c]:

void __init br_fdb_init(void)
{
    br_fdb_cache = kmem_cache_create("bridge_fdb_cache",
                     sizeof(struct net_bridge_fdb_entry),
                     0,
                     SLAB_HWCACHE_ALIGN, NULL, NULL);
}

6.2 数据库更新

当网桥收到一个数据包时，它会获取该数据的源MAC地址，然后对数据库进行更新。如果该MAC地址不在数库中，则创新一个数据项。如果存在，更新它的年龄。数据库使用hash表的结构方式，便于高效查询。下面是hash功能代码的分析：

路径：[/net/bridge/br_fdb.c]

void br_fdb_update(struct net_bridge *br, struct net_bridge_port *source,
         const unsigned char *addr)
{
    /*--br_mac_hash函数是hash表中的hash函数，具体算法过程可参阅该函数代码;
        br->hash就是数据库的hash表，每个hash值对应一个链表;
        数据库的每项为net_bridge_fdb_entry结构--*/
    struct hlist_head *head = &br->hash[br_mac_hash(addr)];
    struct net_bridge_fdb_entry *fdb;

    /* some users want to always flood. */
    if (hold_time(br) == 0)
        return;

    rcu_read_lock();
    fdb = fdb_find(head, addr);
    /*--如果找到对应的fdb，更新fdb->dst，fdb->ageing_timer--*/
    if (likely(fdb)) {
        /* attempt to update an entry for a local interface */
        if (unlikely(fdb->is_local)) {
            if (net_ratelimit())
                printk(KERN_WARNING "%s: received packet with "
                 " own address as source address\n",
                 source->dev->name);
        } else {
            /* fastpath: update of existing entry */
            fdb->dst = source;
            fdb->ageing_timer = jiffies;
        }
    } else { /*--没有找到，则新建一个fdb--*/
        spin_lock_bh(&br->hash_lock);
        if (!fdb_find(head, addr))
            fdb_create(head, source, addr, 0);
        /* else we lose race and someone else inserts
         * it first, don't bother updating
         */
        spin_unlock_bh(&br->hash_lock);
    }
    rcu_read_unlock();
}

6.3 创建数据项

在更新函数里面已为某一MAC找到了它所属于的Hash链表，因此，创建函数只需要在该链上添加一个数据项即可。

static struct net_bridge_fdb_entry *fdb_create(struct hlist_head *head,
                     struct net_bridge_port *source,
                     const unsigned char *addr,
                     int is_local)
{
    struct net_bridge_fdb_entry *fdb;

    /*--申请数据区--*/
    fdb = kmem_cache_alloc(br_fdb_cache, GFP_ATOMIC);
    if (fdb) {
        memcpy(fdb->addr.addr, addr, ETH_ALEN);
        atomic_set(&fdb->use_count, 1);
        hlist_add_head_rcu(&fdb->hlist, head); /*--添加到链表--*/

        fdb->dst = source;
        fdb->is_local = is_local;
        fdb->is_static = is_local;
        fdb->ageing_timer = jiffies; //MAC年龄

    }
    return fdb;
}

6.4 查找数据项

查找分两种：一种是数据项更新时候的查找，另一种是转发报文时候查找，两者区别是转发时查找需要判断MAC地址是否过期，即我们常说的MAC老化；更新时则不用判断；

网桥更新一MAC地址时，不管该地址是否已经过期了，只需遍历该MAC地址对应的Hash链表，然后更新年龄，此时它肯定不过期了。

网桥要转发数据时，除了要找到该目标MAC的出口端口外，还要判断该记录是否过期了。

更新时查找：

static inline struct net_bridge_fdb_entry *fdb_find(struct hlist_head *head,
                         const unsigned char *addr)
{
    struct hlist_node *h;
    struct net_bridge_fdb_entry *fdb;

    /*--遍历链表比较地址--*/
    hlist_for_each_entry_rcu(fdb, h, head, hlist) {
        if (!compare_ether_addr(fdb->addr.addr, addr))
            return fdb;
    }
    return NULL;
}

转发时查找：

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;

    /*--遍历链表比较地址--*/
    hlist_for_each_entry_rcu(fdb, h, &br->hash[br_mac_hash(addr)], hlist) {
        if (!compare_ether_addr(fdb->addr.addr, addr)) {
            /*--判断是否过期--*/
            if (unlikely(has_expired(br, fdb)))
                break;
            return fdb;
        }
    }

    return NULL;
}

比较一下，转发时多了一个函数处理：has_expired, Has_expired函数来决定该数据项是否是过期的，代码如下：

/*--数据项的可保留时间根据拓扑结构是否改变来决定，
    改变则为forward_delay，否则为ageing_time--*/
/* if topology_changing then use forward_delay (default 15 sec)
* otherwise keep longer (default 5 minutes)
*/
static __inline__ unsigned long hold_time(const struct net_bridge *br)
{
    return br->topology_change ? br->forward_delay : br->ageing_time;
}

static __inline__ int has_expired(const struct net_bridge *br,
                 const struct net_bridge_fdb_entry *fdb)
{
    /*--1. 如果该数据项是静态的，即不是学习过来的，它永远不会过期。
         因为它就是网桥自己端口的地址
        2. 如果最近更新时间加上可保留时间大于当前时间，即老化时间还在以后，
         表示尚未过期，time_before_eq返回真，否则返回假
    --*/
    return !fdb->is_static
        && time_before_eq(fdb->ageing_timer + hold_time(br), jiffies);
}

6.5 MAC地址过期清理

桥建立时设置一个定时器，循环检测，如果发现有过期的MAC，则清除对应的数据项，MAC地址过期清除由函数br_fdb_cleanup实现：

/*--定时器循环检查MAC地址是否过期
    定时器在桥初始化中定义开启--*/
void br_fdb_cleanup(unsigned long _data)
{
    struct net_bridge *br = (struct net_bridge *)_data;
    unsigned long delay = hold_time(br);/*--获取MAC地址可保留时间--*/
    int i;

    spin_lock_bh(&br->hash_lock);
    for (i = 0; i < BR_HASH_SIZE; i++) {
        struct net_bridge_fdb_entry *f;
        struct hlist_node *h, *n;

        /*--如果该地址不是静态的，并且已经过期，则从数据库中清除该MAC映射--*/
        hlist_for_each_entry_safe(f, h, n, &br->hash[i], hlist) {
            if (!f->is_static &&
             time_before_eq(f->ageing_timer + delay, jiffies))
                fdb_delete(f);
        }
    }
    spin_unlock_bh(&br->hash_lock);

    /*--更新检查定时器--*/
    mod_timer(&br->gc_timer, jiffies + HZ/10);
}