stp_process.c

来自「stp代码」· C语言 代码 · 共 1,383 行 · 第 1/3 页

/***********************************************************************
* Copyright (C) 2005,UNE Corporation.
* 
* File Name: stp_process.c
* File Mark: Core protocol for spanning tree, this supports
             IEEE Multiple Spanning Tree 802.1s, i.e. Per VLAN based 
             STP(PVST)
* Description:  
* Others: 
 * Note:
 *     1. Although the spanning tree software supports multiple
 *        spanning tree, on early StrataSwitch based systems
 *        (BCM5600, BCM5680) which do not have spanning tree group
 *        table, only one instance of STP can be ran.  Later
 *        generations of chip (Starta II, XGS) supports up to
 *        256 instances of spanning tree.
 *     2. Multiple instances of Spanning Tree all share one thread.
 *        which are started when the first instance of STP is started,
 *        and teared down when the last instance of STP exits.
 *     3. Only supports IEEE 802.1D spanning tree, doesn't support
 *        IBM or DEC spanning tree.
* Version: V1.0
* Author: 
* Date: 
* History 1:
*     Date: 
* 	  Version:
*     Author: 
*     Modification:  
* History 2: …
**********************************************************************/

#include <vxWorks.h>
#include <sysLib.h>
#include <taskLib.h>


#include <sys/types.h>
#include <soc/mem.h>
#include <soc/drv.h>
#include <soc/types.h>
#include <soc/util.h>
#include <soc/debug.h>

#include <bcm/error.h>
#include <bcm/pmux.h>
#include <bcm/port.h>
#include <bcm/stg.h>
#include <bcm/packet.h>
#include <bcm/l2.h>
#include <bcm/mirror.h>
#include <bcm/stack.h>

#include <sal/user/sal.h>
#include <sal/user/io.h>
#include <sal/user/config.h>
#include <sal/kern/libc.h>

#include <sys/types.h>

#include <stp/stp.h>
#include <stp/stp_api.h>
#include <soc/debug.h>
#include <soc/drv.h>
#include <bcm/types.h>
/*
 * Linked list of Span Tree instances
 */
spantree_t *stp_instance_q = NULL;

/*
 * STP thread related
 */
static int stp_exit = 0;
static sal_thread_t stp_thread_id = NULL;
static int stp_exit_all = 0;
/*
 * Function declarations
 */
static Boolean root_bridge(spantree_t *stp);
static void    start_hold_timer(spantree_t *stp, stp_port_t *port);
static void    stop_hold_timer(spantree_t *stp, stp_port_t *port);
static Boolean hold_timer_expired(spantree_t *stp, stp_port_t *port);
static void    start_message_age_timer(spantree_t *stp, stp_port_t *p, uint16 msg_age);
static void    stop_message_age_timer(spantree_t *stp, stp_port_t *port);
static Boolean message_age_timer_expired(spantree_t *stp, stp_port_t *port);
static Boolean is_designated_port(spantree_t *stp, stp_port_t *port);
static void    root_selection(spantree_t *stp);
static void    designated_port_selection(spantree_t *stp);
static Boolean designated_for_some_port(spantree_t *stp);
static void    become_designated_port(spantree_t *stp, stp_port_t *port);
static void    make_forwarding(spantree_t *stp, stp_port_t *port);
static void    make_blocking(spantree_t *stp, stp_port_t *port);
static void    set_port_state(spantree_t *stp, stp_port_t *p, stp_portstate_t state);
static void    start_forward_delay_timer(spantree_t *stp, stp_port_t *port);
static void    stop_forward_delay_timer(spantree_t *stp, stp_port_t *port);
static Boolean forward_delay_timer_expired(spantree_t *stp, stp_port_t *port);
static void    topology_change_detection(spantree_t *stp);
static void    start_tc_timer(spantree_t *stp);
static void    stop_tc_timer(spantree_t *stp);
static Boolean tc_timer_expired(spantree_t *stp);
static void    start_tcn_timer(spantree_t *stp);
static void    stop_tcn_timer(spantree_t *stp);
static Boolean tcn_timer_expired(spantree_t *stp);
static void    start_hello_timer(spantree_t *stp);
static void    stop_hello_timer(spantree_t *stp);
static Boolean hello_timer_expired(spantree_t *stp);
static void stp_make_all_active_port_forwarding(void);

extern void stp_send_config_bpdu(spantree_t *stp, stp_port_t *pt, Config_bpdu *bpdu);
extern void stp_send_tcn_bpdu(spantree_t *stp,stp_port_t *pt, Tcn_bpdu * bpdu);
extern void stp_port_state_set(spantree_t *stp,stp_port_t *pt, stp_portstate_t st);
extern int  get_global_port(int unit,int lcport);
extern int  bcm_port_link_status_get(int unit,bcm_port_t port, int *up);
extern int  bcm_stg_stp_set(int unit,bcm_stg_t stg,bcm_port_t port, int stp_state);
extern void stk_pakq_release(void);
extern void stp_shutdown( void );
extern void stp_close_mstp_flag_valued(void);

/*
 * compare to bridge IDs
 */
static int
stp_cmpid(uint8 *id1, uint8 *id2, int size)
{
    return (sal_memcmp(id1, id2, size));
}

/*
 * Send a HELLO on the specified port (8.6)
 */
static void
transmit_config(spantree_t *stp, stp_port_t *port)
{
    if (port->hold_timer.active) { /* (8.6.1.3.1) */
        port->config_pending = True; /* (8.6.1.3.1) */
    } else { /* (8.6.1.3.2) */
        port->config_bpdu.type = BPDU_TYPE_CONFIG;
       sal_memcpy(port->config_bpdu.root_id, stp->designated_root, ID_BYTES);
        port->config_bpdu.root_path_cost = stp->root_path_cost;
        sal_memcpy(port->config_bpdu.bridge_id, stp->bridge_id, ID_BYTES);
        port->config_bpdu.port_id = port->port_id;

        if (root_bridge(stp)) {
            port->config_bpdu.message_age = 0; /* (8.6.1.3.2(e))*/
        } else {
            port->config_bpdu.message_age =
                stp->root_port->message_age_timer.value + MESSAGE_AGE_INCREMENT;
        }

        port->config_bpdu.max_age = stp->max_age; /* (8.6.1.3.2(g))*/
        port->config_bpdu.hello_time = stp->hello_time;
        port->config_bpdu.forward_delay = stp->forward_delay;
        port->config_bpdu.tc_acknowledgment =
            port->tc_acknowledge; /* (8.6.1.3.2(h)) */
        port->config_bpdu.topology_change =
            stp->topology_change; /* (8.6.1.3.2(i)) */

        if (port->config_bpdu.message_age < stp->max_age) {
            port->tc_acknowledge = False; /* (8.6.1.3.3) */
            port->config_pending = False; /* (8.6.1.3.3)*/
            stp_send_config_bpdu(stp, port, &port->config_bpdu);
            start_hold_timer(stp, port); /* (8.6.3.3(b))*/
        }
    }
}

/*
 * Returns TRUE if we're the root of the spanning tree
 */
static Boolean
root_bridge(spantree_t *stp)
{
    return (!stp_cmpid(stp->designated_root, stp->bridge_id, ID_BYTES));
}

/*
 * Returns TRUE if this IEEE HELLO changes our port information (8.6.2.2)
 */
static Boolean
supersedes_port_info(spantree_t *stp, stp_port_t *port, Config_bpdu *config)
{
    int root, designated_bridge, bridge_id;

    root = stp_cmpid(config->root_id, port->designated_root, ID_BYTES);
    if (root != 0) {
        return (root < 0);   /* (8.6.2.2 a) */
    }

    /* Roots are equal, further checks needed */
    if (config->root_path_cost != port->designated_cost) {
        return (config->root_path_cost < port->designated_cost);
        /* (8.6.2.2 b) */
    }

    /* Costs are equal, further checks are needed */
    designated_bridge = stp_cmpid(config->bridge_id,
                                  port->designated_bridge, ID_BYTES);
    if (designated_bridge != 0) {
        return (designated_bridge < 0);  /* (8.6.2.2 c) */
    }

    /* Designated bridges are equal, further checks are needed (8.6.2.2 d) */
    bridge_id = stp_cmpid(config->bridge_id, stp->bridge_id, ID_BYTES);
    if (bridge_id != 0) {
        return (TRUE);   /* (8.6.2.2 d1) */
    }

    /* same bridge, compare port ID, (8.6.2.2 d2) */
    return (config->port_id <= port->designated_port);
}

/*
 * Move hello information into the port table (8.6.2)
 */
static void
record_config_information(spantree_t *stp, stp_port_t *port, Config_bpdu *config)
{
    sal_memcpy(port->designated_root, config->root_id, ID_BYTES);
    sal_memcpy(port->designated_bridge, config->bridge_id, ID_BYTES);
    port->designated_cost = config->root_path_cost;
    port->designated_port = config->port_id;
    start_message_age_timer(stp, port, config->message_age); /* (8.6.2.3.2) */
}

/*
 * Record new timeout values for spanning tree (8.6.3)
 */
static void
record_config_timeout_values(spantree_t *stp, Config_bpdu *config)
{
    stp->max_age = config->max_age;
    stp->hello_time = config->hello_time;
    stp->forward_delay = config->forward_delay;
    stp->topology_change = config->topology_change;
}

/*
 * Generate HELLOs on all ports that are the designated port (8.6.4)
 */
static void
config_bpdu_generation(spantree_t *stp)
{
    stp_port_t *port;

    FOR_ALL_PORTS_IN_STP(stp, port) {    /* (8.6.4.3) */
        if (is_designated_port(stp, port) && (port->state != STP_DISABLED)) {
            transmit_config(stp, port);
        } /* (8.6.1.2)*/ 
    }
}

/*
 * Check if the port is a designated port
 */
static Boolean
is_designated_port(spantree_t *stp, stp_port_t *port)
{
    return ((stp_cmpid(port->designated_bridge, stp->bridge_id, ID_BYTES) == 0) &&
            (port->designated_port == port->port_id));
}

/*
 * Reply with BPDU (8.6.5)
 */
static void
reply(spantree_t *stp, stp_port_t *port)
{
    transmit_config(stp, port); /* (8.6.5.3) */
}

/*
 * Transmit a IEEE topology change notification (8.6.6)
 */
static void
transmit_tcn(spantree_t *stp)
{
    stp_port_t *port;

    port = stp->root_port;
    port->tcn_bpdu.type = BPDU_TYPE_TCN;
    stp_send_tcn_bpdu(stp, port, &port->tcn_bpdu);
/*    debugk(DK_STP,"transmit_tcn :treeid =%d,port=%d\n",stp->external_id,get_global_port(port->unit,port->port));*/
}

/*
 * Update our knowledge of the spanning tree after recieving a HELLO (8.6.7)
 */
static void
configuration_update(spantree_t *stp)
{
    root_selection(stp); /* (8.6.7.3.1) */
    designated_port_selection(stp); /* (8.6.7.3.2) */
}

/*
 * Select our designated root and root port (8.6.8)
 */
static void
root_selection(spantree_t *stp)
{
    stp_port_t *port;
    stp_port_t *root_port;
    int cmp, port_cost, root_cost;

    root_port = NULL;

    FOR_ALL_PORTS_IN_STP(stp, port) {   /* (8.6.8.3.1) */
        if (!is_designated_port(stp, port) &&
            (port->state != STP_DISABLED) &&
            (stp_cmpid(port->designated_root, stp->bridge_id, ID_BYTES) < 0)) {
            if (root_port == NULL) {
                root_port = port;
                continue;
            }

            cmp = stp_cmpid(port->designated_root,
                            root_port->designated_root, ID_BYTES);
            if (cmp != 0) {
                if (cmp < 0) {
                    root_port = port;
                }
                continue;
            }

            /* The designated roots are equal, check cost */
            port_cost = port->designated_cost + port->path_cost;
            root_cost = root_port->designated_cost + root_port->path_cost;
            if (port_cost != root_cost) {
                if (port_cost < root_cost) {
                    root_port = port;
                }
                continue;
            }

            /* The path costs are equal, check designated bridge */
            cmp = stp_cmpid(port->designated_bridge, 
                            root_port->designated_bridge, ID_BYTES);
            if (cmp != 0) {
                if (cmp < 0) {
                    root_port = port;
                }
                continue;
            }

            /* The designated bridges are equal, check designated ports */
            if (port->designated_port != root_port->designated_port) {
                if (port->designated_port <
                    root_port->designated_port) { /* (8.6.8.3.1(d)) */
                    root_port = port;
                }
                continue;
            }

            if (port->port_id < root_port->port_id) {
                root_port = port;
            } /* (8.6.8.3.1(e)) */
        }
    }

    stp->root_port = root_port; /* (8.6.8.3.1) */
    if (root_port == NULL) {  /* (8.6.8.3.2) */
	sal_memcpy(stp->designated_root, stp->bridge_id, ID_BYTES);
        stp->root_path_cost = 0;
    } else { /* (8.6.8.3.3) */
	sal_memcpy(stp->designated_root,
                   root_port->designated_root, ID_BYTES);
        stp->root_path_cost = root_port->designated_cost + root_port->path_cost;
    }
}

/*
 * Figure out who is our designated port.
 * This function must be called after root selection (8.6.9)
 */
static void
designated_port_selection(spantree_t *stp)
{
    stp_port_t *port;
    int cmp;

    FOR_ALL_PORTS_IN_STP(stp, port) {  /* (8.6.9.3) */
        if (is_designated_port(stp, port)) { /* (8.6.9.3 a) */
            become_designated_port(stp, port); /* (8.6.10.2 a) */
            continue;
        }

	cmp = stp_cmpid(port->designated_root, stp->designated_root, ID_BYTES);
        if (cmp != 0) {    /* (8.6.9.3 b) */
            become_designated_port(stp, port);
            continue;
        }

        /* (8.6.9.3 c) */
        if (stp->root_path_cost < port->designated_cost) {
            become_designated_port(stp, port);
            continue;
        }

        if (stp->root_path_cost == port->designated_cost) {
            cmp = stp_cmpid(stp->bridge_id, port->designated_bridge, ID_BYTES);
            if (cmp < 0) {   /* (8.6.9.3 d) */
                become_designated_port(stp, port);
                continue;
            }

            /* (8.6.9.3 e) */
            if (cmp == 0 &&
                port->port_id <= port->designated_port) {
                become_designated_port(stp, port);
                continue;
            }
        }
    }
}

/*
 * Make the current port the designated port (8.6.10)
 */
static void
become_designated_port(spantree_t *stp, stp_port_t *port)
{
    sal_memcpy(port->designated_root, stp->designated_root, ID_BYTES);
    sal_memcpy(port->designated_bridge, stp->bridge_id, ID_BYTES);
    port->designated_cost = stp->root_path_cost;
    port->designated_port = port->port_id;
}

/*
 * Adjust port states given current topology (8.6.11)
 */
static void
port_state_selection(spantree_t *stp)
{
    stp_port_t *port;

    FOR_ALL_PORTS_IN_STP(stp, port) {
        if (port == stp->root_port) {  /* (8.6.11.3 a) */
            port->config_pending = False;
            port->tc_acknowledge = False;
            make_forwarding(stp, port); /* (8.6.11.3 a2)*/
        } else if (is_designated_port(stp, port)) {  /* (8.6.11.3 b) */
            stop_message_age_timer(stp, port);
            make_forwarding(stp, port);
        } else {  /* (8.6.11.3 c) */
            port->config_pending = False;
            port->tc_acknowledge = False;
            make_blocking(stp, port);
        }
    }
}

/*
 * Set port state to STP_FORWARDING (8.6.12)
 */
static void
make_forwarding(spantree_t *stp, stp_port_t *port)
{
    if (port->state == STP_BLOCKING) {  /* (8.6.12.3) */
      set_port_state(stp, port, STP_LISTENING); /* (8.6.12.3 a) */
        start_forward_delay_timer(stp, port); /* (8.6.12.3 b) */