rib.h 16 KB

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