Aquire serializer before calling ioctl
[dragonfly.git] / sys / net / bridge / bridgestp.c
1 /*
2  * Copyright (c) 2000 Jason L. Wright (jason@thought.net)
3  * All rights reserved.
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions
7  * are met:
8  * 1. Redistributions of source code must retain the above copyright
9  *    notice, this list of conditions and the following disclaimer.
10  * 2. Redistributions in binary form must reproduce the above copyright
11  *    notice, this list of conditions and the following disclaimer in the
12  *    documentation and/or other materials provided with the distribution.
13  * 3. All advertising materials mentioning features or use of this software
14  *    must display the following acknowledgement:
15  *      This product includes software developed by Jason L. Wright
16  * 4. The name of the author may not be used to endorse or promote products
17  *    derived from this software without specific prior written permission.
18  *
19  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
20  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
21  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
22  * DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT,
23  * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
24  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
25  * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
26  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
27  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
28  * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
29  * POSSIBILITY OF SUCH DAMAGE.
30  *
31  * $OpenBSD: bridgestp.c,v 1.5 2001/03/22 03:48:29 jason Exp $
32  * $NetBSD: bridgestp.c,v 1.5 2003/11/28 08:56:48 keihan Exp $
33  * $FreeBSD: src/sys/net/bridgestp.c,v 1.7 2005/10/11 02:58:32 thompsa Exp $
34  * $DragonFly: src/sys/net/bridge/bridgestp.c,v 1.2 2005/12/22 15:16:13 corecode Exp $
35  */
36
37 /*
38  * Implementation of the spanning tree protocol as defined in
39  * ISO/IEC Final DIS 15802-3 (IEEE P802.1D/D17), May 25, 1998.
40  * (In English: IEEE 802.1D, Draft 17, 1998)
41  */
42
43 #include <sys/cdefs.h>
44
45 #include <sys/param.h>
46 #include <sys/systm.h>
47 #include <sys/mbuf.h>
48 #include <sys/socket.h>
49 #include <sys/sockio.h>
50 #include <sys/kernel.h>
51 #include <sys/callout.h>
52 #include <sys/proc.h>
53 #include <sys/lock.h>
54 #include <sys/thread.h>
55 #include <sys/thread2.h>
56
57 #include <net/if.h>
58 #include <net/if_dl.h>
59 #include <net/if_types.h>
60 #include <net/if_llc.h>
61 #include <net/if_media.h>
62
63 #include <netinet/in.h>
64 #include <netinet/in_systm.h>
65 #include <netinet/in_var.h>
66 #include <netinet/if_ether.h>
67 #include <net/bridge/if_bridgevar.h>
68
69 /* BPDU message types */
70 #define BSTP_MSGTYPE_CFG        0x00            /* Configuration */
71 #define BSTP_MSGTYPE_TCN        0x80            /* Topology chg notification */
72
73 /* BPDU flags */
74 #define BSTP_FLAG_TC            0x01            /* Topology change */
75 #define BSTP_FLAG_TCA           0x80            /* Topology change ack */
76
77 #define BSTP_MESSAGE_AGE_INCR   (1 * 256)       /* in 256ths of a second */
78 #define BSTP_TICK_VAL           (1 * 256)       /* in 256ths of a second */
79
80 /*
81  * Because BPDU's do not make nicely aligned structures, two different
82  * declarations are used: bstp_?bpdu (wire representation, packed) and
83  * bstp_*_unit (internal, nicely aligned version).
84  */
85
86 /* configuration bridge protocol data unit */
87 struct bstp_cbpdu {
88         uint8_t         cbu_dsap;               /* LLC: destination sap */
89         uint8_t         cbu_ssap;               /* LLC: source sap */
90         uint8_t         cbu_ctl;                /* LLC: control */
91         uint16_t        cbu_protoid;            /* protocol id */
92         uint8_t         cbu_protover;           /* protocol version */
93         uint8_t         cbu_bpdutype;           /* message type */
94         uint8_t         cbu_flags;              /* flags (below) */
95
96         /* root id */
97         uint16_t        cbu_rootpri;            /* root priority */
98         uint8_t cbu_rootaddr[6];        /* root address */
99
100         uint32_t        cbu_rootpathcost;       /* root path cost */
101
102         /* bridge id */
103         uint16_t        cbu_bridgepri;          /* bridge priority */
104         uint8_t         cbu_bridgeaddr[6];      /* bridge address */
105
106         uint16_t        cbu_portid;             /* port id */
107         uint16_t        cbu_messageage;         /* current message age */
108         uint16_t        cbu_maxage;             /* maximum age */
109         uint16_t        cbu_hellotime;          /* hello time */
110         uint16_t        cbu_forwarddelay;       /* forwarding delay */
111 } __attribute__((__packed__));
112
113 /* topology change notification bridge protocol data unit */
114 struct bstp_tbpdu {
115         uint8_t         tbu_dsap;               /* LLC: destination sap */
116         uint8_t         tbu_ssap;               /* LLC: source sap */
117         uint8_t         tbu_ctl;                /* LLC: control */
118         uint16_t        tbu_protoid;            /* protocol id */
119         uint8_t         tbu_protover;           /* protocol version */
120         uint8_t         tbu_bpdutype;           /* message type */
121 } __attribute__((__packed__));
122
123 const uint8_t bstp_etheraddr[] = { 0x01, 0x80, 0xc2, 0x00, 0x00, 0x00 };
124
125 void    bstp_initialize_port(struct bridge_softc *, struct bridge_iflist *);
126 void    bstp_ifupdstatus(struct bridge_softc *, struct bridge_iflist *);
127 void    bstp_enable_port(struct bridge_softc *, struct bridge_iflist *);
128 void    bstp_disable_port(struct bridge_softc *, struct bridge_iflist *);
129 void    bstp_enable_change_detection(struct bridge_iflist *);
130 void    bstp_disable_change_detection(struct bridge_iflist *);
131 int     bstp_root_bridge(struct bridge_softc *sc);
132 int     bstp_supersedes_port_info(struct bridge_softc *,
133             struct bridge_iflist *, struct bstp_config_unit *);
134 int     bstp_designated_port(struct bridge_softc *, struct bridge_iflist *);
135 int     bstp_designated_for_some_port(struct bridge_softc *);
136 void    bstp_transmit_config(struct bridge_softc *, struct bridge_iflist *);
137 void    bstp_transmit_tcn(struct bridge_softc *);
138 void    bstp_received_config_bpdu(struct bridge_softc *,
139             struct bridge_iflist *, struct bstp_config_unit *);
140 void    bstp_received_tcn_bpdu(struct bridge_softc *, struct bridge_iflist *,
141             struct bstp_tcn_unit *);
142 void    bstp_record_config_information(struct bridge_softc *,
143             struct bridge_iflist *, struct bstp_config_unit *);
144 void    bstp_record_config_timeout_values(struct bridge_softc *,
145             struct bstp_config_unit *);
146 void    bstp_config_bpdu_generation(struct bridge_softc *);
147 void    bstp_send_config_bpdu(struct bridge_softc *, struct bridge_iflist *,
148             struct bstp_config_unit *);
149 void    bstp_configuration_update(struct bridge_softc *);
150 void    bstp_root_selection(struct bridge_softc *);
151 void    bstp_designated_port_selection(struct bridge_softc *);
152 void    bstp_become_designated_port(struct bridge_softc *,
153             struct bridge_iflist *);
154 void    bstp_port_state_selection(struct bridge_softc *);
155 void    bstp_make_forwarding(struct bridge_softc *, struct bridge_iflist *);
156 void    bstp_make_blocking(struct bridge_softc *, struct bridge_iflist *);
157 void    bstp_set_port_state(struct bridge_iflist *, uint8_t);
158 void    bstp_set_bridge_priority(struct bridge_softc *, uint64_t);
159 void    bstp_set_port_priority(struct bridge_softc *, struct bridge_iflist *,
160             uint16_t);
161 void    bstp_set_path_cost(struct bridge_softc *, struct bridge_iflist *,
162             uint32_t);
163 void    bstp_topology_change_detection(struct bridge_softc *);
164 void    bstp_topology_change_acknowledged(struct bridge_softc *);
165 void    bstp_acknowledge_topology_change(struct bridge_softc *,
166             struct bridge_iflist *);
167
168 void    bstp_tick(void *);
169 void    bstp_timer_start(struct bridge_timer *, uint16_t);
170 void    bstp_timer_stop(struct bridge_timer *);
171 int     bstp_timer_expired(struct bridge_timer *, uint16_t);
172
173 void    bstp_hold_timer_expiry(struct bridge_softc *, struct bridge_iflist *);
174 void    bstp_message_age_timer_expiry(struct bridge_softc *,
175             struct bridge_iflist *);
176 void    bstp_forward_delay_timer_expiry(struct bridge_softc *,
177             struct bridge_iflist *);
178 void    bstp_topology_change_timer_expiry(struct bridge_softc *);
179 void    bstp_tcn_timer_expiry(struct bridge_softc *);
180 void    bstp_hello_timer_expiry(struct bridge_softc *);
181
182 void
183 bstp_transmit_config(struct bridge_softc *sc, struct bridge_iflist *bif)
184 {
185         if (bif->bif_hold_timer.active) {
186                 bif->bif_config_pending = 1;
187                 return;
188         }
189
190         bif->bif_config_bpdu.cu_message_type = BSTP_MSGTYPE_CFG;
191         bif->bif_config_bpdu.cu_rootid = sc->sc_designated_root;
192         bif->bif_config_bpdu.cu_root_path_cost = sc->sc_root_path_cost;
193         bif->bif_config_bpdu.cu_bridge_id = sc->sc_bridge_id;
194         bif->bif_config_bpdu.cu_port_id = bif->bif_port_id;
195
196         if (bstp_root_bridge(sc))
197                 bif->bif_config_bpdu.cu_message_age = 0;
198         else
199                 bif->bif_config_bpdu.cu_message_age =
200                     sc->sc_root_port->bif_message_age_timer.value +
201                     BSTP_MESSAGE_AGE_INCR;
202
203         bif->bif_config_bpdu.cu_max_age = sc->sc_max_age;
204         bif->bif_config_bpdu.cu_hello_time = sc->sc_hello_time;
205         bif->bif_config_bpdu.cu_forward_delay = sc->sc_forward_delay;
206         bif->bif_config_bpdu.cu_topology_change_acknowledgment
207             = bif->bif_topology_change_acknowledge;
208         bif->bif_config_bpdu.cu_topology_change = sc->sc_topology_change;
209
210         if (bif->bif_config_bpdu.cu_message_age < sc->sc_max_age) {
211                 bif->bif_topology_change_acknowledge = 0;
212                 bif->bif_config_pending = 0;
213                 bstp_send_config_bpdu(sc, bif, &bif->bif_config_bpdu);
214                 bstp_timer_start(&bif->bif_hold_timer, 0);
215         }
216 }
217
218 void
219 bstp_send_config_bpdu(struct bridge_softc *sc, struct bridge_iflist *bif,
220     struct bstp_config_unit *cu)
221 {
222         struct ifnet *ifp;
223         struct mbuf *m;
224         struct ether_header *eh;
225         struct bstp_cbpdu bpdu;
226
227         ifp = bif->bif_ifp;
228
229         if ((ifp->if_flags & IFF_RUNNING) == 0)
230                 return;
231
232         MGETHDR(m, MB_DONTWAIT, MT_DATA);
233         if (m == NULL)
234                 return;
235
236         eh = mtod(m, struct ether_header *);
237
238         m->m_pkthdr.rcvif = ifp;
239         m->m_pkthdr.len = sizeof(*eh) + sizeof(bpdu);
240         m->m_len = m->m_pkthdr.len;
241
242         bpdu.cbu_ssap = bpdu.cbu_dsap = LLC_8021D_LSAP;
243         bpdu.cbu_ctl = LLC_UI;
244         bpdu.cbu_protoid = htons(0);
245         bpdu.cbu_protover = 0;
246         bpdu.cbu_bpdutype = cu->cu_message_type;
247         bpdu.cbu_flags = (cu->cu_topology_change ? BSTP_FLAG_TC : 0) |
248             (cu->cu_topology_change_acknowledgment ? BSTP_FLAG_TCA : 0);
249
250         bpdu.cbu_rootpri = htons(cu->cu_rootid >> 48);
251         bpdu.cbu_rootaddr[0] = cu->cu_rootid >> 40;
252         bpdu.cbu_rootaddr[1] = cu->cu_rootid >> 32;
253         bpdu.cbu_rootaddr[2] = cu->cu_rootid >> 24;
254         bpdu.cbu_rootaddr[3] = cu->cu_rootid >> 16;
255         bpdu.cbu_rootaddr[4] = cu->cu_rootid >> 8;
256         bpdu.cbu_rootaddr[5] = cu->cu_rootid >> 0;
257
258         bpdu.cbu_rootpathcost = htonl(cu->cu_root_path_cost);
259
260         bpdu.cbu_bridgepri = htons(cu->cu_rootid >> 48);
261         bpdu.cbu_bridgeaddr[0] = cu->cu_rootid >> 40;
262         bpdu.cbu_bridgeaddr[1] = cu->cu_rootid >> 32;
263         bpdu.cbu_bridgeaddr[2] = cu->cu_rootid >> 24;
264         bpdu.cbu_bridgeaddr[3] = cu->cu_rootid >> 16;
265         bpdu.cbu_bridgeaddr[4] = cu->cu_rootid >> 8;
266         bpdu.cbu_bridgeaddr[5] = cu->cu_rootid >> 0;
267
268         bpdu.cbu_portid = htons(cu->cu_port_id);
269         bpdu.cbu_messageage = htons(cu->cu_message_age);
270         bpdu.cbu_maxage = htons(cu->cu_max_age);
271         bpdu.cbu_hellotime = htons(cu->cu_hello_time);
272         bpdu.cbu_forwarddelay = htons(cu->cu_forward_delay);
273
274         memcpy(eh->ether_shost, IF_LLADDR(ifp), ETHER_ADDR_LEN);
275         memcpy(eh->ether_dhost, bstp_etheraddr, ETHER_ADDR_LEN);
276         eh->ether_type = htons(sizeof(bpdu));
277
278         memcpy(mtod(m, caddr_t) + sizeof(*eh), &bpdu, sizeof(bpdu));
279
280         bridge_enqueue(sc, ifp, m);
281 }
282
283 int
284 bstp_root_bridge(struct bridge_softc *sc)
285 {
286         return (sc->sc_designated_root == sc->sc_bridge_id);
287 }
288
289 int
290 bstp_supersedes_port_info(struct bridge_softc *sc, struct bridge_iflist *bif,
291     struct bstp_config_unit *cu)
292 {
293         if (cu->cu_rootid < bif->bif_designated_root)
294                 return (1);
295         if (cu->cu_rootid > bif->bif_designated_root)
296                 return (0);
297
298         if (cu->cu_root_path_cost < bif->bif_designated_cost)
299                 return (1);
300         if (cu->cu_root_path_cost > bif->bif_designated_cost)
301                 return (0);
302
303         if (cu->cu_bridge_id < bif->bif_designated_bridge)
304                 return (1);
305         if (cu->cu_bridge_id > bif->bif_designated_bridge)
306                 return (0);
307
308         if (sc->sc_bridge_id != cu->cu_bridge_id)
309                 return (1);
310         if (cu->cu_port_id <= bif->bif_designated_port)
311                 return (1);
312         return (0);
313 }
314
315 void
316 bstp_record_config_information(struct bridge_softc *sc,
317     struct bridge_iflist *bif, struct bstp_config_unit *cu)
318 {
319         bif->bif_designated_root = cu->cu_rootid;
320         bif->bif_designated_cost = cu->cu_root_path_cost;
321         bif->bif_designated_bridge = cu->cu_bridge_id;
322         bif->bif_designated_port = cu->cu_port_id;
323         bstp_timer_start(&bif->bif_message_age_timer, cu->cu_message_age);
324 }
325
326 void
327 bstp_record_config_timeout_values(struct bridge_softc *sc,
328     struct bstp_config_unit *config)
329 {
330         sc->sc_max_age = config->cu_max_age;
331         sc->sc_hello_time = config->cu_hello_time;
332         sc->sc_forward_delay = config->cu_forward_delay;
333         sc->sc_topology_change = config->cu_topology_change;
334 }
335
336 void
337 bstp_config_bpdu_generation(struct bridge_softc *sc)
338 {
339         struct bridge_iflist *bif;
340
341         LIST_FOREACH(bif, &sc->sc_iflist, bif_next) {
342                 if ((bif->bif_flags & IFBIF_STP) == 0)
343                         continue;
344                 if (bstp_designated_port(sc, bif) &&
345                     (bif->bif_state != BSTP_IFSTATE_DISABLED))
346                         bstp_transmit_config(sc, bif);
347         }
348 }
349
350 int
351 bstp_designated_port(struct bridge_softc *sc, struct bridge_iflist *bif)
352 {
353         return ((bif->bif_designated_bridge == sc->sc_bridge_id)
354             && (bif->bif_designated_port == bif->bif_port_id));
355 }
356
357 void
358 bstp_transmit_tcn(struct bridge_softc *sc)
359 {
360         struct bstp_tbpdu bpdu;
361         struct bridge_iflist *bif = sc->sc_root_port;
362         struct ifnet *ifp = bif->bif_ifp;
363         struct ether_header *eh;
364         struct mbuf *m;
365
366         if ((ifp->if_flags & IFF_RUNNING) == 0)
367                 return;
368
369         MGETHDR(m, MB_DONTWAIT, MT_DATA);
370         if (m == NULL)
371                 return;
372
373         m->m_pkthdr.rcvif = ifp;
374         m->m_pkthdr.len = sizeof(*eh) + sizeof(bpdu);
375         m->m_len = m->m_pkthdr.len;
376
377         eh = mtod(m, struct ether_header *);
378
379         memcpy(eh->ether_shost, IF_LLADDR(ifp), ETHER_ADDR_LEN);
380         memcpy(eh->ether_dhost, bstp_etheraddr, ETHER_ADDR_LEN);
381         eh->ether_type = htons(sizeof(bpdu));
382
383         bpdu.tbu_ssap = bpdu.tbu_dsap = LLC_8021D_LSAP;
384         bpdu.tbu_ctl = LLC_UI;
385         bpdu.tbu_protoid = 0;
386         bpdu.tbu_protover = 0;
387         bpdu.tbu_bpdutype = BSTP_MSGTYPE_TCN;
388
389         memcpy(mtod(m, caddr_t) + sizeof(*eh), &bpdu, sizeof(bpdu));
390
391         bridge_enqueue(sc, ifp, m);
392 }
393
394 void
395 bstp_configuration_update(struct bridge_softc *sc)
396 {
397         bstp_root_selection(sc);
398         bstp_designated_port_selection(sc);
399 }
400
401 void
402 bstp_root_selection(struct bridge_softc *sc)
403 {
404         struct bridge_iflist *root_port = NULL, *bif;
405
406         LIST_FOREACH(bif, &sc->sc_iflist, bif_next) {
407                 if ((bif->bif_flags & IFBIF_STP) == 0)
408                         continue;
409                 if (bstp_designated_port(sc, bif))
410                         continue;
411                 if (bif->bif_state == BSTP_IFSTATE_DISABLED)
412                         continue;
413                 if (bif->bif_designated_root >= sc->sc_bridge_id)
414                         continue;
415                 if (root_port == NULL)
416                         goto set_port;
417
418                 if (bif->bif_designated_root < root_port->bif_designated_root)
419                         goto set_port;
420                 if (bif->bif_designated_root > root_port->bif_designated_root)
421                         continue;
422
423                 if ((bif->bif_designated_cost + bif->bif_path_cost) <
424                     (root_port->bif_designated_cost + root_port->bif_path_cost))
425                         goto set_port;
426                 if ((bif->bif_designated_cost + bif->bif_path_cost) >
427                     (root_port->bif_designated_cost + root_port->bif_path_cost))
428                         continue;
429
430                 if (bif->bif_designated_bridge <
431                     root_port->bif_designated_bridge)
432                         goto set_port;
433                 if (bif->bif_designated_bridge >
434                     root_port->bif_designated_bridge)
435                         continue;
436
437                 if (bif->bif_designated_port < root_port->bif_designated_port)
438                         goto set_port;
439                 if (bif->bif_designated_port > root_port->bif_designated_port)
440                         continue;
441
442                 if (bif->bif_port_id >= root_port->bif_port_id)
443                         continue;
444 set_port:
445                 root_port = bif;
446         }
447
448         sc->sc_root_port = root_port;
449         if (root_port == NULL) {
450                 sc->sc_designated_root = sc->sc_bridge_id;
451                 sc->sc_root_path_cost = 0;
452         } else {
453                 sc->sc_designated_root = root_port->bif_designated_root;
454                 sc->sc_root_path_cost = root_port->bif_designated_cost +
455                     root_port->bif_path_cost;
456         }
457 }
458
459 void
460 bstp_designated_port_selection(struct bridge_softc *sc)
461 {
462         struct bridge_iflist *bif;
463
464         LIST_FOREACH(bif, &sc->sc_iflist, bif_next) {
465                 if ((bif->bif_flags & IFBIF_STP) == 0)
466                         continue;
467                 if (bstp_designated_port(sc, bif))
468                         goto designated;
469                 if (bif->bif_designated_root != sc->sc_designated_root)
470                         goto designated;
471
472                 if (sc->sc_root_path_cost < bif->bif_designated_cost)
473                         goto designated;
474                 if (sc->sc_root_path_cost > bif->bif_designated_cost)
475                         continue;
476
477                 if (sc->sc_bridge_id < bif->bif_designated_bridge)
478                         goto designated;
479                 if (sc->sc_bridge_id > bif->bif_designated_bridge)
480                         continue;
481
482                 if (bif->bif_port_id > bif->bif_designated_port)
483                         continue;
484 designated:
485                 bstp_become_designated_port(sc, bif);
486         }
487 }
488
489 void
490 bstp_become_designated_port(struct bridge_softc *sc, struct bridge_iflist *bif)
491 {
492         bif->bif_designated_root = sc->sc_designated_root;
493         bif->bif_designated_cost = sc->sc_root_path_cost;
494         bif->bif_designated_bridge = sc->sc_bridge_id;
495         bif->bif_designated_port = bif->bif_port_id;
496 }
497
498 void
499 bstp_port_state_selection(struct bridge_softc *sc)
500 {
501         struct bridge_iflist *bif;
502
503         LIST_FOREACH(bif, &sc->sc_iflist, bif_next) {
504                 if ((bif->bif_flags & IFBIF_STP) == 0)
505                         continue;
506                 if (bif == sc->sc_root_port) {
507                         bif->bif_config_pending = 0;
508                         bif->bif_topology_change_acknowledge = 0;
509                         bstp_make_forwarding(sc, bif);
510                 } else if (bstp_designated_port(sc, bif)) {
511                         bstp_timer_stop(&bif->bif_message_age_timer);
512                         bstp_make_forwarding(sc, bif);
513                 } else {
514                         bif->bif_config_pending = 0;
515                         bif->bif_topology_change_acknowledge = 0;
516                         bstp_make_blocking(sc, bif);
517                 }
518         }
519 }
520
521 void
522 bstp_make_forwarding(struct bridge_softc *sc, struct bridge_iflist *bif)
523 {
524         if (bif->bif_state == BSTP_IFSTATE_BLOCKING) {
525                 bstp_set_port_state(bif, BSTP_IFSTATE_LISTENING);
526                 bstp_timer_start(&bif->bif_forward_delay_timer, 0);
527         }
528 }
529
530 void
531 bstp_make_blocking(struct bridge_softc *sc, struct bridge_iflist *bif)
532 {
533         if ((bif->bif_state != BSTP_IFSTATE_DISABLED) &&
534             (bif->bif_state != BSTP_IFSTATE_BLOCKING)) {
535                 if ((bif->bif_state == BSTP_IFSTATE_FORWARDING) ||
536                     (bif->bif_state == BSTP_IFSTATE_LEARNING)) {
537                         if (bif->bif_change_detection_enabled) {
538                                 bstp_topology_change_detection(sc);
539                         }
540                 }
541                 bstp_set_port_state(bif, BSTP_IFSTATE_BLOCKING);
542                 bridge_rtdelete(sc, bif->bif_ifp, IFBF_FLUSHDYN);
543                 bstp_timer_stop(&bif->bif_forward_delay_timer);
544         }
545 }
546
547 void
548 bstp_set_port_state(struct bridge_iflist *bif, uint8_t state)
549 {
550         bif->bif_state = state;
551 }
552
553 void
554 bstp_topology_change_detection(struct bridge_softc *sc)
555 {
556         if (bstp_root_bridge(sc)) {
557                 sc->sc_topology_change = 1;
558                 bstp_timer_start(&sc->sc_topology_change_timer, 0);
559         } else if (!sc->sc_topology_change_detected) {
560                 bstp_transmit_tcn(sc);
561                 bstp_timer_start(&sc->sc_tcn_timer, 0);
562         }
563         sc->sc_topology_change_detected = 1;
564 }
565
566 void
567 bstp_topology_change_acknowledged(struct bridge_softc *sc)
568 {
569         sc->sc_topology_change_detected = 0;
570         bstp_timer_stop(&sc->sc_tcn_timer);
571 }
572
573 void
574 bstp_acknowledge_topology_change(struct bridge_softc *sc,
575     struct bridge_iflist *bif)
576 {
577         bif->bif_topology_change_acknowledge = 1;
578         bstp_transmit_config(sc, bif);
579 }
580
581 struct mbuf *
582 bstp_input(struct ifnet *ifp, struct mbuf *m)
583 {
584         struct bridge_softc *sc = ifp->if_bridge;
585         struct bridge_iflist *bif = NULL;
586         struct ether_header *eh;
587         struct bstp_tbpdu tpdu;
588         struct bstp_cbpdu cpdu;
589         struct bstp_config_unit cu;
590         struct bstp_tcn_unit tu;
591         uint16_t len;
592
593         eh = mtod(m, struct ether_header *);
594
595         LIST_FOREACH(bif, &sc->sc_iflist, bif_next) {
596                 if ((bif->bif_flags & IFBIF_STP) == 0)
597                         continue;
598                 if (bif->bif_ifp == ifp)
599                         break;
600         }
601         if (bif == NULL)
602                 goto out;
603
604         len = ntohs(eh->ether_type);
605         if (len < sizeof(tpdu))
606                 goto out;
607
608         m_adj(m, ETHER_HDR_LEN);
609
610         if (m->m_pkthdr.len > len)
611                 m_adj(m, len - m->m_pkthdr.len);
612         if (m->m_len < sizeof(tpdu) &&
613             (m = m_pullup(m, sizeof(tpdu))) == NULL)
614                 goto out;
615
616         memcpy(&tpdu, mtod(m, caddr_t), sizeof(tpdu));
617
618         if (tpdu.tbu_dsap != LLC_8021D_LSAP ||
619             tpdu.tbu_ssap != LLC_8021D_LSAP ||
620             tpdu.tbu_ctl != LLC_UI)
621                 goto out;
622         if (tpdu.tbu_protoid != 0 || tpdu.tbu_protover != 0)
623                 goto out;
624
625         switch (tpdu.tbu_bpdutype) {
626         case BSTP_MSGTYPE_TCN:
627                 tu.tu_message_type = tpdu.tbu_bpdutype;
628                 bstp_received_tcn_bpdu(sc, bif, &tu);
629                 break;
630         case BSTP_MSGTYPE_CFG:
631                 if (m->m_len < sizeof(cpdu) &&
632                     (m = m_pullup(m, sizeof(cpdu))) == NULL)
633                         goto out;
634                 memcpy(&cpdu, mtod(m, caddr_t), sizeof(cpdu));
635
636                 cu.cu_rootid =
637                     (((uint64_t)ntohs(cpdu.cbu_rootpri)) << 48) |
638                     (((uint64_t)cpdu.cbu_rootaddr[0]) << 40) |
639                     (((uint64_t)cpdu.cbu_rootaddr[1]) << 32) |
640                     (((uint64_t)cpdu.cbu_rootaddr[2]) << 24) |
641                     (((uint64_t)cpdu.cbu_rootaddr[3]) << 16) |
642                     (((uint64_t)cpdu.cbu_rootaddr[4]) << 8) |
643                     (((uint64_t)cpdu.cbu_rootaddr[5]) << 0);
644
645                 cu.cu_bridge_id =
646                     (((uint64_t)ntohs(cpdu.cbu_bridgepri)) << 48) |
647                     (((uint64_t)cpdu.cbu_bridgeaddr[0]) << 40) |
648                     (((uint64_t)cpdu.cbu_bridgeaddr[1]) << 32) |
649                     (((uint64_t)cpdu.cbu_bridgeaddr[2]) << 24) |
650                     (((uint64_t)cpdu.cbu_bridgeaddr[3]) << 16) |
651                     (((uint64_t)cpdu.cbu_bridgeaddr[4]) << 8) |
652                     (((uint64_t)cpdu.cbu_bridgeaddr[5]) << 0);
653
654                 cu.cu_root_path_cost = ntohl(cpdu.cbu_rootpathcost);
655                 cu.cu_message_age = ntohs(cpdu.cbu_messageage);
656                 cu.cu_max_age = ntohs(cpdu.cbu_maxage);
657                 cu.cu_hello_time = ntohs(cpdu.cbu_hellotime);
658                 cu.cu_forward_delay = ntohs(cpdu.cbu_forwarddelay);
659                 cu.cu_port_id = ntohs(cpdu.cbu_portid);
660                 cu.cu_message_type = cpdu.cbu_bpdutype;
661                 cu.cu_topology_change_acknowledgment =
662                     (cpdu.cbu_flags & BSTP_FLAG_TCA) ? 1 : 0;
663                 cu.cu_topology_change =
664                     (cpdu.cbu_flags & BSTP_FLAG_TC) ? 1 : 0;
665                 bstp_received_config_bpdu(sc, bif, &cu);
666                 break;
667         default:
668                 goto out;
669         }
670
671  out:
672         if (m)
673                 m_freem(m);
674         return (NULL);
675 }
676
677 void
678 bstp_received_config_bpdu(struct bridge_softc *sc, struct bridge_iflist *bif,
679     struct bstp_config_unit *cu)
680 {
681         int root;
682
683         root = bstp_root_bridge(sc);
684
685         if (bif->bif_state != BSTP_IFSTATE_DISABLED) {
686                 if (bstp_supersedes_port_info(sc, bif, cu)) {
687                         bstp_record_config_information(sc, bif, cu);
688                         bstp_configuration_update(sc);
689                         bstp_port_state_selection(sc);
690
691                         if ((bstp_root_bridge(sc) == 0) && root) {
692                                 bstp_timer_stop(&sc->sc_hello_timer);
693
694                                 if (sc->sc_topology_change_detected) {
695                                         bstp_timer_stop(
696                                             &sc->sc_topology_change_timer);
697                                         bstp_transmit_tcn(sc);
698                                         bstp_timer_start(&sc->sc_tcn_timer, 0);
699                                 }
700                         }
701
702                         if (bif == sc->sc_root_port) {
703                                 bstp_record_config_timeout_values(sc, cu);
704                                 bstp_config_bpdu_generation(sc);
705
706                                 if (cu->cu_topology_change_acknowledgment)
707                                         bstp_topology_change_acknowledged(sc);
708                         }
709                 } else if (bstp_designated_port(sc, bif))
710                         bstp_transmit_config(sc, bif);
711         }
712 }
713
714 void
715 bstp_received_tcn_bpdu(struct bridge_softc *sc, struct bridge_iflist *bif,
716     struct bstp_tcn_unit *tcn)
717 {
718         if (bif->bif_state != BSTP_IFSTATE_DISABLED &&
719             bstp_designated_port(sc, bif)) {
720                 bstp_topology_change_detection(sc);
721                 bstp_acknowledge_topology_change(sc, bif);
722         }
723 }
724
725 void
726 bstp_hello_timer_expiry(struct bridge_softc *sc)
727 {
728         bstp_config_bpdu_generation(sc);
729         bstp_timer_start(&sc->sc_hello_timer, 0);
730 }
731
732 void
733 bstp_message_age_timer_expiry(struct bridge_softc *sc,
734     struct bridge_iflist *bif)
735 {
736         int root;
737
738         root = bstp_root_bridge(sc);
739         bstp_become_designated_port(sc, bif);
740         bstp_configuration_update(sc);
741         bstp_port_state_selection(sc);
742
743         if ((bstp_root_bridge(sc)) && (root == 0)) {
744                 sc->sc_max_age = sc->sc_bridge_max_age;
745                 sc->sc_hello_time = sc->sc_bridge_hello_time;
746                 sc->sc_forward_delay = sc->sc_bridge_forward_delay;
747
748                 bstp_topology_change_detection(sc);
749                 bstp_timer_stop(&sc->sc_tcn_timer);
750                 bstp_config_bpdu_generation(sc);
751                 bstp_timer_start(&sc->sc_hello_timer, 0);
752         }
753 }
754
755 void
756 bstp_forward_delay_timer_expiry(struct bridge_softc *sc,
757     struct bridge_iflist *bif)
758 {
759         if (bif->bif_state == BSTP_IFSTATE_LISTENING) {
760                 bstp_set_port_state(bif, BSTP_IFSTATE_LEARNING);
761                 bstp_timer_start(&bif->bif_forward_delay_timer, 0);
762         } else if (bif->bif_state == BSTP_IFSTATE_LEARNING) {
763                 bstp_set_port_state(bif, BSTP_IFSTATE_FORWARDING);
764                 if (bstp_designated_for_some_port(sc) &&
765                     bif->bif_change_detection_enabled)
766                         bstp_topology_change_detection(sc);
767         }
768 }
769
770 int
771 bstp_designated_for_some_port(struct bridge_softc *sc)
772 {
773
774         struct bridge_iflist *bif;
775
776         LIST_FOREACH(bif, &sc->sc_iflist, bif_next) {
777                 if ((bif->bif_flags & IFBIF_STP) == 0)
778                         continue;
779                 if (bif->bif_designated_bridge == sc->sc_bridge_id)
780                         return (1);
781         }
782         return (0);
783 }
784
785 void
786 bstp_tcn_timer_expiry(struct bridge_softc *sc)
787 {
788         bstp_transmit_tcn(sc);
789         bstp_timer_start(&sc->sc_tcn_timer, 0);
790 }
791
792 void
793 bstp_topology_change_timer_expiry(struct bridge_softc *sc)
794 {
795         sc->sc_topology_change_detected = 0;
796         sc->sc_topology_change = 0;
797 }
798
799 void
800 bstp_hold_timer_expiry(struct bridge_softc *sc, struct bridge_iflist *bif)
801 {
802         if (bif->bif_config_pending)
803                 bstp_transmit_config(sc, bif);
804 }
805
806 void
807 bstp_initialization(struct bridge_softc *sc)
808 {
809         struct bridge_iflist *bif, *mif;
810
811         mif = NULL;
812         LIST_FOREACH(bif, &sc->sc_iflist, bif_next) {
813                 if ((bif->bif_flags & IFBIF_STP) == 0)
814                         continue;
815                 if (bif->bif_ifp->if_type != IFT_ETHER)
816                         continue;
817                 bif->bif_port_id = (bif->bif_priority << 8) |
818                     (bif->bif_ifp->if_index & 0xff);
819
820                 if (mif == NULL) {
821                         mif = bif;
822                         continue;
823                 }
824                 if (memcmp(IF_LLADDR(bif->bif_ifp),
825                     IF_LLADDR(mif->bif_ifp), ETHER_ADDR_LEN) < 0) {
826                         mif = bif;
827                         continue;
828                 }
829         }
830         if (mif == NULL) {
831                 bstp_stop(sc);
832                 return;
833         }
834
835         sc->sc_bridge_id =
836             (((uint64_t)sc->sc_bridge_priority) << 48) |
837             (((uint64_t)IF_LLADDR(mif->bif_ifp)[0]) << 40) |
838             (((uint64_t)IF_LLADDR(mif->bif_ifp)[1]) << 32) |
839             (IF_LLADDR(mif->bif_ifp)[2] << 24) |
840             (IF_LLADDR(mif->bif_ifp)[3] << 16) |
841             (IF_LLADDR(mif->bif_ifp)[4] << 8) |
842             (IF_LLADDR(mif->bif_ifp)[5]);
843
844         sc->sc_designated_root = sc->sc_bridge_id;
845         sc->sc_root_path_cost = 0;
846         sc->sc_root_port = NULL;
847
848         sc->sc_max_age = sc->sc_bridge_max_age;
849         sc->sc_hello_time = sc->sc_bridge_hello_time;
850         sc->sc_forward_delay = sc->sc_bridge_forward_delay;
851         sc->sc_topology_change_detected = 0;
852         sc->sc_topology_change = 0;
853         bstp_timer_stop(&sc->sc_tcn_timer);
854         bstp_timer_stop(&sc->sc_topology_change_timer);
855
856         if (callout_pending(&sc->sc_bstpcallout) == 0)
857                 callout_reset(&sc->sc_bstpcallout, hz,
858                     bstp_tick, sc);
859
860         LIST_FOREACH(bif, &sc->sc_iflist, bif_next) {
861                 if (bif->bif_flags & IFBIF_STP)
862                         bstp_ifupdstatus(sc, bif);
863                 else
864                         bstp_disable_port(sc, bif);
865         }
866
867         bstp_port_state_selection(sc);
868         bstp_config_bpdu_generation(sc);
869         bstp_timer_start(&sc->sc_hello_timer, 0);
870 }
871
872 void
873 bstp_stop(struct bridge_softc *sc)
874 {
875         struct bridge_iflist *bif;
876
877         LIST_FOREACH(bif, &sc->sc_iflist, bif_next) {
878                 bstp_set_port_state(bif, BSTP_IFSTATE_DISABLED);
879                 bstp_timer_stop(&bif->bif_hold_timer);
880                 bstp_timer_stop(&bif->bif_message_age_timer);
881                 bstp_timer_stop(&bif->bif_forward_delay_timer);
882         }
883
884         callout_stop(&sc->sc_bstpcallout);
885
886         bstp_timer_stop(&sc->sc_topology_change_timer);
887         bstp_timer_stop(&sc->sc_tcn_timer);
888         bstp_timer_stop(&sc->sc_hello_timer);
889
890 }
891
892 void
893 bstp_initialize_port(struct bridge_softc *sc, struct bridge_iflist *bif)
894 {
895         bstp_become_designated_port(sc, bif);
896         bstp_set_port_state(bif, BSTP_IFSTATE_BLOCKING);
897         bif->bif_topology_change_acknowledge = 0;
898         bif->bif_config_pending = 0;
899         bif->bif_change_detection_enabled = 1;
900         bstp_timer_stop(&bif->bif_message_age_timer);
901         bstp_timer_stop(&bif->bif_forward_delay_timer);
902         bstp_timer_stop(&bif->bif_hold_timer);
903 }
904
905 void
906 bstp_enable_port(struct bridge_softc *sc, struct bridge_iflist *bif)
907 {
908         bstp_initialize_port(sc, bif);
909         bstp_port_state_selection(sc);
910 }
911
912 void
913 bstp_disable_port(struct bridge_softc *sc, struct bridge_iflist *bif)
914 {
915         int root;
916
917         root = bstp_root_bridge(sc);
918         bstp_become_designated_port(sc, bif);
919         bstp_set_port_state(bif, BSTP_IFSTATE_DISABLED);
920         bif->bif_topology_change_acknowledge = 0;
921         bif->bif_config_pending = 0;
922         bstp_timer_stop(&bif->bif_message_age_timer);
923         bstp_timer_stop(&bif->bif_forward_delay_timer);
924         bstp_configuration_update(sc);
925         bstp_port_state_selection(sc);
926         bridge_rtdelete(sc, bif->bif_ifp, IFBF_FLUSHDYN);
927
928         if (bstp_root_bridge(sc) && (root == 0)) {
929                 sc->sc_max_age = sc->sc_bridge_max_age;
930                 sc->sc_hello_time = sc->sc_bridge_hello_time;
931                 sc->sc_forward_delay = sc->sc_bridge_forward_delay;
932
933                 bstp_topology_change_detection(sc);
934                 bstp_timer_stop(&sc->sc_tcn_timer);
935                 bstp_config_bpdu_generation(sc);
936                 bstp_timer_start(&sc->sc_hello_timer, 0);
937         }
938 }
939
940 void
941 bstp_set_bridge_priority(struct bridge_softc *sc, uint64_t new_bridge_id)
942 {
943         struct bridge_iflist *bif;
944         int root;
945
946         root = bstp_root_bridge(sc);
947
948         LIST_FOREACH(bif, &sc->sc_iflist, bif_next) {
949                 if ((bif->bif_flags & IFBIF_STP) == 0)
950                         continue;
951                 if (bstp_designated_port(sc, bif))
952                         bif->bif_designated_bridge = new_bridge_id;
953         }
954
955         sc->sc_bridge_id = new_bridge_id;
956
957         bstp_configuration_update(sc);
958         bstp_port_state_selection(sc);
959
960         if (bstp_root_bridge(sc) && (root == 0)) {
961                 sc->sc_max_age = sc->sc_bridge_max_age;
962                 sc->sc_hello_time = sc->sc_bridge_hello_time;
963                 sc->sc_forward_delay = sc->sc_bridge_forward_delay;
964
965                 bstp_topology_change_detection(sc);
966                 bstp_timer_stop(&sc->sc_tcn_timer);
967                 bstp_config_bpdu_generation(sc);
968                 bstp_timer_start(&sc->sc_hello_timer, 0);
969         }
970 }
971
972 void
973 bstp_set_port_priority(struct bridge_softc *sc, struct bridge_iflist *bif,
974     uint16_t new_port_id)
975 {
976         if (bstp_designated_port(sc, bif))
977                 bif->bif_designated_port = new_port_id;
978
979         bif->bif_port_id = new_port_id;
980
981         if ((sc->sc_bridge_id == bif->bif_designated_bridge) &&
982             (bif->bif_port_id < bif->bif_designated_port)) {
983                 bstp_become_designated_port(sc, bif);
984                 bstp_port_state_selection(sc);
985         }
986 }
987
988 void
989 bstp_set_path_cost(struct bridge_softc *sc, struct bridge_iflist *bif,
990     uint32_t path_cost)
991 {
992         bif->bif_path_cost = path_cost;
993         bstp_configuration_update(sc);
994         bstp_port_state_selection(sc);
995 }
996
997 void
998 bstp_enable_change_detection(struct bridge_iflist *bif)
999 {
1000         bif->bif_change_detection_enabled = 1;
1001 }
1002
1003 void
1004 bstp_disable_change_detection(struct bridge_iflist *bif)
1005 {
1006         bif->bif_change_detection_enabled = 0;
1007 }
1008
1009 void
1010 bstp_linkstate(struct ifnet *ifp, int state)
1011 {
1012         struct bridge_softc *sc;
1013         struct bridge_iflist *bif;
1014
1015         sc = ifp->if_bridge;
1016         lwkt_serialize_enter(sc->sc_ifp->if_serializer);
1017
1018         LIST_FOREACH(bif, &sc->sc_iflist, bif_next) {
1019                 if ((bif->bif_flags & IFBIF_STP) == 0)
1020                         continue;
1021
1022                 if (bif->bif_ifp == ifp) {
1023                         bstp_ifupdstatus(sc, bif);
1024                         break;
1025                 }
1026         }
1027         lwkt_serialize_exit(sc->sc_ifp->if_serializer);
1028 }
1029
1030 void
1031 bstp_ifupdstatus(struct bridge_softc *sc, struct bridge_iflist *bif)
1032 {
1033         struct ifnet *ifp = bif->bif_ifp;
1034         struct ifmediareq ifmr;
1035         int error = 0;
1036
1037         bzero((char *)&ifmr, sizeof(ifmr));
1038         lwkt_serialize_enter(ifp->if_serializer);
1039         error = (*ifp->if_ioctl)(ifp, SIOCGIFMEDIA, (caddr_t)&ifmr, curthread->td_proc->p_ucred);
1040         lwkt_serialize_exit(ifp->if_serializer);
1041
1042         if ((error == 0) && (ifp->if_flags & IFF_UP)) {
1043                 if (ifmr.ifm_status & IFM_ACTIVE) {
1044                         if (bif->bif_state == BSTP_IFSTATE_DISABLED)
1045                                 bstp_enable_port(sc, bif);
1046
1047                 } else {
1048                         if (bif->bif_state != BSTP_IFSTATE_DISABLED)
1049                                 bstp_disable_port(sc, bif);
1050                 }
1051                 return;
1052         }
1053
1054         if (bif->bif_state != BSTP_IFSTATE_DISABLED)
1055                 bstp_disable_port(sc, bif);
1056 }
1057
1058 void
1059 bstp_tick(void *arg)
1060 {
1061         struct bridge_softc *sc = arg;
1062         struct bridge_iflist *bif;
1063
1064         lwkt_serialize_enter(sc->sc_ifp->if_serializer);
1065
1066 #if 0
1067         LIST_FOREACH(bif, &sc->sc_iflist, bif_next) {
1068                 if ((bif->bif_flags & IFBIF_STP) == 0)
1069                         continue;
1070                 /*
1071                  * XXX This can cause a lag in "link does away"
1072                  * XXX and "spanning tree gets updated".  We need
1073                  * XXX come sort of callback from the link state
1074                  * XXX update code to kick spanning tree.
1075                  * XXX --thorpej@NetBSD.org
1076                  */
1077                 bstp_ifupdstatus(sc, bif);
1078         }
1079 #endif
1080
1081         if (bstp_timer_expired(&sc->sc_hello_timer, sc->sc_hello_time))
1082                 bstp_hello_timer_expiry(sc);
1083
1084         if (bstp_timer_expired(&sc->sc_tcn_timer, sc->sc_bridge_hello_time))
1085                 bstp_tcn_timer_expiry(sc);
1086
1087         if (bstp_timer_expired(&sc->sc_topology_change_timer,
1088             sc->sc_topology_change_time))
1089                 bstp_topology_change_timer_expiry(sc);
1090
1091         LIST_FOREACH(bif, &sc->sc_iflist, bif_next) {
1092                 if ((bif->bif_flags & IFBIF_STP) == 0)
1093                         continue;
1094                 if (bstp_timer_expired(&bif->bif_message_age_timer,
1095                     sc->sc_max_age))
1096                         bstp_message_age_timer_expiry(sc, bif);
1097         }
1098
1099         LIST_FOREACH(bif, &sc->sc_iflist, bif_next) {
1100                 if ((bif->bif_flags & IFBIF_STP) == 0)
1101                         continue;
1102                 if (bstp_timer_expired(&bif->bif_forward_delay_timer,
1103                     sc->sc_forward_delay))
1104                         bstp_forward_delay_timer_expiry(sc, bif);
1105
1106                 if (bstp_timer_expired(&bif->bif_hold_timer,
1107                     sc->sc_hold_time))
1108                         bstp_hold_timer_expiry(sc, bif);
1109         }
1110
1111         if (sc->sc_ifp->if_flags & IFF_RUNNING)
1112                 callout_reset(&sc->sc_bstpcallout, hz, bstp_tick, sc);
1113
1114         lwkt_serialize_exit(sc->sc_ifp->if_serializer);
1115 }
1116
1117 void
1118 bstp_timer_start(struct bridge_timer *t, uint16_t v)
1119 {
1120         t->value = v;
1121         t->active = 1;
1122 }
1123
1124 void
1125 bstp_timer_stop(struct bridge_timer *t)
1126 {
1127         t->value = 0;
1128         t->active = 0;
1129 }
1130
1131 int
1132 bstp_timer_expired(struct bridge_timer *t, uint16_t v)
1133 {
1134         if (t->active == 0)
1135                 return (0);
1136         t->value += BSTP_TICK_VAL;
1137         if (t->value >= v) {
1138                 bstp_timer_stop(t);
1139                 return (1);
1140         }
1141         return (0);
1142
1143 }