2 * mstp.h State machines from IEEE 802.1Q-2005
4 * This program is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU General Public License
6 * as published by the Free Software Foundation; either version
7 * 2 of the License, or (at your option) any later version.
9 * Authors: Vitalii Demianets <vitas@nppfactor.kiev.ua>
17 #include "bridge_ctl.h"
20 /* #define HMAC_MDS_TEST_FUNCTIONS */
22 /* Useful macro for counting number of elements in array */
23 #define COUNT_OF(x) ((sizeof(x)/sizeof(0[x])) / ((size_t)(!(sizeof(x) % sizeof(0[x])))))
26 * assign() and cmp() macros that also do strict type-checking. See the
27 * "unnecessary" pointer comparison.
28 * NOTE: potential double-evaluation of the first argument in assign macro!
29 * It is the price for type-safety ;)
31 #define assign(x, y) ({ \
32 typeof(x) _assign1 = (x); \
33 typeof(y) _assign2 = (y); \
34 (void)(&_assign1 == &_assign2); \
36 #define _ncmp(x, y) ({ \
37 typeof(x) _cmp1 = (x); \
38 typeof(y) _cmp2 = (y); \
39 (void)(&_cmp1 == &_cmp2); \
40 memcmp(&_cmp1, &_cmp2, sizeof(_cmp1)); })
41 #define cmp(x, _op, y) (_ncmp((x), (y)) _op 0)
43 /* 13.7, Table 13-1 */
44 #define HMAC_KEY {0x13, 0xAC, 0x06, 0xA6, 0x2E, 0x47, 0xFD, 0x51, \
45 0xF9, 0x5D, 0x2B, 0xA2, 0x43, 0xCD, 0x03, 0x46}
46 extern void hmac_md5(unsigned char * text
, int text_len
, unsigned char * key
,
47 int key_len
, caddr_t digest
);
48 #ifdef HMAC_MDS_TEST_FUNCTIONS
49 extern bool MD5TestSuite(void);
50 #endif /* HMAC_MDS_TEST_FUNCTIONS */
52 #define MAX_PORT_NUMBER 4095
55 #define MAX_MSTID 4094
57 /* MAX_xxx_MSTIS: CIST not counted */
58 #define MAX_STANDARD_MSTIS 64
59 #define MAX_IMPLEMENTATION_MSTIS 63
62 #define MAX_PATH_COST 200000000u
70 __u8 mac_address
[ETH_ALEN
];
71 } __attribute__((packed
)) s
;
72 } bridge_identifier_t
;
74 typedef __be16 port_identifier_t
;
76 /* These macros work well for both PortID and BridgeID */
77 #define GET_PRIORITY_FROM_IDENTIFIER(id) (((__u8 *)(&(id)))[0] & 0xF0)
78 #define SET_PRIORITY_IN_IDENTIFIER(pri, id) do{ \
79 __u8 *first_octet = (__u8 *)(&(id)); \
80 *first_octet &= 0x0F; \
81 *first_octet |= (pri) & 0xF0; \
84 #define CONFIGURATION_NAME_LEN 32
85 #define CONFIGURATION_DIGEST_LEN 16
88 __u8 a
[1 + CONFIGURATION_NAME_LEN
+ 2 + CONFIGURATION_DIGEST_LEN
];
91 __u8 selector
; /* always 0 */
92 __u8 configuration_name
[CONFIGURATION_NAME_LEN
];
93 __be16 revision_level
;
94 __u8 configuration_digest
[CONFIGURATION_DIGEST_LEN
];
95 } __attribute__((packed
)) s
;
96 } __attribute__((packed
)) mst_configuration_identifier_t
;
100 bridge_identifier_t RRootID
;
101 __be32 IntRootPathCost
;
102 bridge_identifier_t DesignatedBridgeID
;
103 port_identifier_t DesignatedPortID
;
104 /* not used for MSTIs, only for CIST */
105 bridge_identifier_t RootID
;
106 __be32 ExtRootPathCost
;
107 } port_priority_vector_t
;
109 /* 17.14 of 802.1D, Table 17-1 */
110 #define MIN_COMPAT_HELLO_TIME 1
115 /* not used for MSTIs, only for CIST */
124 /* see bpduFlagOffset_t enum for offsets of flag bits */
126 bridge_identifier_t mstiRRootID
;
127 __be32 mstiIntRootPathCost
;
128 /* only bits 7..4, bits 3..0 are zero on Tx and ignored on Rx */
129 __u8 bridgeIdentifierPriority
;
130 /* only bits 7..4, bits 3..0 are zero on Tx and ignored on Rx */
131 __u8 portIdentifierPriority
;
133 } __attribute__((packed
)) msti_configuration_message_t
;
137 /* always zero for the Spanning Tree BPDUs */
138 __be16 protocolIdentifier
;
139 /* protoSTP for the Config and TCN
140 * protoRSTP for the RST
141 * protoMSTP for the MST
142 * (see protocol_version_t enum) */
143 __u8 protocolVersion
;
144 /* values are defined in bpduType_t enum */
146 /* TCN BPDU ends here */
147 /* see bpduFlagOffset_t enum for offsets of flag bits */
149 bridge_identifier_t cistRootID
;
150 __be32 cistExtRootPathCost
;
151 bridge_identifier_t cistRRootID
;
152 port_identifier_t cistPortID
;
156 __u8 ForwardDelay
[2];
157 /* Config BPDU ends here */
158 __u8 version1_len
; /* always zero */
159 /* RST BPDU ends here */
161 mst_configuration_identifier_t mstConfigurationIdentifier
;
162 __be32 cistIntRootPathCost
;
163 bridge_identifier_t cistBridgeID
;
164 __u8 cistRemainingHops
;
165 msti_configuration_message_t mstConfiguration
[MAX_STANDARD_MSTIS
];
166 } __attribute__((packed
)) bpdu_t
;
168 #define TCN_BPDU_SIZE offsetof(bpdu_t, flags)
169 #define CONFIG_BPDU_SIZE offsetof(bpdu_t, version1_len)
170 #define RST_BPDU_SIZE offsetof(bpdu_t, version3_len)
171 #define MST_BPDU_SIZE_WO_MSTI_MSGS offsetof(bpdu_t, mstConfiguration)
172 #define MST_BPDU_VER3LEN_WO_MSTI_MSGS (MST_BPDU_SIZE_WO_MSTI_MSGS \
173 - offsetof(bpdu_t, mstConfigurationIdentifier))
178 SuperiorDesignatedInfo
,
179 RepeatedDesignatedInfo
,
180 InferiorDesignatedInfo
,
181 InferiorRootAlternateInfo
190 } port_info_origin_t
;
204 encodedRoleMaster
= 0,
205 encodedRoleAlternateBackup
= 1,
207 encodedRoleDesignated
= 3
208 } port_encoded_role_t
;
215 } protocol_version_t
;
228 offsetRole
= 2, /* actually, role is coded in two-bit field */
229 offsetRole1
= 3, /* second bit of two-bit role field */
231 offsetForwarding
= 5,
234 /* in MSTI Configuration Message flags bit7 is used for Master flag */
235 #define offsetMaster offsetTcAck
238 #define BPDU_FLAGS_ROLE_SET(role) (((role) & 3) << offsetRole)
239 #define BPDU_FLAGS_ROLE_GET(flags) (((flags) >> offsetRole) & 3)
249 /* 13.28 Port Receive state machine */
256 /* 13.29 Port Protocol Migration state machine */
264 /* 13.30 Bridge Detection state machine */
271 /* 13.31 Port Transmit state machine */
275 PTSM_TRANSMIT_CONFIG
,
278 PTSM_TRANSMIT_PERIODIC
,
282 /* 13.32 Port Information state machine */
283 /* #define PISM_ENABLE_LOG */
289 PISM_SUPERIOR_DESIGNATED
,
290 PISM_REPEATED_DESIGNATED
,
291 PISM_INFERIOR_DESIGNATED
,
298 /* 13.33 Port Role Selection state machine */
305 /* 13.34 Port Role Transitions state machine */
306 /* #define PRTSM_ENABLE_LOG */
309 /* Disabled Port role transitions */
313 /* MasterPort role transitions */
314 PRTSM_MASTER_PROPOSED
,
317 PRTSM_MASTER_RETIRED
,
318 PRTSM_MASTER_FORWARD
,
320 PRTSM_MASTER_DISCARD
,
322 /* RootPort role transitions */
331 /* DesignatedPort role transitions */
332 PRTSM_DESIGNATED_PROPOSE
,
333 PRTSM_DESIGNATED_AGREED
,
334 PRTSM_DESIGNATED_SYNCED
,
335 PRTSM_DESIGNATED_RETIRED
,
336 PRTSM_DESIGNATED_FORWARD
,
337 PRTSM_DESIGNATED_LEARN
,
338 PRTSM_DESIGNATED_DISCARD
,
339 PRTSM_DESIGNATED_PORT
,
340 /* AlternatePort and BackupPort role transitions */
343 PRTSM_ALTERNATE_PROPOSED
,
344 PRTSM_ALTERNATE_AGREED
,
348 /* 13.35 Port State Transition state machine */
356 /* 13.36 Topology Change state machine */
370 * Following standard-defined variables are not defined as variables.
371 * Their functionality is implemented indirectly by other means:
372 * - BEGIN, tick, ageingTime.
377 struct list_head list
; /* anchor in global list of bridges */
379 /* List of all ports */
380 struct list_head ports
;
381 /* List of all tree instances, first in list (trees.next) is CIST */
382 struct list_head trees
;
383 #define GET_CIST_TREE(br) list_entry((br)->trees.next, tree_t, bridge_list)
387 /* Per-bridge configuration parameters */
388 mst_configuration_identifier_t MstConfigId
; /* 13.24.b */
389 protocol_version_t ForceProtocolVersion
; /* 13.22.e */
390 __u8 MaxHops
; /* 13.22.o */
391 __u8 Forward_Delay
; /* 13.22.f */
392 __u8 Max_Age
; /* 13.22.i */
393 unsigned int Transmit_Hold_Count
; /* 13.22.g */
394 unsigned int Migrate_Time
; /* 13.22.h */
395 unsigned int rapidAgeingWhile
;
397 __u16 vid2fid
[MAX_VID
+ 1];
398 __be16 fid2mstid
[MAX_FID
+ 1];
400 /* not in standard */
403 sysdep_br_data_t sysdeps
;
408 struct list_head bridge_list
; /* anchor in bridge's list of trees */
410 __be16 MSTID
; /* 0 == CIST */
412 /* List of the per-port data structures for this tree instance */
413 struct list_head ports
;
415 /* 13.23.(c,f,g) Per-bridge per-tree variables */
416 bridge_identifier_t BridgeIdentifier
;
417 port_identifier_t rootPortId
;
418 port_priority_vector_t rootPriority
;
420 /* 13.23.d This is totally calculated from BridgeIdentifier */
421 port_priority_vector_t BridgePriority
;
423 /* 13.23.e Some waste of space here, as MSTIs only use
424 * remainingHops member of the struct times_t,
425 * but saves extra checks and improves readability */
426 times_t BridgeTimes
, rootTimes
;
428 /* 12.8.1.1.3.(b,c,d) */
429 unsigned int time_since_topology_change
;
430 unsigned int topology_change_count
;
431 bool topology_change
;
434 PRSSM_states_t PRSSM_state
;
440 struct list_head br_list
; /* anchor in bridge's list of ports */
444 /* List of all tree instances, first in list (trees.next) is CIST.
445 * List is sorted by MSTID (by insertion procedure MSTP_IN_create_msti).
447 struct list_head trees
;
448 #define GET_CIST_PTP_FROM_PORT(prt) \
449 list_entry((prt)->trees.next, per_tree_port_t, port_list)
451 /* 13.21.(a,b,c) Per-port timers */
452 unsigned int mdelayWhile
, helloWhen
, edgeDelayWhile
;
454 /* 13.24.(b,c,e,f,g,j,k,l,m,n,o,p,q,r,aw) Per-port variables */
455 unsigned int txCount
;
456 bool operEdge
, portEnabled
, infoInternal
, rcvdInternal
;
457 bool mcheck
, rcvdBpdu
, rcvdRSTP
, rcvdSTP
, rcvdTcAck
, rcvdTcn
, sendRSTP
;
458 bool tcAck
, newInfo
, newInfoMsti
;
461 bool operPointToPointMAC
;
463 /* Per-port configuration parameters */
464 bool restrictedRole
, restrictedTcn
; /* 13.24.(h,i) */
465 __u32 ExternalPortPathCost
; /* 13.22.p */
466 __u32 AdminExternalPortPathCost
; /* 0 = calculate from speed */
467 admin_p2p_t AdminP2P
; /* 6.4.3 */
468 bool AdminEdgePort
; /* 13.22.k */
469 bool AutoEdge
; /* 13.22.m */
472 PRSM_states_t PRSM_state
;
473 PPMSM_states_t PPMSM_state
;
474 BDSM_states_t BDSM_state
;
475 PTSM_states_t PTSM_state
;
477 /* Copy of the received BPDU */
479 int rcvdBpduNumOfMstis
;
481 sysdep_if_data_t sysdeps
;
486 struct list_head port_list
; /* anchor in port's list of trees */
487 struct list_head tree_list
; /* anchor in tree's list of per-port data */
490 __be16 MSTID
; /* 0 == CIST */
492 int state
; /* BR_STATE_xxx */
494 /* 13.21.(d,e,f,g,h) Per-port per-tree timers */
495 unsigned int fdWhile
, rrWhile
, rbWhile
, tcWhile
, rcvdInfoWhile
;
497 /* 13.24.(s,t,u,v,w,x,y,z,aa,ab,ac,ad,ae,af,ag,ai,aj,ak,ap,as,at,au,av)
498 * Per-port per-tree variables */
499 bool agree
, agreed
, disputed
, forward
, forwarding
, learn
, learning
;
500 port_info_t rcvdInfo
;
501 port_info_origin_t infoIs
;
502 bool proposed
, proposing
, rcvdMsg
, rcvdTc
, reRoot
, reselect
, selected
;
503 bool fdbFlush
, tcProp
, updtInfo
, sync
, synced
;
504 port_identifier_t portId
;
505 port_role_t role
, selectedRole
;
507 /* 13.24.(al,an,aq) Some waste of space here, as MSTIs don't use
508 * RootID and ExtRootPathCost members of the struct port_priority_vector_t,
509 * but saves extra checks and improves readability */
510 port_priority_vector_t designatedPriority
, msgPriority
, portPriority
;
512 /* 13.24.(am,ao,ar) Some waste of space here, as MSTIs only use
513 * remainingHops member of the struct times_t,
514 * but saves extra checks and improves readability */
515 times_t designatedTimes
, msgTimes
, portTimes
;
517 /* 13.24.(ax,ay) Per-port per-MSTI variables, not applicable to CIST */
518 bool master
, mastered
;
520 /* Per-port per-tree configuration parameters */
521 __u32 InternalPortPathCost
; /* 13.22.q */
522 __u32 AdminInternalPortPathCost
; /* 0 = calculate from speed */
524 /* not in standard, used for calculation of port uptime */
525 unsigned int start_time
;
528 PISM_states_t PISM_state
;
529 PRTSM_states_t PRTSM_state
;
530 PSTSM_states_t PSTSM_state
;
531 TCSM_states_t TCSM_state
;
533 /* Auxiliary flag, helps preventing infinite recursion */
534 bool calledFromFlushRoutine
;
536 /* Pointer to the corresponding MSTI Configuration Message
537 * in the port->rcvdBpduData */
538 msti_configuration_message_t
*rcvdMstiConfig
;
541 /* External events (inputs) */
542 bool MSTP_IN_bridge_create(bridge_t
*br
, __u8
*macaddr
);
543 bool MSTP_IN_port_create_and_add_tail(port_t
*prt
, __u16 portno
);
544 void MSTP_IN_delete_port(port_t
*prt
);
545 void MSTP_IN_delete_bridge(bridge_t
*br
);
546 void MSTP_IN_set_bridge_address(bridge_t
*br
, __u8
*macaddr
);
547 void MSTP_IN_set_bridge_enable(bridge_t
*br
, bool up
);
548 void MSTP_IN_set_port_enable(port_t
*prt
, bool up
, int speed
, int duplex
);
549 void MSTP_IN_one_second(bridge_t
*br
);
550 void MSTP_IN_all_fids_flushed(per_tree_port_t
*ptp
);
551 void MSTP_IN_rx_bpdu(port_t
*prt
, bpdu_t
*bpdu
, int size
);
553 bool MSTP_IN_set_vid2fid(bridge_t
*br
, __u16 vid
, __u16 fid
);
554 bool MSTP_IN_set_all_vids2fids(bridge_t
*br
, __u16
*vids2fids
);
555 bool MSTP_IN_set_fid2mstid(bridge_t
*br
, __u16 fid
, __u16 mstid
);
556 bool MSTP_IN_set_all_fids2mstids(bridge_t
*br
, __u16
*fids2mstids
);
557 bool MSTP_IN_get_mstilist(bridge_t
*br
, int *num_mstis
, __u16
*mstids
);
558 bool MSTP_IN_create_msti(bridge_t
*br
, __u16 mstid
);
559 bool MSTP_IN_delete_msti(bridge_t
*br
, __u16 mstid
);
560 void MSTP_IN_set_mst_config_id(bridge_t
*br
, __u16 revision
, __u8
*name
);
562 /* External actions (outputs) */
563 void MSTP_OUT_set_state(per_tree_port_t
*ptp
, int new_state
);
564 void MSTP_OUT_flush_all_fids(per_tree_port_t
*ptp
);
565 void MSTP_OUT_set_ageing_time(bridge_t
*br
, int ageingTime
);
566 void MSTP_OUT_tx_bpdu(port_t
*prt
, bpdu_t
*bpdu
, int size
);
568 /* Structures for communicating with user */
569 /* 12.8.1.1 Read CIST Bridge Protocol Parameters */
572 bridge_identifier_t bridge_id
;
573 unsigned int time_since_topology_change
;
574 unsigned int topology_change_count
;
575 bool topology_change
;
576 bridge_identifier_t designated_root
;
577 unsigned int root_path_cost
;
578 port_identifier_t root_port_id
;
580 __u8 root_forward_delay
;
582 __u8 bridge_forward_delay
;
583 unsigned int tx_hold_count
;
584 protocol_version_t protocol_version
;
585 bridge_identifier_t regional_root
;
586 unsigned int internal_path_cost
;
587 bool enabled
; /* not in standard */
591 void MSTP_IN_get_cist_bridge_status(bridge_t
*br
, CIST_BridgeStatus
*status
);
593 /* 12.8.1.2 Read MSTI Bridge Protocol Parameters */
596 bridge_identifier_t bridge_id
;
597 unsigned int time_since_topology_change
;
598 unsigned int topology_change_count
;
599 bool topology_change
;
600 bridge_identifier_t regional_root
;
601 unsigned int internal_path_cost
;
602 port_identifier_t root_port_id
;
605 void MSTP_IN_get_msti_bridge_status(tree_t
*tree
, MSTI_BridgeStatus
*status
);
607 /* 12.8.1.3 Set CIST Bridge Protocol Parameters */
611 bool set_bridge_max_age
;
613 __u8 bridge_forward_delay
;
614 bool set_bridge_forward_delay
;
616 /* Superseded by MSTP_IN_set_msti_bridge_config for the CIST.
617 * __u8 bridge_priority;
618 * bool set_bridge_priority; */
620 protocol_version_t protocol_version
;
621 bool set_protocol_version
;
623 unsigned int tx_hold_count
;
624 bool set_tx_hold_count
;
630 int MSTP_IN_set_cist_bridge_config(bridge_t
*br
, CIST_BridgeConfig
*cfg
);
632 /* 12.8.1.4 Set MSTI Bridge Protocol Parameters */
633 /* No need in special structure for single parameter Bridge Priority */
635 int MSTP_IN_set_msti_bridge_config(tree_t
*tree
, __u8 bridge_priority
);
637 /* 12.8.2.1 Read CIST Port Parameters */
641 int state
; /* BR_STATE_xxx */
642 port_identifier_t port_id
;
643 __u32 admin_external_port_path_cost
; /* not in standard. 0 = auto */
644 __u32 external_port_path_cost
;
645 bridge_identifier_t designated_root
; /* from portPriority */
646 __u32 designated_external_cost
; /* from portPriority */
647 bridge_identifier_t designated_bridge
; /* from portPriority */
648 port_identifier_t designated_port
; /* from portPriority */
649 bool tc_ack
; /* tcAck */
650 __u8 port_hello_time
; /* from portTimes */
651 bool admin_edge_port
;
652 bool auto_edge_port
; /* not in standard */
654 /* 802.1Q-2005 wants here MAC_Enabled & MAC_Operational. We don't know
655 * neither of these. Return portEnabled and feel happy. */
657 admin_p2p_t admin_p2p
;
659 bool restricted_role
;
663 bridge_identifier_t designated_regional_root
; /* from portPriority */
664 __u32 designated_internal_cost
; /* from portPriority */
665 __u32 admin_internal_port_path_cost
; /* not in standard. 0 = auto */
666 __u32 internal_port_path_cost
; /* not in standard */
669 void MSTP_IN_get_cist_port_status(port_t
*prt
, CIST_PortStatus
*status
);
671 /* 12.8.2.2 Read MSTI Port Parameters */
675 int state
; /* BR_STATE_xxx */
676 port_identifier_t port_id
;
677 __u32 admin_internal_port_path_cost
; /* not in standard. 0 = auto */
678 __u32 internal_port_path_cost
;
679 bridge_identifier_t designated_regional_root
; /* from portPriority */
680 __u32 designated_internal_cost
; /* from portPriority */
681 bridge_identifier_t designated_bridge
; /* from portPriority */
682 port_identifier_t designated_port
; /* from portPriority */
687 void MSTP_IN_get_msti_port_status(per_tree_port_t
*ptp
,
688 MSTI_PortStatus
*status
);
690 /* 12.8.2.3 Set CIST port parameters */
693 __u32 admin_external_port_path_cost
; /* not in standard. 0 = auto */
694 bool set_admin_external_port_path_cost
;
696 /* Superseded by MSTP_IN_set_msti_port_config for the CIST.
697 * __u32 admin_internal_port_path_cost;
698 * bool set_admin_internal_port_path_cost;
700 * __u8 port_priority;
701 * bool set_port_priority;
704 bool admin_edge_port
;
705 bool set_admin_edge_port
;
707 bool auto_edge_port
; /* not in standard */
708 bool set_auto_edge_port
;
710 admin_p2p_t admin_p2p
;
713 bool restricted_role
;
714 bool set_restricted_role
;
717 bool set_restricted_tcn
;
720 int MSTP_IN_set_cist_port_config(port_t
*prt
, CIST_PortConfig
*cfg
);
722 /* 12.8.2.4 Set MSTI port parameters */
725 __u32 admin_internal_port_path_cost
; /* 0 = auto */
726 bool set_admin_internal_port_path_cost
;
729 bool set_port_priority
;
732 int MSTP_IN_set_msti_port_config(per_tree_port_t
*ptp
, MSTI_PortConfig
*cfg
);
734 /* 12.8.2.5 Force BPDU Migration Check */
735 int MSTP_IN_port_mcheck(port_t
*prt
);