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