tests: Add tests for timers

Signed-off-by: Christian Franke <chris@opensourcerouting.org>
Signed-off-by: David Lamparter <equinox@opensourcerouting.org>
lib: remove unused thread_master_debug function

Signed-off-by: Christian Franke <chris@opensourcerouting.org>
Signed-off-by: David Lamparter <equinox@opensourcerouting.org>
lib: use heap to manage timers

Signed-off-by: Christian Franke <chris@opensourcerouting.org>
Signed-off-by: David Lamparter <equinox@opensourcerouting.org>
zebra: Change the mechanism for comparing route ID's.

The current format uses subtraction of two ints. Unfortunately, the
subtraction method does not work for all combinations of numbers.
For example, the with numbers represented by 10.x.x.x and 192.x.x.x,
10.x.x.x - 192.x.x.x will yield a very large positive number indicating
that 10.x.x.x is larger.

Signed-off-by: Ken Williams <kenneth.j.williams@intel.com>
Acked-by: Feng Lu <lu.feng@6wind.com>
Signed-off-by: David Lamparter <equinox@opensourcerouting.org>
ospfd: run DR election prior to LSA regeneration

The results from DR election are used when constructing router-LSAs.
E.g. they are used to determine whether a broadcast interface should
be added with a link type of stub interface or transit interface.

Therefore, we should run DR election prior before regenerating LSAs.

Before commit c363d3861b5384a31465a72ddc3b0f6ff007a95a the DR election
was called synchronously prior to router-LSA regeneration which was run
asynchronously.

This fixes bug #761 on the Quagga bugzilla.

Signed-off-by: Christian Franke <chris@opensourcerouting.org>
Acked-by: Feng Lu <lu.feng@6wind.com>
Signed-off-by: David Lamparter <equinox@opensourcerouting.org>
ospfd: don't allow to set network type on loopback interfaces

OSPFd only allocates some stub information for loopback interfaces.
This causes a crash when the interface state machine is started on
that interface by configuring a different network type.

It doesn't make much sense to configure the network type of a loopback
interface, therefore, just forbid it.

See also bugzilla #670.

Signed-off-by: Christian Franke <chris@opensourcerouting.org>
Signed-off-by: David Lamparter <equinox@opensourcerouting.org>
ospfd: check the LS-Ack's recentness instead of only comparing the #seq

ISSUE:

RTA(DR)-----(BackupDR)RTB

RTA advertises a new LSA to RTB, and then flushes the LSA (with setting
the age of the LSA to MaxAge) within 1 second. Then the LSA is deleted
from RTA, while it still exists on RTB with non-MaxAge and can not be
flushed any more.

FIX:

The reason can be explained in below:

a) RTA -- new LSA, #seq=1 --> RTB (RTB will send the delayed Ack in 1s)
b) RTA -- MaxAge LSA, #seq=1 --> RTB (RTB discards it for the MIN_LS_ARRIVAL)
c) RTA <-- Ack for the new LSA, #seq=1 -- RTB (RTA accepts it)

In the step c), ospf_ls_ack() compares the #seq of the entry in the LS-Ack
with that of local MaxAge LSA. The #seq of the two entries are same. So
the Ack is accepted and the LSA is removed from the retransmit-list (while
it should not).

In RFC2328, section  13.7.  Receiving link state acknowledgments:

o   If the acknowledgment is for the same instance that is  <==
    contained on the list, remove the item from the list and
    examine the next acknowledgment.  Otherwise:

where "same instance" does not mean the same #seq. We must call
ospf_lsa_more_recent() to check whether the two instances are same.

Signed-off-by: Feng Lu <lu.feng@6wind.com>
Signed-off-by: Christian Franke <chris@opensourcerouting.org>
Signed-off-by: David Lamparter <equinox@opensourcerouting.org>
ospfd: fix a reference counting issue introduced by commit 4de8bf0011

Commit 4de8bf0011 added a return statement to a loop iterating over a
route_table. That loop uses route_top/route_next.

As commit 4de8bf0011 failed to add a route_node_unlock before the
return statement, a reference is leaked when this codepath is taken.

Signed-off-by: Christian Franke <chris@opensourcerouting.org>
Acked-by: Feng Lu <lu.feng@6wind.com>
Signed-off-by: David Lamparter <equinox@opensourcerouting.org>
ospfd: clarify indentation and comments in ospf_lsa_maxage_delete

Signed-off-by: Christian Franke <chris@opensourcerouting.org>
Acked-by: Feng Lu <lu.feng@6wind.com>
Signed-off-by: David Lamparter <equinox@opensourcerouting.org>
ospfd: For an ABR, ensure the right LSID is MaxAge'd

PROBLEM:

Accurate garbage collection of maxage LSAs. The global OSPF structure has
a maxage_lsa tree - the key to the tree is <ls-id, adv-router> tuple. Suppose
the ABR has multiple areas and has originated some intra-area LSAs. The
key for all those LSAs is the same. The code then ends up in a state where
all but the first LSA do not get cleaned up from the areas' LSDB. A subsequent
event would readvertise those LSAs.

PATCH:

Since the LSA is going to stick around till it actually gets cleaned up by
the maxage_walker, make the LSA pointer as the key. Each distinct LSA that
gets maxage'd then gets added to the tree and will get cleaned up correctly.

Signed-off-by: Pradosh Mohapatra <pmohapat@cumulusnetworks.com>
[CF: Use CHAR_BIT; use uintptr_t; use sizeof(field) instead of sizeof(type)]
Signed-off-by: Christian Franke <chris@opensourcerouting.org>
[DL: this must remain a temporary fix! needs to be redone after 0.99.23]
Signed-off-by: David Lamparter <equinox@opensourcerouting.org>
ospfd: add debug messages for router lsa-generation

Add log messages to lsa_link_broadcast_set so it becomes more
apparent why a particular broadcast interface was added as
transit or stub interface.

Signed-off-by: Christian Franke <chris@opensourcerouting.org>
Acked-by: Feng Lu <lu.feng@6wind.com>
Signed-off-by: David Lamparter <equinox@opensourcerouting.org>
bgpd: use ATTR_FLAG_BIT() for BGP_ATTR_ values

* bgp_attr.c: this UNSET_FLAG()s are bogus. I did a quick review and
  I think that they could not cause any bug anyway.

Signed-off-by: Jorge Boncompte [DTI2] <jorge@dti2.net>
Acked-by: Feng Lu <lu.feng@6wind.com>
Signed-off-by: David Lamparter <equinox@opensourcerouting.org>
bgpd: add 'bgp bestpath as-path multipath-relax'

Compute multipath in BGP based on AS_PATH hop count match. If the knob
is turned on, it is not required to have an exact match of AS_PATHs
(provided other multipath conditions are met, of course).

Signed-off-by: Pradosh Mohapatra <pmohapat at cumulusnetworks.com>
Reviewed-by: Dinesh G Dutt <ddutt at cumulusnetworks.com>
Signed-off-by: David Lamparter <equinox@opensourcerouting.org>
bgpd: track correct originator-id in reflected routes

ISSUE:

Suppose route1 and route2 received from route-reflector-client1 and client2
respectively have identical attributes. The current logic of creating the
adj-rib-out for a peer threads the 'adv' structures for both routes against
the same attribute. This results in 'bgp_update_packet()' to pack those
routes in the same UPDATE message with one attr structure formatted. The
originator-id is thus set according to the first route's received router id.
This is incorrect.

PATCH:

Fix bgp_announce_check() function to set the originator-id in the
advertising attr structure. Also, fix the attribute hash function and
compare function to consider originator-id. Otherwise attributes where all
fields except the originator-id are identical get merged into one memory
location.

Signed-off-by: Pradosh Mohapatra <pmohapat at cumulusnetworks.com>
Reviewed-by: Scott Feldman <sfeldma at cumulusnetworks.com>
Reviewed-by: Ken Yin <kyin at cumulusnetworks.com>
[DL: whitespace changes dropped]
Signed-off-by: David Lamparter <equinox@opensourcerouting.org>
bgpd: display multipath status in "show ip bgp"

The output of "show ip bg" does not show whether and which routes are
installed as multipath routes along the best route:

BGP table version is 0, local router ID is 10.10.100.209
Status codes: s suppressed, d damped, h history, * valid, > best, i - internal,
              r RIB-failure, S Stale, R Removed
Origin codes: i - IGP, e - EGP, ? - incomplete

   Network          Next Hop            Metric LocPrf Weight Path
*>i1.0.0.0/24       10.10.100.1              1    111      0 15169 i
* i                 10.10.100.2              1    111      0 15169 i
* i                 10.10.100.3              1    111      0 65100 15169 i

This patch adds a new status code that is showing exactly which routes
are used as multipath:

BGP table version is 0, local router ID is 10.10.100.209
Status codes: s suppressed, d damped, h history, * valid, > best, = multipath,
              i internal, r RIB-failure, S Stale, R Removed
Origin codes: i - IGP, e - EGP, ? - incomplete

   Network          Next Hop            Metric LocPrf Weight Path
*>i1.0.0.0/24       10.10.100.1              1    111      0 15169 i
*=i                 10.10.100.2              1    111      0 15169 i
* i                 10.10.100.3              1    111      0 65100 15169 i

The inconsistency in the status code legend ("i - internal" vs. "i internal")
inherent from old IOS was fixed. It had to be touched anyways.

Signed-off-by: Boian Bonev <bbonev at ipacct.com>
[DL: rewrap long line, clean whitespace in same chunk]
Signed-off-by: David Lamparter <equinox@opensourcerouting.org>
bgpd: send notify in OpenSent when stopping manually

The issue it fixes is that the notification message is not sent to a
second peer when bgp is stopped manually.

According to BGP RFC4271, section 8.2.2, regarding the FSM transitions,
in OpenSent state:

If a ManualStop event (Event 2) is issued in the OpenSent state, the
local system:

  * sends the NOTIFICATION with a Cease,
  * sets the ConnectRetryTimer to zero,
  * releases all BGP resources,
  * drops the TCP connection,
  * sets the ConnectRetryCounter to zero, and
  * changes its state to Idle.

I've added a check for OpenSent state when the notification is sent from
the functions which are called from the CLI commands which
directly/indirectly stop/restart BGP.

Acked-by: Pradosh Mohapatra <pmohapat@cumulusnetworks.com>
Signed-off-by: David Lamparter <equinox@opensourcerouting.org>
bgpd: fix O_NONBLOCK on outgoing connects

BGP was setting sockets to be non-blocking only for the accepted passive
peers.  As a fix, setting the BGP sockets to be non-blocking even for
the active peers.

Signed-off-by: Vipin Kumar <vipin@cumulusnetworks.com>
Reviewed-by: Pradosh Mohapatra <pmohapat@cumulusnetworks.com>
Reviewed-by: Dinesh Dutt <ddutt@cumulusnetworks.com>
[DL: patch split, this is item 1.]
Signed-off-by: David Lamparter <equinox@opensourcerouting.org>
bgpd: increase TCP socket buffer size

BGP does not respond fairly in high scale.  As the number of BGP peers
and prefixes increase, triggers like interface flaps which lead to BGP
peer flaps, cause blockage in bgp_write.

BGP does handle the cases of TCP socket buffer full by queuing a write
event back, there is no functional issue there as such. Still,
increasing the peer socket buffer size should help reduce event queueing
in BGP.

Signed-off-by: Vipin Kumar <vipin@cumulusnetworks.com>
Reviewed-by: Pradosh Mohapatra <pmohapat@cumulusnetworks.com>
Reviewed-by: Dinesh Dutt <ddutt@cumulusnetworks.com>
[DL: patch split, this is item 3.]
Signed-off-by: David Lamparter <equinox@opensourcerouting.org>
bgpd: fix fast external fallover behavior

ISSUES

1. When an interface goes down, the zclient callbacks are invoked
   in the following order: (a) address_delete() that removes the
   connected address list: ifp->connected, (b) interface_down()
   that performs "fast external fallover" operation. The operation
   relies on ifp->connected to look for peers that should be brought
   down. That's a cyclic dependency.

2. 'ttl-security' configuration handler sets peer->ttl to
   MAXTTL (so that BGP packets are sent with TTL=255, as per the
   requirement of ttl-security). This, however, is incompatible
   with 'fast external fallover' as the fallover operation checks
   for (ttl == 1) to determine directly connected peers.

3. The current fallover operation does not work for IPv6 address family.

PATCH

1. The patch removes the dependency on 'ifp->connected' list for fast
   fallover. The peer already contains a nexthop structure that reflects
   the peering address. The nexthop structure has a pointer to the
   interface (ifp) that peering address resolves to. Everytime the TCP
   connection succeeds, the ifp is updated. The patch uses this ifp in
   the interface_down() callback for a match for the peers that should be
   brought down.

2. The evaluation for directly connected peering is enhanced as
   'peer->ttl == 1' OR 'peer->gtsm_hops == 1'. Thus a ttl-security
   configuration on the peer with one hop is directly connected and
   should be brought down under 'fast external fallover'.

3. Because of fix (1), IPv6 address family works automatically.

Signed-off-by: Pradosh Mohapatra <pmohapat@cumulusnetworks.com>
Reviewed-by: Dinesh G Dutt <ddutt@cumulusnetworks.com>
Signed-off-by: David Lamparter <equinox@opensourcerouting.org>
bgpd: factor out TTL setting

TTL/min TTL are set from both bgp_accept() and bgp_connect().  Factor
them out so the following change to enable iBGP GTSM becomes more
readable.

[DL: originally by Dinesh G Dutt <ddutt@cumulusnetworks.com>,
     split off from the next commit]
Signed-off-by: David Lamparter <equinox@opensourcerouting.org>