path: root/src/vnet/fib/fib.h

/*
 * Copyright (c) 2016 Cisco and/or its affiliates.
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at:
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
/**
 * \brief
 * A IP v4/6 independent FIB.
 *
 * The main functions provided by the FIB are as follows;
 *
 *  - source priorities
 *
 *   A route can be added to the FIB by more than entity or source. Sources
 * include, but are not limited to, API, CLI, LISP, MAP, etc (for the full list
 * see fib_entry.h). Each source provides the forwarding information (FI) that
 * is has determined as required for that route. Since each source determines the
 * FI using different best  path and loop prevention algorithms, it is not
 * correct for the FI of multiple sources to be combined. Instead the FIB must
 * choose to use the FI from only one source. This choose is based on a static
 * priority assignment. For example;
 * IF a prefix is added as a result of interface configuration:
 *    set interface address 192.168.1.1/24 GigE0
 * and then it is also added from the CLI
 *    ip route 192.168.1.1/32 via 2.2.2.2/32
 * then the 'interface' source will prevail, and the route will remain as
 * 'local'.
 * The requirement of the FIB is to always install the FI from the winning
 * source and thus to maintain the FI added by losing sources so it can be
 * installed should the winning source be withdrawn.
 *
 *  - adj-fib maintenance
 *
 *   When ARP or ND discover a neighbour on a link an adjacency forms for the
 * address of that neighbour. It is also required to insert a route in the
 * appropriate FIB table, corresponding to the VRF for the link, an entry for
 * that neighbour. This entry is often referred to as an adj-fib. Adj-fibs
 * have a dedicated source; 'ADJ'.
 * The priority of the ADJ source is lower than most. This is so the following
 * config;
 *    set interface address 192.168.1.1/32 GigE0
 *    ip arp 192.168.1.2 GigE0 dead.dead.dead
 *    ip route add 192.168.1.2 via 10.10.10.10 GigE1
 * will forward traffic for 192.168.1.2 via GigE1. That is the route added
 * by the control plane is favoured over the adjacency discovered by ARP.
 * The control plane, with its associated authentication, is considered the
 * authoritative source.
 * To counter the nefarious addition of adj-fib, through the nefarious injection
 * of adjacencies, the FIB is also required to ensure that only adj-fibs whose
 * less specific covering prefix is connected are installed in forwarding. This
 * requires the use of 'cover tracking', where a route maintains a dependency
 * relationship with the route that is its less specific cover. When this cover
 * changes (i.e. there is a new covering route) or the forwarding information
 * of the cover changes, then the covered route is notified.
 *
 * Overlapping sub-nets are not supported, so no adj-fib has multiple paths.
 * The control plane is expected to remove a prefix configured for an interface
 * before the interface changes VRF.
 * So while the following config is accepted:
 *    set interface address 192.168.1.1/32 GigE0
 *    ip arp 192.168.1.2 GigE0 dead.dead.dead
 *    set interface ip table GigE0 2
 * it does not result in the desired behaviour.
 *
 *  - attached export.
 *
 * Further to adj-fib maintenance above consider the following config:
 *    set interface address 192.168.1.1/24 GigE0
 *    ip route add table 2 192.168.1.0/24 GigE0
 * Traffic destined for 192.168.1.2 in table 2 will generate an ARP request
 * on GigE0. However, since GigE0 is in table 0, all adj-fibs will be added in
 * FIB 0. Hence all hosts in the sub-net are unreachable from table 2. To resolve
 * this, all adj-fib and local prefixes are exported (i.e. copied) from the 
 * 'export' table 0, to the 'import' table 2. There can be many import tables
 * for a single export table.
 *
 *  - recursive route resolution
 *
 *   A recursive route is of the form:
 *       1.1.1.1/32 via 10.10.10.10
 * i.e. a route for which no egress interface is provided. In order to forward
 * traffic to 1.1.1.1/32 the FIB must therefore first determine how to forward
 * traffic to 10.10.10.10/32. This is recursive resolution.
 * Recursive resolution, just like normal resolution, proceeds via a longest
 * prefix match for the 'via-address' 10.10.10.10. Note it is only possible
 * to add routes via an address (i.e. a /32 or /128) not via a shorter mask
 * prefix. There is no use case for the latter.
 * Since recursive resolution proceeds via a longest prefix match, the entry
 * in the FIB that will resolve the recursive route, termed the via-entry, may
 * change as other routes are added to the FIB. Consider the recursive
 * route shown above, and this non-recursive route:
 *       10.10.10.0/24 via 192.168.16.1 GigE0
 * The entry for 10.10.10.0/24 is thus the resolving via-entry. If this entry is
 * modified, to say;
 *       10.10.10.0/24 via 192.16.1.3 GigE0
 * Then packet for 1.1.1.1/32 must also be sent to the new next-hop.
 * Now consider the addition of;
 *       10.10.10.0/28 via 192.168.16.2 GigE0
 * The more specific /28 is a better longest prefix match and thus becomes the
 * via-entry. Removal of the /28 means the resolution will revert to the /24.
 * The tracking to the changes in recursive resolution is the requirement of
 * the FIB. When the forwarding information of the via-entry changes a back-walk
 * is used to update dependent recursive routes. When new routes are added to
 * the table the cover tracking feature provides the necessary notifications to
 * the via-entry routes.
 * The adjacency constructed for 1.1.1.1/32 will be a recursive adjacency
 * whose next adjacency will be contributed from the via-entry. Maintaining
 * the validity of this recursive adjacency is a requirement of the FIB.
 *
 *  - recursive loop avoidance
 *
 * Consider this set of routes:
 *     1.1.1.1/32 via 2.2.2.2
 *     2.2.2.2/32 via 3.3.3.3
 *     3.3.3.3/32 via 1.1.1.1
 * this is termed a recursion loop - all of the routes in the loop are
 * unresolved in so far as they do not have a resolving adjacency, but each
 * is resolved because the via-entry is known. It is important here to note
 * the distinction between the control-plane objects and the data-plane objects
 * (more details in the implementation section). The control plane objects must
 * allow the loop to form (i.e. the graph becomes cyclic), however, the
 * data-plane absolutely must not allow the loop to form, otherwise the packet
 * would loop indefinitely and never egress the device - meltdown would follow.
 * The control plane must allow the loop to form, because when the loop breaks,
 * all members of the loop need to be updated. Forming the loop allows the
 * dependencies to be correctly setup to allow this to happen.
 * There is no limit to the depth of recursion supported by VPP so:
 *    9.9.9.100/32 via 9.9.9.99
 *    9.9.9.99/32  via 9.9.9.98
 *    9.9.9.98/32  via 9.9.9.97
 *      ... turtles, turtles, turtles ...
 *    9.9.9.1/32 via 10.10.10.10 Gig0
 * is supported to as many layers of turtles is desired, however, when
 * back-walking a graph (in this case from 9.9.9.1/32 up toward 9.9.9.100/32)
 * a FIB needs to differentiate the case where the recursion is deep versus
 * the case where the recursion is looped. A simple method, employed by VPP FIB,
 * is to limit the number of steps. VPP FIB limit is 16. Typical BGP scenarios
 * in the wild do not exceed 3 (BGP Inter-AS option C).
 * 
 * - Fast Convergence
 * 
 * After a network topology change, the 'convergence' time, is the time taken
 * for the router to complete a transition to forward traffic using the new
 * topology. The convergence time is therefore a summation of the time to;
 *  - detect the failure.
 *  - calculate the new 'best path' information
 *  - download the new best paths to the data-plane.
 *  - install those best best in data-plane forwarding.
 * The last two points are of relevance to VPP architecture. The download API is
 * binary and batch, details are not discussed here. There is no HW component to
 * programme, installation time is bounded by the memory allocation and table
 * lookup and insert access times.
 *
 * 'Fast' convergence refers to a set of technologies that a FIB can employ to
 * completely or partially restore forwarding whilst the convergence actions
 * listed above are ongoing. Fast convergence technologies are further
 * sub-divided into Prefix Independent Convergence (PIC) and Loop Free
 * Alternate path Fast re-route (LFA-FRR or sometimes called IP-FRR) which
 * affect recursive and non-recursive routes respectively.
 *
 * LFA-FRR
 *
 * Consider the network topology below:
 *
 *          C
 *        /   \
 *  X -- A --- B - Y
 *       |     |
 *       D     F
 *        \   /
 *          E
 *
 * all links are equal cost, traffic is passing from X to Y. the best path is
 * X-A-B-Y. There are two alternative paths, one via C and one via E. An
 * alternate path is considered to be loop free if no other router on that path
 * would forward the traffic back to the sender. Consider router C, its best
 * path to Y is via B, so if A were to send traffic destined to Y to C, then C
 * would forward that traffic to B - this is a loop-free alternate path. In
 * contrast consider router D. D's shortest path to Y is via A, so if A were to
 * send traffic destined to Y via D, then D would send it back to A; this is
 * not a loop-free alternate path. There are several points of note;
 *   - we are considering the pre-failure routing topology
 *   - any equal-cost multi-path between A and B is also a LFA path.
 *   - in order for A to calculate LFA paths it must be aware of the best-path
 *     to Y from the perspective of D. These calculations are thus limited to
 *     routing protocols that have a full view of the network topology, i.e.
 *     link-state DB protocols like OSPF or an SDN controller. LFA protected
 *     prefixes are thus non-recursive.
 *
 * LFA is specified as a 1 to 1 redundancy; a primary path has only one LFA
 * (a.k.a. backup) path. To my knowledge this limitation is one of complexity
 * in the calculation of and capacity planning using a 1-n redundancy. 
 *
 * In the event that the link A-B fails, the alternate path via C can be used.
 * In order to provide 'fast' failover in the event of a failure, the control
 * plane will download both the primary and the backup path to the FIB. It is
 * then a requirement of the FIB to perform the failover (a.k.a cutover) from
 * the primary to the backup path as quickly as possible, and particularly
 * without any other control-plane intervention. The expectation is cutover is
 * less than 50 milli-seconds - a value allegedly from the VOIP QoS. Note that
 * cutover time still includes the fault detection time, which in a vitalised
 * environment could be the dominant factor. Failure detection can be either a
 * link down, which will affect multiple paths on a multi-access interface, or
 * via a specific path heartbeat (i.e. BFD). 
 * At this time VPP does not support LFA, that is it does not support the
 * installation of a primary and backup path[s] for a route. However, it does
 * support ECMP, and VPP FIB is designed to quickly remove failed paths from
 * the ECMP set, however, it does not insert shared objects specific to the
 * protected resource into the forwarding object graph, since this would incur
 * a forwarding/performance cost. Failover time is thus route number dependent.
 * Details are provided in the implementation section below.
 *
 * PIC
 *
 * PIC refers to the concept that the converge time should be independent of
 * the number of prefixes/routes that are affected by the failure. PIC is
 * therefore most appropriate when considering networks with large number of
 * prefixes, i.e. BGP networks and thus recursive prefixes. There are several
 * flavours of PIC covering different locations of protection and failure
 * scenarios. An outline is given below, see the literature for more details:
 *
 * Y/16 - CE1 -- PE1---\
 *                | \   P1---\
 *                |  \        PE3 -- CE3 - X/16
 *                |   - P2---/
 * Y/16 - CE2 -- PE2---/
 *
 * CE = customer edge, PE = provider edge. external-BGP runs between customer
 * and provider, internal-BGP runs between provider and provider.
 *
 * 1) iBGP PIC-core: consider traffic from CE1 to X/16 via CE3. On PE1 there is
 *    are routes;
 *       X/16 (and hundreds of thousands of others like it)
 *         via PE3
 *    and
 *      PE3/32 (its loopback address)
 *        via 10.0.0.1 Link0 (this is P1)
 *        via 10.1.1.1 Link1 (this is P2)
 * the failure is the loss of link0 or link1
 * As in all PIC scenarios, in order to provide prefix independent convergence
 * it must be that the route for X/16 (and all other routes via PE3) do not
 * need to be updated in the FIB. The FIB therefore needs to update a single
 * object that is shared by all routes - once this shared object is updated,
 * then all routes using it will be instantly updated to use the new forwarding
 * information. In this case the shared object is the resolving route via PE3.
 * Once the route via PE3 is updated via IGP (OSPF) convergence, then all
 * recursive routes that resolve through it are also updated. VPP FIB
 * implements this scenario via a recursive-adjacency. the X/16 and it sibling
 * routes share a recursive-adjacency that links to/points at/stacks on the
 * normal adjacency contributed by the route for PE3. Once this shared
 * recursive adj is re-linked then all routes are switched to using the new
 * forwarding information. This is shown below;
 *
 * pre-failure;
 *   X/16 --> R-ADJ-1 --> ADJ-1-PE3 (multi-path via P1 and P2)
 *
 * post-failure:
 *   X/16 --> R-ADJ-1 --> ADJ-2-PE3 (single path via P1)
 *
 * note that R-ADJ-1 (the recursive adj) remains in the forwarding graph,
 * therefore X/16 (and all its siblings) is not updated.
 * X/16 and its siblings share the recursive adj since they share the same
 * path-list. It is the path-list object that contributes the recursive-adj
 * (see next section for more details)
 *
 *
 * 2) iBGP PIC-edge; Traffic from CE3 to Y/16. On PE3 there is are routes;
 *      Y/16  (and hundreds of thousands of others like it)
 *        via PE1
 *        via PE2 
 *  and
 *     PE1/32 (PE1's loopback address)
 *       via 10.0.2.2 Link0 (this is P1)
 *     PE2/32 (PE2's loopback address)
 *       via 10.0.3.3 Link1 (this is P2)
 *
 * the failure is the loss of reachability to PE2. this could be either the
 * loss of the link P2-PE2 or the loss of the node PE2. This is detected either
 * by the withdrawal of the PE2's loopback route or by some form of failure
 * detection (i.e. BFD).
 * VPP FIB again provides PIC via the use of the shared recursive-adj. Y/16 and
 * its siblings will again share a path-list for the list {PE1,PE2}, this
 * path-list will contribute a multi-path-recursive-adj, i.e. a multi-path-adj
 * with each choice therein being another adj;
 *
 *  Y/16 -> RM-ADJ --> ADJ1 (for PE1)
 *                 --> ADJ2 (for PE2)
 *
/*
 * Copyright (c) 2015 Cisco and/or its affiliates.
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at:
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
/*
 * interface_output.c: interface output node
 *
 * Copyright (c) 2008 Eliot Dresselhaus
 *
 * Permission is hereby granted, free of charge, to any person obtaining
 * a copy of this software and associated documentation files (the
 * "Software"), to deal in the Software without restriction, including
 * without limitation the rights to use, copy, modify, merge, publish,
 * distribute, sublicense, and/or sell copies of the Software, and to
 * permit persons to whom the Software is furnished to do so, subject to
 * the following conditions:
 *
 * The above copyright notice and this permission notice shall be
 * included in all copies or substantial portions of the Software.
 *
 *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
 *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
 *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
 *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
 *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 */

#include <vnet/vnet.h>
#include <vnet/ip/icmp46_packet.h>
#include <vnet/ethernet/packet.h>
#include <vnet/ip/format.h>
#include <vnet/ip/ip4.h>
#include <vnet/ip/ip6.h>
#include <vnet/udp/udp_packet.h>
#include <vnet/feature/feature.h>
#include <vnet/classify/pcap_classify.h>
#include <vnet/interface_output.h>
#include <vppinfra/vector/mask_compare.h>
#include <vppinfra/vector/compress.h>

typedef struct
{
  u32 sw_if_index;
  u32 flags;
  u8 data[128 - 2 * sizeof (u32)];
}
interface_output_trace_t;

#ifndef CLIB_MARCH_VARIANT
u8 *
format_vnet_interface_output_trace (u8 * s, va_list * va)
{
  CLIB_UNUSED (vlib_main_t * vm) = va_arg (*va, vlib_main_t *);
  vlib_node_t *node = va_arg (*va, vlib_node_t *);
  interface_output_trace_t *t = va_arg (*va, interface_output_trace_t *);
  vnet_main_t *vnm = vnet_get_main ();
  vnet_sw_interface_t *si;
  u32 indent;

  if (t->sw_if_index != (u32) ~ 0)
    {
      indent = format_get_indent (s);

      if (pool_is_free_index
	  (vnm->interface_main.sw_interfaces, t->sw_if_index))
	{
	  /* the interface may have been deleted by the time the trace is printed */
	  s = format (s, "sw_if_index: %d ", t->sw_if_index);
	}
      else
	{
	  si = vnet_get_sw_interface (vnm, t->sw_if_index);
	  s =
	    format (s, "%U ", format_vnet_sw_interface_name, vnm, si,
		    t->flags);
	}
      s =
	format (s, "\n%U%U", format_white_space, indent,
		node->format_buffer ? node->format_buffer : format_hex_bytes,
		t->data, sizeof (t->data));
    }
  return s;
}
#endif /* CLIB_MARCH_VARIANT */

static void
vnet_interface_output_trace (vlib_main_t * vm,
			     vlib_node_runtime_t * node,
			     vlib_frame_t * frame, uword n_buffers)
{
  u32 n_left, *from;

  n_left = n_buffers;
  from = vlib_frame_vector_args (frame);

  while (n_left >= 4)
    {
      u32 bi0, bi1;
      vlib_buffer_t *b0, *b1;
      interface_output_trace_t *t0, *t1;

      /* Prefetch next iteration. */
      vlib_prefetch_buffer_with_index (vm, from[2], LOAD);
      vlib_prefetch_buffer_with_index (vm, from[3], LOAD);

      bi0 = from[0];
      bi1 = from[1];

      b0 = vlib_get_buffer (vm, bi0);
      b1 = vlib_get_buffer (vm, bi1);

      if (b0->flags & VLIB_BUFFER_IS_TRACED)
	{
	  t0 = vlib_add_trace (vm, node, b0, sizeof (t0[0]));
	  t0->sw_if_index = vnet_buffer (b0)->sw_if_index[VLIB_TX];
	  t0->flags = b0->flags;
	  clib_memcpy_fast (t0->data, vlib_buffer_get_current (b0),
			    sizeof (t0->data));
	}
      if (b1->flags & VLIB_BUFFER_IS_TRACED)
	{
	  t1 = vlib_add_trace (vm, node, b1, sizeof (t1[0]));
	  t1->sw_if_index = vnet_buffer (b1)->sw_if_index[VLIB_TX];
	  t1->flags = b1->flags;
	  clib_memcpy_fast (t1->data, vlib_buffer_get_current (b1),
			    sizeof (t1->data));
	}
      from += 2;
      n_left -= 2;
    }

  while (n_left >= 1)
    {
      u32 bi0;
      vlib_buffer_t *b0;
      interface_output_trace_t *t0;

      bi0 = from[0];

      b0 = vlib_get_buffer (vm, bi0);

      if (b0->flags & VLIB_BUFFER_IS_TRACED)
	{
	  t0 = vlib_add_trace (vm, node, b0, sizeof (t0[0]));
	  t0->sw_if_index = vnet_buffer (b0)->sw_if_index[VLIB_TX];
	  t0->flags = b0->flags;
	  clib_memcpy_fast (t0->data, vlib_buffer_get_current (b0),
			    sizeof (t0->data));
	}
      from += 1;
      n_left -= 1;
    }
}

static_always_inline void
vnet_interface_output_handle_offload (vlib_main_t *vm, vlib_buffer_t *b)
{
  vnet_calc_checksums_inline (vm, b, b->flags & VNET_BUFFER_F_IS_IP4,
			      b->flags & VNET_BUFFER_F_IS_IP6);
}

static_always_inline uword
vnet_interface_output_node_inline (vlib_main_t *vm, u32 sw_if_index,
				   vlib_combined_counter_main_t *ccm,
				   vlib_buffer_t **b, u32 config_index, u8 arc,
				   u32 n_left, int do_tx_offloads,
				   int arc_or_subif)
{
  u32 n_bytes = 0;
  u32 n_bytes0, n_bytes1, n_bytes2, n_bytes3;
  u32 ti = vm->thread_index;

  while (n_left >= 8)
    {
      u32 or_flags;

      /* Prefetch next iteration. */
      vlib_prefetch_buffer_header (b[4], LOAD);
      vlib_prefetch_buffer_header (b[5], LOAD);
      vlib_prefetch_buffer_header (b[6], LOAD);
      vlib_prefetch_buffer_header (b[7], LOAD);

      if (do_tx_offloads)
	or_flags = b[0]->flags | b[1]->flags | b[2]->flags | b[3]->flags;

      /* Be grumpy about zero length buffers for benefit of
	 driver tx function. */
      ASSERT (b[0]->current_length > 0);
      ASSERT (b[1]->current_length > 0);
      ASSERT (b[2]->current_length > 0);
      ASSERT (b[3]->current_length > 0);

      n_bytes += n_bytes0 = vlib_buffer_length_in_chain (vm, b[0]);
      n_bytes += n_bytes1 = vlib_buffer_length_in_chain