aspath.hh

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

// Copyright (c) 2001-2011 XORP, Inc and Others
//
// This program is free software; you can redistribute it and/or modify
// it under the terms of the GNU General Public License, Version 2, June
// 1991 as published by the Free Software Foundation. Redistribution
// and/or modification of this program under the terms of any other
// version of the GNU General Public License is not permitted.
// 
// 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. For more details,
// see the GNU General Public License, Version 2, a copy of which can be
// found in the XORP LICENSE.gpl file.
// 
// XORP Inc, 2953 Bunker Hill Lane, Suite 204, Santa Clara, CA 95054, USA;
// http://xorp.net

// $XORP: xorp/bgp/aspath.hh,v 1.34 2008/10/02 21:56:14 bms Exp $

#ifndef __BGP_ASPATH_HH__
#define __BGP_ASPATH_HH__

#include <sys/types.h>
#include <inttypes.h>




#include "libxorp/xorp.h"
#include "libxorp/debug.h"
#include "libxorp/xlog.h"
#include "libxorp/asnum.hh"
#include "libxorp/exceptions.hh"
#include "exceptions.hh"

class AS4Path;

// AS Path Values
enum ASPathSegType {
    AS_NONE = 0,    // not initialized
    AS_SET = 1,
    AS_SEQUENCE = 2,
    AS_CONFED_SEQUENCE = 3,
    AS_CONFED_SET = 4
};

class ASSegment {
public:
    typedef list<AsNum> ASLIST;
    typedef ASLIST::iterator iterator;
    typedef ASLIST::const_iterator const_iterator;
    typedef ASLIST::const_reverse_iterator const_reverse_iterator;

    ASSegment(ASPathSegType t = AS_NONE) : _type(t) {
    }

    ASSegment(const uint8_t* d) throw(CorruptMessage)   {
    decode(d);
    }

    ASSegment(const ASSegment& a) :
    _type(a._type), _aslist(a._aslist)      {}

    ~ASSegment()                    {}

    void clear()                    {
    _type = AS_NONE;
    _aslist.clear();
    }

    size_t path_length() const              {
    if (_type == AS_SET || _type == AS_CONFED_SET)
        return 1;
    else if (_type == AS_SEQUENCE || _type == AS_CONFED_SEQUENCE)
        return _aslist.size();
    else
        return 0; // XXX should not be called!
    }

    size_t as_size() const              {
    return _aslist.size();
    }

    void add_as(const AsNum& n)             {
    debug_msg("Number of As entries %u\n", XORP_UINT_CAST(_aslist.size()));
    _aslist.push_back(n);
    }

    void prepend_as(const AsNum& n)         {
    debug_msg("Number of As entries %u\n", XORP_UINT_CAST(_aslist.size()));
    _aslist.push_front(n);
    }

    bool contains(const AsNum& as_num) const        {
    const_iterator iter;

    for (iter = _aslist.begin(); iter != _aslist.end(); ++iter)
        if (*iter == as_num)
        return true;
    return false;
    }

    const AsNum& first_asnum() const;

    const AsNum& as_num(int n) const            {
    const_iterator i = _aslist.begin();

    while (n--)
        i++;

    return *i;
    }

    void decode(const uint8_t *d) throw(CorruptMessage);

    const uint8_t *encode(size_t &len, uint8_t *buf) const;

    size_t wire_size() const            {
    return 2 + 2 * _aslist.size();
    }

    string str() const;

    string short_str() const;

    bool operator==(const ASSegment& him) const;

    bool operator<(const ASSegment& him) const;

    ASPathSegType type() const          { return _type; }
    void set_type(ASPathSegType t)      { _type = t; }

    size_t encode_for_mib(uint8_t* buf, size_t buf_size) const;

    bool two_byte_compatible() const;

protected:
    ASPathSegType   _type;
    ASLIST      _aslist;
};


/* subsclass of ASSegment to handle encoding and decoding of 4-byte AS
   numbers from a AS4_PATH attribute */
class AS4Segment : public ASSegment {
public:
    AS4Segment(const uint8_t* d) throw(CorruptMessage) { decode(d); }
    void decode(const uint8_t *d) throw(CorruptMessage);

    const uint8_t *encode(size_t &len, uint8_t *buf) const;

    size_t wire_size() const            {
    return 2 + 4 * _aslist.size();
    }
private:
    /* no storage, as this is handled by the underlying ASSegment */
};

class ASPath {
public:
    typedef list <ASSegment>::const_iterator const_iterator;
    typedef list <ASSegment>::iterator iterator;

    ASPath() : _num_segments(0), _path_len(0)       {}

    ASPath(const char *as_path) throw(InvalidString);

    ASPath(const uint8_t* d, size_t len) throw(CorruptMessage) {
    decode(d, len); 
    }

    ASPath(const ASPath &asp1, const ASPath &asp2);

    ASPath(const ASPath &a) : _segments(a._segments), 
    _num_segments(a._num_segments), _path_len(a._path_len) {}

    ~ASPath()                       {}

    void add_segment(const ASSegment& s);
    void prepend_segment(const ASSegment& s);

    size_t path_length() const              { return _path_len; }

    bool contains(const AsNum& as_num) const        {
    const_iterator i = _segments.begin();
    for (; i != _segments.end(); ++i)
        if ((*i).contains(as_num))
        return true;
    return false;
    }

    const AsNum& first_asnum() const            {
    XLOG_ASSERT(!_segments.empty());
    return _segments.front().first_asnum();
    }

    string str() const;
    string short_str() const;

    const ASSegment& segment(size_t n) const        {
    if (n < _num_segments) {
        const_iterator iter = _segments.begin();
        for (u_int i = 0; i<n; i++)
        ++iter;
        return (*iter);
        }
    XLOG_FATAL("Segment %u doesn't exist.", (uint32_t)n);
    xorp_throw(InvalidString, "segment invalid n\n");
    }

    size_t num_segments() const         { return _num_segments; }

    const uint8_t *encode(size_t &len, uint8_t *buf) const;

    size_t wire_size() const;

    void prepend_as(const AsNum &asn);

    void prepend_confed_as(const AsNum &asn);

    void remove_confed_segments();

    bool contains_confed_segments() const;

    ASPath& operator=(const ASPath& him);

    bool operator==(const ASPath& him) const;

    bool operator<(const ASPath& him) const;

    void encode_for_mib(vector<uint8_t>& aspath) const;

    bool two_byte_compatible() const;

    void merge_as4_path(AS4Path& as4_path);

protected:
    list <ASSegment>    _segments;
    size_t      _num_segments;
    size_t      _path_len;

private:
    void decode(const uint8_t *d, size_t len) throw(CorruptMessage);
};

/* subclass to handle 4-byte AS encoding and decoding */
class AS4Path : public ASPath {
public:
    AS4Path(const uint8_t* d, size_t len) throw(CorruptMessage);

    AS4Path(const char *as_path) throw(InvalidString) 
    : ASPath(as_path)
    {};

#if 0

    AS4Path(const uint8_t* d, size_t len, const ASPath& as_path)
    throw(CorruptMessage);

#endif

    const uint8_t *encode(size_t &len, uint8_t *buf) const;

    size_t wire_size() const;

    void cross_validate(const ASPath& as_path);

private:
    void decode(const uint8_t *d, size_t len) throw(CorruptMessage);
    void pad_segment(const ASSegment& old_seg, ASSegment& new_seg);
    void do_patchup(const ASPath& as_path);
};

#endif // __BGP_ASPATH_HH__