sys/net/bridge/bridgestp.c

   1 /*
   2  * Copyright (c) 2000 Jason L. Wright (jason@thought.net)
   3  * All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions
   7  * are met:
   8  * 1. Redistributions of source code must retain the above copyright
   9  *    notice, this list of conditions and the following disclaimer.
  10  * 2. Redistributions in binary form must reproduce the above copyright
  11  *    notice, this list of conditions and the following disclaimer in the
  12  *    documentation and/or other materials provided with the distribution.
  13  * 3. All advertising materials mentioning features or use of this software
  14  *    must display the following acknowledgement:
  15  *      This product includes software developed by Jason L. Wright
  16  * 4. The name of the author may not be used to endorse or promote products
  17  *    derived from this software without specific prior written permission.
  18  *
  19  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  20  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
  21  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  22  * DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT,
  23  * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
  24  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
  25  * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  26  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
  27  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
  28  * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  29  * POSSIBILITY OF SUCH DAMAGE.
  30  *
  31  * $OpenBSD: bridgestp.c,v 1.5 2001/03/22 03:48:29 jason Exp $
  32  * $NetBSD: bridgestp.c,v 1.5 2003/11/28 08:56:48 keihan Exp $
  33  * $FreeBSD: src/sys/net/bridgestp.c,v 1.7 2005/10/11 02:58:32 thompsa Exp $
  34  */
  35
  36 /*
  37  * Implementation of the spanning tree protocol as defined in
  38  * ISO/IEC Final DIS 15802-3 (IEEE P802.1D/D17), May 25, 1998.
  39  * (In English: IEEE 802.1D, Draft 17, 1998)
  40  */
  41
  42 #include <sys/param.h>
  43 #include <sys/systm.h>
  44 #include <sys/mbuf.h>
  45 #include <sys/socket.h>
  46 #include <sys/sockio.h>
  47 #include <sys/kernel.h>
  48 #include <sys/callout.h>
  49 #include <sys/proc.h>
  50 #include <sys/lock.h>
  51 #include <sys/thread.h>
  52 #include <sys/thread2.h>
  53 #include <sys/msgport2.h>
  54
  55 #include <net/if.h>
  56 #include <net/if_dl.h>
  57 #include <net/if_types.h>
  58 #include <net/if_llc.h>
  59 #include <net/if_media.h>
  60
  61 #include <netinet/in.h>
  62 #include <netinet/in_systm.h>
  63 #include <netinet/in_var.h>
  64 #include <netinet/if_ether.h>
  65 #include <net/bridge/if_bridgevar.h>
  66
  67 /* BPDU message types */
  68 #define BSTP_MSGTYPE_CFG        0x00            /* Configuration */
  69 #define BSTP_MSGTYPE_TCN        0x80            /* Topology chg notification */
  70
  71 /* BPDU flags */
  72 #define BSTP_FLAG_TC            0x01            /* Topology change */
  73 #define BSTP_FLAG_TCA           0x80            /* Topology change ack */
  74
  75 #define BSTP_MESSAGE_AGE_INCR   (1 * 256)       /* in 256ths of a second */
  76 #define BSTP_TICK_VAL           (1 * 256)       /* in 256ths of a second */
  77
  78 /*
  79  * Because BPDU's do not make nicely aligned structures, two different
  80  * declarations are used: bstp_?bpdu (wire representation, packed) and
  81  * bstp_*_unit (internal, nicely aligned version).
  82  */
  83
  84 /* configuration bridge protocol data unit */
  85 struct bstp_cbpdu {
  86         uint8_t         cbu_dsap;               /* LLC: destination sap */
  87         uint8_t         cbu_ssap;               /* LLC: source sap */
  88         uint8_t         cbu_ctl;                /* LLC: control */
  89         uint16_t        cbu_protoid;            /* protocol id */
  90         uint8_t         cbu_protover;           /* protocol version */
  91         uint8_t         cbu_bpdutype;           /* message type */
  92         uint8_t         cbu_flags;              /* flags (below) */
  93
  94         /* root id */
  95         uint16_t        cbu_rootpri;            /* root priority */
  96         uint8_t cbu_rootaddr[6];        /* root address */
  97
  98         uint32_t        cbu_rootpathcost;       /* root path cost */
  99
 100         /* bridge id */
 101         uint16_t        cbu_bridgepri;          /* bridge priority */
 102         uint8_t         cbu_bridgeaddr[6];      /* bridge address */
 103
 104         uint16_t        cbu_portid;             /* port id */
 105         uint16_t        cbu_messageage;         /* current message age */
 106         uint16_t        cbu_maxage;             /* maximum age */
 107         uint16_t        cbu_hellotime;          /* hello time */
 108         uint16_t        cbu_forwarddelay;       /* forwarding delay */
 109 } __attribute__((__packed__));
 110
 111 /* topology change notification bridge protocol data unit */
 112 struct bstp_tbpdu {
 113         uint8_t         tbu_dsap;               /* LLC: destination sap */
 114         uint8_t         tbu_ssap;               /* LLC: source sap */
 115         uint8_t         tbu_ctl;                /* LLC: control */
 116         uint16_t        tbu_protoid;            /* protocol id */
 117         uint8_t         tbu_protover;           /* protocol version */
 118         uint8_t         tbu_bpdutype;           /* message type */
 119 } __attribute__((__packed__));
 120
 121 const uint8_t bstp_etheraddr[] = { 0x01, 0x80, 0xc2, 0x00, 0x00, 0x00 };
 122
 123 static void     bstp_initialize_port(struct bridge_softc *,
 124                     struct bridge_iflist *);
 125 static void     bstp_ifupdstatus(struct bridge_softc *, struct bridge_iflist *);
 126 static void     bstp_enable_port(struct bridge_softc *, struct bridge_iflist *);
 127 static void     bstp_disable_port(struct bridge_softc *,
 128                     struct bridge_iflist *);
 129 #ifdef notused
 130 static void     bstp_enable_change_detection(struct bridge_iflist *);
 131 static void     bstp_disable_change_detection(struct bridge_iflist *);
 132 #endif /* notused */
 133 static int      bstp_root_bridge(struct bridge_softc *sc);
 134 static void     bstp_transmit_config(struct bridge_softc *,
 135                     struct bridge_iflist *);
 136 static void     bstp_transmit_tcn(struct bridge_softc *);
 137 static void     bstp_received_config_bpdu(struct bridge_softc *,
 138                     struct bridge_iflist *, struct bstp_config_unit *);
 139 static void     bstp_received_tcn_bpdu(struct bridge_softc *,
 140                     struct bridge_iflist *, struct bstp_tcn_unit *);
 141 static void     bstp_record_config_information(struct bridge_softc *,
 142                     struct bridge_iflist *, struct bstp_config_unit *);
 143 static void     bstp_record_config_timeout_values(struct bridge_softc *,
 144                     struct bstp_config_unit *);
 145 static void     bstp_config_bpdu_generation(struct bridge_softc *);
 146 static void     bstp_send_config_bpdu(struct bridge_softc *,
 147                     struct bridge_iflist *, struct bstp_config_unit *);
 148 static void     bstp_configuration_update(struct bridge_softc *);
 149 static void     bstp_port_state_selection(struct bridge_softc *);
 150 static void     bstp_clear_peer_info(struct bridge_softc *,
 151                     struct bridge_iflist *);
 152 static void     bstp_make_forwarding(struct bridge_softc *,
 153                     struct bridge_iflist *);
 154 static void     bstp_make_blocking(struct bridge_softc *,
 155                     struct bridge_iflist *);
 156 static void     bstp_make_l1blocking(struct bridge_softc *sc,
 157                     struct bridge_iflist *bif);
 158 static void     bstp_adjust_bonded_states(struct bridge_softc *sc,
 159                     struct bridge_iflist *obif);
 160 static void     bstp_set_port_state(struct bridge_iflist *, uint8_t);
 161 #ifdef notused
 162 static void     bstp_set_bridge_priority(struct bridge_softc *, uint64_t);
 163 static void     bstp_set_port_priority(struct bridge_softc *,
 164                     struct bridge_iflist *, uint16_t);
 165 static void     bstp_set_path_cost(struct bridge_softc *,
 166                     struct bridge_iflist *, uint32_t);
 167 #endif /* notused */
 168 static void     bstp_topology_change_detection(struct bridge_softc *);
 169 static void     bstp_topology_change_acknowledged(struct bridge_softc *);
 170 static void     bstp_acknowledge_topology_change(struct bridge_softc *,
 171                     struct bridge_iflist *);
 172
 173 static void     bstp_tick(void *);
 174 static void     bstp_timer_start(struct bridge_timer *, uint16_t);
 175 static void     bstp_timer_stop(struct bridge_timer *);
 176 static int      bstp_timer_expired(struct bridge_timer *, uint16_t);
 177
 178 static void     bstp_hold_timer_expiry(struct bridge_softc *,
 179                     struct bridge_iflist *);
 180 static void     bstp_message_age_timer_expiry(struct bridge_softc *,
 181                     struct bridge_iflist *);
 182 static void     bstp_forward_delay_timer_expiry(struct bridge_softc *,
 183                     struct bridge_iflist *);
 184 static void     bstp_topology_change_timer_expiry(struct bridge_softc *);
 185 static void     bstp_tcn_timer_expiry(struct bridge_softc *);
 186 static void     bstp_hello_timer_expiry(struct bridge_softc *);
 187 static int      bstp_addr_cmp(const uint8_t *, const uint8_t *);
 188
 189 /*
 190  * When transmitting a config we tack on our path cost to
 191  * our aggregated path-to-root cost.
 192  *
 193  * Note that sc_designated_cost is the lowest root path cost from all
 194  * incoming links.  When one is talking about two bridges with multiple
 195  * links between them the root path cost the secondary bridge transmits
 196  * will be the lowest root path cost it received across those three
 197  * links and NOT necessarily the root path cost it received specifically
 198  * on that particular link.  The receiving end must still add its local
 199  * link cost back in for differentiation purposes.
 200  */
 201 static void
 202 bstp_transmit_config(struct bridge_softc *sc, struct bridge_iflist *bif)
 203 {
 204         if (bif->bif_hold_timer.active) {
 205                 bif->bif_config_pending = 1;
 206                 return;
 207         }
 208
 209         bif->bif_config_bpdu.cu_message_type = BSTP_MSGTYPE_CFG;
 210         bif->bif_config_bpdu.cu_rootid = sc->sc_designated_root;
 211         bif->bif_config_bpdu.cu_root_path_cost = sc->sc_designated_cost +
 212                                                  bif->bif_path_cost;
 213         bif->bif_config_bpdu.cu_bridge_id = sc->sc_bridge_id;
 214         bif->bif_config_bpdu.cu_port_id = bif->bif_port_id;
 215
 216         if (bstp_root_bridge(sc)) {
 217                 bif->bif_config_bpdu.cu_message_age = 0;
 218         } else if (sc->sc_root_port) {
 219                 bif->bif_config_bpdu.cu_message_age =
 220                         sc->sc_root_port->bif_message_age_timer.value +
 221                         BSTP_MESSAGE_AGE_INCR;
 222         } else {
 223                 bif->bif_config_bpdu.cu_message_age = BSTP_MESSAGE_AGE_INCR;
 224         }
 225
 226         bif->bif_config_bpdu.cu_max_age = sc->sc_max_age;
 227         bif->bif_config_bpdu.cu_hello_time = sc->sc_hello_time;
 228         bif->bif_config_bpdu.cu_forward_delay = sc->sc_forward_delay;
 229         bif->bif_config_bpdu.cu_topology_change_acknowledgment
 230             = bif->bif_topology_change_acknowledge;
 231         bif->bif_config_bpdu.cu_topology_change = sc->sc_topology_change;
 232
 233         if (bif->bif_config_bpdu.cu_message_age < sc->sc_max_age ||
 234             (sc->sc_ifp->if_flags & IFF_LINK1)) {
 235                 bif->bif_topology_change_acknowledge = 0;
 236                 bif->bif_config_pending = 0;
 237                 bstp_send_config_bpdu(sc, bif, &bif->bif_config_bpdu);
 238                 bstp_timer_start(&bif->bif_hold_timer, 0);
 239         }
 240 }
 241
 242 static void
 243 bstp_send_config_bpdu(struct bridge_softc *sc, struct bridge_iflist *bif,
 244                       struct bstp_config_unit *cu)
 245 {
 246         struct ifnet *ifp;
 247         struct mbuf *m;
 248         struct ether_header *eh;
 249         struct bstp_cbpdu bpdu;
 250
 251         ifp = bif->bif_ifp;
 252
 253         if ((ifp->if_flags & IFF_RUNNING) == 0)
 254                 return;
 255
 256         MGETHDR(m, MB_DONTWAIT, MT_DATA);
 257         if (m == NULL)
 258                 return;
 259
 260         eh = mtod(m, struct ether_header *);
 261
 262         m->m_pkthdr.rcvif = ifp;
 263         m->m_pkthdr.len = sizeof(*eh) + sizeof(bpdu);
 264         m->m_len = m->m_pkthdr.len;
 265
 266         bpdu.cbu_ssap = bpdu.cbu_dsap = LLC_8021D_LSAP;
 267         bpdu.cbu_ctl = LLC_UI;
 268         bpdu.cbu_protoid = htons(0);
 269         bpdu.cbu_protover = 0;
 270         bpdu.cbu_bpdutype = cu->cu_message_type;
 271         bpdu.cbu_flags = (cu->cu_topology_change ? BSTP_FLAG_TC : 0) |
 272             (cu->cu_topology_change_acknowledgment ? BSTP_FLAG_TCA : 0);
 273
 274         bpdu.cbu_rootpri = htons(cu->cu_rootid >> 48);
 275         bpdu.cbu_rootaddr[0] = cu->cu_rootid >> 40;
 276         bpdu.cbu_rootaddr[1] = cu->cu_rootid >> 32;
 277         bpdu.cbu_rootaddr[2] = cu->cu_rootid >> 24;
 278         bpdu.cbu_rootaddr[3] = cu->cu_rootid >> 16;
 279         bpdu.cbu_rootaddr[4] = cu->cu_rootid >> 8;
 280         bpdu.cbu_rootaddr[5] = cu->cu_rootid >> 0;
 281
 282         bpdu.cbu_rootpathcost = htonl(cu->cu_root_path_cost);
 283
 284         bpdu.cbu_bridgepri = htons(cu->cu_bridge_id >> 48);
 285         bpdu.cbu_bridgeaddr[0] = cu->cu_bridge_id >> 40;
 286         bpdu.cbu_bridgeaddr[1] = cu->cu_bridge_id >> 32;
 287         bpdu.cbu_bridgeaddr[2] = cu->cu_bridge_id >> 24;
 288         bpdu.cbu_bridgeaddr[3] = cu->cu_bridge_id >> 16;
 289         bpdu.cbu_bridgeaddr[4] = cu->cu_bridge_id >> 8;
 290         bpdu.cbu_bridgeaddr[5] = cu->cu_bridge_id >> 0;
 291
 292         bpdu.cbu_portid = htons(cu->cu_port_id);
 293         bpdu.cbu_messageage = htons(cu->cu_message_age);
 294         bpdu.cbu_maxage = htons(cu->cu_max_age);
 295         bpdu.cbu_hellotime = htons(cu->cu_hello_time);
 296         bpdu.cbu_forwarddelay = htons(cu->cu_forward_delay);
 297
 298         /*
 299          * Packets sent from the bridge always use the bridge MAC
 300          * as the source.
 301          */
 302         memcpy(eh->ether_shost, IF_LLADDR(sc->sc_ifp), ETHER_ADDR_LEN);
 303         memcpy(eh->ether_dhost, bstp_etheraddr, ETHER_ADDR_LEN);
 304         eh->ether_type = htons(sizeof(bpdu));
 305
 306         memcpy(mtod(m, caddr_t) + sizeof(*eh), &bpdu, sizeof(bpdu));
 307
 308         bridge_enqueue(ifp, m);
 309 }
 310
 311 static int
 312 bstp_root_bridge(struct bridge_softc *sc)
 313 {
 314         return (sc->sc_designated_root == sc->sc_bridge_id);
 315 }
 316
 317 /*
 318  * Returns TRUE if the recorded information from our peer has a shorter
 319  * graph distance than our current best.
 320  */
 321 int
 322 bstp_supersedes_port_info(struct bridge_softc *sc, struct bridge_iflist *bif)
 323 {
 324         if (bif->bif_peer_root < sc->sc_designated_root)
 325                 return (1);
 326         if (bif->bif_peer_root > sc->sc_designated_root)
 327                 return (0);
 328
 329         /*
 330          * bif_peer_cost and sc_designated_cost do not include the local
 331          * bif_path_cost, otherwise we would not be able to make this
 332          * comparison.
 333          */
 334         if (bif->bif_peer_cost < sc->sc_designated_cost)
 335                 return (1);
 336         if (bif->bif_peer_cost > sc->sc_designated_cost)
 337                 return (0);
 338
 339         /*
 340          * When the peer costs match we have to check the local path
 341          * cost against the selected root port.  sc_designated_cost
 342          * in an aggregation and cannot be used.
 343          */
 344         if (sc->sc_root_port &&
 345             bif->bif_path_cost < sc->sc_root_port->bif_path_cost)
 346                 return (1);
 347         if (sc->sc_root_port &&
 348             bif->bif_path_cost > sc->sc_root_port->bif_path_cost)
 349                 return (0);
 350
 351         /*
 352          * If the path costs are identical the bridge with the lowest
 353          * bridge_id wins.
 354          */
 355         if (bif->bif_peer_bridge < sc->sc_designated_bridge)
 356                 return (1);
 357         if (bif->bif_peer_bridge > sc->sc_designated_bridge)
 358                 return (0);
 359
 360         /*
 361          * bridge_id or bridge+port collision w/peer returns TRUE.
 362          *
 363          * This case can also occur when two bridges are connected
 364          * via multiple links whos path costs have not been set.
 365          */
 366         if (bif->bif_peer_bridge != sc->sc_bridge_id)
 367                 return (1);
 368         if (bif->bif_peer_port <= sc->sc_designated_port)
 369                 return (1);
 370         return (0);
 371 }
 372
 373 /*
 374  * The shorter graph distance represented by cu (most of which is also
 375  * already stored in our bif_peer_* fields) becomes the designated info.
 376  *
 377  * NOTE: sc_designated_cost does not include bif_path_cost, it is added
 378  *       in later on a port-by-port basis as needed.
 379  */
 380 static void
 381 bstp_record_config_information(struct bridge_softc *sc,
 382                                struct bridge_iflist *bif,
 383                                struct bstp_config_unit *cu)
 384 {
 385         sc->sc_designated_root = bif->bif_peer_root;
 386         sc->sc_designated_cost = bif->bif_peer_cost;
 387         sc->sc_designated_bridge = bif->bif_peer_bridge;
 388         sc->sc_designated_port = bif->bif_peer_port;
 389         bstp_timer_start(&bif->bif_message_age_timer, cu->cu_message_age);
 390 }
 391
 392 static void
 393 bstp_record_config_timeout_values(struct bridge_softc *sc,
 394                                   struct bstp_config_unit *config)
 395 {
 396         sc->sc_max_age = config->cu_max_age;
 397         sc->sc_hello_time = config->cu_hello_time;
 398         sc->sc_forward_delay = config->cu_forward_delay;
 399         sc->sc_topology_change = config->cu_topology_change;
 400 }
 401
 402 static void
 403 bstp_config_bpdu_generation(struct bridge_softc *sc)
 404 {
 405         struct bridge_iflist *bif, *nbif;
 406
 407         TAILQ_FOREACH_MUTABLE(bif, &sc->sc_iflists[mycpuid], bif_next, nbif) {
 408                 if ((bif->bif_flags & IFBIF_STP) == 0)
 409                         continue;
 410                 if (bif->bif_state != BSTP_IFSTATE_DISABLED &&
 411                     ((sc->sc_ifp->if_flags & IFF_LINK1) ||
 412                      (bif->bif_flags & IFBIF_DESIGNATED))) {
 413                         bstp_transmit_config(sc, bif);
 414                 }
 415
 416                 if (nbif != NULL && !nbif->bif_onlist) {
 417                         KKASSERT(bif->bif_onlist);
 418                         nbif = TAILQ_NEXT(bif, bif_next);
 419                 }
 420         }
 421 }
 422
 423 static void
 424 bstp_transmit_tcn(struct bridge_softc *sc)
 425 {
 426         struct bstp_tbpdu bpdu;
 427         struct ifnet *ifp;
 428         struct ether_header *eh;
 429         struct mbuf *m;
 430
 431         if (sc->sc_root_port == NULL)   /* all iterfaces disabled */
 432                 return;
 433
 434         ifp = sc->sc_root_port->bif_ifp;
 435         if ((ifp->if_flags & IFF_RUNNING) == 0)
 436                 return;
 437
 438         MGETHDR(m, MB_DONTWAIT, MT_DATA);
 439         if (m == NULL)
 440                 return;
 441
 442         m->m_pkthdr.rcvif = ifp;
 443         m->m_pkthdr.len = sizeof(*eh) + sizeof(bpdu);
 444         m->m_len = m->m_pkthdr.len;
 445
 446         eh = mtod(m, struct ether_header *);
 447
 448         /*
 449          * Packets sent from the bridge always use the bridge MAC
 450          * as the source.
 451          */
 452         memcpy(eh->ether_shost, IF_LLADDR(sc->sc_ifp), ETHER_ADDR_LEN);
 453         memcpy(eh->ether_dhost, bstp_etheraddr, ETHER_ADDR_LEN);
 454         eh->ether_type = htons(sizeof(bpdu));
 455
 456         bpdu.tbu_ssap = bpdu.tbu_dsap = LLC_8021D_LSAP;
 457         bpdu.tbu_ctl = LLC_UI;
 458         bpdu.tbu_protoid = 0;
 459         bpdu.tbu_protover = 0;
 460         bpdu.tbu_bpdutype = BSTP_MSGTYPE_TCN;
 461
 462         memcpy(mtod(m, caddr_t) + sizeof(*eh), &bpdu, sizeof(bpdu));
 463
 464         bridge_enqueue(ifp, m);
 465 }
 466
 467 /*
 468  * Recalculate sc->sc_designated* and sc->sc_root_port (if our bridge
 469  * is calculated to be the root bridge).  We do this by initializing
 470  * the designated variables to point at us and then scan our peers.
 471  * Any uninitialized peers will have a max-value root.
 472  *
 473  * Clear IFBIF_DESIGNATED on any ports which no longer match the criteria
 474  * required to be a designated port.  Only aged out ports and the root
 475  * port can be designated.
 476  *
 477  * If we win we do a second scan to determine which port on our bridge
 478  * is the best.
 479  */
 480 static void
 481 bstp_configuration_update(struct bridge_softc *sc)
 482 {
 483         uint64_t        designated_root = sc->sc_bridge_id;
 484         uint64_t        designated_bridge = sc->sc_bridge_id;
 485         uint32_t        designated_cost = 0xFFFFFFFFU;
 486         uint32_t        designated_root_cost = 0xFFFFFFFFU;
 487         uint16_t        designated_port = 65535;
 488         struct bridge_iflist *root_port = NULL;
 489         struct bridge_iflist *bif;
 490
 491         /*
 492          * Resolve information from our peers.  Aged peers will have
 493          * a maxed bif_peer_root and not come under consideration.
 494          */
 495         TAILQ_FOREACH(bif, &sc->sc_iflists[mycpuid], bif_next) {
 496                 if ((bif->bif_flags & IFBIF_STP) == 0)
 497                         continue;
 498                 if (bif->bif_state == BSTP_IFSTATE_DISABLED ||
 499                     bif->bif_state == BSTP_IFSTATE_L1BLOCKING) {
 500                         continue;
 501                 }
 502
 503                 if (bif->bif_peer_root > designated_root)
 504                         continue;
 505                 if (bif->bif_peer_root < designated_root)
 506                         goto set_port;
 507
 508                 /*
 509                  * NOTE: The designated_cost temporary variable already added
 510                  *       in the path code of the related root port.
 511                  */
 512                 if (bif->bif_peer_cost + bif->bif_path_cost > designated_cost)
 513                         continue;
 514                 if (bif->bif_peer_cost + bif->bif_path_cost < designated_cost)
 515                         goto set_port;
 516
 517                 if (bif->bif_peer_bridge > designated_bridge)
 518                         continue;
 519                 if (bif->bif_peer_bridge < designated_bridge)
 520                         goto set_port;
 521
 522                 if (bif->bif_peer_port > designated_port)
 523                         continue;
 524                 if (bif->bif_peer_port < designated_port)
 525                         goto set_port;
 526
 527                 /*
 528                  * Same root, path cost, bridge, and port.  Set the root
 529                  * only if we do not already have it.
 530                  */
 531                 if (root_port)
 532                         continue;
 533
 534                 /*
 535                  * New root port (from peers)
 536                  *
 537                  * NOTE: Temporarily add bif_path_cost into the designated
 538                  *       cost to reduce complexity in the loop, it will be
 539                  *       subtracted out when we are done.
 540                  */
 541 set_port:
 542                 designated_root = bif->bif_peer_root;
 543                 designated_cost = bif->bif_peer_cost + bif->bif_path_cost;
 544                 designated_root_cost = bif->bif_peer_cost;
 545                 designated_bridge = bif->bif_peer_bridge;
 546                 designated_port = bif->bif_peer_port;
 547                 root_port = bif;
 548         }
 549
 550         /*
 551          * root_port will be NULL at the start here if all of our
 552          * peers are aged or are not as good a root as our bridge would
 553          * be.  It can also be NULL due to all related links being
 554          * disabled.
 555          *
 556          * If the root winds up being our bridge scan again against local
 557          * information.  Unconditionally update IFBIF_DESIGNATED.
 558          */
 559         TAILQ_FOREACH(bif, &sc->sc_iflists[mycpuid], bif_next) {
 560                 bif->bif_flags &= ~(IFBIF_DESIGNATED | IFBIF_ROOT);
 561                 if ((bif->bif_flags & IFBIF_STP) == 0)
 562                         continue;
 563                 if (bif->bif_state == BSTP_IFSTATE_DISABLED ||
 564                     bif->bif_state == BSTP_IFSTATE_L1BLOCKING) {
 565                         continue;
 566                 }
 567
 568                 /*
 569                  * Set DESIGNATED for an aged or unknown peer.
 570                  */
 571                 if (bif->bif_peer_bridge == 0xFFFFFFFFFFFFFFFFLLU)
 572                         bif->bif_flags |= IFBIF_DESIGNATED;
 573                 if (designated_root != sc->sc_bridge_id)
 574                         continue;
 575
 576                 /*
 577                  * This is only reached if our bridge is the root bridge,
 578                  * select the root port (IFBIF_DESIGNATED is set at the
 579                  * end).
 580                  *
 581                  * The peer cost will incorporate the peer bridge's best
 582                  * cost to the root bridge (us), which is NOT necessarily
 583                  * our path cost, plus the peer bridge's own path cost.
 584                  * Because of this we must still add in our path cost for
 585                  * further differentiation.  Because the peer's 'best' cost
 586                  * is applied to all of its outgoing messages we should
 587                  * still come to the same conclusion as the peer.
 588                  */
 589                 if (bif->bif_peer_cost + bif->bif_path_cost > designated_cost)
 590                         continue;
 591                 if (bif->bif_peer_cost + bif->bif_path_cost < designated_cost)
 592                         goto set_port2;
 593
 594                 if (bif->bif_port_id > designated_port)
 595                         continue;
 596                 if (bif->bif_port_id < designated_port)
 597                         goto set_port2;
 598                 /* degenerate case (possible peer collision w/our key */
 599
 600                 /*
 601                  * New port.  Since we are the root, the root cost is always
 602                  * 0.  The peer's cu_root_path_cost does not necessarily
 603                  * incorporate our peer path cost, but instead incorporates
 604                  * the lowest path cost to root for the target bridge
 605                  * when multiple links are present between the two bridges.
 606                  * Thus for selection purposes we must still add in our
 607                  * local path cost.
 608                  */
 609 set_port2:
 610                 designated_cost = bif->bif_peer_cost + bif->bif_path_cost;
 611                 designated_root_cost = 0;
 612                 designated_bridge = sc->sc_bridge_id;
 613                 designated_port = bif->bif_port_id;
 614                 root_port = bif;
 615         }
 616
 617         /*
 618          * Update aggregate information.  The selected root port always
 619          * becomes a designated port (along with aged ports).  This can
 620          * either be the port whos peer is closest to the root or it
 621          * can be one of our ports if our bridge is the root.
 622          *
 623          * The root cost we record in sc_designated_root does not include
 624          * bif_path_cost of the root port, since we may transmit this
 625          * out of any port we will add the cost back in later on on
 626          * a per-port basis.
 627          *
 628          * root_port can be NULL here (if all links are disabled)
 629          */
 630         if (root_port) {
 631                 sc->sc_designated_root = designated_root;
 632                 sc->sc_designated_cost = designated_root_cost;
 633                 sc->sc_designated_bridge = designated_bridge;
 634                 sc->sc_designated_port = designated_port;
 635                 root_port->bif_flags |= IFBIF_DESIGNATED | IFBIF_ROOT;
 636         } else {
 637                 sc->sc_designated_root = designated_root;
 638                 sc->sc_designated_cost = designated_cost;
 639                 sc->sc_designated_bridge = designated_bridge;
 640                 sc->sc_designated_port = designated_port;
 641         }
 642         sc->sc_root_port = root_port;
 643 }
 644
 645 /*
 646  * Calculate the desired state for each interface link on our bridge.
 647  *
 648  * The best port will match against sc->sc_root_port (whether we are root
 649  * or whether that port is the closest to the root).  We push this port
 650  * towards a FORWARDING state.
 651  *
 652  * Next come designated ports, either aged ports or ports with no peer info
 653  * (yet), or the peer who is closest to the root. We push this port towards
 654  * a FORWARDING state as well.
 655  *
 656  * Any remaining ports are pushed towards a BLOCKING state.  Both sides of
 657  * the port (us and our peer) should wind up placing the two ends in this
 658  * state or bad things happen.
 659  */
 660 static void
 661 bstp_port_state_selection(struct bridge_softc *sc)
 662 {
 663         struct bridge_iflist *bif, *nbif;
 664
 665         TAILQ_FOREACH_MUTABLE(bif, &sc->sc_iflists[mycpuid], bif_next, nbif) {
 666                 if ((bif->bif_flags & IFBIF_STP) == 0)
 667                         continue;
 668                 if (sc->sc_root_port &&
 669                     bif->bif_info == sc->sc_root_port->bif_info) {
 670                         bif->bif_config_pending = 0;
 671                         bif->bif_topology_change_acknowledge = 0;
 672                         bstp_make_forwarding(sc, bif);
 673                 } else if (bif->bif_flags & IFBIF_DESIGNATED) {
 674                         bstp_timer_stop(&bif->bif_message_age_timer);
 675                         bstp_make_forwarding(sc, bif);
 676                 } else {
 677                         bif->bif_config_pending = 0;
 678                         bif->bif_topology_change_acknowledge = 0;
 679                         bstp_make_blocking(sc, bif);
 680                 }
 681
 682                 if (nbif != NULL && !nbif->bif_onlist) {
 683                         KKASSERT(bif->bif_onlist);
 684                         nbif = TAILQ_NEXT(bif, bif_next);
 685                 }
 686         }
 687 }
 688
 689 /*
 690  * Clear peer info, effectively makes the port looked aged out.
 691  * It becomes a designated go-to port.
 692  */
 693 static void
 694 bstp_clear_peer_info(struct bridge_softc *sc, struct bridge_iflist *bif)
 695 {
 696         bif->bif_peer_root = 0xFFFFFFFFFFFFFFFFLLU;
 697         bif->bif_peer_cost = 0xFFFFFFFFU;
 698         bif->bif_peer_bridge = 0xFFFFFFFFFFFFFFFFLLU;
 699         bif->bif_peer_port = 0xFFFFU;
 700
 701         if (bif->bif_state != BSTP_IFSTATE_DISABLED &&
 702             bif->bif_state != BSTP_IFSTATE_L1BLOCKING) {
 703                 bif->bif_flags |= IFBIF_DESIGNATED;
 704         }
 705 }
 706
 707 static void
 708 bstp_make_forwarding(struct bridge_softc *sc, struct bridge_iflist *bif)
 709 {
 710         if (bif->bif_state == BSTP_IFSTATE_BLOCKING ||
 711             bif->bif_state == BSTP_IFSTATE_BONDED) {
 712                 bstp_set_port_state(bif, BSTP_IFSTATE_LISTENING);
 713                 bstp_timer_start(&bif->bif_forward_delay_timer, 0);
 714         }
 715 }
 716
 717 static void
 718 bstp_make_blocking(struct bridge_softc *sc, struct bridge_iflist *bif)
 719 {
 720         if (bif->bif_state != BSTP_IFSTATE_DISABLED &&
 721             bif->bif_state != BSTP_IFSTATE_BLOCKING &&
 722             bif->bif_state != BSTP_IFSTATE_BONDED &&
 723             bif->bif_state != BSTP_IFSTATE_L1BLOCKING) {
 724                 if ((bif->bif_state == BSTP_IFSTATE_FORWARDING) ||
 725                     (bif->bif_state == BSTP_IFSTATE_LEARNING)) {
 726                         if (bif->bif_change_detection_enabled) {
 727                                 bstp_topology_change_detection(sc);
 728                         }
 729                 }
 730                 bstp_set_port_state(bif, BSTP_IFSTATE_BLOCKING);
 731                 bridge_rtdelete(sc, bif->bif_ifp, IFBF_FLUSHDYN);
 732                 bstp_timer_stop(&bif->bif_forward_delay_timer);
 733                 if (sc->sc_ifp->if_flags & IFF_LINK2)
 734                         bstp_adjust_bonded_states(sc, bif);
 735         }
 736 }
 737
 738 static void
 739 bstp_make_l1blocking(struct bridge_softc *sc, struct bridge_iflist *bif)
 740 {
 741         int was_forwarding = (bif->bif_state == BSTP_IFSTATE_FORWARDING);
 742
 743         switch(bif->bif_state) {
 744         case BSTP_IFSTATE_LISTENING:
 745         case BSTP_IFSTATE_LEARNING:
 746         case BSTP_IFSTATE_FORWARDING:
 747         case BSTP_IFSTATE_BLOCKING:
 748         case BSTP_IFSTATE_BONDED:
 749                 bstp_set_port_state(bif, BSTP_IFSTATE_L1BLOCKING);
 750                 bridge_rtdelete(sc, bif->bif_ifp, IFBF_FLUSHDYN);
 751                 bstp_timer_stop(&bif->bif_forward_delay_timer);
 752                 bstp_timer_stop(&bif->bif_link1_timer);
 753                 if (bif->bif_flags & IFBIF_DESIGNATED) {
 754                         bif->bif_flags &= ~IFBIF_DESIGNATED;
 755                         bstp_configuration_update(sc);
 756                         bstp_port_state_selection(sc);
 757                 }
 758                 if (was_forwarding && (sc->sc_ifp->if_flags & IFF_LINK2))
 759                         bstp_adjust_bonded_states(sc, bif);
 760                 break;
 761         default:
 762                 break;
 763         }
 764 }
 765
 766 /*
 767  * Member (bif) changes to or from a FORWARDING state.  All members in the
 768  * same bonding group which are in a BLOCKING or BONDED state must be set
 769  * to either BLOCKING or BONDED based on whether any members in the bonding
 770  * group remain in the FORWARDING state.
 771  *
 772  * Going between the BLOCKING and BONDED states does not require a
 773  * configuration update.
 774  */
 775 static void
 776 bstp_adjust_bonded_states(struct bridge_softc *sc, struct bridge_iflist *obif)
 777 {
 778         struct bridge_iflist *bif;
 779         int state = BSTP_IFSTATE_BLOCKING;
 780
 781         TAILQ_FOREACH(bif, &sc->sc_iflists[mycpuid], bif_next) {
 782                 if ((bif->bif_flags & IFBIF_STP) == 0)
 783                         continue;
 784                 if (bif->bif_state != BSTP_IFSTATE_FORWARDING)
 785                         continue;
 786                 if (memcmp(IF_LLADDR(bif->bif_ifp), IF_LLADDR(obif->bif_ifp),
 787                            ETHER_ADDR_LEN) != 0) {
 788                         continue;
 789                 }
 790                 state = BSTP_IFSTATE_BONDED;
 791                 break;
 792         }
 793         TAILQ_FOREACH(bif, &sc->sc_iflists[mycpuid], bif_next) {
 794                 if ((bif->bif_flags & IFBIF_STP) == 0)
 795                         continue;
 796                 if (bif->bif_state != BSTP_IFSTATE_BLOCKING &&
 797                     bif->bif_state != BSTP_IFSTATE_BONDED) {
 798                         continue;
 799                 }
 800                 if (memcmp(IF_LLADDR(bif->bif_ifp), IF_LLADDR(obif->bif_ifp),
 801                            ETHER_ADDR_LEN) != 0) {
 802                         continue;
 803                 }
 804                 if (bif->bif_bond_weight == 0)
 805                         bif->bif_state = BSTP_IFSTATE_BLOCKING;
 806                 else
 807                         bif->bif_state = state;
 808         }
 809 }
 810
 811 static void
 812 bstp_set_port_state(struct bridge_iflist *bif, uint8_t state)
 813 {
 814         bif->bif_state = state;
 815 }
 816
 817 static void
 818 bstp_topology_change_detection(struct bridge_softc *sc)
 819 {
 820         if (bstp_root_bridge(sc)) {
 821                 sc->sc_topology_change = 1;
 822                 bstp_timer_start(&sc->sc_topology_change_timer, 0);
 823         } else if (!sc->sc_topology_change_detected) {
 824                 bstp_transmit_tcn(sc);
 825                 bstp_timer_start(&sc->sc_tcn_timer, 0);
 826         }
 827         sc->sc_topology_change_detected = 1;
 828 }
 829
 830 static void
 831 bstp_topology_change_acknowledged(struct bridge_softc *sc)
 832 {
 833         sc->sc_topology_change_detected = 0;
 834         bstp_timer_stop(&sc->sc_tcn_timer);
 835 }
 836
 837 static void
 838 bstp_acknowledge_topology_change(struct bridge_softc *sc,
 839                                  struct bridge_iflist *bif)
 840 {
 841         bif->bif_topology_change_acknowledge = 1;
 842         bstp_transmit_config(sc, bif);
 843 }
 844
 845 void
 846 bstp_input(struct bridge_softc *sc, struct bridge_iflist *bif, struct mbuf *m)
 847 {
 848         struct ether_header *eh;
 849         struct bstp_tbpdu tpdu;
 850         struct bstp_cbpdu cpdu;
 851         struct bstp_config_unit cu;
 852         struct bstp_tcn_unit tu;
 853         uint16_t len;
 854
 855         if ((bif->bif_flags & IFBIF_STP) == 0)
 856                 goto out;
 857
 858         /*
 859          * The L1BLOCKING (ping pong failover) test needs to reset the
 860          * timer if LINK1 is active.
 861          */
 862         if (bif->bif_state == BSTP_IFSTATE_L1BLOCKING) {
 863                 bstp_set_port_state(bif, BSTP_IFSTATE_BLOCKING);
 864                 if (sc->sc_ifp->if_flags & IFF_LINK1)
 865                         bstp_timer_start(&bif->bif_link1_timer, 0);
 866                 bstp_make_forwarding(sc, bif);
 867         } else if (sc->sc_ifp->if_flags & IFF_LINK1) {
 868                 bstp_timer_start(&bif->bif_link1_timer, 0);
 869         }
 870
 871         eh = mtod(m, struct ether_header *);
 872
 873         len = ntohs(eh->ether_type);
 874         if (len < sizeof(tpdu))
 875                 goto out;
 876
 877         m_adj(m, ETHER_HDR_LEN);
 878
 879         if (m->m_pkthdr.len > len)
 880                 m_adj(m, len - m->m_pkthdr.len);
 881         if (m->m_len < sizeof(tpdu) &&
 882             (m = m_pullup(m, sizeof(tpdu))) == NULL)
 883                 goto out;
 884
 885         memcpy(&tpdu, mtod(m, caddr_t), sizeof(tpdu));
 886
 887         if (tpdu.tbu_dsap != LLC_8021D_LSAP ||
 888             tpdu.tbu_ssap != LLC_8021D_LSAP ||
 889             tpdu.tbu_ctl != LLC_UI)
 890                 goto out;
 891         if (tpdu.tbu_protoid != 0 || tpdu.tbu_protover != 0)
 892                 goto out;
 893
 894         switch (tpdu.tbu_bpdutype) {
 895         case BSTP_MSGTYPE_TCN:
 896                 tu.tu_message_type = tpdu.tbu_bpdutype;
 897                 bstp_received_tcn_bpdu(sc, bif, &tu);
 898                 break;
 899         case BSTP_MSGTYPE_CFG:
 900                 if (m->m_len < sizeof(cpdu) &&
 901                     (m = m_pullup(m, sizeof(cpdu))) == NULL)
 902                         goto out;
 903                 memcpy(&cpdu, mtod(m, caddr_t), sizeof(cpdu));
 904
 905                 cu.cu_rootid =
 906                     (((uint64_t)ntohs(cpdu.cbu_rootpri)) << 48) |
 907                     (((uint64_t)cpdu.cbu_rootaddr[0]) << 40) |
 908                     (((uint64_t)cpdu.cbu_rootaddr[1]) << 32) |
 909                     (((uint64_t)cpdu.cbu_rootaddr[2]) << 24) |
 910                     (((uint64_t)cpdu.cbu_rootaddr[3]) << 16) |
 911                     (((uint64_t)cpdu.cbu_rootaddr[4]) << 8) |
 912                     (((uint64_t)cpdu.cbu_rootaddr[5]) << 0);
 913
 914                 cu.cu_bridge_id =
 915                     (((uint64_t)ntohs(cpdu.cbu_bridgepri)) << 48) |
 916                     (((uint64_t)cpdu.cbu_bridgeaddr[0]) << 40) |
 917                     (((uint64_t)cpdu.cbu_bridgeaddr[1]) << 32) |
 918                     (((uint64_t)cpdu.cbu_bridgeaddr[2]) << 24) |
 919                     (((uint64_t)cpdu.cbu_bridgeaddr[3]) << 16) |
 920                     (((uint64_t)cpdu.cbu_bridgeaddr[4]) << 8) |
 921                     (((uint64_t)cpdu.cbu_bridgeaddr[5]) << 0);
 922
 923                 cu.cu_root_path_cost = ntohl(cpdu.cbu_rootpathcost);
 924                 cu.cu_message_age = ntohs(cpdu.cbu_messageage);
 925                 cu.cu_max_age = ntohs(cpdu.cbu_maxage);
 926                 cu.cu_hello_time = ntohs(cpdu.cbu_hellotime);
 927                 cu.cu_forward_delay = ntohs(cpdu.cbu_forwarddelay);
 928                 cu.cu_port_id = ntohs(cpdu.cbu_portid);
 929                 cu.cu_message_type = cpdu.cbu_bpdutype;
 930                 cu.cu_topology_change_acknowledgment =
 931                     (cpdu.cbu_flags & BSTP_FLAG_TCA) ? 1 : 0;
 932                 cu.cu_topology_change =
 933                     (cpdu.cbu_flags & BSTP_FLAG_TC) ? 1 : 0;
 934                 bstp_received_config_bpdu(sc, bif, &cu);
 935                 break;
 936         default:
 937                 goto out;
 938         }
 939 out:
 940         if (m)
 941                 m_freem(m);
 942 }
 943
 944 static void
 945 bstp_received_config_bpdu(struct bridge_softc *sc, struct bridge_iflist *bif,
 946                           struct bstp_config_unit *cu)
 947 {
 948         int iamroot;
 949
 950         iamroot = bstp_root_bridge(sc);
 951
 952         if (bif->bif_state != BSTP_IFSTATE_DISABLED) {
 953                 /*
 954                  * Record information from peer.  The peer_cost field
 955                  * does not include the local bif->bif_path_cost, it will
 956                  * be added in as needed (since it can be modified manually
 957                  * this way we don't have to worry about fixups).
 958                  */
 959                 bif->bif_peer_root = cu->cu_rootid;
 960                 bif->bif_peer_cost = cu->cu_root_path_cost;
 961                 bif->bif_peer_bridge = cu->cu_bridge_id;
 962                 bif->bif_peer_port = cu->cu_port_id;
 963
 964                 if (bstp_supersedes_port_info(sc, bif)) {
 965                         bstp_record_config_information(sc, bif, cu);
 966                         bstp_configuration_update(sc);
 967                         bstp_port_state_selection(sc);
 968
 969                         /*
 970                          * If our bridge loses its root status (?)
 971                          *
 972                          * Hello's (unsolicited CFG packets) are generated
 973                          * every hello period of LINK1 is set, otherwise
 974                          * we are no longer the root bridge and must stop
 975                          * generating unsolicited CFG packets.
 976                          */
 977                         if (iamroot && bstp_root_bridge(sc) == 0) {
 978                                 if ((sc->sc_ifp->if_flags & IFF_LINK1) == 0)
 979                                         bstp_timer_stop(&sc->sc_hello_timer);
 980
 981                                 if (sc->sc_topology_change_detected) {
 982                                         bstp_timer_stop(
 983                                             &sc->sc_topology_change_timer);
 984                                         bstp_transmit_tcn(sc);
 985                                         bstp_timer_start(&sc->sc_tcn_timer, 0);
 986                                 }
 987                         }
 988
 989                         if (sc->sc_root_port &&
 990                             bif->bif_info == sc->sc_root_port->bif_info) {
 991                                 bstp_record_config_timeout_values(sc, cu);
 992                                 bstp_config_bpdu_generation(sc);
 993
 994                                 if (cu->cu_topology_change_acknowledgment)
 995                                         bstp_topology_change_acknowledged(sc);
 996                         }
 997                 } else if (bif->bif_flags & IFBIF_DESIGNATED) {
 998                         /*
 999                          * Update designated ports (aged out peers or
1000                          * the port closest to the root) at a faster pace.
1001                          *
1002                          * Clear our designated flag if we aren't marked
1003                          * as the root port.
1004                          */
1005                         bstp_transmit_config(sc, bif);
1006                         if ((bif->bif_flags & IFBIF_ROOT) == 0) {
1007                                 bif->bif_flags &= ~IFBIF_DESIGNATED;
1008                                 bstp_configuration_update(sc);
1009                                 bstp_port_state_selection(sc);
1010                         }
1011                 }
1012         }
1013 }
1014
1015 static void
1016 bstp_received_tcn_bpdu(struct bridge_softc *sc, struct bridge_iflist *bif,
1017                        struct bstp_tcn_unit *tcn)
1018 {
1019         if (bif->bif_state != BSTP_IFSTATE_DISABLED &&
1020             (bif->bif_flags & IFBIF_DESIGNATED)) {
1021                 bstp_topology_change_detection(sc);
1022                 bstp_acknowledge_topology_change(sc, bif);
1023         }
1024 }
1025
1026 /*
1027  * link1 forces continuous hello's (the bridge interface must be cycled
1028  * to start them up), so keep the timer hot if that is the case, otherwise
1029  * only send HELLO's if we are the root.
1030  */
1031 static void
1032 bstp_hello_timer_expiry(struct bridge_softc *sc)
1033 {
1034         bstp_config_bpdu_generation(sc);
1035
1036         if ((sc->sc_ifp->if_flags & IFF_LINK1) || bstp_root_bridge(sc))
1037                 bstp_timer_start(&sc->sc_hello_timer, 0);
1038 }
1039
1040 static void
1041 bstp_message_age_timer_expiry(struct bridge_softc *sc,
1042                               struct bridge_iflist *bif)
1043 {
1044         int iamroot;
1045
1046         iamroot = bstp_root_bridge(sc);
1047         bstp_clear_peer_info(sc, bif);
1048         bstp_configuration_update(sc);
1049         bstp_port_state_selection(sc);
1050
1051         /*
1052          * If we've become the root and were not the root before
1053          * we have some cleanup to do.  This also occurs if we
1054          * wind up being completely isolated.
1055          */
1056         if (iamroot == 0 && bstp_root_bridge(sc)) {
1057                 sc->sc_max_age = sc->sc_bridge_max_age;
1058                 sc->sc_hello_time = sc->sc_bridge_hello_time;
1059                 sc->sc_forward_delay = sc->sc_bridge_forward_delay;
1060
1061                 bstp_topology_change_detection(sc);
1062                 bstp_timer_stop(&sc->sc_tcn_timer);
1063                 bstp_config_bpdu_generation(sc);
1064                 bstp_timer_start(&sc->sc_hello_timer, 0);
1065         }
1066 }
1067
1068 static void
1069 bstp_forward_delay_timer_expiry(struct bridge_softc *sc,
1070                                 struct bridge_iflist *bif)
1071 {
1072         if (bif->bif_state == BSTP_IFSTATE_LISTENING) {
1073                 bstp_set_port_state(bif, BSTP_IFSTATE_LEARNING);
1074                 bstp_timer_start(&bif->bif_forward_delay_timer, 0);
1075         } else if (bif->bif_state == BSTP_IFSTATE_LEARNING) {
1076                 bstp_set_port_state(bif, BSTP_IFSTATE_FORWARDING);
1077                 if (sc->sc_designated_bridge == sc->sc_bridge_id &&
1078                     bif->bif_change_detection_enabled) {
1079                         bstp_topology_change_detection(sc);
1080                 }
1081                 bstp_configuration_update(sc);
1082                 bstp_port_state_selection(sc);
1083                 if (sc->sc_ifp->if_flags & IFF_LINK2)
1084                         bstp_adjust_bonded_states(sc, bif);
1085         }
1086 }
1087
1088 static void
1089 bstp_tcn_timer_expiry(struct bridge_softc *sc)
1090 {
1091         bstp_transmit_tcn(sc);
1092         bstp_timer_start(&sc->sc_tcn_timer, 0);
1093 }
1094
1095 static void
1096 bstp_topology_change_timer_expiry(struct bridge_softc *sc)
1097 {
1098         sc->sc_topology_change_detected = 0;
1099         sc->sc_topology_change = 0;
1100 }
1101
1102 static void
1103 bstp_hold_timer_expiry(struct bridge_softc *sc, struct bridge_iflist *bif)
1104 {
1105         if (bif->bif_config_pending)
1106                 bstp_transmit_config(sc, bif);
1107 }
1108
1109 /*
1110  * If no traffic received directly on this port for the specified
1111  * period with link1 set we go into a special blocking mode to
1112  * fail-over traffic to another port.
1113  */
1114 static void
1115 bstp_link1_timer_expiry(struct bridge_softc *sc, struct bridge_iflist *bif)
1116 {
1117         if (sc->sc_ifp->if_flags & IFF_LINK1)
1118                 bstp_make_l1blocking(sc, bif);
1119 }
1120
1121 static int
1122 bstp_addr_cmp(const uint8_t *a, const uint8_t *b)
1123 {
1124         int i, d;
1125
1126         for (i = 0, d = 0; i < ETHER_ADDR_LEN && d == 0; i++) {
1127                 d = ((int)a[i]) - ((int)b[i]);
1128         }
1129
1130         return (d);
1131 }
1132
1133 void
1134 bstp_initialization(struct bridge_softc *sc)
1135 {
1136         struct bridge_iflist *bif, *mif, *nbif;
1137         u_char *e_addr;
1138
1139         KKASSERT(&curthread->td_msgport == BRIDGE_CFGPORT);
1140
1141         /*
1142          * Figure out our bridge ID, use the lowest-valued MAC.
1143          * Include the bridge's own random MAC in the calculation.
1144          */
1145         mif = NULL;
1146
1147         TAILQ_FOREACH(bif, &sc->sc_iflists[mycpuid], bif_next) {
1148                 if ((bif->bif_flags & IFBIF_STP) == 0)
1149                         continue;
1150                 if (bif->bif_ifp->if_type != IFT_ETHER)
1151                         continue;
1152                 if (mif == NULL) {
1153                         mif = bif;
1154                         continue;
1155                 }
1156
1157                 bif->bif_port_id = (bif->bif_priority << 8) |
1158                                    (bif->bif_ifp->if_index & 0xff);
1159                 if (bstp_addr_cmp(IF_LLADDR(bif->bif_ifp),
1160                                   IF_LLADDR(mif->bif_ifp)) < 0) {
1161                         mif = bif;
1162                         continue;
1163                 }
1164         }
1165         if (mif == NULL) {
1166                 bstp_stop(sc);
1167                 return;
1168         }
1169
1170         if (bstp_addr_cmp(IF_LLADDR(sc->sc_ifp), IF_LLADDR(mif->bif_ifp)) < 0)
1171                 e_addr = IF_LLADDR(sc->sc_ifp);
1172         else
1173                 e_addr = IF_LLADDR(mif->bif_ifp);
1174
1175         sc->sc_bridge_id =
1176             (((uint64_t)sc->sc_bridge_priority) << 48) |
1177             (((uint64_t)e_addr[0]) << 40) |
1178             (((uint64_t)e_addr[1]) << 32) |
1179             (((uint64_t)e_addr[2]) << 24) |
1180             (((uint64_t)e_addr[3]) << 16) |
1181             (((uint64_t)e_addr[4]) << 8) |
1182             (((uint64_t)e_addr[5]));
1183
1184         /*
1185          * Remainder of setup.
1186          */
1187
1188         sc->sc_designated_root = sc->sc_bridge_id;
1189         sc->sc_designated_cost = 0;
1190         sc->sc_root_port = NULL;
1191
1192         sc->sc_max_age = sc->sc_bridge_max_age;
1193         sc->sc_hello_time = sc->sc_bridge_hello_time;
1194         sc->sc_forward_delay = sc->sc_bridge_forward_delay;
1195         sc->sc_topology_change_detected = 0;
1196         sc->sc_topology_change = 0;
1197         bstp_timer_stop(&sc->sc_tcn_timer);
1198         bstp_timer_stop(&sc->sc_topology_change_timer);
1199
1200         if (callout_pending(&sc->sc_bstpcallout) == 0)
1201                 callout_reset(&sc->sc_bstpcallout, hz,
1202                     bstp_tick, sc);
1203
1204         TAILQ_FOREACH_MUTABLE(bif, &sc->sc_iflists[mycpuid], bif_next, nbif) {
1205                 if (sc->sc_ifp->if_flags & IFF_LINK1)
1206                         bstp_timer_start(&bif->bif_link1_timer, 0);
1207                 if (bif->bif_flags & IFBIF_STP)
1208                         bstp_ifupdstatus(sc, bif);
1209                 else
1210                         bstp_disable_port(sc, bif);
1211
1212                 if (nbif != NULL && !nbif->bif_onlist) {
1213                         KKASSERT(bif->bif_onlist);
1214                         nbif = TAILQ_NEXT(bif, bif_next);
1215                 }
1216         }
1217
1218         bstp_port_state_selection(sc);
1219         bstp_config_bpdu_generation(sc);
1220         bstp_timer_start(&sc->sc_hello_timer, 0);
1221 }
1222
1223 void
1224 bstp_stop(struct bridge_softc *sc)
1225 {
1226         struct bridge_iflist *bif;
1227         struct lwkt_msg *lmsg;
1228
1229         KKASSERT(&curthread->td_msgport == BRIDGE_CFGPORT);
1230
1231         TAILQ_FOREACH(bif, &sc->sc_iflists[mycpuid], bif_next) {
1232                 bstp_set_port_state(bif, BSTP_IFSTATE_DISABLED);
1233                 bstp_timer_stop(&bif->bif_hold_timer);
1234                 bstp_timer_stop(&bif->bif_message_age_timer);
1235                 bstp_timer_stop(&bif->bif_forward_delay_timer);
1236                 bstp_timer_stop(&bif->bif_link1_timer);
1237         }
1238
1239         callout_stop(&sc->sc_bstpcallout);
1240
1241         bstp_timer_stop(&sc->sc_topology_change_timer);
1242         bstp_timer_stop(&sc->sc_tcn_timer);
1243         bstp_timer_stop(&sc->sc_hello_timer);
1244
1245         crit_enter();
1246         lmsg = &sc->sc_bstptimemsg.lmsg;
1247         if ((lmsg->ms_flags & MSGF_DONE) == 0) {
1248                 /* Pending to be processed; drop it */
1249                 lwkt_dropmsg(lmsg);
1250         }
1251         crit_exit();
1252 }
1253
1254 /*
1255  * [re]initialize a port.  The port is initialized to a L1BLOCKING state
1256  * or a BLOCKING state.  When link ping/pong is enabled (LINK1) we start
1257  * out in the L1BLOCKING state to prevent flapping from blowing up the
1258  * state of the other ports.
1259  *
1260  * Either way the first config packet received will knock the port into
1261  * the LISTENING state.
1262  */
1263 static void
1264 bstp_initialize_port(struct bridge_softc *sc, struct bridge_iflist *bif)
1265 {
1266         int needs_adjust = (bif->bif_state == BSTP_IFSTATE_FORWARDING ||
1267                             bif->bif_state == BSTP_IFSTATE_BLOCKING ||
1268                             bif->bif_state == BSTP_IFSTATE_BONDED);
1269
1270         if (sc->sc_ifp->if_flags & IFF_LINK1)
1271                 bstp_set_port_state(bif, BSTP_IFSTATE_L1BLOCKING);
1272         else
1273                 bstp_set_port_state(bif, BSTP_IFSTATE_BLOCKING);
1274         bstp_clear_peer_info(sc, bif);
1275         bif->bif_topology_change_acknowledge = 0;
1276         bif->bif_config_pending = 0;
1277         bif->bif_change_detection_enabled = 1;
1278         bstp_timer_stop(&bif->bif_message_age_timer);
1279         bstp_timer_stop(&bif->bif_forward_delay_timer);
1280         bstp_timer_stop(&bif->bif_hold_timer);
1281         bstp_timer_stop(&bif->bif_link1_timer);
1282         if (needs_adjust && (sc->sc_ifp->if_flags & IFF_LINK2))
1283                 bstp_adjust_bonded_states(sc, bif);
1284 }
1285
1286 /*
1287  * When enabling a port that was previously disabled no configuration
1288  * update occurs, otherwise down/up or running/not-running flapping
1289  * (e.g. by openvpn on a TAP interface) will blow up the other ports.
1290  */
1291 static void
1292 bstp_enable_port(struct bridge_softc *sc, struct bridge_iflist *bif)
1293 {
1294         int was_disabled = (bif->bif_state == BSTP_IFSTATE_DISABLED ||
1295                             bif->bif_state == BSTP_IFSTATE_L1BLOCKING);
1296
1297         bstp_initialize_port(sc, bif);
1298         if (sc->sc_ifp->if_flags & IFF_LINK1)
1299                 bstp_timer_start(&bif->bif_link1_timer, 0);
1300         if (was_disabled == 0) {
1301                 bstp_configuration_update(sc);
1302                 bstp_port_state_selection(sc);
1303         }
1304         bstp_adjust_bonded_states(sc, bif);
1305 }
1306
1307 /*
1308  * When disabling a port that was previously in a non-forwarding or bonded
1309  * state no configuration update occurs, otherwise down/up or
1310  * running/not-running flapping (e.g. by openvpn on a TAP interface) will
1311  * blow up the other ports.
1312  */
1313 static void
1314 bstp_disable_port(struct bridge_softc *sc, struct bridge_iflist *bif)
1315 {
1316         int was_forwarding = (bif->bif_state == BSTP_IFSTATE_FORWARDING);
1317         int was_bonded = (bif->bif_state == BSTP_IFSTATE_BONDED);
1318         int iamroot;
1319
1320         iamroot = bstp_root_bridge(sc);
1321
1322         bstp_clear_peer_info(sc, bif);
1323         bstp_set_port_state(bif, BSTP_IFSTATE_DISABLED);
1324         bif->bif_topology_change_acknowledge = 0;
1325         bif->bif_config_pending = 0;
1326         bstp_timer_stop(&bif->bif_message_age_timer);
1327         bstp_timer_stop(&bif->bif_forward_delay_timer);
1328         bstp_timer_stop(&bif->bif_link1_timer);
1329         if (was_forwarding || was_bonded) {
1330                 bstp_configuration_update(sc);
1331                 bstp_port_state_selection(sc);
1332         }
1333         bridge_rtdelete(sc, bif->bif_ifp, IFBF_FLUSHDYN);
1334         if (was_forwarding && (sc->sc_ifp->if_flags & IFF_LINK2))
1335                 bstp_adjust_bonded_states(sc, bif);
1336
1337         if (iamroot == 0 && bstp_root_bridge(sc)) {
1338                 sc->sc_max_age = sc->sc_bridge_max_age;
1339                 sc->sc_hello_time = sc->sc_bridge_hello_time;
1340                 sc->sc_forward_delay = sc->sc_bridge_forward_delay;
1341
1342                 bstp_topology_change_detection(sc);
1343                 bstp_timer_stop(&sc->sc_tcn_timer);
1344                 bstp_config_bpdu_generation(sc);
1345                 bstp_timer_start(&sc->sc_hello_timer, 0);
1346         }
1347 }
1348
1349 void
1350 bstp_linkstate(struct ifnet *ifp, int state)
1351 {
1352         struct bridge_softc *sc;
1353         struct bridge_iflist *bif;
1354
1355         sc = ifp->if_bridge;
1356         ifnet_serialize_all(sc->sc_ifp);
1357
1358         /*
1359          * bstp_ifupdstatus() may block, but it is the last
1360          * operation of the member iface iteration, so we
1361          * don't need to use LIST_FOREACH_MUTABLE()+bif_onlist
1362          * check here.
1363          */
1364         TAILQ_FOREACH(bif, &sc->sc_iflists[mycpuid], bif_next) {
1365                 if ((bif->bif_flags & IFBIF_STP) == 0)
1366                         continue;
1367
1368                 if (bif->bif_ifp == ifp) {
1369                         bstp_ifupdstatus(sc, bif);
1370                         break;
1371                 }
1372         }
1373         ifnet_deserialize_all(sc->sc_ifp);
1374 }
1375
1376 static void
1377 bstp_ifupdstatus(struct bridge_softc *sc, struct bridge_iflist *bif)
1378 {
1379         struct ifnet *ifp = bif->bif_ifp;
1380         struct ifmediareq ifmr;
1381         int error = 0;
1382
1383         bzero((char *)&ifmr, sizeof(ifmr));
1384         ifnet_serialize_all(ifp);
1385         error = (*ifp->if_ioctl)(ifp, SIOCGIFMEDIA, (caddr_t)&ifmr, NULL);
1386         ifnet_deserialize_all(ifp);
1387
1388         if ((error == 0) && (ifp->if_flags & IFF_UP)) {
1389                 if (ifmr.ifm_status & IFM_ACTIVE) {
1390                         if (bif->bif_state == BSTP_IFSTATE_DISABLED)
1391                                 bstp_enable_port(sc, bif);
1392
1393                 } else {
1394                         if (bif->bif_state != BSTP_IFSTATE_DISABLED)
1395                                 bstp_disable_port(sc, bif);
1396                 }
1397                 return;
1398         }
1399
1400         if (bif->bif_state != BSTP_IFSTATE_DISABLED)
1401                 bstp_disable_port(sc, bif);
1402 }
1403
1404 static void
1405 bstp_tick(void *arg)
1406 {
1407         struct bridge_softc *sc = arg;
1408         struct lwkt_msg *lmsg;
1409
1410         KKASSERT(mycpuid == BRIDGE_CFGCPU);
1411
1412         crit_enter();
1413
1414         if (callout_pending(&sc->sc_bstpcallout) ||
1415             !callout_active(&sc->sc_bstpcallout)) {
1416                 crit_exit();
1417                 return;
1418         }
1419         callout_deactivate(&sc->sc_bstpcallout);
1420
1421         lmsg = &sc->sc_bstptimemsg.lmsg;
1422         KKASSERT(lmsg->ms_flags & MSGF_DONE);
1423         lwkt_sendmsg(BRIDGE_CFGPORT, lmsg);
1424
1425         crit_exit();
1426 }
1427
1428 void
1429 bstp_tick_handler(netmsg_t msg)
1430 {
1431         struct bridge_softc *sc = msg->lmsg.u.ms_resultp;
1432         struct bridge_iflist *bif;
1433
1434         KKASSERT(&curthread->td_msgport == BRIDGE_CFGPORT);
1435         crit_enter();
1436         /* Reply ASAP */
1437         lwkt_replymsg(&msg->lmsg, 0);
1438         crit_exit();
1439
1440         ifnet_serialize_all(sc->sc_ifp);
1441
1442         /*
1443          * NOTE:
1444          * We don't need to worry that member iface is ripped
1445          * from the per-cpu list during the blocking operation
1446          * in the loop body, since deletion is serialized by
1447          * BRIDGE_CFGPORT
1448          */
1449
1450         TAILQ_FOREACH(bif, &sc->sc_iflists[mycpuid], bif_next) {
1451                 if ((bif->bif_flags & IFBIF_STP) == 0)
1452                         continue;
1453                 /*
1454                  * XXX This can cause a lag in "link does away"
1455                  * XXX and "spanning tree gets updated".  We need
1456                  * XXX come sort of callback from the link state
1457                  * XXX update code to kick spanning tree.
1458                  * XXX --thorpej@NetBSD.org
1459                  */
1460                 bstp_ifupdstatus(sc, bif);
1461         }
1462
1463         if (bstp_timer_expired(&sc->sc_hello_timer, sc->sc_hello_time))
1464                 bstp_hello_timer_expiry(sc);
1465
1466         if (bstp_timer_expired(&sc->sc_tcn_timer, sc->sc_bridge_hello_time))
1467                 bstp_tcn_timer_expiry(sc);
1468
1469         if (bstp_timer_expired(&sc->sc_topology_change_timer,
1470             sc->sc_topology_change_time))
1471                 bstp_topology_change_timer_expiry(sc);
1472
1473         TAILQ_FOREACH(bif, &sc->sc_iflists[mycpuid], bif_next) {
1474                 if ((bif->bif_flags & IFBIF_STP) == 0)
1475                         continue;
1476                 if (bstp_timer_expired(&bif->bif_message_age_timer,
1477                     sc->sc_max_age))
1478                         bstp_message_age_timer_expiry(sc, bif);
1479         }
1480
1481         TAILQ_FOREACH(bif, &sc->sc_iflists[mycpuid], bif_next) {
1482                 if ((bif->bif_flags & IFBIF_STP) == 0)
1483                         continue;
1484                 if (bstp_timer_expired(&bif->bif_forward_delay_timer,
1485                     sc->sc_forward_delay))
1486                         bstp_forward_delay_timer_expiry(sc, bif);
1487
1488                 if (bstp_timer_expired(&bif->bif_hold_timer,
1489                     sc->sc_hold_time))
1490                         bstp_hold_timer_expiry(sc, bif);
1491
1492                 if (bstp_timer_expired(&bif->bif_link1_timer,
1493                     sc->sc_hello_time * 10))
1494                         bstp_link1_timer_expiry(sc, bif);
1495         }
1496
1497         if (sc->sc_ifp->if_flags & IFF_RUNNING)
1498                 callout_reset(&sc->sc_bstpcallout, hz, bstp_tick, sc);
1499
1500         ifnet_deserialize_all(sc->sc_ifp);
1501 }
1502
1503 static void
1504 bstp_timer_start(struct bridge_timer *t, uint16_t v)
1505 {
1506         t->value = v;
1507         t->active = 1;
1508 }
1509
1510 static void
1511 bstp_timer_stop(struct bridge_timer *t)
1512 {
1513         t->value = 0;
1514         t->active = 0;
1515 }
1516
1517 static int
1518 bstp_timer_expired(struct bridge_timer *t, uint16_t v)
1519 {
1520         if (t->active == 0)
1521                 return (0);
1522         t->value += BSTP_TICK_VAL;
1523         if (t->value >= v) {
1524                 bstp_timer_stop(t);
1525                 return (1);
1526         }
1527         return (0);
1528
1529 }