pim_macro.c 12 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438
  1. /*
  2. PIM for Quagga
  3. Copyright (C) 2008 Everton da Silva Marques
  4. This program is free software; you can redistribute it and/or modify
  5. it under the terms of the GNU General Public License as published by
  6. the Free Software Foundation; either version 2 of the License, or
  7. (at your option) any later version.
  8. This program is distributed in the hope that it will be useful, but
  9. WITHOUT ANY WARRANTY; without even the implied warranty of
  10. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  11. General Public License for more details.
  12. You should have received a copy of the GNU General Public License
  13. along with this program; see the file COPYING; if not, write to the
  14. Free Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston,
  15. MA 02110-1301 USA
  16. $QuaggaId: $Format:%an, %ai, %h$ $
  17. */
  18. #include <zebra.h>
  19. #include "log.h"
  20. #include "pim_macro.h"
  21. #include "pimd.h"
  22. #include "pim_str.h"
  23. #include "pim_iface.h"
  24. #include "pim_ifchannel.h"
  25. #define PIM_IFP_I_am_DR(pim_ifp) ((pim_ifp)->pim_dr_addr.s_addr == (pim_ifp)->primary_address.s_addr)
  26. /*
  27. DownstreamJPState(S,G,I) is the per-interface state machine for
  28. receiving (S,G) Join/Prune messages.
  29. DownstreamJPState(S,G,I) is either Join or Prune-Pending ?
  30. */
  31. static int downstream_jpstate_isjoined(const struct pim_ifchannel *ch)
  32. {
  33. return ch->ifjoin_state != PIM_IFJOIN_NOINFO;
  34. }
  35. /*
  36. The clause "local_receiver_include(S,G,I)" is true if the IGMP/MLD
  37. module or other local membership mechanism has determined that local
  38. members on interface I desire to receive traffic sent specifically
  39. by S to G.
  40. */
  41. static int local_receiver_include(const struct pim_ifchannel *ch)
  42. {
  43. /* local_receiver_include(S,G,I) ? */
  44. return ch->local_ifmembership == PIM_IFMEMBERSHIP_INCLUDE;
  45. }
  46. /*
  47. RFC 4601: 4.1.6. State Summarization Macros
  48. The set "joins(S,G)" is the set of all interfaces on which the
  49. router has received (S,G) Joins:
  50. joins(S,G) =
  51. { all interfaces I such that
  52. DownstreamJPState(S,G,I) is either Join or Prune-Pending }
  53. DownstreamJPState(S,G,I) is either Join or Prune-Pending ?
  54. */
  55. int pim_macro_chisin_joins(const struct pim_ifchannel *ch)
  56. {
  57. return downstream_jpstate_isjoined(ch);
  58. }
  59. /*
  60. RFC 4601: 4.6.5. Assert State Macros
  61. The set "lost_assert(S,G)" is the set of all interfaces on which the
  62. router has received (S,G) joins but has lost an (S,G) assert.
  63. lost_assert(S,G) =
  64. { all interfaces I such that
  65. lost_assert(S,G,I) == TRUE }
  66. bool lost_assert(S,G,I) {
  67. if ( RPF_interface(S) == I ) {
  68. return FALSE
  69. } else {
  70. return ( AssertWinner(S,G,I) != NULL AND
  71. AssertWinner(S,G,I) != me AND
  72. (AssertWinnerMetric(S,G,I) is better
  73. than spt_assert_metric(S,I) )
  74. }
  75. }
  76. AssertWinner(S,G,I) is the IP source address of the Assert(S,G)
  77. packet that won an Assert.
  78. */
  79. int pim_macro_ch_lost_assert(const struct pim_ifchannel *ch)
  80. {
  81. struct interface *ifp;
  82. struct pim_interface *pim_ifp;
  83. struct pim_assert_metric spt_assert_metric;
  84. ifp = ch->interface;
  85. if (!ifp) {
  86. char src_str[100];
  87. char grp_str[100];
  88. pim_inet4_dump("<src?>", ch->source_addr, src_str, sizeof(src_str));
  89. pim_inet4_dump("<grp?>", ch->group_addr, grp_str, sizeof(grp_str));
  90. zlog_warn("%s: (S,G)=(%s,%s): null interface",
  91. __PRETTY_FUNCTION__,
  92. src_str, grp_str);
  93. return 0; /* false */
  94. }
  95. /* RPF_interface(S) == I ? */
  96. if (ch->upstream->rpf.source_nexthop.interface == ifp)
  97. return 0; /* false */
  98. pim_ifp = ifp->info;
  99. if (!pim_ifp) {
  100. char src_str[100];
  101. char grp_str[100];
  102. pim_inet4_dump("<src?>", ch->source_addr, src_str, sizeof(src_str));
  103. pim_inet4_dump("<grp?>", ch->group_addr, grp_str, sizeof(grp_str));
  104. zlog_warn("%s: (S,G)=(%s,%s): multicast not enabled on interface %s",
  105. __PRETTY_FUNCTION__,
  106. src_str, grp_str, ifp->name);
  107. return 0; /* false */
  108. }
  109. if (PIM_INADDR_IS_ANY(ch->ifassert_winner))
  110. return 0; /* false */
  111. /* AssertWinner(S,G,I) == me ? */
  112. if (ch->ifassert_winner.s_addr == pim_ifp->primary_address.s_addr)
  113. return 0; /* false */
  114. spt_assert_metric = pim_macro_spt_assert_metric(&ch->upstream->rpf,
  115. pim_ifp->primary_address);
  116. return pim_assert_metric_better(&ch->ifassert_winner_metric,
  117. &spt_assert_metric);
  118. }
  119. /*
  120. RFC 4601: 4.1.6. State Summarization Macros
  121. pim_include(S,G) =
  122. { all interfaces I such that:
  123. ( (I_am_DR( I ) AND lost_assert(S,G,I) == FALSE )
  124. OR AssertWinner(S,G,I) == me )
  125. AND local_receiver_include(S,G,I) }
  126. AssertWinner(S,G,I) is the IP source address of the Assert(S,G)
  127. packet that won an Assert.
  128. */
  129. int pim_macro_chisin_pim_include(const struct pim_ifchannel *ch)
  130. {
  131. struct pim_interface *pim_ifp = ch->interface->info;
  132. if (!pim_ifp) {
  133. char src_str[100];
  134. char grp_str[100];
  135. pim_inet4_dump("<src?>", ch->source_addr, src_str, sizeof(src_str));
  136. pim_inet4_dump("<grp?>", ch->group_addr, grp_str, sizeof(grp_str));
  137. zlog_warn("%s: (S,G)=(%s,%s): multicast not enabled on interface %s",
  138. __PRETTY_FUNCTION__,
  139. src_str, grp_str, ch->interface->name);
  140. return 0; /* false */
  141. }
  142. /* local_receiver_include(S,G,I) ? */
  143. if (!local_receiver_include(ch))
  144. return 0; /* false */
  145. /* OR AssertWinner(S,G,I) == me ? */
  146. if (ch->ifassert_winner.s_addr == pim_ifp->primary_address.s_addr)
  147. return 1; /* true */
  148. return (
  149. /* I_am_DR( I ) ? */
  150. PIM_IFP_I_am_DR(pim_ifp)
  151. &&
  152. /* lost_assert(S,G,I) == FALSE ? */
  153. (!pim_macro_ch_lost_assert(ch))
  154. );
  155. }
  156. int pim_macro_chisin_joins_or_include(const struct pim_ifchannel *ch)
  157. {
  158. if (pim_macro_chisin_joins(ch))
  159. return 1; /* true */
  160. return pim_macro_chisin_pim_include(ch);
  161. }
  162. /*
  163. RFC 4601: 4.6.1. (S,G) Assert Message State Machine
  164. CouldAssert(S,G,I) =
  165. SPTbit(S,G)==TRUE
  166. AND (RPF_interface(S) != I)
  167. AND (I in ( ( joins(*,*,RP(G)) (+) joins(*,G) (-) prunes(S,G,rpt) )
  168. (+) ( pim_include(*,G) (-) pim_exclude(S,G) )
  169. (-) lost_assert(*,G)
  170. (+) joins(S,G) (+) pim_include(S,G) ) )
  171. CouldAssert(S,G,I) is true for downstream interfaces that would be in
  172. the inherited_olist(S,G) if (S,G) assert information was not taken
  173. into account.
  174. CouldAssert(S,G,I) may be affected by changes in the following:
  175. pim_ifp->primary_address
  176. pim_ifp->pim_dr_addr
  177. ch->ifassert_winner_metric
  178. ch->ifassert_winner
  179. ch->local_ifmembership
  180. ch->ifjoin_state
  181. ch->upstream->rpf.source_nexthop.mrib_metric_preference
  182. ch->upstream->rpf.source_nexthop.mrib_route_metric
  183. ch->upstream->rpf.source_nexthop.interface
  184. */
  185. int pim_macro_ch_could_assert_eval(const struct pim_ifchannel *ch)
  186. {
  187. struct interface *ifp;
  188. /* SPTbit(S,G) is always true for PIM-SSM-Only Routers */
  189. ifp = ch->interface;
  190. if (!ifp) {
  191. char src_str[100];
  192. char grp_str[100];
  193. pim_inet4_dump("<src?>", ch->source_addr, src_str, sizeof(src_str));
  194. pim_inet4_dump("<grp?>", ch->group_addr, grp_str, sizeof(grp_str));
  195. zlog_warn("%s: (S,G)=(%s,%s): null interface",
  196. __PRETTY_FUNCTION__,
  197. src_str, grp_str);
  198. return 0; /* false */
  199. }
  200. /* RPF_interface(S) != I ? */
  201. if (ch->upstream->rpf.source_nexthop.interface == ifp)
  202. return 0; /* false */
  203. /* I in joins(S,G) (+) pim_include(S,G) ? */
  204. return pim_macro_chisin_joins_or_include(ch);
  205. }
  206. /*
  207. RFC 4601: 4.6.3. Assert Metrics
  208. spt_assert_metric(S,I) gives the assert metric we use if we're
  209. sending an assert based on active (S,G) forwarding state:
  210. assert_metric
  211. spt_assert_metric(S,I) {
  212. return {0,MRIB.pref(S),MRIB.metric(S),my_ip_address(I)}
  213. }
  214. */
  215. struct pim_assert_metric pim_macro_spt_assert_metric(const struct pim_rpf *rpf,
  216. struct in_addr ifaddr)
  217. {
  218. struct pim_assert_metric metric;
  219. metric.rpt_bit_flag = 0;
  220. metric.metric_preference = rpf->source_nexthop.mrib_metric_preference;
  221. metric.route_metric = rpf->source_nexthop.mrib_route_metric;
  222. metric.ip_address = ifaddr;
  223. return metric;
  224. }
  225. /*
  226. RFC 4601: 4.6.3. Assert Metrics
  227. An assert metric for (S,G) to include in (or compare against) an
  228. Assert message sent on interface I should be computed using the
  229. following pseudocode:
  230. assert_metric my_assert_metric(S,G,I) {
  231. if( CouldAssert(S,G,I) == TRUE ) {
  232. return spt_assert_metric(S,I)
  233. } else if( CouldAssert(*,G,I) == TRUE ) {
  234. return rpt_assert_metric(G,I)
  235. } else {
  236. return infinite_assert_metric()
  237. }
  238. }
  239. */
  240. struct pim_assert_metric pim_macro_ch_my_assert_metric_eval(const struct pim_ifchannel *ch)
  241. {
  242. struct pim_interface *pim_ifp;
  243. pim_ifp = ch->interface->info;
  244. if (pim_ifp) {
  245. if (PIM_IF_FLAG_TEST_COULD_ASSERT(ch->flags)) {
  246. return pim_macro_spt_assert_metric(&ch->upstream->rpf, pim_ifp->primary_address);
  247. }
  248. }
  249. return qpim_infinite_assert_metric;
  250. }
  251. /*
  252. RFC 4601 4.2. Data Packet Forwarding Rules
  253. RFC 4601 4.8.2. PIM-SSM-Only Routers
  254. Macro:
  255. inherited_olist(S,G) =
  256. joins(S,G) (+) pim_include(S,G) (-) lost_assert(S,G)
  257. */
  258. static int pim_macro_chisin_inherited_olist(const struct pim_ifchannel *ch)
  259. {
  260. if (pim_macro_ch_lost_assert(ch))
  261. return 0; /* false */
  262. return pim_macro_chisin_joins_or_include(ch);
  263. }
  264. /*
  265. RFC 4601 4.2. Data Packet Forwarding Rules
  266. RFC 4601 4.8.2. PIM-SSM-Only Routers
  267. Additionally, the Packet forwarding rules of Section 4.2 can be
  268. simplified in a PIM-SSM-only router:
  269. iif is the incoming interface of the packet.
  270. oiflist = NULL
  271. if (iif == RPF_interface(S) AND UpstreamJPState(S,G) == Joined) {
  272. oiflist = inherited_olist(S,G)
  273. } else if (iif is in inherited_olist(S,G)) {
  274. send Assert(S,G) on iif
  275. }
  276. oiflist = oiflist (-) iif
  277. forward packet on all interfaces in oiflist
  278. Macro:
  279. inherited_olist(S,G) =
  280. joins(S,G) (+) pim_include(S,G) (-) lost_assert(S,G)
  281. Note:
  282. - The following test is performed as response to WRONGVIF kernel
  283. upcall:
  284. if (iif is in inherited_olist(S,G)) {
  285. send Assert(S,G) on iif
  286. }
  287. See pim_mroute.c mroute_msg().
  288. */
  289. int pim_macro_chisin_oiflist(const struct pim_ifchannel *ch)
  290. {
  291. if (ch->upstream->join_state != PIM_UPSTREAM_JOINED) {
  292. /* oiflist is NULL */
  293. return 0; /* false */
  294. }
  295. /* oiflist = oiflist (-) iif */
  296. if (ch->interface == ch->upstream->rpf.source_nexthop.interface)
  297. return 0; /* false */
  298. return pim_macro_chisin_inherited_olist(ch);
  299. }
  300. /*
  301. RFC 4601: 4.6.1. (S,G) Assert Message State Machine
  302. AssertTrackingDesired(S,G,I) =
  303. (I in ( ( joins(*,*,RP(G)) (+) joins(*,G) (-) prunes(S,G,rpt) )
  304. (+) ( pim_include(*,G) (-) pim_exclude(S,G) )
  305. (-) lost_assert(*,G)
  306. (+) joins(S,G) ) )
  307. OR (local_receiver_include(S,G,I) == TRUE
  308. AND (I_am_DR(I) OR (AssertWinner(S,G,I) == me)))
  309. OR ((RPF_interface(S) == I) AND (JoinDesired(S,G) == TRUE))
  310. OR ((RPF_interface(RP(G)) == I) AND (JoinDesired(*,G) == TRUE)
  311. AND (SPTbit(S,G) == FALSE))
  312. AssertTrackingDesired(S,G,I) is true on any interface in which an
  313. (S,G) assert might affect our behavior.
  314. */
  315. int pim_macro_assert_tracking_desired_eval(const struct pim_ifchannel *ch)
  316. {
  317. struct pim_interface *pim_ifp;
  318. struct interface *ifp;
  319. ifp = ch->interface;
  320. if (!ifp) {
  321. char src_str[100];
  322. char grp_str[100];
  323. pim_inet4_dump("<src?>", ch->source_addr, src_str, sizeof(src_str));
  324. pim_inet4_dump("<grp?>", ch->group_addr, grp_str, sizeof(grp_str));
  325. zlog_warn("%s: (S,G)=(%s,%s): null interface",
  326. __PRETTY_FUNCTION__,
  327. src_str, grp_str);
  328. return 0; /* false */
  329. }
  330. pim_ifp = ifp->info;
  331. if (!pim_ifp) {
  332. char src_str[100];
  333. char grp_str[100];
  334. pim_inet4_dump("<src?>", ch->source_addr, src_str, sizeof(src_str));
  335. pim_inet4_dump("<grp?>", ch->group_addr, grp_str, sizeof(grp_str));
  336. zlog_warn("%s: (S,G)=(%s,%s): multicast not enabled on interface %s",
  337. __PRETTY_FUNCTION__,
  338. src_str, grp_str, ch->interface->name);
  339. return 0; /* false */
  340. }
  341. /* I in joins(S,G) ? */
  342. if (pim_macro_chisin_joins(ch))
  343. return 1; /* true */
  344. /* local_receiver_include(S,G,I) ? */
  345. if (local_receiver_include(ch)) {
  346. /* I_am_DR(I) ? */
  347. if (PIM_IFP_I_am_DR(pim_ifp))
  348. return 1; /* true */
  349. /* AssertWinner(S,G,I) == me ? */
  350. if (ch->ifassert_winner.s_addr == pim_ifp->primary_address.s_addr)
  351. return 1; /* true */
  352. }
  353. /* RPF_interface(S) == I ? */
  354. if (ch->upstream->rpf.source_nexthop.interface == ifp) {
  355. /* JoinDesired(S,G) ? */
  356. if (PIM_UPSTREAM_FLAG_TEST_DR_JOIN_DESIRED(ch->upstream->flags))
  357. return 1; /* true */
  358. }
  359. return 0; /* false */
  360. }