Internet on FIRE

/*

 *        BIRD -- BGP Packet Processing

 *

 *        (c) 2000 Martin Mares <mj@ucw.cz>

 *        (c) 2008--2016 Ondrej Zajicek <santiago@crfreenet.org>

 *        (c) 2008--2016 CZ.NIC z.s.p.o.

 *

 *        Can be freely distributed and used under the terms of the GNU GPL.

 */

#undef LOCAL_DEBUG

#include <stdlib.h>

#include "nest/bird.h"

#include "nest/iface.h"

#include "nest/protocol.h"

#include "nest/route.h"

#include "nest/attrs.h"

#include "nest/mrtdump.h"

#include "conf/conf.h"

#include "lib/unaligned.h"

#include "lib/flowspec.h"

#include "lib/socket.h"

#include "nest/cli.h"

#include "bgp.h"

#define BGP_RR_REQUEST                0

#define BGP_RR_BEGIN                1

#define BGP_RR_END                2

#define BGP_NLRI_MAX                (4 + 1 + 32)

#define BGP_MPLS_BOS                1        /* Bottom-of-stack bit */

#define BGP_MPLS_MAX                10        /* Max number of labels that 24*n <= 255 */

#define BGP_MPLS_NULL                3        /* Implicit NULL label */

#define BGP_MPLS_MAGIC                0x800000 /* Magic withdraw label value, RFC 3107 3 */

static struct tbf rl_rcv_update = TBF_DEFAULT_LOG_LIMITS;

static struct tbf rl_snd_update = TBF_DEFAULT_LOG_LIMITS;

/* Table for state -> RFC 6608 FSM error subcodes */

static byte fsm_err_subcode[BS_MAX] = {

  [BS_OPENSENT] = 1,

  [BS_OPENCONFIRM] = 2,

  [BS_ESTABLISHED] = 3

};

static struct bgp_channel *

bgp_get_channel(struct bgp_proto *p, u32 afi)

{

  uint i;

  for (i = 0; i < p->channel_count; i++)

    if (p->afi_map[i] == afi)

      return p->channel_map[i];

  return NULL;

}

static inline void

put_af3(byte *buf, u32 id)

{

  put_u16(buf, id >> 16);

  buf[2] = id & 0xff;

}

static inline void

put_af4(byte *buf, u32 id)

{

  put_u16(buf, id >> 16);

  buf[2] = 0;

  buf[3] = id & 0xff;

}

static inline u32

get_af3(byte *buf)

{

  return (get_u16(buf) << 16) | buf[2];

}

static inline u32

get_af4(byte *buf)

{

  return (get_u16(buf) << 16) | buf[3];

}

/*

 * MRT Dump format is not semantically specified.

 * We will use these values in appropriate fields:

 *

 * Local AS, Remote AS - configured AS numbers for given BGP instance.

 * Local IP, Remote IP - IP addresses of the TCP connection (0 if no connection)

 *

 * We dump two kinds of MRT messages: STATE_CHANGE (for BGP state

 * changes) and MESSAGE (for received BGP messages).

 *

 * STATE_CHANGE uses always AS4 variant, but MESSAGE uses AS4 variant

 * only when AS4 session is established and even in that case MESSAGE

 * does not use AS4 variant for initial OPEN message. This strange

 * behavior is here for compatibility with Quagga and Bgpdump,

 */

static byte *

mrt_put_bgp4_hdr(byte *buf, struct bgp_conn *conn, int as4)

{

  struct bgp_proto *p = conn->bgp;

  uint v4 = ipa_is_ip4(p->cf->remote_ip);

  if (as4)

  {

    put_u32(buf+0, p->remote_as);

    put_u32(buf+4, p->public_as);

    buf+=8;

  }

  else

  {

    put_u16(buf+0, (p->remote_as <= 0xFFFF) ? p->remote_as : AS_TRANS);

    put_u16(buf+2, (p->public_as <= 0xFFFF) ? p->public_as : AS_TRANS);

    buf+=4;

  }

  put_u16(buf+0, (p->neigh && p->neigh->iface) ? p->neigh->iface->index : 0);

  put_u16(buf+2, v4 ? BGP_AFI_IPV4 : BGP_AFI_IPV6);

  buf+=4;

  if (v4)

  {

    buf = put_ip4(buf, conn->sk ? ipa_to_ip4(conn->sk->daddr) : IP4_NONE);

    buf = put_ip4(buf, conn->sk ? ipa_to_ip4(conn->sk->saddr) : IP4_NONE);

  }

  else

  {

    buf = put_ip6(buf, conn->sk ? ipa_to_ip6(conn->sk->daddr) : IP6_NONE);

    buf = put_ip6(buf, conn->sk ? ipa_to_ip6(conn->sk->saddr) : IP6_NONE);

  }

  return buf;

}

static void

mrt_dump_bgp_packet(struct bgp_conn *conn, byte *pkt, uint len)

{

  byte *buf = alloca(128+len);        /* 128 is enough for MRT headers */

  byte *bp = buf + MRTDUMP_HDR_LENGTH;

  int as4 = conn->bgp->as4_session;

  bp = mrt_put_bgp4_hdr(bp, conn, as4);

  memcpy(bp, pkt, len);

  bp += len;

  mrt_dump_message(&conn->bgp->p, BGP4MP, as4 ? BGP4MP_MESSAGE_AS4 : BGP4MP_MESSAGE,

                   buf, bp-buf);

}

static inline u16

convert_state(uint state)

{

  /* Convert state from our BS_* values to values used in MRTDump */

  return (state == BS_CLOSE) ? 1 : state + 1;

}

void

mrt_dump_bgp_state_change(struct bgp_conn *conn, uint old, uint new)

{

  byte buf[128];

  byte *bp = buf + MRTDUMP_HDR_LENGTH;

  bp = mrt_put_bgp4_hdr(bp, conn, 1);

  put_u16(bp+0, convert_state(old));

  put_u16(bp+2, convert_state(new));

  bp += 4;

  mrt_dump_message(&conn->bgp->p, BGP4MP, BGP4MP_STATE_CHANGE_AS4, buf, bp-buf);

}

static byte *

bgp_create_notification(struct bgp_conn *conn, byte *buf)

{

  struct bgp_proto *p = conn->bgp;

  BGP_TRACE(D_PACKETS, "Sending NOTIFICATION(code=%d.%d)", conn->notify_code, conn->notify_subcode);

  buf[0] = conn->notify_code;

  buf[1] = conn->notify_subcode;

  memcpy(buf+2, conn->notify_data, conn->notify_size);

  return buf + 2 + conn->notify_size;

}

/* Capability negotiation as per RFC 5492 */

const struct bgp_af_caps *

bgp_find_af_caps(struct bgp_caps *caps, u32 afi)

{

  struct bgp_af_caps *ac;

  WALK_AF_CAPS(caps, ac)

    if (ac->afi == afi)

      return ac;

  return NULL;

}

static struct bgp_af_caps *

bgp_get_af_caps(struct bgp_caps *caps, u32 afi)

{

  struct bgp_af_caps *ac;

  WALK_AF_CAPS(caps, ac)

    if (ac->afi == afi)

      return ac;

  ac = &caps->af_data[caps->af_count++];

  memset(ac, 0, sizeof(struct bgp_af_caps));

  ac->afi = afi;

  return ac;

}

static int

bgp_af_caps_cmp(const void *X, const void *Y)

{

  const struct bgp_af_caps *x = X, *y = Y;

  return (x->afi < y->afi) ? -1 : (x->afi > y->afi) ? 1 : 0;

}

static byte *

bgp_write_capabilities(struct bgp_conn *conn, byte *buf)

{

  struct bgp_proto *p = conn->bgp;

  struct bgp_channel *c;

  struct bgp_caps *caps;

  struct bgp_af_caps *ac;

  uint any_ext_next_hop = 0;

  uint any_add_path = 0;

  byte *data;

  /* Prepare bgp_caps structure */

  int n = list_length(&p->p.channels);

  caps = mb_allocz(p->p.pool, sizeof(struct bgp_caps) + n * sizeof(struct bgp_af_caps));

  conn->local_caps = caps;

  caps->as4_support = p->cf->enable_as4;

  caps->ext_messages = p->cf->enable_extended_messages;

  caps->route_refresh = p->cf->enable_refresh;

  caps->enhanced_refresh = p->cf->enable_refresh;

  if (caps->as4_support)

    caps->as4_number = p->public_as;

  if (p->cf->gr_mode)

  {

    caps->gr_aware = 1;

    caps->gr_time = p->cf->gr_time;

    caps->gr_flags = p->p.gr_recovery ? BGP_GRF_RESTART : 0;

  }

  /* Allocate and fill per-AF fields */

  WALK_LIST(c, p->p.channels)

  {

    ac = &caps->af_data[caps->af_count++];

    ac->afi = c->afi;

    ac->ready = 1;

    ac->ext_next_hop = bgp_channel_is_ipv4(c) && c->cf->ext_next_hop;

    any_ext_next_hop |= ac->ext_next_hop;

    ac->add_path = c->cf->add_path;

    any_add_path |= ac->add_path;

    if (c->cf->gr_able)

    {

      ac->gr_able = 1;

      if (p->p.gr_recovery)

        ac->gr_af_flags |= BGP_GRF_FORWARDING;

    }

  }

  /* Sort capability fields by AFI/SAFI */

  qsort(caps->af_data, caps->af_count, sizeof(struct bgp_af_caps), bgp_af_caps_cmp);

  /* Create capability list in buffer */

  /*

   * Note that max length is ~ 20+14*af_count. With max 12 channels that is

   * 188. Option limit is 253 and buffer size is 4096, so we cannot overflow

   * unless we add new capabilities or more AFs.

   */

  WALK_AF_CAPS(caps, ac)

    if (ac->ready)

    {

      *buf++ = 1;                /* Capability 1: Multiprotocol extensions */

      *buf++ = 4;                /* Capability data length */

      put_af4(buf, ac->afi);

      buf += 4;

    }

  if (caps->route_refresh)

  {

    *buf++ = 2;                        /* Capability 2: Support for route refresh */

    *buf++ = 0;                        /* Capability data length */

  }

  if (any_ext_next_hop)

  {

    *buf++ = 5;                        /* Capability 5: Support for extended next hop */

    *buf++ = 0;                        /* Capability data length, will be fixed later */

    data = buf;

    WALK_AF_CAPS(caps, ac)

      if (ac->ext_next_hop)

      {

        put_af4(buf, ac->afi);

        put_u16(buf+4, BGP_AFI_IPV6);

        buf += 6;

      }

    data[-1] = buf - data;

  }

  if (caps->ext_messages)

  {

    *buf++ = 6;                        /* Capability 6: Support for extended messages */

    *buf++ = 0;                        /* Capability data length */

  }

  if (caps->gr_aware)

  {

    *buf++ = 64;                /* Capability 64: Support for graceful restart */

    *buf++ = 0;                        /* Capability data length, will be fixed later */

    data = buf;

    put_u16(buf, caps->gr_time);

    buf[0] |= caps->gr_flags;

    buf += 2;

    WALK_AF_CAPS(caps, ac)

      if (ac->gr_able)

      {

        put_af3(buf, ac->afi);

        buf[3] = ac->gr_af_flags;

        buf += 4;

      }

    data[-1] = buf - data;

  }

  if (caps->as4_support)

  {

    *buf++ = 65;                /* Capability 65: Support for 4-octet AS number */

    *buf++ = 4;                        /* Capability data length */

    put_u32(buf, p->public_as);

    buf += 4;

  }

  if (any_add_path)

  {

    *buf++ = 69;                /* Capability 69: Support for ADD-PATH */

    *buf++ = 0;                        /* Capability data length, will be fixed later */

    data = buf;

    WALK_AF_CAPS(caps, ac)

      if (ac->add_path)

      {

        put_af3(buf, ac->afi);

        buf[3] = ac->add_path;

        buf += 4;

      }

    data[-1] = buf - data;

  }

  if (caps->enhanced_refresh)

  {

    *buf++ = 70;                /* Capability 70: Support for enhanced route refresh */

    *buf++ = 0;                        /* Capability data length */

  }

  return buf;

}

static void

bgp_read_capabilities(struct bgp_conn *conn, struct bgp_caps *caps, byte *pos, int len)

{

  struct bgp_proto *p = conn->bgp;

  struct bgp_af_caps *ac;

  int i, cl;

  u32 af;

  while (len > 0)

  {

    if (len < 2 || len < (2 + pos[1]))

      goto err;

    /* Capability length */

    cl = pos[1];

    /* Capability type */

    switch (pos[0])

    {

    case  1: /* Multiprotocol capability, RFC 4760 */

      if (cl != 4)

        goto err;

      af = get_af4(pos+2);

      ac = bgp_get_af_caps(caps, af);

      ac->ready = 1;

      break;

    case  2: /* Route refresh capability, RFC 2918 */

      if (cl != 0)

        goto err;

      caps->route_refresh = 1;

      break;

    case  5: /* Extended next hop encoding capability, RFC 5549 */

      if (cl % 6)

        goto err;

      for (i = 0; i < cl; i += 6)

      {

        /* Specified only for IPv4 prefixes with IPv6 next hops */

        if ((get_u16(pos+2+i+0) != BGP_AFI_IPV4) ||

            (get_u16(pos+2+i+4) != BGP_AFI_IPV6))

          continue;

        af = get_af4(pos+2+i);

        ac = bgp_get_af_caps(caps, af);

        ac->ext_next_hop = 1;

      }

      break;

    case  6: /* Extended message length capability, RFC draft */

      if (cl != 0)

        goto err;

      caps->ext_messages = 1;

      break;

    case 64: /* Graceful restart capability, RFC 4724 */

      if (cl % 4 != 2)

        goto err;

      /* Only the last instance is valid */

      WALK_AF_CAPS(caps, ac)

      {

        ac->gr_able = 0;

        ac->gr_af_flags = 0;

      }

      caps->gr_aware = 1;

      caps->gr_flags = pos[2] & 0xf0;

      caps->gr_time = get_u16(pos + 2) & 0x0fff;

      for (i = 2; i < cl; i += 4)

      {

        af = get_af3(pos+2+i);

        ac = bgp_get_af_caps(caps, af);

        ac->gr_able = 1;

        ac->gr_af_flags = pos[2+i+3];

      }

      break;

    case 65: /* AS4 capability, RFC 6793 */

      if (cl != 4)

        goto err;

      caps->as4_support = 1;

      caps->as4_number = get_u32(pos + 2);

      break;

    case 69: /* ADD-PATH capability, RFC 7911 */

      if (cl % 4)

        goto err;

      for (i = 0; i < cl; i += 4)

      {

        byte val = pos[2+i+3];

        if (!val || (val > BGP_ADD_PATH_FULL))

        {

          log(L_WARN "%s: Got ADD-PATH capability with unknown value %u, ignoring",

              p->p.name, val);

          break;

        }

      }

      for (i = 0; i < cl; i += 4)

      {

        af = get_af3(pos+2+i);

        ac = bgp_get_af_caps(caps, af);

        ac->add_path = pos[2+i+3];

      }

      break;

    case 70: /* Enhanced route refresh capability, RFC 7313 */

      if (cl != 0)

        goto err;

      caps->enhanced_refresh = 1;

      break;

      /* We can safely ignore all other capabilities */

    }

    ADVANCE(pos, len, 2 + cl);

  }

  return;

err:

  bgp_error(conn, 2, 0, NULL, 0);

  return;

}

static int

bgp_read_options(struct bgp_conn *conn, byte *pos, int len)

{

  struct bgp_proto *p = conn->bgp;

  struct bgp_caps *caps;

  int ol;

  /* Max number of announced AFIs is limited by max option length (255) */

  caps = alloca(sizeof(struct bgp_caps) + 64 * sizeof(struct bgp_af_caps));

  memset(caps, 0, sizeof(struct bgp_caps));

  while (len > 0)

  {

    if ((len < 2) || (len < (2 + pos[1])))

    { bgp_error(conn, 2, 0, NULL, 0); return -1; }

    ol = pos[1];

    if (pos[0] == 2)

    {

      /* BGP capabilities, RFC 5492 */

      if (p->cf->capabilities)

        bgp_read_capabilities(conn, caps, pos + 2, ol);

    }

    else

    {

      /* Unknown option */

      bgp_error(conn, 2, 4, pos, ol); /* FIXME: ol or ol+2 ? */

      return -1;

    }

    ADVANCE(pos, len, 2 + ol);

  }

  uint n = sizeof(struct bgp_caps) + caps->af_count * sizeof(struct bgp_af_caps);

  conn->remote_caps = mb_allocz(p->p.pool, n);

  memcpy(conn->remote_caps, caps, n);

  return 0;

}

static byte *

bgp_create_open(struct bgp_conn *conn, byte *buf)

{

  struct bgp_proto *p = conn->bgp;

  BGP_TRACE(D_PACKETS, "Sending OPEN(ver=%d,as=%d,hold=%d,id=%08x)",

            BGP_VERSION, p->public_as, p->cf->hold_time, p->local_id);

  buf[0] = BGP_VERSION;

  put_u16(buf+1, (p->public_as < 0xFFFF) ? p->public_as : AS_TRANS);

  put_u16(buf+3, p->cf->hold_time);

  put_u32(buf+5, p->local_id);

  if (p->cf->capabilities)

  {

    /* Prepare local_caps and write capabilities to buffer */

    byte *end = bgp_write_capabilities(conn, buf+12);

    uint len = end - (buf+12);

    buf[9] = len + 2;                /* Optional parameters length */

    buf[10] = 2;                /* Option 2: Capability list */

    buf[11] = len;                /* Option data length */

    return end;

  }

  else

  {

    /* Prepare empty local_caps */

    conn->local_caps = mb_allocz(p->p.pool, sizeof(struct bgp_caps));

    buf[9] = 0;                        /* No optional parameters */

    return buf + 10;

  }

  return buf;

}

static void

bgp_rx_open(struct bgp_conn *conn, byte *pkt, uint len)

{

  struct bgp_proto *p = conn->bgp;

  struct bgp_conn *other;

  u32 asn, hold, id;

  /* Check state */

  if (conn->state != BS_OPENSENT)

  { bgp_error(conn, 5, fsm_err_subcode[conn->state], NULL, 0); return; }

  /* Check message contents */

  if (len < 29 || len != 29 + (uint) pkt[28])

  { bgp_error(conn, 1, 2, pkt+16, 2); return; }

  if (pkt[19] != BGP_VERSION)

  { u16 val = BGP_VERSION; bgp_error(conn, 2, 1, (byte *) &val, 2); return; }

  asn = get_u16(pkt+20);

  hold = get_u16(pkt+22);

  id = get_u32(pkt+24);

  BGP_TRACE(D_PACKETS, "Got OPEN(as=%d,hold=%d,id=%R)", asn, hold, id);

  if (bgp_read_options(conn, pkt+29, pkt[28]) < 0)

    return;

  if (hold > 0 && hold < 3)

  { bgp_error(conn, 2, 6, pkt+22, 2); return; }

  /* RFC 6286 2.2 - router ID is nonzero and AS-wide unique */

  if (!id || (p->is_internal && id == p->local_id))

  { bgp_error(conn, 2, 3, pkt+24, -4); return; }

  struct bgp_caps *caps = conn->remote_caps;

  if (caps->as4_support)

  {

    u32 as4 = caps->as4_number;

    if ((as4 != asn) && (asn != AS_TRANS))

      log(L_WARN "%s: Peer advertised inconsistent AS numbers", p->p.name);

    if (as4 != p->remote_as)

    { as4 = htonl(as4); bgp_error(conn, 2, 2, (byte *) &as4, 4); return; }

  }

  else

  {

    if (asn != p->remote_as)

    { bgp_error(conn, 2, 2, pkt+20, 2); return; }

  }

  /* Check the other connection */

  other = (conn == &p->outgoing_conn) ? &p->incoming_conn : &p->outgoing_conn;

  switch (other->state)

  {

  case BS_CONNECT:

  case BS_ACTIVE:

    /* Stop outgoing connection attempts */

    bgp_conn_enter_idle_state(other);

    break;

  case BS_IDLE:

  case BS_OPENSENT:

  case BS_CLOSE:

    break;

  case BS_OPENCONFIRM:

    /*

     * Description of collision detection rules in RFC 4271 is confusing and

     * contradictory, but it is essentially:

     *

     * 1. Router with higher ID is dominant

     * 2. If both have the same ID, router with higher ASN is dominant [RFC6286]

     * 3. When both connections are in OpenConfirm state, one initiated by

     *    the dominant router is kept.

     *

     * The first line in the expression below evaluates whether the neighbor

     * is dominant, the second line whether the new connection was initiated

     * by the neighbor. If both are true (or both are false), we keep the new

     * connection, otherwise we keep the old one.

     */

    if (((p->local_id < id) || ((p->local_id == id) && (p->public_as < p->remote_as)))

        == (conn == &p->incoming_conn))

    {

      /* Should close the other connection */

      BGP_TRACE(D_EVENTS, "Connection collision, giving up the other connection");

      bgp_error(other, 6, 7, NULL, 0);

      break;

    }

    /* Fall thru */

  case BS_ESTABLISHED:

    /* Should close this connection */

    BGP_TRACE(D_EVENTS, "Connection collision, giving up this connection");

    bgp_error(conn, 6, 7, NULL, 0);

    return;

  default:

    bug("bgp_rx_open: Unknown state");

  }

  /* Update our local variables */

  conn->hold_time = MIN(hold, p->cf->hold_time);

  conn->keepalive_time = p->cf->keepalive_time ? : conn->hold_time / 3;

  conn->as4_session = conn->local_caps->as4_support && caps->as4_support;

  conn->ext_messages = conn->local_caps->ext_messages && caps->ext_messages;

  p->remote_id = id;

  DBG("BGP: Hold timer set to %d, keepalive to %d, AS to %d, ID to %x, AS4 session to %d\n",

      conn->hold_time, conn->keepalive_time, p->remote_as, p->remote_id, conn->as4_session);

  bgp_schedule_packet(conn, NULL, PKT_KEEPALIVE);

  bgp_start_timer(conn->hold_timer, conn->hold_time);

  bgp_conn_enter_openconfirm_state(conn);

}

/*

 *        Next hop handling

 */

#define REPORT(msg, args...) \

  ({ log(L_REMOTE "%s: " msg, s->proto->p.name, ## args); })

#define DISCARD(msg, args...) \

  ({ REPORT(msg, ## args); return; })

#define WITHDRAW(msg, args...) \

  ({ REPORT(msg, ## args); s->err_withdraw = 1; return; })

#define BAD_AFI                "Unexpected AF <%u/%u> in UPDATE"

#define BAD_NEXT_HOP        "Invalid NEXT_HOP attribute"

#define NO_NEXT_HOP        "Missing NEXT_HOP attribute"

#define NO_LABEL_STACK        "Missing MPLS stack"

static void

bgp_apply_next_hop(struct bgp_parse_state *s, rta *a, ip_addr gw, ip_addr ll)

{

  struct bgp_proto *p = s->proto;

  struct bgp_channel *c = s->channel;

  if (c->cf->gw_mode == GW_DIRECT)

  {

    neighbor *nbr = NULL;

    /* GW_DIRECT -> single_hop -> p->neigh != NULL */

    if (ipa_nonzero(gw))

      nbr = neigh_find2(&p->p, &gw, NULL, 0);

    else if (ipa_nonzero(ll))

      nbr = neigh_find2(&p->p, &ll, p->neigh->iface, 0);

    if (!nbr || (nbr->scope == SCOPE_HOST))

      WITHDRAW(BAD_NEXT_HOP);

    a->dest = RTD_UNICAST;

    a->nh.gw = nbr->addr;

    a->nh.iface = nbr->iface;

  }

  else /* GW_RECURSIVE */

  {

    if (ipa_zero(gw))

      WITHDRAW(BAD_NEXT_HOP);

    rtable *tab = ipa_is_ip4(gw) ? c->igp_table_ip4 : c->igp_table_ip6;

    s->hostentry = rt_get_hostentry(tab, gw, ll, c->c.table);

    if (!s->mpls)

      rta_apply_hostentry(a, s->hostentry, NULL);

    /* With MPLS, hostentry is applied later in bgp_apply_mpls_labels() */

  }

}

static void

bgp_apply_mpls_labels(struct bgp_parse_state *s, rta *a, u32 *labels, uint lnum)

{

  if (lnum > MPLS_MAX_LABEL_STACK)

  {

    REPORT("Too many MPLS labels ($u)", lnum);

    a->dest = RTD_UNREACHABLE;

    a->hostentry = NULL;

    a->nh = (struct nexthop) { };

    return;

  }

  /* Handle implicit NULL as empty MPLS stack */

  if ((lnum == 1) && (labels[0] == BGP_MPLS_NULL))

    lnum = 0;

  if (s->channel->cf->gw_mode == GW_DIRECT)

  {

    a->nh.labels = lnum;

    memcpy(a->nh.label, labels, 4*lnum);

  }

  else /* GW_RECURSIVE */

  {

    mpls_label_stack ms;

    ms.len = lnum;

    memcpy(ms.stack, labels, 4*lnum);

    rta_apply_hostentry(a, s->hostentry, &ms);

  }

}

static inline int

bgp_use_next_hop(struct bgp_export_state *s, eattr *a)

{

  struct bgp_proto *p = s->proto;

  ip_addr *nh = (void *) a->u.ptr->data;

  if (s->channel->cf->next_hop_self)

    return 0;

  if (s->channel->cf->next_hop_keep)

    return 1;

  /* Keep it when explicitly set in export filter */

  if (a->type & EAF_FRESH)

    return 1;

  /* Keep it when exported to internal peers */

  if (p->is_interior && ipa_nonzero(*nh))

    return 1;

  /* Keep it when forwarded between single-hop BGPs on the same iface */

  struct iface *ifa = (s->src && s->src->neigh) ? s->src->neigh->iface : NULL;

  return p->neigh && (p->neigh->iface == ifa);

}

static inline int

bgp_use_gateway(struct bgp_export_state *s)

{

  struct bgp_proto *p = s->proto;

  rta *ra = s->route->attrs;

  if (s->channel->cf->next_hop_self)

    return 0;

  /* We need one valid global gateway */

  if ((ra->dest != RTD_UNICAST) || ra->nh.next || ipa_zero(ra->nh.gw) || ipa_is_link_local(ra->nh.gw))

    return 0;

  /* Use it when exported to internal peers */

  if (p->is_interior)

    return 1;

  /* Use it when forwarded to single-hop BGP peer on on the same iface */

  return p->neigh && (p->neigh->iface == ra->nh.iface);

}

static void

bgp_update_next_hop_ip(struct bgp_export_state *s, eattr *a, ea_list **to)

{

  if (!a || !bgp_use_next_hop(s, a))

  {

    if (bgp_use_gateway(s))

    {

      rta *ra = s->route->attrs;

      ip_addr nh[1] = { ra->nh.gw };

      bgp_set_attr_data(to, s->pool, BA_NEXT_HOP, 0, nh, 16);

      if (s->mpls)

      {

        u32 implicit_null = BGP_MPLS_NULL;

        u32 *labels = ra->nh.labels ? ra->nh.label : &implicit_null;

        uint lnum = ra->nh.labels ? ra->nh.labels : 1;

        bgp_set_attr_data(to, s->pool, BA_MPLS_LABEL_STACK, 0, labels, lnum * 4);

      }

    }

    else

    {

      ip_addr nh[2] = { s->channel->next_hop_addr, s->channel->link_addr };

      bgp_set_attr_data(to, s->pool, BA_NEXT_HOP, 0, nh, ipa_nonzero(nh[1]) ? 32 : 16);

      /* TODO: Use local MPLS assigned label */

      if (s->mpls)

        bgp_unset_attr(to, s->pool, BA_MPLS_LABEL_STACK);

    }

  }

  /* Check if next hop is valid */

  a = bgp_find_attr(*to, BA_NEXT_HOP);

  if (!a)

    WITHDRAW(NO_NEXT_HOP);

  ip_addr *nh = (void *) a->u.ptr->data;

  ip_addr peer = s->proto->cf->remote_ip;

  uint len = a->u.ptr->length;

  /* Forbid zero next hop */

  if (ipa_zero(nh[0]) && ((len != 32) || ipa_zero(nh[1])))

    WITHDRAW(BAD_NEXT_HOP);

  /* Forbid next hop equal to neighbor IP */

  if (ipa_equal(peer, nh[0]) || ((len == 32) && ipa_equal(peer, nh[1])))

    WITHDRAW(BAD_NEXT_HOP);

  /* Forbid next hop with non-matching AF */

  if ((ipa_is_ip4(nh[0]) != bgp_channel_is_ipv4(s->channel)) &&

      !s->channel->ext_next_hop)

    WITHDRAW(BAD_NEXT_HOP);

  /* Just check if MPLS stack */

  if (s->mpls && !bgp_find_attr(*to, BA_MPLS_LABEL_STACK))

    WITHDRAW(NO_LABEL_STACK);

}

static uint

bgp_encode_next_hop_ip(struct bgp_write_state *s, eattr *a, byte *buf, uint size UNUSED)

{

  /* This function is used only for MP-BGP, see bgp_encode_next_hop() for IPv4 BGP */

  ip_addr *nh = (void *) a->u.ptr->data;

  uint len = a->u.ptr->length;

  ASSERT((len == 16) || (len == 32));

  /*

   * Both IPv4 and IPv6 next hops can be used (with ext_next_hop enabled). This

   * is specified in RFC 5549 for IPv4 and in RFC 4798 for IPv6. The difference

   * is that IPv4 address is directly encoded with IPv4 NLRI, but as IPv4-mapped

   * IPv6 address with IPv6 NLRI.

   */

  if (bgp_channel_is_ipv4(s->channel) && ipa_is_ip4(nh[0]))

  {

    put_ip4(buf, ipa_to_ip4(nh[0]));

    return 4;

  }

  put_ip6(buf, ipa_to_ip6(nh[0]));

  if (len == 32)

    put_ip6(buf+16, ipa_to_ip6(nh[1]));

  return len;

}

static void

bgp_decode_next_hop_ip(struct bgp_parse_state *s, byte *data, uint len, rta *a)

{

  struct bgp_channel *c = s->channel;

  struct adata *ad = lp_alloc_adata(s->pool, 32);

  ip_addr *nh = (void *) ad->data;

  if (len == 4)

  {

    nh[0] = ipa_from_ip4(get_ip4(data));

    nh[1] = IPA_NONE;

  }

  else if (len == 16)

  {

    nh[0] = ipa_from_ip6(get_ip6(data));

    nh[1] = IPA_NONE;

    if (ipa_is_link_local(nh[0]))

    { nh[1] = nh[0]; nh[0] = IPA_NONE; }

  }

  else if (len == 32)

  {

    nh[0] = ipa_from_ip6(get_ip6(data));

    nh[1] = ipa_from_ip6(get_ip6(data+16));

    if (ipa_is_ip4(nh[0]) || !ip6_is_link_local(nh[1]))

      nh[1] = IPA_NONE;

  }

  else

    bgp_parse_error(s, 9);

  if (ipa_zero(nh[1]))

    ad->length = 16;

  if ((bgp_channel_is_ipv4(c) != ipa_is_ip4(nh[0])) && !c->ext_next_hop)

    WITHDRAW(BAD_NEXT_HOP);

  // XXXX validate next hop

  bgp_set_attr_ptr(&(a->eattrs), s->pool, BA_NEXT_HOP, 0, ad);

  bgp_apply_next_hop(s, a, nh[0], nh[1]);

}

static uint

bgp_encode_next_hop_vpn(struct bgp_write_state *s, eattr *a, byte *buf, uint size UNUSED)

{

  ip_addr *nh = (void *) a->u.ptr->data;

  uint len = a->u.ptr->length;

  ASSERT((len == 16) || (len == 32));

  /*

   * Both IPv4 and IPv6 next hops can be used (with ext_next_hop enabled). This

   * is specified in RFC 5549 for VPNv4 and in RFC 4659 for VPNv6. The difference

   * is that IPv4 address is directly encoded with VPNv4 NLRI, but as IPv4-mapped

   * IPv6 address with VPNv6 NLRI.

   */

  if (bgp_channel_is_ipv4(s->channel) && ipa_is_ip4(nh[0]))

  {

    put_u64(buf, 0); /* VPN RD is 0 */

    put_ip4(buf+8, ipa_to_ip4(nh[0]));

    return 12;

  }

  put_u64(buf, 0); /* VPN RD is 0 */

  put_ip6(buf+8, ipa_to_ip6(nh[0]));

  if (len == 16)

    return 24;

  put_u64(buf+24, 0); /* VPN RD is 0 */

  put_ip6(buf+32, ipa_to_ip6(nh[1]));

  return 48;

}

static void

bgp_decode_next_hop_vpn(struct bgp_parse_state *s, byte *data, uint len, rta *a)

{

  struct bgp_channel *c = s->channel;

  struct adata *ad = lp_alloc_adata(s->pool, 32);

  ip_addr *nh = (void *) ad->data;

  if (len == 12)

  {

    nh[0] = ipa_from_ip4(get_ip4(data+8));

    nh[1] = IPA_NONE;

  }

  else if (len == 24)

  {

    nh[0] = ipa_from_ip6(get_ip6(data+8));

    nh[1] = IPA_NONE;

    if (ipa_is_link_local(nh[0]))

    { nh[1] = nh[0]; nh[0] = IPA_NONE; }

  }

  else if (len == 48)

  {

    nh[0] = ipa_from_ip6(get_ip6(data+8));

    nh[1] = ipa_from_ip6(get_ip6(data+32));

    if (ipa_is_ip4(nh[0]) || !ip6_is_link_local(nh[1]))

      nh[1] = IPA_NONE;

  }

  else

    bgp_parse_error(s, 9);

  if (ipa_zero(nh[1]))

    ad->length = 16;

  /* XXXX which error */

  if ((get_u64(data) != 0) || ((len == 48) && (get_u64(data+24) != 0)))

    bgp_parse_error(s, 9);

  if ((bgp_channel_is_ipv4(c) != ipa_is_ip4(nh[0])) && !c->ext_next_hop)

    WITHDRAW(BAD_NEXT_HOP);

  // XXXX validate next hop

  bgp_set_attr_ptr(&(a->eattrs), s->pool, BA_NEXT_HOP, 0, ad);

  bgp_apply_next_hop(s, a, nh[0], nh[1]);

}

static uint

bgp_encode_next_hop_none(struct bgp_write_state *s UNUSED, eattr *a UNUSED, byte *buf UNUSED, uint size UNUSED)

{

  return 0;

}

static void

bgp_decode_next_hop_none(struct bgp_parse_state *s UNUSED, byte *data UNUSED, uint len UNUSED, rta *a UNUSED)

{

  /*

   * Although we expect no next hop and RFC 7606 7.11 states that attribute

   * MP_REACH_NLRI with unexpected next hop length is considered malformed,

   * FlowSpec RFC 5575 4 states that next hop shall be ignored on receipt.

   */

  return;

}

static void

bgp_update_next_hop_none(struct bgp_export_state *s, eattr *a, ea_list **to)

{

  /* NEXT_HOP shall not pass */

  if (a)

    bgp_unset_attr(to, s->pool, BA_NEXT_HOP);

}

/*

 *        UPDATE

 */

static void

bgp_rte_update(struct bgp_parse_state *s, net_addr *n, u32 path_id, rta *a0)

{

  if (path_id != s->last_id)

  {

    s->last_src = rt_get_source(&s->proto->p, path_id);

    s->last_id = path_id;

    rta_free(s->cached_rta);

    s->cached_rta = NULL;

  }

  if (!a0)

  {

    /* Route withdraw */

    rte_update2(&s->channel->c, n, NULL, s->last_src);

    return;

  }

  /* Prepare cached route attributes */

  if (s->cached_rta == NULL)

  {

    a0->src = s->last_src;

    /* Workaround for rta_lookup() breaking eattrs */

    ea_list *ea = a0->eattrs;

    s->cached_rta = rta_lookup(a0);

    a0->eattrs = ea;

  }

  rta *a = rta_clone(s->cached_rta);

  rte *e = rte_get_temp(a);

  e->pflags = 0;

  e->u.bgp.suppressed = 0;

  rte_update2(&s->channel->c, n, e, s->last_src);

}

static void

bgp_encode_mpls_labels(struct bgp_write_state *s UNUSED, adata *mpls, byte **pos, uint *size, byte *pxlen)

{

  u32 dummy = 0;

  u32 *labels = mpls ? (u32 *) mpls->data : &dummy;

  uint lnum = mpls ? (mpls->length / 4) : 1;

  for (uint i = 0; i < lnum; i++)

  {

    put_u24(*pos, labels[i] << 4);

    ADVANCE(*pos, *size, 3);

  }

  /* Add bottom-of-stack flag */

  (*pos)[-1] |= BGP_MPLS_BOS;

  *pxlen += 24 * lnum;

}

static void

bgp_decode_mpls_labels(struct bgp_parse_state *s, byte **pos, uint *len, uint *pxlen, rta *a)

{

  u32 labels[BGP_MPLS_MAX], label;

  uint lnum = 0;

  do {

    if (*pxlen < 24)

      bgp_parse_error(s, 1);

    label = get_u24(*pos);

    labels[lnum++] = label >> 4;

    ADVANCE(*pos, *len, 3);

    *pxlen -= 24;

    /* Withdraw: Magic label stack value 0x800000 according to RFC 3107, section 3, last paragraph */

    if (!a && !s->err_withdraw && (lnum == 1) && (label == BGP_MPLS_MAGIC))

      break;

  }

  while (!(label & BGP_MPLS_BOS));

  if (!a)

    return;

  /* Attach MPLS attribute unless we already have one */

  if (!s->mpls_labels)

  {

    s->mpls_labels = lp_alloc_adata(s->pool, 4*BGP_MPLS_MAX);

    bgp_set_attr_ptr(&(a->eattrs), s->pool, BA_MPLS_LABEL_STACK, 0, s->mpls_labels);

  }

  /* Overwrite data in the attribute */

  s->mpls_labels->length = 4*lnum;

  memcpy(s->mpls_labels->data, labels, 4*lnum);

  /* Update next hop entry in rta */

  bgp_apply_mpls_labels(s, a, labels, lnum);

  /* Attributes were changed, invalidate cached entry */

  rta_free(s->cached_rta);

  s->cached_rta = NULL;

  return;

}

static uint

bgp_encode_nlri_ip4(struct bgp_write_state *s, struct bgp_bucket *buck, byte *buf, uint size)

{

  byte *pos = buf;

  while (!EMPTY_LIST(buck->prefixes) && (size >= BGP_NLRI_MAX))

  {

    struct bgp_prefix *px = HEAD(buck->prefixes);

    struct net_addr_ip4 *net = (void *) px->net;

    /* Encode path ID */

    if (s->add_path)

    {

      put_u32(pos, px->path_id);

      ADVANCE(pos, size, 4);

    }

    /* Encode prefix length */

    *pos = net->pxlen;

    ADVANCE(pos, size, 1);

    /* Encode MPLS labels */

    if (s->mpls)

      bgp_encode_mpls_labels(s, s->mpls_labels, &pos, &size, pos - 1);

    /* Encode prefix body */

    ip4_addr a = ip4_hton(net->prefix);

    uint b = (net->pxlen + 7) / 8;

    memcpy(pos, &a, b);

    ADVANCE(pos, size, b);

    bgp_free_prefix(s->channel, px);

  }

  return pos - buf;

}

static void

bgp_decode_nlri_ip4(struct bgp_parse_state *s, byte *pos, uint len, rta *a)

{

  while (len)

  {

    net_addr_ip4 net;

    u32 path_id = 0;

    /* Decode path ID */

    if (s->add_path)

    {

      if (len < 5)

        bgp_parse_error(s, 1);

      path_id = get_u32(pos);

      ADVANCE(pos, len, 4);

    }

    /* Decode prefix length */

    uint l = *pos;

    ADVANCE(pos, len, 1);

    if (len < ((l + 7) / 8))

      bgp_parse_error(s, 1);

    /* Decode MPLS labels */

    if (s->mpls)

      bgp_decode_mpls_labels(s, &pos, &len, &l, a);

    if (l > IP4_MAX_PREFIX_LENGTH)

      bgp_parse_error(s, 10);

    /* Decode prefix body */

    ip4_addr addr = IP4_NONE;

    uint b = (l + 7) / 8;

    memcpy(&addr, pos, b);

    ADVANCE(pos, len, b);

    net = NET_ADDR_IP4(ip4_ntoh(addr), l);

    net_normalize_ip4(&net);

    // XXXX validate prefix

    bgp_rte_update(s, (net_addr *) &net, path_id, a);

  }

}

static uint

bgp_encode_nlri_ip6(struct bgp_write_state *s, struct bgp_bucket *buck, byte *buf, uint size)

{

  byte *pos = buf;

  while (!EMPTY_LIST(buck->prefixes) && (size >= BGP_NLRI_MAX))

  {

    struct bgp_prefix *px = HEAD(buck->prefixes);

    struct net_addr_ip6 *net = (void *) px->net;

    /* Encode path ID */

    if (s->add_path)

    {

      put_u32(pos, px->path_id);

      ADVANCE(pos, size, 4);

    }

    /* Encode prefix length */

    *pos = net->pxlen;

    ADVANCE(pos, size, 1);

    /* Encode MPLS labels */

    if (s->mpls)

      bgp_encode_mpls_labels(s, s->mpls_labels, &pos, &size, pos - 1);

    /* Encode prefix body */

    ip6_addr a = ip6_hton(net->prefix);

    uint b = (net->pxlen + 7) / 8;

    memcpy(pos, &a, b);

    ADVANCE(pos, size, b);

    bgp_free_prefix(s->channel, px);

  }

  return pos - buf;

}

static void

bgp_decode_nlri_ip6(struct bgp_parse_state *s, byte *pos, uint len, rta *a)

{

  while (len)

  {

    net_addr_ip6 net;

    u32 path_id = 0;

    /* Decode path ID */

    if (s->add_path)

    {

      if (len < 5)

        bgp_parse_error(s, 1);

      path_id = get_u32(pos);

      ADVANCE(pos, len, 4);

    }

    /* Decode prefix length */

    uint l = *pos;

    ADVANCE(pos, len, 1);

    if (len < ((l + 7) / 8))

      bgp_parse_error(s, 1);

    /* Decode MPLS labels */

    if (s->mpls)

      bgp_decode_mpls_labels(s, &pos, &len, &l, a);

    if (l > IP6_MAX_PREFIX_LENGTH)

      bgp_parse_error(s, 10);

    /* Decode prefix body */

    ip6_addr addr = IP6_NONE;

    uint b = (l + 7) / 8;

    memcpy(&addr, pos, b);

    ADVANCE(pos, len, b);

    net = NET_ADDR_IP6(ip6_ntoh(addr), l);

    net_normalize_ip6(&net);