bgpd: add replace-as modifier for BGP neighbor

Added replace-as modifier for BGP neighbors when using
local-as. If the replace-as modifier is specified, only the
replacement AS as specified by the local-as modifier is
prepended to the AS_PATH, not the process's AS.

In bgp_attr.c, I decided that

if (peer->change_local_as) {
  /* If replace-as is specified, we only use the change_local_as when
     advertising routes. */
  if( ! CHECK_FLAG (peer->flags, PEER_FLAG_LOCAL_AS_REPLACE_AS) ) {
    aspath = aspath_add_seq (aspath, peer->local_as);
  }
  aspath = aspath_add_seq (aspath, peer->change_local_as);
} else {
  aspath = aspath_add_seq (aspath, peer->local_as);
}

was clearer than the alternative that didn't duplicate the prepending of the
process's AS:

/* First, append the process local AS unless we have an alternate local_as
 * and we're replacing it (as opposed to just prepending it). */
if (! (peer->change_local_as
       && CHECK_FLAG (peer->flags, PEER_FLAG_LOCAL_AS_REPLACE_AS) ) ) {
  aspath = aspath_add_seq (aspath, peer->local_as);
}

if (peer->change_local_as)
  aspath = aspath_add_seq (aspath, peer->change_local_as);
}

But I could be convinced otherwise.

Signed-off-by: David Lamparter <equinox@opensourcerouting.org>
bgpd: Fixed out-of-date comment

When going through the code to write the documentation for local-as,
I discovered that one of the comments was out-of-date.

Signed-off-by: David Lamparter <equinox@opensourcerouting.org>
bgpd: document bgp neighbor local-as peer command

Signed-off-by: David Lamparter <equinox@opensourcerouting.org>
zebra: add structure to hold per-prefix state in RIB

Add the rib_dest_t structure to hold per-prefix state in the routing
information base. This gives us an appropriate place to maintain the
queueing state of a route_node. Queuing state was previously being
stored on the first rib in the list of ribs hanging off the
route_node.

  * zebra/rib.h

    - Add new structure rib_dest_t.

    - Remove the rn_status field from 'struct rib', it is no longer
      required.

    - Add macros (RNODE_FOREACH_RIB, RNODE_FOREACH_RIB_SAFE) for
      walking all 'struct ribs' corresponding to a route_node. These
      hide the fact that there is an intermediate rib_dest_t
      structure.

    - Add a few utility inlines to go between a rib_dest_t and
      associated structures.

  * zebra/zebra_rib.c

    - rib_link()/rib_unlink()

      Tweak for new behavior, where the 'info' pointer of a route_node
      points to a rib_dest_t. The list of ribs for a prefix now hangs
      off of the dest.

      Change the way we ref count route_nodes. We now hold a single
      ref count on a route_node if there is a corresponding
      rib_dest_t.

    - Maintain the queuing state of a route_node on the flags field of
      the rib_dest_t.

    - Add the rib_gc_dest() function, which deletes a rib_dest_t if it
      is no longer required. A rib_dest_t can be deleted iff there are
      no struct ribs hanging off of it.

    - Call rib_gc_dest() any time we unlink a rib from the
      rib_dest_t. Currently we only need to call it once, just before
      we return from rib_process().

  * zebra/{redistribute,zebra_rib,zebra_snmp,zebra_vty}.c

    Use new macros to walk over route_node ribs.

  * lib/memtypes.c

    Add memory type for rib_dest_t.

Signed-off-by: Avneesh Sachdev <avneesh@opensourcerouting.org>
Signed-off-by: David Lamparter <equinox@opensourcerouting.org>
zebra: add way to determine VRF/AFI/SAFI of table

Add some code that allows us to determine which VRF and AFI/SAFI a
given RIB table corresponds to.

  * zebra/rib.h

    Add rib_table_info_t structure, which contains information about
    the VRF, AFI and SAFI that a table is for.

  * zebra/zebra_rib.c

    - Add the vrf_table_create() function, which creates a table and
      sets its 'info' pointer to a newly created rib_table_info_t.
      The 'info' pointer allows us to go from a route_node or a table
      to the associated vrf.

    - vrf_alloc(): Use vrf_create_table() to create tables.

  * lib/memtypes.c

    Add memory type for rib_table_info_t.

Signed-off-by: Avneesh Sachdev <avneesh@opensourcerouting.org>
Signed-off-by: David Lamparter <equinox@opensourcerouting.org>
zebra: add iterator for walking all tables in RIB

* lib/zebra.h

    Add macro ZEBRA_NUM_OF, which returns the number of elements in a
    static array.

  * zebra/rib.h

    Add the rib_tables_iter_t structure and associated functions,
    which allow one to walk all tables in the rib.

  * zebra/zebra_rib.c

    - Add vrf_id_get_next() to retrieve the first VRF id (if any) that
      is greater than a given VRF id.

    - Add rib_tables_iter_next().

Signed-off-by: Avneesh Sachdev <avneesh@opensourcerouting.org>
Signed-off-by: David Lamparter <equinox@opensourcerouting.org>
zebra: extern/extract some functions from rt_netlink.c

* zebra/{rib.h,zebra_rib.c}

    Add nexthop_type_to_str(), which returns a human-readable string
    corresponding to a nexthop type.

  * zebra/rt_netlink.[hc]

    - Add new header file that exposes some existing and new
      netlink-related functions from rt_netlink.c to the rest of
      zebra.

        addattr32
        addattr_l
        rta_addattr_l
        nl_msg_type_to_str (new)
        nl_rtproto_to_str (new)

    - Use nexthop_type_to_str() instead of the static array
      'nexthop_types_desc'.

Signed-off-by: Avneesh Sachdev <avneesh@opensourcerouting.org>
Signed-off-by: David Lamparter <equinox@opensourcerouting.org>
lib: bring in sys/queue.h from FreeBSD tree

Bring in sys/queue.h from the FreeBSD tree as lib/queue.h.

This header implements lists of various flavors using inline
linkages. The imported file corresponds to SVN revision 221843 (url
below) and is available under the terms of the New BSD license
(3-clause).

  http://svnweb.freebsd.org/base/head/sys/sys/queue.h?revision=221843

Signed-off-by: Avneesh Sachdev <avneesh@opensourcerouting.org>
Signed-off-by: David Lamparter <equinox@opensourcerouting.org>
fpm: Add public header for Forwarding Plane Manager

The Forwarding Plane Manager (FPM) is an optional component that may
be used in scenarios where the router has a forwarding path that is
distinct from the kernel, commonly a hardware-based fast path. It is
responsible for programming forwarding information (such as routes and
nexthops) in the fast path.

In Quagga, the Routing Information Base is maintained in the 'zebra'
infrastructure daemon. Routing protocols communicate their best routes
to zebra, and zebra computes the best route across protocols for each
prefix. This latter information comprises the bulk of the Forwarding
Information Base.

The new header file added by this patch, 'fpm/fpm.h', defines a
point-to-point interface using which zebra can update the FPM about
changes in routes. The communication takes place over a stream
socket. The FPM listens on a well-known TCP port, and zebra initiates
the connection.

All messages sent over the connection start with a short 'FPM header'.
In the case of route add/delete messages, the header is followed by a
netlink message. Zebra should send a complete copy of the forwarding
table(s) to the FPM, including routes that it may have picked up from
the kernel.

The FPM interface uses replace semantics. That is, if a 'route add'
message for a prefix is followed by another 'route add' message, the
information in the second message is complete by itself, and replaces
the information sent in the first message.

If the connection to the FPM goes down for some reason, the client
(zebra) should send the FPM a complete copy of the forwarding table(s)
when it reconnects.

Signed-off-by: Avneesh Sachdev <avneesh@opensourcerouting.org>
Signed-off-by: David Lamparter <equinox@opensourcerouting.org>
zebra: add module to communicate routes to FPM

Enhance zebra to send routes to the (optional) Forwarding Path Manager
component using the interface defined by fpm/fpm.h.

  * configure.ac

    - Add --enable-fpm flag.

      The FPM-related code in zebra is activated only if the build is
      configured with '--enable-fpm'.

    - Add HAVE_NETLINK automake conditional.

      This allows us to conditionally build netlink-dependent C code.

  * zebra/{rib.h,zebra_rib.c}

    - Add the 'fpm_q_entries' field to the rib_dest_t structure. This
      allows dests to be placed on the fpm queue.

    - Define a couple new rib_dest_t flags that hold FPM-related
      state.

    - Invoke the zfpm_trigger_update() function for a route_node
      whenever the information to be sent to the FPM changes.

    - rib_can_delete_dest(): Return FALSE if we have to update the FPM
      about the given dest. This ensures that the dest is not deleted
      even if there are no ribs hanging off of it.

  * zebra/zebra_fpm.c

    This file holds most of the code for interacting with the FPM.

    - If quagga was configured with '--enable-fpm', periodically try
      to connect to the FPM.

    - When the connection comes up, enqueue all relevent dests to the
      FPM queue.

    - When the FPM socket is readable, dequeue the next rib_dest_t
      from the FPM queue, encode it in to a message and send the
      message to the FPM.

    - When the connection to the FPM goes down, remove all dests from
      the FPM queue, and then start trying to connect to the FPM
      again.

    - Expose the following new operational commands:

      show zebra fpm stats
      clear zebra fpm stats

  * zebra/zebra_fpm_netlink.c

    - zfpm_netlink_encode_route(): Function to encode information
      about a rib_dest_t in netlink format.

  * zebra/zebra_fpm_private.h

    Private header file for the zebra FPM module.

  * zebra/zebra_fpm.h

    Header file exported by zebra FPM module to the rest of zebra.

  * zebra/debug.c

    Add the 'debug zebra fpm' command.

  * zebra/main.c

    Initialize the zebra-FPM code on startup.

  * zebra/misc_null.c

    Add stub for zfpm_trigger_update().

  * zebra/Makefile.am

    - Include new file zebra_fpm.c in build.

    - Include zebra_fpm_netlink.c in build if HAVE_NETLINK is defined.

  * vtysh/Makefile.am

    Include zebra_fpm.c in list of files that define cli commands.

Signed-off-by: Avneesh Sachdev <avneesh@opensourcerouting.org>
Signed-off-by: David Lamparter <equinox@opensourcerouting.org>
doc: add blurbs on zebra FPM interface and commands

Update documentation with some text on the zebra interface to the
optional Forwarding Path Manager component, and the related cli
commands.

Signed-off-by: Avneesh Sachdev <avneesh@opensourcerouting.org>
Signed-off-by: David Lamparter <equinox@opensourcerouting.org>
zebra: include intf when sending IPv4 nexthop to FPM

* zebra/zebra_fpm_netlink.c

    Change the zebra FPM code to include an interface index when
    encoding a nexthop even if the protocol only provided a gateway
    address (e.g, NEXTHOP_TYPE_IPV4).

Signed-off-by: Avneesh Sachdev <avneesh@opensourcerouting.org>
Signed-off-by: David Lamparter <equinox@opensourcerouting.org>