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