/* 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 ranges02j,22apr03,ram	SPR#76812 Modifications for OSPF performance enhancements02i,29jan03,asr Fix for SPR# 85573.02h,07jan02,agi Fixed SPR#78251, ANVL 4.202g,22nov02,htm Fix SPR#8327402f,05aug02,jkw Fix TSR 28803002e,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 paths01x,26jun01,jkw Added updates for multiple path destination01w,20jun01,jkw Added unnumbered link support01v,03may01,jkw Added checks for NULL pointers and alarm messages01u,26sep00,reshma Added WindRiver CopyRight01t,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-interface01p,13aug99,jack   compilation fixes no IP case01o,12may99,jack   Changes related to equal cost multi path and			  ospf_set_patricia_route_change_status_on_ospf_rt_node01n,12may99,jack   fixes for equal cost multipath01m,11may99,jack	  Fixes related to equal cost multi path 01l,10may99,jack	  Multipath fixes01k,28dec98,jack   Compiled and added some comments01j,11nov98,jack   Config changes, linted and big endian changes01i,30oct98,jack   Incorporate changes for compilation on Vxworks01h,23aug98,jack   ANVL tested OSPF with PATRICIA tree route table and no recursion01g,10aug98,jack   PATRICIA Route Table Based OSPF Code Base01f,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_shortest_path_calculation.c is used for creating the shortest path for intra-arearoute calculations and stub networks.  This file will call the dijkstra algorithm for eacharea.  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