lsdb.c

BCAST Implementation for NS2

/*
 *   OSPFD routing daemon
 *   Copyright (C) 1998 by John T. Moy
 *   
 *   This program is free software; you can redistribute it and/or
 *   modify it under the terms of the GNU General Public License
 *   as published by the Free Software Foundation; either version 2
 *   of the License, or (at your option) any later version.
 *   
 *   This program is distributed in the hope that it will be useful,
 *   but WITHOUT ANY WARRANTY; without even the implied warranty of
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *   GNU General Public License for more details.
 *   
 *   You should have received a copy of the GNU General Public License
 *   along with this program; if not, write to the Free Software
 *   Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
 */

/* Routines that manipulate the OSPF link-state database. The
 * database is represented by the LSdb class.
 */


#include "ospfinc.h"
#include "system.h"
#include "opqlsa.h"

/* Find the AVL tree associated with this particular area
 * and LS type.
 */

AVLtree *OSPF::FindLSdb(SpfIfc *ip, SpfArea *ap, byte lstype)

{
    if (lstype == LST_ASL)	// AS-external_LSAs
	return(&ospf->extLSAs);
    if (lstype == LST_AS_OPQ)	// AS-scoped Opaque-LSAs
	return(&ospf->ASOpqLSAs);

    if (ap) {
	switch(lstype) {
          case LST_RTR:		// Router-LSAs
	    return(&ap->rtrLSAs);
          case LST_NET:		// Network-LSAs
	    return(&ap->netLSAs);
          case LST_SUMM:	// Summary-link LSAs (inter-area routes)
	    return(&ap->summLSAs);
          case LST_ASBR:	// ASBR-summaries
	    return(&ap->asbrLSAs);
          case LST_GM:		// Group-membership-LSA (MOSPF)
	    return(&ap->grpLSAs);
          case LST_AREA_OPQ:	// Area-scoped Opaque-LSAs
	    return(&ap->AreaOpqLSAs);
          default:
	    break;
        }
    }

    if (ip && lstype == LST_LINK_OPQ)	// Link-scoped Opaque-LSAs
	return(&ip->LinkOpqLSAs);

    return(0);
}

/* Return the flooding scope of an LSA, based on its LS type.
 */

int flooding_scope(byte lstype)

{
    switch(lstype) {
      case LST_LINK_OPQ:// Link-scoped Opaque-LSAs
	return(LocalScope);
      case LST_RTR: 	// Router-LSAs
      case LST_NET: 	// Network-LSAs
      case LST_SUMM:	// Summary-link LSAs (inter-area routes)
      case LST_ASBR:	// ASBR-summaries (inter-area)
      case LST_GM:	// Group-membership-LSA (MOSPF)
      case LST_AREA_OPQ:// Area-scoped Opaque-LSAs
	return(AreaScope);
      case LST_ASL: 	// AS-external_LSAs
      case LST_AS_OPQ:	// AS-scoped Opaque-LSAs
	return(GlobalScope);
      default:
	break;
    }

    return(0);
}

/* Return the number of LSAs currently in the
 * area's link-state database.
 */

int SpfArea::n_LSAs()

{
    int n_lsas;

    n_lsas = rtrLSAs.size();
    n_lsas += netLSAs.size();
    n_lsas += summLSAs.size();
    n_lsas += asbrLSAs.size();
    n_lsas += grpLSAs.size();
    return(n_lsas);
}


/* Find an LSA in the link state database, given the LSA's
 * LS type, Link State ID and Originating Router.
 * If this is a network-LSA, and the passed rtid is 0, stop
 * after matching the Link State ID. This is necessary when
 * performing the Dijkstra.
 */

LSA *OSPF::FindLSA(SpfIfc *ip,SpfArea *ap,byte lstype,lsid_t lsid, rtid_t rtid)

{
    AVLtree *btree;

    if (!(btree = FindLSdb(ip, ap, lstype)))
	return(0);

    return((LSA *) btree->find((uns32) lsid, (uns32) rtid));
}

/* Find the LSA of a given type and Link State ID that we
 * ourselves have originated, if any.
 */

LSA *OSPF::myLSA(SpfIfc *ip, SpfArea *ap, byte lstype, lsid_t lsid)

{
    return(FindLSA(ip, ap, lstype, lsid, myid));
}

/* Append all the LSAs of a particular type to a given lsalist.
 * Use for example when creating a Database Summary list at the
 * beginning of the Database Description process.
 * When in hitless restart, we don't add our own router-LSAs
 * to the list, as they will look like topology changes
 * to the neighboring routers. Instead, we reflood the router-LSAs
 * at the conclusion of hitless restart.
 */

void SpfIfc::AddTypesToList(byte lstype, LsaList *lp)

{
    AVLtree *btree;
    LSA *lsap;
    SpfArea *ap;

    ap = area();
    if (!(btree = ospf->FindLSdb(this, ap, lstype)))
	return;

    lsap = (LSA *) btree->sllhead;
    for (; lsap; lsap = (LSA *) lsap->sll)
	lp->addEntry(lsap);
}

/* Add an LSA to the database. If there is already a database copy, and
 * it's not on any lists, it can just be updated in place. As a special
 * case, if it is a simple refresh, we can just return after updating
 * the stored link state header.
 *
 * Otherwise, we allocate a new database copy, install it in the database
 * and parse it for ease of later routing calculations. In the process,
 * the old database copy is unparsed. NOTE: this may cause the old data
 * copy to be freed in the process, so the caller should no longer
 * reference "current" after calling this routine.
 */

LSA *OSPF::AddLSA(SpfIfc *ip,SpfArea *ap,LSA *current,LShdr *hdr,bool changed)

{
    LSA *lsap;
    int blen;
    RTE *old_rte = 0;
    bool min_failed=false;

    blen = ntoh16(hdr->ls_length) - sizeof(LShdr);
    if (current) {
        min_failed = current->since_received() < MinArrival;
	old_rte = current->rtentry();
	current->stop_aging();
	update_lsdb_xsum(current, false);
    }

    if (current && current->refct == 0) {
	// Update in place
	if (changed)
	    UnParseLSA(current);
	lsap = current;
	lsap->hdr_parse(hdr);
	lsap->start_aging();
	lsap->changed = changed;
	lsap->deferring = false;
	lsap->rollover = current->rollover;
	lsap->min_failed = min_failed;
	if (!changed) {
	    update_lsdb_xsum(lsap, true);
	    return(lsap);
	}
    }
    else {
	switch (hdr->ls_type) {
	  case LST_RTR:
	    lsap = new rtrLSA(ap, hdr, blen);
	    break;
	  case LST_NET:
	    lsap = new netLSA(ap, hdr, blen);
	    break;
	  case LST_SUMM:
	    lsap = new summLSA(ap, hdr, blen);
	    break;
	  case LST_ASBR:
	    lsap = new asbrLSA(ap, hdr, blen);
	    break;
	  case LST_ASL:
	    lsap = new ASextLSA(hdr, blen);
	    break;
	  case LST_GM:
	    lsap = new grpLSA(ap, hdr, blen);
	    break;
	  case LST_LINK_OPQ:
	  case LST_AREA_OPQ:
	  case LST_AS_OPQ:
	    lsap = new opqLSA(ip, ap, hdr, blen);
	    break;
	  default:
	    lsap = 0;
	    sys->halt(HALT_LSTYPE, "Bad LS type");
	    break;
	}

	// If database copy, unparse it
	if (!current)
	    lsap->changed = true;
	else {
	    lsap->changed = changed;
	    lsap->rollover = current->rollover;
	    lsap->min_failed = min_failed;
	    if (current->lsa_rxmt != 0)
		lsap->changed |= current->changed;
	    lsap->update_in_place(current);
	    UnParseLSA(current);
	}
	lsap->start_aging();
    }
    
    // Parse the new body contents
    ParseLSA(lsap, hdr);
    update_lsdb_xsum(lsap, true);
    // Provide Opaque-LSAs to requesters
    if (hdr->ls_type >= LST_LINK_OPQ && hdr->ls_type <= LST_AS_OPQ)
        upload_opq(lsap);
    // If changes, schedule new routing calculations
    if (changed) {
	rtsched(lsap, old_rte);
	cancel_help_sessions(lsap);
	if (in_hitless_restart())
	    htl_check_consistency(ap, hdr);
    }

    return(lsap);
}

/* When overwriting the database copy, copy the needed state
 * into the nely installed LSA.
 */

void LSA::update_in_place(LSA *)

{
}

void rteLSA::update_in_place(LSA *lsap)

{
    rteLSA *rtelsap;

    rtelsap = (rteLSA *) lsap;
    orig_rte = rtelsap->orig_rte;
}

/* Flush the locally-originated LSAs of a particular type.
 */

void OSPF::flush_self_orig(AVLtree *tree)

{
    AVLsearch iter(tree);
    LSA *lsap;

    while ((lsap = (LSA *)iter.next()))
	if (lsap->adv_rtr() == my_id())
	    lsa_flush(lsap);
}

/* Delete LSAs from an area's link-state database. This is done
 * silently, without reflooding, as this routine is only called when
 * there are no operational interfaces left connecting to the
 * area (this could be as a result of something like a change in
 * the area's stub status). However, we do inform local applications
 * that Opaque-LSAs have been deleted.
 *
 * This routine must perform the logic included in OSPF::DeleteLSA()
 * for each LSA, although we choose to do it here in a more
 * efficient manner.
 *
 * All AS-external-LSAs are left alone, as they belong to all