Add support for 802.1D spanning tree protocol.

NOTE: this requires recompiling brconfig with updated include files.

6 files changed, 1617 insertions, 102 deletions

diff --git a/sys/conf/files b/sys/conf/files
index 639d057c205..58cae074312 100644
--- a/sys/conf/files
+++ b/sys/conf/files
@@ -1,4 +1,4 @@
-#	$OpenBSD: files,v 1.180 2000/11/16 20:02:21 provos Exp $
+#	$OpenBSD: files,v 1.181 2000/12/12 03:41:22 jason Exp $
 #	$NetBSD: files,v 1.87 1996/05/19 17:17:50 jonathan Exp $
 
 #	@(#)files.newconf	7.5 (Berkeley) 5/10/93
@@ -502,6 +502,7 @@ file net/zlib.c				ppp_deflate
 file net/if_tokensubr.c			token			needs-flag
 file net/if_tun.c			tun			needs-count
 file net/if_bridge.c			bridge			needs-count
+file net/bridgestp.c			bridge
 file net/if_vlan.c			vlan			needs-count
 file net/radix.c
 file net/raw_cb.c
diff --git a/sys/net/bridgestp.c b/sys/net/bridgestp.c
new file mode 100644
index 00000000000..14a4e4a02be
--- /dev/null
+++ b/sys/net/bridgestp.c
@@ -0,0 +1,1294 @@
+/*	$OpenBSD: bridgestp.c,v 1.1 2000/12/12 03:41:22 jason Exp $	*/
+
+/*
+ * Copyright (c) 2000 Jason L. Wright (jason@thought.net)
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ * 3. All advertising materials mentioning features or use of this software
+ *    must display the following acknowledgement:
+ *      This product includes software developed by Jason L. Wright
+ * 4. The name of the author may not be used to endorse or promote products
+ *    derived from this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
+ * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+ * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ * DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT,
+ * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+ * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
+ * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ */
+
+/*
+ * Implementation of the spanning tree protocol as defined in
+ * ISO/IEC Final DIS 15802-3 (IEEE P802.1D/D17), May 25, 1998.
+ * (In English: IEEE 802.1D, Draft 17, 1998)
+ */
+
+#include "bridge.h"
+
+#if NBRIDGE > 0
+
+#include <sys/param.h>
+#include <sys/systm.h>
+#include <sys/mbuf.h>
+#include <sys/socket.h>
+#include <sys/ioctl.h>
+#include <sys/device.h>
+#include <sys/kernel.h>
+
+#include <net/if.h>
+#include <net/if_types.h>
+#include <net/if_llc.h>
+#include <net/if_media.h>
+#include <net/route.h>
+#include <net/netisr.h>
+
+#ifdef INET
+#include <netinet/in.h>
+#include <netinet/in_systm.h>
+#include <netinet/in_var.h>
+#include <netinet/ip.h>
+#include <netinet/if_ether.h>
+
+#ifdef IPFILTER
+#include <netinet/ip_fil_compat.h>
+#include <netinet/ip_fil.h>
+#endif
+#endif
+
+#if NBPFILTER > 0
+#include <net/bpf.h>
+#endif
+
+#include <net/if_bridge.h>
+
+/* BPDU message types */
+#define	BSTP_MSGTYPE_CFG	0x00		/* Configuration */
+#define	BSTP_MSGTYPE_TCN	0x80		/* Topology chg notification */
+
+/* BPDU flags */
+#define	BSTP_FLAG_TC		0x01		/* Topology change */
+#define	BSTP_FLAG_TCA		0x80		/* Topology change ack */
+
+#define	BSTP_MESSAGE_AGE_INCR	(1 * 256)	/* in 256ths of a second */
+#define	BSTP_TICK_VAL		(1 * 256)	/* in 256ths of a second */
+
+/*
+ * Because BPDU's do not make nicely aligned structures, two different
+ * declarations are used: bstp_?bpdu (wire representation, packed) and
+ * bstp_*_unit (internal, nicely aligned version).
+ */
+
+/* configuration bridge protocol data unit */
+struct bstp_cbpdu {
+	u_int8_t	cbu_dsap;		/* LLC: destination sap */
+	u_int8_t	cbu_ssap;		/* LLC: source sap */
+	u_int8_t	cbu_ctl;		/* LLC: control */
+	u_int16_t	cbu_protoid;		/* protocol id */
+	u_int8_t	cbu_protover;		/* protocol version */
+	u_int8_t	cbu_bpdutype;		/* message type */
+	u_int8_t	cbu_flags;		/* flags (below) */
+
+	/* root id */
+	u_int16_t	cbu_rootpri;		/* root priority */
+	u_int8_t	cbu_rootaddr[6];	/* root address */
+
+	u_int32_t	cbu_rootpathcost;	/* root path cost */
+
+	/* bridge id */
+	u_int16_t	cbu_bridgepri;		/* bridge priority */
+	u_int8_t	cbu_bridgeaddr[6];	/* bridge address */
+
+	u_int16_t	cbu_portid;		/* port id */
+	u_int16_t	cbu_messageage;		/* current message age */
+	u_int16_t	cbu_maxage;		/* maximum age */
+	u_int16_t	cbu_hellotime;		/* hello time */
+	u_int16_t	cbu_forwarddelay;	/* forwarding delay */
+} __attribute__((__packed__));
+
+/* topology change notification bridge protocol data unit */
+struct bstp_tbpdu {
+	u_int8_t	tbu_dsap;		/* LLC: destination sap */
+	u_int8_t	tbu_ssap;		/* LLC: source sap */
+	u_int8_t	tbu_ctl;		/* LLC: control */
+	u_int16_t	tbu_protoid;		/* protocol id */
+	u_int8_t	tbu_protover;		/* protocol version */
+	u_int8_t	tbu_bpdutype;		/* message type */
+} __attribute__((__packed__));
+
+u_int8_t bstp_etheraddr[] = { 0x01, 0x80, 0xc2, 0x00, 0x00, 0x00 };
+
+void bstp_initialization __P((struct bridge_softc *));
+void bstp_stop __P((struct bridge_softc *));
+void bstp_initialize_port __P((struct bridge_softc *, struct bridge_iflist *));
+void bstp_ifupdstatus __P((struct bridge_softc *, struct bridge_iflist *));
+void bstp_enable_port __P((struct bridge_softc *, struct bridge_iflist *));
+void bstp_disable_port __P((struct bridge_softc *, struct bridge_iflist *));
+void bstp_enable_change_detection __P((struct bridge_iflist *));
+void bstp_disable_change_detection __P((struct bridge_iflist *));
+int bstp_root_bridge __P((struct bridge_softc *sc));
+int bstp_supersedes_port_info __P((struct bridge_softc *, struct bridge_iflist *, struct bstp_config_unit *));
+int bstp_designated_port __P((struct bridge_softc *, struct bridge_iflist *));
+int bstp_designated_for_some_port __P((struct bridge_softc *));
+void bstp_transmit_config __P((struct bridge_softc *, struct bridge_iflist *));
+void bstp_transmit_tcn __P((struct bridge_softc *));
+struct mbuf *bstp_input __P((struct bridge_softc *, struct ifnet *,
+    struct ether_header *, struct mbuf *));
+void bstp_received_config_bpdu __P((struct bridge_softc *, struct bridge_iflist *, struct bstp_config_unit *));
+void bstp_received_tcn_bpdu __P((struct bridge_softc *, struct bridge_iflist *, struct bstp_tcn_unit *));
+void bstp_record_config_information __P((struct bridge_softc *, struct bridge_iflist *, struct bstp_config_unit *));
+void bstp_record_config_timeout_values __P((struct bridge_softc *, struct bstp_config_unit *));
+void bstp_config_bpdu_generation __P((struct bridge_softc *));
+void bstp_send_config_bpdu __P((struct bridge_iflist *, struct bstp_config_unit *));
+void bstp_send_tcn_bpdu __P((struct bridge_softc *, struct bridge_iflist *, struct bstp_tcn_unit *));
+void bstp_configuration_update __P((struct bridge_softc *));
+void bstp_root_selection __P((struct bridge_softc *));
+void bstp_designated_port_selection __P((struct bridge_softc *));
+void bstp_become_designated_port __P((struct bridge_softc *, struct bridge_iflist *));
+void bstp_port_state_selection __P((struct bridge_softc *));
+void bstp_make_forwarding __P((struct bridge_softc *, struct bridge_iflist *));
+void bstp_make_blocking __P((struct bridge_softc *, struct bridge_iflist *));
+void bstp_set_port_state __P((struct bridge_iflist *, u_int8_t));
+void bstp_set_bridge_priority __P((struct bridge_softc *, u_int64_t));
+void bstp_set_port_priority __P((struct bridge_softc *, struct bridge_iflist *, u_int16_t));
+void bstp_set_path_cost __P((struct bridge_softc *, struct bridge_iflist *, u_int32_t));
+void bstp_topology_change_detection __P((struct bridge_softc *));
+void bstp_topology_change_acknowledged __P((struct bridge_softc *));
+void bstp_acknowledge_topology_change __P((struct bridge_softc *, struct bridge_iflist *));
+
+void bstp_tick __P((void *));
+void bstp_timer_start __P((struct bridge_timer *, u_int16_t));
+void bstp_timer_stop __P((struct bridge_timer *));
+int bstp_timer_expired __P((struct bridge_timer *, u_int16_t));
+
+void bstp_hold_timer_expiry __P((struct bridge_softc *, struct bridge_iflist *));
+void bstp_message_age_timer_expiry __P((struct bridge_softc *, struct bridge_iflist *));
+void bstp_forward_delay_timer_expiry __P((struct bridge_softc *, struct bridge_iflist *));
+void bstp_topology_change_timer_expiry __P((struct bridge_softc *));
+void bstp_tcn_timer_expiry __P((struct bridge_softc *));
+void bstp_hello_timer_expiry __P((struct bridge_softc *));
+
+void
+bstp_transmit_config(sc, bif)
+	struct bridge_softc *sc;
+	struct bridge_iflist *bif;
+{
+	if (bif->bif_hold_timer.active) {
+		bif->bif_config_pending = 1;
+		return;
+	}
+
+	bif->bif_config_bpdu.cu_message_type = BSTP_MSGTYPE_CFG;
+	bif->bif_config_bpdu.cu_rootid = sc->sc_designated_root;
+	bif->bif_config_bpdu.cu_root_path_cost = sc->sc_root_path_cost;
+	bif->bif_config_bpdu.cu_bridge_id = sc->sc_bridge_id;
+	bif->bif_config_bpdu.cu_port_id = bif->bif_port_id;
+
+	if (bstp_root_bridge(sc))
+		bif->bif_config_bpdu.cu_message_age = 0;
+	else
+		bif->bif_config_bpdu.cu_message_age =
+		    sc->sc_root_port->bif_message_age_timer.value +
+		    BSTP_MESSAGE_AGE_INCR;
+
+	bif->bif_config_bpdu.cu_max_age = sc->sc_max_age;
+	bif->bif_config_bpdu.cu_hello_time = sc->sc_hello_time;
+	bif->bif_config_bpdu.cu_forward_delay = sc->sc_forward_delay;
+	bif->bif_config_bpdu.cu_topology_change_acknowledgment
+	    = bif->bif_topology_change_acknowledge;
+	bif->bif_config_bpdu.cu_topology_change = sc->sc_topology_change;
+
+	if (bif->bif_config_bpdu.cu_message_age < sc->sc_max_age) {
+		bif->bif_topology_change_acknowledge = 0;
+		bif->bif_config_pending = 0;
+		bstp_send_config_bpdu(bif, &bif->bif_config_bpdu);
+		bstp_timer_start(&bif->bif_hold_timer, 0);
+	}
+}
+
+void
+bstp_send_config_bpdu(bif, cu)
+	struct bridge_iflist *bif;
+	struct bstp_config_unit *cu;
+{
+	struct arpcom *arp;
+	struct ifnet *ifp;
+	struct mbuf *m;
+	struct ether_header eh;
+	struct bstp_cbpdu bpdu;
+	int s;
+
+	s = splimp();
+	ifp = bif->ifp;
+	arp = (struct arpcom *)ifp;
+
+	if ((ifp->if_flags & IFF_RUNNING) == 0) {
+		splx(s);
+		return;
+	}
+	if (IF_QFULL(&ifp->if_snd)) {
+		splx(s);
+		return;
+	}
+
+	MGETHDR(m, M_DONTWAIT, MT_DATA);
+	if (m == NULL) {
+		splx(s);
+		return;
+	}
+	m->m_pkthdr.rcvif = ifp;
+	m->m_pkthdr.len = sizeof(eh) + sizeof(bpdu);
+	m->m_len = m->m_pkthdr.len;
+
+	bpdu.cbu_ssap = bpdu.cbu_dsap = LLC_8021D_LSAP;
+	bpdu.cbu_ctl = LLC_UI;
+	bpdu.cbu_protoid = htons(0);
+	bpdu.cbu_protover = 0;
+	bpdu.cbu_bpdutype = cu->cu_message_type;
+	bpdu.cbu_flags = (cu->cu_topology_change ? BSTP_FLAG_TC : 0) |
+	    (cu->cu_topology_change_acknowledgment ? BSTP_FLAG_TCA : 0);
+
+	bpdu.cbu_rootpri = htons(cu->cu_rootid >> 48);
+	bpdu.cbu_rootaddr[0] = cu->cu_rootid >> 40;
+	bpdu.cbu_rootaddr[1] = cu->cu_rootid >> 32;
+	bpdu.cbu_rootaddr[2] = cu->cu_rootid >> 24;
+	bpdu.cbu_rootaddr[3] = cu->cu_rootid >> 16;
+	bpdu.cbu_rootaddr[4] = cu->cu_rootid >> 8;
+	bpdu.cbu_rootaddr[5] = cu->cu_rootid >> 0;
+
+	bpdu.cbu_rootpathcost = htonl(cu->cu_root_path_cost);
+
+	bpdu.cbu_bridgepri = htons(cu->cu_rootid >> 48);
+	bpdu.cbu_bridgeaddr[0] = cu->cu_rootid >> 40;
+	bpdu.cbu_bridgeaddr[1] = cu->cu_rootid >> 32;
+	bpdu.cbu_bridgeaddr[2] = cu->cu_rootid >> 24;
+	bpdu.cbu_bridgeaddr[3] = cu->cu_rootid >> 16;
+	bpdu.cbu_bridgeaddr[4] = cu->cu_rootid >> 8;
+	bpdu.cbu_bridgeaddr[5] = cu->cu_rootid >> 0;
+
+	bpdu.cbu_portid = htons(cu->cu_port_id);
+	bpdu.cbu_messageage = htons(cu->cu_message_age);
+	bpdu.cbu_maxage = htons(cu->cu_max_age);
+	bpdu.cbu_hellotime = htons(cu->cu_hello_time);
+	bpdu.cbu_forwarddelay = htons(cu->cu_forward_delay);
+
+	bcopy(arp->ac_enaddr, eh.ether_shost, ETHER_ADDR_LEN);
+	bcopy(bstp_etheraddr, eh.ether_dhost, ETHER_ADDR_LEN);
+	eh.ether_type = htons(sizeof(bpdu));
+
+	bcopy(&eh, m->m_data, sizeof(eh));
+	bcopy(&bpdu, m->m_data + sizeof(eh), sizeof(bpdu));
+
+	IF_ENQUEUE(&ifp->if_snd, m);
+	if ((ifp->if_flags & IFF_OACTIVE) == 0)
+		(*ifp->if_start)(ifp);
+	splx(s);
+}
+
+int
+bstp_root_bridge(sc)
+	struct bridge_softc *sc;
+{
+	return (sc->sc_designated_root == sc->sc_bridge_id);
+}
+
+int
+bstp_supersedes_port_info(sc, bif, cu)
+	struct bridge_softc *sc;
+	struct bridge_iflist *bif;
+	struct bstp_config_unit *cu;
+{
+	if (cu->cu_rootid < bif->bif_designated_root)
+		return (1);
+	if (cu->cu_rootid > bif->bif_designated_root)
+		return (0);
+
+	if (cu->cu_root_path_cost < bif->bif_designated_cost)
+		return (1);
+	if (cu->cu_root_path_cost > bif->bif_designated_cost)
+		return (0);
+
+	if (cu->cu_bridge_id < bif->bif_designated_bridge)
+		return (1);
+	if (cu->cu_bridge_id > bif->bif_designated_bridge)
+		return (0);
+
+	if (sc->sc_bridge_id != cu->cu_bridge_id)
+		return (1);
+	if (cu->cu_port_id <= bif->bif_designated_port)
+		return (1);
+	return (0);
+}
+
+void
+bstp_record_config_information(sc, bif, cu)
+	struct bridge_softc *sc;
+	struct bridge_iflist *bif;
+	struct bstp_config_unit *cu;
+{
+	bif->bif_designated_root = cu->cu_rootid;
+	bif->bif_designated_cost = cu->cu_root_path_cost;
+	bif->bif_designated_bridge = cu->cu_bridge_id;
+	bif->bif_designated_port = cu->cu_port_id;
+	bstp_timer_start(&bif->bif_message_age_timer, cu->cu_message_age);
+}
+
+void
+bstp_record_config_timeout_values(sc, config)
+	struct bridge_softc *sc;
+	struct bstp_config_unit *config;
+{
+	sc->sc_max_age = config->cu_max_age;
+	sc->sc_hello_time = config->cu_hello_time;
+	sc->sc_forward_delay = config->cu_forward_delay;
+	sc->sc_topology_change = config->cu_topology_change;
+}
+
+void
+bstp_config_bpdu_generation(sc)
+	struct bridge_softc *sc;
+{
+	struct bridge_iflist *bif;
+
+	LIST_FOREACH(bif, &sc->sc_iflist, next) {
+		if (!(bif->bif_flags & IFBIF_STP))
+			continue;
+		if (bstp_designated_port(sc, bif) &&
+		    (bif->bif_state != BSTP_IFSTATE_DISABLED))
+			bstp_transmit_config(sc, bif);
+	}
+}
+
+int
+bstp_designated_port(sc, bif)
+	struct bridge_softc *sc;
+	struct bridge_iflist *bif;
+{
+	return ((bif->bif_designated_bridge == sc->sc_bridge_id)
+	    && (bif->bif_designated_port == bif->bif_port_id));
+}
+
+void
+bstp_transmit_tcn(sc)
+	struct bridge_softc *sc;
+{
+	struct bridge_iflist *bif;
+
+	bif = sc->sc_root_port;
+	bif->bif_tcn_bpdu.tu_message_type = BSTP_MSGTYPE_TCN;
+	bstp_send_tcn_bpdu(sc, bif, &bif->bif_tcn_bpdu);
+}
+
+void
+bstp_send_tcn_bpdu(sc, bif, tu)
+	struct bridge_softc *sc;
+	struct bridge_iflist *bif;
+	struct bstp_tcn_unit *tu;
+{
+	struct arpcom *arp;
+	struct ifnet *ifp;
+	struct mbuf *m;
+	struct ether_header eh;
+	struct bstp_tbpdu bpdu;
+	int s;
+
+	s = splimp();
+	ifp = bif->ifp;
+	arp = (struct arpcom *)ifp;
+
+	if ((ifp->if_flags & IFF_RUNNING) == 0) {
+		splx(s);
+		return;
+	}
+	if (IF_QFULL(&ifp->if_snd)) {
+		splx(s);
+		return;
+	}
+
+	MGETHDR(m, M_DONTWAIT, MT_DATA);
+	if (m == NULL) {
+		splx(s);
+		return;
+	}
+	m->m_pkthdr.rcvif = ifp;
+	m->m_pkthdr.len = sizeof(eh) + sizeof(bpdu);
+	m->m_len = m->m_pkthdr.len;
+
+	bpdu.tbu_ssap = bpdu.tbu_dsap = LLC_8021D_LSAP;
+	bpdu.tbu_ctl = LLC_UI;
+	bpdu.tbu_protoid = 0;
+	bpdu.tbu_protover = 0;
+	bpdu.tbu_bpdutype = tu->tu_message_type;
+
+	bcopy(arp->ac_enaddr, eh.ether_shost, ETHER_ADDR_LEN);
+	bcopy(bstp_etheraddr, eh.ether_dhost, ETHER_ADDR_LEN);
+	eh.ether_type = htons(sizeof(bpdu));
+
+	bcopy(&eh, m->m_data, sizeof(eh));
+	bcopy(&bpdu, m->m_data + sizeof(eh), sizeof(bpdu));
+
+	IF_ENQUEUE(&ifp->if_snd, m);
+	if ((ifp->if_flags & IFF_OACTIVE) == 0)
+		(*ifp->if_start)(ifp);
+	splx(s);
+}
+
+void
+bstp_configuration_update(sc)
+	struct bridge_softc *sc;
+{
+	bstp_root_selection(sc);
+	bstp_designated_port_selection(sc);
+}
+
+void
+bstp_root_selection(sc)
+	struct bridge_softc *sc;
+{
+	struct bridge_iflist *root_port = NULL, *bif;
+
+	LIST_FOREACH(bif, &sc->sc_iflist, next) {
+		if (!(bif->bif_flags & IFBIF_STP))
+			continue;
+		if (bstp_designated_port(sc, bif))
+			continue;
+		if (bif->bif_state == BSTP_IFSTATE_DISABLED)
+			continue;
+		if (bif->bif_designated_root >= sc->sc_bridge_id)
+			continue;
+		if (root_port == NULL)
+			goto set_port;
+
+		if (bif->bif_designated_root < root_port->bif_designated_root)
+			goto set_port;
+		if (bif->bif_designated_root > root_port->bif_designated_root)
+			continue;
+
+		if ((bif->bif_designated_cost + bif->bif_path_cost) <
+		    (root_port->bif_designated_cost + root_port->bif_path_cost))
+			goto set_port;
+		if ((bif->bif_designated_cost + bif->bif_path_cost) >
+		    (root_port->bif_designated_cost + root_port->bif_path_cost))
+			continue;
+
+		if (bif->bif_designated_bridge < root_port->bif_designated_bridge)
+			goto set_port;
+		if (bif->bif_designated_bridge > root_port->bif_designated_bridge)
+			continue;
+
+		if (bif->bif_designated_port < root_port->bif_designated_port)
+			goto set_port;
+		if (bif->bif_designated_port > root_port->bif_designated_port)
+			continue;
+
+		if (bif->bif_port_id >= root_port->bif_port_id)
+			continue;
+set_port:
+		root_port = bif;
+	}
+
+	sc->sc_root_port = root_port;
+	if (root_port == NULL) {
+		sc->sc_designated_root = sc->sc_bridge_id;
+		sc->sc_root_path_cost = 0;
+	} else {
+		sc->sc_designated_root = root_port->bif_designated_root;
+		sc->sc_root_path_cost = root_port->bif_designated_cost +
+		    root_port->bif_path_cost;
+	}
+}
+
+void
+bstp_designated_port_selection(sc)
+	struct bridge_softc *sc;
+{
+	struct bridge_iflist *bif;
+
+	LIST_FOREACH(bif, &sc->sc_iflist, next) {
+		if (!(bif->bif_flags & IFBIF_STP))
+			continue;
+		if (bstp_designated_port(sc, bif))
+			goto designated;
+		if (bif->bif_designated_root != sc->sc_designated_root)
+			goto designated;
+
+		if (sc->sc_root_path_cost < bif->bif_designated_cost)
+			goto designated;
+		if (sc->sc_root_path_cost > bif->bif_designated_cost)
+			continue;
+
+		if (sc->sc_bridge_id < bif->bif_designated_bridge)
+			goto designated;
+		if (sc->sc_bridge_id > bif->bif_designated_bridge)
+			continue;
+
+		if (bif->bif_port_id > bif->bif_designated_port)
+			continue;
+designated:
+		bstp_become_designated_port(sc, bif);
+	}
+}
+
+void
+bstp_become_designated_port(sc, bif)
+	struct bridge_softc *sc;
+	struct bridge_iflist *bif;
+{
+	bif->bif_designated_root = sc->sc_designated_root;
+	bif->bif_designated_cost = sc->sc_root_path_cost;
+	bif->bif_designated_bridge = sc->sc_bridge_id;
+	bif->bif_designated_port = bif->bif_port_id;
+}
+
+void
+bstp_port_state_selection(sc)
+	struct bridge_softc *sc;
+{
+	struct bridge_iflist *bif;
+
+	LIST_FOREACH(bif, &sc->sc_iflist, next) {
+		if (!(bif->bif_flags & IFBIF_STP))
+			continue;
+		if (bif == sc->sc_root_port) {
+			bif->bif_config_pending = 0;
+			bif->bif_topology_change_acknowledge = 0;
+			bstp_make_forwarding(sc, bif);
+		} else if (bstp_designated_port(sc, bif)) {
+			bstp_timer_stop(&bif->bif_message_age_timer);
+			bstp_make_forwarding(sc, bif);
+		} else {
+			bif->bif_config_pending = 0;
+			bif->bif_topology_change_acknowledge = 0;
+			bstp_make_blocking(sc, bif);
+		}
+	}
+}
+
+void
+bstp_make_forwarding(sc, bif)
+	struct bridge_softc *sc;
+	struct bridge_iflist *bif;
+{
+	if (bif->bif_state == BSTP_IFSTATE_BLOCKING) {
+		bstp_set_port_state(bif, BSTP_IFSTATE_LISTENING);
+		bstp_timer_start(&bif->bif_forward_delay_timer, 0);
+	}
+}
+
+void
+bstp_make_blocking(sc, bif)
+	struct bridge_softc *sc;
+	struct bridge_iflist *bif;
+{
+	if ((bif->bif_state != BSTP_IFSTATE_DISABLED) &&
+	    (bif->bif_state != BSTP_IFSTATE_BLOCKING)) {
+		if ((bif->bif_state == BSTP_IFSTATE_FORWARDING) ||
+		    (bif->bif_state == BSTP_IFSTATE_LEARNING)) {
+			if (bif->bif_change_detection_enabled) {
+				bstp_topology_change_detection(sc);
+			}
+		}
+		bstp_set_port_state(bif, BSTP_IFSTATE_BLOCKING);
+		bstp_timer_stop(&bif->bif_forward_delay_timer);
+	}
+}
+
+void
+bstp_set_port_state(bif, state)
+	struct bridge_iflist *bif;
+	u_int8_t state;
+{
+	bif->bif_state = state;
+}
+
+void
+bstp_topology_change_detection(sc)
+	struct bridge_softc *sc;
+{
+	if (bstp_root_bridge(sc)) {
+		sc->sc_topology_change = 1;
+		bstp_timer_start(&sc->sc_topology_change_timer, 0);
+	} else if (!sc->sc_topology_change_detected) {
+		bstp_transmit_tcn(sc);
+		bstp_timer_start(&sc->sc_tcn_timer, 0);
+	}
+	sc->sc_topology_change_detected = 1;
+}
+
+void
+bstp_topology_change_acknowledged(sc)
+	struct bridge_softc *sc;
+{
+	sc->sc_topology_change_detected = 0;
+	bstp_timer_stop(&sc->sc_tcn_timer);
+}
+
+void
+bstp_acknowledge_topology_change(sc, bif)
+	struct bridge_softc *sc;
+	struct bridge_iflist *bif;
+{
+	bif->bif_topology_change_acknowledge = 1;
+	bstp_transmit_config(sc, bif);
+}
+
+struct mbuf *
+bstp_input(sc, ifp, eh, m)
+	struct bridge_softc *sc;
+	struct ifnet *ifp;
+	struct ether_header *eh;
+	struct mbuf *m;
+{
+	struct bridge_iflist *bif = NULL;
+	struct bstp_tbpdu tpdu;
+	struct bstp_cbpdu cpdu;
+	struct bstp_config_unit cu;
+	struct bstp_tcn_unit tu;
+	u_int16_t len;
+
+	LIST_FOREACH(bif, &sc->sc_iflist, next) {
+		if (!(bif->bif_flags & IFBIF_STP))
+			continue;
+		if (bif->ifp == ifp)
+			break;
+	}
+	if (bif == NULL)
+		goto out;
+
+	len = ntohs(eh->ether_type);
+	if (len < sizeof(tpdu))
+		goto out;
+	if (m->m_pkthdr.len > len)
+		m_adj(m, len - m->m_pkthdr.len);
+	if ((m = m_pullup(m, sizeof(tpdu))) == NULL)
+		goto out;
+	bcopy(mtod(m, struct tpdu *), &tpdu, sizeof(tpdu));
+
+	if (tpdu.tbu_dsap != LLC_8021D_LSAP ||
+	    tpdu.tbu_ssap != LLC_8021D_LSAP ||
+	    tpdu.tbu_ctl != LLC_UI)
+		goto out;
+	if (tpdu.tbu_protoid != 0 || tpdu.tbu_protover != 0)
+		goto out;
+
+	switch (tpdu.tbu_bpdutype) {
+	case BSTP_MSGTYPE_TCN:
+		tu.tu_message_type = tpdu.tbu_bpdutype;
+		bstp_received_tcn_bpdu(sc, bif, &tu);
+		break;
+	case BSTP_MSGTYPE_CFG:
+		if ((m = m_pullup(m, sizeof(cpdu))) == NULL)
+			goto out;
+		bcopy(mtod(m, struct bstp_cpdu *), &cpdu, sizeof(cpdu));
+
+		cu.cu_rootid =
+		    (((u_int64_t)ntohs(cpdu.cbu_rootpri)) << 48) |
+		    (((u_int64_t)cpdu.cbu_rootaddr[0]) << 40) |
+		    (((u_int64_t)cpdu.cbu_rootaddr[1]) << 32) |
+		    (((u_int64_t)cpdu.cbu_rootaddr[2]) << 24) |
+		    (((u_int64_t)cpdu.cbu_rootaddr[3]) << 16) |
+		    (((u_int64_t)cpdu.cbu_rootaddr[4]) << 8) |
+		    (((u_int64_t)cpdu.cbu_rootaddr[5]) << 0);
+		    
+		cu.cu_bridge_id =
+		    (((u_int64_t)ntohs(cpdu.cbu_bridgepri)) << 48) |
+		    (((u_int64_t)cpdu.cbu_bridgeaddr[0]) << 40) |
+		    (((u_int64_t)cpdu.cbu_bridgeaddr[1]) << 32) |
+		    (((u_int64_t)cpdu.cbu_bridgeaddr[2]) << 24) |
+		    (((u_int64_t)cpdu.cbu_bridgeaddr[3]) << 16) |
+		    (((u_int64_t)cpdu.cbu_bridgeaddr[4]) << 8) |
+		    (((u_int64_t)cpdu.cbu_bridgeaddr[5]) << 0);
+
+		cu.cu_root_path_cost = ntohl(cpdu.cbu_rootpathcost);
+		cu.cu_message_age = ntohs(cpdu.cbu_messageage);
+		cu.cu_max_age = ntohs(cpdu.cbu_maxage);
+		cu.cu_hello_time = ntohs(cpdu.cbu_hellotime);
+		cu.cu_forward_delay = ntohs(cpdu.cbu_forwarddelay);
+		cu.cu_port_id = ntohs(cpdu.cbu_portid);
+		cu.cu_message_type = cpdu.cbu_bpdutype;
+		cu.cu_topology_change_acknowledgment =
+		    (cpdu.cbu_flags & BSTP_FLAG_TCA) ? 1 : 0;
+		cu.cu_topology_change =
+		    (cpdu.cbu_flags & BSTP_FLAG_TC) ? 1 : 0;
+		bstp_received_config_bpdu(sc, bif, &cu);
+		break;
+	default:
+		goto out;
+	}
+
+out:
+	if (m)
+		m_freem(m);
+	return (NULL);
+}
+
+void
+bstp_received_config_bpdu(sc, bif, cu)
+	struct bridge_softc *sc;
+	struct bridge_iflist *bif;
+	struct bstp_config_unit *cu;
+{
+	int root;
+
+	root = bstp_root_bridge(sc);
+
+	if (bif->bif_state != BSTP_IFSTATE_DISABLED) {
+		if (bstp_supersedes_port_info(sc, bif, cu)) {
+			bstp_record_config_information(sc, bif, cu);
+			bstp_configuration_update(sc);
+			bstp_port_state_selection(sc);
+
+			if ((!bstp_root_bridge(sc)) && root) {
+				bstp_timer_stop(&sc->sc_hello_timer);
+
+				if (sc->sc_topology_change_detected) {
+					bstp_timer_stop(&sc->sc_topology_change_timer);
+					bstp_transmit_tcn(sc);
+					bstp_timer_start(&sc->sc_tcn_timer, 0);
+				}
+			}
+
+			if (bif == sc->sc_root_port) {
+				bstp_record_config_timeout_values(sc, cu);
+				bstp_config_bpdu_generation(sc);
+
+				if (cu->cu_topology_change_acknowledgment)
+					bstp_topology_change_acknowledged(sc);
+			}
+		}
+		else if (bstp_designated_port(sc, bif))
+			bstp_transmit_config(sc, bif);
+	}
+}
+
+void
+bstp_received_tcn_bpdu(sc, bif, tcn)
+	struct bridge_softc *sc;
+	struct bridge_iflist *bif;
+	struct bstp_tcn_unit *tcn;
+{
+	if (bif->bif_state != BSTP_IFSTATE_DISABLED &&
+	    bstp_designated_port(sc, bif)) {
+			bstp_topology_change_detection(sc);
+			bstp_acknowledge_topology_change(sc, bif);
+	}
+}
+
+void
+bstp_hello_timer_expiry(sc)
+	struct bridge_softc *sc;
+{
+	bstp_config_bpdu_generation(sc);
+	bstp_timer_start(&sc->sc_hello_timer, 0);
+}
+
+void
+bstp_message_age_timer_expiry(sc, bif)
+	struct bridge_softc *sc;
+	struct bridge_iflist *bif;
+{
+	int root;
+
+	root = bstp_root_bridge(sc);
+	bstp_become_designated_port(sc, bif);
+	bstp_configuration_update(sc);
+	bstp_port_state_selection(sc);
+
+	if ((bstp_root_bridge(sc)) && (!root)) {
+		sc->sc_max_age = sc->sc_bridge_max_age;
+		sc->sc_hello_time = sc->sc_bridge_hello_time;
+		sc->sc_forward_delay = sc->sc_bridge_forward_delay;
+
+		bstp_topology_change_detection(sc);
+		bstp_timer_stop(&sc->sc_tcn_timer);
+		bstp_config_bpdu_generation(sc);
+		bstp_timer_start(&sc->sc_hello_timer, 0);
+	}
+}
+
+void
+bstp_forward_delay_timer_expiry(sc, bif)
+	struct bridge_softc *sc;
+	struct bridge_iflist *bif;
+{
+	if (bif->bif_state == BSTP_IFSTATE_LISTENING) {
+		bstp_set_port_state(bif, BSTP_IFSTATE_LEARNING);
+		bstp_timer_start(&bif->bif_forward_delay_timer, 0);
+	} else if (bif->bif_state == BSTP_IFSTATE_LEARNING) {
+		bstp_set_port_state(bif, BSTP_IFSTATE_FORWARDING);
+		if (bstp_designated_for_some_port(sc) &&
+		    bif->bif_change_detection_enabled)
+			bstp_topology_change_detection(sc);
+	}
+}
+
+int
+bstp_designated_for_some_port(sc)
+	struct bridge_softc *sc;
+{
+
+	struct bridge_iflist *bif;
+
+	LIST_FOREACH(bif, &sc->sc_iflist, next) {
+		if (!(bif->bif_flags & IFBIF_STP))
+			continue;
+		if (bif->bif_designated_bridge == sc->sc_bridge_id)
+			return (1);
+	}
+	return (0);
+}
+
+void
+bstp_tcn_timer_expiry(sc)
+	struct bridge_softc *sc;
+{
+	bstp_transmit_tcn(sc);
+	bstp_timer_start(&sc->sc_tcn_timer, 0);
+}
+
+void
+bstp_topology_change_timer_expiry(sc)
+	struct bridge_softc *sc;
+{
+	sc->sc_topology_change_detected = 0;
+	sc->sc_topology_change = 0;
+}
+
+void
+bstp_hold_timer_expiry(sc, bif)
+	struct bridge_softc *sc;
+	struct bridge_iflist *bif;
+{
+	if (bif->bif_config_pending)
+		bstp_transmit_config(sc, bif);
+}
+
+void
+bstp_initialization(sc)
+	struct bridge_softc *sc;
+{
+	struct bridge_iflist *bif, *mif;
+	struct arpcom *ac, *mac;
+
+	mif = NULL; mac = NULL;
+	LIST_FOREACH(bif, &sc->sc_iflist, next) {
+		if (!(bif->bif_flags & IFBIF_STP))
+			continue;
+		if (bif->ifp->if_type != IFT_ETHER)
+			continue;
+		bif->bif_port_id = (bif->bif_priority << 8) |
+		    (bif->ifp->if_index & 0xff);
+
+		if (mif == NULL) {
+			mif = bif;
+			mac = (struct arpcom *)bif->ifp;
+			continue;
+		}
+		ac = (struct arpcom *)bif->ifp;
+		if (memcmp(ac->ac_enaddr, mac->ac_enaddr, ETHER_ADDR_LEN) < 0) {
+			mif = bif;
+			mac = (struct arpcom *)bif->ifp;
+			continue;
+		}
+	}
+	if (mif == NULL) {
+		bstp_stop(sc);
+		return;
+	}
+
+	sc->sc_bridge_id =
+	    (((u_int64_t)sc->sc_bridge_priority) << 48) |
+	    (((u_int64_t)mac->ac_enaddr[0]) << 40) |
+	    (((u_int64_t)mac->ac_enaddr[1]) << 32) |
+	    (mac->ac_enaddr[2] << 24) | (mac->ac_enaddr[3] << 16) |
+	    (mac->ac_enaddr[4] << 8) | (mac->ac_enaddr[5]);
+
+	sc->sc_designated_root = sc->sc_bridge_id;
+	sc->sc_root_path_cost = 0;
+	sc->sc_root_port = NULL;
+
+	sc->sc_max_age = sc->sc_bridge_max_age;
+	sc->sc_hello_time = sc->sc_bridge_hello_time;
+	sc->sc_forward_delay = sc->sc_bridge_forward_delay;
+	sc->sc_topology_change_detected = 0;
+	sc->sc_topology_change = 0;
+	bstp_timer_stop(&sc->sc_tcn_timer);
+	bstp_timer_stop(&sc->sc_topology_change_timer);
+
+	if (!timeout_initialized(&sc->sc_bstptimeout))
+		timeout_set(&sc->sc_bstptimeout, bstp_tick, sc);
+	if (!timeout_pending(&sc->sc_bstptimeout))
+		timeout_add(&sc->sc_bstptimeout, hz);
+
+	LIST_FOREACH(bif, &sc->sc_iflist, next) {
+		if (bif->bif_flags & IFBIF_STP)
+			bstp_enable_port(sc, bif);
+		else
+			bstp_disable_port(sc, bif);
+	}
+
+	bstp_port_state_selection(sc);
+	bstp_config_bpdu_generation(sc);
+	bstp_timer_start(&sc->sc_hello_timer, 0);
+}
+
+void
+bstp_stop(sc)
+	struct bridge_softc *sc;
+{
+
+	struct bridge_iflist *bif;
+
+	LIST_FOREACH(bif, &sc->sc_iflist, next) {
+		bstp_set_port_state(bif, BSTP_IFSTATE_DISABLED);
+		bstp_timer_stop(&bif->bif_hold_timer);
+		bstp_timer_stop(&bif->bif_message_age_timer);
+		bstp_timer_stop(&bif->bif_forward_delay_timer);
+	}
+
+	if (timeout_initialized(&sc->sc_bstptimeout) &&
+	    timeout_pending(&sc->sc_bstptimeout))
+		timeout_del(&sc->sc_bstptimeout);
+
+	bstp_timer_stop(&sc->sc_topology_change_timer);
+	bstp_timer_stop(&sc->sc_tcn_timer);
+	bstp_timer_stop(&sc->sc_hello_timer);
+
+}
+
+void
+bstp_initialize_port(sc, bif)
+	struct bridge_softc *sc;
+	struct bridge_iflist *bif;
+{
+	bstp_become_designated_port(sc, bif);
+	bstp_set_port_state(bif, BSTP_IFSTATE_BLOCKING);
+	bif->bif_topology_change_acknowledge = 0;
+	bif->bif_config_pending = 0;
+	bif->bif_change_detection_enabled = 1;
+	bstp_timer_stop(&bif->bif_message_age_timer);
+	bstp_timer_stop(&bif->bif_forward_delay_timer);
+	bstp_timer_stop(&bif->bif_hold_timer);
+}
+
+void
+bstp_enable_port(sc, bif)
+	struct bridge_softc *sc;
+	struct bridge_iflist *bif;
+{
+	bstp_initialize_port(sc, bif);
+	bstp_port_state_selection(sc);
+}
+
+void
+bstp_disable_port(sc, bif)
+	struct bridge_softc *sc;
+	struct bridge_iflist *bif;
+{
+	int root;
+
+	root = bstp_root_bridge(sc);
+	bstp_become_designated_port(sc, bif);
+	bstp_set_port_state(bif, BSTP_IFSTATE_DISABLED);
+	bif->bif_topology_change_acknowledge = 0;
+	bif->bif_config_pending = 0;
+	bstp_timer_stop(&bif->bif_message_age_timer);
+	bstp_timer_stop(&bif->bif_forward_delay_timer);
+	bstp_configuration_update(sc);
+	bstp_port_state_selection(sc);
+
+	if (bstp_root_bridge(sc) && (!root))	{
+		sc->sc_max_age = sc->sc_bridge_max_age;
+		sc->sc_hello_time = sc->sc_bridge_hello_time;
+		sc->sc_forward_delay = sc->sc_bridge_forward_delay;
+
+		bstp_topology_change_detection(sc);
+		bstp_timer_stop(&sc->sc_tcn_timer);
+		bstp_config_bpdu_generation(sc);
+		bstp_timer_start(&sc->sc_hello_timer, 0);
+	}
+}
+
+void
+bstp_set_bridge_priority(sc, new_bridge_id)
+	struct bridge_softc *sc;
+	u_int64_t new_bridge_id;
+{
+	int root;
+	struct bridge_iflist *bif;
+
+	root = bstp_root_bridge(sc);
+
+	LIST_FOREACH(bif, &sc->sc_iflist, next) {
+		if (!(bif->bif_flags & IFBIF_STP))
+			continue;
+		if (bstp_designated_port(sc, bif))
+			bif->bif_designated_bridge = new_bridge_id;
+	}
+
+	sc->sc_bridge_id = new_bridge_id;
+
+	bstp_configuration_update(sc);
+	bstp_port_state_selection(sc);
+
+	if (bstp_root_bridge(sc) && (!root)) {
+		sc->sc_max_age = sc->sc_bridge_max_age;
+		sc->sc_hello_time = sc->sc_bridge_hello_time;
+		sc->sc_forward_delay = sc->sc_bridge_forward_delay;
+
+		bstp_topology_change_detection(sc);
+		bstp_timer_stop(&sc->sc_tcn_timer);
+		bstp_config_bpdu_generation(sc);
+		bstp_timer_start(&sc->sc_hello_timer, 0);
+	}
+}
+
+void
+bstp_set_port_priority(sc, bif, new_port_id)
+	struct bridge_softc *sc;
+	struct bridge_iflist *bif;
+	u_int16_t new_port_id;
+{
+	if (bstp_designated_port(sc, bif))
+		bif->bif_designated_port = new_port_id;
+
+	bif->bif_port_id = new_port_id;
+
+	if ((sc->sc_bridge_id == bif->bif_designated_bridge) &&
+	    (bif->bif_port_id < bif->bif_designated_port)) {
+		bstp_become_designated_port(sc, bif);
+		bstp_port_state_selection(sc);
+	}
+}
+
+void
+bstp_set_path_cost(sc, bif, path_cost)
+	struct bridge_softc *sc;
+	struct bridge_iflist *bif;
+	u_int32_t path_cost;
+{
+	bif->bif_path_cost = path_cost;
+	bstp_configuration_update(sc);
+	bstp_port_state_selection(sc);
+}
+
+void
+bstp_enable_change_detection(bif)
+	struct bridge_iflist *bif;
+{
+	bif->bif_change_detection_enabled = 1;
+}
+
+void
+bstp_disable_change_detection(bif)
+	struct bridge_iflist *bif;
+{
+	bif->bif_change_detection_enabled = 0;
+}
+
+void
+bstp_ifupdstatus(sc, bif)
+	struct bridge_softc *sc;
+	struct bridge_iflist *bif;
+{
+	struct ifnet *ifp = bif->ifp;
+	struct ifmediareq ifmr;
+	int err;
+
+	if (ifp->if_flags & IFF_UP) {
+		ifmr.ifm_count = 0;
+		err = (*ifp->if_ioctl)(ifp, SIOCGIFMEDIA, (caddr_t)&ifmr);
+		if (err) {
+			if (bif->bif_state == BSTP_IFSTATE_DISABLED)
+				bstp_enable_port(sc, bif);
+			return;
+		}
+
+		if (!(ifmr.ifm_status & IFM_AVALID)) {
+			if (bif->bif_state == BSTP_IFSTATE_DISABLED)
+				bstp_enable_port(sc, bif);
+			return;
+		}
+
+		if (ifmr.ifm_status & IFM_ACTIVE) {
+			if (bif->bif_state == BSTP_IFSTATE_DISABLED)
+				bstp_enable_port(sc, bif);
+			return;
+		}
+
+		if (bif->bif_state != BSTP_IFSTATE_DISABLED)
+			bstp_disable_port(sc, bif);
+
+		return;
+	}
+
+	if (bif->bif_state != BSTP_IFSTATE_DISABLED)
+		bstp_disable_port(sc, bif);
+}
+
+void
+bstp_tick(vsc)
+	void *vsc;
+{
+	struct bridge_softc *sc = vsc;
+	struct bridge_iflist *bif;
+	int s;
+
+	s = splnet();
+
+	LIST_FOREACH(bif, &sc->sc_iflist, next) {
+		if (!(bif->bif_flags & IFBIF_STP))
+			continue;
+		bstp_ifupdstatus(sc, bif);
+	}
+
+	if (bstp_timer_expired(&sc->sc_hello_timer, sc->sc_hello_time))
+		bstp_hello_timer_expiry(sc);
+
+	if (bstp_timer_expired(&sc->sc_tcn_timer, sc->sc_bridge_hello_time))
+		bstp_tcn_timer_expiry(sc);
+
+	if (bstp_timer_expired(&sc->sc_topology_change_timer,
+	    sc->sc_topology_change_time))
+		bstp_topology_change_timer_expiry(sc);
+
+	LIST_FOREACH(bif, &sc->sc_iflist, next) {
+		if (!(bif->bif_flags & IFBIF_STP))
+			continue;
+		if (bstp_timer_expired(&bif->bif_message_age_timer,
+		    sc->sc_max_age))
+			bstp_message_age_timer_expiry(sc, bif);
+	}
+
+	LIST_FOREACH(bif, &sc->sc_iflist, next) {
+		if (!(bif->bif_flags & IFBIF_STP))
+			continue;
+		if (bstp_timer_expired(&bif->bif_forward_delay_timer,
+		    sc->sc_forward_delay))
+			bstp_forward_delay_timer_expiry(sc, bif);
+
+		if (bstp_timer_expired(&bif->bif_hold_timer,
+		    sc->sc_hold_time))
+			bstp_hold_timer_expiry(sc, bif);
+	}
+
+	if (sc->sc_if.if_flags & IFF_RUNNING)
+		timeout_add(&sc->sc_bstptimeout, hz);
+
+	splx(s);
+}
+
+void
+bstp_timer_start(t, v)
+	struct bridge_timer *t;
+	u_int16_t v;
+{
+	t->value = v;
+	t->active = 1;
+}
+
+void
+bstp_timer_stop(t)
+	struct bridge_timer *t;
+{
+	t->value = 0;
+	t->active = 0;
+}
+
+int
+bstp_timer_expired(t, v)
+	struct bridge_timer *t;
+	u_int16_t v;
+{
+	if (!t->active)
+		return (0);
+	t->value += BSTP_TICK_VAL;
+	if (t->value >= v) {
+		bstp_timer_stop(t);
+		return (1);
+	}
+	return (0);
+
+}
+
+int
+bstp_ioctl(ifp, cmd, data)
+	struct ifnet *ifp;
+	u_long cmd;
+	caddr_t	data;
+{
+	struct bridge_softc *sc = (struct bridge_softc *)ifp;
+	struct ifbrparam *bp = (struct ifbrparam *)data;
+	int r = 0, err = 0;
+
+	switch (cmd) {
+	case SIOCBRDGGPRI:
+		bp->ifbrp_prio = sc->sc_bridge_priority;
+		break;
+	case SIOCBRDGGMA:
+		bp->ifbrp_maxage = sc->sc_bridge_max_age >> 8;
+		break;
+	case SIOCBRDGGHT:
+		bp->ifbrp_hellotime = sc->sc_bridge_hello_time >> 8;
+		break;
+	case SIOCBRDGGFD:
+		bp->ifbrp_fwddelay = sc->sc_bridge_forward_delay >> 8;
+		break;
+	case SIOCBRDGSPRI:
+		sc->sc_bridge_priority = bp->ifbrp_prio;
+		r = 1;
+		break;
+	case SIOCBRDGSMA:
+		if (bp->ifbrp_maxage == 0) {
+			err = EINVAL;
+			break;
+		}
+		sc->sc_bridge_max_age = bp->ifbrp_maxage << 8;
+		r = 1;
+		break;
+	case SIOCBRDGSHT:
+		if (bp->ifbrp_hellotime == 0) {
+			err = EINVAL;
+			break;
+		}
+		sc->sc_bridge_hello_time = bp->ifbrp_hellotime << 8;
+		r = 1;
+		break;
+	case SIOCBRDGSFD:
+		if (bp->ifbrp_fwddelay == 0) {
+			err = EINVAL;
+			break;
+		}
+		sc->sc_bridge_forward_delay = bp->ifbrp_fwddelay << 8;
+		r = 1;
+		break;
+	case SIOCBRDGADD:
+	case SIOCBRDGDEL:
+	case SIOCBRDGSIFFLGS:
+	case SIOCBRDGSIFPRIO:
+		r = 1;
+		break;
+	default:
+		break;
+	}
+
+	if (r)
+		bstp_initialization(sc);
+
+	return (err);
+}
+
+#endif /* NBRIDGE */
diff --git a/sys/net/if_bridge.c b/sys/net/if_bridge.c
index 54c9e275ff4..383fee5c449 100644
--- a/sys/net/if_bridge.c
+++ b/sys/net/if_bridge.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: if_bridge.c,v 1.42 2000/11/10 05:24:58 jason Exp $	*/
+/*	$OpenBSD: if_bridge.c,v 1.43 2000/12/12 03:41:22 jason Exp $	*/
 
 /*
  * Copyright (c) 1999, 2000 Jason L. Wright (jason@thought.net)
@@ -83,68 +83,28 @@
 /*
  * Maximum number of addresses to cache
  */
-#ifndef BRIDGE_RTABLE_MAX
-#define BRIDGE_RTABLE_MAX	100
+#ifndef	BRIDGE_RTABLE_MAX
+#define	BRIDGE_RTABLE_MAX	100
 #endif
 
+/* spanning tree defaults */
+#define	BSTP_DEFAULT_MAX_AGE		(20 * 256)
+#define	BSTP_DEFAULT_HELLO_TIME		(2 * 256)
+#define	BSTP_DEFAULT_FORWARD_DELAY	(15 * 256)
+#define	BSTP_DEFAULT_HOLD_TIME		(1 * 256)
+#define	BSTP_DEFAULT_BRIDGE_PRIORITY	0x8000
+#define	BSTP_DEFAULT_PORT_PRIORITY	0x80
+#define	BSTP_DEFAULT_PATH_COST		55
+
 /*
  * Timeout (in seconds) for entries learned dynamically
  */
-#ifndef BRIDGE_RTABLE_TIMEOUT
-#define BRIDGE_RTABLE_TIMEOUT	240
+#ifndef	BRIDGE_RTABLE_TIMEOUT
+#define	BRIDGE_RTABLE_TIMEOUT	240
 #endif
 
 extern int ifqmaxlen;
 
-/*
- * Bridge filtering rules
- */
-SIMPLEQ_HEAD(brl_head, brl_node);
-
-struct brl_node {
-	SIMPLEQ_ENTRY(brl_node)	brl_next;	/* next rule */
-	struct ether_addr	brl_src;	/* source mac address */
-	struct ether_addr	brl_dst;	/* destination mac address */
-	u_int8_t		brl_action;	/* what to do with match */
-	u_int8_t		brl_flags;	/* comparision flags */
-};
-
-/*
- * Bridge interface list
- */
-struct bridge_iflist {
-	LIST_ENTRY(bridge_iflist)	next;		/* next in list */
-	struct brl_head			bif_brlin;	/* input rules */
-	struct brl_head			bif_brlout;	/* output rules */
-	struct				ifnet *ifp;	/* member interface */
-	u_int32_t			bif_flags;	/* member flags */
-};
-
-/*
- * Bridge route node
- */
-struct bridge_rtnode {
-	LIST_ENTRY(bridge_rtnode)	brt_next;	/* next in list */
-	struct				ifnet *brt_if;	/* destination ifs */
-	u_int8_t			brt_flags;	/* address flags */
-	u_int8_t			brt_age;	/* age counter */
-	struct				ether_addr brt_addr;	/* dst addr */
-};
-
-/*
- * Software state for each bridge
- */
-struct bridge_softc {
-	struct				ifnet sc_if;	/* the interface */
-	u_int32_t			sc_brtmax;	/* max # addresses */
-	u_int32_t			sc_brtcnt;	/* current # addrs */
-	u_int32_t			sc_brttimeout;	/* timeout ticks */
-	u_int32_t			sc_hashkey;	/* hash key */
-	struct timeout			sc_brtimeout;	/* timeout state */
-	LIST_HEAD(, bridge_iflist)	sc_iflist;	/* interface list */
-	LIST_HEAD(bridge_rthead, bridge_rtnode)	*sc_rts;/* hash table */
-};
-
 struct bridge_softc bridgectl[NBRIDGE];
 
 void	bridgeattach __P((int));
@@ -205,6 +165,11 @@ bridgeattach(unused)
 
 		sc->sc_brtmax = BRIDGE_RTABLE_MAX;
 		sc->sc_brttimeout = BRIDGE_RTABLE_TIMEOUT;
+		sc->sc_bridge_max_age = BSTP_DEFAULT_MAX_AGE;
+		sc->sc_bridge_hello_time = BSTP_DEFAULT_HELLO_TIME;
+		sc->sc_bridge_forward_delay= BSTP_DEFAULT_FORWARD_DELAY;
+		sc->sc_bridge_priority = BSTP_DEFAULT_BRIDGE_PRIORITY;
+		sc->sc_hold_time = BSTP_DEFAULT_HOLD_TIME;
 		timeout_set(&sc->sc_brtimeout, bridge_timer, sc);
 		LIST_INIT(&sc->sc_iflist);
 		ifp = &sc->sc_if;
@@ -237,16 +202,15 @@ bridge_ioctl(ifp, cmd, data)
 	struct ifbreq *req = (struct ifbreq *)data;
 	struct ifbaconf *baconf = (struct ifbaconf *)data;
 	struct ifbareq *bareq = (struct ifbareq *)data;
-	struct ifbcachereq *bcachereq = (struct ifbcachereq *)data;
+	struct ifbrparam *bparam = (struct ifbrparam *)data;
 	struct ifbifconf *bifconf = (struct ifbifconf *)data;
-	struct ifbcachetoreq *bcacheto = (struct ifbcachetoreq *)data;
 	struct ifbrlreq *brlreq = (struct ifbrlreq *)data;
 	struct ifbrlconf *brlconf = (struct ifbrlconf *)data;
 	struct ifreq ifreq;
 	int error = 0, s;
 	struct bridge_iflist *p;
 
-	s = splsoftnet();
+	s = splnet();
 	switch (cmd) {
 	case SIOCBRDGADD:
 		if ((error = suser(prc->p_ucred, &prc->p_acflag)) != 0)
@@ -325,9 +289,12 @@ bridge_ioctl(ifp, cmd, data)
 			error = ENOMEM;
 			break;
 		}
+		bzero(p, sizeof(struct bridge_iflist));
 
 		p->ifp = ifs;
 		p->bif_flags = IFBIF_LEARNING | IFBIF_DISCOVER;
+		p->bif_priority = BSTP_DEFAULT_PORT_PRIORITY;
+		p->bif_path_cost = BSTP_DEFAULT_PATH_COST;
 		SIMPLEQ_INIT(&p->bif_brlin);
 		SIMPLEQ_INIT(&p->bif_brlout);
 		LIST_INSERT_HEAD(&sc->sc_iflist, p, next);
@@ -378,6 +345,9 @@ bridge_ioctl(ifp, cmd, data)
 			break;
 		}
 		req->ifbr_ifsflags = p->bif_flags;
+		req->ifbr_state = p->bif_state;
+		req->ifbr_priority = p->bif_priority;
+		req->ifbr_portno = p->ifp->if_index & 0xff;
 		break;
 	case SIOCBRDGSIFFLGS:
 		if ((error = suser(prc->p_ucred, &prc->p_acflag)) != 0)
@@ -399,8 +369,35 @@ bridge_ioctl(ifp, cmd, data)
 			error = ESRCH;
 			break;
 		}
+		if ((req->ifbr_ifsflags & IFBIF_STP) &&
+		    (ifs->if_type != IFT_ETHER)) {
+			error = EINVAL;
+			break;
+		}
 		p->bif_flags = req->ifbr_ifsflags;
 		break;
+	case SIOCBRDGSIFPRIO:
+		if ((error = suser(prc->p_ucred, &prc->p_acflag)) != 0)
+			break;
+		ifs = ifunit(req->ifbr_ifsname);
+		if (ifs == NULL) {
+			error = ENOENT;
+			break;
+		}
+		if ((caddr_t)sc != ifs->if_bridge) {
+			error = ESRCH;
+			break;
+		}
+		LIST_FOREACH(p, &sc->sc_iflist, next) {
+			if (p->ifp == ifs)
+				break;
+		}
+		if (p == LIST_END(&sc->sc_iflist)) {
+			error = ESRCH;
+			break;
+		}
+		p->bif_priority = req->ifbr_priority;
+		break;
 	case SIOCBRDGRTS:
 		error = bridge_rtfind(sc, baconf);
 		break;
@@ -437,24 +434,24 @@ bridge_ioctl(ifp, cmd, data)
 		error = bridge_rtdaddr(sc, &bareq->ifba_dst);
 		break;
 	case SIOCBRDGGCACHE:
-		bcachereq->ifbc_size = sc->sc_brtmax;
+		bparam->ifbrp_csize = sc->sc_brtmax;
 		break;
 	case SIOCBRDGSCACHE:
 		if ((error = suser(prc->p_ucred, &prc->p_acflag)) != 0)
 			break;
-		sc->sc_brtmax = bcachereq->ifbc_size;
+		sc->sc_brtmax = bparam->ifbrp_csize;
 		bridge_rttrim(sc);
 		break;
 	case SIOCBRDGSTO:
 		if ((error = suser(prc->p_ucred, &prc->p_acflag)) != 0)
 			break;
-		sc->sc_brttimeout = bcacheto->ifbct_time;
+		sc->sc_brttimeout = bparam->ifbrp_ctime;
 		timeout_del(&sc->sc_brtimeout);
-		if (bcacheto->ifbct_time != 0)
+		if (bparam->ifbrp_ctime != 0)
 			timeout_add(&sc->sc_brtimeout, sc->sc_brttimeout * hz);
 		break;
 	case SIOCBRDGGTO:
-		bcacheto->ifbct_time = sc->sc_brttimeout;
+		bparam->ifbrp_ctime = sc->sc_brttimeout;
 		break;
 	case SIOCSIFFLAGS:
 		if ((ifp->if_flags & IFF_UP) == IFF_UP)
@@ -528,9 +525,24 @@ bridge_ioctl(ifp, cmd, data)
 	case SIOCBRDGGRL:
 		error = bridge_brlconf(sc, brlconf);
 		break;
+	case SIOCBRDGGPRI:
+	case SIOCBRDGGMA:
+	case SIOCBRDGGHT:
+	case SIOCBRDGGFD:
+		break;
+	case SIOCBRDGSPRI:
+	case SIOCBRDGSFD:
+	case SIOCBRDGSMA:
+	case SIOCBRDGSHT:
+		error = suser(prc->p_ucred, &prc->p_acflag);
+		break;
 	default:
 		error = EINVAL;
 	}
+
+	if (!error)
+		error = bstp_ioctl(ifp, cmd, data);
+
 	splx(s);
 	return (error);
 }
@@ -583,6 +595,9 @@ bridge_bifconf(sc, bifc)
 		    sizeof(breq.ifbr_ifsname)-1);
 		breq.ifbr_ifsname[sizeof(breq.ifbr_ifsname) - 1] = '\0';
 		breq.ifbr_ifsflags = p->bif_flags;
+		breq.ifbr_state = p->bif_state;
+		breq.ifbr_priority = p->bif_priority;
+		breq.ifbr_portno = p->ifp->if_index & 0xff;
 		error = copyout((caddr_t)&breq,
 		    (caddr_t)(bifc->ifbic_req + i), sizeof(breq));
 		if (error)
@@ -849,6 +864,9 @@ bridge_start(ifp)
 {
 }
 
+/*
+ * Loop through each bridge interface and process their input queues.
+ */
 void
 bridgeintr(void)
 {
@@ -870,7 +888,7 @@ bridgeintr(void)
 }
 
 /*
- * Loop through each bridge interface and process their input queues.
+ * Process a single frame.  Frame must be freed or queued before returning.
  */
 void
 bridgeintr_frame(sc, m)
@@ -908,6 +926,14 @@ bridgeintr_frame(sc, m)
 		return;
 	}
 
+	if ((ifl->bif_flags & IFBIF_STP) &&
+	    ((ifl->bif_state == BSTP_IFSTATE_BLOCKING) ||
+	     (ifl->bif_state == BSTP_IFSTATE_LISTENING) ||
+	     (ifl->bif_state == BSTP_IFSTATE_DISABLED))) {
+		m_freem(m);
+		return;
+	}
+
 	if (m->m_pkthdr.len < sizeof(eh)) {
 		m_freem(m);
 		return;
@@ -930,6 +956,17 @@ bridgeintr_frame(sc, m)
 	      eh.ether_shost[5] == 0))
 		bridge_rtupdate(sc, src, src_if, 0, IFBAF_DYNAMIC);
 
+	if ((ifl->bif_flags & IFBIF_STP) &&
+	    (ifl->bif_state == BSTP_IFSTATE_LEARNING)) {
+		m_freem(m);
+		return;
+	}
+
+	/*
+	 * At this point, the port either doesn't participate in stp or
+	 * it's in the forwarding state
+	 */
+
 	/*
 	 * If packet is unicast, destined for someone on "this"
 	 * side of the bridge, drop it.
@@ -1017,6 +1054,12 @@ bridgeintr_frame(sc, m)
 		m_freem(m);
 		return;
 	}
+	if ((ifl->bif_flags & IFBIF_STP) &&
+	    (ifl->bif_state == BSTP_IFSTATE_DISABLED ||
+	     ifl->bif_state == BSTP_IFSTATE_BLOCKING)) {
+		m_free(m);
+		return;
+	}
 	if (bridge_filterrule(&ifl->bif_brlout, &eh) == BRL_ACTION_BLOCK) {
 		m_freem(m);
 		return;
@@ -1070,7 +1113,31 @@ bridge_input(ifp, eh, m)
 	if ((sc->sc_if.if_flags & IFF_RUNNING) == 0)
 		return (m);
 
+	LIST_FOREACH(ifl, &sc->sc_iflist, next) {
+		if (ifl->ifp == ifp)
+			break;
+	}
+	if (ifl == LIST_END(&sc->sc_iflist))
+		return (m);
+
 	if (m->m_flags & (M_BCAST | M_MCAST)) {
+		/* Tap off 802.1D packets, they do not get forwarded */
+		if (bcmp(eh->ether_dhost, bstp_etheraddr, ETHER_ADDR_LEN) == 0) {
+			m = bstp_input(sc, ifp, eh, m);
+			if (m == NULL)
+				return (NULL);
+		}
+
+		/*
+		 * No need to queue frames for ifs in the blocking, disabled,
+		 *  or listening state
+		 */
+		if ((ifl->bif_flags & IFBIF_STP) &&
+		    ((ifl->bif_state == BSTP_IFSTATE_BLOCKING) ||
+		     (ifl->bif_state == BSTP_IFSTATE_LISTENING) ||
+		     (ifl->bif_state == BSTP_IFSTATE_DISABLED)))
+			return (m);
+
 		/*
 		 * make a copy of 'm' with 'eh' tacked on to the
 		 * beginning.  Return 'm' for local processing
@@ -1096,6 +1163,17 @@ bridge_input(ifp, eh, m)
 	}
 
 	/*
+	 * No need to queue frames for ifs in the blocking, disabled, or
+	 * listening state
+	 */
+	if ((ifl->bif_flags & IFBIF_STP) &&
+	    ((ifl->bif_state == BSTP_IFSTATE_BLOCKING) ||
+	     (ifl->bif_state == BSTP_IFSTATE_LISTENING) ||
+	     (ifl->bif_state == BSTP_IFSTATE_DISABLED)))
+		return (m);
+
+
+	/*
 	 * Unicast, make sure it's not for us.
 	 */
 	LIST_FOREACH(ifl, &sc->sc_iflist, next) {
@@ -1157,6 +1235,11 @@ bridge_broadcast(sc, ifp, eh, m)
 		if (dst_if->if_index == ifp->if_index)
 			continue;
 
+		if ((p->bif_flags & IFBIF_STP) &&
+		    (p->bif_state == BSTP_IFSTATE_BLOCKING ||
+		     p->bif_state == BSTP_IFSTATE_DISABLED))
+			continue;
+
 		if ((p->bif_flags & IFBIF_DISCOVER) == 0 &&
 		    (m->m_flags & (M_BCAST | M_MCAST)) == 0)
 			continue;
diff --git a/sys/net/if_bridge.h b/sys/net/if_bridge.h
index 209c6113752..8ed3a5462ea 100644
--- a/sys/net/if_bridge.h
+++ b/sys/net/if_bridge.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: if_bridge.h,v 1.12 2000/01/25 22:06:27 jason Exp $	*/
+/*	$OpenBSD: if_bridge.h,v 1.13 2000/12/12 03:41:22 jason Exp $	*/
 
 /*
  * Copyright (c) 1999, 2000 Jason L. Wright (jason@thought.net)
@@ -38,15 +38,26 @@ struct ifbreq {
 	char		ifbr_name[IFNAMSIZ];	/* bridge ifs name */
 	char		ifbr_ifsname[IFNAMSIZ];	/* member ifs name */
 	u_int32_t	ifbr_ifsflags;		/* member ifs flags */
+	u_int8_t	ifbr_state;		/* member stp state */
+	u_int8_t	ifbr_priority;		/* member stp priority */
+	u_int8_t	ifbr_portno;		/* member port number */
 };
 /* SIOCBRDGIFFLGS, SIOCBRDGIFFLGS */
-#define	IFBIF_LEARNING	0x1	/* ifs can learn */
-#define	IFBIF_DISCOVER	0x2	/* ifs sends packets w/unknown dest */
-#define IFBIF_BLOCKNONIP 0x04	/* ifs blocks non-IP/ARP traffic in/out */
+#define	IFBIF_LEARNING		0x01	/* ifs can learn */
+#define	IFBIF_DISCOVER		0x02	/* ifs sends packets w/unknown dest */
+#define	IFBIF_BLOCKNONIP 	0x04	/* ifs blocks non-IP/ARP in/out */
+#define	IFBIF_STP		0x08	/* ifs participates in spanning tree */
 /* SIOCBRDGFLUSH */
 #define	IFBF_FLUSHDYN	0x0	/* flush dynamic addresses only */
 #define	IFBF_FLUSHALL	0x1	/* flush all addresses from cache */
 
+/* port states */
+#define	BSTP_IFSTATE_DISABLED	0
+#define	BSTP_IFSTATE_LISTENING	1
+#define	BSTP_IFSTATE_LEARNING	2
+#define	BSTP_IFSTATE_FORWARDING	3
+#define	BSTP_IFSTATE_BLOCKING	4
+
 /*
  * Interface list structure
  */
@@ -87,21 +98,23 @@ struct ifbaconf {
 #define	ifbac_req	ifbac_ifbacu.ifbacu_req
 };
 
-/*
- * Bridge cache size get/set
- */
-struct ifbcachereq {
-	char			ifbc_name[IFNAMSIZ];	/* bridge ifs name */
-	u_int32_t		ifbc_size;		/* cache size */
-};
-
-/*
- * Bridge cache timeout get/set
- */
-struct ifbcachetoreq {
-	char			ifbct_name[IFNAMSIZ];	/* bridge ifs name */
-	u_int32_t		ifbct_time;		/* cache time (sec) */
+struct ifbrparam {
+	char			ifbrp_name[IFNAMSIZ];
+	union {
+		u_int32_t	ifbrpu_csize;		/* cache size */
+		u_int32_t	ifbrpu_ctime;		/* cache time (sec) */
+		u_int16_t	ifbrpu_prio;		/* bridge priority */
+		u_int8_t	ifbrpu_hellotime;	/* hello time (sec) */
+		u_int8_t	ifbrpu_fwddelay;	/* fwd delay (sec) */
+		u_int8_t	ifbrpu_maxage;		/* max age (sec) */
+	} ifbrp_ifbrpu;
 };
+#define	ifbrp_csize	ifbrp_ifbrpu.ifbrpu_csize
+#define	ifbrp_ctime	ifbrp_ifbrpu.ifbrpu_ctime
+#define	ifbrp_prio	ifbrp_ifbrpu.ifbrpu_prio
+#define	ifbrp_hellotime	ifbrp_ifbrpu.ifbrpu_hellotime
+#define	ifbrp_fwddelay	ifbrp_ifbrpu.ifbrpu_fwddelay
+#define	ifbrp_maxage	ifbrp_ifbrpu.ifbrpu_maxage
 
 /*
  * Bridge mac rules
@@ -134,9 +147,122 @@ struct ifbrlconf {
 };
 
 #ifdef _KERNEL
+/*
+ * Bridge filtering rules
+ */
+SIMPLEQ_HEAD(brl_head, brl_node);
+
+struct brl_node {
+	SIMPLEQ_ENTRY(brl_node)	brl_next;	/* next rule */
+	struct ether_addr	brl_src;	/* source mac address */
+	struct ether_addr	brl_dst;	/* destination mac address */
+	u_int8_t		brl_action;	/* what to do with match */
+	u_int8_t		brl_flags;	/* comparision flags */
+};
+
+struct bridge_timer {
+	u_int16_t active;
+	u_int16_t value;
+};
+
+struct bstp_config_unit {
+	u_int64_t	cu_rootid;
+	u_int64_t	cu_bridge_id;
+	u_int32_t	cu_root_path_cost;
+	u_int16_t	cu_message_age;
+	u_int16_t	cu_max_age;
+	u_int16_t	cu_hello_time;
+	u_int16_t	cu_forward_delay;
+	u_int16_t	cu_port_id;
+	u_int8_t	cu_message_type;
+	u_int8_t	cu_topology_change_acknowledgment;
+	u_int8_t	cu_topology_change;
+};
+
+struct bstp_tcn_unit {
+	u_int8_t	tu_message_type;
+};
+
+/*
+ * Bridge interface list
+ */
+struct bridge_iflist {
+	LIST_ENTRY(bridge_iflist)	next;		/* next in list */
+	u_int64_t			bif_designated_root;
+	u_int64_t			bif_designated_bridge;
+	u_int32_t			bif_path_cost;
+	u_int32_t			bif_designated_cost;
+	struct bridge_timer		bif_hold_timer;
+	struct bridge_timer		bif_message_age_timer;
+	struct bridge_timer		bif_forward_delay_timer;
+	struct bstp_config_unit		bif_config_bpdu;
+	struct bstp_tcn_unit		bif_tcn_bpdu;
+	u_int16_t			bif_port_id;
+	u_int16_t			bif_designated_port;
+	u_int8_t			bif_state;
+	u_int8_t			bif_topology_change_acknowledge;
+	u_int8_t			bif_config_pending;
+	u_int8_t			bif_change_detection_enabled;
+	u_int8_t			bif_priority;
+	struct brl_head			bif_brlin;	/* input rules */
+	struct brl_head			bif_brlout;	/* output rules */
+	struct				ifnet *ifp;	/* member interface */
+	u_int32_t			bif_flags;	/* member flags */
+};
+
+/*
+ * Bridge route node
+ */
+struct bridge_rtnode {
+	LIST_ENTRY(bridge_rtnode)	brt_next;	/* next in list */
+	struct				ifnet *brt_if;	/* destination ifs */
+	u_int8_t			brt_flags;	/* address flags */
+	u_int8_t			brt_age;	/* age counter */
+	struct				ether_addr brt_addr;	/* dst addr */
+};
+
+/*
+ * Software state for each bridge
+ */
+struct bridge_softc {
+	struct				ifnet sc_if;	/* the interface */
+	u_int64_t			sc_designated_root;
+	u_int64_t			sc_bridge_id;
+	struct bridge_iflist		*sc_root_port;
+	u_int32_t			sc_root_path_cost;
+	u_int16_t			sc_max_age;
+	u_int16_t			sc_hello_time;
+	u_int16_t			sc_forward_delay;
+	u_int16_t			sc_bridge_max_age;
+	u_int16_t			sc_bridge_hello_time;
+	u_int16_t			sc_bridge_forward_delay;
+	u_int16_t			sc_topology_change_time;
+	u_int16_t			sc_hold_time;
+	u_int16_t			sc_bridge_priority;
+	u_int8_t			sc_topology_change_detected;
+	u_int8_t			sc_topology_change;
+	struct bridge_timer		sc_hello_timer;
+	struct bridge_timer		sc_topology_change_timer;
+	struct bridge_timer		sc_tcn_timer;
+	u_int32_t			sc_brtmax;	/* max # addresses */
+	u_int32_t			sc_brtcnt;	/* current # addrs */
+	u_int32_t			sc_brttimeout;	/* timeout ticks */
+	u_int32_t			sc_hashkey;	/* hash key */
+	struct timeout			sc_brtimeout;	/* timeout state */
+	struct timeout			sc_bstptimeout;	/* stp timeout */
+	LIST_HEAD(, bridge_iflist)	sc_iflist;	/* interface list */
+	LIST_HEAD(bridge_rthead, bridge_rtnode)	*sc_rts;/* hash table */
+};
+
+extern u_int8_t bstp_etheraddr[];
+
 void	bridge_ifdetach __P((struct ifnet *));
 struct mbuf *bridge_input __P((struct ifnet *, struct ether_header *,
     struct mbuf *));
 int	bridge_output __P((struct ifnet *, struct mbuf *, struct sockaddr *,
     struct rtentry *rt));
+struct mbuf *bstp_input __P((struct bridge_softc *, struct ifnet *,
+    struct ether_header *, struct mbuf *));
+void	bstp_initialization __P((struct bridge_softc *));
+int	bstp_ioctl __P((struct ifnet *, u_long, caddr_t));
 #endif /* _KERNEL */
diff --git a/sys/net/if_ethersubr.c b/sys/net/if_ethersubr.c
index 8e6de698d74..39cf70baeb0 100644
--- a/sys/net/if_ethersubr.c
+++ b/sys/net/if_ethersubr.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: if_ethersubr.c,v 1.39 2000/10/18 16:16:33 jason Exp $	*/
+/*	$OpenBSD: if_ethersubr.c,v 1.40 2000/12/12 03:41:22 jason Exp $	*/
 /*	$NetBSD: if_ethersubr.c,v 1.19 1996/05/07 02:40:30 thorpej Exp $	*/
 
 /*
@@ -87,6 +87,7 @@ didn't get a copy, you may request one from <license@ipv6.nrl.navy.mil>.
 #include <sys/ioctl.h>
 #include <sys/errno.h>
 #include <sys/syslog.h>
+#include <sys/timeout.h>
 
 #include <machine/cpu.h>
 
diff --git a/sys/sys/sockio.h b/sys/sys/sockio.h
index a5b269608a2..165665a3cae 100644
--- a/sys/sys/sockio.h
+++ b/sys/sys/sockio.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: sockio.h,v 1.16 2000/04/26 18:37:37 chris Exp $	*/
+/*	$OpenBSD: sockio.h,v 1.17 2000/12/12 03:41:23 jason Exp $	*/
 /*	$NetBSD: sockio.h,v 1.5 1995/08/23 00:40:47 thorpej Exp $	*/
 
 /*-
@@ -96,34 +96,44 @@
 #define	SIOCGIFPSRCADDR	_IOWR('i', 71, struct ifreq)	/* get gif psrc addr */
 #define	SIOCGIFPDSTADDR	_IOWR('i', 72, struct ifreq)	/* get gif pdst addr */
 
-#define	SIOCBRDGADD	_IOWR('i', 60, struct ifbreq)	/* add bridge ifs */
-#define	SIOCBRDGDEL	_IOWR('i', 61, struct ifbreq)	/* del bridge ifs */
+#define	SIOCBRDGADD	 _IOW('i', 60, struct ifbreq)	/* add bridge ifs */
+#define	SIOCBRDGDEL	 _IOW('i', 61, struct ifbreq)	/* del bridge ifs */
 #define	SIOCBRDGGIFFLGS	_IOWR('i', 62, struct ifbreq)	/* get brdg if flags */
-#define	SIOCBRDGSIFFLGS	_IOWR('i', 63, struct ifbreq)	/* set brdg if flags */
-#define	SIOCBRDGSCACHE	_IOWR('i', 64, struct ifbcachereq) /* set cache size */
-#define	SIOCBRDGGCACHE	_IOWR('i', 65, struct ifbcachereq) /* get cache size */
+#define	SIOCBRDGSIFFLGS	 _IOW('i', 63, struct ifbreq)	/* set brdg if flags */
+#define	SIOCBRDGSCACHE	 _IOW('i', 64, struct ifbrparam)/* set cache size */
+#define	SIOCBRDGGCACHE	_IOWR('i', 65, struct ifbrparam)/* get cache size */
 #define	SIOCBRDGIFS	_IOWR('i', 66, struct ifbreq)	/* get member ifs */
 #define	SIOCBRDGRTS	_IOWR('i', 67, struct ifbaconf)	/* get addresses */
 #define	SIOCBRDGSADDR	_IOWR('i', 68, struct ifbareq)	/* set addr flags */
-#define	SIOCBRDGSTO	_IOWR('i', 69, struct ifbcachetoreq) /* cache timeout */
-#define	SIOCBRDGGTO	_IOWR('i', 70, struct ifbcachetoreq) /* cache timeout */
-#define	SIOCBRDGDADDR	_IOWR('i', 71, struct ifbareq)	/* delete addr */
-#define	SIOCBRDGFLUSH	_IOWR('i', 72, struct ifbreq)	/* flush addr cache */
+#define	SIOCBRDGSTO	 _IOW('i', 69, struct ifbrparam)/* cache timeout */
+#define	SIOCBRDGGTO	_IOWR('i', 70, struct ifbrparam)/* cache timeout */
+#define	SIOCBRDGDADDR	 _IOW('i', 71, struct ifbareq)	/* delete addr */
+#define	SIOCBRDGFLUSH	 _IOW('i', 72, struct ifbreq)	/* flush addr cache */
 
 #define SIOCGENCSA	_IOWR('i', 73, struct ifsa)	/* get enc sa */
-#define SIOCSENCDSTSA	_IOW('i', 74, struct ifsa)	/* set enc sa */
-#define SIOCSENCSRCSA	_IOW('i', 75, struct ifsa)	/* set enc sa */
-#define SIOCSENCCLEARSA	_IOW('i', 76, struct ifsa)	/* set enc sa */
+#define SIOCSENCDSTSA	 _IOW('i', 74, struct ifsa)	/* set enc sa */
+#define SIOCSENCSRCSA	 _IOW('i', 75, struct ifsa)	/* set enc sa */
+#define SIOCSENCCLEARSA	 _IOW('i', 76, struct ifsa)	/* set enc sa */
 
-#define SIOCBRDGARL	_IOWR('i', 77, struct ifbrlreq)	/* add bridge rule */
-#define SIOCBRDGFRL	_IOWR('i', 78, struct ifbrlreq)	/* flush brdg rules */
+#define SIOCBRDGARL	 _IOW('i', 77, struct ifbrlreq)	/* add bridge rule */
+#define SIOCBRDGFRL	 _IOW('i', 78, struct ifbrlreq)	/* flush brdg rules */
 #define SIOCBRDGGRL	_IOWR('i', 79, struct ifbrlconf)/* get bridge rules */
-
-#define GRESADDRS       _IOW('i', 101, struct ifreq)
-#define GRESADDRD       _IOW('i', 102, struct ifreq)   
+#define	SIOCBRDGGPRI	_IOWR('i', 80, struct ifbrparam)/* get priority */
+#define	SIOCBRDGSPRI	 _IOW('i', 80, struct ifbrparam)/* set priority */
+#define	SIOCBRDGGHT	_IOWR('i', 81, struct ifbrparam)/* get hello time */
+#define	SIOCBRDGSHT	 _IOW('i', 81, struct ifbrparam)/* set hello time */
+#define	SIOCBRDGGFD	_IOWR('i', 82, struct ifbrparam)/* get forward delay */
+#define	SIOCBRDGSFD	 _IOW('i', 82, struct ifbrparam)/* set forward delay */
+#define	SIOCBRDGGMA	_IOWR('i', 83, struct ifbrparam)/* get max age */
+#define	SIOCBRDGSMA	 _IOW('i', 83, struct ifbrparam)/* set max age */
+#define	SIOCBRDGSIFPRIO	 _IOW('i', 84, struct ifbreq)	/* set if priority */
+
+#define	SIOCBRDGS
+#define GRESADDRS        _IOW('i', 101, struct ifreq)
+#define GRESADDRD        _IOW('i', 102, struct ifreq)   
 #define GREGADDRS       _IOWR('i', 103, struct ifreq)
 #define GREGADDRD       _IOWR('i', 104, struct ifreq)
-#define GRESPROTO       _IOW('i' , 105, struct ifreq)
+#define GRESPROTO        _IOW('i', 105, struct ifreq)
 #define GREGPROTO       _IOWR('i', 106, struct ifreq)
 
 #define	SIOCSIFMTU	 _IOW('i', 127, struct ifreq)	/* set ifnet mtu */