ospf_routing_table.c

vxworks下ospf协议栈

/* ospf_routing_table.c */

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

/*
modification history
___________________
02r,22jul03,agi    Fixed compiler warning
02q,09jun03,htm    SPR#87382 - Fix for ANVL 4.2
02p,11jun03,ram    SPR#88965 Separate route table and LSDB hash parameters
02o,22may03,kkz    SPR 88613 - area aggregation, including correct use of "active" flag for address ranges, to track
                   active links
02n,22apr03,ram	   SPR#76812 Modifications for OSPF performance enhancements
02m,07jan03,agi    Added SPR#78251, ANVL 4.2 fix
02l,06jan03,dsk    Fix for SPR#75194, ANVL 27.15
02k,22nov02,htm    Fix for TSR# 297651 (SPR# 83274).
02j,02dec02,kkz    Fix SPR 84567
02i,22nov02,hme    Fix for SPR 83274
02h,19nov02,mwv    Merge TMS code SPR 84284
02g,18oct02,hme    As part of the TSR 291001, call
                   ospf_export_route_to_other_protocols() with OSPF_DELETE_PATH 
02f,08oct02,agi    Fixed compiler warning
02e,05aug02,jkw    Fix TSR 288035 and TSR 288030
02d,10jul02,jkw    Fix UNH 5.3 test.
02c,20dec01,jkw    Removed sptr_area->sptr_interfaces structure.
02b,23aug01,jkw    Fixed compiler warnings.
02a,14aug01,kc     Bring down virtual link if endpoint not reachable.
01z,03may01,jkw    Added checks for NULL pointers and alarm messages
01y,26sep00,reshma Added WindRiver CopyRight
01x,25sep00,reshma RFC-1587 implementation for OSPF NSSA Option, also tested against ANVL.
01w,07jul00,reshma Unix compatibility related changes.
01v,04apr00,reshma Added some MIB support (Read only).Passed all important ANVL OSPF tests.
01u,23dec99,reshma Compatibility with VxWorks-IP and VxWorks RTM-interface
01t,13aug99,jack   compilation fixes no IP case
01s,12may99,jack   Changes related to equal cost multi path and
                   ospf_set_patricia_route_change_status_on_ospf_rt_node
01r,12may99,jack   Fix in ospf_get_new_next_hop_blocks_and_mark_ospf_rt_node_new
01q,12may99,jack   Changes in function
                   ospf_get_new_next_hop_blocks_and_mark_ospf_rt_node_new
01p,10may99,jack   Changes in prototypes and call and declaration of
                   ospf_get_new_next_hop_blocks
01o,10may99,jack   Changes related to ospf_get_new_next_hop_blocks
01n,28dec98,jack   Compiled and added some comments
01m,30nov98,jack   Removed C++ style comments and removed some commented out code
01l,23nov98,jack   Changed %p in printing to %lx
01k,13nov98,jack   Changes related to introducing queuing in OSPF to RTM interface and bug
                   fix on the external route additions path (to RTM)
01j,11nov98,jack   Config changes, linted and big endian changes
01i,30oct98,jack   Incorporate changes for compilation on Vxworks
01h,23aug98,jack   ANVL tested OSPF with PATRICIA tree route table and no recursion
01g,10aug98,jack   PATRICIA Route Table Based OSPF Code Base
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_routing_table.c is used for calculating and building a new routing table.  This file will
call the appropriate functions to build the intra-area, inter-area, and external paths for
building the routing table.
This file is used whenever the routing table needs to be built.
*/

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

/***********************************************************************************************************************************/
static OSPF_TRANSIT_AREA_ENTRY *ospf_create_transit_area_list (void);
static void ospf_examine_transit_areas_for_better_paths (OSPF_TRANSIT_AREA_ENTRY *sptr_transit_list,OSPF_AREA_ENTRY *sptr_area);
#if defined __OSPF_DEBUG__
static void ospf_print_areas_and_lsas (void);
#endif

/* SPR#76812 */
static void ospf_print_lsas (OSPF_LS_DATABASE_HEAD ls_db_head);
static void ospf_generate_events_due_to_routing_table_changes (OSPF_ROUTING_TABLE_NODE *sptr_old_routing_table_head[OSPF_ROUTE_TABLE_MAX][OSPF_RT_HASH_TABLE_SIZE]);

/***********************************************************************************************************************************/
/* ANVL 27.15 start */
BOOLEAN ospf_verify_if_route_is_old(OSPF_ROUTING_TABLE_ENTRY *sptr_routing_table_entry)
    {
    OSPF_ROUTING_TABLE_NODE *sptr_old_routing_table_node;
    OSPF_ROUTING_TABLE_ENTRY     *sptr_old_routing_table_entry;
	ULONG index;
	enum OSPF_ROUTE_TABLE_TYPE table_type;

    /* if this is called from task executing Dijkstra, then pointer to old routing table still exists.
    If this is called from receive task while processing a received type 3 LSA, then old routing table
    pointer is null. */

    if (sptr_routing_table_entry == NULL)
        {  /* just for robustness. If we are executing this, it should be for a valid routing table entry */
        return TRUE; /* CI */
        }

	/* SPR#76812 -- Begin */
	for(table_type = OSPF_ROUTE_TABLE_NETWORK; table_type < OSPF_ROUTE_TABLE_MAX; table_type++)
	{
		for(index = 0x00000000L; index < OSPF_RT_HASH_TABLE_SIZE; index++)
		{
			for (sptr_old_routing_table_node = ospf.sptr_old_routing_table[table_type][index];
				 sptr_old_routing_table_node != NULL;
        		 sptr_old_routing_table_node = sptr_old_routing_table_node->sptr_forward_link)
        	{
        		if (sptr_old_routing_table_node->sptr_routing_table_entry != NULL)
            	{
            		/* compare sptr_old_routing_table_node with routing_table_entry */
            		sptr_old_routing_table_entry = sptr_old_routing_table_node->sptr_routing_table_entry;

            		if (sptr_old_routing_table_entry->destination_id == sptr_routing_table_entry->destination_id )
            	    {
            		    if ((sptr_old_routing_table_entry->destination_type == sptr_routing_table_entry->destination_type ) &&
            		        (sptr_old_routing_table_entry->address_mask == sptr_routing_table_entry->address_mask ) &&
            		        (sptr_old_routing_table_entry->advertising_router == sptr_routing_table_entry->advertising_router ) &&
            		        (sptr_old_routing_table_entry->link_state_id == sptr_routing_table_entry->link_state_id ) &&
            		        (sptr_old_routing_table_entry->path_cost == sptr_routing_table_entry->path_cost ) &&
            		        (sptr_old_routing_table_entry->path_type == sptr_routing_table_entry->path_type ) )
            	        {
            		        return TRUE;
            	        } /* if routing table entry unchanged */
            	    } /* if found routing table entry for same destination */
            	} /* if entry in old routing table is not null */
        	} /* for every entry in the old routing table */
		}
	}
	/* SPR#76812 -- End */

    return(FALSE);
    } /* ospf_verify_if_route_is_old */
/* ANVL 27.15 end */

/***********************************************************************************************************************************/
void ospf_schedule_routing_table_build (void)
    {
    OSPF_PRINTF_DEBUG (OSPF_DEBUG_PRINTF, "OSPF: Entering ospf_schedule_routing_table_build\r\n");

    if (ospf.build_routing_table == FALSE)
        {
        ospf.build_routing_table = TRUE;
        }

    return;
    }
/*****************************************************************************//* section 16 of OSPF specification (page 148-149) */
void ospf_build_routing_table (void)
    {
    OSPF_ROUTING_TABLE_NODE *sptr_old_routing_table_head[OSPF_ROUTE_TABLE_MAX][OSPF_RT_HASH_TABLE_SIZE];
	ULONG index;
	enum OSPF_ROUTE_TABLE_TYPE table_type;
    OSPF_AREA_ENTRY *sptr_area = NULL;
    OSPF_AREA_ENTRY *sptr_next_area = NULL;
    enum BOOLEAN I_am_an_area_border_router;
    OSPF_TRANSIT_AREA_ENTRY *sptr_transit_list;
    enum OSPF_ROUTE_PATH_TYPE route_path_type;

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

    sptr_area = NULL;
    sptr_transit_list = NULL;
    route_path_type = OSPF_ROUTE_PATH_TYPE_WILDCARD; /* recursion deletion and linear list elimination changes */

    OSPF_PRINTF_ROUTING_TABLE (OSPF_ROUTING_TABLE_PRINTF, "OSPF: Building the routing table\r\n");

#if defined __OSPF_DEBUG__	/* Printing large amount of data causes some delays, can be turned on, when needed */
    ospf_print_areas_and_lsas ();

    ospf_display_routing_table ();
#endif

    ospf.build_routing_table = FALSE;

    /* SPR#76812 -- Begin */
    for(table_type = OSPF_ROUTE_TABLE_NETWORK; table_type < OSPF_ROUTE_TABLE_MAX; table_type++)
	{
		for(index = 0x00000000L; index < OSPF_RT_HASH_TABLE_SIZE; index++)
		{
			sptr_old_routing_table_head[table_type][index] = ospf.sptr_routing_table_head[table_type][index];
			ospf.sptr_old_routing_table[table_type][index] = sptr_old_routing_table_head[table_type][index];
			ospf.sptr_routing_table_head[table_type][index] = NULL;
		}
	}
	/* SPR#76812 -- End */

    for (sptr_area = ospf.sptr_area_list; sptr_area != NULL; sptr_area = sptr_next_area)
        {
        sptr_next_area = sptr_area->sptr_forward_link;
        ospf_calculate_shortest_path_tree (sptr_area);
        }


    I_am_an_area_border_router = ospf_check_if_area_border_router ();

    if (I_am_an_area_border_router == TRUE)                                                         /* section 16, item (2)  */
        {
        sptr_area = ospf.sptr_backbone_area;
        }
    else
        {
        for (sptr_area = ospf.sptr_area_list; sptr_area != NULL; sptr_area = sptr_next_area)
            {
            sptr_next_area = sptr_area->sptr_forward_link;
            if (sptr_area->number_of_interfaces_in_up_state == 0)
                {
                continue;
                }
            break;
            }
        }

    if (sptr_area != NULL)
        {
        ospf_calculate_inter_area_routes (sptr_area);                                                                   /* section 16, item (3)  */
        }


    if (I_am_an_area_border_router == TRUE)
        {
        sptr_transit_list = ospf_create_transit_area_list ();
        if (sptr_transit_list != NULL)
            {
            ospf_examine_transit_areas_for_better_paths (sptr_transit_list, sptr_area);                     /* section 16, item (4)  */
            if (sptr_transit_list != NULL)
                {
                (void) ospf_free_entire_list ((OSPF_GENERIC_NODE *) sptr_transit_list);
                }
            }
        }

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

    ospf_calculate_routes_to_external_destinations ();                                                          /* section 16, item (5) */

#if defined (__NSSA__)
    ospf_calculate_type_7_as_external_routes ();                                                                /*  Calculate type-7 As external routes*/