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>
build: include git info

If enabled with --with-pkg-gitversion on ./configure, this will append
git version strings and branch information at the following places:
 - overall version number: 0.99.21-g0123456
 - login motd and show version: tag information + git id + branches

Sample output:
  Hello, this is Quagga (version 0.99.21-g14b49ad-dirty).
  Copyright 1996-2005 Kunihiro Ishiguro, et al.

  This is a git build of quagga_0_99_21_release-106-g14b49ad-dirty
  Associated branch(es):
	local:master

[v2]: fix build without gitinfo (add "else" branch)
[v2]: fix for repos without any tags (different git describe output)
Signed-off-by: David Lamparter <equinox@opensourcerouting.org>
isisd: do not add >63 IP addresses to hello

RFC1195 s4.2 "Multiple IP Addresses per Interface" explicitly forbids us
from adding multiple tuples of IP addresses, putting a hard cutoff at 63
IP addresses.

* isisd/isis_tlv.c: cut off (and return success) at 63 addrs.

Signed-off-by: David Lamparter <equinox@opensourcerouting.org>
Tested-by: Martin Winter <mwinter@opensourcerouting.org>
isisd: refuse adjacencies with our own system ID

isisd would form an adjacency with another router despite the system IDs
being identical.  This would later cause an assertion failure like this:

  assertion=0x555555596db8 "isis_find_vertex (spftree->paths, id, vtype) == ((void *)0)",
  file=0x555555596c60 "isis_spf.c", line=515, function=0x555555597900 "isis_spf_add2tent") at log.c:619

which is caused by trying to add a path expected to not exist, but
suddenly colliding due to the duplicate system ID.

* isis_pdu.c: check for system ID collision on receiving Hello

Signed-off-by: David Lamparter <equinox@opensourcerouting.org>
isisd: drop hellos without supported protocol list

isisd should not form adjacencies on receiving an IS-IS Hello without a
list of supported protocols (cf. RFC 1195 s4.4 p32 "Maintaining Router
Adjacencies")  Also fixes memleaks in these error cases.

* isisd/isis_pdu.c: improve TLVFLAG_NLPID handling

Signed-off-by: David Lamparter <equinox@opensourcerouting.org>
Tested-by: Martin Winter <mwinter@opensourcerouting.org>
isisd: fix spftree_area_del typo causing SEGV

spftree_area_del didn't clear the IPv6 L2 spftree due to a simple typo,
leading to a SEGV on shutdown when the still-armed timer would try to
run an IPv6 L2 SPF calculation with its data free'd already.

Signed-off-by: David Lamparter <equinox@opensourcerouting.org>
isisd: save metric-style narrow

isisd defaults to wide metric style. So if narrow metric style is
configured, a matching setting should be written to the configuration,
allowing a narrow metric-style setting to be saved.

Signed-off-by: Christian Franke <chris@opensourcerouting.org>
Signed-off-by: David Lamparter <equinox@opensourcerouting.org>
isisd: always join all IS-IS multicast groups

The socket is only created once when an interface is brought up, and the
multicast groups were joined according to configuration at that point.
This breaks when later switching an interface to another IS-IS level.

Since, for a separate conformance issue (ANVL ISIS-6.4), we should be
inspecting the destination address anyway, the simplest fix here is to
just join all groups unconditionally.  There shouldn't be much traffic
on these anyway, worst case we might be picking up some unrelated
multicast groups due to NIC filter aliasing though...

Signed-off-by: David Lamparter <equinox@opensourcerouting.org>
Tested-by: Martin Winter <mwinter@opensourcerouting.org>
isisd: address Coverity warnings

this fixes a bunch of issues found by Coverity SCAN and flagged as
"high" impact -- although, they're all rather minute issues.

* isisd/isis_adjacency.c: one superfluous check, one possible NULL deref
* isisd/isis_circuit.c: two prefix memory leaks
* isisd/isis_csm.c: one missing break
* isisd/isis_lsp.c: one possible NULL deref
* isisd/isis_pfpacket.c: one error-case fd leak
* isisd/isis_route.c: one isis_route_info memory leak
* isisd/isis_routemap.c: one... fnord
* isisd/isis_tlv.c: one infinite loop

Reported-by: Coverity SCAN
Signed-off-by: David Lamparter <equinox@opensourcerouting.org>