ospf_dijkstra.c

vxworks下ospf协议栈

/* ospf_dijkstra.c - Executes the dijkstra algorithm for the shortest path */

/* Copyright 1998 - 2003 Wind River Systems, Inc. */

/*
modification history
--------------------
02w,20jun03,htm SPR# 87386 - Added ospf_check_if_net_link_exists() to check if a link
                exists to a transit network in the router LSA of the attached router   
02v,26may03,agi Changed rwos_get_system_elapsed_time_second() to
                ospf_get_system_elapsed_time_second()
02u,15may03,htm	SPR#86907 Vitual link is not included in router-LSA for the 
                backbone
02t,22apr03,ram	SPR#76812 Modifications for OSPF performance enhancements
02s,11feb03,kkz SPR 86188 - fix ospf_examine_router_link_advertisement_for_vertex_V to
                correctly increment router links to avoid page fault
02r,03feb03,dsk SPR 86030 - avoid reading from null pointer
02q,27jan03,mwv SPR 85572 - initialize Vertex W in ospf_set_intervening_router ()                            
02p,07jan03,agi Fixed SPR#84719
02o,07jan03,agi Fixed compilation error
02n,03dec02,ram SPR 84312 - Change elapsed time to return seconds
02m,01dec02,dsk	Fix for ANVL 5.3 SPR# 83333
02l,19nov02,mwv Merge TMS code SPR 84284
02k,15nov02,dsk SPR 84180 - Fixed Dijkstra computation of the routing
                table for unnumbered links.
02j,07oct02,agi Fixed compiler warnings
02i,05aug02,jkw	Fix for TSR 288030.
02h,10jul02,jkw	Fix UNH 5.3 test.
02g,24apr02,jkw	Fix UNH 4.4 test.
02f,30jan02,jkw	Fix routes not being propagated.
02e,20dec01,jkw	Removed sptr_area->sptr_interfaces structure.
02d,09nov01,jkw	Null pointer check.
02c,11oct01,jkw	Set pointer to NULL after table_free.
02b,03Sep01,jkw	Added Mistral updates for next hop calculation.
02a,01jun01,jkw	Added updates for multiple path destination for inter area
01z,26jun01,jkw	Added updates for multiple path destination
01y,20jun01,jkw	Added unnumbered link support
01x,03may01,jkw	Added checks for NULL pointers and alarm messages
01w,26sep00,reshma	Added WindRiver CopyRight
01v,25sep00,reshma	RFC-1587 implementation for OSPF NSSA Option, also 
			tested against ANVL.
01u,07jul00,reshma	Unix compatibility related changes.
01t,04apr00,reshma	Added some MIB support (Read only).Passed all important
			ANVL OSPF tests.
01s,23dec99,reshma	Compatibility with VxWorks-IP and VxWorks RTM-interface
01r,12may99,jack		Changes related to equal cost multi path and
			ospf_set_patricia_route_change_status_on_ospf_rt_node
01q,12may99,jack		Fixes for equal cost multipath
01p,10may99,jack		Changes in prototypes and call and declaration of
			ospf_get_new_next_hop_blocks
01o,06jan99,jack	Added a new function ospf_check_and_mark_area_address_
			range
01n,05jan99,jack	Fixed the mask settings here
01m,05jan99,jack	Fixed the mask setting on ASBR and ABR routes
01l,28dec98,jack	Compiled and added some comments
01k,11nov98,jack	Config changes, linted and big endian changes
01j,30oct98,jack	Incorporate changes for compilation on Vxworks
01i,23aug98,jack	ANVL tested OSPF with PATRICIA tree route table and no 
			recursion
01h,10aug98,jack	PATRICIA Route Table Based OSPF Code Base
01g,19jun98,jack	Listroutine changes. OSPF add and delete list routines,
			eventually call the rwutils list routines.
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_dijkstra.c is used for calculating the shortest path first algorithm for an
intra area path.

This file is used whenever OSPF needs to recalculate the routing table for an
area.
*/


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

/******************************************************************************/
/* SPR 86907  -- Begin */
extern OSPF_ROUTING_TABLE_ENTRY* ospf_find_routing_table_entry_for_ABR(ULONG destination_id_to_look, ULONG area_id);
/* SPR 86907  -- End */
/* SPR 87386 - Begin */
enum TEST ospf_check_if_net_link_exists (OSPF_NETWORK_LINK_ADVERTISEMENT_HEADER *sptr_network, 
                                         OSPF_ROUTER_LINK_ADVERTISEMENT_HEADER *sptr_router);
/* SPR 87386 - End */

static void ospf_examine_advertisements_associated_with_vertex_V (OSPF_AREA_ENTRY *sptr_area,OSPF_SHORTEST_PATH_NODE *sptr_shortest_path_node);
static void ospf_examine_router_link_advertisement_for_vertex_V (OSPF_ROUTER_LINK_ADVERTISEMENT_HEADER *sptr_router_link_advertisement,
	OSPF_AREA_ENTRY *sptr_area,OSPF_SHORTEST_PATH_NODE *sptr_vertex_V);
static void ospf_examine_network_link_advertisement_for_vertex_V (OSPF_NETWORK_LINK_ADVERTISEMENT_HEADER *sptr_network_link_advertisement,
	OSPF_AREA_ENTRY *sptr_area,OSPF_SHORTEST_PATH_NODE *sptr_vertex_V);
static enum TEST ospf_check_if_vertex_W_is_already_on_the_shortest_path_tree (OSPF_AREA_ENTRY *sptr_area,ULONG vertex_W, BYTE_ENUM (OSPF_LS_TYPE)	ls_type);
static OSPF_SHORTEST_PATH_NODE *ospf_find_vertex_W_on_candidate_list (OSPF_SHORTEST_PATH_NODE *sptr_candidate,ULONG vertex_W, BYTE_ENUM (OSPF_LS_TYPE)	link_type);
static OSPF_SHORTEST_PATH_NODE *ospf_choose_closest_vertex_to_root (OSPF_SHORTEST_PATH_NODE *sptr_candidate);
static void ospf_add_closest_vertex_to_shortest_path_tree (OSPF_SHORTEST_PATH_NODE *sptr_vertex_to_add,OSPF_AREA_ENTRY *sptr_area);
static void ospf_add_routing_table_entry_for_area_border_router (OSPF_SHORTEST_PATH_NODE *sptr_vertex_V,OSPF_AREA_ENTRY *sptr_area);
static void ospf_add_routing_table_entry_for_autonomous_system_boundary_router (OSPF_SHORTEST_PATH_NODE *sptr_vertex_V,OSPF_AREA_ENTRY *sptr_area);
static void ospf_add_routing_table_entry_for_transit_network (OSPF_SHORTEST_PATH_NODE *sptr_vertex_V,OSPF_AREA_ENTRY *sptr_area);
static OSPF_LS_DATABASE_NODE *ospf_find_only_the_router_or_network_LSAs_advertised_by_vertex_V (ULONG vertex_V,OSPF_AREA_ENTRY *sptr_area, BYTE_ENUM (OSPF_LS_TYPE) link_type_of_vertex);
static enum TEST ospf_set_next_hop_for_abr_or_asbr (OSPF_ROUTING_TABLE_ENTRY	*sptr_routing_table_entry, OSPF_AREA_ENTRY *sptr_area, OSPF_SHORTEST_PATH_NODE *sptr_vertex_V);
static void ospf_add_non_stub_intra_area_entry_to_ospf_routing_table (OSPF_SHORTEST_PATH_NODE *sptr_vertex_V, OSPF_AREA_ENTRY *sptr_area);
static OSPF_ROUTING_TABLE_NODE* ospf_add_fields_to_ospf_route_entry (ULONG destination_id_for_vertex_V, ULONG address_mask_for_vertex_V, OSPF_SHORTEST_PATH_NODE *sptr_vertex_V,
	OSPF_AREA_ENTRY *sptr_area, enum OSPF_ROUTE_DESTINATION_TYPE ospf_route_destination_type);
static void ospf_check_and_mark_area_address_range (ULONG destination_id_for_vertex_V, OSPF_AREA_ENTRY *sptr_area);
/******************************************************************************/
/* section 16.1, first stage (page 151-154) */


/*******************************************************************************
*
* ospf_run_dijkstra - calculates the shortest path tree for a particular area
*
* This routine will run the dijkstra algorithm for a particular area.
*
* <sptr_area> OSPF area
*
* RETURNS: 	N/A
*
* ERRNO: N/A
*
* NOMANUAL
*/
void ospf_run_dijkstra (OSPF_AREA_ENTRY *sptr_area)
{
	OSPF_SHORTEST_PATH_NODE *sptr_vertex_V =NULL;
	OSPF_SHORTEST_PATH_NODE *sptr_vertex_P =NULL;
	OSPF_SHORTEST_PATH_NODE *sptr_vertex_to_add =NULL;
	enum BOOLEAN done;

	OSPF_PRINTF_PROLOGUE (OSPF_PROLOGUE_PRINTF, "OSPF: Entering ospf_run_dijkstra\r\n");

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

	
    sptr_vertex_V = &sptr_area->shortest_path_first_tree;				/* start at the root */
	sptr_area->number_of_area_border_routers = 0;
	sptr_area->number_of_autonomous_system_boundary_routers = 0;
	sptr_area->nssa_abr_to_convert_type_7_to_type_5 = 0;

	done = FALSE;

	do
		{
		ospf_examine_advertisements_associated_with_vertex_V (sptr_area, sptr_vertex_V);

		if (sptr_area->sptr_candidate == NULL)
			{
			done = TRUE;
			}
		else
			{
			sptr_vertex_to_add = ospf_choose_closest_vertex_to_root (sptr_area->sptr_candidate);

			ospf_add_closest_vertex_to_shortest_path_tree (sptr_vertex_to_add, sptr_area);

			sptr_vertex_P = sptr_vertex_V;

			sptr_vertex_V = sptr_vertex_to_add;

			OSPF_PRINTF_ROUTING_TABLE (OSPF_ROUTING_TABLE_PRINTF, "==========++++++++++>>>>>PARENT VERTEX:%lx, Parent vertex_type:%x, Parent vertex cost:%d ADDING FOLLOWING VERTEX TO THE SPT: vertex:%lx, vertex_type:%x, vertex_cost:%d  \r\n",
				sptr_vertex_P->vertex, sptr_vertex_P->vertex_type, sptr_vertex_P->cost, sptr_vertex_V->vertex, sptr_vertex_V->vertex_type, sptr_vertex_V->cost);

			ospf_add_non_stub_intra_area_entry_to_ospf_routing_table (sptr_vertex_V, sptr_area);    /* It can be an entry for ABR, ASBR or transit network or combination of any of these */
			}
		}
	while (done == FALSE);

	return;
}

/**************************************************************************************
*
* ospf_examine_advertisements_associated_with_vertex_V - examines advertisements associated with vertex
*
* This routine will call the functions to find all network and router lsas associated with the vertex
* and call the functions to examine the router and network lsas to build the shortest path tree.
*
* <sptr_area> OSPF area
*
* <sptr_shortest_path_node> Shortest path node for building the routing table
*
* RETURNS: 	N/A
*
* ERRNO: N/A
*
* NOMANUAL
*/
/*******************************************************************************************//* section 16.1, item (2) (page 151) */
static void ospf_examine_advertisements_associated_with_vertex_V (OSPF_AREA_ENTRY *sptr_area,OSPF_SHORTEST_PATH_NODE *sptr_shortest_path_node)
{
	OSPF_LS_DATABASE_NODE *sptr_vertex_V_advertisements =NULL;
	OSPF_LS_DATABASE_NODE *sptr_database_node= NULL;
	OSPF_LS_DATABASE_ENTRY *sptr_database_entry =NULL;

	OSPF_PRINTF_PROLOGUE (OSPF_PROLOGUE_PRINTF, "OSPF: Entering ospf_examine_advertisements_associated_with_vertex_V\r\n");

	OSPF_PRINTF_ROUTING_TABLE (OSPF_ROUTING_TABLE_PRINTF, "|||||----->>>>>OSPF:   Finding all LSAs by vertex which is added to SPT (in HEX): %lx for dijkestra   and vertex type:%x<<<<<-----\r\n",
		sptr_shortest_path_node->vertex, sptr_shortest_path_node->vertex_type);

	sptr_vertex_V_advertisements = ospf_find_only_the_router_or_network_LSAs_advertised_by_vertex_V  (sptr_shortest_path_node->vertex, sptr_area, sptr_shortest_path_node->vertex_type);

	for (sptr_database_node = sptr_vertex_V_advertisements; sptr_database_node != NULL;
		sptr_database_node = sptr_database_node->sptr_forward_link)
		{
		sptr_database_entry = sptr_database_node->sptr_ls_database_entry;

        if ( sptr_database_entry == NULL )
            continue;

		switch (sptr_database_entry->advertisement.sptr_router->ls_header.type)
			{
			case OSPF_LS_ROUTER:
				{
				ospf_examine_router_link_advertisement_for_vertex_V (sptr_database_entry->advertisement.sptr_router, sptr_area,
					sptr_shortest_path_node);

				break;
				}


			case OSPF_LS_NETWORK:
				{
				ospf_examine_network_link_advertisement_for_vertex_V (sptr_database_entry->advertisement.sptr_network, sptr_area,
					sptr_shortest_path_node);

				break;
				}

			default:
				{
				break;
				}
			}
		}
	    if ( sptr_vertex_V_advertisements != NULL )
		   {
			(void) ospf_free_entire_list ((OSPF_GENERIC_NODE *) sptr_vertex_V_advertisements);
			}

	return;
}

/*******************************************************************************
*
* ospf_find_only_the_router_or_network_LSAs_advertised_by_vertex_V - finds link state advertisements associated with vertex
*
* This routine will find all network and router lsas associated with the vertex
*
* <vertex_V> Vertex on router OSPF is examining
*
* <sptr_area> OSPF area
*
* <link_type_of_vertex> Type of vertex we are examining
*
* RETURNS: 	OSPF_LS_DATABASE_NODE * or NULL
*
* ERRNO: N/A
*
* NOMANUAL
*/

static OSPF_LS_DATABASE_NODE *
ospf_find_only_the_router_or_network_LSAs_advertised_by_vertex_V
    (
    ULONG vertex_V,
    OSPF_AREA_ENTRY *sptr_area,
    BYTE_ENUM (OSPF_LS_TYPE) link_type_of_vertex
    )
{
	OSPF_LS_DATABASE_NODE *sptr_first_database_node =NULL;
	enum OSPF_LS_TYPE ls_type;
	ULONG index =0;
	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 database_entry_advertising_router =0;
	OSPF_LS_DATABASE_NODE *sptr_database_node =NULL;
	OSPF_INTERFACE *sptr_interface =NULL;

	OSPF_PRINTF_PROLOGUE (OSPF_PROLOGUE_PRINTF, "OSPF: Entering ospf_find_only_the_router_or_network_LSAs_advertised_by_vertex_V\r\n");

	sptr_interface = NULL;

	PARAMETER_NOT_USED (sptr_interface);

	sptr_first_database_node = NULL;


	for (ls_type = OSPF_LS_ROUTER; ls_type <= OSPF_LS_NETWORK; ++ls_type)
		{
		for (index = 0x00000000L, sptr_ls_database_head = &(sptr_area->ls_database_hash_table[ls_type][index]);
			index < OSPF_HASH_TABLE_SIZE; ++index, sptr_ls_database_head = &(sptr_area->ls_database_hash_table[ls_type][index]))
			{
	        /* 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;

				database_entry_advertising_router = sptr_database_entry->advertisement.sptr_router->ls_header.advertising_router;
				database_entry_advertising_router = net_to_host_long (database_entry_advertising_router);

				if ( (vertex_V == database_entry_advertising_router) && (sptr_database_entry->advertisement.sptr_router->ls_header.type == OSPF_LS_ROUTER)
					 && (link_type_of_vertex == sptr_database_entry->advertisement.sptr_router->ls_header.type))
					{
					OSPF_PRINTF_DEBUG (OSPF_DEBUG_PRINTF, "OSPF:   ADDING THIS NODE and ***************VERTEX: (HEX) %lx ************************\r\n", vertex_V);

					sptr_database_node = (OSPF_LS_DATABASE_NODE *) table_malloc (1, sizeof (OSPF_LS_DATABASE_NODE));

					if (sptr_database_node != NULL)
						{
						memset (sptr_database_node, 0x00, sizeof (OSPF_LS_DATABASE_NODE));

						sptr_database_node->sptr_ls_database_entry = sptr_database_entry;

						if (sptr_first_database_node == NULL)
							{
							sptr_first_database_node = sptr_database_node;
							}
						else
							{
							ospf_add_node_to_end_of_list ((OSPF_GENERIC_NODE *) sptr_database_node, (OSPF_GENERIC_NODE *) sptr_first_database_node);
							}
						}
					else
						{
						ospf_print_memory_error_message_and_free_buffer_if_necessary ((void *)NULL , "OSPF_LS_DATABASE_NODE");
						}
					}
					/* For this vertex, process network links and other stubs : This was missing before  */
				else if ( (vertex_V == net_to_host_long (sptr_database_entry->advertisement.sptr_router->ls_header.id)) && (sptr_database_entry->advertisement.sptr_router->ls_header.type == OSPF_LS_NETWORK)
					&& (link_type_of_vertex == sptr_database_entry->advertisement.sptr_router->ls_header.type) )
					{