Linux 网桥实现分析

第一部份 源码框架
一、网桥原理
传统的中继器，如HUB，是一个单纯的物理层设备，它将每一个收到的数据包，在其所有的端口上广播，由接收主机来判断这个数据包是否是给自己的。这样，网络资源被极大的浪费掉了。
网桥之所以不同于中继器，主要在于其除了有中继的作用外，还有一个更重要的作用，就是学习MAC地址，然后根据每个数据包的目的MAC与自身端口的对应，从关联端口发送数据，而不完全地在整个网段中进行广播。所以，网桥的实现中，有两个关键点：
1、学习MAC地址，起初，网桥是没有任何地址与端口的对应关系的，它发送数据，还是得想HUB一样，但是每发送一个数据，它都会关心数据包的来源MAC是从自己的哪个端口来的，由于学习，建立地址-端口的对照表（CAM表）。
2、每发送一个数据包，网桥都会提取其目的MAC地址，从自己的地址-端口对照表(CAM表)中查找由哪个端口把数据包发送出去。

二、Linux网桥源码的实现
1、调用
在src/net/core/dev.c的软中断函数static void net_rx_action(struct softirq_action *h)中（line 1479）
#if defined(CONFIG_BRIDGE) || defined(CONFIG_BRIDGE_MODULE)
                        if (skb->dev->br_port != NULL &&
                            br_handle_frame_hook != NULL) {
                                handle_bridge(skb, pt_prev);
                                dev_put(rx_dev);
                                continue;
                        }
#endif
如果定义了网桥或网桥模块，则由handle_bridge函数处理skb->dev->br_port ：接收该数据包的端口是网桥端口组的一员，如果接收当前数据包的接口不是网桥的某一物理端口，则其值为NULL；
br_handle_frame_hook ：定义了网桥处理函数这段代码将数据包进行转向，转向的后的处理函数是钩子函数br_handle_frame_hook，在此之前，handle_bridge函数还要处理一些其它的事情：
static __inline__ int handle_bridge(struct sk_buff *skb,
                                     struct packet_type *pt_prev)
{
        int ret = NET_RX_DROP;
        if (pt_prev) {
                if (!pt_prev->data)
                        ret = deliver_to_old_ones(pt_prev, skb, 0);
                else {
                        atomic_inc(&skb->users);
                        ret = pt_prev->func(skb, skb->dev, pt_prev);
                }
        }
        br_handle_frame_hook(skb);
        return ret;
}
pt_prev用于在共享SKB的时候提高效率,handle_bridge函数最后将控制权交由到了br_handle_frame_hook的手上。

2、钩子函数的注册
br_handle_frame_hook用于网桥的处理，在网桥的初始化函数中（net/bridge/br.c）：
static int __init br_init(void)
{
        printk(KERN_INFO "NET4: Ethernet Bridge 008 for NET4.0/n");
        br_handle_frame_hook = br_handle_frame;
        br_ioctl_hook = br_ioctl_deviceless_stub;
#if defined(CONFIG_ATM_LANE) || defined(CONFIG_ATM_LANE_MODULE)
        br_fdb_get_hook = br_fdb_get;
        br_fdb_put_hook = br_fdb_put;
#endif
        register_netdevice_notifier(&br_device_notifier);
        return 0;
}
初始化函数中指明了钩子函数实际上指向的是br_hanlde_frame

3、br_handle_frame(br_input.c)
/*网桥处理函数*/
void br_handle_frame(struct sk_buff *skb)
{
        struct net_bridge *br;
        unsigned char *dest;
        struct net_bridge_port *p;
        /*获取目的MAC地址*/
        dest = skb->mac.ethernet->h_dest;
        /*skb->dev->br_port用于指定接收该数据包的端口，若不是属于网桥的端口，则为NULL*/
        p = skb->dev->br_port;
        if (p == NULL)                /*端口不是网桥组端口中*/
                goto err_nolock;
        /*本端口所属的网桥组*/
        br = p->br;       
        /*加锁，因为在转发中需要读CAM表，所以必须加读锁，避免在这个过程中另外的内核控制路径(如多处理机上另外一个CPU上的系统调用)修改CAM表*/
        read_lock(&br->lock);
        if (skb->dev->br_port == NULL)                /*前面判断过的*/
                goto err;       
        /*br->dev是网桥的虚拟网卡，如果它未UP，或网桥DISABLED,p->state实际上是桥的当前端口的STP计算判断后的状态*/
        if (!(br->dev.flags & IFF_UP) ||
            p->state == BR_STATE_DISABLED)
                goto err;       
        /*源MAC地址为255.X.X.X，即源MAC是多播或广播，丢弃之*/
        if (skb->mac.ethernet->h_source[0] & 1)
                goto err;
        /*众所周之，网桥之所以是网桥，比HUB更智能，是因为它有一个MAC-PORT的表，这样转发数据就不用广播，而查表定端口就可以了
        每次收到一个包，网桥都会学习其来源MAC，添加进这个表。Linux中这个表叫CAM表(这个名字是其它资料上看的)。
        如果桥的状态是LEARNING或FORWARDING(学习或转发)，则学习该包的源地址skb->mac.ethernet->h_source，
        将其添加到CAM表中，如果已经存在于表中了，则更新定时器，br_fdb_insert完成了这一过程*/
        if (p->state == BR_STATE_LEARNING ||
            p->state == BR_STATE_FORWARDING)
                br_fdb_insert(br, p, skb->mac.ethernet->h_source, 0);       
        /*
* STP协议的BPDU包的目的MAC采用的是多播目标MAC地址：
* 01-80-c2-00-00-00（Bridge_group_addr：网桥组多播地址），这里先判断网桥是否
* 开启了STP（由用户层来控制，如brctl），如果开启了，则比较目的地址前5位
* 是否与多播目标MAC地址相同：
* (!memcmp(dest, bridge_ula, 5)
* 如果相同，如果地址第6位非空
* !(dest[5] & 0xF0))
* 那么这确定是一个STP的BPDU包，则跳转到handle_special_frame，将处理权
* 将给函数br_stp_handle_bpdu
       */
        if (br->stp_enabled &&
            !memcmp(dest, bridge_ula, 5) &&
            !(dest[5] & 0xF0))
goto handle_special_frame;
       
        /*处理钩子函数，然后转交br_handle_frame_finish函数继续处理*/
        if (p->state == BR_STATE_FORWARDING) {
                NF_HOOK(PF_BRIDGE, NF_BR_PRE_ROUTING, skb, skb->dev, NULL,
                        br_handle_frame_finish);
                read_unlock(&br->lock);
                return;
        }
err:
        read_unlock(&br->lock);
err_nolock:
        kfree_skb(skb);
        return;
handle_special_frame:
        if (!dest[5]) {
                br_stp_handle_bpdu(skb);
                return;
        }
        kfree_skb(skb);
}
可见，这个函数中有三个重要的地方：
1、地址学习：br_fdb_insert
2、STP的处理：br_stp_handle_bpdu
3、br_handle_frame_finish，我们还没有查CAM表，转发数据呢……
我们先来看网桥的进一步处理br_handle_frame_finish，地址学习等内容，后面再来分析。

4、br_handle_frame_finish
        static int br_handle_frame_finish(struct sk_buff *skb)
{
        struct net_bridge *br;
        unsigned char *dest;
        struct net_bridge_fdb_entry *dst;
        struct net_bridge_port *p;
        int passedup;

        /*前面基本相同*/
        dest = skb->mac.ethernet->h_dest;
        p = skb->dev->br_port;
        if (p == NULL)
                goto err_nolock;
        br = p->br;
        read_lock(&br->lock);
        if (skb->dev->br_port == NULL)
                goto err;
        passedup = 0;       
        /*
* 如果网桥的虚拟网卡处于混杂模式，那么每个接收到的数据包都需要克隆一份
* 送到AF_PACKET协议处理体(网络软中断函数net_rx_action中ptype_all链的
* 处理)。
*/
        if (br->dev.flags & IFF_PROMISC) {
                struct sk_buff *skb2;

                skb2 = skb_clone(skb, GFP_ATOMIC);
                if (skb2 != NULL) {
                        passedup = 1;
                        br_pass_frame_up(br, skb2);
                }
        }
/*
* 目的MAC为广播或多播，则需要向本机的上层协议栈传送这个数据包，这里
* 有一个标志变量passedup，用于表示是否传送过了，如果已传送过，那就算了
*/
        if (dest[0] & 1) {
                br_flood_forward(br, skb, !passedup);
                if (!passedup)
                        br_pass_frame_up(br, skb);
                goto out;
        }
/*
* 用户层常常需要用到一个虚拟的地址来管理网桥，如果目的地址非常，且为本
* 地址地址，则交由上层函数处理
*/
        if (dst != NULL && dst->is_local) {
                if (!passedup)
                        br_pass_frame_up(br, skb);
                else
                        kfree_skb(skb);
                br_fdb_put(dst);
                goto out;
        }       
        /*查询CAM表，如果查到表了，转发之*/
        if (dst != NULL) {
                br_forward(dst->dst, skb);
                br_fdb_put(dst);
                goto out;
        }
        /*如果表里边查不到，那么只好学习学习HUB了……*/
        br_flood_forward(br, skb, 0);
out:
        read_unlock(&br->lock);
        return 0;
err:
        read_unlock(&br->lock);
err_nolock:
        kfree_skb(skb);
        return 0;
}

在这个函数中，涉及到两个重要方面：
1、查表：br_forward
2、网桥数据转发：br_fdb_put。
另外，网桥的处理中，还涉及到内核中一些重要的数据结构：
对Linux上所有接口进行网桥划分，可以把一组端口划分到一个网桥之中，同时一个系统上允许有多个网桥。内核描述一个网桥，使用了struct net_bridge结构：
struct net_bridge
{
        struct net_bridge                *next;                        //下一个网桥
        rwlock_t                        lock;                        //读写锁
        struct net_bridge_port                *port_list;                //桥组中的端口列表
       
/*网桥都会有一个虚拟设备用来进行管理，就是它了。说到这里，我想到了以前一个没有解决的问题：对网桥管理IP配置后，发现其虚拟的MAC地址是动态生成的，取的是桥组中某一个物理端口的MAC地址（好像是第一个），这样，如果远程管理时就有麻烦：如果你动态调整网桥中的端口，如删除某个网卡出去，用于管理的虚拟网卡的地址就有可以改变，导致不能远程管理，盼指点如何解决此问题呢？也许看完整个代码就会也答案……*/
        struct net_device                dev;                       
        struct net_device_stats                statistics;                //网桥虚拟网卡的统计数据
        rwlock_t                        hash_lock;                //hash表的读写锁，这个表就是用于存放桥的MAC-PORT对应表
        struct net_bridge_fdb_entry        *hash[BR_HASH_SIZE];        //就是这张表了，也叫CAM表
        struct timer_list                tick;
        /*以下定义了STP协议所使用的信息，参见STP协议的相关定义*/
        bridge_id                        designated_root;
        int                                root_path_cost;
        int                                root_port;
        int                                max_age;
        int                                hello_time;
        int                                forward_delay;
        bridge_id                        bridge_id;
        int                                bridge_max_age;
        int                                bridge_hello_time;
        int                                bridge_forward_delay;
        unsigned                        stp_enabled:1;
        unsigned                        topology_change:1;
        unsigned                        topology_change_detected:1;
        struct br_timer                        hello_timer;
        struct br_timer                        tcn_timer;
        struct br_timer                        topology_change_timer;
        struct br_timer                        gc_timer;
        int                                ageing_time;
        int                                gc_interval;
};
可以看出，桥中有几个重要的地方：
1、桥的端口成员：struct net_bridge_port   *port_list;
2、桥的CAM表：struct net_bridge_fdb_entry *hash[BR_HASH_SIZE];
3、桥的虚拟网卡
4、STP
桥的虚拟网卡是一个struct net_device设备，它在2.4中是如此庞大，要对它在这里进行分析无疑是非常困难的，改天大家一起讨论吧。
STP的相关成员的定义与STP包的结构是紧密相关的，看了其包结构，可以分析出这些成员了，不再一一列举了。
网桥中的端口，用struct net_bridge结构表示，它实际上表示的是接收该数据包的网桥的端口的相关信息：
struct net_bridge_port
{
        struct net_bridge_port                *next;                //网桥端口组中的下一个端口
        struct net_bridge                *br;                //当前端口（接收数据包这个）所在的桥组
        struct net_device                *dev;                //本端口所指向的物理网卡
        int                                port_no;        //本端口在网桥中的编号
        port_id                                port_id;       
        int                                state;
        int                                path_cost;
        bridge_id                        designated_root;
        int                                designated_cost;
        bridge_id                        designated_bridge;
        port_id                                designated_port;
        unsigned                        topology_change_ack:1;
        unsigned                        config_pending:1;
        int                                priority;
        struct br_timer                        forward_delay_timer;
        struct br_timer                        hold_timer;
        struct br_timer                        message_age_timer;
};
这个结构对应了内核缓存中的skb->dev->br_port;
整个网桥的源码框架就这样了，学习，查表，进行STP处理，数据传送。

第二部份，CAM表的学习与查找
前一章说过，CAM表的学习，是通过br_fdb_insert函数，而查找，则是调用了br_forward函数

1、CAM表的结构
每一个地址-端口对应的项称为fdb项，内核中使用链表来组织fdb，它是一个struct net_bridge_fdb_entry
类型：

#define BR_HASH_BITS 8
#define BR_HASH_SIZE (1 << BR_HASH_BITS)

struct net_bridge_fdb_entry
{
        struct net_bridge_fdb_entry        *next_hash;          //用于CAM表连接的链表指针
        struct net_bridge_fdb_entry        **pprev_hash;        //为什么是pprev不是prev呢？还没有仔细去研究
        atomic_t                        use_count;              //此项当前的引用计数器
        mac_addr                        addr;                   //MAC地址
        struct net_bridge_port                *dst;             //此项所对应的物理端口
        unsigned long                        ageing_timer;      //处理MAC超时
        unsigned                        is_local:1;             //是否是本机的MAC地址
        unsigned                        is_static:1;             //是否是静态MAC地址
};

内核中，整个CAM表是用br->hash[hash_value]这个数组来存储的，其中hash_value是根据源MAC地址进行hash运算得出的一个值，
这样，br->hash[hash]就指向了此源MAC地址对应的fdb项所在的链表的首部。这样说可能有点复杂，可用下图来表示：
br->hash[hash_0]->fdb1->fdb2->fdb3……
br->hash[hash_1]->fdb1->fdb2->fdb3……
br->hash[hash_2]->fdb1->fdb2->fdb3……
br->hash[hash_3]->fdb1->fdb2->fdb3……
……
其中的hash_0、hash_1……是通过对源MAC地址进行hash运算求出的。so easy……

2、br_fdb_insert
/*
* Function:br_fdb_insert
* Purpose：网桥CAM表的学习，查询新收到的源MAC-端口在原来表中是否有变化，以便更新CAM表
* Arguments：
*         struct net_bridge *br=>当前网桥
*        struct net_bridge_port *source=>源端口
*        unsigned char *addr=>源地址
*        int is_local=>是否为本地
* Return:
*        void
*/
void br_fdb_insert(struct net_bridge *br,
                   struct net_bridge_port *source,
                   unsigned char *addr,
                   int is_local)
{
        struct net_bridge_fdb_entry *fdb;
        int hash;

        /*
         * CAM表是一个数组，每个数组元素又是一个链表，这里根据源地址，求对应的hash值，也就是当前源地址在表中的对应的编号id，
         * 这样，就可以通过br->hash[id]来访问该地址对应的fdb项的链表了。
        */
        hash = br_mac_hash(addr);

        write_lock_bh(&br->hash_lock);                /*加锁*/
        fdb = br->hash[hash];                        /*取得当前源地址对应的fdb项链表*/
        
        /*如果链表不为空，则遍历该链表，找到地址匹配的项，然后替换它*/
        while (fdb != NULL) {
                if (!fdb->is_local &&
                    !memcmp(fdb->addr.addr, addr, ETH_ALEN)) {
                        __fdb_possibly_replace(fdb, source, is_local);
                        write_unlock_bh(&br->hash_lock);
                        return;
                }

                fdb = fdb->next_hash;
        }

        /*如果链表为空，则为新的fdb项分配空间，构建fdb项，然后构建hash 链表*/
        fdb = kmalloc(sizeof(*fdb), GFP_ATOMIC);
        if (fdb == NULL) {
                write_unlock_bh(&br->hash_lock);
                return;
        }

        memcpy(fdb->addr.addr, addr, ETH_ALEN);
        atomic_set(&fdb->use_count, 1);
        fdb->dst = source;
        fdb->is_local = is_local;
        fdb->is_static = is_local;
        fdb->ageing_timer = jiffies;

        /*因为本项源地址对应的hash值已计算出来了，则直接将本项给当前桥br*/
        __hash_link(br, fdb, hash);

        write_unlock_bh(&br->hash_lock);                /*解锁*/
}

这个函数中涉及到三个重要函数：
1、br_mac_hask：计算地址对应的hash值；
2、__fdb_possibly_replace：替换fdb项；
3、__hash_link：将当前项fdb插入hash表中；

A、br_mac_hask

函数用于计算地址对应的hash值。
将MAC地址逐字节左移两位，然后与下一字节值求异或，完成之后，再将高8位和低8位再异或，最后使用return x & (BR_HASH_SIZE - 1);将hash值限定在指定范围之内。
static __inline__ int br_mac_hash(unsigned char *mac)
{
        unsigned long x;

        x = mac[0];
        x = (x << 2) ^ mac[1];
        x = (x << 2) ^ mac[2];
        x = (x << 2) ^ mac[3];
        x = (x << 2) ^ mac[4];
        x = (x << 2) ^ mac[5];

        x ^= x >> 8;

        /*
         * #define BR_HASH_BITS 8
         * #define BR_HASH_SIZE (1 << BR_HASH_BITS)
         */
        return x & (BR_HASH_SIZE - 1);
}

B、__fdb_possibly_replace
因为在链表的循环查找中，发现当前源地址已在表项中存在，所以，需要更新它，这是一个单纯的替换操作：

static __inline__ void __fdb_possibly_replace(struct net_bridge_fdb_entry *fdb,
                                              struct net_bridge_port *source,
                                              int is_local)
{
        if (!fdb->is_static || is_local) {
                fdb->dst = source;                        /*更新当前地址所对应的端口*/
                fdb->is_local = is_local;
                fdb->is_static = is_local;
                fdb->ageing_timer = jiffies;
        }
}

C、__hash_link

函数将待插入项ent插入到hash值对应的桥的br->hash[hash]的链表的第一个项

static __inline__ void __hash_link(struct net_bridge *br,
                                   struct net_bridge_fdb_entry *ent,
                                   int hash)
{
        /*让ent->next指向链表首部，这样后边br->hash[hash]=ent，于是链首指针就指向ent了*/
        ent->next_hash = br->hash[hash];
        if (ent->next_hash != NULL)
                ent->next_hash->pprev_hash = &ent->next_hash;                /*回指上一个元素*/
        br->hash[hash] = ent;
        ent->pprev_hash = &br->hash[hash];                /*ent->pprev回指链首指针*/
}

3、br_forward
/*
* Function:br_fdb_insert
* Purpose：网桥CAM表的查找，查找待发送数据包目的MAC地址对应的fdb 表项
* Arguments：
*         struct net_bridge *br=>当前网桥
*        unsigned char *addr=>待查找地址
* Return:
*        net_bridge_fdb_entry *=>查找到的fdb项，未查到则为NULL
*/
struct net_bridge_fdb_entry *br_fdb_get(struct net_bridge *br, unsigned char *addr)
{
        struct net_bridge_fdb_entry *fdb;

        read_lock_bh(&br->hash_lock);                /*加锁*/
        fdb = br->hash[br_mac_hash(addr)];        /*计算地址对应的hash值*/
        
        /*遍历链表，查找与地址相匹配的fdb项*/
        while (fdb != NULL) {
                if (!memcmp(fdb->addr.addr, addr, ETH_ALEN)) {
                        if (!has_expired(br, fdb)) {
                                atomic_inc(&fdb->use_count);
                                read_unlock_bh(&br->hash_lock);
                                return fdb;
                        }

                        read_unlock_bh(&br->hash_lock);
                        return NULL;
                }

                fdb = fdb->next_hash;
        }

        read_unlock_bh(&br->hash_lock);                /*解锁*/
        return NULL;
}

这样，网桥中最重要的学习/查表的全过程就这样了，如果没有STP，那么全过程就是这样，当然，如果网桥
打开了STP开关，则网桥需要进行STP的相关处理，STP的处理，是网桥中的一个重要部份，将在下一章进行分析。 

第三部份，STP的实现分析初步

一、STP的框架结构
STP发送的是BPDU包，该包有所有两种类型：配置和TCN（拓朴变更通知）；
对于BPDU包的处理，有两种：接收和发送（废话），
对于配置类型的BPDU包的发送，它是靠定时器来完成的，参BPDU包的几个定时器参数；
对于TCP类型的BPDU包的发送，从名字可以看出来，它是当发现拓朴结构发生变更时发送的，如本机网桥配置的变化，物理接口的变动，分析其它机器变动后发出来的STP包等等。

BPDU的封包采用的是IEEE802封包（本想把封包结构的图片贴上来，找不着在哪儿上传图片）。

前面分析过， br_handle_frame函数中，当网桥开启了STP，且根据目的物理地址判断出这是一个STP包，则交给br_stp_handle_bpdu函数处理。
br_stp_handle_bpdu函数主要是判断是哪种类型的BPDU包，然后调用相关的处理函数，即：
if(type==config)
{
    br_received_config_bpdu();
}
else if(type==tcn)
{
    br_received_tcn_bpdu();
}

这是对接收到BPDU包的处理，关于config类型的BPDU包的发送，后面再分析；TCN包的发送，有一部份是在接收包处理过程中处理的（因为分析config类型的BPDU包的时候，发现拓朴变更，当然要发送TCN包了），所以这里一起来分析。

二、Config类型的BPDU包的接收处理
这个处理过程是在拆完BPDU包后，调用br_received_config_bpdu函数完成的。
还是得先交待一些理论的东西：

STP协议最终是为了在网络中生成一棵无环状的树，以期消除广播风暴以及单播数据帧对网络的影响。它始终在选举三样东东：
1、根网桥；
2、根端口；
3、“指定端口”和“指定网桥”

（这三个概念非常重要，如果你还不清楚，建议查阅相关文档先，否则下边的代码分析也无从谈起了）
然后再根据选举出来的这三个东东，确定端口的状态：阻塞、转发、学习、监听、禁用……
要选举出这三样东东，得有一个判断标志，即算法，STP的判断标准是：
1、判断根桥ID，以最小的为优；
2、判断到根桥的最小路径开销；
3、确定最小发送发BID（Sender BID）
4、确定最小的端口ID

如果前面你查阅了BPDU的封包结构，根桥ID、最小路径开销、发送方网桥的ID、端口ID这几个概念应该没有问题了，不过这里还是简单交一下：
1、根桥ID，我们配置了网桥后，用brctl命令会发现8000.XXXXXX这样一串，这就是网桥的ID号，用一标识每一个网桥，后面的XXXX一般的桥的MAC地址，这样ID值就不会重复。根桥ID，是指网络中所有网桥的ID值最小的那一个，对应的具有根桥ID的桥，当然也是网络的根桥了；

2、最小路径开销
动态路由中也类似这个概念，不过这里用的不是跳数（局域网不比广域网，不一定跳数大就慢，比如跳数小，是10M链路，跳数大的却是千兆链路），最初的开销定义为1000M/链种带宽，当然，这种方式不适用于万兆网了……所以后来又有一个新的，对每一种链路定义一个常数值——详请请查阅相关资料；

3、发送方ID
网桥之前要收敛出一个无环状拓朴，就需要互相发送BPDU包，当然需要把自己的ID告诉对方，这样对方好拿来互相比较；

4、端口ID
端口ID由优先级+端口编号组成，用于标识某个桥的某个端口，后面比较时好用。

生成树算法就是利用上述四个参数在判断，判断过程总是相同的：
1、确定根桥，桥ID最小的（即把包中的桥ID，同自己以前记录的那个最小的桥ID相比，机器加电时，总是以自己的桥ID为根桥ID）的为根桥；

2、确定最小路径开销；

3、确定最小发送方ID；

4、确定最小的端口ID：

这四步非常地重要，后面的所以比较都是这四个步骤。

有了这些概念，来看看对config类型的BPDU包的处理：

void br_received_config_bpdu(struct net_bridge_port *p, struct br_config_bpdu *bpdu)
{
        struct net_bridge *br;
        int was_root;

        if (p->state == BR_STATE_DISABLED)
                return;

        br = p->br;
        read_lock(&br->lock);

        /*自己是根桥吗？用自己的br_ID和BPDU包中的根ID相比较*/
        was_root = br_is_root_bridge(br);
        
        /*比桥BPDU包中的信息(bpdu)和原先的对应的信息(p)，如果需要更新，返回1，相同返回0，不需更新返回-1*/
        if (br_supersedes_port_info(p, bpdu)) {
                /*刷新自己的相关信息*/
                br_record_config_information(p, bpdu);
                /*进行root_bridge、port的选举*/
                br_configuration_update(br);
                /*设置端口状态*/
                br_port_state_selection(br);

以上这一段的逻辑概念很简单：
1、把收到的BPDU包中的参数同自己原先记录的相比较，（遵循前面说的四个比较步骤），以判断是否需要进行更新——br_supersedes_port_info(p, bpdu)。
2、如果判断需要进行更新，即上述四个步骤中，有任意一项有变动，则刷新自己的保存记录：br_record_config_information(p, bpdu);
3、因为有变动，就需要改变自己的配置了：br_configuration_update(br);即前面说的，根据四步判断后选举根桥（注：根桥不是在这里选举的，前文说过，它是定时器定时发送BPDU包，然后收到的机器只需改变自己的记录即可）、根端口、指定端口；
4、设置物理端口的转发状态：br_port_state_selection


2.1 br_supersedes_port_info(p, bpdu)


/* called under bridge lock */
static int br_supersedes_port_info(struct net_bridge_port *p, struct br_config_bpdu *bpdu)
{
        int t;
/*第一步*/
        t = memcmp(&bpdu->root, &p->designated_root, ;
        if (t < 0)
                return 1;
        else if (t > 0)
                return 0;
/*第二步*/
        if (bpdu->root_path_cost < p->designated_cost)
                return 1;
        else if (bpdu->root_path_cost > p->designated_cost)
                return 0;
/*第三步，要同两个桥ID比：已记录的最小发送ID和自己的ID*/
        t = memcmp(&bpdu->bridge_id, &p->designated_bridge, ;
        if (t < 0)
                return 1;
        else if (t > 0)
                return 0;

        if (memcmp(&bpdu->bridge_id, &p->br->bridge_id, )
                return 1;
/*第四步*/
        if (bpdu->port_id <= p->designated_port)
                return 1;

        return 0;
}

2.2 br_record_config_information
如果检测到有变动，则刷新自己的记录先：
/* called under bridge lock */
static void br_record_config_information(struct net_bridge_port *p, struct br_config_bpdu *bpdu)
{
        p->designated_root = bpdu->root;
        p->designated_cost = bpdu->root_path_cost;
        p->designated_bridge = bpdu->bridge_id;
        p->designated_port = bpdu->port_id;
/*设置时间戳，关于STP的时间处理，后面来分析*/
        br_timer_set(&p->message_age_timer, jiffies - bpdu->message_age);
}

p对应的四个成员的概念对照BPDU封包结构，不难理解其含义：
        p->designated_root：                指定的根网桥的网桥ID
        p->designated_cost ：                指定的到根桥的链路花销
        p->designated_bridge：                指定的发送当前BPDU包的网桥的ID
        p->designated_port：                指定的发送当前BPDU包的网桥的端口的ID

2。3 br_configuration_update前面说过，根桥的选举不是在这里进行，这里进行根端口和指定端口的选举
/* called under bridge lock */
void br_configuration_update(struct net_bridge *br)
{
        
                br_root_selection(br);/*选举根端口*/
        br_designated_port_selection(br);/*选举指定端口*/
}

2.3.1 根端口的选举br_root_selection根端口的选举同样是以上四个步骤，只是有一点小技巧：它逐个遍历桥的每一个所属端口，找出一个符合条件的，保存下来，再用下一个来与之做比较，用变量root_port 来标志：
/* called under bridge lock */
static void br_root_selection(struct net_bridge *br)
{
        struct net_bridge_port *p;
        int root_port;

        root_port = 0;
/*获得桥的所属端口列表*/
        p = br->port_list;
/*这个循环非常重要，它遍历桥的每一个端口，进行以上四步判断，找到一个，将其“保存”下来，然后再用下一个与保存的相比较，直至遍历完，找到最优的那个，这个“保存”打了引号，是因为它仅仅是记当了端口编号：root_port = p->port_no;，然后再将其传递给比较函数br_should_become_root_port*/
        while (p != NULL) {
                if (br_should_become_root_port(p, root_port))
                        root_port = p->port_no;

                p = p->next;
        }

        br->root_port = root_port;
/*找完了还没有找到，则认为自己就是根桥……*/
        if (!root_port) {
                br->designated_root = br->bridge_id;
                br->root_path_cost = 0;
        }
/*否则记录相应的值*/
               else {
                p = br_get_port(br, root_port);
                br->designated_root = p->designated_root;
                br->root_path_cost = p->designated_cost + p->path_cost;
        }
}

br_should_become_root_port函数用以判断端口p是否应该变成根端口，与它相比较的是原来那个根端口，函数第二个参数则为此的ID号，在函数中调用 br_get_port获取该端口：

/* called under bridge lock */
static int br_should_become_root_port(struct net_bridge_port *p, int root_port)
{
        struct net_bridge *br;
        struct net_bridge_port *rp;
        int t;

        br = p->br;
/*若当前端口是关闭状态或为一个指定端口，则不参与选举，返回*/
        if (p->state == BR_STATE_DISABLED ||
            br_is_designated_port(p))
                return 0;
/*在根端口的选举中，根桥是没有选举权的*/
        if (memcmp(&br->bridge_id, &p->designated_root,  <= 0)
                return 0;

/*没有指定等比较的端口ID（因为第一次它初始化为0的）*/
        if (!root_port)
                return 1;

/*获取待比较的根端口*/
        rp = br_get_port(br, root_port);

/*又是四大步，像打蓝球*/
        t = memcmp(&p->designated_root, &rp->designated_root, ;
        if (t < 0)
                return 1;
        else if (t > 0)
                return 0;

        if (p->designated_cost + p->path_cost <
            rp->designated_cost + rp->path_cost)
                return 1;
        else if (p->designated_cost + p->path_cost >
                 rp->designated_cost + rp->path_cost)
                return 0;

        t = memcmp(&p->designated_bridge, &rp->designated_bridge, ;
        if (t < 0)
                return 1;
        else if (t > 0)
                return 0;

        if (p->designated_port < rp->designated_port)
                return 1;
        else if (p->designated_port > rp->designated_port)
                return 0;

        if (p->port_id < rp->port_id)
                return 1;

        return 0;
}

这样，遍历完成后，根端口就被选出来了。

2。3。2 指定端口的选举br_designated_port_selection
/* called under bridge lock */
static void br_designated_port_selection(struct net_bridge *br)
{
        struct net_bridge_port *p;

        p = br->port_list;
        while (p != NULL) {
                if (p->state != BR_STATE_DISABLED &&
                    br_should_become_designated_port(p))
                        br_become_designated_port(p);

                p = p->next;
        }
}
事实上这个过程与根端口的选举过程极为类似，没有分析的必要了！

2。3。3 端口状态选择
/* called under bridge lock */
void br_port_state_selection(struct net_bridge *br)
{
        struct net_bridge_port *p;

        p = br->port_list;
        while (p != NULL) {
                if (p->state != BR_STATE_DISABLED) {
                        if (p->port_no == br->root_port) {
                                p->config_pending = 0;
                                p->topology_change_ack = 0;
                                br_make_forwarding(p);
                        } else if (br_is_designated_port(p)) {
                                br_timer_clear(&p->message_age_timer);
                                br_make_forwarding(p);
                        } else {
                                p->config_pending = 0;
                                p->topology_change_ack = 0;
                                br_make_blocking(p);
                        }
                }

                p = p->next;
        }
}

函数的逻辑结构也很简单：
遍历整个桥所属端口：
while (p != NULL)
如果端口已经DISABLED，则没有判断的必要了：
p->state != BR_STATE_DISABLED

如果端口是根端口，或者是指定端口，就让让它forwarding，否则就让它blocking：

                        if (p->port_no == br->root_port) {
                                p->config_pending = 0;
                                p->topology_change_ack = 0;
                                br_make_forwarding(p);
                        } else if (br_is_designated_port(p)) {
                                br_timer_clear(&p->message_age_timer);
                                br_make_forwarding(p);
                        } else {
                                p->config_pending = 0;
                                p->topology_change_ack = 0;
                                br_make_blocking(p);
                        }

/* called under bridge lock */
static void br_make_forwarding(struct net_bridge_port *p)
{
        if (p->state == BR_STATE_BLOCKING) {
                printk(KERN_INFO "%s: port %i(%s) entering %s state/n",
                       p->br->dev.name, p->port_no, p->dev->name, "listening");

                p->state = BR_STATE_LISTENING;
                br_timer_set(&p->forward_delay_timer, jiffies);
        }
}

/* called under bridge lock */
static void br_make_blocking(struct net_bridge_port *p)
{
        if (p->state != BR_STATE_DISABLED &&
            p->state != BR_STATE_BLOCKING) {
                if (p->state == BR_STATE_FORWARDING ||
                    p->state == BR_STATE_LEARNING)
                        br_topology_change_detection(p->br);

                printk(KERN_INFO "%s: port %i(%s) entering %s state/n",
                       p->br->dev.name, p->port_no, p->dev->name, "blocking");

                p->state = BR_STATE_BLOCKING;
                br_timer_clear(&p->forward_delay_timer);
        }
}

都是设置p->state 相应状态位就可以了！！

三、选举完成之后
实在不会取名字了，前面分析了br_received_config_bpdu中前面的判断、刷新、选举、设置端口状态的过程，然而，如果桥认为当前这个BPDU是一个“最优的”（即符合前面判断四步中的某一步），所作的动作不止于此：
1、如果因为这个BPDU导致拓朴变化了，如自己以前是根桥，现在不是了，需要发送TCN包，进行通告；
2、需要把这个BPDU包继续转发下去（如果自己收到数据的端口是根端口的话，那么就有可能有许多交换机（网桥）串在自己的指定端口下边，总得把这个包能过指定端口再发给它们吧，否则交换机就不叫交换机了）

指下来继续看代码：
/*前面说的第1步*/
                     if (!br_is_root_bridge(br) && was_root) {
                        br_timer_clear(&br->hello_timer);
                        if (br->topology_change_detected) {
                                br_timer_clear(&br->topology_change_timer);
                                br_transmit_tcn(br);
                                br_timer_set(&br->tcn_timer, jiffies);
                        }
                }
/*前面说的第2步*/
                if (p->port_no == br->root_port) {
                        br_record_config_timeout_values(br, bpdu);
                        br_config_bpdu_generation(br);
                        if (bpdu->topology_change_ack)
                                br_topology_change_acknowledged(br);
                }

tcn包的发送，呆会单独来分析，先来看br_config_bpdu_generation函数，这个函数也很简单：遍历桥的所有端口，如果是指定端口，就发送一个config 类型的BPDU包：
/* called under bridge lock */
void br_config_bpdu_generation(struct net_bridge *br)
{
        struct net_bridge_port *p;

        p = br->port_list;
        while (p != NULL) {
                if (p->state != BR_STATE_DISABLED &&
                    br_is_designated_port(p))
                        br_transmit_config(p);

                p = p->next;
        }
}
然后就是层层函数调用，组包，最终是调用dev_queue_xmit函数发送出去的。

如果收到这个BPDU包，不是“最优”的，而接收数据包的接口不是根端口，直接将转发出去就可以了，起个中继的作用：
else if (br_is_designated_port(p))
{               
                br_reply(p);               
}
br_reply同样调用了br_transmit_config函数