]> git.saurik.com Git - apple/xnu.git/blob - bsd/net/bridgestp.c
projects / apple / xnu.git / blob
? search:


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