lib/bfd.c

   1 /* Copyright (c) 2013 Nicira, Inc.
   2  *
   3  * Licensed under the Apache License, Version 2.0 (the "License");
   4  * you may not use this file except in compliance with the License.
   5  * You may obtain a copy of the License at:
   6  *
   7  *     http://www.apache.org/licenses/LICENSE-2.0
   8  *
   9  * Unless required by applicable law or agreed to in writing, software
  10  * distributed under the License is distributed on an "AS IS" BASIS,
  11  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  12  * See the License for the specific language governing permissions and
  13  * limitations under the License. */
  14
  15 #include <config.h>
  16 #include "bfd.h"
  17
  18 #include <arpa/inet.h>
  19 #include <netinet/in_systm.h>
  20 #include <netinet/ip.h>
  21
  22 #include "byte-order.h"
  23 #include "csum.h"
  24 #include "dpif.h"
  25 #include "dynamic-string.h"
  26 #include "flow.h"
  27 #include "hash.h"
  28 #include "hmap.h"
  29 #include "list.h"
  30 #include "netlink.h"
  31 #include "odp-util.h"
  32 #include "ofpbuf.h"
  33 #include "ovs-thread.h"
  34 #include "openvswitch/types.h"
  35 #include "packets.h"
  36 #include "poll-loop.h"
  37 #include "random.h"
  38 #include "smap.h"
  39 #include "timeval.h"
  40 #include "unixctl.h"
  41 #include "util.h"
  42 #include "vlog.h"
  43
  44 VLOG_DEFINE_THIS_MODULE(bfd);
  45
  46 /* XXX Finish BFD.
  47  *
  48  * The goal of this module is to replace CFM with something both more flexible
  49  * and standards compliant.  In service of this goal, the following needs to be
  50  * done.
  51  *
  52  * - Compliance
  53  *   * Implement Demand mode.
  54  *   * Go through the RFC line by line and verify we comply.
  55  *   * Test against a hardware implementation.  Preferably a popular one.
  56  *   * Delete BFD packets with nw_ttl != 255 in the datapath to prevent DOS
  57  *     attacks.
  58  *
  59  * - Unit tests.
  60  *
  61  * - Set TOS/PCP on the outer tunnel header when encapped.
  62  *
  63  * - Sending BFD messages should be in its own thread/process.
  64  *
  65  * - Scale testing.  How does it operate when there are large number of bfd
  66  *   sessions?  Do we ever have random flaps?  What's the CPU utilization?
  67  *
  68  * - Rely on data traffic for liveness by using BFD demand mode.
  69  *   If we're receiving traffic on a port, we can safely assume it's up (modulo
  70  *   unidrectional failures).  BFD has a demand mode in which it can stay quiet
  71  *   unless it feels the need to check the status of the port.  Using this, we
  72  *   can implement a strategy in which BFD only sends control messages on dark
  73  *   interfaces.
  74  *
  75  * - Depending on how one interprets the spec, it appears that a BFD session
  76  *   can never change bfd.LocalDiag to "No Diagnostic".  We should verify that
  77  *   this is what hardware implementations actually do.  Seems like "No
  78  *   Diagnostic" should be set once a BFD session state goes UP. */
  79
  80 #define BFD_VERSION 1
  81
  82 enum flags {
  83     FLAG_MULTIPOINT = 1 << 0,
  84     FLAG_DEMAND = 1 << 1,
  85     FLAG_AUTH = 1 << 2,
  86     FLAG_CTL = 1 << 3,
  87     FLAG_FINAL = 1 << 4,
  88     FLAG_POLL = 1 << 5
  89 };
  90
  91 enum state {
  92     STATE_ADMIN_DOWN = 0 << 6,
  93     STATE_DOWN = 1 << 6,
  94     STATE_INIT = 2 << 6,
  95     STATE_UP = 3 << 6
  96 };
  97
  98 enum diag {
  99     DIAG_NONE = 0,                /* No Diagnostic. */
 100     DIAG_EXPIRED = 1,             /* Control Detection Time Expired. */
 101     DIAG_ECHO_FAILED = 2,         /* Echo Function Failed. */
 102     DIAG_RMT_DOWN = 3,            /* Neighbor Signaled Session Down. */
 103     DIAG_FWD_RESET = 4,           /* Forwarding Plane Reset. */
 104     DIAG_PATH_DOWN = 5,           /* Path Down. */
 105     DIAG_CPATH_DOWN = 6,          /* Concatenated Path Down. */
 106     DIAG_ADMIN_DOWN = 7,          /* Administratively Down. */
 107     DIAG_RCPATH_DOWN = 8          /* Reverse Concatenated Path Down. */
 108 };
 109
 110 /* RFC 5880 Section 4.1
 111  *  0                   1                   2                   3
 112  *  0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
 113  * +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 114  * |Vers |  Diag   |Sta|P|F|C|A|D|M|  Detect Mult  |    Length     |
 115  * +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 116  * |                       My Discriminator                        |
 117  * +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 118  * |                      Your Discriminator                       |
 119  * +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 120  * |                    Desired Min TX Interval                    |
 121  * +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 122  * |                   Required Min RX Interval                    |
 123  * +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 124  * |                 Required Min Echo RX Interval                 |
 125  * +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ */
 126 struct msg {
 127     uint8_t vers_diag;    /* Version and diagnostic. */
 128     uint8_t flags;        /* 2bit State field followed by flags. */
 129     uint8_t mult;         /* Fault detection multiplier. */
 130     uint8_t length;       /* Length of this BFD message. */
 131     ovs_be32 my_disc;     /* My discriminator. */
 132     ovs_be32 your_disc;   /* Your discriminator. */
 133     ovs_be32 min_tx;      /* Desired minimum tx interval. */
 134     ovs_be32 min_rx;      /* Required minimum rx interval. */
 135     ovs_be32 min_rx_echo; /* Required minimum echo rx interval. */
 136 };
 137 BUILD_ASSERT_DECL(BFD_PACKET_LEN == sizeof(struct msg));
 138
 139 #define DIAG_MASK 0x1f
 140 #define VERS_SHIFT 5
 141 #define STATE_MASK 0xC0
 142 #define FLAGS_MASK 0x3f
 143
 144 struct bfd {
 145     struct hmap_node node;        /* In 'all_bfds'. */
 146     uint32_t disc;                /* bfd.LocalDiscr. Key in 'all_bfds' hmap. */
 147
 148     char *name;                   /* Name used for logging. */
 149
 150     bool cpath_down;              /* Concatenated Path Down. */
 151     uint8_t mult;                 /* bfd.DetectMult. */
 152
 153     enum state state;             /* bfd.SessionState. */
 154     enum state rmt_state;         /* bfd.RemoteSessionState. */
 155
 156     enum diag diag;               /* bfd.LocalDiag. */
 157     enum diag rmt_diag;           /* Remote diagnostic. */
 158
 159     enum flags flags;             /* Flags sent on messages. */
 160     enum flags rmt_flags;         /* Flags last received. */
 161
 162     uint32_t rmt_disc;            /* bfd.RemoteDiscr. */
 163
 164     uint8_t eth_dst[ETH_ADDR_LEN];/* Ethernet destination address. */
 165     bool eth_dst_set;             /* 'eth_dst' set through database. */
 166
 167     uint16_t udp_src;             /* UDP source port. */
 168
 169     /* All timers in milliseconds. */
 170     long long int rmt_min_rx;     /* bfd.RemoteMinRxInterval. */
 171     long long int rmt_min_tx;     /* Remote minimum TX interval. */
 172
 173     long long int cfg_min_tx;     /* Configured minimum TX rate. */
 174     long long int cfg_min_rx;     /* Configured required minimum RX rate. */
 175     long long int poll_min_tx;    /* Min TX negotating in a poll sequence. */
 176     long long int poll_min_rx;    /* Min RX negotating in a poll sequence. */
 177     long long int min_tx;         /* bfd.DesiredMinTxInterval. */
 178     long long int min_rx;         /* bfd.RequiredMinRxInterval. */
 179
 180     long long int last_tx;        /* Last TX time. */
 181     long long int next_tx;        /* Next TX time. */
 182     long long int detect_time;    /* RFC 5880 6.8.4 Detection time. */
 183
 184     int forwarding_override;      /* Manual override of 'forwarding' status. */
 185
 186     atomic_bool check_tnl_key;    /* Verify tunnel key of inbound packets? */
 187     atomic_int ref_cnt;
 188 };
 189
 190 static struct ovs_mutex mutex = OVS_MUTEX_INITIALIZER;
 191 static struct hmap all_bfds__ = HMAP_INITIALIZER(&all_bfds__);
 192 static struct hmap *const all_bfds OVS_GUARDED_BY(mutex) = &all_bfds__;
 193
 194 static bool bfd_forwarding__(const struct bfd *) OVS_REQUIRES(mutex);
 195 static bool bfd_in_poll(const struct bfd *) OVS_REQUIRES(mutex);
 196 static void bfd_poll(struct bfd *bfd) OVS_REQUIRES(mutex);
 197 static const char *bfd_diag_str(enum diag) OVS_REQUIRES(mutex);
 198 static const char *bfd_state_str(enum state) OVS_REQUIRES(mutex);
 199 static long long int bfd_min_tx(const struct bfd *) OVS_REQUIRES(mutex);
 200 static long long int bfd_tx_interval(const struct bfd *)
 201     OVS_REQUIRES(mutex);
 202 static long long int bfd_rx_interval(const struct bfd *)
 203     OVS_REQUIRES(mutex);
 204 static void bfd_set_next_tx(struct bfd *) OVS_REQUIRES(mutex);
 205 static void bfd_set_state(struct bfd *, enum state, enum diag)
 206     OVS_REQUIRES(mutex);
 207 static uint32_t generate_discriminator(void) OVS_REQUIRES(mutex);
 208 static void bfd_put_details(struct ds *, const struct bfd *)
 209     OVS_REQUIRES(mutex);
 210 static void bfd_unixctl_show(struct unixctl_conn *, int argc,
 211                              const char *argv[], void *aux OVS_UNUSED);
 212 static void bfd_unixctl_set_forwarding_override(struct unixctl_conn *,
 213                                                 int argc, const char *argv[],
 214                                                 void *aux OVS_UNUSED);
 215 static void log_msg(enum vlog_level, const struct msg *, const char *message,
 216                     const struct bfd *) OVS_REQUIRES(mutex);
 217
 218 static struct vlog_rate_limit rl = VLOG_RATE_LIMIT_INIT(20, 20);
 219
 220 /* Returns true if the interface on which 'bfd' is running may be used to
 221  * forward traffic according to the BFD session state. */
 222 bool
 223 bfd_forwarding(const struct bfd *bfd) OVS_EXCLUDED(mutex)
 224 {
 225     bool ret;
 226
 227     ovs_mutex_lock(&mutex);
 228     ret = bfd_forwarding__(bfd);
 229     ovs_mutex_unlock(&mutex);
 230     return ret;
 231 }
 232
 233 /* Returns a 'smap' of key value pairs representing the status of 'bfd'
 234  * intended for the OVS database. */
 235 void
 236 bfd_get_status(const struct bfd *bfd, struct smap *smap)
 237     OVS_EXCLUDED(mutex)
 238 {
 239     ovs_mutex_lock(&mutex);
 240     smap_add(smap, "forwarding", bfd_forwarding__(bfd)? "true" : "false");
 241     smap_add(smap, "state", bfd_state_str(bfd->state));
 242     smap_add(smap, "diagnostic", bfd_diag_str(bfd->diag));
 243
 244     if (bfd->state != STATE_DOWN) {
 245         smap_add(smap, "remote_state", bfd_state_str(bfd->rmt_state));
 246         smap_add(smap, "remote_diagnostic", bfd_diag_str(bfd->rmt_diag));
 247     }
 248     ovs_mutex_unlock(&mutex);
 249 }
 250
 251 /* Initializes, destroys, or reconfigures the BFD session 'bfd' (named 'name'),
 252  * according to the database configuration contained in 'cfg'.  Takes ownership
 253  * of 'bfd', which may be NULL.  Returns a BFD object which may be used as a
 254  * handle for the session, or NULL if BFD is not enabled according to 'cfg'.
 255  * Also returns NULL if cfg is NULL. */
 256 struct bfd *
 257 bfd_configure(struct bfd *bfd, const char *name, const struct smap *cfg)
 258     OVS_EXCLUDED(mutex)
 259 {
 260     static struct ovsthread_once once = OVSTHREAD_ONCE_INITIALIZER;
 261     static atomic_uint16_t udp_src = ATOMIC_VAR_INIT(0);
 262
 263     long long int min_tx, min_rx;
 264     bool need_poll = false;
 265     bool cpath_down;
 266     const char *hwaddr;
 267     uint8_t ea[ETH_ADDR_LEN];
 268
 269     if (ovsthread_once_start(&once)) {
 270         unixctl_command_register("bfd/show", "[interface]", 0, 1,
 271                                  bfd_unixctl_show, NULL);
 272         unixctl_command_register("bfd/set-forwarding",
 273                                  "[interface] normal|false|true", 1, 2,
 274                                  bfd_unixctl_set_forwarding_override, NULL);
 275         ovsthread_once_done(&once);
 276     }
 277
 278     if (!cfg || !smap_get_bool(cfg, "enable", false)) {
 279         bfd_unref(bfd);
 280         return NULL;
 281     }
 282
 283     ovs_mutex_lock(&mutex);
 284     if (!bfd) {
 285         bfd = xzalloc(sizeof *bfd);
 286         bfd->name = xstrdup(name);
 287         bfd->forwarding_override = -1;
 288         bfd->disc = generate_discriminator();
 289         hmap_insert(all_bfds, &bfd->node, bfd->disc);
 290
 291         bfd->diag = DIAG_NONE;
 292         bfd->min_tx = 1000;
 293         bfd->mult = 3;
 294         atomic_init(&bfd->ref_cnt, 1);
 295
 296         /* RFC 5881 section 4
 297          * The source port MUST be in the range 49152 through 65535.  The same
 298          * UDP source port number MUST be used for all BFD Control packets
 299          * associated with a particular session.  The source port number SHOULD
 300          * be unique among all BFD sessions on the system. */
 301         atomic_add(&udp_src, 1, &bfd->udp_src);
 302         bfd->udp_src = (bfd->udp_src % 16384) + 49152;
 303
 304         bfd_set_state(bfd, STATE_DOWN, DIAG_NONE);
 305
 306         memcpy(bfd->eth_dst, eth_addr_bfd, ETH_ADDR_LEN);
 307     }
 308
 309     atomic_store(&bfd->check_tnl_key,
 310                  smap_get_bool(cfg, "check_tnl_key", false));
 311     min_tx = smap_get_int(cfg, "min_tx", 100);
 312     min_tx = MAX(min_tx, 100);
 313     if (bfd->cfg_min_tx != min_tx) {
 314         bfd->cfg_min_tx = min_tx;
 315         if (bfd->state != STATE_UP
 316             || (!bfd_in_poll(bfd) && bfd->cfg_min_tx < bfd->min_tx)) {
 317             bfd->min_tx = bfd->cfg_min_tx;
 318         }
 319         need_poll = true;
 320     }
 321
 322     min_rx = smap_get_int(cfg, "min_rx", 1000);
 323     min_rx = MAX(min_rx, 100);
 324     if (bfd->cfg_min_rx != min_rx) {
 325         bfd->cfg_min_rx = min_rx;
 326         if (bfd->state != STATE_UP
 327             || (!bfd_in_poll(bfd) && bfd->cfg_min_rx > bfd->min_rx)) {
 328             bfd->min_rx = bfd->cfg_min_rx;
 329         }
 330         need_poll = true;
 331     }
 332
 333     cpath_down = smap_get_bool(cfg, "cpath_down", false);
 334     if (bfd->cpath_down != cpath_down) {
 335         bfd->cpath_down = cpath_down;
 336         if (bfd->diag == DIAG_NONE || bfd->diag == DIAG_CPATH_DOWN) {
 337             bfd_set_state(bfd, bfd->state, DIAG_NONE);
 338         }
 339         need_poll = true;
 340     }
 341
 342     hwaddr = smap_get(cfg, "bfd_dst_mac");
 343     if (hwaddr && eth_addr_from_string(hwaddr, ea) && !eth_addr_is_zero(ea)) {
 344         memcpy(bfd->eth_dst, ea, ETH_ADDR_LEN);
 345         bfd->eth_dst_set = true;
 346     } else if (bfd->eth_dst_set) {
 347         memcpy(bfd->eth_dst, eth_addr_bfd, ETH_ADDR_LEN);
 348         bfd->eth_dst_set = false;
 349     }
 350
 351     if (need_poll) {
 352         bfd_poll(bfd);
 353     }
 354     ovs_mutex_unlock(&mutex);
 355     return bfd;
 356 }
 357
 358 struct bfd *
 359 bfd_ref(const struct bfd *bfd_)
 360 {
 361     struct bfd *bfd = CONST_CAST(struct bfd *, bfd_);
 362     if (bfd) {
 363         int orig;
 364         atomic_add(&bfd->ref_cnt, 1, &orig);
 365         ovs_assert(orig > 0);
 366     }
 367     return bfd;
 368 }
 369
 370 void
 371 bfd_unref(struct bfd *bfd) OVS_EXCLUDED(mutex)
 372 {
 373     if (bfd) {
 374         int orig;
 375
 376         atomic_sub(&bfd->ref_cnt, 1, &orig);
 377         ovs_assert(orig > 0);
 378         if (orig == 1) {
 379             ovs_mutex_lock(&mutex);
 380             hmap_remove(all_bfds, &bfd->node);
 381             free(bfd->name);
 382             free(bfd);
 383             ovs_mutex_unlock(&mutex);
 384         }
 385     }
 386 }
 387
 388 void
 389 bfd_wait(const struct bfd *bfd) OVS_EXCLUDED(mutex)
 390 {
 391     ovs_mutex_lock(&mutex);
 392     if (bfd->flags & FLAG_FINAL) {
 393         poll_immediate_wake();
 394     }
 395
 396     poll_timer_wait_until(bfd->next_tx);
 397     if (bfd->state > STATE_DOWN) {
 398         poll_timer_wait_until(bfd->detect_time);
 399     }
 400     ovs_mutex_unlock(&mutex);
 401 }
 402
 403 void
 404 bfd_run(struct bfd *bfd) OVS_EXCLUDED(mutex)
 405 {
 406     ovs_mutex_lock(&mutex);
 407     if (bfd->state > STATE_DOWN && time_msec() >= bfd->detect_time) {
 408         bfd_set_state(bfd, STATE_DOWN, DIAG_EXPIRED);
 409     }
 410
 411     if (bfd->min_tx != bfd->cfg_min_tx || bfd->min_rx != bfd->cfg_min_rx) {
 412         bfd_poll(bfd);
 413     }
 414     ovs_mutex_unlock(&mutex);
 415 }
 416
 417 bool
 418 bfd_should_send_packet(const struct bfd *bfd) OVS_EXCLUDED(mutex)
 419 {
 420     bool ret;
 421     ovs_mutex_lock(&mutex);
 422     ret = bfd->flags & FLAG_FINAL || time_msec() >= bfd->next_tx;
 423     ovs_mutex_unlock(&mutex);
 424     return ret;
 425 }
 426
 427 void
 428 bfd_put_packet(struct bfd *bfd, struct ofpbuf *p,
 429                uint8_t eth_src[ETH_ADDR_LEN]) OVS_EXCLUDED(mutex)
 430 {
 431     long long int min_tx, min_rx;
 432     struct udp_header *udp;
 433     struct eth_header *eth;
 434     struct ip_header *ip;
 435     struct msg *msg;
 436
 437     ovs_mutex_lock(&mutex);
 438     if (bfd->next_tx) {
 439         long long int delay = time_msec() - bfd->next_tx;
 440         long long int interval = bfd_tx_interval(bfd);
 441         if (delay > interval * 3 / 2) {
 442             VLOG_INFO("%s: long delay of %lldms (expected %lldms) sending BFD"
 443                       " control message", bfd->name, delay, interval);
 444         }
 445     }
 446
 447     /* RFC 5880 Section 6.5
 448      * A BFD Control packet MUST NOT have both the Poll (P) and Final (F) bits
 449      * set. */
 450     ovs_assert(!(bfd->flags & FLAG_POLL) || !(bfd->flags & FLAG_FINAL));
 451
 452     ofpbuf_reserve(p, 2); /* Properly align after the ethernet header. */
 453     eth = ofpbuf_put_uninit(p, sizeof *eth);
 454     memcpy(eth->eth_src, eth_src, ETH_ADDR_LEN);
 455     memcpy(eth->eth_dst, bfd->eth_dst, ETH_ADDR_LEN);
 456     eth->eth_type = htons(ETH_TYPE_IP);
 457
 458     ip = ofpbuf_put_zeros(p, sizeof *ip);
 459     ip->ip_ihl_ver = IP_IHL_VER(5, 4);
 460     ip->ip_tot_len = htons(sizeof *ip + sizeof *udp + sizeof *msg);
 461     ip->ip_ttl = MAXTTL;
 462     ip->ip_tos = IPTOS_LOWDELAY | IPTOS_THROUGHPUT;
 463     ip->ip_proto = IPPROTO_UDP;
 464     ip->ip_src = htonl(0xA9FE0100); /* 169.254.1.0 Link Local. */
 465     ip->ip_dst = htonl(0xA9FE0101); /* 169.254.1.1 Link Local. */
 466     ip->ip_csum = csum(ip, sizeof *ip);
 467
 468     udp = ofpbuf_put_zeros(p, sizeof *udp);
 469     udp->udp_src = htons(bfd->udp_src);
 470     udp->udp_dst = htons(BFD_DEST_PORT);
 471     udp->udp_len = htons(sizeof *udp + sizeof *msg);
 472
 473     msg = ofpbuf_put_uninit(p, sizeof *msg);
 474     msg->vers_diag = (BFD_VERSION << 5) | bfd->diag;
 475     msg->flags = (bfd->state & STATE_MASK) | bfd->flags;
 476
 477     msg->mult = bfd->mult;
 478     msg->length = BFD_PACKET_LEN;
 479     msg->my_disc = htonl(bfd->disc);
 480     msg->your_disc = htonl(bfd->rmt_disc);
 481     msg->min_rx_echo = htonl(0);
 482
 483     if (bfd_in_poll(bfd)) {
 484         min_tx = bfd->poll_min_tx;
 485         min_rx = bfd->poll_min_rx;
 486     } else {
 487         min_tx = bfd_min_tx(bfd);
 488         min_rx = bfd->min_rx;
 489     }
 490
 491     msg->min_tx = htonl(min_tx * 1000);
 492     msg->min_rx = htonl(min_rx * 1000);
 493
 494     bfd->flags &= ~FLAG_FINAL;
 495
 496     log_msg(VLL_DBG, msg, "Sending BFD Message", bfd);
 497
 498     bfd->last_tx = time_msec();
 499     bfd_set_next_tx(bfd);
 500     ovs_mutex_unlock(&mutex);
 501 }
 502
 503 bool
 504 bfd_should_process_flow(const struct bfd *bfd, const struct flow *flow,
 505                         struct flow_wildcards *wc)
 506 {
 507     bool check_tnl_key;
 508     memset(&wc->masks.dl_dst, 0xff, sizeof wc->masks.dl_dst);
 509     if (bfd->eth_dst_set && memcmp(bfd->eth_dst, flow->dl_dst, ETH_ADDR_LEN)) {
 510         return false;
 511     }
 512
 513     memset(&wc->masks.nw_proto, 0xff, sizeof wc->masks.nw_proto);
 514     memset(&wc->masks.tp_dst, 0xff, sizeof wc->masks.tp_dst);
 515
 516     atomic_read(&bfd->check_tnl_key, &check_tnl_key);
 517     if (check_tnl_key) {
 518         memset(&wc->masks.tunnel.tun_id, 0xff, sizeof wc->masks.tunnel.tun_id);
 519     }
 520     return (flow->dl_type == htons(ETH_TYPE_IP)
 521             && flow->nw_proto == IPPROTO_UDP
 522             && flow->tp_dst == htons(BFD_DEST_PORT)
 523             && (!check_tnl_key || flow->tunnel.tun_id == htonll(0)));
 524 }
 525
 526 void
 527 bfd_process_packet(struct bfd *bfd, const struct flow *flow,
 528                    const struct ofpbuf *p) OVS_EXCLUDED(mutex)
 529 {
 530     uint32_t rmt_min_rx, pkt_your_disc;
 531     enum state rmt_state;
 532     enum flags flags;
 533     uint8_t version;
 534     struct msg *msg;
 535
 536     /* This function is designed to follow section RFC 5880 6.8.6 closely. */
 537
 538     ovs_mutex_lock(&mutex);
 539     if (flow->nw_ttl != 255) {
 540         /* XXX Should drop in the kernel to prevent DOS. */
 541         goto out;
 542     }
 543
 544     msg = ofpbuf_at(p, (uint8_t *)p->l7 - (uint8_t *)p->data, BFD_PACKET_LEN);
 545     if (!msg) {
 546         VLOG_INFO_RL(&rl, "%s: Received unparseable BFD control message.",
 547                      bfd->name);
 548         goto out;
 549     }
 550
 551     /* RFC 5880 Section 6.8.6
 552      * If the Length field is greater than the payload of the encapsulating
 553      * protocol, the packet MUST be discarded.
 554      *
 555      * Note that we make this check implicity.  Above we use ofpbuf_at() to
 556      * ensure that there are at least BFD_PACKET_LEN bytes in the payload of
 557      * the encapsulating protocol.  Below we require msg->length to be exactly
 558      * BFD_PACKET_LEN bytes. */
 559
 560     flags = msg->flags & FLAGS_MASK;
 561     rmt_state = msg->flags & STATE_MASK;
 562     version = msg->vers_diag >> VERS_SHIFT;
 563
 564     log_msg(VLL_DBG, msg, "Received BFD control message", bfd);
 565
 566     if (version != BFD_VERSION) {
 567         log_msg(VLL_WARN, msg, "Incorrect version", bfd);
 568         goto out;
 569     }
 570
 571     /* Technically this should happen after the length check. We don't support
 572      * authentication however, so it's simpler to do the check first. */
 573     if (flags & FLAG_AUTH) {
 574         log_msg(VLL_WARN, msg, "Authenticated control message with"
 575                    " authentication disabled", bfd);
 576         goto out;
 577     }
 578
 579     if (msg->length != BFD_PACKET_LEN) {
 580         log_msg(VLL_WARN, msg, "Unexpected length", bfd);
 581         if (msg->length < BFD_PACKET_LEN) {
 582             goto out;
 583         }
 584     }
 585
 586     if (!msg->mult) {
 587         log_msg(VLL_WARN, msg, "Zero multiplier", bfd);
 588         goto out;
 589     }
 590
 591     if (flags & FLAG_MULTIPOINT) {
 592         log_msg(VLL_WARN, msg, "Unsupported multipoint flag", bfd);
 593         goto out;
 594     }
 595
 596     if (!msg->my_disc) {
 597         log_msg(VLL_WARN, msg, "NULL my_disc", bfd);
 598         goto out;
 599     }
 600
 601     pkt_your_disc = ntohl(msg->your_disc);
 602     if (pkt_your_disc) {
 603         /* Technically, we should use the your discriminator field to figure
 604          * out which 'struct bfd' this packet is destined towards.  That way a
 605          * bfd session could migrate from one interface to another
 606          * transparently.  This doesn't fit in with the OVS structure very
 607          * well, so in this respect, we are not compliant. */
 608        if (pkt_your_disc != bfd->disc) {
 609            log_msg(VLL_WARN, msg, "Incorrect your_disc", bfd);
 610            goto out;
 611        }
 612     } else if (rmt_state > STATE_DOWN) {
 613         log_msg(VLL_WARN, msg, "Null your_disc", bfd);
 614         goto out;
 615     }
 616
 617     bfd->rmt_disc = ntohl(msg->my_disc);
 618     bfd->rmt_state = rmt_state;
 619     bfd->rmt_flags = flags;
 620     bfd->rmt_diag = msg->vers_diag & DIAG_MASK;
 621
 622     if (flags & FLAG_FINAL && bfd_in_poll(bfd)) {
 623         bfd->min_tx = bfd->poll_min_tx;
 624         bfd->min_rx = bfd->poll_min_rx;
 625         bfd->flags &= ~FLAG_POLL;
 626         log_msg(VLL_INFO, msg, "Poll sequence terminated", bfd);
 627     }
 628
 629     if (flags & FLAG_POLL) {
 630         /* RFC 5880 Section 6.5
 631          * When the other system receives a Poll, it immediately transmits a
 632          * BFD Control packet with the Final (F) bit set, independent of any
 633          * periodic BFD Control packets it may be sending
 634          * (see section 6.8.7). */
 635         bfd->flags &= ~FLAG_POLL;
 636         bfd->flags |= FLAG_FINAL;
 637     }
 638
 639     rmt_min_rx = MAX(ntohl(msg->min_rx) / 1000, 1);
 640     if (bfd->rmt_min_rx != rmt_min_rx) {
 641         bfd->rmt_min_rx = rmt_min_rx;
 642         bfd_set_next_tx(bfd);
 643         log_msg(VLL_INFO, msg, "New remote min_rx", bfd);
 644     }
 645
 646     bfd->rmt_min_tx = MAX(ntohl(msg->min_tx) / 1000, 1);
 647     bfd->detect_time = bfd_rx_interval(bfd) * bfd->mult + time_msec();
 648
 649     if (bfd->state == STATE_ADMIN_DOWN) {
 650         VLOG_DBG_RL(&rl, "Administratively down, dropping control message.");
 651         goto out;
 652     }
 653
 654     if (rmt_state == STATE_ADMIN_DOWN) {
 655         if (bfd->state != STATE_DOWN) {
 656             bfd_set_state(bfd, STATE_DOWN, DIAG_RMT_DOWN);
 657         }
 658     } else {
 659         switch (bfd->state) {
 660         case STATE_DOWN:
 661             if (rmt_state == STATE_DOWN) {
 662                 bfd_set_state(bfd, STATE_INIT, bfd->diag);
 663             } else if (rmt_state == STATE_INIT) {
 664                 bfd_set_state(bfd, STATE_UP, bfd->diag);
 665             }
 666             break;
 667         case STATE_INIT:
 668             if (rmt_state > STATE_DOWN) {
 669                 bfd_set_state(bfd, STATE_UP, bfd->diag);
 670             }
 671             break;
 672         case STATE_UP:
 673             if (rmt_state <= STATE_DOWN) {
 674                 bfd_set_state(bfd, STATE_DOWN, DIAG_RMT_DOWN);
 675                 log_msg(VLL_INFO, msg, "Remote signaled STATE_DOWN", bfd);
 676             }
 677             break;
 678         case STATE_ADMIN_DOWN:
 679         default:
 680             NOT_REACHED();
 681         }
 682     }
 683     /* XXX: RFC 5880 Section 6.8.6 Demand mode related calculations here. */
 684
 685 out:
 686     ovs_mutex_unlock(&mutex);
 687 }
 688 \f
 689 static bool
 690 bfd_forwarding__(const struct bfd *bfd) OVS_REQUIRES(mutex)
 691 {
 692     if (bfd->forwarding_override != -1) {
 693         return bfd->forwarding_override == 1;
 694     }
 695
 696     return bfd->state == STATE_UP
 697         && bfd->rmt_diag != DIAG_PATH_DOWN
 698         && bfd->rmt_diag != DIAG_CPATH_DOWN
 699         && bfd->rmt_diag != DIAG_RCPATH_DOWN;
 700 }
 701
 702 /* Helpers. */
 703 static bool
 704 bfd_in_poll(const struct bfd *bfd) OVS_REQUIRES(mutex)
 705 {
 706     return (bfd->flags & FLAG_POLL) != 0;
 707 }
 708
 709 static void
 710 bfd_poll(struct bfd *bfd) OVS_REQUIRES(mutex)
 711 {
 712     if (bfd->state > STATE_DOWN && !bfd_in_poll(bfd)
 713         && !(bfd->flags & FLAG_FINAL)) {
 714         bfd->poll_min_tx = bfd->cfg_min_tx;
 715         bfd->poll_min_rx = bfd->cfg_min_rx;
 716         bfd->flags |= FLAG_POLL;
 717         bfd->next_tx = 0;
 718         VLOG_INFO_RL(&rl, "%s: Initiating poll sequence", bfd->name);
 719     }
 720 }
 721
 722 static long long int
 723 bfd_min_tx(const struct bfd *bfd) OVS_REQUIRES(mutex)
 724 {
 725     /* RFC 5880 Section 6.8.3
 726      * When bfd.SessionState is not Up, the system MUST set
 727      * bfd.DesiredMinTxInterval to a value of not less than one second
 728      * (1,000,000 microseconds).  This is intended to ensure that the
 729      * bandwidth consumed by BFD sessions that are not Up is negligible,
 730      * particularly in the case where a neighbor may not be running BFD. */
 731     return (bfd->state == STATE_UP ? bfd->min_tx : MAX(bfd->min_tx, 1000));
 732 }
 733
 734 static long long int
 735 bfd_tx_interval(const struct bfd *bfd) OVS_REQUIRES(mutex)
 736 {
 737     long long int interval = bfd_min_tx(bfd);
 738     return MAX(interval, bfd->rmt_min_rx);
 739 }
 740
 741 static long long int
 742 bfd_rx_interval(const struct bfd *bfd) OVS_REQUIRES(mutex)
 743 {
 744     return MAX(bfd->min_rx, bfd->rmt_min_tx);
 745 }
 746
 747 static void
 748 bfd_set_next_tx(struct bfd *bfd) OVS_REQUIRES(mutex)
 749 {
 750     long long int interval = bfd_tx_interval(bfd);
 751     interval -= interval * random_range(26) / 100;
 752     bfd->next_tx = bfd->last_tx + interval;
 753 }
 754
 755 static const char *
 756 bfd_flag_str(enum flags flags)
 757 {
 758     struct ds ds = DS_EMPTY_INITIALIZER;
 759     static char flag_str[128];
 760
 761     if (!flags) {
 762         return "none";
 763     }
 764
 765     if (flags & FLAG_MULTIPOINT) {
 766         ds_put_cstr(&ds, "multipoint ");
 767     }
 768
 769     if (flags & FLAG_DEMAND) {
 770         ds_put_cstr(&ds, "demand ");
 771     }
 772
 773     if (flags & FLAG_AUTH) {
 774         ds_put_cstr(&ds, "auth ");
 775     }
 776
 777     if (flags & FLAG_CTL) {
 778         ds_put_cstr(&ds, "ctl ");
 779     }
 780
 781     if (flags & FLAG_FINAL) {
 782         ds_put_cstr(&ds, "final ");
 783     }
 784
 785     if (flags & FLAG_POLL) {
 786         ds_put_cstr(&ds, "poll ");
 787     }
 788
 789     /* Do not copy the trailing whitespace. */
 790     ds_chomp(&ds, ' ');
 791     ovs_strlcpy(flag_str, ds_cstr(&ds), sizeof flag_str);
 792     ds_destroy(&ds);
 793     return flag_str;
 794 }
 795
 796 static const char *
 797 bfd_state_str(enum state state)
 798 {
 799     switch (state) {
 800     case STATE_ADMIN_DOWN: return "admin_down";
 801     case STATE_DOWN: return "down";
 802     case STATE_INIT: return "init";
 803     case STATE_UP: return "up";
 804     default: return "invalid";
 805     }
 806 }
 807
 808 static const char *
 809 bfd_diag_str(enum diag diag) {
 810     switch (diag) {
 811     case DIAG_NONE: return "No Diagnostic";
 812     case DIAG_EXPIRED: return "Control Detection Time Expired";
 813     case DIAG_ECHO_FAILED: return "Echo Function Failed";
 814     case DIAG_RMT_DOWN: return "Neighbor Signaled Session Down";
 815     case DIAG_FWD_RESET: return "Forwarding Plane Reset";
 816     case DIAG_PATH_DOWN: return "Path Down";
 817     case DIAG_CPATH_DOWN: return "Concatenated Path Down";
 818     case DIAG_ADMIN_DOWN: return "Administratively Down";
 819     case DIAG_RCPATH_DOWN: return "Reverse Concatenated Path Down";
 820     default: return "Invalid Diagnostic";
 821     }
 822 };
 823
 824 static void
 825 log_msg(enum vlog_level level, const struct msg *p, const char *message,
 826         const struct bfd *bfd) OVS_REQUIRES(mutex)
 827 {
 828     struct ds ds = DS_EMPTY_INITIALIZER;
 829
 830     if (vlog_should_drop(THIS_MODULE, level, &rl)) {
 831         return;
 832     }
 833
 834     ds_put_format(&ds,
 835                   "%s: %s."
 836                   "\n\tvers:%"PRIu8" diag:\"%s\" state:%s mult:%"PRIu8
 837                   " length:%"PRIu8
 838                   "\n\tflags: %s"
 839                   "\n\tmy_disc:0x%"PRIx32" your_disc:0x%"PRIx32
 840                   "\n\tmin_tx:%"PRIu32"us (%"PRIu32"ms)"
 841                   "\n\tmin_rx:%"PRIu32"us (%"PRIu32"ms)"
 842                   "\n\tmin_rx_echo:%"PRIu32"us (%"PRIu32"ms)",
 843                   bfd->name, message, p->vers_diag >> VERS_SHIFT,
 844                   bfd_diag_str(p->vers_diag & DIAG_MASK),
 845                   bfd_state_str(p->flags & STATE_MASK),
 846                   p->mult, p->length, bfd_flag_str(p->flags & FLAGS_MASK),
 847                   ntohl(p->my_disc), ntohl(p->your_disc),
 848                   ntohl(p->min_tx), ntohl(p->min_tx) / 1000,
 849                   ntohl(p->min_rx), ntohl(p->min_rx) / 1000,
 850                   ntohl(p->min_rx_echo), ntohl(p->min_rx_echo) / 1000);
 851     bfd_put_details(&ds, bfd);
 852     VLOG(level, "%s", ds_cstr(&ds));
 853     ds_destroy(&ds);
 854 }
 855
 856 static void
 857 bfd_set_state(struct bfd *bfd, enum state state, enum diag diag)
 858     OVS_REQUIRES(mutex)
 859 {
 860     if (diag == DIAG_NONE && bfd->cpath_down) {
 861         diag = DIAG_CPATH_DOWN;
 862     }
 863
 864     if (bfd->state != state || bfd->diag != diag) {
 865         if (!VLOG_DROP_INFO(&rl)) {
 866             struct ds ds = DS_EMPTY_INITIALIZER;
 867
 868             ds_put_format(&ds, "%s: BFD state change: %s->%s"
 869                           " \"%s\"->\"%s\".\n",
 870                           bfd->name, bfd_state_str(bfd->state),
 871                           bfd_state_str(state), bfd_diag_str(bfd->diag),
 872                           bfd_diag_str(diag));
 873             bfd_put_details(&ds, bfd);
 874             VLOG_INFO("%s", ds_cstr(&ds));
 875             ds_destroy(&ds);
 876         }
 877
 878         bfd->state = state;
 879         bfd->diag = diag;
 880
 881         if (bfd->state <= STATE_DOWN) {
 882             bfd->rmt_state = STATE_DOWN;
 883             bfd->rmt_diag = DIAG_NONE;
 884             bfd->rmt_min_rx = 1;
 885             bfd->rmt_flags = 0;
 886             bfd->rmt_disc = 0;
 887             bfd->rmt_min_tx = 0;
 888         }
 889     }
 890 }
 891
 892 static uint32_t
 893 generate_discriminator(void)
 894 {
 895     uint32_t disc = 0;
 896
 897     /* RFC 5880 Section 6.8.1
 898      * It SHOULD be set to a random (but still unique) value to improve
 899      * security.  The value is otherwise outside the scope of this
 900      * specification. */
 901
 902     while (!disc) {
 903         struct bfd *bfd;
 904
 905         /* 'disc' is by definition random, so there's no reason to waste time
 906          * hashing it. */
 907         disc = random_uint32();
 908         HMAP_FOR_EACH_IN_BUCKET (bfd, node, disc, all_bfds) {
 909             if (bfd->disc == disc) {
 910                 disc = 0;
 911                 break;
 912             }
 913         }
 914     }
 915
 916     return disc;
 917 }
 918
 919 static struct bfd *
 920 bfd_find_by_name(const char *name) OVS_REQUIRES(mutex)
 921 {
 922     struct bfd *bfd;
 923
 924     HMAP_FOR_EACH (bfd, node, all_bfds) {
 925         if (!strcmp(bfd->name, name)) {
 926             return bfd;
 927         }
 928     }
 929     return NULL;
 930 }
 931
 932 static void
 933 bfd_put_details(struct ds *ds, const struct bfd *bfd) OVS_REQUIRES(mutex)
 934 {
 935     ds_put_format(ds, "\tForwarding: %s\n",
 936                   bfd_forwarding__(bfd) ? "true" : "false");
 937     ds_put_format(ds, "\tDetect Multiplier: %d\n", bfd->mult);
 938     ds_put_format(ds, "\tConcatenated Path Down: %s\n",
 939                   bfd->cpath_down ? "true" : "false");
 940     ds_put_format(ds, "\tTX Interval: Approx %lldms\n", bfd_tx_interval(bfd));
 941     ds_put_format(ds, "\tRX Interval: Approx %lldms\n", bfd_rx_interval(bfd));
 942     ds_put_format(ds, "\tDetect Time: now %+lldms\n",
 943                   time_msec() - bfd->detect_time);
 944     ds_put_format(ds, "\tNext TX Time: now %+lldms\n",
 945                   time_msec() - bfd->next_tx);
 946     ds_put_format(ds, "\tLast TX Time: now %+lldms\n",
 947                   time_msec() - bfd->last_tx);
 948
 949     ds_put_cstr(ds, "\n");
 950
 951     ds_put_format(ds, "\tLocal Flags: %s\n", bfd_flag_str(bfd->flags));
 952     ds_put_format(ds, "\tLocal Session State: %s\n",
 953                   bfd_state_str(bfd->state));
 954     ds_put_format(ds, "\tLocal Diagnostic: %s\n", bfd_diag_str(bfd->diag));
 955     ds_put_format(ds, "\tLocal Discriminator: 0x%"PRIx32"\n", bfd->disc);
 956     ds_put_format(ds, "\tLocal Minimum TX Interval: %lldms\n",
 957                   bfd_min_tx(bfd));
 958     ds_put_format(ds, "\tLocal Minimum RX Interval: %lldms\n", bfd->min_rx);
 959
 960     ds_put_cstr(ds, "\n");
 961
 962     ds_put_format(ds, "\tRemote Flags: %s\n", bfd_flag_str(bfd->rmt_flags));
 963     ds_put_format(ds, "\tRemote Session State: %s\n",
 964                   bfd_state_str(bfd->rmt_state));
 965     ds_put_format(ds, "\tRemote Diagnostic: %s\n",
 966                   bfd_diag_str(bfd->rmt_diag));
 967     ds_put_format(ds, "\tRemote Discriminator: 0x%"PRIx32"\n", bfd->rmt_disc);
 968     ds_put_format(ds, "\tRemote Minimum TX Interval: %lldms\n",
 969                   bfd->rmt_min_tx);
 970     ds_put_format(ds, "\tRemote Minimum RX Interval: %lldms\n",
 971                   bfd->rmt_min_rx);
 972 }
 973
 974 static void
 975 bfd_unixctl_show(struct unixctl_conn *conn, int argc, const char *argv[],
 976                  void *aux OVS_UNUSED) OVS_EXCLUDED(mutex)
 977 {
 978     struct ds ds = DS_EMPTY_INITIALIZER;
 979     struct bfd *bfd;
 980
 981     ovs_mutex_lock(&mutex);
 982     if (argc > 1) {
 983         bfd = bfd_find_by_name(argv[1]);
 984         if (!bfd) {
 985             unixctl_command_reply_error(conn, "no such bfd object");
 986             goto out;
 987         }
 988         bfd_put_details(&ds, bfd);
 989     } else {
 990         HMAP_FOR_EACH (bfd, node, all_bfds) {
 991             ds_put_format(&ds, "---- %s ----\n", bfd->name);
 992             bfd_put_details(&ds, bfd);
 993         }
 994     }
 995     unixctl_command_reply(conn, ds_cstr(&ds));
 996     ds_destroy(&ds);
 997
 998 out:
 999     ovs_mutex_unlock(&mutex);
1000 }
1001
1002
1003 static void
1004 bfd_unixctl_set_forwarding_override(struct unixctl_conn *conn, int argc,
1005                                     const char *argv[], void *aux OVS_UNUSED)
1006     OVS_EXCLUDED(mutex)
1007 {
1008     const char *forward_str = argv[argc - 1];
1009     int forwarding_override;
1010     struct bfd *bfd;
1011
1012     ovs_mutex_lock(&mutex);
1013     if (!strcasecmp("true", forward_str)) {
1014         forwarding_override = 1;
1015     } else if (!strcasecmp("false", forward_str)) {
1016         forwarding_override = 0;
1017     } else if (!strcasecmp("normal", forward_str)) {
1018         forwarding_override = -1;
1019     } else {
1020         unixctl_command_reply_error(conn, "unknown fault string");
1021         goto out;
1022     }
1023
1024     if (argc > 2) {
1025         bfd = bfd_find_by_name(argv[1]);
1026         if (!bfd) {
1027             unixctl_command_reply_error(conn, "no such BFD object");
1028             goto out;
1029         }
1030         bfd->forwarding_override = forwarding_override;
1031     } else {
1032         HMAP_FOR_EACH (bfd, node, all_bfds) {
1033             bfd->forwarding_override = forwarding_override;
1034         }
1035     }
1036
1037     unixctl_command_reply(conn, "OK");
1038
1039 out:
1040     ovs_mutex_unlock(&mutex);
1041 }