br_stp.c 11 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459
  1. /*
  2. * Spanning tree protocol; generic parts
  3. * Linux ethernet bridge
  4. *
  5. * Authors:
  6. * Lennert Buytenhek <buytenh@gnu.org>
  7. *
  8. * $Id: br_stp.c,v 1.1.1.1 2007/06/12 07:27:14 eyryu Exp $
  9. *
  10. * This program is free software; you can redistribute it and/or
  11. * modify it under the terms of the GNU General Public License
  12. * as published by the Free Software Foundation; either version
  13. * 2 of the License, or (at your option) any later version.
  14. */
  15. #include <linux/kernel.h>
  16. #include <linux/smp_lock.h>
  17. #include "br_private.h"
  18. #include "br_private_stp.h"
  19. /* since time values in bpdu are in jiffies and then scaled (1/256)
  20. * before sending, make sure that is at least one.
  21. */
  22. #define MESSAGE_AGE_INCR ((HZ < 256) ? 1 : (HZ/256))
  23. static const char *br_port_state_names[] = {
  24. [BR_STATE_DISABLED] = "disabled",
  25. [BR_STATE_LISTENING] = "listening",
  26. [BR_STATE_LEARNING] = "learning",
  27. [BR_STATE_FORWARDING] = "forwarding",
  28. [BR_STATE_BLOCKING] = "blocking",
  29. };
  30. void br_log_state(const struct net_bridge_port *p)
  31. {
  32. pr_info("%s: port %d(%s) entering %s state\n",
  33. p->br->dev->name, p->port_no, p->dev->name,
  34. br_port_state_names[p->state]);
  35. }
  36. /* called under bridge lock */
  37. struct net_bridge_port *br_get_port(struct net_bridge *br, u16 port_no)
  38. {
  39. struct net_bridge_port *p;
  40. list_for_each_entry_rcu(p, &br->port_list, list) {
  41. if (p->port_no == port_no)
  42. return p;
  43. }
  44. return NULL;
  45. }
  46. /* called under bridge lock */
  47. static int br_should_become_root_port(const struct net_bridge_port *p,
  48. u16 root_port)
  49. {
  50. struct net_bridge *br;
  51. struct net_bridge_port *rp;
  52. int t;
  53. br = p->br;
  54. if (p->state == BR_STATE_DISABLED ||
  55. br_is_designated_port(p))
  56. return 0;
  57. if (memcmp(&br->bridge_id, &p->designated_root, 8) <= 0)
  58. return 0;
  59. if (!root_port)
  60. return 1;
  61. rp = br_get_port(br, root_port);
  62. t = memcmp(&p->designated_root, &rp->designated_root, 8);
  63. if (t < 0)
  64. return 1;
  65. else if (t > 0)
  66. return 0;
  67. if (p->designated_cost + p->path_cost <
  68. rp->designated_cost + rp->path_cost)
  69. return 1;
  70. else if (p->designated_cost + p->path_cost >
  71. rp->designated_cost + rp->path_cost)
  72. return 0;
  73. t = memcmp(&p->designated_bridge, &rp->designated_bridge, 8);
  74. if (t < 0)
  75. return 1;
  76. else if (t > 0)
  77. return 0;
  78. if (p->designated_port < rp->designated_port)
  79. return 1;
  80. else if (p->designated_port > rp->designated_port)
  81. return 0;
  82. if (p->port_id < rp->port_id)
  83. return 1;
  84. return 0;
  85. }
  86. /* called under bridge lock */
  87. static void br_root_selection(struct net_bridge *br)
  88. {
  89. struct net_bridge_port *p;
  90. u16 root_port = 0;
  91. list_for_each_entry(p, &br->port_list, list) {
  92. if (br_should_become_root_port(p, root_port))
  93. root_port = p->port_no;
  94. }
  95. br->root_port = root_port;
  96. if (!root_port) {
  97. br->designated_root = br->bridge_id;
  98. br->root_path_cost = 0;
  99. } else {
  100. p = br_get_port(br, root_port);
  101. br->designated_root = p->designated_root;
  102. br->root_path_cost = p->designated_cost + p->path_cost;
  103. }
  104. }
  105. /* called under bridge lock */
  106. void br_become_root_bridge(struct net_bridge *br)
  107. {
  108. br->max_age = br->bridge_max_age;
  109. br->hello_time = br->bridge_hello_time;
  110. br->forward_delay = br->bridge_forward_delay;
  111. br_topology_change_detection(br);
  112. del_timer(&br->tcn_timer);
  113. if (br->dev->flags & IFF_UP) {
  114. br_config_bpdu_generation(br);
  115. mod_timer(&br->hello_timer, jiffies + br->hello_time);
  116. }
  117. }
  118. /* called under bridge lock */
  119. void br_transmit_config(struct net_bridge_port *p)
  120. {
  121. struct br_config_bpdu bpdu;
  122. struct net_bridge *br;
  123. if (timer_pending(&p->hold_timer)) {
  124. p->config_pending = 1;
  125. return;
  126. }
  127. br = p->br;
  128. bpdu.topology_change = br->topology_change;
  129. bpdu.topology_change_ack = p->topology_change_ack;
  130. bpdu.root = br->designated_root;
  131. bpdu.root_path_cost = br->root_path_cost;
  132. bpdu.bridge_id = br->bridge_id;
  133. bpdu.port_id = p->port_id;
  134. if (br_is_root_bridge(br))
  135. bpdu.message_age = 0;
  136. else {
  137. struct net_bridge_port *root
  138. = br_get_port(br, br->root_port);
  139. bpdu.message_age = br->max_age
  140. - (root->message_age_timer.expires - jiffies)
  141. + MESSAGE_AGE_INCR;
  142. }
  143. bpdu.max_age = br->max_age;
  144. bpdu.hello_time = br->hello_time;
  145. bpdu.forward_delay = br->forward_delay;
  146. if (bpdu.message_age < br->max_age) {
  147. br_send_config_bpdu(p, &bpdu);
  148. p->topology_change_ack = 0;
  149. p->config_pending = 0;
  150. mod_timer(&p->hold_timer, jiffies + BR_HOLD_TIME);
  151. }
  152. }
  153. /* called under bridge lock */
  154. static inline void br_record_config_information(struct net_bridge_port *p,
  155. const struct br_config_bpdu *bpdu)
  156. {
  157. p->designated_root = bpdu->root;
  158. p->designated_cost = bpdu->root_path_cost;
  159. p->designated_bridge = bpdu->bridge_id;
  160. p->designated_port = bpdu->port_id;
  161. mod_timer(&p->message_age_timer, jiffies
  162. + (p->br->max_age - bpdu->message_age));
  163. }
  164. /* called under bridge lock */
  165. static inline void br_record_config_timeout_values(struct net_bridge *br,
  166. const struct br_config_bpdu *bpdu)
  167. {
  168. br->max_age = bpdu->max_age;
  169. br->hello_time = bpdu->hello_time;
  170. br->forward_delay = bpdu->forward_delay;
  171. br->topology_change = bpdu->topology_change;
  172. }
  173. /* called under bridge lock */
  174. void br_transmit_tcn(struct net_bridge *br)
  175. {
  176. br_send_tcn_bpdu(br_get_port(br, br->root_port));
  177. }
  178. /* called under bridge lock */
  179. static int br_should_become_designated_port(const struct net_bridge_port *p)
  180. {
  181. struct net_bridge *br;
  182. int t;
  183. br = p->br;
  184. if (br_is_designated_port(p))
  185. return 1;
  186. if (memcmp(&p->designated_root, &br->designated_root, 8))
  187. return 1;
  188. if (br->root_path_cost < p->designated_cost)
  189. return 1;
  190. else if (br->root_path_cost > p->designated_cost)
  191. return 0;
  192. t = memcmp(&br->bridge_id, &p->designated_bridge, 8);
  193. if (t < 0)
  194. return 1;
  195. else if (t > 0)
  196. return 0;
  197. if (p->port_id < p->designated_port)
  198. return 1;
  199. return 0;
  200. }
  201. /* called under bridge lock */
  202. static void br_designated_port_selection(struct net_bridge *br)
  203. {
  204. struct net_bridge_port *p;
  205. list_for_each_entry(p, &br->port_list, list) {
  206. if (p->state != BR_STATE_DISABLED &&
  207. br_should_become_designated_port(p))
  208. br_become_designated_port(p);
  209. }
  210. }
  211. /* called under bridge lock */
  212. static int br_supersedes_port_info(struct net_bridge_port *p, struct br_config_bpdu *bpdu)
  213. {
  214. int t;
  215. t = memcmp(&bpdu->root, &p->designated_root, 8);
  216. if (t < 0)
  217. return 1;
  218. else if (t > 0)
  219. return 0;
  220. if (bpdu->root_path_cost < p->designated_cost)
  221. return 1;
  222. else if (bpdu->root_path_cost > p->designated_cost)
  223. return 0;
  224. t = memcmp(&bpdu->bridge_id, &p->designated_bridge, 8);
  225. if (t < 0)
  226. return 1;
  227. else if (t > 0)
  228. return 0;
  229. if (memcmp(&bpdu->bridge_id, &p->br->bridge_id, 8))
  230. return 1;
  231. if (bpdu->port_id <= p->designated_port)
  232. return 1;
  233. return 0;
  234. }
  235. /* called under bridge lock */
  236. static inline void br_topology_change_acknowledged(struct net_bridge *br)
  237. {
  238. br->topology_change_detected = 0;
  239. del_timer(&br->tcn_timer);
  240. }
  241. /* called under bridge lock */
  242. void br_topology_change_detection(struct net_bridge *br)
  243. {
  244. int isroot = br_is_root_bridge(br);
  245. pr_info("%s: topology change detected, %s\n", br->dev->name,
  246. isroot ? "propagating" : "sending tcn bpdu");
  247. if (isroot) {
  248. br->topology_change = 1;
  249. mod_timer(&br->topology_change_timer, jiffies
  250. + br->bridge_forward_delay + br->bridge_max_age);
  251. } else if (!br->topology_change_detected) {
  252. br_transmit_tcn(br);
  253. mod_timer(&br->tcn_timer, jiffies + br->bridge_hello_time);
  254. }
  255. br->topology_change_detected = 1;
  256. }
  257. /* called under bridge lock */
  258. void br_config_bpdu_generation(struct net_bridge *br)
  259. {
  260. struct net_bridge_port *p;
  261. list_for_each_entry(p, &br->port_list, list) {
  262. if (p->state != BR_STATE_DISABLED &&
  263. br_is_designated_port(p))
  264. br_transmit_config(p);
  265. }
  266. }
  267. /* called under bridge lock */
  268. static inline void br_reply(struct net_bridge_port *p)
  269. {
  270. br_transmit_config(p);
  271. }
  272. /* called under bridge lock */
  273. void br_configuration_update(struct net_bridge *br)
  274. {
  275. br_root_selection(br);
  276. br_designated_port_selection(br);
  277. }
  278. /* called under bridge lock */
  279. void br_become_designated_port(struct net_bridge_port *p)
  280. {
  281. struct net_bridge *br;
  282. br = p->br;
  283. p->designated_root = br->designated_root;
  284. p->designated_cost = br->root_path_cost;
  285. p->designated_bridge = br->bridge_id;
  286. p->designated_port = p->port_id;
  287. }
  288. /* called under bridge lock */
  289. static void br_make_blocking(struct net_bridge_port *p)
  290. {
  291. if (p->state != BR_STATE_DISABLED &&
  292. p->state != BR_STATE_BLOCKING) {
  293. if (p->state == BR_STATE_FORWARDING ||
  294. p->state == BR_STATE_LEARNING)
  295. br_topology_change_detection(p->br);
  296. p->state = BR_STATE_BLOCKING;
  297. br_log_state(p);
  298. del_timer(&p->forward_delay_timer);
  299. }
  300. }
  301. /* called under bridge lock */
  302. static void br_make_forwarding(struct net_bridge_port *p)
  303. {
  304. if (p->state == BR_STATE_BLOCKING) {
  305. if (p->br->stp_enabled) {
  306. p->state = BR_STATE_LISTENING;
  307. } else {
  308. p->state = BR_STATE_LEARNING;
  309. }
  310. br_log_state(p);
  311. mod_timer(&p->forward_delay_timer, jiffies + p->br->forward_delay); }
  312. }
  313. /* called under bridge lock */
  314. void br_port_state_selection(struct net_bridge *br)
  315. {
  316. struct net_bridge_port *p;
  317. list_for_each_entry(p, &br->port_list, list) {
  318. if (p->state != BR_STATE_DISABLED) {
  319. if (p->port_no == br->root_port) {
  320. p->config_pending = 0;
  321. p->topology_change_ack = 0;
  322. br_make_forwarding(p);
  323. } else if (br_is_designated_port(p)) {
  324. del_timer(&p->message_age_timer);
  325. br_make_forwarding(p);
  326. } else {
  327. p->config_pending = 0;
  328. p->topology_change_ack = 0;
  329. br_make_blocking(p);
  330. }
  331. }
  332. }
  333. }
  334. /* called under bridge lock */
  335. static inline void br_topology_change_acknowledge(struct net_bridge_port *p)
  336. {
  337. p->topology_change_ack = 1;
  338. br_transmit_config(p);
  339. }
  340. /* called under bridge lock */
  341. void br_received_config_bpdu(struct net_bridge_port *p, struct br_config_bpdu *bpdu)
  342. {
  343. struct net_bridge *br;
  344. int was_root;
  345. br = p->br;
  346. was_root = br_is_root_bridge(br);
  347. if (br_supersedes_port_info(p, bpdu)) {
  348. br_record_config_information(p, bpdu);
  349. br_configuration_update(br);
  350. br_port_state_selection(br);
  351. if (!br_is_root_bridge(br) && was_root) {
  352. del_timer(&br->hello_timer);
  353. if (br->topology_change_detected) {
  354. del_timer(&br->topology_change_timer);
  355. br_transmit_tcn(br);
  356. mod_timer(&br->tcn_timer,
  357. jiffies + br->bridge_hello_time);
  358. }
  359. }
  360. if (p->port_no == br->root_port) {
  361. br_record_config_timeout_values(br, bpdu);
  362. br_config_bpdu_generation(br);
  363. if (bpdu->topology_change_ack)
  364. br_topology_change_acknowledged(br);
  365. }
  366. } else if (br_is_designated_port(p)) {
  367. br_reply(p);
  368. }
  369. }
  370. /* called under bridge lock */
  371. void br_received_tcn_bpdu(struct net_bridge_port *p)
  372. {
  373. if (br_is_designated_port(p)) {
  374. pr_info("%s: received tcn bpdu on port %i(%s)\n",
  375. p->br->dev->name, p->port_no, p->dev->name);
  376. br_topology_change_detection(p->br);
  377. br_topology_change_acknowledge(p);
  378. }
  379. }