/* ospf_external_route_calculation.c - Calculate the external paths using the external lsas *//* Copyright 1998 - 2002 Wind River Systems, Inc. */#include "copyright_wrs.h"/*modification history--------------------02l,03jul03,ram    Re-added invalidation of learned external routes if maxaged02k,11jun03,ram    SPR#88965 Separate route table and LSDB hash parameters02j,22apr03,ram	   SPR#76812 Modifications for OSPF performance enhancements02i,17feb03,ram	   SPR 85432 Added supplemental changes to handle larger number of external routes02h,28jan03,ram	   SPR 85050 Added support for external route redistribution based on 				   OSPF external metric values02g,11dec02,ram	   SPR 84714 Added support for ospf type 1 external and re-calculation 				   of external routes when the most preferred one is deleted02f,05Dec02,smr    Fixed SPR 84815 for ANVL test 3.402e,22nov02,htm    Fix for TSR 297651 (SPR#83274).02d,19nov02,mwv    Merge TMS code SPR 8428402c,27aug02,jkw    Fix to external routing to find external routes in routing table.02b,18apr02,jkw    External 1583compatibility flooding.02a,16apr02,jkw    One copy of external and type 11 lsa01z,07feb02,jkw    Fix forwarding address with external lsa.01y,05feb02,kc     Modified ospf_install_the_external_area_path_to_N() to fix                   problem related to the neighbor router id problem.SPR #6565301x,13nov01,jkw    Change number of address ranges to ULONG01w,11oct01,jkw    Set pointer to NULL after table_free.01v,03sep01,jkw    Added Mistral changes for 2178 updates.01u,03may01,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.01r,07jul00,reshma Unix compatibility related changes.01q,04apr00,reshma Added some MIB support (Read only).Passed all important ANVL OSPF tests.01p,23dec99,reshma Compatibility with VxWorks-IP and VxWorks RTM-interface01o,12may99,jack   Changes related to equal cost multi path and                   ospf_set_patricia_route_change_status_on_ospf_rt_node01n,28dec98,jack   Compiled and added some comments01m,17nov98,jack   Added ospf_display_routing_table () on ASBR lookup failure01l,13nov98,jack   Changes related to introducing queuing in OSPF to RTM interface and                   bug fix on the external route additions path (to RTM)01k,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,04jun98,jack   Always sptr_routing_table_node_for_N->discard_entry = TRUE, must come                   after  Fn call spf_export_route_to_other_protocols (OSPF_REPLACE_PATH,                   ..... Therefore, this change is made01f,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_external_route_calculation.c is used for calculating the routes to external destinations.External routes are calculated using external lsas.This file is used when calculating the routing table for external routes.*/#include "ospf.h"#if defined (__OSPF_VIRTUAL_STACK__)#include "ospf_vs_lib.h"#endif /* __OSPF_VIRTUAL_STACK__ *//***********************************************************************************************************************************/static OSPF_ROUTING_TABLE_ENTRY *ospf_get_forwarding_address (UNION_OSPF_LINK_STATE_ADVERTISEMENT *advertisement,ULONG *sptr_distance_X,    OSPF_ROUTING_TABLE_ENTRY *sptr_routing_table_entry_for_ASBR);static void ospf_create_and_install_a_new_external_area_path_to_N (ULONG destination_N,    OSPF_ROUTING_TABLE_ENTRY *sptr_routing_table_entry_for_N,UNION_OSPF_LINK_STATE_ADVERTISEMENT *advertisement,    OSPF_ROUTING_TABLE_ENTRY *sptr_routing_table_entry_for_forwarding_address,    OSPF_ROUTING_TABLE_ENTRY *sptr_routing_table_entry_for_ASBR,ULONG distance_X,ULONG cost_Y,    enum BOOLEAN on_new_external_lsa_received_path);static void ospf_install_the_external_area_path_to_N (ULONG destination_N,OSPF_ROUTING_TABLE_ENTRY *sptr_routing_table_entry_for_N,    UNION_OSPF_LINK_STATE_ADVERTISEMENT *advertisement,OSPF_ROUTING_TABLE_ENTRY *sptr_routing_table_entry_for_forwarding_address,    OSPF_ROUTING_TABLE_ENTRY *sptr_routing_table_entry_for_ASBR,ULONG distance_X,ULONG cost_Y);static enum BOOLEAN ospf_install_new_external_path_based_on_cost (ULONG destination_N,    OSPF_ROUTING_TABLE_NODE *sptr_routing_table_node_for_N, ULONG distance_X,ULONG cost_Y,    UNION_OSPF_LINK_STATE_ADVERTISEMENT *advertisement, OSPF_ROUTING_TABLE_ENTRY *sptr_routing_table_entry_for_forwarding_address,    OSPF_ROUTING_TABLE_ENTRY *sptr_routing_table_entry_for_ASBR);static enum OSPF_ROUTING_TABLE_UPDATE_ACTION ospf_compare_costs_of_external_paths (OSPF_ROUTING_TABLE_ENTRY *sptr_routing_table_entry_for_N,    ULONG distance_X,ULONG cost_Y,ULONG tos0_metric);static void ospf_install_the_external_area_path_to_N_and_replace_rtm_route (ULONG destination_N,    OSPF_ROUTING_TABLE_NODE *sptr_routing_table_node_for_N, UNION_OSPF_LINK_STATE_ADVERTISEMENT *advertisement,    OSPF_ROUTING_TABLE_ENTRY *sptr_routing_table_entry_for_forwarding_address,    OSPF_ROUTING_TABLE_ENTRY *sptr_routing_table_entry_for_ASBR, ULONG distance_X,ULONG cost_Y);static void ospf_invalidate_external_route_entry (OSPF_EXTERNAL_LINK_ADVERTISEMENT_HEADER *sptr_external);/*************************************************************************** ospf_calculate_routes_to_external_destinations - traverse through all the external lsas** This routine will traverse through all the external link state* advertisements and calculate the paths to the external* destinations.** RETURNS: N/A** ERRNO: N/A** NOMANUAL*//*******************************************************************************//* section 16.4 of OSPF specification (page 160) */void ospf_calculate_routes_to_external_destinations (void){    OSPF_LS_DATABASE_HEAD *sptr_ls_database_head = NULL;    OSPF_LS_DATABASE_ENTRY *sptr_database_entry = NULL;    OSPF_LS_DATABASE_ENTRY *sptr_next_database_entry = NULL;    ULONG index;    OSPF_PRINTF_PROLOGUE (OSPF_PROLOGUE_PRINTF, "OSPF: Entering ospf_calculate_routes_to_external_destinations\r\n");	/* Check for external lsdb */    for (index = 0x00000000L, sptr_ls_database_head = &(ospf.external_database_hash_table[LS_EXTERNAL_LSA][index]); /* for each hash list */        index < OSPF_HASH_TABLE_SIZE; ++index, sptr_ls_database_head = &(ospf.external_database_hash_table[LS_EXTERNAL_LSA][index]))        {        if (sptr_ls_database_head == NULL)			{            continue;            }        /* SPR#76812 */       	for (sptr_database_entry = sptr_ls_database_head->sptr_linear_database_entry;       		sptr_database_entry != NULL;       	    sptr_database_entry = sptr_next_database_entry)            {			sptr_next_database_entry = sptr_database_entry->sptr_forward_link;            if (sptr_database_entry->advertisement.sptr_external != NULL)                {                ospf_calculate_routes_to_a_single_external_destination (&(sptr_database_entry->advertisement), FALSE);                }            }        }    return;}/* SPR#76812 *//*************************************************************************** ospf_calculate_routes_to_a_single_external_destination - create a new routing table entry for the external destination** This routine will calculate the external path to the external* destination and call the function to create the new routing* table entry for that path.** <advertisement> Advertisement to be examined** <on_new_external_lsa_received_path> Boolean to see if external lsa was received on new path** RETURNS: N/A** ERRNO: N/A** NOMANUAL*//*******************************************************************************//* section 16.4 of OSPF specification (page 160) */void ospf_calculate_routes_to_a_single_external_destination (UNION_OSPF_LINK_STATE_ADVERTISEMENT *advertisement,    enum BOOLEAN on_new_external_lsa_received_path){    ULONG destination_N =0;    ULONG autonomous_system_boundary_router =0;    OSPF_ROUTING_TABLE_ENTRY *sptr_routing_table_entry_for_ASBR =NULL;    OSPF_ROUTING_TABLE_ENTRY *sptr_routing_table_entry_for_forwarding_address =NULL;    OSPF_ROUTING_TABLE_ENTRY *sptr_routing_table_entry_for_N =NULL;    OSPF_ROUTING_TABLE_NODE *sptr_routing_table_node_for_N =NULL;    ULONG distance_X =0;    ULONG cost_Y =0;    ULONG tos0_metric =0;    USHORT age =0;	OSPF_ROUTING_TABLE_ENTRY *sptr_routing_table_entry_for_1583 = NULL;    ULONG tos0_forwarding_address = 0;	ULONG network_mask = 0;	/* SPR 85050 -- Begin */	enum OSPF_ROUTING_TABLE_UPDATE_ACTION action;	OSPF_LS_DATABASE_ENTRY *sptr_external_database_entry = NULL;	/* SPR 85050 -- End */    OSPF_PRINTF_PROLOGUE (OSPF_PROLOGUE_PRINTF, "OSPF: Entering ospf_calculate_routes_to_a_single_external_destination\r\n");    tos0_metric = net_to_host_long (advertisement->sptr_external->tos0_metric);    age = net_to_host_short (advertisement->sptr_external->ls_header.age);    autonomous_system_boundary_router = net_to_host_long (advertisement->sptr_external->ls_header.advertising_router);	/* SPR 85050 -- Begin */	/* SPR 84714 -- Begin */    if ( ((tos0_metric & OSPF_LSInfinity) == OSPF_LSInfinity) || (age >= OSPF_MAXIMUM_AGE) )       {		  /* If the route is not self originated clean it up		   * self originated routes are taken care of the aging process */		  if(autonomous_system_boundary_router != ospf.router_id)		  {		  	ospf_invalidate_external_route_entry (advertisement->sptr_external);			ospf_display_routing_table ();		  }	      return;                                     /* section 16.4, items (1 & 2) (page 160) */       }    /* SPR 84714 -- End */	/* SPR 84714 -- Begin */	cost_Y = (tos0_metric & OSPF_LSInfinity);    /* SPR 84714 -- End */    destination_N = net_to_host_long (advertisement->sptr_external->ls_header.id);    /* Fix for SPR# 297651 (SPR#83274) */    sptr_routing_table_node_for_N = ospf_find_router_or_network_routing_table_node (destination_N, advertisement->sptr_external->ls_header.type,                                                                                    OSPF_ROUTE_PATH_TYPE_WILDCARD, NULL);    if (sptr_routing_table_node_for_N != NULL)        {        sptr_routing_table_entry_for_N = sptr_routing_table_node_for_N->sptr_routing_table_entry;        /* SPR 85432 Supplemental -- Begin */        /* Check if routing table entry is inter or intra */        if((sptr_routing_table_entry_for_N->path_type == OSPF_ROUTE_PATH_TYPE_INTRA) ||           (sptr_routing_table_entry_for_N->path_type == OSPF_ROUTE_PATH_TYPE_INTER))           {			   return;		   }		/* SPR 85432 Supplemental -- End */        }    else        {        sptr_routing_table_entry_for_N = NULL;        }    /* We have to compare external routes learned from neighbors with     * the same route originated by this router. Originated routes are     * not installed in the OSPF routing table because no ASBR routing     * table entry exists for it and no forwarding address. Thus we must     * do the comparison here before we proceed.     * If the route is self originated and the route was learned from a     * neighbor compare the metrics, if the self originated is better     * the one learned from the neighbor is removed from the OSPF and     * kernel routing table.     * If the route is learned from the neighbor and the same route was     * originated by this router, compare the metrics and if the self     * originated one is better don't install it the OSPF and kernel routing     * table.*/     if(autonomous_system_boundary_router == ospf.router_id)     {    	if (sptr_routing_table_node_for_N != NULL)        {			/* The same route was learned from a neighbor */        	/* Compare the metrics of the self originated route with the one in the routing table        	 * the distance is considered zero for self originated type 1 externals */			action = ospf_compare_costs_of_external_paths (sptr_routing_table_entry_for_N, 0, cost_Y, tos0_metric);			/* if the same or better metric remove the route entry in the routing table */			if(action == OSPF_REPLACE_PATH)			{				/* Remove the entry in the routing table */				ospf_invalidate_routing_table_entry (sptr_routing_table_node_for_N, advertisement->sptr_external->network_mask, destination_N, NULL);        	}		}		return;	}	else	{		/* This external route is learned from a neighbor */		/* If a self originated route exists and is most preferred compare the metrics */		/* To avoid unnessary lookups, if the routing table entry is not null that means		 * even if a self originated route exists its not the most preferred one and there		 * is no point in comparing metrics with it */		if(sptr_routing_table_node_for_N == NULL)		{			/* SPR#76812 */			sptr_external_database_entry = ospf_find_LSA (NULL, destination_N,ospf.router_id, OSPF_LS_AS_EXTERNAL);			if((sptr_external_database_entry != NULL) &&			  (net_to_host_short(sptr_external_database_entry->advertisement.sptr_external->ls_header.age) < OSPF_MAXIMUM_AGE))			{				if(ospf_compare_costs_of_external_lsdb_entries(tos0_metric,						net_to_host_long(sptr_external_database_entry->advertisement.sptr_external->tos0_metric)) == FALSE)				{					/* Newly added external route is less preferred than self originated one */					return;				}			}		}	}    /* SPR 85050 -- End */	/* SPR#76812 -- Begin */	sptr_routing_table_entry_for_ASBR = ospf_find_routing_table_entry_1583_asbr(autonomous_system_boundary_router);	/* SPR#76812 -- End */	if (sptr_routing_table_entry_for_ASBR == NULL) /* ASBR is unreachable */        {        OSPF_PRINTF_ROUTING_TABLE (OSPF_ROUTING_TABLE_PRINTF, "OSPF_ROUTING_TABLE: ---------> EXT LSA - Did not add route to ext destination- Destinatin:%lx (LSA queued) - Reason - No route to ASBR \r\n",            net_to_host_long (advertisement->sptr_external->ls_header.id));        return;                                     /* section 16.4, item (3) (pages 160-161) */        }    sptr_routing_table_entry_for_forwarding_address = ospf_get_forwarding_address (advertisement, &distance_X, sptr_routing_table_entry_for_ASBR);    if ((sptr_routing_table_entry_for_forwarding_address == NULL) && (distance_X == 0x00000000L))        {        return;        }	else if (sptr_routing_table_entry_for_forwarding_address != NULL)		{		if ((sptr_routing_table_entry_for_forwarding_address->path_type != OSPF_ROUTE_PATH_TYPE_INTRA) &&			(sptr_routing_table_entry_for_forwarding_address->path_type != OSPF_ROUTE_PATH_TYPE_INTER))    /* an intra area or inter area path must therefore exist to this forwarding adress */			{			return;			}		}    if (sptr_routing_table_entry_for_N == NULL)     /* section 16.4, item (4) (page 161) */    {        ospf_create_and_install_a_new_external_area_path_to_N (destination_N, sptr_routing_table_entry_for_N, advertisement,            sptr_routing_table_entry_for_forwarding_address, sptr_routing_table_entry_for_ASBR, distance_X, /*#$-NOTE:note57-$#*/            cost_Y, on_new_external_lsa_received_path);		return;    }	else	{		if (ospf.ospf_rfc1583_compatibility == FALSE)		{		    tos0_forwarding_address = net_to_host_long (advertisement->sptr_external->tos0_forwarding_address);    	    network_mask = net_to_host_long (advertisement->sptr_external->network_mask);		    tos0_forwarding_address = tos0_forwarding_address & network_mask;			/* SPR#76812 -- Begin */			if (tos0_forwarding_address != 0x00000000)			{				sptr_routing_table_entry_for_1583 = ospf_find_routing_table_entry_1583_asbr(tos0_forwarding_address);			}			else			{				sptr_routing_table_entry_for_1583 =	ospf_find_routing_table_entry_1583_asbr(autonomous_system_boundary_router);			}			/* SPR#76812 -- End */			if (sptr_routing_table_entry_for_1583 == NULL)			{				ospf_create_and_install_a_new_external_area_path_to_N (destination_N, sptr_routing_table_entry_for_N, advertisement,				    sptr_routing_table_entry_for_forwarding_address, sptr_routing_table_entry_for_ASBR, distance_X, /*#$-NOTE:note57-$#*/					cost_Y, on_new_external_lsa_received_path);				return;			}		}		ospf_install_new_external_path_based_on_cost (destination_N, sptr_routing_table_node_for_N, distance_X, cost_Y,			advertisement, sptr_routing_table_entry_for_forwarding_address, sptr_routing_table_entry_for_ASBR); /*#$-NOTE:note56-$#*/