xorp

next_hop_resolver.hh

00001 // -*- c-basic-offset: 4; tab-width: 8; indent-tabs-mode: t -*-
00002 
00003 // Copyright (c) 2001-2011 XORP, Inc and Others
00004 //
00005 // This program is free software; you can redistribute it and/or modify
00006 // it under the terms of the GNU General Public License, Version 2, June
00007 // 1991 as published by the Free Software Foundation. Redistribution
00008 // and/or modification of this program under the terms of any other
00009 // version of the GNU General Public License is not permitted.
00010 // 
00011 // This program is distributed in the hope that it will be useful, but
00012 // WITHOUT ANY WARRANTY; without even the implied warranty of
00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. For more details,
00014 // see the GNU General Public License, Version 2, a copy of which can be
00015 // found in the XORP LICENSE.gpl file.
00016 // 
00017 // XORP Inc, 2953 Bunker Hill Lane, Suite 204, Santa Clara, CA 95054, USA;
00018 // http://xorp.net
00019 
00020 // $XORP: xorp/bgp/next_hop_resolver.hh,v 1.36 2008/10/02 21:56:16 bms Exp $
00021 
00022 #ifndef __BGP_NEXT_HOP_RESOLVER_HH__
00023 #define __BGP_NEXT_HOP_RESOLVER_HH__
00024 
00025 
00026 
00027 
00028 
00029 
00030 
00031 #include "libxorp/ipv4.hh"
00032 #include "libxorp/ipv6.hh"
00033 #include "libxorp/ipnet.hh"
00034 #include "libxorp/ref_trie.hh"
00035 
00036 #include "libxipc/xrl_std_router.hh"
00037 
00038 template<class A> class NhLookupTable;
00039 template<class A> class NextHopCache;
00040 template<class A> class NextHopResolver;
00041 template<class A> class NextHopRibRequest;
00042 template<class A> class DecisionTable;
00043 template<class A> class NHRequest;
00044 
00085 class BGPMain;
00086 
00087 template<class A>
00088 class NextHopResolver {
00089 public:
00090     NextHopResolver(XrlStdRouter *xrl_router, EventLoop& eventloop,
00091             BGPMain& bgp);
00092 
00093     virtual ~NextHopResolver();
00094 
00104     void add_decision(DecisionTable<A> *decision);
00105 
00110     bool register_ribname(const string& r);
00111 
00122     virtual bool register_nexthop(A nexthop, IPNet<A> net_from_route,
00123                   NhLookupTable<A> *requester);
00124 
00134     virtual void deregister_nexthop(A nexthop, IPNet<A> net_from_route,
00135                     NhLookupTable<A> *requester);
00136 
00137 
00151     virtual bool lookup(const A nexthop, bool& resolvable,
00152             uint32_t& metric) const;
00153 
00157     bool rib_client_route_info_changed(const A& addr,
00158                        const uint32_t& prefix_len,
00159                        const A& nexthop,
00160                        const uint32_t& metric);
00161 
00166     bool rib_client_route_info_invalid(const A& addr,
00167                        const uint32_t&  prefix_len);
00168 
00177     void next_hop_changed(A nexthop);
00178 
00191     void next_hop_changed(A nexthop, bool old_resolves, uint32_t old_metric);
00192 
00198     NextHopRibRequest<A> *get_next_hop_rib_request()
00199     {
00200     return &_next_hop_rib_request;
00201     }
00202 
00206     EventLoop& eventloop() {return _eventloop;}
00207 
00208 protected:
00209     list<DecisionTable<A> *> _decision;
00210 private:
00211     string _ribname;    // RIB name to use in XRL calls
00212     XrlStdRouter *_xrl_router;
00213     EventLoop& _eventloop;
00214     BGPMain& _bgp;
00215     NextHopCache<A> _next_hop_cache;
00216     NextHopRibRequest<A> _next_hop_rib_request;
00217 };
00218 
00235 template<class A>
00236 class NextHopCache {
00237 public:
00238     ~NextHopCache();
00239 
00252     void add_entry(A addr, A nexthop, int prefix_len, int real_prefix_len,
00253            bool resolvable, uint32_t metric = 0);
00254 
00271     bool validate_entry(A addr, A nexthop, int prefix_len, int real_prefix_len);
00272 
00285     map <A, int> change_entry(A addr, int prefix_len, uint32_t metric);
00286 
00298     map <A, int> delete_entry(A addr, int prefix_len);
00299 
00310     bool lookup_by_addr(A addr, int prefix_len, bool& resolvable,
00311             uint32_t& metric) const;
00312 
00323     bool lookup_by_nexthop(A nexthop, bool& resolvable, uint32_t& metric)
00324     const;
00325 
00339     bool lookup_by_nexthop_without_entry(A nexthop, bool& resolvable,
00340                      uint32_t& metric) const;
00341 
00342     /*
00343      * Try and register this next hop.
00344      *
00345      * If this next hop is known or covered then this next hop is
00346      * added to map of next hops that is associated with the
00347      * NextHopEntry.
00348      *
00349      * @param nexthop Next hop.
00350      * @param ref_cnt_incr How much to increase the reference count by.
00351      * @return True if this next hop is known or its in a covered
00352      * range.
00353      */
00354     bool register_nexthop(A nexthop, int ref_cnt_incr = 1);
00355 
00356     /*
00357      * Deregister this next hop.
00358      *
00359      * The NextHopEntry has a map of next hops with reference
00360      * counts. A deregister causes this next hop to be removed from
00361      * its associated NextHopEntry. If the map becomes empty then the
00362      * entry can be removed. If the map becomes empty then this fact
00363      * is signalled in the return value and this next hop can be
00364      * deregistered from the RIB.
00365      *
00366      * @param nexthop Next hop.
00367      * @param last True if this is the last next hop and the entry
00368      * has been freed.
00369      * @param addr If this was the last entry the base address.
00370      * @param prefix_len If this was the last entry the associated prefix_len.
00371      * @return True if an entry was found.
00372      */
00373     bool deregister_nexthop(A nexthop, bool& last, A& addr, uint32_t& prefix_len);
00374 private:
00375     struct NextHopEntry {
00376     A _address; // Base address as returned by the RIB
00377 #ifdef  USE_NEXTHOP
00378     A _nexthop; // The initial next hop. Used to find entry by
00379             // prefix_len
00380 #endif
00381     map <A, int> _nexthop_references;
00382     int _prefix_len;
00383     int _real_prefix_len;
00384     bool _resolvable;
00385     int _metric;
00386     };
00387 
00388     typedef set<NextHopEntry *> RealPrefixEntry;
00389     typedef RefTriePostOrderIterator<A, RealPrefixEntry> RealPrefixIterator;
00390 
00391     typedef NextHopEntry PrefixEntry;
00392     typedef RefTriePostOrderIterator<A, PrefixEntry *> PrefixIterator;
00393 
00400     RefTrie<A, PrefixEntry *> _next_hop_by_prefix;
00401     RefTrie<A, RealPrefixEntry> _next_hop_by_real_prefix;
00402 
00411     PrefixEntry *rpe_to_pe(const RealPrefixEntry& pe, A addr,
00412                int real_prefix_len) const;
00421     PrefixEntry *rpe_to_pe_delete(RealPrefixEntry& pe, A addr,
00422                   int real_prefix_len);
00423 };
00424 
00435 template <class A>
00436 class RibRequestQueueEntry {
00437 public:
00438     typedef enum {REGISTER, DEREGISTER} RegisterMode;
00439     RibRequestQueueEntry(RegisterMode mode) : _register_mode(mode) {}
00440     virtual ~RibRequestQueueEntry() {}
00441 protected:
00442     RegisterMode _register_mode;
00443 };
00444 
00445 template <class A>
00446 class RibRegisterQueueEntry : public RibRequestQueueEntry<A> {
00447 public:
00448     typedef RibRequestQueueEntry<A> QE;
00449     RibRegisterQueueEntry(A nexthop, IPNet<A> net_from_route, 
00450              NhLookupTable<A> *requester)
00451     : RibRequestQueueEntry<A>(QE::REGISTER),
00452       _nexthop(nexthop), _new_register(true), 
00453       _requests(net_from_route, requester),
00454       _reregister(false), _ref_cnt(0)
00455     {}
00456     RibRegisterQueueEntry(A nexthop, uint32_t ref_cnt, bool resolvable, 
00457                uint32_t metric)
00458     : RibRequestQueueEntry<A>(QE::REGISTER),
00459       _nexthop(nexthop), _new_register(false), _reregister(true),
00460       _ref_cnt(ref_cnt), _resolvable(resolvable), _metric(metric)
00461     {}
00462 
00463     void register_nexthop(IPNet<A> net_from_route, 
00464               NhLookupTable<A> *requester) {
00465     XLOG_ASSERT(true == _reregister || true == _new_register);
00466     XLOG_ASSERT(QE::_register_mode == QE::REGISTER);
00467     _new_register = true;
00468     _requests.add_request(net_from_route, requester);
00469     }
00470 
00471     bool deregister_nexthop(IPNet<A> net_from_route, 
00472                 NhLookupTable<A> *requester) {
00473     XLOG_ASSERT(true == _reregister || true == _new_register);
00474     XLOG_ASSERT(QE::_register_mode == QE::REGISTER);
00475     if (_new_register && _requests.remove_request(net_from_route, 
00476                               requester)) {
00477         return true;
00478     }
00479     if (_reregister) {
00480         XLOG_ASSERT(_ref_cnt > 0);
00481         _ref_cnt--;
00482         return true;
00483     }
00484     return false;
00485     }
00486 
00487     void reregister_nexthop(uint32_t ref_cnt, bool resolvable,
00488                 uint32_t metric) {
00489     XLOG_ASSERT(false == _reregister);
00490     XLOG_ASSERT(0 == _ref_cnt);
00491     XLOG_ASSERT(QE::_register_mode == QE::REGISTER);
00492     _reregister = true;
00493     _ref_cnt = ref_cnt;
00494     _resolvable = resolvable;
00495     _metric = metric;
00496     }
00497 
00498     bool resolvable() const {
00499     assert(QE::_register_mode == QE::REGISTER);
00500     return _resolvable;
00501     }
00502     bool reregister() const {
00503     assert(QE::_register_mode == QE::REGISTER);
00504     return _reregister;
00505     }
00506 
00507     bool new_register() const {
00508     assert(QE::_register_mode == QE::REGISTER);
00509     return _new_register;
00510     }
00511     bool metric() const {
00512     assert(QE::_register_mode == QE::REGISTER);
00513     return _metric;
00514     }
00515     const A& nexthop() const {
00516     return _nexthop;
00517     }
00518     uint32_t ref_cnt() const {
00519     return _ref_cnt;
00520     }
00521     NHRequest<A>& requests() {
00522     return _requests;
00523     }
00524 private:
00525     /*
00526     ** Register info.
00527     */
00528     A _nexthop;
00529     bool _new_register;
00530     NHRequest<A> _requests;
00531 
00532     /*
00533     ** Reregister info.
00534     */
00535     bool _reregister;
00536     uint32_t _ref_cnt;
00541     bool _resolvable;
00542     uint32_t _metric;
00543 };
00544 
00545 template <class A>
00546 class RibDeregisterQueueEntry : public RibRequestQueueEntry<A> {
00547 public:
00548     typedef RibRequestQueueEntry<A> QE;
00549     RibDeregisterQueueEntry(A base_addr, uint32_t prefix_len)
00550     : RibRequestQueueEntry<A>(QE::DEREGISTER), 
00551     _base_addr(base_addr), _prefix_len(prefix_len)
00552 
00553     {}
00554     const A& base_addr() const { return _base_addr;}
00555     uint32_t prefix_len() const { return _prefix_len;}
00556 private:
00557     /*
00558     ** Deregister info.
00559     */
00560     A _base_addr;
00561     uint32_t _prefix_len;
00562 };
00563 
00564 
00574 template<class A>
00575 class NextHopRibRequest {
00576 public:
00577     NextHopRibRequest(XrlStdRouter *,
00578               NextHopResolver<A>& next_hop_resolver,
00579               NextHopCache<A>& next_hop_cache,
00580               BGPMain& bgp);
00581     ~NextHopRibRequest();
00582 
00583     bool register_ribname(const string& r) { _ribname = r; return true; }
00584 
00593     void register_nexthop(A nexthop, IPNet<A> net,
00594               NhLookupTable<A> *requester);
00595 
00599     void send_next_request();
00600 
00609     void register_interest(A nexthop);
00610 
00614     void register_interest_response(const XrlError& error,
00615                     const bool *resolves,
00616                     const A *addr,
00617                     const uint32_t *prefix_len,
00618                     const uint32_t *real_prefix_len,
00619                     const A *actual_nexthop,
00620                     const uint32_t *metric,
00621                     const A nexthop_interest,
00622                     const string comment);
00623 
00624 
00628     bool premature_invalid(const A& addr, const uint32_t& prefix_len);
00629 
00633     bool tardy_invalid(const A& addr, const uint32_t& prefix_len);
00634 
00644     bool deregister_nexthop(A nexthop, IPNet<A> net,
00645                 NhLookupTable<A> *requester);
00646 
00667     void reregister_nexthop(A nexthop, uint32_t ref_cnt, bool resolvable,
00668                 uint32_t metric);
00669 
00680     bool lookup(const A& nexthop, bool& resolvable, uint32_t& metric) const;
00681 
00682     /*
00683      * Deregister ourselves from the RIB for this next hop
00684      *
00685      * @param nexthop The next hop.
00686      * @param prefix_len The prefix_len we registered with.
00687      */
00688     void deregister_from_rib(const A& nexthop, uint32_t prefix_len);
00689 
00690     /*
00691      * Deregister ourselves from the RIB for this next hop
00692      *
00693      * @param nexthop The next hop.
00694      * @param prefix_len The prefix_len we registered with.
00695      */
00696     void deregister_interest(A nexthop, uint32_t prefix_len);
00697 
00704     void deregister_interest_response(const XrlError& error, 
00705                       A addr,
00706                       uint32_t prefix_len,
00707                       string comment);
00708 
00709 private:
00710     string _ribname;
00711     XrlStdRouter *_xrl_router;
00712     NextHopResolver<A>& _next_hop_resolver;
00713     NextHopCache<A>& _next_hop_cache;
00714     BGPMain& _bgp;
00715 
00719     bool _busy;
00720 
00721     bool _invalid;      // True if received an unmatched invalid call.
00722     IPNet<A> _invalid_net;  // Saved invalid subnet.
00723 
00724     bool _tardy_invalid;    // True if we are expecting an invalid
00725                 // from the RIB.
00726     IPNet<A> _tardy_invalid_net;// Saved invalid subnet.
00727 
00731     list<RibRequestQueueEntry<A> *> _queue;
00732 
00737     static void zapper(RibRequestQueueEntry<A> *req) { delete req; }
00738 };
00739 
00740 template<class A>
00741 class NHRequest {
00742 public:
00743     NHRequest();
00744     NHRequest(IPNet<A> net,
00745           NhLookupTable<A> *requester);
00746     void add_request(IPNet<A> net,
00747              NhLookupTable<A> *requester);
00748     bool remove_request(IPNet<A> net,
00749             NhLookupTable<A> *requester);
00750     const set <NhLookupTable<A>*>& requesters() const {
00751     return _requesters;
00752     }
00753     const set <IPNet<A> >& request_nets(NhLookupTable<A>* requester) const;
00754     int requests() const { return _request_total; }
00755 
00756 private:
00757     set <NhLookupTable<A> *> _requesters;
00758     map <NhLookupTable<A> *, multiset<IPNet<A> > > _request_map;
00759     mutable map <NhLookupTable<A> *, set<IPNet<A> > > _answer;
00760     int _request_total;
00761 };
00762 
00763 #endif // __BGP_NEXT_HOP_RESOLVER_HH__
 All Classes Namespaces Functions Variables Typedefs Enumerations