rib.h 16 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629
  1. /*
  2. * Routing Information Base header
  3. * Copyright (C) 1997 Kunihiro Ishiguro
  4. *
  5. * This file is part of GNU Zebra.
  6. *
  7. * GNU Zebra is free software; you can redistribute it and/or modify it
  8. * under the terms of the GNU General Public License as published by the
  9. * Free Software Foundation; either version 2, or (at your option) any
  10. * later version.
  11. *
  12. * GNU Zebra is distributed in the hope that it will be useful, but
  13. * WITHOUT ANY WARRANTY; without even the implied warranty of
  14. * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  15. * General Public License for more details.
  16. *
  17. * You should have received a copy of the GNU General Public License
  18. * along with GNU Zebra; see the file COPYING. If not, write to the Free
  19. * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
  20. * 02111-1307, USA.
  21. */
  22. #ifndef _ZEBRA_RIB_H
  23. #define _ZEBRA_RIB_H
  24. #include "linklist.h"
  25. #include "prefix.h"
  26. #include "table.h"
  27. #include "queue.h"
  28. #define DISTANCE_INFINITY 255
  29. /* Routing information base. */
  30. union g_addr {
  31. struct in_addr ipv4;
  32. #ifdef HAVE_IPV6
  33. struct in6_addr ipv6;
  34. #endif /* HAVE_IPV6 */
  35. };
  36. struct rib
  37. {
  38. /* Link list. */
  39. struct rib *next;
  40. struct rib *prev;
  41. /* Nexthop structure */
  42. struct nexthop *nexthop;
  43. /* Refrence count. */
  44. unsigned long refcnt;
  45. /* Uptime. */
  46. time_t uptime;
  47. /* Type fo this route. */
  48. int type;
  49. /* VRF identifier. */
  50. vrf_id_t vrf_id;
  51. /* Which routing table */
  52. int table;
  53. /* Metric */
  54. u_int32_t metric;
  55. /* Distance. */
  56. u_char distance;
  57. /* Flags of this route.
  58. * This flag's definition is in lib/zebra.h ZEBRA_FLAG_* and is exposed
  59. * to clients via Zserv
  60. */
  61. u_char flags;
  62. /* RIB internal status */
  63. u_char status;
  64. #define RIB_ENTRY_REMOVED (1 << 0)
  65. /* Nexthop information. */
  66. u_char nexthop_num;
  67. u_char nexthop_active_num;
  68. u_char nexthop_fib_num;
  69. };
  70. /* meta-queue structure:
  71. * sub-queue 0: connected, kernel
  72. * sub-queue 1: static
  73. * sub-queue 2: RIP, RIPng, OSPF, OSPF6, IS-IS
  74. * sub-queue 3: iBGP, eBGP
  75. * sub-queue 4: any other origin (if any)
  76. */
  77. #define MQ_SIZE 5
  78. struct meta_queue
  79. {
  80. struct list *subq[MQ_SIZE];
  81. u_int32_t size; /* sum of lengths of all subqueues */
  82. };
  83. /*
  84. * Structure that represents a single destination (prefix).
  85. */
  86. typedef struct rib_dest_t_
  87. {
  88. /*
  89. * Back pointer to the route node for this destination. This helps
  90. * us get to the prefix that this structure is for.
  91. */
  92. struct route_node *rnode;
  93. /*
  94. * Doubly-linked list of routes for this prefix.
  95. */
  96. struct rib *routes;
  97. /*
  98. * Flags, see below.
  99. */
  100. u_int32_t flags;
  101. /*
  102. * Linkage to put dest on the FPM processing queue.
  103. */
  104. TAILQ_ENTRY(rib_dest_t_) fpm_q_entries;
  105. } rib_dest_t;
  106. #define RIB_ROUTE_QUEUED(x) (1 << (x))
  107. /*
  108. * The maximum qindex that can be used.
  109. */
  110. #define ZEBRA_MAX_QINDEX (MQ_SIZE - 1)
  111. /*
  112. * This flag indicates that a given prefix has been 'advertised' to
  113. * the FPM to be installed in the forwarding plane.
  114. */
  115. #define RIB_DEST_SENT_TO_FPM (1 << (ZEBRA_MAX_QINDEX + 1))
  116. /*
  117. * This flag is set when we need to send an update to the FPM about a
  118. * dest.
  119. */
  120. #define RIB_DEST_UPDATE_FPM (1 << (ZEBRA_MAX_QINDEX + 2))
  121. /*
  122. * Macro to iterate over each route for a destination (prefix).
  123. */
  124. #define RIB_DEST_FOREACH_ROUTE(dest, rib) \
  125. for ((rib) = (dest) ? (dest)->routes : NULL; (rib); (rib) = (rib)->next)
  126. /*
  127. * Same as above, but allows the current node to be unlinked.
  128. */
  129. #define RIB_DEST_FOREACH_ROUTE_SAFE(dest, rib, next) \
  130. for ((rib) = (dest) ? (dest)->routes : NULL; \
  131. (rib) && ((next) = (rib)->next, 1); \
  132. (rib) = (next))
  133. #define RNODE_FOREACH_RIB(rn, rib) \
  134. RIB_DEST_FOREACH_ROUTE (rib_dest_from_rnode (rn), rib)
  135. #define RNODE_FOREACH_RIB_SAFE(rn, rib, next) \
  136. RIB_DEST_FOREACH_ROUTE_SAFE (rib_dest_from_rnode (rn), rib, next)
  137. /* Static route information. */
  138. struct static_ipv4
  139. {
  140. /* For linked list. */
  141. struct static_ipv4 *prev;
  142. struct static_ipv4 *next;
  143. /* VRF identifier. */
  144. vrf_id_t vrf_id;
  145. /* Administrative distance. */
  146. u_char distance;
  147. /* Flag for this static route's type. */
  148. u_char type;
  149. #define STATIC_IPV4_GATEWAY 1
  150. #define STATIC_IPV4_IFNAME 2
  151. #define STATIC_IPV4_BLACKHOLE 3
  152. /* Nexthop value. */
  153. union
  154. {
  155. struct in_addr ipv4;
  156. char *ifname;
  157. } gate;
  158. /* bit flags */
  159. u_char flags;
  160. /*
  161. see ZEBRA_FLAG_REJECT
  162. ZEBRA_FLAG_BLACKHOLE
  163. */
  164. };
  165. #ifdef HAVE_IPV6
  166. /* Static route information. */
  167. struct static_ipv6
  168. {
  169. /* For linked list. */
  170. struct static_ipv6 *prev;
  171. struct static_ipv6 *next;
  172. /* VRF identifier. */
  173. vrf_id_t vrf_id;
  174. /* Administrative distance. */
  175. u_char distance;
  176. /* Flag for this static route's type. */
  177. u_char type;
  178. #define STATIC_IPV6_GATEWAY 1
  179. #define STATIC_IPV6_GATEWAY_IFNAME 2
  180. #define STATIC_IPV6_IFNAME 3
  181. /* Nexthop value. */
  182. struct in6_addr ipv6;
  183. char *ifname;
  184. /* bit flags */
  185. u_char flags;
  186. /*
  187. see ZEBRA_FLAG_REJECT
  188. ZEBRA_FLAG_BLACKHOLE
  189. */
  190. };
  191. #endif /* HAVE_IPV6 */
  192. enum nexthop_types_t
  193. {
  194. NEXTHOP_TYPE_IFINDEX = 1, /* Directly connected. */
  195. NEXTHOP_TYPE_IFNAME, /* Interface route. */
  196. NEXTHOP_TYPE_IPV4, /* IPv4 nexthop. */
  197. NEXTHOP_TYPE_IPV4_IFINDEX, /* IPv4 nexthop with ifindex. */
  198. NEXTHOP_TYPE_IPV4_IFNAME, /* IPv4 nexthop with ifname. */
  199. NEXTHOP_TYPE_IPV6, /* IPv6 nexthop. */
  200. NEXTHOP_TYPE_IPV6_IFINDEX, /* IPv6 nexthop with ifindex. */
  201. NEXTHOP_TYPE_IPV6_IFNAME, /* IPv6 nexthop with ifname. */
  202. NEXTHOP_TYPE_BLACKHOLE, /* Null0 nexthop. */
  203. };
  204. /* Nexthop structure. */
  205. struct nexthop
  206. {
  207. struct nexthop *next;
  208. struct nexthop *prev;
  209. /* Interface index. */
  210. char *ifname;
  211. unsigned int ifindex;
  212. enum nexthop_types_t type;
  213. u_char flags;
  214. #define NEXTHOP_FLAG_ACTIVE (1 << 0) /* This nexthop is alive. */
  215. #define NEXTHOP_FLAG_FIB (1 << 1) /* FIB nexthop. */
  216. #define NEXTHOP_FLAG_RECURSIVE (1 << 2) /* Recursive nexthop. */
  217. #define NEXTHOP_FLAG_ONLINK (1 << 3) /* Nexthop should be installed onlink. */
  218. /* Nexthop address */
  219. union g_addr gate;
  220. union g_addr src;
  221. /* Nexthops obtained by recursive resolution.
  222. *
  223. * If the nexthop struct needs to be resolved recursively,
  224. * NEXTHOP_FLAG_RECURSIVE will be set in flags and the nexthops
  225. * obtained by recursive resolution will be added to `resolved'.
  226. * Only one level of recursive resolution is currently supported. */
  227. struct nexthop *resolved;
  228. };
  229. /* The following for loop allows to iterate over the nexthop
  230. * structure of routes.
  231. *
  232. * We have to maintain quite a bit of state:
  233. *
  234. * nexthop: The pointer to the current nexthop, either in the
  235. * top-level chain or in the resolved chain of ni.
  236. * tnexthop: The pointer to the current nexthop in the top-level
  237. * nexthop chain.
  238. * recursing: Information if nh currently is in the top-level chain
  239. * (0) or in a resolved chain (1).
  240. *
  241. * Initialization: Set `nexthop' and `tnexthop' to the head of the
  242. * top-level chain. As nexthop is in the top level chain, set recursing
  243. * to 0.
  244. *
  245. * Iteration check: Check that the `nexthop' pointer is not NULL.
  246. *
  247. * Iteration step: This is the tricky part. Check if `nexthop' has
  248. * NEXTHOP_FLAG_RECURSIVE set. If yes, this implies that `nexthop' is in
  249. * the top level chain and has at least one nexthop attached to
  250. * `nexthop->resolved'. As we want to descend into `nexthop->resolved',
  251. * set `recursing' to 1 and set `nexthop' to `nexthop->resolved'.
  252. * `tnexthop' is left alone in that case so we can remember which nexthop
  253. * in the top level chain we are currently handling.
  254. *
  255. * If NEXTHOP_FLAG_RECURSIVE is not set, `nexthop' will progress in its
  256. * current chain. If we are recursing, `nexthop' will be set to
  257. * `nexthop->next' and `tnexthop' will be left alone. If we are not
  258. * recursing, both `tnexthop' and `nexthop' will be set to `nexthop->next'
  259. * as we are progressing in the top level chain.
  260. * If we encounter `nexthop->next == NULL', we will clear the `recursing'
  261. * flag as we arived either at the end of the resolved chain or at the end
  262. * of the top level chain. In both cases, we set `tnexthop' and `nexthop'
  263. * to `tnexthop->next', progressing to the next position in the top-level
  264. * chain and possibly to its end marked by NULL.
  265. */
  266. #define ALL_NEXTHOPS_RO(head, nexthop, tnexthop, recursing) \
  267. (tnexthop) = (nexthop) = (head), (recursing) = 0; \
  268. (nexthop); \
  269. (nexthop) = CHECK_FLAG((nexthop)->flags, NEXTHOP_FLAG_RECURSIVE) \
  270. ? (((recursing) = 1), (nexthop)->resolved) \
  271. : ((nexthop)->next ? ((recursing) ? (nexthop)->next \
  272. : ((tnexthop) = (nexthop)->next)) \
  273. : (((recursing) = 0),((tnexthop) = (tnexthop)->next)))
  274. /* Structure holding nexthop & VRF identifier,
  275. * used for applying the route-map. */
  276. struct nexthop_vrfid
  277. {
  278. struct nexthop *nexthop;
  279. vrf_id_t vrf_id;
  280. };
  281. /* Routing table instance. */
  282. struct zebra_vrf
  283. {
  284. /* Identifier. */
  285. vrf_id_t vrf_id;
  286. /* Routing table name. */
  287. char *name;
  288. /* Description. */
  289. char *desc;
  290. /* FIB identifier. */
  291. u_char fib_id;
  292. /* Routing table. */
  293. struct route_table *table[AFI_MAX][SAFI_MAX];
  294. /* Static route configuration. */
  295. struct route_table *stable[AFI_MAX][SAFI_MAX];
  296. /* 2nd pointer type used primarily to quell a warning on
  297. * ALL_LIST_ELEMENTS_RO
  298. */
  299. struct list _rid_all_sorted_list;
  300. struct list _rid_lo_sorted_list;
  301. struct list *rid_all_sorted_list;
  302. struct list *rid_lo_sorted_list;
  303. struct prefix rid_user_assigned;
  304. };
  305. /*
  306. * rib_table_info_t
  307. *
  308. * Structure that is hung off of a route_table that holds information about
  309. * the table.
  310. */
  311. typedef struct rib_table_info_t_
  312. {
  313. /*
  314. * Back pointer to zebra_vrf.
  315. */
  316. struct zebra_vrf *zvrf;
  317. afi_t afi;
  318. safi_t safi;
  319. } rib_table_info_t;
  320. typedef enum
  321. {
  322. RIB_TABLES_ITER_S_INIT,
  323. RIB_TABLES_ITER_S_ITERATING,
  324. RIB_TABLES_ITER_S_DONE
  325. } rib_tables_iter_state_t;
  326. /*
  327. * Structure that holds state for iterating over all tables in the
  328. * Routing Information Base.
  329. */
  330. typedef struct rib_tables_iter_t_
  331. {
  332. vrf_id_t vrf_id;
  333. int afi_safi_ix;
  334. rib_tables_iter_state_t state;
  335. } rib_tables_iter_t;
  336. /* RPF lookup behaviour */
  337. enum multicast_mode
  338. {
  339. MCAST_NO_CONFIG = 0, /* MIX_MRIB_FIRST, but no show in config write */
  340. MCAST_MRIB_ONLY, /* MRIB only */
  341. MCAST_URIB_ONLY, /* URIB only */
  342. MCAST_MIX_MRIB_FIRST, /* MRIB, if nothing at all then URIB */
  343. MCAST_MIX_DISTANCE, /* MRIB & URIB, lower distance wins */
  344. MCAST_MIX_PFXLEN, /* MRIB & URIB, longer prefix wins */
  345. /* on equal value, MRIB wins for last 2 */
  346. };
  347. extern void multicast_mode_ipv4_set (enum multicast_mode mode);
  348. extern enum multicast_mode multicast_mode_ipv4_get (void);
  349. extern const char *nexthop_type_to_str (enum nexthop_types_t nh_type);
  350. extern struct nexthop *nexthop_ifindex_add (struct rib *, unsigned int);
  351. extern struct nexthop *nexthop_ifname_add (struct rib *, char *);
  352. extern struct nexthop *nexthop_blackhole_add (struct rib *);
  353. extern struct nexthop *nexthop_ipv4_add (struct rib *, struct in_addr *,
  354. struct in_addr *);
  355. extern struct nexthop *nexthop_ipv4_ifindex_add (struct rib *,
  356. struct in_addr *,
  357. struct in_addr *,
  358. unsigned int);
  359. extern int nexthop_has_fib_child(struct nexthop *);
  360. extern void rib_lookup_and_dump (struct prefix_ipv4 *);
  361. extern void rib_lookup_and_pushup (struct prefix_ipv4 *);
  362. #define rib_dump(prefix ,rib) _rib_dump(__func__, prefix, rib)
  363. extern void _rib_dump (const char *,
  364. union prefix46constptr, const struct rib *);
  365. extern int rib_lookup_ipv4_route (struct prefix_ipv4 *, union sockunion *,
  366. vrf_id_t);
  367. #define ZEBRA_RIB_LOOKUP_ERROR -1
  368. #define ZEBRA_RIB_FOUND_EXACT 0
  369. #define ZEBRA_RIB_FOUND_NOGATE 1
  370. #define ZEBRA_RIB_FOUND_CONNECTED 2
  371. #define ZEBRA_RIB_NOTFOUND 3
  372. #ifdef HAVE_IPV6
  373. extern struct nexthop *nexthop_ipv6_add (struct rib *, struct in6_addr *);
  374. #endif /* HAVE_IPV6 */
  375. extern struct zebra_vrf *zebra_vrf_alloc (vrf_id_t);
  376. extern struct route_table *zebra_vrf_table (afi_t, safi_t, vrf_id_t);
  377. extern struct route_table *zebra_vrf_static_table (afi_t, safi_t, vrf_id_t);
  378. /* NOTE:
  379. * All rib_add_ipv[46]* functions will not just add prefix into RIB, but
  380. * also implicitly withdraw equal prefix of same type. */
  381. extern int rib_add_ipv4 (int type, int flags, struct prefix_ipv4 *p,
  382. struct in_addr *gate, struct in_addr *src,
  383. unsigned int ifindex, vrf_id_t vrf_id, int table_id,
  384. u_int32_t, u_char, safi_t);
  385. extern int rib_add_ipv4_multipath (struct prefix_ipv4 *, struct rib *, safi_t);
  386. extern int rib_delete_ipv4 (int type, int flags, struct prefix_ipv4 *p,
  387. struct in_addr *gate, unsigned int ifindex,
  388. vrf_id_t, safi_t safi);
  389. extern struct rib *rib_match_ipv4_safi (struct in_addr addr, safi_t safi,
  390. int skip_bgp, struct route_node **rn_out,
  391. vrf_id_t);
  392. extern struct rib *rib_match_ipv4_multicast (struct in_addr addr,
  393. struct route_node **rn_out,
  394. vrf_id_t);
  395. extern struct rib *rib_lookup_ipv4 (struct prefix_ipv4 *, vrf_id_t);
  396. extern void rib_update (vrf_id_t);
  397. extern void rib_weed_tables (void);
  398. extern void rib_sweep_route (void);
  399. extern void rib_close_table (struct route_table *);
  400. extern void rib_close (void);
  401. extern void rib_init (void);
  402. extern unsigned long rib_score_proto (u_char proto);
  403. extern int
  404. static_add_ipv4_safi (safi_t safi, struct prefix *p, struct in_addr *gate,
  405. const char *ifname, u_char flags, u_char distance,
  406. vrf_id_t vrf_id);
  407. extern int
  408. static_delete_ipv4_safi (safi_t safi, struct prefix *p, struct in_addr *gate,
  409. const char *ifname, u_char distance, vrf_id_t vrf_id);
  410. #ifdef HAVE_IPV6
  411. extern int
  412. rib_add_ipv6 (int type, int flags, struct prefix_ipv6 *p,
  413. struct in6_addr *gate, unsigned int ifindex, vrf_id_t vrf_id,
  414. int table_id, u_int32_t metric, u_char distance, safi_t safi);
  415. extern int
  416. rib_delete_ipv6 (int type, int flags, struct prefix_ipv6 *p,
  417. struct in6_addr *gate, unsigned int ifindex, vrf_id_t vrf_id, safi_t safi);
  418. extern struct rib *rib_lookup_ipv6 (struct in6_addr *, vrf_id_t);
  419. extern struct rib *rib_match_ipv6 (struct in6_addr *, vrf_id_t);
  420. extern struct route_table *rib_table_ipv6;
  421. extern int
  422. static_add_ipv6 (struct prefix *p, u_char type, struct in6_addr *gate,
  423. const char *ifname, u_char flags, u_char distance,
  424. vrf_id_t vrf_id);
  425. extern int
  426. static_delete_ipv6 (struct prefix *p, u_char type, struct in6_addr *gate,
  427. const char *ifname, u_char distance, vrf_id_t vrf_id);
  428. #endif /* HAVE_IPV6 */
  429. extern int rib_gc_dest (struct route_node *rn);
  430. extern struct route_table *rib_tables_iter_next (rib_tables_iter_t *iter);
  431. /*
  432. * Inline functions.
  433. */
  434. /*
  435. * rib_table_info
  436. */
  437. static inline rib_table_info_t *
  438. rib_table_info (struct route_table *table)
  439. {
  440. return (rib_table_info_t *) table->info;
  441. }
  442. /*
  443. * rib_dest_from_rnode
  444. */
  445. static inline rib_dest_t *
  446. rib_dest_from_rnode (struct route_node *rn)
  447. {
  448. return (rib_dest_t *) rn->info;
  449. }
  450. /*
  451. * rnode_to_ribs
  452. *
  453. * Returns a pointer to the list of routes corresponding to the given
  454. * route_node.
  455. */
  456. static inline struct rib *
  457. rnode_to_ribs (struct route_node *rn)
  458. {
  459. rib_dest_t *dest;
  460. dest = rib_dest_from_rnode (rn);
  461. if (!dest)
  462. return NULL;
  463. return dest->routes;
  464. }
  465. /*
  466. * rib_dest_prefix
  467. */
  468. static inline struct prefix *
  469. rib_dest_prefix (rib_dest_t *dest)
  470. {
  471. return &dest->rnode->p;
  472. }
  473. /*
  474. * rib_dest_af
  475. *
  476. * Returns the address family that the destination is for.
  477. */
  478. static inline u_char
  479. rib_dest_af (rib_dest_t *dest)
  480. {
  481. return dest->rnode->p.family;
  482. }
  483. /*
  484. * rib_dest_table
  485. */
  486. static inline struct route_table *
  487. rib_dest_table (rib_dest_t *dest)
  488. {
  489. return dest->rnode->table;
  490. }
  491. /*
  492. * rib_dest_vrf
  493. */
  494. static inline struct zebra_vrf *
  495. rib_dest_vrf (rib_dest_t *dest)
  496. {
  497. return rib_table_info (rib_dest_table (dest))->zvrf;
  498. }
  499. /*
  500. * rib_tables_iter_init
  501. */
  502. static inline void
  503. rib_tables_iter_init (rib_tables_iter_t *iter)
  504. {
  505. memset (iter, 0, sizeof (*iter));
  506. iter->state = RIB_TABLES_ITER_S_INIT;
  507. }
  508. /*
  509. * rib_tables_iter_started
  510. *
  511. * Returns TRUE if this iterator has started iterating over the set of
  512. * tables.
  513. */
  514. static inline int
  515. rib_tables_iter_started (rib_tables_iter_t *iter)
  516. {
  517. return iter->state != RIB_TABLES_ITER_S_INIT;
  518. }
  519. /*
  520. * rib_tables_iter_cleanup
  521. */
  522. static inline void
  523. rib_tables_iter_cleanup (rib_tables_iter_t *iter)
  524. {
  525. iter->state = RIB_TABLES_ITER_S_DONE;
  526. }
  527. #endif /*_ZEBRA_RIB_H */