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_set_port_state(struct bridge_iflist *, uint8_t);
 159 #ifdef notused
 160 static void     bstp_set_bridge_priority(struct bridge_softc *, uint64_t);
 161 static void     bstp_set_port_priority(struct bridge_softc *,
 162                     struct bridge_iflist *, uint16_t);
 163 static void     bstp_set_path_cost(struct bridge_softc *,
 164                     struct bridge_iflist *, uint32_t);
 165 #endif /* notused */
 166 static void     bstp_topology_change_detection(struct bridge_softc *);
 167 static void     bstp_topology_change_acknowledged(struct bridge_softc *);
 168 static void     bstp_acknowledge_topology_change(struct bridge_softc *,
 169                     struct bridge_iflist *);
 170
 171 static void     bstp_tick(void *);
 172 static void     bstp_timer_start(struct bridge_timer *, uint16_t);
 173 static void     bstp_timer_stop(struct bridge_timer *);
 174 static int      bstp_timer_expired(struct bridge_timer *, uint16_t);
 175
 176 static void     bstp_hold_timer_expiry(struct bridge_softc *,
 177                     struct bridge_iflist *);
 178 static void     bstp_message_age_timer_expiry(struct bridge_softc *,
 179                     struct bridge_iflist *);
 180 static void     bstp_forward_delay_timer_expiry(struct bridge_softc *,
 181                     struct bridge_iflist *);
 182 static void     bstp_topology_change_timer_expiry(struct bridge_softc *);
 183 static void     bstp_tcn_timer_expiry(struct bridge_softc *);
 184 static void     bstp_hello_timer_expiry(struct bridge_softc *);
 185 static int      bstp_addr_cmp(const uint8_t *, const uint8_t *);
 186
 187 /*
 188  * When transmitting a config we tack on our path cost to
 189  * our aggregated path-to-root cost.
 190  */
 191 static void
 192 bstp_transmit_config(struct bridge_softc *sc, struct bridge_iflist *bif)
 193 {
 194         if (bif->bif_hold_timer.active) {
 195                 bif->bif_config_pending = 1;
 196                 return;
 197         }
 198
 199         bif->bif_config_bpdu.cu_message_type = BSTP_MSGTYPE_CFG;
 200         bif->bif_config_bpdu.cu_rootid = sc->sc_designated_root;
 201         bif->bif_config_bpdu.cu_root_path_cost = sc->sc_designated_cost +
 202                                                  bif->bif_path_cost;
 203         bif->bif_config_bpdu.cu_bridge_id = sc->sc_bridge_id;
 204         bif->bif_config_bpdu.cu_port_id = bif->bif_port_id;
 205
 206         if (bstp_root_bridge(sc)) {
 207                 bif->bif_config_bpdu.cu_message_age = 0;
 208         } else if (sc->sc_root_port) {
 209                 bif->bif_config_bpdu.cu_message_age =
 210                         sc->sc_root_port->bif_message_age_timer.value +
 211                         BSTP_MESSAGE_AGE_INCR;
 212         } else {
 213                 bif->bif_config_bpdu.cu_message_age = BSTP_MESSAGE_AGE_INCR;
 214         }
 215
 216         bif->bif_config_bpdu.cu_max_age = sc->sc_max_age;
 217         bif->bif_config_bpdu.cu_hello_time = sc->sc_hello_time;
 218         bif->bif_config_bpdu.cu_forward_delay = sc->sc_forward_delay;
 219         bif->bif_config_bpdu.cu_topology_change_acknowledgment
 220             = bif->bif_topology_change_acknowledge;
 221         bif->bif_config_bpdu.cu_topology_change = sc->sc_topology_change;
 222
 223         if (bif->bif_config_bpdu.cu_message_age < sc->sc_max_age ||
 224             (sc->sc_ifp->if_flags & IFF_LINK1)) {
 225                 bif->bif_topology_change_acknowledge = 0;
 226                 bif->bif_config_pending = 0;
 227                 bstp_send_config_bpdu(sc, bif, &bif->bif_config_bpdu);
 228                 bstp_timer_start(&bif->bif_hold_timer, 0);
 229         }
 230 }
 231
 232 static void
 233 bstp_send_config_bpdu(struct bridge_softc *sc, struct bridge_iflist *bif,
 234                       struct bstp_config_unit *cu)
 235 {
 236         struct ifnet *ifp;
 237         struct mbuf *m;
 238         struct ether_header *eh;
 239         struct bstp_cbpdu bpdu;
 240
 241         ifp = bif->bif_ifp;
 242
 243         if ((ifp->if_flags & IFF_RUNNING) == 0)
 244                 return;
 245
 246         MGETHDR(m, MB_DONTWAIT, MT_DATA);
 247         if (m == NULL)
 248                 return;
 249
 250         eh = mtod(m, struct ether_header *);
 251
 252         m->m_pkthdr.rcvif = ifp;
 253         m->m_pkthdr.len = sizeof(*eh) + sizeof(bpdu);
 254         m->m_len = m->m_pkthdr.len;
 255
 256         bpdu.cbu_ssap = bpdu.cbu_dsap = LLC_8021D_LSAP;
 257         bpdu.cbu_ctl = LLC_UI;
 258         bpdu.cbu_protoid = htons(0);
 259         bpdu.cbu_protover = 0;
 260         bpdu.cbu_bpdutype = cu->cu_message_type;
 261         bpdu.cbu_flags = (cu->cu_topology_change ? BSTP_FLAG_TC : 0) |
 262             (cu->cu_topology_change_acknowledgment ? BSTP_FLAG_TCA : 0);
 263
 264         bpdu.cbu_rootpri = htons(cu->cu_rootid >> 48);
 265         bpdu.cbu_rootaddr[0] = cu->cu_rootid >> 40;
 266         bpdu.cbu_rootaddr[1] = cu->cu_rootid >> 32;
 267         bpdu.cbu_rootaddr[2] = cu->cu_rootid >> 24;
 268         bpdu.cbu_rootaddr[3] = cu->cu_rootid >> 16;
 269         bpdu.cbu_rootaddr[4] = cu->cu_rootid >> 8;
 270         bpdu.cbu_rootaddr[5] = cu->cu_rootid >> 0;
 271
 272         bpdu.cbu_rootpathcost = htonl(cu->cu_root_path_cost);
 273
 274         bpdu.cbu_bridgepri = htons(cu->cu_bridge_id >> 48);
 275         bpdu.cbu_bridgeaddr[0] = cu->cu_bridge_id >> 40;
 276         bpdu.cbu_bridgeaddr[1] = cu->cu_bridge_id >> 32;
 277         bpdu.cbu_bridgeaddr[2] = cu->cu_bridge_id >> 24;
 278         bpdu.cbu_bridgeaddr[3] = cu->cu_bridge_id >> 16;
 279         bpdu.cbu_bridgeaddr[4] = cu->cu_bridge_id >> 8;
 280         bpdu.cbu_bridgeaddr[5] = cu->cu_bridge_id >> 0;
 281
 282         bpdu.cbu_portid = htons(cu->cu_port_id);
 283         bpdu.cbu_messageage = htons(cu->cu_message_age);
 284         bpdu.cbu_maxage = htons(cu->cu_max_age);
 285         bpdu.cbu_hellotime = htons(cu->cu_hello_time);
 286         bpdu.cbu_forwarddelay = htons(cu->cu_forward_delay);
 287
 288         /*
 289          * Packets sent from the bridge always use the bridge MAC
 290          * as the source.
 291          */
 292         memcpy(eh->ether_shost, IF_LLADDR(sc->sc_ifp), ETHER_ADDR_LEN);
 293         memcpy(eh->ether_dhost, bstp_etheraddr, ETHER_ADDR_LEN);
 294         eh->ether_type = htons(sizeof(bpdu));
 295
 296         memcpy(mtod(m, caddr_t) + sizeof(*eh), &bpdu, sizeof(bpdu));
 297
 298         bridge_enqueue(ifp, m);
 299 }
 300
 301 static int
 302 bstp_root_bridge(struct bridge_softc *sc)
 303 {
 304         return (sc->sc_designated_root == sc->sc_bridge_id);
 305 }
 306
 307 /*
 308  * Returns TRUE if the recorded information from our peer has a shorter
 309  * graph distance than our current best.
 310  */
 311 int
 312 bstp_supersedes_port_info(struct bridge_softc *sc, struct bridge_iflist *bif)
 313 {
 314         if (bif->bif_peer_root < sc->sc_designated_root)
 315                 return (1);
 316         if (bif->bif_peer_root > sc->sc_designated_root)
 317                 return (0);
 318
 319         /*
 320          * Both bif_peer_cost and sc_designated_cost have NOT added in
 321          * bif->bif_path_cost, so we can optimize it out.
 322          */
 323         if (bif->bif_peer_cost < sc->sc_designated_cost)
 324                 return (1);
 325         if (bif->bif_peer_cost > sc->sc_designated_cost)
 326                 return (0);
 327
 328         if (bif->bif_peer_bridge < sc->sc_designated_bridge)
 329                 return (1);
 330         if (bif->bif_peer_bridge > sc->sc_designated_bridge)
 331                 return (0);
 332
 333         /* bridge_id or bridge+port collision w/peer returns TRUE */
 334         if (bif->bif_peer_bridge != sc->sc_bridge_id)
 335                 return (1);
 336         if (bif->bif_peer_port <= sc->sc_designated_port)
 337                 return (1);
 338         return (0);
 339 }
 340
 341 /*
 342  * The shorter graph distance represented by cu (most of which is also
 343  * already stored in our bif_peer_* fields) becomes the designated info.
 344  *
 345  * NOTE: sc_designated_cost does not include bif_path_cost, it is added
 346  *       in later on a port-by-port basis as needed.
 347  */
 348 static void
 349 bstp_record_config_information(struct bridge_softc *sc,
 350                                struct bridge_iflist *bif,
 351                                struct bstp_config_unit *cu)
 352 {
 353         sc->sc_designated_root = bif->bif_peer_root;
 354         sc->sc_designated_cost = bif->bif_peer_cost;
 355         sc->sc_designated_bridge = bif->bif_peer_bridge;
 356         sc->sc_designated_port = bif->bif_peer_port;
 357         bstp_timer_start(&bif->bif_message_age_timer, cu->cu_message_age);
 358 }
 359
 360 static void
 361 bstp_record_config_timeout_values(struct bridge_softc *sc,
 362                                   struct bstp_config_unit *config)
 363 {
 364         sc->sc_max_age = config->cu_max_age;
 365         sc->sc_hello_time = config->cu_hello_time;
 366         sc->sc_forward_delay = config->cu_forward_delay;
 367         sc->sc_topology_change = config->cu_topology_change;
 368 }
 369
 370 static void
 371 bstp_config_bpdu_generation(struct bridge_softc *sc)
 372 {
 373         struct bridge_iflist *bif, *nbif;
 374
 375         TAILQ_FOREACH_MUTABLE(bif, &sc->sc_iflists[mycpuid], bif_next, nbif) {
 376                 if ((bif->bif_flags & IFBIF_STP) == 0)
 377                         continue;
 378                 if (bif->bif_state != BSTP_IFSTATE_DISABLED &&
 379                     ((sc->sc_ifp->if_flags & IFF_LINK1) ||
 380                      (bif->bif_flags & IFBIF_DESIGNATED))) {
 381                         bstp_transmit_config(sc, bif);
 382                 }
 383
 384                 if (nbif != NULL && !nbif->bif_onlist) {
 385                         KKASSERT(bif->bif_onlist);
 386                         nbif = TAILQ_NEXT(bif, bif_next);
 387                 }
 388         }
 389 }
 390
 391 static void
 392 bstp_transmit_tcn(struct bridge_softc *sc)
 393 {
 394         struct bstp_tbpdu bpdu;
 395         struct ifnet *ifp;
 396         struct ether_header *eh;
 397         struct mbuf *m;
 398
 399         if (sc->sc_root_port == NULL)   /* all iterfaces disabled */
 400                 return;
 401
 402         ifp = sc->sc_root_port->bif_ifp;
 403         if ((ifp->if_flags & IFF_RUNNING) == 0)
 404                 return;
 405
 406         MGETHDR(m, MB_DONTWAIT, MT_DATA);
 407         if (m == NULL)
 408                 return;
 409
 410         m->m_pkthdr.rcvif = ifp;
 411         m->m_pkthdr.len = sizeof(*eh) + sizeof(bpdu);
 412         m->m_len = m->m_pkthdr.len;
 413
 414         eh = mtod(m, struct ether_header *);
 415
 416         /*
 417          * Packets sent from the bridge always use the bridge MAC
 418          * as the source.
 419          */
 420         memcpy(eh->ether_shost, IF_LLADDR(sc->sc_ifp), ETHER_ADDR_LEN);
 421         memcpy(eh->ether_dhost, bstp_etheraddr, ETHER_ADDR_LEN);
 422         eh->ether_type = htons(sizeof(bpdu));
 423
 424         bpdu.tbu_ssap = bpdu.tbu_dsap = LLC_8021D_LSAP;
 425         bpdu.tbu_ctl = LLC_UI;
 426         bpdu.tbu_protoid = 0;
 427         bpdu.tbu_protover = 0;
 428         bpdu.tbu_bpdutype = BSTP_MSGTYPE_TCN;
 429
 430         memcpy(mtod(m, caddr_t) + sizeof(*eh), &bpdu, sizeof(bpdu));
 431
 432         bridge_enqueue(ifp, m);
 433 }
 434
 435 /*
 436  * Recalculate sc->sc_designated* and sc->sc_root_port (if our bridge
 437  * is calculated to be the root bridge).  We do this by initializing
 438  * the designated variables to point at us and then scan our peers.
 439  * Any uninitialized peers will have a max-value root.
 440  *
 441  * Clear IFBIF_DESIGNATED on any ports which no longer match the criteria
 442  * required to be a designated port.  Only aged out ports and the root
 443  * port can be designated.
 444  *
 445  * If we win we do a second scan to determine which port on our bridge
 446  * is the best.
 447  */
 448 static void
 449 bstp_configuration_update(struct bridge_softc *sc)
 450 {
 451         uint64_t        designated_root = sc->sc_bridge_id;
 452         uint64_t        designated_bridge = sc->sc_bridge_id;
 453         uint32_t        designated_cost = 0xFFFFFFFFU;
 454         uint16_t        designated_port = 65535;
 455         struct bridge_iflist *root_port = NULL;
 456         struct bridge_iflist *bif;
 457
 458         /*
 459          * Resolve information from our peers.  Aged peers will have
 460          * a maxed bif_peer_root and not come under consideration.
 461          */
 462         TAILQ_FOREACH(bif, &sc->sc_iflists[mycpuid], bif_next) {
 463                 if ((bif->bif_flags & IFBIF_STP) == 0)
 464                         continue;
 465                 if (bif->bif_state == BSTP_IFSTATE_DISABLED ||
 466                     bif->bif_state == BSTP_IFSTATE_L1BLOCKING) {
 467                         continue;
 468                 }
 469
 470                 if (bif->bif_peer_root > designated_root)
 471                         continue;
 472                 if (bif->bif_peer_root < designated_root)
 473                         goto set_port;
 474
 475                 /*
 476                  * NOTE: The designated_cost temporary variable already added
 477                  *       in the path code of the related root port.
 478                  */
 479                 if (bif->bif_peer_cost + bif->bif_path_cost > designated_cost)
 480                         continue;
 481                 if (bif->bif_peer_cost + bif->bif_path_cost < designated_cost)
 482                         goto set_port;
 483
 484                 if (bif->bif_peer_bridge > designated_bridge)
 485                         continue;
 486                 if (bif->bif_peer_bridge < designated_bridge)
 487                         goto set_port;
 488
 489                 if (bif->bif_peer_port > designated_port)
 490                         continue;
 491                 if (bif->bif_peer_port < designated_port)
 492                         goto set_port;
 493
 494                 /*
 495                  * Same root, path cost, bridge, and port.  Set the root
 496                  * only if we do not already have it.
 497                  */
 498                 if (root_port)
 499                         continue;
 500
 501                 /*
 502                  * New root port (from peers)
 503                  *
 504                  * NOTE: Temporarily add bif_path_cost into the designated
 505                  *       cost to reduce complexity in the loop, it will be
 506                  *       subtracted out when we are done.
 507                  */
 508 set_port:
 509                 designated_root = bif->bif_peer_root;
 510                 designated_cost = bif->bif_peer_cost + bif->bif_path_cost;
 511                 designated_bridge = bif->bif_peer_bridge;
 512                 designated_port = bif->bif_peer_port;
 513                 root_port = bif;
 514         }
 515
 516         /*
 517          * root_port will be NULL at the start here if all of our
 518          * peers are aged or are not as good a root as our bridge would
 519          * be.  It can also be NULL due to all related links being
 520          * disabled.
 521          *
 522          * If the root winds up being our bridge scan again against local
 523          * information.  Unconditionally update IFBIF_DESIGNATED.
 524          */
 525         TAILQ_FOREACH(bif, &sc->sc_iflists[mycpuid], bif_next) {
 526                 bif->bif_flags &= ~(IFBIF_DESIGNATED | IFBIF_ROOT);
 527                 if ((bif->bif_flags & IFBIF_STP) == 0)
 528                         continue;
 529                 if (bif->bif_state == BSTP_IFSTATE_DISABLED ||
 530                     bif->bif_state == BSTP_IFSTATE_L1BLOCKING) {
 531                         continue;
 532                 }
 533
 534                 /*
 535                  * Set DESIGNATED for an aged or unknown peer.
 536                  */
 537                 if (bif->bif_peer_bridge == 0xFFFFFFFFFFFFFFFFLLU)
 538                         bif->bif_flags |= IFBIF_DESIGNATED;
 539                 if (designated_root != sc->sc_bridge_id)
 540                         continue;
 541
 542                 /*
 543                  * This is only reached if our bridge is the root bridge,
 544                  * select the root port (IFBIF_DESIGNATED is set at the
 545                  * end).
 546                  *
 547                  * We do NOT use peer info here.
 548                  */
 549                 if (bif->bif_path_cost > designated_cost)
 550                         continue;
 551                 if (bif->bif_path_cost < designated_cost)
 552                         goto set_port2;
 553
 554                 if (bif->bif_port_id > designated_port)
 555                         continue;
 556                 if (bif->bif_port_id < designated_port)
 557                         goto set_port2;
 558                 /* degenerate case (possible peer collision w/our key */
 559
 560                 /*
 561                  * New port
 562                  */
 563 set_port2:
 564                 designated_cost = bif->bif_path_cost;
 565                 designated_bridge = sc->sc_bridge_id;
 566                 designated_port = bif->bif_port_id;
 567                 root_port = bif;
 568         }
 569
 570         /*
 571          * Update aggregate information.  The selected root port always
 572          * becomes a designated port (along with aged ports).  This can
 573          * either be the port whos peer is closest to the root or it
 574          * can be one of our ports if our bridge is the root.
 575          *
 576          * The root cost we record in sc_designated_root does not include
 577          * bif_path_cost of the root port, since we may transmit this
 578          * out of any port we will add the cost back in later on on
 579          * a per-port basis.
 580          *
 581          * root_port can be NULL here (if all links are disabled)
 582          */
 583         if (root_port) {
 584                 sc->sc_designated_root = designated_root;
 585                 sc->sc_designated_cost = designated_cost -
 586                                          root_port->bif_path_cost;
 587                 sc->sc_designated_bridge = designated_bridge;
 588                 sc->sc_designated_port = designated_port;
 589                 root_port->bif_flags |= IFBIF_DESIGNATED | IFBIF_ROOT;
 590         } else {
 591                 sc->sc_designated_root = designated_root;
 592                 sc->sc_designated_cost = designated_cost;
 593                 sc->sc_designated_bridge = designated_bridge;
 594                 sc->sc_designated_port = designated_port;
 595         }
 596         sc->sc_root_port = root_port;
 597 }
 598
 599 /*
 600  * Calculate the desired state for each interface link on our bridge.
 601  *
 602  * The best port will match against sc->sc_root_port (whether we are root
 603  * or whether that port is the closest to the root).  We push this port
 604  * towards a FORWARDING state.
 605  *
 606  * Next come designated ports, either aged ports or ports with no peer info
 607  * (yet), or the peer who is closest to the root. We push this port towards
 608  * a FORWARDING state as well.
 609  *
 610  * Any remaining ports are pushed towards a BLOCKED state.  Both sides of
 611  * the port (us and our peer) should wind up placing the two ends in this
 612  * state or bad things happen.
 613  */
 614 static void
 615 bstp_port_state_selection(struct bridge_softc *sc)
 616 {
 617         struct bridge_iflist *bif, *nbif;
 618
 619         TAILQ_FOREACH_MUTABLE(bif, &sc->sc_iflists[mycpuid], bif_next, nbif) {
 620                 if ((bif->bif_flags & IFBIF_STP) == 0)
 621                         continue;
 622                 if (sc->sc_root_port &&
 623                     bif->bif_info == sc->sc_root_port->bif_info) {
 624                         bif->bif_config_pending = 0;
 625                         bif->bif_topology_change_acknowledge = 0;
 626                         bstp_make_forwarding(sc, bif);
 627                 } else if (bif->bif_flags & IFBIF_DESIGNATED) {
 628                         bstp_timer_stop(&bif->bif_message_age_timer);
 629                         bstp_make_forwarding(sc, bif);
 630                 } else {
 631                         bif->bif_config_pending = 0;
 632                         bif->bif_topology_change_acknowledge = 0;
 633                         bstp_make_blocking(sc, bif);
 634                 }
 635
 636                 if (nbif != NULL && !nbif->bif_onlist) {
 637                         KKASSERT(bif->bif_onlist);
 638                         nbif = TAILQ_NEXT(bif, bif_next);
 639                 }
 640         }
 641 }
 642
 643 /*
 644  * Clear peer info, effectively makes the port looked aged out.
 645  * It becomes a designated go-to port.
 646  */
 647 static void
 648 bstp_clear_peer_info(struct bridge_softc *sc, struct bridge_iflist *bif)
 649 {
 650         bif->bif_peer_root = 0xFFFFFFFFFFFFFFFFLLU;
 651         bif->bif_peer_cost = 0xFFFFFFFFU;
 652         bif->bif_peer_bridge = 0xFFFFFFFFFFFFFFFFLLU;
 653         bif->bif_peer_port = 0xFFFFU;
 654
 655         if (bif->bif_state != BSTP_IFSTATE_DISABLED &&
 656             bif->bif_state != BSTP_IFSTATE_L1BLOCKING) {
 657                 bif->bif_flags |= IFBIF_DESIGNATED;
 658         }
 659 }
 660
 661 static void
 662 bstp_make_forwarding(struct bridge_softc *sc, struct bridge_iflist *bif)
 663 {
 664         if (bif->bif_state == BSTP_IFSTATE_BLOCKING) {
 665                 bstp_set_port_state(bif, BSTP_IFSTATE_LISTENING);
 666                 bstp_timer_start(&bif->bif_forward_delay_timer, 0);
 667         }
 668 }
 669
 670 static void
 671 bstp_make_blocking(struct bridge_softc *sc, struct bridge_iflist *bif)
 672 {
 673         if (bif->bif_state != BSTP_IFSTATE_DISABLED &&
 674             bif->bif_state != BSTP_IFSTATE_BLOCKING &&
 675             bif->bif_state != BSTP_IFSTATE_L1BLOCKING) {
 676                 if ((bif->bif_state == BSTP_IFSTATE_FORWARDING) ||
 677                     (bif->bif_state == BSTP_IFSTATE_LEARNING)) {
 678                         if (bif->bif_change_detection_enabled) {
 679                                 bstp_topology_change_detection(sc);
 680                         }
 681                 }
 682                 bstp_set_port_state(bif, BSTP_IFSTATE_BLOCKING);
 683                 bridge_rtdelete(sc, bif->bif_ifp, IFBF_FLUSHDYN);
 684                 bstp_timer_stop(&bif->bif_forward_delay_timer);
 685         }
 686 }
 687
 688 static void
 689 bstp_make_l1blocking(struct bridge_softc *sc, struct bridge_iflist *bif)
 690 {
 691         switch(bif->bif_state) {
 692         case BSTP_IFSTATE_LISTENING:
 693         case BSTP_IFSTATE_LEARNING:
 694         case BSTP_IFSTATE_FORWARDING:
 695         case BSTP_IFSTATE_BLOCKING:
 696                 bstp_set_port_state(bif, BSTP_IFSTATE_L1BLOCKING);
 697                 bridge_rtdelete(sc, bif->bif_ifp, IFBF_FLUSHDYN);
 698                 bstp_timer_stop(&bif->bif_forward_delay_timer);
 699                 bstp_timer_stop(&bif->bif_link1_timer);
 700                 if (bif->bif_flags & IFBIF_DESIGNATED) {
 701                         bif->bif_flags &= ~IFBIF_DESIGNATED;
 702                         bstp_configuration_update(sc);
 703                         bstp_port_state_selection(sc);
 704                 }
 705                 break;
 706         default:
 707                 break;
 708         }
 709 }
 710
 711 static void
 712 bstp_set_port_state(struct bridge_iflist *bif, uint8_t state)
 713 {
 714         bif->bif_state = state;
 715 }
 716
 717 static void
 718 bstp_topology_change_detection(struct bridge_softc *sc)
 719 {
 720         if (bstp_root_bridge(sc)) {
 721                 sc->sc_topology_change = 1;
 722                 bstp_timer_start(&sc->sc_topology_change_timer, 0);
 723         } else if (!sc->sc_topology_change_detected) {
 724                 bstp_transmit_tcn(sc);
 725                 bstp_timer_start(&sc->sc_tcn_timer, 0);
 726         }
 727         sc->sc_topology_change_detected = 1;
 728 }
 729
 730 static void
 731 bstp_topology_change_acknowledged(struct bridge_softc *sc)
 732 {
 733         sc->sc_topology_change_detected = 0;
 734         bstp_timer_stop(&sc->sc_tcn_timer);
 735 }
 736
 737 static void
 738 bstp_acknowledge_topology_change(struct bridge_softc *sc,
 739                                  struct bridge_iflist *bif)
 740 {
 741         bif->bif_topology_change_acknowledge = 1;
 742         bstp_transmit_config(sc, bif);
 743 }
 744
 745 void
 746 bstp_input(struct bridge_softc *sc, struct bridge_iflist *bif, struct mbuf *m)
 747 {
 748         struct ether_header *eh;
 749         struct bstp_tbpdu tpdu;
 750         struct bstp_cbpdu cpdu;
 751         struct bstp_config_unit cu;
 752         struct bstp_tcn_unit tu;
 753         uint16_t len;
 754
 755         if ((bif->bif_flags & IFBIF_STP) == 0)
 756                 goto out;
 757
 758         /*
 759          * The L1BLOCKING (ping pong failover) test needs to reset the
 760          * timer if LINK1 is active.
 761          */
 762         if (bif->bif_state == BSTP_IFSTATE_L1BLOCKING) {
 763                 bstp_set_port_state(bif, BSTP_IFSTATE_BLOCKING);
 764                 if (sc->sc_ifp->if_flags & IFF_LINK1)
 765                         bstp_timer_start(&bif->bif_link1_timer, 0);
 766                 bstp_make_forwarding(sc, bif);
 767         } else if (sc->sc_ifp->if_flags & IFF_LINK1) {
 768                 bstp_timer_start(&bif->bif_link1_timer, 0);
 769         }
 770
 771         eh = mtod(m, struct ether_header *);
 772
 773         len = ntohs(eh->ether_type);
 774         if (len < sizeof(tpdu))
 775                 goto out;
 776
 777         m_adj(m, ETHER_HDR_LEN);
 778
 779         if (m->m_pkthdr.len > len)
 780                 m_adj(m, len - m->m_pkthdr.len);
 781         if (m->m_len < sizeof(tpdu) &&
 782             (m = m_pullup(m, sizeof(tpdu))) == NULL)
 783                 goto out;
 784
 785         memcpy(&tpdu, mtod(m, caddr_t), sizeof(tpdu));
 786
 787         if (tpdu.tbu_dsap != LLC_8021D_LSAP ||
 788             tpdu.tbu_ssap != LLC_8021D_LSAP ||
 789             tpdu.tbu_ctl != LLC_UI)
 790                 goto out;
 791         if (tpdu.tbu_protoid != 0 || tpdu.tbu_protover != 0)
 792                 goto out;
 793
 794         switch (tpdu.tbu_bpdutype) {
 795         case BSTP_MSGTYPE_TCN:
 796                 tu.tu_message_type = tpdu.tbu_bpdutype;
 797                 bstp_received_tcn_bpdu(sc, bif, &tu);
 798                 break;
 799         case BSTP_MSGTYPE_CFG:
 800                 if (m->m_len < sizeof(cpdu) &&
 801                     (m = m_pullup(m, sizeof(cpdu))) == NULL)
 802                         goto out;
 803                 memcpy(&cpdu, mtod(m, caddr_t), sizeof(cpdu));
 804
 805                 cu.cu_rootid =
 806                     (((uint64_t)ntohs(cpdu.cbu_rootpri)) << 48) |
 807                     (((uint64_t)cpdu.cbu_rootaddr[0]) << 40) |
 808                     (((uint64_t)cpdu.cbu_rootaddr[1]) << 32) |
 809                     (((uint64_t)cpdu.cbu_rootaddr[2]) << 24) |
 810                     (((uint64_t)cpdu.cbu_rootaddr[3]) << 16) |
 811                     (((uint64_t)cpdu.cbu_rootaddr[4]) << 8) |
 812                     (((uint64_t)cpdu.cbu_rootaddr[5]) << 0);
 813
 814                 cu.cu_bridge_id =
 815                     (((uint64_t)ntohs(cpdu.cbu_bridgepri)) << 48) |
 816                     (((uint64_t)cpdu.cbu_bridgeaddr[0]) << 40) |
 817                     (((uint64_t)cpdu.cbu_bridgeaddr[1]) << 32) |
 818                     (((uint64_t)cpdu.cbu_bridgeaddr[2]) << 24) |
 819                     (((uint64_t)cpdu.cbu_bridgeaddr[3]) << 16) |
 820                     (((uint64_t)cpdu.cbu_bridgeaddr[4]) << 8) |
 821                     (((uint64_t)cpdu.cbu_bridgeaddr[5]) << 0);
 822
 823                 cu.cu_root_path_cost = ntohl(cpdu.cbu_rootpathcost);
 824                 cu.cu_message_age = ntohs(cpdu.cbu_messageage);
 825                 cu.cu_max_age = ntohs(cpdu.cbu_maxage);
 826                 cu.cu_hello_time = ntohs(cpdu.cbu_hellotime);
 827                 cu.cu_forward_delay = ntohs(cpdu.cbu_forwarddelay);
 828                 cu.cu_port_id = ntohs(cpdu.cbu_portid);
 829                 cu.cu_message_type = cpdu.cbu_bpdutype;
 830                 cu.cu_topology_change_acknowledgment =
 831                     (cpdu.cbu_flags & BSTP_FLAG_TCA) ? 1 : 0;
 832                 cu.cu_topology_change =
 833                     (cpdu.cbu_flags & BSTP_FLAG_TC) ? 1 : 0;
 834                 bstp_received_config_bpdu(sc, bif, &cu);
 835                 break;
 836         default:
 837                 goto out;
 838         }
 839 out:
 840         if (m)
 841                 m_freem(m);
 842 }
 843
 844 static void
 845 bstp_received_config_bpdu(struct bridge_softc *sc, struct bridge_iflist *bif,
 846                           struct bstp_config_unit *cu)
 847 {
 848         int iamroot;
 849
 850         iamroot = bstp_root_bridge(sc);
 851
 852         if (bif->bif_state != BSTP_IFSTATE_DISABLED) {
 853                 /*
 854                  * Record information from peer.  The peer_cost field
 855                  * does not include the local bif->bif_path_cost, it will
 856                  * be added in as needed (since it can be modified manually
 857                  * this way we don't have to worry about fixups).
 858                  */
 859                 bif->bif_peer_root = cu->cu_rootid;
 860                 bif->bif_peer_cost = cu->cu_root_path_cost;
 861                 bif->bif_peer_bridge = cu->cu_bridge_id;
 862                 bif->bif_peer_port = cu->cu_port_id;
 863
 864                 if (bstp_supersedes_port_info(sc, bif)) {
 865                         bstp_record_config_information(sc, bif, cu);
 866                         bstp_configuration_update(sc);
 867                         bstp_port_state_selection(sc);
 868
 869                         /*
 870                          * If our bridge loses its root status (?)
 871                          *
 872                          * Hello's (unsolicited CFG packets) are generated
 873                          * every hello period of LINK1 is set, otherwise
 874                          * we are no longer the root bridge and must stop
 875                          * generating unsolicited CFG packets.
 876                          */
 877                         if (iamroot && bstp_root_bridge(sc) == 0) {
 878                                 if ((sc->sc_ifp->if_flags & IFF_LINK1) == 0)
 879                                         bstp_timer_stop(&sc->sc_hello_timer);
 880
 881                                 if (sc->sc_topology_change_detected) {
 882                                         bstp_timer_stop(
 883                                             &sc->sc_topology_change_timer);
 884                                         bstp_transmit_tcn(sc);
 885                                         bstp_timer_start(&sc->sc_tcn_timer, 0);
 886                                 }
 887                         }
 888
 889                         if (sc->sc_root_port &&
 890                             bif->bif_info == sc->sc_root_port->bif_info) {
 891                                 bstp_record_config_timeout_values(sc, cu);
 892                                 bstp_config_bpdu_generation(sc);
 893
 894                                 if (cu->cu_topology_change_acknowledgment)
 895                                         bstp_topology_change_acknowledged(sc);
 896                         }
 897                 } else if (bif->bif_flags & IFBIF_DESIGNATED) {
 898                         /*
 899                          * Update designated ports (aged out peers or
 900                          * the port closest to the root) at a faster pace.
 901                          *
 902                          * Clear our designated flag if we aren't marked
 903                          * as the root port.
 904                          */
 905                         bstp_transmit_config(sc, bif);
 906                         if ((bif->bif_flags & IFBIF_ROOT) == 0) {
 907                                 bif->bif_flags &= ~IFBIF_DESIGNATED;
 908                                 bstp_configuration_update(sc);
 909                                 bstp_port_state_selection(sc);
 910                         }
 911                 }
 912         }
 913 }
 914
 915 static void
 916 bstp_received_tcn_bpdu(struct bridge_softc *sc, struct bridge_iflist *bif,
 917                        struct bstp_tcn_unit *tcn)
 918 {
 919         if (bif->bif_state != BSTP_IFSTATE_DISABLED &&
 920             (bif->bif_flags & IFBIF_DESIGNATED)) {
 921                 bstp_topology_change_detection(sc);
 922                 bstp_acknowledge_topology_change(sc, bif);
 923         }
 924 }
 925
 926 /*
 927  * link1 forces continuous hello's (the bridge interface must be cycled
 928  * to start them up), so keep the timer hot if that is the case, otherwise
 929  * only send HELLO's if we are the root.
 930  */
 931 static void
 932 bstp_hello_timer_expiry(struct bridge_softc *sc)
 933 {
 934         bstp_config_bpdu_generation(sc);
 935
 936         if ((sc->sc_ifp->if_flags & IFF_LINK1) || bstp_root_bridge(sc))
 937                 bstp_timer_start(&sc->sc_hello_timer, 0);
 938 }
 939
 940 static void
 941 bstp_message_age_timer_expiry(struct bridge_softc *sc,
 942                               struct bridge_iflist *bif)
 943 {
 944         int iamroot;
 945
 946         iamroot = bstp_root_bridge(sc);
 947         bstp_clear_peer_info(sc, bif);
 948         bstp_configuration_update(sc);
 949         bstp_port_state_selection(sc);
 950
 951         /*
 952          * If we've become the root and were not the root before
 953          * we have some cleanup to do.  This also occurs if we
 954          * wind up being completely isolated.
 955          */
 956         if (iamroot == 0 && bstp_root_bridge(sc)) {
 957                 sc->sc_max_age = sc->sc_bridge_max_age;
 958                 sc->sc_hello_time = sc->sc_bridge_hello_time;
 959                 sc->sc_forward_delay = sc->sc_bridge_forward_delay;
 960
 961                 bstp_topology_change_detection(sc);
 962                 bstp_timer_stop(&sc->sc_tcn_timer);
 963                 bstp_config_bpdu_generation(sc);
 964                 bstp_timer_start(&sc->sc_hello_timer, 0);
 965         }
 966 }
 967
 968 static void
 969 bstp_forward_delay_timer_expiry(struct bridge_softc *sc,
 970                                 struct bridge_iflist *bif)
 971 {
 972         if (bif->bif_state == BSTP_IFSTATE_LISTENING) {
 973                 bstp_set_port_state(bif, BSTP_IFSTATE_LEARNING);
 974                 bstp_timer_start(&bif->bif_forward_delay_timer, 0);
 975         } else if (bif->bif_state == BSTP_IFSTATE_LEARNING) {
 976                 bstp_set_port_state(bif, BSTP_IFSTATE_FORWARDING);
 977                 if (sc->sc_designated_bridge == sc->sc_bridge_id &&
 978                     bif->bif_change_detection_enabled) {
 979                         bstp_topology_change_detection(sc);
 980                 }
 981         }
 982 }
 983
 984 static void
 985 bstp_tcn_timer_expiry(struct bridge_softc *sc)
 986 {
 987         bstp_transmit_tcn(sc);
 988         bstp_timer_start(&sc->sc_tcn_timer, 0);
 989 }
 990
 991 static void
 992 bstp_topology_change_timer_expiry(struct bridge_softc *sc)
 993 {
 994         sc->sc_topology_change_detected = 0;
 995         sc->sc_topology_change = 0;
 996 }
 997
 998 static void
 999 bstp_hold_timer_expiry(struct bridge_softc *sc, struct bridge_iflist *bif)
1000 {
1001         if (bif->bif_config_pending)
1002                 bstp_transmit_config(sc, bif);
1003 }
1004
1005 /*
1006  * If no traffic received directly on this port for the specified
1007  * period with link1 set we go into a special blocking mode to
1008  * fail-over traffic to another port.
1009  */
1010 static void
1011 bstp_link1_timer_expiry(struct bridge_softc *sc, struct bridge_iflist *bif)
1012 {
1013         if (sc->sc_ifp->if_flags & IFF_LINK1)
1014                 bstp_make_l1blocking(sc, bif);
1015 }
1016
1017 static int
1018 bstp_addr_cmp(const uint8_t *a, const uint8_t *b)
1019 {
1020         int i, d;
1021
1022         for (i = 0, d = 0; i < ETHER_ADDR_LEN && d == 0; i++) {
1023                 d = ((int)a[i]) - ((int)b[i]);
1024         }
1025
1026         return (d);
1027 }
1028
1029 void
1030 bstp_initialization(struct bridge_softc *sc)
1031 {
1032         struct bridge_iflist *bif, *mif, *nbif;
1033         u_char *e_addr;
1034
1035         KKASSERT(&curthread->td_msgport == BRIDGE_CFGPORT);
1036
1037         /*
1038          * Figure out our bridge ID, use the lowest-valued MAC.
1039          * Include the bridge's own random MAC in the calculation.
1040          */
1041         mif = NULL;
1042
1043         TAILQ_FOREACH(bif, &sc->sc_iflists[mycpuid], bif_next) {
1044                 if ((bif->bif_flags & IFBIF_STP) == 0)
1045                         continue;
1046                 if (bif->bif_ifp->if_type != IFT_ETHER)
1047                         continue;
1048                 if (mif == NULL) {
1049                         mif = bif;
1050                         continue;
1051                 }
1052
1053                 bif->bif_port_id = (bif->bif_priority << 8) |
1054                                    (bif->bif_ifp->if_index & 0xff);
1055                 if (bstp_addr_cmp(IF_LLADDR(bif->bif_ifp),
1056                                   IF_LLADDR(mif->bif_ifp)) < 0) {
1057                         mif = bif;
1058                         continue;
1059                 }
1060         }
1061         if (mif == NULL) {
1062                 bstp_stop(sc);
1063                 return;
1064         }
1065
1066         if (bstp_addr_cmp(IF_LLADDR(sc->sc_ifp), IF_LLADDR(mif->bif_ifp)) < 0)
1067                 e_addr = IF_LLADDR(sc->sc_ifp);
1068         else
1069                 e_addr = IF_LLADDR(mif->bif_ifp);
1070
1071         sc->sc_bridge_id =
1072             (((uint64_t)sc->sc_bridge_priority) << 48) |
1073             (((uint64_t)e_addr[0]) << 40) |
1074             (((uint64_t)e_addr[1]) << 32) |
1075             (((uint64_t)e_addr[2]) << 24) |
1076             (((uint64_t)e_addr[3]) << 16) |
1077             (((uint64_t)e_addr[4]) << 8) |
1078             (((uint64_t)e_addr[5]));
1079
1080         /*
1081          * Remainder of setup.
1082          */
1083
1084         sc->sc_designated_root = sc->sc_bridge_id;
1085         sc->sc_designated_cost = 0;
1086         sc->sc_root_port = NULL;
1087
1088         sc->sc_max_age = sc->sc_bridge_max_age;
1089         sc->sc_hello_time = sc->sc_bridge_hello_time;
1090         sc->sc_forward_delay = sc->sc_bridge_forward_delay;
1091         sc->sc_topology_change_detected = 0;
1092         sc->sc_topology_change = 0;
1093         bstp_timer_stop(&sc->sc_tcn_timer);
1094         bstp_timer_stop(&sc->sc_topology_change_timer);
1095
1096         if (callout_pending(&sc->sc_bstpcallout) == 0)
1097                 callout_reset(&sc->sc_bstpcallout, hz,
1098                     bstp_tick, sc);
1099
1100         TAILQ_FOREACH_MUTABLE(bif, &sc->sc_iflists[mycpuid], bif_next, nbif) {
1101                 if (sc->sc_ifp->if_flags & IFF_LINK1)
1102                         bstp_timer_start(&bif->bif_link1_timer, 0);
1103                 if (bif->bif_flags & IFBIF_STP)
1104                         bstp_ifupdstatus(sc, bif);
1105                 else
1106                         bstp_disable_port(sc, bif);
1107
1108                 if (nbif != NULL && !nbif->bif_onlist) {
1109                         KKASSERT(bif->bif_onlist);
1110                         nbif = TAILQ_NEXT(bif, bif_next);
1111                 }
1112         }
1113
1114         bstp_port_state_selection(sc);
1115         bstp_config_bpdu_generation(sc);
1116         bstp_timer_start(&sc->sc_hello_timer, 0);
1117 }
1118
1119 void
1120 bstp_stop(struct bridge_softc *sc)
1121 {
1122         struct bridge_iflist *bif;
1123         struct lwkt_msg *lmsg;
1124
1125         KKASSERT(&curthread->td_msgport == BRIDGE_CFGPORT);
1126
1127         TAILQ_FOREACH(bif, &sc->sc_iflists[mycpuid], bif_next) {
1128                 bstp_set_port_state(bif, BSTP_IFSTATE_DISABLED);
1129                 bstp_timer_stop(&bif->bif_hold_timer);
1130                 bstp_timer_stop(&bif->bif_message_age_timer);
1131                 bstp_timer_stop(&bif->bif_forward_delay_timer);
1132                 bstp_timer_stop(&bif->bif_link1_timer);
1133         }
1134
1135         callout_stop(&sc->sc_bstpcallout);
1136
1137         bstp_timer_stop(&sc->sc_topology_change_timer);
1138         bstp_timer_stop(&sc->sc_tcn_timer);
1139         bstp_timer_stop(&sc->sc_hello_timer);
1140
1141         crit_enter();
1142         lmsg = &sc->sc_bstptimemsg.lmsg;
1143         if ((lmsg->ms_flags & MSGF_DONE) == 0) {
1144                 /* Pending to be processed; drop it */
1145                 lwkt_dropmsg(lmsg);
1146         }
1147         crit_exit();
1148 }
1149
1150 static void
1151 bstp_initialize_port(struct bridge_softc *sc, struct bridge_iflist *bif)
1152 {
1153         bstp_set_port_state(bif, BSTP_IFSTATE_BLOCKING);
1154         bstp_clear_peer_info(sc, bif);
1155         bif->bif_topology_change_acknowledge = 0;
1156         bif->bif_config_pending = 0;
1157         bif->bif_change_detection_enabled = 1;
1158         bstp_timer_stop(&bif->bif_message_age_timer);
1159         bstp_timer_stop(&bif->bif_forward_delay_timer);
1160         bstp_timer_stop(&bif->bif_hold_timer);
1161         bstp_timer_stop(&bif->bif_link1_timer);
1162 }
1163
1164 static void
1165 bstp_enable_port(struct bridge_softc *sc, struct bridge_iflist *bif)
1166 {
1167         bstp_initialize_port(sc, bif);
1168         if (sc->sc_ifp->if_flags & IFF_LINK1)
1169                 bstp_timer_start(&bif->bif_link1_timer, 0);
1170         bstp_port_state_selection(sc);
1171 }
1172
1173 static void
1174 bstp_disable_port(struct bridge_softc *sc, struct bridge_iflist *bif)
1175 {
1176         int iamroot;
1177
1178         iamroot = bstp_root_bridge(sc);
1179
1180         bstp_clear_peer_info(sc, bif);
1181         bstp_set_port_state(bif, BSTP_IFSTATE_DISABLED);
1182         bif->bif_topology_change_acknowledge = 0;
1183         bif->bif_config_pending = 0;
1184         bstp_timer_stop(&bif->bif_message_age_timer);
1185         bstp_timer_stop(&bif->bif_forward_delay_timer);
1186         bstp_timer_stop(&bif->bif_link1_timer);
1187         bstp_configuration_update(sc);
1188         bstp_port_state_selection(sc);
1189         bridge_rtdelete(sc, bif->bif_ifp, IFBF_FLUSHDYN);
1190
1191         if (iamroot == 0 && bstp_root_bridge(sc)) {
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
1196                 bstp_topology_change_detection(sc);
1197                 bstp_timer_stop(&sc->sc_tcn_timer);
1198                 bstp_config_bpdu_generation(sc);
1199                 bstp_timer_start(&sc->sc_hello_timer, 0);
1200         }
1201 }
1202
1203 void
1204 bstp_linkstate(struct ifnet *ifp, int state)
1205 {
1206         struct bridge_softc *sc;
1207         struct bridge_iflist *bif;
1208
1209         sc = ifp->if_bridge;
1210         ifnet_serialize_all(sc->sc_ifp);
1211
1212         /*
1213          * bstp_ifupdstatus() may block, but it is the last
1214          * operation of the member iface iteration, so we
1215          * don't need to use LIST_FOREACH_MUTABLE()+bif_onlist
1216          * check here.
1217          */
1218         TAILQ_FOREACH(bif, &sc->sc_iflists[mycpuid], bif_next) {
1219                 if ((bif->bif_flags & IFBIF_STP) == 0)
1220                         continue;
1221
1222                 if (bif->bif_ifp == ifp) {
1223                         bstp_ifupdstatus(sc, bif);
1224                         break;
1225                 }
1226         }
1227         ifnet_deserialize_all(sc->sc_ifp);
1228 }
1229
1230 static void
1231 bstp_ifupdstatus(struct bridge_softc *sc, struct bridge_iflist *bif)
1232 {
1233         struct ifnet *ifp = bif->bif_ifp;
1234         struct ifmediareq ifmr;
1235         int error = 0;
1236
1237         bzero((char *)&ifmr, sizeof(ifmr));
1238         ifnet_serialize_all(ifp);
1239         error = (*ifp->if_ioctl)(ifp, SIOCGIFMEDIA, (caddr_t)&ifmr, NULL);
1240         ifnet_deserialize_all(ifp);
1241
1242         if ((error == 0) && (ifp->if_flags & IFF_UP)) {
1243                 if (ifmr.ifm_status & IFM_ACTIVE) {
1244                         if (bif->bif_state == BSTP_IFSTATE_DISABLED)
1245                                 bstp_enable_port(sc, bif);
1246
1247                 } else {
1248                         if (bif->bif_state != BSTP_IFSTATE_DISABLED)
1249                                 bstp_disable_port(sc, bif);
1250                 }
1251                 return;
1252         }
1253
1254         if (bif->bif_state != BSTP_IFSTATE_DISABLED)
1255                 bstp_disable_port(sc, bif);
1256 }
1257
1258 static void
1259 bstp_tick(void *arg)
1260 {
1261         struct bridge_softc *sc = arg;
1262         struct lwkt_msg *lmsg;
1263
1264         KKASSERT(mycpuid == BRIDGE_CFGCPU);
1265
1266         crit_enter();
1267
1268         if (callout_pending(&sc->sc_bstpcallout) ||
1269             !callout_active(&sc->sc_bstpcallout)) {
1270                 crit_exit();
1271                 return;
1272         }
1273         callout_deactivate(&sc->sc_bstpcallout);
1274
1275         lmsg = &sc->sc_bstptimemsg.lmsg;
1276         KKASSERT(lmsg->ms_flags & MSGF_DONE);
1277         lwkt_sendmsg(BRIDGE_CFGPORT, lmsg);
1278
1279         crit_exit();
1280 }
1281
1282 void
1283 bstp_tick_handler(netmsg_t msg)
1284 {
1285         struct bridge_softc *sc = msg->lmsg.u.ms_resultp;
1286         struct bridge_iflist *bif;
1287
1288         KKASSERT(&curthread->td_msgport == BRIDGE_CFGPORT);
1289         crit_enter();
1290         /* Reply ASAP */
1291         lwkt_replymsg(&msg->lmsg, 0);
1292         crit_exit();
1293
1294         ifnet_serialize_all(sc->sc_ifp);
1295
1296         /*
1297          * NOTE:
1298          * We don't need to worry that member iface is ripped
1299          * from the per-cpu list during the blocking operation
1300          * in the loop body, since deletion is serialized by
1301          * BRIDGE_CFGPORT
1302          */
1303
1304         TAILQ_FOREACH(bif, &sc->sc_iflists[mycpuid], bif_next) {
1305                 if ((bif->bif_flags & IFBIF_STP) == 0)
1306                         continue;
1307                 /*
1308                  * XXX This can cause a lag in "link does away"
1309                  * XXX and "spanning tree gets updated".  We need
1310                  * XXX come sort of callback from the link state
1311                  * XXX update code to kick spanning tree.
1312                  * XXX --thorpej@NetBSD.org
1313                  */
1314                 bstp_ifupdstatus(sc, bif);
1315         }
1316
1317         if (bstp_timer_expired(&sc->sc_hello_timer, sc->sc_hello_time))
1318                 bstp_hello_timer_expiry(sc);
1319
1320         if (bstp_timer_expired(&sc->sc_tcn_timer, sc->sc_bridge_hello_time))
1321                 bstp_tcn_timer_expiry(sc);
1322
1323         if (bstp_timer_expired(&sc->sc_topology_change_timer,
1324             sc->sc_topology_change_time))
1325                 bstp_topology_change_timer_expiry(sc);
1326
1327         TAILQ_FOREACH(bif, &sc->sc_iflists[mycpuid], bif_next) {
1328                 if ((bif->bif_flags & IFBIF_STP) == 0)
1329                         continue;
1330                 if (bstp_timer_expired(&bif->bif_message_age_timer,
1331                     sc->sc_max_age))
1332                         bstp_message_age_timer_expiry(sc, bif);
1333         }
1334
1335         TAILQ_FOREACH(bif, &sc->sc_iflists[mycpuid], bif_next) {
1336                 if ((bif->bif_flags & IFBIF_STP) == 0)
1337                         continue;
1338                 if (bstp_timer_expired(&bif->bif_forward_delay_timer,
1339                     sc->sc_forward_delay))
1340                         bstp_forward_delay_timer_expiry(sc, bif);
1341
1342                 if (bstp_timer_expired(&bif->bif_hold_timer,
1343                     sc->sc_hold_time))
1344                         bstp_hold_timer_expiry(sc, bif);
1345
1346                 if (bstp_timer_expired(&bif->bif_link1_timer,
1347                     sc->sc_hello_time * 10))
1348                         bstp_link1_timer_expiry(sc, bif);
1349         }
1350
1351         if (sc->sc_ifp->if_flags & IFF_RUNNING)
1352                 callout_reset(&sc->sc_bstpcallout, hz, bstp_tick, sc);
1353
1354         ifnet_deserialize_all(sc->sc_ifp);
1355 }
1356
1357 static void
1358 bstp_timer_start(struct bridge_timer *t, uint16_t v)
1359 {
1360         t->value = v;
1361         t->active = 1;
1362 }
1363
1364 static void
1365 bstp_timer_stop(struct bridge_timer *t)
1366 {
1367         t->value = 0;
1368         t->active = 0;
1369 }
1370
1371 static int
1372 bstp_timer_expired(struct bridge_timer *t, uint16_t v)
1373 {
1374         if (t->active == 0)
1375                 return (0);
1376         t->value += BSTP_TICK_VAL;
1377         if (t->value >= v) {
1378                 bstp_timer_stop(t);
1379                 return (1);
1380         }
1381         return (0);
1382
1383 }