sys/net/bridgestp.c

   1 /*      $NetBSD: bridgestp.c,v 1.5 2003/11/28 08:56:48 keihan Exp $     */
   2
   3 /*
   4  * Copyright (c) 2000 Jason L. Wright (jason@thought.net)
   5  * Copyright (c) 2006 Andrew Thompson (thompsa@FreeBSD.org)
   6  * All rights reserved.
   7  *
   8  * Redistribution and use in source and binary forms, with or without
   9  * modification, are permitted provided that the following conditions
  10  * are met:
  11  * 1. Redistributions of source code must retain the above copyright
  12  *    notice, this list of conditions and the following disclaimer.
  13  * 2. Redistributions in binary form must reproduce the above copyright
  14  *    notice, this list of conditions and the following disclaimer in the
  15  *    documentation and/or other materials provided with the distribution.
  16  *
  17  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  18  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
  19  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  20  * DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT,
  21  * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
  22  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
  23  * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  24  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
  25  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
  26  * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  27  * POSSIBILITY OF SUCH DAMAGE.
  28  *
  29  * OpenBSD: bridgestp.c,v 1.5 2001/03/22 03:48:29 jason Exp
  30  */
  31
  32 /*
  33  * Implementation of the spanning tree protocol as defined in
  34  * ISO/IEC 802.1D-2004, June 9, 2004.
  35  */
  36
  37 #include <sys/cdefs.h>
  38 __FBSDID("$FreeBSD$");
  39
  40 #include <sys/param.h>
  41 #include <sys/systm.h>
  42 #include <sys/mbuf.h>
  43 #include <sys/socket.h>
  44 #include <sys/sockio.h>
  45 #include <sys/kernel.h>
  46 #include <sys/callout.h>
  47 #include <sys/module.h>
  48 #include <sys/proc.h>
  49 #include <sys/lock.h>
  50 #include <sys/mutex.h>
  51 #include <sys/taskqueue.h>
  52
  53 #include <net/if.h>
  54 #include <net/if_dl.h>
  55 #include <net/if_types.h>
  56 #include <net/if_llc.h>
  57 #include <net/if_media.h>
  58
  59 #include <netinet/in.h>
  60 #include <netinet/in_systm.h>
  61 #include <netinet/in_var.h>
  62 #include <netinet/if_ether.h>
  63 #include <net/bridgestp.h>
  64
  65 #ifdef  BRIDGESTP_DEBUG
  66 #define DPRINTF(fmt, arg...)    printf("bstp: " fmt, ##arg)
  67 #else
  68 #define DPRINTF(fmt, arg...)
  69 #endif
  70
  71 #define PV2ADDR(pv, eaddr)      do {            \
  72         eaddr[0] = pv >> 40;                    \
  73         eaddr[1] = pv >> 32;                    \
  74         eaddr[2] = pv >> 24;                    \
  75         eaddr[3] = pv >> 16;                    \
  76         eaddr[4] = pv >> 8;                     \
  77         eaddr[5] = pv >> 0;                     \
  78 } while (0)
  79
  80 #define INFO_BETTER     1
  81 #define INFO_SAME       0
  82 #define INFO_WORSE      -1
  83
  84 const uint8_t bstp_etheraddr[] = { 0x01, 0x80, 0xc2, 0x00, 0x00, 0x00 };
  85
  86 LIST_HEAD(, bstp_state) bstp_list;
  87 static struct mtx       bstp_list_mtx;
  88
  89 static void     bstp_transmit(struct bstp_state *, struct bstp_port *);
  90 static void     bstp_transmit_bpdu(struct bstp_state *, struct bstp_port *);
  91 static void     bstp_transmit_tcn(struct bstp_state *, struct bstp_port *);
  92 static void     bstp_decode_bpdu(struct bstp_port *, struct bstp_cbpdu *,
  93                     struct bstp_config_unit *);
  94 static void     bstp_send_bpdu(struct bstp_state *, struct bstp_port *,
  95                     struct bstp_cbpdu *);
  96 static void     bstp_enqueue(struct ifnet *, struct mbuf *);
  97 static int      bstp_pdu_flags(struct bstp_port *);
  98 static void     bstp_received_stp(struct bstp_state *, struct bstp_port *,
  99                     struct mbuf **, struct bstp_tbpdu *);
 100 static void     bstp_received_rstp(struct bstp_state *, struct bstp_port *,
 101                     struct mbuf **, struct bstp_tbpdu *);
 102 static void     bstp_received_tcn(struct bstp_state *, struct bstp_port *,
 103                     struct bstp_tcn_unit *);
 104 static void     bstp_received_bpdu(struct bstp_state *, struct bstp_port *,
 105                     struct bstp_config_unit *);
 106 static int      bstp_pdu_rcvtype(struct bstp_port *, struct bstp_config_unit *);
 107 static int      bstp_pdu_bettersame(struct bstp_port *, int);
 108 static int      bstp_info_cmp(struct bstp_pri_vector *,
 109                     struct bstp_pri_vector *);
 110 static int      bstp_info_superior(struct bstp_pri_vector *,
 111                     struct bstp_pri_vector *);
 112 static void     bstp_assign_roles(struct bstp_state *);
 113 static void     bstp_update_roles(struct bstp_state *, struct bstp_port *);
 114 static void     bstp_update_state(struct bstp_state *, struct bstp_port *);
 115 static void     bstp_update_tc(struct bstp_port *);
 116 static void     bstp_update_info(struct bstp_port *);
 117 static void     bstp_set_other_tcprop(struct bstp_port *);
 118 static void     bstp_set_all_reroot(struct bstp_state *);
 119 static void     bstp_set_all_sync(struct bstp_state *);
 120 static void     bstp_set_port_state(struct bstp_port *, int);
 121 static void     bstp_set_port_role(struct bstp_port *, int);
 122 static void     bstp_set_port_proto(struct bstp_port *, int);
 123 static void     bstp_set_port_tc(struct bstp_port *, int);
 124 static void     bstp_set_timer_tc(struct bstp_port *);
 125 static void     bstp_set_timer_msgage(struct bstp_port *);
 126 static int      bstp_rerooted(struct bstp_state *, struct bstp_port *);
 127 static uint32_t bstp_calc_path_cost(struct bstp_port *);
 128 static void     bstp_notify_state(void *, int);
 129 static void     bstp_notify_rtage(void *, int);
 130 static void     bstp_ifupdstatus(struct bstp_state *, struct bstp_port *);
 131 static void     bstp_enable_port(struct bstp_state *, struct bstp_port *);
 132 static void     bstp_disable_port(struct bstp_state *, struct bstp_port *);
 133 static void     bstp_tick(void *);
 134 static void     bstp_timer_start(struct bstp_timer *, uint16_t);
 135 static void     bstp_timer_stop(struct bstp_timer *);
 136 static void     bstp_timer_latch(struct bstp_timer *);
 137 static int      bstp_timer_expired(struct bstp_timer *);
 138 static void     bstp_hello_timer_expiry(struct bstp_state *,
 139                     struct bstp_port *);
 140 static void     bstp_message_age_expiry(struct bstp_state *,
 141                     struct bstp_port *);
 142 static void     bstp_migrate_delay_expiry(struct bstp_state *,
 143                     struct bstp_port *);
 144 static void     bstp_edge_delay_expiry(struct bstp_state *,
 145                     struct bstp_port *);
 146 static int      bstp_addr_cmp(const uint8_t *, const uint8_t *);
 147 static int      bstp_same_bridgeid(uint64_t, uint64_t);
 148 static void     bstp_reinit(struct bstp_state *);
 149
 150 static void
 151 bstp_transmit(struct bstp_state *bs, struct bstp_port *bp)
 152 {
 153         if (bs->bs_running == 0)
 154                 return;
 155
 156         /*
 157          * a PDU can only be sent if we have tx quota left and the
 158          * hello timer is running.
 159          */
 160         if (bp->bp_hello_timer.active == 0) {
 161                 /* Test if it needs to be reset */
 162                 bstp_hello_timer_expiry(bs, bp);
 163                 return;
 164         }
 165         if (bp->bp_txcount > bs->bs_txholdcount)
 166                 /* Ran out of karma */
 167                 return;
 168
 169         if (bp->bp_protover == BSTP_PROTO_RSTP) {
 170                 bstp_transmit_bpdu(bs, bp);
 171                 bp->bp_tc_ack = 0;
 172         } else { /* STP */
 173                 switch (bp->bp_role) {
 174                         case BSTP_ROLE_DESIGNATED:
 175                                 bstp_transmit_bpdu(bs, bp);
 176                                 bp->bp_tc_ack = 0;
 177                                 break;
 178
 179                         case BSTP_ROLE_ROOT:
 180                                 bstp_transmit_tcn(bs, bp);
 181                                 break;
 182                 }
 183         }
 184         bstp_timer_start(&bp->bp_hello_timer, bp->bp_desg_htime);
 185         bp->bp_flags &= ~BSTP_PORT_NEWINFO;
 186 }
 187
 188 static void
 189 bstp_transmit_bpdu(struct bstp_state *bs, struct bstp_port *bp)
 190 {
 191         struct bstp_cbpdu bpdu;
 192
 193         BSTP_LOCK_ASSERT(bs);
 194
 195         bpdu.cbu_rootpri = htons(bp->bp_desg_pv.pv_root_id >> 48);
 196         PV2ADDR(bp->bp_desg_pv.pv_root_id, bpdu.cbu_rootaddr);
 197
 198         bpdu.cbu_rootpathcost = htonl(bp->bp_desg_pv.pv_cost);
 199
 200         bpdu.cbu_bridgepri = htons(bp->bp_desg_pv.pv_dbridge_id >> 48);
 201         PV2ADDR(bp->bp_desg_pv.pv_dbridge_id, bpdu.cbu_bridgeaddr);
 202
 203         bpdu.cbu_portid = htons(bp->bp_port_id);
 204         bpdu.cbu_messageage = htons(bp->bp_desg_msg_age);
 205         bpdu.cbu_maxage = htons(bp->bp_desg_max_age);
 206         bpdu.cbu_hellotime = htons(bp->bp_desg_htime);
 207         bpdu.cbu_forwarddelay = htons(bp->bp_desg_fdelay);
 208
 209         bpdu.cbu_flags = bstp_pdu_flags(bp);
 210
 211         switch (bp->bp_protover) {
 212                 case BSTP_PROTO_STP:
 213                         bpdu.cbu_bpdutype = BSTP_MSGTYPE_CFG;
 214                         break;
 215
 216                 case BSTP_PROTO_RSTP:
 217                         bpdu.cbu_bpdutype = BSTP_MSGTYPE_RSTP;
 218                         break;
 219         }
 220
 221         bstp_send_bpdu(bs, bp, &bpdu);
 222 }
 223
 224 static void
 225 bstp_transmit_tcn(struct bstp_state *bs, struct bstp_port *bp)
 226 {
 227         struct bstp_tbpdu bpdu;
 228         struct ifnet *ifp = bp->bp_ifp;
 229         struct ether_header *eh;
 230         struct mbuf *m;
 231
 232         KASSERT(bp == bs->bs_root_port, ("%s: bad root port\n", __func__));
 233
 234         if ((ifp->if_drv_flags & IFF_DRV_RUNNING) == 0)
 235                 return;
 236
 237         MGETHDR(m, M_DONTWAIT, MT_DATA);
 238         if (m == NULL)
 239                 return;
 240
 241         m->m_pkthdr.rcvif = ifp;
 242         m->m_pkthdr.len = sizeof(*eh) + sizeof(bpdu);
 243         m->m_len = m->m_pkthdr.len;
 244
 245         eh = mtod(m, struct ether_header *);
 246
 247         memcpy(eh->ether_shost, IF_LLADDR(ifp), ETHER_ADDR_LEN);
 248         memcpy(eh->ether_dhost, bstp_etheraddr, ETHER_ADDR_LEN);
 249         eh->ether_type = htons(sizeof(bpdu));
 250
 251         bpdu.tbu_ssap = bpdu.tbu_dsap = LLC_8021D_LSAP;
 252         bpdu.tbu_ctl = LLC_UI;
 253         bpdu.tbu_protoid = 0;
 254         bpdu.tbu_protover = 0;
 255         bpdu.tbu_bpdutype = BSTP_MSGTYPE_TCN;
 256
 257         memcpy(mtod(m, caddr_t) + sizeof(*eh), &bpdu, sizeof(bpdu));
 258
 259         bp->bp_txcount++;
 260         bstp_enqueue(ifp, m);
 261 }
 262
 263 static void
 264 bstp_decode_bpdu(struct bstp_port *bp, struct bstp_cbpdu *cpdu,
 265     struct bstp_config_unit *cu)
 266 {
 267         int flags;
 268
 269         cu->cu_pv.pv_root_id =
 270             (((uint64_t)ntohs(cpdu->cbu_rootpri)) << 48) |
 271             (((uint64_t)cpdu->cbu_rootaddr[0]) << 40) |
 272             (((uint64_t)cpdu->cbu_rootaddr[1]) << 32) |
 273             (((uint64_t)cpdu->cbu_rootaddr[2]) << 24) |
 274             (((uint64_t)cpdu->cbu_rootaddr[3]) << 16) |
 275             (((uint64_t)cpdu->cbu_rootaddr[4]) << 8) |
 276             (((uint64_t)cpdu->cbu_rootaddr[5]) << 0);
 277
 278         cu->cu_pv.pv_dbridge_id =
 279             (((uint64_t)ntohs(cpdu->cbu_bridgepri)) << 48) |
 280             (((uint64_t)cpdu->cbu_bridgeaddr[0]) << 40) |
 281             (((uint64_t)cpdu->cbu_bridgeaddr[1]) << 32) |
 282             (((uint64_t)cpdu->cbu_bridgeaddr[2]) << 24) |
 283             (((uint64_t)cpdu->cbu_bridgeaddr[3]) << 16) |
 284             (((uint64_t)cpdu->cbu_bridgeaddr[4]) << 8) |
 285             (((uint64_t)cpdu->cbu_bridgeaddr[5]) << 0);
 286
 287         cu->cu_pv.pv_cost = ntohl(cpdu->cbu_rootpathcost);
 288         cu->cu_message_age = ntohs(cpdu->cbu_messageage);
 289         cu->cu_max_age = ntohs(cpdu->cbu_maxage);
 290         cu->cu_hello_time = ntohs(cpdu->cbu_hellotime);
 291         cu->cu_forward_delay = ntohs(cpdu->cbu_forwarddelay);
 292         cu->cu_pv.pv_dport_id = ntohs(cpdu->cbu_portid);
 293         cu->cu_pv.pv_port_id = bp->bp_port_id;
 294         cu->cu_message_type = cpdu->cbu_bpdutype;
 295
 296         /* Strip off unused flags in STP mode */
 297         flags = cpdu->cbu_flags;
 298         switch (cpdu->cbu_protover) {
 299                 case BSTP_PROTO_STP:
 300                         flags &= BSTP_PDU_STPMASK;
 301                         /* A STP BPDU explicitly conveys a Designated Port */
 302                         cu->cu_role = BSTP_ROLE_DESIGNATED;
 303                         break;
 304
 305                 case BSTP_PROTO_RSTP:
 306                         flags &= BSTP_PDU_RSTPMASK;
 307                         break;
 308         }
 309
 310         cu->cu_topology_change_ack =
 311                 (flags & BSTP_PDU_F_TCA) ? 1 : 0;
 312         cu->cu_proposal =
 313                 (flags & BSTP_PDU_F_P) ? 1 : 0;
 314         cu->cu_agree =
 315                 (flags & BSTP_PDU_F_A) ? 1 : 0;
 316         cu->cu_learning =
 317                 (flags & BSTP_PDU_F_L) ? 1 : 0;
 318         cu->cu_forwarding =
 319                 (flags & BSTP_PDU_F_F) ? 1 : 0;
 320         cu->cu_topology_change =
 321                 (flags & BSTP_PDU_F_TC) ? 1 : 0;
 322
 323         switch ((flags & BSTP_PDU_PRMASK) >> BSTP_PDU_PRSHIFT) {
 324                 case BSTP_PDU_F_ROOT:
 325                         cu->cu_role = BSTP_ROLE_ROOT;
 326                         break;
 327                 case BSTP_PDU_F_ALT:
 328                         cu->cu_role = BSTP_ROLE_ALTERNATE;
 329                         break;
 330                 case BSTP_PDU_F_DESG:
 331                         cu->cu_role = BSTP_ROLE_DESIGNATED;
 332                         break;
 333         }
 334 }
 335
 336 static void
 337 bstp_send_bpdu(struct bstp_state *bs, struct bstp_port *bp,
 338     struct bstp_cbpdu *bpdu)
 339 {
 340         struct ifnet *ifp;
 341         struct mbuf *m;
 342         struct ether_header *eh;
 343
 344         BSTP_LOCK_ASSERT(bs);
 345
 346         ifp = bp->bp_ifp;
 347
 348         if ((ifp->if_drv_flags & IFF_DRV_RUNNING) == 0)
 349                 return;
 350
 351         MGETHDR(m, M_DONTWAIT, MT_DATA);
 352         if (m == NULL)
 353                 return;
 354
 355         eh = mtod(m, struct ether_header *);
 356
 357         bpdu->cbu_ssap = bpdu->cbu_dsap = LLC_8021D_LSAP;
 358         bpdu->cbu_ctl = LLC_UI;
 359         bpdu->cbu_protoid = htons(BSTP_PROTO_ID);
 360
 361         memcpy(eh->ether_shost, IF_LLADDR(ifp), ETHER_ADDR_LEN);
 362         memcpy(eh->ether_dhost, bstp_etheraddr, ETHER_ADDR_LEN);
 363
 364         switch (bpdu->cbu_bpdutype) {
 365                 case BSTP_MSGTYPE_CFG:
 366                         bpdu->cbu_protover = BSTP_PROTO_STP;
 367                         m->m_pkthdr.len = sizeof(*eh) + BSTP_BPDU_STP_LEN;
 368                         eh->ether_type = htons(BSTP_BPDU_STP_LEN);
 369                         memcpy(mtod(m, caddr_t) + sizeof(*eh), bpdu,
 370                             BSTP_BPDU_STP_LEN);
 371                         break;
 372
 373                 case BSTP_MSGTYPE_RSTP:
 374                         bpdu->cbu_protover = BSTP_PROTO_RSTP;
 375                         bpdu->cbu_versionlen = htons(0);
 376                         m->m_pkthdr.len = sizeof(*eh) + BSTP_BPDU_RSTP_LEN;
 377                         eh->ether_type = htons(BSTP_BPDU_RSTP_LEN);
 378                         memcpy(mtod(m, caddr_t) + sizeof(*eh), bpdu,
 379                             BSTP_BPDU_RSTP_LEN);
 380                         break;
 381
 382                 default:
 383                         panic("not implemented");
 384         }
 385         m->m_pkthdr.rcvif = ifp;
 386         m->m_len = m->m_pkthdr.len;
 387
 388         bp->bp_txcount++;
 389         bstp_enqueue(ifp, m);
 390 }
 391
 392 static void
 393 bstp_enqueue(struct ifnet *dst_ifp, struct mbuf *m)
 394 {
 395         int err = 0;
 396
 397         IFQ_ENQUEUE(&dst_ifp->if_snd, m, err);
 398
 399         if ((dst_ifp->if_drv_flags & IFF_DRV_OACTIVE) == 0)
 400                 (*dst_ifp->if_start)(dst_ifp);
 401 }
 402
 403 static int
 404 bstp_pdu_flags(struct bstp_port *bp)
 405 {
 406         int flags = 0;
 407
 408         if (bp->bp_proposing && bp->bp_state != BSTP_IFSTATE_FORWARDING)
 409                 flags |= BSTP_PDU_F_P;
 410
 411         if (bp->bp_agree)
 412                 flags |= BSTP_PDU_F_A;
 413
 414         if (bp->bp_tc_timer.active)
 415                 flags |= BSTP_PDU_F_TC;
 416
 417         if (bp->bp_tc_ack)
 418                 flags |= BSTP_PDU_F_TCA;
 419
 420         switch (bp->bp_state) {
 421                 case BSTP_IFSTATE_LEARNING:
 422                         flags |= BSTP_PDU_F_L;
 423                         break;
 424
 425                 case BSTP_IFSTATE_FORWARDING:
 426                         flags |= (BSTP_PDU_F_L | BSTP_PDU_F_F);
 427                         break;
 428         }
 429
 430         switch (bp->bp_role) {
 431                 case BSTP_ROLE_ROOT:
 432                         flags |=
 433                                 (BSTP_PDU_F_ROOT << BSTP_PDU_PRSHIFT);
 434                         break;
 435
 436                 case BSTP_ROLE_ALTERNATE:
 437                 case BSTP_ROLE_BACKUP:  /* fall through */
 438                         flags |=
 439                                 (BSTP_PDU_F_ALT << BSTP_PDU_PRSHIFT);
 440                         break;
 441
 442                 case BSTP_ROLE_DESIGNATED:
 443                         flags |=
 444                                 (BSTP_PDU_F_DESG << BSTP_PDU_PRSHIFT);
 445                         break;
 446         }
 447
 448         /* Strip off unused flags in either mode */
 449         switch (bp->bp_protover) {
 450                 case BSTP_PROTO_STP:
 451                         flags &= BSTP_PDU_STPMASK;
 452                         break;
 453                 case BSTP_PROTO_RSTP:
 454                         flags &= BSTP_PDU_RSTPMASK;
 455                         break;
 456         }
 457         return (flags);
 458 }
 459
 460 struct mbuf *
 461 bstp_input(struct bstp_port *bp, struct ifnet *ifp, struct mbuf *m)
 462 {
 463         struct bstp_state *bs = bp->bp_bs;
 464         struct ether_header *eh;
 465         struct bstp_tbpdu tpdu;
 466         uint16_t len;
 467
 468         if (bp->bp_active == 0) {
 469                 m_freem(m);
 470                 return (NULL);
 471         }
 472
 473         BSTP_LOCK(bs);
 474
 475         eh = mtod(m, struct ether_header *);
 476
 477         len = ntohs(eh->ether_type);
 478         if (len < sizeof(tpdu))
 479                 goto out;
 480
 481         m_adj(m, ETHER_HDR_LEN);
 482
 483         if (m->m_pkthdr.len > len)
 484                 m_adj(m, len - m->m_pkthdr.len);
 485         if (m->m_len < sizeof(tpdu) &&
 486             (m = m_pullup(m, sizeof(tpdu))) == NULL)
 487                 goto out;
 488
 489         memcpy(&tpdu, mtod(m, caddr_t), sizeof(tpdu));
 490
 491         /* basic packet checks */
 492         if (tpdu.tbu_dsap != LLC_8021D_LSAP ||
 493             tpdu.tbu_ssap != LLC_8021D_LSAP ||
 494             tpdu.tbu_ctl != LLC_UI)
 495                 goto out;
 496         if (tpdu.tbu_protoid != BSTP_PROTO_ID)
 497                 goto out;
 498
 499         /*
 500          * We can treat later versions of the PDU as the same as the maximum
 501          * version we implement. All additional parameters/flags are ignored.
 502          */
 503         if (tpdu.tbu_protover > BSTP_PROTO_MAX)
 504                 tpdu.tbu_protover = BSTP_PROTO_MAX;
 505
 506         if (tpdu.tbu_protover != bp->bp_protover) {
 507                 /*
 508                  * Wait for the migration delay timer to expire before changing
 509                  * protocol version to avoid flip-flops.
 510                  */
 511                 if (bp->bp_flags & BSTP_PORT_CANMIGRATE)
 512                         bstp_set_port_proto(bp, tpdu.tbu_protover);
 513                 else
 514                         goto out;
 515         }
 516
 517         /* Clear operedge upon receiving a PDU on the port */
 518         bp->bp_operedge = 0;
 519         bstp_timer_start(&bp->bp_edge_delay_timer,
 520             BSTP_DEFAULT_MIGRATE_DELAY);
 521
 522         switch (tpdu.tbu_protover) {
 523                 case BSTP_PROTO_STP:
 524                         bstp_received_stp(bs, bp, &m, &tpdu);
 525                         break;
 526
 527                 case BSTP_PROTO_RSTP:
 528                         bstp_received_rstp(bs, bp, &m, &tpdu);
 529                         break;
 530         }
 531 out:
 532         BSTP_UNLOCK(bs);
 533         if (m)
 534                 m_freem(m);
 535         return (NULL);
 536 }
 537
 538 static void
 539 bstp_received_stp(struct bstp_state *bs, struct bstp_port *bp,
 540     struct mbuf **mp, struct bstp_tbpdu *tpdu)
 541 {
 542         struct bstp_cbpdu cpdu;
 543         struct bstp_config_unit *cu = &bp->bp_msg_cu;
 544         struct bstp_tcn_unit tu;
 545
 546         switch (tpdu->tbu_bpdutype) {
 547         case BSTP_MSGTYPE_TCN:
 548                 tu.tu_message_type = tpdu->tbu_bpdutype;
 549                 bstp_received_tcn(bs, bp, &tu);
 550                 break;
 551         case BSTP_MSGTYPE_CFG:
 552                 if ((*mp)->m_len < BSTP_BPDU_STP_LEN &&
 553                     (*mp = m_pullup(*mp, BSTP_BPDU_STP_LEN)) == NULL)
 554                         return;
 555                 memcpy(&cpdu, mtod(*mp, caddr_t), BSTP_BPDU_STP_LEN);
 556
 557                 bstp_decode_bpdu(bp, &cpdu, cu);
 558                 bstp_received_bpdu(bs, bp, cu);
 559                 break;
 560         }
 561 }
 562
 563 static void
 564 bstp_received_rstp(struct bstp_state *bs, struct bstp_port *bp,
 565     struct mbuf **mp, struct bstp_tbpdu *tpdu)
 566 {
 567         struct bstp_cbpdu cpdu;
 568         struct bstp_config_unit *cu = &bp->bp_msg_cu;
 569
 570         if (tpdu->tbu_bpdutype != BSTP_MSGTYPE_RSTP)
 571                 return;
 572
 573         if ((*mp)->m_len < BSTP_BPDU_RSTP_LEN &&
 574             (*mp = m_pullup(*mp, BSTP_BPDU_RSTP_LEN)) == NULL)
 575                 return;
 576         memcpy(&cpdu, mtod(*mp, caddr_t), BSTP_BPDU_RSTP_LEN);
 577
 578         bstp_decode_bpdu(bp, &cpdu, cu);
 579         bstp_received_bpdu(bs, bp, cu);
 580 }
 581
 582 static void
 583 bstp_received_tcn(struct bstp_state *bs, struct bstp_port *bp,
 584     struct bstp_tcn_unit *tcn)
 585 {
 586         bp->bp_rcvdtcn = 1;
 587         bstp_update_tc(bp);
 588 }
 589
 590 static void
 591 bstp_received_bpdu(struct bstp_state *bs, struct bstp_port *bp,
 592     struct bstp_config_unit *cu)
 593 {
 594         int type;
 595
 596         BSTP_LOCK_ASSERT(bs);
 597
 598         /* We need to have transitioned to INFO_MINE before proceeding */
 599         switch (bp->bp_infois) {
 600                 case BSTP_INFO_DISABLED:
 601                 case BSTP_INFO_AGED:
 602                         return;
 603         }
 604
 605         type = bstp_pdu_rcvtype(bp, cu);
 606
 607         switch (type) {
 608                 case BSTP_PDU_SUPERIOR:
 609                         bs->bs_allsynced = 0;
 610                         bp->bp_agreed = 0;
 611                         bp->bp_proposing = 0;
 612
 613                         if (cu->cu_proposal && cu->cu_forwarding == 0)
 614                                 bp->bp_proposed = 1;
 615                         if (cu->cu_topology_change)
 616                                 bp->bp_rcvdtc = 1;
 617                         if (cu->cu_topology_change_ack)
 618                                 bp->bp_rcvdtca = 1;
 619
 620                         if (bp->bp_agree &&
 621                             !bstp_pdu_bettersame(bp, BSTP_INFO_RECEIVED))
 622                                 bp->bp_agree = 0;
 623
 624                         /* copy the received priority and timers to the port */
 625                         bp->bp_port_pv = cu->cu_pv;
 626                         bp->bp_port_msg_age = cu->cu_message_age;
 627                         bp->bp_port_max_age = cu->cu_max_age;
 628                         bp->bp_port_fdelay = cu->cu_forward_delay;
 629                         bp->bp_port_htime =
 630                                 (cu->cu_hello_time > BSTP_MIN_HELLO_TIME ?
 631                                  cu->cu_hello_time : BSTP_MIN_HELLO_TIME);
 632
 633                         /* set expiry for the new info */
 634                         bstp_set_timer_msgage(bp);
 635
 636                         bp->bp_infois = BSTP_INFO_RECEIVED;
 637                         bstp_assign_roles(bs);
 638                         break;
 639
 640                 case BSTP_PDU_REPEATED:
 641                         if (cu->cu_proposal && cu->cu_forwarding == 0)
 642                                 bp->bp_proposed = 1;
 643                         if (cu->cu_topology_change)
 644                                 bp->bp_rcvdtc = 1;
 645                         if (cu->cu_topology_change_ack)
 646                                 bp->bp_rcvdtca = 1;
 647
 648                         /* rearm the age timer */
 649                         bstp_set_timer_msgage(bp);
 650                         break;
 651
 652                 case BSTP_PDU_INFERIOR:
 653                         if (cu->cu_learning) {
 654                                 bp->bp_agreed = 1;
 655                                 bp->bp_proposing = 0;
 656                         }
 657                         break;
 658
 659                 case BSTP_PDU_INFERIORALT:
 660                         /*
 661                          * only point to point links are allowed fast
 662                          * transitions to forwarding.
 663                          */
 664                         if (cu->cu_agree && bp->bp_ptp_link) {
 665                                 bp->bp_agreed = 1;
 666                                 bp->bp_proposing = 0;
 667                         } else
 668                                 bp->bp_agreed = 0;
 669
 670                         if (cu->cu_topology_change)
 671                                 bp->bp_rcvdtc = 1;
 672                         if (cu->cu_topology_change_ack)
 673                                 bp->bp_rcvdtca = 1;
 674                         break;
 675
 676                 case BSTP_PDU_OTHER:
 677                         return; /* do nothing */
 678         }
 679         /* update the state machines with the new data */
 680         bstp_update_state(bs, bp);
 681 }
 682
 683 static int
 684 bstp_pdu_rcvtype(struct bstp_port *bp, struct bstp_config_unit *cu)
 685 {
 686         int type;
 687
 688         /* default return type */
 689         type = BSTP_PDU_OTHER;
 690
 691         switch (cu->cu_role) {
 692         case BSTP_ROLE_DESIGNATED:
 693                 if (bstp_info_superior(&bp->bp_port_pv, &cu->cu_pv))
 694                         /* bpdu priority is superior */
 695                         type = BSTP_PDU_SUPERIOR;
 696                 else if (bstp_info_cmp(&bp->bp_port_pv, &cu->cu_pv) ==
 697                     INFO_SAME) {
 698                         if (bp->bp_port_msg_age != cu->cu_message_age ||
 699                             bp->bp_port_max_age != cu->cu_max_age ||
 700                             bp->bp_port_fdelay != cu->cu_forward_delay ||
 701                             bp->bp_port_htime != cu->cu_hello_time)
 702                                 /* bpdu priority is equal and timers differ */
 703                                 type = BSTP_PDU_SUPERIOR;
 704                         else
 705                                 /* bpdu is equal */
 706                                 type = BSTP_PDU_REPEATED;
 707                 } else
 708                         /* bpdu priority is worse */
 709                         type = BSTP_PDU_INFERIOR;
 710
 711                 break;
 712
 713         case BSTP_ROLE_ROOT:
 714         case BSTP_ROLE_ALTERNATE:
 715         case BSTP_ROLE_BACKUP:
 716                 if (bstp_info_cmp(&bp->bp_port_pv, &cu->cu_pv) <= INFO_SAME)
 717                         /*
 718                          * not a designated port and priority is the same or
 719                          * worse
 720                          */
 721                         type = BSTP_PDU_INFERIORALT;
 722                 break;
 723         }
 724
 725         return (type);
 726 }
 727
 728 static int
 729 bstp_pdu_bettersame(struct bstp_port *bp, int newinfo)
 730 {
 731         if (newinfo == BSTP_INFO_RECEIVED &&
 732             bp->bp_infois == BSTP_INFO_RECEIVED &&
 733             bstp_info_cmp(&bp->bp_port_pv, &bp->bp_msg_cu.cu_pv) >= INFO_SAME)
 734                 return (1);
 735
 736         if (newinfo == BSTP_INFO_MINE &&
 737             bp->bp_infois == BSTP_INFO_MINE &&
 738             bstp_info_cmp(&bp->bp_port_pv, &bp->bp_desg_pv) >= INFO_SAME)
 739                 return (1);
 740
 741         return (0);
 742 }
 743
 744 static int
 745 bstp_info_cmp(struct bstp_pri_vector *pv,
 746     struct bstp_pri_vector *cpv)
 747 {
 748         if (cpv->pv_root_id < pv->pv_root_id)
 749                 return (INFO_BETTER);
 750         if (cpv->pv_root_id > pv->pv_root_id)
 751                 return (INFO_WORSE);
 752
 753         if (cpv->pv_cost < pv->pv_cost)
 754                 return (INFO_BETTER);
 755         if (cpv->pv_cost > pv->pv_cost)
 756                 return (INFO_WORSE);
 757
 758         if (cpv->pv_dbridge_id < pv->pv_dbridge_id)
 759                 return (INFO_BETTER);
 760         if (cpv->pv_dbridge_id > pv->pv_dbridge_id)
 761                 return (INFO_WORSE);
 762
 763         if (cpv->pv_dport_id < pv->pv_dport_id)
 764                 return (INFO_BETTER);
 765         if (cpv->pv_dport_id > pv->pv_dport_id)
 766                 return (INFO_WORSE);
 767
 768         return (INFO_SAME);
 769 }
 770
 771 /*
 772  * This message priority vector is superior to the port priority vector and
 773  * will replace it if, and only if, the message priority vector is better than
 774  * the port priority vector, or the message has been transmitted from the same
 775  * designated bridge and designated port as the port priority vector.
 776  */
 777 static int
 778 bstp_info_superior(struct bstp_pri_vector *pv,
 779     struct bstp_pri_vector *cpv)
 780 {
 781         if (bstp_info_cmp(pv, cpv) == INFO_BETTER ||
 782             (bstp_same_bridgeid(pv->pv_dbridge_id, cpv->pv_dbridge_id) &&
 783             (cpv->pv_dport_id & 0xfff) == (pv->pv_dport_id & 0xfff)))
 784                 return (1);
 785         return (0);
 786 }
 787
 788 static void
 789 bstp_assign_roles(struct bstp_state *bs)
 790 {
 791         struct bstp_port *bp, *rbp = NULL;
 792         struct bstp_pri_vector pv;
 793
 794         /* default to our priority vector */
 795         bs->bs_root_pv = bs->bs_bridge_pv;
 796         bs->bs_root_msg_age = 0;
 797         bs->bs_root_max_age = bs->bs_bridge_max_age;
 798         bs->bs_root_fdelay = bs->bs_bridge_fdelay;
 799         bs->bs_root_htime = bs->bs_bridge_htime;
 800         bs->bs_root_port = NULL;
 801
 802         /* check if any recieved info supersedes us */
 803         LIST_FOREACH(bp, &bs->bs_bplist, bp_next) {
 804                 if (bp->bp_infois != BSTP_INFO_RECEIVED)
 805                         continue;
 806
 807                 pv = bp->bp_port_pv;
 808                 pv.pv_cost += bp->bp_path_cost;
 809
 810                 /*
 811                  * The root priority vector is the best of the set comprising
 812                  * the bridge priority vector plus all root path priority
 813                  * vectors whose bridge address is not equal to us.
 814                  */
 815                 if (bstp_same_bridgeid(pv.pv_dbridge_id,
 816                     bs->bs_bridge_pv.pv_dbridge_id) == 0 &&
 817                     bstp_info_cmp(&bs->bs_root_pv, &pv) == INFO_BETTER) {
 818                         /* the port vector replaces the root */
 819                         bs->bs_root_pv = pv;
 820                         bs->bs_root_msg_age = bp->bp_port_msg_age +
 821                             BSTP_MESSAGE_AGE_INCR;
 822                         bs->bs_root_max_age = bp->bp_port_max_age;
 823                         bs->bs_root_fdelay = bp->bp_port_fdelay;
 824                         bs->bs_root_htime = bp->bp_port_htime;
 825                         rbp = bp;
 826                 }
 827         }
 828
 829         LIST_FOREACH(bp, &bs->bs_bplist, bp_next) {
 830                 /* calculate the port designated vector */
 831                 bp->bp_desg_pv.pv_root_id = bs->bs_root_pv.pv_root_id;
 832                 bp->bp_desg_pv.pv_cost = bs->bs_root_pv.pv_cost;
 833                 bp->bp_desg_pv.pv_dbridge_id = bs->bs_bridge_pv.pv_dbridge_id;
 834                 bp->bp_desg_pv.pv_dport_id = bp->bp_port_id;
 835                 bp->bp_desg_pv.pv_port_id = bp->bp_port_id;
 836
 837                 /* calculate designated times */
 838                 bp->bp_desg_msg_age = bs->bs_root_msg_age;
 839                 bp->bp_desg_max_age = bs->bs_root_max_age;
 840                 bp->bp_desg_fdelay = bs->bs_root_fdelay;
 841                 bp->bp_desg_htime = bs->bs_bridge_htime;
 842
 843
 844                 switch (bp->bp_infois) {
 845                 case BSTP_INFO_DISABLED:
 846                         bstp_set_port_role(bp, BSTP_ROLE_DISABLED);
 847                         break;
 848
 849                 case BSTP_INFO_AGED:
 850                         bstp_set_port_role(bp, BSTP_ROLE_DESIGNATED);
 851                         bstp_update_info(bp);
 852                         break;
 853
 854                 case BSTP_INFO_MINE:
 855                         bstp_set_port_role(bp, BSTP_ROLE_DESIGNATED);
 856                         /* update the port info if stale */
 857                         if (bstp_info_cmp(&bp->bp_port_pv,
 858                             &bp->bp_desg_pv) != INFO_SAME ||
 859                             (rbp != NULL &&
 860                             (bp->bp_port_msg_age != rbp->bp_port_msg_age ||
 861                             bp->bp_port_max_age != rbp->bp_port_max_age ||
 862                             bp->bp_port_fdelay != rbp->bp_port_fdelay ||
 863                             bp->bp_port_htime != rbp->bp_port_htime)))
 864                                 bstp_update_info(bp);
 865                         break;
 866
 867                 case BSTP_INFO_RECEIVED:
 868                         if (bp == rbp) {
 869                                 /*
 870                                  * root priority is derived from this
 871                                  * port, make it the root port.
 872                                  */
 873                                 bstp_set_port_role(bp, BSTP_ROLE_ROOT);
 874                                 bs->bs_root_port = bp;
 875                         } else if (bstp_info_cmp(&bp->bp_port_pv,
 876                                     &bp->bp_desg_pv) == INFO_BETTER) {
 877                                 /*
 878                                  * the port priority is lower than the root
 879                                  * port.
 880                                  */
 881                                 bstp_set_port_role(bp, BSTP_ROLE_DESIGNATED);
 882                                 bstp_update_info(bp);
 883                         } else {
 884                                 if (bstp_same_bridgeid(
 885                                     bp->bp_port_pv.pv_dbridge_id,
 886                                     bs->bs_bridge_pv.pv_dbridge_id)) {
 887                                         /*
 888                                          * the designated bridge refers to
 889                                          * another port on this bridge.
 890                                          */
 891                                         bstp_set_port_role(bp,
 892                                             BSTP_ROLE_BACKUP);
 893                                 } else {
 894                                         /*
 895                                          * the port is an inferior path to the
 896                                          * root bridge.
 897                                          */
 898                                         bstp_set_port_role(bp,
 899                                             BSTP_ROLE_ALTERNATE);
 900                                 }
 901                         }
 902                         break;
 903                 }
 904         }
 905 }
 906
 907 static void
 908 bstp_update_state(struct bstp_state *bs, struct bstp_port *bp)
 909 {
 910         struct bstp_port *bp2;
 911         int synced;
 912
 913         BSTP_LOCK_ASSERT(bs);
 914
 915         /* check if all the ports have syncronised again */
 916         if (!bs->bs_allsynced) {
 917                 synced = 1;
 918                 LIST_FOREACH(bp2, &bs->bs_bplist, bp_next) {
 919                         if (!(bp2->bp_synced ||
 920                              bp2->bp_role == BSTP_ROLE_ROOT)) {
 921                                 synced = 0;
 922                                 break;
 923                         }
 924                 }
 925                 bs->bs_allsynced = synced;
 926         }
 927
 928         bstp_update_roles(bs, bp);
 929         bstp_update_tc(bp);
 930 }
 931
 932 static void
 933 bstp_update_roles(struct bstp_state *bs, struct bstp_port *bp)
 934 {
 935         switch (bp->bp_role) {
 936         case BSTP_ROLE_DISABLED:
 937                 /* Clear any flags if set */
 938                 if (bp->bp_sync || !bp->bp_synced || bp->bp_reroot) {
 939                         bp->bp_sync = 0;
 940                         bp->bp_synced = 1;
 941                         bp->bp_reroot = 0;
 942                 }
 943                 break;
 944
 945         case BSTP_ROLE_ALTERNATE:
 946         case BSTP_ROLE_BACKUP:
 947                 if ((bs->bs_allsynced && !bp->bp_agree) ||
 948                     (bp->bp_proposed && bp->bp_agree)) {
 949                         bp->bp_proposed = 0;
 950                         bp->bp_agree = 1;
 951                         bp->bp_flags |= BSTP_PORT_NEWINFO;
 952                         DPRINTF("%s -> ALTERNATE_AGREED\n",
 953                             bp->bp_ifp->if_xname);
 954                 }
 955
 956                 if (bp->bp_proposed && !bp->bp_agree) {
 957                         bstp_set_all_sync(bs);
 958                         bp->bp_proposed = 0;
 959                         DPRINTF("%s -> ALTERNATE_PROPOSED\n",
 960                             bp->bp_ifp->if_xname);
 961                 }
 962
 963                 /* Clear any flags if set */
 964                 if (bp->bp_sync || !bp->bp_synced || bp->bp_reroot) {
 965                         bp->bp_sync = 0;
 966                         bp->bp_synced = 1;
 967                         bp->bp_reroot = 0;
 968                         DPRINTF("%s -> ALTERNATE_PORT\n", bp->bp_ifp->if_xname);
 969                 }
 970                 break;
 971
 972         case BSTP_ROLE_ROOT:
 973                 if (bp->bp_state != BSTP_IFSTATE_FORWARDING && !bp->bp_reroot) {
 974                         bstp_set_all_reroot(bs);
 975                         DPRINTF("%s -> ROOT_REROOT\n", bp->bp_ifp->if_xname);
 976                 }
 977
 978                 if ((bs->bs_allsynced && !bp->bp_agree) ||
 979                     (bp->bp_proposed && bp->bp_agree)) {
 980                         bp->bp_proposed = 0;
 981                         bp->bp_sync = 0;
 982                         bp->bp_agree = 1;
 983                         bp->bp_flags |= BSTP_PORT_NEWINFO;
 984                         DPRINTF("%s -> ROOT_AGREED\n", bp->bp_ifp->if_xname);
 985                 }
 986
 987                 if (bp->bp_proposed && !bp->bp_agree) {
 988                         bstp_set_all_sync(bs);
 989                         bp->bp_proposed = 0;
 990                         DPRINTF("%s -> ROOT_PROPOSED\n", bp->bp_ifp->if_xname);
 991                 }
 992
 993                 if (bp->bp_state != BSTP_IFSTATE_FORWARDING &&
 994                     (bp->bp_forward_delay_timer.active == 0 ||
 995                     (bstp_rerooted(bs, bp) &&
 996                     bp->bp_recent_backup_timer.active == 0 &&
 997                     bp->bp_protover == BSTP_PROTO_RSTP))) {
 998                         switch (bp->bp_state) {
 999                         case BSTP_IFSTATE_DISCARDING:
1000                                 bstp_set_port_state(bp, BSTP_IFSTATE_LEARNING);
1001                                 break;
1002                         case BSTP_IFSTATE_LEARNING:
1003                                 bstp_set_port_state(bp,
1004                                     BSTP_IFSTATE_FORWARDING);
1005                                 break;
1006                         }
1007                 }
1008
1009                 if (bp->bp_state == BSTP_IFSTATE_FORWARDING && bp->bp_reroot) {
1010                         bp->bp_reroot = 0;
1011                         DPRINTF("%s -> ROOT_REROOTED\n", bp->bp_ifp->if_xname);
1012                 }
1013                 break;
1014
1015         case BSTP_ROLE_DESIGNATED:
1016                 if (bp->bp_recent_root_timer.active == 0 && bp->bp_reroot) {
1017                         bp->bp_reroot = 0;
1018                         DPRINTF("%s -> DESIGNATED_RETIRED\n",
1019                             bp->bp_ifp->if_xname);
1020                 }
1021
1022                 if ((bp->bp_state == BSTP_IFSTATE_DISCARDING &&
1023                     !bp->bp_synced) || (bp->bp_agreed && !bp->bp_synced) ||
1024                     (bp->bp_operedge && !bp->bp_synced) ||
1025                     (bp->bp_sync && bp->bp_synced)) {
1026                         bstp_timer_stop(&bp->bp_recent_root_timer);
1027                         bp->bp_synced = 1;
1028                         bp->bp_sync = 0;
1029                         DPRINTF("%s -> DESIGNATED_SYNCED\n",
1030                             bp->bp_ifp->if_xname);
1031                 }
1032
1033                 if (bp->bp_state != BSTP_IFSTATE_FORWARDING &&
1034                     !bp->bp_agreed && !bp->bp_proposing &&
1035                     !bp->bp_operedge) {
1036                         bp->bp_proposing = 1;
1037                         bp->bp_flags |= BSTP_PORT_NEWINFO;
1038                         bstp_timer_start(&bp->bp_edge_delay_timer,
1039                             (bp->bp_ptp_link ? BSTP_DEFAULT_MIGRATE_DELAY :
1040                              bp->bp_desg_max_age));
1041                         DPRINTF("%s -> DESIGNATED_PROPOSE\n",
1042                             bp->bp_ifp->if_xname);
1043                 }
1044
1045                 if (bp->bp_state != BSTP_IFSTATE_FORWARDING &&
1046                     (bp->bp_forward_delay_timer.active == 0 || bp->bp_agreed ||
1047                     bp->bp_operedge) &&
1048                     (bp->bp_recent_root_timer.active == 0 || !bp->bp_reroot) &&
1049                     !bp->bp_sync) {
1050                         if (bp->bp_agreed)
1051                                 DPRINTF("%s -> AGREED\n", bp->bp_ifp->if_xname);
1052                         /*
1053                          * If agreed|operedge then go straight to forwarding,
1054                          * otherwise follow discard -> learn -> forward.
1055                          */
1056                         if (bp->bp_agreed || bp->bp_operedge ||
1057                             bp->bp_state == BSTP_IFSTATE_LEARNING) {
1058                                 bstp_set_port_state(bp,
1059                                     BSTP_IFSTATE_FORWARDING);
1060                                 bp->bp_agreed = bp->bp_protover;
1061                         } else if (bp->bp_state == BSTP_IFSTATE_DISCARDING)
1062                                 bstp_set_port_state(bp, BSTP_IFSTATE_LEARNING);
1063                 }
1064
1065                 if (((bp->bp_sync && !bp->bp_synced) ||
1066                     (bp->bp_reroot && bp->bp_recent_root_timer.active) ||
1067                     (bp->bp_flags & BSTP_PORT_DISPUTED)) && !bp->bp_operedge &&
1068                     bp->bp_state != BSTP_IFSTATE_DISCARDING) {
1069                         bstp_set_port_state(bp, BSTP_IFSTATE_DISCARDING);
1070                         bp->bp_flags &= ~BSTP_PORT_DISPUTED;
1071                         bstp_timer_start(&bp->bp_forward_delay_timer,
1072                             bp->bp_protover == BSTP_PROTO_RSTP ?
1073                             bp->bp_desg_htime : bp->bp_desg_fdelay);
1074                         DPRINTF("%s -> DESIGNATED_DISCARD\n",
1075                             bp->bp_ifp->if_xname);
1076                 }
1077                 break;
1078         }
1079
1080         if (bp->bp_flags & BSTP_PORT_NEWINFO)
1081                 bstp_transmit(bs, bp);
1082 }
1083
1084 static void
1085 bstp_update_tc(struct bstp_port *bp)
1086 {
1087         switch (bp->bp_tcstate) {
1088                 case BSTP_TCSTATE_ACTIVE:
1089                         if ((bp->bp_role != BSTP_ROLE_DESIGNATED &&
1090                             bp->bp_role != BSTP_ROLE_ROOT) || bp->bp_operedge)
1091                                 bstp_set_port_tc(bp, BSTP_TCSTATE_LEARNING);
1092
1093                         if (bp->bp_rcvdtcn)
1094                                 bstp_set_port_tc(bp, BSTP_TCSTATE_TCN);
1095                         if (bp->bp_rcvdtc)
1096                                 bstp_set_port_tc(bp, BSTP_TCSTATE_TC);
1097
1098                         if (bp->bp_tc_prop && !bp->bp_operedge)
1099                                 bstp_set_port_tc(bp, BSTP_TCSTATE_PROPAG);
1100
1101                         if (bp->bp_rcvdtca)
1102                                 bstp_set_port_tc(bp, BSTP_TCSTATE_ACK);
1103                         break;
1104
1105                 case BSTP_TCSTATE_INACTIVE:
1106                         if ((bp->bp_state == BSTP_IFSTATE_LEARNING ||
1107                             bp->bp_state == BSTP_IFSTATE_FORWARDING) &&
1108                             bp->bp_fdbflush == 0)
1109                                 bstp_set_port_tc(bp, BSTP_TCSTATE_LEARNING);
1110                         break;
1111
1112                 case BSTP_TCSTATE_LEARNING:
1113                         if (bp->bp_rcvdtc || bp->bp_rcvdtcn || bp->bp_rcvdtca ||
1114                             bp->bp_tc_prop)
1115                                 bstp_set_port_tc(bp, BSTP_TCSTATE_LEARNING);
1116                         else if (bp->bp_role != BSTP_ROLE_DESIGNATED &&
1117                                  bp->bp_role != BSTP_ROLE_ROOT &&
1118                                  bp->bp_state == BSTP_IFSTATE_DISCARDING)
1119                                 bstp_set_port_tc(bp, BSTP_TCSTATE_INACTIVE);
1120
1121                         if ((bp->bp_role == BSTP_ROLE_DESIGNATED ||
1122                             bp->bp_role == BSTP_ROLE_ROOT) &&
1123                             bp->bp_state == BSTP_IFSTATE_FORWARDING &&
1124                             !bp->bp_operedge)
1125                                 bstp_set_port_tc(bp, BSTP_TCSTATE_DETECTED);
1126                         break;
1127
1128                 /* these are transient states and go straight back to ACTIVE */
1129                 case BSTP_TCSTATE_DETECTED:
1130                 case BSTP_TCSTATE_TCN:
1131                 case BSTP_TCSTATE_TC:
1132                 case BSTP_TCSTATE_PROPAG:
1133                 case BSTP_TCSTATE_ACK:
1134                         DPRINTF("Invalid TC state for %s\n",
1135                             bp->bp_ifp->if_xname);
1136                         break;
1137         }
1138
1139 }
1140
1141 static void
1142 bstp_update_info(struct bstp_port *bp)
1143 {
1144         struct bstp_state *bs = bp->bp_bs;
1145
1146         bp->bp_proposing = 0;
1147         bp->bp_proposed = 0;
1148
1149         if (bp->bp_agreed && !bstp_pdu_bettersame(bp, BSTP_INFO_MINE))
1150                 bp->bp_agreed = 0;
1151
1152         if (bp->bp_synced && !bp->bp_agreed) {
1153                 bp->bp_synced = 0;
1154                 bs->bs_allsynced = 0;
1155         }
1156
1157         /* copy the designated pv to the port */
1158         bp->bp_port_pv = bp->bp_desg_pv;
1159         bp->bp_port_msg_age = bp->bp_desg_msg_age;
1160         bp->bp_port_max_age = bp->bp_desg_max_age;
1161         bp->bp_port_fdelay = bp->bp_desg_fdelay;
1162         bp->bp_port_htime = bp->bp_desg_htime;
1163         bp->bp_infois = BSTP_INFO_MINE;
1164
1165         /* Set transmit flag but do not immediately send */
1166         bp->bp_flags |= BSTP_PORT_NEWINFO;
1167 }
1168
1169 /* set tcprop on every port other than the caller */
1170 static void
1171 bstp_set_other_tcprop(struct bstp_port *bp)
1172 {
1173         struct bstp_state *bs = bp->bp_bs;
1174         struct bstp_port *bp2;
1175
1176         BSTP_LOCK_ASSERT(bs);
1177
1178         LIST_FOREACH(bp2, &bs->bs_bplist, bp_next) {
1179                 if (bp2 == bp)
1180                         continue;
1181                 bp2->bp_tc_prop = 1;
1182         }
1183 }
1184
1185 static void
1186 bstp_set_all_reroot(struct bstp_state *bs)
1187 {
1188         struct bstp_port *bp;
1189
1190         BSTP_LOCK_ASSERT(bs);
1191
1192         LIST_FOREACH(bp, &bs->bs_bplist, bp_next)
1193                 bp->bp_reroot = 1;
1194 }
1195
1196 static void
1197 bstp_set_all_sync(struct bstp_state *bs)
1198 {
1199         struct bstp_port *bp;
1200
1201         BSTP_LOCK_ASSERT(bs);
1202
1203         LIST_FOREACH(bp, &bs->bs_bplist, bp_next) {
1204                 bp->bp_sync = 1;
1205                 bp->bp_synced = 0;      /* Not explicit in spec */
1206         }
1207
1208         bs->bs_allsynced = 0;
1209 }
1210
1211 static void
1212 bstp_set_port_state(struct bstp_port *bp, int state)
1213 {
1214         if (bp->bp_state == state)
1215                 return;
1216
1217         bp->bp_state = state;
1218
1219         switch (bp->bp_state) {
1220                 case BSTP_IFSTATE_DISCARDING:
1221                         DPRINTF("state changed to DISCARDING on %s\n",
1222                             bp->bp_ifp->if_xname);
1223                         break;
1224
1225                 case BSTP_IFSTATE_LEARNING:
1226                         DPRINTF("state changed to LEARNING on %s\n",
1227                             bp->bp_ifp->if_xname);
1228
1229                         bstp_timer_start(&bp->bp_forward_delay_timer,
1230                             bp->bp_protover == BSTP_PROTO_RSTP ?
1231                             bp->bp_desg_htime : bp->bp_desg_fdelay);
1232                         break;
1233
1234                 case BSTP_IFSTATE_FORWARDING:
1235                         DPRINTF("state changed to FORWARDING on %s\n",
1236                             bp->bp_ifp->if_xname);
1237
1238                         bstp_timer_stop(&bp->bp_forward_delay_timer);
1239                         /* Record that we enabled forwarding */
1240                         bp->bp_forward_transitions++;
1241                         break;
1242         }
1243
1244         /* notify the parent bridge */
1245         taskqueue_enqueue(taskqueue_swi, &bp->bp_statetask);
1246 }
1247
1248 static void
1249 bstp_set_port_role(struct bstp_port *bp, int role)
1250 {
1251         struct bstp_state *bs = bp->bp_bs;
1252
1253         if (bp->bp_role == role)
1254                 return;
1255
1256         /* perform pre-change tasks */
1257         switch (bp->bp_role) {
1258                 case BSTP_ROLE_DISABLED:
1259                         bstp_timer_start(&bp->bp_forward_delay_timer,
1260                             bp->bp_desg_max_age);
1261                         break;
1262
1263                 case BSTP_ROLE_BACKUP:
1264                         bstp_timer_start(&bp->bp_recent_backup_timer,
1265                             bp->bp_desg_htime * 2);
1266                         /* fall through */
1267                 case BSTP_ROLE_ALTERNATE:
1268                         bstp_timer_start(&bp->bp_forward_delay_timer,
1269                             bp->bp_desg_fdelay);
1270                         bp->bp_sync = 0;
1271                         bp->bp_synced = 1;
1272                         bp->bp_reroot = 0;
1273                         break;
1274
1275                 case BSTP_ROLE_ROOT:
1276                         bstp_timer_start(&bp->bp_recent_root_timer,
1277                             BSTP_DEFAULT_FORWARD_DELAY);
1278                         break;
1279         }
1280
1281         bp->bp_role = role;
1282         /* clear values not carried between roles */
1283         bp->bp_proposing = 0;
1284         bs->bs_allsynced = 0;
1285
1286         /* initialise the new role */
1287         switch (bp->bp_role) {
1288                 case BSTP_ROLE_DISABLED:
1289                 case BSTP_ROLE_ALTERNATE:
1290                 case BSTP_ROLE_BACKUP:
1291                         DPRINTF("%s role -> ALT/BACK/DISABLED\n",
1292                             bp->bp_ifp->if_xname);
1293                         bstp_set_port_state(bp, BSTP_IFSTATE_DISCARDING);
1294                         bstp_timer_stop(&bp->bp_recent_root_timer);
1295                         bstp_timer_latch(&bp->bp_forward_delay_timer);
1296                         bp->bp_sync = 0;
1297                         bp->bp_synced = 1;
1298                         bp->bp_reroot = 0;
1299                         break;
1300
1301                 case BSTP_ROLE_ROOT:
1302                         DPRINTF("%s role -> ROOT\n",
1303                             bp->bp_ifp->if_xname);
1304                         bstp_set_port_state(bp, BSTP_IFSTATE_DISCARDING);
1305                         bstp_timer_latch(&bp->bp_recent_root_timer);
1306                         bp->bp_proposing = 0;
1307                         break;
1308
1309                 case BSTP_ROLE_DESIGNATED:
1310                         DPRINTF("%s role -> DESIGNATED\n",
1311                             bp->bp_ifp->if_xname);
1312                         bstp_timer_start(&bp->bp_hello_timer,
1313                             bp->bp_desg_htime);
1314                         bp->bp_agree = 0;
1315                         break;
1316         }
1317
1318         /* let the TC state know that the role changed */
1319         bstp_update_tc(bp);
1320 }
1321
1322 static void
1323 bstp_set_port_proto(struct bstp_port *bp, int proto)
1324 {
1325         struct bstp_state *bs = bp->bp_bs;
1326
1327         /* supported protocol versions */
1328         switch (proto) {
1329                 case BSTP_PROTO_STP:
1330                         /* we can downgrade protocols only */
1331                         bstp_timer_stop(&bp->bp_migrate_delay_timer);
1332                         /* clear unsupported features */
1333                         bp->bp_operedge = 0;
1334                         /* STP compat mode only uses 16 bits of the 32 */
1335                         if (bp->bp_path_cost > 65535)
1336                                 bp->bp_path_cost = 65535;
1337                         break;
1338
1339                 case BSTP_PROTO_RSTP:
1340                         bstp_timer_start(&bp->bp_migrate_delay_timer,
1341                             bs->bs_migration_delay);
1342                         break;
1343
1344                 default:
1345                         DPRINTF("Unsupported STP version %d\n", proto);
1346                         return;
1347         }
1348
1349         bp->bp_protover = proto;
1350         bp->bp_flags &= ~BSTP_PORT_CANMIGRATE;
1351 }
1352
1353 static void
1354 bstp_set_port_tc(struct bstp_port *bp, int state)
1355 {
1356         struct bstp_state *bs = bp->bp_bs;
1357
1358         bp->bp_tcstate = state;
1359
1360         /* initialise the new state */
1361         switch (bp->bp_tcstate) {
1362                 case BSTP_TCSTATE_ACTIVE:
1363                         DPRINTF("%s -> TC_ACTIVE\n", bp->bp_ifp->if_xname);
1364                         /* nothing to do */
1365                         break;
1366
1367                 case BSTP_TCSTATE_INACTIVE:
1368                         bstp_timer_stop(&bp->bp_tc_timer);
1369                         /* flush routes on the parent bridge */
1370                         bp->bp_fdbflush = 1;
1371                         taskqueue_enqueue(taskqueue_swi, &bp->bp_rtagetask);
1372                         bp->bp_tc_ack = 0;
1373                         DPRINTF("%s -> TC_INACTIVE\n", bp->bp_ifp->if_xname);
1374                         break;
1375
1376                 case BSTP_TCSTATE_LEARNING:
1377                         bp->bp_rcvdtc = 0;
1378                         bp->bp_rcvdtcn = 0;
1379                         bp->bp_rcvdtca = 0;
1380                         bp->bp_tc_prop = 0;
1381                         DPRINTF("%s -> TC_LEARNING\n", bp->bp_ifp->if_xname);
1382                         break;
1383
1384                 case BSTP_TCSTATE_DETECTED:
1385                         bstp_set_timer_tc(bp);
1386                         bstp_set_other_tcprop(bp);
1387                         /* send out notification */
1388                         bp->bp_flags |= BSTP_PORT_NEWINFO;
1389                         bstp_transmit(bs, bp);
1390                         getmicrotime(&bs->bs_last_tc_time);
1391                         DPRINTF("%s -> TC_DETECTED\n", bp->bp_ifp->if_xname);
1392                         bp->bp_tcstate = BSTP_TCSTATE_ACTIVE; /* UCT */
1393                         break;
1394
1395                 case BSTP_TCSTATE_TCN:
1396                         bstp_set_timer_tc(bp);
1397                         DPRINTF("%s -> TC_TCN\n", bp->bp_ifp->if_xname);
1398                         /* fall through */
1399                 case BSTP_TCSTATE_TC:
1400                         bp->bp_rcvdtc = 0;
1401                         bp->bp_rcvdtcn = 0;
1402                         if (bp->bp_role == BSTP_ROLE_DESIGNATED)
1403                                 bp->bp_tc_ack = 1;
1404
1405                         bstp_set_other_tcprop(bp);
1406                         DPRINTF("%s -> TC_TC\n", bp->bp_ifp->if_xname);
1407                         bp->bp_tcstate = BSTP_TCSTATE_ACTIVE; /* UCT */
1408                         break;
1409
1410                 case BSTP_TCSTATE_PROPAG:
1411                         /* flush routes on the parent bridge */
1412                         bp->bp_fdbflush = 1;
1413                         taskqueue_enqueue(taskqueue_swi, &bp->bp_rtagetask);
1414                         bp->bp_tc_prop = 0;
1415                         bstp_set_timer_tc(bp);
1416                         DPRINTF("%s -> TC_PROPAG\n", bp->bp_ifp->if_xname);
1417                         bp->bp_tcstate = BSTP_TCSTATE_ACTIVE; /* UCT */
1418                         break;
1419
1420                 case BSTP_TCSTATE_ACK:
1421                         bstp_timer_stop(&bp->bp_tc_timer);
1422                         bp->bp_rcvdtca = 0;
1423                         DPRINTF("%s -> TC_ACK\n", bp->bp_ifp->if_xname);
1424                         bp->bp_tcstate = BSTP_TCSTATE_ACTIVE; /* UCT */
1425                         break;
1426         }
1427 }
1428
1429 static void
1430 bstp_set_timer_tc(struct bstp_port *bp)
1431 {
1432         struct bstp_state *bs = bp->bp_bs;
1433
1434         if (bp->bp_tc_timer.active)
1435                 return;
1436
1437         switch (bp->bp_protover) {
1438                 case BSTP_PROTO_RSTP:
1439                         bstp_timer_start(&bp->bp_tc_timer,
1440                             bp->bp_desg_htime + BSTP_TICK_VAL);
1441                         bp->bp_flags |= BSTP_PORT_NEWINFO;
1442                         break;
1443
1444                 case BSTP_PROTO_STP:
1445                         bstp_timer_start(&bp->bp_tc_timer,
1446                             bs->bs_root_max_age + bs->bs_root_fdelay);
1447                         break;
1448         }
1449 }
1450
1451 static void
1452 bstp_set_timer_msgage(struct bstp_port *bp)
1453 {
1454         if (bp->bp_port_msg_age + BSTP_MESSAGE_AGE_INCR <=
1455             bp->bp_port_max_age) {
1456                 bstp_timer_start(&bp->bp_message_age_timer,
1457                     bp->bp_port_htime * 3);
1458         } else
1459                 /* expires immediately */
1460                 bstp_timer_start(&bp->bp_message_age_timer, 0);
1461 }
1462
1463 static int
1464 bstp_rerooted(struct bstp_state *bs, struct bstp_port *bp)
1465 {
1466         struct bstp_port *bp2;
1467         int rr_set = 0;
1468
1469         LIST_FOREACH(bp2, &bs->bs_bplist, bp_next) {
1470                 if (bp2 == bp)
1471                         continue;
1472                 if (bp2->bp_recent_root_timer.active) {
1473                         rr_set = 1;
1474                         break;
1475                 }
1476         }
1477         return (!rr_set);
1478 }
1479
1480 int
1481 bstp_set_htime(struct bstp_state *bs, int t)
1482 {
1483         /* convert seconds to ticks */
1484         t *=  BSTP_TICK_VAL;
1485
1486         /* value can only be changed in leagacy stp mode */
1487         if (bs->bs_protover != BSTP_PROTO_STP)
1488                 return (EPERM);
1489
1490         if (t < BSTP_MIN_HELLO_TIME || t > BSTP_MAX_HELLO_TIME)
1491                 return (EINVAL);
1492
1493         BSTP_LOCK(bs);
1494         bs->bs_bridge_htime = t;
1495         bstp_reinit(bs);
1496         BSTP_UNLOCK(bs);
1497         return (0);
1498 }
1499
1500 int
1501 bstp_set_fdelay(struct bstp_state *bs, int t)
1502 {
1503         /* convert seconds to ticks */
1504         t *= BSTP_TICK_VAL;
1505
1506         if (t < BSTP_MIN_FORWARD_DELAY || t > BSTP_MAX_FORWARD_DELAY)
1507                 return (EINVAL);
1508
1509         BSTP_LOCK(bs);
1510         bs->bs_bridge_fdelay = t;
1511         bstp_reinit(bs);
1512         BSTP_UNLOCK(bs);
1513         return (0);
1514 }
1515
1516 int
1517 bstp_set_maxage(struct bstp_state *bs, int t)
1518 {
1519         /* convert seconds to ticks */
1520         t *= BSTP_TICK_VAL;
1521
1522         if (t < BSTP_MIN_MAX_AGE || t > BSTP_MAX_MAX_AGE)
1523                 return (EINVAL);
1524
1525         BSTP_LOCK(bs);
1526         bs->bs_bridge_max_age = t;
1527         bstp_reinit(bs);
1528         BSTP_UNLOCK(bs);
1529         return (0);
1530 }
1531
1532 int
1533 bstp_set_holdcount(struct bstp_state *bs, int count)
1534 {
1535         struct bstp_port *bp;
1536
1537         if (count < BSTP_MIN_HOLD_COUNT ||
1538             count > BSTP_MAX_HOLD_COUNT)
1539                 return (EINVAL);
1540
1541         BSTP_LOCK(bs);
1542         bs->bs_txholdcount = count;
1543         LIST_FOREACH(bp, &bs->bs_bplist, bp_next)
1544                 bp->bp_txcount = 0;
1545         BSTP_UNLOCK(bs);
1546         return (0);
1547 }
1548
1549 int
1550 bstp_set_protocol(struct bstp_state *bs, int proto)
1551 {
1552         struct bstp_port *bp;
1553
1554         switch (proto) {
1555                 /* Supported protocol versions */
1556                 case BSTP_PROTO_STP:
1557                 case BSTP_PROTO_RSTP:
1558                         break;
1559
1560                 default:
1561                         return (EINVAL);
1562         }
1563
1564         BSTP_LOCK(bs);
1565         bs->bs_protover = proto;
1566         bs->bs_bridge_htime = BSTP_DEFAULT_HELLO_TIME;
1567         LIST_FOREACH(bp, &bs->bs_bplist, bp_next) {
1568                 /* reinit state */
1569                 bp->bp_infois = BSTP_INFO_DISABLED;
1570                 bp->bp_txcount = 0;
1571                 bstp_set_port_proto(bp, bs->bs_protover);
1572                 bstp_set_port_role(bp, BSTP_ROLE_DISABLED);
1573                 bstp_set_port_tc(bp, BSTP_TCSTATE_INACTIVE);
1574                 bstp_timer_stop(&bp->bp_recent_backup_timer);
1575         }
1576         bstp_reinit(bs);
1577         BSTP_UNLOCK(bs);
1578         return (0);
1579 }
1580
1581 int
1582 bstp_set_priority(struct bstp_state *bs, int pri)
1583 {
1584         if (pri < 0 || pri > BSTP_MAX_PRIORITY)
1585                 return (EINVAL);
1586
1587         /* Limit to steps of 4096 */
1588         pri -= pri % 4096;
1589
1590         BSTP_LOCK(bs);
1591         bs->bs_bridge_priority = pri;
1592         bstp_reinit(bs);
1593         BSTP_UNLOCK(bs);
1594         return (0);
1595 }
1596
1597 int
1598 bstp_set_port_priority(struct bstp_port *bp, int pri)
1599 {
1600         struct bstp_state *bs = bp->bp_bs;
1601
1602         if (pri < 0 || pri > BSTP_MAX_PORT_PRIORITY)
1603                 return (EINVAL);
1604
1605         /* Limit to steps of 16 */
1606         pri -= pri % 16;
1607
1608         BSTP_LOCK(bs);
1609         bp->bp_priority = pri;
1610         bstp_reinit(bs);
1611         BSTP_UNLOCK(bs);
1612         return (0);
1613 }
1614
1615 int
1616 bstp_set_path_cost(struct bstp_port *bp, uint32_t path_cost)
1617 {
1618         struct bstp_state *bs = bp->bp_bs;
1619
1620         if (path_cost > BSTP_MAX_PATH_COST)
1621                 return (EINVAL);
1622
1623         /* STP compat mode only uses 16 bits of the 32 */
1624         if (bp->bp_protover == BSTP_PROTO_STP && path_cost > 65535)
1625                 path_cost = 65535;
1626
1627         BSTP_LOCK(bs);
1628
1629         if (path_cost == 0) {   /* use auto */
1630                 bp->bp_flags &= ~BSTP_PORT_ADMCOST;
1631                 bp->bp_path_cost = bstp_calc_path_cost(bp);
1632         } else {
1633                 bp->bp_path_cost = path_cost;
1634                 bp->bp_flags |= BSTP_PORT_ADMCOST;
1635         }
1636         bstp_reinit(bs);
1637         BSTP_UNLOCK(bs);
1638         return (0);
1639 }
1640
1641 int
1642 bstp_set_edge(struct bstp_port *bp, int set)
1643 {
1644         struct bstp_state *bs = bp->bp_bs;
1645
1646         BSTP_LOCK(bs);
1647         if ((bp->bp_operedge = set) == 0)
1648                 bp->bp_flags &= ~BSTP_PORT_ADMEDGE;
1649         else
1650                 bp->bp_flags |= BSTP_PORT_ADMEDGE;
1651         BSTP_UNLOCK(bs);
1652         return (0);
1653 }
1654
1655 int
1656 bstp_set_autoedge(struct bstp_port *bp, int set)
1657 {
1658         struct bstp_state *bs = bp->bp_bs;
1659
1660         BSTP_LOCK(bs);
1661         if (set) {
1662                 bp->bp_flags |= BSTP_PORT_AUTOEDGE;
1663                 /* we may be able to transition straight to edge */
1664                 if (bp->bp_edge_delay_timer.active == 0)
1665                         bstp_edge_delay_expiry(bs, bp);
1666         } else
1667                 bp->bp_flags &= ~BSTP_PORT_AUTOEDGE;
1668         BSTP_UNLOCK(bs);
1669         return (0);
1670 }
1671
1672 int
1673 bstp_set_ptp(struct bstp_port *bp, int set)
1674 {
1675         struct bstp_state *bs = bp->bp_bs;
1676
1677         BSTP_LOCK(bs);
1678         bp->bp_ptp_link = set;
1679         BSTP_UNLOCK(bs);
1680         return (0);
1681 }
1682
1683 int
1684 bstp_set_autoptp(struct bstp_port *bp, int set)
1685 {
1686         struct bstp_state *bs = bp->bp_bs;
1687
1688         BSTP_LOCK(bs);
1689         if (set) {
1690                 bp->bp_flags |= BSTP_PORT_AUTOPTP;
1691                 if (bp->bp_role != BSTP_ROLE_DISABLED)
1692                         bstp_ifupdstatus(bs, bp);
1693         } else
1694                 bp->bp_flags &= ~BSTP_PORT_AUTOPTP;
1695         BSTP_UNLOCK(bs);
1696         return (0);
1697 }
1698
1699 /*
1700  * Calculate the path cost according to the link speed.
1701  */
1702 static uint32_t
1703 bstp_calc_path_cost(struct bstp_port *bp)
1704 {
1705         struct ifnet *ifp = bp->bp_ifp;
1706         uint32_t path_cost;
1707
1708         /* If the priority has been manually set then retain the value */
1709         if (bp->bp_flags & BSTP_PORT_ADMCOST)
1710                 return bp->bp_path_cost;
1711
1712         if (ifp->if_link_state == LINK_STATE_DOWN) {
1713                 /* Recalc when the link comes up again */
1714                 bp->bp_flags |= BSTP_PORT_PNDCOST;
1715                 return (BSTP_DEFAULT_PATH_COST);
1716         }
1717
1718         if (ifp->if_baudrate < 1000)
1719                 return (BSTP_DEFAULT_PATH_COST);
1720
1721         /* formula from section 17.14, IEEE Std 802.1D-2004 */
1722         path_cost = 20000000000ULL / (ifp->if_baudrate / 1000);
1723
1724         if (path_cost > BSTP_MAX_PATH_COST)
1725                 path_cost = BSTP_MAX_PATH_COST;
1726
1727         /* STP compat mode only uses 16 bits of the 32 */
1728         if (bp->bp_protover == BSTP_PROTO_STP && path_cost > 65535)
1729                 path_cost = 65535;
1730
1731         return (path_cost);
1732 }
1733
1734 /*
1735  * Notify the bridge that a port state has changed, we need to do this from a
1736  * taskqueue to avoid a LOR.
1737  */
1738 static void
1739 bstp_notify_state(void *arg, int pending)
1740 {
1741         struct bstp_port *bp = (struct bstp_port *)arg;
1742         struct bstp_state *bs = bp->bp_bs;
1743
1744         if (bp->bp_active == 1 && bs->bs_state_cb != NULL)
1745                 (*bs->bs_state_cb)(bp->bp_ifp, bp->bp_state);
1746 }
1747
1748 /*
1749  * Flush the routes on the bridge port, we need to do this from a
1750  * taskqueue to avoid a LOR.
1751  */
1752 static void
1753 bstp_notify_rtage(void *arg, int pending)
1754 {
1755         struct bstp_port *bp = (struct bstp_port *)arg;
1756         struct bstp_state *bs = bp->bp_bs;
1757         int age = 0;
1758
1759         BSTP_LOCK(bs);
1760         switch (bp->bp_protover) {
1761                 case BSTP_PROTO_STP:
1762                         /* convert to seconds */
1763                         age = bp->bp_desg_fdelay / BSTP_TICK_VAL;
1764                         break;
1765
1766                 case BSTP_PROTO_RSTP:
1767                         age = 0;
1768                         break;
1769         }
1770         BSTP_UNLOCK(bs);
1771
1772         if (bp->bp_active == 1 && bs->bs_rtage_cb != NULL)
1773                 (*bs->bs_rtage_cb)(bp->bp_ifp, age);
1774
1775         /* flush is complete */
1776         BSTP_LOCK(bs);
1777         bp->bp_fdbflush = 0;
1778         BSTP_UNLOCK(bs);
1779 }
1780
1781 void
1782 bstp_linkstate(struct ifnet *ifp, int state)
1783 {
1784         struct bstp_state *bs;
1785         struct bstp_port *bp;
1786
1787         /* search for the stp port */
1788         mtx_lock(&bstp_list_mtx);
1789         LIST_FOREACH(bs, &bstp_list, bs_list) {
1790                 BSTP_LOCK(bs);
1791                 LIST_FOREACH(bp, &bs->bs_bplist, bp_next) {
1792                         if (bp->bp_ifp == ifp) {
1793                                 bstp_ifupdstatus(bs, bp);
1794                                 bstp_update_state(bs, bp);
1795                                 /* it only exists once so return */
1796                                 BSTP_UNLOCK(bs);
1797                                 mtx_unlock(&bstp_list_mtx);
1798                                 return;
1799                         }
1800                 }
1801                 BSTP_UNLOCK(bs);
1802         }
1803         mtx_unlock(&bstp_list_mtx);
1804 }
1805
1806 static void
1807 bstp_ifupdstatus(struct bstp_state *bs, struct bstp_port *bp)
1808 {
1809         struct ifnet *ifp = bp->bp_ifp;
1810         struct ifmediareq ifmr;
1811         int error = 0;
1812
1813         BSTP_LOCK_ASSERT(bs);
1814
1815         bzero((char *)&ifmr, sizeof(ifmr));
1816         error = (*ifp->if_ioctl)(ifp, SIOCGIFMEDIA, (caddr_t)&ifmr);
1817
1818         if ((error == 0) && (ifp->if_flags & IFF_UP)) {
1819                 if (ifmr.ifm_status & IFM_ACTIVE) {
1820                         /* A full-duplex link is assumed to be point to point */
1821                         if (bp->bp_flags & BSTP_PORT_AUTOPTP) {
1822                                 bp->bp_ptp_link =
1823                                     ifmr.ifm_active & IFM_FDX ? 1 : 0;
1824                         }
1825
1826                         /* Calc the cost if the link was down previously */
1827                         if (bp->bp_flags & BSTP_PORT_PNDCOST) {
1828                                 bp->bp_path_cost = bstp_calc_path_cost(bp);
1829                                 bp->bp_flags &= ~BSTP_PORT_PNDCOST;
1830                         }
1831
1832                         if (bp->bp_role == BSTP_ROLE_DISABLED)
1833                                 bstp_enable_port(bs, bp);
1834                 } else {
1835                         if (bp->bp_role != BSTP_ROLE_DISABLED) {
1836                                 bstp_disable_port(bs, bp);
1837                                 if ((bp->bp_flags & BSTP_PORT_ADMEDGE) &&
1838                                     bp->bp_protover == BSTP_PROTO_RSTP)
1839                                         bp->bp_operedge = 1;
1840                         }
1841                 }
1842                 return;
1843         }
1844
1845         if (bp->bp_infois != BSTP_INFO_DISABLED)
1846                 bstp_disable_port(bs, bp);
1847 }
1848
1849 static void
1850 bstp_enable_port(struct bstp_state *bs, struct bstp_port *bp)
1851 {
1852         bp->bp_infois = BSTP_INFO_AGED;
1853         bstp_assign_roles(bs);
1854 }
1855
1856 static void
1857 bstp_disable_port(struct bstp_state *bs, struct bstp_port *bp)
1858 {
1859         bp->bp_infois = BSTP_INFO_DISABLED;
1860         bstp_assign_roles(bs);
1861 }
1862
1863 static void
1864 bstp_tick(void *arg)
1865 {
1866         struct bstp_state *bs = arg;
1867         struct bstp_port *bp;
1868
1869         BSTP_LOCK_ASSERT(bs);
1870
1871         if (bs->bs_running == 0)
1872                 return;
1873
1874         /* slow timer to catch missed link events */
1875         if (bstp_timer_expired(&bs->bs_link_timer)) {
1876                 LIST_FOREACH(bp, &bs->bs_bplist, bp_next)
1877                         bstp_ifupdstatus(bs, bp);
1878                 bstp_timer_start(&bs->bs_link_timer, BSTP_LINK_TIMER);
1879         }
1880
1881         LIST_FOREACH(bp, &bs->bs_bplist, bp_next) {
1882                 /* no events need to happen for these */
1883                 bstp_timer_expired(&bp->bp_tc_timer);
1884                 bstp_timer_expired(&bp->bp_recent_root_timer);
1885                 bstp_timer_expired(&bp->bp_forward_delay_timer);
1886                 bstp_timer_expired(&bp->bp_recent_backup_timer);
1887
1888                 if (bstp_timer_expired(&bp->bp_hello_timer))
1889                         bstp_hello_timer_expiry(bs, bp);
1890
1891                 if (bstp_timer_expired(&bp->bp_message_age_timer))
1892                         bstp_message_age_expiry(bs, bp);
1893
1894                 if (bstp_timer_expired(&bp->bp_migrate_delay_timer))
1895                         bstp_migrate_delay_expiry(bs, bp);
1896
1897                 if (bstp_timer_expired(&bp->bp_edge_delay_timer))
1898                         bstp_edge_delay_expiry(bs, bp);
1899
1900                 /* update the various state machines for the port */
1901                 bstp_update_state(bs, bp);
1902
1903                 if (bp->bp_txcount > 0)
1904                         bp->bp_txcount--;
1905         }
1906
1907         callout_reset(&bs->bs_bstpcallout, hz, bstp_tick, bs);
1908 }
1909
1910 static void
1911 bstp_timer_start(struct bstp_timer *t, uint16_t v)
1912 {
1913         t->value = v;
1914         t->active = 1;
1915         t->latched = 0;
1916 }
1917
1918 static void
1919 bstp_timer_stop(struct bstp_timer *t)
1920 {
1921         t->value = 0;
1922         t->active = 0;
1923         t->latched = 0;
1924 }
1925
1926 static void
1927 bstp_timer_latch(struct bstp_timer *t)
1928 {
1929         t->latched = 1;
1930         t->active = 1;
1931 }
1932
1933 static int
1934 bstp_timer_expired(struct bstp_timer *t)
1935 {
1936         if (t->active == 0 || t->latched)
1937                 return (0);
1938         t->value -= BSTP_TICK_VAL;
1939         if (t->value <= 0) {
1940                 bstp_timer_stop(t);
1941                 return (1);
1942         }
1943         return (0);
1944 }
1945
1946 static void
1947 bstp_hello_timer_expiry(struct bstp_state *bs, struct bstp_port *bp)
1948 {
1949         if ((bp->bp_flags & BSTP_PORT_NEWINFO) ||
1950             bp->bp_role == BSTP_ROLE_DESIGNATED ||
1951             (bp->bp_role == BSTP_ROLE_ROOT &&
1952              bp->bp_tc_timer.active == 1)) {
1953                 bstp_timer_start(&bp->bp_hello_timer, bp->bp_desg_htime);
1954                 bp->bp_flags |= BSTP_PORT_NEWINFO;
1955                 bstp_transmit(bs, bp);
1956         }
1957 }
1958
1959 static void
1960 bstp_message_age_expiry(struct bstp_state *bs, struct bstp_port *bp)
1961 {
1962         if (bp->bp_infois == BSTP_INFO_RECEIVED) {
1963                 bp->bp_infois = BSTP_INFO_AGED;
1964                 bstp_assign_roles(bs);
1965                 DPRINTF("aged info on %s\n", bp->bp_ifp->if_xname);
1966         }
1967 }
1968
1969 static void
1970 bstp_migrate_delay_expiry(struct bstp_state *bs, struct bstp_port *bp)
1971 {
1972         bp->bp_flags |= BSTP_PORT_CANMIGRATE;
1973 }
1974
1975 static void
1976 bstp_edge_delay_expiry(struct bstp_state *bs, struct bstp_port *bp)
1977 {
1978         if ((bp->bp_flags & BSTP_PORT_AUTOEDGE) &&
1979             bp->bp_protover == BSTP_PROTO_RSTP && bp->bp_proposing &&
1980             bp->bp_role == BSTP_ROLE_DESIGNATED) {
1981                 bp->bp_operedge = 1;
1982                 DPRINTF("%s -> edge port\n", bp->bp_ifp->if_xname);
1983         }
1984 }
1985
1986 static int
1987 bstp_addr_cmp(const uint8_t *a, const uint8_t *b)
1988 {
1989         int i, d;
1990
1991         for (i = 0, d = 0; i < ETHER_ADDR_LEN && d == 0; i++) {
1992                 d = ((int)a[i]) - ((int)b[i]);
1993         }
1994
1995         return (d);
1996 }
1997
1998 /*
1999  * compare the bridge address component of the bridgeid
2000  */
2001 static int
2002 bstp_same_bridgeid(uint64_t id1, uint64_t id2)
2003 {
2004         u_char addr1[ETHER_ADDR_LEN];
2005         u_char addr2[ETHER_ADDR_LEN];
2006
2007         PV2ADDR(id1, addr1);
2008         PV2ADDR(id2, addr2);
2009
2010         if (bstp_addr_cmp(addr1, addr2) == 0)
2011                 return (1);
2012
2013         return (0);
2014 }
2015
2016 void
2017 bstp_reinit(struct bstp_state *bs)
2018 {
2019         struct bstp_port *bp;
2020         struct ifnet *ifp, *mif;
2021         u_char *e_addr;
2022         static const u_char llzero[ETHER_ADDR_LEN];     /* 00:00:00:00:00:00 */
2023
2024         BSTP_LOCK_ASSERT(bs);
2025
2026         mif = NULL;
2027         /*
2028          * Search through the Ethernet adapters and find the one with the
2029          * lowest value. The adapter which we take the MAC address from does
2030          * not need to be part of the bridge, it just needs to be a unique
2031          * value.
2032          */
2033         IFNET_RLOCK();
2034         TAILQ_FOREACH(ifp, &ifnet, if_link) {
2035                 if (ifp->if_type != IFT_ETHER)
2036                         continue;
2037
2038                 if (bstp_addr_cmp(IF_LLADDR(ifp), llzero) == 0)
2039                         continue;
2040
2041                 if (mif == NULL) {
2042                         mif = ifp;
2043                         continue;
2044                 }
2045                 if (bstp_addr_cmp(IF_LLADDR(ifp), IF_LLADDR(mif)) < 0) {
2046                         mif = ifp;
2047                         continue;
2048                 }
2049         }
2050         IFNET_RUNLOCK();
2051
2052         if (LIST_EMPTY(&bs->bs_bplist) || mif == NULL) {
2053                 /* Set the bridge and root id (lower bits) to zero */
2054                 bs->bs_bridge_pv.pv_dbridge_id =
2055                     ((uint64_t)bs->bs_bridge_priority) << 48;
2056                 bs->bs_bridge_pv.pv_root_id = bs->bs_bridge_pv.pv_dbridge_id;
2057                 bs->bs_root_pv = bs->bs_bridge_pv;
2058                 /* Disable any remaining ports, they will have no MAC address */
2059                 LIST_FOREACH(bp, &bs->bs_bplist, bp_next) {
2060                         bp->bp_infois = BSTP_INFO_DISABLED;
2061                         bstp_set_port_role(bp, BSTP_ROLE_DISABLED);
2062                 }
2063                 callout_stop(&bs->bs_bstpcallout);
2064                 return;
2065         }
2066
2067         e_addr = IF_LLADDR(mif);
2068         bs->bs_bridge_pv.pv_dbridge_id =
2069             (((uint64_t)bs->bs_bridge_priority) << 48) |
2070             (((uint64_t)e_addr[0]) << 40) |
2071             (((uint64_t)e_addr[1]) << 32) |
2072             (((uint64_t)e_addr[2]) << 24) |
2073             (((uint64_t)e_addr[3]) << 16) |
2074             (((uint64_t)e_addr[4]) << 8) |
2075             (((uint64_t)e_addr[5]));
2076
2077         bs->bs_bridge_pv.pv_root_id = bs->bs_bridge_pv.pv_dbridge_id;
2078         bs->bs_bridge_pv.pv_cost = 0;
2079         bs->bs_bridge_pv.pv_dport_id = 0;
2080         bs->bs_bridge_pv.pv_port_id = 0;
2081
2082         if (bs->bs_running && callout_pending(&bs->bs_bstpcallout) == 0)
2083                 callout_reset(&bs->bs_bstpcallout, hz, bstp_tick, bs);
2084
2085         LIST_FOREACH(bp, &bs->bs_bplist, bp_next) {
2086                 bp->bp_port_id = (bp->bp_priority << 8) |
2087                     (bp->bp_ifp->if_index  & 0xfff);
2088                 bstp_ifupdstatus(bs, bp);
2089         }
2090
2091         bstp_assign_roles(bs);
2092         bstp_timer_start(&bs->bs_link_timer, BSTP_LINK_TIMER);
2093 }
2094
2095 static int
2096 bstp_modevent(module_t mod, int type, void *data)
2097 {
2098         switch (type) {
2099         case MOD_LOAD:
2100                 mtx_init(&bstp_list_mtx, "bridgestp list", NULL, MTX_DEF);
2101                 LIST_INIT(&bstp_list);
2102                 bstp_linkstate_p = bstp_linkstate;
2103                 break;
2104         case MOD_UNLOAD:
2105                 bstp_linkstate_p = NULL;
2106                 mtx_destroy(&bstp_list_mtx);
2107                 break;
2108         default:
2109                 return (EOPNOTSUPP);
2110         }
2111         return (0);
2112 }
2113
2114 static moduledata_t bstp_mod = {
2115         "bridgestp",
2116         bstp_modevent,
2117         0
2118 };
2119
2120 DECLARE_MODULE(bridgestp, bstp_mod, SI_SUB_PSEUDO, SI_ORDER_ANY);
2121 MODULE_VERSION(bridgestp, 1);
2122
2123 void
2124 bstp_attach(struct bstp_state *bs, struct bstp_cb_ops *cb)
2125 {
2126         BSTP_LOCK_INIT(bs);
2127         callout_init_mtx(&bs->bs_bstpcallout, &bs->bs_mtx, 0);
2128         LIST_INIT(&bs->bs_bplist);
2129
2130         bs->bs_bridge_max_age = BSTP_DEFAULT_MAX_AGE;
2131         bs->bs_bridge_htime = BSTP_DEFAULT_HELLO_TIME;
2132         bs->bs_bridge_fdelay = BSTP_DEFAULT_FORWARD_DELAY;
2133         bs->bs_bridge_priority = BSTP_DEFAULT_BRIDGE_PRIORITY;
2134         bs->bs_hold_time = BSTP_DEFAULT_HOLD_TIME;
2135         bs->bs_migration_delay = BSTP_DEFAULT_MIGRATE_DELAY;
2136         bs->bs_txholdcount = BSTP_DEFAULT_HOLD_COUNT;
2137         bs->bs_protover = BSTP_PROTO_RSTP;
2138         bs->bs_state_cb = cb->bcb_state;
2139         bs->bs_rtage_cb = cb->bcb_rtage;
2140
2141         getmicrotime(&bs->bs_last_tc_time);
2142
2143         mtx_lock(&bstp_list_mtx);
2144         LIST_INSERT_HEAD(&bstp_list, bs, bs_list);
2145         mtx_unlock(&bstp_list_mtx);
2146 }
2147
2148 void
2149 bstp_detach(struct bstp_state *bs)
2150 {
2151         KASSERT(LIST_EMPTY(&bs->bs_bplist), ("bstp still active"));
2152
2153         mtx_lock(&bstp_list_mtx);
2154         LIST_REMOVE(bs, bs_list);
2155         mtx_unlock(&bstp_list_mtx);
2156         callout_drain(&bs->bs_bstpcallout);
2157         BSTP_LOCK_DESTROY(bs);
2158 }
2159
2160 void
2161 bstp_init(struct bstp_state *bs)
2162 {
2163         BSTP_LOCK(bs);
2164         callout_reset(&bs->bs_bstpcallout, hz, bstp_tick, bs);
2165         bs->bs_running = 1;
2166         bstp_reinit(bs);
2167         BSTP_UNLOCK(bs);
2168 }
2169
2170 void
2171 bstp_stop(struct bstp_state *bs)
2172 {
2173         struct bstp_port *bp;
2174
2175         BSTP_LOCK(bs);
2176
2177         LIST_FOREACH(bp, &bs->bs_bplist, bp_next)
2178                 bstp_set_port_state(bp, BSTP_IFSTATE_DISCARDING);
2179
2180         bs->bs_running = 0;
2181         callout_stop(&bs->bs_bstpcallout);
2182         BSTP_UNLOCK(bs);
2183 }
2184
2185 int
2186 bstp_create(struct bstp_state *bs, struct bstp_port *bp, struct ifnet *ifp)
2187 {
2188         bzero(bp, sizeof(struct bstp_port));
2189
2190         BSTP_LOCK(bs);
2191         bp->bp_ifp = ifp;
2192         bp->bp_bs = bs;
2193         bp->bp_priority = BSTP_DEFAULT_PORT_PRIORITY;
2194         TASK_INIT(&bp->bp_statetask, 0, bstp_notify_state, bp);
2195         TASK_INIT(&bp->bp_rtagetask, 0, bstp_notify_rtage, bp);
2196
2197         /* Init state */
2198         bp->bp_infois = BSTP_INFO_DISABLED;
2199         bp->bp_flags = BSTP_PORT_AUTOEDGE|BSTP_PORT_AUTOPTP;
2200         bstp_set_port_state(bp, BSTP_IFSTATE_DISCARDING);
2201         bstp_set_port_proto(bp, bs->bs_protover);
2202         bstp_set_port_role(bp, BSTP_ROLE_DISABLED);
2203         bstp_set_port_tc(bp, BSTP_TCSTATE_INACTIVE);
2204         bp->bp_path_cost = bstp_calc_path_cost(bp);
2205         BSTP_UNLOCK(bs);
2206         return (0);
2207 }
2208
2209 int
2210 bstp_enable(struct bstp_port *bp)
2211 {
2212         struct bstp_state *bs = bp->bp_bs;
2213         struct ifnet *ifp = bp->bp_ifp;
2214
2215         KASSERT(bp->bp_active == 0, ("already a bstp member"));
2216
2217         switch (ifp->if_type) {
2218                 case IFT_ETHER: /* These can do spanning tree. */
2219                         break;
2220                 default:
2221                         /* Nothing else can. */
2222                         return (EINVAL);
2223         }
2224
2225         BSTP_LOCK(bs);
2226         LIST_INSERT_HEAD(&bs->bs_bplist, bp, bp_next);
2227         bp->bp_active = 1;
2228         bp->bp_flags |= BSTP_PORT_NEWINFO;
2229         bstp_reinit(bs);
2230         bstp_update_roles(bs, bp);
2231         BSTP_UNLOCK(bs);
2232         return (0);
2233 }
2234
2235 void
2236 bstp_disable(struct bstp_port *bp)
2237 {
2238         struct bstp_state *bs = bp->bp_bs;
2239
2240         KASSERT(bp->bp_active == 1, ("not a bstp member"));
2241
2242         BSTP_LOCK(bs);
2243         bstp_disable_port(bs, bp);
2244         LIST_REMOVE(bp, bp_next);
2245         bp->bp_active = 0;
2246         bstp_reinit(bs);
2247         BSTP_UNLOCK(bs);
2248 }
2249
2250 /*
2251  * The bstp_port structure is about to be freed by the parent bridge.
2252  */
2253 void
2254 bstp_destroy(struct bstp_port *bp)
2255 {
2256         KASSERT(bp->bp_active == 0, ("port is still attached"));
2257         taskqueue_drain(taskqueue_swi, &bp->bp_statetask);
2258         taskqueue_drain(taskqueue_swi, &bp->bp_rtagetask);
2259 }