/* ospf_routing_table_lookups.c *//* Copyright 2000 Wind River Systems, Inc. *//*modification history___________________ 02b,11jun03,ram            SPR#88965 Separate route table and LSDB hash parameters 02a,22apr03,ram	   		SPR#76812 Modifications for OSPF performance enhancements 35,18april02,jkw			External 1583compatibility flooding. 34,04march02,bt			modified highest cost for RFC2328 and lowest cost for RFC1583 19,11october01,jkw			Set pointer to NULL after table_free. 22,22september01,kc		Replaced ospf_get_port_number() with ospf_validate_interface().							No longer reference to port number. 21,3september01,jkw		Added Mistral updates for NULL pointer checks. 20,3may01,jkw				Added checks for NULL pointers and alarm messages 19,26september00,reshma	Added WindRiver CopyRight 18,25september00,reshma	RFC-1587 implementation for OSPF NSSA Option, also tested against ANVL. 17,07july00,reshma			Unix compatibility related changes. 16,04april00,reshma		Added some MIB support (Read only).Passed all important ANVL OSPF tests. 15,23december99,reshma		Compatibility with VxWorks-IP and VxWorks RTM-interface 14,13august99,jack			compilation fixes no IP case 13,19july99,jack			changed port comparision from 0x9999 to NO_SUCH_PORT 12,12july99,jack			Added table_free in ospf_find_route_and_update_cache 11,28december98,jack		Compiled and added some comments 10,11november98,jack		Config changes, linted and big endian changes 09,30october98,jack		Incorporate changes for compilation on Vxworks 08,23august98,jack			ANVL tested OSPF with PATRICIA tree route table and no recursion 07,10august98,jack			PATRICIA Route Table Based OSPF Code Base 06,04june98,jack			Integration with RTM and BGP 05,24april98,jack			RTM changes 04,10july97,cindy			Pre-release v1.52b 03,02october97,cindy		Release Version 1.52 02,22october96,cindy		Release Version 1.50 01,05june96,cindy			First Beta Release*//*DESCRIPTIONospf_routing_table_lookups.c is used for finding routing table entries in the routing table.This file is used whenever a lookup for a routing table entry needs to take place.*/#include "ospf.h"#if defined (__OSPF_VIRTUAL_STACK__)#include "ospf_vs_lib.h"#endif /* __OSPF_VIRTUAL_STACK__ *//* SPR#76812 -- Begin *//***********************************************************************************************************************************/static void ospf_insert_discard_entries_into_the_routing_table (OSPF_ROUTING_TABLE_NODE *sptr_discard_entries);static void ospf_select_most_specific_match_from_remaining_set (OSPF_ROUTING_TABLE_NODE **ptr_to_sptr_first_node,	USHORT *usptr_number_of_entries);static void ospf_remove_discard_entries_from_the_routing_table (void);static void ospf_select_complete_set_of_matching_entries_from_the_routing_table (ULONG destination_ip_address,	OSPF_ROUTING_TABLE_NODE **ptr_to_sptr_first_matching_node, USHORT *usptr_number_of_entries);static void ospf_reduce_set_to_those_having_the_most_preferential_path_type (OSPF_ROUTING_TABLE_NODE **ptr_to_sptr_first_node,	USHORT *usptr_number_of_entries);/**********************************************************************************************************************************//***************************************************************************//* section 11.1 of OSPF specification (page 100-101) */OSPF_ROUTING_TABLE_ENTRY *ospf_routing_table_lookup (ULONG destination_ip_address,ULONG type_of_service,	OSPF_ROUTING_TABLE_NODE *sptr_routing_table_node_from_patricia){	OSPF_AREA_ENTRY *sptr_area = NULL;	OSPF_AREA_ENTRY *sptr_next_area = NULL;	OSPF_ADDRESS_RANGE_LIST_ENTRY *sptr_address_range;	OSPF_ROUTING_TABLE_NODE *sptr_routing_table_node;	OSPF_ROUTING_TABLE_ENTRY *sptr_routing_table_entry;	USHORT number_of_entries;	PARAMETER_NOT_USED(type_of_service);	PARAMETER_NOT_USED(sptr_routing_table_node_from_patricia);	/* "Discard" entries are necessary to ensure that route summarization at area boundaries will not cause packet looping. */	OSPF_PRINTF_DEBUG (OSPF_DEBUG_PRINTF, "OSPF: Entering ospf_routing_table_lookup\r\n");	sptr_routing_table_node = NULL;	number_of_entries = 0x0000;	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->sptr_address_ranges != NULL)			{			for (sptr_address_range = sptr_area->sptr_address_ranges; sptr_address_range != NULL;				sptr_address_range = sptr_address_range->sptr_forward_link)				{				if (sptr_address_range->active == TRUE)				/* for each active area address range */					{					ospf_insert_discard_entries_into_the_routing_table (sptr_address_range->sptr_discard_entries);					}				}			}		}	ospf_select_complete_set_of_matching_entries_from_the_routing_table (destination_ip_address, &sptr_routing_table_node,		&number_of_entries);	 /* NEWRT LOOKUP */																	/* section 11.1, item (1) (page 101) */	if (sptr_routing_table_node == NULL)		{		return (NULL);		}	ospf_select_most_specific_match_from_remaining_set (&sptr_routing_table_node, &number_of_entries);/* section 11.1, item (3) (page 101) */	/* RFC 2328 G.4 */	if (number_of_entries > 0x0001)																					/* section 11.1, item (4) (page 101) */		{		ospf_reduce_set_to_those_having_the_most_preferential_path_type (&sptr_routing_table_node,			&number_of_entries);																								/* section 11.1, item (2) (page 101) */		}	if (number_of_entries == 0x0000)		{		sptr_routing_table_node->sptr_routing_table_entry = NULL;		}	ospf_remove_discard_entries_from_the_routing_table ();	sptr_routing_table_entry = sptr_routing_table_node->sptr_routing_table_entry;	if (sptr_routing_table_node != NULL)		{		ospf_free_entire_list ((OSPF_GENERIC_NODE*) sptr_routing_table_node);		}	return (sptr_routing_table_entry);}/****************************************************************************************//* section 11.1, item (1) (page 101) */static void ospf_select_complete_set_of_matching_entries_from_the_routing_table (ULONG destination_ip_address,	OSPF_ROUTING_TABLE_NODE **ptr_to_sptr_first_matching_node, USHORT *usptr_number_of_entries){	OSPF_ROUTING_TABLE_NODE *sptr_previous_node;	OSPF_ROUTING_TABLE_NODE *sptr_matching_node;	OSPF_ROUTING_TABLE_NODE *sptr_routing_table_node;	ULONG hash_id;	OSPF_PRINTF_DEBUG (OSPF_DEBUG_PRINTF, "OSPF: Entering ospf_select_complete_set_of_matching_entries_from_the_routing_table\r\n");	sptr_previous_node = NULL;	sptr_matching_node = NULL;	sptr_routing_table_node = NULL;	hash_id = destination_ip_address;	hash_id = hash_id & OSPF_RT_HASH_MASK;	*usptr_number_of_entries = 0x0000;	for(sptr_routing_table_node = ospf.sptr_routing_table_head[OSPF_ROUTE_TABLE_NETWORK][hash_id];		sptr_routing_table_node != NULL;		sptr_routing_table_node = sptr_routing_table_node->sptr_forward_link)		{			if(sptr_routing_table_node->active_areas_discarded_entry == FALSE)			{				if(ospf_check_if_ip_destination_falls_into_address_range (destination_ip_address,					sptr_routing_table_node->sptr_routing_table_entry->destination_id,					sptr_routing_table_node->sptr_routing_table_entry->address_mask) == PASS)				{					sptr_matching_node = (OSPF_ROUTING_TABLE_NODE *) table_malloc (1, sizeof (OSPF_ROUTING_TABLE_NODE));					if (sptr_matching_node == NULL)					{						ospf_print_memory_error_message_and_free_buffer_if_necessary ((void *) NULL, "OSPF_ROUTING_TABLE_NODE");						return;					}					++(*usptr_number_of_entries);					sptr_matching_node->sptr_forward_link = NULL;					sptr_matching_node->sptr_backward_link = sptr_previous_node;					sptr_matching_node->sptr_routing_table_entry = sptr_routing_table_node->sptr_routing_table_entry;					if (*ptr_to_sptr_first_matching_node == NULL)					{						*ptr_to_sptr_first_matching_node = sptr_matching_node;					}					else if (sptr_previous_node != NULL)					{						sptr_previous_node->sptr_forward_link = sptr_matching_node;					}					sptr_previous_node = sptr_matching_node;				}			}		}	return;}/****************************************************************************************//* section 11.1, item (2) (page 101) */static void ospf_reduce_set_to_those_having_the_most_preferential_path_type (OSPF_ROUTING_TABLE_NODE **ptr_to_sptr_first_node,	USHORT *usptr_number_of_entries){	enum OSPF_ROUTE_PATH_TYPE best_path;	OSPF_ROUTING_TABLE_NODE *sptr_node;	OSPF_ROUTING_TABLE_NODE *sptr_next_node;	OSPF_ROUTING_TABLE_NODE *sptr_would_be_first_node;	OSPF_PRINTF_DEBUG (OSPF_DEBUG_PRINTF, "OSPF: Entering ospf_reduce_set_to_those_having_the_most_preferential_path_type\r\n");	if ((*ptr_to_sptr_first_node)->sptr_forward_link == NULL)		{		return;													/* only one node in the linked list, so by default it is the best */		}	/* assume the first node in the list is a keeper unless we discover otherwise */	best_path = (*ptr_to_sptr_first_node)->sptr_routing_table_entry->path_type;	for (sptr_node = (*ptr_to_sptr_first_node)->sptr_forward_link; sptr_node != NULL; sptr_node = sptr_next_node)		{		sptr_next_node = sptr_node->sptr_forward_link;		if (sptr_node->sptr_routing_table_entry->path_type == best_path)			{			continue;											/* same type, so keep it in the list for now */			}		else if (sptr_node->sptr_routing_table_entry->path_type > best_path)			{			sptr_would_be_first_node = *ptr_to_sptr_first_node;			ospf_remove_node_from_list ((OSPF_GENERIC_NODE **) &sptr_would_be_first_node, (OSPF_GENERIC_NODE *) sptr_node);	/* it's not as good as what we already have, so toss it */			table_free ((void *) sptr_node);			sptr_node = NULL;			--(*usptr_number_of_entries);			*ptr_to_sptr_first_node = sptr_would_be_first_node;			}		else			{			/* we found a better type, so remove all nodes so far from the list and start with this one */			best_path = sptr_node->sptr_routing_table_entry->path_type;						/* new best type */			while (*ptr_to_sptr_first_node != sptr_node)				{				sptr_would_be_first_node = *ptr_to_sptr_first_node;				ospf_remove_node_from_list ((OSPF_GENERIC_NODE **) &sptr_would_be_first_node, (OSPF_GENERIC_NODE *) *ptr_to_sptr_first_node);				table_free ((void *) *ptr_to_sptr_first_node);				*ptr_to_sptr_first_node = NULL;				--(*usptr_number_of_entries);				*ptr_to_sptr_first_node = sptr_would_be_first_node;				}			}		}	return;}/****************************************************************************************//* section 11.1, item (3) (page 101) */static void ospf_select_most_specific_match_from_remaining_set (OSPF_ROUTING_TABLE_NODE **ptr_to_sptr_first_node,USHORT *usptr_number_of_entries){	OSPF_ROUTING_TABLE_NODE *sptr_node;	OSPF_ROUTING_TABLE_NODE *sptr_next_node;	OSPF_ROUTING_TABLE_NODE *sptr_would_be_first_node;	ULONG most_specific_address_mask;	OSPF_PRINTF_DEBUG (OSPF_DEBUG_PRINTF, "OSPF: Entering ospf_select_most_specific_match_from_remaining_set\r\n");	if ((*ptr_to_sptr_first_node)->sptr_forward_link == NULL)		{		return;		/* only one node in the linked list, so by default it is the best */		}	/* assume the first node in the list has the most specific address mask unless we discover otherwise */	most_specific_address_mask = (*ptr_to_sptr_first_node)->sptr_routing_table_entry->address_mask;	for (sptr_node = (*ptr_to_sptr_first_node)->sptr_forward_link; sptr_node != NULL; sptr_node = sptr_next_node)		{		sptr_next_node = sptr_node->sptr_forward_link;		if (sptr_node->sptr_routing_table_entry->address_mask == most_specific_address_mask)			{			/* keep it in the list for now */			continue;			}		else if (sptr_node->sptr_routing_table_entry->address_mask < most_specific_address_mask)			{			/* it's not as good as what we already have, so toss it */			sptr_would_be_first_node = *ptr_to_sptr_first_node;			ospf_remove_node_from_list ((OSPF_GENERIC_NODE **) &sptr_would_be_first_node, (OSPF_GENERIC_NODE *) sptr_node);