ospf_shortest_path_calculation.c

vxworks下ospf协议栈

/* ospf_shortest_path_calculation.c */

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

/*
modification history
--------------------
02j,22may03,kkz SPR 88613, Area address ranges, "active" flag not cleared for inactive ranges
02j,22apr03,ram	SPR#76812 Modifications for OSPF performance enhancements
02i,29jan03,asr Fix for SPR# 85573.
02h,07jan02,agi Fixed SPR#78251, ANVL 4.2
02g,22nov02,htm Fix SPR#83274
02f,05aug02,jkw Fix TSR 288030
02e,30jan02,jkw Fix routes not being propagated.
02d,20dec01,jkw Removed sptr_area->sptr_interfaces structure.
02c,13oct01,kc  Dynamic configuration changes.
02b,11oct01,jkw Set pointer to NULL after table_free.
02a,23aug01,jkw Fixed compiler warnings.
01z,18jul01,jkw Fix for checking for NULL pointer in 
                ospf_set_next_hop_when_intervening_router_is_present.
01y,28jun01,jkw Added fixes for multiple inter-area paths
01x,26jun01,jkw Added updates for multiple path destination
01w,20jun01,jkw Added unnumbered link support
01v,03may01,jkw Added checks for NULL pointers and alarm messages
01u,26sep00,reshma Added WindRiver CopyRight
01t,25sep00,reshma RFC-1587 implementation for OSPF NSSA Option, also tested against ANVL.
01s,07jul00,reshma Unix compatibility related changes.
01r,04apr00,reshma Added some MIB support (Read only).Passed all important ANVL OSPF tests.
01q,23dec99,reshma Compatibility with VxWorks-IP and VxWorks RTM-interface
01p,13aug99,jack   compilation fixes no IP case
01o,12may99,jack   Changes related to equal cost multi path and
			  ospf_set_patricia_route_change_status_on_ospf_rt_node
01n,12may99,jack   fixes for equal cost multipath
01m,11may99,jack	  Fixes related to equal cost multi path 
01l,10may99,jack	  Multipath fixes
01k,28dec98,jack   Compiled and added some comments
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_shortest_path_calculation.c is used for creating the shortest path for intra-area
route calculations and stub networks.  This file will call the dijkstra algorithm for each
area.  This file will add stub networks to 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 void ospf_initialize_data_structures_for_shortest_path_calculation (OSPF_AREA_ENTRY *sptr_area);
static void ospf_add_stub_networks_to_shortest_path_tree (OSPF_AREA_ENTRY *sptr_area);
static enum TEST ospf_check_if_vertex_is_reachable (ULONG vertex,OSPF_LS_DATABASE_ENTRY *sptr_database_entry);
static enum TEST ospf_examine_distance_of_stub_network (OSPF_ROUTER_LINK_PIECE *sptr_link,OSPF_SHORTEST_PATH_NODE *sptr_vertex_V,
	ULONG *ulptr_cost_D,OSPF_ROUTING_TABLE_NODE **ptr_to_sptr_routing_table_node);
static OSPF_SHORTEST_PATH_NODE *ospf_create_stub_vertex (ULONG vertex,OSPF_LS_DATABASE_ENTRY *sptr_database_entry,ULONG cost_D,
	OSPF_SHORTEST_PATH_NODE *sptr_vertex_V, OSPF_AREA_ENTRY *sptr_area );
static OSPF_ROUTING_TABLE_ENTRY *ospf_set_routing_table_entry_for_stub_network (OSPF_ROUTING_TABLE_ENTRY *sptr_routing_table_entry,
	OSPF_SHORTEST_PATH_NODE *sptr_vertex_stub,OSPF_AREA_ENTRY *sptr_area,OSPF_SHORTEST_PATH_NODE *sptr_vertex_V, OSPF_ROUTER_LINK_PIECE *sptr_link);
static OSPF_ROUTING_TABLE_ENTRY *ospf_update_routing_table_entry_for_stub_network (OSPF_ROUTING_TABLE_NODE *sptr_routing_table_node,
	OSPF_SHORTEST_PATH_NODE *sptr_vertex_stub,OSPF_AREA_ENTRY *sptr_area,OSPF_SHORTEST_PATH_NODE *sptr_vertex_V,ULONG cost_D);
static OSPF_ROUTING_TABLE_ENTRY *ospf_create_routing_table_entry_for_stub_network (OSPF_SHORTEST_PATH_NODE *sptr_vertex_stub,
	OSPF_SHORTEST_PATH_NODE *sptr_vertex_V,OSPF_AREA_ENTRY *sptr_area, OSPF_ROUTER_LINK_PIECE *sptr_link);
static OSPF_NEXT_HOP_BLOCK *ospf_create_next_hop_block (void);
static ULONG ospf_find_outgoing_interface_for_router (ULONG router, ULONG interface_address, ULONG *next_hop_router);
static OSPF_NEXT_HOP_BLOCK *ospf_set_next_hop_when_intervening_router_is_present (OSPF_SHORTEST_PATH_NODE  *sptr_destination, OSPF_SHORTEST_PATH_NODE  *sptr_parent, OSPF_AREA_ENTRY *sptr_area, OSPF_ROUTER_LINK_PIECE *sptr_link);
static OSPF_NEXT_HOP_BLOCK *ospf_set_next_hop_when_parent_vertex_is_this_router (OSPF_SHORTEST_PATH_NODE *sptr_destination, OSPF_ROUTER_LINK_PIECE *sptr_link, OSPF_AREA_ENTRY *sptr_area);
static OSPF_NEXT_HOP_BLOCK *ospf_set_outgoing_interface_for_a_locally_attached_stub_network (OSPF_ROUTING_TABLE_ENTRY *sptr_routing_table_entry,
	OSPF_AREA_ENTRY *sptr_area);
static enum TEST ospf_check_if_link_exists_for_ls_header_type_of_ls_router (UNION_OSPF_LINK_STATE_ADVERTISEMENT *sptr_advertisement,ULONG vertex,OSPF_AREA_ENTRY *sptr_area);
/************************************************//* Run Dijkstra on this area *//* section 16.1 of OSPF specification (page 150) */
void ospf_calculate_shortest_path_tree (OSPF_AREA_ENTRY *sptr_area)
{

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

	if ( (sptr_area->sptr_interfaces != NULL ) && (sptr_area->sptr_interfaces->type == OSPF_VIRTUAL_LINK) )
		{
		if (sptr_area->area_id != OSPF_BACKBONE)
			{
			return;
			}
		}

	ospf_initialize_data_structures_for_shortest_path_calculation (sptr_area);

	++(sptr_area->shortest_path_first_run_count);

	++(ospf.routing_table_revision_number);

	ospf_run_dijkstra (sptr_area);										/* section 16.1, first stage (page 151-154) */

	ospf_add_stub_networks_to_shortest_path_tree (sptr_area);	/* section 16.1, second stage (page 154-155) */

#if defined(__OSPF_MIB__)
    ospf2Mapi_request( (void *)sptr_area, ospfAreaUpdateReqType );
#endif /* __OSPF_MIB__ */

	return;
}
/**********************************************************************************************************************************/
static void ospf_initialize_data_structures_for_shortest_path_calculation (OSPF_AREA_ENTRY *sptr_area)
{
    OSPF_ADDRESS_RANGE_LIST_ENTRY *sptr_address_range;
	OSPF_PRINTF_DEBUG (OSPF_DEBUG_PRINTF, "OSPF: Entering ospf_initialize_data_structures_for_shortest_path_calculation\r\n");

	ospf_free_areas_shortest_path_tree_nodes (sptr_area->shortest_path_first_tree.sptr_forward_link);

	/* free associated next_hops */
	if (sptr_area->shortest_path_first_tree.sptr_next_hop != NULL)
		{
		ospf_free_entire_list ((OSPF_GENERIC_NODE*) sptr_area->shortest_path_first_tree.sptr_next_hop);
		}

    sptr_area->shortest_path_first_tree.sptr_forward_link = NULL;
	sptr_area->shortest_path_first_tree.sptr_backward_link = NULL;
	sptr_area->shortest_path_first_tree.sptr_next_hop = NULL;

	ospf_free_areas_shortest_path_tree_nodes (sptr_area->sptr_candidate);

	sptr_area->sptr_candidate = NULL;
    /* UNH 4.2 start */
    /* reset transit area bits for non backbone areas, but only during init SPF for backbone area,
       not also during init SPF for other areas. 
       The SPF computation for backbone handles virtual links (which are part of the backbone
       by definition even if they reside in other areas). Therefore during SPF computation
       for backbone area, the transit area bits will be set for areas where the virtual links 
       actually reside. Do not reset transit area bit again during init SPF for 
       non-backbone areas. */
    
    if (sptr_area->area_id == OSPF_BACKBONE) 
    { /* reset transit area bits for all non backbone areas, because area 0 will then set them to correct values */
        OSPF_AREA_ENTRY *sptr_area_non_backbone;
        for (sptr_area_non_backbone = ospf.sptr_area_list;sptr_area_non_backbone != NULL; sptr_area_non_backbone = sptr_area_non_backbone->sptr_forward_link) 
        {
            if (sptr_area_non_backbone->area_id == OSPF_BACKBONE) 
            {
                continue;
            }
            /* reset transit area bit to FALSE; it will be properly set during SPF for backbone area */
            sptr_area->flags._bit.transit = FALSE;
        }
    }
    /* UNH 4.2 end */
    /* SPR 88613  Begin */
    /* Reset the active flag for area address ranges in this area.  This flag will
     * be set during run_dijkstra, for each address range with an active network
     */
    for (sptr_address_range = sptr_area->sptr_address_ranges; sptr_address_range != NULL;
        sptr_address_range = sptr_address_range->sptr_forward_link)
        {
        sptr_address_range->active = (BYTE_ENUM (BOOLEAN)) FALSE;
        }
    /* SPR 88613 End */

	return;
}
/***********************************************************************************//* section 16.1, second stage (page 154-155) */
static void ospf_add_stub_networks_to_shortest_path_tree (OSPF_AREA_ENTRY *sptr_area)
{
	OSPF_SHORTEST_PATH_NODE *sptr_vertex_V;
	OSPF_SHORTEST_PATH_NODE *sptr_vertex_stub;
	OSPF_LS_DATABASE_ENTRY *sptr_database_entry;
	OSPF_ROUTER_LINK_PIECE *sptr_link;
	USHORT number_of_links;
	ULONG cost_D;
	OSPF_ROUTING_TABLE_NODE *sptr_routing_table_node;
	OSPF_ROUTING_TABLE_ENTRY *sptr_routing_table_entry;
	enum TEST return_code;


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

	sptr_routing_table_node = NULL;
	sptr_routing_table_entry = NULL;

	for (sptr_vertex_V = &sptr_area->shortest_path_first_tree; sptr_vertex_V != NULL;
		sptr_vertex_V = sptr_vertex_V->sptr_forward_link)
		{
		/* SPR#76812 -- Begin */
		sptr_database_entry = ospf_find_LSA (sptr_area, sptr_vertex_V->vertex, 0x00000000L, OSPF_LS_ROUTER);
		/* SPR#76812 -- End */

		if (sptr_database_entry == NULL)
			{
			continue;
			}

		return_code = ospf_check_if_vertex_is_reachable (sptr_vertex_V->vertex, sptr_database_entry);

		if (return_code == FAIL)
			{
			continue;															/* discard unreachable vertices */
			}

		number_of_links = sptr_database_entry->advertisement.sptr_router->number_of_links;
		number_of_links = net_to_host_short (number_of_links);

		for (sptr_link = &sptr_database_entry->advertisement.sptr_router->link; number_of_links > 0x0000;	--number_of_links,
			sptr_link = (OSPF_ROUTER_LINK_PIECE *) ((ULONG) sptr_link + OSPF_ROUTER_LINK_PIECE_SIZE +
			((sptr_link->number_of_metrics) * OSPF_ROUTER_LINK_METRIC_PIECE_SIZE)))
			{
			OSPF_PRINTF_DEBUG (OSPF_DEBUG_PRINTF, "OSPF: PROCESSING STUB NETWORK: %lx FOR SPT: ospf_shortest_path_calculation.c: Function ospf_add_stub_networks_to_shortest_path_tree \r\n", sptr_link->link_id);

			sptr_routing_table_node = NULL;
			if (sptr_link->type == OSPF_ROUTER_LINK_TYPE_STUB_NETWORK)
				{
				/* section 16.1, stage 2, item (1) (p 154) */

				/*
				 * In the following function, ospf_examine_distance_of_stub_network, a route marked as NOT_AVAILABLE
				 * may be marked as NOT_NEW
				 */

				return_code = ospf_examine_distance_of_stub_network (sptr_link, sptr_vertex_V, &cost_D, &sptr_routing_table_node);

				if (return_code == FAIL)
					{
					continue;
					}

				sptr_vertex_stub = ospf_create_stub_vertex (sptr_link->link_id, sptr_database_entry, cost_D, sptr_vertex_V, sptr_area );

				if (sptr_vertex_stub == NULL)
					{
					continue;
					}

				sptr_vertex_stub->sptr_next_hop = ospf_calculate_the_set_of_next_hops (sptr_vertex_stub, sptr_vertex_V, sptr_link, sptr_area);
				sptr_vertex_stub->cost = cost_D;

				/* section 16.1, stage 2, item (2) (p 154-155) */
				if (sptr_routing_table_node == NULL)
					{
					sptr_routing_table_entry = ospf_set_routing_table_entry_for_stub_network (sptr_routing_table_entry, sptr_vertex_stub,
						sptr_area, sptr_vertex_V, sptr_link);
					}
				else
					{
					sptr_routing_table_entry = ospf_update_routing_table_entry_for_stub_network (sptr_routing_table_node, sptr_vertex_stub,
						sptr_area, sptr_vertex_V, cost_D);
					if (sptr_routing_table_entry == NULL)
						{
						/* SPR#76812 -- Begin */
						ospf_delete_routing_table_node(sptr_routing_table_node);
						/* SPR#76812 -- End */

						sptr_routing_table_node = NULL;

						}
					}

				if (sptr_vertex_stub->sptr_next_hop != NULL)
					{
					ospf_free_entire_list ( (OSPF_GENERIC_NODE*) sptr_vertex_stub->sptr_next_hop);
					}

				table_free ((void*) sptr_vertex_stub);

				sptr_vertex_stub = NULL;
				}
			}
		}

	return;
}
/**********************************************************************************************************************************/
static enum TEST ospf_check_if_vertex_is_reachable (ULONG vertex,OSPF_LS_DATABASE_ENTRY *sptr_database_entry)
{
	USHORT age;
	char print_buffer[PRINT_BUFFER_SIZE];

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

	age = sptr_database_entry->advertisement.sptr_router->ls_header.age;
	age = net_to_host_short (age);

	if ((sptr_database_entry == NULL) || (age == OSPF_MAXIMUM_AGE) ||
		(ospf_check_if_link_exists (&sptr_database_entry->advertisement, vertex, sptr_database_entry->sptr_ls_database_area) == FAIL))
		{
		OSPF_CONVERT_IP_ADDRESS_TO_DOT_FORMAT_FOR_DEBUG (print_buffer, vertex);

		OSPF_PRINTF_DEBUG (OSPF_DEBUG_PRINTF, "OSPF: Link does not exist    to vertex  %s \r\n", print_buffer);

		return (FAIL);
		}
	else