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