ospf_routing_table_updates.c

vxworks下ospf协议栈

/* ospf_routing_table_updates.c */

/* Copyright 2000-2002 Wind River Systems, Inc. */
#include "copyright_wrs.h"

/*
modification history
___________________ 
02g,22jul03,agi    Fixed compiler warning
02f,09jun03,htm    SPR#87382 Fix for ANVL 4.2
02e,11jun03,ram    SPR#88965 Separate route table and LSDB hash parameters
02d,22apr03,ram	   SPR#76812 Modifications for OSPF performance enhancements
02c,11dec02,ram    SPR 84714 Added fixes for external ospf type 1 and 2 support
02b,06jan02,dsk    Fix for SPR#75194, ANVL 27.15
02a,22nov02,htm    Fix for TSR# 297651 SPR(83274).
01z,27nov02,fli    Fixed memory leaking when adding/deleting external route (SPR 83981).
01y,18apr02,jkw    External 1583compatibility flooding.
01x,16apr02,jkW    One copy of external and type 11 lsa
01w,04mar02,bt     modified highest cost for RFC2328 and lowest cost for RFC1583
01v,28jun01,jkw    Added fixes for multiple inter-area paths
01u,26sep00,reshma Added WindRiver CopyRight
01t,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-interface
01p,12may99,jack   change in ospf_invalidate_routing_table_entry
01o,11may99,jack   Fixes related to equal cost multi path
01n,10may99,jack   Change in function ospf_find_routing_table_node
01m,28dec98,jack   Compiled and added some comments
01l,11nov98,jack   Config changes, linted and big endian changes
01k,30oct98,jack   Incorporate changes for compilation on Vxworks
01j,23aug98,jack   ANVL tested OSPF with PATRICIA tree route table and no recursion
01i,10aug98,jack   PATRICIA Route Table Based OSPF Code Base
01h,19jun98,jacK   listroutine changes. OSPF add and delete list routines, eventually call
                   the rwutils list routines.
01g,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 made
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_routing_table_updates.c is used for updating the routing table when new link state
advertisements are received.
This file is used whenever a new link state advertisement is received.
*/

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

/***********************************************************************************************************************************/
static void ospf_case_1_summary_link_incremental_update (OSPF_SUMMARY_LINK_ADVERTISEMENT_HEADER *sptr_summary,
                                                         OSPF_AREA_ENTRY *sptr_area_A, enum BOOLEAN new_summary_lsa_received);
static void ospf_case_2_summary_link_incremental_update (OSPF_SUMMARY_LINK_ADVERTISEMENT_HEADER *sptr_summary,
                                                         OSPF_AREA_ENTRY *sptr_area_A, enum BOOLEAN new_summary_lsa_received);
static enum BOOLEAN ospf_check_next_hops_for_changes (OSPF_NEXT_HOP_BLOCK *sptr_new_next_hop, OSPF_NEXT_HOP_BLOCK *sptr_next_hop);
/*********************************************************************************************//* section 16.5 (pages 162-163) */
void ospf_update_routing_table_due_to_receipt_of_a_new_summary_link_advertisement (OSPF_SUMMARY_LINK_ADVERTISEMENT_HEADER *sptr_summary,
                                                                                   OSPF_AREA_ENTRY *sptr_area_A)
    {
    ULONG tos0_metric;
    USHORT age;
    ULONG advertising_router;
    enum BOOLEAN I_am_an_area_border_router;
    enum BOOLEAN new_summary_lsa_received;

    OSPF_PRINTF_DEBUG (OSPF_DEBUG_PRINTF, "OSPF: Entering ospf_update_routing_table_due_to_receipt_of_a_new_summary_link_advertisement\r\n");

    new_summary_lsa_received = TRUE;

    tos0_metric = net_to_host_long (sptr_summary->tos0_metric);
    tos0_metric = tos0_metric & OSPF_LSInfinity;
    age = net_to_host_short (sptr_summary->ls_header.age);
    advertising_router = net_to_host_long (sptr_summary->ls_header.advertising_router);

    if ((tos0_metric == OSPF_LSInfinity) || (age == OSPF_MAXIMUM_AGE) || (advertising_router == ospf.router_id))
        {
        if ( (tos0_metric == OSPF_LSInfinity) || (age == OSPF_MAXIMUM_AGE) )
            {
            /* SPR 87382, ANVL 4.2 - Begin */
            /* 
             * Removed call for ospf_invalidate_inter_area_route_entry() since the old
             * routing table entry is used inside ospf_generate_events_due_to_routing_table_changes()
             * to generate the proper LSAs for the old routing table entries that no longer exist in the new RT. 
             * Also we need to schdule building the routing table regardless of whether the new LSA is
             * type 3 or 4.
             */ 
            /* SPR 87382, ANVL 4.2 - End */

            ospf_schedule_routing_table_build (); 

            ospf_display_routing_table ();
            }

        return;                                             /* section 16.3, items (1 & 2) (page 158) */
        }

    I_am_an_area_border_router = ospf_check_if_area_border_router ();

    if ((sptr_area_A->area_id == OSPF_BACKBONE) || (I_am_an_area_border_router == FALSE))
        {
        ospf_case_1_summary_link_incremental_update (sptr_summary, sptr_area_A, new_summary_lsa_received);
        }
    else if ((sptr_area_A->flags._bit.transit == TRUE) && (I_am_an_area_border_router == TRUE))
        {
        ospf_case_2_summary_link_incremental_update (sptr_summary, sptr_area_A, new_summary_lsa_received);
        }

    ospf_display_routing_table ();

    return;
    }
/******************************************************************************************//* section 16.5 Case 1, (page 162) */
static void ospf_case_1_summary_link_incremental_update (OSPF_SUMMARY_LINK_ADVERTISEMENT_HEADER *sptr_summary,
                                                         OSPF_AREA_ENTRY *sptr_area_A, enum BOOLEAN new_summary_lsa_received)
    {
    ULONG destination_N;
    OSPF_ROUTING_TABLE_NODE *sptr_routing_table_node_for_N;
    enum BOOLEAN inter_area_route_added_to_routing_table;
    OSPF_ROUTING_TABLE_NODE *sptr_new_routing_table_node_for_N;
    OSPF_ADVERTISEMENT_NODE advertisement_node;
    enum BOOLEAN router_is_attached_to_at_least_one_transit_area;
    enum BOOLEAN next_hops_have_changed;
    enum BOOLEAN I_am_an_area_border_router;
    OSPF_AREA_ENTRY *sptr_area_to_summarize_new_route_into = NULL;
    OSPF_AREA_ENTRY *sptr_next_area_to_summarize_new_route_into = NULL;
    ULONG link_state_id;
    ULONG id_in_host_order;
    ULONG advertising_router_in_host_order;
    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_AREA_ENTRY *sptr_area = NULL;
    OSPF_AREA_ENTRY *sptr_next_area = NULL;


    OSPF_PRINTF_DEBUG (OSPF_DEBUG_PRINTF, "OSPF: Entering ospf_case_1_summary_link_incremental_update\r\n");

    destination_N = net_to_host_long (sptr_summary->ls_header.id);

    sptr_routing_table_node_for_N = ospf_find_routing_table_node (destination_N, (enum OSPF_LS_TYPE) sptr_summary->ls_header.type,
                                                                  OSPF_ROUTE_PATH_TYPE_INTER, sptr_area_A);   /* NEWRT LOOKUP */

    if (sptr_routing_table_node_for_N != NULL)
        {
        /* ANVL 27.15 start */
        /* only invalidate routing table entry if from same advertising router */
        if ((sptr_routing_table_node_for_N->sptr_routing_table_entry->destination_id == destination_N) &&
            (sptr_routing_table_node_for_N->sptr_routing_table_entry->advertising_router == sptr_summary->ls_header.advertising_router ))
            {
            /* Invalidate only if old route entry has same advertising router */
            /* ANVL 27.15 end */
            ospf_invalidate_routing_table_entry (sptr_routing_table_node_for_N, sptr_summary->network_mask, destination_N, sptr_area_A);
            }
        }

    advertisement_node.sptr_forward_link = NULL;
    advertisement_node.sptr_backward_link = NULL;
    advertisement_node.advertisement.sptr_summary = sptr_summary;

    inter_area_route_added_to_routing_table = ospf_calculate_inter_area_routes_for_a_single_summary_advertisement (
                                                                                                                  &advertisement_node, sptr_area_A, new_summary_lsa_received);

    I_am_an_area_border_router = ospf_check_if_area_border_router ();

    /* ANVL 27.15 start */
    /* If new path not better, do not send LSA */
    /*CI: if ((sptr_routing_table_node_for_N != NULL) && (inter_area_route_added_to_routing_table == FALSE))*/
    if ((sptr_routing_table_node_for_N != NULL) && (inter_area_route_added_to_routing_table == TRUE))
        {
        /* received LSA, recomputed inter-area path and new path is better */
        /* ANVL 27.15 end */
        if (I_am_an_area_border_router == TRUE)
            {
            for (sptr_area_to_summarize_new_route_into = ospf.sptr_area_list; sptr_area_to_summarize_new_route_into != NULL;
                sptr_area_to_summarize_new_route_into = sptr_next_area_to_summarize_new_route_into)
                {
                sptr_next_area_to_summarize_new_route_into = sptr_area_to_summarize_new_route_into->sptr_forward_link;
                if (sptr_area_to_summarize_new_route_into != ospf.sptr_backbone_area)
                    {
                    id_in_host_order = net_to_host_long (sptr_summary->ls_header.id);

                    advertising_router_in_host_order = net_to_host_long (sptr_summary->ls_header.advertising_router);

					/* SPR#76812 -- Begin */
 					sptr_database_entry = ospf_find_LSA (sptr_area_A, id_in_host_order, advertising_router_in_host_order, sptr_summary->ls_header.type);
 					/* SPR#76812 -- End */

                    if (sptr_database_entry != NULL)
                        {
                        (void) ospf_flood_advertisement_out_some_subset_of_the_routers_interfaces (
                                                                                                  sptr_database_entry->advertisement.sptr_router, sptr_area_to_summarize_new_route_into, NULL, NULL, TRUE);
                        }
                    }
                }
            }
        /* ANVL 27.15 start */
        } /* if new computed path is better flood LSA */
    /* ANVL 27.15 end */

    router_is_attached_to_at_least_one_transit_area = ospf_check_for_transit_areas ();

    if ((I_am_an_area_border_router == TRUE) && (router_is_attached_to_at_least_one_transit_area == TRUE))
        {
        ospf_examine_a_single_destination_for_a_better_path (&advertisement_node, sptr_area_A);
        }

    sptr_new_routing_table_node_for_N = ospf_find_routing_table_node (destination_N, (enum OSPF_LS_TYPE) sptr_summary->ls_header.type,
                                                                      OSPF_ROUTE_PATH_TYPE_INTER, sptr_area_A);        /* NEWRT LOOKUP */

    if (sptr_new_routing_table_node_for_N == NULL)                      /* N is newly unreachable */
        {
        for (sptr_area = ospf.sptr_area_list; sptr_area != NULL; sptr_area = sptr_next_area)
            {
            sptr_next_area = sptr_area->sptr_forward_link;
            /* Check for external lsdb */
            for (index = 0x00000000L, sptr_ls_database_head = &(ospf.external_database_hash_table[LS_EXTERNAL_LSA][index]); /* for each hash list */