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>

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>

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>

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: 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>

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>

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>

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>

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: 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 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>

bgpd: document bgp neighbor local-as peer command

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: 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>

lib: Implement monotonically increasing clock for Darwin.

There is no Posix CLOCK_MONOTONIC in Darwin, but monotonically
increasing clock can be implemented using mach_absolute_time().

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

isisd: clock_gettime() -> quagga_gettime() conversion.

* isisd/isis_spf.c: Use portable quagga_gettime() like the rest of
    the Quagga code.

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

ospfd: remove some buggy extra ';' symbols.

 * ospfd/ospf_apiserver.c: extra ; causing lookup to fail always
 * ospfd/ospf_lsa.c: extra ; causing debug output even when disabled

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

build: check actually-used BSD link state fields

ifi_link_state missing in OS X. There could be other *BSD's that haven't
implemented it and possibly affects older implementations.

The existing HAVE_BSD_LINK_DETECT configure.ac check is only confirming
the link state detection using ifmediareq.ifm_status found in
<net/if_media.h>. This is the link state detection used in
zebra/ioctl.c. Later, *BSD redefined struct if_data in <net/if.h> and
included link state detection. This is the method used in
zebra/kernel_socket.c

Additional test defined in config.ac to test for member struct
if_data.ifi_link_state defined in <net/if.h> separate from test for
<net/if_media.h> ifmediareq.ifm_status

Fixed #ifdef's in zebra/kernel_socket.c to use the new #define
No impact on older function calls in zebra/ioctl.c

Tested on 64bit OS X 10.7, FreeBSD 9.0 amd64 & i386 (32bit)
using gcc & clang. Tested on linux 64bit.

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

zebra: kernel_socket: fix overflow in RTA_ADDR & RTA_ATTR

In zebra/kernel_socket.c, copying sockaddr from *_msghdr:

There are really 2 different lengths that need to be determined.
  1) the length required to point to the next sockaddr in the mesg
     buffer which might include any required padding and
  2) the actual length of the sockaddr data that needs to be copied
     into the destination field.
They may or may not be the same value.

Sizeof sockaddr_in6 is 28, which to pad for alignment purposes on 32
bit systems with a long of 4 bytes is evenly divided and requires
no padding. On 64 bit systems, with a long of 8 it is padded with 4
extra bytes.So the current RTA_* macros are copying 32 bytes into a 28
byte field on 64 bitsystems, where the field overflow did not occur
on the 32 bit systems.

Since using sa_len required the use of an #ifdef which couldn't be used
directly inside a #define, it made sense to move the copy into the
function to allow typdef checking throughout and eliminate the hack
to suppress compiler warnings.

Fixed declaration of cp in ifm_read after compiler noticed type mismatch.

Tested on 64bit OS X 10.7, FreeBSD 9.0 amd64 & i386 (32bit)
using gcc & clang

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

zebra: kernel_socket: fix 64bit MacOS X alignment

In OS X 10.7 zebra crashed on invalid execution address.

sockaddr padding in *_msghdr is observed to be 4 bytes in 64bit OS X.

The ROUNDUP macro assumed alignment on sizeof(long) which
allocates 8 bytes on 64bit systems, 4 bytes on 32bit systems
which is true for BSD generally.

Test for Apple and use sizeof(int) which allocates 4 bytes on 32 & 64bit
systems.

Tested on 64bit OS X 10.7, FreeBSD 9.0 amd64 & i386 (32bit)
using gcc & clang

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

doc: update installation instructions

configure parameters have changed quite a bit, several options are
enabled by default now and there's --disable-tests.  Update
documentation to match.

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

build: compile tests/ by default

Broke the tests again... let's just build them by default so it's easier
to notice.  If anyone doesn't want to build tests, there's
--disable-tests.

NB: tests will be neither run nor installed.

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

tests: fix missing array_size() include

 * tests/test-sig.c: add #include "lib/memory.h" to get array_size()

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

bgpd: CVE-2012-1820, DoS in bgp_capability_orf()

An ORF (code 3) capability TLV is defined to contain exactly one
AFI/SAFI block. Function bgp_capability_orf(), which parses ORF
capability TLV, uses do-while cycle to call its helper function
bgp_capability_orf_entry(), which actually processes the AFI/SAFI data
block. The call is made at least once and repeated as long as the input
buffer has enough data for the next call.

The helper function, bgp_capability_orf_entry(), uses "Number of ORFs"
field of the provided AFI/SAFI block to verify, if it fits the input
buffer. However, the check is made based on the total length of the ORF
TLV regardless of the data already consumed by the previous helper
function call(s). This way, the check condition is only valid for the
first AFI/SAFI block inside an ORF capability TLV.

For the subsequent calls of the helper function, if any are made, the
check condition may erroneously tell, that the current "Number of ORFs"
field fits the buffer boundary, where in fact it does not. This makes it
possible to trigger an assertion by feeding an OPEN message with a
specially-crafted malformed ORF capability TLV.

This commit fixes the vulnerability by making the implementation follow
the spec.

build: reorder libraries to address linker error

The linker on some systems (for example, Ubuntu 12.04 LTS x86_64)
appears to be sensitive to the order in which libraries are
specified. On these systems, if a library 'A' depends on a library
'B', it has to be specified before 'B' when linking an executable.

  * zebra/Makefile.am: Make sure LIBCAP comes after libzebra.

  * tests/Makefile.am: Ensure libm comes after libbgp.

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

bgpd: flock() dump files (BZ#742)

flock()ing the BGP dump files helps consumers determine when they're
safe to read.

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

lib: treat OSX as BSD for IP_HDRINCL (BZ#739)

Mac OS X needs HAVE_IP_HDRINCL_BSD_ORDER defined like BSD. If it's not
defined, it'll fail like this:

  *** sendmsg in ospf_write failed to 224.0.0.5, id 0, off 0, len 64,
  interface en0, mtu 1500: Invalid argument

Which is caused by reordering iph->ip_len in
sockopt_iphdrincl_swab_htosys.

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

*: use array_size() helper macro

Use the array_size() helper macro.  Replaces several instances of local
macros with the same definition.

Reviewed-by: Scott Feldman <sfeldma@cumulusnetworks.com>
Signed-off-by: David Lamparter <equinox@opensourcerouting.org>

isisd: don't overrun list of protocols

isisd currently has a list of supported protocols as a fixed array of
size 4.  this can be overran, leading to an overwrite of the ipv4_addrs
pointer.

  * isisd/isis_pdu.c: don't accept more protocols than there's space for

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

lib: add array_size() helper

implement array_size as sizeof(array) / sizeof(array element)

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

isisd: don't process invalid prefixes from TLVs

it's possible to feed invalid prefixes (1.2.3.4/40 or dead::beef/200) on
IS-IS.  if this is not checked, it will later cause an assert in
processing.  let's simply abort processing the TLV if the prefix is
invalid.

  * isisd/isis_tlv.c: check prefix lengths for validity

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

isisd: pull up invalid prefix assert()

processing invalid prefixes causes isisd to assert() or otherwise
misbehave in ip_masklen/apply_mask.  pull up the assert() to indicate
better there's broken data in isisd's LSDB.

  * isisd/isis_spf.c: assert() prefix lengths

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

isisd: fix null pointer dereference in send_lsp()

  * isisd/isis_pdu.c: (send_lsp) Handle case where there are no LSPs
    on the LSP transmission queue. This can happen if, for instance,
    the queue is cleared because of protocol events before the
    send_lsp thread gets a chance to run.

isisd: tighten checks on ISIS pdu length

  * isisd/isis_pdu.c: Fix problem where isisd would crash if it
    received a LAN IIH with the 'pdu length' field set to zero.
    Similar problems can occur in parsing other ISIS PDUs as well --
    check that the PDU length in an ISIS hello, LSP or SNP packet is
    at least as big as the size of the respective fixed header.

lib: improve sanity checks in stream_set_endp()

  * lib/stream.c: (stream_set_endp) Add checks to make sure that the
    supplied 'endp' is within the 'size' of the stream, and that the
    current read pointer 'getp' is not beyond the specified 'endp'.

ospfd: respect max-metric over configured cost for summary LSAs

ISSUE

When max-metric router-lsa administrative is invoked on an ABR created with...
area <area> range <addr/mask>
the summary LSAs are sent out with 65535 (max-metric) added to the normal cost.

When max-metric router-lsa administrative is invoked on an ABR created with...
area <area> range <addr/mask> cost <cost>
the summary LSAs are sent out with <cost> (the max-metric is ignored).  This
second behavior effectively incapacitates the max-metric function.

PATCH

This patch evaluates the state of the router and if it's isolated as a stub
router (rfc3137) via `max-metric router-lsa`, we unconditionally uses the
value of 0xff0000 when advertising summary LSAs.

Signed-off-by: JR Rivers <jrrivers@cumulusnetworks.com>
Signed-off-by: Scott Feldman <sfeldma@cumulusnetworks.com>
Reviewed-by: Ayan Banerjee <ayan@cumulusnetworks.com>
Reviewed-by: Dinesh Dutt <ddutt@cumulusnetworks.com>
Signed-off-by: David Lamparter <equinox@opensourcerouting.org>

ospfd: ABR algorithm not propagating MAXAGE LSAs into area

When a range (or sub-range) is deleted, the area is notified by propagating a
MAXAGE LSA.  This LSA stays in the database for a while to both insure
propagation as well as in the off chance that it's useful in the near future.

Unfortunately, the ABR algorithm was treating these MAXAGE LSAs as unchanged and
not propagating them within the areas.

Signed-off-by: JR Rivers <jrrivers@cumulusnetworks.com>
Signed-off-by: Scott Feldman <sfeldma@cumulusnetworks.com>
Reviewed-by: Dinesh Dutt <ddutt@cumulusnetworks.com>
Reviewed-by: Shrijeet Mukherjee <shm@cumulusnetworks.com>
Signed-off-by: David Lamparter <equinox@opensourcerouting.org>

ospfd: blackhole route removal for area range

ISSUE

When an area range is created in which there the sub-area has routes that are
smaller than the range, an ABR creates a blackhole route to cover the range.
When the range is removed, the blackhole route is not removed.

--A----B----C---

B is an ABR with A in area 1 and C in area 0.  If A advertises `10.2.0.0/30` and
`10.2.0.4/30` and B is configured with `area 0.0.0.1 range 10.2.0.0/29` a
blackhole is created on B (`blackhole 10.2.0.0/29 proto zebra`).  When the
area/range is removed via the command line, the blackhole remains in existence
even though the "range" route is removed from area 0 and the individual routes
are propagated.

PATCH

The reason for this behavior is that, prior to this patch, the range is deleted
from the area's list, so when ospf_abr_manage_discard_routes() gets called,
there is nothing to clean up.  The patch removes the discard route as part of
the processing of the command line (ospf_area_range_unset()).

Signed-off-by: JR Rivers <jrrivers@cumulusnetworks.com>
Signed-off-by: Scott Feldman <sfeldma@cumulusnetworks.com>
Reviewed-by: Shrijeet Mukherjee <shm@cumulusnetworks.com>
Signed-off-by: David Lamparter <equinox@opensourcerouting.org>

lib: improve fletcher checksum validation

OVERVIEW

The checksum used in OSPF (rfc2328) is specified in rc905 annex B.  There is an
sample implementation in rfc1008 which forms the basis of the quagga
implementation.  This algorithm works perfectly when generating a checksum;
however, validation is a bit problematic.

The following LSA (generated by a non-quagga implementation) is received by
quagga and marked with an invalid checksum; however, it passes both the rfc905
and rfc1008 validation checks.

static uint8_t lsa_10_121_233_29[] = {
   0x0e, 0x10, 0x02, 0x03,
   0x09, 0x00, 0x35, 0x40,
   0x0a, 0x79, 0xe9, 0x1d,
   0x80, 0x00, 0x00, 0x03,
   0x00, 0x8a, 0x00, 0x1c,
   0xff, 0xff, 0xff, 0xe0,
   0x00, 0x00, 0x36, 0xb0
};

LS Type: Summary-LSA (IP network)
   LS Age: 3600 seconds
   Do Not Age: False
   Options: 0x02 (E)
   Link-State Advertisement Type: Summary-LSA (IP network) (3)
   Link State ID: 9.0.53.64
   Advertising Router: 10.121.233.29 (10.121.233.29)
   LS Sequence Number: 0x80000003
   LS Checksum: 0x008a
   Length: 28
   Netmask: 255.255.255.224
   Metric: 14000

You'll note that one byte of the checksum is 0x00; quagga would calculate the
checksum as 0xff8a.

It can be argued that the sourcing implementation generates an incorrect
checksum; however, rfc905 indicates that, for 1's complement arithmetic, the
value 255 shall be regarded as 0, thus either values are valid.

EXPLANATION

The quagga ospfd and ospf6d implementations operate by copying the PDU's
existing checksum in a holding variable, calculating the checksum, and comparing
the resulting checksum to the original.  As a note, this implementation has the
side effect of modifying the contents of the PDU.

Evaluation of both rfc905 and rfc1008 shows that checksum validation should
involve calculating the sum over the PDU and checking that both resulting C0 and
C1 values are zero.  This behavior is enacted in the rfc1008 implementation by
calling encodecc with k = 0 (checksum offset); however, this functionality had
been omitted from the quagga implementation.

PATCH

This patch adds the ability to call the quagga's fletcher_checksum() with a
checksum offset value of 0xffff (aka FLETCHER_CHECKSUM_VALIDATE) which returns
the sum over the buffer (a value of 0 indicates a valid checksum).  This is
similar to the mechanism in rfc1008 when called with k = 0.  The patch also
introduces ospf_lsa_checksum_valid().

ospf6d had it's own implementation of the fletcher checksum in
ospf6_lsa_checksum(); it's the same algorithm as in fletcher_checksum().  This
patch removes the local implementation in favor of the library's as well as creates
and uses ospf6_lsa_checksum_valid().

quagga's ISIS implementation suffers from the same problem; however, I do not
have the facilities to validate a fix to ISIS, thus this change has been left to
the ISIS maintainers.  The function iso_csum_verify() should be reduced to
running the fletcher checksum over the buffer using an offset of 0.

Signed-off-by: JR Rivers <jrrivers@cumulusnetworks.com>
Reviewed-by: Scott Feldman <sfeldma@cumulusnetworks.com>
Reviewed-by: Nolan Leake <nolan@cumulusnetworks.com>
Reviewed-by: Ayan Banerjee <ayan@cumulusnetworks.com>
Reviewed-by: Shrijeet Mukherjee <shm@cumulusnetworks.com>
Signed-off-by: David Lamparter <equinox@opensourcerouting.org>

zebra: make static routes respect table setting

Make static routes respect non-default routing tables.

BEFORE PATCH
------------

! in zebra.conf
table 1

! add static route
vtysh> ip route 10.0.0.0/30 eth0

cumulus@net-top0:~$ ip route
default via 192.168.0.2 dev eth0
10.0.0.0/30 dev eth0  proto zebra
192.168.0.0/24 dev eth0  proto kernel  scope link  src 192.168.0.15

! nothing in table 1
cumulus@net-top0:~$ ip route show table 1

AFTER PATCH
-----------

! in zebra.conf
table 1

! add static route
vtysh> ip route 10.0.0.0/30 eth0

cumulus@net-top0:~$ ip route
default via 192.168.0.2 dev eth0
192.168.0.0/24 dev eth0  proto kernel  scope link  src 192.168.0.15

! static route in table 1
cumulus@net-top0:~$ ip route show table 1
10.0.0.0/30 dev eth0  proto zebra

Signed-off-by: Nolan Leake <nolan@cumulusnetworks.com>
Reviewed-by: Scott Feldman <sfeldma@cumulusnetworks.com>
Signed-off-by: David Lamparter <equinox@opensourcerouting.org>

Revert "ospfd: Do not fall back to intervening router."

This reverts commit 9289c6ff55cd96c943d23e43fc9e5f987aa965ed.

The commit reverted an earlier change which was fixed a bug that caused
black-holes to remote destinations with multiple paths, that could occur
during convergence. Overall, the previous code is more correct.

lib/table: add route_table_get_next() and iterator

  * lib/table.[ch]

    - Add a function (route_table_get_next()) to get the route_node in
      a tree that succeeds a given prefix in iteration order.

      This allows one to reliably walk nodes in a tree while allowing
      modifications, and is useful for achieving scale and
      performance. Other approaches are also possible -- the main plus
      point of this one is that it does not require any state about
      the walk to be maintained in the table data structures.

    - Add an iterator for walking the nodes in a tree. This introduces
      a new structure (route_table_iter_t) and the following main
      functions.

        route_table_iter_init()
        route_table_iter_pause()
        route_table_iter_next()
        route_table_iter_cleanup()

      The iterator normally uses node pointers and the existing
      route_next() function to walk nodes efficiently. When an
      iteration is 'paused' with route_table_iter_pause(), it stores
      the last prefix processed. The next call to
      route_table_iter_next() transparently invokes
      route_table_get_next() with the prefix to resume iteration.

  * bgpd/bgp_table.[ch]

    Add wrappers for the new table features described above.

  * tests/table_test.c

    Add tests for the new table code.

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

bgpd: make bgp_table a wrapper around table library

Make the BGP table code a thin wrapper around the table implementation
in libzebra.

  * bgpd/bgp_table.[ch]

    - Use the ROUTE_NODE_FIELDS macro to embed the fields of a
      route_node in the bgp_node structure.

    - Add a route_table field to the bgp_table structure.

      Initialize the route_table with a delegate, such that the nodes
      in the table are bgp_node structures.

    - Add inline wrappers that call route_table functions underneath,
      and accept/return the correct BGP types.

  * bgpd/bgp_route.c

    Change some code to use inline wrappers instead of accessing
    fields of nodes/tables directly. The latter does not always work
    because the types of some fields need to be translated now.

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

lib: prepare table code for reuse by bgp_table

  * lib/table.[ch]

    - Add a macro (ROUTE_NODE_FIELDS) that expands to all the fields
      of a route_node structure.

    - Add the route_table_delegate_t structure, a function vector
      which allows clients to customize the behavior of one or more
      tables.

      The delegate currently contains the 'create_node' and
      'destroy_node' functions, and hence enables a table to use an
      alternative node structure. The alternative node is expected to
      embed the fields of a route_node using ROUTE_NODE_FIELDS.

    - Add route_table_init_with_delegate() to create a new table with
      a given delegate.

    - Make route_table_init() a thin wrapper around
      route_table_init_with_delegate(). The delegate it passes in
      simply creates/destroys route_node structures as before.

    - Add a user data pointer (info) to the route_table
      structure. This can be used by a client to keep per-table state.

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

lib: bring some changes over from bgp_table to table

  * lib/table.c

    - Maintain table node count. Expose it via the route_table_count()
      function (from revision cbdfbaa5).

    - route_unlock_node(): Add assertion (from revision 228da428).

    - route_table_free(): Make static and fix up cleanup code (from
      revision 228da428).

    - route_node_delete(): Change to be static.

    - Add 'const' qualifier in a couple places.

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

build: fix extract.pl for cross compilation

extract.pl should invoke the C preprocessor for the target system, not the
host.

* vtysh/extract.pl.in: use @CPP@ to get target cpp

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

ripd: clear sockaddr_in before using

ripd_create_socket() failed in bind() on Mac OS X 10.7 since there was garbage
in unused fields of struct sockaddr_in.

* ripd/ripd.c: zero out struct sockaddr_sin from before filling.

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

build: fix autoconf multicast check on OpenBSD

Fix the "BSD struct ip_mreq hack" autoconf test to work with OpenBSD.

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

build: correct libtool parameter used within Makefiles

This corrects the parameters passed to libtool when linking
the shared libraries. The paramter name is -version-info not
-version.

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

ospfd: Do not fall back to intervening router.

The patch in bug 330 did two things. It add a return value
whether ospf_nexthop_calculation() failed or not and also
moved the return stmt for 16.1.1 para 5 so now SPF
will fallback to the intervening router when no back links are found
by 16.1.1 para 5. This is wrong and can potentially create black holes
or routing loops according to Dave Katz and Acee Lindem at ospf@ietf.org

Even if the current code could be proved to be harmless in all cases,
it adds substantial extra processing and memory allocations.

Signed-off-by: Joakim Tjernlund <Joakim.Tjernlund@transmode.se>
Signed-off-by: David Lamparter <equinox@opensourcerouting.org>

ospfd: use ZEBRA_NEXTHOP_IPV4_IFINDEX

OSPF really needs to specify interface in its routes. Otherwise
ospf may change the wrong route.

Signed-off-by: Joakim Tjernlund <Joakim.Tjernlund@transmode.se>
[fixed up some whitespace errors, split patch in two]
Signed-off-by: David Lamparter <equinox@opensourcerouting.org>

zebra: Add support for ZEBRA_NEXTHOP_IPV4_IFINDEX

Actually implement the IPV4_IFINDEX nexthop type that has been drifting
around as a definition forever (without any warning about it being a
placeholder).

Signed-off-by: Joakim Tjernlund <Joakim.Tjernlund@transmode.se>
Signed-off-by: David Lamparter <equinox@opensourcerouting.org>

ospf_spf_process_stubs: use LSA pos to find OSFP interface

This is better than a prefix lookup as prefixes may not be
unique, that is, the same prefix can exist on several interfaces.

Signed-off-by: Joakim Tjernlund <Joakim.Tjernlund@transmode.se>
Signed-off-by: David Lamparter <equinox@opensourcerouting.org>

ospfd: Optimize and improve SPF nexthop calculation

Maintain router LSA positions in OSPF interface.
Find the OSPF interface in nexthop_calculation using
the position in the router LSA. This is possible because
the only time nexthop_calculation needs to look up interfaces
is when dealing with its own Router LSA.

This has the following advantages:
 - Multiple PtP interfaces with the same IP address between two routers.
 - Use Unnumbered PtP on just one end of the link.
 - Faster OI lookup for the OSPF interface and only
   done once for PtoP links.

*ospf_interface.h: (struct ospf_interface) Add storage for
   storing router LSA position.

*ospf_interface.c: (ospf_if_lookup_by_lsa_pos)
   lookup OSPF I/F in an area using LSA position.

*ospf_lsa.c: (router_lsa_link_set) record Router LSA position.

*ospf_spf.c: (ospf_spf_next) Count and pass along lsa position.
     (ospf_nexthop_calculation) Add lsa position argument.
     call ospf_if_lookup_by_lsa_pos() for OSFP interface handle.
     Clean up and remove all calls ospf_if_is_configured() the
     rest. Adjust a few debug logs.

Signed-off-by: Joakim Tjernlund <Joakim.Tjernlund@transmode.se>
Signed-off-by: David Lamparter <equinox@opensourcerouting.org>

ospfd: avoid exhausting memory with OSPF vertices (BZ#476)

This was found in scale testing at OSR;  ospfd is adding the same link
over and over again to the SPF tree.  This fix prevents the resulting
memory corruption from happening and adds a debug message to track
occurence of this issue and/or confirm a proper fix.

(This version was improved by Scott Feldman over the earlier RFC.)

* ospfd/ospf_spf.c: (ospf_spf_add_parent) loop over existing vertices
  and refuse to add duplicates.

Tested-by: Martin Winter <mwinter@opensourcerouting.org>
Signed-off-by: Scott Feldman <sfeldma@cumulusnetworks.com>
Signed-off-by: David Lamparter <equinox@opensourcerouting.org>

lib: make IPv6 prefix parser slightly more strict

This makes it possible to have both "show babel route A.B.C.D/M"
and "show babel route X:X::X:X/M" commands at the same time without
the parser complaining about ambiguity.

* lib/command.c: only accept STATE_DOT after : was seen.

Reported-by: Juliusz Chroboczek <jch@pps.jussieu.fr>
Signed-off-by: David Lamparter <equinox@opensourcerouting.org>

build: fix isisd topology out of tree build

isisd got the include directory wrong on building with a separate build
directory.

  * configure.ac: adjust ISIS_TOPOLOGY_INCLUDES

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

zebra: lingering IP address after deletion (BZ#486)

zebra address bookkeeping is a mess. this is just a workaround to have
IPv4 address deletion somewhat working on Linux.

the if_unset_prefix call is synchronous, when it returns success the
address deletion completed successfully. this is either signaled by a
netlink ACK or by an OK return value from ioctl().

This version is wrapped by #ifdef HAVE_NETLINK so we don't touch the
BSDs for now.

* zebra/interface.c: On Linux, update zebra internal state after
  deleting an address.

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

configure: Add --with-pkg-extra-version=VER for packagers/distributions.

This change adds a --with-pkg-extra-version option to ./configure to allow
packagers and distributions to fine tune the version displayed to the end
user to assist in support. It is also very useful when reporting bugs on
the official Quagga mailing lists.

There are two ways of utilsing this functionality:

      a) ./configure --with-pkg-extra-version=-wmo1
      b) EXTRAVERSION=-wmo1 ./configure

The latter is a common way for many distributions to add extra version
strings to signify their own patch level to a given package.

Also, minor whitespace fix in configure summary.

Signed-off-by: Joachim Nilsson <joachim.nilsson@westermo.se>
Signed-off-by: Joachim Nilsson <troglobit@gmail.com>
Signed-off-by: David Lamparter <equinox@opensourcerouting.org>

Merge remote branch 'vincentbernat/feature/ospfv3-mib'

Merge remote branch 'vincentbernat/feature/agentx'

ospf6d: fix segfault when requesting inexistant interfaces or areas

ospf6d: add SNMP notifications/traps support

Only implement ospfv3NbrStateChange and ospfv3IfStateChange.

ospf6d: add SNMP support for ospfv3*LsdbTable

This includes:
 - ospfv3AsLsdbTable
 - ospfv3AreaLsdbTable
 - ospfv3LinkLsdbTable

ospf6d: add SNMP implementation of ospfv3IfTable

ospf6d: complete SNMP implementation of ospfv3AreaTable

ospf6d: complete SNMP implementation for scalar objects

ospf6d: add SNMP support for ospfv3NbrTable

snmp: fix OSPFV3-MIB implementation

Use the real MIB from RFC 5643. Fix used ASN1 types. Indexes are not
exported any more (they are "no access"). Fix some endian
issues. Also, ID are just integers, not IPv4 addresses.

No additional OID are supported in this commit.

snmp: let handlers accept OID from a lesser prefix

Most table handlers do not expect to be given an OID whose prefix is
outside what they can handle. This is not a problem with the SMUX
implementation since it always correct the OID such that the prefix
matches. However, this is not the case for the AgentX
implementation. A new function, smux_header_table() is used to do this
normalization.

agentx: add appropriate documentation

agentx: handle SNMP traps

smux_trap() signature has been changed to provide appropriate level
information to send SNMPv2 notifications. This includes the addition
of the enterprise OID to use (from which is derived the SNMP trap OID)
and the MIB registry to locate the appropriate function for variable
bindings provided by the trap.

The SMUX implementation has been updated but ignore the provided
enterprise OID. Instead, it still uses the SMUX peer OID to keep
compatibility with previous versions of Quagga. The SMUX
implementation also ignores the provided MIB registry since it uses
smux_get() function to grab the appropriate values. This is not
possible with the AgentX implementation since there is no such
function provided by NetSNMP.

smux: drop findVar element from trap object struct

This element was not unused.

smux: remove `tick` argument from smux_trap()

smux_trap() contains an argument whose use appears to be to set
sysUpTime.0/timestamp field in SNMP trap. However, this value is not
used in smux_trap(). Moreover, it is expected that this field is the
value of sysUpTime.0 when the trap was sent and not any other time
related to the trap. To avoid any confusion, we remove this field from
the signature of the function.

agentx: add AgentX support to Quagga.

--enable-snmp will enable AgentX support in Quagga. SMUX is still here
and can be enabled with --enable-snmp=smux. AgentX support can be
enabled with "agentx" in configuration file. As for SMUX, this command
is not understood by vtysh. It can be disabled with "no agentx",
though there is no real use of this since this command cannot be used
with vtysh.

If "agentx" and "no agentx" command were added to vtysh, it would not
be possible to disable agentx support after enabling it because
NetSNMP does not expose the appropriate methods for this.

The internals of AgentX are hidden by NetSNMP. Therefore, we don't
have a file descriptor to add to the threading system. We do not have
the timers to set either. Therefore, the event loop is modified to
make use of snmp_select_info() from NetSNMP.

Traps are not supported yet.

smux: isolate SMUX implementation from SNMP implementation

lib/snmp.c gets OID related helper functions that can be used with
another SNMP interface. smux.h is cleaned of SMUX specific bits to
only expose functions that may be used by an alternative
implementation. We also do not redefine functions already present in
NetSNMP. Just use the appropriate headers.

build: use net-snmp-config to configure NetSNMP

The correct method to link to NetSNMP is to use net-snmp-config (which
is like pkg-config). Explicit link to libcrypto is also dropped
(NetSNMP libs are linked to libcrypto, no need to link Quagga to
it). Moreover, @SNMP_INCLUDES@ is dropped because useless. Due to a
bug in configure.ac, it was properly populated.

build: only define HAVE_SNMP

NetSNMP is the only SNMP implementation for Quagga. We don't need two
different symbols.

build: allow configure and build in a separate directory

Some .h files in lib/ are autogenerated. The search path should
include the build directory and the source directory. They usually
match but sometimes, they may be different. For example:

 $ mkdir build
 $ cd build
 $ ../configure
 $ make

isisd: fix typo in topology generator (BZ#731)

There was a "lsp->" missing before "level" in line 2416.
(introduced by git commit e38e0df)

Reported-by: Seblu <seblu@seblu.net>
Signed-off-by: David Lamparter <equinox@opensourcerouting.org>

bgpd: Partially revert f018db8, fixes BZ#730

  The change from bgp_node_get() to bgp_node_lookup() broke aggregation.

Signed-off-by: Jorge Boncompte [DTI2] <jorge@dti2.net>
Tested-by: Martin Winter <mwinter@opensourcerouting.org>
Signed-off-by: David Lamparter <equinox@opensourcerouting.org>

bgpd: Fix for commit 6a4677b7, fixes BZ#729

  The timers are rearmed after events processing. After 6a4677b7 we
do not generate events that can rearm the holdtime timer.

  Fix it's to call bgp_timer_set() directly as it's done from bgp_event().

Signed-off-by: Jorge Boncompte [DTI2] <jorge@dti2.net>
Tested-by: Martin Winter <mwinter@opensourcerouting.org>
Signed-off-by: David Lamparter <equinox@opensourcerouting.org>

tests: BGP unit tests to set BGP_OPT_NO_LISTEN so they can run

BGP tests had been broken by auto-creation of listen socket. This allows
them to run at least, though at least 1 test seems to have other breakage,
aspath_test.

bgpd: Add "no listen" socket option for the BGP master configuration

* bgpd.h: add a BGP_OPT_NO_LISTEN option for the master BGP configuration,
  to prevent any listen socket being created automatically. Allows code
  to be used outside of BGP daemon settings.
* bgpd.c: (bgp_get) honour above the flag, suppress auto-creation of listen
  socket on first BGP instance if set.
  (bgp_option_set) whitelist BGP_OPT_NO_LISTEN

lib: Add back sockunion_str2su

* sockunion.h: Add back sockunion_str2su, its removal breaks things needlessly
  (e.g. our own unit tests).
* sockunion.c: (sockunion_str2su) implement on top of str2sockunion.

Revert "bgpd: Make socket init separate, so unit tests work again."

This reverts commit 7621f336e2f346edee43227f0b1ef93fe769720b. See bug #727

lib: do not allocate/free thread funcnames

  This avoids memory heap fragmentation and imposses less load on the
system memory allocator.

* thread.h: FUNCNAME_LEN defined to 64 (ISO C99 says max 63)

Signed-off-by: Jorge Boncompte [DTI2] <jorge@dti2.net>
[changed FUNCNAME_LEN to a less arbitrary value]
Signed-off-by: David Lamparter <equinox@opensourcerouting.org>

lib: micro-op for thread_get()

thread_trim_head() already checks that the list is not empty.

Signed-off-by: Jorge Boncompte [DTI2] <jorge@dti2.net>
Signed-off-by: David Lamparter <equinox@opensourcerouting.org>

lib: remove RUSAGE_T from struct thread

* thread.c: It's only temporarily used in thread_call() to calculate the
  diffs. Saves 80 bytes per copy.

Signed-off-by: Jorge Boncompte [DTI2] <jorge@dti2.net>
Signed-off-by: David Lamparter <equinox@opensourcerouting.org>

micro-op bgp_node_[get|lookup]() and route_node_[get|lookup]()

  Reduce indirection for values that doesn't change in the loop.

Signed-off-by: Jorge Boncompte [DTI2] <jorge@dti2.net>
[adjusted after dropping previous patch]
Signed-off-by: David Lamparter <equinox@opensourcerouting.org>

bgpd: optimize bgp_aggregate_[increment|decrement]()

  If there were no aggregates configured this functions were allocating
and freeing a struct bgp_node for every call, and it's called for every
prefix received.

* bgp_route.c: Bail out early if the there are no aggregates configured.
  Change from bgp_node_get() to bgp_node_lookup() that does not allocate
  a new struct bgp_node if not found.

Signed-off-by: Jorge Boncompte [DTI2] <jorge@dti2.net>
Signed-off-by: David Lamparter <equinox@opensourcerouting.org>

bgpd: optimize bgp_update_main() in the soft_reconfig case

Avoids 3 checks per call.

Signed-off-by: Jorge Boncompte [DTI2] <jorge@dti2.net>
Signed-off-by: David Lamparter <equinox@opensourcerouting.org>

bgpd: optimize holdtime timer cancelling

* bgp_packet.c: (bgp_update_receive) for every update received we queue
  an event just to cancel the holdtime timer, done in bgp_fsm_update().
  Instead cancel the timer directly an avoid a scheduling pass.

  This incidently fixes another problem found on a slow box, where thousands
of events threads were queued, and run, but never freed, because they are
moved to the unused list that grows without bounds.

Signed-off-by: Jorge Boncompte [DTI2] <jorge@dti2.net>
Signed-off-by: David Lamparter <equinox@opensourcerouting.org>

bgpd: Remove useless initialization

It's initialized below

Signed-off-by: Jorge Boncompte [DTI2] <jorge@dti2.net>
Signed-off-by: David Lamparter <equinox@opensourcerouting.org>

bgpd: reduce struct attr_extra allocations/freeing

Try to use on stack structs for temporary uses.

Signed-off-by: Jorge Boncompte [DTI2] <jorge@dti2.net>
Signed-off-by: David Lamparter <equinox@opensourcerouting.org>

bgpd: use on stack struct attr_extra in bgp_update_receive()

Reduce memory heap fragmentation and pressure on the memory allocator.

Signed-off-by: Jorge Boncompte [DTI2] <jorge@dti2.net>
Signed-off-by: David Lamparter <equinox@opensourcerouting.org>

bgpd: fix struct attr_extra leak in bgp_default_originate()

  The call to bgp_attr_default_set() above creates the attr_extra struct,
but the attr.extra = NULL initialization was leaking it.

Signed-off-by: Jorge Boncompte [DTI2] <jorge@dti2.net>
Signed-off-by: David Lamparter <equinox@opensourcerouting.org>

bgpd: use on stack struct attr_extra in bgp_attr_unintern()

  Reduce memory heap fragmentation and pressure on the memory allocator.

Signed-off-by: Jorge Boncompte [DTI2] <jorge@dti2.net>
Signed-off-by: David Lamparter <equinox@opensourcerouting.org>

bgpd: cleanup bgp_attr_unintern()

Signed-off-by: Jorge Boncompte [DTI2] <jorge@dti2.net>
Signed-off-by: David Lamparter <equinox@opensourcerouting.org>

bgpd: use on stack struct attr_extra on bgp_attr_aggregate_intern()

Reduce memory heap fragmentation and pressure on the memory allocator.

Signed-off-by: Jorge Boncompte [DTI2] <jorge@dti2.net>
Signed-off-by: David Lamparter <equinox@opensourcerouting.org>