/* 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 on03d,30jun03,agi    Fixed SPR#88879, ospf does not clean up external LSDB when                    an interface is brought down03c,26jun03,agi    Re-added LSA early retrasmission changes with a fix for new                   routing table03b,23jun03,agi    Backed out SPR#88619 early LSA retransmission changes, not                    compatible with new routing table03a,30may03,asr    Changed route_proto to route_protocol02z,30may03,agi    Fix for tOspfTimer crash02y,30may03,asr	   Changes to make OSPF virtual stack compatible03b,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 fix02v,23may03,ram    SRP#76812 Correction for code submitted by mistake02u,14may03,agi    Changed RWOS semaphores to vxWorks semaphores02t,22apr03,ram	   SPR#76812 Modifications for OSPF performance enhancements02s,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 values02p,16jan03,smr    SPR 78250 - Modified to pass UNH 3.2102o,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.102m,03dec02,ram	   SPR 84312 - Change elapsed time to return seconds02l,19nov02,mwv    Merge TMS code SPR 8428402k,17Oct02,hme    Fix TSR #291001 also TSR #29354802j,08oct02,agi    Fixed compiler warnings02i,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_LSA02d,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 lsa02b,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 structure01u,3may01,jkw     Added checks for NULL pointers and alarm messages01t,26sep00,reshma Added WindRiver CopyRight01s,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-interface01n,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_class01l,28dec98,jack   Compiled and added some comments01k,11nov98,jack   Config changes, linted and big endian changes01j,30oct98,jack   Incorporate changes for compilation on Vxworks01i,23aug98,jack   ANVL tested OSPF with PATRICIA tree route table and no recursion01h,10aug98,jack   PATRICIA Route Table Based OSPF Code Base01g,05aug98,jack   Added a fix where routing_table_head was refered in function                   ospf_free_database_entry01f,04jun98,jack   Integration with RTM and BGP01e,24apr98,jack   RTM changes01d,10jul97,cindy  Pre-release v1.52b01c,02oct97,cindy  Release Version 1.5201b,22oct96,cindy  Release Version 1.5001a,05jun96,cindy  First Beta Release*//*DESCRIPTIONospf_link_state_database.c is used for adding, deleting and looking up link state advertisementsin the link state database.This file is used whenever a link state advertisement is installed in or deleted from the linkstate 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__ */