lib/stp.c

   1 /*
   2  * Copyright (c) 2008, 2009, 2010, 2011, 2012, 2013, 2014 Nicira, Inc.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at:
   7  *
   8  *     http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 /* Based on sample implementation in 802.1D-1998.  Above copyright and license
  18  * applies to all modifications. */
  19
  20 #include <config.h>
  21
  22 #include "stp.h"
  23 #include <sys/types.h>
  24 #include <netinet/in.h>
  25 #include <arpa/inet.h>
  26 #include <inttypes.h>
  27 #include <stdlib.h>
  28 #include "byte-order.h"
  29 #include "connectivity.h"
  30 #include "ofpbuf.h"
  31 #include "ovs-atomic.h"
  32 #include "dp-packet.h"
  33 #include "packets.h"
  34 #include "seq.h"
  35 #include "unixctl.h"
  36 #include "util.h"
  37 #include "openvswitch/vlog.h"
  38
  39 VLOG_DEFINE_THIS_MODULE(stp);
  40
  41 static struct vlog_rate_limit stp_rl = VLOG_RATE_LIMIT_INIT(60, 60);
  42
  43 #define STP_PROTOCOL_ID 0x0000
  44 #define STP_PROTOCOL_VERSION 0x00
  45 #define STP_TYPE_CONFIG 0x00
  46 #define STP_TYPE_TCN 0x80
  47
  48 OVS_PACKED(
  49 struct stp_bpdu_header {
  50     ovs_be16 protocol_id;       /* STP_PROTOCOL_ID. */
  51     uint8_t protocol_version;   /* STP_PROTOCOL_VERSION. */
  52     uint8_t bpdu_type;          /* One of STP_TYPE_*. */
  53 });
  54 BUILD_ASSERT_DECL(sizeof(struct stp_bpdu_header) == 4);
  55
  56 enum stp_config_bpdu_flags {
  57     STP_CONFIG_TOPOLOGY_CHANGE_ACK = 0x80,
  58     STP_CONFIG_TOPOLOGY_CHANGE = 0x01
  59 };
  60
  61 OVS_PACKED(
  62 struct stp_config_bpdu {
  63     struct stp_bpdu_header header; /* Type STP_TYPE_CONFIG. */
  64     uint8_t flags;                 /* STP_CONFIG_* flags. */
  65     ovs_be64 root_id;              /* 8.5.1.1: Bridge believed to be root. */
  66     ovs_be32 root_path_cost;       /* 8.5.1.2: Cost of path to root. */
  67     ovs_be64 bridge_id;            /* 8.5.1.3: ID of transmitting bridge. */
  68     ovs_be16 port_id;              /* 8.5.1.4: Port transmitting the BPDU. */
  69     ovs_be16 message_age;          /* 8.5.1.5: Age of BPDU at tx time. */
  70     ovs_be16 max_age;              /* 8.5.1.6: Timeout for received data. */
  71     ovs_be16 hello_time;           /* 8.5.1.7: Time between BPDU generation. */
  72     ovs_be16 forward_delay;        /* 8.5.1.8: State progression delay. */
  73 });
  74 BUILD_ASSERT_DECL(sizeof(struct stp_config_bpdu) == 35);
  75
  76 OVS_PACKED(
  77 struct stp_tcn_bpdu {
  78     struct stp_bpdu_header header; /* Type STP_TYPE_TCN. */
  79 });
  80 BUILD_ASSERT_DECL(sizeof(struct stp_tcn_bpdu) == 4);
  81
  82 struct stp_timer {
  83     bool active;                 /* Timer in use? */
  84     int value;                   /* Current value of timer, counting up. */
  85 };
  86
  87 struct stp_port {
  88     struct stp *stp;
  89     char *port_name;                /* Human-readable name for log messages. */
  90     void *aux;                      /* Auxiliary data the user may retrieve. */
  91     int port_id;                    /* 8.5.5.1: Unique port identifier. */
  92     enum stp_state state;           /* 8.5.5.2: Current state. */
  93     int path_cost;                  /* 8.5.5.3: Cost of tx/rx on this port. */
  94     stp_identifier designated_root; /* 8.5.5.4. */
  95     int designated_cost;            /* 8.5.5.5: Path cost to root on port. */
  96     stp_identifier designated_bridge; /* 8.5.5.6. */
  97     int designated_port;            /* 8.5.5.7: Port to send config msgs on. */
  98     bool topology_change_ack;       /* 8.5.5.8: Flag for next config BPDU. */
  99     bool config_pending;            /* 8.5.5.9: Send BPDU when hold expires? */
 100     bool change_detection_enabled;  /* 8.5.5.10: Detect topology changes? */
 101
 102     struct stp_timer message_age_timer; /* 8.5.6.1: Age of received info. */
 103     struct stp_timer forward_delay_timer; /* 8.5.6.2: State change timer. */
 104     struct stp_timer hold_timer;        /* 8.5.6.3: BPDU rate limit timer. */
 105
 106     int tx_count;                   /* Number of BPDUs transmitted. */
 107     int rx_count;                   /* Number of valid BPDUs received. */
 108     int error_count;                /* Number of bad BPDUs received. */
 109
 110     bool state_changed;
 111 };
 112
 113 struct stp {
 114     struct ovs_list node;           /* Node in all_stps list. */
 115
 116     /* Static bridge data. */
 117     char *name;                     /* Human-readable name for log messages. */
 118     stp_identifier bridge_id;       /* 8.5.3.7: This bridge. */
 119     int max_age;                    /* 8.5.3.4: Time to drop received data. */
 120     int hello_time;                 /* 8.5.3.5: Time between sending BPDUs. */
 121     int forward_delay;              /* 8.5.3.6: Delay between state changes. */
 122     int bridge_max_age;             /* 8.5.3.8: max_age when we're root. */
 123     int bridge_hello_time;          /* 8.5.3.9: hello_time as root. */
 124     int bridge_forward_delay;       /* 8.5.3.10: forward_delay as root. */
 125     int rq_max_age;                 /* User-requested max age, in ms. */
 126     int rq_hello_time;              /* User-requested hello time, in ms. */
 127     int rq_forward_delay;           /* User-requested forward delay, in ms. */
 128     int elapsed_remainder;          /* Left-over msecs from last stp_tick(). */
 129
 130     /* Dynamic bridge data. */
 131     stp_identifier designated_root; /* 8.5.3.1: Bridge believed to be root. */
 132     unsigned int root_path_cost;    /* 8.5.3.2: Cost of path to root. */
 133     struct stp_port *root_port;     /* 8.5.3.3: Lowest cost port to root. */
 134     bool topology_change_detected;  /* 8.5.3.11: Detected a topology change? */
 135     bool topology_change;           /* 8.5.3.12: Received topology change? */
 136
 137     /* Bridge timers. */
 138     struct stp_timer hello_timer;   /* 8.5.4.1: Hello timer. */
 139     struct stp_timer tcn_timer;     /* 8.5.4.2: Topology change timer. */
 140     struct stp_timer topology_change_timer; /* 8.5.4.3. */
 141
 142     /* Ports. */
 143     struct stp_port ports[STP_MAX_PORTS];
 144
 145     /* Interface to client. */
 146     bool fdb_needs_flush;          /* MAC learning tables needs flushing. */
 147     struct stp_port *first_changed_port;
 148     void (*send_bpdu)(struct dp_packet *bpdu, int port_no, void *aux);
 149     void *aux;
 150
 151     struct ovs_refcount ref_cnt;
 152 };
 153
 154 static struct ovs_mutex mutex;
 155 static struct ovs_list all_stps__ = OVS_LIST_INITIALIZER(&all_stps__);
 156 static struct ovs_list *const all_stps OVS_GUARDED_BY(mutex) = &all_stps__;
 157
 158 #define FOR_EACH_ENABLED_PORT(PORT, STP)                        \
 159     for ((PORT) = stp_next_enabled_port((STP), (STP)->ports);   \
 160          (PORT);                                                \
 161          (PORT) = stp_next_enabled_port((STP), (PORT) + 1))
 162 static struct stp_port *
 163 stp_next_enabled_port(const struct stp *stp, const struct stp_port *port)
 164     OVS_REQUIRES(mutex)
 165 {
 166     for (; port < &stp->ports[ARRAY_SIZE(stp->ports)]; port++) {
 167         if (port->state != STP_DISABLED) {
 168             return CONST_CAST(struct stp_port *, port);
 169         }
 170     }
 171     return NULL;
 172 }
 173
 174 #define MESSAGE_AGE_INCREMENT 1
 175
 176 static void stp_transmit_config(struct stp_port *) OVS_REQUIRES(mutex);
 177 static bool stp_supersedes_port_info(const struct stp_port *,
 178                                      const struct stp_config_bpdu *)
 179     OVS_REQUIRES(mutex);
 180 static void stp_record_config_information(struct stp_port *,
 181                                           const struct stp_config_bpdu *)
 182     OVS_REQUIRES(mutex);
 183 static void stp_record_config_timeout_values(struct stp *,
 184                                              const struct stp_config_bpdu  *)
 185     OVS_REQUIRES(mutex);
 186 static bool stp_is_designated_port(const struct stp_port *)
 187     OVS_REQUIRES(mutex);
 188 static void stp_config_bpdu_generation(struct stp *) OVS_REQUIRES(mutex);
 189 static void stp_transmit_tcn(struct stp *) OVS_REQUIRES(mutex);
 190 static void stp_configuration_update(struct stp *) OVS_REQUIRES(mutex);
 191 static bool stp_supersedes_root(const struct stp_port *root,
 192                                 const struct stp_port *) OVS_REQUIRES(mutex);
 193 static void stp_root_selection(struct stp *) OVS_REQUIRES(mutex);
 194 static void stp_designated_port_selection(struct stp *) OVS_REQUIRES(mutex);
 195 static void stp_become_designated_port(struct stp_port *)
 196     OVS_REQUIRES(mutex);
 197 static void stp_port_state_selection(struct stp *) OVS_REQUIRES(mutex);
 198 static void stp_make_forwarding(struct stp_port *) OVS_REQUIRES(mutex);
 199 static void stp_make_blocking(struct stp_port *) OVS_REQUIRES(mutex);
 200 static void stp_set_port_state(struct stp_port *, enum stp_state)
 201     OVS_REQUIRES(mutex);
 202 static void stp_topology_change_detection(struct stp *) OVS_REQUIRES(mutex);
 203 static void stp_topology_change_acknowledged(struct stp *)
 204     OVS_REQUIRES(mutex);
 205 static void stp_acknowledge_topology_change(struct stp_port *)
 206     OVS_REQUIRES(mutex);
 207 static void stp_received_config_bpdu(struct stp *, struct stp_port *,
 208                                      const struct stp_config_bpdu *)
 209     OVS_REQUIRES(mutex);
 210 static void stp_received_tcn_bpdu(struct stp *, struct stp_port *)
 211     OVS_REQUIRES(mutex);
 212 static void stp_hello_timer_expiry(struct stp *) OVS_REQUIRES(mutex);
 213 static void stp_message_age_timer_expiry(struct stp_port *)
 214     OVS_REQUIRES(mutex);
 215 static bool stp_is_designated_for_some_port(const struct stp *)
 216     OVS_REQUIRES(mutex);
 217 static void stp_forward_delay_timer_expiry(struct stp_port *)
 218     OVS_REQUIRES(mutex);
 219 static void stp_tcn_timer_expiry(struct stp *) OVS_REQUIRES(mutex);
 220 static void stp_topology_change_timer_expiry(struct stp *)
 221     OVS_REQUIRES(mutex);
 222 static void stp_hold_timer_expiry(struct stp_port *) OVS_REQUIRES(mutex);
 223 static void stp_initialize_port(struct stp_port *, enum stp_state)
 224     OVS_REQUIRES(mutex);
 225 static void stp_become_root_bridge(struct stp *) OVS_REQUIRES(mutex);
 226 static void stp_update_bridge_timers(struct stp *) OVS_REQUIRES(mutex);
 227
 228 static int clamp(int x, int min, int max);
 229 static int ms_to_timer(int ms);
 230 static int timer_to_ms(int timer);
 231 static void stp_start_timer(struct stp_timer *, int value);
 232 static void stp_stop_timer(struct stp_timer *);
 233 static bool stp_timer_expired(struct stp_timer *, int elapsed, int timeout);
 234
 235 static void stp_send_bpdu(struct stp_port *, const void *, size_t)
 236     OVS_REQUIRES(mutex);
 237 static void stp_unixctl_tcn(struct unixctl_conn *, int argc,
 238                             const char *argv[], void *aux);
 239
 240 void
 241 stp_init(void)
 242 {
 243     unixctl_command_register("stp/tcn", "[bridge]", 0, 1, stp_unixctl_tcn,
 244                              NULL);
 245 }
 246
 247 /* Creates and returns a new STP instance that initially has no ports enabled.
 248  *
 249  * 'bridge_id' should be a 48-bit MAC address as returned by
 250  * eth_addr_to_uint64().  'bridge_id' may also have a priority value in its top
 251  * 16 bits; if those bits are set to 0, STP_DEFAULT_BRIDGE_PRIORITY is used.
 252  * (This priority may be changed with stp_set_bridge_priority().)
 253  *
 254  * When the bridge needs to send out a BPDU, it calls 'send_bpdu'.  This
 255  * callback may be called from stp_tick() or stp_received_bpdu().  The
 256  * arguments to 'send_bpdu' are an STP BPDU encapsulated in 'bpdu',
 257  * the spanning tree port number 'port_no' that should transmit the
 258  * packet, and auxiliary data to be passed to the callback in 'aux'.
 259  */
 260 struct stp *
 261 stp_create(const char *name, stp_identifier bridge_id,
 262            void (*send_bpdu)(struct dp_packet *bpdu, int port_no, void *aux),
 263            void *aux)
 264 {
 265     static struct ovsthread_once once = OVSTHREAD_ONCE_INITIALIZER;
 266     struct stp *stp;
 267     struct stp_port *p;
 268
 269     if (ovsthread_once_start(&once)) {
 270         /* We need a recursive mutex because stp_send_bpdu() could loop back
 271          * into the stp module through a patch port.  This happens
 272          * intentionally as part of the unit tests.  Ideally we'd ditch
 273          * the call back function, but for now this is what we have. */
 274         ovs_mutex_init_recursive(&mutex);
 275         ovsthread_once_done(&once);
 276     }
 277
 278     ovs_mutex_lock(&mutex);
 279     stp = xzalloc(sizeof *stp);
 280     stp->name = xstrdup(name);
 281     stp->bridge_id = bridge_id;
 282     if (!(stp->bridge_id >> 48)) {
 283         stp->bridge_id |= (uint64_t) STP_DEFAULT_BRIDGE_PRIORITY << 48;
 284     }
 285
 286     stp->rq_max_age = STP_DEFAULT_MAX_AGE;
 287     stp->rq_hello_time = STP_DEFAULT_HELLO_TIME;
 288     stp->rq_forward_delay = STP_DEFAULT_FWD_DELAY;
 289     stp_update_bridge_timers(stp);
 290     stp->max_age = stp->bridge_max_age;
 291     stp->hello_time = stp->bridge_hello_time;
 292     stp->forward_delay = stp->bridge_forward_delay;
 293
 294     stp->designated_root = stp->bridge_id;
 295     stp->root_path_cost = 0;
 296     stp->root_port = NULL;
 297     stp->topology_change_detected = false;
 298     stp->topology_change = false;
 299
 300     stp_stop_timer(&stp->tcn_timer);
 301     stp_stop_timer(&stp->topology_change_timer);
 302     stp_start_timer(&stp->hello_timer, 0);
 303
 304     stp->send_bpdu = send_bpdu;
 305     stp->aux = aux;
 306
 307     stp->first_changed_port = &stp->ports[ARRAY_SIZE(stp->ports)];
 308     for (p = stp->ports; p < &stp->ports[ARRAY_SIZE(stp->ports)]; p++) {
 309         p->stp = stp;
 310         p->port_id = (stp_port_no(p) + 1) | (STP_DEFAULT_PORT_PRIORITY << 8);
 311         p->path_cost = 19;      /* Recommended default for 100 Mb/s link. */
 312         stp_initialize_port(p, STP_DISABLED);
 313     }
 314     ovs_refcount_init(&stp->ref_cnt);
 315
 316     list_push_back(all_stps, &stp->node);
 317     ovs_mutex_unlock(&mutex);
 318     return stp;
 319 }
 320
 321 struct stp *
 322 stp_ref(const struct stp *stp_)
 323 {
 324     struct stp *stp = CONST_CAST(struct stp *, stp_);
 325     if (stp) {
 326         ovs_refcount_ref(&stp->ref_cnt);
 327     }
 328     return stp;
 329 }
 330
 331 /* Destroys 'stp'. */
 332 void
 333 stp_unref(struct stp *stp)
 334 {
 335     if (stp && ovs_refcount_unref_relaxed(&stp->ref_cnt) == 1) {
 336         size_t i;
 337
 338         ovs_mutex_lock(&mutex);
 339         list_remove(&stp->node);
 340         ovs_mutex_unlock(&mutex);
 341         free(stp->name);
 342
 343         for (i = 0; i < STP_MAX_PORTS; i++) {
 344             free(stp->ports[i].port_name);
 345         }
 346         free(stp);
 347     }
 348 }
 349
 350 /* Runs 'stp' given that 'ms' milliseconds have passed. */
 351 void
 352 stp_tick(struct stp *stp, int ms)
 353 {
 354     struct stp_port *p;
 355     int elapsed;
 356
 357     ovs_mutex_lock(&mutex);
 358     /* Convert 'ms' to STP timer ticks.  Preserve any leftover milliseconds
 359      * from previous stp_tick() calls so that we don't lose STP ticks when we
 360      * are called too frequently. */
 361     ms = clamp(ms, 0, INT_MAX - 1000) + stp->elapsed_remainder;
 362     elapsed = ms_to_timer(ms);
 363     stp->elapsed_remainder = ms - timer_to_ms(elapsed);
 364     if (!elapsed) {
 365         goto out;
 366     }
 367
 368     if (stp_timer_expired(&stp->hello_timer, elapsed, stp->hello_time)) {
 369         stp_hello_timer_expiry(stp);
 370     }
 371     if (stp_timer_expired(&stp->tcn_timer, elapsed, stp->bridge_hello_time)) {
 372         stp_tcn_timer_expiry(stp);
 373     }
 374     if (stp_timer_expired(&stp->topology_change_timer, elapsed,
 375                           stp->max_age + stp->forward_delay)) {
 376         stp_topology_change_timer_expiry(stp);
 377     }
 378     FOR_EACH_ENABLED_PORT (p, stp) {
 379         if (stp_timer_expired(&p->message_age_timer, elapsed, stp->max_age)) {
 380             stp_message_age_timer_expiry(p);
 381         }
 382     }
 383     FOR_EACH_ENABLED_PORT (p, stp) {
 384         if (stp_timer_expired(&p->forward_delay_timer, elapsed,
 385                               stp->forward_delay)) {
 386             stp_forward_delay_timer_expiry(p);
 387         }
 388         if (stp_timer_expired(&p->hold_timer, elapsed, ms_to_timer(1000))) {
 389             stp_hold_timer_expiry(p);
 390         }
 391     }
 392
 393 out:
 394     ovs_mutex_unlock(&mutex);
 395 }
 396
 397 static void
 398 set_bridge_id(struct stp *stp, stp_identifier new_bridge_id)
 399     OVS_REQUIRES(mutex)
 400 {
 401     if (new_bridge_id != stp->bridge_id) {
 402         bool root;
 403         struct stp_port *p;
 404
 405         root = stp_is_root_bridge(stp);
 406         FOR_EACH_ENABLED_PORT (p, stp) {
 407             if (stp_is_designated_port(p)) {
 408                 p->designated_bridge = new_bridge_id;
 409             }
 410         }
 411         stp->bridge_id = new_bridge_id;
 412         stp_configuration_update(stp);
 413         stp_port_state_selection(stp);
 414         if (stp_is_root_bridge(stp) && !root) {
 415             stp_become_root_bridge(stp);
 416         }
 417     }
 418 }
 419
 420 void
 421 stp_set_bridge_id(struct stp *stp, stp_identifier bridge_id)
 422 {
 423     const uint64_t mac_bits = (UINT64_C(1) << 48) - 1;
 424     const uint64_t pri_bits = ~mac_bits;
 425     ovs_mutex_lock(&mutex);
 426     set_bridge_id(stp, (stp->bridge_id & pri_bits) | (bridge_id & mac_bits));
 427     ovs_mutex_unlock(&mutex);
 428 }
 429
 430 void
 431 stp_set_bridge_priority(struct stp *stp, uint16_t new_priority)
 432 {
 433     const uint64_t mac_bits = (UINT64_C(1) << 48) - 1;
 434     ovs_mutex_lock(&mutex);
 435     set_bridge_id(stp, ((stp->bridge_id & mac_bits)
 436                         | ((uint64_t) new_priority << 48)));
 437     ovs_mutex_unlock(&mutex);
 438 }
 439
 440 /* Sets the desired hello time for 'stp' to 'ms', in milliseconds.  The actual
 441  * hello time is clamped to the range of 1 to 10 seconds and subject to the
 442  * relationship (bridge_max_age >= 2 * (bridge_hello_time + 1 s)).  The bridge
 443  * hello time is only used when 'stp' is the root bridge. */
 444 void
 445 stp_set_hello_time(struct stp *stp, int ms)
 446 {
 447     ovs_mutex_lock(&mutex);
 448     stp->rq_hello_time = ms;
 449     stp_update_bridge_timers(stp);
 450     ovs_mutex_unlock(&mutex);
 451 }
 452
 453 /* Sets the desired max age for 'stp' to 'ms', in milliseconds.  The actual max
 454  * age is clamped to the range of 6 to 40 seconds and subject to the
 455  * relationships (2 * (bridge_forward_delay - 1 s) >= bridge_max_age) and
 456  * (bridge_max_age >= 2 * (bridge_hello_time + 1 s)).  The bridge max age is
 457  * only used when 'stp' is the root bridge. */
 458 void
 459 stp_set_max_age(struct stp *stp, int ms)
 460 {
 461     ovs_mutex_lock(&mutex);
 462     stp->rq_max_age = ms;
 463     stp_update_bridge_timers(stp);
 464     ovs_mutex_unlock(&mutex);
 465 }
 466
 467 /* Sets the desired forward delay for 'stp' to 'ms', in milliseconds.  The
 468  * actual forward delay is clamped to the range of 4 to 30 seconds and subject
 469  * to the relationship (2 * (bridge_forward_delay - 1 s) >= bridge_max_age).
 470  * The bridge forward delay is only used when 'stp' is the root bridge. */
 471 void
 472 stp_set_forward_delay(struct stp *stp, int ms)
 473 {
 474     ovs_mutex_lock(&mutex);
 475     stp->rq_forward_delay = ms;
 476     stp_update_bridge_timers(stp);
 477     ovs_mutex_unlock(&mutex);
 478 }
 479
 480 /* Returns the name given to 'stp' in the call to stp_create(). */
 481 const char *
 482 stp_get_name(const struct stp *stp)
 483 {
 484     char *name;
 485
 486     ovs_mutex_lock(&mutex);
 487     name = stp->name;
 488     ovs_mutex_unlock(&mutex);
 489     return name;
 490 }
 491
 492 /* Returns the bridge ID for 'stp'. */
 493 stp_identifier
 494 stp_get_bridge_id(const struct stp *stp)
 495 {
 496     stp_identifier bridge_id;
 497
 498     ovs_mutex_lock(&mutex);
 499     bridge_id = stp->bridge_id;
 500     ovs_mutex_unlock(&mutex);
 501     return bridge_id;
 502 }
 503
 504 /* Returns the bridge ID of the bridge currently believed to be the root. */
 505 stp_identifier
 506 stp_get_designated_root(const struct stp *stp)
 507 {
 508     stp_identifier designated_root;
 509
 510     ovs_mutex_lock(&mutex);
 511     designated_root = stp->designated_root;
 512     ovs_mutex_unlock(&mutex);
 513     return designated_root;
 514 }
 515
 516 /* Returns true if 'stp' believes itself to the be root of the spanning tree,
 517  * false otherwise. */
 518 bool
 519 stp_is_root_bridge(const struct stp *stp)
 520 {
 521     bool is_root;
 522
 523     ovs_mutex_lock(&mutex);
 524     is_root = stp->bridge_id == stp->designated_root;
 525     ovs_mutex_unlock(&mutex);
 526     return is_root;
 527 }
 528
 529 /* Returns the cost of the path from 'stp' to the root of the spanning tree. */
 530 int
 531 stp_get_root_path_cost(const struct stp *stp)
 532 {
 533     int cost;
 534
 535     ovs_mutex_lock(&mutex);
 536     cost = stp->root_path_cost;
 537     ovs_mutex_unlock(&mutex);
 538     return cost;
 539 }
 540
 541 /* Returns the bridge hello time, in ms.  The returned value is not necessarily
 542  * the value passed to stp_set_hello_time(): it is clamped to the valid range
 543  * and quantized to the STP timer resolution.  */
 544 int
 545 stp_get_hello_time(const struct stp *stp)
 546 {
 547     int time;
 548
 549     ovs_mutex_lock(&mutex);
 550     time = timer_to_ms(stp->bridge_hello_time);
 551     ovs_mutex_unlock(&mutex);
 552     return time;
 553 }
 554
 555 /* Returns the bridge max age, in ms.  The returned value is not necessarily
 556  * the value passed to stp_set_max_age(): it is clamped to the valid range,
 557  * quantized to the STP timer resolution, and adjusted to match the constraints
 558  * due to the hello time.  */
 559 int
 560 stp_get_max_age(const struct stp *stp)
 561 {
 562     int time;
 563
 564     ovs_mutex_lock(&mutex);
 565     time = timer_to_ms(stp->bridge_max_age);
 566     ovs_mutex_unlock(&mutex);
 567     return time;
 568 }
 569
 570 /* Returns the bridge forward delay, in ms.  The returned value is not
 571  * necessarily the value passed to stp_set_forward_delay(): it is clamped to
 572  * the valid range, quantized to the STP timer resolution, and adjusted to
 573  * match the constraints due to the forward delay.  */
 574 int
 575 stp_get_forward_delay(const struct stp *stp)
 576 {
 577     int time;
 578
 579     ovs_mutex_lock(&mutex);
 580     time = timer_to_ms(stp->bridge_forward_delay);
 581     ovs_mutex_unlock(&mutex);
 582     return time;
 583 }
 584
 585 /* Returns true if something has happened to 'stp' which necessitates flushing
 586  * the client's MAC learning table.  Calling this function resets 'stp' so that
 587  * future calls will return false until flushing is required again. */
 588 bool
 589 stp_check_and_reset_fdb_flush(struct stp *stp)
 590 {
 591     bool needs_flush;
 592
 593     ovs_mutex_lock(&mutex);
 594     needs_flush = stp->fdb_needs_flush;
 595     stp->fdb_needs_flush = false;
 596     ovs_mutex_unlock(&mutex);
 597     return needs_flush;
 598 }
 599
 600 /* Returns the port in 'stp' with index 'port_no', which must be between 0 and
 601  * STP_MAX_PORTS. */
 602 struct stp_port *
 603 stp_get_port(struct stp *stp, int port_no)
 604 {
 605     struct stp_port *port;
 606
 607     ovs_mutex_lock(&mutex);
 608     ovs_assert(port_no >= 0 && port_no < ARRAY_SIZE(stp->ports));
 609     port = &stp->ports[port_no];
 610     ovs_mutex_unlock(&mutex);
 611     return port;
 612 }
 613
 614 /* Returns the port connecting 'stp' to the root bridge, or a null pointer if
 615  * there is no such port. */
 616 struct stp_port *
 617 stp_get_root_port(struct stp *stp)
 618 {
 619     struct stp_port *port;
 620
 621     ovs_mutex_lock(&mutex);
 622     port = stp->root_port;
 623     ovs_mutex_unlock(&mutex);
 624     return port;
 625 }
 626
 627 /* Finds a port whose state has changed.  If successful, stores the port whose
 628  * state changed in '*portp' and returns true.  If no port has changed, stores
 629  * NULL in '*portp' and returns false. */
 630 bool
 631 stp_get_changed_port(struct stp *stp, struct stp_port **portp)
 632 {
 633     struct stp_port *end, *p;
 634     bool changed = false;
 635
 636     ovs_mutex_lock(&mutex);
 637     end = &stp->ports[ARRAY_SIZE(stp->ports)];
 638     for (p = stp->first_changed_port; p < end; p++) {
 639         if (p->state_changed) {
 640             p->state_changed = false;
 641             stp->first_changed_port = p + 1;
 642             *portp = p;
 643             changed = true;
 644             goto out;
 645         }
 646     }
 647     stp->first_changed_port = end;
 648     *portp = NULL;
 649
 650 out:
 651     ovs_mutex_unlock(&mutex);
 652     return changed;
 653 }
 654
 655 /* Returns the name for the given 'state' (for use in debugging and log
 656  * messages). */
 657 const char *
 658 stp_state_name(enum stp_state state)
 659 {
 660     switch (state) {
 661     case STP_DISABLED:
 662         return "disabled";
 663     case STP_LISTENING:
 664         return "listening";
 665     case STP_LEARNING:
 666         return "learning";
 667     case STP_FORWARDING:
 668         return "forwarding";
 669     case STP_BLOCKING:
 670         return "blocking";
 671     default:
 672         OVS_NOT_REACHED();
 673     }
 674 }
 675
 676 /* Returns true if 'state' is one in which packets received on a port should
 677  * be forwarded, false otherwise.
 678  */
 679 bool
 680 stp_forward_in_state(enum stp_state state)
 681 {
 682     return (state & STP_FORWARDING) != 0;
 683 }
 684
 685 /* Returns true if 'state' is one in which MAC learning should be done on
 686  * packets received on a port, false otherwise.
 687  */
 688 bool
 689 stp_learn_in_state(enum stp_state state)
 690 {
 691     return (state & (STP_LEARNING | STP_FORWARDING)) != 0;
 692 }
 693
 694 /* Returns true if 'state' is one in which bpdus should be forwarded on a
 695  * port, false otherwise.
 696  *
 697  * Returns true if 'state' is STP_DISABLED, since in that case the port does
 698  * not generate the bpdu and should just forward it (e.g. patch port on pif
 699  * bridge). */
 700 bool
 701 stp_should_forward_bpdu(enum stp_state state)
 702 {
 703     return (state &
 704             ( STP_DISABLED | STP_LISTENING | STP_LEARNING
 705               | STP_FORWARDING)) != 0;
 706 }
 707
 708 /* Returns the name for the given 'role' (for use in debugging and log
 709  * messages). */
 710 const char *
 711 stp_role_name(enum stp_role role)
 712 {
 713     switch (role) {
 714     case STP_ROLE_ROOT:
 715         return "root";
 716     case STP_ROLE_DESIGNATED:
 717         return "designated";
 718     case STP_ROLE_ALTERNATE:
 719         return "alternate";
 720     case STP_ROLE_DISABLED:
 721         return "disabled";
 722     default:
 723         OVS_NOT_REACHED();
 724     }
 725 }
 726
 727 /* Notifies the STP entity that bridge protocol data unit 'bpdu', which is
 728  * 'bpdu_size' bytes in length, was received on port 'p'.
 729  *
 730  * This function may call the 'send_bpdu' function provided to stp_create(). */
 731 void
 732 stp_received_bpdu(struct stp_port *p, const void *bpdu, size_t bpdu_size)
 733 {
 734     struct stp *stp = p->stp;
 735     const struct stp_bpdu_header *header;
 736
 737     ovs_mutex_lock(&mutex);
 738     if (p->state == STP_DISABLED) {
 739         goto out;
 740     }
 741
 742     if (bpdu_size < sizeof(struct stp_bpdu_header)) {
 743         VLOG_WARN("%s: received runt %"PRIuSIZE"-byte BPDU", stp->name, bpdu_size);
 744         p->error_count++;
 745         goto out;
 746     }
 747
 748     header = bpdu;
 749     if (header->protocol_id != htons(STP_PROTOCOL_ID)) {
 750         VLOG_WARN("%s: received BPDU with unexpected protocol ID %"PRIu16,
 751                   stp->name, ntohs(header->protocol_id));
 752         p->error_count++;
 753         goto out;
 754     }
 755     if (header->protocol_version != STP_PROTOCOL_VERSION) {
 756         VLOG_DBG("%s: received BPDU with unexpected protocol version %"PRIu8,
 757                  stp->name, header->protocol_version);
 758     }
 759
 760     switch (header->bpdu_type) {
 761     case STP_TYPE_CONFIG:
 762         if (bpdu_size < sizeof(struct stp_config_bpdu)) {
 763             VLOG_WARN("%s: received config BPDU with invalid size %"PRIuSIZE,
 764                       stp->name, bpdu_size);
 765             p->error_count++;
 766             goto out;
 767         }
 768         stp_received_config_bpdu(stp, p, bpdu);
 769         break;
 770
 771     case STP_TYPE_TCN:
 772         if (bpdu_size != sizeof(struct stp_tcn_bpdu)) {
 773             VLOG_WARN("%s: received TCN BPDU with invalid size %"PRIuSIZE,
 774                       stp->name, bpdu_size);
 775             p->error_count++;
 776             goto out;
 777         }
 778         stp_received_tcn_bpdu(stp, p);
 779         break;
 780
 781     default:
 782         VLOG_WARN("%s: received BPDU of unexpected type %"PRIu8,
 783                   stp->name, header->bpdu_type);
 784         p->error_count++;
 785         goto out;
 786     }
 787     p->rx_count++;
 788
 789 out:
 790     ovs_mutex_unlock(&mutex);
 791 }
 792
 793 /* Returns the STP entity in which 'p' is nested. */
 794 struct stp *
 795 stp_port_get_stp(struct stp_port *p)
 796 {
 797     struct stp *stp;
 798
 799     ovs_mutex_lock(&mutex);
 800     stp = p->stp;
 801     ovs_mutex_unlock(&mutex);
 802     return stp;
 803 }
 804
 805 void
 806 stp_port_set_name(struct stp_port *p, const char *name)
 807 {
 808     char *old;
 809
 810     ovs_mutex_lock(&mutex);
 811     old = p->port_name;
 812     p->port_name = xstrdup(name);
 813     free(old);
 814     ovs_mutex_unlock(&mutex);
 815 }
 816
 817 /* Sets the 'aux' member of 'p'.
 818  *
 819  * The 'aux' member will be reset to NULL when stp_port_disable() is
 820  * called or stp_port_enable() is called when the port is in a Disabled
 821  * state. */
 822 void
 823 stp_port_set_aux(struct stp_port *p, void *aux)
 824 {
 825     ovs_mutex_lock(&mutex);
 826     p->aux = aux;
 827     ovs_mutex_unlock(&mutex);
 828 }
 829
 830 /* Returns the 'aux' member of 'p'. */
 831 void *
 832 stp_port_get_aux(struct stp_port *p)
 833 {
 834     void *aux;
 835
 836     ovs_mutex_lock(&mutex);
 837     aux = p->aux;
 838     ovs_mutex_unlock(&mutex);
 839     return aux;
 840 }
 841
 842 /* Returns the index of port 'p' within its bridge. */
 843 int
 844 stp_port_no(const struct stp_port *p)
 845 {
 846     struct stp *stp;
 847     int index;
 848
 849     ovs_mutex_lock(&mutex);
 850     stp = p->stp;
 851     ovs_assert(p >= stp->ports && p < &stp->ports[ARRAY_SIZE(stp->ports)]);
 852     index = p - p->stp->ports;
 853     ovs_mutex_unlock(&mutex);
 854     return index;
 855 }
 856
 857 /* Returns the port ID for 'p'. */
 858 int
 859 stp_port_get_id(const struct stp_port *p)
 860 {
 861     int port_id;
 862
 863     ovs_mutex_lock(&mutex);
 864     port_id = p->port_id;
 865     ovs_mutex_unlock(&mutex);
 866     return port_id;
 867 }
 868
 869 /* Returns the state of port 'p'. */
 870 enum stp_state
 871 stp_port_get_state(const struct stp_port *p)
 872 {
 873     enum stp_state state;
 874
 875     ovs_mutex_lock(&mutex);
 876     state = p->state;
 877     ovs_mutex_unlock(&mutex);
 878     return state;
 879 }
 880
 881 /* Returns the role of port 'p'. */
 882 enum stp_role
 883 stp_port_get_role(const struct stp_port *p)
 884 {
 885     struct stp_port *root_port;
 886     enum stp_role role;
 887
 888     ovs_mutex_lock(&mutex);
 889     root_port = p->stp->root_port;
 890     if (root_port && root_port->port_id == p->port_id) {
 891         role = STP_ROLE_ROOT;
 892     } else if (stp_is_designated_port(p)) {
 893         role = STP_ROLE_DESIGNATED;
 894     } else if (p->state == STP_DISABLED) {
 895         role = STP_ROLE_DISABLED;
 896     } else {
 897         role = STP_ROLE_ALTERNATE;
 898     }
 899     ovs_mutex_unlock(&mutex);
 900     return role;
 901 }
 902
 903 /* Retrieves BPDU transmit and receive counts for 'p'. */
 904 void
 905 stp_port_get_counts(const struct stp_port *p,
 906                     int *tx_count, int *rx_count, int *error_count)
 907 {
 908     ovs_mutex_lock(&mutex);
 909     *tx_count = p->tx_count;
 910     *rx_count = p->rx_count;
 911     *error_count = p->error_count;
 912     ovs_mutex_unlock(&mutex);
 913 }
 914
 915 /* Disables STP on port 'p'. */
 916 void
 917 stp_port_disable(struct stp_port *p)
 918 {
 919     struct stp *stp;
 920
 921     ovs_mutex_lock(&mutex);
 922     stp = p->stp;
 923     if (p->state != STP_DISABLED) {
 924         bool root = stp_is_root_bridge(stp);
 925         stp_become_designated_port(p);
 926         stp_set_port_state(p, STP_DISABLED);
 927         p->topology_change_ack = false;
 928         p->config_pending = false;
 929         stp_stop_timer(&p->message_age_timer);
 930         stp_stop_timer(&p->forward_delay_timer);
 931         stp_configuration_update(stp);
 932         stp_port_state_selection(stp);
 933         if (stp_is_root_bridge(stp) && !root) {
 934             stp_become_root_bridge(stp);
 935         }
 936         p->aux = NULL;
 937     }
 938     ovs_mutex_unlock(&mutex);
 939 }
 940
 941 /* Enables STP on port 'p'.  The port will initially be in "blocking" state. */
 942 void
 943 stp_port_enable(struct stp_port *p)
 944 {
 945     ovs_mutex_lock(&mutex);
 946     if (p->state == STP_DISABLED) {
 947         stp_initialize_port(p, STP_BLOCKING);
 948         stp_port_state_selection(p->stp);
 949     }
 950     ovs_mutex_unlock(&mutex);
 951 }
 952
 953 /* Sets the priority of port 'p' to 'new_priority'.  Lower numerical values
 954  * are interpreted as higher priorities. */
 955 void
 956 stp_port_set_priority(struct stp_port *p, uint8_t new_priority)
 957 {
 958     uint16_t new_port_id;
 959
 960     ovs_mutex_lock(&mutex);
 961     new_port_id  = (p->port_id & 0xff) | (new_priority << 8);
 962     if (p->port_id != new_port_id) {
 963         struct stp *stp = p->stp;
 964         if (stp_is_designated_port(p)) {
 965             p->designated_port = new_port_id;
 966         }
 967         p->port_id = new_port_id;
 968         if (stp->bridge_id == p->designated_bridge
 969             && p->port_id < p->designated_port) {
 970             stp_become_designated_port(p);
 971             stp_port_state_selection(stp);
 972         }
 973     }
 974     ovs_mutex_unlock(&mutex);
 975 }
 976
 977 /* Convert 'speed' (measured in Mb/s) into the path cost. */
 978 uint16_t
 979 stp_convert_speed_to_cost(unsigned int speed)
 980 {
 981     uint16_t ret;
 982
 983     ovs_mutex_lock(&mutex);
 984     ret = speed >= 10000 ? 2  /* 10 Gb/s. */
 985         : speed >= 1000 ? 4 /* 1 Gb/s. */
 986         : speed >= 100 ? 19 /* 100 Mb/s. */
 987         : speed >= 16 ? 62  /* 16 Mb/s. */
 988         : speed >= 10 ? 100 /* 10 Mb/s. */
 989         : speed >= 4 ? 250  /* 4 Mb/s. */
 990         : 19;             /* 100 Mb/s (guess). */
 991     ovs_mutex_unlock(&mutex);
 992     return ret;
 993 }
 994
 995 /* Sets the path cost of port 'p' to 'path_cost'.  Lower values are generally
 996  * used to indicate faster links.  Use stp_port_set_speed() to automatically
 997  * generate a default path cost from a link speed. */
 998 void
 999 stp_port_set_path_cost(struct stp_port *p, uint16_t path_cost)
1000 {
1001     ovs_mutex_lock(&mutex);
1002     if (p->path_cost != path_cost) {
1003         struct stp *stp = p->stp;
1004         p->path_cost = path_cost;
1005         stp_configuration_update(stp);
1006         stp_port_state_selection(stp);
1007     }
1008     ovs_mutex_unlock(&mutex);
1009 }
1010
1011 /* Sets the path cost of port 'p' based on 'speed' (measured in Mb/s). */
1012 void
1013 stp_port_set_speed(struct stp_port *p, unsigned int speed)
1014 {
1015     stp_port_set_path_cost(p, stp_convert_speed_to_cost(speed));
1016 }
1017
1018 /* Enables topology change detection on port 'p'. */
1019 void
1020 stp_port_enable_change_detection(struct stp_port *p)
1021 {
1022     p->change_detection_enabled = true;
1023 }
1024
1025 /* Disables topology change detection on port 'p'. */
1026 void
1027 stp_port_disable_change_detection(struct stp_port *p)
1028 {
1029     p->change_detection_enabled = false;
1030 }
1031 \f
1032 static void
1033 stp_transmit_config(struct stp_port *p) OVS_REQUIRES(mutex)
1034 {
1035     struct stp *stp = p->stp;
1036     bool root = stp_is_root_bridge(stp);
1037     if (!root && !stp->root_port) {
1038         return;
1039     }
1040     if (p->hold_timer.active) {
1041         VLOG_DBG_RL(&stp_rl, "bridge: %s, port: %s, transmit config bpdu pending",
1042                     stp->name, p->port_name);
1043         p->config_pending = true;
1044     } else {
1045         struct stp_config_bpdu config;
1046         memset(&config, 0, sizeof config);
1047         config.header.protocol_id = htons(STP_PROTOCOL_ID);
1048         config.header.protocol_version = STP_PROTOCOL_VERSION;
1049         config.header.bpdu_type = STP_TYPE_CONFIG;
1050         config.flags = 0;
1051         if (p->topology_change_ack) {
1052             config.flags |= STP_CONFIG_TOPOLOGY_CHANGE_ACK;
1053         }
1054         if (stp->topology_change) {
1055             config.flags |= STP_CONFIG_TOPOLOGY_CHANGE;
1056         }
1057         config.root_id = htonll(stp->designated_root);
1058         config.root_path_cost = htonl(stp->root_path_cost);
1059         config.bridge_id = htonll(stp->bridge_id);
1060         config.port_id = htons(p->port_id);
1061         if (root) {
1062             config.message_age = htons(0);
1063         } else {
1064             config.message_age = htons(stp->root_port->message_age_timer.value
1065                                        + MESSAGE_AGE_INCREMENT);
1066         }
1067         config.max_age = htons(stp->max_age);
1068         config.hello_time = htons(stp->hello_time);
1069         config.forward_delay = htons(stp->forward_delay);
1070         if (ntohs(config.message_age) < stp->max_age) {
1071             p->topology_change_ack = false;
1072             p->config_pending = false;
1073             VLOG_DBG_RL(&stp_rl, "bridge: %s, port: %s, transmit config bpdu",
1074                         stp->name, p->port_name);
1075             stp_send_bpdu(p, &config, sizeof config);
1076             stp_start_timer(&p->hold_timer, 0);
1077         }
1078     }
1079 }
1080
1081 static bool
1082 stp_supersedes_port_info(const struct stp_port *p,
1083                          const struct stp_config_bpdu *config)
1084      OVS_REQUIRES(mutex)
1085 {
1086     if (ntohll(config->root_id) != p->designated_root) {
1087         return ntohll(config->root_id) < p->designated_root;
1088     } else if (ntohl(config->root_path_cost) != p->designated_cost) {
1089         return ntohl(config->root_path_cost) < p->designated_cost;
1090     } else if (ntohll(config->bridge_id) != p->designated_bridge) {
1091         return ntohll(config->bridge_id) < p->designated_bridge;
1092     } else {
1093         return (ntohll(config->bridge_id) != p->stp->bridge_id
1094                 || ntohs(config->port_id) <= p->designated_port);
1095     }
1096 }
1097
1098 static void
1099 stp_record_config_information(struct stp_port *p,
1100                               const struct stp_config_bpdu *config)
1101      OVS_REQUIRES(mutex)
1102 {
1103     p->designated_root = ntohll(config->root_id);
1104     p->designated_cost = ntohl(config->root_path_cost);
1105     p->designated_bridge = ntohll(config->bridge_id);
1106     p->designated_port = ntohs(config->port_id);
1107     stp_start_timer(&p->message_age_timer, ntohs(config->message_age));
1108 }
1109
1110 static void
1111 stp_record_config_timeout_values(struct stp *stp,
1112                                  const struct stp_config_bpdu  *config)
1113      OVS_REQUIRES(mutex)
1114 {
1115     stp->max_age = ntohs(config->max_age);
1116     stp->hello_time = ntohs(config->hello_time);
1117     stp->forward_delay = ntohs(config->forward_delay);
1118     stp->topology_change = config->flags & STP_CONFIG_TOPOLOGY_CHANGE;
1119 }
1120
1121 static bool
1122 stp_is_designated_port(const struct stp_port *p) OVS_REQUIRES(mutex)
1123 {
1124     return (p->designated_bridge == p->stp->bridge_id
1125             && p->designated_port == p->port_id);
1126 }
1127
1128 static void
1129 stp_config_bpdu_generation(struct stp *stp) OVS_REQUIRES(mutex)
1130 {
1131     struct stp_port *p;
1132
1133     FOR_EACH_ENABLED_PORT (p, stp) {
1134         if (stp_is_designated_port(p)) {
1135             stp_transmit_config(p);
1136         }
1137     }
1138 }
1139
1140 static void
1141 stp_transmit_tcn(struct stp *stp) OVS_REQUIRES(mutex)
1142 {
1143     struct stp_port *p = stp->root_port;
1144     struct stp_tcn_bpdu tcn_bpdu;
1145
1146     if (!p) {
1147         return;
1148     }
1149     VLOG_DBG_RL(&stp_rl, "bridge: %s, root port: %s, transmit tcn", stp->name,
1150                 p->port_name);
1151     tcn_bpdu.header.protocol_id = htons(STP_PROTOCOL_ID);
1152     tcn_bpdu.header.protocol_version = STP_PROTOCOL_VERSION;
1153     tcn_bpdu.header.bpdu_type = STP_TYPE_TCN;
1154     stp_send_bpdu(p, &tcn_bpdu, sizeof tcn_bpdu);
1155 }
1156
1157 static void
1158 stp_configuration_update(struct stp *stp) OVS_REQUIRES(mutex)
1159 {
1160     stp_root_selection(stp);
1161     stp_designated_port_selection(stp);
1162     seq_change(connectivity_seq_get());
1163 }
1164
1165 static bool
1166 stp_supersedes_root(const struct stp_port *root, const struct stp_port *p)
1167     OVS_REQUIRES(mutex)
1168 {
1169     int p_cost = p->designated_cost + p->path_cost;
1170     int root_cost = root->designated_cost + root->path_cost;
1171
1172     if (p->designated_root != root->designated_root) {
1173         return p->designated_root < root->designated_root;
1174     } else if (p_cost != root_cost) {
1175         return p_cost < root_cost;
1176     } else if (p->designated_bridge != root->designated_bridge) {
1177         return p->designated_bridge < root->designated_bridge;
1178     } else if (p->designated_port != root->designated_port) {
1179         return p->designated_port < root->designated_port;
1180     } else {
1181         return p->port_id < root->port_id;
1182     }
1183 }
1184
1185 static void
1186 stp_root_selection(struct stp *stp) OVS_REQUIRES(mutex)
1187 {
1188     struct stp_port *p, *root;
1189
1190     root = NULL;
1191     FOR_EACH_ENABLED_PORT (p, stp) {
1192         if (stp_is_designated_port(p)
1193             || p->designated_root >= stp->bridge_id) {
1194             continue;
1195         }
1196         if (root && !stp_supersedes_root(root, p)) {
1197             continue;
1198         }
1199         root = p;
1200     }
1201     stp->root_port = root;
1202     if (!root) {
1203         stp->designated_root = stp->bridge_id;
1204         stp->root_path_cost = 0;
1205     } else {
1206         stp->designated_root = root->designated_root;
1207         stp->root_path_cost = root->designated_cost + root->path_cost;
1208     }
1209 }
1210
1211 static void
1212 stp_designated_port_selection(struct stp *stp) OVS_REQUIRES(mutex)
1213 {
1214     struct stp_port *p;
1215
1216     FOR_EACH_ENABLED_PORT (p, stp) {
1217         if (stp_is_designated_port(p)
1218             || p->designated_root != stp->designated_root
1219             || stp->root_path_cost < p->designated_cost
1220             || (stp->root_path_cost == p->designated_cost
1221                 && (stp->bridge_id < p->designated_bridge
1222                     || (stp->bridge_id == p->designated_bridge
1223                         && p->port_id <= p->designated_port))))
1224         {
1225             stp_become_designated_port(p);
1226         }
1227     }
1228 }
1229
1230 static void
1231 stp_become_designated_port(struct stp_port *p) OVS_REQUIRES(mutex)
1232 {
1233     struct stp *stp = p->stp;
1234     p->designated_root = stp->designated_root;
1235     p->designated_cost = stp->root_path_cost;
1236     p->designated_bridge = stp->bridge_id;
1237     p->designated_port = p->port_id;
1238 }
1239
1240 static void
1241 stp_port_state_selection(struct stp *stp) OVS_REQUIRES(mutex)
1242 {
1243     struct stp_port *p;
1244
1245     FOR_EACH_ENABLED_PORT (p, stp) {
1246         if (p == stp->root_port) {
1247             p->config_pending = false;
1248             p->topology_change_ack = false;
1249             stp_make_forwarding(p);
1250         } else if (stp_is_designated_port(p)) {
1251             stp_stop_timer(&p->message_age_timer);
1252             stp_make_forwarding(p);
1253         } else {
1254             p->config_pending = false;
1255             p->topology_change_ack = false;
1256             stp_make_blocking(p);
1257         }
1258     }
1259 }
1260
1261 static void
1262 stp_make_forwarding(struct stp_port *p) OVS_REQUIRES(mutex)
1263 {
1264     if (p->state == STP_BLOCKING) {
1265         stp_set_port_state(p, STP_LISTENING);
1266         stp_start_timer(&p->forward_delay_timer, 0);
1267     }
1268 }
1269
1270 static void
1271 stp_make_blocking(struct stp_port *p) OVS_REQUIRES(mutex)
1272 {
1273     if (!(p->state & (STP_DISABLED | STP_BLOCKING))) {
1274         if (p->state & (STP_FORWARDING | STP_LEARNING)) {
1275             if (p->change_detection_enabled) {
1276                 stp_topology_change_detection(p->stp);
1277             }
1278         }
1279         stp_set_port_state(p, STP_BLOCKING);
1280         stp_stop_timer(&p->forward_delay_timer);
1281     }
1282 }
1283
1284 static void
1285 stp_set_port_state(struct stp_port *p, enum stp_state state)
1286     OVS_REQUIRES(mutex)
1287 {
1288     if (state != p->state && !p->state_changed) {
1289         p->state_changed = true;
1290         if (p < p->stp->first_changed_port) {
1291             p->stp->first_changed_port = p;
1292         }
1293         seq_change(connectivity_seq_get());
1294     }
1295     p->state = state;
1296 }
1297
1298 static void
1299 stp_topology_change_detection(struct stp *stp) OVS_REQUIRES(mutex)
1300 {
1301     static struct vlog_rate_limit rl = VLOG_RATE_LIMIT_INIT(1, 5);
1302
1303     if (stp_is_root_bridge(stp)) {
1304         stp->topology_change = true;
1305         stp_start_timer(&stp->topology_change_timer, 0);
1306     } else if (!stp->topology_change_detected) {
1307         stp_transmit_tcn(stp);
1308         stp_start_timer(&stp->tcn_timer, 0);
1309     }
1310     stp->fdb_needs_flush = true;
1311     stp->topology_change_detected = true;
1312     seq_change(connectivity_seq_get());
1313     VLOG_INFO_RL(&rl, "%s: detected topology change.", stp->name);
1314 }
1315
1316 static void
1317 stp_topology_change_acknowledged(struct stp *stp) OVS_REQUIRES(mutex)
1318 {
1319     stp->topology_change_detected = false;
1320     stp_stop_timer(&stp->tcn_timer);
1321 }
1322
1323 static void
1324 stp_acknowledge_topology_change(struct stp_port *p) OVS_REQUIRES(mutex)
1325 {
1326     p->topology_change_ack = true;
1327     stp_transmit_config(p);
1328 }
1329
1330 static void
1331 stp_received_config_bpdu(struct stp *stp, struct stp_port *p,
1332                          const struct stp_config_bpdu *config)
1333     OVS_REQUIRES(mutex)
1334 {
1335     if (ntohs(config->message_age) >= ntohs(config->max_age)) {
1336         VLOG_WARN("%s: received config BPDU with message age (%u) greater "
1337                   "than max age (%u)",
1338                   stp->name,
1339                   ntohs(config->message_age), ntohs(config->max_age));
1340         return;
1341     }
1342     if (p->state != STP_DISABLED) {
1343         bool root = stp_is_root_bridge(stp);
1344         if (stp_supersedes_port_info(p, config)) {
1345             stp_record_config_information(p, config);
1346             stp_configuration_update(stp);
1347             stp_port_state_selection(stp);
1348             if (!stp_is_root_bridge(stp) && root) {
1349                 stp_stop_timer(&stp->hello_timer);
1350                 if (stp->topology_change_detected) {
1351                     stp_stop_timer(&stp->topology_change_timer);
1352                     stp_transmit_tcn(stp);
1353                     stp_start_timer(&stp->tcn_timer, 0);
1354                 }
1355             }
1356             if (p == stp->root_port) {
1357                 stp_record_config_timeout_values(stp, config);
1358                 stp_config_bpdu_generation(stp);
1359                 if (config->flags & STP_CONFIG_TOPOLOGY_CHANGE_ACK) {
1360                     stp_topology_change_acknowledged(stp);
1361                 }
1362                 if (config->flags & STP_CONFIG_TOPOLOGY_CHANGE) {
1363                     stp->fdb_needs_flush = true;
1364                 }
1365             }
1366         } else if (stp_is_designated_port(p)) {
1367             stp_transmit_config(p);
1368         }
1369     }
1370 }
1371
1372 static void
1373 stp_received_tcn_bpdu(struct stp *stp, struct stp_port *p)
1374     OVS_REQUIRES(mutex)
1375 {
1376     if (p->state != STP_DISABLED) {
1377         if (stp_is_designated_port(p)) {
1378             stp_topology_change_detection(stp);
1379             stp_acknowledge_topology_change(p);
1380         }
1381     }
1382 }
1383
1384 static void
1385 stp_hello_timer_expiry(struct stp *stp) OVS_REQUIRES(mutex)
1386 {
1387     stp_config_bpdu_generation(stp);
1388     stp_start_timer(&stp->hello_timer, 0);
1389 }
1390
1391 static void
1392 stp_message_age_timer_expiry(struct stp_port *p) OVS_REQUIRES(mutex)
1393 {
1394     struct stp *stp = p->stp;
1395     bool root = stp_is_root_bridge(stp);
1396
1397     VLOG_DBG_RL(&stp_rl, "bridge: %s, port: %s, message age timer expired",
1398                 stp->name, p->port_name);
1399     stp_become_designated_port(p);
1400     stp_configuration_update(stp);
1401     stp_port_state_selection(stp);
1402     if (stp_is_root_bridge(stp) && !root) {
1403         stp->max_age = stp->bridge_max_age;
1404         stp->hello_time = stp->bridge_hello_time;
1405         stp->forward_delay = stp->bridge_forward_delay;
1406         stp_topology_change_detection(stp);
1407         stp_stop_timer(&stp->tcn_timer);
1408         stp_config_bpdu_generation(stp);
1409         stp_start_timer(&stp->hello_timer, 0);
1410     }
1411 }
1412
1413 static bool
1414 stp_is_designated_for_some_port(const struct stp *stp) OVS_REQUIRES(mutex)
1415 {
1416     const struct stp_port *p;
1417
1418     FOR_EACH_ENABLED_PORT (p, stp) {
1419         if (p->designated_bridge == stp->bridge_id) {
1420             return true;
1421         }
1422     }
1423     return false;
1424 }
1425
1426 static void
1427 stp_forward_delay_timer_expiry(struct stp_port *p) OVS_REQUIRES(mutex)
1428 {
1429     if (p->state == STP_LISTENING) {
1430         stp_set_port_state(p, STP_LEARNING);
1431         stp_start_timer(&p->forward_delay_timer, 0);
1432     } else if (p->state == STP_LEARNING) {
1433         stp_set_port_state(p, STP_FORWARDING);
1434         if (stp_is_designated_for_some_port(p->stp)) {
1435             if (p->change_detection_enabled) {
1436                 stp_topology_change_detection(p->stp);
1437             }
1438         }
1439     }
1440 }
1441
1442 static void
1443 stp_tcn_timer_expiry(struct stp *stp) OVS_REQUIRES(mutex)
1444 {
1445     stp_transmit_tcn(stp);
1446     stp_start_timer(&stp->tcn_timer, 0);
1447 }
1448
1449 static void
1450 stp_topology_change_timer_expiry(struct stp *stp) OVS_REQUIRES(mutex)
1451 {
1452     stp->topology_change_detected = false;
1453     stp->topology_change = false;
1454 }
1455
1456 static void
1457 stp_hold_timer_expiry(struct stp_port *p) OVS_REQUIRES(mutex)
1458 {
1459     if (p->config_pending) {
1460         stp_transmit_config(p);
1461     }
1462 }
1463
1464 static void
1465 stp_initialize_port(struct stp_port *p, enum stp_state state)
1466     OVS_REQUIRES(mutex)
1467 {
1468     ovs_assert(state & (STP_DISABLED | STP_BLOCKING));
1469     stp_become_designated_port(p);
1470
1471     if (!p->state && state == STP_DISABLED) {
1472         p->state = state; /* Do not trigger state change when initializing. */
1473     } else {
1474         stp_set_port_state(p, state);
1475     }
1476     p->topology_change_ack = false;
1477     p->config_pending = false;
1478     p->change_detection_enabled = true;
1479     p->aux = NULL;
1480     stp_stop_timer(&p->message_age_timer);
1481     stp_stop_timer(&p->forward_delay_timer);
1482     stp_stop_timer(&p->hold_timer);
1483     p->tx_count = p->rx_count = p->error_count = 0;
1484 }
1485
1486 static void
1487 stp_become_root_bridge(struct stp *stp) OVS_REQUIRES(mutex)
1488 {
1489     stp->max_age = stp->bridge_max_age;
1490     stp->hello_time = stp->bridge_hello_time;
1491     stp->forward_delay = stp->bridge_forward_delay;
1492     stp_topology_change_detection(stp);
1493     stp_stop_timer(&stp->tcn_timer);
1494     stp_config_bpdu_generation(stp);
1495     stp_start_timer(&stp->hello_timer, 0);
1496 }
1497
1498 static void
1499 stp_start_timer(struct stp_timer *timer, int value) OVS_REQUIRES(mutex)
1500 {
1501     timer->value = value;
1502     timer->active = true;
1503 }
1504
1505 static void
1506 stp_stop_timer(struct stp_timer *timer) OVS_REQUIRES(mutex)
1507 {
1508     timer->active = false;
1509 }
1510
1511 static bool
1512 stp_timer_expired(struct stp_timer *timer, int elapsed, int timeout)
1513     OVS_REQUIRES(mutex)
1514 {
1515     if (timer->active) {
1516         timer->value += elapsed;
1517         if (timer->value >= timeout) {
1518             timer->active = false;
1519             return true;
1520         }
1521     }
1522     return false;
1523 }
1524
1525 /* Returns the number of whole STP timer ticks in 'ms' milliseconds.  There
1526  * are 256 STP timer ticks per second. */
1527 static int
1528 ms_to_timer(int ms)
1529 {
1530     return ms * 0x100 / 1000;
1531 }
1532
1533 /* Returns the number of whole milliseconds in 'timer' STP timer ticks.  There
1534  * are 256 STP timer ticks per second. */
1535 static int
1536 timer_to_ms(int timer)
1537 {
1538     return timer * 1000 / 0x100;
1539 }
1540
1541 static int
1542 clamp(int x, int min, int max)
1543 {
1544     return x < min ? min : x > max ? max : x;
1545 }
1546
1547 static void
1548 stp_update_bridge_timers(struct stp *stp) OVS_REQUIRES(mutex)
1549 {
1550     int ht, ma, fd;
1551
1552     ht = clamp(stp->rq_hello_time, 1000, 10000);
1553     ma = clamp(stp->rq_max_age, MAX(2 * (ht + 1000), 6000), 40000);
1554     fd = clamp(stp->rq_forward_delay, ma / 2 + 1000, 30000);
1555
1556     stp->bridge_hello_time = ms_to_timer(ht);
1557     stp->bridge_max_age = ms_to_timer(ma);
1558     stp->bridge_forward_delay = ms_to_timer(fd);
1559
1560     if (stp_is_root_bridge(stp)) {
1561         stp->max_age = stp->bridge_max_age;
1562         stp->hello_time = stp->bridge_hello_time;
1563         stp->forward_delay = stp->bridge_forward_delay;
1564     }
1565 }
1566
1567 static void
1568 stp_send_bpdu(struct stp_port *p, const void *bpdu, size_t bpdu_size)
1569     OVS_REQUIRES(mutex)
1570 {
1571     struct eth_header *eth;
1572     struct llc_header *llc;
1573     struct dp_packet *pkt;
1574
1575     /* Skeleton. */
1576     pkt = dp_packet_new(ETH_HEADER_LEN + LLC_HEADER_LEN + bpdu_size);
1577     eth = dp_packet_put_zeros(pkt, sizeof *eth);
1578     llc = dp_packet_put_zeros(pkt, sizeof *llc);
1579     dp_packet_reset_offsets(pkt);
1580     dp_packet_set_l3(pkt, dp_packet_put(pkt, bpdu, bpdu_size));
1581
1582     /* 802.2 header. */
1583     eth->eth_dst = eth_addr_stp;
1584     /* p->stp->send_bpdu() must fill in source address. */
1585     eth->eth_type = htons(dp_packet_size(pkt) - ETH_HEADER_LEN);
1586
1587     /* LLC header. */
1588     llc->llc_dsap = STP_LLC_DSAP;
1589     llc->llc_ssap = STP_LLC_SSAP;
1590     llc->llc_cntl = STP_LLC_CNTL;
1591
1592     p->stp->send_bpdu(pkt, stp_port_no(p), p->stp->aux);
1593     p->tx_count++;
1594 }
1595 \f
1596 /* Unixctl. */
1597
1598 static struct stp *
1599 stp_find(const char *name) OVS_REQUIRES(mutex)
1600 {
1601     struct stp *stp;
1602
1603     LIST_FOR_EACH (stp, node, all_stps) {
1604         if (!strcmp(stp->name, name)) {
1605             return stp;
1606         }
1607     }
1608     return NULL;
1609 }
1610
1611 static void
1612 stp_unixctl_tcn(struct unixctl_conn *conn, int argc,
1613                 const char *argv[], void *aux OVS_UNUSED)
1614 {
1615     ovs_mutex_lock(&mutex);
1616     if (argc > 1) {
1617         struct stp *stp = stp_find(argv[1]);
1618
1619         if (!stp) {
1620             unixctl_command_reply_error(conn, "no such stp object");
1621             goto out;
1622         }
1623         stp_topology_change_detection(stp);
1624     } else {
1625         struct stp *stp;
1626
1627         LIST_FOR_EACH (stp, node, all_stps) {
1628             stp_topology_change_detection(stp);
1629         }
1630     }
1631
1632     unixctl_command_reply(conn, "OK");
1633
1634 out:
1635     ovs_mutex_unlock(&mutex);
1636 }