ospf_link_state_database.c

vxworks下ospf协议栈

/* ospf_link_state_database.c - OSPF link state database */

/* Copyright 2000-2003 Wind River Systems, Inc. */
#include "copyright_wrs.h"

/*
modification history
--------------------
03e,17jul03,agi    Fixed compilation with __OPAQUE_LSA__ flag turned on
03d,30jun03,agi    Fixed SPR#88879, ospf does not clean up external LSDB when 
                   an interface is brought down
03c,26jun03,agi    Re-added LSA early retrasmission changes with a fix for new
                   routing table
03b,23jun03,agi    Backed out SPR#88619 early LSA retransmission changes, not 
                   compatible with new routing table
03a,30may03,asr    Changed route_proto to route_protocol
02z,30may03,agi    Fix for tOspfTimer crash
02y,30may03,asr	   Changes to make OSPF virtual stack compatible
03b,09may03,kc     Fixed SPR#88389 - update the lock_time_MinLSInterval value
                   in ospf_flush_the_link_state_database_of_self_originated_external_lsa().
                   Also added route_proto and is_default_route arguments to the routine
                   so that it can be used to flush the self-originated external lsa that
                   matches the given route protocol ID.
03a,26may03,agi    Changed rwos_get_system_elapsed_time_second() to
                   ospf_get_system_elapsed_time_second()
02w,23may03,dsk    SRP 88619 LSA early retransmission fix
02v,23may03,ram    SRP#76812 Correction for code submitted by mistake
02u,14may03,agi    Changed RWOS semaphores to vxWorks semaphores
02t,22apr03,ram	   SPR#76812 Modifications for OSPF performance enhancements
02s,17feb03,ram	   SPR 85893 Modified changes to eliminate side effects.
02r,29jan03,mwv    SPR 85893 - added function ospf_find_all_LSA() and modify ospf_find_LSA()
02q,28jan03,ram    SPR 85050 Added support for external route redistribution based on
 				   OSPF external metric values
02p,16jan03,smr    SPR 78250 - Modified to pass UNH 3.21
02o,14jan03,asr    SPR 85550 - force a routing table build rather than scheduling one.
02n,09dec02,hme    Add a new function ospf_find_database_entry() as part of a fix to SPR#75796, ANVL37.1
02m,03dec02,ram	   SPR 84312 - Change elapsed time to return seconds
02l,19nov02,mwv    Merge TMS code SPR 84284
02k,17Oct02,hme    Fix TSR #291001 also TSR #293548
02j,08oct02,agi    Fixed compiler warnings
02i,18aug02,kc     Corrected fixes for area lsdb checksum. Fixed ospf database overflow
                   in ospf_install_a_new_advertisement_in_the_link_state_database()
                   again.
02h,24jul02,jkw    Fix network lsa not being updated.
02g,18jul02,jkw    Fix Area Lsdb checksum sum.
02f,05jun02,kc     Corrected problem with database overflow implementation
                   in ospf_install_a_new_advertisement_in_the_link_state_database().
02e,13may02,ark    Added fix for SPR 75793. Added new function ospf_find_network_LSA
02d,19apr02,kc     Fixed ospf_remove_mib_database_entry_from_list() to explicitly set
                   the checksumsum value to zero if the lsa count is zero.
02c,16apr02,jkw    One copy of external and type 11 lsa
02b,09apr02,jkw    Sequence number wrap.
02a,16jan02,kc     Fixed ospf_add_new_mib_database_entry() - changed ospf2Mapi()
                   request type from update to create.
01z,09dec01,jkw    External route calculation changes.
01y,13oct01,jkw    Dynamic configuration changes.
01x,11oct01,jkw    Set pointer to NULL after table_free.
01w,22aug,jkw      Added opaque support for freeing up database.
01v,23jul01,jkw    Added in changes for new UNION_OSPF_LS_ID structure
01u,3may01,jkw     Added checks for NULL pointers and alarm messages
01t,26sep00,reshma Added WindRiver CopyRight
01s,25sep00,reshma RFC-1587 implementation for OSPF NSSA Option, also tested against ANVL.
                   added ospf_mib_delete_xxx_entry functions.
01r,11jul00,reshma MIB- LSDB entry : ospfLsdbAdvertisement modified.
01q,07jul00,reshma Unix compatibility related changes.
01p,04apr00,reshma Added some MIB support (Read only).Passed all important ANVL OSPF tests.
01o,23dec99,reshma Compatibility with VxWorks-IP and VxWorks RTM-interface
01n,10jun99,jack   Fixes in ospf_install_a_new_advertisement_in_the_link_state_database
                   to process LSInfinity cost adv properly.
01m,09jun99,jack   Fix in ospf_add_advertisement_to_the_global_external_advertisemnts_list
                   _of_ospf_class
01l,28dec98,jack   Compiled and added some comments
01k,11nov98,jack   Config changes, linted and big endian changes
01j,30oct98,jack   Incorporate changes for compilation on Vxworks
01i,23aug98,jack   ANVL tested OSPF with PATRICIA tree route table and no recursion
01h,10aug98,jack   PATRICIA Route Table Based OSPF Code Base
01g,05aug98,jack   Added a fix where routing_table_head was refered in function
                   ospf_free_database_entry
01f,04jun98,jack   Integration with RTM and BGP
01e,24apr98,jack   RTM changes
01d,10jul97,cindy  Pre-release v1.52b
01c,02oct97,cindy  Release Version 1.52
01b,22oct96,cindy  Release Version 1.50
01a,05jun96,cindy  First Beta Release
*/

/*
DESCRIPTION
ospf_link_state_database.c is used for adding, deleting and looking up link state advertisements
in the link state database.
This file is used whenever a link state advertisement is installed in or deleted from the link
state database.
*/

#include "ospf.h"
#if defined (__OSPF_VIRTUAL_STACK__)
#include "ospf_vs_lib.h"
#endif /* __OSPF_VIRTUAL_STACK__ */

/********************************************************************************************************************************/
static char *cptr_ls_type_string[] = {"Stub","Router","Network","Summary Network","Summary AS Boundary Router","AS External",
        "Bad LS Type"};
/********************************************************************************************************************************/
static enum TEST ospf_check_body_of_advertisements_for_differences (UNION_OSPF_LINK_STATE_ADVERTISEMENT *sptr_advertisement,
        OSPF_LS_DATABASE_ENTRY *sptr_old_instance);
/* SPR 85050 */
static OSPF_LS_DATABASE_ENTRY *ospf_add_entry_to_link_state_database (OSPF_LS_DATABASE_ENTRY *sptr_database_entry,OSPF_AREA_ENTRY *sptr_area,
        UNION_OSPF_LINK_STATE_ADVERTISEMENT *sptr_advertisement, int route_protocol);
static void ospf_add_new_mib_database_entry (OSPF_LS_DATABASE_ENTRY *sptr_new_database_entry,OSPF_AREA_ENTRY *sptr_area);
static void ospf_remove_mib_database_entry_from_list (OSPF_LS_DATABASE_ENTRY *sptr_database_entry_to_remove,OSPF_AREA_ENTRY *sptr_area);
OSPF_LS_DATABASE_ENTRY *ospf_process_old_ls_summary_summaryASBR_and_external_advertisements (OSPF_LS_DATABASE_ENTRY *sptr_old_instance, OSPF_AREA_ENTRY *sptr_area);
static void ospf_add_advertisement_to_the_global_summary_advertisemnts_list_of_area (
        UNION_OSPF_LINK_STATE_ADVERTISEMENT *sptr_advertisement, OSPF_AREA_ENTRY *sptr_area);

#if defined (__OSPF_DB_OVERFLOW_SUPPORT__)
void ospfExitOverflowState();
void ospfSetOverflowInterval(ULONG secs);
bool ospfSetDbLimit(ULONG num_ext_lsa);
void ospfShowDbOverflowStatus();
#endif /*__OSPF_DB_OVERFLOW_SUPPORT__*/
/******************************************************************************/
/* section 13.2 (p. 137) */
OSPF_LS_DATABASE_ENTRY *ospf_install_a_new_advertisement_in_the_link_state_database (OSPF_LS_DATABASE_ENTRY *sptr_old_instance,
        UNION_OSPF_LINK_STATE_ADVERTISEMENT *sptr_advertisement,OSPF_AREA_ENTRY *sptr_area, enum TEST *enumptr_test_different_lsa,int route_protocol)
{
        enum TEST difference_found;
        OSPF_LS_DATABASE_ENTRY *sptr_new_instance = NULL ;

    	enum OSPF_LS_TYPE ls_type;
#if defined (__NSSA__)
#if defined (__NSSA_FIXES__)
	  	enum BOOLEAN I_am_an_area_border_router;
#endif /* __NSSA_FIXES__ */
#endif /* __NSSA__ */

        OSPF_PRINTF_DEBUG (OSPF_DEBUG_PRINTF, "OSPF: Entering ospf_install_a_new_advertisement_in_the_link_state_database\r\n");

    if ((sptr_area == NULL) || (sptr_advertisement == NULL))
        {
        return( NULL );
        }

        difference_found = ospf_check_if_new_advertisement_is_different_from_its_previous_instance (sptr_advertisement,
                sptr_old_instance);
        *enumptr_test_different_lsa = difference_found;

        if (sptr_old_instance != NULL)
                {
                sptr_old_instance = ospf_process_old_ls_summary_summaryASBR_and_external_advertisements (sptr_old_instance, sptr_area);
                }

        ls_type = sptr_advertisement->sptr_router->ls_header.type;


#if defined(__OSPF_DB_OVERFLOW_SUPPORT__)
        /*
         * ospf_external_lsdb_limit if not set to -1 means that there is only a certain
         * number of external LSAs that we can received/installed.
         */
        if ( (ospf.ospf_external_lsdb_limit != -1) && (ls_type == OSPF_LS_AS_EXTERNAL) )
        	{
            /*
             * RFC1765 section 2.3.1 item #3 - if adding the LSA to the router's database
             * would keep the number of non-default AS-external-LSA less than or equal to
             * ospfExtLsdbLimit, the LSA is accepted.
             */
            if ((ospf.ospf_external_lsa_count + 1) <= ospf.ospf_external_lsdb_limit)
                {
                sptr_new_instance = ospf_add_entry_to_link_state_database (sptr_old_instance, sptr_area, sptr_advertisement, route_protocol);
                }

            /*
             * RFC1765 section 2.1 - when the number of non-default AS-external-LSAs
             * reaches the ospfExtLsdbLimit, the router enters OverflowState. The router
             * never hold more than ospfExtLsdbLimit non-default AS-external-LSAs in
             * its database.
             */
            if (ospf.ospf_external_lsa_count >= ospf.ospf_external_lsdb_limit)
            	{
                /* SPR#88389 - route proto 0 means flush all self-originated
                 * external routes, set is_default_route to FALSE since all
                 * self-originated external routes must be flushed anyway
                 */
                ospf_flush_the_link_state_database_of_self_originated_external_lsa (0, FALSE);
                OSPF_PRINTF_DB_OVERFLOW (OSPF_DB_OVERFLOW_PRINTF, "OSPF: Flushing the LSDB\n");
                ospf.in_overflow_state = TRUE;
                return(sptr_new_instance);
                }
        	}
        else
        	{
            /* if we are here, install the received LSA */
#if defined (__NSSA__)
#if defined (__NSSA_FIXES__)
		/*************SPR 75500**************/
        I_am_an_area_border_router = ospf_check_if_area_border_router ();
        /* P bit is 0*/
        if ((sptr_advertisement->sptr_router->ls_header.options._bit.dont_propagate == TRUE)&& (sptr_advertisement->sptr_router->ls_header.advertising_router !=
			net_to_host_long(ospf.router_id)) && (I_am_an_area_border_router == TRUE))
			{
            logMsg("\n",0,0,0,0,0,0);
			}
        else
			{
			/* SPR 85050 */
            sptr_new_instance = ospf_add_entry_to_link_state_database (sptr_old_instance, sptr_area, sptr_advertisement, route_protocol);
			}
#else /* __NSSA_FIXES__ */

			/* SPR 85050 */
            sptr_new_instance = ospf_add_entry_to_link_state_database (sptr_old_instance, sptr_area, sptr_advertisement, route_protocol);

#endif /* __NSSA_FIXES__ */
#else /* __NSSA__ not defined */

			/* SPR 85050 */
		    sptr_new_instance = ospf_add_entry_to_link_state_database (sptr_old_instance, sptr_area, sptr_advertisement, route_protocol);

#endif /* __NSSA__ */
			}


#else /*__OSPF_DB_OVERFLOW_SUPPORT__*/
	    /*************SPR 75500**************/
#if defined (__NSSA__)
#if defined (__NSSA_FIXES__)
      	I_am_an_area_border_router = ospf_check_if_area_border_router ();

      	if ((sptr_advertisement->sptr_router->ls_header.options._bit.dont_propagate == TRUE )
        	&& (sptr_advertisement->sptr_router->ls_header.advertising_router !=
			net_to_host_long(ospf.router_id )) &&(I_am_an_area_border_router == TRUE ))
			{
           	logMsg("\n",0,0,0,0,0,0);
			}
       	else
	   		{
			/* SPR 85050 */
            sptr_new_instance = ospf_add_entry_to_link_state_database (sptr_old_instance, sptr_area, sptr_advertisement, route_protocol);
			}
#else/*__NSSA_FIXES__*/
		/* SPR 85050 */
        sptr_new_instance = ospf_add_entry_to_link_state_database (sptr_old_instance, sptr_area, sptr_advertisement, route_protocol);
#endif /* __NSSA_FIXES__ */
#else /*__NSSA__*/
		/* SPR 85050 */
        sptr_new_instance = ospf_add_entry_to_link_state_database (sptr_old_instance, sptr_area, sptr_advertisement, route_protocol);
#endif/*__NSSA__*/

#endif /*__OSPF_DB_OVERFLOW_SUPPORT__*/


        if (sptr_new_instance == NULL)
                {
                return NULL;
                }


        if ((difference_found == PASS) && ((sptr_advertisement->sptr_router->ls_header.type == OSPF_LS_ROUTER) ||
                (sptr_advertisement->sptr_router->ls_header.type == OSPF_LS_NETWORK)))
                {
                ospf_schedule_routing_table_build ();           /* the entire routing table must be recalculated (page 137) */
                }

        if ((sptr_advertisement->sptr_router->ls_header.type == OSPF_LS_SUMMARY_NETWORK) ||
                (sptr_advertisement->sptr_router->ls_header.type == OSPF_LS_SUMMARY_AS_BOUNDARY_ROUTER))
                {
                ospf_add_advertisement_to_the_global_summary_advertisemnts_list_of_area (sptr_advertisement, sptr_area);

                if (difference_found == PASS)
                        {
                        ospf_update_routing_table_due_to_receipt_of_a_new_summary_link_advertisement (sptr_advertisement->sptr_summary, sptr_area);
                        }
                }

        if (sptr_advertisement->sptr_router->ls_header.type == OSPF_LS_AS_EXTERNAL)
                {
                if (difference_found == PASS)
                    {
                    /* SPR 85550 start */
                    /* in receiving type 5 LSAs: routing table was updated here
                    from the receive task only for that route without a full
                    routing table build. This works well if the route is unique,
                    but if there are multiple routes to same destination, the
                    new route computed based on this type 5 LSA only may not
                    be the best route overall, therefore a schedule of SPF was added.*/

                    ospf_schedule_routing_table_build ();
                    }
                }

#if defined (__NSSA__)
#if defined(__NSSA_FIXES__)
       if (sptr_advertisement->sptr_router->ls_header.type == OSPF_LS_TYPE_7)
          {
                if (difference_found == PASS)
                {
                   ospf_update_routing_table_due_to_receipt_of_a_new_type_7_external_link_advertisement(sptr_advertisement->sptr_type_7, sptr_area);
                   if ((I_am_an_area_border_router == TRUE)&& (sptr_area->flags._bit.nssa == TRUE))
                    {
                       ospf_translate_type_7_routes_into_type_5_lsa();
                    }

                }
         }
#endif /* __NSSA_FIXES__ */
#endif /* __NSSA__ */