bgp_update.h

Go to the documentation of this file.

/*
 * Copyright (c) 2013 Juniper Networks, Inc. All rights reserved.
 */

#ifndef SRC_BGP_BGP_UPDATE_H_
#define SRC_BGP_BGP_UPDATE_H_

#include <boost/intrusive/list.hpp>
#include <boost/intrusive/slist.hpp>
#include <boost/intrusive/set.hpp>

#include <algorithm>
#include <list>

#include "bgp/bgp_ribout.h"

class BgpRoute;
class RibUpdateMonitor;
class RouteUpdate;
class UpdateList;

//
// This is the base class for elements in the UpdatesByOrder list container
// in an UpdateQueue. Each element can either be an RouteUpdate (UPDATE) or
// an UpdateMarker (MARKER).
//
class UpdateEntry {
public:
    enum EntryType {
        UPDATE  = 1,
        MARKER
    };

    explicit UpdateEntry(EntryType type) : type_(type) { }

    bool IsMarker() { return (type_ == MARKER); }
    bool IsUpdate() { return (type_ == UPDATE); }

    // Intrusive DLL
    boost::intrusive::list_member_hook<> list_node;

private:
    EntryType type_;
    DISALLOW_COPY_AND_ASSIGN(UpdateEntry);
};

//
// This class represents an update marker in the UpdatesByOrder container
// in an UpdateQueue. It contains a set of bits corresponding to the peers
// that have not seen any updates after the marker.
//
struct UpdateMarker : public UpdateEntry {
    UpdateMarker() : UpdateEntry(MARKER) {
    }
    RibPeerSet members;
};

//
// This class represents a unique collection of attributes for a particular
// prefix that needs to be sent to a subset of peers.  It is essentially a
// combination of a RouteUpdate and a RibOutAttr that keeps track of the
// subset of peers by using a RibPeerSet.
//
// Since an UpdateInfo is relevant only in the context of a RouteUpdate, it
// is on a singly linked list container in the RouteUpdate and maintains a
// back pointer to the RouteUpdate.
//
// An UpdateInfo is also part of the set container in an UpdateQueue that
// is sorted by attribute, timestamp and prefix.
//
struct UpdateInfo {
    UpdateInfo() : update(NULL) { }
    explicit UpdateInfo(const RibPeerSet &target)
        : target(target),
          update(NULL) {
    }
    UpdateInfo(const RibPeerSet &target, RibOutAttr &roattr)
        : roattr(roattr),
          target(target),
          update(NULL) {
    }

    void clear() {
        roattr.clear();
        target.clear();
    }

    void swap(UpdateInfo &rhs) {
        std::swap(roattr, rhs.roattr);
        std::swap(target, rhs.target);
    }

    // Intrusive slist node for RouteUpdate.
    boost::intrusive::slist_member_hook<> slist_node;

    // Node in UpdateQueue tree. Sorted by attribute, timestamp, rt prefix.
    boost::intrusive::set_member_hook<> update_node;

    // Update attributes.
    RibOutAttr roattr;

    // Update mask
    RibPeerSet target;

    // Backpointer to the RouteUpdate.
    RouteUpdate *update;

private:
    DISALLOW_COPY_AND_ASSIGN(UpdateInfo);
};

//
// Disposer for UpdateInfo.
//
struct UpdateInfoDisposer {
    void operator()(UpdateInfo *uinfo) { delete uinfo; }
};

#ifndef _LIBCPP_VERSION
namespace std {
template <>
inline void swap<UpdateInfo>(UpdateInfo &lhs, UpdateInfo &rhs) {
    swap(lhs.roattr, rhs.roattr);
    swap(lhs.target, rhs.target);
}
}
#endif

//
// Wrapper for intrusive slist of UpdateInfos. Destructor automatically
// deletes any elements still on the slist.
//
// TBD: create a class template.
//
class UpdateInfoSList {
public:
    typedef boost::intrusive::member_hook<
        UpdateInfo,
        boost::intrusive::slist_member_hook<>,
        &UpdateInfo::slist_node
    > Node;
    typedef boost::intrusive::slist<
        UpdateInfo,
        Node,
        boost::intrusive::linear<true>
    > List;

    UpdateInfoSList() { }
    ~UpdateInfoSList() { list_.clear_and_dispose(UpdateInfoDisposer()); }
    const UpdateInfo *FindUpdateInfo(const RibOutAttr &roattr) const;

    List *operator->() { return &list_; }
    const List *operator->() const { return &list_; }
    void swap(UpdateInfoSList &uinfo_slist) { list_.swap(uinfo_slist.list_); }

private:
    List list_;
    DISALLOW_COPY_AND_ASSIGN(UpdateInfoSList);
};

//
// This class represents an UPDATE element in the FIFO of UpdateEntry that
// is maintained within an UpdateQueue.
//
// A RouteUpdate contains a back pointer to a Route (which corresponds to
// the prefix) and a list of UpdateInfo elements. Each element contains a
// unique set of attributes that need to be advertised to a subset of the
// peers.  In the typical case, the list of UpdateInfo elements contains
// only a single entry.  However, separating the prefix information from
// the attributes in this manner allows the implementation to be extended
// to support add-path or route reflection.
//
// A RouteUpdate is also derived from a DBState which means that it is
// part of the state map within a DBEntry. This allows a RouteUpdate to
// be associated with a DBEntry using the listener id of the RibOut as
// the index. In the steady state, the DBEntry maps the listener id for
// the RibOut to a RouteState which contains the history of what has
// already been advertised.  When a RouteUpdate is created this history
// gets transferred from the RouteState to the RouteUpdate. This allows
// the DbEntry to map a listener id to either a RouteState or RouteUpdate
// instead of maintaining references to both.
//
class RouteUpdate : public DBState, public UpdateEntry {
public:
    enum Flag {
        F_LIST = 0,     // Entry is part of a list.
    };

    RouteUpdate(BgpRoute *route, int queue_id);
    ~RouteUpdate();

    void SetUpdateInfo(UpdateInfoSList &uinfo_slist);
    void BuildNegativeUpdateInfo(UpdateInfoSList &uinfo_slist) const;
    void ClearUpdateInfo();
    bool CompareUpdateInfo(const UpdateInfoSList &uinfo_slist) const;
    UpdateInfo *FindUpdateInfo(const RibOutAttr &roattr);
    const UpdateInfo *FindUpdateInfo(const RibOutAttr &roattr) const;
    void MergeUpdateInfo(UpdateInfoSList &uinfo_slist);
    bool RemoveUpdateInfo(UpdateInfo *uinfo);
    void ResetUpdateInfo(const RibPeerSet &peerset);
    void TrimRedundantUpdateInfo(UpdateInfoSList &uinfo_slist) const;

    void SetHistory(AdvertiseSList &history);
    void ClearHistory();
    void SwapHistory(AdvertiseSList &history) { history_.swap(history); }
    void MoveHistory(RouteState *rstate);
    void UpdateHistory(RibOut *ribout, const RibOutAttr *roattr,
                       const RibPeerSet &bits);
    const AdvertiseInfo *FindHistory(const RibOutAttr &roattr) const;

    AdvertiseSList &History() { return history_; }
    const AdvertiseSList &History() const { return history_; }

    UpdateInfoSList &Updates() { return updates_; }
    const UpdateInfoSList &Updates() const { return updates_; }


    // Return true if there is an history entry with a non-null attribute.
    bool IsAdvertised() const;
    bool OnUpdateList () { return FlagIsSet(RouteUpdate::F_LIST); }

    UpdateList *MakeUpdateList();
    UpdateList *GetUpdateList(RibOut *ribout);
    void set_update_list() { FlagSet(RouteUpdate::F_LIST); }
    void clear_update_list() { FlagReset(RouteUpdate::F_LIST); }

    BgpRoute *route() { return route_; }

    int queue_id() const { return queue_id_; }
    void set_queue_id(int queue_id) { queue_id_ = queue_id; }

    uint64_t tstamp() const { return tstamp_; }
    void set_tstamp(uint64_t tstamp) { tstamp_ = tstamp; }

    bool empty() const { return updates_->empty(); }

private:
    friend class RibUpdateMonitor;

    bool FlagIsSet(Flag flag) const { return flags_ & (1 << flag); }
    void FlagSet(Flag flag) { flags_ |= (1 << flag); }
    void FlagReset(Flag flag) { flags_ &= ~(1 << flag); }

    BgpRoute *route_;
    int8_t queue_id_;
    int8_t flags_;
    AdvertiseSList history_;  // Update history
    UpdateInfoSList updates_;       // The state we want to advertise
    uint64_t tstamp_;
    DISALLOW_COPY_AND_ASSIGN(RouteUpdate);
};

//
// If multiple RouteUpdates are active across different queues they are
// stored as an UpdateList.  An UpdateList is created when there's more
// than 1 RouteUpdate and is deleted when the number goes back to 1. An
// UpdateList keeps a list of pointers to RouteUpdates.
//
// The main motivation for creating an UpdateList is to avoid impacting
// the order in which updates from the QUPDATE queue are sent out when
// new peer(s) join or existing peer(s) request a refresh.  Without the
// notion of an UpdateList, we would have to dequeue a RouteUpdate and
// enqueue it again at the end when handling a join/refresh.
//
// The scheduled UpdateInfos are maintained in individual RouteUpdates in
// each queue, while the history is maintained in the UpdateList.
//
class UpdateList : public DBState {
public:
    typedef std::list<RouteUpdate *> List;

    UpdateList() { }

    AdvertiseSList &History() { return history_; }
    const AdvertiseSList &History() const { return history_; }

    void SetHistory(AdvertiseSList &history);
    void SwapHistory(AdvertiseSList &history) { history_.swap(history); }
    void MoveHistory(RouteState *rstate);
    void MoveHistory(RouteUpdate *rt_update);
    const AdvertiseInfo *FindHistory(const RibOutAttr &roattr) const;

    List *GetList() { return &list_; }
    const List *GetList() const { return &list_; }

    void AddUpdate(RouteUpdate *rt_update);
    void RemoveUpdate(RouteUpdate *rt_update);
    RouteUpdate *FindUpdate(int queue_id);
    RouteUpdate *MakeRouteUpdate();

private:
    friend class RibUpdateMonitor;

    AdvertiseSList history_;  // Update history
    List list_;
    DISALLOW_COPY_AND_ASSIGN(UpdateList);
};

#endif  // SRC_BGP_BGP_UPDATE_H_