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