route_db.cc

RIP 协议实现

// -*- c-basic-offset: 4; tab-width: 8; indent-tabs-mode: t -*-
// vim:set sts=4 ts=8:

// Copyright (c) 2001-2008 XORP, Inc.
//
// Permission is hereby granted, free of charge, to any person obtaining a
// copy of this software and associated documentation files (the "Software")
// to deal in the Software without restriction, subject to the conditions
// listed in the XORP LICENSE file. These conditions include: you must
// preserve this copyright notice, and you cannot mention the copyright
// holders in advertising related to the Software without their permission.
// The Software is provided WITHOUT ANY WARRANTY, EXPRESS OR IMPLIED. This
// notice is a summary of the XORP LICENSE file; the license in that file is
// legally binding.

#ident "$XORP: xorp/rip/route_db.cc,v 1.36 2008/07/23 05:11:36 pavlin Exp $"

// #define DEBUG_LOGGING
// #define DEBUG_PRINT_FUNCTION_NAME

#include "rip_module.h"

#include "libxorp/xorp.h"
#include "libxorp/debug.h"
#include "libxorp/eventloop.hh"
#include "libxorp/ipv4.hh"
#include "libxorp/ipv6.hh"
#include "libxorp/xlog.h"

#include <map>

#include "constants.hh"
#include "route_db.hh"
#include "update_queue.hh"
#include "rip_varrw.hh"
#include "peer.hh"


// ----------------------------------------------------------------------------
// NetCmp

template <typename A>
bool
NetCmp<A>::operator() (const IPNet<A>& l, const IPNet<A>& r) const
{
    if (l.prefix_len() < r.prefix_len())
	return true;
    if (l.prefix_len() > r.prefix_len())
	return false;
    return l.masked_addr() < r.masked_addr();
}


// ----------------------------------------------------------------------------
// RouteDB

template <typename A>
RouteDB<A>::RouteDB(EventLoop& e, PolicyFilters& pfs)
    : _eventloop(e),
      _policy_filters(pfs)
{
    _uq = new UpdateQueue<A>();
}

template <typename A>
RouteDB<A>::~RouteDB()
{
    _routes.erase(_routes.begin(), _routes.end());

    for (typename RouteContainerNoRef::iterator i = _rib_routes.begin();
	i != _rib_routes.end(); ++i) {
	delete (*i).second;
    }	
    
    delete _uq;
}

template <typename A>
bool
RouteDB<A>::insert_peer(Peer<A>* peer)
{
    typename set<Peer<A>* >::iterator iter;

    iter = _peers.find(peer);
    if (iter != _peers.end())
	return (false);

    _peers.insert(peer);
    return (true);
}

template <typename A>
bool
RouteDB<A>::erase_peer(Peer<A>* peer)
{
    typename set<Peer<A>* >::iterator iter;

    iter = _peers.find(peer);
    if (iter == _peers.end())
	return (false);

    _peers.erase(iter);
    return (true);
}

template <typename A>
void
RouteDB<A>::delete_route(Route* r)
{
    typename RouteContainer::iterator i = _routes.find(r->net());
    if (i == _routes.end()) {
	// Libxorp is bjorkfest if this happens...
	XLOG_ERROR("Route for %s missing when deletion came.",
		   r->net().str().c_str());
	return;
    }

    //
    // Check if we have rib routes to replace the delete route.
    // XXX: might be more correct to do all this in expire route.
    //
    typename RouteContainerNoRef::iterator iter = _rib_routes.find(r->net());
  
    _routes.erase(i);

    // add possible rib route
    if (iter != _rib_routes.end()) {
        r = iter->second;

	debug_msg("[RIP] Deleted route, but re-added from RIB routes: %s\n",
		  r->net().str().c_str());

        update_route(r->net(), r->nexthop(), r->ifname(), r->vifname(),
		     r->cost(), r->tag(), _rib_origin, r->policytags(), false);
    }
}

template <typename A>
void
RouteDB<A>::set_deletion_timer(Route* r)
{
    RouteOrigin* o = r->origin();
    uint32_t deletion_ms = o->deletion_secs() * 1000;

    XorpTimer t = _eventloop.new_oneoff_after_ms(deletion_ms,
				callback(this, &RouteDB<A>::delete_route, r));

    r->set_timer(t);
}

template <typename A>
void
RouteDB<A>::expire_route(Route* r)
{
    if (false == update_route(r->net(), r->nexthop(), r->ifname(),
			      r->vifname(), RIP_INFINITY, r->tag(),
			      r->origin(), r->policytags(), false)) {
	XLOG_ERROR("Expire route failed.");
    }
}

template <typename A>
void
RouteDB<A>::set_expiry_timer(Route* r)
{
    XorpTimer t;
    RouteOrigin* o = r->origin();
    uint32_t expiry_secs = o->expiry_secs();

    if (expiry_secs) {
	t = _eventloop.new_oneoff_after_ms(expiry_secs * 1000,
			   callback(this, &RouteDB<A>::expire_route, r));
    }
    r->set_timer(t);
}

template <typename A>
bool
RouteDB<A>::do_filtering(Route* r)
{
    try {
	RIPVarRW<A> varrw(*r);

	debug_msg("[RIP] Running import filter on route %s\n",
		  r->net().str().c_str());

	bool accepted = _policy_filters.run_filter(filter::IMPORT, varrw);

	if (!accepted)
	    return false;

	RIPVarRW<A> varrw2(*r);

	debug_msg("[RIP] Running source match filter on route %s\n",
		  r->net().str().c_str());
	_policy_filters.run_filter(filter::EXPORT_SOURCEMATCH, varrw2);

	return true;
    } catch(const PolicyException& e) {
	XLOG_FATAL("PolicyException: %s", e.str().c_str());
	XLOG_UNFINISHED();
    }
}

template <typename A>
bool
RouteDB<A>::update_route(const Net&		net,
			 const Addr&		nexthop,
			 const string&		ifname,
			 const string&		vifname,
			 uint32_t		cost,
			 uint32_t		tag,
			 RouteOrigin*		o,
			 const PolicyTags&	policytags,
			 bool			is_policy_push)
{
    if (tag > 0xffff) {
	// Ingress sanity checks should take care of this
	XLOG_FATAL("Invalid tag (%u) when updating route.",
		   XORP_UINT_CAST(tag));
	return false;
    }

    if (cost > RIP_INFINITY) {
	cost = RIP_INFINITY;
    }

    //
    // Update steps, based on RFC2453 pp. 26-28
    //
    bool updated = false;

    Route* r = 0;
    typename RouteContainer::iterator i = _routes.find(net);
    if (_routes.end() == i) {

	// Route does not appear in table so it needs to be
	// created if peer does not have an entry for it or
	// resurrected if it does.  But first this...
	if (cost == RIP_INFINITY) {
	    // Don't bother adding a route for unreachable net
	    return false;
	}

	// Create route if necessary
	r = o->find_route(net);
	if (r == 0) {
	    r = new Route(net, nexthop, ifname, vifname, cost, o, tag,
			  policytags);

	    set_expiry_timer(r);
	    bool ok(_routes.insert(typename
				   RouteContainer::value_type(net, r)).second);
	    
	    XLOG_ASSERT(ok);
	    
	    bool accepted = do_filtering(r);
	    r->set_filtered(!accepted);

	    if (!accepted)
		return false;

	    _uq->push_back(r);
	    return true;
	}

	// Resurrect route
	
	bool ok(_routes.insert(typename
			       RouteContainer::value_type(net, r)).second);
	XLOG_ASSERT(ok);

	// XXX: this is wrong
	bool accepted = do_filtering(r);
	r->set_filtered(!accepted);

	if (accepted)
	    updated = true;
    } else {
	r = i->second.get();
    }

    RouteEntryOrigin<A>* no_origin = NULL;
    RouteEntry<A>* new_route = new RouteEntry<A>(r->net(), nexthop,
						 ifname, vifname,
						 cost, no_origin, tag,
						 policytags);
    // XXX: lost origin
    bool accepted = do_filtering(new_route);

    // XXX: this whole section of code is too entangled.
    if (r->origin() == o) {
	uint16_t orig_cost = r->cost();
	
	updated |= r->set_nexthop(new_route->nexthop());
	updated |= r->set_ifname(new_route->ifname());
	updated |= r->set_vifname(new_route->vifname());
	updated |= r->set_tag(new_route->tag());
	updated |= r->set_cost(new_route->cost());
	updated |= r->set_policytags(new_route->policytags());

	delete new_route;

	if (cost == RIP_INFINITY) {
	    if ((orig_cost == RIP_INFINITY) && r->timer().scheduled()) {
		//
		// XXX: The deletion process is started only when the
		// metric is set the first time to infinity.
		//
	    } else {
		set_deletion_timer(r);
	    }
	} else {
	    if (is_policy_push && !updated) {
		//
		// XXX: The same route was pushed because of policy
		// reconfiguration, hence we don't need to update its
		// expiry timer.
		//
	    } else {
		set_expiry_timer(r);
	    }
	}
	
	bool was_filtered = r->filtered();
	r->set_filtered(!accepted);

	debug_msg("[RIP] Was filtered: %d, Accepted: %d\n",
		  was_filtered, accepted);
	
	if (accepted) {
	    if (was_filtered) {
		updated = true;
	    } else {
	    }
	} else {
	    if (was_filtered) {
		return false;
	    } else {
		if (cost != RIP_INFINITY) {
		    //
		    // XXX: Advertise the filtered route with INFINITY metric.
		    // If the filtered route should not be advertised with