/* ospf_routing_table.c *//* Copyright 2000-2003 Wind River Systems, Inc. */#include "copyright_wrs.h"/*modification history___________________02r,22jul03,agi    Fixed compiler warning02q,09jun03,htm    SPR#87382 - Fix for ANVL 4.202p,11jun03,ram    SPR#88965 Separate route table and LSDB hash parameters02o,22may03,kkz    SPR 88613 - area aggregation, including correct use of "active" flag for address ranges, to track                   active links02n,22apr03,ram	   SPR#76812 Modifications for OSPF performance enhancements02m,07jan03,agi    Added SPR#78251, ANVL 4.2 fix02l,06jan03,dsk    Fix for SPR#75194, ANVL 27.1502k,22nov02,htm    Fix for TSR# 297651 (SPR# 83274).02j,02dec02,kkz    Fix SPR 8456702i,22nov02,hme    Fix for SPR 8327402h,19nov02,mwv    Merge TMS code SPR 8428402g,18oct02,hme    As part of the TSR 291001, call                   ospf_export_route_to_other_protocols() with OSPF_DELETE_PATH 02f,08oct02,agi    Fixed compiler warning02e,05aug02,jkw    Fix TSR 288035 and TSR 28803002d,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 messages01y,26sep00,reshma Added WindRiver CopyRight01x,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-interface01t,13aug99,jack   compilation fixes no IP case01s,12may99,jack   Changes related to equal cost multi path and                   ospf_set_patricia_route_change_status_on_ospf_rt_node01r,12may99,jack   Fix in ospf_get_new_next_hop_blocks_and_mark_ospf_rt_node_new01q,12may99,jack   Changes in function                   ospf_get_new_next_hop_blocks_and_mark_ospf_rt_node_new01p,10may99,jack   Changes in prototypes and call and declaration of                   ospf_get_new_next_hop_blocks01o,10may99,jack   Changes related to ospf_get_new_next_hop_blocks01n,28dec98,jack   Compiled and added some comments01m,30nov98,jack   Removed C++ style comments and removed some commented out code01l,23nov98,jack   Changed %p in printing to %lx01k,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 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_routing_table.c is used for calculating and building a new routing table.  This file willcall the appropriate functions to build the intra-area, inter-area, and external paths forbuilding 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*/